Алгоритмы квантования для полутоновых и цветных изображений

Содержание

Слайд 2

Содержание Квантование Алгоритм равномерного разбиения цветового пространства Алгоритм разбиения по частоте

Содержание

Квантование
Алгоритм равномерного разбиения цветового пространства
Алгоритм разбиения по частоте вхождения
Метод разбиения цветового

куба - локально отсортированный поиск
Алгоритм медианного сечения
Методы кластеризации для квантования изображений
Слайд 3

Квантование Квантование - это замена величины отсчета ближайшим значением из набора

Квантование

Квантование - это замена величины отсчета ближайшим значением из набора фиксированных величин.


Применительно к изображениям это означает уменьшение количества значений атрибутов для каждого пикселя или, проще, уменьшение количества цветов в изображении.
При этом требуется, чтобы качество изображения ухудшилось как можно меньше. Квантование нужно для:
экономии памяти;
улучшения свойств последовательностей для сжатия;
подготовки для последующей обработки;
добавления эффектов.
Экономия памяти достигается, очевидно, за счет уменьшения затрат на хранение значений атрибутов.
Многие форматы хранения изображений, вместо хранения значений атрибутов, хранят номера ссылок на строки палитры.
Палитра - это таблица, строки которой содержат фиксированное значение атрибута.
Улучшение свойств последовательностей для сжатия достигается за счет уменьшения количества возможных значений, а значит, увеличения повторений.
Слайд 4

Алгоритм равномерного разбиения цветового пространства Рассмотрим самый простой алгоритм квантования -

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

Рассмотрим самый простой алгоритм квантования - алгоритм равномерного разбиения цветового пространства,

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

Алгоритм равномерного разбиения цветового пространства // из 256 оттенков серого делаем

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

// из 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 );
}
В результате работы данного алгоритма (см. рис.) в изображении часто возникают слишком четкие границы, а детали, наоборот, стираются. Однако основные достоинства данного алгоритма - простота и высокая скорость.
Слайд 6

Алгоритм разбиения по частоте вхождения Идея алгоритма состоит в построении палитры,

Алгоритм разбиения по частоте вхождения

Идея алгоритма состоит в построении палитры, состоящей

из N самых часто встречающихся значений атрибутов в исходном изображении.
Для этого нужно построить гистограмму значений атрибутов, затем взять N самых часто встречающихся и провести собственно квантование.
 Соответственно, возникает вопрос: что делать с теми значениями, которые не уместились в палитру? Естественно заменить &лишние& значения самыми близкими аналогами из тех, что попали в палитру.
Близость понимается как квадрат евклидова расстояния, т.е. в пространстве RGB
dist(C1,C2) = (R1 - R2)2 + (G1 - G2)2 + (B1 - B2)2,
где C1, C2 - значения атрибутов.
Задача поиска ближайшего значения в таблице может быть решена несколькими способами.
Самый простой: для каждого значения, не представленного в таблице, перебрать расстояния до всех имеющихся в таблице элементов и выбрать элемент с минимальным расстоянием.
Однако такой метод очень трудоемок и потому не используется на практике.
Вообще, задача поиска в n -мерном пространстве точки из некоторого набора, ближайшей к данной, является одной из классических задач вычислительной геометрии
Слайд 7

Метод разбиения цветового куба - локально отсортированный поиск Разобьем цветовое пространство

Метод разбиения цветового куба - локально отсортированный поиск

