Описание Image Processing Toolbox. Задача фурье-оптика и методы цифровой обработки изображений

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

Рис.1.5.Функция, описывающая квантование

Задача построения квантователя состоит в определении значений порогов и уровней . Простейший способ решения этой задачи состоит в разбиении динамического диапазона на одинаковые интервалы. Однако такое решение не является наилучшим. Если значения яркости большинства отсчетов изображения сгруппированы, например, в «темной» области и число уровней ограничено, то целесообразно квантовать неравномерно. В «темной» области следует квантовать чаще, а в «светлой» реже. Это позволит уменьшить ошибку квантования .

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

(1.12)

в предположении, что яркость - случайная величина с известной плотностью вероятности .

Cреднеквадратическая ошибка квантования (1.12) равна

. (1.13)

Дифференцируя (1.13) по переменным , и приравнивая производные нулю, получаем нелинейных уравнений

.

Следует отметить, что крайние пороги и определяются динамическим диапазоном яркости. Уравнения (1.14) нетрудно привести к виду

.

Из (1.15) следует, что пороги должны располагаться по середине между двумя соседними уровнями и . Решение этих уравнений можно найти итеративным способом. Оптимальный квантователь, удовлетворяющий критерию (1.12), называется квантователем Ллойда-Макса , а среднеквадратическая ошибка для такого квантователя равна

(1.16)

При равномерном распределении яркости нелинейные уравнения (1.15) можно представить в виде

,

а среднеквадратическая ошибка равна .

В системах цифровой обработки изображений стремятся уменьшить число уровней и порогов квантования, т.к. от их количества зависит длина двоичного кодового слова, которым представляются проквантованные отсчеты в ЭВМ. Однако при относительно небольшом числе уровней на проквантованном изображении появляются ложные контуры. Они возникают вследствие скачкообразного изменения яркости проквантованного изображения (рис.1.6) и особенно заметны на пологих участках ее изменения.

Ложные контуры значительно ухудшают визуальное качество изображения, т.к. зрение человека особенно чувствительно именно к контурам. При равномерном квантовании типичных изображений требуется не менее 64 уровней. На рис.1.7.а и 1.7.б приведены результаты равномерного квантования изображения «Портрет» соответственно на 256 и 14 уровней квантования.

Рис.1.6. К механизму возникновения ложных контуров

Рис.1.7. Результаты равномерного квантования
Рис.1.8. Результат неравномерного квантования	Рис.1.9. Гистограмма изображения “Портрет”

В темных частях изображения на рис. 1.7.б заметны ложные контуры. Использование квантователя Ллойда-Макса позволяет существенно снизить их уровень (см. рис. 1.8, где число уровней квантования также равно 14). На рис. 1.9 приведена гистограмма яркости изображения «Портрет» при 256 уровнях квантования и отмечены пороги при . Из рисунка следует, что чаще квантуются те области динамического диапазона, в которых сгруппированы значения яркости отсчетов.

Чтобы избежать неравномерного квантования, которое не может быть выполнено с помощью стандартного АЦП, используют нелинейные преобразования (рис.1.10). Отсчет исходного изображения подвергается нелинейному преобразованию, чтобы плотность распределения вероятностей преобразованных отсчетов была равномерной, т.е. выполняется процедура эквализации, которая подробно описана в главе 2. Затем отсчеты квантуются с равномерным шагом и подвергаются обратному нелинейному преобразованию.

Рис.1.10. Квантование с предварительным нелинейным преобразованием

Для разрушения ложных контуров Робертс предложил перед равномерным квантованием к отсчетам яркости добавлять шум с равномерной плотностью распределения вероятностей. Добавленный шум переводит одни отсчеты изображения на уровень выше, а другие на уровень ниже. Тем самым разрушаются ложные контуры. Дисперсия добавляемого шума должна быть небольшой, чтобы не привести к искажениям, воспринимаемым как «снег» на изображении, и в то же время достаточной для разрушения ложных контуров. Обычно используют равномерно распределенный шум на интервале . Результаты равномерного квантования на 14 и 8 уровней изображения «Портрет» с предварительным добавлением шума приведены на рис.1.11.а и 1.11.б. При 8-ми уровнях квантования добавляемый шум становится слишком заметным, однако ложные контуры разрушены практически полностью.

Рис.1.11. Результаты равномерного квантования с предварительным добавлением шума

