Псевдотонирование изображений: одиннадцать алгоритмов и исходники

Автор оригинала: Таннер Хелланд
  • Перевод

Псевдотонирование: обзор



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

На самом деле псевдотонирование по-прежнему остаётся уникальным методом не только по практическим соображениям (например, подготовка полноцветного изображения для печати на чёрно-белом принтере), но и по художественным. Дизеринг также находит применение в веб-дизайне, где этот полезный метод используется для сокращения числа цветов изображения, что уменьшает размер файла (и трафик) без ущерба для качества. Он также используется при уменьшении цифровых фотографий в формате RAW в 48 или 64 бита на пиксель до RGB в 24 бита на пиксель для редактирования.

И это — применения лишь в области изображений. В звуке дизеринг тоже играет ключевую роль, но боюсь, обсуждать здесь дизеринг аудио я не буду. Только псевдотонирование изображений.

В этой статье я собираюсь сосредоточиться на трех пунктах:

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

Псевдотонирование: примеры


Рассмотрим следующее полноцветное изображение, обои со знаменитым Кубом-Компаньоном из игры Portal:


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

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


Это то же изображение, что и выше, но ограниченное веб-палитрой безопасных цветов.

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


Здесь изображение едва узнаваемо.

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

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


Значительно лучше, чем в версии без псевдотонирования!

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

В качестве другого примера: здесь чёрно-белая версия нашего изображения с похожим псевдотонированием:


Если говорить конкретно, то здесь применено псевдотонирование по двухрядном алгоритму Сьерры (2-row Sierra).

Несмотря на наличие только чёрного и белого цветов, мы всё ещё можем различить форму куба вплоть до сердец с обеих сторон. Дизеринг — чрезвычайно мощный метод, и его можно использовать в ЛЮБОЙ ситуации, когда данные должны быть представлены в более низком разрешении, чем то, для которого их создавали. В этой статье основное внимание будет уделено изображениям, но те же методы могут быть применены к любым двухмерным данным (или к одномерным данным, что еще проще!).

Основная концепция псевдотонирования


Если коротко, псевдотонирование в корне связано с рассеиванием ошибок.

Рассеивание ошибок работает следующим образом: предположим, что нам нужно свести фотографию в градациях серого до чёрных и белых цветов, чтобы мы могли напечатать её на принтере, который поддерживает только чистый черный (чернила) или чистый белый (бумага без чернил) цвет. Первый пиксель на изображении — тёмно-серый, со значением 96 по шкале от 0 до 255, где 0 — чистый чёрный цвет, 255 — чистый белый.


Визуализация значений RGB в нашем примере.

При преобразовании такого пикселя в черный или белый мы используем простую формулу: значение цвета ближе к 0 (черному) или 255 (белому)? 96 ближе к 0, чем к 255, поэтому мы делаем пиксель черным.

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

Рассеивание ошибок следует более умному подходу к проблеме. Как вы могли предположить, рассеивание ошибок работает путем «рассеивания» — или распространения — ошибки каждого вычисления в соседние пиксели. Если алгоритм находит серый пиксель со значением 96, он также определяет, что 96 ближе к 0, чем к 255 — и поэтому делает пиксель черным. Но тогда алгоритм учитывает «ошибку» в его преобразовании. В частности, ошибку в том, что серый пиксель, который мы заставили быть черным, на самом деле был на расстоянии в 96 шагов от черного.

Когда он перемещается к следующему пикселю, алгоритм рассеивания ошибок добавляет ошибку предыдущего пикселя к текущему пикселю. Если следующий пиксель также имеет серый цвет 96, вместо того, чтобы сделать его черным, алгоритм добавляет ошибку 96 из предыдущего пикселя. Это приводит к значению 192, которое на самом деле ближе к 255 — и, следовательно, ближе к белому! Таким образом, алгоритм делает этот пиксель белым и снова учитывает ошибку. В этом случае ошибка составляет −63, потому что 192 на 63 меньше, чем 255 — то значение, на которое этот пиксель поменяли.

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

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


Это самое простое применение псевдотонирования с рассеиванием ошибок.

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

В приведенном выше простом примере алгоритма рассеивания ошибок очевидна другая проблема — если у вас есть блок очень похожих цветов, и вы толкаете ошибку только вправо, все «точки» оказываются в одном и том же месте! Это приводит к забавным линиям точек, которые почти так же отвлекают, как и оригинальная версия без псевдотонирования.

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

Псевдотонирование с двухмерным рассеиванием ошибок


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

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

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


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

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

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

Алгоритм рассеивания ошибок Флойда-Стейнберга


Первая и возможно самая известная формула рассеивания ошибок была опубликована Робертом Флойдом и Луисом Стейнбергом в 1976 году. Рассеивание ошибок происходит по следующей схеме:

       X   7
   3   5   1

     (1/16)

