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

12.1. Введение

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

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

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

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

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

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

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

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

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.2) в изображении часто возникают слишком четкие границы, а детали, наоборот, стираются. Однако основные достоинства данного алгоритма - простота и высокая скорость.

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

Идея алгоритма

Идея алгоритма состоит в построении палитры, состоящей из N самых часто встречающихся значений атрибутов в исходном изображении. Для этого нужно построить гистограмму значений атрибутов, затем взять N самых часто встречающихся и провести собственно квантование [35]. Соответственно, возникает вопрос: что делать с теми значениями, которые не уместились в палитру? Естественно заменить лишние значения самыми близкими аналогами из тех, что попали в палитру. Близость понимается как квадрат евклидова расстояния, т.е. в пространстве RGB

dist(C1,C2) = (R1 - R2)2 + (G1 - G2)2 + (B1 - B2)2,

где C1, C2 - значения атрибутов (см. лекцию 1).

Задача поиска ближайшего значения в таблице может быть решена несколькими способами. Самый простой: для каждого значения, не представленного в таблице, перебрать расстояния до всех имеющихся в таблице элементов и выбрать элемент с минимальным расстоянием. Однако такой метод очень трудоемок и потому не используется на практике. Вообще, задача поиска в n -мерном пространстве точки из некоторого набора, ближайшей к данной, является одной из классических задач вычислительной геометрии (см., например, [7], [23]). Здесь мы приведем одно из часто используемых решений, менее трудоемкое.

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

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

(рис 12.2) Результат работы алгоритма разбиения по частоте вхождения.(рис 12.3) Предварительные вычисления для локально отсортированного поиска// 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 ) } );
}

// 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;
            }
      }
}

Найденное расстояние полагается порогом, при превышении которого очередное значение из палитры не добавляется в список. Следует отметить, что не требуется обрабатывать кубики, состоящие из тех значений, которые не принадлежат исходному изображению. Выбор числа K является отдельным и достаточно сложным вопросом. Чем оно больше, тем больше требуется времени для предварительных вычислений, но тем меньше требуется времени на поиск ближайшего значения при квантовании. Соответственно, нужен некий компромисс. Общая рекомендация такова: выбирать $$$K = \frac{M}{32} \ldots \frac{M}{20}$$$, где M - число значений атрибутов вдоль каждой из основных цветовых осей. Приведенный алгоритм называют локально отсортированным поиском (предварительные вычисления - см. алгоритм 12.2, процесс квантования - см. алгоритм 12.3.

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

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

Построим алгоритм, который сформирует палитру так, чтобы каждое значение из нее отвечало равному количеству значений атрибутов пикселей в исходном изображении. Это достигается путем последовательного разбиения цветового пространства на параллелепипеды со сторонами, параллельными осям цветового пространства RGB [35].

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

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

// 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;
      }
}

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 равно желаемому размеру палитры.

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

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

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

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

Часто реализации алгоритма используют специальные структуры для хранения разбиения цветового пространства. Примером такой структуры может служить BSP дерево (подробнее см. [23]).

Результаты работы алгоритма являются очень хорошими (см. рис. 12.4); при этом скорость работы данного алгоритма высока. Различные вариации данного алгоритма используются в известных приложениях для обработки изображений, например в GNU ImageManipulation Program (GIMP).

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

В данном разделе будут рассмотрены методы, производящие кластеризацию значений атрибутов изображения для дальнейшего построения палитры. В общем случае кластеризация - это процесс разбиения объектов на группы (кластеры) на основе свойств, описывающих сущность объектов [38]. В применении к квантованию изображений это означает процесс разбиения значений атрибутов на группы (кластеры) так, что внутри каждой группы находятся лишь близкие значения.

Метод 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;
      // пересчитываем центры кластеров
      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;
}

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

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