Масштабирование, поворот и сдвиг растра методом суперсемплинга

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

Соответствующие функции были успешно созданы и внедрены, а поскольку они могут представлять интерес для широкой общественности, я решил опубликовать готовую утилиту с открытым кодом и пояснениями.

Утилита и исходные коды размещены в архиве здесь.

Среда разработки: Delphi/Object Pascal.

Свободное использование и распространение приветствуются.

Ниже мы рассмотрим теорию и практику.



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

Коротко суть метода


Растровое изображение можно представить как прямоугольник, сложенный из квадратов одинакового размера. Каждый квадрат (пиксель изображения) окрашен сплошным однородным цветом. Если растр получен в результате фотографирования, то, с некоторыми допущениями, можно сказать, что за каждым пикселем находилось некое исходное детальное изображение, которое безвозвратно утеряно и представлено в виде квадрата усреднённого цвета. Таким образом, пиксель представляет собой хэш, свёртку для бесконечного множества разных изображений. И определить точно, хэшем какого именно детального изображения является данный пиксель, без дополнительной информации невозможно.

Например, если любое из этих трёх изображений



попало бы в объектив фотоаппарата так, чтобы его угловой размер соответствовал одному пикселю, то на фотографии каждая из этих трёх картинок была бы представлена вот таким пикселем (увеличен в 225 раз):


Очевидно, что все детали безвозвратно утеряны.

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

Обычно конечным оценщиком качества полученного после трансформации изображения является человеческое зрение и поэтому популярные методы преобразований ориентированы на то, чтобы получить чёткое изображение с контрастными деталями для комфортного восприятия человеком. Но не всегда человек является финальным звеном в использовании изображения и не всегда контрастные детали — это главный критерий качества. Иногда важнее сохранить информацию о цвете и пространственных нюансах изображения.

Любые методы трансформации растра (в частности, масштабирование и поворот), которые используют информацию от нескольких соседних пикселей (например, фильтр Ланцоша или бикубическая интерполяция) фактически пытаются «угадать» утерянную информацию, частично воссоздать по соседним пикселям ту картинку, которая находилась «за» пикселями. Настолько, насколько это позволяет метод. Но это неизбежно приводит к искажениям цвета и геометрии изображения.

Поэтому, если в качестве входных данных у нас есть только растр и никакой другой дополнительной информации нет, то справедливым будет предположение, что конкретно вот эта матрица цветных квадратов и есть исходное изображение для осуществления необходимых преобразований. Результат попиксельной работы с растром неизбежно получится более размытым, чем исходное изображение, но при этом максимально сохранится исходная информация без дополнительных искусственных искажений.

Метод суперсемплинга предполагает, что цвет каждого пикселя итогового изображения рассчитывается как сумма цветов частей соответствующих пикселей исходного изображения, взятых пропорционально площадям этих частей, полученных после преобразования. Разберём по порядку масштабирование, поворот и сдвиг.

Масштабирование


Рассмотрим рисунок. Штриховкой обозначен пиксель исходного изображения, увеличенный для примера по оси Х на 2,5 и по оси Y на 1,5, и расположенный на сплошной сетке пикселей итогового изображения:



Как видно из рисунка, пиксель исходного изображения после масштабирования определил цвет сразу 2-х верхних пикселей итогового изображения. Цвет пограничных пикселей, в зависимости от параметров преобразования, может формироваться из цветов 2-х или 4-х пикселей исходного изображения, пропорционально отсекаемым площадям. Например, для формирования цвета нижнего правого пикселя (на рисунке) от исходного пикселя будет взята только 1/4.

При коэффициентах масштабирования меньше единицы цвет каждого пикселя итогового изображения формируется путём усреднения цветов, как минимум, двух пикселей исходного изображения, так же пропорционально площадям, отсекаемых сеткой итогового изображения.

Для ознакомления с другими методами масштабирования могу порекомендовать эти статьи на Хабре:

habr.com/ru/post/243285
habr.com/ru/post/340966

Поворот




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

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

Если исходное изображение должно быть подвергнуто и повороту, и масштабированию, то для коэффициентов масштабирования больше единицы следует осуществлять сначала масштабирование, а затем поворот. Рассмотрим на примере.

