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

- 3 да 1997

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

ВИЗИЛЬТЕР Юрий Валентинович

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

05.13.14 - системы обработки информации и управления

Автореферат диссертации на соискание ученой степени кандидата технических наук

Москва 1997

Работа выполнена в Государственном научно-исследовательском институте авиационных систем

Научный руководитель:

кандидат технических наук, старший научный сотрудник Желтов С.Ю. Официальные оппоненты:

• доктор физико-математических наук, профессор Тюкавкин Д.В.

• кандидат технических наук Левшин В.А. Ведущая организация: ЦКБ "Комета".

Защита состоится "_"__199 г..

на заседании диссертационного совета Д 053.18.08 Московского государственного авиационного института (технического университета)

С диссертацией можно ознакомиться в библиотеке Московского государственного авиационного института (технического университета)

Отзывы на автореферат в 2-х экземплярах просим высылать по адресу: 125871, ГСП, Москва, Волоколамское ш., 4, Ученый совет, ученому секретарю диссертационного совета Д 053.18.08.

Автореферат разослан "_"__ 199 г..

Ученый се " 153.18.08.

кандидат т

Карп К.А.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

>дним из наиболее важных источников информации является канал зрительного осприятия. Использование в современных автоматических системах цифровых идеодатчиков с высоким разрешением (размер получаемых изображений орядка 104-106 элементов и более) позволило существенно приблизить нформативность искусственных зрительных устройств к соответствующим арактеристикам человеческого глаза. Тем ; острее стала ощущаться еобходимость создания эффективных алгоритмов автоматического анализа зображений, обеспечивающих качественную обработку возросших объемов анных. Специфика разработки таких инженерных приложений определяется ледующими основными особенностями. Во-первых, при разработке систем нформационного обеспечения требуется решать не общую проблему втоматического понимания изображения произвольной сцены, а гораздо более пределенную и узкую задачу проблемно-ориентированной интерпретации •зображения. Во-вторых, к алгоритмам обработки изображений в системах [нформационного обеспечения предъявляются специальные требования, вязанные с конкретными характеристиками разрабатываемой или уже уществуюшей системы управления. В области информационного обеспечения истем управления сложными динамическими объектами, необходимая [нтерпретация изображения часто сводится к обнаружению и идентификации на [зображении объектов, присутствие которых может повлиять на формирование "правления. Эта задача носит также название задачи детектирования. В ависимости от специфики конкретной задачи, система автоматического ■правления предъявляет к подсистеме анализа изображений следующие »сновные требования: быстродействие, достоверность детектирования, точность [змерения различных характеристик объектов.

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

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

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

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

При этом решались следующие задачи:

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

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

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

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

Диссертационная работа ■ выполнена в ГосНИИ АС на основе исследований, проведенных в рамках НИР "Рубеж-5", НИР "Феникс-НГ", НИР "Образ" и НИР "Секира", а также по контракту N 605018 JWS/amm ГосНИИ АС с компанией Intermec (США).

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

Научная новизна работы состоит в следующем:

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

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

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

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

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

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

На защиту выносятся следующие основные положения:

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

2. Для случая статистически независимых свидетельств имеет место теорема

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

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

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

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

Результаты данного исследования также использовались в НПО ИТ при разработке алгоритмического обеспечения для системы обнаружения объектов на изображениях ИК-диапазона.

В ходе работы создана интегрированная система анализа и обработки изображений для персональных ЭВМ типа IBM PC/AT. Данное программное обеспечение активно используется в ГосНИИ АС при решении задач анализа изображений. !:

Апробация работы. Основные положения диссертационной работы докладывались автором на следующих международных конференциях: international Society for Photogrammetry and Remote Sensing (iSPRS) Intercommission III-V Workshop (Цюрих,1995), Digital Photogrammetry and Remote Sensing '95 (С.Петербург, 1995) и EuroOPTO Satellite Remote Sensing7/ (Париж, 1995), XVIII ISPRS Congress (Вена, 1996).

Публикации. По материалам диссертации опубликовано 10 печатных работ.

Структура диссертации. Диссертационная работа состоит из введения, 4 разделов и заключения, содержит 140 страниц машинописного текста и 52 рисунка. Список цитируемой литературы включает 63 наименования.

СОДЕРЖАНИЕ РАБОТЫ

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

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

В области анализа изображений под задачей детектирования понимают задачу обнаружения на реальном изображении объекта, заранее заданного эталонным изображением, яркостно-геометрической моделью или любым другим описанием. В -.реальных системах объекты наблюдаемой сцены могут регистрироваться в различном масштабе, под различными ракурсами, в различное время года, в различное время дня, в различных погодных условиях, в присутствии разного рода помех и т.д. Это приводит к требованию построения алгоритмов детектирования объектов; инвариантных к условиям регистрации. Для формального описания задачи вводятся и анализируются следующие основные элементы : модель объекта М,- модель регистрации изображения Б и модель искажений К. "•< ■ • ••••»; •••

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

При помощи модели регистрации будем описывать любые регулярные (обусловленные условиями съемки), геометрические и радиометрические искажения изображения, полученного в результате актуализации модели. Она может быть представлена в виде некоторой полугруппы преобразований Б. Без принципиальной потери общности можно считать Б параметрическим множеством преобразований 8(0), где 9 - вектор параметров.

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

С учетом выше изложенного, наблюдаемое реальное изображение оказывается связанным с моделью следующим образом:

1шк=г(5(Ас1(М))), (1)

где Аа(М) - выборка элемента из М; беБ; геЯ.

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

Пусть формальный результат алгоритма детектирования имеет вид c=Rec(ImR). Тогда условие правильного детектирования объекта имеет вид

c=Rec(r(s(Act(Mc)))), (2)

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

Ji^l-^xmiiUPic, / A/c'))+Xx(l-maxmax(/>(c, / Мс'))), (3)

