Математические методы распознавания образов

Размещено на http://www.allbest.ru/

ВВЕДЕНИЕ

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

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

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

Многообразие целей и задач обработки изображений можно классифицировать следующим образом:

- улучшение качества изображений;

- измерения на изображениях;

- спектральный анализ многомерных сигналов;

- распознавание изображений;

- компрессия изображений.

1. МЕТОДЫ КОМПЬЮТЕРНОЙ ОБРАБОТКИ ИЗОБРАЖЕНИЙ

1.1 Представление изображений в компьютере

1.1.1 Средства ввода изображения

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

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

Рисунок 1. Фрагмент матричного видео датчика

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

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

Рисунок 2. Переход от непрерывного изображения к дискретному

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

(1)

Для сокращения записи обозначим

(2)

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

(3)

где скобки обознают целую часть числа.

Если область определения непрерывного изображения - квадрат , и шаг дискретизации выбран одинаковым по осям , и , то

(4)

и размерность таблицы составляет .

Элемент таблицы, полученной путем дискретизации изображения, называют «пиксель» или «отсчет». Рассмотрим пиксель . Это число принимает непрерывные значения /4, с.30/.

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

Операцию аналого-цифрового преобразования (дискретизации непрерывной величины по уровню) часто называют квантованием. Число уровней квантования, при условии, что значения функции яркости лежат в интервале , равно

(5)

Рисунок 3 - Квантование непрерывной величины

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

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

1.2 Представление цвета в компьютерных системах

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

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

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

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

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

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

Наука, которая изучает цвет и его измерения, называется колориметрией. Она описывает общие закономерности цветового восприятия света человеком.

Одним из основных законов колориметрии являются законы смешивания цветов. Эти законы в наиболее полном виде были сформулированы немецким математиком Германом Грассманом:

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

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

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

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

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

3) Цвет смеси зависит только от цветов смешиваемых компонент и не зависит от их спектральных составов.

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

1.2.1 Аддитивная цветовая модель RGB

Данная модель построена на основе строения глаза. Она идеально удобна для светящихся поверхностей (мониторы, телевизоры, цветные лампы и т.п.). В основе ее лежат три цвета: Red- красный, Green- зеленый и Blue- синий. Еще Ломоносов заметил, что с помощью этих трех основных цветов можно получить почти весь видимый спектр. Например, желтый цвет- это сложение красного и зеленого. Поэтому RGB называют аддитивной системой смешения цветов.

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

1.2.2 Кодирование цвета. Палитра

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

Для модели RGB каждая из компонент может представляться числами, ограниченными некоторым диапазоном - например дробными числами от до либо целыми числами от до некоторого максимального значения. В настоящее время достаточно распространенным является формат True Color, в котором каждая компонента представлена в виде байта, что дает градаций для каждой компоненты: . Количество цветов составляет .

Такой способ кодирования цветов можно назвать компонентным. В компьютере коды изображений True Color представляются в виде троек байтов, либо упаковываются в длинное целое (четырехбайтное) - 32 бита (так, например, сделано в API Windows):

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

1.3 Повышение качества изображений и оценка их геометрических параметров

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

1) Улучшение зрительных характеристик: повышение контраста, четкости, выравнивание яркости по полю и т.д. Важно отметить, что речь здесь идет о качестве как о характеристике самого изображения (а не о мере близости к некоторому «эталону»), то есть цель обработки - получение в каком-то смысле «удобного для наблюдения», «хорошего» изображения.

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

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

1.3.1 Пороговая обработка

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

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

(6)

где - некоторое «пороговое» значение яркости (рисунок 4).

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



Рисунок 4. Пример порогового преобразования яркости изображения

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

Рисунок 5. К вопросу о выборе порога при пороговой обработке

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

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

Рисунок 6. Методики определения порога при пороговой обработке

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

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

где - аналитически заданные функции плотности вероятностей для объекта и фона;

- вероятность объекта (точнее, доля площади изображения, занимаемая объектом).

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

1.3.2 Повышение резкости изображений

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

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

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

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

Итак, повышение резкости заключается в усилении высокочастотных составляющих пространственного спектра изображения.

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

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

Пусть - произвольная строка исходного нерезкого изображения. На рис. 7 кривая 1 представляет собой строку изображения с расфокусированной границей объекта.



Рисунок 7. Пример подчеркивания границ с использованием низкочастотной фильтрации

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

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

Теперь рассмотрим эту процедуру подробнее для двумерного случая. Низкочастотная фильтрация (сглаживание) осуществляется усреднением отсчетов поля яркости в окне:

(7)



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

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

(8)

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

Далее вычисляются высокочастотное изображение

и изображение с повышенной резкостью

где - коэффициент усиления разностного (высокочастотного) сигнала .

Раскрывая обозначения, получаем

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

(9)

где - импульсная характеристика КИХ-фильтра, осуществляющего подчеркивание границ (повышение резкости);

