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

Московский государственный университет им. М.В.Ломоносова

На правах рукописи

БУРЯКДмитрий Юрьевич

МЕТОД АВТОМАТИЗИРОВАННОГО КОНСТРУИРОВАНИЯ ПРОЦЕДУР АНАЛИЗА ИЗОБРАЖЕНИЙ С ИСПОЛЬЗОВАНИЕМ ГЕНЕТИЧЕСКИХ АЛГОРИТМОВ

Специальность 05.13.11 - математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата физико-математических наук

Москва-2004

Работа выполнена на кафедре автоматизации систем вычислительных комплексов факультета вычислительной математики и кибернетики Московского государственного университета им. М.В. Ломоносова.

Научные руководители: доктор физико-математических наук,

профессор, член-корреспондент РАН Королев Лев Николаевич; кандидат физико-математических наук, доцент

Попова Нина Николаевна.

Официальные оппоненты: доктор физико-математических наук, доцент

Жданов Александр Аркадьевич; кандидат физико-математических наук Богомолов Никита Александрович.

Ведущая организация: Федеральное государственное унитарное

предприятие «Государственный научно-исследовательский институт авиационных систем» (ФГУП «ГосНИИАС»)

Защита диссертации состоится " АЗ " _2004 г. в

// часов на заседании диссертационного совета Д 501.001.44 в МГУ им. М.В. Ломоносова по адресу: 119992, ГСП-2, Москва, Ленинские горы, МГУ, 2-й учебный корпус, факультет ВМиК, аудитория 685.

С диссертацией можно ознакомиться в библиотеке факультета ВМиК

МГУ.

Автореферат разослан

/ Ученый секретарь диссертационного совета профессор

Н.П. Трифонов

Общая характеристика работы

Актуальность работы

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

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

сие. КЛЦИОНАЛЬНЛЯ I БИБЛИОТЕКА. I С.Пете» О»

ЛИОТЕКА I

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

Цель работы

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

Процедуры, отвечающие указанным требованиям, будем называть эффективными решающими процедурами.

Для достижения поставленной цели требуется:

• сформулировать основные принципы автоматизации процесса конструирования процедур идентификации и обнаружения объектов на изображениях;

• разработать модели процедур идентификации и обнаружения объектов;

• разработать критерий оценки эффективности конструируемых решающих процедур;

• разработать метод отбора эффективных процедур идентификации и обнаружения;

• разработать программное обеспечение, реализующее данный метод;

• провести экспериментальное исследование эффективности предложенного метода.

Научная новизна работы

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

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

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

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

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

Практическая значимость

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

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

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

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

• автоматические системы принятия решений, основанные на анализе визуальной информации;

• робототехника;

• системы контроля качества продукции на производстве.

Апробация работы и публикации

Результаты работы докладывались и обсуждались на следующих конференциях и семинарах:

• XI Международная научная конференция студентов и аспирантов по фундаментальным наукам "Ломоносов", Россия, Москва, 2002;

• 12-я Международная конференция по компьютерной графике ГРАФИКОН-2002, Россия, Нижний Новгород, 2002;

• 6-я Международная конференция "Распознавание образов и анализ изображений: новые информационные технологии" (РОАИ-6-2002), Россия, Великий Новгород, 2002;

• Ломоносовские чтения-2003, Россия, Москва, 2003;

• Всероссийская научно-техническая конференция "Методы и средства обработки информации" (МСО-2003), Россия, Москва, 2003;

• Семинар по обработке экспериментальных данных при помощи нейронных сетей и генетических алгоритмов под руководством Королева Л.Н. и Поповой Н.Н. (факультет ВМиК МГУ).

• Научно-исследовательский семинар по автоматизации программирования под руководством Шура-Бура М.Р.

Основные результаты работы изложены в 8-и научных публикациях.

Структура и объем работы

Диссертация состоит из введения, четырех глав, заключения и списка литературы. Содержание работы изложено на 126 страницах. Список литературы включает 64 наименования. В работе содержится 42 рисунка и 5 таблиц.

Содержание работы

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

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

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

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

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

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

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

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

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

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

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

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

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

• Объекты представлены своими проекциями на плоскость.

• Объекты одного класса получены путем одного и того же вида проектирования на плоскость и имеют одинаковую структуру.

• Допускается пропорциональное изменение размеров объектов одного класса (масштабирование).

