2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Однозначное соответсвие при повороте растровой картинки
Сообщение18.01.2016, 00:36 
Аватара пользователя


07/02/12
1403
Питер
Есть такая задача:
Рассмотрим растровое изображение, которое нужно повернуть на определенный угол.
Поворачивать будем без интерполяции (обычно такой метод называется 'по ближайшему соседу' 'nearest neighbor') - т.е. для каждого пикселя результирующей картинки выбирается один конкретный пискель исходной.
Повернуть нужно так, что бы все до единого пиксели картинки прообраза были использованы, причем один раз. Т.е. по сути нужно пронумеровать пиксели исходной и повернутой картинки так, что бы при переносе изображения попиксельно по номеру пикселя оно выглядело повернутым.
Справедливости ради стоит отметить, что размер результирующей картинки будет больше исходной и в ней будут непронумерованные пиксели, то только по краям (прямоугольник, в который вписан повернутый прямоугольник).
Какой алгоритм для решения этой задачи стоит применить?

 Профиль  
                  
 
 Re: Однозначное соответсвие при повороте растровой картинки
Сообщение18.01.2016, 00:45 
Аватара пользователя


11/06/12
10390
стихия.вздох.мюсли
Рассмотрим изображение размером два на два пикселя...

 Профиль  
                  
 
 Re: Однозначное соответсвие при повороте растровой картинки
Сообщение18.01.2016, 01:18 
Аватара пользователя


07/02/12
1403
Питер
Aritaborian в сообщении #1091643 писал(а):
Рассмотрим изображение размером два на два пикселя...

А какие проблемы? Можно пиксели и такого изображения перенумеровать. Вообще любого можно, алгоритм хочется, который дырок не оставляет. Повернутая картинка 2x2 будет правда совпадать с исходной до десятка градусов примерно, но это не страшно

 Профиль  
                  
 
 Re: Однозначное соответсвие при повороте растровой картинки
Сообщение18.01.2016, 07:53 
Заслуженный участник


27/04/09
28128
А на 45°? Расстояния между центрами пикселей в диагональной сетке как-то не очень прельщают, плюс это вообще получается две наложенные друг на друга квадратные сетки. Хотя ясное доказательство невозможности нормального расположения (допустим, под ним понимается такое, что центры пикселей дрейфуют по сравнению с точным их поворотом на не более чем какую-то величину по отношению к масштабу сетки; величину щас не прикину без бумажки) хотя бы для этого угла на ум быстро не приходит.

 Профиль  
                  
 
 Re: Однозначное соответсвие при повороте растровой картинки
Сообщение18.01.2016, 14:31 
Аватара пользователя


07/02/12
1403
Питер
arseniiv в сообщении #1091678 писал(а):
А на 45°?

Ну будет какое-то очень неточное изображение, с трудом напоминающее исходное. Растровые изображения 2x2 - это все-таки экзотика. Но изображение 200x200 будет уже довольно информативным.

-- 18.01.2016, 14:34 --

arseniiv в сообщении #1091678 писал(а):
Хотя ясное доказательство невозможности нормального расположения (допустим, под ним понимается такое, что центры пикселей дрейфуют по сравнению с точным их поворотом на не более чем какую-то величину по отношению к масштабу сетки; величину щас не прикину без бумажки) хотя бы для этого угла на ум быстро не приходит

А оно есть?
Возьмем условие, что абсолютное расстояние не должно превосходить 1 пиксель (или 2).

-- 18.01.2016, 14:41 --

У меня есть предположение, что честная повернутая сетка, в которой интегральные ошибки не накапливаются и округление четко детерминировано, не оставит дырок и выберет все пиксели по одному разу.

 Профиль  
                  
 
 Re: Однозначное соответсвие при повороте растровой картинки
Сообщение19.01.2016, 14:27 
Аватара пользователя


31/10/08
1244
Поверните на угол кратный 90 градуса, а затем на остаток угла сделайте скос на $X$ и $Y$.

 Профиль  
                  
 
 Re: Однозначное соответсвие при повороте растровой картинки
Сообщение19.01.2016, 16:18 
Аватара пользователя


07/02/12
1403
Питер
Pavia в сообщении #1092204 писал(а):
сделайте скос на $X$ и $Y$

что вы имеете в виду под скосом?
допустим, нужно повернуть на 15 градусов.
допустим, мы умеем рисовать наклонную линию на прообразе, отображая ее попиксельно в горизонтальную линию результата.
как нарисовать вторую линию, что б не было коллизий и пропущенных пикселей?

 Профиль  
                  
 
 Re: Однозначное соответсвие при повороте растровой картинки
