Технической кибернетики национальной академии наук беларуси удк 681.3

ГОСУДАРСТВЕННОЕ НАУЧНОЕ УЧРЕЖДЕНИЕ «ИНСТИТУТ ТЕХНИЧЕСКОЙ КИБЕРНЕТИКИ НАЦИОНАЛЬНОЙ АКАДЕМИИ НАУК БЕЛАРУСИ» УДК 681.327.12.001.362 УЛЬД АХМЕД ТАЛЕБ Махфуд [email protected] КОМБИНИРОВАННЫЕ АЛГОРИТМЫ СЕГМЕНТАЦИИ ЦВЕТНЫХ ИЗОБРАЖЕНИЙ 05.13.01 – Системный анализ, управление и обработка информации АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук Минск 2002 1 ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ Актуальность. Сегментация визуальной информации является предварительным этапом любой системы обработки изображений, так как позволяет упростить последующий анализ однородных областей изображения, их яркостных и геометрических характеристик. Сегментацию следует рассматривать как начальный этап построения формального описания сцены, качество выполнения которого во многом определяет успех решения задачи распознавания изображений, интерпретации и идентификации визуально наблюдаемых объектов.

Для решения задачи сегментации полутоновых изображений было разработано много методов и алгоритмов. В последние годы все больше визуальная информация регистрируется в виде цветных изображений. Сегментация цветных изображений является более сложной задачей, чем полутоновых. Так, если в полутоновом изображении пиксель может иметь 256 оттенков яркости, в случае цветного изображения пиксель может иметь один из 256 оттенков яркости каждого из трех цветов, что делает количество возможных цветов равным (256)3=16 216, поэтому возникают трудности при адаптации известных алгоритмов сегментации полутоновых изображений для обработки цветных.

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

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

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

Связь работы с крупными научными программами, темами.

Диссертационная работа выполнена в лаборатории обработки и распознавания изображений Института технической кибернетики НАН Беларуси в 1998-2001 гг. в рамках следующих научно-исследовательских работ: Научно-исследовательская работа “Интеллект-17”, тема “Создание теоретических основ разработки, анализа и распознавания изображений с использованием методов искусственного интеллекта” (1996-2000 гг.);

Проект Фонда фундаментальных исследований Республики Беларусь № Т98-226 “Проблемно-ориентированное распознавание объектов полутоновых изображений” (1999-2001 гг.);

Проект Фонда фундаментальных исследований Республики Беларусь № 98М- “Предварительная обработка и анализ фотопортретов” (1999-2000 гг.);

Государственная научно-техническая программа “Передовые информационные и телекоммуникационные системы” (2001-2003 гг.) утвержденная постановлением Совета Министров РБ от 01.02.2001г. № 141.

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

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

• алгоритма сегментации путем наращивания областей с использованием градиентной информации;

• алгоритма сегментации средствами кластерного анализа;

• алгоритма сегментации, комбинирующего кластерный анализ и метод главных компонент;

• алгоритма идентификации участков человеческой кожи.

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

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

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

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

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

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

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

Разработанные алгоритмы используются на Научно-инженерном республиканском унитарном предприятии «Геоинформационные системы» для обработки цветных изображений, полученных с помощью спутника NOAA.

Алгоритмы преобразования цветных изображений в полутоновые и алгоритмы сегментации были программно реализованы и переданы НПП «Регула» для применения в системе контроля подлинности денежных знаков для автоматической идентификации бумажной подложки на цветных изображениях банкнот.

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

Основные положения диссертации, выносимые на защиту:

• Алгоритм преобразования цветных изображений в полутоновые.

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

• Алгоритм сегментации средствами кластерного анализа.

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

• Алгоритм идентификации участков человеческой кожи на цветных изображениях.

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

Апробация результатов диссертации. Основные положения диссертационной работы докладывались и обсуждались на 5-й международной конференции “Pattern Recognition and Information Processing” (Minsk, 1999), 7-й Белорусской математической конференции (Минск, 2000), на республиканском научном семинаре (Минск, БГУ, 2000), 6-й международной конференции “Pattern Recognition and Information Processing” (Minsk, 2001) и на семинарах ИТК (1998 2002).

Опубликованность результатов. Результаты проведенных исследований опубликованы в 7 печатных работах и 4 отчетах научно-исследовательских работ.