• Ориентация и положение объекта в плоскости не фиксированы. Метод оперирует изображениями, представленными в пиксельном

виде. Исходными данными для метода являются:

• эталонные изображения объектов распознаваемых классов, по одному для каждого класса;

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

• пороговое значение для меры близости - число из интервала (0,1], такое что, если значение меры близости двух изображений превышает данный порог, то считается, что на изображениях представлены объекты, относящиеся к одному классу;

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

которая обладает следующими свойствами:

• является минимизированной по времени своего выполнения;

• идентифицирует объекты заданных классов в соответствии с заданным порогом для меры близости;

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

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

В рамках разработанного метода каждая процедура в общем случае представима в виде упорядоченной последовательности: где является процедурой идентификации некоторого фрагмента объекта заданного класса. Такие процедуры р^ будем называть элементарными процедурами. Элементарная процедура идентифицирует соответствующий ей фрагмент в некоторой позиции на изображении, если значение меры близости между фрагментом и областью изображения в данной позиции превышает заданное пороговое значение. Число элементарных процедур, входящих в последовательность, будем называть длиной процедуры Решение об идентификации объекта на изображении принимается на основе результатов последовательного применения к этому изображению каждой из элементарных процедур. Будем считать, что процедура осуществила идентификацию заданного объекта, если на изображении были обнаружены все фрагменты, сопоставленные элементарным процедурам Пусть множество IV состоит из

всевозможных процедур, отвечающих описанной структуре.

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

настройки одной из моделей базовых алгоритмов распознавания.

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

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

изображению и с использованием алгоритмов из базы знаний.

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

Для построения процедур, формирующих множество на

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

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

Рис. 1. Конструирование процедуры идентификации.

Поиск оптимальной процедуры идентификации в подмножестве Ж осуществляется при помощи генетических алгоритмов.

Была разработана модель процедуры идентификации р=(р1,р2,...,рт)> которая обладает следующими свойствами.

1. Каждой элементарной процедуре р] поставлен в соответствие единственный фрагмент ¡ггу эталонного изображения, идентификацию которого она выполняет.

2. Элементарные процедуры ру выполняются последовательно.

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

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

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

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

"(locMax,

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

превышает заданный порог; - общее количество позиций на

эталонном изображении, где может быть идентифицирован данный фрагмент.

Для вычисления вектора положения всего объекта на

изображении используется выражение:

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

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

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

где р' =(р'1,р2,—,р'„ ), i= 1,2,...Д - подпроцедура, выполняющая идентификацию объектов /-го класса и конструируемая в соответствии с описанным ранее методом.

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

1. Если существует единственный номер j, такой что р1 {Im)=TRUE и для всех то объект, изображенный на 1т, является представителем класса у.

2. Если для всех i = l,2,...,N р'(Jm)=FALSE, то в этом случае представленный объект не относится ни к одному из заданных классов.

3. В остальных случаях, т.е. когда существуют ji,j2< ••• Jit (A-Hl)» таких что

результат идентификации объекта на изображении 1т не

определен.

Здесь: p\lm) означает применение подпроцедурык входному изображению 1т, при этом p'(Jm) возвращает значение TRUE, если на изображении идентифицирован объект, соответствующий - в

противном случае.

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

1. Если существуют номера и

для всех то

на изображении присутствует к объектов, являющихся представителями классов

2. Если для всех г = 1,2,..., N р' (1т)=РА1ЛЕ, то в этом случае на изображении нет объектов, относящихся к: данным классам.

3. Если существуют номера ]1 и ]2„ такие что р1' (1т)=ТК1}Е, р*г(1т)=ТКиЕ и КЬ, то результат по объекту, локализованному данными подпроцедурами, не определен.

Здесь: 0} - вектор положения объекта, локализованного подпроцедурой - заданная максимально допустимая погрешность в

определении координат.

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

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

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

где: Н - эталонное изображение объекта, Б' - фрагмент изображения из обучающей выборки, содержащий локализованный объект, Л, средние значения интенсивности изображений Я и 5 соответственно.

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

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

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

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

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

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

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

Модель ГА для поиска субоптимальных процедур идентификации объектов одного класса имеет следующую структуру.

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

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

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

И 2*тРИ{р)

где аЬйПЦр) - значение функционала качества процедуры^, тРк(р) максимальное значение качества среди всех допустимых процедур.

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

положение и/или размер соответствующего фрагмента эталонного изображения.

