Предварительная обработка изображений

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 21:58, 5 декабря 2016.


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

Содержание

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

Задача сегментации и распознавания изображений технически комплексная. Она делится на несколько больших сегментов (подзадач):

Рис. 1 Этапы алгоритмов распознавания изображения

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

  1. Изображения предъявляются на сложном фоне;
  2. Искомые области имеют сложную геометрию;
  3. Входные данные имеют шум или дезориентирующую информацию;
  4. Различные части изображения имеют различные характеристики (подсветка, освещенность, помехи)

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

Pис. 2 Некоторые методы применяемые при распознавании изображений

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

Сегментация - процесс поиска однородных областей на изображении. Этот этап весьма трудный и в общем виде не алгоритмизированный для произвольных изображений. Наиболее распространены методы сегментации, основанные на определении однородных яркостей (цветов) или однородностей типа текстур.

Улучшение/фильтрация - могут использоваться после проведения сегментации, и преследует ту же цель что и предварительная обработка: снижение помех на изображении, возникших в результате дискретизации и квантования, а также подавления внешних шумов.

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

Фильтрация зашумленных изображений

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

Гауссов шум

Pис. 3 График плотности распределения Гауссового шума

Гауссов шум является наиболее простым с математической точки зрения. Спектральные составляющие этого типа шума равномерно распределены по всему диапазону задействованных частот. Примерами белого шума являются шум водопада или эфирные помехи. В природе и технике «чисто» белый шум (то есть белый шум, имеющий одинаковую спектральную мощность на всех частотах) не встречается (ввиду того, что такой сигнал имел бы бесконечную мощность), однако под категорию белых шумов попадают любые шумы, спектральная плотность которых одинакова (или слабо отличается) в рассматриваемом диапазоне частот. Функция плотности распределения Гауссового шума случайной величины имеет вид:

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

График функции представлен на приведенном справа рисунке.


Шум Релея

Pис. 4 График плотности распределения шума Релея

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

Среднее значение и дисперсия имеют вид:

График плотности распределения представлен на рисунке.


Шум Эрланга

Pис. 5 График плотности распределения шум Эрланга

Функция плотности распределения вероятности шум Эрланга задается выражением


где – положительное число.

Среднее значение и дисперсия имеют вид:

График плотности распределения показан на рисунке.


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


Пространственная фильтрация изображений

Задача пространственной фильтрации в общем виде рассмотрена в разделе 2.9 В общем виде модель искаженного изображения имеет вид:

в пространственном представлении: в частотном представлении:

Если искажение представлено только шумом, то эти формулы принимают вид:

или

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

Фильтр, основанный на вычислении среднего арифметического

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

Пусть - некоторая окрестность размерами m*n и с центром в точке . Необходимо вычислить среднее арифметическое по окрестности . Таким образом, для произвольной точки обрабатываемой окрестности имеем:

Данную операцию можно представить в виде маски, все коэффициенты которой равны .


Фильтр, основанный на вычислении среднего геометрического

Изображение, восстановлено таким фильтром задается выражением

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


Фильтры, основанные на вычислении среднего гармонического

Результат обработки этим фильтром задается выражением

Среднегармонический фильтр хорошо справляется с «белым» шумом (т.е. когда зашумление выражается в появлении белых точек на изображении). Этот фильтр так же хорошо применим при работе с Гауссовым шумом.

Фильтры, основанные на порядковых статистиках

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


Медианный фильтр

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

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

Pис. 6 Пример работы медианного фильтра длинной 5 единиц

Фильтры, основанные на вычислении максимума и минимума

Следующим по значимости после медианного фильтра можно считать фильтр, основанный на вычислении минимума/максимума. Откликом медианного фильтра на некоторую последовательность данных является среднее значение из упорядоченной последовательности этих данных. Однако можно использовать либо максимальное, либо минимальное значение в упорядоченной последовательности. Если мы выбираем максимальное значение, то это приводит к поиску в изображении точек с максимальным значением яркости. Такой фильтр хорошо использовать в случае «черного» импульсного шума. Если же напротив, использовать минимальное значение, то мы найдем точки с минимальным значением яркости. Это значит, что такой фильтр хорошо применять для исключения «белого» импульсного шума.