Из них: 1 статья в журнале «Вести Национальной академии наук Беларуси», статьи в трудах международных конференций, 1 препринт, 2 статьи в сборнике Института технической кибернетики Национальной академии наук Беларуси.

Структура и объем диссертации. Диссертация состоит из введения, общей характеристики, трех глав с выводами, заключения, списка литературы (насчитывает 110 наименований) и приложения, изложенных на 128 страницах, включая четыре таблицы и 48 иллюстраций, размещенных на 36 страницах.

ОСНОВНОЕ СОДЕРЖАНИЕ Во введении обоснована актуальность и практическая значимость темы диссертационной работы и определены основные задачи исследования.

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

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

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

Преобразование системы цветовых координат. Были применены преобразования систем координат RGB в HSV, TLS, (R/G, R/B,G/B), (2R-G-B) и описан новый алгоритм преобразования цветных изображений в полутоновые.

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

Grayij=0.3*Rij+0.59*Gij+0.11*Bij;

(1) Grayij=(Rij + Gij + Bij)/3, (2) где Grayij – яркость пикселя с координатами (i,j) в полутоновом представлении исходного цветного изображения;

Rij, Gij, Bij – значения яркости красного, зеленого и синего цветов.

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

• Цветное изображение размером MN, заданное в системе координат RGB, представлять в виде трех векторов каждый длиной MN.

• Вычислить ковариационную матрицу изображения, ее собственные значения exy, x, y = 1,2,3.

• Определить оси новой системы координат.

• В качестве полутонового варианта принимать проекцию исходного изображения на главную ось.

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

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

б) формулой (1);

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

Слияние. Маленькая область (количество пикселей которой меньше заданного порога) присоединяется к ближайшей к ней по яркости большой области.

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

Морфологическая фильтрация. К бинарному изображению применяются последовательно такие операции математической морфологии, как расширение (дилатация) и сжатие (эрозия). Такая фильтрация является наиболее эффективной процедурой для алгоритмов сегментации кожи человека.

б) а) Рис.2. Обработка изображения: а) результат сегментации;

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

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

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

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

Пусть A={Aij} обозначает цветное изображение, Aij={rija,gija,bija} – пиксель, имеющий координаты i,j, и rija,gija,bija – яркость соответственно красного, синего и зеленого цветов пикселя, где 0 i,j N, 0 rija,gija,bija Z = 255, N N – размер изображения и Z – максимальное значение каждой компоненты цвета. C – результат сегментации, являющийся псевдоцветным изображением (т.е. пиксель имеет средний цвет области, к которой он относится).

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

{ [d(A, C) + d(C, A)] 2 }1/ F1(A, C) = ij ij 2ZN i, j Для уменьшения влияния шума использована фильтрация локального расстояния от пикселя Aij изображения A к изображению С:

{ [d (A, C) + d (C, A)] 2 }1/ F1(A, C) = 2ZN i, j ij ij ij ij где dij(Aij,Cw) = min(l,m) W {d(Aij,Clm)};

W – рассматриваемое квадратное окно на изображении С размером (2w+1)(2w+1) с центром в точке (i,j).

Если не требуется фильтровать, то d(Aij,C)=d(Aij,Cw). Аналогично вычисляется d(Сij,A). Функция F1 принимает значения в диапазоне [0,1].

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

