Обработка цветов и кодирование подмножеств

Алгоритм кодирования выполняется в два прохода:

1. Первый проход. Анализ изображения, обработка цветов.

a. Выделение цветов.

b. Интеллектуальное прореживание, устранение неразличимых оттенков.

c. Определение количества подмножеств – N.

2. Второй проход. Кодирование.

a. Представление двумерных множеств, как одномерные.

b. Определение принадлежности пикселя к соответствующему подмножеству.

c. Послойное кодирование подмножеств с учетом анализа очередного пикселя, для экономии объема.

d. Запись в файл блоков кода переменной длины.

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

Исходя из вышесказанного, мы получаем незакодированное изображение, описываемое как набор подмножеств, описывающих форму объектов:

где:

здесь это не измененное множество, то есть это те цвета, которые мы видим на изображении, та же точно форма и эти множества друг от друга независимы.

На рис.2 отражены 4 представления набора пикселей(сверху вниз): привычное представление в цвете; срез поверхности точек в 3-D пространстве  (по функции top-surface) [5]; срез объемной фигуры, отражающей структуру изображения(функция Umbra) [5]; собственный способ представления , повышающий эффективность кодирования. Измененные множества отмечаются как  и работать с ними можно также, как и с любыми другими множествами, но они зависят от других слоев, которые должны прорисовываться сверху, поскольку суть представления в том, что если одни цветовые слои включают в себя другие, то нет необходимости запоминать несущественные элементы в более низших слоях, которые в дальнейшем будут затерты более высшими. Таким образом, достигается дополнительное сжатие, отраженное в разнице между последними двумя представлениями. То есть отличие слоя от слоя в пропущенных, сэкономленных пикселях будет нивелировано слоем , который впоследствии затрет несущественную разницу.

Рис.2. Разбиение изображения на цветовые слои, срез 3D поверхности

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

С учетом вышеуказанных требований была предложена структура кодировки (Рис.3). Где Блоки «0:0, 0:1 и т.д.» – это количество чередующихся сгруппированных заполненных либо пустых пикселей, по принципу «есть цвет – нет цвета».

Объем данных каждого элемента структуры:

Рис.3. Структура кодировки

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

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