Функция изменения размера изображения, предоставленная Emgu (оболочка.net для OpenCV), может использовать любой из четырех методов интерполяции :

• CV_INTER_NN (по умолчанию)
• CV_INTER_LINEAR
• CV_INTER_CUBIC
• CV_INTER_AREA

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

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

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

4 ответов

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

Линейная интерполяция менее быстрая, но не приведет к потере информации, если вы не уменьшаете изображение (которое вы есть).

Кубическая интерполяция (вероятно, фактически "Бикубическая") использует одну из многих возможных формул, которые включают в себя несколько соседних пикселей. Это намного лучше для сокращения изображений, но вы по-прежнему ограничены в отношении того, сколько вы можете уменьшить без потери информации. В зависимости от алгоритма вы можете уменьшить свои изображения на 50% или 75%. Основной подход этого подхода заключается в том, что он намного медленнее.

Не уверен, что такое "area" - на самом деле это может быть "Bicubic". По всей вероятности, этот параметр даст лучший результат (с точки зрения потери/появления информации), но за счет самого продолжительного времени обработки.

Используемый метод интерполяции зависит от того, чего вы пытаетесь достичь:

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

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

Алгоритмы: (описания из документации OpenCV)

• INTER_NEAREST - интерполяция ближайшего соседа
• INTER_LINEAR - билинейная интерполяция (используется по умолчанию)
• INTER_AREA - повторная выборка с использованием отношения области пикселей. Это может быть предпочтительный метод для прореживания изображения, поскольку он дает результаты без муара. Но когда изображение масштабируется, оно похоже на метод INTER_NEAREST.
• INTER_CUBIC - бикубическая интерполяция по окрестности 4x4 пикселей.
• INTER_LANCZOS4 - интерполяция Lanczos в окрестности 8x8 пикселей

Если вы хотите увеличить скорость, используйте метод Nearest Neighbor.

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

В старые недобрые времена многие продавцы предпочли бы называть в качестве спецификации интерполированное значение разрешающей способности, если бы они его знали. В то время разрешающая способность была ниже (до появления доступных пленочных сканеров), поэтому искушение было очень велико. Так у планшетных сканеров, которые используются для получения изображений фотографий и подобных продуктов, реальное оптическое разрешение могло быть 300x300 выборок на дюйм. С помощью магии интерполяции тот же самый сканер мог выдавать поддельное разрешение в 600x600 выборок на дюйм или даже 1200x1200 выборок на дюйм. И именно это рекламировали бы продавцы. Доверчивые покупатели могли бы думать, что они покупают сканер с разрешением 1200x1200 выборок на дюйм, тогда как большая часть дополнительной четкости была бы математическим "шаманством".

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

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

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

Не путайте интерполяцию с изменением масштаба. При увеличении масштаба изображения каждый пиксель дублируется определенное количество раз. Чтобы увеличить размер изображения втрое, каждый пиксель дублируется трижды. То же самое происходит при уменьшении масштаба изображения. При простом изменении масштаба уменьшение размера изображения на одну треть от оригинала означает отбрасывание каждого третьего пикселя (в надежде, что оставшиеся пиксели все-таки сохранят некое подобие оригинала). В любом случае на получившемся изображении, скорее всего, будут грубые края или "лесенки" на диагональных линиях.

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

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

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

Поскольку в таком случае нужно проверять только каждый второй пиксель, это достаточно быстрый метод, хотя и не очень точный. Он не подходит для большей части фотографических изображений, содержащих плавные переходы между отдельными участками, поскольку дает в них заметно более зубчатые края. Если вы сканируете изображение с четкими границами, например, фрагмент текста или изображение, которое будет сохраняться в формате GIF, алгоритм ближайших соседей будет вполне пригоден. В таких случаях он дает меньшие файлы, при этом эффективно сохраняя резкие границы. На рис. 3.4 изображена буква А (один из типов изображений, для которых достаточно хорошо работает алгоритм ближайших соседей), а на рис. 3.5 показана увеличенная на 600% часть этой буквы после обработки с помощью данного.

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

