Software & Systems

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

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

В соответствии с общим феноменологическим подходом, разрабатываемым в НИИСИ РАН и реализованным в системе PICASSO (PICture Algorithms Study SOftware), в данной работе проводится сравнительное исследование качества четырех известных методов сегментации на совокупности искусственных тестовых изображений с априорно заданным решением задачи.

Смысл сегментации изображений

Основными понятиями в тематике сегментации изображений на основе некоторой однородности являются сегмент, регион, сегментная карта, границы. При работе программы сегментации создается новое изображение – сегментная карта, содержащая области равномерной закраски. Если исходный рисунок имеет значительное количество градаций яркости (например 256), в типичном случае полученный рисунок с сегментной картой имеет существенно меньшее количество градаций яркости (например 3–5). Такие области на сегментной карте называются сегментами. При наложении сегментной карты на исходное изображение границы ее сегментов оконтуривают области исходного изображения, которые называются регионами. Сегментация – это построение сегментной карты и разбиение исходного изображения на регионы (рис. 1, [1]).

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

Тестируемые методы сегментации

Для тестирования были выбраны четыре метода сегментации: EDISON, JSEG, EDGEFLOW и MULTISCALE.

Сегментатор EDISON [2]. Программная система EDISON (Edge Detection and Image SegmentatiON) выполняет сегментацию изображений, выделение границ, а также фильтрацию шума, сохраняющую резкие перепады яркости изображения. В этом методе определяются границы на изображении и используются в процессе сегментации.

Одним из основных параметров метода является минимальный размер региона в пикселах, который может создать данный метод. При тестировании брались значения этого параметра 100 и 1000 и методы обозначались как EDISON 100 и EDISON 1000.

Сегментатор JSEG [1]. Метод предназначен для автоматической сегментации изображений и видео, которые могут содержать цветные регионы и текстуры. Обработка изображения методом JSEG состоит из двух независимых шагов: цветовой квантизации и пространственной сегментации. Чтобы получить сегментацию всего изображения, применяется метод растущих областей.

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

Сегментатор EDGEFLOW [3]. Для сегментации и выделения границ изображения используется метод потока граничных точек (edgeflow). При этом в каждой точке изображения вычисляется направление изменения яркости, цвета или текстуры. Так формируется векторное поле потока граничных точек. Интегральные кривые этого поля проходят через области изображения, образуя гомогенные регионы, сталкиваются друг с другом и стабилизируются, образуя границы регионов.

Данный метод имеет параметр «смещение», очень существенно влияющий на работу. (Далее в статье после названия метода указывается выбранное значение смещения – например EDGEFLOW 26.)

Сегментатор MULTISCALE [4]. При обработке методом MULTISCALE изображение вначале анализируется в более грубом масштабе, а затем в более мелком. При рассмотрении изображения в грубом масштабе шум и помехи малозаметны, а в более мелком – лучше заметны детали объектов. Объединение этих подходов позволяет фильтровать шум и сохранять важные детали изображения.

a) b) c)

Рис. 1. Пример сегментации изображения: исходное изображение(a), сегментная карта (b), исходное изображение с регионами и границами (c)

Метод имеет много параметров: число шкал – масштабов, точность постобработки и др. В описании метода некоторые значения параметров рекомендованы как безопасные. Они и были взяты при тестировании.

Наборы искусственных изображений и методики тестирования

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

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

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

По вертикали яркость неизменна, она изменяется в горизонтальном направлении. Яркость изображений слева равна нулю, справа – значению, являющемуся параметром семейства. Возрастание яркости линейное, с точностью до дискретизации. Значения яркости – целые числа от 0 до 255.

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

В качестве примера на рисунке 3 показан результат сегментации трех изображений, в которых яркость линейно нарастает от 0 на левой стороне квадрата до, соответственно, 10, 100, 200 на правой стороне. Изображены только границы сегментов.

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

a) b) c)

Рис. 2. Яркости справа: a) 0, b) 200, c) 255; яркость слева всюду 0

a) b) c)

Рис. 3. Метод EDGEFLOW 10. Сегментация областей с медленно изменяющейся яркостью

a) b) c)

Рис. 4. Углы a) 2, b) 80, c) 160 градусов: всюду яркость изображения 50 на фоне 200

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

