Распознавание объектов на изображении

СОДЕРЖАНИЕ

Введение…………………………………………………………………………………………………..3

Глава 1. Распознавание изображений……………………………………………………………………4

   1.1 Вероятностный критерий качества классификации………………………….…….……..4

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

   1.3 Основные группы признаков, используемых при распознавании        изображений……………………………………………………………………………………………….6

Глава 2. Обнаружение и распознавание объектов на изображениях……………………….…….……7

   2.1 Задачи распознавания на изображениях…………………………………………….……..7

   2.2 Формирование признаков по изображению…………………………………...…….…….9

   2.3 Обнаружение и локализация объектов на изображении……………………..…….…….12

2.3.1 Критерии локализации объектов……………………………………….…….…....13

2.3.2 Совместное обнаружение и локализация объектов…………………..…….…….14

Глава 3. Простая модель распознавания  образов………………………………………………….……17

Приложение. Пример программы по распознаванию объекта на изображении и нахождению некоторых его геометрических характеристик…………………………………….…….…….…….…19

Заключение……………………………………..……………………………………………...…….……21

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

ВВЕДЕНИЕ

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

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

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

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

    Первые попытки изучения возможностей автоматизации процесса распознавания образов относятся к началу 50-х годов, когда цифровые вычислительные машины постепенно стали общедоступным средством обработки информации. В конце 50-х годов Розенблатт предложил персептронный алгоритм, который представлял собой одну из первых моделей процессов запоминания и организации информации, реализуемых мозгом. Базой для решения задач отнесения объектов к тому или иному классу послужили результаты классической теории статистических решений. В её рамках строились алгоритмы, обеспечивающие на основе экспериментальных измерений параметров, характеризующих этот объект, а также некоторых априорных данных, описывающих классы, определение конкретного класса, к которому может быть отнесен распознаваемый объект.  К середине 70-х годов определился облик распознавания как самостоятельного научного направления, появилась возможность создания нормальной математической теории распознавания.  Cущественный вклад в дисциплину распознавания образов внесли Ф. Розенблатт, В.М. Глушков, В.С. Михалевич, В.С. Пугачев, Н.П. Бусленко, Ю.И. Журавлев, Я.З. Цыпкин, А.Г. Ивахненко, М.М. Бонгард, В.Н. Вапник, Г.П. Тартаковский, В.Г. Репин, Л.А. Растригин, А.Л. Горелик, В.Л. Матросов, Р. Гонсалес, У. Гренандер.

ГЛАВА 1.  РАСПОЗНАВАНИЕ ИЗОБРАЖЕНИЙ

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

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

• отбор и упорядочивание признаков (критерием является степень важности признаков для характеристики образов);
• классификация (её задача – принятие решения о принадлежности образа тому или иному классу на основе анализа вычислительных признаков);

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

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

   При использовании любого из данных подходов мы получаем в качестве признаков упорядоченный набор числовых данных, обозначающих вектор признаков y = (y_o, y₁, … , y_k-1)^T, который можно рассматривать как точку в k-мерном пространстве признаков D.

С геометрической точки зрения задача классификации – разбиение  пространства признаков D на L взаимно непересекающихся областей D_l (l = 0,…, L-1), каждая из которых соответствует некоторому классу Ω_l образов.

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

Классификатор должен быть таким, чтобы области, выделяемые в  пространстве признаков, соответствовали  классам, то есть должно выполняться  условие: объект ω принадлежит классу Ω_l тогда и только тогда, когда соответствующий объекту вектор признаков y(ω) принадлежит области D_l .

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

       Обозначим p_lj (  l, j = 0, … , L-1) вероятность того, что классификатор принимает решение об отнесении вектора признаков некоторого объекта к области Dj, в то время как сам объект принадлежит классу Ω_l .

 При l ≠ j вероятности p_lj характеризуют ошибки распознавания и называются вероятностями неверной (ошибочной) классификации, а при l = j вероятности p_lj задают вероятности верной классификации представителей соответствующего класса.

 То есть основная  задача при построении классификатора  – уменьшение вероятностей ошибочной  классификации.

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

  В данной формуле:

• P(Ω_l) – априорная вероятность появления объектов из класса Ω_l
• p(y / Ω_l) – условная плотность вероятностей случайного вектора признаков Y для объектов класса Ω_l (или функция правдоподобия для класса)
• p(y) – безусловная плотность вероятностей случайного вектора Y
• c = (c_ij), (i,j = 0,..L-1) – элементы квадратной матрицы, характеризующие величины штрафов (потерь) за ошибки классификатора.

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

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

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

1) Классификатор Байеса. Стратегия Байеса используется при наличии полной априорной информации о классах, то есть когда известны: функция правдоподобия для каждого из классов, матрица штрафов и априорные вероятности для каждого класса. Стратегия выбирается таким образом, чтобы обеспечить минимум общего риска (риск Байеса). Он будет обеспечен, если разбиение пространства признаков D будет осуществляться по правилу: вектор y принадлежит области D_l тогда и только тогда, когда соответствующий условный средний риск R_l(y) минимален. Классификатор Байеса также называется классификатором отношения правдоподобия.

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

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

3) Классификатор Неймана – Пирсона. Тоже используется в случае двух классов, если известны только функции правдоподобия для каждого из классов. Суть в следующем: задаётся допустимое значение вероятности ошибки первого рода p₀, а затем классификатор строится так, чтобы обеспечить минимум вероятности ошибки второго рода p₁. Классификатор Неймана-Пирсона – это классификатор отношения правдоподобия.

