Комментарии 23
Почему я пишу статью о псевдотонировании в эпоху, когда дешевые мобильные телефоны работают с великолепием 32-битной графики?
Можно подумать что 24 бита + альфа на пиксель достаточно, но это не так.
В зависимости от вашего монитора и натренированности, разница в цвете будет между едва заметным до вырвиглазного.
С разными тонами, ситуация разная. Синий мы различаем хуже чем зеленый, например. К тому же не редко соседний тон должен сменить два значения, скажем синий и зеленый, что делает ситуацию еще хужее. Наш глаз различает больше цветов чем 256^3.
Так что дитеринг никуда не ушел и останется с нами пока мы не перейдем на 2 байта на канал.
В ordered dithering нет никакого размытия. Там просто сравниваются значения из изображения со значениями из матрицы. Поэтому перевод «с упорядоченным размытием» может запутать. Исторически ordered dithering возник из random dithering, в котором к изображению добавлялся случайный шум, а потом делалось квантование (в простейшем случае бинаризация). Этот шум на русский язык переводили как «возбуждение»: random dithering == псевдосмешение со случайным возбуждением. Соответственно, order dithering == псевдосмешение с матрицей возбуждения или с упорядоченным возбуждением. Хотя, конечно, на русском языке этой теме посвящено мало книг и статей, так что с терминологией не всё однозначно.
На самом деле псевдотонирование по-прежнему остаётся уникальным методом не только по практическим соображениям (например, подготовка полноцветного изображения для печати на чёрно-белом принтере)Для печати используют «halftoning» — полутонирование, а не псевдотонирование. Это другие алгоритмы.
Следует отметить, что у всех перечисленных в статье алгоритмов есть существенная особенность, которая ограничивает их область применения. При масштабировании (особенно в не кратное двум раз) изображений, обработанных dithering, возникают визуальные артефакты (например, муар может возникать). Для интереса, я советую вырезать любое (кроме исходного) изображение из примеров в статье и посмотреть его, например при масштабе в 70%.
В ordered dithering нет никакого размытия.
Хотя, конечно, на русском языке этой теме посвящено мало книг и статей, так что с терминологией не всё однозначно.Да, какой-то упорядоченности нет. Я заимствовал термин из курса лекций ИНТУИТа.
1. Банальный рандом пропорционально яркости. Используется порой для смешивания в шейдерах, когда исходное изображение ступенчатое, и надо немного размыть. Попадалось в описании движка одной игры. По качеству сильно хуже, но вполне работает.
2. Рекурсивная мозайка (Recursive Wang Tiles for Real-Time Blue Noise). Описание с исходниками есть тут. Рилтайм и очень качественно.
Пробежался по коду:
А зачем пиксели в базе данных хранить? Если в скорости затык, то можно же image.load() использовать, при этом обращаться к ним непосредственно как к массиву в памяти.
Во вторых: цвета пикселей хранятся в числах с плавающей запятой, для более точного вычисления палитры, более точного поиска ближайшего цвета, более точного псевдотонирования (в нём используются дроби); матрица float на 12 мегапикселей сжирает много оперативки, база данных с таким объёмом работает шустро и оперативки съедает чуток.
По скорости затык в вычислении палитры и поиске ближайшего цвета в палитре. Смотрел по статистике cProfile, обращение к пикселям в базе на фоне этих двух операций просто мгновенное.
Вспоминается, когда я недавно смотрел алгоритмы псевдосмешения, каждый третий оказывался запатентованным. Например, метод void-and-cluster для генерации матрицы упорядоченного дизеренга. Да и вообще в таких вещах, как изображения, видео и аудио так много патентов на алгоритмы обработки, что приходится быть крайне осторожным.
каждый третий оказывался запатентованным. Например, метод void-and-cluster для генерации матрицы упорядоченного дизеренга.
А на сколько тривиальны запатентованные алгоритмы?
Отличная статья, всегда было интересно как работает gameboy camera.
Приложу несколько своих фоток:
ps: эти фотки не с gameboy camera, но тоже в тему :)
Подумал что надо бы отписаться если не на статью, то хоть сюда.
- Можно получить очень хороший результат, даже с ядром распространение всего на 2 клети и ровно пополам, если использовать ротацию ядер на каждой следующей линии.
1. половину всегда распространяем на соседа справа (грядущего к обработке)
2. вторую половину кладем в буфер по своему X индексу
3. забираем ошибку из верхнего/ верхнего-левого / или верхнего правого соседа, в зависимости от своего X индекса
задача что бы вектора ложились регулярно но сильно перемешиваясь:
- на самом деле если вы просчитаете влияние распространяемых на клетки ошибки в таком формате, оно будет разноситься дальше чем на клетку, угасая вдвое на каждом шаге, что дает довольно похожее на большие ядро где в центре веса больше.
Перемешивание векторов распределения значительно дешевле (по сути его можно вообще размотать и захардкодить для разных линий) так что оно не накладывает доп расходов. И не смотря на то, что такое распределение математически менее точно нежели большое ядро, гораздо важнее, что здесь достаточное перемешивание ошибки что бы избегать явных паттернов. С чем проблема всех перечисленных однострочных алгоритмов.
Помимо быстродействия о требуемой памяти. Однострочными я называю те, для которых ядро не опускается ниже одной строки, а следовательно в поточном алгоритме для хранения отложенных данных ошибки не требуется "окно" размером значительно большим одной строки изображения. И этот такой.
тесты гонял там https://codepen.io/impfromliga/pen/zYoVXZg?editors=0010
цикл перемешивания векторов возможен различный, на в 3 или в 2 позиции:
можно подобрать оптимальный учтя какой усредненный градиент весов получается с учетом того что на каждой линии половина ошибки размазывается и вправо
вспомнил тут вашу статью и то что озвученная выше идея псевдо-хаотического разброса давно реализована: https://codepen.io/impfromliga/pen/zYoVXZg
- математика целочисленная, кондишнов нет (позаимствовано у Брезенхема, из реализации когда переполняющийся 9й бит математически сам едет куда надо)
- на масках и сдвигах деление только на 2
- с отбросом из каналов последнего бита, реализовано вычисление всех каналов через uint32 типизированный массив единовременно
(получилось очень шустро и удается даже видео поток на JS дизерить, даже на мобиле)
ЧБ выглядит тоже достойно. (для алгоритма с одной линией по отсутствию паттернов лучше аналогов, при том что он быстрее даже самого быстрого из них "сиерры лайт" - на самом деле с него стартовала идея этого алгоритма)
- в обоих скринах бралась гамма коррекция, сделанная через pow(x/255,1.5)*255
- функция усреднения цвета = среднее арифметическое
Но субъективно вижу чуть большее растекание
- что логично, т.к. ошибка бросается пополам всего в 2 пиксела, и псевдо-хаотически может пройти больший путь пока ее влияние иссякнет (аналог некоторой составляющей блюр ядра)
Одноканальное ядро в базовом виде:
var errs= Array(w).fill(0);
for(var y=0; y<h; y++){
for(var e=0, x=0; x<w; x++){
var i= x+y*w;
var q=i<<2;
var cur= buf8[q] + e + errs[(i+(x%3)-1)%w];
errs[(i-1)%w]=e;
buf8[q]= buf8[q+1]= buf8[q+2]= (cur>255)*255;
cur&=255;
e=cur>>1;
}
y++;
for(var e=0, x=w; x--;){
var i= x+y*w;
var q=i<<2;
var cur= buf8[q] + e + errs[(i+((x+y)%3)-1)%w];
errs[(i+1)%w]=e;
buf8[q]= buf8[q+1]= buf8[q+2]= (cur>255)*255;
cur&=255;
e=cur>>1;
}
}
Псевдотонирование изображений: одиннадцать алгоритмов и исходники