Сохранение углов при сегментации. На рисунке 4 даны примеры из параметризованного семейства углов, состоящего из 180 изображений. Параметром семейства является значение угла от 1 до 180 гра- дусов.

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

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

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

В качестве примера на рисунке 5 показаны граничные линии, полученные после сегментации изображений семейства (рис. 4) с углами в 5, 30, 90 градусов.

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

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

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

Рис. 5. Метод JSEG. Сегментация углов

a) b) c)

Рис. 6. Круг яркости a) 150 на фоне 30, b) 255 на фоне 200, c) 150 на фоне 200

Сегментация зашумленных и размытых изображений. Для тестирования при зашумлении и размытии используются изображения: угол (рис. 4, величина 110°, яркость 50 на фоне яркости 200) и круг (рис. 6, радиус 100 пикселов, яркость 200 на фоне яркости 30). Кроме того, взяты изображения Step, Junction, Snail и Roof из базы данных PICASSO (рис. 7, левый столбец).

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

Для каждого тестового изображения строится по два однопараметрических семейства новых изображений. Первое семейство строится путем добавления к исходному изображению гауссова шума (средний столбец рис. 7). Значение девиации шума σ является параметром семейства. Второе семейство строится путем размытия изображений по Гауссу (правый столбец рис. 7). Параметром семейства является радиус окна размытия r.

Пример сегментации приведен на рисунке 8, сегментные карты опущены, показаны только границы полученных сегментов.

Рис. 7. Изображения Step, Junction, Snail, Roof

Рис. 8. Метод EDISON_1000. Верхний ряд: сегментация исходных изображений Junction, Snail, Roof и Step. Средний ряд: сегментация при гауссовом зашумлении, девиация 4. Нижний ряд: сегментация при гауссовом размытии, радиус 3 пиксела

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

Среднее расстояние d(X,Y), хаусдорфово χ(X,Y) и между множествами X и Y определяются как

,

.

Здесь ρ(x,Y) – расстояние от точки до множества Y: , а ρ(x, y) – обычное евклидово расстояние между точками x и y; NX и NY – количество точек в X и Y. В нашем случае множества X и Y – наборы граничных точек, заключенных в области изображения, а оба расстояния измеряются в пикселах.

Среднее расстояние вводится потому, что по паре расстояний χ и d можно лучше судить о качестве сегментации, чем по одному из них. Именно, пусть X и Y – наборы граничных точек на двух изображениях. Если величины d(X,Y) и χ(X,Y) малы, X и Y мало отличаются и границы близки. Если значение d мало, а χ велико, это означает, что в X входят точки, значительно удаленные от точек Y (либо наоборот), но их количество невелико. Если же d и χ велики, то и количество таких точек большое.

Методики тестирования при зашумлении и размытии схожи. Для определенности рассмотрим случай зашумления.

Пусть I – некоторое исходное изображение; Iσ – изображение с добавленным гауссовым шумом с девиацией σ. Далее вся серия Iσ обрабатывается сегментатором, в результате чего получается серия сегментных карт s(Iσ). Находя на них граничные точки, получаем серию изображений, содержащих только границы: B(s(Iσ)). Обозначим B(I) граничные точки I. Вычислим величины d(σ)=d(B(I),B(s(Iσ))) и χ(σ)= =χ(B(I),B(s(Iσ))).

Зависимости d=d(σ) и χ=χ(σ) могут быть изображены в виде графиков. Если используется несколько исходных тестовых изображений, функции d(σ) и χ(σ) вычисляются отдельно для каждого из них и усредняются по всем исходным изображениям. Благодаря усреднению графики более объективно отражают особенности самого сегментатора. При размытии изображений вместо девиации шума σ берется радиус окна гауссова размытия r.

Рис. 9. Сохранение углов при сегментации EDGEFLOW и JSEG