Таблица 1. Операция скрещивания.

Исходные данные Результат

Р=(Р1,Р2,-,Рт) И 1 < У < /и, 1</<к\ с1=(рьРъ--;Р]-1, дь—.дк),

Таблица 2. Операция мутации.

Исходные данные Результат

Р=(Р1>Р2>-,Рь--,Рт) Р=(Р1.Р2,--;Р'ь--,Рт)

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

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

перегенерации всего текущего поколения, если полученное значение меньше некоторого заданного пользователем порога.

Общая схема функционирования ГА поиска субоптимальной процедуры идентификации объектов одного класса состоит из следующих основных этапов.

1. Формирование начальной популяции процедур.

2. Контроль длин решающих процедур из текущей популяции.

3. Оценка показателя качества процедур из текущей популяции.

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

5. Если не выполнен критерий окончания работы ГА, то формирование новой популяции решающих процедур и переход на этап 2.

Модель ГА для поиска субоптимальной процедуры обнаружения объектов одного класса имеет аналогичную структуру.

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

Расчет значения показателя качества процедуры осуществляется по следующей формуле:

ЯР)=w* + &'" •

здесь: w - вес процедуры р, вычисляемый как среднее арифметическое значений весов всех элементарных процедур p,, входящих в состав - минимальное значение среди значений нормированных

коэффициентов корреляции, полученных на этапе постпроверки процедуры р на всех изображениях обучающей выборки; f(p,S) - оценка частичного показателя качества процедуры р на отдельном изображении S', суммирование ведется по всем изображениям из обучающей выборки.

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

В случае если S содержит объект заданного класса, применяется формула:

Г (Р, S) = t{p, S)+A* t(p, S)* [1 - lp(p, 5)],

f'(p,S) = t(p,S) + A * t(p,S)* lp(p,S),

где - вычислительная сложность процедуры р при обработке

изображения - оценка меры близости между объектом,

идентифицированным процедурой р на изображении 5, и эталонным изображением; А - константа, задаваемая пользователем.

Если хотя бы одна из элементарных процедур, входящих в состав р, не отвечает заданному порогу для меры близости, то в качестве оценки показателя качества берется заранее выбранное максимальное значение:

f(p,S) = МАХ

Основным принципом, лежащим в основе модели ГА для поиска субоптимальных процедур идентификации и обнаружения объектов N классов, является независимое использование N популяций, каждой из которых соответствует свой класс объектов. При этом в рамках каждой популяции ГА функционирует по описанной выше схеме и выполняет

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

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

2. Оценка качества решающих процедур в каждой популяции.

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

4. Построение полной идентификационной процедуры, на основе выбранных подпроцедур, и оценка ее качества.

5. Если не выполнен критерий окончания работы ГА, то формирование популяций следующего поколения и переход на этап 2.

Оценка показателя качества полной идентификационной процедуры выполняется путем суммирования значений показателей качества составляющих ее подпроцедур, вычисляемых по формулам, указанным выше:

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

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

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

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

• алгоритм вычисления нормированного коэффициента корреляции;

• алгоритм на основе обобщенного преобразования Хафа;

• алгоритм на основе «структурной» модификации обобщенного преобразования Хафа.

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

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

где: fig- средние значения интенсивности для изображений fag соответственно.

Алгоритм вычисления нормированного коэффициента корреляции не является инвариантным к повороту изображения.

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

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

Обобщенное преобразование Хафа (GHT) предназначено для обнаружения на изображении произвольных контурных объектов.

Пусть искомый объект задан с помощью просмотровой таблицы (lookup table, LUT):

где - вектор значений переменных, которые однозначно

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

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

Алгоритм, основанный на обобщенном преобразовании Хафа, состоит из нескольких этапов:

1. Выполнение обобщенного преобразования Хафа и формирование аккумуляторного массива.

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

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

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

5. Выбор в качестве результата кандидата с максимальным значением коэффициента корреляции.

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

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

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

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

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

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

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

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

Для проверки работоспособности разработанного метода применительно к реальным изображениям использовалась база оцифрованных фотографий объектов различной структуры: дорожных знаков, монет, некоторых типов инструментов. Формат представления изображений - 8 бит на пиксель (256 градаций серого).

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

Экспериментальные исследования программной системы в целом подтвердили работоспособность предложенного метода

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

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

Основные результаты работы

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

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

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

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

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

шума на изображении и при этом быть эффективными по времени работы.

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

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

Публикации по теме диссертации

1. Буряк Д.Ю., Визильтер Ю.В. Автоматическое конструирование оптимальных процедур анализа изображений с использованием генетических алгоритмов // Материалы Международной конференции студентов и аспирантов по фундаментальным наукам "Ломоносов 2002", секция "Вычислительная математика и кибернетика". - М.: Издательский отдел факультета ВМиК МГУ, 2002, с.6.

2. Буряк. Д.Ю., Визильтер Ю.В. Автоматизированное конструирование близких к оптимальным процедур идентификации и обнаружения объектов на изображении с использованием генетических алгоритмов // 12-я Международная конференция по компьютерной графике и машинному зрению ГРАФИК0Н-2002. Труды конференции. - Нижний Новгород: Типография Нижегородского государственного университета им. Н.И. Лобачевского, 2002, с.292-298.

3. Буряк Д.Ю., Визильтер Ю.В. Возможности применения генетических алгоритмов для автоматизированного конструирования процедур анализа изображений // 6-я Международная конференция "Распознавание образов и анализ изображений: новые информационные

технологии" (РОАИ-6-2002). Труды конференции. - Великий Новгород: НовГУ им. Ярослава Мудрого, 2002, с.87-92.

4. Буряк Д.Ю., Визильтер Ю.В. Метод автоматизированного конструирования процедур обнаружения объектов на цифровых изображениях // Программные системы и инструменты: Тематический сборник факультета ВМиК МГУ им. Ломоносова: №3 под ред. Л.Н.Королева. - М.: Издательский отдел факультета ВМиК МГУ, 2002, с. 107-120.

5. D. Yu. Buryak and Yu. V. Vizil'ter. Application of genetic algorithms for automated construction of image analysis procedures // Pattern Recognition and Image Analysis, Vol. 13, No. 1,2003, p.77-79.

6. D.Yu. Buryak and Yu.V. Vizil'ter. Automated construction of identification procedures for objects belonging to several classes // Programming and Computer Software. Vol. 29, No. 4,2003, p.238-243.

7. D.Yu. Buryak and Yu.V. Vizil'ter. The use of genetic algorithms for the automated construction of the image analysis procedures // Pattern Recognition and Image Analysis, Vol. 13, No. 3,2003, p.483-488.

8. Буряк Д.Ю., Визильтер Ю.В. Модели представления решающих процедур и их использование в генетическом алгоритме для поиска оптимальных процедур анализа изображений // Методы и средства обработки информации: Труды первой Всероссийской научной конференции под ред. Л.Н. Королева. - М.: Издательский отдел факультета вычислительной математики и кибернетики МГУ им. М.В. Ломоносова, 2003, с.317-323.

Заказ №508. Объем 1 п.л. Тираж 100 экз.

Отпечатано в ООО «Петроруш». Г. Москва, ул. Палиха-2а, тел. 250-92-06 www.postator.ru

Введение.

1. Анализ основных подходов к построению процедур анализа изображений.

1.1. Неформальная постановка задачи конструирования процедур идентификации и обнаружения объектов на изображениях.

1.2. Подходы, основанные на использовании библиотек функций.

1.3. Алгоритмы вычисления оценок.

1.4. Методы автоматизированного конструирования отдельных элементов алгоритма распознавания.

1.5. Использование баз знаний.

1.6. Генетическое программирование.

1.7. Выводы.

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

2.1. Исходные данные.

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

2.3. Обоснование применения ГА для поиска оптимальных решений.

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

2.5. Построение субоптимальных процедур идентификации и обнаружения объектов нескольких классов.

2.6. Повышение устойчивости конструируемых процедур.

2.7. Инвариантность решающих процедур к сдвигу, повороту и масштабированию объекта на изображении.

2.8. Выводы.

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

3.1. Модель генетического алгоритма для поиска субоптимальных процедур идентификации и обнаружения объектов одного класса.

3.2. Функционал оценки качества процедур идентификации и обнаружения объектов одного класса.

3.3. Модель генетического алгоритма для поиска субоптимальных процедур идентификации и обнаружения объектов нескольких классов.

3.4. Выводы.

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

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

4.2. Базовые алгоритмы.

4.3. Алгоритм выполнения решающей процедуры.

4.4. Алгоритм оценки качества хромосомы.

4.5. Алгоритм формирования очередной популяции.

