Математические методы моделирования, обнаружения и идентификации объектов

Министерство науки и высшего образования Российской Федерации 
 
НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ 

 
 
 
 
 
 
И.В. БОРИСОВА 
 
 
 
 
 
МАТЕМАТИЧЕСКИЕ МЕТОДЫ  
МОДЕЛИРОВАНИЯ,  
ОБНАРУЖЕНИЯ  
И ИДЕНТИФИКАЦИИ ОБЪЕКТОВ 
 
Утверждено Редакционно-издательским советом университета 
в качестве учебного пособия 
 
 
 
 
 
 
 
 
 
 
 
НОВОСИБИРСК 
2020 

 

УДК 004.93(075.8) 
         Б 825 
 

Рецензенты: 

д-р техн. наук, доцент, профессор  В.Н. Легкий, 
канд. техн. наук М.М. Кузнецов 
 
Работа подготовлена на кафедре автономных информационных 
и управляющих систем факультета летательных аппаратов 
 
 
Борисова И.В. 
Б 825   
Математические методы моделирования, обнаружения и 
идентификации объектов: учебное пособие / И.В. Борисова. – 
Новосибирск: Изд-во НГТУ, 2020. – 91 с. 
 
ISBN 978-5-7782-4320-0 
 
Представлены основы теории распознавания образов, принципы 
работы нейронных сетей и современные подходы к моделированию и 
распознаванию объектов по их изображениям. Рассматриваются дескрипторы изображений, инвариантные к масштабу, принципы построения и обучения классификаторов. 
Учебное пособие предназначено для студентов старших курсов и 
магистрантов, обучающихся по направлению подготовки 27.04.04 
«Управление в технических системах», магистерская программа «Автономные информационные и управляющие системы», специальности 
17.05.01 «Боеприпасы и взрыватели», специализация «Автономные системы управления действием средств поражения». Пособие будет полезно также студентам, обучающимся по направлениям и специальностям в области обработки информации. 
 
УДК 004.93(075.8) 
 
 
ISBN 978-5-7782-4320-0  
 
 
 
 
 
 Борисова И.В., 2020 
 Новосибирский государственный 
    технический университет, 2020 

 

ВВЕДЕНИЕ 

В своей практике человек решает разнообразные задачи по классификации и распознаванию объектов, явлений и ситуаций. Для этого он 
использует огромные ресурсы своего мозга и опыт, накопляемый в течение всей жизни. Работы по автоматизации процесса распознавания 
образов начались в 50-х годах ХХ века, для решения таких задач в этот 
период использовались идеи теории статистических решений. В 1957 г. 
Ф. Розенблатт предложил техническую модель зрительного анализатора 
(персептрон) которая положила начало развитию нейронных сетей. 
Дальнейшие исследования привели к формированию теории распознавания образов как самостоятельного научного направления. Помимо 
аналитических методов, отличающихся строго количественным подходом к образам, были разработаны синтаксические методы, использующие взаимосвязи между компонентами образа. 
При решении задач обнаружения и распознавания объектов по их 
изображениям приходится учитывать следующие особенности: 
 объекты могут иметь малый контраст по отношению к фону; 
 характеристики изображений фона не могут быть определены заранее; 
 объекты должны обнаруживаться при частичной видимости; 
 видимый размер объектов и их ракурс могут изменяться; 
 должна быть возможность обработки информации, полученной от 
различных датчиков, в разных спектральных диапазонах. 
Признаки изображений, лежащие в основе многофункциональной 
обработки видеоинформации, должны быть  универсальными, чтобы 
позволить реализовать все требуемые возможности системы. Особое 
внимание исследователей занимает применение ориентации градиента 
яркости в окрестности точки как локального признака изображений. 
В последние два десятилетия активно развиваются подходы к описанию 

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

 

1. ОСНОВЫ ПОСТРОЕНИЯ СИСТЕМ  
РАСПОЗНАВАНИЯ ОБРАЗОВ 

Способность к распознаванию образов считается основным свойством живых организмов. Для человека характерны два типа распознавания: конкретных объектов и абстрактных объектов. Процессы, включающие распознавание зрительных и слуховых образов, можно определить как «сенсорное» распознавание. Мы распознаем рисунки, символы, музыку, речь и окружающие нас объекты. С другой стороны, математическую задачу можно решить с закрытыми ушами и глазами. Распознавание абстрактных объектов можно определить как «понятийное». 
Для распознавания человек использует накопленный им опыт: входной 
образ сравнивается со статистическими совокупностями и выполняется 
оценка относительных шансов на то, что исходные данные соответствуют тому или иному из известных множеств. 
Классическая задача распознавания образов рассматривается как 
задача отнесения исходных данных к определенному классу с по- 
мощью выделения существенных признаков (инвариантных свойств), 
характеризующих эти данные, из общей массы несущественных признаков. Под классом образов понимается некоторая категория, определяемая рядом свойств, общих для всех ее элементов. Образ – это описание любого элемента как представителя соответствующего класса 
образов. 
В различных задачах понятию «образ» придается различный смысл. 
Чаще всего под образом понимают вектор значений признаков объектов, но в задачах сравнения с эталоном это может быть и непосредственно фрагмент изображения. Более того, иногда понятие «образ» используют вместо понятия «модель», считая его некоторым структурированным приближенным описанием изучаемого объекта, явления или 
процесса. 

1.1. ОСНОВНЫЕ ЗАДАЧИ, ВОЗНИКАЮЩИЕ  
ПРИ РАЗРАБОТКЕ СИСТЕМ РАСПОЗНАВАНИЯ ОБРАЗОВ 

