Дизеринг по шаблону

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

1. Дизеринг по шаблону
2. Дизеринг на основе распределения коррекции цвета на соседние клетки изображения

Сегодня мы рассмотрим первый.

В качестве исходного изображения возьмем градиент из черного в белый размером 16x16 клеточек:

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

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

Давайте попробуем нашу картинку превратить в черно-белую с порогом 120:

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

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

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

Создается впечатление, будто в нем множество оттенков серого цвета, но на самом деле оно составлено только из точек черного или белого!

Такое смешивание точек ограниченного количества цветов для имитации полутонов называется дизеринг (dithering).

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

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

Идея дизеринга по шаблону заключается в том, чтобы сформировать определенный узор для каждого оттенка, который можно изобразить с помощью шаблона заданного размера. Например, если размер шаблона 4x4 клеточки, то он позволяет передать 17 оттенков. Если размер 8x8 клеточек, то с помощью такого шаблона можно передать 65 оттенка.

Например, один из распространенных шаблонов - матрица Байера 4x4 - позволяет передать 17 оттенков с помощью следующего набора узоров:

А для матрицы Байера 8x8 набор доступных узоров гораздо богаче и позволяет передать уже 65 оттенков:

Матрица Байера 4x4 выглядит следующим образом:

12	4	14	6
3	11	1	9
15	7	13	5
0	8	2	10

Клеточек у нас в шаблоне 4x4 всего 16, и в каждую мы можем поставить число от 0 до 16, тем самым формируя узор дизеринга для каждого полутона.

Работает это по следующему принципу. Яркость клеточки представляет собой диапазон значений от 0 до 255, и значения из шаблона разбивают этот диапазон равномерно на 16 участков, в зависимости от значения порога в матрице:

0: 0-15	4: 61-79	8: 128-143	12: 192-207
1: 16-31	5: 80-95	9: 144-159	13: 208-223
2: 32-47	6: 96-111	10: 160-175	14: 224-239
3: 48-63	7: 112-127	11: 176-191	15: 240-255

При применении дизеринга по шаблону исходное изображение разбивается на участки размером с шаблон (в нашем случае это будут участки 4x4 клеточки) и каждая клеточка полученного участка сопоставляется с шаблоном по следующему алгоритму:

1. Берем значение из шаблона, соответствующее положению клеточки участка относительно матрицы
2. Вычисляем пороговое значение по формуле ЗначениеИзШаблона/КоличествоЯчеекШаблона*255
3. Если значение яркости клеточки рисунка больше порога, то клеточка будет белой. Если меньше или равно - черной
4. Записываем вычисленное значение яркости в результат дизеринга.

Давайте попробуем обработать нашу картинку по шагам.

Разобьем ее на участки размером 4x4 клеточки:

Начнем обработку с первого блока:

И с первой клеточки:

Ей соответствует значение 12 из шаблона, следовательно порог будет 12/16*255=191,25

Значение 0 яркости меньше порога, поэтому в результирующей картинке клеточка не поменяется, как была черной, так и останется.

Теперь берем вторую клеточку:

Ей соответствует значение 4 из шаблона, порог 63,75. Значение яркости меньше порога, поэтому в результирующей картинке клеточка станет черной.

Идем дальше:

Соответствующее значение из шаблона - 14, порог 223,125. Снова черный в результате.

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

Значения яркости	Шаблон	Пороговые значения (округленно)	Результат
0 11 19 28 11 19 28 36 19 28 36 45 28 36 45 53	12 4 14 6 3 11 1 9 15 7 13 5 0 8 2 10	191,3 63,8 223,1 95,6 47,8 175,3 15,9 143,4 239,1 111,6 207,2 79,7 0 127,5 31,9 159,4	Ч Ч Ч Ч Ч Ч Б Ч Ч Ч Ч Ч Б Ч Б Ч

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

Теперь проделаем аналогичную операцию для следующего блока:

Значения яркости	Шаблон	Пороговые значения (округленно)	Результат
36 45 53 61 44 53 61 70 53 61 70 78 62 70 78 87	12 4 14 6 3 11 1 9 15 7 13 5 0 8 2 10	191,3 63,8 223,1 95,6 47,8 175,3 15,9 143,4 239,1 111,6 207,2 79,7 0 127,5 31,9 159,4	Ч Ч Ч Ч Ч Ч Б Ч Ч Ч Ч Ч Б Ч Б Ч

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

Теперь возьмем третий и четвертый блоки:

Значения яркости	Шаблон	Пороговые значения (округленно)	Результат
70 78 87 95 78 87 95 103 87 95 104 112 95 104 112 121	12 4 14 6 3 11 1 9 15 7 13 5 0 8 2 10	191,3 63,8 223,1 95,6 47,8 175,3 15,9 143,4 239,1 111,6 207,2 79,7 0 127,5 31,9 159,4	Ч Б Ч Ч Б Ч Б Ч Ч Ч Ч Б Б Ч Б Ч

Значения яркости	Шаблон	Пороговые значения (округленно)	Результат
103 112 120 129 112 120 129 137 120 129 137 146 129 137 146 154	12 4 14 6 3 11 1 9 15 7 13 5 0 8 2 10	191,3 63,8 223,1 95,6 47,8 175,3 15,9 143,4 239,1 111,6 207,2 79,7 0 127,5 31,9 159,4	Ч Б Ч Б Б Ч Б Ч Ч Б Ч Б Б Б Б Ч

Таким образом у нас получилась вот такая полоска:

Выполним аналогичную операцию для всех остальных блоков, в результате у нас получится такая картинка:

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

Видно, что с помощью дизеринга нам удалось создать имитацию полутонов.

Аналогичным образом выполняются вычисления и для шаблона размером 8x8, только картинка 16x16 при этом будет делиться на 4 блока, а не на 16.

Конечно, на такой маленькой картинке, как 16x16, артефакты дизеринга видны слишком хорошо, но давайте посмотрим, как выглядит дизеринг по матрице Байера 4x4  на картинке размером 300x300 точек: