Универсальная классификация алгоритмов сегментации изображений.

 

Поршнев Сергей Владимирович,

доктор технических наук, профессор,

заведующий кафедрой автоматики и информационных технологий,

Левашкина Анастасия Олеговна,

аспирант,

Радиотехнический институт Уральского Государственного Технического Университета-УПИ.

 

1.                  Введение.

 

Сегментация изображения – это процесс разделения изображения на множество непересекающихся областей, объединение которых даст целое изображение. К областям, получаемым в результате сегментации, предъявляются следующие требования [1]:

1.                  Области должны быть однородны относительно определенных характеристик.

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

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

4.                  Границы каждого сегмента должны быть простыми, пространственно точными.

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

Напомним, что первые алгоритмы сегментации изображений (АСИ) были предложены в 40-х годах XX в., а в 1965 г. Робертсом был предложен алгоритм регистрации границ изображения АСИ, остающийся популярным и сегодня, - детектор краев Робертса [2]. К настоящему моменту создано большое количество разнообразных алгоритмов сегментации, описание которых приводится преимущественно в англоязычной литературе (см., например, [1,2,6-20, 23-34, 37-48, 50-59]). Из русскоязычных публикаций выделим работы обзорного характера [3-5, 45]. В тоже время необходимо отметить, что в большинстве из них описано состояние методов и алгоритмов сегментации изображений двадцатилетней давности. Более поздних обзоров по данной теме на русском языке авторам обнаружить не удалось.

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

Целью статьи является анализ известных подходов к построению классификации АСИ и описание обобщенного подхода, позволяющего создать классификацию, включающую в себя все известные АСИ.

 

2.                  Анализ подходов к классификации АСИ.

 

Среди известных подходов к построению классификации известных АСИ можно выделить:

1.                  подход Фу (Fu) [6];

2.                  подход Пала (Pal) [7];

3.                  подход Скарбека и Кошана (Skarbek и Koschan) [8];

4.                  подход Лючиса и Митра (Lucchese и Mitra) [9].

Классификация АСИ, основанная на подходе Фу[6], представлена на рис. 1. В соответствие с данной классификацией выделены следующие типы АСИ:

1.                  Алгоритмы пороговой обработка и кластеризации.

2.                  Алгоритмы выделения краев.

3.                  Алгоритмы извлечения областей.

 

Рис. 1.

Классификация АСИ, предложенная Фу.

 

Недостаток данной классификации, с нашей точки зрения, состоит в том, что алгоритмы пороговой обработки одновременно можно отнести к алгоритмам извлечения областей. Таким образом, группа алгоритмов (1) фактически является подгруппой группы (3).

Известна альтернативная классификация, основанная на подходе предложенном Палом [7] (рис. 2). В соответствии с ней АСИ разделены на следующие группы:

1.                  Алгоритмы пороговой обработки.

2.                  Алгоритмы классификации пикселей (включая релаксацию, подходы на основе случайного поля марковского типа и подходы на основе нейронных сетей).

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

4.                  Алгоритмы сегментации цветных изображений.

5.                  Алгоритмы выделения краев.

6.                  Алгоритмы, использующие методы теории нечетких множеств (данные АСИ предполагают применение теории нечетких множеств к группам (1), (2), (5)).

 

Рис. 2.

Классификация АСИ, предложенная Палом.

 

Необходимо отметить, что, вообще говоря, множества информационных признаков, выделенных Палом групп АСИ, пересекаются друг с другом. Например, в АСИ, отнесенных к группам (3) и (4), основной акцент сделан на том как сегментированы изображения. Кроме того, авторами рассматриваемой классификации [7] показано, что сегментация цветных изображений и изображений, воспроизводящих трехмерную структуру сцены, может быть основана на алгоритмах пороговой обработки, классификации пикселей, и регистрации краев. С другой стороны, АСИ, использующие методы теории нечетких множеств, в соответствие с данной классификацией оказываются включенными в различные группы - (1), (2) и (5). Таким образом, в классификации Пала в действительности остаются только три различных группы. Также отметим, что АСИ, включенные в группы (1) и (2) имеют много общего [6], в тоже время некоторые известные АСИ, например, алгоритм выращивания областей нельзя отнести ни к одной из групп.

Иная классификация приведена в обзоре Скарбека и Кошана [8] (рис. 3). В соответствии с данной классификацией все алгоритмы разделены на следующие 4 группы:

1.    Алгоритмы, основанные на анализе свойств пикселей.

2.    Алгоритмы, основанные на анализе свойств области.

3.    Алгоритмы, основанные на выделения краев областей.

4.    Алгоритмы, учитывающие физические свойства объектов, представленных на изображении.

 

Рис. 3.

Классификация АСИ, предложенная Скарбеком и Кошананом.

 

Известна классификация АСИ Лючиса и Митра [9] (рис. 4). Здесь авторы выделяют следующие три класса алгоритмов:

1.    Алгоритмы, основанные на анализе свойств на пространстве признаков.

2.    Алгоритмы, основанные на анализе свойствах областей.

3.    Алгоритмы, учитывающие физические свойства объектов, представленных на изображении.

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

 

Рис. 4.

Классификация АСИ, предложенная Лючисом и Митрой.

 

Классификация алгоритмов сегментации полутоновых изображений, предложенная Денисовым и Низовкиным [3], представлена на рис. 5. Здесь авторы выделяют следующие группы алгоритмов:

1.                  Алгоритмы на основе выделения границ областей.

2.                  Алгоритмы на основе разметки точек области.

 

Рис. 5.

Классификация АСИ, предложенная Денисовым и Низовкиным.

 

Следует также упомянуть классификации сделанные только по единственному информационному признаку. В работе [4] приводится классификация только алгоритмов на основе пороговой обработки, в работе [5] - только алгоритмов выделения границ областей, а Харалик и Шапиро [1], Саху [10], Спирковска [11] предложили классификации алгоритмов сегментации полутоновых изображений.

Известна попытка построения универсальной классификация АСИ, предложенная Чангом [12], которая объединяет подходы [13], а также Розенфельда [14]. Данная классификация представлена на рис.6 и в табл.1. Напомним, что подход Гонсалеса и Вудса основан на том, что сегментация полутоновых изображений в основном выполняется на основе анализа двух основных свойств – разрывности и сходств в значениях уровня серого цвета [13]. В классификации Гонсалеса и Вудса выделены две категории алгоритмов:

1.                  Алгоритмы, основанные на нахождении границ – регистрации контуров объектов с использованием свойства разрывности.

2.                  Алгоритмы, основанные на нахождении  областей – локализации объектов в соответствии со свойствами сходства.

Классификация АСИ, предложенная Розенфельдом [14], основана на стратегии последовательности выполнения вычислительных действий, выполняемых при обработке изображения (последовательные вычисления, параллельные вычисления). В данной классификации выделены следующие группы АСИ:

1.                  Алгоритмы последовательной обработки.

2.                  Алгоритмы параллельной обработки.

 

Таблица 1.

Классификация Чанга.

 

Рис. 6.

Обозначения информационных признаков в классификации Чанга.

 

Легко проверить, что выделенные 4 группы вмещают в себя все существующие алгоритмы сегментации:

1.                  Большинство алгоритмов сегментации на основе выделении краев могут быть отнесены к группе G1.

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

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

4.                  Алгоритмы, основанные на представлении изображения с помощью вейвлетов, алгоритмы выращивания областей, разбиения/объединения областей часто относятся к группе G4.

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

 

3.                  Обобщенная классификация АСИ.

 

При построении обобщенной классификации АСИ мы предлагаем использовать следующие информационные признаки алгоритмов:

1.                  Свойства, на основе которых выполняется сегментация (разрывность или сходство низкоуровневых признаков).

2.                  Стратегия обработки изображения – последовательная или параллельная.

3.                  Тип изображения – цветное или полутоновое – к которому могут быть применены алгоритмы сегментации.

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

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

1. Исторически первые алгоритмы сегментации разрабатывались для полутоновых изображений (например, операторы градиента) и только потом для сегментации цветных изображений.

2. Одним из современных подходов к улучшению качества результатов, даваемых алгоритмами сегментации, является использование критериев качества сегментации, встраиваемых в АСИ.

В соответствии с предложенным подходом можно выделить следующие группы алгоритмов, представленных в табл.2 и на рис.7.

 

Таблица 2.

Информационные признаки второго уровня.

