Обработка и передача изображений

THE AUTOMATED FEATURE EXTRACTION SYSTEM BASED ON THE CHARACTERISTIC SEQUENCES FOR TIME SERIES AND GRAYSCALE IMAGE CLASSIFICATION

Gorshkov A., Gryzlova T.

Rybinsk State Academy of Aviation Technology

Introduction

Wide set of recognition time series tasks can be solved with pattern recognition technique, based on the statistics of characteristic sequences, that were realized in automatic system feature extraction. It is a computer-aided flexible feature extraction system based on the characteristic sequences of the digital signals. A characteristic sequence of the digital signals is a cluster of its subsequences. Our approach allows to find feature spaces for time series and for grayscale images.

The method

The automated approach to feature extraction is based upon three things: a new type of features, an algorithm of building of the base features set and an algorithm of finding of the feature space as subset of the base features set. The new feature description includes an etalon sequence (), a distance function , a threshold value of the distance and an algorithm of sequences enumeration . Value of the feature is the frequency of the signal sequences x enumerated by for which the following statement is right: .

The algorithm of building of the base features set includes three stages. The result of sequences clustering stage is the etalon sequences set. The distance thresh adjustment stage allows to raise informativeness of the features. The third stage is features pair correlations deleting.

The algorithm of the feature space finding includes two stages: deleting low informative features and finding feature space on the base of random search with adaptation.

Results

We test our method on the six problems. The method gave the possibilities to find more effective pattern spaces than Zeus system, than the dynamic time warping based systems, than the system based on the generalized feature extraction for structural pattern recognition and than the sparse part-based representation of images. Three of these problems are known as: «Gun-point», «Trace» and «Wafer» [1 - 3]. They are a short length time series classification problems. Two other problems are grayscale image classification problems: classification image fragments with cars for car image detection [4] and classification image fragments with forest on aerial images. Last problem is the transmission bearing fault diagnostics of gas turbine engine based on registration of the vibration [5].

References

1. 
   Eads D., Glocer K., Perkins S., Theiler J. Grammar-guided feature extraction for time series classification. Neural Information Processing Systems, 2005.
   
2. 
   Olszewski R. T. Generalized Feature Extraction for Structural Pattern Recognition in Time-Series Data. PhD thesis, Carnegie Mellon University, Pittsburgh, PA, 2001.
   
3. 
   Ratanamahatana C. A., Keogh E. Everything you know about dynamic time warping is wrong. In 10th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining Workshop on Temporal Data Mining, 2004.
   
4. 
   Agrawal S., Roth D., Awan A. Learning to Detect Objects in Images via a Sparse, Part-Based Representation. IEEE Transactions of pattern analysis and machine intelligence, vol. 26, No. 11, November 2004.
   
5. 
   Gorshkov A., Gryzlova T., Komarov B, Shepel V. Transmission bearing state diagnostics in statistics areas of vibrations typical sequences // Aerospace technic and technology. – 2006. - № 10. – p. 152-156.
   



Распознавание двумерных образов на основе инвариантных к поворотам моментов

Смоляков А.В, Кандрин А.Е., Скопинцев Я.М.

Ярославский государственный университет им. П.Г. Демидова
150000, Россия, Ярославль, ул. Советская, 14, Тел. (4852) 79-77-75. E-mail: [email protected]

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

Процесс распознавания объекта на изображении можно формально разделить на основные этапы:

1) поиск искомого объекта;

2) нахождение признаков данного объекта;

3) классификация.

			
Рис. 1. Исходные тестовые изображения

В данной статье рассматривается метод распознавания образов на двумерных изображениях на основе вычисления признаков, в качестве которых выступают инвариантные к поворотам моменты [1]. Данный метод отличается относительной простотой вычислений. Суть метода заключается в нахождении моментов n-го порядка изображений объектов. Необходимо отобрать такие моменты, которые имеют определённые значения, отличные друг от друга для всех объектов отдельного класса. Вычислив эти моменты, можно будет с определенной вероятностью говорить о наличии искомого объекта на изображении и принадлежности его к какому-либо виду. Для корректной работы алгоритма образы на изображении не должны перекрываться. На рис. 1 представлены примеры тестовых изображений.

					
а)
б)
в)
Рис. 2. Этап предобработки: а) выделение краев; б) пороговая фильтрация; в) поиск односвязных областей

Процедуру предварительной обработки входных изображений можно представить в виде последовательности операций:

1. 
   выравнивание интенсивности;
   
2. 
   выделение краев с использованием пороговой фильтрации;
   
3. 
   поиск односвязных областей;
   
4. 
   масштабирование.
   

Рассмотрим подробнее каждую стадию обработки.

1. Выравнивание интенсивности

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

2. Выделение краев

Для этой цели используется двумерное вейвлет-преобразование входных изображений, в результате чего получается четыре набора коэффициентов [2, 3]. На изображении края представляют собой резкие перепады интенсивности, поэтому информация о них содержится в высокочастотной области; т.е. берется высокочастотный набор коэффициентов вейвлет-преобразования, где свертка происходит с импульсными характеристиками фильтров верхних частот по строкам и по столбцам (на рис. 2а представлены восстановленные изображения только по высокочастотным коэффициентам без пороговой фильтрации). Далее эта матрица вейвлет-коэффициентов подвергается пороговой фильтрации, целью которой является отсеивание тех элементов, которые в последствии могут образовывать ложные контура на получаемом изображении. После фильтрации производится восстановление изображения только по этой матрице вейвлет-коэффициентов, на котором остаются только очертания нужных нам объектов (рис. 2б).

3. Поиск односвязных областей

Данный этап применяется для нахождения на изображении области с интересующим образом объекта. Это осуществляется посредством обнаружения на рисунке односвязных областей, т.е. областей, представляющих собой множество пикселей, у каждого из которых имеются соседние пиксели, принадлежащие данному множеству (рис. 2в).

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

4. Масштабирование

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

После этапа предобработки осуществляется вычисление инвариантных к поворотам моментов изображений областей, содержащих объекты. Формула для вычисления в полярных координатах имеет следующий вид: где - момент порядка m, n, q; - модуль ( - комплексно сопряженное с ); – изображение в полярных координатах; – вейвлет-функция.

Здесь в качестве вейвлет-функции использовалась функция следующего вида [3, 4]:

(1).

Графики вейвлет-функций с различными значениями параметров m, n представлены на рис. 3.

Рис. 3. Графики вейвлет-функций при различных значениях m и n

Для успешного разделения классов изображений вектор признаков составляется не из всех моментов, а только из тех, которые удовлетворяют определенному критерию [1]. Сущность его заключается в следующем. Для каждого изображения образа определенного класса вычисляются моменты порядка m, n, q {}. Для всех моментов изображений определенного образа вычисляется среднее значение и дисперсия . Момент используется для классификации, если для любых двух образов определённого класса входных изображений i и j выполняется неравенство где параметр α обычно принимается равным 3.

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

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

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

При распознавании изображений монет достигается высокий процент правильных классификаций (95–98 %) при относительно небольшом числе используемых моментов (20-25), а при увеличении их количества процент правильных классификаций растет и стремится к 100 %. Данный метод может использоваться для распознавания и других классов двумерных объектов, таких, например, как цифры или буквы. Вероятность правильной классификации зависит от количества распознаваемых объектов, содержащихся в классе, а также от числа используемых моментов, т.к. при увеличении числа объектов может потребоваться большее число признаков, требующихся для их классификации.

Литература

1. 
   Prokop R.J., Reeves A.P. A survey of moment-based techniques for unoccluded object representation and recognition // CVGIP: Graphical Models Image Process. 1992. V. 54, № 5. P. 438-460.
   
2. 
   Добеши И. Десять лекций по вейвлетам: Пер. с англ. – М.: НИЦ «Регулярная и хаотическая динамика», 2004.
   
3. 
   Chui C.K. An introduction to wavelets. Academic Press, New York, 1992.
   
4. 
   Unser M., Aldroubi A., Eden M. On the asymptotic convergence of B-spline wavelets to Gabor functions // IEEE Trans. Inform. Theory. 1992. V. 38, P. 864-872.
   
5. 
   Unser M. A practical guide to the implementation of the wavelet transform / In: A. Aldroubi, M. Unser, (Eds.) Wavelets in Medicine and Biology. CRC Press, Boca Raton, FL, 1996. P. 37-73.
   
6. 
   Воробьев В.И., Грибунин В.Г. Теория и практика вейвлет-преобразования. – СПб.: ВУС, 1999.
   



Recognition of 2-D patterns on the base of invariant to rotation moments

Smolyakov A., Kandrin A., Skopintsev Y.