- Бикубический метод . Самый распространенный метод интерполяции - бикубический, при котором для получения информации для создания новых, интерполированных пикселей, проверяются все окружающие пиксели. Этот метод используется по умолчанию во многих сканерах, а также в Photoshop. В последней версии Photoshop к основному алгоритму бикубической интерполяции добавлены еще два варианта - бикубическое сглаживание (Bicubic Smoother), лучше всего сглаживающее зубцы при увеличении изображения, и бикубическое увеличение резкости (Bicubic Sharper), сохраняющее детали при выполнении субдискретизации для уменьшения изображения. Бикубическая интерполяция показана на рис. 3.7.

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

Какая-то интерполяция происходит при любом сканировании с разрешением, отличным от естественного разрешения сканера. Например, если реальное разрешение вашего сканера составляет 4000 выборок на дюйм, то всякий раз, когда вы сканируете с разрешением, скажем, 2000 spi, желая уменьшить размер файла для не очень важных изображений, конечное изображение формируется в помощью интерполяции. Если же сканер с разрешающей способностью 4000 spi позволяет выполнять сканирование с разрешением 8000 spi, интерполяция запускается для имитации более высокого разрешения. В некоторых сканерах интерполяция выполняется аппаратно при создании отсканированного изображения, тогда как в других этот этап выполняется с помощью программного обеспечения на компьютере.

Изменение разрешения путем интерполяции изображения

Лекция: Adobe Photoshop CS5 для дизайнера и фотографа

Adobe Photoshop CS5 - последняя версия легендарного графического редактора. Сам перевод названия программы "Фотомагазин" говорит о том, что это программа для фотографов. Программное обеспечение Adobe® Photoshop® CS5, соответствует мировым стандартам, позволяет создавать профессиональные изображения на высшем уровне. В новой версии вы сможете рисовать реалистичные иллюстрации, быстро создавать эффектные изображения HDR, устранять шумы, добавлять зернистость и настраивать виньетирование с помощью самых современных инструментов для обработки фотографий. В лекциях мы не будем глубоко вникать в теорию компьютерной графики, а заострим внимание на практике работы с фотоизображениями.

Основные понятия компьютерной графики

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

Разрешение изображения

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

Количество пикселей в изображении определяет его разрешение. Пиксели часто называют точками, тогда разрешение измеряется в dpi (dot per inch), то есть в количестве точек на дюйм.

Примечание

В компьютерной литературе существует путаница в терминах и некоторые из авторов разрешение мониторов измеряют в dpi (dot per inch), сканеров в ppi (pixel per inch) - пиксель на дюйм, а принтеров в lpi (line per inch) - линий на дюйм. Другие же авторы книг разрешение любого изображения, не зависимо от способа его получения измеряют только в dpi.

Если вдуматься, то становится очевидным, что чем выше разрешение, тем большее количество пикселей содержит изображение и тем большим количеством деталей (то есть - качеством) такое изображение характеризуется. С другой стороны, более высокое разрешение изображение прямо связано с большим размером файла такого изображения. Поэтому установка величины разрешения зависит от целей и задач компьютерного художника и для конкретной работы будет разной. Например, веб-дизайнеры обычно работают с изображениями 72-96 dpi, в то время как полиграфисты предпочитают разрешения изображений от 300 dpi и выше (рис. 1.1).

Рис. 1.1. Изображение высокого разрешения слева (файл 977 Кб) и низкого разрешения справа (файл 41 Кб)

Глубина цвета

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

Новый термин

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

Для примера на рис. 1.2 показано одно и то же изображение, но с разной глубиной цвета: в два цвета сверху, и в 256 оттенков серого снизу. Из этой иллюстрации наглядно видно, что чем выше число воспроизводимых градаций яркости пикселя в черно-белых изображениях (и количество отображаемых цветов в цветном изображении), тем качество растрового изображения выше.

Рис. 1.2. Одно и то же изображение, но с разной глубиной цвета

С точки зрения цветовой глубины растровые изображения можно разбить на несколько типов:

Для монохромного черно-белого (Black and White) изображения используются только два типа ячеек: черные и белые. Поэтому для запоминания каждого пикселя требуется только 1 бит памяти компьютера. Такие изображения часто называются 1-битовыми изображениями. Соответственно, их цветовая разрешающая способность будет равна 1 бит/пиксель.

В другом типе растровых изображений, называемом оттенки серого (Grayscale), на каждый пиксель выделяется до 8 бит информации. Это позволяет оперировать с комбинацией из 256 градаций яркости, перекрывающей весь диапазон оттенков серого от черного до белого. Пример десятиступенчатой шкалы оттенков серого приведен на рис. 1.3.