(10)

На практике из соображений простоты берут обычно центрированное квадратное окно малого размера (3x3 или 5x5). При этом имеет всего несколько ненулевых отсчетов. Значения этих отсчетов удобно задавать в форме так называемой «маски».

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

(11)

соответствует случаю, когда сглаживание производится усреднением по пяти отсчетам,



с коэффициентом . Маска

(12)

получается при сглаживании усреднением по девяти точкам:

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

Два первых требования относятся к частотной характеристике КИХ-фильтра, которая в общем случае определяется соотношением

(13)

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

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

Найдем и покажем на координатной сетке некоторые значения частотной характеристики (см. рис. 8)

Рисунок 8. Пример частотной характеристики высокочастотного фильтра

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

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

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

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

Рассмотрим этот вопрос подробнее. Если на изображении присутствует шум, то это означает, что каждый отсчет искажен, и на вход высокочастотного КИХ-фильтра поступает не , а , где - аддитивный шум.

Тогда и на выходе фильтра имеем смесь: , где - шумовая составляющая на обработанном изображении,

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

 (14)

где - коэффициент увеличения мощности (дисперсии) шума после подчеркивания границ линейным фильтром:

(15)

Для рассмотренных выше масок этот коэффициент очень велик: для маски (11) , для маски (12) .

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

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

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

1.3.3 Оценка геометрических характеристик объектов на изображениях

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

Класс таких задач очень широк:

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

­ обнаружение объектов и определение их координат;

­ оценка геометрических параметров объектов и т.д.

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

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

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

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

Рассмотрим данный алгоритм измерения геометрических характеристик объектов на примере определения площадей объектов. Будем считать, что площадь - это число отсчетов, принадлежащих объекту, то есть каждый отсчет представляет собой квадрат единичной площади (рис. 9). Объект определяется по критерию четырехсвязности.

Рисунок 9. Иллюстрация к определению площади объекта

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

Если , то есть отсчет принадлежит фону, то осуществляется переход к следующему отсчету.

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

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

Если , и , то отсчет присоединяется к области, к которой принадлежит соседний по горизонтали единичный отсчет , пересчитывается характеристика этой области (прибавляется единица к площади).

Если и , то такое же действие выполняется по отношению к области, к которой принадлежит отсчет .

Если , то анализируются области принадлежности этих отсчетов.

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

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

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



Рисунок 10. Схема алгоритма расчета геометрических характеристик на изображении

Для окончательной ясности рассмотрим пример. Будем измерять площади объектов на фрагменте (рис. 11а). Составим таблицу площадей объектов и покажем, как она модифицируется и наращивается в процессе построчного просмотра отсчетов.

а) б)

Рисунок 11 - Измерение площади объекта на изображении: пример фрагмента изображения (а), пример разметки областей алгоритмом (б)

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

Таблица 1

Расчет площадей объектов на изображении

Текущий отсчет	Характеристика (площадь) области
		-	-
		-	-
			-
			-
			-
			-
		объединение с обл. 1	-
		-
		-

Разметка областей приведена на рис. 11б. В итоге получим две области: площадь первой - отсчетов, второй - отсчета.

Аналогично считаются и многие другие характеристики объектов. Единственным требованием к характеристикам, измеряемым по описанному алгоритму, является следующее: должно существовать правило вычисления характеристики объединенной области по характеристикам объединяемых областей. Конкретнее, пусть - характеристика, вычисленная по области (множеству отсчетов) . Тогда должно существовать правило такое, что

(16)

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

1) - «аддитивные» характеристики,

2) - «экстремальные» характеристики,

где - произвольные функции координат .

Примеры:

а) площадь , то есть - аддитивная характеристика с ;

б) координаты «краев» изображения по вертикали и горизонтали (рис. 12а).

Рисунок 12 - Измерение геометрических характеристик объектов: координаты краев области на изображении (а), область изображения и ее центр тяжести (б), максимальные линейные размеры объекта на изображении (в)

Здесь



экстремальные характеристики с и .

Подобные «объединяемые» характеристики можно назвать первичными (базовыми). По ним можно вычислять некоторые вторичные (производные) характеристики, которые сами по себе не удовлетворяют сформированному требованию. Рассмотрим, например, следующие.

1. Центр тяжести объекта или области (рис. 12б) для случая непрерывных аргументов вычисляется по формулам

(17)

Для цифрового изображения приведенные выражения запишутся в виде

(18)

то есть

(19)

- три аддитивные первичные характеристики.

2. Размеры объекта по вертикали и горизонтали (рис. 12в),

(20)

вычисляются через четыре экстремальные характеристики, рассматриваемые выше.

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

2. Распознавание изображений

2.1 Постановка задачи

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

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

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

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

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

­ отбор и упорядочивание признаков;

­ собственно классификация.

Задача отбора и упорядочивания признаков трудно формализуема. Критерием отбора и упорядочения является степень важности признаков для характеристики образов.

