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

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

1

29TMN215

1

29TMN215

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

Штанчаев Хайрутин Баширович

ОАО “Каспийский завод листового стекла”

Инженер АСУ ТП

ФГБОУ ВПО “Дагестанский государственный

технический университет”

Россия, Махачкала Аспирант

С математической точки зрения, изображение можно представить как вещественную функцию img двух переменных х и y, I(x,y).

Функция ?????? = ??(??, ??), в общем случае определяется в прямоугольной форме [4,5], но для удобства исследований в работе все изображения определяются квадратными областями, т.е. ?? ? [0; ??], а ?? ? [0; ??], где W - ширина изображения, H-высота изображения и W=H. Тогда говорят, что изображение имеет размер WxH. Значение, стоящее на пересечении x и y, называется пикселем. Не трудно заметить, что изображение схоже с прямоугольной системой координат. Можно отметить, что началом координат (0,0) применительно к изображению, нужно считать (x,y)=(1,1). Важно знать, что пара (x,y)=(1,2) относится ко второму пикселю.

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

где H- высота изображения, W- ширина изображения.

Особенностью такого представления цифрового изображения является то, что первый элемент в выражении (1) имеет координаты (x,y)=(0,0), а не (x,y)=(1,1) как указывалось выше[2].

Обобщенная графовая модель

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

?? = (??, ??), ?? = {??_??1}, E = {e_??2}, ??1 ? ?? ? ??, ??2 ? 1 … ??[1,3]

где: V - множество вершин графа;

E - множество ребер графа;

W - ширина изображения;

H - высота изображения.

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

???_??(??_??, ??_??) ? ??????, ?? = 1 … (?? ? ??), ?? = {?? ? ??_??(??_??, ??_??), ?? ? (??_??, ??_??+??)} (2)

где: x, y - координаты пикселя ??_??; ?? = 1 … ??, ?? = 1 … ??

Графически обобщенная модель для изображения img представлена на рисунке 1.

Рис. 1. Обобщенная графовая модель изображения A, B, C, D - стороны решетки графовой модели

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

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

Ново добавленная вершина заменяет старую если их координаты совпадают.

Ребра могут добавляться в любом количестве.

Введем основные определения графовой модели.

Определение 1. Восстановление изображения по графовой модели - получение изображения из графа представляя вершину графа как пиксель. Т.е. для некоторого графа G имеем: ???_??2(??, ??) ? ??, ?????? = ?????? ? ??_??2(??, ??).

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

Ограничение обозначается как R(x1,x2,x3,x4); x1 - глубина ограничения со стороны A, x2 -глубина ограничения со стороны B, x3 -глубина ограничения со стороны C, x4 - глубина ограничения со стороны D.

Ограничение означает удаление ??1строк для стороны A, x2 столбцов для стороны B, x3 строк для стороны C, x4 столбцов для стороны D:

Ограничение возможно и в определенном интервале, тогда из графовой модели удаляется область с определенной стороны. Ограничение на интервале :

.

где: N - наименование стороны; [o, q] - интервал вершин; m - глубина ограничения.

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

Наращивание графовой модели обозначается N(x1,x2,x3,x4) Редукция означает добавление x1 строк для стороны A, x2 столбцов для стороны B, x3 строк для стороны C, x4 столбцов для стороны D:

Следует отметить, что . Из этого следует, что записи и означают, что вершины из старой модели переносятся в новый со смещением на глубину наращивания:

где: k1, k2 - глубина наращивания.

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

Zone - название зоны - верхняя левая вершина

- верхняя правая вершина.

- нижняя левая вершина.

- нижняя правая вершина.

Зону с ограничением можно видеть на рисунке 2. Если G графовая модель, то ограниченная зона получается удалением вершин не входящих в указанный интервал. Так же можно получить зону ограничением. Но при ограничении получается “обрезанный” основной граф, а зона может иметь вид многоугольника. В этом случае зона имеет вид:

????????(??_??1, ??_??2, … , ??_????)

где: ??_???? - последняя вершина многоугольной зоны. Также и представляется зона которая состоит из цепи вершин выражается как:

????????{??₁ … . ??_??3}, получить ее можно из любой графовой модели

??_???????? = ??(??)/??_??4 если ???_??4 ? ?? ??_??4 ? ??_??3

Рис. 2. Зона в графовой модели. Слева зона с ограничением. Справа зона образованная цепью вершин

Цветная графовая модель

Определение 5. Цвет вершины графа (z) - цвет в который окрашена вершина исходя из цвета пикселя составившей эту вершину. Цвет z исходя из поставленный задачи можно выразить численно как в цветовой системе RGB (например черный - 000000) или лингвистически (черный цвет или black). Если окрасить все вершины графа G в соответствующий цвет Z получим цветную графовую модель. Тогда вместо графа G имеем тройку:

??_?????????? = (??, ??, ??), ?? = {??_??3}, E = {e_??4}, ?? = {??_??5}, ??3 = ??5 ? ?? ? ??, ??4 ? 1 … ?? где:

V - множество вершин графа;

E - множество ребер графа;

W - ширина изображения;

H - высота изображения;

Z - множество цветов вершин графа.

Например на рисунке 3 показан цветной граф у которого первые и последние вершины черного цвета.

Рис. 3. Цветная графовая модель изображения Для составления такого графа перепишем 2: ???_??(??, ??) ? ??????, ?? = 1 … (?? ? ??)

??_?????????? = {?? ? ??_??(??, ??), ?? ? (??_??, ??_??+??), ?? ? ??(??_??(??, ??)}(2.3)

где: x,y -координаты пикселя ??_??;

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

Определение 6. Сегментация графа - разделение графа на ?? подграфов по цветовому признаку. Цветовой признак зависит от поставленной задачи. Восстановив изображение по сегментированному графу можно получить сегментированное изображение.

Обозначим цветовой признак как P. Опишем сегментацию графа Gcolor как удаление вершины ??_??6 с цветом z(??_??6) который не равен P, т.е.:

???_??6, если ??(??_??6) ? ??,

??(??????????) = ??(????????????)\{????6} , ??(??????????) = ??(????????????)\{(????6, ????6+1)|????6 ? ??(????????????)}

Например если сегментировать граф показанный на рисунке 3 по черному цвету, мы получим граф представленный на рисунке 4

Рис. 4. Цветной граф после сегментации

Для восстановления цветного графа имеем:

???_??3(??, ??) ? ??, ?????? = {?????? ? ??_??3, ??????????(??_??3) = ??_??3}

Где запись color означает установку цвета пикселя в указанный.

Раздельная графовая модель

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

???????????? = {????}, т.е. ???? ? ????????????

Разделение суперграфа ??_?????????? на подграфы по столбцам:

??_?? = ??(??_??????????)\??(??, ??₉), ??(??_??) = ??(??_??????????)\{(??, ??)|?? ? ??(??_??)}, ??₉ = 1 … ??.

Разделение суперграфа ??_?????????? на подграфы по строкам:

??_?? = ??(??_??????????)\??(??₁₀, ??), ??(??_??) = ??(??_??????????)\{(??, ??)|?? ? ??(??_??)}, ??₁₀ = 1 … ??.

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

??????(??₁) = 1, ??????(??_??) = 1, ??????(??_?? … . ??_???1) = 2.

Также стоит обратить внимание на то, то раздельная графовая модель может быть выстроена как для обобщенного графа так и для цветного и сегментированного графов.

Раздельная модель для столбцов суперграфа 2 графически показана на следующем рисунке.

Рис. 5. Раздельная графовая модель для обобщенного суперграфа по столбцам

А раздельная модель для графа 5 по строкам выглядит так:

Рис. 6. Раздельная графовая модель для цветного суперграфа по строкам

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

Описанная в статье математическая модель, основанная на графах, является достаточной и качественной заменой классической модели представления изображения. Такая модель хорошо подходит для представления, фильтрации и сегментации изображения в современных системах распознавания образов[6]. Одно изображение можно представить в разных графовых моделях в зависимости от поставленной задачи. Математический аппарат модели является гибким и встраиваемым в любую систему по необходимости. Графовая модель позволяет сократить вычисления связанные с манипуляциями с каждым пикселем.

Литература

изображение распознавание образ пиксель

1. Асанов М.О. Дискретная математика: графы, матроиды, алгоритмы: учебное пособие / М.О. Асанов, В.А. Баранский, В.В. Расин. - СПб.: Лань, 2010.

2. Брусенцов В., Поляков А. Методы и алгоритмы компьютерной графики в примерах на Visual C++ - БХВ-Петербург,2012.-544 c.

3. Мельников О.И. Теория графов в занимательных задачах. Изд. 3, испр. и доп.2009. 232 с.

4. Методы компьютерной обработки изображений / под. ред. В.А. Сойфера-М.: ФИЗМАТЛИТ, 2003. -784 с.

5. Тропченко А.Ю., Тропченко А.А. Методы сжатия изображений, аудио сигналов и видео: Учебное пособие - СПб: СПбГУ ИТМО, 2009. - 108 с.

6. Штанчаев Х.Б. Применение графовой модели и априорного классификатора для сегментации изображения в задачах распознавания лица человека // Интернетжурнал «НАУКОВЕДЕНИЕ» Том 7, № 2 (2015) http://naukovedenie.ru/PDF/130TVN215.pdf (доступ свободный). Загл. с экрана. Яз. рус., англ. DOI: 10.15862/130TVN215.

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