Pис. 7 Пример реализации «максимального» фильтра
Pис. 8 Пример реализации «минимального» фильтра


Выбор средней точки

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


Рис. 9 Пример реализации фильтра средней точки


Фильтрации на основе вейвлет-преобразований

(см. также разделы 2.9.9 и 2.9.10)

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

Модель сигнала можно записать следующим образом:

здесь – полезный сигнал,
– шум,
– уровень шума,
– исследуемый сигнал.

Для такой модели удаление шума с помощью вейвлет-преобразования выполняется в 4 этапа:

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

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

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

  • «длинные» вейвлеты создают более гладкую аппроксимацию сигнала, и наоборот – «короткие» вейвлеты лучше отслеживают пики аппроксимируемой функции;
  • глубина разложения влияет на масштаб отсеиваемых деталей, т.е. при увеличении глубины разложения модель вычитает шум все большего уровня, пока не наступит «переукрупнение» масштаба деталей и преобразование начнет искажать форму исходного сигнала.
Pис. 10 Пример использования вейвлета Добеши для фильтрации сигнала

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

где – длина выборки,
– пороговое значение.

Если уровень шума (для гауссовского распределения – это среднеквадратичное отклонение) отличается от 1, то значение порога должно быть масштабировано на это величину.

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

Выбор способа фильтрации

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

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

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

Основные типы методов сегментации изображений

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

1. Морфологические методы – применяются в основном для работы с двоичными (черно-белыми) изображениями. Эти методы позволяют извлекать компоненты изображения, которые в последствии могут использоваться для представления формы объекта.
2. Пороговые методы – обладают интуитивно понятными свойствами и просты в реализации. Существуют несколько основных видов пороговой сегментации, но базовыми являются только два: метод с оптимальным порогом и метод с адаптивным порогом. Все остальные методы этого класса являются производными от двух упомянутых алгоритмов.
3. Методы наращивания областей – представляют собой алгоритмы, рекурсивно выполняющие процедуру группировки пикселей в подобласти по заранее заданным критериям. Одним из основных методов здесь является метод водоразделов.
4. Текстурные методы – опираются при анализе на диффузные (цвет, отражательная способность) свойства поверхности анализируемого объекта. Представленные в этой категории методы являются наборами сложных операторов, которые способны свести процесс распознавания поверхностей к простой задаче различения уровней яркости.

Морфологические методы

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

  • NOT (логическое «НЕ»)
  • AND (логическое «И»)
  • OR (логическое «ИЛИ»)
  • XOR (исключающее «ИЛИ»)

Примеры соответствующих процедур представлены на рисунке:

Pис. 11 Примеры простейших логических операций над изображением


Операции эрозии и дилатации

Дилатация

Пусть и – множества пространства . Дилатацией множества по множеству определяется как:

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

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


Pис. 12 Пример выполнения дилатации множества А по примитиву В

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


Pис. 13 Пример использования процедуры дилатации для улучшения текста


Эрозия

Для множеств и из пространства эрозия по определяется как:

Иначе говоря, эрозия множества по примитиву - это множество всех точек , при сдвиге в которые множество целиком содержится в . Как и в случае дилатации, данное уравнение не является единственным способом определения процедуры эрозии. На приведенном ниже изображении, слева показано множество до применения к нему эрозии и примитив . Справа показан результат эрозии множества . Пунктирной линией выделена форма исходного множества, а сплошной – результат выполненной операции. Сплошная линия соответствует тем предельным значения , при сдвиге центра примитива за которые перестает выполняться требование, что бы было подмножеством . Таким образом, геометрическое место точек внутри сплошной линии является результатом эрозии множества по примитиву .

Pис. 14 Пример применения операции эрозии к множеству А по примитиву В


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