4.6. Алгоритм регенерации популяции.

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

4.8. Выводы.

Актуальность работы. Проблема разработки методов, позволяющих автоматизировать процессы выбора и настройки алгоритмического и программного обеспечения идентификации и обнаружения объектов на цифровых изображениях, является актуальной. Задачи идентификации и обнаружения объектов на цифровых изображениях возникают в самых различных областях науки и техники [1,3,6,18,23,29]. К настоящему времени разработано большое число методов, алгоритмов, моделей, которые позволяют решать различные задачи в этой области. Однако, проблема создания алгоритмов решения вновь возникающих задач идентификации и обнаружения является чрезвычайно трудоемкой, требующей наличия большого опыта в области анализа изображений.

Основное внимание в литературе при освещении вопросов создания процедур распознавания уделено применению специализированных библиотек функций [27,31,35,36,39,45,51], моделей алгоритмов вычисления оценок [7,8,9,10,12,13,19,20], методам, основанным на использовании моделей предметной области [33,43,44,47,54], а также теории генетического программирования [30,32,49,53]. Проведенный анализ показал, что существующие подходы к решению поставленной задачи обладают рядом недостатков, препятствующих их эффективному применению на практике. В работе предложен новый метод построения процедур идентификации и обнаружения объектов на цифровых изображениях, основанный на автоматическом выделение характерных локальных свойств объекта и применяющий теорию генетического программирования для конструирования на основе выделенных свойств решающих процедур, которые способны работать в реальном масштабе времени. Данный метод автоматически подстраивается под специфику каждой конкретной решаемой задачи и позволяет учитывать опыт, накопленный исследователями в области анализа изображений.

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

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

Задачи. Для достижения поставленной цели требуется:

• сформулировать принципы, которые позволили бы автоматизировать процесс конструирования процедур идентификации и обнаружения объектов на изображениях;

• разработать модели представления процедур идентификации и обнаружения объектов;

• разработать критерий оценки эффективности конструируемых решающих процедур;

• разработать метод отбора эффективных процедур идентификации и обнаружения;

• разработать программное обеспечение, реализующее данный метод;

• провести экспериментальное исследование эффективности предложенного метода.

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

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

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

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

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

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

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

• автоматические системы принятия решений, основанные на анализе визуальной информации;

• робототехника;

• системы контроля качества продукции на производстве.

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

• XI Международная научная конференция студентов и аспирантов по фундаментальным наукам "Ломоносов", Россия, Москва, 2002;

• 12-я Международная конференция по компьютерной графике ГРАФИКОН-2002, Россия, Нижний Новгород, 2002;

• 6-я Международная конференция "Распознавание образов и анализ изображений: новые информационные технологии" (РОАИ-6-2002), Россия, Великий Новгород, 2002;

• Ломоносовские чтения-2003, Россия, Москва, 2003;

• Всероссийская научно-техническая конференция "Методы и средства обработки информации" (МСО-2003), Россия, Москва, 2003;

• Семинар по обработке экспериментальных данных при помощи нейронных сетей и генетических алгоритмов под руководством Королева JI.H. и Поповой Н.Н. (факультет ВмиК МГУ).

• Научно-исследовательский семинар по автоматизации программирования под руководством Шура-Бура М.Р.

Публикации. Основные результаты работы изложены в 8-и научных публикациях [57-64].

Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения и списка литературы. Содержание работы изложено на 126 страницах. Список литературы включает 64 наименования. В работе содержится 42 рисунка и 5 таблиц.

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

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

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

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

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

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

Заключение

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

1. Вапник В.Н., Червоненкис А.Я. Теория распознавания образов. М.:Наука, 1974. - 416с.

2. Вендров A.M. Проектирование программного обеспечения экономических информационных систем. М.: Финансы и статистика 2000.

3. Верхаген К., Дейн Р., Грун Ф., Йостен Й., Вербек П. Распознавание образов: состояние и перспективы. М.:Радио и связь, 1985. - 104с.

4. Гилл Ф., Мюррей У. Численные методы условной оптимизации. М.: Мир, 1977.

5. Гирсанов И.В. Математическая теория экстремальных задач. М.: Изд-во МГУ, 1970.

6. Горелик A.JL, Скрипкин В.А. Методы распознавания. М.:Высшая школа, 1984. - 208с.

