Русская Википедия:Алгоритмы масштабирования пиксельной графики
Алгори́тмы масштаби́рования пи́ксельной гра́фики — алгоритмы масштабирования цифровых изображений, созданные специально для увеличения качества графики низкого разрешения. В отличие от традиционных алгоритмов масштабирования, дают менее размытую картинку.
Причины появления
Существуют два стандартных алгоритма масштабирования изображений, билинейная и бикубическая интерполяция. Поскольку цветовые координаты текущего пикселя обычно вычисляются путём интерполяции четырёх соседних, обработанное изображение получается размытым. Хотя это приемлемо для полноцветных изображений, применение интерполяции ведет к снижению контрастности (резкости на границах), и, поэтому, данный метод дает плохие результаты на изображениях с индексированной палитрой.
Метод ближайшего соседа сохраняет резкие границы, но привносит в изображение ступенчатость (в частности, диагональные линии напоминают «лесенку» из квадратов). Таким образом, идеальный алгоритм для увеличения пиксельной графики должен интерполировать области непрерывного тона, сохранять чёткость для горизонтальных и вертикальных линий и сглаживать (с применением антиалиасинга) диагональные линии и кривые. Было предпринято несколько попыток решения этой задачи.
Эффективность
Поскольку основная область применения данных алгоритмов — это эмуляторы старых консольных и DOS’овских игр, многие из них рассчитаны на вывод динамически изменяющегося изображения в реальном времени (при достаточно малом разрешении картинки на входе).
Многие алгоритмы работают только при увеличении в целое число раз: 2x, 3x и 4x.
Алгоритмы
EPX/Scale2x/AdvMAME2x
EPX («Eric’s Pixel eXpansion», пиксельное увеличение Эрика) — алгоритм, разработанный Эриком Джонстоном из LucasArts приблизительно в 1992 году[1], при портировании движка SCUMM с IBM PC (разрешение 320×200, 256 цветов) на первые цветные компьютеры Macintosh, где разрешение было выше примерно вдвое[2].
Алгоритм работает следующим образом:
A --\ 1 2 C P B --/ 3 4 D Если C==A => 1=A Если A==B => 2=B Если B==D => 4=D Если D==C => 3=C Если 3 или более пикселов из A, B, C, D одинаковы: 1=P, 2=P, 3=P, 4=P
Последовавшие реализации этого алгоритма (такие как AdvMAME2x и Scale2x, разработанные приблизительно в 2001 году) имеют иную (более эффективную), но функционально идентичную, реализацию:
A --\ 1 2 C P B --/ 3 4 D 1=P; 2=P; 3=P; 4=P; Если C==A и C!=D и A!=B => 1=A Если A==B и A!=C и B!=D => 2=B Если B==D и B!=A и D!=C => 4=D Если D==C и D!=B и C!=A => 3=C
AdvMAME4x/Scale4x — это просто дважды примененный EPX.
Scale3x/AdvMAME3x
Алгоритм AdvMAME3x/Scale3x — не то же самое, что EPX, но они достаточно схожи между собой:
A B C --\ 1 2 3 D E F > 4 5 6 G H I --/ 7 8 9 1=E; 2=E; 3=E; 4=E; 5=E; 6=E; 7=E; 8=E; 9=E; Если D==B и D!=H и B!=F => 1=D Если (D==B и D!=H и B!=F и E!=C) или (B==F и B!=D и F!=H и E!=A) => 2=B Если B==F и B!=D и F!=H => 3=F Если (H==D и H!=F и D!=B и E!=A) или (D==B и D!=H и B!=F и E!=G) => 4=D 5=E Если (B==F и B!=D и F!=H и E!=I) или (F==H и F!=B и H!=D и E!=C) => 6=F Если H==D и H!=F и D!=B => 7=D Если (F==H и F!=B и H!=D и E!=G) или (H==D и H!=F и D!=B и E!=I) => 8=H Если F==H и F!=B и H!=D => 9=F
Eagle
Сначала: |Затем:
. . . --\ CC |S T U --\ 1 2
. C . --/ CC |V C W --/ 3 4
. . . |X Y Z
| Если V==S==T => 1=S
| Если T==U==W => 2=U
| Если V==X==Y => 3=X
| Если W==Z==Y => 4=Z
Таким образом, одиночный чёрный пиксел на белом фоне при применении данного алгоритма растворится. Эта ошибка исправлена в алгоритмах 2xSaI и HQ3x.
2xSaI
2xSaI, (2x Scale and Interpolation, двукратное увеличение и интерполяция), является усовершенствованием алгоритма Eagle. Был разработан Дереком Лиау Кие Фа (Derek Liauw Kie Fa), также известным как Kreed, первоначально для использования в эмуляторах, где и поныне является достаточно популярным алгоритмом. Многие популярные эмуляторы, такие как ZSNES, Jnes, DOSBox и VisualBoyAdvance, имеют поддержку данного алгоритма вывода.
Kreed опубликовал исходные коды алгоритма [1] под лицензией GPL, т. е. его можно свободно использовать в любых целях, оговорённых лицензией. Для использования алгоритма в не-GPL продуктах, разработчику придется переписать его без использования кода, написанного Kreed.
Super 2xSaI и Super Eagle
Немного модифицированные реализации имеют названия «Super 2xSaI», «2xSaI», и «Super Eagle».
Super Eagle написан Kreed’ом, аналогичен 2XSaI, но на выходе получается более сильное смешение цветов пикселей (блендинг).
Super 2xSaI написан Kreed’ом, фильтр для сглаживания графики, но с более сильным блендингом, чем в Super Eagle.
Семейство hqnx
Максим Степин разработал алгоритмы hq2x, hq3x и hq4x для увеличения в пропорциях 2:1, 3:1 и 4:1 соответственно. Цвет каждого пиксела сравнивается с восемью соседними, соседи помечаются как ближние и дальние, далее используется прегенерированная таблица для отыскания необходимого соотношения значений для каждого из 4, 9 или 16 выходных пикселей. Алгоритм hq3x отлично сглаживает диагональные линии с наклоном ±1:2, ±1:1 и ±2:1 (при условии отсутствия антиалиасинга на входе алгоритма); линии с другим коэффициентом наклона будут представлены как ломаные из вышеупомянутых диагональных. Хорошо сглаживаются крутые кривые. В отличие от 2xSaI, к выводу применяется антиалиасинг[3].
hqnx был изначально придуман для эмулятора Super Nintendo, ZSNES. Автор bsnes опубликовал в открытом доступе компактную реализацию hq2x. Доступен порт на шейдерах, качество которого сравнимо с ранними версиями xBR. До появления порта, шейдер под названием "scalehq" часто путали с hqx.
Семейство xBR
В этом семействе есть 6 фильтров: xBR, xBRZ, xBR-Hybrid, Super xBR, xBR+3D и Super xBR+3D.
xBR ("масштабирование по правилам"), созданный Hyllian, работает почти так же, как HQx (основанный на распознавании образов), и будет генерировать тот же результат, что и HQx, при задании вышеупомянутого шаблона. Однако он пошел дальше, чем HQx, используя двухэтапный набор правил интерполяции, которые лучше обрабатывают более сложные шаблоны, такие как сглаженные линии и кривые. Масштабированные фоновые текстуры сохраняют четкие характеристики исходного изображения, а не становятся размытыми, как это имеет тенденцию делать HQx (часто ScaleHQ на практике). Новейшие версии xBR являются многопроходными и позволяют лучше сохранять мелкие детали. Существует также версия xBR в сочетании с шейдером Reverse-AA, называемая xBR-Hybrid. xBR+3D - это версия с 3D-маской, которая фильтрует только 2D-элементы.
xBRZ от Zenju - это модифицированная версия xBR. Он реализован с нуля как фильтр на основе процессора в C++. В нем используется та же основная идея, что и в xBR для распознавания образов и интерполяции, но с другим набором правил, предназначенных для сохранения мелких деталей изображения размером всего в несколько пикселей. Это делает его полезным для масштабирования деталей лиц и, в частности, глаз. xBRZ оптимизирован для многоядерных процессоров и 64-разрядных архитектур и показывает производительность на 40-60% выше, чем HQx, даже при работе только на одном ядре процессора. Он поддерживает масштабирование изображений с помощью альфа-канала и масштабирование целочисленными коэффициентами от 2× до 6×.
Super xBR - это алгоритм, разработанный компанией Hylian в 2015 году. Он использует некоторые комбинации известных линейных фильтров наряду с правилами обнаружения границ xBR нелинейным способом. Он работает в два прохода и может масштабировать изображение только в два раза (или кратно двум при повторном нанесении, а также имеет противозвонный фильтр). Super xBR+3D - это версия с 3D-маской, которая фильтрует только 2D-элементы. Существует также версия Super xBR, переписанная на C/C++.
Алгоритм Копфа-Лищински
Алгоритм разработан в 2011 году и представлен на SIGGRAPH 2011 в документе "Depixelizing Pixel Art"[4]. Переводит пиксельное изображение с небольшим количеством цветов в векторную форму. Впрочем, если на картинке есть антиалиасинг, результаты получаются хуже. Доступна реализация на языке python.
Алгоритм был перенесен на графические процессоры и оптимизирован для рендеринга в реальном времени. Доступен исходный код для этого варианта.[5]
Применение в эмуляторах игровых приставок
На достаточно быстрых компьютерах данные алгоритмы позволяют реализовать вывод масштабированного изображения, по скорости приемлемый для приложений реального времени, в частности, компьютерных игр. Высокооптимизированные алгоритмы дают четкую и резкую картинку с минимальным размытием. Алгоритмы масштабирования пиксельной графики были реализованы для множества эмуляторов, 2D-игровых движков и движков для игр-переделок, например, для AdvanceMAME, DOSBox, и ScummVM. Они получили высокую оценку среди геймеров, которые стали переделывать игры, написанные в 80-х и 90-х. В настоящее время (2013 г.) такие фильтры используются в коммерческих эмуляторах Xbox Live, Virtual Console, и PSN для того, чтобы классические игры низкого разрешения лучше выглядели на дисплеях высокого разрешения. К таким играм относятся Sonic's Ultimate Genesis Collection, Castlevania: The Dracula X Chronicles, Castlevania: Symphony of the Night, и Akumajō Dracula X Chi no Rondo'.
Примечания
Ссылки
- Усовершенствованная версия 2xSaI с поддержкой 32-битного цвета
- Домашняя страница Scale2x
- Проект hq3x (Доступны утилиты для Windows)
- Проект hqx на Google Code