I у к;

где P(Cj / ML') - вероятность принятия решения j для объектов класса q; Хе [0,1] - параметр настройки.

Кроме того, при создании систем реального времени на выбор алгоритма Ree накладываются дополнительные ограничения по затратным параметрам (прежде всего - по времени и необходимым аппаратным ресурсам), совокупность которых можно описать некоторым обобщенным критерием' Cos/(Rec). Таким образом, при создании систем обнаружения и распознавания объектов на изображениях необходимо решить задачу условной оптимизации

Jj->max(Rec); Cos/(Rec)<Costmax,

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

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

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

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

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

Р(Н / FilmП - _____Р(Н)*Р(Е(Im) /_//_) ____

V /cum« я(Я)хЯ(£(1т)/Я) + Я(//г7*>(£(1т)/Яс)' W

где Нс - гипотеза "не Н". Изображение Im здесь также рассматривается как событие E(Ini) или, точнее, в процессе анализа изображения Im происходйт ряд событий, совокупность которых и составляет E(Im). Иными словами, если каждый существенный факт, установленный в ходе анализа изображения Im, есть событие ек, то

E(Im)=e,ne2i"v.rieK, (5)

где К - общее число таких событий. Таким образом, для проверки любой гипотезы Н относительно изображения Im необходимо вычислить выражение (4) с учетом (5). , . . • • ■

Если предположить, что события {ек} •независимы в совокупности, то из (4) и (5) следует , , ■•. i. ■ • ■ ■ •

Р(Н / lm) =____Willi^(6)

nti/im) р{Н) х П{Я(е>.у Н)) + p(HC) х j-J,^ / нс)}. W

где П{х]<}=х1хх'2х...хх^.:''

Выражение (6) дает возможность . определить важное понятие "влияющего события" или "свидетельства". Пусть йшы некоторое событие е и некоторая' гипотеза Н, причем P(e/H)=P(e/Ht). Тогда из (6) следует, что

(Р(е/Н)=Р(е/Нс)) => (P(H/Im)=P(H/(E(Im)rie))),

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

S(H)={e: Р(е/Н)*Р(е/Нс)}.

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

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

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

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

В диссертации показано, что процедурами событийного анализа, и частности, являются: базовые операторы математической морфологии (по Ссрра) (ММ), преобразование Hough (НТ) и обобщенное преобразование Hougli (GHT), а также морфологический анализ изображений (по Пытьеву).

Основными преимуществами предложенного неметрического метода по сравнению с методами, основанными на непосредственном метрическом сравнении с эталоном, являются:

• возможность использования обобщенных моделей;