Yaroslavl State University
150000, Russia, Yaroslavl, Sovetskaya st., 14. Phone. (4852) 79-77-75. E-mail: [email protected]

Recognition and analysis of patterns on the image is an actual problem in our days and present great practical value while creating systems of artificial intelligence.

Process of recognition of an object on the image may be officially divided on the main phases:

1) searching object on the image;

2) finding features of this object;

3) classification.

First phase include several stages. First of all color model transformed to HSI (Hue, Saturation, Intensity) model and the other processing is being made only upon component I. Secondly, smoothing of intensity is made by changing intensity at every point of the image so, that average value of intensity at every line and every column is being equal to average value at all image, to liquidate unevenness of illumination. Third stage concludes in edge detection with 2D-wavelet transform, because in particular contours of the objects are more informative from the recognition point of view. At this stage threshold filtering of wavelet coefficients is made to remove noises and spurious high frequency changes. The last stage conclude in finding of simply connected domains on the images, which are used to localize domains on the image with the objects of recognition. This procedure allows to localize domains of all objects on the image, which are not collide with each others.

Vector of the features is being constructed after localization of the object on the image. For these features are used invariant to rotation moments [1]

Moments of such sort where for the function is used wavelet function (B-spline wavelet), allow to take features, which are more effectively characterize object and its difference from the others object of certain class.

Further, for the correct work of the algorithm moments, that satisfy certain criterion of selection, are chose. Directly pattern recognition are made by calculating vector of features, which consist from chosen moments of different orders and finding minimal distance deviation of this feature vector from the other vectors of known objects.

Method of recognition based on using of invariant wavelet-moments demonstrates very good results in classification of 2-D images. Percent of perfect classification aim to 100 % for the relatively small vector of distinctive features consists from 25 and more moments for experiments with class of coins.

Literature

1. 
   Prokop R.J., Reeves A.P. A survey of for unoccluded object representation and recognition // CVGIP: Graphical Models Image Process. 1992. V. 54, № 5. P. 438-460.
   



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

Бабаян П.В., Корепанов С.Е.

Рязанский государственный радиотехнический университет

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

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

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

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

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

Разностный корреляционный алгоритм основывается на минимизации разностной критериальной функции (РКФ) (1): , (1), где – яркость точки изображения текущего кадра с координатами , – яркость точки эталонного изображения объекта с координатами , – смещение объекта на текущем кадре , – множество точек эталонного изображения объекта.

Совместно с разностным корреляционным алгоритмом часто применяют методы, улучшающие качество слежения за объектом. В частности, для предсказания траектории движения наблюдаемого объекта прогнозируют положение объекта при помощи метода, основанного на траекторном фильтре Калмана [4]. Для того чтобы учитывать возможность изменения объекта, применяют фильтрацию эталонного изображения (2):

(2), где , сглаженное к n-му кадру эталонное изображение объекта, , сглаженное к (n-1)му кадру эталонное изображение объекта, , изображение объекта, найденное на n-м кадре, – параметр сглаживания.

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

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

Добиться улучшения слежения за объектами в сложной помеховой обстановке предлагается с помощью модифицирования критериальной функции разностного корреляционного алгоритма таким образом, чтобы при автоматическом слежении за объектом учитывать влияние получаемых на предыдущих кадрах прогнозируемых координат объекта. Предлагается ввести штраф при отклонении найденных координат объекта от прогнозируемых. Модифицированная критериальная функция (МКФ) вычисляется по формуле (3): (3), где – штрафная функция, вычисляемая по формуле (4): , (4), где – прогнозируемые координаты объекта, – параметр, характеризующий вид штрафной функции, – параметр, характеризующий степень доверия к прогнозируемым координатам.

Штрафная функция, на которую умножается РКФ, позволяет учитывать отклонение положения объекта от прогнозируемых координат. Если координаты найденного минимума РКФ соответствуют прогнозируемым координатам, то штрафная функция не вносит изменений и равна единице. При отклонении координат минимума РКФ от прогнозируемых координат, соответственно, вносится поправка, определяемая значением штрафной функции. Данный подход позволяет следить за объектами даже в тех случаях, когда в зону поиска попадают другие объекты, похожие на наблюдаемый объект. Преобразование критериальной функции в таком случае представлено на рис. 1.


б)

а)

в)


Рис. 1 Преобразование критериальной функции (а – РКФ, б – штрафная функция, в – МКФ)

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

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

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

Таблица 1 Среднеквадратическая ошибка определения координат объекта при k=2

