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

Пусть дано множество 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(ω) вычислить предикаты:

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

Таблица 4.1. Таблица обучения
Объект	Признаки и их значения	Класс
x1	xj	xn
ω 1	11	1j	1n	Ω 1
...
ω 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ω ' считаются похожими, если выполняется не менее чем неравенств вида

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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