Курс лекций по специальному курсу «Теория принятия решений и распознавания образов» (стр. 6 )

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

По Бейесу ищется решение минимизирующее средний риск.

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

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

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

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

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

Например:

Ÿ Горные работы - чел/час;

Ÿ Металлургическая промышленность - 0,6 чел/час;

Ÿ Транспортные работы - 10 чел/час;

Ÿ Работа с электричеством - 51 чел/час.

3. Распознавание образов

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

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

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

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

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

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

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

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

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

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

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

Рис.35. Обобщенная схема принятия решений при распознавании образов

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

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

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

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

Наиболее часто - это определение законов распределения и их параметров по имеющимся выборкам.

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

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

3.1 Классификация систем распознавания образов

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

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

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

Для классификации систем распознавания можно использовать следующие признаки:

1. Однородность информации для описания распознаваемых объектов или явлений.

2. Способ получения апостериорной информации.

3. Количество первоначальной априорной информации.

4. Характер информации о признаках распознавания.

1. Однородность информации. Здесь под однородностью следует понимать - различную или единую физическую природу информации (признаков).

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

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

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

2. Способ получения апостериорной информации. По этому принципу сложные системы распознавания делятся на одноуровневые и многоуровневые.

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

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

Таким образом:

Ÿ в одноуровневых СР информация о признаках распознаваемого объекта (апостериорная информация) формируется непосредственно на основе обработки прямых измерений;

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

3. Количество первоначальной априорной информации.

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

Соответственно этому системы распознавания делятся на системы без обучения, обучающиеся (ОСР) и самообучающиеся системы (ССР).

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

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

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

Исходная информация для обучающихся систем распознавания (ОСР) представляется в виде набора объектов w1, w2,...,wl, распределенных по m классам:

(w1 ,w2 ,...,wr ) W1

(w r+1 ,w r+2 ,...,wq ) W2

..................

(wg+1 ,wg+2 ,...,wl ) Wm

Простейшая цель обучения заключаются для ОСР в определении разделяющих функций

Fi(X1 ,X2 ,.....,Xn),

где i = 1,2,....,m (номер класса).

Определение этой функции осуществляется путем многократного предъявления системе указанных объектов (из набора w1,w2,....,wl ) с указанием, какому классу они принадлежат.

То есть, на стадии формирования ОСР работают с “учителем”, осуществляющим указание о принадлежности предъявленного для обучения объекта. И прежде, чем система будет применяться, должен пройти этап обучения.

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

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

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

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

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

4. Характер информации о признаках распознавания.

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

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

Характеристики систем по данному признаку классификации приведены в таблице 7.

3.2. Алфавит признаков, его компоновка и минимизация

Методика формирования компактного алфавита признаков

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

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

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

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

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

Рис.36. Сжатие описаний пространства признаков до соприкосновения доверительных интервалов границ классов (А и В)

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

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

На рис. 37 приведены графики сигналов до (пунктир) и после (сплошная) укрупнения. Сигнал поднят на 200 единиц для лучшего различия. Из графиков видно то, что два объекта после сжатия сохранили свойство обнаружения.

Рис.37. Сигналы от объектов до и после сжатия

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

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

Как правило при перекодировке учитывается частота появления цветов о объектов исследуемого класса.

Перекодировка обычно выполняется табличным преобразованием, при котором исходные компоненты описания пикселя является смещениями для таблиц перекодировки.

Интегрально таблицы преобразований выглядят как новые цветовые палитры.

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

Например: если W - исходное изображение, w - бинаризованное изображение, y, x - координаты бинаризуемый точки, xs, ys - размеры сегмента, hx, hy - шаг смешения сегмента, nx - число сегментов по x, то правило бинаризации можно записать следующим выражением:

,

где среднее, медиана или мода j - го сегмента.

3.3. Распознавание объектов по геометрическим параметрам

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

Рис.38. Сигнал в стереоскопическом дальномере

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

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

Далее формируется описание объектов в пространстве их яркостных и геометрических параметров (линейных размеров).

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

После обнаружения определяются координата схожих объектов в зоне левого канала наблюдения ( ~ 23000 мкм).

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

Вторая задача – идентификация стволов нарезного оружия по следам на пулях.

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

Рис. 39. Трассы сканирования оболочки пули и профилограммы

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

Рис. 40. Профилограмма с эксцентриситетом

Рис. 41. Профилограмма после устранения эксцентриситета

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

Рис. 42. Сравниваемые профилограммы в полярной системе координат

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

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

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

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

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

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

Определение положения границ объекта по переходам свет/тень.

Часто данная операция проходит путем сравнения с порогом фиксированным или адаптивно перестраиваемым по форме сигнала в зоне фронта.

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

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

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

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

Сформируем пороговой обработкой адаптивный фильтр – рис. 43.

Вычислим свертку сигнала с правой частью фильтра. Результат вычислений приведен на рис. 44. Отчетливо виден пик сигнала, по его положению несложно оценить координату объекта (4214 мкм). Это и есть грубо вычисленная координата. Ее дискретность – 14 мкм (шаг элементов фотоприемной матрицы).

Рис. 43. Цифровой фильтр селекции сигналов

Рис. 44. Отклик на интегрирующий поисковый фильтр

Как видно из графиков (рис. 38 и рис. 44) улучшилось соотношение

сигнал /шум. Оценить улучшение количественно можно оценив шум вне зоны сигнала и размах сигнала.

,

где si – соотношение сигнал/шум в децибелах для исходного и отфильтрованного сигналов, точка b – положение максимума сигнала, r_mean, r_stdev – оценки среднего и среднеквадратичного отклонения на участке предшествующем сигналу. Расчеты показали увеличение si после фильтрации практически на 8 децибел.

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

Формулу свертки оставляют прежней.

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

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

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

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

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

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