α σ	0	0,05	0,1	0,12	0,13	0,14	0,2
0	2,19	2,72	2,12	2,09	-	0,03	0,07
0,005	5,69	3,92	0,61	0,59	0,5	0,89	0,97
0,008	c	0,9	0,77	1,14	0,54	c	3,61
0,01	с	c	2,08	1,17	2,83	c	c
0,013	c	c	1,38	c	c	c	c
0,02	c	c	с	c	c	c	c

Из таблицы видно, что при повышении шума становится трудно подобрать параметр для качественного слежения за объектом, но при нормальном шуме, дисперсия которого не превышает 0,013, наилучшее качество слежения за объектом достигается при .

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


б)

а)

в)

Рис. 2 Пример слежения за объектом

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

Литература

1. 
   Алпатов Б.А., Бабаян П.В. Методы обработки и анализа изображений в бортовых системах обнаружения и сопровождения объектов. // Цифровая обработка сигналов. – 2006. – №2. – С. 45-51.
   
2. 
   У. Прэтт. Цифровая обработка изображений: В 2-х т: Пер. с англ./Под ред. О.С.Лебедева. – М.: Мир, 1982.
   
3. 
   Муравьёв В.С., Муравьёв С.И. Алгоритм выделения и измерения координат объектов, наблюдаемых на облачных фонах // Вестник Рязанского государственного радиотехнического университета, Рязань. 2007. – №21, – С.20-24.
   
4. 
   А. Брайсон, Хо Ю-Ши. Прикладная теория оптимального управления./Под ред. А.М. Летова – М.Мир, 1972.
   


Correlation algorithm of automatic object tracking in difficult OBSERVING CONDITIONs

Babayan P., Korepanov S.

Ryazan state radio engineering university

Automatic object tracking is one of the relevant problems of process imaging. Today technologies of automatic object tracking are widely used in control systems, in security systems and in special techniques.

Task of automatic object tracking is concluded in detection of object on every frame from sequence of frames and in definition coordinates of this object.

In this work one of the methods of automatic object tracking is viewed. This method is directed to object tracking in difficult high clutter environment. Difficult high clutter environment is conditioned by heterogeneity of atmosphere, noises of camera and the presence of closely located similar objects. The first example of such a problems is observation of the cars riding on the road in the presence of partial mutual screening. Another example is automatic object tracking on heterogeneous background particularly near the skyline. Object tracking can be carried out on sequence of frames obtained in visible or spectral range.

The base of proposed task solution is a difference correlation algorithm. Differencel correlation algorithm bases on minimization of difference criterial function (DCF) (1): , (1),

where – brightness of point with coordinates on current image, – brightness of point with coordinates on etalon object image, – displacement of object on current frame , – a set of points of etalon object.

The imperfections of correlation methods are a high computational complexity, an unsteadiness in the presence of geometric distortions of the object, a beforehand necessity of knowledge of object image. The mistakes of object tracking are sufficiently concerned with the presence of closely located objects.

It is proposed to modify the criterial function to improve object tracking in difficult high clutter environment. This modification is concluded in considering of influence of predictable object coordinates. It is proposed to apply a penalty when recent coordinates differ from predictable. Modification of criterial function (MCF) is calculated by the expression (2): (2), where – penalty function calculated by the expression (3): , (3), where – predictable object coordinates, – parameter, defining a shape of penalty function, – parameter, defining a degree of belief to predictable coordinates.

Penalty function allows to consider deviation of object position from predictable coordinates. If coordinates of found minimum of DCF are corresponded to predictable coordinates, then penalty function doesn’t bring changes and it is equal to one. A correction is brought if the coordinates of DCF minimum are differ from the predictable coordinates. This approach allows to track the object even in the case of the presence of other objects, similar to observed object, situated in search zone.

Using algorithm based on modification of criterial function one can improve characteristics of object tracking in condition of difficult high clutter environment, as well as in the presence of closely located similar objects situated on image,



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

Кий К.И.

Институт Прикладной Математики им. Келдыша РАН, Международная Лаборатория “Сенсорика”

Введение