Pис. 15 Пример использования процедуры эрозии для устранения деталей с изображения

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


Выделение границ

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

здесь – любой примитив операции.

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


Pис. 16 Пример получения границы методом выделения границ


Выделение связных компонент

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

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

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


где , а – любой подходящий примитив.

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


Pис. 17 Пример выполнения операции выделения связных компонент

Пороговые методы

Данные методы обладают интуитивно понятными свойствами и просты в реализации. Базовыми являются два метода: метод с глобальным порогом и метод с адаптивным порогом.

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


где 1 – пиксель, соответствующий объекту, а 0 – пиксель, соответствующий фону.

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


Pис. 18 Пример гистограмм с возможностью разделения одиночным (Т) и множественным (Т1, Т2) порогами


Пороговый метод с глобальным порогом

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

Pис. 19 Пример разделения изображения с использованием глобального порога Т

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

  • Выбирается некоторая начальная оценка порога ;
  • Используя порог , сегментируем изображение на две области и ;
  • Вычисляем значения и средних значений яркости областей и ;
  • Вычисляется новое значение порога:
  • Вычисляем шаги 2-4 до тех пор, пока разница значений при соседних итерациях не окажется меньше либо равно некоторому .

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


Пороговый метод с адаптивным порогом

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


Pис. 20 Пример обработки изображения глобальным (б) и адаптивным (в) порогами

На рисунке 20 (а) показано начальное изображение некоторой области. На рисунке 20 (б) представлен результат использования глобального порога. Как видно, правая часть искомой области затерялась, так значения пикселей фона и пикселей объекта слились и были отсечены как фон. На рисунке 20 (в) показан результат использования адаптивного порога.

В качестве критерия разбиения удобно использовать понятие дисперсии освещения. Т.е. изображение разбивается на области, освещенность которых приблизительно одинакова. Дисперсия вычисляется как:

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

Методы сегментации – Метод водоразделов

Метод водоразделов включает в себя следующие три базовых концепции:

  • Обнаружение и устранение разрывов;
  • Пороговая обработка;
  • Обработка областей;

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

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

  • Точки локального минимума;
  • Точки, находящиеся на склоне, с которых вода сливается к центру водоема;
  • Точки, находящиеся на гребне возвышенности;

Линии, образованные точками-гребнями, представляют собой линии водоразделов. Ясно, что основной задачей данного метода является именно поиск линий водоразделов.



Для того, что бы лучше понять идею метода, опишем его алгоритм:

1. В местах локального минимума образуем «дырки», через которые вода начнет заполнять трехмерную поверхность;
2. Если вода с двух сторон гребня готова объединиться в один бассейн, устанавливаем перегородку;
3. Когда над водой останутся только загородки, останавливаем алгоритм.

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

Pис. 21 Пример работы алгоритма водоразделов


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


Рис 22 Построение водоразделов методом дилатации


В качестве примитива используется матрица 3*3 элемента. Во время работы алгоритма используются два правила:

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

На рисунке 22(А) показаны две начальные области. При применении дилатации к областям (рисунок 22 (Б)) их площадь увеличивается. На следующем шаге (рисунок 22(В)) наращиваемые области готовы слиться в одну, значит необходимо установить перегородку. После того, как точки раздела найдены, им присваивается значение равное максимальной яркости + 1. Это предотвращает слияние областей в ходе работы алгоритма. Важно отметить, что полученные линии водораздела - связные компоненты, не имеющие разрывов в линиях сегментации.

Непосредственное применение метода водораздела может привести избыточной сегментации, вызванное локальными неровностями и шумом в изображении (рисунок 22(А)). Практическое решение этой проблемы состоит в том, что бы ограничить допустимое число областей путем включения дополнительного шага предварительной обработки. Такой подход основан на идее маркеров. Маркер представляет собой связную компоненту, принадлежащую изображению. Будем различать внешние (соответствуют фону) и внутренние (относятся к объекту) маркеры.

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

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