• возможность использования структурных иерархических моделей:

• возможность комплексирования разнородной информации.

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

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

Иерархические модели, к тому же, определяют "связи над связями", т.е. должны описываться гипотезами более высокого уровня, для которых входными событиями ^являются события, связанные с гипотезами о связях. Использование структурных, иерархических моделей должно:быть основано на соответствующей теореме разделения. Важный частный, случай теоремы разделения, доказан в подразделе 2..1Д для случая статистически независимых свидетельств. При этом основным, условием применимости является то, что набор гипотез первого уровня <H>=(Hj} должен удовлетворять ограничению

S(H¡)oS(Hj)=0, Vi#j; H¡,HjC<H>; US{Hf)= S(H).

Этот результат, в частности, объясняет высокую вычислительную эффективность морфологического сравнения .изображений. По', форме! 'В эурм ' случае,.разбиение кадра на непересекающиеся'' облаёти'; как даз й .ббеспеч'Ив^ет, выполнение указанного условия для всей совокупности пй'ксельнь1х событий. В теоретическом плане, доказательство теоремы1'1 разделения'" впервые позволяет обосновать оптимальный характер модульных (многоэтапных) процедур анализа изображений. : j- : : >"'

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

• независимое аккумулирование свидетельств;

• декомпозиция вектора параметров;

• редукция вектора параметров;

• загрубление модели объекта.

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

Пусть существует, декомпозиция модели регистрации 5(0)=5'(0')»8"(0"), где <Ит(0)=с11, сНт(0")=<12 и с11+с12=<1. В этом случае имеется возможность представления выражения для апостериорной вероятности в виде произведения двух сомножителей, причем второй из них зависит от первого, а первый от второго - не зависит. Это значит, что мы можем сначала оценить вектор параметров преобразования 0', а затем, используя эту оценку, - вектор 0". Выгода от такого разделения очевидна, так как вместо работы в пространстве параметров размерности с1 мы сначала работаем в пространстве размерности (11, а затем - в пространстве размерности с12. Часто достаточно определить лишь параметры О'. В этом случае имеет место редукция вектора параметров.

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

В заключительной части раздела, был предложен байесовский мета-алгоритм, обобщающий все рассмотренные возможности уменьшения вычислительных затрат. Однако, строгие вероятностные построения требуют точного знания вероятностной модели, параметры которой, как правило, не известны, а зачастую неизвестен и вид закона их распределения. Поэтому с практической точки зрения имеет смысл вообще отказаться от термина "вероятность" в пользу термина "достоверность", имея в виду, что вычисляемые значения К(М/1т) характеризуют апостериорную уверенность в истинности тех или иных утверждений, но не являются их апостериорными вероятностями в строгом смысле. Одним из удобных способов построения таких рассуждений является использование качественной вероятностной модели, описываемой формулой (6), в которой РСе^Н) и Р(ек/Нс) понимаются уже не как истинные условные вероятности, а лишь как условные меры связи гипотезы Н и события ек. Схема детектирования при этом принимает следующий, наиболее общий вид:

1) Выполнить первичное аккумулирование свидетельств и определить параметры 0,' преобразования з(8)=5(в1,)«з(02), доставляющего максимум критерию достоверности для параметров регистрации К(5(0,)/{1тк,М'}), М'эМ; вычислить значение этого критерия.