В работе рассматривается содержательная система для сжатого описания и сегментации цветных изо-бражений в реальном времени, предназначенная для решения широкого спектра задач понимания изображений. Система основана на новом подходе к описанию и сегментации цветных изображений, предложенном в серии работ автора [1-6, 8]. Подход использует разбиение изображения на узкие полосы (горизонтальные или вертикальные). Обработка изображений в системе основана на представлении цветных изображений в системе координат (G/(G+B), G/(G+R), I), где (R, G, B) координаты стандартного представления цветных изображений, и I интенсивность полутоновой компоненты изображения, которая позволяет восстанавливать полную цветовую информацию (оттенок, насыщение, etc.) и удобна для сведения первоначальной 3-D задачи цветового зрения к задачам меньшей размерности. Как известно [10], в человеческом мозге при обработке цветных изображений происходит переход от (R, G, B) изображения полученного на сетчатке к трем оппонентным цветам: черному-белому, красному-зеленому и желтому-голубому. В нашем подходе используется переход к оппонентной тройке (I, G/(G+B), R/(R+B)). Эта система координат удобна также для учета специфических особенностей человеческого зрения [10]. Реализованная зрительная система содержит подсистемы со следующими базисными функциями: раннее зрение (выделение локальных объектов в узких полосах изображения), промежуточное зрение (конструкция глобальных объектов), и зрение верхнего уровня (приблизительная качественная классификация выделенных глобальных объектов). На стадии раннего зрения, система не имеет информации о решаемой задаче. Предложенная система не концентрирует усилия на поиски заранее определенных признаков (например, прямолинейных отрезков), т.е. она не основана на модели сцены заданной заранее, но готовит общее локальное описание и классификацию. На промежуточной стадии обработки, при группировке локальных объектов в части возможных глобальных объектов, используются только общие идеи, основанные на новой версии определения однородности по яркости, текстуре, цвету и форме. Результаты обработки на ранней стадии представлены в форме наборов интервалов на вертикальной или горизонтальной оси плоскости изображения (это зависит от выбранного типа полос (горизонтальные или вертикальные)). Каждый из этих интервалов имеет цветовые (оттенок и насыщение) и яркостные характеристики. Кроме того, он имеет такие качественные характеристики как значимость и заметность, а также некоторый тип текстурной характеристики (чистота).

В [1-3] были представлены первые идеи описываемого подхода для изображений задаваемых скалярной функцией интенсивности (например, полутоновых телевизионных изображений) и дано приложение развитой теории к задаче понимания изображения при автономном движении мобильного робота на дороге. В деталях, результаты успешных экспериментов по автономному движению реального робота на дороге, полученные на основе предложенного метода были представлены в [7]. В дальнейшем метод был распространен на обработку отдельных цветовых компонентов (G/(G+B), G/(G+R), R/(R+B), S, H…) [4-6], а затем и полную обработку двумерной цветовой компоненты с учетом информации о полутоновой компоненте [8, 9]. В [6] был дан пример системы приближенных геометрических рассуждений для автоматического понимания дорожных сцен, основанный на предложенной технике. Данный подход позволяет находить в кадре "заметные" окрашенные объекты размером от трех пикселов. Разработанная теория позволяет аксиоматизировать многие подобные неформальные определения и дает новые текстурные признаки изображений. Она позволяет формализовать построение частей локальных и глобальных объектов на изображении и дает набор “кубиков”, которые определяют существенные детали изображения и дают возможность применить методы искусственного интеллекта для широкого круга изображений.

1. Теоретические Основы Предлагаемого Подхода

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

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

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

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