классификация	С использованием критерия качества	Без использования критерия качества
Цветные изображения	W1: алгоритмы сегментации цветных изображений с использованием критерия качества	W3: алгоритмы сегментации цветных изображений без использования критерия качества
Полутоновые изображения	W2: алгоритмы сегментации полутоновых изображений с использованием критерия качества	W4: алгоритмы сегментации полутоновых изображений без использования критерия качества

 

Рис. 7.

Обозначения информационных признаков второго уровня.

 

На рис. 8 представлена классификация известных АСИ, построенная в соответствии с предложенными принципами. Отметим, что в соответствие с предложенной классификацией, каждый из алгоритмов, описанных в [15-59], может быть однозначно отнесен к одной из соответствующих групп.

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

1.                  G1_W1 – алгоритмы параллельной обработки на основе выделения границ для сегментации цветных изображений с использованием критерия качества;

2.                  G1_W2 – алгоритмы параллельной обработки на основе выделения границ для сегментации полутоновых изображений с использованием критерия качества;

3.                  G2_W1 – алгоритмы последовательной обработки на основе выделения границ для сегментации цветных изображений с использованием критерия качества;

4.                  G2_W2 – алгоритмы последовательной обработки на основе выделения границ для сегментации полутоновых изображений с использованием критерия качества;

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

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

 

 Рис. 8.

Обобщенная классификация АСИ.

 

4.      Заключение.

 

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

2.                  Анализ результатов классификации АСИ позволил обнаружить, что на сегодняшний день отсутствуют следующие АСИ: алгоритмы параллельной обработки на основе выделения границ для сегментации цветных изображений с использованием критерия качества; алгоритмы параллельной обработки на основе выделения границ для сегментации полутоновых изображений с использованием критерия качества; алгоритмы последовательной обработки на основе выделения границ для сегментации цветных изображений с использованием критерия качества; алгоритмы последовательной обработки на основе выделения границ для сегментации полутоновых изображений с использованием критерия качества; алгоритмы последовательной обработки на основе выделения областей для сегментации полутоновых изображений с использованием критерия качества.

 

Литература.

 

1.                  Haralick R., Shapiro L. (1985). Image segmentation techniques, Computer Vision, Graphics and Image Processing (CVGIP), 29, 100-132.

2.                  Roberts L. (1965). Machine perception of three dimensional solids, in J. Tippett et al. Optical and electro-optical information processing, 159-197.

3.                  Денисов Д.А., Низовкин В.А. Сегментация изображений на ЭВМ // Зарубежная радиоэлектроника, 1985. №10, с. 5-31.

4.                  Бакут П.А., Колмогоров Г.С., Ворновицкий И.Э. Сегментация изображений: методы пороговой обработки // Зарубежная радиэлектроника, 1987. №10, с. 6-24.

5.                  Бакут П.А., Колмогоров Г.С. Сегментация изображений: методы выделения границ областей // Зарубежная радиоэлектроника, 1987. №10, с. 25-47.

6.                  Fu K., Mui J. (1981). A survey on image segmentation, Pattern Recognition, 13, 3-16.

7.                  Pal N., Pal S. (1993). A survey on image segmentation techniques, Pattern Recognition, 26, 1277-1294.

8.                  Skarbek W., Koschan A. (1994). Color Image Segmentation - A Survey, Technisher Bericht, Technical University of Berlin, 94-32.

9.                  Lucchese L., Mitra S. (2001). Color Image Segmentation: A State-of-the-Art Survey, Image Processing, Vision, and Pattern Recognition. Proc. of the Indian National Science Academy (INSA-A), New Delhi, India. 2001, 207-221.

10.               Sahoo P.K. et.al. (1988). A survey of thresholding techniques, Computer Vision, Graphics and Image Processing, 41, 233-260.

11.               Spirkovska L. (1993). A summary of image segmentation techniques, NASA technical memorandum 104022, June.

12.               Zhang Y. (2006). Advances in Image And Video Segmentation. USA: IRM Press.

13.               Gonzalez R., Woods R. (2002). Digital image processing (2nd ed.). NJ:Prentice Hall.

14.               Rosenfeld A. (1981) Image pattern recognition, Proceedings of IEEE, 69(5), 596-605.

15.               Macaire L., Ultre V., Postaire J.G. (1996). Determination of compatibility coefficients for color edge detection by relaxation, International Conference on Image Processing, C., 1045-1048.

16.               Nevatia. (1977). A color edge detector and its use in scene segmentation, IEEE Trans. On System, Man and Cybernetics, Vol. SMC-7, No.11, 820-826.