d (A, C ) = max i l, j m, r a r c, g a g c, b a b c }, { 1 ij lm ij lm ij lm ij lm d (A, C ) = max i l, j m, ( r a r c, g a g c, b a b c ) /3 } { 2 ij lm ij lm ij lm ij lm d (A, C ) = ( i l, j m, r a r c, g a g c, b a b c ) / 3.

3 ij lm ij lm ij lm ij lm В результате экспериментальных исследований установлено, что при F1(A,C ) 0.16 изображения A и C представляют почти одинаковую сцену, при F1(A,C)0. изображения A и C представляют разные сцены. В результате порог между сходством и несходством изображений был выбран равным 0.17. Изображения A и C представляют одну и ту же сцену, если 99% локальных отличий d(Aij,C) и d(Cij,A) меньше W. Значение сходства изображений может быть оценено в виде 1-F1(A,C).

В качестве оценки результата сегментации цветных изображений исследована функция Лью и Янг (Liu, Yang) R ei, F2(I) = R 1000(MN) i = 1 Ai где I – сегментируемое изображение размером MN;

R – количество областей на сегментируемом изображении;

Ai – площадь i-й области;

ei – средняя цветовая ошибка i-й области, которая равняется сумме евклидовых расстояний между RGB цветовым вектором пикселей i-й области (на исходном изображении) и цветовым вектором, соответствующим области i на сегментированном изображении.

Алгоритм, для которого значение функции F2(I) меньше, считается лучшим.

Предыдущую функцию можно модифицировать следующим образом:

e2 R(A ) R 1 k k ) ], F3(I) = R [ +( 1 + logA 10000(MN) A k =1 k k где R(A) – количество областей, площадь каждой из которых равняется A.

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

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

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

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

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

Алгоритм сегментации состоит из следующих этапов:

Этап 1. Преобразование цветного изображения в полутоновое. Выполнить преобразование с помощью алгоритма преобразования цветного изображения в полутоновое, описанного выше.

Этап 2. Автоматический поиск стартовых точек. Определить стартовые точки (этапы определения стартовых точек показаны на рис.3).

Этап 3. Сегментация методом наращивания областей. Области вокруг стартовых точек наращиваются следующим критерием однородности:

V = *(aR*Rij + aG*Gij + aB*Bij) + *Gradij, (3) где Rij, Gij, Bij – соответственно значение яркости красного, зеленого и голубого цветов пикселя с координатами (i,j);

Gradij – значение цветного градиента;

aR, aG, aB – коэффициенты (0‹ aR, aG, aB 1), значения aR=aG=aB дают приемлемый результат сегментации;

+ =1, 0, 0.

Этап 4. Постобработка изображения. Мелкие области сливаются с крупными ближайшими областями, согласно критерию однородности. Отдельные пиксели присоединяются к ближайшим по яркости областям.

б) в) г) а) Рис.3. определение стартовых точек: а) полутоновое изображение;

б) края;

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

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

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

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

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

Исходное =0.1 =0.3 =0.5 = 0,1 F1 F 0,1 значение функции оценки 0,1 0,0 0,0 0,0 0,0 0,0 a lfa 0 0,1 0,2 0,3 0,4 0,5 0,6 0,7 0,8 0,9 Рис.4. Сегментация с разными коэффициентами и графики функции оценки Сегментация цветных изображений средствами кластерного анализа.

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

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

Для преобразования исходного изображения в множество векторов-признаков в процессе экспериментальных исследований для каждого пикселя с координатами (i,j) были отобраны следующие девять признаков:

Rij, Gij,Bij – соответственно значения яркости красного, зеленого и синего цветов пикселя с координатами i;

j (1 i m, 1 j n);

GradRij, GradGij, GradBij – значения градиента яркости пикселя вдоль каждой из трех цветовых осей;

DRij = maxRij/minRij – отношение значений максимальной и минимальной разности яркостей красного цвета между пикселем i,j и его соседями в окрестности [3x3];

DGij = maxGij/minGij – отношение значений максимальной и минимальной разности яркостей зеленого цвета между пикселем i,j и его соседями;

DBij = maxBij/minBij – отношение значений максимальной и минимальной разности яркостей синего цвета между пикселем i,j и его соседями (в случае, если minRij =0, DRij = maxRij). Алгоритм состоит из следующих этапов:

Этап 1. Построение признакового описания изображения. Каждому пикселю (i,j) со значениями яркостей (Rij,Gij,Bij) необходимо поставить в соответствие его образ (вектор-признак) Vij:

Vij=(Rij,Gij,Bij,GradRij,GradGij,GradBij,DRij,DGij,DBij) и сформировать множество S, которое состоит из mn образов:

S= {Vij, i=1,2,…m;

j=1,2,…,n}.

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

Этап 2. Кластеризация. Кластеризация признакового пространства осуществляется с помощью алгоритма k–средних.

Этап 3. Постобработка. На сегментированном изображении кластеру в признаковом пространстве могут соответствовать несколько мелких областей.

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

Для большинства изображений из рассматриваемых классов количество кластеров, при котором получается приемлемый результат сегментации, равняется Q=[3,5]. Экспериментально показано, что предложенный алгоритм дает качественные результаты сегментации, согласующиеся с визуальными оценками.

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

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

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

V1ij, V2ij, V3ij – соответственно значения пикселя с координатами i;

j (1im, 1jn) в новой системе координат;

GradV1ij, GradV2ij, GradV3ij – значения градиента пикселя (i,j) вдоль каждой из трех компонент осей.

Исходное Q=3;

=3 Q=4;