Однако для того чтобы иметь возможность сжимать информацию, определяемую слоями и сравнивать слои (например, строить описания глобальных принадлежащих нескольким полосам) объектов на изображении необходимо ввести на расслоении топологии. Эти топологии задаются метриками нескольких типов. Элементами (точками) каждого слоя описанного расслоения являются интервалы на горизонтальной оси, которым предписаны мощность и значение функции интенсивности изображения. Интервалы, соответствующие одному и тому же значению интенсивности, объединяются в наборы. Как первый шаг для введения близости точек в расслоении мы должны определить несколько нестандартных мер близостей в пространстве интервалов. Естественно, что при этом интервалы должны быть близки, если близки подмножества на изображении, которым они соответствуют. Если мы посмотрим на полосу изображения и на множество отрезков слоя расслоения, который соответствует данной полосе (представленное подсистемой визуализации в соответствующем окне разработанного программного комплекса), то легко заметить, что однородным объектам в полосе соответствуют кластеры интервалов в слое расслоения, которые близки одновременно как отрезки на горизонтальной оси и по значениям функции интенсивности, приписанных каждому интервалу. Реальные объекты в полосе (например, часть или целое изображение людей, автомобилей, etc.), которые состоят из нескольких относительно однородных объектов, представлены в соответствующем слое ансамблями кластеров, которые близки по пространственной координате на горизонтальной оси. Эти наблюдения дают основу для формальной процедуры поиска частей реальных объектов в полосе, которая состоит в поисках кластеров отрезков в слое близких одновременно как отрезки и с близкими значениями функции интенсивности. Так как локальные вариации интенсивности в реальных объектах в полосе могут иметь место только на небольшой части объекта, то интервалы следует считать близкими, если не оба их конца близки, а если велико их относительное пересечение (например, это пересечение велико в меньшем интервале). Данные соображения приводят к введению на пространстве отрезков мер близости, которые не только не являются евклидовыми, но и не сохраняют в индуцированной топологии свойства отделимости по Хаусдорфу (точки не отделяются окрестностями). В качестве примера рассмотрим следующее псевдо-расстояние, которое имеет важное применение в данном методе: . Здесь I, J некоторые отрезки и L(I) длина соответствующего отрезка. С помощью таких мер, использования близости интенсивностей, и разработанных оригинальных методов кластеризации определятся кластеры (сгустки) интервалов слоя расслоения, которые определяют локальные связные объекты в полосе. Каждый сгусток определяется объемлющим интервалом и двумя порогами интенсивности, соответствующим минимальному и максимальному значению интенсивности интервалов включенных в сгусток. Поэтому сгусток определяет некоторое множество в рассматриваемой полосе (выделенное с помощью определяемых локальных порогов) и кратко его геометрическое расположение можно описать соответствующим объемлющим интервалом сгустка. С помощью предложенных мер близости можно также сравнивать сгустки в соседних полосах и строить непрерывные системы сгустков расположенных в нескольких полосах - возможные глобальные объекты на изображении. С помощью изучения взаимного расположения полученных сгустков с учетом их мощности удается ввести текстурные признаки их характеризующие, а также искать точки контрастных переходов на изображении.

Данная конструкция построения локальных и глобальных объектов на изображении может быть обобщена на полноразмерное цветное изображение. Для того чтобы обобщить конструкции, выполненные для изображений заданных скалярной функцией интенсивности на векторный случай цветного изображения выполняются следующие процедуры. Рассматривается функция G/(G+B), которая принимает значения от 0 до 1. Диапазон ее разбивается на определенное число градаций, например 64. При проходе массива полосы мы исследуем также значения функций G/(G+R) и I (также имеющих 64 значения градации). Функции G/(G+B) и G/(G+R) в совокупности определят оттенок и насыщение. В формировании цвета также принимает участие полутоновая компонента. Мы искусственно вводим дополнительные значения G/(G+B), чтобы компенсировать изменение цвета при переходе через ноль компоненты G/(G+R) (например, переход от желтого к зеленому или переход от зеленого к синему). После цветоразделения, мы получаем наборы отрезков на горизонтальной оси, которым соответствует некоторое фиксированное значение G/(G+B) и некоторые интервалы значений параметров G/(G+R) и I, включая статистические характеристики распределения значений G/(G+R). Далее запускаются процедуры нахождения кластеров полученных окрашенных интервалов (цветовых сгустков) и процедуры получения глобальных объектов как непрерывных систем цветовых сгустков в полосах. Первое краткое описание этого метода и его применение к анализу дорожных сцен дано в [9]. В настоящий момент конструкция значительно усовершенствована и готовятся детальные журнальные публикации для ее описания. На основе новых результатов написан комплекс программ и разрабатываются применения этого комплекса для навигации мобильных роботах в помещениях.



2. Программная Реализация и Возможные Применения

Для реализации предложенных методов сжатого описания и сегментации изображений разработан комплекс программ, написанных на С++ в Visual Studio 2005 работающих под Windows XP. С использованием DirectXShow 9 комплекс стыкован с вводом из видеокамеры. Время обработки одного изображения линейно зависит от числа пикселов и производительности процессора. Имеется также слабая зависимость от числа полос, на которые разбито изображение. При обработке цветных изображений размера 640 х 480 на процессоре Pentium 4, 3.0 GHz в зависимости от числа полос (в типичных примерах от 16 до 32) скорость обработки от 10 до 8 fps. Для изображений размера 320 х 240 скорость обработки в четыре раза выше. Скорость обработки скалярных изображений (например, инфракрасных, выше более чем в шесть раз). Развитый язык содержательного описания результатов обработки позволяет решать многие задачи распознавания при меняющихся условиях окружающей среды.

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