Рассмотрим отдельно вопрос о выборе B(I). Когда I – достаточно простое изображение, например угол или круг, для него легко вручную построить идеальные граничные линии ground truth и выбрать их в качестве изображения B(I). При тестировании так и было сделано. Более того, все сегментаторы хорошо обрабатывают простые изображения при малых уровнях зашумления или размытия (например рис. 5), так что сравнение полученных границ с ground truth возможно. Но на сложных изображениях Step, Junction, Snail, Roof даже при обработке неискаженного изображения все методы сегментации дают границы, сильно отличающиеся от предполагаемых идеальных (рис. 8). Причина в наличии областей с медленно изменяющейся яркостью, обработка которых создает для всех методов сегментации дополнительные трудности (рис. 3). Поэтому в данном случае мы исследуем, насколько результат сегментации искаженного сложного изображения отличается от результата сегментации исходного изображения. Иными словами, на изображениях Step, Junction, Snail, Roof изучается устойчивость сегментации. При этом в качестве B(I) берутся границы, полученные при сегментации исходного изображения, B(s(I0)). Тем самым тестирование на простых и сложных изображениях проводится по несколько разным методикам.

Замечание. Как выяснилось в экспериментах, все методы сегментации обладают определенной нестабильностью работы: небольшие изменения на обрабатываемом изображении могут приводить к относительно существенным изменениям всего результата сегментации. Например, при линейном увеличении максимальной яркости изображений (рис. 2) количество ложных границ в некоторых пределах может скачкообразно и увеличиваться, и уменьшаться. Аналогичное явление происходит при сегментации углов, зашумленных и размытых изображений. В итоге в типичном случае графики получаются негладкими и неудобными для анализа. Пример для сегментации углов приведен на рисунке 9. Однако, хотя в этом примере график имеет изломы, по нему ясно видна тенденция к более точной сегментации при увеличении угла. Подобные тенденции могут стать более очевидными с помощью построения линии тренда графиков. Линия тренда представляет собой полиномиальное или иное приближение точек графика и строится стандартными средствами.

Рис. 10. Линии тренда графиков при сегментации регионов с медленно изменяющейся яркостью

Результаты тестирования

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

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

Сохранение углов при сегментации. Оказалось, что методы EDISON и MULTISCALE сохраняют углы (рис. 4) практически идеально: расстояние между точкой истинной вершины угла и ближайшей к ней точкой отсегментированного угла всегда составляет 0–1 пиксел. Поэтому графики тестирования данных методов не приводятся. В то же время методы EDGEFLOW и JSEG значительно искажают малые углы (рис. 10).

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

Сегментация слабоконтрастных областей. За исключением JSEG, все тестируемые методы выделяют круг как отдельный сегмент, если его яркость превышает яркость фона на 1–2 единицы, независимо от яркости самого фона.

Для JSEG оказалось, что, когда объект (круг) находится на темном фоне (яркость от 0 до 15), он выделяется как отдельный сегмент, только если его яркость превышает яркость фона как минимум на 23 единицы. Например, на фоне 1 выделится круг яркости не менее 24, на фоне 10 – не менее 33 и т.д. При этом используется стандартная серая палитра с диапазоном допустимых яркостей 0…255. Если же круг находится на более светлом фоне (яркость 22 и выше, до наибольших возможных значений), для выделения его как сегмента достаточно, чтобы его яркость превышала яркость фона всего на 1.

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

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

Зашумление изображений. Для тестирования качества сегментации при зашумлении к изображениям на рисунках 4, 6, 7 добавляется гауссов шум с девиацией от 0 до 30 с шагом 1.

На рисунке 12 даны сравнительные графики по всем методам при обработке простых двутоновых изображений круг и угол (рис. 4, 6). Граничные кривые, полученные после сегментации данных изображений, сравнивались с заданными идеальными границами, которые очевидны и не приводятся. Здесь и далее графики представлены как линии тренда результатов измерений.

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

В целом при увеличении зашумления как среднее, так и хаусдорфово расстояния растут для всех тестируемых методов. Спад некоторых графиков при больших значениях девиации шума означает, что граничные кривые очень сильно искажаются, отчего вся сегментация становится недостоверной. Метод EDISON может использоваться при значениях девиации не более 15–20, а метод EDGEFLOW – при значениях не более 3–5. Метод MULTISCALE более устойчив к зашумлению простых изображений: замедление роста графика среднего расстояния и некоторая тенденция к спаду начинаются при значениях девиации шума 20–25.

На рисунке 13 даны сравнительные графики по всем методам при обработке изображений Step, Junction, Snail, Roof (рис. 7), содержащих области с медленно изменяющейся яркостью. Как уже было сказано, в данном случае эталоном для сравнения являются граничные кривые, полученные после сегментации исходных изображений.