7. Гуревич И.Б. Проблема распознавания изображений // Распознавание, классификация, прогноз. Москва: изд-во "Наука", - 1989. - выпуск 1, - с. 280329.

8. Докторович А.Б. Задача выбора оптимального алгоритма распознавания в одном классе алгоритмов голосования // Кибернетика. Киев, 1974. - № 4.

9. И. Енч В. Алгоритм оптимизации параметров одного класса распознающих алгоритмов // Труды Международного симпозиума по практическому применению методов распознавания образов, ВЦ АН СССР, -1973.- с. 237-245.

10. Журавлев Ю.И., Никифоров В.В. Алгоритмы распознавания, основанные на вычислении оценок // Кибернетика. 1971. - № 3, - с. 1-11.

11. Журавлев Ю.И., Камилов М.М., Туляганов Ш.Е. Алгоритмы вычисления оценок и их применение. Ташкент: изд-во "Фан", 1974.

12. Журавлев Ю.И. Об алгебраическом подходе к решению задач распознавания или классификации // Проблемы кибернетики, 1978. вып. 33, -с. 5-68.

13. Журавлев Ю.И. Алгоритмы распознавания, основанные на вычислении оценок. Содержательный смысл параметров, задающих алгоритм // Труды Международного симпозиума по практическому применению методов распознавания образов, ВЦ АН СССР, 1973.

14. Журавлев Ю.И. Экстремальные алгоритмы в математических моделях для задач распознавания и классификации // ДАН СССР, 1976. - т. 231,- № 3,-с. 532-535.

15. Журавлев Ю.И., Михалевич М. Алгоритмы распознавания, основанные на вычислении оценок для задач с пересекающимися классами // Труды ВЦ Польской АН. Варшава, 1974. - вып. 145.

16. Иванов В.А., Косых В.П. Алгоритм сравнения фрагментов изображений двух кристаллов для контроля внешнего вида микросхем // Автометрия. 1989. -№2. - С.29-34.

17. Ищук В.И. О поиске оптимальных весовых коэффициентов для одного класса алгоритмов вычисления оценок // Сборник работ по математической кибернетике, ВЦ АН СССР . 1976. - вып.1, - с. 186-194.

18. Камилов М.М. Об оптимизации и некоторых применениях алгоритмов вычисления оценок // Труды Международного симпозиума по практическому применению методов распознавания образов, ВЦ АН СССР. -1973.

19. Камилов М.М., Алиев Э.М. Выбор длины голосующих наборов в алгоритмах вычисления оценок // Вопросы кибернетики. Ташкент, 1971,- вып. 44.

20. Камилов М.М., Алиев Э.М., Ким А.Н. О вычислении s-порогов при распознавании объектов алгоритмами голосования // Вопросы кибернетики. -Ташкент, 1971. вып. 43.

21. Киричук Н.А., Косых В.П., Петунин А.И. Автоматическая классификация лейкоцитов человека с использованием комплекса "Зенит-К" // Автометрия. -№2. С.38-42

22. Красильников Н.Н. Теория передачи и восприятия изображений. М.: Радио и связь, 1986.

23. Кульянов Е.Г. Об оптимизации одного класса алгоритмов распознавания // Журнал вычислительной математики и математической физики. 1974. - т. 14, - № 3, - с. 756-767.

24. Лоран П.Ж. Аппроксимация и оптимизация. М.: Мир, 1975.

25. Орлов В. Концепция визуального программирования в IBM VisualAge Smalltalk. Материалы конференции "Индустрия программирования '96м.

26. Рязанов В.В. Оптимизация алгоритмов вычисления оценок по параметрам, характеризующим представительность эталонных строк // Журнал вычислительной математики и математической физики. 1976. - т. 16, - № 6.

27. Хорн Б.К.П. Зрение роботов. М.:Мир. - 1989. - 487с.

28. Discipulus. Owner's Manual. Register Machine Learning Technologies, Inc. 2000.

29. Open Source Computer Vision Library. Reference Manual. Intel Corporation, 2001.

30. Banzhaf W., Nordin P., Keller R.E., Francone F.D. Genetic Programming an Introduction: On the Automatic Evolution of Computer Programs and Its Applications. Dpunkt.verlag and Morgan Kaufmann Publishers, Inc. USA. 1998.

31. Buckner, J., Pahl, M., Stahlhut, O., Liedtke, C.-E. A Knowledge-Based System for Context Dependent Evaluation of Remote Sensing Data. // Lecture Notes in Computer Science. Springer-Verlag Heidelberg, 2002. Vol. 2449. - pp. 58-65.