Это исходное изображение:



Оно сначала было подвергнуто масштабированию с коэффициентом 4, а затем осуществлён поворот на 10° по часовой стрелке, в результате получено следующее изображение:



А здесь наоборот, сначала изображение было подвергнуто повороту, а затем – масштабированию:



Как видим, артефакты, возникшие вследствие поворота, после масштабирования увеличились в размерах. По этой же причине, для коэффициентов масштабирования меньше единицы, следует сначала осуществлять поворот, и только потом масштабирование, чтобы уменьшить влияние этих артефактов на итоговое изображение. Но только при условии, что коэффициенты масштабирования по осям X и Y равны.

Если же коэффициенты масштабирования по осям X и Y не равны, то, в случае необходимости сохранения пропорций исходного изображения, всегда сначала необходимо выполнять масштабирование, и только потом поворот. В качестве примера возьмём зелёный квадрат из примера выше. Сначала изменим масштаб по оси Х в 2 раза и по оси Y в 4 раза, а затем повернём на 10° по часовой стрелке:



А теперь сначала повернём на 10°, после чего изменим масштаб по оси Х в 2 раза и по оси Y в 4 раза:



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

Сдвиг


Процедура сдвига используется в том случае, когда для получения итогового изображения нужно совместить друг с другом встык несколько фрагментов. При этом может понадобиться совмещать края фрагментов не только с точностью до целых пикселей, но и долей пикселя. Сдвиг может осуществляться либо по одной из осей, либо по двум осям. На рисунке для примера изображён вариант сдвига пикселя по оси Х вправо на 0,5 пикселя:



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

На следующем рисунке изображён вариант сдвига по двум осям – по оси Х вправо на 0,5 пикселя и по оси Y вниз на 0,5 пикселя:



В таком случае для формирования цвета пикселя итогового изображения в расчёт берутся цвета ровно четырёх пикселей исходного изображения. Пиксели, выходящие за пределы изображения при сдвиге, обрезаются. А пиксели, находящиеся на противоположном крае исходного изображения, смешиваются с заданным цветом фона.

Примечание для программистов


Для удобства использования рассмотренных процедур в приложениях, все необходимые типы данных, переменные и подпрограммы вынесены в модуль RSSUtils.pas. Файл модуля достаточно разместить в корневом каталоге проекта и указать его имя в разделе uses. После чего из модуля могут быть вызваны следующие процедуры:

ScalePic (SursBit, ResBit:pbit; SclX, SclY:extended; FonR, FonG, FonB:byte) – масштабирование;
RotatePic (SursBit, ResBit:pbit; Ugol:extended; CX, CY:extended; FonR, FonG, FonB:byte) – поворот;
ShiftPic (SursBit, ResBit:pbit; ShX, ShY:extended; FonR, FonG, FonB:byte) – сдвиг, где

SursBit, ResBit – указатели на переменные типа TBitmap для исходного и итогового изображений, соответственно;
SclX, SclY – коэффициенты масштабирования по осям X и Y, соответственно;
Ugol – угол поворота изображения в градусах по часовой стрелке;
CX, CY – координаты центра поворота относительно исходного изображения;
ShX, ShY – величина смещения в пикселях по осям X и Y, соответственно;
FonR, FonG, FonB – RGB-составляющие цвета фона, для замощения участков изображения, не покрытых исходным изображением после трансформации.

Для каскадного применения преобразований нужно вызывать соответствующие процедуры
последовательно, передавая указатель на итоговый битмап предыдущей процедуры в
качестве указателя на исходный битмап для последующей процедуры. Процедуры работают только с 24-битными битмапами.
AdBlock похитил этот баннер, но баннеры не зубы — отрастут

Подробнее
Реклама

