ScanCombine: поворотный момент!
Уже два года прошло с начала работ над этим несчастным проектом, и только сейчас мне удалось реализовать команду «исправление наклона», так, чтобы она могла быть отменена, и при этом файл «контроля версий» не слишком раздувался.
Напомню: в свободное от работы время я пытаюсь написать свой аналог программам ScanKromsator / ScanTailor, с убийственной фичей - картинки обрабатываются на лету, не дожидаясь финального этапа, но любое действие можно отменить, вплоть до отката к оригиналам, благодаря "файлам контроля версий". Также "в меню" - возможность построить цветовой профиль сканера, внедрять его в изображения, а затем преобразовать их в sRGB (это фактически реализовано уже) и вообще проведение всех операций с учетом цветового профиля. Как мы убедимся совсем скоро - это позволяет повысить их качество.
Самый простой метод поворота - «ближайшего соседа» - сам по себе обратим: пиксели на изображении просто переставляются немножко другим способом и могут без потерь быть возращены на исходные позиции. Но качество поворота оставляет желать лучшего: отчетливо видны сдвиги на 1 пиксель по горизонтали и вертикали.
Следующим по сложности является метод билинейной интерполяции: мы определяем «исходную позицию» нового пикселя, она приходится где-то посерединке между старыми, и тогда мы берём взвешенную сумму четырёх соседних. Метод даёт весьма качественный результат, разве что картинка немного размывается. Кстати, в «плохих» реализациях (а таких большинство) размазывание гораздо сильнее из-за того, что не учитывается гамма: если вертикальная черная линия сдвинулась на четверть пикселя влево, то в прошлом белые (255) пиксели приобретут яркость 255 * (1-0,75) + 0 * 0,25 = 191, что в линейном выражении составляет примерно (191/255)^2,2 = 53% от полной яркости - т. е. буква визуально «разбухнет», что обычно связывают с размыванием - это не так. При работе в линейном пространстве метод даёт хорошие результаты и свободен от артефактов более сложных методов (бикубической интерполяции и Ланцоша/Lanczos), когда вблизи резких граней может появляться «звон», а из-за ограничения промежуточных результатов ещё и асимметрия возникает.
Ниже показано два «черных прямоугольника», повернутых на 45 градусов, оба с билинейной интерполяцией, но один - в линейном пространстве, второй - непосредственно с 8-битными значениями. Если открыть их в соседних вкладках и переключать взад-вперед, можно заметить, как прямоугольник «пульсирует» - при «плохом» методе он явно толще.
На мелком тексте это более заметно за счет гораздо большого "периметра" букв - любая тонкая линия будет расширяться с обеих сторон. Ещё про необходимость работы в линейном пространстве можно посмотреть в видеоролике Minute Physics: Computer Color is Broken (очень наглядно описывают), а также посмотреть обсуждение новой фичи в фотошопе Blend RGB colors using gamma. Много подробностей по работе Bicubic и необходимости не "обрезать" промежуточные результаты (и вообще куча подводных камней этого дела) можно найти на сайте ImageWorsener
В общем, поворот с билинейной интерполяцией при правильной реализации - очень хорошая вещь, почти не портящая изображение. Но сжатие не обманешь: у меня получалось, что картинка png размером 6 МБ после поворота стала занимать 4 МБ (несмотря на увеличившееся количество пикселей), поскольку предикторы начали гораздо лучше угадывать, каким будет следующий пиксель. (сейчас я начал сомневаться в строгости того эксперимента. Возможно, разный размер был обусловлен различными кодерами - мой, работающий в параноидальном режиме, делал огромную фору тому, что из BookPavilion - программы идущей в комплекте со сканером OpticBook. Но стабильное уменьшение размера после поворота - это факт)
В файл контроля версий должна была заноситься «дельта»: разность между исходной картинкой и картинкой, которую дал предиктор (уже мой, не из png), попытавшись обратить операцию, зная лишь конечный результат. Год назад мой предиктор попросту осуществлял поворот в обратную сторону на тот же угол, используя ту же самую линейную интерполяцию. В результате исходная картинка размывалась дважды, и «дельта» содержала очень много мелких деталей, из-за чего весила прилично, те же самые 4 МБ при исходном изображении в 6 МБ.
Да, результат работы предиктора налицо: нам не пришлось хранить все 6 МБ, но экономия в 2 МБ (33 %) - это несерьёзно! Неужели такая точная операция, как поворот, не может быть обращена получше?
У меня были мысли, как это сделать, они зачастую заводили куда-то в сторону систем линейных уравнений с размерностью эдак 1 000 000 х 1 000 000, но с 1 000 000 ненулевыми членами. Но дело усложнялось тем, что на самом деле неизвестных меньше, чем уравнений, поскольку картинка малость «расплылась» в стороны, мы уместили её в бОльший прямоугольник, чтобы ничего не пропало.
Надо ещё понимать, что это Undo и яйца выеденного не стоит, если не будет работать сколько-нибудь шустро, поэтому все эти разреженные матрицы и итеративные методы надо было выкинуть из головы, взяв что-то более простое.
В конце концов, решение было найдено: разложение поворота на 2-3 «скоса» (shear). Идея старше меня (обычно все ссылаются на эту статью A. W. Paeth - A FAST ALGORITHM FOR GENERAL RASTER ROTATION), но как ни странно, её прилично "задвинули в долгий ящик".
Скос - это одна из самых простых операций над изображением, мы просто сдвигаем каждую строку или каждый столбец на определенное число пикселей, так что прямоугольная картинка превращается в параллелограмм.
Более строго, вертикальный скос перемещает точку с координатами (x,y) в координаты
x’ = x
y’ = y + (x - cx)*tgα
Здесь α - угол наклона. Гораздо удобнее оказывается работать непосредственно с tgα, хоть это не так наглядно. Вертикальная линия x = cx останется на месте.
Аналогично, горизонтальный скос задаётся соотношениями
x’ = x + (y - cy)*tgα
y’ = y
Горизонтальная линия y = cy останется на месте.
Величины сx, cy важны при реализации, чтобы пиксели не выходили за пределы изображения, но пока можно про них забыть: если cx = cy = 0, то скос можно описать матрицей 2х2:
(буквы образованы от Shear Vertical и Shear Horizontal)
Определитель каждой из этих матриц равен единице, значит, и определитель их произведения будет равен единице, как и должно быть, если мы хотим осуществить поворот.
Несколько скосов в одном направлении легко заменяются на один-единственный, так что большого смысла в этом нет. Что-то интересное будет получаться, если чередовать вертикальные и горизонтальные скосы. При выполнении сначала вертикального скоса на величину α, а затем горизонтального на величину β, получим преобразование
В линейном приближении оно вполне сойдёт за поворот на угол φ, если взять -β = α = φ. По мере увеличения угла результат такого преобразования будет всё сильнее отличаться от поворота, мало того, поворот будет производиться не на тот угол, который надо. Можно задать коэффициенты α и β так, что преобразование S2 будет отличаться от правильного лишь масштабом осей. Для этого надо взять
Тогда S2 можно разложить на две матрицы:
то есть изображение повернется на искомый угол, но ещё сожмётся по горизонтали и растянется во столько же раз по вертикали. Полная площадь обязана оставаться такой же, поскольку у нас единичный определитель!
Величина эффекта составляет 1 - cos2φ ≈ φ2. Для 1 градуса это будет 0,0003, или 0.03%. Вместо исходного разрешения 600x600 dpi мы фактически получим 599,91x600,09 dpi- такое вряд ли получится уловить невооруженным глазом.
Ниже будет показано, как исправляется наклон в 1,47° на скане книги.
Но в случае 10 градусов это будет уже 3% и 590,88х 609,25 dpi. Наихудшая ситуация будет при повороте на 45°: соотношение сторон будет вдвое отличаться от истинного!
Поэтому для столь больших углов необходимо применить 3 скоса, к примеру, вертикальный, горизонтальный и ещё один вертикальный, что приводит уже к точному результату:
(это хороший пример, чтобы вспомнить тригонометрию - очень красиво всё сокращается!)
На рисунке ниже показано, как таким образом можно осуществить поворот на 90 градусов:
разумеется, никто в здравом уме не будет производить поворот на 90 градусов таким способом, но это единственный случай, когда подобный метод сводится ровно к перестановке пикселей без какой-либо интерполяции, поэтому он очень хорош для иллюстрации. Кроме того, здесь видно - хотя исходное и итоговое изображения имеют размер 3х3, но для выполнения операции понадобилось изображение побольше: 3х5! Это один из недостатков поворота через скосы - чтобы не «срезались углы», надо очень аккуратно работать, предусмотрев сколько надо места для промежуточных этапов.
Покажем, как выполняется поворот через три скоса и сравним с тем, что получается через два.
Поворот на 1.5° (скан был повернут на 1 градус в фотошопе)
Исходная картинка: https://img-fotki.yandex.ru/get/898391/41043419.8a/0_17f33b_f43119e9_orig
После 1-го скоса (по методу 2-х скосов): https://img-fotki.yandex.ru/get/898391/41043419.8a/0_17f33e_2a57b605_orig
Результат после 2-го скоса (по методу 2-х скосов): https://img-fotki.yandex.ru/get/898391/41043419.8a/0_17f339_8f023015_orig
После 1-го скоса (по методу 3-х скосов): https://img-fotki.yandex.ru/get/898391/41043419.8a/0_17f33c_a72b717b_orig
После 2-го скоса (по методу 3-х скосов): https://img-fotki.yandex.ru/get/898391/41043419.8a/0_17f33d_dd3f0bb5_orig
Результат после 3-го скоса (по методу 3-х скосов): https://img-fotki.yandex.ru/get/898391/41043419.8a/0_17f33a_43567bde_orig
если браузер их покажет существенно разных размеров, это проблема браузера, они отличаются не более чем на пиксел. Откройте на 100% и сравнивайте уже там. У меня обнаружить различия не удаётся.
Поворот на 10° (скан был повернут на 9.5 градус в фотошопе)
Исходная картинка: https://img-fotki.yandex.ru/get/914565/41043419.8a/0_17f42f_16ea8e13_orig
(это не та, я ещё обрезал её, чтобы текста было побольше, а рамок поменьше. Вечером вставлю правильную)
После 1-го скоса (по методу 2-х скосов): https://img-fotki.yandex.ru/get/898391/41043419.8a/0_17f337_b6305f7_orig
Результат после 2-го скоса (по методу 2-х скосов): https://img-fotki.yandex.ru/get/898391/41043419.8a/0_17f33f_ad22b519_orig
После 1-го скоса (по методу 3-х скосов): https://img-fotki.yandex.ru/get/898391/41043419.8a/0_17f333_288b882b_orig
После 2-го скоса (по методу 3-х скосов): https://img-fotki.yandex.ru/get/898391/41043419.8a/0_17f334_86ff333d_orig
Результат после 3-го скоса (по методу 3-х скосов): https://img-fotki.yandex.ru/get/898391/41043419.8a/0_17f340_4b0304e9_orig
И снова: нужно оба изображения открыть в полном масштабе и сравнивать на нём. Теперь уже отчетливо видно, что при использовании 2-х скосов изображение сплющивается по горизонтали и растягивается по вертикали - при углах в 10° применять 2 скоса не рекомендуется! Теоретически можно было бы поменять настройки dpi изображения, так что "уважающие себя" просмотрщики скомпенсировали бы размеры (благо, на 100% масштабе все равно не так часто нужно смотреть), но таких - немного. Уж лучше не лениться и сделать всё "по науке". Впрочем, проблема не такая уж острая - очень редко сканы будут повёрнуты аж на 10 градусов, величина в 0.5 .. 1,5° куда более реалистична.
У меня на данный момент "зашит" такой критерий: результирующая ширина или высота изображения должны отличаться от истинного менее чем на 1 пиксель. Тогда для изображений 4000х6000 критическим становятся те самые 1.5 ° - как видим, там как раз получилась разница в 1 пиксель.
Поворот на 45° (скан был повернут на 44,5 градуса в фотошопе)
Это максимальный поворот, который должны получать алгоритмы "произвольного наклона" - всё, что выше, можно свести к поворотам на 90 и 180 градусов, плюс поворот на 0..45°. Впрочем, и это достаточно умозрительно - не представляю, когда пользователь может захотеть повернуть изображение на 59 градусов.
Прошу заметить: исходную картинку я порезал прилично - откусил её углы, чтобы хоть что-то видно было, остался текст за всеми этими рамками. И в процессе операций ничего из исходной картинки не исчезает, только добавляются белые треугольные области.
Исходная картинка: https://img-fotki.yandex.ru/get/898391/41043419.8a/0_17f341_8f41a243_orig
После 1-го скоса (по методу 2-х скосов): https://img-fotki.yandex.ru/get/898391/41043419.8a/0_17f338_632654d4_orig
Результат после 2-го скоса (по методу 2-х скосов): https://img-fotki.yandex.ru/get/898391/41043419.8a/0_17f342_4a21188f_orig
После 1-го скоса (по методу 3-х скосов): https://img-fotki.yandex.ru/get/898391/41043419.8a/0_17f335_747ff40d_orig
После 2-го скоса (по методу 3-х скосов): https://img-fotki.yandex.ru/get/898391/41043419.8a/0_17f336_ef729862_orig
Результат после 3-го скоса (по методу 3-х скосов): https://img-fotki.yandex.ru/get/898391/41043419.8a/0_17f343_51a25fd_orig
Теперь уже и сравнивать друг с другом не надо - отчетливо видно, как картинка растянулась при повороте по упрощенному методу. Ровно вдвое - математика внезапно работает.
И нафига?
Вся прелесть в том, что мы свели двумерную задачу к набору задач одномерных, ну а обратить сдвиг строки на дробное число пикселей гораздо проще - тут уже не нужно «в явном виде» или итеративно решать систему уравнений, достаточно «прогонки» с одного из концов.
Выглядит это примерно так: у нас была строка s0, s1, … sW-1, а мы сдвинули её на α пикселей вправо, 0<α<1. Результирующую строку мы вычисляли по формулам:
d0=αF + (1-α)s0,
d1=αs0+(1-α)s1,
…
dW-1=αsW-2+(1-α)sW-1,
dW=αsW-1+(1-α)F
Здесь s и d (от “source” и “destination”) представлены в линейном пространстве, F (от “Fill”) соответствует белому, а вообще говоря, тому цвету, которым мы заполняем «пустые» углы. Пока что у меня происходит заполнение белым, но очень полезным может оказаться вариант с заполнением «прозрачным», чтобы в дальнейшем отличать «реальное изображение» от новых областей, которых на исходном скане не было.
Заметим, кстати, что мы уширили строку: она имела размер W, а теперь: W+1 (это при сдвиге меньше чем на пиксель, а так-то она и ещё длиннее может становиться).
Чтобы теперь, зная d, найти s, мы пойдём методично с одного из краёв, с какого именно - зависит от α. При α > 0,5 нужно начинать «с конца»:
sW-1=(dW-(1-α)F)/α,
sW-2=(dW-1-(1-α)sW-1)/α,
…
Коэффициент при «рекуррентном» члене (1-α)/α будет меньше единицы, благодаря чему метод получается устойчивым. Попробуй мы пойти с обратной стороны, у нас был бы коэффициент α/(1-α) > 1, и всё пойдёт вразнос. Если α < 0,5, то всё наоборот: нужно идти с начала строки, ни в коем случае не с конца. Случай α = 0,5 - "граничный", тут однажды возникшая ошибка будет распространяться по всей строке, оставляя "волну". А кому сейчас легко?
Конечно, мы не добьёмся полной обратимости, по крайней мере, если исходное и итоговое изображения имеют одинаковую глубину цвета (скажем, 8 бит grayscale) из-за ошибок квантования, но в целом этот метод даёт гораздо лучшее «предсказание» исходной картинки, чем сдвиг на α в обратную сторону через ту же линейную интерполяцию, или сдвиг назад через «ближайшего соседа».
В статье FULLY REVERSIBLE IMAGE ROTATION BY 1-D FILTERING предложены симметричные методы, которые выглядят совершенно одинаково «вперед» и «назад», которые полностью обратимы при условии абсолютной точности вычислений и представления результатов. Возможно, было бы лучше применить их - как-нибудь попробую. Пока я не сделал этого, исходя из мысли «Undo не должно диктовать нам, как поворачивать изображение - пусть подстраивается под используемые методы!».
В реализации возникает много подводных камней - в целом всё это мелкие технические проблемы, но сквозь них нужно долго и упорно пробираться. Первое - это правильное определение промежуточных и итоговых размеров изображения, так, чтобы ни один пиксель исходного изображения не ушел «за рамки», но и лишнего пространства бы не образовывалось. Даже вычисления с плавающей точкой здесь подкладывают свинью: при попытке повернуть изображение 13х13 пикселов на 90 градусов, я получил размеры итогового изображения в 13х14, с нижней строкой, заполненной белым. Оказалось, что результатом вычисления ceil(0 - 13) стало -12 (в оправдание FPU могу сказать, что там использовались tan(45°) и sin(90°), так что 13 могло быть уже не совсем 13). Чтобы таких вещей не возникало, был введен для каждого изображения параметр shiftTolerance, который показывает, при каком минимальном сдвиге может измениться значение хотя бы одного пикселя. Его величина зависит от цветового профиля / гаммы, в линейном случае это будет 1/255 = 0,0039, а для стандартной гаммы в 2.2: 0,00029. Функции floor и ceil соответственно доработаны, чтобы «прощать» отклонение от целого числа на такие величины.
Продолжение следует...
(и да, я не забыл про ликбез по кватернионам, его тоже хочу завершить в ближайшее время)
Напомню: в свободное от работы время я пытаюсь написать свой аналог программам ScanKromsator / ScanTailor, с убийственной фичей - картинки обрабатываются на лету, не дожидаясь финального этапа, но любое действие можно отменить, вплоть до отката к оригиналам, благодаря "файлам контроля версий". Также "в меню" - возможность построить цветовой профиль сканера, внедрять его в изображения, а затем преобразовать их в sRGB (это фактически реализовано уже) и вообще проведение всех операций с учетом цветового профиля. Как мы убедимся совсем скоро - это позволяет повысить их качество.
Самый простой метод поворота - «ближайшего соседа» - сам по себе обратим: пиксели на изображении просто переставляются немножко другим способом и могут без потерь быть возращены на исходные позиции. Но качество поворота оставляет желать лучшего: отчетливо видны сдвиги на 1 пиксель по горизонтали и вертикали.
Следующим по сложности является метод билинейной интерполяции: мы определяем «исходную позицию» нового пикселя, она приходится где-то посерединке между старыми, и тогда мы берём взвешенную сумму четырёх соседних. Метод даёт весьма качественный результат, разве что картинка немного размывается. Кстати, в «плохих» реализациях (а таких большинство) размазывание гораздо сильнее из-за того, что не учитывается гамма: если вертикальная черная линия сдвинулась на четверть пикселя влево, то в прошлом белые (255) пиксели приобретут яркость 255 * (1-0,75) + 0 * 0,25 = 191, что в линейном выражении составляет примерно (191/255)^2,2 = 53% от полной яркости - т. е. буква визуально «разбухнет», что обычно связывают с размыванием - это не так. При работе в линейном пространстве метод даёт хорошие результаты и свободен от артефактов более сложных методов (бикубической интерполяции и Ланцоша/Lanczos), когда вблизи резких граней может появляться «звон», а из-за ограничения промежуточных результатов ещё и асимметрия возникает.
Ниже показано два «черных прямоугольника», повернутых на 45 градусов, оба с билинейной интерполяцией, но один - в линейном пространстве, второй - непосредственно с 8-битными значениями. Если открыть их в соседних вкладках и переключать взад-вперед, можно заметить, как прямоугольник «пульсирует» - при «плохом» методе он явно толще.
На мелком тексте это более заметно за счет гораздо большого "периметра" букв - любая тонкая линия будет расширяться с обеих сторон. Ещё про необходимость работы в линейном пространстве можно посмотреть в видеоролике Minute Physics: Computer Color is Broken (очень наглядно описывают), а также посмотреть обсуждение новой фичи в фотошопе Blend RGB colors using gamma. Много подробностей по работе Bicubic и необходимости не "обрезать" промежуточные результаты (и вообще куча подводных камней этого дела) можно найти на сайте ImageWorsener
В общем, поворот с билинейной интерполяцией при правильной реализации - очень хорошая вещь, почти не портящая изображение. Но сжатие не обманешь: у меня получалось, что картинка png размером 6 МБ после поворота стала занимать 4 МБ (несмотря на увеличившееся количество пикселей), поскольку предикторы начали гораздо лучше угадывать, каким будет следующий пиксель. (сейчас я начал сомневаться в строгости того эксперимента. Возможно, разный размер был обусловлен различными кодерами - мой, работающий в параноидальном режиме, делал огромную фору тому, что из BookPavilion - программы идущей в комплекте со сканером OpticBook. Но стабильное уменьшение размера после поворота - это факт)
В файл контроля версий должна была заноситься «дельта»: разность между исходной картинкой и картинкой, которую дал предиктор (уже мой, не из png), попытавшись обратить операцию, зная лишь конечный результат. Год назад мой предиктор попросту осуществлял поворот в обратную сторону на тот же угол, используя ту же самую линейную интерполяцию. В результате исходная картинка размывалась дважды, и «дельта» содержала очень много мелких деталей, из-за чего весила прилично, те же самые 4 МБ при исходном изображении в 6 МБ.
Да, результат работы предиктора налицо: нам не пришлось хранить все 6 МБ, но экономия в 2 МБ (33 %) - это несерьёзно! Неужели такая точная операция, как поворот, не может быть обращена получше?
У меня были мысли, как это сделать, они зачастую заводили куда-то в сторону систем линейных уравнений с размерностью эдак 1 000 000 х 1 000 000, но с 1 000 000 ненулевыми членами. Но дело усложнялось тем, что на самом деле неизвестных меньше, чем уравнений, поскольку картинка малость «расплылась» в стороны, мы уместили её в бОльший прямоугольник, чтобы ничего не пропало.
Надо ещё понимать, что это Undo и яйца выеденного не стоит, если не будет работать сколько-нибудь шустро, поэтому все эти разреженные матрицы и итеративные методы надо было выкинуть из головы, взяв что-то более простое.
В конце концов, решение было найдено: разложение поворота на 2-3 «скоса» (shear). Идея старше меня (обычно все ссылаются на эту статью A. W. Paeth - A FAST ALGORITHM FOR GENERAL RASTER ROTATION), но как ни странно, её прилично "задвинули в долгий ящик".
Скос - это одна из самых простых операций над изображением, мы просто сдвигаем каждую строку или каждый столбец на определенное число пикселей, так что прямоугольная картинка превращается в параллелограмм.
Более строго, вертикальный скос перемещает точку с координатами (x,y) в координаты
x’ = x
y’ = y + (x - cx)*tgα
Здесь α - угол наклона. Гораздо удобнее оказывается работать непосредственно с tgα, хоть это не так наглядно. Вертикальная линия x = cx останется на месте.
Аналогично, горизонтальный скос задаётся соотношениями
x’ = x + (y - cy)*tgα
y’ = y
Горизонтальная линия y = cy останется на месте.
Величины сx, cy важны при реализации, чтобы пиксели не выходили за пределы изображения, но пока можно про них забыть: если cx = cy = 0, то скос можно описать матрицей 2х2:
(буквы образованы от Shear Vertical и Shear Horizontal)
Определитель каждой из этих матриц равен единице, значит, и определитель их произведения будет равен единице, как и должно быть, если мы хотим осуществить поворот.
Несколько скосов в одном направлении легко заменяются на один-единственный, так что большого смысла в этом нет. Что-то интересное будет получаться, если чередовать вертикальные и горизонтальные скосы. При выполнении сначала вертикального скоса на величину α, а затем горизонтального на величину β, получим преобразование
В линейном приближении оно вполне сойдёт за поворот на угол φ, если взять -β = α = φ. По мере увеличения угла результат такого преобразования будет всё сильнее отличаться от поворота, мало того, поворот будет производиться не на тот угол, который надо. Можно задать коэффициенты α и β так, что преобразование S2 будет отличаться от правильного лишь масштабом осей. Для этого надо взять
Тогда S2 можно разложить на две матрицы:
то есть изображение повернется на искомый угол, но ещё сожмётся по горизонтали и растянется во столько же раз по вертикали. Полная площадь обязана оставаться такой же, поскольку у нас единичный определитель!
Величина эффекта составляет 1 - cos2φ ≈ φ2. Для 1 градуса это будет 0,0003, или 0.03%. Вместо исходного разрешения 600x600 dpi мы фактически получим 599,91x600,09 dpi- такое вряд ли получится уловить невооруженным глазом.
Ниже будет показано, как исправляется наклон в 1,47° на скане книги.
Но в случае 10 градусов это будет уже 3% и 590,88х 609,25 dpi. Наихудшая ситуация будет при повороте на 45°: соотношение сторон будет вдвое отличаться от истинного!
Поэтому для столь больших углов необходимо применить 3 скоса, к примеру, вертикальный, горизонтальный и ещё один вертикальный, что приводит уже к точному результату:
(это хороший пример, чтобы вспомнить тригонометрию - очень красиво всё сокращается!)
На рисунке ниже показано, как таким образом можно осуществить поворот на 90 градусов:
разумеется, никто в здравом уме не будет производить поворот на 90 градусов таким способом, но это единственный случай, когда подобный метод сводится ровно к перестановке пикселей без какой-либо интерполяции, поэтому он очень хорош для иллюстрации. Кроме того, здесь видно - хотя исходное и итоговое изображения имеют размер 3х3, но для выполнения операции понадобилось изображение побольше: 3х5! Это один из недостатков поворота через скосы - чтобы не «срезались углы», надо очень аккуратно работать, предусмотрев сколько надо места для промежуточных этапов.
Покажем, как выполняется поворот через три скоса и сравним с тем, что получается через два.
Поворот на 1.5° (скан был повернут на 1 градус в фотошопе)
Исходная картинка: https://img-fotki.yandex.ru/get/898391/41043419.8a/0_17f33b_f43119e9_orig
После 1-го скоса (по методу 2-х скосов): https://img-fotki.yandex.ru/get/898391/41043419.8a/0_17f33e_2a57b605_orig
Результат после 2-го скоса (по методу 2-х скосов): https://img-fotki.yandex.ru/get/898391/41043419.8a/0_17f339_8f023015_orig
После 1-го скоса (по методу 3-х скосов): https://img-fotki.yandex.ru/get/898391/41043419.8a/0_17f33c_a72b717b_orig
После 2-го скоса (по методу 3-х скосов): https://img-fotki.yandex.ru/get/898391/41043419.8a/0_17f33d_dd3f0bb5_orig
Результат после 3-го скоса (по методу 3-х скосов): https://img-fotki.yandex.ru/get/898391/41043419.8a/0_17f33a_43567bde_orig
если браузер их покажет существенно разных размеров, это проблема браузера, они отличаются не более чем на пиксел. Откройте на 100% и сравнивайте уже там. У меня обнаружить различия не удаётся.
Поворот на 10° (скан был повернут на 9.5 градус в фотошопе)
Исходная картинка: https://img-fotki.yandex.ru/get/914565/41043419.8a/0_17f42f_16ea8e13_orig
(это не та, я ещё обрезал её, чтобы текста было побольше, а рамок поменьше. Вечером вставлю правильную)
После 1-го скоса (по методу 2-х скосов): https://img-fotki.yandex.ru/get/898391/41043419.8a/0_17f337_b6305f7_orig
Результат после 2-го скоса (по методу 2-х скосов): https://img-fotki.yandex.ru/get/898391/41043419.8a/0_17f33f_ad22b519_orig
После 1-го скоса (по методу 3-х скосов): https://img-fotki.yandex.ru/get/898391/41043419.8a/0_17f333_288b882b_orig
После 2-го скоса (по методу 3-х скосов): https://img-fotki.yandex.ru/get/898391/41043419.8a/0_17f334_86ff333d_orig
Результат после 3-го скоса (по методу 3-х скосов): https://img-fotki.yandex.ru/get/898391/41043419.8a/0_17f340_4b0304e9_orig
И снова: нужно оба изображения открыть в полном масштабе и сравнивать на нём. Теперь уже отчетливо видно, что при использовании 2-х скосов изображение сплющивается по горизонтали и растягивается по вертикали - при углах в 10° применять 2 скоса не рекомендуется! Теоретически можно было бы поменять настройки dpi изображения, так что "уважающие себя" просмотрщики скомпенсировали бы размеры (благо, на 100% масштабе все равно не так часто нужно смотреть), но таких - немного. Уж лучше не лениться и сделать всё "по науке". Впрочем, проблема не такая уж острая - очень редко сканы будут повёрнуты аж на 10 градусов, величина в 0.5 .. 1,5° куда более реалистична.
У меня на данный момент "зашит" такой критерий: результирующая ширина или высота изображения должны отличаться от истинного менее чем на 1 пиксель. Тогда для изображений 4000х6000 критическим становятся те самые 1.5 ° - как видим, там как раз получилась разница в 1 пиксель.
Поворот на 45° (скан был повернут на 44,5 градуса в фотошопе)
Это максимальный поворот, который должны получать алгоритмы "произвольного наклона" - всё, что выше, можно свести к поворотам на 90 и 180 градусов, плюс поворот на 0..45°. Впрочем, и это достаточно умозрительно - не представляю, когда пользователь может захотеть повернуть изображение на 59 градусов.
Прошу заметить: исходную картинку я порезал прилично - откусил её углы, чтобы хоть что-то видно было, остался текст за всеми этими рамками. И в процессе операций ничего из исходной картинки не исчезает, только добавляются белые треугольные области.
Исходная картинка: https://img-fotki.yandex.ru/get/898391/41043419.8a/0_17f341_8f41a243_orig
После 1-го скоса (по методу 2-х скосов): https://img-fotki.yandex.ru/get/898391/41043419.8a/0_17f338_632654d4_orig
Результат после 2-го скоса (по методу 2-х скосов): https://img-fotki.yandex.ru/get/898391/41043419.8a/0_17f342_4a21188f_orig
После 1-го скоса (по методу 3-х скосов): https://img-fotki.yandex.ru/get/898391/41043419.8a/0_17f335_747ff40d_orig
После 2-го скоса (по методу 3-х скосов): https://img-fotki.yandex.ru/get/898391/41043419.8a/0_17f336_ef729862_orig
Результат после 3-го скоса (по методу 3-х скосов): https://img-fotki.yandex.ru/get/898391/41043419.8a/0_17f343_51a25fd_orig
Теперь уже и сравнивать друг с другом не надо - отчетливо видно, как картинка растянулась при повороте по упрощенному методу. Ровно вдвое - математика внезапно работает.
И нафига?
Вся прелесть в том, что мы свели двумерную задачу к набору задач одномерных, ну а обратить сдвиг строки на дробное число пикселей гораздо проще - тут уже не нужно «в явном виде» или итеративно решать систему уравнений, достаточно «прогонки» с одного из концов.
Выглядит это примерно так: у нас была строка s0, s1, … sW-1, а мы сдвинули её на α пикселей вправо, 0<α<1. Результирующую строку мы вычисляли по формулам:
d0=αF + (1-α)s0,
d1=αs0+(1-α)s1,
…
dW-1=αsW-2+(1-α)sW-1,
dW=αsW-1+(1-α)F
Здесь s и d (от “source” и “destination”) представлены в линейном пространстве, F (от “Fill”) соответствует белому, а вообще говоря, тому цвету, которым мы заполняем «пустые» углы. Пока что у меня происходит заполнение белым, но очень полезным может оказаться вариант с заполнением «прозрачным», чтобы в дальнейшем отличать «реальное изображение» от новых областей, которых на исходном скане не было.
Заметим, кстати, что мы уширили строку: она имела размер W, а теперь: W+1 (это при сдвиге меньше чем на пиксель, а так-то она и ещё длиннее может становиться).
Чтобы теперь, зная d, найти s, мы пойдём методично с одного из краёв, с какого именно - зависит от α. При α > 0,5 нужно начинать «с конца»:
sW-1=(dW-(1-α)F)/α,
sW-2=(dW-1-(1-α)sW-1)/α,
…
Коэффициент при «рекуррентном» члене (1-α)/α будет меньше единицы, благодаря чему метод получается устойчивым. Попробуй мы пойти с обратной стороны, у нас был бы коэффициент α/(1-α) > 1, и всё пойдёт вразнос. Если α < 0,5, то всё наоборот: нужно идти с начала строки, ни в коем случае не с конца. Случай α = 0,5 - "граничный", тут однажды возникшая ошибка будет распространяться по всей строке, оставляя "волну". А кому сейчас легко?
Конечно, мы не добьёмся полной обратимости, по крайней мере, если исходное и итоговое изображения имеют одинаковую глубину цвета (скажем, 8 бит grayscale) из-за ошибок квантования, но в целом этот метод даёт гораздо лучшее «предсказание» исходной картинки, чем сдвиг на α в обратную сторону через ту же линейную интерполяцию, или сдвиг назад через «ближайшего соседа».
В статье FULLY REVERSIBLE IMAGE ROTATION BY 1-D FILTERING предложены симметричные методы, которые выглядят совершенно одинаково «вперед» и «назад», которые полностью обратимы при условии абсолютной точности вычислений и представления результатов. Возможно, было бы лучше применить их - как-нибудь попробую. Пока я не сделал этого, исходя из мысли «Undo не должно диктовать нам, как поворачивать изображение - пусть подстраивается под используемые методы!».
В реализации возникает много подводных камней - в целом всё это мелкие технические проблемы, но сквозь них нужно долго и упорно пробираться. Первое - это правильное определение промежуточных и итоговых размеров изображения, так, чтобы ни один пиксель исходного изображения не ушел «за рамки», но и лишнего пространства бы не образовывалось. Даже вычисления с плавающей точкой здесь подкладывают свинью: при попытке повернуть изображение 13х13 пикселов на 90 градусов, я получил размеры итогового изображения в 13х14, с нижней строкой, заполненной белым. Оказалось, что результатом вычисления ceil(0 - 13) стало -12 (в оправдание FPU могу сказать, что там использовались tan(45°) и sin(90°), так что 13 могло быть уже не совсем 13). Чтобы таких вещей не возникало, был введен для каждого изображения параметр shiftTolerance, который показывает, при каком минимальном сдвиге может измениться значение хотя бы одного пикселя. Его величина зависит от цветового профиля / гаммы, в линейном случае это будет 1/255 = 0,0039, а для стандартной гаммы в 2.2: 0,00029. Функции floor и ceil соответственно доработаны, чтобы «прощать» отклонение от целого числа на такие величины.
Продолжение следует...
(и да, я не забыл про ликбез по кватернионам, его тоже хочу завершить в ближайшее время)