На рисунке 13 видно, что наибольшие значения расстояний получились для метода EDGEFLOW 26, причем графики начинают спадать при значениях девиации 7–8. Это, видимо, и есть тот уровень зашумления, с которым способен работать данный метод. Величины расстояний для EDGEFLOW 10 меньше, однако графики перестают расти и начинают спадать приблизительно при той же величине шума. MULTISCALE несколько более устойчив к зашумлению: спад графиков начинается при значениях девиации порядка 20.

Рис. 12. Зашумление простых изображений

Но большие в целом значения расстояний d и χ говорят о том, что при увеличении зашумления изображения этот метод создает много лишних крупных сегментов. Методы EDISON и JSEG показали наилучшие результаты. Их графики лежат ниже графиков остальных методов. Графики EDISON начинают спадать при значениях девиации 15–20. Видимо, это предельное зашумление, при котором метод эффективен. У JSEG показатели еще лучше.

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

Размытие изображений. Для тестирования качества сегментации при размытии изображений производится гауссово размытие исходных изображений рисунков 4 и 6 с радиусом окна от 0 до 12 пикселов с шагом 0,4 пиксела и изображений рисунка 7 с радиусом окна от 0 до 3 пикселов с шагом 0,1 пиксела.

Рис. 13. Зашумление сложных изображений

На рисунке 14 приведены сравнительные графики по всем методам при сегментации простых изображений – круг и угол (рис. 4, 6).

При тестировании на размытых простых изображениях наилучшее качество показал метод EDISON: у него значения как среднего, так и хаусдорфова расстояний наименьшие по сравнению с другими методами. Это означает точное сохранение формы границ при размытии исходного изображения. Метод EDGEFLOW может работать при значениях радиуса окна размытия не более 3–4, после чего на сегментной карте возникает значительное количество лишних сегментов. На это обстоятельство указывают большие значения как среднего, так и хаусдорфова расстояний. Метод JSEG хорошо работает до значений радиуса 8–9. Примерно такие же показатели у метода MULTISCALE. Однако следует еще раз подчеркнуть, что все эти результаты относятся к простым изображениям, на которых не создаются ложные границы.

На рисунке 15 приведены сравнительные графики при обработке сложных изображений, содержащих области с медленно изменяющейся яркостью Step, Junction, Snail, Roof (рис. 7). Как видно, для всех методов сегментация сложных изображений оказалась более трудной задачей, чем сегментация простых. Обратим внимание на диапазоны значений радиуса окна размытия на графиках рисунков 14 и 15. Радиус на рисунке 14 изменяется от 0 до 12 пикселов. Для получения приемлемого качества сегментации в случае сложных изображений (рис. 15) пришлось ограничиться максимальным значением радиуса, равным 3 пикселам. При значениях радиуса, равных 2–3, значения всех расстояний, показанные на рисунке 14, в несколько раз меньше расстояний на рисунке 15.

На рисунке 15 видно, что при тестировании на размытых сложных изображениях наилучшее качество показал метод JSEG: у него значения как среднего, так и хаусдорфова расстояний наименьшие по сравнению с другими методами. Это означает точное сохранение формы границ при размытии исходного изображения. Метод EDGEFLOW может работать при значениях радиуса окна размытия не более 1–1,5 пиксела. После этих значений начинают значительно изменяться количество и форма сегментов. Методы EDISON и MULTISCALE близки по своим показателям. Однако большие значения хаусдорфова расстояния при существенно меньших (в 10–20 раз) значениях среднего расстояния указывают на большое количество мелких искажений (изломов) граничных линий. Сохранение границ ухудшается при значениях радиуса окна размытия, больших 1 пиксела.

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

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

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

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

Список литературы

1. Manjunath B.S., Deng Y. (http://vision.ece.ucsb.edu/segmentation/jseg).

2. Georgescu B., Christoudias C.M., Meer P. (www.caip.rutgers.edu/riul/research/code/EDISON).

3. Ma Wei-Ying, Manjunath B.S. (http://vision.ece.ucsb.edu/ segmentation/edgeflow).

4. Sumengen B., Manjunath B.S. (http://barissumengen. com/seg/).