РАСПОЗНАВАНИЕ НЕДЕФОРМИРУЕМЫХ ТРЕХМЕРНЫХ ОБЪЕКТОВ НА ИЗОБРАЖЕНИЯХ ПО КОНТУРАМ

Студент 545 гр. кафедры системного программирования СПбГУ, nikolai. *****@***com

Аннотация

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

Введение

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

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

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

Существующие решения

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

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

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

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

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

Предлагаемый подход

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

Выделение контуров

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

https://pandia.ru/text/78/196/images/image002_10.png" width="198" height="207 src=">

Выделение особых точек

Среди точек полученного градиента изображения оставляем только те, норма градиента в которых больше определенного порога, таким образом, получая точки контура. Для этих точек градиента оставим только угол между направлением градиента и осью Ох. Если угол α больше π, то запишем вместо него α - π, потому что градиент может быть направлен в противоположные стороны при различных фонах. Отказ от использования информации о норме градиента позволяет использовать точки контура, находящиеся в тени, тем же образом, каким точки контура в освещенной части объекта. Далее бинаризуем посчитанные углы в n бинов, то есть если угол α,: 0 < α < π / n, тогда он попадает в первый бин, а если α,: π / n < α < π * 2 / n, тогда во второй и так далее. Затем из точек удаляем те, для которых неверно, что направление в этой точке является самым частым направлением в некоторой небольшой окрестности точки. Это обеспечивает локальную сонаправленность точек контура и чистит контур от шума. Оставшиеся точки (направление и координаты) и будут использоваться для сравнения двух контуров

Создание базы по трехмерным моделям

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

Рис. 3 Пример трехмерной модели в ракурсе повернутом по оси Оу на 20 градусов и по оси Ох на 10 градусов от фронтального.

Функция схожести и ее подсчет

Назовем каждый контур из базы образцом модели в некотором ракурсе и масштабе. Сдвинем координаты точек в образцах так, чтобы абсцисса самой левой точки была нулем, а ордината самой верхней точки была тоже нулём. Тогда для входного изображения I в точке с и образца T можно ввести функцию схожести

где P – это множество точек образца, О – изображение, соответствующее образцу, ori(O, r) – бинаризованое направление градиента изображения О в точке r. Функция основана на работе Steger и подобная использовалась в работе Farhan . Проблема состоит в том, что такая функция совершенно не устойчива к изменениям, поэтому для каждой точки образца необходимо рассматривать некоторую окрестность R (например, квадрат 7х7 пикселей) вокруг прикладываемой точки:

DIV_ADBLOCK44">

0 " style="border-collapse:collapse;border:none">

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

Рис. 4 График схожести тестового примера по базе (по осям – углы вращения по х и по у). Он показывает, что в области правильного ракурса явный пик функции, который можно найти быстрее, чем перебором всех ракурсов.

Литература

1. Belongie, S.; Malik, J.; Puzicha, J., "Shape matching and object recognition using shape contexts," Pattern Analysis and Machine Intelligence, IEEE Transactions on , vol.24, no.4, pp.509,522, Apr 2002

2. Sebastian, T. B.; Klein, P. N.; Kimia, B. B., "On aligning curves," Pattern Analysis and Machine Intelligence, IEEE Transactions on , vol.25, no.1, pp.116,125, Jan. 2003

3. Macrini, D.; Shokoufandeh, A.; Dickinson, S.; Siddiqi, K.; Zucker, S., "View-based 3-D object recognition using shock graphs," Pattern Recognition, 2002. Proceedings. 16th International Conference on , vol.3, no., pp.24,28 vol.3, 2002

4. Farhan U.; Shun"ichi K.; Satoru I., “Object Search Using Orientation Code Matching”, IAPR Workshop on Machine Vision Applications, Nov. 28-30, 2000

5. C. Steger, “Occlusion Clutter, and Illumination Invariant Object Recognition,” in International Archives of Photogrammetry and Remote Sensing, 2002.

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

Рассмотрим пример распознавания простых объектов на основе набора признаков. При реализации метода в качестве основных будем использовать две функции bwlabel и imfeature, которые встроены в приложение Image Processing Toolbox.

Сначала считаем исходное тестовое изображение в рабочее пространство Matlab

L=imread("test_image.bmp");

и визуализируем его

Figure, imshow(L);

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

Функции bwlabel и imfeature в качестве исходных данных используют полутоновые двумерные изображения. Поскольку изображение test_image.bmp было сформировано как бинарное, но сохранено в формате bmp, то из трехмерной матрицы изображения L, которая содержит три идентичных цветовых шара, необходимо выделить один из шаров, например, первый.

L=L(:,:,1);

Такого же результата можно достичь, используя функцию rgb2gray. Таким образом, матрица L представляет бинарное двумерное изображение.