Еще один метод квантования используется в полиграфии. Это метод формирования растровых бинарных (2-х уровневых) изображений из полутоновых. При печати (например, газет или журналов) изображение формируется из белых и черных точек. Для этого все исходное изображение разбивается по пространственным координатам на одинаковые квадратные блоки. Обычно блок содержит элементов. К каждому отсчету блока добавляется число с соответствующими координатами из матрицы возмущающего сигнала, размеры которой равны размерам блока. Например, в качестве матрицы возмущающего сигнала используют числа :

.

Эта операция повторяется для всех блоков. Получаемое при этом изображение квантуется на два уровня. На рис. 1.12.а приведено полутоновое изображение «Портрет» с добавленным возмущающим сигналом. На рис. 1.12.б,в приведены результаты бинарного квантования изображения «Портрет» с добавленным возмущающим сигналом (рис.1.12.б) и без него (рис.1.12.в).

Рис.1.12.Растрирование изображений

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

Определение глубины цвета

Большинство компьютеров при отображении использует 8, 16 или 24 бит на пиксель. Этим определяется глубина цвета отображаемого изображения.

Независимо от того сколько цветов отображает система, MATLAB может запоминать и обрабатывать изображения с различным числом бит на пиксель: 224 цветов для RGB-изображений в формате uint8, 248 цветов для RGB-изображений в формате uint16 и 2159 цветов для RGB-изображений в формате удвоенной точности. Эти изображения наилучше отображаются в системе с 24-битным представлением цвета, хотя источники формирования изображений не всегда могут обеспечивать такую глубину цвета. В большинстве случаев они обеспечивают 16-битное представление цвета.

• Описание определения глубины цвета системы
• Описание выбора глубины цвета

Описание глубины цвета

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

Get(0,"ScreenDepth") ans = 32

MATLAB возвращает число бит на пиксель:

Значение	Описание
8	8-битное представление отображается 256 цветами. 8-битные полутоновые изображения являются составной частью 24-битного представления графической информации.
16	16-битное представление обычно использует 5-бит на каждую цветовую компоненту, что равно 32 градациям (т.е. 2 5) на красную, зеленую и синюю составляющие. В результате такое представление поддерживает 32,768 (т.е., 2 15) различных цветов. Некоторые системы используют дополнительный бит для увеличения числа градаций отображаемого цвета. В нашем случае число различных цветов при 16-битном представлении равно 64,536 (т.е. 2 16).
24	24-битная визуализация использует 8 бит на каждую из трех цветовых составляющих, т.е. 256 (2 8) градаций на красную, зеленую и синюю компоненту. В результате получается 16,777,216 (т.е. 2 24) различных цветов.
32	32-битная визуализация использует 24 бита для запоминания цветовой информации а еще 8 бит используется для запоминания насыщенности (прозрачности) данных. Это так называемый альфа канал.

Описание выбора глубины цвета