1. Представление исходных данных. На этом этапе определяются 
все возможные признаки, характеризующие объект или явление. Результаты измерений объекта (значения признаков) представляются в 
виде вектора образа. 
Виды признаков: 
 детерминированные, т. е. имеющие конкретные и постоянные числовые значения; 
 вероятностные, т. е. носящие случайный характер; 
 логические, т. е. качественные суждения о наличии либо об отсутствии некоторых свойств или составляющих у объектов или явлений; 
 структурные, т. е. элементарные элементы, примитивы изображения объекта распознавания. 

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

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

1.2. ПРИНЦИПЫ ПОСТРОЕНИЯ СИСТЕМ РАСПОЗНАВАНИЯ 

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

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

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

1.3. ВЫБОР СИСТЕМЫ ИНФОРМАТИВНЫХ ПРИЗНАКОВ 

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

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

Метод последовательного сокращения признаков (Del) 

Пусть задача состоит в том, что из 50 признаков нужно выбрать 25 
наиболее информативных. Оценим ошибку распознавания при использовании всех 50 признаков (
0
 ). Исключим из системы первый признак, 
и найдем ошибку ( 1 ), которую дают оставшиеся 49 признаков. Затем 
исключим из исходной системы второй признак и найдем ошибку (
2
 ) 
в новом 49-мерном пространстве. Эту операцию поочередного исключения одного признака проведем 50 раз. 
Среди полученных величин 
1
50
,...,


 найдем самую малую. Она 
укажет на признак, исключение которого из системы было наименее 
ощутимым. Исключим этот признак из системы и приступим к испытанию оставшихся 49 признаков. Эти процедуры повторяются до тех пор, 
пока в системе не останется заданное число признаков. 

Метод последовательного добавления признаков (Add) 

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

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

Алгоритмы AddDel и DelAdd 

Алгоритмы Add и Del дают оптимальное решение на каждом шаге, 
но это не обеспечивает глобального оптимума. Их сочетание позволяет 
получить лучшие результаты. В алгоритме Add набирается некоторое 
количество информативных признаков и затем часть из них исключается методом Del. После этого размерность информативных признаков 
вновь наращивается алгоритмом Add. Далее снова включается алгоритм 
Del, который исключает из системы «наименее ценные» признаки. Такое чередование алгоритмов Add и Del продолжается до достижения заданного количества признаков. 
Возможна и обратная стратегия: вначале работает алгоритм Del, после сокращения  исходной системы признаков включается алгоритм 
Add, который возвращает в систему ошибочно исключенные из нее признаки. Повторение этих процедур (алгоритм DelAdd) продолжается до 
получения системы из наиболее информативных признаков. 
Эксперименты Института математики СО РАН показали, что алгоритм AddDel приводит к лучшим результатам, чем алгоритмы Add, Del 
и DelAdd [8]. 
Программа, реализующая алгоритм AddDel, применялась при решении задач генетики для выбора признаков, по которым нужно было распознавать три образа. Исходная система включала в себя 444 признака. 
Количество объектов в обучающей выборке было 548. При каждом 
шаге увеличения или уменьшения числа признаков методом скользящего экзамена выполнялось распознавание обучающей выборки и оценивалось количество ошибок. Обнаружилось, что сначала количество 
ошибок уменьшалось, затем начиналось их увеличение. Это позволило 

выбирать как оптимальный состав, так и оптимальное количество признаков. В результате была найдена система из семи признаков, которые 
обеспечили наименьшее число ошибок. 
В другой задаче из области психофизиологии анализировалась таблица, состоящая из 27 объектов, разделенных на три образа, и 280 признаков. Алгоритм AddDel выбрал 11 признаков, обеспечивших безошибочное распознавание  контрольной выборки. 

1.4. КЛАССИФИКАЦИЯ ОБРАЗОВ С ПОМОЩЬЮ 
ФУНКЦИЙ РАССТОЯНИЯ 

Набор из m признаков образует m-мерное пространство признаков, 
или пространство измерений. Каждый объект представляется своим образом как вектор значений признаков, или точка в этом многомерном 
пространстве. В задачах классификации используется эмпирическая гипотеза компактности. Это предположение о том, что сходные образы 
гораздо чаще принадлежат одному классу, чем разным. При этом 
классы образуют компактно локализованные области в пространстве 
признаков  кластеры. Конечно, гипотеза компактности подтверждается не всегда. Если, например, среди признаков имеется много случайных, неинформативных, то точки одного класса могут оказаться далекими друг от друга и рассеянными среди точек других классов. Поэтому 
при выборе системы признаков обычно выполняют пробную классификацию, стремясь к тому, чтобы признаки правильно представляли класс 
объектов, а гипотеза компактности подтвердилась. 
Для формализации понятия сходства образов вводится функция расстояния в пространстве признаков. Эта функция может быть и метрикой, если она удовлетворяет аксиомам метрики, но это не обязательное 
требование. 
Обозначим вектор значений признаков объекта (образ) в m-мерном 
пространстве признаков как 
Т
1
2
,
, .
(
)
.. ,
m
х х
x

Х
. В качестве расстояния 
между классами (или между точкой и классом) могут быть использованы расстояния из семейства функций расстояния Минковского: 

 

1

1
(
,
)
,
m
p
p
i
j
il
jl
l
e
x
x











X X
 
(1.1) 

для p ≥ 1 расстояние будет метрикой, для p < 1  метрикой не будет.