Поворот растрового изображения на углы, кратные 90°, относительно геометрического центра изображения – задача тривиальная и решается без потери качества простым преобразованием координат каждого пикселя.
Ниже мы рассмотрим алгоритм прецизионного поворота растрового изображения на произвольный угол относительно произвольного центра с минимальными потерями.
Выражаю благодарность Харченко Владиславу Владимировичу за оказанную помощь.
Алгоритм
Из вышеприведённого рисунка видно, что после поворота растрового изображения, цвет каждого пикселя итогового изображения определяется сложением цветов нескольких «осколков» нескольких пикселей исходного изображения, пропорционально площадям соответствующих «осколков». Поэтому в общем виде решение нашей задачи будет состоять в том, чтобы найти площади всех «осколков» для каждого пикселя исходного изображения и собрать цвет каждого пикселя итогового изображения из цветов соответствующих «осколков» .В качестве модели пикселя исходного изображения мы будем использовать квадрат со стороной = 1, с такими обозначениями углов:
i1 - самый правый угол;
i2 - самый нижний угол;
i3 - самый левый угол;
i4 - самый верхний угол.
Моделью итогового изображения будет сетка из параллельных горизонтальных и вертикальных линий с расстоянием между линиями = 1.
Координаты центра поворота растрового изображения, в таком представлении, могут быть выражены парой произвольных вещественных чисел. То есть центр поворота в нашей задаче может лежать не в геометрическом центре пикселя и не в точке пересечения линий сетки, а в произвольной точке декартовых координат.
Поскольку при повороте растрового изображения квадрат каждого пикселя поворачивается на один и тот же угол (относительно центра этого пикселя) мы будем решать задачу для одного пикселя, а потом применим полученное решение для каждого пикселя исходного изображения.
Поворот растрового изображения можно разделить на две части:
1. Поворот квадрата каждого пикселя исходного изображения относительно центра этого квадрата на заданный угол.
2. Смещение центра квадрата пикселя в соответствии с углом поворота изображения относительно центра поворота изображения таким образом, чтобы квадрат занял своё итоговое положение на сетке итогового изображения.
При этом сетка итогового изображения рассекает квадрат каждого пикселя исходного изображения на «осколки» в количестве 4, 5 или 6 штук.
Чтобы систематизировать разнообразие получающихся вариантов мне пришлось составить таксономию всевозможных пересечений квадрата пикселя исходного изображения с сеткой итогового изображения. Существенно разных вариантов оказалось всего 23:
Условные обозначения здесь следующие:
- цифры в ячейках обозначают номера углов квадрата пикселя, которые попали в данную ячейку сетки итогового изображения после поворота изображения;
- зелёным цветом обозначены ячейки, в которые попали участки пикселя и гарантированно оставили там по «осколку»;
- жёлтым цветом обозначены ячейки, в которые, в зависимости от условий, могут
попасть (а могут и не попасть) «осколки» квадрата пикселя, образованные не углами квадрата, а сторонами квадрата.
Для наглядности приведу одну из возможных вариаций варианта №3:
Как видим, верхняя правая ячейка не содержит в себе «осколка» пикселя, хотя при других условиях поворота могла бы содержать.
Чтобы не нагружать читателя детальными геометрическими выкладками, скажу сразу, что во всех этих 23-х вариантах пиксель исходного изображения рассекается на «осколки», площадь которых легко вычисляется комбинированием 4-х формул. Ниже приведены эти формулы с иллюстрациями. Красным цветом обозначены линии сетки итогового изображения, которые рассекают квадрат пикселя. Жёлтым цветом закрашена область, площадь которой вычисляется формулой.
Формула 1
Эта формула не используется для расчёта окончательной площади «осколка», но её удобно использовать для быстрого расчёта вспомогательных промежуточных площадей, поскольку нам заведомо известно, что площадь всего пикселя = 1.В качестве входных переменных во всех формулах используются высоты, опущенные из углов квадрата на сетку итогового изображения, по той простой причине, что расчёт этих высот сводится к мгновенному выделению дробной части числового значения координаты соответствующего угла квадрата пикселя.
Формула 2
Данная формула используется только в вариантах 1 и 2.
Формула 3
Часто используемая формула - очень хорошо, что она быстро вычисляется. Поскольку угол поворота одинаков для каждого пикселя - все тригонометрические функции можно посчитать один раз, перед обработкой всех пикселей, и далее использовать эти значения в цикле как константы.Формула 4
Эта формула вычисляется в два этапа. Сначала вычисляется выражение в скобках. Если оно принимает положительное значение, то вычисляется площадь. Если значение отрицательное, значит от пикселя не отсекается «осколок», образованный углом сетки и стороной квадрата и дальнейшие вычисления производить не имеет смысла.С учётом всего вышесказанного, в общем виде алгоритм будет выглядеть так:
1. Загружаем в память ЭВМ исходное изображение.
2. Рассчитываем размеры итогового изображения в пикселях.
3. Создаём промежуточный двумерный массив, каждый элемент которого содержит 3 составляющие цвета RGB в формате числа с плавающей запятой. Размеры массива равны размерам итогового изображения.
4. Последовательно перебираем все пиксели исходного изображения; поворачиваем каждый из них на заданный угол и располагаем на сетке итогового изображения, рассчитав 4 координаты углов квадрата пикселя; классифицируем пиксель по 23 вариантам и считаем площади «осколков»; добавляем в соответствующие элементы промежуточного массива цвета полученных «осколков» пропорционально площади этих «осколков».
5. После обработки всех пикселей исходного изображения округляем значения RGB в промежуточном массиве до целого значения для каждого элемента и создаём на базе этих целых значений итоговое изображение в формате BMP.
Программа
На основании приведённого алгоритма была написана программа для Windows. Исходные коды на Object Pascal и скомпилированный исполняемый файл можно скачать .Интерфейс программы.
По нажатию на кнопку «Open...» открывается диалог выбора BMP-файла. Поддерживаются битмапы только с 24-битной палитрой. Открытое изображение отображается в окне. В заголовке окна выводится полный путь к файлу и размеры изображения.
В поле «Angle» задаётся угол поворота в градусах – любое положительное число.
В качестве десятичного разделителя при вводе дробных чисел может быть использована как точка, так и запятая.
Радиокнопками «CW» и «CCW» задаётся направление вращения: «по часовой стрелке» и «против часовой стрелки», соответственно.
В блоке «Background color» можно задать цвет фона, с которым будут смешиваться граничные пиксели изображения. По умолчанию цвет фона – чёрный.
В полях «Centre X» и «Centre Y» задаются координаты центра поворота. При этом следует учитывать, что начало координат находится в левом верхнем углу изображения и Y увеличивается вниз. По умолчанию центр поворота устанавливается в геометрическом центре загруженного изображения.
По нажатию на кнопку «Rotate» либо по нажатию на клавишу Enter изображение поворачивается на заданный угол относительно заданного центра поворота и отображается в окне. Поворот изображения на углы, кратные 90°, реализован по упрощённой схеме, путём простого преобразования координат пикселей исходного изображения, при этом значения «Centre X» и «Centre Y» игнорируются.
Время работы алгоритма в секундах отображается под кнопкой «Rotate».
Через кнопку «Save…» повёрнутое изображение можно сохранить в BMP-файл.
Если итоговое изображение не помещается в окне – оно подгоняется к границам окна API-функцией StretchBlt – поэтому оценить реальное качество больших картинок можно только по сохранённому BMP-файлу.
Для поворота изображения на другой угол его не нужно загружать повторно - поворачивается изображение из выбранного файла, а не отображённое в данный момент в окне.
Изображение с размерами 1024 х 768 на машине с четырёхядерным процессором 2,67 ГГц поворачивается данной программой на произвольный угол, в среднем, приблизительно, за 0,5 секунды. Изображение с размерами 4000 х 4000 - примерно за 10 секунд. Время работы алгоритма для разных углов может отличаться в связи с тем, что изображение при разных углах дробится на разное количество «осколков», на вычисление площадей которых суммарно тратится, соответственно, разное время.
Промежуточный массив, содержащий информацию о цвете пикселей итогового изображения в формате числа с плавающей запятой, реализован на типе extended (10 байт), поэтому обработка больших изображений (примерно более 5000 х 5000 пикселей) может вызвать ошибку переполнения памяти. Улучшить ситуацию возможно, применив менее точный тип данных и сохраняя целую часть числа сразу в итоговый битмап, оставляя во вспомогательном массиве только дробную часть.
Результаты
Проведём сравнительный анализ работы прецизионного алгоритма и алгоритма поворота изображений, реализованного в программе Photoshop.Тест 1
Для первого теста я взял очень простое изображение - горизонтальную линию чёрного цвета толщиной 1 пиксель и длиной 10 пикселей, смещённую относительно центра белого квадрата с размерами 100 х 100 пикселей:После чего я повернул данное изображение относительно точки с координатами (0, 0) на 3° по часовой стрелке. Точка (0, 0) выбрана потому, что, судя по моим экспериментам, Photoshop поворачивает изображение относительно именно этой точки. Вот сравнительный результат (увеличено в 24 раза):
Прецизионный алгоритм
Photoshop 7.0.1
Photoshop CS6 (64 Bit)
Алгоритм Photoshop даёт более контрастную картинку, прецизионный алгоритм несколько «размывает» изображение. Но в целом, при визуальной оценке, результат получается почти одинаковым. Попутно отметим, что алгоритм поворота, реализованный в Photoshop, не претерпел за 10 лет существенных изменений.
Тест 2
Для второго теста я выбрал тюльпан из стандартного дистрибутива Win7:После поворота данного изображения на 5° по часовой стрелке относительно геометрического центра я суммировал цвет всех пикселей в разрезе каналов RGB. Вот результат для прецизионного алгоритма и алгоритма Photoshop:
Числа в скобках показывают абсолютное отклонение данного показателя от оригинала.
Цвет изображения после прецизионного поворота и до округления практически не поменялся - чего и следовало ожидать.
Самое большое отклонение, в данном конкретном случае, мы обнаруживаем по каналу G для алгоритма Photoshop. В процентном отношении это отклонение составляет всего 0,06%, поэтому «на глаз» оно не заметно, но из соображений перфекционизма результат у Photoshop получается хуже, чем у прецизионного алгоритма.
Важно отметить, что округление цвета каждого пикселя в прецизионном алгоритме до целочисленного значения, необходимого для формата BMP, необратимо уничтожает часть информации о цвете.
Для визуального сравнения двух алгоритмов приведу увеличенный фрагмент изображения,
Повёрнутого на 5° по часовой стрелке, соответственно, Photoshop"ом:
И прецизионным алгоритмом:
Сравнительный анализ показывает, что Photoshop лучше сохраняет контрастные элементы изображения, но при этом создаёт «ореолы» искажённого цвета. Прецизионный алгоритм не искажает цвет но при этом несколько «размывает» изображение.
Выводы
1. Прецизионный и при этом сравнительно быстрый поворот растрового изображения на произвольный угол - возможен. Для меня остаётся загадкой вопрос, почему в профессиональных графических редакторах нет опции, позволяющей пользователю повернуть изображение предельно точно за чуть большее время.2. Несмотря на предельную точность рассмотренного алгоритма, обратное преобразование изображения, т.е. поворот на противоположный угол без потери качества - невозможен, потому что округление точного значения цвета (в формате числа с плавающей запятой) необратимо уничтожает часть информации о цвете.
3. С точки зрения визуального восприятия контрастных деталей лучший результат даёт подоптимальный алгоритм Photoshop. Прецизионный же алгоритм имеет смысл применять в тех случаях, когда важно сохранить максимум информации о цвете изображения.
UPD: Для практического использования написал программу, реализующую упрощённый алгоритм, в котором для каждого пикселя итогового изображения все необходимые кусочки пикселей исходного изображения рассчитываются последовательно и округление цвета происходит немедленно. Только после этого рассчитывается следующий пиксель итогового изображения. При этом к отдельному пикселю исходного изображения программа обращается несколько раз. Время расчётов, таким образом, увеличилось, в среднем, в 1,7 раз, но память в этой версии алгоритма расходуется только на хранение битмапов, что позволяет работать с изображениями больших размеров. Скачать программу и исходники можно
В тригонометрии важным понятием является угол поворота . Ниже мы последовательно будем давать представление о повороте, и вводить все сопутствующие понятия. Начнем с общего представления о повороте, скажем о полном обороте. Далее перейдем к понятию угла поворота и рассмотрим его основные характеристики, такие как направление и величина поворота. Наконец, дадим определение поворота фигуры вокруг точки. Всю теорию по тексту будем снабжать поясняющими примерами и графическими иллюстрациями.
Навигация по странице.
Что называют поворотом точки вокруг точки?
Сразу отметим, что наряду с фразой «поворот вокруг точки» будем также использовать словосочетания «поворот около точки» и «поворот относительно точки», что обозначает одно и то же.
Введем понятие поворота точки вокруг точки .
Сначала дадим определение центра поворота.
Определение.
Точку, относительно которой осуществляется поворот, называют центром поворота .
Теперь скажем, что получается в результате поворота точки.
В результате поворота некоторой точки A относительно центра поворота O получается точка A 1 (которая в случае некоторого количества может совпадать с A ), причем точка A 1 лежит на окружности с центром в точке O радиуса OA . Иными словами, при повороте относительно точки O точка A переходит в точку A 1 , лежащую на окружности с центром в точке O радиуса OA .
Считают, что точка O при повороте вокруг самой себя переходит в саму себя. То есть, в результате поворота вокруг центра поворота O точка O переходит в саму себя.
Также стоит отметить, что поворот точки А вокруг точки O стоит рассматривать как перемещение в результате движения точки А по окружности с центром в точке O радиуса OA .
Для наглядности приведем иллюстрации поворота точки А вокруг точки O , на рисунках, расположенных ниже, перемещение точки А в точку А 1 покажем при помощи стрелки.
Полный оборот
Можно выполнить такой поворот точки A относительно центра поворота O , что точка А , пройдя все точки окружности, окажется на прежнем месте. При этом говорят, что точка А совершила вокруг точки O .
Дадим графическую иллюстрацию полного оборота.
Если же не останавливаться на одном обороте, а продолжать движение точки по окружности, то можно выполнить два, три и так далее полных оборотов. На чертеже ниже справа показано, как могут быть произведены два полных оборота, а слева - три оборота.
Понятие угла поворота
Из введенного в первом пункте понятия поворота точки понятно, что существует бесконечное множество вариантов поворота точки А вокруг точки O . Действительно, любую точку окружности с центром в точке O радиуса OA можно рассматривать как точку A 1 , полученную в результате поворота точки А . Поэтому, чтобы отличать один поворот от другого, вводится понятие угла поворота .
Одной из характеристик угла поворота является направление поворота . По направлению поворота судят о том, как осуществляется поворот точки – по часовой стрелке или против часовой стрелки.
Другой характеристикой угла поворота является его величина . Углы поворота измеряются в тех же единицах, что и : наиболее распространены градусы и радианы. Здесь стоит заметить, что угол поворота может выражаться в градусах любым действительным числом из промежутка от минус бесконечности до плюс бесконечности, в отличие от угла в геометрии, величина которого в градусах положительна и не превосходит 180 .
Для обозначения углов поворота обычно используются строчные буквы греческого алфавита: и т.д. Для обозначения большого количества углов поворота часто применяют одну букву с нижними индексами, к примеру, 
.
Теперь поговорим о характеристиках угла поворота подробнее и по порядку.
Направление поворота
Пусть на окружности с центром в точке O отмечены точки A и A 1 . В точку А 1 можно попасть из точки A , выполнив поворот вокруг центра O либо по часовой стрелке, либо - против часовой стрелки. Эти повороты логично считать различными.
Проиллюстрируем повороты в положительном и отрицательном направлении. На чертеже ниже слева показан поворот в положительном направлении, а справа – в отрицательном.
Величина угла поворота, угол произвольной величины
Угол поворота точки, отличной от центра поворота, полностью определяется указанием его величины, с другой стороны, по величине угла поворота можно судить о том, как этот поворот был осуществлен.
Как мы уже упоминали выше, величина угла поворота в градусах выражается числом от −∞ до +∞ . При этом знак плюс соответствует повороту по часовой стрелке, а знак минус – повороту против часовой стрелки.
Теперь осталось установить соответствие между величиной угла поворота и тем, какому повороту она соответствует.
Начнем с угла поворота, равного нулю градусам. Этому углу поворота отвечает перемещение точки А в себя. Другими словами, при повороте на 0 градусов вокруг точки O точка А остается на месте.
Переходим к повороту точки А вокруг точки O , при котором поворот происходит в пределах половины оборота. Будем считать, что точка А переходит в точку А 1 . В этом случае абсолютная величина угла AOA 1 в градусах не превосходит 180 . Если поворот происходил в положительном направлении, то величина угла поворота считается равной величине угла AOA 1 , а если поворот происходил в отрицательном направлении, то его величина считается равной величине угла АОА 1 со знаком минус. Для примера приведем рисунок, показывающий углы поворота в 30 , 180 и −150 градусов.
Углы поворота большие 180 градусов и меньшие −180 градусов определяются на основе следующего достаточно очевидного свойства последовательных поворотов : несколько последовательных поворотов точки A вокруг центра O равносильны одному повороту, величина которого равна сумме величин этих поворотов.
Приведем пример, иллюстрирующий данное свойство. Выполним поворот точки А относительно точки O на 45 градусов, а затем еще повернем эту точку на 60 градусов, после чего повернем эту точку на −35 градусов. Обозначим промежуточные точки при этих поворотах как A 1 , A 2 и A 3 . В эту же точку А 3 мы могли попасть, выполнив один поворот точки A на угол 45+60+(−35)=70 градусов.
Итак, углы поворота, большие 180 градусов, мы будем представлять как несколько последовательных поворотов на углы, сумма величин которых дает величину исходного угла поворота. Например, угол поворота 279 градусов соответствует последовательным поворотам на 180 и 99 градусов, или на 90 , 90 , 90 и 9 градусов, или на 180 , 180 и −81 градус, или на 279 последовательных поворотов по 1 градусу.
Аналогично определяются и углы поворота, меньшие −180 градусов. К примеру, угол поворота −520 градусов можно интерпретировать как последовательные повороты точки на −180 , −180 и −160 градусов.
Подведем итог . Мы определили угол поворота, величина которого в градусах выражается некоторым действительным числом из промежутка от −∞ до +∞ . В тригонометрии мы будем работать именно с углами поворота, хотя слово «поворот» часто опускают, и говорят просто «угол». Таким образом, в тригонометрии мы будем работать с углами произвольной величины, под которыми будем понимать углы поворота.
В заключение этого пункта отметим, что полный оборот в положительном направлении соответствует углу поворота в 360 градусов (или 2·π радианов), а в отрицательном – углу поворота в −360 градусов (или −2·π рад). При этом удобно большие углы поворота представлять как некоторое количество полных оборотов и еще один поворот на угол величиной от −180 до 180 градусов. Для примера возьмем угол поворота 1 340 градусов. Несложно 1 340 представить как 360·4+(−100) . То есть, исходному углу поворота отвечают 4 полных оборота в положительном направлении и последующий поворот на −100 градусов. Другой пример: угол поворота −745 градусов можно интерпретировать как два оборота против часовой стрелки и последующий поворот на −25 градусов, так как −745=(−360)·2+(−25) .
Поворот фигуры вокруг точки на угол
Понятие поворота точки легко расширяется на поворот любой фигуры вокруг точки на угол (речь идет о таком повороте, что и точка, относительно которой осуществляется поворот, и фигура, которую поворачивают, лежат в одной плоскости).
Под поворотом фигуры будем понимать поворот всех точек фигуры вокруг заданной точки на данный угол.
В качестве примера приведем иллюстрацию следующему действию: выполним поворот отрезка AB на угол относительно точки O , это отрезок при повороте перейдет в отрезок A 1 B 1 .
Список литературы.
- Алгебра: Учеб. для 9 кл. сред. шк./Ю. Н. Макарычев, Н. Г. Миндюк, К. И. Нешков, С. Б. Суворова; Под ред. С. А. Теляковского.- М.: Просвещение, 1990.- 272 с.: ил.- isbn 5-09-002727-7
- Башмаков М. И. Алгебра и начала анализа: Учеб. для 10-11 кл. сред. шк. - 3-е изд. - М.: Просвещение, 1993. - 351 с.: ил. - ISBN 5-09-004617-4.
- Алгебра и начала анализа: Учеб. для 10-11 кл. общеобразоват. учреждений / А. Н. Колмогоров, А. М. Абрамов, Ю. П. Дудницын и др.; Под ред. А. Н. Колмогорова.- 14-е изд.- М.: Просвещение, 2004.- 384 с.: ил.- ISBN 5-09-013651-3.
- Гусев В. А., Мордкович А. Г. Математика (пособие для поступающих в техникумы): Учеб. пособие.- М.; Высш. шк., 1984.-351 с., ил.
Поворот растрового изображения на углы, кратные 90°, относительно геометрического центра изображения – задача тривиальная и решается без потери качества простым преобразованием координат каждого пикселя.
Ниже мы рассмотрим алгоритм прецизионного поворота растрового изображения на произвольный угол относительно произвольного центра с минимальными потерями.
Выражаю благодарность Харченко Владиславу Владимировичу за оказанную помощь.
Алгоритм
Из вышеприведённого рисунка видно, что после поворота растрового изображения, цвет каждого пикселя итогового изображения определяется сложением цветов нескольких «осколков» нескольких пикселей исходного изображения, пропорционально площадям соответствующих «осколков». Поэтому в общем виде решение нашей задачи будет состоять в том, чтобы найти площади всех «осколков» для каждого пикселя исходного изображения и собрать цвет каждого пикселя итогового изображения из цветов соответствующих «осколков» .
В качестве модели пикселя исходного изображения мы будем использовать квадрат со стороной = 1, с такими обозначениями углов:
i1 - самый правый угол;
i2 - самый нижний угол;
i3 - самый левый угол;
i4 - самый верхний угол.
Моделью итогового изображения будет сетка из параллельных горизонтальных и вертикальных линий с расстоянием между линиями = 1.
Координаты центра поворота растрового изображения, в таком представлении, могут быть выражены парой произвольных вещественных чисел. То есть центр поворота в нашей задаче может лежать не в геометрическом центре пикселя и не в точке пересечения линий сетки, а в произвольной точке декартовых координат.
Поскольку при повороте растрового изображения квадрат каждого пикселя поворачивается на один и тот же угол (относительно центра этого пикселя) мы будем решать задачу для одного пикселя, а потом применим полученное решение для каждого пикселя исходного изображения.
Поворот растрового изображения можно разделить на две части:
1. Поворот квадрата каждого пикселя исходного изображения относительно центра этого квадрата на заданный угол.
2. Смещение центра квадрата пикселя в соответствии с углом поворота изображения относительно центра поворота изображения таким образом, чтобы квадрат занял своё итоговое положение на сетке итогового изображения.
При этом сетка итогового изображения рассекает квадрат каждого пикселя исходного изображения на «осколки» в количестве 4, 5 или 6 штук.
Чтобы систематизировать разнообразие получающихся вариантов мне пришлось составить таксономию всевозможных пересечений квадрата пикселя исходного изображения с сеткой итогового изображения. Существенно разных вариантов оказалось всего 23:
Условные обозначения здесь следующие:
- цифры в ячейках обозначают номера углов квадрата пикселя, которые попали в данную ячейку сетки итогового изображения после поворота изображения;
- зелёным цветом обозначены ячейки, в которые попали участки пикселя и гарантированно оставили там по «осколку»;
- жёлтым цветом обозначены ячейки, в которые, в зависимости от условий, могут
попасть (а могут и не попасть) «осколки» квадрата пикселя, образованные не углами квадрата, а сторонами квадрата.
Для наглядности приведу одну из возможных вариаций варианта №3:
Как видим, верхняя правая ячейка не содержит в себе «осколка» пикселя, хотя при других условиях поворота могла бы содержать.
Чтобы не нагружать читателя детальными геометрическими выкладками, скажу сразу, что во всех этих 23-х вариантах пиксель исходного изображения рассекается на «осколки», площадь которых легко вычисляется комбинированием 4-х формул. Ниже приведены эти формулы с иллюстрациями. Красным цветом обозначены линии сетки итогового изображения, которые рассекают квадрат пикселя. Жёлтым цветом закрашена область, площадь которой вычисляется формулой.
Формула 1
Эта формула не используется для расчёта окончательной площади «осколка», но её удобно использовать для быстрого расчёта вспомогательных промежуточных площадей, поскольку нам заведомо известно, что площадь всего пикселя = 1.
В качестве входных переменных во всех формулах используются высоты, опущенные из углов квадрата на сетку итогового изображения, по той простой причине, что расчёт этих высот сводится к мгновенному выделению дробной части числового значения координаты соответствующего угла квадрата пикселя.
Формула 2
Данная формула используется только в вариантах 1 и 2.
Формула 3
Часто используемая формула - очень хорошо, что она быстро вычисляется. Поскольку угол поворота одинаков для каждого пикселя - все тригонометрические функции можно посчитать один раз, перед обработкой всех пикселей, и далее использовать эти значения в цикле как константы.
Формула 4
Эта формула вычисляется в два этапа. Сначала вычисляется выражение в скобках. Если оно принимает положительное значение, то вычисляется площадь. Если значение отрицательное, значит от пикселя не отсекается «осколок», образованный углом сетки и стороной квадрата и дальнейшие вычисления производить не имеет смысла.
С учётом всего вышесказанного, в общем виде алгоритм будет выглядеть так:
1. Загружаем в память ЭВМ исходное изображение.
2. Рассчитываем размеры итогового изображения в пикселях.
3. Создаём промежуточный двумерный массив, каждый элемент которого содержит 3 составляющие цвета RGB в формате числа с плавающей запятой. Размеры массива равны размерам итогового изображения.
4. Последовательно перебираем все пиксели исходного изображения; поворачиваем каждый из них на заданный угол и располагаем на сетке итогового изображения, рассчитав 4 координаты углов квадрата пикселя; классифицируем пиксель по 23 вариантам и считаем площади «осколков»; добавляем в соответствующие элементы промежуточного массива цвета полученных «осколков» пропорционально площади этих «осколков».
5. После обработки всех пикселей исходного изображения округляем значения RGB в промежуточном массиве до целого значения для каждого элемента и создаём на базе этих целых значений итоговое изображение в формате BMP.
Программа
На основании приведённого алгоритма была написана программа для Windows. Исходные коды на Object Pascal и скомпилированный исполняемый файл можно скачать .
Интерфейс программы.
По нажатию на кнопку «Open...» открывается диалог выбора BMP-файла. Поддерживаются битмапы только с 24-битной палитрой. Открытое изображение отображается в окне. В заголовке окна выводится полный путь к файлу и размеры изображения.
В поле «Angle» задаётся угол поворота в градусах – любое положительное число.
В качестве десятичного разделителя при вводе дробных чисел может быть использована как точка, так и запятая.
Радиокнопками «CW» и «CCW» задаётся направление вращения: «по часовой стрелке» и «против часовой стрелки», соответственно.
В блоке «Background color» можно задать цвет фона, с которым будут смешиваться граничные пиксели изображения. По умолчанию цвет фона – чёрный.
В полях «Centre X» и «Centre Y» задаются координаты центра поворота. При этом следует учитывать, что начало координат находится в левом верхнем углу изображения и Y увеличивается вниз. По умолчанию центр поворота устанавливается в геометрическом центре загруженного изображения.
По нажатию на кнопку «Rotate» либо по нажатию на клавишу Enter изображение поворачивается на заданный угол относительно заданного центра поворота и отображается в окне. Поворот изображения на углы, кратные 90°, реализован по упрощённой схеме, путём простого преобразования координат пикселей исходного изображения, при этом значения «Centre X» и «Centre Y» игнорируются.
Время работы алгоритма в секундах отображается под кнопкой «Rotate».
Через кнопку «Save…» повёрнутое изображение можно сохранить в BMP-файл.
Если итоговое изображение не помещается в окне – оно подгоняется к границам окна API-функцией StretchBlt – поэтому оценить реальное качество больших картинок можно только по сохранённому BMP-файлу.
Для поворота изображения на другой угол его не нужно загружать повторно - поворачивается изображение из выбранного файла, а не отображённое в данный момент в окне.
Изображение с размерами 1024 х 768 на машине с четырёхядерным процессором 2,67 ГГц поворачивается данной программой на произвольный угол, в среднем, приблизительно, за 0,5 секунды. Изображение с размерами 4000 х 4000 - примерно за 10 секунд. Время работы алгоритма для разных углов может отличаться в связи с тем, что изображение при разных углах дробится на разное количество «осколков», на вычисление площадей которых суммарно тратится, соответственно, разное время.
Промежуточный массив, содержащий информацию о цвете пикселей итогового изображения в формате числа с плавающей запятой, реализован на типе extended (10 байт), поэтому обработка больших изображений (примерно более 5000 х 5000 пикселей) может вызвать ошибку переполнения памяти. Улучшить ситуацию возможно, применив менее точный тип данных и сохраняя целую часть числа сразу в итоговый битмап, оставляя во вспомогательном массиве только дробную часть.
Результаты
Проведём сравнительный анализ работы прецизионного алгоритма и алгоритма поворота изображений, реализованного в программе Photoshop.
Тест 1
Для первого теста я взял очень простое изображение - горизонтальную линию чёрного цвета толщиной 1 пиксель и длиной 10 пикселей, смещённую относительно центра белого квадрата с размерами 100 х 100 пикселей:
После чего я повернул данное изображение относительно геометрического центра на 3° по часовой стрелке. Вот сравнительный результат (увеличено в 24 раза):
Прецизионный алгоритм
Photoshop CS6 (64 Bit)
Очевидно, что алгоритм Photoshop вносит определённые искажения в изображение. Попутно отметим, что алгоритм поворота, реализованный в Photoshop, не претерпел за 10 лет каких-либо ощутимых изменений.
Тест 2
Для второго теста я выбрал тюльпан из стандартного дистрибутива Win7:
После поворота данного изображения на 5° по часовой стрелке относительно геометрического центра я суммировал цвет всех пикселей в разрезе каналов RGB. Вот результат для прецизионного алгоритма и алгоритма Photoshop:
Числа в скобках показывают абсолютное отклонение данного показателя от оригинала.
Цвет изображения после прецизионного поворота и до округления практически не поменялся - чего и следовало ожидать.
Самое большое отклонение, в данном конкретном случае, мы обнаруживаем по каналу G для алгоритма Photoshop. В процентном отношении это отклонение составляет всего 0,06%, поэтому «на глаз» оно не заметно, но из соображений перфекционизма результат у Photoshop получается хуже, чем у прецизионного алгоритма.
Важно отметить, что округление цвета каждого пикселя в прецизионном алгоритме до целочисленного значения, необходимого для формата BMP, необратимо уничтожает часть информации о цвете.
Для визуального сравнения двух алгоритмов приведу увеличенный фрагмент изображения,
повёрнутого на 5° по часовой стрелке, соответственно, Photoshop"ом:
и прецизионным алгоритмом:
Сравнительный анализ показывает, что Photoshop лучше сохраняет контрастные элементы изображения, но при этом создаёт «ореолы» искажённого цвета. Прецизионный алгоритм не искажает цвет но при этом несколько «размывает» изображение.
Выводы
1. Прецизионный и при этом сравнительно быстрый поворот растрового изображения на произвольный угол - возможен. Для меня остаётся загадкой вопрос, почему в профессиональных графических редакторах нет опции, позволяющей пользователю повернуть изображение предельно точно за чуть большее время.
2. Несмотря на предельную точность рассмотренного алгоритма, обратное преобразование изображения, т.е. поворот на противоположный угол без потери качества - невозможен, потому что округление точного значения цвета (в формате числа с плавающей запятой) необратимо уничтожает часть информации о цвете.
3. С точки зрения визуального восприятия контрастных деталей лучший результат даёт подоптимальный алгоритм. Прецизионный алгоритм имеет смысл применять в тех случаях, когда важно сохранить максимум информации о цвете изображения.
Среди множества терминов тригонометрии важным является понятие угла поворота. В данной статье рассмотрим поворот и все соответствующие ему определения; дадим представление о полном обороте; изучим угол поворота и его характеристики, а также поворот фигуры вокруг точки. Для лучшего понимания теория будет снабжена иллюстрациями и практическими примерами.
Yandex.RTB R-A-339285-1 Определение 1
Центр поворота – точка, относительно которой осуществлен поворот.
Рассмотрим, что происходит в результате поворота точки. Пусть некоторая точка А поворачивается относительно центра поворота О, в результате чего получается точка А 1 (при совершении некоторого количества полных оборотов она может совпасть с точкой А). При этом точка А 1 лежит на окружности с центром в точке О радиуса О А. Другими словами, когда точка А осуществляет поворот относительно точки О, она переходит в точку А 1 , лежащую на окружности с центром О радиуса О А.
Считается, что в данном случае точка О при осуществлении поворота вокруг самой себя переходит в саму себя. Или: когда точка О осуществляет поворот вокруг центра поворота О, она переходит в саму себя.
Отметим также, что поворот точки А относительно центра О нужно рассматривать, в том числе, как перемещение в результате движения точки А по окружности с центром в точке О радиуса О А.
Изобразим графически поворот точки А относительно точки О, перемещение точки А в точку А 1 отметим стрелкой:
Возможно осуществить поворот точки А относительно центра поворота О таким образом, что точка А, пройдя все точки окружности, вернется на прежнее свое место. Тогда говорим, что точка совершила полный оборотвокруг точки О.
Проиллюстрируем:
Если движение точки А по окружности продолжится, то будет выполнено два, три и так далее полных оборотов. На иллюстрации ниже справа отображено два полных оборота, а слева – три:
В рамках всего вышесказанного можно также говорить о частях полного оборота. Например, о половине оборота или трети, или четверти и так далее.
Угол поворота
Из указанного выше понятия поворота точки очевидно, что возможно бесконечное множество вариаций поворота точки А относительно центра О. Любую точку окружности с центром О можно рассматривать как точку А 1 , полученную в результате поворота точки А. Поэтому для определения отличия одного поворота от другого вводится понятие угла поворота.
Угол поворота имеет свои характеристики, одна из которых – направление поворота. По нему определяют, как перемещалась точка – по часовой стрелке или против.
Еще одной характеристикой угла поворота служит его величина. Углы поворота имеют ту же единицу измерения, что и углы в геометрии: наиболее распространены градусы и радианы. Отметим, что угол поворота может выражаться в градусах любым действительным числом в промежутке от - ∞ до + ∞ , что отличает его от угла в геометрии, который выражается только положительным числом, не превосходящим 180 ° .
Чтобы обозначить углы поворота, стандартно используют буквы греческого алфавита: α , β , γ и так далее. Чтобы обозначить большое количество углов поворота, применяют одну и ту же букву с различными нижними индексами: α 1 , α 2 , α 3 … . . α n .
Разберем характеристики угла поворота подробнее.
Отметим на окружности с центром О точки А и А 1 . В точку А 1 возможно попасть, совершив точкой А поворот относительно центра О либо по часовой стрелке, либо – против. Очевидно определять эти повороты, как различные.
Приведем графическую иллюстрацию различных поворотов: слева на чертеже – поворот в положительном направлении; справа – в отрицательном.
Угол поворота точки, не являющейся центром поворота, в полной мере определяется указанием его величины. С другой стороны, по величине угла поворота можно определить, каким образом поворот был осуществлен.
Как было сказано выше, величина угла поворота варьируется в пределах от - ∞ до + ∞ ;
Определение 2
Знак плюс определяет поворот против часовой стрелки, а минус – по часовой стрелке.
Необходимо установить соответствие между самой величиной угла поворота и тем, какому повороту она соответствует.
Пусть угол поворота равен 0 ° . Такому углу поворота соответствует перемещение точки в саму себя. Иначе говоря, при повороте вокруг точки О на 0 ° точка A остается на месте.
Теперь предположим, что поворот точки А происходит в пределах половины оборота: пусть точка А переходит в точку А 1 . В таком случае абсолютная величина угла А О А 1 , выраженная в градусах, не превосходит 180 . Если поворот имел положительное направление, то величина угла поворота считается равной величине угла А О А 1 ; если отрицательное – величина угла поворота равна величине угла А О А 1 со знаком минус. Для иллюстрации этих утверждений отобразим на чертеже углы поворота в 30 ° , 180 ° и - 150 °:
Углы поворота, превышающие 180 или меньшие – 180 определяются, исходя из очевидного свойства последовательных поворотов:
Определение 3
Несколько последовательных поворотов точки А относительно центра О равносильны одному повороту, величина которого равна сумме величин этих поворотов.
Рассмотрим пример, который даст нам возможность графически проиллюстрировать описанное свойство. Пусть точка А выполняет поворот относительно центра О на 45 ° , затем еще на 60 ° и еще раз - на - 35 ° . Обозначим промежуточные точки поворотов А 1 , А 2 и А 3 . В конечную точку А 3 возможно было попасть, совершив один поворот на угол поворота, величина которого равна: 45 ° + 60 ° + (- 35 °) = 70 ° . Проиллюстрируем:
Таким, образом, углы, превышающие 180 ° , будем представлять, как несколько последовательных поворотов на углы, сумма величин которых определяет величину исходного угла поворота. Например, угол поворота 298 ° соответствует последовательным поворотам на 180 ° и 118 ° , или 90 ° , 90 ° , 90 ° и 28 ° , или 180 ° , 180 ° и - 62 ° , или 298 последовательных поворотов на 1 ° .
По такому же принципу определяются углы меньше - 180 ° . Например, угол поворота - 515 ° можно определить, как последовательные повороты на - 180 ° , - 180 ° и - 155 ° .
Нами был определен угол поворота, и его величина выражается в градусах некоторым действительным числом в пределах от - ∞ до + ∞ . Тригонометрия работает именно с углами поворота, хотя для удобства слово «поворот» опускают и говорят «угол». Т.е. будем рассматривать углы произвольной величины, понимая под ними углы поворота.
В заключение также отметим, что полный оборот в положительном направлении соответствует углу поворота в 360 ° или 2 π радиан. Соответственно при отрицательном направлении полный оборот будет соответствовать углу в - 360 ° или - 2 π радиан.
При этом удобно большие углы поворота представлять, как некоторое количество полных оборотов и еще один на величину в пределах от - 180 ° до 180 ° . К примеру, поворот осуществляется на 1478 ° . Представим эту величину как: 360 · 4 + 38 , т.е. заданному углу поворота соответствуют 4 полных оборота и еще один поворот – на 38 ° . Или еще один пример: угол поворота в - 815 ° можно представить, как (- 360) · 2 + (- 95) , т.е. заданному углу поворота соответствуют 2 полных оборота в отрицательном направлении (против часовой стрелки) и еще один поворот того же направления на - 95 ° .
Понятие поворота точки легко распространить на поворот любой фигуры вокруг точки на угол (такой поворот, при котором и точка, относительно которой осуществляется поворот, и сама поворачиваемая фигура лежат в одной плоскости).
Определение 3
Поворот фигуры – это поворот всех ее точек вокруг заданной точки на заданный угол.
Как пример, иллюстрируем следующее действие: поворот отрезка А В на угол α относительно точки О – при повороте заданный отрезок перейдет в отрезок А 1 В 1 .
Если вы заметили ошибку в тексте, пожалуйста, выделите её и нажмите Ctrl+Enter
