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

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

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

Линьков В.В.

The problems of raster images of modeling are considered in the article. Two groups of features are defined: histograms features and the features that reflect innomogenuity. They are of great importance at the evaluation of image compressibility.

Одной из важнейших задач при моделировании изображения является определение набора признаков.

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

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

, (1)

где 0 ? b ? L-1 - уровни квантования. Распределение частот первого порядка, оценивающее Р(b), описывается простым выражением:

P(b)?N(b)/N, (2)

где N - полное число элементов изображения, a N(b) - число элементов изображения, имеющих уровень b.

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

Среднее значение яркости:

(3)

Дисперсия:

(4)

Коэффициент асимметрии:

(5)

Коэффициент эксцесса:

(6)

Энергия:

(7)

Энтропия:

(8)

Гистограммные признаки второго порядка основаны на определении совместного распределения вероятностей пар элементов изображения:

Р(а,b)?Р{a(i,j) = a, а(т,п) = b}, (9)

где а и b - квантованные значения яркости.

Распределение частот, оценивающее распределения второго порядка, определяется формулой:

P(a, b) = N(a, b)/N, (10)

где N -- полное число элементов в изображении, a N(a,b} - число случаев, когда а(i,j)=а и а(т,п) = b.

Характеристиками гистограммы второго порядка являются:

Автокорреляция: (11)

Ковариация: (12)

Момент инерции: (13)

Средняя абсолютная разность: (14)

Энергия второго порядка: (15)

Энтропия второго порядка: (16)

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

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

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

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

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

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

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

Среди наиболее важных геометрических характеристик - длина периметра Р и площадь объекта. К топологическим характеристикам формы относится связность фигуры. Связные компоненты изображения могут содержать дыры. Количество дыр также не изменяется при топологическом отображении. Фундаментальное соотношение между количеством связных компонент С и числом дыр Н на фигуре, называемое числом Эйлера, имеет вид: Е = С-Н.

Число Эйлера - также топологическое свойство, поскольку С и H - топологические свойства.

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

Алгоритмы, реализующие МГУА, воспроизводят схему массовой селекции. В них есть генераторы усложняющихся из ряда в ряд комбинаций и пороговые самоотборы лучших из них. Полное описание объекта заменяется рядами частных описаний, как показано на рис. 1.

Различные алгоритмы МГУА отличаются друг от друга по виду функции. Известны алгоритмы с квадратичным и линейным полиномами, вероятностные алгоритмы МГУА, использующие формулы Байеса или теории статистических решений, и многие другие. В основном алгоритме МГУА используются квадратичные полиномы вида:

(x₁,x₂)=a₀+a₁x₁+a₂x₂+a₃x₁x₂+a₄x₁²+a₅x₂² (17)

Первый ряд селекции:

y₁=f(x₁,x₂), y₂=f(x₁,x₃), …,y_s=f(x_n-1,x_n), где s=C²_n

Второй ряд селекции:

z₁=f(y₁,y₂), z₂=f(y₁,y₃), …,z_p=f(y_s-1,y_s), где p=C²_s

и т. д.

Рисунок 1 - Многорядное описание модели

математическое моделирование растровое изображение

На следующий ряд селекции выбираются только наилучшие по некоторому внешнему критерию модели. В качестве внешнего критерия для открытия функциональной зависимости лучше всего подходит критерий минимума смещения. Для вычисления любого внешнего критерия выборка делится на две подвыборки: обучающую (Х_А, Y_A) и проверочную (Х_В, Y_B), объемом N_A и N_B соответственно. Очевидно, что N_A+N_B = N. Перед разбиением, согласно третьему способу регуляризации, точки располагаются в ряд по величине их дисперсии от среднего значения, и этот ряд делится на две указанные подвыборки. Обучающую подвыборку составляют точки с четными номерами, а проверочную - с нечетными. Критерий минимума смещения вычисляется по следующей формуле:

(18)

где - значение, рассчитанное по модели, построенной на основе данных обучающей подвыборки (Х_А, У_А);

-- значение, рассчитанное по модели, построенной на основе данных проверочной подвыборки (Х_B, Y_B);

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

(19)

Для оценки и отбора моделей целесообразно использовать комбинированный критерий:

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

Сложность модели, оцениваемая как наибольшая степень полинома на каждом ряду селекции.

Правило останова и выбора модели оптимальной сложности в этом случае основывается на анализе структуры отобранных моделей. Если в ряду в качестве оптимальной отобрана модель f(z₀)=O(0)+O(1)z₀, где О(0) обозначает число, близкое к 0, z₀ - модель из предыдущего ряда, которой соответствует наименьшее значение критерия, то модель z₀ - искомая модель оптимальной сложности.

Заключение

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

Литература

1. Линьков, В.В. Классификация алгоритмов сжатия изображений // Информационные системы и модели в научных исследованиях, промышленности и экологии [Текст]: Доклады III Всероссийской научно-технической конференции / В.В. Линьков под общ. ред. д-ра техн. наук, проф. В.М. Панарина - Тула: Изд-во ТулГУ, 2005. - С. 95-99.

2. Линьков, В.В. Методы оптимизации изображений в формате GIF // Информационные системы и модели в научных исследованиях, промышленности и экологии [Текст]: Доклады III Всероссийской научно-технической конференции / В.В. Линьков под общ. ред. д-ра техн. наук, проф. Панарина В.М. - Тула: Изд-во ТулГУ, 2005. - С. 99-103.

3. Линьков, В.В. Методы сжатия и передачи информации в цифровых системах видеонаблюдения [Текст] / В.В. Линьков - Тула: Изд-во ТулГУ // Линьков В.В., Панарин В.М, 2006. -140 с.

4. Ивахненко, А.Г. Моделирование сложных систем: Информационный подход [Текст] / А.Г. Ивахненко под общ. ред. Павлова В.В. - Киев: Вища.шк., 1987. 62 с.

5. Ватолин, Д. Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео [Текст] // Д. Ватолин, А. Ратушняк, М. Смирнов, В. Юкин / Диалог-МИФИ, 2002.

6. Ватолин, Д. Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео [Текст] / Д. Ватолин, А. Ратушняк, М. Смирнов, В. Юкин - М.: ДИАЛОГ - МИФИ, 2003. -384 с.

Размещено на Allbest.ru