Универсальная классификация алгоритмов сегментации
изображений.
Поршнев Сергей Владимирович,
доктор технических наук, профессор,
заведующий
кафедрой автоматики и
информационных технологий,
Левашкина Анастасия Олеговна,
аспирант,
Радиотехнический институт Уральского Государственного Технического
Университета-УПИ.
1.
Введение.
Сегментация изображения – это процесс разделения
изображения на множество непересекающихся областей, объединение которых даст
целое изображение. К областям, получаемым в результате сегментации, предъявляются
следующие требования [1]:
Купить кислородный концентратор Концентратор кислорода для борьбы с дыхательной недостаточностью. В наличии air-med.ru
1.
Области
должны быть однородны относительно определенных характеристик.
2.
Внутренние
части областей должны быть простыми без большого количества маленьких отверстий.
3.
Смежные
области должны существенно отличаться по значениям выбранных характеристик,
относительно которых они считаются однородными.
4.
Границы
каждого сегмента должны быть простыми, пространственно точными.
Сегментация является наиболее критической процедурой процесса
автоматизации анализа изображений, поскольку ее результаты влияют в дальнейшем
на все последующие действия, связанные с анализом изображения: представление
выделенных объектов и их текстовое описание, измерение признаков, а также другие
задачи более высокого уровня (классификация объектов, интерпретация сцен и
т.д.).
Напомним, что первые алгоритмы сегментации изображений
(АСИ) были предложены в 40-х годах XX в., а в
На практике при анализе конкретного изображения
возникает необходимость выбора алгоритма, наиболее подходящего для его
сегментации. При этом, как очевидно, приходится учитывать как свойства
изображения, так и особенности конкретного АСИ. В этой связи задача построения универсальной
классификации алгоритмов, охватывающей все известные АСИ, является актуальной.
Целью статьи является анализ известных подходов к построению
классификации АСИ и описание обобщенного подхода, позволяющего создать классификацию,
включающую в себя все известные АСИ.
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.
Классификация Чанга.
Классификация |
На
основе краев (разрывность) |
На
основе областей (сходство) |
Параллельная
обработка |
G1: алгоритмы параллельной
обработки на основе выделения границ |
G3: алгоритмы параллельной
обработки на основе выделения областей |
Последовательная
обработка |
G2: алгоритмы последовательной
обработки на основе выделения границ |
G4: алгоритмы последовательной
обработки на основе выделения областей |
Рис. 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,
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.
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),
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
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,
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),
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),
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,
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
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.,
49.
Иванов В.К., Пащенко Р.Э., Стадник
А.М., Яцевич С.Е., Кучук Г.А.
Фрактальный анализ изображений лесных массивов // Успехи зарубежной
радиоэлектроники, 2005, №12, pp. 55-62.
50.
Ohta Y., Kanade T.,
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,
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 г.