В приведенных выше обозначениях X означает текущий пиксель. Дробь в нижней части представляет собой делитель для ошибки. Иначе говоря, формула Флойда-Стейнберга может быть записана в виде:

           X    7/16
   3/16  5/16   1/16

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

Вернёмся к нашему оригинальному примеру преобразования пиксельного значения от 96 к 0 (чёрный) или к 255 (белый). При окрашивании пикселя в чёрный мы получаем ошибку 96. Мы распространяем эту ошибку окружающим пикселям, поделив 96 на 16 ( = 6), затем умножаем её на соответствующие значения, например:

           X     +42
   +18    +30    +6

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


Алгоритм рассеивания ошибок Флойда-Стейнберга

Неплохо, а?

Алгоритм рассеивания ошибок Флойда-Стейнберга — вероятно, наиболее известный алгоритм рассеивания ошибок. Он даёт достаточно хорошее качество, а также требует только один передний массив (одномерный массив шириной в изображение, где хранятся значения ошибок, распространяемые к следующей строке). Кроме того, поскольку его делитель 16, вместо деления можно использовать битовые сдвиги. Так алгоритм достигает высокой скорости работы даже на старом оборудовании.

Что касается значений 1/3/5/7, используемых для распространения ошибки – они были выбраны специально, потому что они создают равномерный клетчатый узор для серого изображения. Умно!

Одно предупреждение по поводу алгоритма Флойда-Стейнберга — некоторые программы могут использовать и другие, более простые формулы псевдотонирования и называть их «Флойд-Стейнберг», надеясь, что люди не знают разницы. Вот отличная статья о дизеринге, которая описывает один из таких «ложных алгоритмов Флойда-Стейнберга»:

   X   3
   3   2

   (1/8)

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

Но если вам интересно, вот изображение куба после прохода «ложного Флойда-Стейнберга»:


Гораздо больше скоплений точек, чем в настоящем алгоритме Флойда-Стейнберга — так что не используйте эту формулу!

Алгоритм Джарвиса, Джудиса и Нинке (Jarvis, Judice, Ninke)


В год, когда Флойд и Стейнберг опубликовали свой знаменитый алгоритм дизеринга, был издан менее известный, но гораздо более мощный алгоритм. Фильтр Джарвиса, Джудиса и Нинке значительно сложнее, чем Флойда-Стейнберга:

             X   7   5 
     3   5   7   5   3
     1   3   5   3   1

           (1/48)

При таком алгоритме ошибка распределяется на в три раза больше пикселей, чем у Флойда-Стейнберга, что приводит к более гладкому и более тонкому результату. К сожалению, делитель 48 не является степенью двойки, поэтому битовые сдвиги применить не удастся. Используются только значения 1/48, 3/48, 5/48, и 7/48, так что эти значения могут быть вычислены единожды, а затем размножены несколько раз для небольшого увеличения по скорости.

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


Псевдотонирование Джарвиса, Джудиса и Нинке

Дизеринг Штуки (Stucki)


Через пять лет после публикации формулы дизеринга Джарвиса, Джудиса и Нинке Питер Штуки опубликовал скорректированную версию с небольшими изменениями для улучшения времени обработки:

             X   8   4 
     2   4   8   4   2
     1   2   4   2   1

           (1/42)

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

Для большинства изображений разница между алгоритмами Штуки и JJN будет минимальна. Поэтому первый чаще используется из-за его небольшого преимущества в скорости.


Псевдотонирование Штуки

Дизеринг Аткинсона


В середине 1980-х годов псевдотонирование становится все более популярным, поскольку аппаратное обеспечение компьютеров доросло до поддержки более мощных драйверов видеоадаптера и дисплея. Один из лучших алгоритмов дизеринга той эпохи разработал Билл Аткинсон, сотрудник компании Apple, который работал над всем: от MacPaint (который он писал с нуля для оригинального Macintosh) до HyperCard и QuickDraw.

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

         X   1   1 
     1   1   1
         1

       (1/8)


Псевдотонирование Аткинсона

Псевдотонирование Бёркеса (Burkes)


Через семь лет после того, как Штуки опубликовал улучшения алгоритма Джарвиса, Джудиса и Нинке, Дэниэл Бёркес предложил дальнейшее развитие:

             X   8   4 
     2   4   8   4   2

           (1/32)

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


Псевдотонирование Бёркеса

Псевдотонирование Сьерры (Sierra)


Последние три алгоритма дизеринга были созданы Фрэнком Сьеррой, который опубликовал следующие матрицы в 1989 и 1990 годах:

             X   5   3
     2   4   5   4   2
         2   3   2
           (1/32)

             X   4   3
     1   2   3   2   1
           (1/16)

         X   2
     1   1
       (1/4)

