Дизеринг
Имитация полутонов с помощью смешивания клеточек нескольких цветов
Уменьшение цветов в изображении
Обычно фотографии, снятые на профессиональную фотокамеру или даже на телефон, или изображения, скаченные из интернета, имеют большой размер (несколько тысяч клеточек по ширине и высоте) и огромное количество цветов (миллионы). Даже для вышивки это слишком много, не говоря уже о вязании.
Поэтому для создания схемы, по которой можно связать изделие разумного размера, нужно уменьшить и саму картинку, и количество цветов в ней.
При уменьшении размера неизбежно потеряется детальность изображения. Ниже приведен пример исходного изображения размером 768x768 клеточек, которое было уменьшено до размера 128x128:
Посмотрим теперь, как меняется изображение по мере уменьшения количества цветов в нем, от полноцветного до 2 цветов:
Полноцветное изображение
256 цветов
128 цветов
64 цвета
32 цвета
16 цветов
8 цветов
4 цвета
2 цвета
Поначалу может даже показаться, что ничего не меняется, но по мере того, как цветов становится все меньше и меньше, изображение начинает заметно терять в качестве.
Как же так получается, что изображение с 256 цветами визуально мало чем отличается от полноцветного? Дело в том, что программы для обработки графики при уменьшении количества цветов могут создавать участки, в которых точки одного цвета чередуются с другим таким образом, чтобы на отдалении они визуально сливались и как бы создавали третий цвет. Эта методика называется дизеринг.
Сравните, как выглядит 256-цветное изображение с дизерингом:
и без:
Особенно хорошо разница заметна на черно-белом (его еще называют однобитным, т.к. каждая клеточка может принимать значение либо 0 (черный) либо 1 (белый), не путать с серым полутоновым, где каждая клеточка может содержать оттенки серого цвета) изображении:
Обратите внимание, на первом изображении хорошо видно, как за счет смешивания черных и белых точек создается визуальный эффект полутонов.
Дизеринг по шаблону
Алгоритмов для смешивания черных и белых клеточек для создания эффекта полутонов придумано огромное количество, но самое широкое распространение получили два:
- Дизеринг по шаблону
- Дизеринг на основе распределения коррекции цвета на соседние клетки изображения
Сегодня мы рассмотрим первый.
В качестве исходного изображения возьмем градиент из черного в белый размером 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 клеточки) и каждая клеточка полученного участка сопоставляется с шаблоном по следующему алгоритму:
- Берем значение из шаблона, соответствующее положению клеточки участка относительно матрицы
- Вычисляем пороговое значение по формуле ЗначениеИзШаблона/КоличествоЯчеекШаблона*255
- Если значение яркости клеточки рисунка больше порога, то клеточка будет белой. Если меньше или равно - черной
- Записываем вычисленное значение яркости в результат дизеринга.
Давайте попробуем обработать нашу картинку по шагам.
Разобьем ее на участки размером 4x4 клеточки:
Начнем обработку с первого блока:
И с первой клеточки:
Ей соответствует значение 12 из шаблона, следовательно порог будет 12/16*255=191,25
Значение 0 яркости меньше порога, поэтому в результирующей картинке клеточка не поменяется, как была черной, так и останется.
Теперь берем вторую клеточку:
Ей соответствует значение 4 из шаблона, порог 63,75. Значение яркости меньше порога, поэтому в результирующей картинке клеточка станет черной.
Идем дальше:
Соответствующее значение из шаблона - 14, порог 223,125. Снова черный в результате.
Ниже приведен результат вычислений для текущего блока:
| Значения яркости |
Шаблон |
Пороговые значения (округленно) |
Результат |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
Как мы видим, несмотря на то, что весь блок у нас довольно темный, у нас все-таки появились три белые клеточки, которые должны создавать эффект полутонов. Более того, клеточки с одинаковой яркостью дали в итоге разный результат в зависимости от того, какому значению шаблона они соответствуют.
Теперь проделаем аналогичную операцию для следующего блока:
| Значения яркости |
Шаблон |
Пороговые значения (округленно) |
Результат |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
Обратите внимание, что результат получился такой же, как и в первом блоке, несмотря на то, что исходные цвета были другие.
Теперь возьмем третий и четвертый блоки:
| Значения яркости |
Шаблон |
Пороговые значения (округленно) |
Результат |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
| Значения яркости |
Шаблон |
Пороговые значения (округленно) |
Результат |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
Таким образом у нас получилась вот такая полоска:
Выполним аналогичную операцию для всех остальных блоков, в результате у нас получится такая картинка:
Или, если убрать все надписи и вернуть изначальный размер, она выглядит вот так:
Видно, что с помощью дизеринга нам удалось создать имитацию полутонов.
На видео ниже представлена построчная работа алгоритма от начала до конца изображения:
Аналогичным образом выполняются вычисления и для шаблона размером 8x8, только картинка 16x16 при этом будет делиться на 4 блока, а не на 16.
Конечно, на такой маленькой картинке, как 16x16, артефакты дизеринга видны слишком хорошо, но давайте посмотрим, как выглядит дизеринг по матрице Байера 4x4 на картинке размером 300x300 точек:
Полутона в целом получились, но вышли ступенчатые, и в этом заключается главная проблема дизеринга по шаблону: на переходах полутонов всегда будут ступеньки из разных узоров.
Если взять матрицу Байера 8x8, то у нас будет гораздо больше узоров для разных полутонов и этот эффект будет выражен меньше, но, тем не менее, будет:
Если использовать изображения, приведенные к однобитному цвету с помощью шаблонного дизеринга, в вязании, то нужно иметь в виду следующее:
- Популярные шаблоны дизеринга, такие как матрицы Байера, отлично подходят для вязания жаккарда. Можно сразу брать и вязать.
- В то же самое время матрицы Байера не подходят для мозаичного вязания, так как они устроены таким образом, что создают четное количество клеточек одного цвета по вертикали. Для мозаичного вязания нужно разрабатывать специально адаптированные матрицы.
- Дизеринг по шаблону отлично смотрится в геометрических узорах или там, где в принципе изначально мало цветов и они плоские, нет плавных переходов цвета, например, некоторые виды рисованной мультипликации.
- За счет повторяемости узора в ряду такие схемы проще вязать.
В генераторе схем на сайте доступны как стандартные матрицы Байера, так и разработанные мной адаптированные для мозаики матрицы. А также можно воспользоваться режимом эксперта и составить собственную матрицу, наилучшим образом подходящую для вашей картинки.
Дизеринг с распределением коррекции
В прошлой части мы рассмотрели имитацию полутонов (дизеринг) с помощью шаблона, который обладает несколькими недостатками:
- Количество передаваемых оттенков ограничено размером матрицы
- Каждый оттенок создается хорошо различимым регулярным узором, что может не очень хорошо смотреться на фотографиях
- На изображениях с плавным переходом полутонов будут видны четкие границы узоров
- Тонкие линии контрастного цвета могут пропасть полностью, если попадутся на неудачный участок шаблона
Для борьбы с этими недостатками был придуман другой метод, заключающийся в адаптивном распределении значения коррекции, возникшего при приведении клеточки к черному или белому цвету, на соседние клеточки.
За основу возьмем то же самое изображение 16x16 клеточек из предыдущей части:
Если дизеринг по шаблону при сохранении общего принципа алгоритма использует для создания полутонов шаблоны (матрицы), то дизеринг с распределением коррекции (ошибки) работает с фильтрами, которые указывают, какую часть коррекции на какие именно соседние клеточки необходимо распределить.
Фильтров придумано огромное множество и они создают разные эффекты. Одним из самых распространенных фильтров является фильтр Флойда-Штейнберга, который выглядит следующим образом:
| -1 |
-1 |
7/16 |
| 3/16 |
5/16 |
1/16 |
Здесь голубым цветом выделена исходная клеточка, которую мы модифицируем и с которой распределяем коррекцию на соседние клеточки, красным - клеточка, на которую мы не распространяем коррекцию, а зеленым - клеточки, на которые распространение коррекции происходит.
Знаменатель дроби означает, на сколько частей нужно разделить значение коррекции, а числитель - какая доля коррекции будет распределена. Упрощенно можно считать, что если сумма всех числителей будет равна знаменателю, то полученный результат коррекции будет примерно совпадать с исходным изображением по яркости и контрасту. Если сумма числителей будет меньше знаменателя, то картинка станет более контрастной, потеряются оттенки в самых светлых и самых темных участках. Если больше, то картинка станет ярче.
Как мы видим из таблички, в фильтре Флойда-Штейнберга распространение коррекции происходит вправо, вниз, по диагонали вправо-вниз и влево-вниз. Есть фильтры, которые распространяют коррекцию не только на непосредственно соседние клеточки, но и через одну или даже дальше. Например, фильтр Сьерры выглядит следующим образом:
| -1 |
-1 |
-1 |
5/32 |
3/32 |
| 2/32 |
4/32 |
5/32 |
4/32 |
2/32 |
| -1 |
2/32 |
3/32 |
2/32 |
-1 |
Почему распространение коррекции идет вправо и вниз и не затрагивает клеточки слево от текущей? Дело в том, что обработка изображения идет сверху вниз и слева направо, и слева от текущей клеточки у нас расположены уже обработанные, то есть либо черные, либо белые клеточки. Если на них распространить коррекцию, то они приобретут оттенок серого цвета и их придется обрабатывать повторно. Есть более сложные алгоритмы, которые умеют работать с распределением коррекции на уже обработанные ранее клеточки, но они за рамками данной статьи.
Итак, давайте попробуем обработать нашу картинку алгоритмом дизеринга с распространением коррекции, используя фильтр Флойда-Штейнберга.
Берем первую клеточку. Она уже черного цвета, поэтому делать тут нечего.
У следующей клеточки оттенок серого с яркостью 11. Это меньше порогового значения 128, поэтому мы приведем ее к черному, т.е. к 0. В результате у нас возникнет значение коррекции в 11 единиц, которое нам нужно распределить на соседние клеточки в соответствии с фильтром. Знаменатель дроби (количество долей) у нас 16, поэтому делим 11 на 16 и получаем размер одной доли - 0,6875. Вправо мы должны распределить 7 долей, т.е. 4,8125. Яркость правой клеточки у нас 19, прибавим к ней 4,8125, округлим математически до целого значения и получится новое значение яркости - 24:
Вправо и вниз мы распределяем 1 долю, т.е. 0,6875, или округленно 1:
Вниз распределяем 5 долей, т.е. 3,4375, округленно 3:
И влево-вниз 3 доли, т.е. 2,0625, округленно 2:
Переходим ко второй клеточке. Ее значение яркости уже не 19, а 24, но это все еще меньше 128, поэтому клеточку приводим к черному цвету (0) и получаем значение коррекции 24, которое нужно распределить вправо, вправо-вниз, вниз и влево-вниз соответственно на 11, 2, 8 и 5 значений:
Четвертую клеточку мы тоже приводим к черному и распределяем уже 38 пунктов коррекции:
Пройдем до конца ряда:
Обратите внимание, как постепенно накапливается значение коррекции, высветляя соседние клеточки все больше и больше, пока не приводит к тому, что очередную клеточку мы уже приводим не к черному, а к белому: 143 -> 255. При этом значение коррекции у нас уже становится отрицательным: 143 - 255 = -112, соответственно соседние клеточки мы уже будем распределением коррекции не высветлять, а затемнять, отнимая яркость в соответствии с долями распределения коррекции:
Теперь посмотрим на видео, как происходит обработка картинки от начала до конца:
Конечно, на маленьком изображении результат не так очевиден, но вот как этот алгоритм выглядит на изображении 300x300 точек:
Конечно, результат не идеален, есть неровности и заметные артефакты, некрасивые узоры. Для уменьшения артефактов придуманы другие алгоритмы и разные трюки с обработкой изображений, но их описание за рамками данной статьи.
Ниже приведены результаты преобразования той же картинки размером 300x300 точек с использованием разных фильтров:
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
В генераторе схем для платных подписчиков на Бусти и в ВК доступны все эти фильтры и другие настройки, а также возможность составить собственный фильтр.