Однозначное соответсвие при повороте растровой картинки

[bondkim137]

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

[Aritaborian]

Рассмотрим изображение размером два на два пикселя...

[bondkim137]

Aritaborian в сообщении #1091643 писал(а):

Рассмотрим изображение размером два на два пикселя...

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

[arseniiv]

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

[bondkim137]

arseniiv в сообщении #1091678 писал(а):

А на 45°?

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

-- 18.01.2016, 14:34 --

arseniiv в сообщении #1091678 писал(а):

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

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

-- 18.01.2016, 14:41 --

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

[Pavia]

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

[bondkim137]

Pavia в сообщении #1092204 писал(а):

сделайте скос на $X$ и $Y$

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

[Progger]

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

[bondkim137]

Progger в сообщении #1092311 писал(а):

Пример вращения

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

-- 19.01.2016, 18:28 --

Progger в сообщении #1092311 писал(а):

Вроде у меня получилось что-то такое сделать

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

[Progger]

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$
Получается или я где-то ошибся в вычислениях или из этих трёх преобразований нельзя получить поворот.

[arseniiv]

Сделал 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). Видно, что никаких перекосов в стороны нет.

[bondkim137]

Progger в сообщении #1092370 писал(а):

Там ничего не вращается. Используется последовательно 3 преобразования

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

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

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

-- 20.01.2016, 00:28 --

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

[oleg_2]

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 - это и есть повернутое изображение пиксель в пиксель.

[Progger]

oleg_2 в сообщении #1092514 писал(а):

Существует алгоритм Оуэна и Македона

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

[oleg_2]

Вот чего я не учел в сообщении http://dxdy.ru/post1092514.html#p1092514
Если первый сдвиг сделать на заданный угол, то при втором сдвиге угол первого
сдвига увеличится. Значит угол первого сдвига нужно брать поменьше, с надлежащим
упреждением для второго сдвига.

На рисунке красная ось $x_1$ - это ось первого сдвига. Оси $x_2, y_2$ оси
второго сдвига.