-102) Если К($(01)/{1тК,М'})>£, повторно проанализировать изображение обнаруженного объекта с /целью вычисления ,-'., вероятности принадлежности объекта к | Модели. ^; вычислить значение критерия идентификации К(М/1т^), '' ' ] 3) Если К(М/1т^)>Е, считать, что на изображении обнаружен объект, описываемый моделью 5(0)(М).....

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

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

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

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

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

1. Для конкретной задачи детектирования, формально описать модель объекта, модель регистрации и модель искажений',

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

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

4. Определить типы "событий", вычислительные затраты на регистрацию которых не превышают заданных пределов;

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

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

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

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

В первом подразделе рассматривается задача автоматического обнаружения объектов типа командных пунктов (КП) на мелкдмад^кдеых РЛ-САР-изображениях. Используется следующая иерархическая модель объекта'. "Три близко расположенные группы-точечных объектов. Формы-'точечных облаков и количество точек в них различны. Минимальные расстбяния между группами могут быть сравнимы с-расстояниями'между объектами внутри Групп." Модель регистрации предполагает' сдвиг, повороТ-й' масштабирование изображений. : Модель искажений допускает;наличие!значительного числа ложных объектов.

При решении этой задачи применяется алгоритм морфологической кластеризации бинарных точечных^ -паШтерндв': (БТП), Являющийся в данном случае экстремальным : алгоритмом ''анализа точечных событий. Аппарат морфологических "методов кластеризации развит специально для решения этой задачи. Доказано, что базовые операторы ММ позволяют определить на БТП

ультрамстрику, являющуюся достаточным условием для построения ряда иерархических процедур кластеризации. Предложены: дилатационный (D), клоузинговый (С), дилатационно-эрозионный (DE), клоузинг-эрозионный (СЕ), дидатационно-оупенинговый (DO), и клоузинг - оупенинговый (СО) алгоритмы кластеризации. Масштаб регистрации БТП оценивался при помощи морфологических спектров. Постпроверка результатов детектирования осуществлялась при помощи системы геометрических признаков.

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

Используется загрубленная модель ДОН, в которой "распределение яркости" незашумленного объекта описывается в полярных координатах разделимой функцией F(p,<p), симметричной относительно некоторого базового направления фО. Модель регистрации предполагает сдвиг и поворот изображения. Модель искажений описывает влияние спецвозвоздействий в ИК-диапазоне как шум замещения с редкими всплесками сверхвысокой интенсивности. При разработке алгоритма детектирования использована декомпозиция вектора параметров регистрации: сначала определяется положение объекта, затем - его угловая ориентация. Учет пиксельных событий организован как независимое голосование пикселов в пользу всех возможных в данном положении угловых сенсорных пар. Понятие "угловой сенсорной пары" определено как совокупность двух угловых секторов - возможного носителя углового объекта и его дополнения до полного круга.

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

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

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

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

рсализаиии на базе сканера фирмы, jnlcrmcc (СЩА).со встроенным сигнальным процессором TMS320C3I.

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

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

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

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

. Модель регистрации. Геометрические искажения определяются классом проективных преобразований (в простейшем случае аффинных). Радиометрические регулярные искажения ; заключаются, ! в неравномерном - "размывании" черно-белой палитры ' при" ее-отображении-:на шкалу серого цвета (0-15). При этом предполагается сохранение 'достатЬчного" контраста между любыми двумя соседними полосами (не менее 2 градаций яркости).

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

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

1) Модифицированное преобразование Hough;

2) Дифференцирование аккумулятора;

3) Определение параметров кодосодержащих полос;

4) Определение координат объемлющих прямоугольников;

5) Проверка обнаруженных объемлющих прямоугольников.

Используемый на этапе обнаружения кодосодержащих полос модифицированное преобразование Hough (МНТ) является оригинальной процедурой анализа событий. С одной стороны, этот метод генетически связан как с классическим преобразованием Hough (HT), так и с обобщенным преобразованием Hough (G HT). С другой стороны, он имеет ряд существенных отличительных особенностей, которые делают его несводимым ни к HT ни к GHT.

1) Этот метод не использует просмотровых таблиц (LUT) метода G HT. Голосование реализуется как в классическом преобразовании Hough, но не по всему диапазону значений в, а только в малом растворе "угла голосования" вокруг направления ориентации вектора - градиента.

2) В качестве биссектрисы угла голосования выбирается направление градиента, а не перпендикуляр к нему (как это делается в некоторых реализациях преобразования Hough).

3) Сущность анализа аккумулятора состоит не в поиске локальных максимумов в аккумуляторе (р,6), а в поиске пар "максимум-минимум" в дифференцированном аккумуляторе (dp,ö). Эти сопряженные пары точек в дифференцированном аккумуляторе соответствуют границам сигнала типа "меандр" в соответствующих сечениях аккумулятора G=const в исходном пространстве Hough или штриховым полосам на исходном изображении.

