Каково название этого алгоритма и как оно сравнивается с другими алгоритмами передискретизации изображений?

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

Вы начинаете с изображения. Скажем, 7x7px:

Вам нужно переделать его, скажем, до 5x5px:

Итак, все, что вы делаете, это средний цвет каждого нового квадрата:

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

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

И последнее, но не менее важное: "математически совершенный" не всегда "лучше выглядит", поэтому мне интересно, как он сравнивается с другими стандартными алгоритмами передискретизации изображений (бикубич, lanczos) с точки зрения "качества"? Это, конечно, субъективный термин, поэтому мне действительно интересно, существуют ли существенные различия между этим алгоритмом и другими, о чем большинство людей согласится.

P.S. Несколько вещей, которые я уже могу сказать об этом - это не будет "наилучшим образом" для пиксельного искусства, как показано здесь; для этого существуют специальные алгоритмы (2xSAI и т.д.); а также не будет лучше для увеличения изображений - интерполяция выиграет там. Но для сжатия фотографий...?

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

Ответ 1

Я начну, сказав, что я не знаю официального названия вашего алгоритма. Я знаю, что Paint Shop Pro назвал его "Билинейным" на ранней стадии, но был вынужден переименовать его в "Средневзвешенное" в версии 8, когда было указано, что алгоритм не соответствует классическому определению Bilinear.

Большинство алгоритмов изменения размера могут быть применены в двух независимых проходах: один в направлении X и один в Y. Это не только более эффективно, но и облегчает описание и объяснение различных алгоритмов. С этого момента я буду работать в одном измерении и предположим, что вы можете экстраполировать его на 2D.

Ваш вход состоит из 7 пикселей, которые мы дадим координатам 0, 1, 2, 3, 4, 5, 6. Полезно понять, что пиксель не является небольшим квадратом в этом контексте, а является лишь одной точкой. Для создания вывода вам понадобятся интерполированные значения из точек 0.2, 1.6, 3.0, 4.4, 5.8. Почему не 0.0, 1.5, 3.0, 4.5, 6.0? Предположим, вы удвоили размер ввода и вывода до 14x14 и 10x10: теперь координаты будут 0.0, 1.44, 2.89, 4.33, 5.78, 7.22, 8.67, 10.11, 11.56, 13.0. Начиная со второго пикселя, результаты будут разными, и это неприемлемо. Все точки должны быть 7/5 друг от друга, давая координаты 0,2, 1,6, 3,0, 4,4, 5,8, 7,2, 8,6, 10,0, 11,4, 12,8.

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

Этот первый пример в общей форме называется фильтром Box или Averaging. Но волшебная вещь случается, когда ширина фильтра коробки точно равна 1,0: один пиксель от входа будет попадать в поле и ему будет присваиваться вес 1.0, а всем остальным пикселам на входе будет задан вес 0.0, Это делает его эквивалентом алгоритма Nearest Neighbor.

Наш второй пример обычно называется фильтром палатки. Опять же, это становится чем-то особенным, когда ширина равна 2,0, она становится линейной интерполяцией; применяется в 2D, называемом Bilinear.

Третий пример - кубический фильтр, который при применении в 2D называется бикубическим. Существуют различные варианты этой формулы, в этом примере используется вариант, предложенный Митчеллом и Нетравали.

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

Наконец, мы достигнем вашего алгоритма. Его комбинация усреднения и билинейная, палатка с плоской вершиной.

Ответ 2

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

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

Алгоритм для этого метода называется Supersampling

Благодаря @Guffa для того, чтобы указать на это, это упрощение приведенного выше алгоритма, поскольку оно принимает примерные точки, и оно может пропустить определенные цвета или выбрать один цвет в несколько раз больше, чем другой, даже если он не является наиболее доминирующим.
Алгоритм выше равен бесконечной выборке точек алгоритма суперсэмплинга.

Update: Просто заметил, что даже Java ценит ваш алгоритм:)
AreaAveragingScaleFilter

Ответ 3

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

Он реализован в библиотеке Intel Performance Primitives под названием Super Sampling; (довольно неинформативное) имя - это способ заявить, что в библиотеке нет альтернативного алгоритма суперсэмплинга. В OpenCV он идет под именем INTER_AREA; он указан среди других типов интерполяции, которые могут предполагать, что они взаимозаменяемы, но отметим, что "это может быть предпочтительный метод для прореживания изображений" - довольно консервативное утверждение на мой вкус.

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

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

Если вы предполагаете, что ваша камера идеальна - нет разброса сигнала, 100% охват области приема - тогда среднее значение суперсэмплинга является оптимальным, поскольку оно дает точное изображение, которое было бы получено идеальной камерой с половиной разрешения.

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

Ответ 4

Ваше описание не напоминает мне алгоритм, скорее всего, это структура данных и тип данных. Это напоминает мне kd-tree или quadtree. Kd-tree или quadtree могут помочь вам решить вашу проблему с ближайшим соседом. Однако, если вы хотите получить математическую функцию для сеток, вы также можете взглянуть на кривые заполнения пространства, особенно кривые z morton morton. Это отлично работает для мощности 2 и снижает сложность 2d. Функция f (x, y) = (f (x), f (y)).

Ответ 5

Он также не билинейный

Да, на самом деле. Билинейная передискретизация - это просто линейная интерполяция в двух измерениях.

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

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