Эти три фильтра обычно называются Sierra, Two-Row Sierra (двухрядный алгоритм Сьерры) и Sierra Lite. Их конечное изображение на тестовой картинке куба выглядит следующим образом:


Sierra (иногда называют Sierra-3)


Two-row Sierra (двухрядный алгоритм Сьерры)


Sierra Lite

Остальные соображения по псевдотонированию


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

  • Отслеживание ошибок числами с плавающей запятой или целыми числами. Целочисленные методы теряют некоторое разрешение из-за ошибок квантования.
  • Уменьшение обесцвечивания. Некоторое программное обеспечение уменьшает погрешность по заданному значению (возможно, 50% или 75%), чтобы уменьшить объём обесцвечивания соседних пикселей.
  • Порог отсечения для чёрного или белого. Значения 127 или 128 являются общепринятыми, но на некоторых изображениях может быть полезно использовать другие значения.
  • Для цветных изображений играет важную роль то, как рассчитывается яркость. Я использую формулу яркости HSL ( [max(R,G,B) + min(R,G,B)] / 2). Другие используют ([r+g+b] / 3) или одну из формул ITU. YUV или CIELAB позволят достичь результатов ещё лучше.
  • Гамма-коррекция или другие предварительные модификации. Часто полезно нормализовать изображение перед его преобразованием в чёрно-белое. Выбор метода для этого очевидным образом повлияет на результат.
  • Направление цикла. Я обсуждал стандартный подход «слева направо, сверху вниз», но некоторые умные алгоритмы дизеринга будут следовать змееподобному пути, где направленность слева направо меняется на противоположную. Так можно уменьшить пятна однородных точек и дать более разнообразный внешний вид, но их сложнее реализовать.

Для демонстрационных изображений в этой статье я не выполнял предварительную обработку исходного изображения. Все цветовые соответствия выполняются в пространстве RGB с отсечкой 127 (значения <= 127 установлены на 0). Направление цикла — стандартные слева направо сверху вниз.

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

Я насчитал 9 алгоритмов, но вы обещали 11! Где еще два?


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

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


Псевдотонирование с упорядоченным размытием с матрицей 4×4


Псевдотонирование с упорядоченным размытием с матрицей 8×8

С учетом этих методов статья описывает 11 различных алгоритмов псевдотонирования.

Написание собственного алгоритма псевдотонирования общего назначения