Комментарии 11

    0
    При уменьшении размера с фактором, например 7/8 или 2/3, данный метод даст очень сильный алиасинг. Но в принципе, сохранение интеграла(как у Вас) — это неплохой метод. Когда пихелей много и данные уже отфильтрованы по Найквисту, лучшие методы (ИМХО): сдвиг — в Фурье пространстве и поворот — в Радоне(тоже через Фурье).
      0

      Изображения реального мира практически никогда не ограничены по частотам. И работа с коэффциентами масштабирования, близкими к единице — это боль. Самый лучший способ масштабирования в данном случае — это увеличение в 2 раза нейросеткой, а затем уменьшение с нужным коэффициентом.

        +1
        Все зависит от задачи. Суньте нейросетку в телефон, только потом не удивляйтесь почему он батарейку за час сажает. А если изображения с томографа или просто x ray медицинский то и просто нельзя нейросетку ставить(и вот тут как раз пихели уже лимитированы по частоте )
      +1

      Вижу здесь несколько заблуждений:


      1. Пиксели квадратные.
      2. Значение пикселя равно суммарной интенсивности света, попавшего на пиксель.
      3. Пиксели все одинаковые.

      На самом же деле:


      1. Не существует RGB-пикселей, перед каждым пикселем в матрице стоит светофильтр (обычно красный, зелёный или синий). То есть в каждом пикселе у нас есть R, G или B (иногда Y), но не RGB. Изображение с RGB-пикселями затем восстанавливается программными методами.


      2. Перед каждым пикселем матрицы находится микролинза, фокусирующая свет в центре пикселя. Дополнительно перед этим хозяйством размещается матовая плёнка, основной смысл которой — немного подразмыть изображение, чтобы устранить алиасинг.


      3. Реальный PSF пикселя близок к функции Гаусса, а не к индикаторной функции для квадрата.



      Ну и насчёт суперсэмплинга: его смысл — построение промежуточного изображения в более высоком разрешении. Как это применяется для масштабирования и поворота: сначала увеличиваем очень хорошим алгоритмом изображение в 2-4 раза, затем делаем преобразования, затем качественно уменьшаем в 2-4 раза.

        0
        Пиксели квадратные или нет — это неважно. Важно их количество. И да, их необходимо размывать физически, до семплинга или семплировать с более чем двойной частотой
        гауссиан

        Ну да, любое ядро превращается в гауссиан. (Central limit theorem)
        Соответственно свертка и дельта функции и квадрата с гауссианом все равно дадут гауссиан.
          +1

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


          И PSF пикселя таки довольно близка к прямоугольному импульсу. Вот PSF оптоэлектронной системы в целом уже ближе в Гауссу.

            0

            Ну так это надо сразу оговаривать. Специфика задачи же накладывает свои ограничения.


            Автор же работает со спутниковыми снимками, где конструкция камеры может сильно отличаться.

            Примеры изображений больше похожи на аэрофотосъёмку — там используются обычные матрицы. А вот в спутниках — да, возможна экзотика.


            И PSF пикселя таки довольно близка к прямоугольному импульсу. Вот PSF оптоэлектронной системы в целом уже ближе в Гауссу.

            Ну так нас система в целом и интересует. Я по работе немного заморачивался с вычислением PSF камер (правда, в мобильниках) — везде ядро получалось радиально-симметричным.

              0
              Примеры изображений больше похожи на аэрофотосъёмку — там используются обычные матрицы.

              Да, действительно. Я подумал что это просто произвольные примеры из интернета. Но возможно автор действительно имеет дело в аэрофотосъёмкой.

                0
                Аэрофотосъёмку я показать не могу, у меня к ней нет даже доступа, моя задача была только в написании функций. Здесь представлены просто картинки из интернета, в качестве примера.
          0

          Позвольте я тут глупый вопрос задам? Почему нельзя было найти готовое решение, а нужно было именно своё?

            +1
            Меня попросили — я сделал. Может быть где-то и есть готовое решение именно для метода суперсемплинга, но ни я, ни мои коллеги его не нашли. Готовые методы, которые можно сравнительно легко найти с открытым кодом, ориентированы на человеческое зрение и вносят в изображение специфические искажения, которых заказчик хотел избежать. Здесь же постобработка (векторизация) проводилась машиной, поэтому некоторая размытость изображения после трансформации (а это, в сущности, единственное искажение, вносимое алгоритмом) не критична.

          Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

          Самое читаемое