Рис. 1.3. Десять градаций серого цвета - от белого (100%) до черного (0%)

Для работы с изображениями, описание которых требует большого цветового разрешения, используются цветовые модели RGB, Lab и CMYK. В случае RGB-формата цвет каждого пикселя определяется комбинацией из трех цветов: красного, зеленого и голубого. В зависимости от назначения изображение может иметь 16 битовое, 24 битовое или 32 битовое цветовое разрешение (глубину цвета).

В CMYK-формате цвет каждого пикселя формируется с помощью четырех цветовых каналов: голубого, пурпурного, желтого и черного. Из-за наличия дополнительного канала цветовая модель CMYK содержит примерно на 25 процентов больше информации по сравнению с RGB-изображением.

Изменение разрешения путем интерполяции изображения

Если разрешение цифрового изображения, полученного посредством матрицы сканера (или цифровой фотокамеры) совпадает с числом светочувствительных элементов сканера (или камеры), то говорят о фактическом (аппаратном или физическом) разрешении. Однако как в аппаратуре оцифровки изображений, так и в графических программах предусмотрена возможность использования операции интерполяции (Resampling), то есть изменения разрешения, которая может быть реализована разными способами. Например, в программе Adobe Photoshop (рис. 1.4) реализованы три способа интерполяции - по соседним, билинейная и бикубическая.

Рис. 1.4. Способы интерполяции изображений в Adobe Photoshop

При интерполяции по соседним (Nearest Neighbor) для добавляемого программой пикселя берется значение пикселя соседнего с ним. То есть, если соседний пиксель красный, то и программа увеличивает разрешение изображения добавлением красного пикселя.

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

Бикубическая (Bicubic) интерполяция усредняется значение группы не только непосредственно граничащих, но и всех соседних пикселов. Какой диапазон пикселов выбирается для усреднения и по какому алгоритму это усреднение происходит - этим отличаются способы бикубической интерполяции. На иллюстрации выше мы видим три варианта бикубической интерполяции в Adobe Photoshop.

Примечание

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

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

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

Этот человек сидит среди ромашек, чтобы привлечь ваше внимание к статье.

Для наглядного сравнения я буду использовать изображения одинакового разрешения 1920×1280 (одно , второе), которые буду приводить к размерам 330×220, 1067×667 и 4800×3200. Под иллюстрациями будет написано, сколько миллисекунд занял ресайз в то или иное разрешение. Цифры приведены лишь для понимания сложности алгоритма, поэтому конкретное железо или ПО, на котором они получены, не так важно.

Ближайший сосед (Nearest neighbor)

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

Вообще, качество и производительность любого метода уменьшения можно оценить по отношению количества пикселей, участвовавших в формировании конечного изображения, к числу пикселей в исходном изображении. Чем больше это отношение, тем скорее всего алгоритм качественнее и медленнее. Отношение, равное одному, означает что как минимум каждый пиксель исходного изображения сделал свой вклад в конечное. Но для продвинутых методов оно может быть и больше одного. Дак вот, если например мы уменьшаем изображение методом ближайшего соседа в 3 раза по каждой стороне, то это соотношение равно 1/9. Т.е. большая часть исходных пикселей никак не учитывается.

1920×1280 → 330×220 = 0,12 ms
1920×1280 → 1067×667 = 1,86 ms

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

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

Аффинные преобразования (Affine transformations)

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

Принцип действия заключается в том, что для каждой точки конечного изображения берется фиксированный набор точек исходного и интерполируется в соответствии с их взаимным положением и выбранным фильтром. Количество точек тоже зависит от фильтра. Для билинейной интерполяции берется 2x2 исходных пикселя, для бикубической 4x4. Такой метод дает гладкое изображение при увеличении, но при уменьшении результат очень похож на ближайшего соседа. Смотрите сами: теоретически, при бикубическом фильтре и уменьшении в 3 раза отношение обработанных пикселей к исходным равно 4² / 3² = 1,78. На практике результат значительно хуже т.к. в существующих реализациях окно фильтра и функция интерполяции не масштабируются в соответствии с масштабом изображения, и пиксели ближе к краю окна берутся с отрицательными коэффициентами (в соответствии с функцией), т.е. не вносят полезный вклад в конечное изображение. В результате изображение, уменьшенное с бикубическим фильтром, отличается от изображения, уменьшенного с билинейным, только тем, что оно еще более четкое. Ну а для билинейного фильтра и уменьшения в три раза отношение обработанных пикселей к исходным равно 2² / 3² = 0.44, что принципиально не отличается от ближайшего соседа. Фактически, аффинные преобразования нельзя использовать для уменьшения более чем в 2 раза. И даже при уменьшении до двух раз они дают заметные эффекты лесенки для линий.

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