Литература

1. 
   K.I. Kiy, Тополого-Геометрический Метод Обработки Изображений и Его Применение к Анализу Дорожных Сцен, Изв. Росс. Акад. Наук, Сер. Техническая Кибернетика, No. 5, 1992, 244-248
   
2. 
   K.I. Kiy, New Topological and Fuzzy Structures in Image Segmentation and Image Understanding Tasks, Advances in Intelligent Data Analysis, Proceedings of the Intelligent Data Analysis, Proc. Intelligent Data Analysis (IDA-95) Symposium, Advances in Intelligent Data Analysis, v. 1, pp. 85-89, Baden-Baden, Germany, Aug. 17-19, 1995.
   
3. 
   K.I. Kiy, A New Fuzzy Theory Based Approach to Image Processing. Its Implementation and Applications, Proc. 4th European Congress on Intelligent Technique and Soft Computing, Germany, Aachen, 1996.
   
4. 
   K.I. Kiy, An Implementation of a New Approach to Image Concise Description and Segmentation, Proc. of the IEEE Int. Conf. on Computer Vision and Pattern Recognition, Demo Session, San Juan, USA, p. 4. 1997.
   
5. 
   K.I. Kiy, An Unsupervised Color Vision System for Driving Unmanned Vehicles, Proc. SPIE AeroSense'98 Symposium, Enhanced and Synthetic Vision 1998, Jacques G. Verly, Editor, Proc. SPIE Vol.3364, pp. 371-382, Orlando, USA, 1998.
   
6. 
   K.I. Kiy, An Unsupervised Real-Time Multi-Task Vision System, Proc. IEEE Intelligent Vehicle'98 Conference, Stuttgart, October, 1998.
   
7. 
   K.I. Kiy, A.V. Klimontovich, and G.A. Buivolov, Vision-Based System for Road Following in Real Time, 1995 ICAR IEEE Conference, Proc. of the 7th International Conference on Advanced Robotics, v. 1, pp. 115-124, Barcelona, 1995.
   
8. 
   K.I. Kiy, Strip-Based Color Image Interpretation, Final Report, Institut für Systemdynamik und Flugmechanik UnBW München, LRT, Munich, December, 2001.
   
9. 
   K.I. Kiy and E.D. Dickmanns, A Color Vision System for Real-Time Analysis of Road Scenes, Proc. IEEE Intelligent Vehicle'04 Symposium, Parma, June, 2004, pp. 54--59.
   
10. 
    Хьюбел, Д., Глаз, Мозг, Зрение, Москва: Мир, 1990.
    


A REAL-TIME SYSTEM FOR CONCISE IMAGE DESCRIPTION AND SEGMENTATION

Kiy K.

Keldysh Institute of Applied Mathematics, Russian Academy of Sciences, Miusskaya pl. 4, Moscow, 125047,

International “Sensorika” Laboratory

In this paper, we present a new real-time system for concise image description and segmentation based on a new method of image description and segmentation. The image processing in the developed system is based on the representation of color images in the (,, ) coordinate system, which allows us to recover the complete color information (hue, saturation, etc,) and is convenient for reducing the original 3-D problem of color vision to problems of lower dimensions. The vision system consists of subsystems with the following basic functions: early vision (selection of local objects, intermediate vision (construction of global objects), and approximate qualitative classification of global objects selected at the intermediate stage. At the stage of local (early) vision, the system has no definite ideas what a problem is going to be solved. It does not concentrate its efforts on finding predetermined features (for instance, straight segments), but prepares a general-purpose local image description and classification. This description simultaneously comprises intensity, texture, color, and shape characteristics of the local objects. At the intermediate stage of processing, in grouping local objects into parts of possible global objects, only general ideas based on new versions of definition of homogeneity in intensity, texture, color, shape are used. These stages of processing are not task oriented, so they can be employed in various tasks. In the course of processing, we divide images into several parallel vertical or horizontal strips of a fixed width. The results of the early vision stage are represented in the form of collections of intervals on the vertical or horizontal axis of the image plane (this depends on the employed type of strips (vertical or horizontal)). Each of these intervals has color (hue and saturation) and grayscale intensity characteristics. In addition, it has qualitative characteristics such as its significance and visibility, as well as some texture characteristics (purity). To select small (distant) colored images, we group