К. т. н. Загребнюк В. И., Насиров Ф. В.

Одесская национальная академия связи имени А. С. Попова, Украина

МАТЕМАТИЧЕСКАЯ МОДЕЛЬ ВЫДЕЛЕНИЯ ГРАНИЦ НА ЦВЕТНЫХ ЦИФРОВЫХ ИЗОБРАЖЕНИЯХ

 

В технологии контекстного поиска изображений по регионам (RBIR – Region-based image retrieval ) точность и полнота поиска определяется эффективностью методов выделения объектов (регионов) на изображении. Широкий класс методов выделения объектов основывается на выделении границ регионов на изображениях в градациях серого [1 – 3]. Однако не все методы преобразования цветных изображений в градации серого, сохраняют цветовые контрасты [4], а их потеря сопровождается искажениями контуров, поэтому объекты выделяются на цветных изображениях с использованием текстурно-цветовых методов выделения регионов [5 – 7]. Во всех этих методах дескрипторы – это многомерные векторы, что существенно усложняет, как индексирование, так и поиск изображений по регионам. Таким образом, проблема разработки методов выделения регионов на изображениях со сложным цветовым и пространственным контекстом, которые минимизируют количество признаков в дескрипторе – актуальна. Одно из возможных решений этой проблемы заключается в представлении связного региона его контуром и усредненным значением цвета. Для эффективного определения контура связного региона необходимо разработать математическую модель, позволяющую выделять границы между регионами на цветных цифровых изображениях, что и является целью данной работы.

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

,    

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

,  

где ;

; .

Вычислим собственный и факторный векторы, соответствующие максимальному собственному значению. Собственный вектор   будет иметь компоненты:

;

 

Факторный вектор будет иметь следующую структуру . Нулевая матрица-строка   размерности . Матрица   размерности , будет иметь вид:

,  

а   размерности , будет иметь следующие элементы:

, .

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

.

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

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

Векторизуем матрицу с использованием схемы «Зигзаг» [8]. Тогда получим матрицу строку вида , где   – матрица строка размерности   с нулевыми элементами, а   – матрица строка размерности   с элементами равными . Пусть матрица   имеет   нулевых диагоналей. Если , то , иначе , а . Как и в предыдущих случаях, для окна размером , блочная матрица вложения будет иметь вид . Блочная матрица состоит из следующих блоков:   – нулевая прямоугольная матрица размерности ;   – квадратная матрица размерности , у которой все элементы расположенные выше побочной диагонали равняются нулю, а расположенные на побочной диагонали и ниже нее равняются . У прямоугольной матрицы   размерности   все элементы равны . Для данного случая вычисление собственных и факторных векторов, в общем виде, очень громоздкое, поэтому рассмотрим числовые примеры для   и   при .

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

В этом случае матрица   будет иметь вид:

.

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

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

Рис. 1 . Факторный вектор, соответствующий максимальному собственному значению

 

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

.

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

.

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

 

Список использованных источников:

1. Hiremath P. S. Content Based Image Retrieval based on Color, Texture and Shape features using Image and its complement / P. S. Hiremath , J. Pujari // International Journal of Computer Science and Security, 2007. - V . 1, № 4. - P . 25 - 35.

2. Deshpande A. Design Approach for Content-Based Image Retrieval Using Gabor-Zernike Features / A. Deshpande , S. K. Tadse // International Archive of Applied Sciences and Technology, 2012. - V . 3, № 2. - P . 42 - 46.

3. Chaudhari R. Content Based Image Retrieval Using Color and Shape Features / R. Chaudhari , A. M. Patil // International Journal of Advanced Research in Electrical, Electronics and Instrumentation Engineering, 2012. - V . 1, № 5. - P . 386 - 392.

4. Cadík M. Perceptual Evaluation of Color-to-Grayscale Image Conversions / M. Cadík // Pacific Graphics, 2008. – V. 27 .– P . 128 - 138.

5. Carson C. Blobworld : A system for region-based image indexing and retrieval / C. Carson, M. Thomas, S. Belongie , J. M. Hellerstein , J. Malik // Visual Information and Information Systems. Lecture Notes in Computer Science , 1999. – V .1614 .– P . 509 - 517.

6. Natsev A. WALRUS: A similarity retrieval algorithm for image databases / A. Natsev , R. Rastogi , K. Shim // Newsletter ACM SIGMOD Record, 1999. – V. 28, № 2. – P. 395–406.

7.   Bartolini I. The Windsurf Library for the Efficient Retrieval of Multimedia Hierarchical Data / I. Bartolini , M. Patella, G. Stromei // Proceedings of the International Conference on Signal Processing and Multimedia Applications, 2011. - №1 - P . 139 - 148.

8. ISO/IEC 10918-1:1994 Information technology - Digital compression and coding of continuous-tone still images: Requirements and guidelines. – ISO/IEC, 1994. – 186 p.