Pис. 23 Пример использования маркеров

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


Методы сегментации – Метод текстурных дескрипторов

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

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

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

Pис. 24 Примеры различных текстур


Текстуры можно организовывать иерархическим образом, т.е. они могут выглядеть совершенно по-разному при различных масштабах. Хорошим примером является текстура занавески, показанная на рис. 24 (д). В самом мелком масштабе наше внимание фокусируется на отдельных нитях. Тогда характеристическим размером является толщина нитей. Они также имеют преобладающую локальную ориентацию. На следующем, более грубом уровне, мы распознаем петли сети. Характеристический размер здесь показывает размер петель. На этом уровне локальная ориентация является хорошо распределенной. И, наконец, на еще более грубом уровне мы больше не распознаем отдельные петли, но наблюдаем складки занавески. Они характеризуются еще одним характеристическим размером, показывающим период складок и их ориентацию. Эти рассуждения подчеркивают важность многомасштабного текстурного анализа. Таким образом, многомасштабные структуры данных являются существенными для текстурного анализа.

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

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

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

Для текстурного анализа используются только четыре фундаментальных текстурных оператора:

  • среднее значение;
  • дисперсия;
  • ориентация;
  • масштаб,

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

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

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

где – среднее значение (средняя яркость изображения):

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

равна 0 для областей постоянной яркости (где дисперсия нулевая) и приближается к 1 для больших значений .

Третий момент

является характеристикой асимметрии гистограммы. Среди прочих полезных характеристик текстуры можно выделить «однородность»:

и среднюю энтропию:

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

Коррекция яркости и контрастности изображений

Изображения, вводимые в компьютер, часто являются малоконтрастными. Слабый контраст, как правило, обусловлен широким диапазоном воспроизводимых яркостей, нередко сочетающийся с нелинейностью характеристики передачи уровней. Характер зависимости изменения яркости палитры пикселей от минимального значения до максимального также влияет на качество изображения. Оптимальной является линейная функция изменения интенсивности пикселей. При вогнутой характеристике изображение будет более темным, при выпуклой — более светлым. И в том, и в другом случае признаки объектов могут быть искажены и недостаточно хорошо идентифицируемы. Коррекция (линеаризация) яркости палитры существенно улучшает качество изображения. Малая контрастность может быть обусловлена и тем, что вариации функции яркости пикселей на изображении намного меньше допустимого диапазона шкалы яркостей. В этом случае контрастность изображения повышается путем "растягивания" реального динамического диапазона яркостей на всю шкалу при помощи линейного поэлементного преобразования. Другой способ коррекции яркости палитры связан с инверсией входного изображения. Поскольку различать слабые сигналы на темном фоне достаточно сложно, то инверсная форма представления таких изображений имеет другую гистограмму яркостей, более приемлемую для наблюдения и визуальной идентификации. Некоторые задачи обработки изображения связаны с преобразованием полутонового изображения (много градаций яркости) в бинарное (две градации). Преобразование осуществляется для того, чтобы сократить информационную избыточность изображения, оставить в нем только информацию, которая нужна для решения конкретной задачи. В бинарном изображении должны быть сохранены определенные детали (например, очертания изображенных объектов) и исключены несущественные особенности (фон). Пороговая обработка полутонового изображения заключается в разделении всех элементов изображения на два класса и по признаку яркости с границей , и в выполнении соответствующей пороговой фильтрации с заменой пикселей изображения на установленную яркость классов. Выбор границы определяется видом гистограммы яркости исходного изображения. Для простейших изображений типа чертежей, машинописного текста и т.п., имеющих бимодальное распределение, граница устанавливается по минимуму между модами распределения. В общем случае изображение может быть многомодальным, и если устанавливается достаточно надежное соответствие между объектами и соответствующими модами их яркости, то пороговая фильтрация также может предусматривать несколько классов яркости пикселей. Диапазон яркости изображения в компьютере может иметь отличия от диапазона яркостей исходного, например, в силу недостаточной экспозиции. Существует два возможных способа коррекции яркости. Согласно первому способу изображение линейно отображается в диапазоне яркостей исходного. Второй способ предусматривает ограничение яркости пикселей в обработанном изображении максимальным и минимальным пороговыми уровнями, и имеет более широкое применение. Присутствие в изображении самых светлых и самых темных тонов создает впечатление хорошей контрастности, однако излишняя контрастность приводит к тому, что максимальные градации влияют на средние тона, а большинство деталей изображения окрашены именно в средних тонах и излишняя контрастность может приводит к потере этих деталей или затруднить их выделение.