Ранее в этом году я написал полностью функциональный генератор псевдотонирования общего назначения для PhotoDemon (фоторедактор с открытым исходным кодом). Вместо того чтобы размещать здесь весь код, позвольте мне направить вас на соответствующую страницу на GitHub. Движок преобразования черно-белых изображений начинается на строке 350. Если у вас есть вопросы по коду, который охватывает алгоритмы, описанные на этой странице, пожалуйста, сообщите мне, и я опубликую дополнительные пояснения.

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

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

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

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

    +3
    Почему я пишу статью о псевдотонировании в эпоху, когда дешевые мобильные телефоны работают с великолепием 32-битной графики?

    Можно подумать что 24 бита + альфа на пиксель достаточно, но это не так.


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

    image


    В зависимости от вашего монитора и натренированности, разница в цвете будет между едва заметным до вырвиглазного.


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


    Так что дитеринг никуда не ушел и останется с нами пока мы не перейдем на 2 байта на канал.

      +6
      Ух ты, как все просто, оказывается… Я всегда думал, что для этого какие-то зубодробительные алгоритмы используются, а на самом деле весь алгоритм заключается в проходе матрицей, где от выбора матрицы зависит качество и скорость обработки. Красота!
        +1
        Спасибо за перевод! Есть несколько замечаний по терминам и по смыслу. Помимо «псевдотонирования» используют термин «псевдосмешение (цветов)». Мне он представляется более адекватным, так как ощущение бОльшего количества цветов (или оттенков серого) создается за счет группировки определённых цветов в локальной окрестности, как, например в пуантилизме.
        В ordered dithering нет никакого размытия. Там просто сравниваются значения из изображения со значениями из матрицы. Поэтому перевод «с упорядоченным размытием» может запутать. Исторически ordered dithering возник из random dithering, в котором к изображению добавлялся случайный шум, а потом делалось квантование (в простейшем случае бинаризация). Этот шум на русский язык переводили как «возбуждение»: random dithering == псевдосмешение со случайным возбуждением. Соответственно, order dithering == псевдосмешение с матрицей возбуждения или с упорядоченным возбуждением. Хотя, конечно, на русском языке этой теме посвящено мало книг и статей, так что с терминологией не всё однозначно.
        На самом деле псевдотонирование по-прежнему остаётся уникальным методом не только по практическим соображениям (например, подготовка полноцветного изображения для печати на чёрно-белом принтере)
        Для печати используют «halftoning» — полутонирование, а не псевдотонирование. Это другие алгоритмы.

        Следует отметить, что у всех перечисленных в статье алгоритмов есть существенная особенность, которая ограничивает их область применения. При масштабировании (особенно в не кратное двум раз) изображений, обработанных dithering, возникают визуальные артефакты (например, муар может возникать). Для интереса, я советую вырезать любое (кроме исходного) изображение из примеров в статье и посмотреть его, например при масштабе в 70%.
          +1
          Спасибо, добавил упоминания «псевдосмешения» в начальные абзацы.
          В ordered dithering нет никакого размытия.
          Хотя, конечно, на русском языке этой теме посвящено мало книг и статей, так что с терминологией не всё однозначно.
          Да, какой-то упорядоченности нет. Я заимствовал термин из курса лекций ИНТУИТа.
          +8
          Сразу вспомнилась инсталляция Windows 95.
          Windows 95
          image
            +2
            Вообще есть ещё как минимум 2 метода:
            1. Банальный рандом пропорционально яркости. Используется порой для смешивания в шейдерах, когда исходное изображение ступенчатое, и надо немного размыть. Попадалось в описании движка одной игры. По качеству сильно хуже, но вполне работает.
            2. Рекурсивная мозайка (Recursive Wang Tiles for Real-Time Blue Noise). Описание с исходниками есть тут. Рилтайм и очень качественно.
              0
              Вопрос дилетанта: какой формат лучше (без потерь, минимальный объем) для сохранения подобных изображений?
                +3

                Недавно писал клиент Инстаграма для умных часов pebble time, где всего 64 цвета. Самым лучшим оказался png.
                Думал что не получится ничего разглядеть с низким разрешением и такой палитрой, но нет, используя обычный дезеринг из питоновской pillow, получается вполне сносно.

                0
                Недавно как раз разбирался с квантизацией изображений, оригинал статьи очень пригодился. Кому интересна реализация на python, можете глянуть мой проект на github.
                  0

                  Пробежался по коду:
                  А зачем пиксели в базе данных хранить? Если в скорости затык, то можно же image.load() использовать, при этом обращаться к ним непосредственно как к массиву в памяти.

                    0
                    Во первых: палитра создаётся SQL-запросами (так быстрее, проще и интересней).
                    Во вторых: цвета пикселей хранятся в числах с плавающей запятой, для более точного вычисления палитры, более точного поиска ближайшего цвета, более точного псевдотонирования (в нём используются дроби); матрица float на 12 мегапикселей сжирает много оперативки, база данных с таким объёмом работает шустро и оперативки съедает чуток.
                    По скорости затык в вычислении палитры и поиске ближайшего цвета в палитре. Смотрел по статистике cProfile, обращение к пикселям в базе на фоне этих двух операций просто мгновенное.
                      0

                      Спасибо! Просто интересно было, чем мотивировано такое решение, которое кажется весьма странным )
                      А numpy не пробовали для этих целей? Вроде лучше должен подходить.

                  +4
                  Спасибо большое за теплую ламповую статью. Прям ностальгия напала. Можно добавить, что для того, чтобы результат был вообще потрясающим, раньше всегда добавляли возможность подбора оптимальной палитры из заданного количества цветов. Обычно это делалось на основе цветового куба RGB 255x255x255, который итеративно делился на параллелепипеды с весами, пока их количество не становилось равным количеству заданных цветов. Потом по каждому параллелепипеду считался доминантный цвет и заносился в палитру. Помню утилита под DOS ACDSee умела такое делать.
                    0
                    Это называется квантизация изображений, я о ней недавно писал краткую статью на хабре. Вы описали метод медианного сечения, есть ещё октодерево и метод k-средних.
                      0
                      Да, спасибо, вспомнил. Я просто реализовывал все это в коде, при обработке изображений и видео, когда делал соответствующие редакторы. Просто давно это было, лет 15 назад, и уже все подзабылось.
                    +1

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

                      0
                      Супер спасибо. С интересом прочитал.
                      каждый третий оказывался запатентованным. Например, метод void-and-cluster для генерации матрицы упорядоченного дизеренга.

                      А на сколько тривиальны запатентованные алгоритмы?
                        0

                        Отличная статья, всегда было интересно как работает gameboy camera.


                        Приложу несколько своих фоток:


                        Скрытый текст


                        ps: эти фотки не с gameboy camera, но тоже в тему :)
                          0
                          Вспомнились чтот рубежи 90ых, когда я ansi/ascii артом занимался!
                            0
                            Про предшественников метода распространения ошибки: thresholding и ordered dither можно посмотреть кусок лекции от Computer Science Club. По той же ссылке можно скачать и презентацию с лекции
                              0
                              Интересно, можно ли сделать (полу)автоматический подбор этой матрицы? Но с функцией качества будет засада — она должна одновременно смотреть на локальные кучки пикселей и не просаживать контрастность

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

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