Разобьем цветовое пространство (RGB-куб, см.

рис.) на K x K x K одинаковых кубиков.
Разбиение проводится равномерно на K частей вдоль каждой базовой цветовой оси.
С каждым кубиком свяжем отсортированный список значений (в нашем случае - элементов трехмерного евклидова пространства), которые попали в палитру.
Элементом списка является структура из двух переменных: номера значения в палитре и расстояния до ближайшей точки данного кубика.
Если значение из палитры лежит внутри кубика, то расстояние полагается равным 0.
Для того чтобы создать список для кубика, требуется вычислить расстояние до всех значений в палитре.
Затем этот список сортируется.
Для того чтобы ограничить длину списка, применяется простая техника: не должны включаться те значения, которые явно не могут быть ближайшими к этому кубику, а значит, и к значениям, ему принадлежащим.
Это означает, что сначала отыскивается значение из палитры, ближайшее к центру кубика, затем вычисляется расстояние от этого значения до наиболее удаленной точки кубика.
Слайд 8

Предварительные вычисления для локально отсортированного поиска // Palette - палитра //

Предварительные вычисления для локально отсортированного поиска

// Palette - палитра
// Cubes

- массив кубиков
// Cube.palColorsList - список цветов и расстояний
// для данного кубика
// Cube.center - центр кубика
// dist() - расстояние между кубиком и цветом
// Предполагается, что палитра заполнена в
// соответствии c используемым методом
// Предварительные вычисления
foreach( currentCube in Cubes ) {
// Найти ближайшее значение из палитры к центру куба
closestColor = Palette.FindClosest(currentCube.center, Palette);
// пороговое расстояние
maxDist = FindMaxDist( closestColor, currentCube );
// занести цвет в список, если требуется
foreach( color in Palette )
if( dist( color, currentCube ) < maxDist ) currentCube.palColorsList.Add( { color, dist( color, currentCube ) } ); }
Слайд 9

Квантование по построенной палитре с помощью локально отсортированного поиска // Image

Квантование по построенной палитре с помощью локально отсортированного поиска

// Image -

исходное изображение, newImage – получаемое
// Cubes - массив кубиков
// Cube.palColorsList - список цветов и расстояний
// для данного кубика
// dist() - расстояние между кубиком и цветом
// Предполагается, что палитра заполнена в соответствии c
// методом, а также посчитана предварительная информация для
// кубиков
// Квантование
foreach( pixel in Image ) {
// кубик для данного пикселя
// вычисляется делением координат на размер куба и
// взятием целой части
currentCube = GetCube(Cubes, pixel.color);
// INF - бесконечность справа
minDist = INF;
foreach( entry in currentCube.palColorsList ) {
if( minDist < entry.distance ) break;
// выход из цикла
if( dist(pixel.color, entry.color) < minDist ) { minDist = dist(pixel.color, entry.color);
newImage[pixel].color = entry.color; } } }
Слайд 10

Локально отсортированный поиск Найденное расстояние полагается порогом, при превышении которого очередное

Локально отсортированный поиск

Найденное расстояние полагается порогом, при превышении которого очередное значение

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

Результат работы алгоритма разбиения по частоте вхождения

 Результат работы алгоритма разбиения по частоте вхождения

Слайд 12

Алгоритм медианного сечения Построим алгоритм, который сформирует палитру так, чтобы каждое

Алгоритм медианного сечения

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

равному количеству значений атрибутов пикселей в исходном изображении.
Это достигается путем последовательного разбиения цветового пространства на параллелепипеды со сторонами, параллельными осям цветового пространства RGB 
Первый шаг алгоритма заключается в нахождении минимального параллелепипеда, так что все значения атрибутов пикселей исходного изображения принадлежат ему.
Далее происходит процедура разбиения параллелепипеда.
На втором шаге используется так называемое адаптивное разбиение, состоящее из следующих шагов:
выбор самой длинной стороны (точнее, направления) параллелепипеда,
сортировки значений вдоль выбранного направления,
нахождения медианы множества значений вдоль выбранного направления,
разделения параллелепипеда по найденной медиане на две части.
Таким образом, получится два параллелепипеда, которые содержат примерно равное количество значений.
Слайд 13

Квантование методом медианного сечения // Image - исходное изображение, newImage -

 Квантование методом медианного сечения

// Image - исходное изображение, newImage - результат