Для дальнейших расчетов определим размеры этого изображения

Size(L);

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

Bwlabel(L,8);

Кроме того, в функции bwlabel указывается еще один параметр – значение связности.

Далее приступаем к вычислению признаков объектов, которые отмечены в матрице номеров объектов L. Рассмотрим этот вопрос более подробно. Значения признаков возвращаются в массиве структур feats. Как было отмечено ранее, при распознавании объектов могут использоваться любые наборы признаков.

В рамках этого примера применим наиболее наглядный статистический подход к классификации объектов на основе морфометрических признаков. К основным морфометрическим признакам относятся коэффициенты формы:

1. ‘solidity’ – коэффициент выпуклости: равен отношению площади к выпуклой площади объекта. Представляется числом в диапазоне (0,1].
2. ‘extent’ – коэффициент заполнения: равен отношению площади объекта к площади ограничивающего прямоугольника. Представляется числом в диапазоне (0,1].
3. ‘eccentricity’ – эксцентриситет эллипса с главными моментами инерции, равными главным моментам инерции объекта. Представляется числом в диапазоне (0,1].

Поскольку в данном примере используется тестовое изображение объектов простой формы, то из перечисленных признаков в программной реализации будем использовать только коэффициент заполнения ‘extent’. Как было сказана ранее, параметр ‘extent’ определяется отношением площади объекта к площади ограничивающего прямоугольника. Для круга этот параметр будет равен , а для квадрата – 1. Но эти данные приведены для случая, когда круг и квадрат имеют идеальную форму. Если форма круга или квадрата искажена, то значения параметра ‘extent’ также могут отличаться от приведенных выше значений. Поэтому коэффициенты формы могут вычисляться с некоторой погрешностью. Таким образом, вводя некоторую погрешность в коэффициент формы, допускаются некоторые ее искажения. Причем значение погрешности пропорционально степени искажения. Однако слишком большое значение погрешности может привести к неправильному распознаванию объектов.

Дополнительно также будем определять центр масс объекта с помощью опции ‘centroid’.

Feats=imfeature(L,"Centroid","Extent",8);

Перепишем значения признаков из массива структур feats в отдельные массивы:

Extent=zeros(num); CentX=zeros(num); CentY=zeros(num); for i=1:1:num; Extent(i)=feats(i).Extent; CentX(i)=feats(i).Centroid(1); CentY(i)=feats(i).Centroid(2); end;

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

Krug=imread("krug.bmp"); Kvadrat=imread("kvadrat.bmp"); d=0.15; % погрешность коэффициента формы for i=1:num; L(round(CentY(i)):round(CentY(i))+1,round(CentX(i)):round(CentX(i))+1)=0; if (abs(Extent(i)-0.7822)

Представим результат распознавания

Figure, imshow(L);

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

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

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

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

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

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

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

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

4. Понимание и оценка. Процессом понимания изображения

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

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

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

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

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

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

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

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

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

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

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

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

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

Рис. 9.2. Кластер-анализ спектральной яркости природных объектов, отображенный и двумерную плоскость пары информативных спектральных каналов

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

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

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

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

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

Общая характеристика задач распознавания образов и их типы.

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

Рис. 4.1.

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

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

1. Это информационные задачи , состоящие из двух этапов: а) приведение исходных данных к виду, удобному для распознавания ; б) собственно распознавание (указание принадлежности объекта определенному классу).
2. В этих задачах можно вводить понятие аналогии или подобия объектов и формулировать понятие близости объектов в качестве основания для зачисления объектов в один и тот же класс или разные классы.
3. В этих задачах можно оперировать набором прецедентов-примеров , классификация которых известна и которые в виде формализованных описаний могут быть предъявлены алгоритму распознавания для настройки на задачу в процессе обучения.
4. Для этих задач трудно строить формальные теории и применять классические математические методы (часто недоступна информация для точной математической модели или выигрыш от использования модели и математических методов не соизмерим с затратами).
5. В этих задачах возможна "плохая" информация (информация с пропусками, разнородная, косвенная, нечеткая, неоднозначная, вероятностная).

Целесообразно выделить следующие типы задач распознавания .

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

Основы теории анализа и распознавания изображений.

Пусть дано множество M объектов ; на этом множестве существует разбиение на конечное число подмножеств (классов) i = {1,m} , Объекты задаются значениями некоторых признаков x j , j= {1,N}. Описание объекта называют стандартным, если принимает значение из множества допустимых значений.

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

где i= {1,m}, - неизвестно.

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

Пусть задан полный набор признаков x 1 , ..., x N . Выделим систему подмножеств множества признаков S 1 , ..., S k . Удалим произвольный набор признаков из строк , , ..., и обозначим полученные строки через , , ..., , .

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

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

Пусть - оценка объекта по классу .

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

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

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