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

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

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

P_i(ω Ω_i)={1(ω Ω_i), 0(ω Ω_i), (ω Ω_i)},

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

Таблица 4.1. Таблица обучения

Объект

Признаки и их значения

Класс

x₁

x_j

x_n

_ω1

₁₁

_1j

_1n

Ω₁

...

ω_r1

_r11

_r1j

_r1n

...

ω_rk

_rk1

_rkj

_rkn

Ω_m

...

ω_rm

_rm1

_rmj

_rmn

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

Пусть задан полный набор признаков x₁, ..., x_N. Выделим систему подмножеств множества признаков S₁, ..., S_k. Удалим произвольный набор признаков из строк ω₁, ω₂, ..., ω_rm и обозначим полученные строки через Sω₁, Sω₂, ..., Sω_rm, Sω' .

Правило близости, позволяющее оценить похожесть строк Sω' и Sω_r состоит в следующем. Пусть "усеченные" строки содержат q первых символов, то есть Sω_r=(a₁, ..., a_q) и Sω'=(b₁, ..., b_q) . Заданы пороги ε₁...ε_q, . Строки Sω_r и Sω' считаются похожими, если выполняется не менее чем неравенств вида

|a_j-b_j| ε_j, j=1,2,..., q.

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

Пусть Г_i(ω') - оценка объекта ω' по классу Ω_i.

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

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

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

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

x₃- количество наклонных линий;

x₄- количество горизонтальных линий снизу объекта.

Рис. 4.2.  Пример задачи по распознаванию

На рис. 4.3 приведена таблица обучения и пороги

ε₁=1, ε₂=1, ε₃=1, ε₄=1, =1.

Из этой таблицы видно, что неразличимость символов 6 и 9 привела к необходимости ввода еще одного признака x₄.

Рис. 4.3.  Таблица обучения для задачи по распознаванию

Теперь может быть построена таблица распознавания для объектов на рис. 4.2б.

Читателю предлагается самостоятельно ответить на вопрос: что будет, если увеличить пороги ε₁, ε₂, ε₃, ε₄, ? Как изменится качество распознавания в данной задаче?

Заключая данный раздел лекции, отметим важную мысль, высказанную А. Шамисом в работе [55]: качество распознавания во многом зависит от того, насколько удачно создан алфавит признаков, придуманный разработчиками системы. Поэтому признаки должны быть инвариантны к ориентации, размеру и вариациям формы объектов.