Гистограммы яркости

Инструментом для оценки уровней интенсивности пикселей является гистограмма - графическое отображение количественной характеристики вероятностного распределения интенсивности (яркости) пикселей в выделенном участке изображения. Максимальному значению интенсивности пикселей присваивается уровень градации интенсивности 255 (белый цвет), самому темному - значение 0 (черный цвет). Интенсивности в диапазоне от 0 до 255 имеют линейную шкалу изменения, либо устанавливаемую в соответствии с принятой функцией изменения, например, усиливающей слабые сигналы (градации серого) и ослабляющей сильные сигналы (в области белого цвета), чем повышается пространственное и контрастное разрешение изображения или определенной зоны интереса. Известен метод улучшения изображений, основанный на вычислении логарифма спектральных коэффициентов преобразования Фурье исходного изображения (вычисление кепстра). При обратном преобразовании кепстра в изображение происходит выравнивание гистограммы изображения за счет логарифмического преобразования спектра изображения. Многие изображения характеризуются гистограммами с высокой концентрацией линий в определенных зонах распределения интенсивности. Часто гистограмма распределения яркостей изображения имеет перекос в сторону малых уровней (яркость большинства элементов ниже средней). Одним из методов улучшения качества таких изображений является видоизменение их гистограммы. Выравнивание гистограммы может быть осуществлено на основе возведения в степень модуля спектральных коэффициентов Фурье-преобразования изображения, при этом знак и фаза коэффициентов сохраняется. Если обозначить показатель степени , то при операция извлечения корня степени уменьшает большие спектральные коэффициенты и увеличивает малые. Такое перераспределение энергии в частотной плоскости изображения приводит к более эффективному использованию динамического диапазона интенсивностей пикселей изображения в пространственной области. Выбор хорошей маски регулирования гистограммы интенсивности пикселей повышает контраст, тем самым улучшая контрастную разрешающую способность деталей. В программах обработки есть команды, позволяющие устанавливать цвета при цветном картировании изображений, имеющие плавные или, наоборот, резкие переходы отображаемых деталей в зоне интереса. В сочетании с обращением контраста, преобразующем негативное изображение в позитивное, данный способ позволяет также повысить контраст мелких и средних деталей изображения. Существует достаточно большой арсенал математических моделей и алгоритмов, программная реализация которых позволяет значительно повысить контрастное разрешение изображений. Эти алгоритмы основаны на процессах линейной и нелинейной фильтрации изображений, преобразующей гистограмму интенсивности.

Выравнивание освещенности изображений