В зависимости от используемой системы, можно устанавливать различные значения количества бит на пиксель. (Это может быть также связано с разрешением графических объектов. В большинстве случаев 24-битное представление обеспечивает хорошую визуализацию. Если есть необходимость использовать меньшее число бит на пиксель, то можно использовать 16-битное представление. При обработке полутоновых изображений, в большинстве случаев, достаточно 8 бит на пиксель.

Уменьшение числа цветов на изображении

В этом пункте описано метод уменьшения числа цветов в индексных или RGB изображениях. Рассмотрим также метод диффузионного псевдосмешения цветов (dithering). Этот метод использует визуальное увеличение количества цветов на изображении.

Внизу приведены краткие описания функций уменьшения цветов на изображении в приложении Image Processing Toolbox.

В системах с 24-битным отображением цвета RGB изображения могут отображаться 16,777,216 (т.е. 2 24) цветами. В системах с меньшим количеством отображаемых цветов RGB изображения также будут отображаться хорошо, потому что MATLAB автоматически использует аппроксимацию цветов и диффузионное псевдосмешение цветов.

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

• В системах с 8-битным отображением при визуализации индексных изображений, которые имеют больше, чем 256 цветов, применяется метод диффузионного псевдосмешения цветов (dithering), поскольку не все цвета могут быть представлены системой.
• В некоторых системах палитра в принципе не может иметь больше, чем 256 позиций.
• Если индексное изображение содержит больше, чем 256 цветов, MATLAB запоминает данные изображения в массив не в формате uint8, а в формате удвоенной точности. Это приводит к увеличению объема запоминаемых данных, поскольку каждый пиксель занимает 64 бита.
• Файлы изображений больших размеров желательно записывать в формате, который использует при визуализации 256 цветов. Если при записи (с использованием функции imwrite) в этом же формате изображения имеют больше чем 256 цветов, то в дальнейшем возможны ошибки при визуализации.

Уменьшение числа цветов на индексном изображении

Использование rgb2ind

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

• Квантование
  • Равномерное квантование
  • Квантование с наименьшей дисперсией
• Отображение палитры

Качество результирующего изображения зависит от выбранного метода аппроксимации, диапазона цветов исходного изображения и использования метода диффузионного псевдосмешения цветов (dithering). Отметим, что результат работы методов очень зависит также от конкретного изображения.

Квантование

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

При рассмотрении этого вопроса применяется понятие куб RGB цветов. Куб RGB цветов представляет собой трехмерный массив всех цветов, которые определены для этого типа данных. Поскольку изображения в MATLAB могут быть представлены в различных форматах (uint8, uint16 или double), то это будет влиять на дискретизацию цветов в кубе RGB.

Равномерное квантование. Для выполнения равномерного квантования используется функция rgb2ind с соответствующими параметрами.

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

RGB = imread("peppers.png"); = rgb2ind(RGB, 0.1);

На изображении продемонстрировано равномерное квантование изображения, представленного в формате uint8. Для удобства на изображении показан двухмерный срез цветового куба, где красный цвет равен 0, а диапазон зеленого и голубого равен .

Квантование с наименьшей дисперсией. Для реализации квантования с наименьшей дисперсией используется функция rgb2ind с указанием максимального числа цветов на результирующем изображении. Это число определяет количество ячеек, на которое будет разбит цветовой куб RGB. Рассмотрим пример реализации метода квантования для создания индексного изображения с использованием 185 цветов.

RGB = imread("peppers.png"); = rgb2ind(RGB,185);

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

Уменьшение количества цветов на индексном изображении

Для уменьшения количества цветов на изображении используется также функция imapprox. Функция imapprox использует некоторые методы аппроксимации. По сути, функция imapprox сначала с помощью функции ind2rgb выполняет преобразование изображения в формат RGB, а потом использует функцию rgb2ind для преобразования в индексное изображение с измененным количеством цветов.

Пример.
Рассмотрим пример формирования изображений, которые содержат 128 и 16 цветов с использованием функций rgb2ind и imapprox соответственно.

L=imread("peppers.png"); figure,imshow(L);

Исходное изображение

L=im2double(L); = rgb2ind(L, 128); figure,imshow(x,map);

Изображение со 128 цветами

Imapprox(x,map,16); figure,imshow(Y, newmap);

Изображение с 16 цветами

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

Сглаживание цветовых переходов

Метод диффузионного псевдосмешения цветов (dithering)

При использовании функций rgb2ind или imapprox для уменьшения количества цветов на изображении, качество результирующего изображения немного ниже. Это связано с уменьшением количества цветов, с помощью которых отображается изображение. Обе функции - rgb2ind и imapprox - применяют метод диффузионного псевдосмешения цветов (dithering). Это приводит к визуальному увеличению количества отображаемых цветов. Метод dithering изменяет цвета пикселей окрестности таким образом, что средний цвет окрестности аппроксимирует исходный RGB-цвет.

Рассмотрим пример работы метода диффузионного псевдосмешения цветов (dithering).

1. Считывание и визуализация исходного изображения. rgb=imread("onion.png"); imshow(rgb);

   

2. Создание индексного изображения с восьмью цветами без применения метода диффузионного псевдосмешения цветов (dithering). =rgb2ind(rgb,8,"nodither"); figure, imshow(X_no_dither,map);

   

3. Создание индексного изображения с восьмью цветами с применением метода диффузионного псевдосмешения цветов (dithering). =rgb2ind(rgb,8,"dither"); figure, imshow(X_dither,map);

   

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

   Выполнение преобразования цветовых пространств

   Преобразование цветовых данных между цветовыми пространствами

   Наиболее часто в Image Processing Toolbox для описания цифровых изображений используется цветовая система RGB. В этом случае столбцы палитры представляют собой интенсивности красной, зеленой и синей составляющих. Палитровые изображения могут иметь произвольную глубину цвета, хотя наиболее широкое распространение получили палитровые изображения, глубина цвета которых составляет соответственно 4 и 8 бит на пиксель.

   Известны два подхода к отображению цветов из большего цветового пространства в меньшем. Один из них заключается в том, что цвета, которые находятся за пределами цветового поля преобразуются в наиболее близкие по тону цвета внутри цветового поля. Этот подход называется отсечением (Clipping). Второй метод - это метод сжатия (Compression). Он заключается в том, что каждый цвет на входе независимо от того, попадает он в цветовое поле выводного устройства или нет, приводится к другому цвету из цветового диапазона выходного устройства (естественно, далеко не случайным образом). Существующие методы преобразования цветовых пространств отличаются друг от друга тремя главными особенностями: сжатием цветовой гаммы, тональной компрессией (приведение динамического диапазона вводного устройства к выводному) и отображением точки белого цвета.

   Преобразования между устройство-зависимыми цветовыми пространствами

   Рассмотрим два цветовых пространства RGB и CMYK. Любой цвет в пространстве RGB формируется как сумма разных количеств красной, зеленой и синей составляющих. Когда значения всех составляющих равны нулю, тогда формируется черный цвет. Если все составляющие принимают максимально возможное значение, тогда формируется белый цвет. Однако понятие "белый цвет" является приближенным. Дело в том, что RGB-составляющие обеспечивают только хорошее приближение, а настоящий белый цвет может быть получен только сложением всех его спектральных составляющих, а не только R,G и B. В CMYK-пространстве белый цвет достигается обнулением всех его составляющих, а Cyan (C, Голубой), Magenta (M, Пурпурный) и Yellow (Y, Желтый) используются в нем для создания прочих цветов. Недостатком этого цветового пространства является то, что устройства, которые его используют, не могут отображать яркие и насыщенные цвета.

   Цветовые пространства RGB и CMYK являются устройство-зависимыми, так как цвет в них привязан к тому или иному устройству, для которого заданы эти значения. "Устройством" может быть принтер, сканер, монитор и пр. Действительно, каждый принтер, сканер или монитор одно и то же изображение будут отображать своими цветами, хотя значения RGB на них подаются одинаковые.

   В общем случае, цвет может быть описан координатами для данного набора основных цветов или координатами цветности и уровнем их яркости. Цвет можно описать с помощью линейной или нелинейной функции координат цвета или координат цветности и яркости. Линейные преобразования координат цвета представляют собой переход к новому набору цветов. Существующие системы координат цвета позволяют количественно описать цвета и формулы их преобразования.

   В таблице приведен список устройство-зависимых цветовых пространств, которые поддерживаются приложением по обработке изображений системы Matlab.

   Функция	Назначение	Назначение
   XYZ	Система координат спектральных основных цветов, которая была разработана в 1931 г. МКО (Международной комиссией по освещению).	xyY, uvL, u"v"L и L*a*b*
   xyY	Описание получения нормированных хроматических значений. Составляющая Y, как и в системе XYZ, представляет яркость.	XYZ
   uvL	Равноконтрастная система координат. L представляет яркость и является аналогом Y в XYZ.	XYZ
   u"v"L	Развитие прежней системы с целью получения цветового пространства, в котором единичные изменения цветности и яркости воспринимаются одинаково.	XYZ
   L*a*b*	Попытка учесть зависимость восприятия и яркости. L* представляет собой нелинейное масштабирование L , нормированное относительно некоторых точек.	XYZ
   L*ch	В этой модели c и h представляют соответственно насыщенность и цветность. В полярных координатах эта система преобразуется в L*a*b* .	L*a*b*
   sRGB	Цветовое пространство, которое соответствует цветовому охвату среднестатистического ЭЛТ-монитора.	XYZ и L*a*b*

   Пример: Представление изображений в различных цветовых пространствах

   Считаем изображение в формате RGB в рабочее пространство MATLAB и преобразуем цветовые данные в цветовое пространство XYZ:

   

Аннотация: Введение. Алгоритм равномерного разбиения цветового пространства. Алгоритм разбиения по частоте вхождения: идея алгоритма, метод разбиения цветового куба - локально отсортированный поиск. Алгоритм медианного сечения. Методы кластеризации для квантования изображений: метод K-средних, метод связности графа, иерархический метод, обобщенный метод K-средних или метод динамических сгущений. Заключение.

12.1. Введение

Процесс преобразования аналогового сигнала в цифровую форму состоит из трех стадий: дискретизации ( "Дискретизация. Антиалиасинг. Геометрические преобразования растровых изображений"), квантования и кодирования. В данной лекции рассматривается вторая стадия. Квантование - это замена величины отсчета ближайшим значением из набора фиксированных величин. Применительно к изображениям это означает уменьшение количества значений атрибутов для каждого пикселя или, проще, уменьшение количества цветов в изображении. При этом требуется, чтобы качество изображения ухудшилось как можно меньше. Операция квантования применяется также на уже оцифрованном материале .

Квантование нужно для:

• экономии памяти;
• улучшения свойств последовательностей для сжатия;
• подготовки для последующей обработки;
• добавления эффектов.

Прокомментируем эти пункты подробнее применительно к изображениям.

Экономия памяти достигается, очевидно, за счет уменьшения затрат на хранение значений атрибутов. Многие форматы хранения изображений 1например PNG, GIF , вместо хранения значений атрибутов, хранят номера ссылок на строки палитры. Палитра - это таблица , строки которой содержат фиксированное значение атрибута. Раньше механизм палитры использовался для формирования и вывода изображения на дисплей ввиду того, что объем видеопамяти до 1995 года в обычном настольном компьютере не превышал одного мегабайта.

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

Рис. 12.1.

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

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

В этой лекции предполагается, что значения атрибутов пикселей изображения лежат в цветовом пространстве RGB ( "Основные понятия. Представление цвета в машинной графике"). Псевдокоды алгоритмов для простоты изложения приведены для 8-битного полутонового изображения (256 оттенков) (см. рис. 12.1), перевод осуществляется в 4-битное изображение (16 оттенков).

Рис. 12.2.

12.2. Алгоритм равномерного разбиения цветового пространства

Рассмотрим самый простой алгоритм квантования - алгоритм равномерного разбиения цветового пространства , также называемый линейным квантованием . Разобьем цветовое пространство на равные части по каждому из основных направлений (для RGB таких направлений три - по числу компонент ). Например, в направлении синей или зеленой оси (см. рис. 1.5) разобьем куб на 8 частей, а в направлении красной - на 4 . Множество значений, которые образуются на пересечении разбиений, занесем в таблицу. В нашем примере получается 256 значений, равномерно распределенных по RGB -кубу. Далее преобразование изображения сводится к поиску соответствующего номера в таблице так, чтобы расстояние между реальным цветом и замещающим его было минимальным. Это можно сделать быстро с помощью округления.

// из 256 оттенков серого делаем 16 // I(pixel) - атрибут пикселя // Inew(pixel) новый атрибут - номер ссылки в палитре // Palette - палитра // количество оттенков в исходном изображении NOldColors = 256; // количество элементов в палитре NNewColors = 16; // 1. Заполняем палитру for(i = 0; i < NNewColors; i++) { Palette[i] = i * (NOldColors / NNewColors); } // 2. Вычиcляем новые значения атрибутов foreach(pixel in I) // для каждого пикселя { // округляем, отбрасывая дробную часть Inew(pixel) = I(pixel) / (NOldColors / NNewColors); } Листинг 12.1. Алгоритм равномерного разбиения цветового пространства

В результате работы данного алгоритма (см. рис. 12.2) в изображении часто возникают слишком четкие границы, а детали, наоборот, стираются. Однако основные достоинства данного алгоритма - простота и высокая скорость.

К методам скрытия в пространственной области можно также отнести метод квантования изображения , основанный на межпиксельной зависимости, которую можно описать некоторой функцией . В простейшем случае можно вычислить разницу между смежными пикселями ; и (или и ) и задать ее как параметр функции : , где - дискретная аппроксимация разницы сигналов .

Поскольку - целое число, а реальная разница - действительное число, то возникают ошибки квантования . Для сильно коррелированных сигналов эта ошибка близка к нулю: .

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

	-4	-3	-2	-1
b i

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

Рассмотрим пример программы, реализующей метод квантования изображения

Исходные данные - стандартные.

Шаг 2

Стеганоключ вычисляем по модулям (М.28) и (М.29). При этом модуль (М.28) возвращает все возможные разницы сигналов (от -255 до +255), а модуль (М 29) - значения бит, соответствующие этим разницам.

Значения b i в данном случае рассчитываются на основании массива красной цветовой составляющей. При этом для каждой колонки массива R рассчитывается сумма по модулю 2 составляющих ее элементов с булевым прибавлением к результату суммирования единицы при каждом третьем элементе. В конце модуля полученной вектор b расширяется на длину вектора . Таким образом, элементы массива b носят псевдослучайный характер. Фрагменты сформированного стеганоключа показаны на рис. 5.15.

л-			b=
		-255
		-254
		-253
		-252
		-2
		-1

Рис. 6.15. Фрагменты стеганоключа

Выполним развертывание массива контейнера С (массив синей цветовой составляющей) в вектор, используя модуль (М.16). Зададим стартовый индекс элемента полученного вектора, начиная с которого будет производиться встраивание бит, сообщения (например, ).

Для расчета величины шага (псевдослучайного интервала) используем модуль (М.15). Пусть при этом К := 8.

Шаг 4

Алгоритм встраивания реализует модуль (М.30). Формирование вектора двоичных данных из строки символов аналогично представленному в (М.21) (при этом, однако, необходимо заменить на ).

Для каждого -го бита сообщения выполняется вычисление индекса z элемента вектора контейнера Cv . Рассчитывается разница между соседними пикселями C vz и C vz-1 Внутренним циклом производится поиск соответствующего значения разницы в векторе . В случае обнаружения, переменной присваивается значение индекса i, который соответствует данной разнице в .

Если значение не соответствует текущему биту скрываемого сообщения, то выполняется поиск ближайшего индекса, при котором bi равняется биту сообщения. Поиск производится вниз (L) и вверх (Н) от индекса .

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

Интенсивность пикселя контейнера Sv z равна увеличенной на величину интенсивности смежного пикселя Sv z -1 . Если данное увеличение приводит к выходу значения интенсивности цвета за пределы диапазона , то, наоборот, интенсивности смежного пикселя Sv z -1 присваивается значение интенсивности пикселя Sv z , уменьшенной на величину ). После встраивания последнего бита сообщения внешний цикл прерывается.