1920×1280 → 330×220 = 6.13 ms
1920×1280 → 1067×667 = 17.7 ms
1920×1280 → 4800×3200 = 869 ms

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

Мое скромное мнение, что использование этого способа для произвольного уменьшения изображений попросту является багом , потому что результат получается очень плохой и похож на ближайшего соседа, а ресурсов на этот метод нужно значительно больше. Тем не менее, этот метод нашел широкое применение в программах и библиотеках. Самое удивительное, что этот способ используется во всех браузерах для метода канвы drawImage() (наглядный пример), хотя для простого отображения картинок в элементе используются более аккуратные методы (кроме IE, в нем для обоих случаев используются аффинные преобразования). Помимо этого, такой метод используется в OpenCV, текущей версии питоновской библиотеки Pillow (об этом я надеюсь написать отдельно), в Paint.NET.

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

Суперсемплинг (Supersampling)

С помощью этого метода создаются те самые mip-уровни, с помощью него (если сильно упростить) работает полноэкранное сглаживание в играх. Его суть в разбиении исходного изображения по сетке пикселей конечного и складывании всех исходных пикселей, приходящихся на каждый пиксель конечного в соответствии с площадью, попавшей под конечный пиксель. При использовании этого метода для увеличения, на каждый пиксель конечного изображения приходится ровно один пиксель исходного. Поэтому результат для увеличения равен ближайшему соседу.

Можно выделить два подвида этого метода: с округлением границ пикселей до ближайшего целого числа пикселей и без. В первом случае алгоритм становится малопригодным для масштабирования меньше чем в 3 раза, потому что на какой-нибудь один конечный пиксель может приходиться один исходный, а на соседний - четыре (2x2), что приводит к диспропорции на локальном уровне. В то же время алгоритм с округлением очевидно можно использовать в случаях, когда размер исходного изображения кратен размеру конечного, или масштаб уменьшения достаточно мал (версии разрешением 330×220 почти не отличаются). Отношение обработанных пикселей к исходным при округлении границ всегда равно единице.

1920×1280 → 330×220 = 7 ms
1920×1280 → 1067×667 = 15 ms
1920×1280 → 4800×3200 = 22,5 ms

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

1920×1280 → 330×220 = 19 ms
1920×1280 → 1067×667 = 45 ms
1920×1280 → 4800×3200 = 112 ms

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

Данный метод используется в функции gdImageCopyResampled() библиотеки GD, входящей в состав PHP, есть в OpenCV (флаг INTER_AREA), Intel IPP, AMD Framewave. Примерно по такому же принципу работает libjpeg, когда открывает изображения в уменьшенном в несколько раз виде. Последнее позволяет многим приложениям открывать изображения JPEG заранее уменьшенными в несколько раз без особых накладных расходов (на практике libjpeg открывает уменьшенные изображения даже немного быстрее полноразмерных), а затем применять другие методы для ресайза до точных размеров. Например, если нужно отресайзить JPEG разрешением 1920×1280 в разрешение 330×220, можно открыть оригинальное изображение в разрешении 480×320, а затем уменьшить его до нужных 330×220.

Свертки (Convolution)

Этот метод похож на аффинные преобразования тем, что используются фильтры, но имеет не фиксированное окно, а окно, пропорциональное масштабу. Например, если размер окна фильтра равен 6, а размер изображения уменьшается в 2,5 раза, то в формировании каждого пикселя конечного изображения принимает участие (2,5 * 6)² = 225 пикселей, что гораздо больше, чем в случае суперсемплинга (от 9 до 16). К счастью, свертки можно считать в 2 прохода, сначала в одну сторону, потом в другую, поэтому алгоритмическая сложность расчета каждого пикселя равна не 225, а всего (2,5 * 6) * 2 = 30. Вклад каждого исходного пикселя в конечный как раз определяется фильтром. Отношение обработанных пикселей к исходным целиком определяется размером окна фильтра и равно его квадрату. Т.е. для билинейного фильтра это отношение будет 4, для бикубического 16, для Ланцоша 36. Алгоритм прекрасно работает как для уменьшения, так и для увеличения.