=4 Q=5;

= 0,0 F1 F Значение функции оценки 0,0 0,0 0,0 0,0 0,0 0,0 0,0 Q 2 3 4 5 6 7 Рис.5. Сегментация при разных Q и, графики функции оценки Алгоритм состоит из следующих этапов:

Этап 1. Преобразовать систему координат цветового пространства.

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

Этап 2. Признаковое описание изображения. Каждый пиксель исходного изображения описан в пятимерном пространстве (две пространственные координаты (i,j) и три координаты-проекции на главные компоненты изображения, т.е. V1ij,V2ij,V3ij). Для изображения строится шестимерное признаковое пространство. Каждому пикселю ставится в соответствие его образ (вектор признак) Vij:

Vij=(V1ij,V2ij,V3ij, GradV1ij, GradV2ij, GradV3ij) и формируется множество S, которое состоит из mn образов:

S= {Vij, i=1,2,…m;

j=1,2,…,n}.

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

Этап 3. Кластеризация. Осуществляется с помощью алгоритма k–средних.

Этап 4. Постобработка. Выполняется, как в предыдущем алгоритме.

На рис.6 приведен пример, показывающий преимущества данного алгоритма перед предыдущим.

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

Идентификация участков кожи человека на цветных изображениях. Во многих приложениях на этапе предварительной обработки изображений требуется распознать участки человеческой кожи по ее цвету. К таким приложениям относятся идентификация злокачественных опухолей и заболеваний кожи, автоматическая локализация головы человека на фотографии. В последнее время активно разрабатываются алгоритмы ограничения доступа (в школах и некоторых Q=3;

=3 Q=4;

=3 Q=5;

=3 Q=6;

= Исходное Q=3;

=3 Q=4;

=4 Q=5;

=4 Q=6;

= 0,1 Значение функции оценки 0, К л астери заци я в 0,0 8 RGB К л астери заци я в 0,0 V1V2V 0,0 0,0 2 3 4 5 6 7 8 Q Рис.6. Сегментация путем кластеризации: в пространствах RGB (первая строка), главных компонент (вторая) и графики функций оценки организациях) к сайтам в сети Интернет, содержащим эротические изображения.

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

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

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

Этап 2. Проверить условия Rij Gij Bij 20 & Rij80.

Этап 3. Вычислить признаки Tij, Sij, R_Gij, G_Bij, R_Bij и 2R_G_Bij:

T = arcsin( 3/2 (R - G )/S ) ;

ij ij ij ij S = R 2 + G 2 + B 2 B G B R G R ;

ij ij ij ij ij ij ij ij ij ij R_Gij=Rij/Gij;

G_Bij=Gij/Bij;

R_Bij=Rij/Bij;

где Rij, Gij, Bij – значения яркости красного, зеленого и голубого цветов пикселя a(i,j) отфильтрованного изображения;

T – цветовой тон;

S – насыщенность.

Полученные величины используются в качестве признаков hk: h1=Tij, h2=R_Gij, h3=G_Bij, h4=R_Bij, h5=2R_G_B.

Этап 4. Для каждого пикселя исходного изображения вычисляется значение k zij(h ) вероятности его принадлежности к области, представляющей человеческую кожу согласно признаку hk. Значение zij(hk) вычисляется следующим образом:

(H k - h k )/(H k - Sk ), если Sk h k H k, 2 ij 2 ij z (h k ) = (h k - H k )/(Sk - H k ), если H k h k Sk, ij ij 1 1 1 ij 0, если h k H k или h k H k, ij 2 ij где [H1k,H2k] – экспериментально найденный интервал изменения значений каждого признака hk (k=1,2,..,5), соответствующих цвету человеческой кожи;

Sk – чаще всего встречаемое значение признака hk в данном интервале (экспериментально определенное). Считаем, что zij(Sk)=1, т.е. пиксель (i,j), в котором признак hk=Sk, относится к области человеческой кожи с вероятностью, равной 1.

Этап 5. Вычислит значение Zij для каждого пикселя (i,j), равное сумме значений zij(hk) для всех признаков hk:

Z = z (h k ) ij ij k = Если Zi,j1, считаем данный пиксель относящимся к участку кожи. Пиксели, не удовлетворяющие условиям, описанным на этапах 1-5, считаются не относящимися к участкам кожи.

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