17.               Robinson G.S. (1977). Color Edge Detection, Optical Engineering, Vol.16, No.5, Sept.

18.               Carron T., Lambert P. (1995). Fuzzy Color Edge Extraction by Inference Rulse Quantitative Study and Evaluation of Performances, International Conference in Image Processing, B, 181-184.

19.               Ma W.Y., Manjunath B.S. (1997). Edge Flow: A Framework of boundary Detection and Image segmentation, Proc. Of  IEEE Int`l Conf. on Computer Vision and Pattern Recognition (CVPR`97), Puerto Rico, June, 755-749.

20.               Perez F., Koch C. (1994). Toward Color Image Segmentation in Analog VLSI: Algorithm and Hardware, Int`l Journal of computer vision, vol.12, no.1, 17-42.

21.               Компьютерное зрение / Л. Шапиро, Дж. Стокман; Пер. с англ. – М.: БИНОМ. Лаборатория знаний, 2006. – 752 с., 8 с. ил.: ил.

22.               Гонсалес Р., Вудс Р. Цифровая обработка изображений / Москва: Техносфера, 2006.– 1072 с.

23.               Kirsche R.A., Cahn L., e.a. (1957). – In. Proc. of Eastern Joint Comput. Conf., 221-229.

24.               Smith S., Brady J. (1995). SUSAN – a new approach to low level image processing, International Journal of Computer Vision, 23(1), 45-78.

25.               Rothwell C.A., Mundy J.L., Hoffman W., Nguyen V.-D. (1995). Driving vision by topology, in Procedings of IEEE International Symposium on Computer Vision (ISCV`95), Coral Gables, Fla, USA, November, 395-400.

26.               Meer P., Georgescu B. (2001). Edge detection with embedded confidence, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol.23, no.12, 1351-1365.

27.               Ren X., Malik J. (2002). A Probabilistic Multi-scale Model for Contour Completion Based on Image Statistics, in ECCV '02, Copenhagen, volume 1, 312-327.

28.               B. Sumengen, B. S. Manjunath, C. Kenney, (2002). Image Segmentation using Curve Evolution and Flow Fields, Proc. IEEE International Conference on Image Processing (ICIP), Rochester, NY, USA, Sep.

29.               Shapiro G. (1996). Vector (Self) Snakes: Giometric Framework for Color, Texture and Multiscale Image Segmentation, Proc. of Int`l Conf. on Image Processing (ICIP`95), Lausanne, Switzeland, 16-19 Sept., vol. 1, 817-820.

30.               Shapiro G. (1997). Color Snakes, Computer Vision and Image Understading, vol. 68, no.2, 247-253.

31.               Behiels G., Maes F., Vandermeulen D., et. al. (2002). Evaluation of Image deatures and search sttratagies for segmentation of bone structures in radiographs using active shape models, Medical Image Analysis, 6(1), 47-62.

32.               Omran M., Salman A., Engelbrecht A. (2006). Dynamic clustering using particle swarm optimization witn application in image segmentation, Pattern Anal Applic, 8, 332-334.

33.               Han X., Zhao T. (2005). Auto-K Dynamic Clustering Algorithm, Asian Journal of Information Technology, GPN, 4(4), 44-451.

34.               Deng Y., Manjunath B.S., Shin H. (1999). Color Image Segmantation, IEEE Computer Society Conference on computer vision and pattern recognition, CVPR`99, v.2., 446-451.

35.               Махфуд У.А. Комбинированные алгоритмы сегментации цветных изображений.: дис. канд. тех. наук: 05.13.01/ У.А. Махфуд; Институт технической кибернетики национальной академии наук Беларуси. – Минск, 2002.

36.               Дорогов А.Ю., Курбанов Р.Г., Разин В.В. Быстрая классификация JPEG-изображений [Электронный ресурс] /  грант Яндекса 2005 – Режим доступа:  http://company.yandex.ru/grant/2005/03_Dorogov_102608.pdf, свободный.

37.               Cheng H.D., Li J. (2000). Fuzzy Homogeneity and Scale Cpace Approach to Color Image Segmentation, International Conference on Computer Vision, Pattern Recognition and Image Processing, Atlantic City, Feb. 27 – Mar. 3.

38.               Shi H., Malik J. (1997). Normalized Cuts and Image Segmentation,  Proc. of IEEE Int`l Conference on Computer Vision and Pattern Recognition, San Juan, Puerto Rico, 17-19 June, 731-737.