// Colors, Colors1, Colors2 - множества цветов
// Palette - палитра, NNewColors - желаемое количество цветов
// BBox – параллелепипед
// BBox1, BBox2 - получаемые на шаге разбиения параллелепипеды
// BSPtree - бинарное дерево, представляющее разбиение
// цветового пространства {
// 1. Находим минимальный параллелепипед
BBox = FindBBox( Image ); // 2. Разбиение
i = 1; // получить отсортированное множество значений цветов
// изображения
Colors = sort( Image.colors );
// создаем родительский узел дерева
BSPTree.rootNode = { AllColors, BBox };
DoPartition( i, BSPTree.rootnode );
// 3. Заполним палитру и сформируем итоговое изображение,
// терминальные вершины дерева содержат искомое разбиение
foreach( pixel in Image ) { paletteIndex = BSPTree.FindNode( pixel.color );
newImage[pixel].index = paletteIndex; } }
Слайд 14

Квантование методом медианного сечения DoPartition( i, node ) { // нужно

 Квантование методом медианного сечения

DoPartition( i, node ) {
// нужно ли

проводить разбиение? pow(2,i) - 2 в степени i
if ( pow(2,i+1) > NNewColors ) // остановить разбиение
return; else {
// находим медианное значение вдоль самой длинной
// стороны параллелепипеда
FindMedian( mvalue, direction, node.Colors, node.BBox );
// границы новых параллелепипедов (разбиение вдоль
// самой длинной стороны параллелепипеда)
GetNewBBoxes( node.BBox, BBox1, BBox2, value, direction );
// копируем все значения меньшие value по
// соответствующей координате
Colors1 = { color in node.Colors if( color[direction] < value ) };
// копируем все значения большие или равные value
// по соответствующей координате
Colors2 = { color in node.Colors if( color[direction] >= value ) };
// добавим к узлу дерева детей
BSPTree.node.AddСhildNode( { Colors1, BBox1 } ); BSPTree.node.AddСhildNode( { Colors2, BBox2 } );
foreach( childnode in node ) DoPartition( i+1, childnode ); } }
Предыдущая процедура повторяется для каждого из параллелепипедов до тех пор, пока не сформируется N параллелепипедов, где N равно желаемому размеру палитры.
Слайд 15

Результат работы алгоритма медианного сечения

Результат работы алгоритма медианного сечения

Слайд 16

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

Квантование методом медианного сечения

Если же на каком-то шаге потребуется разделить параллелепипед,

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

Квантование методом медианного сечения Ключевым событием в этом алгоритме является шаг,

Квантование методом медианного сечения

Ключевым событием в этом алгоритме является шаг, на

котором определяется координата, где требуется провести сечение параллелепипеда.
Можно вместо выбора направления наибольшей длины параллелепипеда выбрать направление наибольшей дисперсии соответствующей координаты, или так выбрать место разделения, чтобы сумма дисперсий для двух образующихся параллелепипедов была минимальна.
Часто реализации алгоритма используют специальные структуры для хранения разбиения цветового пространства.
Примером такой структуры может служить BSP дерево.
Результаты работы алгоритма являются очень хорошими (см. рис.); при этом скорость работы данного алгоритма высока.
Различные вариации данного алгоритма используются в известных приложениях для обработки изображений, например в GNUImageManipulation Program (GIMP).
Слайд 18

Методы кластеризации для квантования изображений В данном разделе будут рассмотрены методы,

Методы кластеризации для квантования изображений

В данном разделе будут рассмотрены методы, производящие

кластеризацию значений атрибутов изображения для дальнейшего построения палитры.
В общем случае кластеризация - это процесс разбиения объектов на группы (кластеры) на основе свойств, описывающих сущность объектов.
В применении к квантованию изображений это означает процесс разбиения значений атрибутов на группы (кластеры) так, что внутри каждой группы находятся лишь близкие значения.
Метод K-средних
Это один из самых популярных алгоритмов для кластеризации. Зафиксируем число K - размер палитры - и будем разбивать все значения атрибутов изображения на K кластеров.
Слайд 19

Метод K-средних // K - число центров кластеров = размер палитры

Метод K-средних

// K - число центров кластеров = размер палитры
//

moves - число перемещений при перестройке кластеров
// I - структура, содержащая изображение и информацию
// о принадлежности значений кластерам.
// Clusters - кластеры, Clasters.centers - центры кластеров
K = NOldColors;
// Выберем случайно К центров кластеров
Clusters.centers = GetRandomFromSet(I,k); /
/ Вычисляем принадлежность значений атрибутов кластерам
foreach( pixel in Image ) {
pixel.cluster = Clusters.getClosest( pixel.color ); }
// Основная итерация алгоритма
// T1, T2 - пороги, iter - счетчик итераций
iter = 0;
while( ( moves != 0 ) OR ( moves < T1 AND iter > T2 ) ) {
moves = 0;
Слайд 20

Алгоритм кластеризации K-средних // пересчитываем центры кластеров foreach( cluster in Clusters

Алгоритм кластеризации K-средних

// пересчитываем центры кластеров
foreach( cluster in Clusters )

{
colorSet = { pixel.color for pixels in I
if( pixel.cluster = cluster ) };
cluster.center = Average( colorSet );
} foreach( pixel in I ) {
newcluster = Clusters.getClosest( pixel.color );
if( newcluster != pixel.cluster ) {
moves++; pixel.cluster = newcluster; } }
iter++; }
// заполняем изображение
foreach( pixel in I ) {
pixel.color = Clusters[pixel.cluster].center; }
Слайд 21

Результат работы Алгоритма кластеризации K-средних

Результат работы Алгоритма кластеризации K-средних

Слайд 22

Результат работы Алгоритма кластеризации K-средних Выберем случайным образом K значений атрибутов

Результат работы Алгоритма кластеризации K-средних

Выберем случайным образом K значений атрибутов из исходного изображения

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

Метод связности графа Построим матрицу расстояний D между значениями атрибутов исходного

Метод связности графа

Построим матрицу расстояний D между значениями атрибутов исходного изображения.
В качестве

расстояния можно взять квадрат евклидовой метрики .
Затем выберем число T - порог. После этого построим матрицу B по матрице D по следующему правилу:
Матрицу B можно рассматривать как задающую ребра в графе, в котором вершинам соответствуют пиксели изображения.
Таким образом, связные области графа задают кластеры.
Для формирования кластеров можно использовать волновой алгоритм.
Положим в каждую вершину графа дополнительное число.
Пусть это число равно 0.
Далее выбираем случайную вершину и "поджигаем" ее, т.е. кладем в нее число 1. Затем для каждой вершины, которая соединена ребром с выбранной, кладем 1.
После этого то же самое делаем для связных соседей вершин, куда уже положили 1, - им также кладем число 1, и т.д.
Таким образом, мы запустили волну. Когда она остановится, это означает, что получены все значения кластера.
Далее, следует выбрать случайно ту вершину, которая не попала в кластер, т.е. хранит 0. И запустить для нее волновой алгоритм, например, с числом 2. Проделав такую процедуру несколько раз, получим разбиение на кластеры.
В палитру следует положить центры получившихся кластеров.
Слайд 24

Результат работы алгоритма связности графа Приведенный метод хорошо выявляет кластеры точек

Результат работы алгоритма связности графа

Приведенный метод хорошо выявляет кластеры точек в

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

Иерархический метод Предположим, что в изображении n пикселей и каждый из

Иерархический метод

Предположим, что в изображении n пикселей и каждый из них образует свой

кластер. Свяжем с кластером величину, называемую центром тяжести кластера.
Для кластера, состоящего из одного значения, центром тяжести является само значение (в нашем случае, значение атрибута пикселя).
Построим матрицу расстояний D между кластерами.
В качестве расстояния берется, например, квадрат евклидовой метрики между центрами тяжести кластеров.
Затем выберем число T - порог и пару кластеров (i*, j*) так, чтобы (i*, j*) = arg min(i,j) dij (т.е, чтобы di*j* было минимальным в матрице).
Объединим кластеры, отвечающие i* и j*, положив центром тяжести нового кластера полусумму центров тяжести объединяемых кластеров.
Таким образом, получим n-1 кластеров. Для этих кластеров также построим матрицу расстояний D*и опять найдем пару, имеющую минимальное расстояние между центрами тяжести.
Заменим найденную пару одним кластером, вычислив его центр тяжести.
Следовательно, получим n - 2 кластеров и т.д.
Мы можем сделать максимум n - 1 итерацию.
В таком случае после последней итерации мы получим только один кластер. Чтобы получить K кластеров, нужно сделать n - K итераций.
Данный метод позволяет находить нетривиальные кластеры, однако время его работы очень велико, к тому же затруднена процедура обработки кластеров для большого объема входных данных.
Слайд 26

Обобщенный метод K-средних или метод динамических сгущений Данный метод является развитием

Обобщенный метод K-средних или метод динамических сгущений

Данный метод является развитием идей

метода K-средних и борется с его недостатками . В методе K-средних каждому кластеру соответствует определенное значение, его представитель.
В качестве представителя кластера выступает его центр, например среднее арифметическое элементов кластера.
В идеале, когда перемещения значений из одного кластера в другой отсутствуют, это соответствие - взаимнооднозначное.
Предположим, что представитель кластера - это не одиночное значение, а ядро, обладающее следующими свойствами:
по представителю можно идентифицировать кластер;
по кластеру вычисляется представитель.
Пример: представитель - два значения.
Данный представитель удовлетворяет первому свойству, т.к. можно корректно определить расстояние от объекта, состоящего из двух значений, до объекта из одного значения.
Второе свойство также выполняется, если применить простой алгоритм K-средних с K = 2, т.е. разбить кластер на два, а затем выбрать в качестве представителя исходного кластера центры получившихся двух подкластеров.
Другие примеры представителей: несколько значений, отрезки, разнообразные геометрические фигуры.
Далее обобщенный алгоритм повторяет стандартный алгоритм K-средних: сначала сформировать K кластеров по случайно выбранным ядрам, затем итерировать процесс формирования K новых ядер и пересчета кластеров до тех пор, пока количество перемещений не станет достаточно малым.
Слайд 27

Алгоритм рассеивания ошибок Флойда-Стейнберга Идея состоит в распределении (рассеивании) ошибки, возникшей

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

Идея состоит в распределении (рассеивании) ошибки, возникшей при

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

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

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

// проход по пикселям строго справа

налево, сверху вниз
// Threshold - порог, I(pixel) - атрибут пикселя
// pixel.right - пиксель справа, pixel.down - пиксель внизу
// pixel.down_right - пиксель справа внизу
// pixel.down_left - пиксель слева внизу
foreach( pixel in 8bit_picture )
//для каждого пикселя
{ if( I(pixel) > Threshold ) {
I(pixel) = Белый;
Error = I(pixel) - Белый; } else {
I(pixel) = Черный;
Error = I(pixel) - Черный; }
I(pixel.right)+= 7/16 * Error;
I(pixel.down_right)+= 1/16 * Error;
I(pixel.down)+= 5/16 * Error;
I(pixel.down_left)+= 3/16 * Error; }
Слайд 29

Результат работы алгоритма медианного сечения с применением алгоритма рассеивания ошибок Флойда-Стейнберга

Результат работы алгоритма медианного сечения с применением алгоритма рассеивания ошибок Флойда-Стейнберга

Необходимо

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