1920×1280 → 330×220 = 76 ms
1920×1280 → 1067×667 = 160 ms
1920×1280 → 4800×3200 = 1540 ms

Скорость работы этого метода зависит от всех параметров: размеров исходного изображения, размера конечного изображения, размера окна фильтра.

Именно этот метод реализован в ImageMagick, GIMP, в текущей версии Pillow с флагом ANTIALIAS.

Одно из преимуществ этого метода в том, что фильтры могут задаваться отдельной функцией, никак не привязанной к реализации метода. При этом функция самого фильтра может быть достаточно сложной без особой потери производительности, потому что коэффициенты для всех пикселей в одном столбце и для всех пикселей в одной строке считаются только один раз. Т.е. сама функция фильтра вызывается только (m + n) * w раз, где m и n - размеры конечного изображения, а w - размер окна фильтра. И наклепать этих функций можно множество, было бы математическое обоснование. В ImageMagick, например, их 15. Вот как выглядят самые популярные:

Билинейный фильтр (bilinear или triangle в ImageMagick)


Бикубический фильтр (bicubic , catrom в ImageMagick)


Фильтр Ланцоша (Lanczos)

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

Теперь для интерполяции множеств можно использовать формулу (1). Она примет вид:

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

Пример 4. Пусть – круг радиуса с центром в точке = (0;0), – круг радиуса с центром в некоторой точке . Тогда интерполяционное множество () – это круг с центром в точке , расположенной на отрезке / /, радиуса (рис.9).

Рис.9. Интерполяция двух кругов

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

Замечание. Из свойств арифметических операций над множествами следует, что аналогичная картина получится при интерполяции двух любых кругов. Действительно, круг радиуса с центром в произвольной точке может быть представлен в виде суммы круга радиуса с центром в точке (0;0) и множества, состоящего из одной точки (равносильно вектора ): = + . Тогда интерполяционная формула даёт:

= = + .

Остаётся заметить, что семейство векторов , , является переходным от вектора к нулевому вектору.

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

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

Пример 5. Пусть – квадрат 2 x 2 с правой нижней вершиной в начале координат, – прямоугольник 4 x 5 с левой нижней вершиной в начале координат (стороны обеих фигур параллельны осям координат) (рис. 10). Построим интерполяционное множество .

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

Рис.10. Интерполяция прямоугольников на основе арифметических операций

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

Рис.11. Интерполяция прямоугольников путём интерполяции вершин

Снова обсуждаемый метод интерполяции даёт такой результат, какой мы ожидали бы увидеть.

Пример 6. Пусть – прямоугольные равнобедренные треугольники с гипотенузой h =100 и общей вершиной в начале координат. Тогда в результате интерполяции по Минковскому при получим шестиугольник (интерполяционное множество ) (рис. 12).

Рис.12. Интерполяция симметричных треугольников

Вычисления по интерполяционной формуле (2) сразу приводят к указанному итогу. В отличие от предыдущего примера, в случае данных треугольников сопоставление вершин, осуществляемое методом Минковского, как и сам результат, оказывается несколько неожиданным. Действительно, попарная интерполяция «верхних» и «нижних» вершин треугольников при даёт соответственно «верхнюю» и «нижнюю» вершины шестиугольника. А вот вершины прямых углов треугольников «интерполируются» с каждой из «верхней» и «нижней» вершин другого треугольника.

Результат примера 6, конечно, оставляет вопросы. Однако если вдуматься, то вряд ли мы сможем предложить «логичный» вариант переходного множества. Изначально предполагалось интерполировать «близкие», сходные изображения. См. также ниже замечание об особенностях интерполяции противоположных векторов.

Ещё более удивителен следующий случай.

Пример 7. Пусть – отрезки на осях координат: ,

Тогда – квадрат со стороной единица, нижние вершины которого расположены в точках (1;0) и (2;0) (рис. 13).

Рис.13. Интерполяция отрезков

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

Анализируя разобранные примеры, можно увидеть, что алгоритм Минковского даёт блестящие результаты в случаях, когда:

1) ,