39.               Comaniciu D., Meer P. (2002). Mean shift: A robust approach toward feature space analysis, IEEE Trans. On Pattern Analysis and Machine Intelligence, 24, 603-619.

40.               Felzenswalb P., Huttenlocher D. (2004). Efficient Graph-Based Image Segmentation, Int Journal of Computer Vision, 59(2).

41.               Knudsen T., Muhammed H.; Olsen B. (2002). A Comparison of Neuro-Fuzzy and Traditional Image Segmentation Methods for Automated Detection of Buildings in Aerial Photos, Proceedings of Pcv'02: Photogrammetric Computer Vision.

42.               Kaufman L., Rousseeuw P.J. (1990). Finding Groups in Data: an Introduction to Cluster Analysis, John Willye & Sons.

43.               Ng R., Han J. (1994). Efficient and effective clustering method for spatial data mining, In Proc. of the 20th VLDB Conference, Santiago, Chile, 144-155.

44.               Ester M., Kriegel H.P., Sander J., Xu X. (1996). A density-based algorithm for discovering clusters in large spatial databases with noise, In Proc. of the Second Int`l Conference on Knowledge Discovery and Data Mining, Portland, OR, 226-231.

45.               Guha S., Rstogi R., Skim K. (1998). CURE: An efficient clustering algorithm for large databases, In proc. of 1998 ACM-SIGMOD Int. Conf. On Management of Data, 103-114.

46.               Guha S., Rstogi R., Skim K. (1999). ROCK: a robust clustering algorithm for categorical attributes, In Proc. of the 15th Int`l Conf. on data Eng., 512-521.

47.               Karypis G., Han E.-H., Kumar V. (1999). CHAMELEON: A hierarchical Clustering Algorithm Using Dynamic Modeling, In the Proc. of IEEE Computer, 88-75.

48.               Pelleg D., Moore A. (2000). X-means: Extending k-means with efficient estimation of the number of clusters, InProc. Of the 17th Int`l Conf. on Machine Learning. San Francisco, 727-734.

49.               Иванов В.К., Пащенко Р.Э., Стадник А.М., Яцевич С.Е., Кучук Г.А. Фрактальный анализ изображений лесных массивов // Успехи зарубежной радиоэлектроники, 2005, №12, pp. 55-62.

50.               Ohta Y., Kanade T., Sakai T. (1980). Color Information for region segmentation, Computer Graphics and Image Processing, Vol.13, 222-241.

51.               Ohlander R., Price K., Reddy D.R. (1978). Picture Segmentation Using A Recursive Region Splitting Method, Computer Graphics and Image Processing, 8, 313-333.

52.               Tominaga S. (1986). Color Image Segmentation Using Three Perceptual Attributes, IEEE Proceedings of the Conference on Computer Vision and Pattern Recognition, Los Alamos, CA, 628-630.

53.               Celenk M. (1990). A Color Clustering Technique for image segmentation, Graphical Models and Image Processing, vol.52, no.3, 145-170.

54.               Tremeau A., Borel N. (1997). A region Growing and merging algorithm to color segmentation, Pattern Recogmition, vol.30, no.7, 1191-1203.

55.               Panjwani D.K., Healey G. (1995). Markov Random Field Models for Unsupervised Segmentation of textured color images, IEEE tranc. On Pattern Analysis and Machine Intelligence, vol. PAMI-17, no.10, 939-954.

56.               Barny M., Rossi S., Mecocci A. “A fuzzy expert system for low level image segm,entation”, Proc. of the 8th european signal processing conference (EUSOPCO-96),vol.3, pp.1725-1728.

57.               Yu S. (2005). Segmentation induced by scale invariance, in Proc. of Int`l conf. on computer vision and pattern recognition, 2.

58.               Gevers T., Munoz A. (1997). Combining region splitting and edge detection through guided Delaunay image subdivision, in Proc. of Int`l Conf. on computer vision and pattern recognition, 2.

59.               Freixenet J., Muñoz X., Raba D., Martí J., Cufí X. (2002). Yet Another Survey on Image Segmentation: Region and Boundary Information Integration. ECCV (3), 408-422.

 

Поступила в редакцию 14.03.2008 г.