В третьей главе описаны экспериментальные исследования разработанных алгоритмов сегментации цветных изображений. Целью экспериментов было выяснить, как и при каких параметрах следует комбинировать алгоритмы для получения более качественных результатов сегментации, а также найти способ автоматической оценки результата сегментации для автоматического выбора параметров. Алгоритмы сегментации тестировались на 500 цветных изображениях четырех классов (“портрет”, “ландшафт”, “космические изображения” и “медицинские изображения”), описанные в пространстве RGB, в котором каждый базовый цвет имел 256 оттенков. В экспериментах использовались изображения размерами от 128128 до 256256 пикселей разных форматов (BMP, JPG, TIFF и др.).

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

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

белые области соответствуют участкам кожи человека, черные – всему остальному.

Результаты сегментации разработанным соискателем алгоритмом показаны во второй строке, в третьей строке – результаты сегментации алгоритмом Pitas, в четвертой – алгоритмом Umbraugh.

Приложение содержит акты внедрения результатов диссертационной работы.

Таблица 1.

Приемлемый диапазон значений и рекомендуемые значения для некоторых классов изображений Класс изображения Приемлемый диапазон Портреты [0.3, 0.5] 0. Снимки из космоса [0.1, 0.5] 0. Медицинские изображения [0.1, 0.3] 0. Ландшафт [0.2, 0.6] 0. Таблица 2.

Приемлемый диапазон количества кластеров и рекомендуемые значения для некоторых классов изображений Класс изображения Приемлемый диапазон Портреты [3, 6] Снимки из космоса [3, 5] Медицинские изображения [2, 3] Ландшафт [3, 6] Рис.7. Сегментация цветных изображений (левый столбец) на области кожи (показано белым цветом) и все остальные (показано черным). Второй столбец – результат работы предложенного алгоритма, третий и четвертый – известных в литературе ЗАКЛЮЧЕНИЕ 1. Выполнен обзор литературы по сегментации цветных изображений и показано, что большинство алгоритмов сегментации, разработанных для полутоновых изображений, затруднительно адаптировать для сегментации цветных изображений. Комбинирование различных алгоритмов обработки изображений является перспективным путем решения задач сегментации цветных изображений и позволяет добиться улучшения качества сегментации. Описана общая технология сегментации цветных изображений, состоящая из четырех основных этапов:

предобработка, алгоритм сегментации, постобработка и аналитическая оценка результатов сегментации [7].

2. Разработан алгоритм преобразования цветных изображений в полутоновые, который в качестве полутонового варианта принимает проекцию исходного изображения на главную ось новой системы координат, полученной методом главных компонент. Данный алгоритм отличается от существующих тем, что он учитывает индивидуальные характеристики каждого отдельного цветного изображения и поэтому ориентирован на сегментацию изображений [6].

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

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

4. Предложен и исследован алгоритм сегментации цветных изображений, отличающийся использованием методов кластерного анализа яркостных характеристик изображения. Для большинства изображений из рассматриваемых классов количество кластеров, при котором получается приемлемый результат сегментации, равняется 3-5. Экспериментально показано, что предложенный алгоритм дает качественные результаты сегментации, согласующиеся с визуальными оценками [2].

5. Разработан алгоритм сегментации цветных изображений с применением кластеризации в пространстве главных компонент изображения. Алгоритм преобразует исходное цветное изображение в пространство главных компонент, что упрощает разделимость кластеров, соответствующих однородными областями на исходном изображении, и способствует получению более качественной сегментации изображения [5] по сравнению с алгоритмом сегментации с применением кластеризации в цветовом пространстве RGB.

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

Проведено сравнение алгоритма с известными алгоритмами и экспериментально показаны его преимущества перед ними [3,6].

СПИСОК ОПУБЛИКОВАННЫХ РАБОТ ПО ТЕМЕ ДИССЕРТАЦИИ Статьи в журналах и сборниках 1. Талеб М.А., Старовойтов В.В. О сегментации цветных изображений// Известия Национальной академии наук Беларуси. Сер. технические науки.–Минск.

–2000.-№ 1.-С.107-111.

2. Талеб М.А., Старовойтов В.В. Алгоритм сегментации цветных изображений средствами кластерного анализа// Цифровая обработка изображений.

- Минск: Ин-т техн. кибернетики НАН Беларуси, 2000.Вып.4.-С.107-116.

3. Талеб М.А., Старовойтов В.В. Алгоритм идентификации участков кожи человека на цветных изображениях// Цифровая обработка изображений. - Минск:

Ин-т техн. кибернетики НАН Беларуси, 2001.Вып.5.-С.151-157.

Тезисы докладов и материалы конференций 4. Талеб М. А. Комбинированный алгоритм сегментации цветных изображений// Proc. of 5th Int. Conf. “Pattern recognition and Information processing”. Minsk.- 1999. -Vol.2.-P.163-167.

5. Талеб М.А. Сегментация цветных изображений методами главных компонент и кластерного анализа //Мат. междунар. конф. “VIII Белорусская математическая конференция”. –Минск.- 2000.-Ч. 3.-С.177.

6. Samal D.I., Taleb M.A., Starovoitov V.V. Experiments with preprocessing of human portraits// Proc. of 6th Int. Conf. “Pattern recognition and Information processing”.- Minsk.-2001.-Vol. 2.-P.15-20.

Препринт 7. Старовойтов В.В., Талеб М.А. Методы сегментации цветных изображений.– Минск, 1999. – 44c. – (Препринт/ Ин-т техн. кибернетики НАНБ;

N.1).

РЕЗЮМЕ диссертационной работы Ульд Ахмеда Талеба Махфуда «Комбинированные алгоритмы сегментации цветных изображений».

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

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

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

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

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

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

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

РЭЗЮМЭ дысертацыйнай працы Ульд Ахмеда Талеба Махфуда «Камбінаваныя алгарытмы сегментацыі каляровых відарысаў» Ключавыя словы: алгарытм сегментацыі, каляровыя і паўтонавыя відарысы, камбінаванне алгарытмаў, нарошчванне абласцей, кластэрызацыя, галоўныя кампаненты, ідэнтыфікацыя скуры чалавека.

Дысертацыйная праца прысвечана праблеме сегментацыі каляровых відарысаў. Яе мэтаю з’яўляецца даследаванне спосабаў камбінавання алгарытмаў для забеспячэння якаснай сегментацыі каляровых відарысаў розных класаў.

Распрацаваны алгарытм пераўтварэння каляровых відарысаў у паўтонавыя з прымяненнем праекцыі галоўнай кампаненты відарыса. Распрацаваны алгарытм сегментацыі каляровых відарысаў, які камбінуе нарошчванне абласцей з градыентам яркасці, у якім зыходныя кропкі вызначаюцца аўтаматычна, а крытэрый аднароднасці ўлічвае градыентную інфармацыю пры нарошчванні абласцей.

Распрацаваны алгарытм сегментацыі каляровых відарысаў з выкарыстаннем кластэрнага аналізу. Знойдзены найбольш інфарматыўныя прыкметы, якія дазваляюць атрымаць якасныя вынікі сегментацыі.

Распрацаваны алгарытм сегментацыі каляровых відарысаў з прымяненнем кластэрызацыі ў прасторы галоўных кампанентаў відарысаў. Вызначана дапушчальная колькасць кожнага класа для алгарытмаў з прымяненнем кластэрызацыі.

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

Атрыманыя ў дысертацыйнай працы вынікі даказваюць магчымасць павышэння якасці сегментацыі шляхам камбінавання розных падыходаў.

SUMMARY of the Ph.D. thesis "Combined algorithms of color images segmentation" by Mahfoudh Ould Ahmed Taleb Key words: segmentation algorithm, color and gray images, combination, area growing, clustering, principal component, human skin segmentation.

The thesis is devoted to color image segmentation problem. The aim of the research is a development of color image segmentation algorithms by combination of different image processing approaches, to ensure a qualitative segmentation of color images from different classes.

A new algorithm for transformation of color images to gray images is developed. It use the projection of the color image into its main component as a gray version of the color image.

A new algorithm for color image segmentation by combination of the pixel gray value and gradient in a uniform criteria is developed. Seed points are automatically located. A new algorithm for color image segmentation, which uses cluster analysis in RGB is developed, and features allowing to receive the most qualitative color image segmentation are found.

A new algorithm for color image segmentation which uses cluster analysis and principal component analysis is developed. The acceptable number of clusters for studied image classes are found.

A new human skin segmentation algorithm for color images is developed. It uses a color space transform and fuzzy functions to estimate probability of a skin pixel membership in accordance to experimentally obtained features. Its comparison with known algorithms is carried out and its advantages before them are experimentally shown.

The received results demonstrate a possibility to improve a color image segmentation quality by combination of various image processing algorithms.