4) Лежащая в основе МНТ модель объекта (штрихового кода) не столь проста, как модель объекта, допускаемая HT (прямая линия). В то же время, она и не настолько "жесткая", как модель объекта в GHT. МНТ, в отличие от GHT обеспечивает инвариантность к проективным преобразованиям, используя все тот же двумерный аккумулятор (р,0). Более того, используемая модель объекта является максимально гибкой, поскольку допускается произвольное число элементов объекта (штрихов кода), причем эти элементы (штрихи и разделительные пробелы между ними) могут иметь произвольные параметры (высоту и ширину).1

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

Используемое на этапе поетпроверки объемлющих прямоугольников отношение аспекта также является специально разработанным оригинальным детектором колинеарности. Для всех внутренних точек прямоугольника со значением яркости больше порога вычисляются компоненты вектора - градиента. Из полученных значений компонент градиентов истинных краевых точек формируется матрица обобщенных дисперсий градиента Е. Для полученной матрицы Е вычисляется отношение аспекта F, которое является отношением собственных значений (¡Ц Д2) этой матрицы: F=X,A2, (/.,>Х2). Если отношение аспекта достаточно велико, принимается решение об обнаружении штрихового кода, границей которого является данный объемлющий прямоугольник.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

итоге выполнения диссертационной работы автором получены следующие

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

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

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

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

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

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

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

Решена задача инвариантного (относительно проективных преобразований) детектирования штриховых кодов на сложном структурированном фоне, включающем разнообразные текстовые и графические элементы, в присутствии сложных шумов и искажений (блики, пятна и т.п.). Для этого разработано специальное модифицированное преобразование Hough (МНТ). обеспечивающее робастное обнаружение кодосодержаших полос. Предложен модульный алгоритм обнаружения штриховых кодов, использующий МНТ на начальном этапе детектирования. Алгоритм реализован в виде программы для сигнального процессора TMS320C31, встроенного в ручной сканер J7010 фирмы Intermec (США). Время обработки одного кадра не превышает 0.2 сек. Общий объем программного обеспечения составляет 2500 строк на языке С.

!. Разработана интегрированная система анализа и обработки изображений для персональных ЭВМ типа IBM PC/AT, предназначенная для моделирования

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

Основное содержание диссертации отражено в следующих публикациях:

1. Визильтер Ю.В., Степанов А.А., ЖелтовС.Ю. "Новые методы обработки ■ изображений", НЗНТ, Серия: Авиационные системы, №4; М: ГосНИИ АС, 1992.

2. Лебедев Г.Н., Визильтер Ю.В. "'Алгоритмы обработки бинарных изображений", в кн "Бортовые оперативно-советующие ЭС и математические модели некоторых проблемных ситуаций"; под ред. Г.Н. Лебедева и Б.Е. Федунова.-М.: МАИ, 1996.

3. Visilter Yu., Zheltov S., Stepanov A. "Shape analysis using Pyliev morphologic paradigm and its' use in machine vision" SP1E Proceedings, Volume 2350, 1994.

4. Visilter Yu., Zheltov S. "The conjuntion angle meásurement using the Hough Transform", ISPRS Intercommissiori II1-V workshop, Zurich, 1995.

5. Visilter Yu., Zheltov S., Stepanov A., Morzeev Yu.' "Complete Object-Oriented Image Processing", Scientific review of Valenciennes Univercity, France, 1995.

6. Zheltov S., Visilter Yu., Stepanov A., Morzeev Yu. "The object-oriented frame approach, to image processing and data management in the multisensory remote sensing ", SPIE Proceedings, Volume 2587, 1995:

7. Stepanov > A., • Visilter Yu., Zheltov S., Morzeev Yu. "Object-Oriented Frame approach'..for. improved interfaces design for image processing systems", SPIE Proceedings, Volume 2597, 1995. ':

8. Visilter Yu., Zheltov S., Stepanov A. "Object Detection and Recognition using Events-based Image Analysis", SPIE Proceedings, Volume 2823, 1996.

9. Visilter Yu., Zheltov S., Stepanov A., Morzeev Yu. "Frames based analysis of multisensor image sequences", ISPRS Proceedings, "International archives of photogrammetry and remote sensing, Volume XXXI, part B2, Vienna,, Austria, 1996, ' '' ''

10. Visilter Yu., Zheltov S., Stepanov A. "Events-based Image Analysis for Machine Vision and Digital Photogrammetry", SPIE Proceedings, International archives of photogrammetry and remote sensing, Volume XXXI, part V, 1996.