1.3  Основные  группы признаков, используемых  при распознавании изображений

     1)Геометрические признаки. Группа основана на использовании геометрических характеристик, представленных на изображении объектов.

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

     Основные методы описания контура:

• Цепные коды. Метод цепного кодирования предложен Фриманом. Он заключается в том, чтобы границу объекта, расположенного на дискретной сетке, представить в виде набора элементарных отрезков. В этом случае полной характеристикой границы в каждой точке является направление требуемого отрезка. Здесь предполагается, что точки на границе являются четырёхсвязными (отрезок складывается в четырёх направлениях). Достоинство представления границы объекта цепным кодом – простота реализации алгоритма его описания,  простота получения из описания других геометрических характеристик объекта, возможность достижения инвариантности описания к преобразованиям подобия (масштабирование изображения,  его перенос и поворот).  Недостаток – неустойчивость описаний к искажениям в изображениях.
• Ортогональные представления функции кривизны. Угол наклона к касательной контура рассматривается как периодическая функцию некоторой переменной и получается представление контура в виде ряда Фурье, коэффициенты этого ряда называются фурье-дискрипторами данного контура. Такое описание обладает свойствами инвариантности к преобразованиям подобия, но для его использования необходимо получить промежуточное представление контура в виде функции. Это может быть сделано с помощью ѱ-кривых.
• ѱ-кривые. Представление контура объекта с использованием ѱ-кривой основано на аппроксимации прямолинейных участков границы объекта в виде отрезков ломаных, а области изменения направления границы – в виде дуг окружностей. В этом случае периодическая функция оказывается представлена прямолинейными горизонтальными участками и короткими кривыми, соответствующими областям изменения границы. При правильном построении ѱ-кривых можно добиться инвариантности к преобразованиям подобия.
• Сплайн-аппроксимация границы используется для практических приложений, в частности, для решения задачи описания границы. Суть метода – представление границы объекта в виде кусочно-полиномиальной функции. При использовании наиболее простого задания функции в виде горизонтальных прямых с разрывом в точках изменения направления границы, получаем представление контура в виде полилиний (соединяющихся между собой отрезков прямых).

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

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

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

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

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

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

ГЛАВА 2. ОБНАРУЖЕНИЕ И РАСПОЗНАВАНИЕ ОБРАЗОВ НА ИЗОБРАЖЕНИЯХ

2.1 Задачи распознавания образов на изображениях

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

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

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

      В задачах распознавания образов можно выделить два основных направления.

       1) Изучение способностей к распознаванию, которыми обладают живые организмы.

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

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

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

     Перейдем теперь именно к вопросу о распознавании образа на изображении.

     Круг задач можно разделить на две группы:

       1) распознавание и классификация изображений; 

       2) поиск и распознавание объектов на изображениях.

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

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

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

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

    Примеры задач второй группы: дешифрование аэрокосмических снимков, автоматическое чтение текстов и другие.

    Решение задач второй группы представлено в схеме ниже.

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

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

2.2 Формирование признаков по изображению

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

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

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

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

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

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

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

  1) Нормализация изображений при вычислении признаков.

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

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

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

 2) Нормализация масштаба объекта. Изменение масштаба объекта приводит к тому, что доля    относящихся к объекту отсчетов будет увеличена или уменьшена пропорционально квадрату величины изменения линейных размеров. Пусть K - доля площади изображения, занятая объектом на эталонном изображении, µ₀ = A₀ + A и µ_B = A – средние объекта и фона. При изменении масштаба средние изображения изменяются в соответствии с изменением доли k отсчетов, относящихся к объекту: µ_f = k µ₀ + (1- k) µ_b, откуда

    В результате линейное изменение масштаба

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

  3) Нормализация ориентации объекта. Геометрический подход основан на использовании степенных моментов.  

    Выберем в качестве нормализованной ориентации положение центрированного изображения, при котором момент второго порядка µ₁₁=0. Для симметричного объекта данное условие соответствует ситуации ,когда ось симметрии объекта расположена вдоль оси абсцисс или ординат.

    Пусть изображение повёрнуто относительно своего нормализованного положения. Тогда соответствие между моментами первого и второго порядка запишется так:

-

    Здесь µ₁₁(0) = 0 – момент нормализованного изображения, φ – угол поворота изображения против часовой стрелки, относительно начального положения.  Тогда

= ,        

    Это выражение определяет ориентацию неоднозначно, а с точностью до поворота на tπ/2. Для однозначного ориентирования изображения можно воспользоваться значениями моментов µ₀₂, µ_20, µ₃₀  так: в выражении выше коэффициент t выбирается исходя из условий:

t  =

   В случае нормализации бинарного изображения можно использовать статистический подход. Тогда в качестве ориентации объекта выбирают направление собственного вектора x_λ матрицы ковариации B координат отсчётов ненулевой яркости. При этом собственный вектор должен соответствовать максимальному собственному числу λ_max матрицы ковариации.

 К определению ориентации по собственному вектору матрицы ковариации: «- - >» - собственный вектор, соответствующий максимальному собственному числу, «- - - >» - собственный вектор, соответствующий минимальному собственному числу, «----- >» - оси координат изображения.

      Пусть матрицы ковариации имеет вид B= ,  возможные собственные значения λ находятся из уравнения (B-λE) x_λ =0,  где Е – единичная матрица, x_λ – собственный вектор, соответствующий числу λ. Из данного уравнения получим

    Тогда собственный вектор, соответствующий λ_max, равен

    Cоответствует углу наклона φ такому, что

      Для центрированного изображения , ,