Задача классификации - принятия решения о принадлежности образа тому или иному классу на основе анализа вычисленных признаков - имеет целый ряд строгих математических решений в рамках детерминистического и вероятностного подходов /1, с.10/.

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

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

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

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

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

Рассматривая изображение буквы рис. 13(а) как двумерную последовательность, содержащую пикселей, можно вычислить ее двумерное ДПФ и отобрать из - пикселей спектра наиболее интенсивных. К. Фукунага для решения задачи отбора признаков предлагает разбить изображение на клеток и использовать в качестве признаков степень заштрихованности клеток. К. Фу предлагает работать со скелетизированными изображениями и выбирать в качестве признаков расстояние, измеренное в заранее заданном направлении от края квадрата до края буквы.

Рисунок 13. Иллюстрация отбора признаков в задаче распознавания печатных букв латинского алфавита

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

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

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

(21)

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

(22)

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

(23)

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

Рисунок 14. Пример разбиения двумерного пространства признаков

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

(24)

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

(25)

где

Этому уравнению соответствует гиперплоскость в пространстве . При выражение соответствует уравнению прямой.

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

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

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

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

2.2 Вероятностный критерий качества классификации

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

(26)

Как правило, на практике данное условие выполняется не всегда и существует вероятность неверно классифицировать объект и допустить ошибку при распознавании.

Обозначим вероятность того, что классификатор принимает решение об отнесении вектора признаков некоторого объекта к области , в то время как сам объект принадлежит классу :

(27)

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

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

(28)

В данном выражении:

­ - априорная вероятность появления объектов из класса

­ причем

­ - условная плотность вероятностей случайного вектора признаков для объектов класса (в теории распознавания образов ее называют функцией правдоподобия для соответствующего класса);

­ - безусловная плотность вероятностей случайного вектора ;

­ элементы квадратной матрицы

(29)

характеризуют величины штрафов или потерь за ошибки классификатора.

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

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

(30)

2.3 Оптимальные стратегии статистической классификации

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

Могут использоваться байесова, минимаксная стратегии или стратегия Неймана-Пирсона. В зависимости от того, какая из стратегий используется для построения классификатора, последний называют, соответственно, классификатором Байеса, минимаксным классификатором или классификатором Неймана-Пирсона.

Мы остановимся на рассмотрении классификатора Байеса, так как среди перечисленных выше классификаторов он работает с классами, в отличие от двух других, где количество классов ограничено двумя /8, с.10/.

2.3.1 Классификатор Байеса

Стратегия Байеса используется при наличии полной априорной информации о классах, то есть когда известны:

­ функции правдоподобия для каждого из классов;

­ матрица штрафов;

­ априорные вероятности для каждого из классов.

Стратегия решения выбирается таким образом, чтобы обеспечить минимум общего риска (30). Минимальный общий риск при этом называется риском Байеса. В соответствии с выражениями (28) и (30), минимум общего риска будет обеспечен, если разбиение пространства признаков будет осуществляться по следующему правилу: вектор относится к области только тогда, когда соответствующий условный средний риск минимален:

(31)

Иллюстрация стратегии Байеса приведена на рис. 15а.

Если матрица потерь (29) является простейшей, то есть, если ее элементы удовлетворяют равенству

то после подстановки в (31) выражения для условного среднего риска (28) имеем следующий явный вид классификатора Байеса (см. рис. 15а,б):

(32)

Из (32), в частности, видно, что решающими функциями классификатора Байеса являются функции

(33)

Часто используют также следующую форму записи классификатора Байеса:

(34)

Рисунок 15. Построение классификатора Байеса для простейшей матрицы штрафов: байесова стратегия минимизации общего риска (а), классификатор Байеса (б)

При этом функция



называется отношением правдоподобия, а величина

- пороговым значением /12, с.22/. Таким образом, классификатор Байеса основан на сравнении отношения правдоподобия с пороговым значением

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

с дискриминантными функциями:

3. распознаваниЕ ОБРАЗА ЧЕЛОВЕЧЕСКОГО ГЛАЗА

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

Поэтому я предлагаю конкретизировать задачу распознавания (т.е. рассмотреть её на примере распознавания человеческого глаза).

3.1 Аутентификация по радужной оболочке глаза

изображение цвет компьютерная система

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

Рисунок 16. Границы радужки

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

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

3.2 Методы распознавания по радужке

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

­ выделение радужки на изображении;

­ нормирование размеров изображения радужки;

­ вычисление признаков и формирование из них эталона;

­ радужки;

­ сравнение двух наборов признаков.

3.2.1 Выделение радужки на изображении

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



Рисунок 17. Результаты выделения радужки

3.2.2 Нормирование размеров изображения радужки

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

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

3.2.3 Этап вычисления признаков и формирования эталона радужки

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

3.3 Проблемы распознавания по радужке

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

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

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

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

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