где Grayij – яркость пикселя с координатами (i,j) в полутоновом представлении исходного цветного изображения; Rij, Gij, Bij – значения яркости красного, зеленого и синего цветов.
Государственное научное учреждение «Институт технической кибернетики Национальной Академии наук Беларуси»
Источник информации: http://neuroface.narod.ru/files/mahfoudh_autoref.pdf
Актуальность. Сегментация визуальной информации является предварительным этапом любой системы обработки изображений, так как позволяет упростить последующий анализ однородных областей изображения, их яркостных и геометрических характеристик. Сегментацию следует рассматривать как начальный этап построения формального описания сцены, качество выполнения которого во многом определяет успех решения задачи распознавания изображений, интерпретации и идентификации визуально наблюдаемых объектов.
Для решения задачи сегментации полутоновых изображений было разработано много методов и алгоритмов. В последние годы все больше визуальная информация регистрируется в виде цветных изображений. Сегментация цветных изображений является более сложной задачей, чем полутоновых. Так, если в полутоновом изображении пиксель может иметь 256 оттенков яркости, в случае цветного изображения пиксель может иметь один из 256 оттенков яркости каждого из трех цветов, что делает количество возможных цветов равным (256)3=16 777 216, поэтому возникают трудности при адаптации известных алгоритмов сегментации полутоновых изображений для обработки цветных.
На практике алгоритмы сегментации цветных изображений применяются в разных задачах, например, для анализа качества продукции, определения площади наводнения, прогнозирования урожайности, распознавания лесных пожаров, вычисления высоты прилива с помощью аэрофотоснимков, распознавания печатного и рукописного текста. Еще одним важным применением этих алгоритмов является распознавание участков кожи человека на фотоснимках. К таким задачам относятся идентификация злокачественных опухолей и заболеваний кожи, автоматическая локализация головы человека на фотографии в системах распознавания и т.п. Существующие решения не всегда дают удовлетворительный (качественный) результат, поэтому необходимы новые решения с использованием базовых подходов сегментации и их комбинирования. Кроме того, качество результатов сегментации часто оценивают визуально. Для автоматического сравнения полезно иметь аналитическую меру, позволяющую численно оценить различные варианты сегментации, исследовать их, выбрать конкретные параметры критериев однородности каждого алгоритма, а также сравнить различные алгоритмы сегментации между собой, что позволяет рекомендовать конкретную комбинацию алгоритмов для разных классов цветных изображений.
За последнее десятилетие бурно развивается всемирная сеть Интернет, которая содержит огромное число цветных изображений, увеличивающееся по мере расширения самой сети. Установлено, что около 50% изображений в Интернете содержит изображения людей. Это делает сегментацию цветных изображений, и в частности идентификацию человеческой кожи, весьма актуальной задачей для ограничения доступа к некоторым сайтам.
Таким образом, разработка и исследование алгоритмов сегментации цветных изображений является актуальной задачей.
Цель и задачи исследования. Целью работы является исследование
способов комбинирования алгоритмов для обеспечения качественной сегментации
цветных изображений разных классов. Достижение поставленной цели
потребовало разработки:
- алгоритма преобразования цветных изображений в полутоновые,
максимально сохраняющего индивидуальные особенности изображения;
- алгоритма сегментации путем наращивания областей с использованием
градиентной информации;
- алгоритма сегментации средствами кластерного анализа;
- алгоритма сегментации, комбинирующего кластерный анализ и метод
главных компонент;
- алгоритма идентификации участков человеческой кожи.
Научная новизна полученных результатов
- Разработан алгоритм преобразования цветных изображений в полутоновые,
отличающийся от известных тем, что цветное изображение проектируется не на
фиксированную ось, а на ось, совпадающую с главной компонентой изображения,
которая индивидуальна у каждого изображения.
- Разработан алгоритм сегментации цветных изображений, использующий
градиентную информацию для наращивания областей. Он отличается от
классического наращивания областей тем, что в критерии принадлежности пикселя
области комбинируются яркость и градиент яркости, а стартовые точки
определяются автоматически. Это позволяет улучшить качество сегментации без
существенного проигрыша во времени.
- Разработан алгоритм сегментации цветных изображений средствами
кластерного анализа, использующий в качестве признаков яркости трех цветов, их
градиенты и другие признаки полученных путем анализа яркостей в окрестности
обрабатываемого пикселя, что в отличие от других алгоритмов дает более
качественный результат сегментации.
- Разработан алгоритм сегментации цветных изображений с применением
кластеризации в пространстве главных компонент изображения. В результате
упрощается разделимость кластеров в признаковом пространстве, что способствует
получению более качественной и быстрой сегментации изображения.
- Разработан алгоритм идентификации участков кожи человека на цветном
изображении, отличающийся от существующих использованием функций
принадлежности нечеткому множеству для оценки степени принадлежности
пикселя к области, представляющей кожу.
Методы исследования. Теоретические методы исследования основывались на методах цифровой обработки изображений, распознавания образов, дискретных преобразований и системного анализа. Экспериментальная часть исследования базировалась на обработке и анализе цифровых изображений с помощью ЭВМ с последующей численной и визуальной оценкой результатов. Для программной реализации разработанных алгоритмов использовались методы создания программных систем и программирование на языках высокого уровня, моделирование с помощью специализированных пакетов обработки данных и изображений.
Практическая значимость полученных результатов. Разработанные алгоритмы могут использоваться в системах обработки и распознавания цифровых изображений на этапе предварительной обработки исходных изображений, например, в системах распознавания изображений людей на этапе автоматической локализации головы человека на изображении для его последующего распознавания. В школах для ограничения доступа к сайтам Интернета, содержащим фотографии обнаженных тел, можно использовать алгоритм сегментации по цвету кожи. В медицинских системах автоматизированной диагностики можно применять сегментацию для идентификации злокачественных опухолей и заболеваний кожи. В геоинформационных системах сегментация цветных изображений используется на этапе предварительной обработки космических изображений и аэрофотоснимков для определения площадей полей, наводнений, пожаров и т.п. В издательском деле во многих книгах и газетах изображения печатаются в черно-белом формате, поэтому для них цветные изображения могут быть преобразованы в полутоновые с помощью алгоритмов, описанных в диссертации.
Разработанные алгоритмы используются на Научно-инженерном республиканском унитарном предприятии «Геоинформационные системы» для обработки цветных изображений, полученных с помощью спутника NOAA.
Алгоритмы преобразования цветных изображений в полутоновые и алгоритмы сегментации были программно реализованы и переданы НПП «Регула» для применения в системе контроля подлинности денежных знаков для автоматической идентификации бумажной подложки на цветных изображениях банкнот.
Алгоритмы, описанные в диссертационной работе, используются в учебном процессе в Белорусском государственном университете информатики и радиоэлектроники и в Белорусском государственном техническом университете.
Основные положения диссертации, выносимые на защиту:
- Алгоритм преобразования цветных изображений в полутоновые.
- Алгоритм сегментации путем наращивания областей с использованием
градиентной информации.
- Алгоритм сегментации средствами кластерного анализа.
- Алгоритм сегментации цветных изображений, комбинирующий кластерный
анализ и метод главных компонент.
- Алгоритм идентификации участков человеческой кожи на цветных
изображениях.
Во введении обоснована актуальность и практическая значимость темы диссертационной работы и определены основные задачи исследования.
В первой главе дан обзор методов цифровой обработки цветных изображений. Здесь рассмотрены основные характеристики цветных изображений и определены классы цветных изображений. Рассмотрены разные системы описания цветных изображений и приведена классификация существующих методов сегментации полутоновых и цветных изображений. Сформулированы задачи исследований. Сделаны выводы о важности сегментации изображений как предварительном этапе обработки изображений, о том, что система RGB является наиболее удобной для представления цветных изображений для их сегментации, о сложности в адаптации алгоритмов сегментации полутоновых изображений для цветных и о том, что алгоритмы сегментации цветных изображений следует комбинировать для достижения лучшего качества сегментации.
Вторая глава посвящена сегментации цветных изображений. В ней описана технология сегментации цветных изображений, приведены разработанные алгоритмы. В разделе 2.1 предложена общая схема сегментации, которая включает предобработку исходного цветного изображения, сегментацию, постобработку и оценку результатов. Даны рекомендации по выбору процедур предобработки и постобработки для каждого алгоритма. Исследованы следующие варианты предобработки.
Фильтрация, ориентированная на сегментацию. Эта операция применялась для устранения шумов на изображении и подготовки его к сегментации. В данной главе были исследованы макс-мин, медианные, усредняющие фильтры разных окрестностей. При применении фильтров к цветным изображениям обрабатывался отдельно каждый из базовых цветов, а результат рассматривался как новое цветное изображение.
Преобразование системы цветовых координат. Были применены
преобразования систем координат RGB в HSV, TLS, (R/G, R/B,G/B), (2R-G-B) и
описан новый алгоритм преобразования цветных изображений в полутоновые.
Алгоритм позволяет определить новые оси координат в пространстве цветности и
выбрать первую главную компоненту в качестве оси для проекции цветного
изображения и получения его полутонового варианта. Традиционные полутоновые
преобразования хорошо передают интенсивность цветного изображения, однако в
случае наличия пикселей с разными цветами, но с примерно одинаковой
интенсивностью полутоновое изображение будет представлять однотонную
картину. Цветное изображение часто преобразуется в полутоновое с помощью
следующих формул:
где Grayij – яркость пикселя с координатами (i,j) в полутоновом представлении
исходного цветного изображения; Rij, Gij, Bij – значения яркости красного, зеленого
и синего цветов.
Алгоритм преобразования цветного изображения в его полутоновый вариант
состоит из следующих шагов.
- Цветное изображение размером M?N, заданное в системе координат RGB,
представлять в виде трех векторов каждый длиной M?N.
- Вычислить ковариационную матрицу изображения, ее собственные значения
exy, x, y = 1,2,3.
- Определить оси новой системы координат.
- В качестве полутонового варианта принимать проекцию исходного
изображения на главную ось.
На рис.1 показаны преобразования искусственного цветного изображения областями красного, зеленого и голубого цвета в полутоновое с помощью данного алгоритма и формул (1)-(2).
Постобработка. После сегментации изображение часто имеет ряд недостатков
в виде мелких областей, линий и отдельных пикселей, не отнесенных ни к какой
области. В зависимости от характера недостатка на сегментированном
изображении следует применять процедуры слияния областей и фильтрации
изображения.
Слияние. Маленькая область (количество пикселей которой меньше заданного порога) присоединяется к ближайшей к ней по яркости большой области. Одиночный пиксель добавляется к ближайшей к нему по яркости области или анализируется принадлежность пикселей его окрестности к соседним областям и принимается решение о его добавлении к той области, к которой принадлежит большинство его соседей. Этот вид постобработки рекомендован для алгоритмов наращивания областей и алгоритмов с применением кластерного анализа, так как часто в результате их работы получим мелкие области или пиксели, не отнесенные ни к какой области. Пример постобработки сегментированного изображения показан на рис.2.
Морфологическая фильтрация. К бинарному изображению применяются
последовательно такие операции математической морфологии, как расширение
(дилатация) и сжатие (эрозия). Такая фильтрация является наиболее эффективной
процедурой для алгоритмов сегментации кожи человека.
Оценка результатов сегментации. Результаты сегментации изображений часто оцениваются визуально. Для автоматического сравнения полезно иметь аналитическую меру, позволяющую численно оценить различные варианты сегментации, а также сравнить различные алгоритмы сегментации между собой. В результате анализа литературы найдены три меры, которые были использованы для анализа результатов сегментации цветных изображений.
Мера сходства цветных изображений. В литературе была описана идея, как сравнить цветные изображения. В диссертационной работе эта идея была развита и конкретизирована для оценки результатов сегментации и сравнения алгоритмов сегментации.
Для сравнения исходного и сегментированного изображений необходимо представить последнее в виде псевдоцветного изображения. Для этого каждая область сегментированного изображения раскрашивается средним цветом соответствующей области исходного изображения. Сегментированные изображения сравнивают с исходным изображением или с сегментируемым изображением идеального алгоритма, в результате чего для каждого алгоритма получаем числовую оценку сходства сегментируемого и идеального изображений. Наименьшая оценка указывает на лучший алгоритм сегментации.
Пусть A={Aij} обозначает цветное изображение, Aij={rij a,gija,bija} – пиксель, имеющий координаты i,j, и rija,gija,bija – яркость соответственно красного, синего и зеленого цветов пикселя, где 0 < i,j <= N, 0 <= rija,gija,bija <= Z = 255, NxN – размер изображения и Z – максимальное значение каждой компоненты цвета. C – результат сегментации, являющийся псевдоцветным изображением (т.е. пиксель имеет средний цвет области, к которой он относится).
Глобальное несходство между изображениями A и С может быть вычислено
с помощью функции, предложенной Старовойтовым:
Для уменьшения влияния шума использована фильтрация локального
расстояния от пикселя Aij изображения A к изображению С:
Аналогично вычисляется
d(Сij,A). Функция F1 принимает значения в диапазоне [0,1].
В качестве базовой функции расстояния d могут быть использованы метрики:
В качестве оценки результата сегментации цветных изображений исследована
функция Лью и Янг (Liu, Yang)
Функцию можно модифицировать следующим образом:
где R(A) – количество областей, площадь каждой из которых равняется A.
В разделах 2.2-2.5 описаны четыре комбинированных алгоритма сегментации, разработанные с целью повышения качества сегментации с помощью комбинирования некоторых базовых алгоритмов обработки и сегментации изображений. В число разработанных алгоритмов входят алгоритмы наращивания областей с применением градиентной информации, сегментации с применением кластерного анализа, сегментации с применением кластерного анализа и метода главных компонент и распознавания участков человеческой кожи на цветных изображениях.
Наращивание областей с применением градиентной информации. Метод наращивания областей основан на использовании для целей сегментации локальной признаковой информации и выборе некоторого числа стартовых точек, вокруг которых наращиваются области. Цветное изображение преобразуется в полутоновое, для определения стартовых точек вычисляется градиент функции яркости в каждом пикселе изображения (например, оператором Робертса). Результатом применения этого оператора является матрица MxN, содержащая значения градиента яркости в каждом пикселе полутонового изображения. К матрице градиентов применяется пороговое преобразование для выделения краевых точек изображения. Его результатом является бинарное изображение размером MxN, в котором единицы соответствуют краевым точкам. К бинарному изображению применяется дистанционное преобразование (шахматная метрика). Результатом дистанционного преобразования является матрица таких же размеров (матрица расстояний), в которой элемент (i,j) содержит расстояние от пикселя (i,j) бинарного изображения до ближайшего краевого пикселя. В качестве стартовых точек принимаются локальные максимумы матрицы расстояний.
Стартовые точки размечаются определенным образом, и осуществляется анализ соседних точек. Если для пары точек (например, стартовой и соседней с ней) выполняется условие однородности, то соседняя точка получает ту же метку, что и стартовая. Далее рассматриваются соседи соседей и процесс разметки производится аналогично. Наращивание завершается после того, как каждая точка изображения получает какую-либо метку. Однако наращивание областей с учетом только яркости часто приводит к ошибочному добавлению множества точек в наращиваемую область. Для исключения такой ситуации был разработан алгоритм сегментации, который использует критерий однородности, комбинирующий яркость пикселя и градиент яркости. Степень участия яркости и градиента регулируется коэффициентами альфа и бетта (формула 3).
Алгоритм сегментации состоит из следующих этапов:
Этап 1. Преобразование цветного изображения в полутоновое. Выполнить преобразование с помощью алгоритма преобразования цветного изображения в полутоновое, описанного выше.
Этап 2. Автоматический поиск стартовых точек. Определить стартовые точки (этапы определения стартовых точек показаны на рис.3).
Этап 3. Сегментация методом наращивания областей. Области вокруг
стартовых точек наращиваются следующим критерием однородности:
Этап 4. Постобработка изображения. Мелкие области сливаются с
крупными ближайшими областями, согласно критерию однородности. Отдельные
пиксели присоединяются к ближайшим по яркости областям.
Этап 5. Оценка результатов сегментации. С помощью функции сходства результаты сегментации с разными коэффициентами альфа и бетта сравниваются с исходным изображением. Результат, для которого функция сходства показывает минимум, считается лучшим. Пример сегментации методом наращивания областей с разными коэффициентами ? и график функций оценки показаны на рис.4. Результат, полученный при альфа, равном 0.3, является визуально наилучшим, что подтверждается минимумом функций оценки. При альфа равном 1 результат соответствует применению стандартного алгоритма наращивания областей. Сравнение с алгоритмом наращивания областей показало, что комбинирование дает результаты более качественные, чем результаты алгоритма наращивания в отдельности, а время их выполнения примерно одинаково.
Алгоритм отличается от существующих следующим: а) критерий однородности
учитывает значение яркости и модуль градиента яркости пикселя, что не позволяет
перейти границу наращиваемой области за счет большого модуля градиента в
граничных точках области; б) стартовые точки определяются автоматически путем
обработки исходного изображения градиентным оператором, применения
дистанционного преобразования и поиска локальных максимумов.
Сегментация цветных изображений средствами кластерного анализа. Задачу сегментации можно рассматривать как задачу поиска кластеров, соответствующих однородным областям. Каждому пикселю изображения ставится в соответствие вектор-признак и выполняется кластеризация в пространстве этих признаков. Область формируется из пикселей, векторы-признаки которых вошли в соответствующий кластер.
Для преобразования исходного изображения в множество векторов-признаков в процессе экспериментальных исследований для каждого пикселя с координатами (i,j) были отобраны следующие девять признаков:
Rij, Gij,Bij – соответственно значения яркости красного, зеленого и синего цветов пикселя;
DRij – отношение значений максимальной и минимальной разности яркостей красного цвета между пикселем i,j и его соседями в окрестности [3x3];
DGij – отношение значений максимальной и минимальной разности яркостей зеленого цвета между пикселем i,j и его соседями;
DBij – отношение значений максимальной и минимальной разности яркостей синего цвета между пикселем i,j и его соседями (в случае, если min=max).
Алгоритм состоит из следующих этапов:
Этап 1. Построение признакового описания изображения. Каждому пикселю
(i,j) со значениями яркостей (Rij,Gij,Bij) необходимо поставить в соответствие его
образ (вектор-признак) Vij:
и сформировать множество S, которое состоит из m x n образов.
Этап 2. Кластеризация. Кластеризация признакового пространства осуществляется с помощью алгоритма k–средних.
Этап 3. Постобработка. На сегментированном изображении кластеру в признаковом пространстве могут соответствовать несколько мелких областей. Поэтому требуется постобработка полученных результатов, которая заключается в следующем. Анализируются всевозможные пары кластеров, и вычисляются расстояния между их центрами. Вычисляется среднее расстояние ds между кластерами. Если расстояние между центрами двух кластеров меньше чем среднее расстояние ds, и при этом количество образов, входящих в один из кластеров, меньше одной трети количества пикселей другого кластера, то такие кластеры объединяются в один. В случае объединения вычисляется центр вновь созданного кластера и пересчитываются расстояния между центрами кластеров. В результате этого количество кластеров уменьшается.
Сегментация цветных изображений с учетом главных компонент
изображения и результатов кластерного анализа. Метод главных компонент
позволяет перейти к новой системе координат с ортогональными и максимально
некоррелированными осями, в которой улучшаются условия разделимости
кластеров. Алгоритм сегментации аналогичен алгоритму, описанному выше.
Отличие состоит в том, что в данном алгоритме для исходного изображения
сначала вычисляются главные компоненты и проекция изображения на них, а
признаки для кластеризации выбираются в новой системе координат. В результате
экспериментального исследования были определены следующие шесть признаков:
V1ij, V2ij, V3ij – соответственно значения пикселя с координатами i;j (1<=i<=m, 1<=j<=n)
в новой системе координат; GradV1ij, GradV2ij, GradV3ij – значения градиента
пикселя (i,j) вдоль каждой из трех компонент осей.
Алгоритм состоит из следующих этапов:
Этап 1. Преобразовать систему координат цветового пространства. Вычислить главные компоненты изображения, использовать их в качестве новых осей для описания изображения.
Этап 2. Признаковое описание изображения. Каждый пиксель исходного изображения описан в пятимерном пространстве (две пространственные координаты (i,j) и три координаты-проекции на главные компоненты изображения). Для изображения строится шестимерное признаковое пространство. Каждому пикселю ставится в соответствие его образ (вектор- признак) и формируется множество S, которое состоит из m x n образов. В нем каждый образ соответствует одному пикселю исходного изображения.
Этап 3. Кластеризация. Осуществляется с помощью алгоритма k–средних.
Этап 4. Постобработка. Выполняется, как в предыдущем алгоритме. На рис.6 приведен пример, показывающий преимущества данного алгоритма перед предыдущим.
Алгоритм преобразует исходное цветное изображение методом главных
компонент, в результате получается описание исходного изображения в новой
системе координат и улучшается разделимость кластеров, что способствует
получению качественной кластеризации.
Идентификация участков кожи человека на цветных изображениях. Во многих приложениях на этапе предварительной обработки изображений требуется распознать участки человеческой кожи по ее цвету. К таким приложениям относятся идентификация злокачественных опухолей и заболеваний кожи, автоматическая локализация головы человека на фотографии. В последнее время активно разрабатываются алгоритмы ограничения доступа (в школах и некоторых организациях) к сайтам в сети Интернет, содержащим эротические изображения. Подобные алгоритмы выделяют связные области пикселей, имеющих “цвет кожи". Эта задача нетривиальна, поскольку на изображении кожа даже одного и того же человека выглядит по-разному в разное время года, при разном освещении. Кроме того, люди разных рас имеют разные цвета кожи. Исходными данными в подобных задачах являются цветные изображения. Целью обработки является разделение или сегментация изображения на участки двух типов: области, соответствующие по цвету коже человека, и все остальные. Известные алгоритмы решения данной задачи носят эвристический характер и часто дают неудовлетворительные результаты. Разработанный в диссертационной работе алгоритм обобщает различные эмпирически найденные закономерности. Он состоит из следующих этапов.
Этап 1. Выполнить фильтрацию исходного изображения. Например, min- фильтром и затем max-фильтром (результат является аналогом морфологической операции отмыкания).
Этап 2. Проверить условия Rij > Gij> Bij > 20 & Rij>80.
Этап 3. Вычислить признаки Tij, Sij, R_Gij, G_Bij, R_Bij и 2R_G_Bij
Этап 4. Для каждого пикселя исходного изображения вычисляется значение
zij(hk) вероятности его принадлежности к области, представляющей человеческую
кожу согласно признаку hk. Значение zij(hk) вычисляется следующим образом:
Этап 5. Вычислит значение Zij для каждого пикселя (i,j), равное сумме
значений zij(hk) для всех признаков hk:
Если Zij>1, считаем данный пиксель относящимся к участку кожи. Пиксели, не
удовлетворяющие условиям, описанным на этапах 1-5, считаются не относящимися
к участкам кожи.
Проведено сравнение алгоритма с известными алгоритмами, и
экспериментально показано, что предложенный алгоритм дает более качественные
результаты по сравнению с ними.
В третьей главе описаны экспериментальные исследования разработанных алгоритмов сегментации цветных изображений. Целью экспериментов было выяснить, как и при каких параметрах следует комбинировать алгоритмы для получения более качественных результатов сегментации, а также найти способ автоматической оценки результата сегментации для автоматического выбора параметров. Алгоритмы сегментации тестировались на 500 цветных изображениях четырех классов (“портрет”, “ландшафт”, “космические изображения” и “медицинские изображения”), описанные в пространстве RGB, в котором каждый базовый цвет имел 256 оттенков. В экспериментах использовались изображения размерами от 128?128 до 256?256 пикселей разных форматов (BMP, JPG, TIFF и др.).
Экспериментально определены параметры алгоритмов, при которых достигается лучшее качество сегментации изображений для каждого класса изображений. Алгоритм сегментации с помощью комбинирования значений яркости и градиентной информации дает более качественные результаты, чем при использовании одной яркости в критериях однородности областей. В таблице 1 приведены приемлемый диапазон и рекомендуемые значения ? для некоторых классов изображений.
Для алгоритмов сегментации с применением кластерного анализа с помощью функций оценки определено исходное количество кластеров, при котором получается лучшее качество сегментации для каждого класса изображений.