Вас вітає Наукова спільнота!

Вітаємо на нашому сайті

КОМПЛЕКСИРОВАНИЕ И АНАЛИЗ МЕТОДОВ СЖАТИЯ ИЗОБРАЖЕНИЙ

03.09.2021 20:03

[1. Інформаційні системи і технології]

Автор: Иванов В.Г., доктор техн. наук, профессор, кафедра криминалистики, Национальный юридический университет им. Я. Мудрого, г. Харьков


Сжатие данных является важнейшей перманентной составляющей практически всех современных мультимедийных архитектур и сетевых информационных технологий, и в настоящее время может рассматриваться как “технология расширения возможностей” [1]. Однако, несмотря на существенные достижения в области сжатия изображений, становится очевидным тот факт, что методы, разработанные в рамках классической теории информации и теории сигналов приближаются к свойственному им пределу эффективности кодирования изображений и поэтому остается все меньше возможностей увеличения степени сжатия информации, рост которой, как известно, подчиняется экспоненциальному закону [2]. Поэтому весьма перспективным и многообещающим направлением видится подход на основе объединения и комлексирования методов обработки сигналов изображений и методов распознаваня образов на основе автоматической и нечеткой классификации данных [3, 4].

Метод автоматической классификации базируется на алгоритме k- средних. Для сжатия изображений алгоритм k-средних используется следующим образом. Изображение разбивается на одинаковые, например, квадратные элементы с размером стороны m пикселей. Яркости пикселей каждого элемента составляют  m2-мерный вектор. К совокупности всех элементов применяется алгоритм k-средних, что приводит к разбиению изображения на k, как правило, несвязных областей S1,...,Sk, каждая из которых состоит из почти одинаковых элементов. Для кодирования изображения нужно составить карту регионов, определяющую размещение областей, и для каждой области Sj указать ее представителя, в качестве которого используется ее центр. Отметим, что в данной работе этот алгоритм был дополнен предварительным «просеиванием» элементов [5]. Эта процедура состоит в том, что, задавшись параметром Δ>0 и произвольным элементом x1 из совокупности векторов X, объединяют в один класс X1 все элементы множества, находящиеся от x1 на расстоянии меньшем, чем Δ, то есть удовлетворяющие неравенству




Далее произвольно выбирается элемент x2, не принадлежащий классу X1, и аналогичным образом строится класс X2. Процесс заканчивается, когда каждый элемент из X попадет в какой-либо класс.

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




где Mj – число элементов в классе Xj, j=1,2,...,m, и m=m(Δ) – число получившихся классов.

Предварительное определение центров класса (в нулевом приближении) с помощью метода просеивания увеличивает вероятность того, что алгоритм k-средних даст абсолютный, а не локальный минимум функционала F(S). Кроме того предварительное применение метода просеивания значительно улучшает сходимость алгоритма k-средних и, следовательно, сокращает вычислительное время. Это объясняется тем, что уже на первом шаге центры нулевого приближения аппроксимируют члены своего класса с точностью, не меньшей значения параметра Δ. Еще одним преимуществом предложенной предобработки является то, что метод просеивания позволяет автоматически определить необходимое число классов, дающее приемлемое значение внутриклассовых дисперсий. Действительно, чем выше степень разнородности векторов из X, тем больше необходимо классов для того, чтобы внутриклассовые разбросы не превосходили заданной величины. Количество классов регулируется величиной параметра Δ, который можно уменьшить или увеличить в зависимости от величины, например, средней внутриклассовой дисперсии.

В более совершенном варианте алгоритма сжатия к каждому квадратному элементу изображения пред классификацией применяется декоррелирующее преобразование–дискретное косинусное преобразование Фурье или преобразование Хаара. Далее в качестве пространства признаков используется то или иное число коэффициентов, полученных при одном из этих преобразований. На рис.1 представлены восстановленное изображение zelda.bmp при m=4 и k=80, а также распределение количества элементов по классам. Зависимость коэффициента сжатия от СКО при этих же параметрах приведена на рис.2. Здесь же для сравнения приведена аналогичная зависимость для сжатия стандартным методом JPEG.




Не слишком высокая степень сжатия с помощью метода автоматической классификации в области малых СКО объясняется тем, что для получения высокого качества восстановленного изображения требуется большое число классов. Попытка уменьшить это число с помощью применения больших фрагментов, например, 10x10 приводит к тому, что в каждом классе оказывается слишком мало элементов – практически 1 – 2, так что классификация становится бессмысленной. То же можно сказать и в случае применения самых малых однопиксельных фрагментов 1x1. В этом случае классификация сводится просто к квантованию яркостей пикселей.

Зависимости коэффициента сжатия от СКО для фрагментов различных размеров приведены на рис. 3. Из приведенных графиков вытекает, что для кодирования с высоким качеством (область малых СКО) нужно пользоваться фрагментами 2x2 и 4x4, причем второе является предпочтительней, так как дает лучшее сжатие и в областях с высоким СКО. 




Нечеткой классификацией множества X p-мерных векторов по k классам S=(S1,...,Sk) понимается сопоставление каждому элементу x из X набора k неотрицательных чисел (a1(x),a2(x),...,ak(x)), в сумме составляющих 1. Эти числа называются коэффициентами принадлежности классу и могут трактоваться как вероятности того, что данный элемент принадлежит тому или иному классу. Задача нечеткой классификации состоит в нахождении минимума суммы взвешенных дисперсий нечетких множеств S, то есть функционала




где (e1,...,ek) – набор центров нечетких множеств, а символ ||v|| означает, как и выше, длину вектора v из X.

Алгоритм C-средних, позволяющий решить эту задачу, состоит в следующем.

Параметром классификации является число классов k. Из множества X произвольно выбирается k векторов e1,...,ek, которые рассматриваются как центры классов в первом приближении. После чего строится нечеткое разбиение множества X на классы, порождаемое этими центрами. То есть для каждого вектора x вычисляются коэффициенты принадлежности:




Заметим, что коэффициент aj(x) принадлежности вектора x классу Sj тем больше, чем ближе центр ej этого класса к этому вектору.

После этого для каждого построенного класса находятся центры второго приближения как средневзвешенные средние:




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

Список литературы:

1. Сэломон Д. Сжатие данных, изображений и звука / Д. Сэломон – М.: Техносфера, 2004. – 368 с.

2. Гонсалес Р.. Цифровая обработка изображений/ Р. Гонсалес, Р. Вудс.-Москва: Техносфера, 2012.-1104с.

3. Журавлев Ю.И., Гуревич И.Б. Распознавание образов и распознавание изображений // Распознавание, классификация, прогноз. Математические методы и их применение: Ежегодник / Под ред. Ю.И. Журавлева. – М.: Наука, 1989. – Вып. 2. – С. 5-72.

4. ИвановВ.Г. Сжатие изображений на основе автоматической и нечеткой классификации фрагментов/ В.Г. Иванов, Ю.В. Ломоносов, М.Г. Любарский, //  Проблемы управления и информатики. –2009. –№ 1. – С.52-63.

6. Прикладная статистика: Классификация и снижение размерности: [Справочник] / С.А. Айвазян, В.М. Бухштабер, И.С. Енюков и др.; Под ред. С.А. Айвазяна. – М.: Финансы и статистика, 1989. – 607 с.



допомога Знайшли помилку? Виділіть помилковий текст мишкою і натисніть Ctrl + Enter
Конференції

Конференції 2021