32. Burnett, M. M. and Baker, M. J. A classification system for visual programming languages. J. Visual Languages and Computing, pp. 287-300, September 1994.

33. Chang, S. Visual languages: A tutorial and survey. IEEE Software, 4(l):29-39, January 1987.

34. J.H. Cornell and M. Brady. Generating and generalizing models of visual objects. Artificial Intell., 31: 159-183,1987.

35. Davies. Finding ellipses using the generalized Hough transform. Patterns Recognition Letters 9 (1989) 87-96.

36. Nikos Drakos. Visual Programming Languages: A Survey. CS 263 Final Project. Computer Based Learning Unit, University of Leeds. 1996.

37. Holland, J. Adaptation of natural and artificial systems. MIT Press, Cambridge, MA, 1975.

38. D.P. Huttenlocher and S. Ullman. Recognizing solid objects by alignment with an image. Int. J. Comput. Vision, 5(2): 195-212, Nov. 1990.

39. Rrechel D., Hess F., Comes R., Wangenheim A.V., Blasinger K. Mammalyzer II: A Decision Support System for Early Detection of Breast Cancer in Contrast Enhanced MRI. Springer Informatik Aktuell. Aachen, 1998.

40. Liedtke, C.--E., Buckner, J., Grau O., Growe S., Tonjes, R., "AIDA: A System for the Knowledge Based Interpretation of Remote Sensing Data", 3rd Int. Airborne Remote Sensing Conference & Exhibition, Copenhagen, Denmark,, Vol II, pp. 313-320, July 1997.

41. Fadia Markar. State of the art in visual programming languages. Universite de Geneve. Groupe Programmation Visuelle et Genie Logiciel Memoire de licence. 1997.

42. B.A. McArthur. Incremental Sythesis of Three-Dimensional Object Models Using Random Graphs. PhD thesis, Univ. of Waterloo, 1991.

43. Petrie Ch. Context maintenance. In Proceedings of AAAI-91. 1991. pp 288295.

44. A.R. Pope and D.G. Lowe. Learning object recognition models from images. In Proc. 4. Int. Conf. on Computer Vision, pages 296-301, Berlin, May 1993. IEEE Press.

45. Samuel A. Some studies in machine learning using the game of checkers. In Feigenbaum, E. and Feldman, J., editors, Computers and Thought. McGraw-Hill, New York. 1963.

46. J. Segen. Model learning and recognition of non-rigid objects. In Proc. Conf. Comput. Vision andPatt. Recognit., pp. 597-602,1989.

47. Shu, N. C. Visual Programming Languages: A Perspective and a Dimensional Analysis, pp. 11-34. Plenum Press, 1986.

48. Straub, B.-M., J., Gerke, M., Pahl, M. Automatic Mapping of Settlement Areas Using a Knowledge-Based Image Interpretation System. // Lecture Notes in Computer Science. Springer-Verlag Heidelberg, 2003. Vol. 2626. - pp. 355-364.

49. Teller A., Veloso M. PADO: Learning tree structured algorithms for orchestration into an object recognition system. Technical Report CMU-CS-95-101, Department of Computer Science. Carnegie Mellon University, Pittsburgh, PA.

50. J.J. Weng, N. Ahuja, and T.S. Huang. Learning recognition and segmentation of 3D objects from 2D images. In Proc. Int. Conf. Comput. Vision, pp. 121-128, 1993.

51. A.K.C. Wong and M. You. Entropy and distance of random graphs with application of structural pattern recognition. IEEE Trans. Patt. Anal. Mach. Intell., 7(5):599-609, Sept. 1985.

52. D. Yu. Buryak and Yu. V. Vizil'ter. Application of genetic algorithms for automated construction of image analysis procedures. Pattern Recognition and Image Analysis, Vol. 13, No. 1,2003, pp. 77-79.

53. D.Yu. Buryak and Yu.V. Vizil'ter. Automated construction of identification procedures for objects belonging to several classes. Programming and Computer Software. Vol. 29, No. 4, 2003, pp. 238-243.

54. D.Yu. Buryak and Yu.V. Vizil'ter. The use of genetic algorithms for the automated construction of the image analysis procedures. Pattern Recognition and Image Analysis, Vol. 13, No. 3, 2003, pp. 483-488.