Сообщение19.01.2016, 17:55 


27/08/14
206
Вроде у меня получилось что-то такое сделать. Программа. Для сборки нужен Qt.
Пример вращения Картинки: 15, 30, 45, 60
Позже могу написать теоретическую основу этого преобразования, пока у меня в нём где-то ошибка, но программа вроде работает правильно :D

 Профиль  
                  
 
 Re: Однозначное соответсвие при повороте растровой картинки
Сообщение19.01.2016, 18:22 
Аватара пользователя


07/02/12
1403
Питер
Progger в сообщении #1092311 писал(а):
Пример вращения

можно крутануть картинку 256x256, заполненную уникальными пикселями - например, двумя градиентами по обеим осям. тогда результат можно легко проверить и на дырки и на использование всех исходных пикселей

-- 19.01.2016, 18:28 --

Progger в сообщении #1092311 писал(а):
Вроде у меня получилось что-то такое сделать

нет, у Вас будут ошибки на округлении. хотя бы из-за того, что вы используете синус и косинус. если я все правильно понял, у Вас влоб вращается с nearest-округлением, это не годится

 Профиль  
                  
 
 Re: Однозначное соответсвие при повороте растровой картинки
Сообщение19.01.2016, 20:18 


27/08/14
206
bondkim137 в сообщении #1092323 писал(а):
нет, у Вас будут ошибки на округлении. хотя бы из-за того, что вы используете синус и косинус. если я все правильно понял, у Вас влоб вращается с nearest-округлением, это не годится
Там ничего не вращается. Используется последовательно 3 преобразования:
\begin{vmatrix}
1 & p \\
0 & 1\end{vmatrix}
\begin{vmatrix}
1 & 0 \\
q & 1\end{vmatrix}
\begin{vmatrix}
1 & p \\
0 & 1\end{vmatrix}
Каждое из них даёт однозначное соответствие, а вместе они соответствуют повороту на нужный угол. Если есть картинка для проверки, я могу её повращать - у меня только всякие jpg под рукой есть.

-- 20.01.2016, 00:56 --

Необходимо выполнить преобразование поворота:
\begin{vmatrix}
\cos\alpha & -\sin\alpha \\
\sin\alpha & \cos\alpha
\end{vmatrix}=\begin{vmatrix}
c & -s \\
s & c
\end{vmatrix}
Воспользуемся комбинацией преобразований, которые позволяют получить однозначное соответствие пикселей исходного изображения конечному:
\begin{vmatrix}
1 & p \\
0 & 1
\end{vmatrix}\begin{vmatrix}
1 & 0 \\
q & 1
\end{vmatrix}=\begin{vmatrix}
1 + p q & p \\
q & 1
\end{vmatrix}
Из этого нельзя получить нужную матрицу поворота. Добавим ещё одно преобразование:
\begin{vmatrix}
1 & p \\
0 & 1
\end{vmatrix}\begin{vmatrix}
1 & 0 \\
q & 1
\end{vmatrix}\begin{vmatrix}
1 & r \\
0 & 1
\end{vmatrix}=\begin{vmatrix}
1 + p q & r + pqr + q \\
q & qr + 1
\end{vmatrix}
Получаем систему из 4 уравнений с 3 неизвестными:
\begin{cases}
1 + pq = c \\
qr + 1 = c \\
q = s \\
r + pqr + q = -s
\end{cases}
Из первых трёх получаем:
$p = r = \frac {c - 1} s$
$q = s$
Четвёртое уравнение должно выполняться, но у меня оно сводится к:
${c^2} + {s^2} = 0$
Получается или я где-то ошибся в вычислениях или из этих трёх преобразований нельзя получить поворот.

 Профиль  
                  
 
 Re: Однозначное соответсвие при повороте растровой картинки
Сообщение19.01.2016, 22:40 
Заслуженный участник


27/04/09
28128
Сделал LDU-разложение по-честному. Получилось$$\begin{bmatrix} 1 & 0 \\ s/c & 1 \end{bmatrix} \begin{bmatrix} 1 & -sc \\ 0 & 1 \end{bmatrix} \begin{bmatrix} c & 0 \\ 0 & 1/c \end{bmatrix}.$$

-- Ср янв 20, 2016 00:57:28 --