Часто некоторые участки на изображении бывают слишком темными, чтобы на них можно было что-то разглядеть. Если прибавить яркости ко всему изображению, то изначально светлые участки могут оказаться засвеченными. Чтобы улучшить вид изображения в таких случаях, применяется метод выравнивания освещенности. Освещенность меняется в пространстве достаточно медленно и ее можно считать низкочастотным сигналом. Само же изображение можно считать в среднем более высокочастотным сигналом. Если бы в процессе фотографии эти сигналы складывались, то их можно было бы разделять с помощью обычных фильтров. Однако на реальной фотографии получается произведение той картины, которую мы хотим видеть, и карты освещенности. И поскольку эти сигналы не складываются, а перемножаются, то избавиться от неравномерностей освещенности простой фильтрацией не удастся. Для решения таких задач применяется гомоморфная обработка. Идея обработки заключается в сведении нелинейной задачи к линейной. Например, можно свести задачу разделения перемноженных сигналов к задаче разделения сложенных сигналов. Для этого нужно взять логарифм от произведения изображений, который будет равен сумме логарифмов сомножителей. При этом задача разделения произведения сигналов сводится к задаче разделения суммы НЧ- и ВЧ- сигналов и решается с помощью ВЧ-фильтра, который удалит из суммы сигналов низкие частоты. Останется взять от полученного сигнала экспоненту, чтобы вернуться к исходному масштабу амплитуд. ВЧ-фильтр можно реализовать следующим образом. Сначала к изображению применяется операция размытия (НЧ-фильтр), а потом из исходного изображения вычитается размытое. Наилучший радиус размытия зависит от конкретного изображения. Можно начать эксперименты с радиуса порядка десяти пикселей. Обычно для размытия изображения применяется двумерный гауссовский фильтр, имеющий вид . Здесь – нормирующая константа (сумма всех коэффициентов фильтра должна быть равна 1), – «ширина» фильтра, регулирующая степень размытия. Непосредственное вычисление двумерной свертки с таким ядром требует больших вычислений даже при сравнительно небольшом размере ядра. Однако эквивалентного эффекта можно достичь, отфильтровав одномерным гауссианом сначала строки изображения, а затем столбцы полученного изображения. Полученный от выравнивания освещенности эффект может оказаться слишком сильным (темные области станут по яркости такими же, как и светлые). Чтобы уменьшить эффект, можно просто смешать обработанное изображение с исходным в определенной пропорции.

Улучшение пространственного разрешения

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

а) «величины» — степени влияния воздействия на резкость изображения;
б) «радиуса» — толщины контура резкости;
в) «порога дискриминации» — определения контуров объектов путем задания разности значений интенсивности соседних пикселей, достаточной для того, чтобы программа повысила контрастность между ними.

Некоторые программы содержат автоматическую установку оптимального соотношения контрастности и яркости, поддерживающих необходимую четкость изображения. При обработке изображений важную роль играют алгоритмы ранговой фильтрации, позволяющие устранять «размытость» деталей (улучшить их фокусировку) за счет выбора двумерной маски пикселей, выполнения операции ранжирования значений интенсивности пикселей в пределах задаваемой маски и присвоения центральному пикселю значения, равного максимальному значению по ранжиру. К виду ранговой относится также процедура медианной фильтрации, устраняющая в изображении некоррелированные случайные сигналы и импульсные помехи без "размытия" резких перепадов яркости на границах объектов. Применение линейной фильтрации обусловлено ее возможностями коррекции искажений различного типа, возникающих вследствие несовершенства устройств, формирующих изображение. Посредством линейной фильтрации удается уменьшить влияние флуктуационных шумов и других дефектов на воспроизводимых изображениях в режиме повышения контраста малоконтрастных деталей при увеличении масштаба зон интереса. Коррекция аппертурных искажений изображений в случае отсутствия шумовой составляющей сигнала осуществляется путем инверсной фильтрации (деконволюции). Однако следует учитывать, фильтры деконволюции имеют коэффициент усиления дисперсии шумов, больший 1, и вместо улучшения изображения может увеличиться зашумленность. Перспективными считаются нелинейные методы фильтрации на основе частотных масок, позволяющих уменьшить влияние низкочастотных компонент сигнала изображения и усилить влияние высокочастотных компонент, что повышает пространственное разрешение деталей, описываемых в спектре изображения более высокими пространственными частотами.

Поиск границ на основе градиента

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

Pис. 25

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

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


Pис. 26


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

Pис. 27

При проведении гистерезисной фильтрации вводят не одно, а два пороговых значения. Меньшее () соответствует минимальной длине градиента, при которой пиксель может быть признан граничным. Большее (), соответствует минимальной длине градиента, при которой пиксель может инициализировать контур. После того как контур инициализируется в максимальном пикселе с длиной градиента, большей , рассматриваются каждый соседний с ним максимальный пиксель . Если пиксель имеет длину градиента, большую , и угол между векторами и близок к то добавляется к контуру, и процесс рекурсивно переходит к . Его результат для исходного изображения на рис.26 показан на рис.27.

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

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