Проводим обратное свертывание вектора Sv в матрицу, имеющую размерность первичного массива С (М.7). Получаем массив S .

Привлекает внимание

Например, старый добрый формат GIF использует палитру, максимум на 256 цветов. Если вы захотите сохранить серию своих селфи как gif-анимацию (кому бы это надо было), то первое, что вам, а точнее программе, которую вы будете для этого использовать, надо будет сделать – создать палитру. Можно использовать статическую палитру, например web-safe colors , алгоритм квантизации получиться очень простым и быстрым, но результат будет «не очень». Можно создать оптимальную палитру на основе цветов изображения, что даст результат наиболее визуально похожий на оригинал.

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

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

Предыстория

Давным-давно, когда Nokia была тёплой и ламповой главенствовала на рынке смартфонов, а владельцы смартфонов гордо звали себя «смартфонщики», в те стародавние времена писал я простенькие программки на python для series60. На одну из них намедни наткнулся копаясь в архивах. GifTool – программка для создания gif-анимации из набора картинок. В ней я реализовал квантизацию методом медианного сечения, алгоритм сжатия LZW, вся структура файла создавалась самостоятельно, для неизменившихся на следующем слайде пикселей использовалась прозрачность, чтобы уменьшить итоговый размер файла. Захотелось мне освежить свою память, посмотреть – как же она работала. Открыл код и … Это чувство, когда ты не можешь разобраться в своём говнокоде десятилетней давности. Про PEP8 я тогда не знал, поэтому читаемость кода была чуть менее чем никакой (тогда мне нравился минимализм, как и многим начинающим программистам). Прослезился, поплевался, отрефакторил в PyCharm, разобрался как реализовал метод медианного сечения, по быстрому накидал «грязный» скрипт. Работает! Палитра создаётся, изображение на выходе получается сносное. И тут меня закусило – смогу ли я добиться лучших результатов, чтобы картинка визуально была как можно ближе к оригиналу.

