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

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

 

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

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

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

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

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

применительно к тоновой аппроксимации монохромных мультитоновых изображений существует возможность использовать другие подходы, более точные, нежели метод k-средних.

Для реализации оптимальной тоновой аппроксимации изображений известен способ использования алгоритма кластеризации k-средних для реализации тоновой аппроксимации (Llyod S. Least squares quantization. IEEE Trans. Vol. 28. Pp. 129-137. 1982.). Целью данного алгоритма является минимизация суммарного квадратичного отклонения внутри кластерных элементов от цента своего кластера, называемого центроидом. Входными данными для алгоритма являются стартовые значения центроидов, после чего формируются соответствующие центроидам кластеры наиболее близких к ним элементов. В пределах каждого из кластеров вычисляется центр масс, который в итоге назначается новым центроидом и осуществляет переформирование границ кластеров в соответствии с новым значением центроида. Данная процедура повторяется до тех пор пока значения центроидов изменяются.

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

Известен способ НейроКвант, который предполагает оптимизацию тоновой аппроксимации изображений на основе использования самоорганизующейся нейронной сети Кохонена, которая применяется в задачах кластеризации. Способ НейроКвант обеспечивает высокое качество тоновой аппроксимации, но одновременно с этим требует серьезный временной ресурс на этапе обучения нейронной сети, что фактически исключает возможность использования данного алгоритма в ряде практических задач (Dekker A. Kohonen neural networks for optimal color quantization. Network Computation in Neural Systems. Vol 5. Pp. 351-367. 2009.).

Наиболее близкими к предлагаемому изобретению являются способ, описанный в работе P. Scheunders «A Genetic C-Means Clustering Algorithm Applied To Color Image Quantization», подразумевающий гибридное использование простого генетического алгоритма Голдберга и обобщенного алгоритма кластеризации k-средних. Гибридизация предполагает смешенную схему взаимодействия двух алгоритмов и заключается в следующих шагах:

1. гибридный алгоритм случайным образом генерирует популяцию (множество) особей (альтернативных решений);

2. сгенерированные альтернативны поочередно обрабатываются алгоритмом k-средних, после чего к полученным решениям применяются генетические операторы;

3. этот процесс повторяется заданное количество поколений.

К недостаткам данного способа можно отнести:

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

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

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

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

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

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

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

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

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

при этом на начальном этапе аппроксимации

выбор подмножеств тонов, упорядоченных по возрастанию их целочисленных кодов, осуществляется так, что их объединение образует полное исходное множество тонов, а пересечения соседних по возрастанию кодов подмножеств тонов дают пустые множества;

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

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

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

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

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

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

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

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

критериальная оценка стартового аппроксимирующего вектора сравнивается с вычисленной аналогично критериальной оценкой каждого из комбинаторно сформированных векторов тоновых кодов, рассматриваемых, как варианты тонов аппроксимирующих векторов, и полученные оценки сравниваются на условия «хуже, одинаково, лучше», и, если ни один из комбинаторных вариантов не обеспечивает оценки, лучшей, чем оценка второго стартового варианта аппроксимирующих тонов, то второй стартовый вариант объявляется экстремумом (финишным вектором);

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

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

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

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

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

Сущность изобретения поясняется чертежом, где на

фиг. 1 приведено исходное цифровое изображение;

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

фиг.3 - построение интегральной диаграммы яркости изображения;

фиг. 4 – таблица формирования координат ближайшей окрестности нового стартового вектора.

Способ осуществляется следующим образом:

Для исходного цифрового монохромного изображения (фиг. 1), подлежащего воздействию процедуры тоновой аппроксимации, выбирается количество аппроксимирующих тонов, выделяемых для формирования аппроксимированной версии исходного изображения, и выполняется построение его интегральной диаграммы яркости (см. фиг. 3), где по оси абсцисс отложены исходные тона, а по оси ординат количество пикселей (приведено к диапазону от 0 до 1), после чего вычисляется первая стартовая совокупность аппроксимирующих тонов обработкой кривой интегральной диаграммы. Эти первые стартовые значения аппроксимирующих тонов выбираются как округленные до ближайшего целого абсциссы, образованные пересечением кривой интегральной диаграммы яркости тонов изображения ее ординатами, которые получены путем деления оси ординат от нуля до полного количества пикселей в исходном изображении на удвоенное количество тонов в их множестве, выбранном для аппроксимации. Каждая нечётная абсцисса, округленная до ближайшего целого, назначается кодовым значением аппроксимирующего тона, а каждая чётная абсцисса назначается максимальным кодом первого стартового подмножества, включающего аппроксимирующий тон подмножества аппроксимируемых тонов. На интегральной диаграмме (фиг. 3) синими линиями отмечены максимальные коды подмножества, а красными линиями - соответствующие коды аппроксимирующих тонов.

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

,

где - первая стартовая аппроксимирующая совокупность тонов, а максимальные тона подмножеств тонов, заменяемых этими аппроксимирующими тонами будет задана также вектором размерности 8:

,

где индекс b указывает на принадлежность элементов верхней границе подмножеств, - максимальный код тона исходного изображения. Таким образом, например, первым аппроксимирующим тоном «8» будут заменены исходные тона от 0 до 14 включительно.

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

В настоящем примере используется средний модуль отклонения:

,

где - пиксель аппроксимированного изображения, - пиксель оригинального изображения, а – общее число пикселей цифрового изображения.

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

Для рассматриваемого примера была найдена новая стартовая (субоптимальная) совокупность (вектор) следующего вида:

,

где - вторая стартовая аппроксимирующая совокупность тонов, найденная подходящим поисковым алгоритмом. Вторая стартовая аппроксимирующая палитра отличается от первой не только всеми элементами (аппроксимирующими тонами), но и значительно лучшим значением критерия оценки качества тоновой аппроксимации: 6,69 против 7,073.

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

Здесь средняя строка – новый стартовый вектор, полученный поисковым алгоритмом для отыскания его экстремальной структуры. Верхняя строка составлена из элементов средней, уменьшенных на 1, а нижняя – из тех же элементов, увеличенных на 1. В результате получены столбцы троек значений возрастающих на 1 тон. Из элементов этих троек, рассматриваемых по возрастанию, формируются все возможные варианты векторов аппроксимирующих тонов окрестности стартового вектора (средней строки), которые исследуются на условия «хуже, одинаково, лучше» выбранным изначально критерием.

Логико-комбинаторный анализ решаемой задачи показывает, что для изображений различной тоновой структуры возможны 3 кардинально различающихся ситуации:

• критериальные оценки всех векторов окрестности отвечают условию «хуже», т.е. стартовая совокупность экстремальна и является оптимумом для решаемой задачи;

• часть из критериальных оценок отвечают условию «лучше», тогда наилучшие из них (или одна, если оптимум единственный) снова исследуются на экстремум описанной последовательностью действий;

• часть из критериальных оценок векторов окрестности отвечают условию «одинаково», а остальные оценки отвечают условию «хуже», тогда на экстремум исследуются векторы, равнозначные стартовому.

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

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

,

где - найденный предложенным способом экстремум аппроксимирующей палитры улучшен до 6,674 относительно оценки 6,69, найденной на этапе варьирования тонов первой стартовой аппроксимирующей совокупности для улучшения качества аппроксимации.

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

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

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

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

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

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

при этом на начальном этапе аппроксимации

выбор подмножеств тонов, упорядоченных по возрастанию их целочисленных кодов, осуществляется так, что их объединение образует полное исходное множество тонов, а пересечения соседних по возрастанию кодов подмножеств тонов дают пустые множества;

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

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

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

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

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

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

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

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

критериальная оценка второго стартового аппроксимирующего вектора сравнивается с вычисленной аналогично критериальной оценкой каждого из комбинаторно сформированных векторов тоновых кодов, рассматриваемых как варианты тонов аппроксимирующих векторов, и полученные оценки сравниваются на условия «хуже, одинаково, лучше», и, если ни один из комбинаторных вариантов не обеспечивает оценки, лучшей, чем оценка второго стартового варианта аппроксимирующих тонов, то второй стартовый вариант объявляется экстремумом (финишным вектором);

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

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

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