Вкупе с примерами вращения Ады — которые, вроде, совершенно нормальные! — можно вывести только одно: ваши преобразования — не совсем $\begin{bmatrix} 1 & p \\ 0 & 1\end{bmatrix}$ и аналогичное, а имеют на диагонали что-нибудь кроме единиц. (В код пока не совсем вник.)

P. S. Нет, вывод оказался неверным. Хм. :?

-- Ср янв 20, 2016 01:00:11 --

А вы вращали несколько раз по 15°? Кажется, понятно.

-- Ср янв 20, 2016 01:08:55 --

Вот разница в значениях пикселей Ады, взятой выше (честно говоря, стоило сохранять её в формат со сжатием без потерь), с Адой, повёрнутой обычным способом на те же 60° (всё в GIMP). Видно, что никаких перекосов в стороны нет.

 Профиль  
                  
 
 Re: Однозначное соответсвие при повороте растровой картинки
Сообщение20.01.2016, 00:25 
Аватара пользователя


07/02/12
1403
Питер
Progger в сообщении #1092370 писал(а):
Там ничего не вращается. Используется последовательно 3 преобразования

Может быть, я не правильно понял Ваш код. там фреймворк QT используется, я с ним не знаком.

Проверить можно градиентом, как я говорил - сгенерируйте картинку 256x256.
Слева сверху черная, сверху справа - зеленая, слева снизу - синяя, справа снизу - сине-зеленая.
Каждый пиксель будет один раз встречаться.

Визуально будет видно, что поворот похож на правильный. И проверить на встречаемость каждого пикселя один раз в результирующей картинке не сложно.

-- 20.01.2016, 00:28 --

Как алгоритм появится, покажу, зачем он нужен - прикольная штука =)

 Профиль  
                  
 
 Re: Однозначное соответсвие при повороте растровой картинки
Сообщение20.01.2016, 05:53 


02/10/12
300
bondkim137 в сообщении #1091642 писал(а):
Справедливости ради стоит отметить, что размер результирующей картинки будет больше исходной и в ней будут непронумерованные пиксели, то только по краям (прямоугольник, в который вписан повернутый прямоугольник).

Существует алгоритм Оуэна и Македона.
В офтопе скрины страничек, где упоминается этот алгоритм.

(Оффтоп)

http://www.bsu.by/Cache/Page/353423.pdf
Изображение

http://www.gamedev.ru/files/images/?id=90803
Изображение

Как я понимаю, этот алгоритм не подразумевает отображения пиксель в пиксель,
там происходит растяжение и сжатие строк и столбцов. Но т. к. Вам размеры
повернутого изображения не важны, то этот алгоритм можно сделать "точным".
Предположим для примера, что угол поворота задан такой, что горизонтальная
прямая при повороте на этот угол на каждые два пикселя по горизонтали поднимается
вверх на один пиксель (см. рисунки ниже 1, 2 и 3). Если присмотреться, то
на рисунках видна сетка, каждая ячейка это пиксель (если на Вашем мониторе
сетку не видно, то каждый квадратик, красный, черный, синий, это пиксель).
Исходный рисунок (Рис. 1) размером 8х3 состоит из трех цветных линий.
Изображение
При первом сдвиге я просто поднял соответствующие столбцы (Рис. 2).
При втором сдвиге я сдвинул соответствующие строки (Рис. 3).
Вот этот Рис. 3 - это и есть повернутое изображение пиксель в пиксель.

 Профиль  
                  
 
 Re: Однозначное соответсвие при повороте растровой картинки
Сообщение20.01.2016, 07:14 


27/08/14
206
oleg_2 в сообщении #1092514 писал(а):
Существует алгоритм Оуэна и Македона
Отлично. Моя реализация соответствует этому алгоритму, значит я где-то ошибся в вычислениях, но коэффициенты вычислил правильно :D

 Профиль  
                  
 
 Re: Однозначное соответсвие при повороте растровой картинки
Сообщение20.01.2016, 07:46 


02/10/12
300
Вот чего я не учел в сообщении http://dxdy.ru/post1092514.html#p1092514
Если первый сдвиг сделать на заданный угол, то при втором сдвиге угол первого
сдвига увеличится. Значит угол первого сдвига нужно брать поменьше, с надлежащим
упреждением для второго сдвига.
Изображение
На рисунке красная ось $x_1$ - это ось первого сдвига. Оси $x_2, y_2$ оси
второго сдвига.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 26 ]  На страницу 1, 2  След.

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group