Итак – метод медианного сечения. Он прост до безобразия. Первым делом надо из всех уникальных цветов изображения составить RGB куб. Далее рассечь его по самой длинной стороне. Например, диапазон красного у нас от 7 до 231 (длина 231-7=224), зелёного от 32 до 170 (длина 170-32=138), синего от 12 до 250 (длина 250-12=238), значит, будем «резать» куб по синей стороне. Получившиеся сегменты так же рассекаем по длинной стороне и т.д. пока не получим 256 сегментов. Для каждого сегмента высчитать средний цвет – так мы и получим палитру.

Пара картинок почти в тему, для наглядности

Что здесь можно улучшить? Первое, что приходит в голову – вычислять средний цвет не тупо сложив все цвета и разделив на их количество [ sum(color) / count(color) ], а с учётом, сколько раз каждый цвет встречается в изображении. То есть каждый цвет умножаем на количество его вхождений в изображении, полученные значения складываем, результат делим на количество вхождений в изображении всех цветов данного сегмента [ sum(color * total) / sum(total) ]. В результате, наиболее часто встречаемые цвета имеют приоритет при вычислении, но и редкие цвета вносят свои корректировки, поэтому палитра получается лучше, визуальное отклонение цветов меньше. Для лучших результатов желательно ещё учитывать гамму, но я оставил это на потом. Второе не так явно – медианное сечение совсем не учитывает особенности восприятия цвета человеческим глазом. Оттенки зелёного мы воспринимаем гораздо лучше оттенков синего. Я решил исправить это недоразумение и «сплющил» куб – длины сторон помножил на коэффициенты из этой статьи . В результате по зелёной и красной стороне сечений стало больше, по синей меньше. Такого решения я больше нигде не встречал (может плохо искал), но результат на лицо.

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

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