Этот алгоритм носит названия алгоритма Кэнни и наиболее часто применяется для нахождения границ.

Поиск границ на основе лапласиана

Pис. 28

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


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



Выделение объектов на изображении

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

Алгоритм "Волшебная палочка" (Magic wand)

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

Алгоритм "умные ножницы"

используется с 1996 году, завоевал популярность и был встроен в распространенный редактор фотоизображений Adobe Photoshop. При использовании алгоритма пользователь обводит границу между объектом и фоном, указывая точки на границе с некоторым промежутком, а "умные ножницы" проводят граничную линию между последовательно указанными точками.

Pис. 29

Представим себе растр изображения в виде графа (рис.29) с ребрами, образованными сторонами пикселей. При указании пользователем двух последовательных точек и алгоритм "ножниц" вычисляет минимальное расстояние между точками и по ребрам графа, при этом условная геометрическая длина каждого ребра на этом пути имеет обратную зависимость от величины цветового перепада пикселей по его сторонам. Поскольку ребра, соответствующие резким цветовым перепадам, будут иметь меньшую условную длину, "умные ножницы" стремятся провести границу именно по таким ребрам. "Умные ножницы" существенно ускоряют процесс выделения объекта. Однако и они работают не очень хорошо при наличии пестрого фона и/или пестрого объекта. В таких случаях требуется указывать большее количество граничных точек. Сегментация при помощи разрезов на графах. Третий способ выделения объекта на фоне также основан на теории графов. Пользователь просто отмечает некоторое множество пикселей, принадлежащих объекту, и некоторое множество пикселей, принадлежащих фону. Поскольку эти пиксели не обязаны быть рядом с границей, такая разметка не требует от пользователя особых усилий. Результатом алгоритма служит сегментация, в которой все множество math>A\,\!</math> относится к объекту, а множество - к фону. Если результат выделения с первого раза не удовлетворяет пользователя, он добавляет в исходные множества пиксели, доотмечая их на изображении. Например, если алгоритм ошибочно отнес кусок объекта к фону, пользователь отмечает часть пикселей этого куска как пиксели объекта (множество math>A\,\!</math>). Результатом перезапуска алгоритма служит уточненная сегментация. Рассмотрим, как работает алгоритм. Построим граф на растре следующим образом. Пиксельные вершины графа расположим в центре каждого пикселя, а под цветом вершины мы будем понимать цвет пикселя. Каждую вершину соединим с соседними вершинами и получим восемь ребер, которые соединяют центры соседних пикселей. Припишем каждому ребру вес:

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

Данный вес тем меньше, чем больше разница между цветами вершин.

Pис. 30

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

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

Пример выделения объекта приведен на рис.30.

Выделение признаков объектов

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

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

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

Определение площади и периметра

Площадь изображения объекта вычисляется путём подсчёта числа элементов, относящихся к объекту:

где - множество координат массива , принадлежащих выделенному объекту.

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

Определение радиусов вписанных и описанных окружностей

Pис. 31

(рис.32) складывается из двух этапов.

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

Нормированный признак инвариантен к масштабу изображения объекта.

Определение сторон описанного прямоугольника

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

Pис. 32

Данный признак не инвариантен к развороту изображения объекта.

Определение числа и взаимного положения углов

Pис. 33

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

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

Если условие выполняется, тогда данная точка контура принадлежит множеству угловых точек . Здесь – пороговое значение, выбираемое с учётом свойств объектов.

Определение моментов инерции объекта

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

Pис. 34

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

Порядок вычислений:

1. Определяются координаты центра "тяжести" (энергетического центра) изображения объекта.
2. Определяются промежуточные моменты , ,
3. Вычисляются главные моменты.