Вот теперь можно снова вернуться к индексированию. Рассеиванием ошибок мы изменяем цвета пикселей и получаем такие, которых нет в нашем RGB-кубе (напомню, он составлен исключительно из цветов изображения). Теперь нельзя просто посмотреть в каком сегменте находится цвет, чтобы назначить индекс. Решение нашлось сразу – поиск ближайшего цвета в палитре . В данную формулу я подставил всё те же коэффициенты. Сравнивая результаты подбора цвета палитры по индексу сегмента в который входит исходный цвет и результаты поиска ближайшего цвета, наглядно увидел, что ближайший цвет часто оказывается в соседнем сегменте. Если исходный цвет находится ближе к центру сегмента – то индекс сегмента соответствует индексу цвета в палитре, но чем ближе исходный цвет к краям сегмента, тем больше вероятность, что ближайший цвет окажется в соседнем сегменте. В общем, единственный правильный путь индексирования – поиск ближайшего цвета в палитре. Но у поиска есть минус – он медленный, очень медленный. Писать числодробилку на python плохая идея.

Ну вот, хотел объяснить в двух словах, а получилась целая куча непонятной писанины. Надеюсь, код я пишу лучше, чем объясняю, поэтому вот ссылочка на github . Код несколько раз переписывался, сначала совершенствовался алгоритм, пока результат меня не устроил, потом оказалось, что он жрёт слишком много оперативы при обработке фотографий (сначала тестировал на небольших картинках), пришлось перенести RGB-куб, медианное сечение и карту пикселей в базу данных (sqlite). Скрипт работает очень медленно, но результат получается лучше, чем квантизация средствами PIL/Pillow и GIMP’ом (в нём эта операция называется индексирование).

Наглядная демонстрация:

Оригинал

Результат квантизации в GIMP, оптимальная палитра на 256 цветов + размывание цвета по Флойду-Стенбергу (нормальное)

Результат квантизации PIL/Pillow image.convert(mode="P", dither=PIL.Image.FLOYDSTEINBERG, palette=PIL.Image.ADAPTIVE, colors=256)

Результат квантизации моим кодом

На что обратить внимание: рассеивание ошибки у GIMP сильно «шумит», PIL/Pillow создает не очень оптимальную палитру и практически не рассеивает ошибки (резкие переходы между цветами).
Если не видите разницу - посмотрите другие примеры на github .

P.S.: есть замечательная программа Color Quantizer , которая справляется с данной задачей лучше и быстрее, поэтому практического смысла мой скрипт не имеет, сделан исключительно из «спортивного» интереса.
UPD: обновил проект на github . Добавил алгоритм квантизации Octree (октодерево), популярные формулы рассеивания ошибок, поиск ближайшего цвета по среднему значению красного.