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

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

КУЧУГАНОВ Александр Валерьевич

УДК 004.932

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

Специальность: 05.13.18 — Математическое моделирование, численные методы и комплексы программ

Автореферат

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

Ижевск 2006

Работа выполнена в ГОУ ВПО "Ижевский государственный технический университет" (ГОУ ВПО ИжГТУ).

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

кандидат технических наук,

доцент Моченое Станислав Васильевич

Официальные оппоненты:

доктор технических наук, профессор Мурынов Андрей Ильич;

доктор технических наук, профессор Кетков Юлий Лазаревич (Нижегородский государственный университет)

Ведущая организация:

ГОУ ВПО «Таганрогский радиотехнический университет»

Защита состоится "29" сентября 2006 г. в 14 часов на заседании диссертационного совета Д 212.065.04 при ГОУ ВПО "Ижевский государственный технический университет" по адресу: 426069, г.Ижевск, ул. Студенческая, 7, корпус 1, аудитория 4.

Отзыв на автореферат, заверенный гербовой печатью просим выслать по адресу: 426069, г.Ижевск, ул. Студенческая, 7, корпус 1.

С диссертацией можно ознакомиться в библиотеке ГОУ ВПО ИжГТУ. Автореферат разослан "25 " августа 2006 г.

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

доктор технических наук, профессор Л-"* Б.Я. Бендерский

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

Актуальность работы. Компьютерная обработка оцифрованных изображений - одна из наиболее развитых областей применения вычислительной техники. . Она используется для решения задач во многих сферах научной и профессиональной деятельности: биологии, медицине, геодезии, картографии, в различных опытно-конструкторских и научно-исследовательских разработках. Цифровой обработке изображений посвящено множество работ отечественных и зарубежных ученых: Л.П. Ярославского, Ю.И. Журавлева, И.Б. Гуревича, У. Прэтга, А. Розенфельда. К. Фу, Р. Гонсалеса, К. Ли и др., издаются специализированные научно-прикладные журналы: Pattern Recognition and Image Analysis, Pattern Analysis and Applications, International Journal of Pattern Recognition and Artificial Intelligence, Image and Vision Computing и т.д. Следует отметить, что соответствующее программное обеспечение не всегда успевает за вновь возникающими потребностями пользователей, в частности, в таких задачах, как сжатие изображений, Internet-поиск, создание, анализ и хранение электронных документов и др. При этом существующие системы векторизации в основном выдают результат в виде множества контурных линий, представленных сплайнами, что удобно для дизайнера, но не эффективно в задачах распознавания и автоматизации проектирования.

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

Д. Хьюбел и Т. Визель (Нобелевская премия, 1981 г.), исследуя механизмы зрения низших позвоночных и млекопитающих, сумели выяснить логическую по-, следовательность переработки сигналов поступающих из сетчатки глаза и высказали несколько, предположений относительно того, какая организация коры головного мозга могла бы это обеспечить. Новый подход не только стимулировал выдвижение гипотез о механизмах, лежащих в основе зрительного восприятия, но и воодушевил тех, кто работал на других направлениях. В 1983 году Гордон М. Шеперд выдвинул гипотезу о том, что переработка информации внутри функциональных корковых единиц, не является параллельной или последовательной, как предполагалось ранее, а опирается на оба типа связей. Проводимые физиоло-

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

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

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

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

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

Для достижения поставленной цели требуется решение следующих задач:

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

- разработка многоуровневой итерационной технологии анализа и обработки растройых изображений;

'- исследование существующих и разработка новых методов выделения основных интегральных и дифференциальных характеристик заданных областей изображения;

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

- разработка экстраполирующих методов выделения признаков объектов;

- разработка метода адаптивной настройки анализирующих фильтров по характеру окрестности;

- разработка5 итерационных алгоритмов аппроксимации цепочек пикселей отрезками прямых и'дуг; <..-.■•■

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

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

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

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

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

На защиту выносятся: Результаты аналитического обзора состояния в предметной области исследования; предлагаемые методы анализа и распознавания изображений двухмерных и трехмерных объектов реального мира, основанные на гипотетических моделях механизмов зрения биологических систем, а также результаты исследования предложенных методов и технологий их применения в задачах распознавания образов на полутоновых растровых изображениях:

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

- многоуровневая итерационная технология анализа и обработки растровых изображений;

- метод анализа локальных областей изображения;

- нейросетевая модель локального анализатора; ■

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

- экстраполяционный метод уточнения особых точек; -

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

- структурная схема и ГОЕР диаграмма процессов анализа и обработки изображений в программной системе, созданной на основе предложенных методов и моделей;

- результаты экспериментальных исследований предложенных методов и моделей на примере обработки изображений двумерных и трехмерных объектов: чертежей, рисунков, карт, электрокардиограмм, рукописных текстов; фотоизображений, ландшафтов; - ■

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

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

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

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

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

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

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

Разработанные алгоритмы и методы их комбинирования для обработки полутоновых изображений с целью последующего использования полученной информации в различных исследовательских и прикладных системах положены в основу программно-исследовательского комплекса АС?Я (АШоОиа^КеэеагсЬег).

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

- создания электронных архивов конструкторско-технологической документации;

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

- сбора и анализа экологической информации в геоинформационной системе "ЭКО грунт";

- определения психологического портрета личности по почерку;

- анализа папиллярных узоров пальцевых отпечатков;

- определения структурных характеристик и оценки вероятности родства но конфигурации ушной раковины;

- построения параметрических скульптурных портретов и трехмерных фотороботов по фотографиям или рисункам в системе Сопсер1-8си1р1ег.

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

Разработанные программные модули внедрены в ИП "Ионова" (г. Ижевск) для ускорения компьютерного моделирования и дизайн — работ, в Республиканской клинической больнице №7 - для создания и анализа банка ЭКГ, на ОАО «Концерн «Ижмаш» - для автоматизированной модификации типовых каркасных

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

Апробация работы. Основные положения диссертационной работы докладывались: на Международной научно-технической конференции "Информационные технологии в инновационных проектах" (Ижевск, 2001); на 11-й Международной конференции по компьютерной графике и машинному зрению Графикон -2001 (Нижний Новгород, 2001); на Международной научно-технической конференции IEEE AIS'05 (Дивноморское, 2005).

Публикации. По материалам диссертации опубликовано 7 статей. В том числе в списке, утвержденном ВАК: Кучуганов A.B. Построение трехмерной модели с использованием системы выделения контуров на полутоновых изображениях // Известия ТРТУ. Тематический выпуск «Интеллектуальные САПР» - Таганрог: Изд-во ТРТУ, № 8, 2006. С. 182-186.

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

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

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

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

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

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

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

Для выделения локальных характеристик на первом уровне анализируются два вида окрестностей заданного пикселя: окрестность Я1 размером 3x3 и окрестность К2 размером 5x5 (рис. I).

-4 ' •з 2

5 Ь.у 1

6 7 8

7 6 • / X

8 > '

9 8».,

10 16

II 12 13 14 15

а) б)

Рис. 1. Виды анализируемых окрестностей: а) Окрестность 3x3; б) Окрестность 5x5 и анализируемые лучи

Анализ лучей, исходящих из центрального пикселя окрестности. Чтобы в дальнейшем произвести идентификацию точки необходимо проанализировать перепады яркостей в окрестностях Я-1 и Я-2 относительно выбранной центральной точки, введем дополнительное множество ТВ лучей, исходящих из пикселя Множество ТВ можно представить в следующем виде:

га = {г4у};

>(г/). если (/?(/•;_,) -) а Р) V(/У{гД,)-/?(,•/) < /') Л* 255) Л (/?{,/) !Ь,= . V(/?(,£,)-До3) 2:/>)

иначе 255,

где: Р(г1) — яркость у-той точки в окрестности радиуса Л = 2= 1 ..16;

Р — исходное пороговое значение яркости, заданное пользователем.

Формулу (1) можно интерпретировать следующим образом. Если разность яркостей предыдущего и текущего лучей больше либо равна Р, т.е. произошел спуск на темный луч, или если разность яркостей меньше порогового значения, но текущий луч темнее или равен по яркости предыдущему темному лучу, то пиксели находятся в яркостной "впадине". Яркость текущего пикселя заносится в множество ТВ с индексом номера луча (рис. I). Когда текущий луч находится в яркостной впадине, он сравнивается с последующим и, если разность превышает или равна пороговому значению, он также заносится в множество ТВ.

Несколько соседних черных лучей составляют "темный" сектор, например, сектор, образованный лучами г23, г24 (рис. 2). Здесь и далее, поскольку все лучи исходят из одного центра, для краткости будем обозначать их индексом конечной точки.

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

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

255 200

1b,=255 th7=255

tbj=255

\ tbs=200 у

tb4=i00 jf

• t » i i i i i • i i •

S,

¿1 s,

P'IOO

Л Л

' Ркс. 2. Определение принадлежности точки к множеству темных лучей

Вычисление вектора контурной линии в заданной точке. Любой пиксель gx), изображения <3 может быть отнесен либо к контурам объектов на изображении, либо к множеству фоновых точек. Если очередной пиксель имеет исходящие темные сектора, то он принадлежит множеству контурных точек.

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

Множество направлений А = {щ}, исходящих из контурной точки определяется следующей формулой: '

S (С 255 - А, ) ■ аШ " ' ' "'<* '' " v •

^——-, пока tb j Ф 255

Е(255 -lb.) . (2)

/-1

360 , в противном случае где i - изменяется от 1 до 8, т.к. на окрестности R2 не может быть более 8 независимых направлений одновременно.

Тогда, количество ветвей KW(gxy), исходящих из точки gxy, равняется количеству элементов множества А.

Таким образом, любой пиксель изображения мы можем отнести либо к множеству объектов К, либо к фону:

gx,y еК, если KW(gxJ KcS . (3)

Выделение особых точек. Используя полученные данные, мы, можем определить тип окрестности. Выделим из множества К объектов изображения род-множество ОТ особых точек и подмножество L линий объектов на изображении.

Особыми точками ОТ={о1,} будем считать точки типа разветвление, конец ветви и острый угол (рис. 3.):

X

б)

Рис. 3. Особые (узловые) точки изображения: а) конец ветви; б) разветвление; в) угол

и)

ОТ = {о()гдео< ={ > ^2) ^ С^^С^,)=2) хч (Лг,) -(/г,) <90>

' ' 1 [иначе к^Ь

(4)

где:

ЬсК линий объектов; ■ОТсК узловых точек, К=ОТ<~Ь. Таким образом, точка принадлежит линиям объектов на изображении, если имеет два исходящих направления и угол между ними более 90°.

Рис. 4. Анализ границ площадного объекта

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

Поскольку направления по "краям" есть направления лучей на границах черного сектора, то изменим массив^ так, что

а(ЮУ) = сс(1)иа(К1¥+Х) = аи), если Ш) * 255) л(?Щ-1) = 255)л((ЬО) * 255) лЩ]+1) = 255) л(/-у > 5), (5)

где: ¿./-изменяются ).. 16 и соответствуют направлениям (рис. 1); а(0, а@) - углы начала и конца черного сектора из пикселя К\У- количество ветвей из пикселя (£х,у), значение изменяется от 1 до 8.

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

Предложенный оператор анализа окрестности может работать как на полутоновых (256 градаций одного цвета), так и на двухцветных изображениях, позволяет получать информацию: об исходящих из пикселя направлениях tía следующие и о типе участка линии (разветвление, конец ветви, острый угол, линия, площадной объект). -

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

На основе описанных алгоритмов оператора-анализатора локальных облас- 4 1 тей изображения построена нейросетевая модель, представленная на рис. 5., pea- ; лизующая параллельную обработку информации и выделение первичных признаков изображений. Даная модель может быть реализована на основе специализИ- ' ' рованной СБИС.

Выход типа Конец ветви Разветвление Угол Линия

окрестности или край

Рис. 5. Нейросетевая модель оператора-анализатора локальных областей изображения

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

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

Оптимизация особых точек, В процессе автономного анализа областей изображения, который осуществляется построчным сканированием полутонового изображения с помощью оператора-анализатора локальных областей, как правило, в области сближения, пересечения или окончания линий выделяется не одна, а некоторое связное подмножество особых точек, которые образуют зону артефактов, Величина этой зоны зависит от ширины линий и размеров анализирующего фильтра (3x3, 5x5 и т.д.). Отбраковка лишних ОТ в артефактной зоне позволяет не только снизить количество "шумовых" отрезков, но и повысить качество последующей аппроксимации контуров отрезками прямых и дуг.

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

а) б)

Рис. б. Оптимизация особой точки

В процессе рекурсивной оптимизации из любой найденной ОТ происходит смещение на шаг А~1 по направлениям исходящих ветвей и, если новая ОТ имеет меньшую среднюю яркость в своей окрестности, то рекурсивно вызывается дан-

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

3ot,„i„ -MlNk' (ot¡), где ot¡„¡„ - точка с минимальной яркостью из множества ОТ\

ot¡- /-тая точка из множества ОТ, i = 1,.к, где к количество точек в области ОТ;

MINk' - функция выбора точки с минимальной яркостью из области ОТ. Экстраполяция особых точек Осуществляется для ОТ типа "разветвление" и "угол" путем расчета мнимой точки пересечения ветвей, исходящих из ОТ. Для этого из ранее отобранной ОТ выполняется шаг h-2 (или более) в каждом из направлений ветвей (рис. 7). В полученных точках вычисляются направления "назад" а,=а,+л, где а, - направление продолжения ветви. Искомая уточненная ОТ е.сть точка пересечения всех направлений "назад".

Расчет точки пересечения прямых произведем по углам и координатам точек на исходящих ветвях. Для этого вычислим координаты точки на первой ветви:

X¡ ~ Хот + h ■ cos(a¡); Y\ " YOT-h -sin (a,); где h = 2 - размер шага в пикселях; я/ - угол первой ветви; Хот, Уог~ координаты особой точки. Затем выделим точки на всех следующих ветвях:

X¡ ~ Хот + h • cos(a); Y, = Y,,, - h ■ sinfa), i = 2..KW.

Уточненная ОТ

Исходная ОТ и вектора исходящих eetnoeü

Рис. 7. Уточнение особой точки по пересечению исходящих ветвей

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

у = кх + Ь, (р,

зт Ф ;, у =х-— + Ь;

СОЯ (р

у со$<р = хв'тср + Ьсо.ч(р; х ятф = -у со$<р + Ьсохгр

или в каноническом виде:

' Ах + Ву 1 С - О, А — згпф; В=со$<р; С = -X/ хт<р + у/ созф — -(Ах/ + Ву)), где XI, у/ - координаты любой точки, принадлежащей описываемой прямой. Искомыми координатами пересечения прямых является решение системы линейных уравнений с двумя неизвестными:

В,С2 - В2С, = В,С2 - В2С, А,Вг - А2В, I

~~ С2'^! С^^ — С2Л1

А, + В,+С,=0

' или Л2+В2+С2=0

у 'А,В2-А2В, г

где 2 = А1В2-А2В1.

Полученные точки пересечения усредняются.

Трассировка линий. Следующий этап второго уровня анализа изображений - трассировка и слияние в цепочки точек, принадлежащих контурам, т.е. точек, в которых количество исходящих ветвей К\¥= 2 и разность углов между ними больше 90°. Началом и концом цепочки являются особые точки.

Последовательно перебирая ОТ и все направления из них, мы выделим все цепочки (множество К) на изображении. Каждая следующая точка цепочки вычисляется по формулам:

х> = х„ + соя(а,);

где х„, у„ - точка, принадлежащая К (на первом шаге ОТ);

о, - направление на следующий пиксель (на первом шаге /-тое направление из ОТ).

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

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

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

характеристик объекта.

2. "Переход на слежение по краю" - автоматическая замена направления вглубь объекта на два направления движения по "краям".

3. "Повышение чувствительности локального анализатора" - если в процессе трассировки контура количество исходящих ветвей становится меньше либо равно единице, то яркостный порог динамически уменьшается до тех пор, пока не будет найдено продолжение линии. Адаптация порога позволяет отслеживать на изображении даже очень тонкие (яркостно слабые) линии, если удалось "зацепиться" за такую линию на каком-то участке при исходном яркостном пороге (рис. 86). Иначе искомые линии становятся короче или превращаются в точки (шумы) (рис. 8в). Если же изначально установить минимальный порог, то появляется много шумовых линий (рис. 8г).

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

'Л

в)

-

Рис. 8. Отслеживание «исчезающих» линий с помощью адаптивного метода: а) исходное изображение; б) обработка с помощью адаптивного метода; в) обработка с помощью жесткого порога, равного исходному динамическому; г) жесткий порог с минимальным значением динамического.

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

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

Заключительным этапом второго уровня анализа является классификация участков линий по признаку "дуга-прямая" и аппроксимация отслеженных последовательностей точек отрезками прямых и дуг, в ходе которой автоматически уточняются параметры отрезков по расстоянию (в пикселях) от фактического контура^ На исходном изображении (рис. 9а, 284x356) выделены 6 цепочек, описывающих объекты, общей длиной 2005 пикселей. Далее эти цепочки были обработаны с допустимой величиной отклонения (ошибки) аппроксимации 1 пиксель (рис 96: белые — исходные цепочки, черные линии — результат аппроксимации) в результате чего получено 37 дуг и 5 отрезков. На рис. 9в максимальная допустимая величина ошибки аппроксимации установлена 2 пикселя, получено 27 дуг и 1

Рис. 9. Настройка на величину допустимой ошибки аппроксимации: а) исходное изображение с выделенными последовательностями пикселей; б) максимальная величина ошибки аппроксимации I пиксель; в) максимальная величина ошибки аппроксимации 2 пикселя.

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

В четвертой главе описывается система анализа изображений Л()К. (Аи1о<ЗиаН1у11е8еагсЬег), представляющая собой комплекс программ, предназначенный для преобразования изображений 256 градаций серого цвета в векторный вид. Она снабжена несколькими удобными инструментами и настройками для ис-

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

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

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

На рис. 10а показано исходное изображение фрагмента чертежа; 106 - изображение, обработанное без применения инструмента "Утончение", в результате мы получили двойные контуры, описывающие каждую линию; 10в — изображение после двукратного применения инструмента "Утончение" и аппроксимации.

б) в)

Рис. 10. Обработка чертежных изображений

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

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

а) " ...... б) в) г)

Рис 11. Обработка картографических изображений

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

а) б) в)

Рис. 12. Обработка изображений человеческого уха

В качестве примера обработки изображений 3D объектов на рис. 12 приведены результаты анализа фотографий уха. С помощью представленной программной системы была исследована методика установления отцовства на основе анализа структур ушных раковин. Для этого была разработана математическая модель определения реперных точек в конфигурации ушной раковины, с помощью которой получены структурные характеристики для расчета необходимых параметров и оценки вероятности родства. Работа проводилась совместно с кафедрой "Криминалистика и судебная экспертиза" Удмуртского государственного университета. На рис. 12а представлено обработанное изображение без применения предварительного сглаживания и то же изображение после предварительного сглаживания и обработки (рис. 126). Также здесь виден эффект от применения режима адаптивной настройки анализирующих фильтров по характеру окрестно-

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

В настоящее время существует большая потребность в средствах быстрой разработки геометрических моделей на основе простого инструментария и без привлечения дорогостоящего оборудования. Нами были проведены эксперименты по использованию представленной программной системы векторизации для быстрого создания геометрических моделей в системе концептуального трехмерного проектирования «Sculpter», разработанной на кафедре АСОИУ ГОУ ВПО ИжГТУ. Это, с одной стороны, позволит на начальных стадиях проектирования разрабатывать трехмерные ГМ приемлемого качества, а с другой — достаточно легко встраивать новые методы в существующие системы геометрического моделирования и САПР.

к) л)

Рис 13. Обработка изображений лица человека

В системе «Sculpter» на основе заранее заданных профилей (рис. 13а и рис. 136) и сечений (рис. 13 в) строится трехмерная модель (рис. 13 г), в данном случае головы человека. Для' проведения эксперимента по параметризации трехмерной модели головы человека были взяты фотографии в фас и профиль (рис 13д и рис. 13е). Далее были проведены сглаживание и векторизация полученных изображений (рис. 13ж и рис. 13з). Затем с помощью полученных векторов были параметризованы типовые профили (рис. 13и и рис. 13к) и построена в системе «Sculpter» трехмерная модель (рис.--13л). Полученная трехмерная модель является приближенной, но уже сейчас (без дополнительных доработок системы под конкретную прикладную область) приводит к существенному сокращению ручного труда.

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

В работе приведены результаты экспериментальных исследований предложенных моделей и методов на примерах обработки:

- чертежей, рисунков, электрокардиограмм, карт, рукописного текста;

- фотоизображений уха, лица, ландшафта.

В приложениях даны результаты сравнительного анализа качества векторизации чертежей, сканированных с бумажных носителей, обработанные известными программами Spotlight 6.0 Pro, RasterVect, Vextractor, Vectory 6.0 и с помощью разработанной программной системы AQR. Эксперименты показывают, что система AQR дает снижение количества отрезков векторизированного чертежа в среднем на 10%, что соответственно сокращает долю ручного труда на последующих этапах занесения архивных чертежей в банк конструкторско-технологических данных.

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

Приведены акты внедрения. ¥

ЗАКЛЮЧЕНИЕ

В работе получены следующие основные выводы и результаты:

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

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

На первом уровне технологии анализа изображений - локального зрительного анализа:

3. Разработаны методы и технология оператора первого уровня - анализатора локальных областей изображения, состоящая из: /. .».

- анализа лучей, исходящих из центра окрестности;

- выделения темных секторов;

- вычисления вектора контурной линии;

- выделения особых точек; - •

- определения границ площадного объекта,

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

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

На втором уровне технологии анализа изображений — логическом: •'

5. Разработан метод оптимизации особых точек путем рекурсивного поиска экстремума яркости окрестности в зоне артефактов изображения. ■ " '

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

7. Разработаны методы и технология выделения контурных линий, управляемая текущим изображением и заключающаяся в: '

- трассировке контурных точек;

- скачкообразном переходе в особые точки при входе в атрефактные зоны;

- автоматической смене режима слежения за линией на движение по краю при встрече с площадными объектами;

- повышении чувствительности локальных анализаторов на концах линий; •

- смене разрешающей способности при изменении ширины линий;

- утончении линий без изменения топологии особых точек; 1 ' < '

- итерационной классификации участков линий по признаку "дуга-прямая".

8. На основе разработанных моделей и методов создана программная система AQR (AutoQualityResearcher) для обработки и векторизации полутоновых растровых изображений. Проведенные экспериментальные исследования на примерах обработки изображений двумерных и трехмерных объектов:

- чертежей, рисунков, карт, электрокардиограмм, рукописных текстов;

- фотоизображений ушей, лиц, ландшафтов

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ ИЗЛОЖЕНЫ В СЛЕДУЮЩИХ ПУБЛИКАЦИЯХ

1. Моченов C.B., Кучуганов A.B. Адаптивные алгоритмы векторизации растровых изображений // Информационные технологии в инновационных проектах. Тр. Ш Международной науч.- техн. конф. 23-24 мая. — Ижевск: изд. Ижевский радиозавод, 2001. - 4.1. - С. 181-182.

2. Моченов C.B., Кучуганов A.B. Метод адаптивной векторизации фотоизображений // Сб. тр. 11-й Междунар. Конф. по компьютерной графике и машинному зрению Графикон - 2001 (Нижний Новгород, 10-15 сентября 2001 г). - Нижний Новгород: ННГАСУ, 2001. - С. 227-230.

3. Кучуганов A.B. CALS и чертежные архивы // Перспективные информационные технологии и интеллектуальные системы. — № 4(16), .2003. -http://oitis.tsure.ru.

4. Моченов C.B., Кучуганов A.B. Модель высокопроизводительной системы для выделения контуров полутоновых изображений И Т.2. Междунар. науч.-тех. конф. "Интеллектуальные системы" (AIS'05) и "Интеллектуальные САПР" (CAD-2005) - 2005 (Дивноморское, 3-10 сентября 2005г). - Дивноморское: ФИЗМАТЛИТ, 2005. Т.2.-С. 353-359.

5. Кучуганов A.B., Лапинская Г. В. Автоматизированный анализ психологического портрета личности по почерку // Наука Удмуртии - Ижевск: Изд-во Книжное дело, 2006. № 3, С. 77-82.

6. Кучуганов A.B. Построение трехмерной модели с использованием системы выделения контуров на полутоновых изображениях // Известия ТРТУ. Тематический выпуск «Интеллектуальные САПР» - Таганрог: Изд-во ТРТУ, № 8, 2006. С. 182-186. ,

7. Кучуганов A.B., Лапинская Г. В. Распознавание рукописных текстов // Современные информационные технологии и письменное наследие: от древних рукописей к электронным текстам: материалы междунар. науч. конф. (Ижевск, 1317 июля 2006 г.) - Ижевск: Изд-во ИжГТУ, 2006. С. 98-103.

В авторской редакции Подписано в печать 23.08.06. Усл. псч. л. 1,40. Тираж 100 экз. Заказ №214 Отпечатано в типографии издательства ИжПГУ. 426069. Ижевск, Студенческая, 7

ВВЕДЕНИЕ.

1. ОБРАБОТКА ВИЗУАЛЬНОЙ ИНФОРМАЦИИ.

1.1. Аналитический обзор методов.

1.1.1. Обобщение метода поэлементной обработки.

1.1.2. Обработка изображений скользящим окном.

1.2. Принципы зрительного восприятия в биологических системах.

1.3. Выводы и постановка задачи исследования.

2. ОПЕРАТОР АНАЛИЗА ЛОКАЛЬНЫХ ОБЛАСТЕЙ ИЗОБРАЖЕНИЯ.

2.1. Выбор окрестности для анализа растра.

2.1.1. Гексагональный растр.

2.1.2. Выбор радиуса окрестности.

2.1.3. Методы анализа окрестности.

2.1.4. Обработка невидимых областей.

2.2. Заполнение окрестности точки.

2.3. Анализ лучей, исходящих из центрального пикселя окрестности.

2.4. Вычисление вектора контурной линии в заданной точке.

2.5. Выделение особых точек.

2.6. Границы площадных объектов.

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

2.8. Выводы по главе.

3. АЛГОРИТМЫ АДАПТИВНОГО АНАЛИЗА ПОЛУТОНОВЫХ ИЗОБРАЖЕНИЙ.

3.1. Обработка артефактных зон.

3.2. Поиск контуров, не имеющих особых точек.

3.2.1. Поиск гладких контуров на изображении типа «Draw».

3.2.2. Поиск гладких контуров на изображении типа «Photo».

3.3. Трассировка линий.

3.3.1. Выделение цепочек.

3.3.2. Захват Особых Точек.

3.3.3. Переход на слежение по краю.

3.3.4. Адаптивная настройка анализирующих фильтров по характеру окрестности.

3.3.5. Смена разрешающей способности.

3.3.6. Утончение.

3.4. Аппроксимация цепочек отрезками прямых и дуг.

3.4.1. Разбиение последовательностей пикселей на участки.

3.4.2. Вычисление параметров отрезков и дуг.

3.5. Выводы по главе.

4. СИСТЕМА АНАЛИЗА ИЗОБРАЖЕНИЙ.

4.1. Архитектура системы и сценарий диалога.

4.2. Эксперименты с изображениями двухмерных объектов.

4.2.1. Обработка чертежных изображений.

4.2.2. Обработка картографических изображений.

4.2.3. Обработка электрокардиограмм (ЭКГ).

4.2.4. Анализ рукописного текста.

4.2.5. Примеры обработки рисунков.

4.3. Эксперименты с изображениями трехмерных объектов.

4.3.1. Обработка аэро-фото снимков.

4.3.2. Эксперименты с изображениями ушей.

4.3.3. Эксперименты с изображениями лиц человека.

4.4. Выводы по главе.

Компьютерная обработка оцифрованных изображений - одна из наиболее развитых областей применения вычислительной техники. Она используется для решения задач во многих сферах научной и профессиональной деятельности: биологии, медицине, геодезии, картографии, в различных опытно-конструкторских и научно-исследовательских разработках. Цифровой обработке изображений посвящено множество работ отечественных ученых: Л.П. Ярославского, Ю.И. Журавлева, И.Б. Гуревича и др., в том числе Ижевского государственного технического университета: P.M. Гафарова, В.М. Златкиса, С.Ю. Купчинауса, В.Н. Милича, А.И. Мурынова, A.M. Сметанина и зарубежных: У. Прэтта, А. Розенфельда, К. Фу, Р. Гонсалеса, К. Ли и др., издаются специализированные научно-прикладные журналы: Pattern Recognition and Image Analysis, Pattern Analysis and Applications, International Journal of Pattern Recognition and Artificial Intelligence, Image and Vision Computing и т.д.

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

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

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

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

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

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

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

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

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

Для достижения поставленной цели требуется решение следующих задач:

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

- разработка многоуровневой итерационной технологии анализа и обработки растровых изображений;

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

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

- разработка экстраполирующих методов выделения признаков объектов;

-разработка метода адаптивной настройки анализирующих фильтров по характеру окрестности;

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

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

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

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

На защиту выносятся: Результаты аналитического обзора состояния в предметной области исследования; предлагаемые методы анализа и распознавания изображений двухмерных и трехмерных объектов реального мира, основанные на гипотетических моделях механизмов зрения биологических систем, а также результаты исследования предложенных методов и технологий их применения в задачах распознавания образов на полутоновых растровых изображениях:

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

- многоуровневая итерационная технология анализа и обработки растровых изображений;

- метод анализа локальных областей изображения;

- нейросетевая модель локального анализатора;

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

- экстраполяционный метод уточнения особых точек;

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

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

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

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

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

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

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

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

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

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

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

Разработанные алгоритмы и методы их комбинирования для обработки полутоновых изображений с целью последующего использования полученной информации в различных исследовательских и прикладных системах положены в основу программно-исследовательского комплекса AQR (AutoQualityResearcher).

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

- создания электронных архивов конструкторско-технологической документации;

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

- сбора и анализа экологической информации в геоинформационной системе "ЭКО грунт";

- определения психологического портрета личности по почерку;

- анализа папиллярных узоров пальцевых отпечатков;

- определения структурных характеристик и оценки вероятности родства по конфигурации ушной раковины;

- построения параметрических скульптурных портретов и трехмерных фотороботов по фотографиям или рисункам в системе Concept-Sculpter.

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

Разработанные программные модули внедрены в ИП "Ионова" (г. Ижевск) для ускорения компьютерного моделирования и дизайн-работ, в Республиканской клинической больнице №7 - для создания и анализа банка ЭКГ, на ОАО "Концерн "Ижмаш" - для автоматизированной модификации типовых каркасных моделей головы и автоматического синтеза поверхностных моделей скульптурных портретов.

Апробация работы. Основные положения диссертационной работы докладывались: на Международной научно-технической конференции "Информационные технологии в инновационных проектах" (Ижевск, 2001); на 11-й Международной конференции по компьютерной графике и машинному зрению Графикон - 2001 (Нижний Новгород, 2001); на

Международной научно-технической конференции IEEE AIS'05 (Дивноморское, 2005).

Публикации. По материалам диссертации опубликовано 7 статей. В том числе в списке, утвержденном ВАК: Кучуганов А.В. Построение трехмерной модели с использованием системы выделения контуров на полутоновых изображениях // Известия ТРТУ. Тематический выпуск "Интеллектуальные САПР" - Таганрог: Изд-во ТРТУ, № 8, 2006. С. 182-186.

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

4.4. Выводы по главе

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

- чертежей, рисунков, электрокардиограмм, карт, рукописного текста;

- фотоизображений уха, лица, ландшафта.

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

Необходимо отметить, что для применения в какой-либо конкретной прикладной области представленная система требует соответствующей доработки. А именно, подключение решающего блока, который бы включал в себя методы логического вывода, выполнял функции третьего уровня иерархии - "осмысление" набора найденных объектов [22]).

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

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

На первом уровне технологии анализа изображений - локального зрительного анализа:

3. Разработаны методы и технология оператора анализатора локальных областей изображения, состоящая из:

- анализа лучей, исходящих из центра окрестности;

- выделения темных секторов;

- вычисления вектора контурной линии;

- выделения особых точек;

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

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

На втором уровне технологии анализа изображений - комплексном (логическом):

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

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

7. Разработаны методы и технология выделения контурных линий, управляемая текущим изображением и заключающаяся в:

- трассировке контурных точек;

-скачкообразном переходе в особые точки при входе в атрефактные зоны;

-автоматической смене режима слежения за линией на движение по краю при встрече с площадными объектами;

-повышении чувствительности локальных анализаторов на концах линий;

- смене разрешающей способности при изменении ширины линий;

- утончении линий без изменения топологии особых точек;

-итерационной классификации участков линий по признаку "дугапрямая".

8. На основе разработанных моделей и методов создана программная система AQR (AutoQualityResearcher) для обработки и векторизации полутоновых растровых изображений. Проведенные экспериментальные исследования на примерах обработки изображений двумерных и трехмерных объектов:

- чертежей, рисунков, карт, электрокардиограмм, рукописных текстов;

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

1. Адаптивные методы обработки изображений. Сб. науч. тр. под ред. В.И. Сифорова, Л.П. Ярославского М.: Наука, 1988. - 244 с.

2. Анисимов Б.В. Распознавание и цифровая обработка изображений. М., Высшая школа, 1983.

3. Байгарова Н.С., Бухштаб Ю.А., Евтеева Н.Н., Корягин Д.А. Некоторые подходы к организации содержательного поиска изображений и видеоинформации ИПМ им. М.В. Келдыша РАН. Москва, 2002.

4. Беликова Т.П. Некоторые методы цифрового препарирования изображений//Цифровая обработка сигналов и ее применение,- М.: Наука, 1981. С.87-98.

5. Беликова Т.П., Кронрод М.А., Чочиа П.А., Ярославский Л.П. Цифровая обработка фотоснимков поверхности Марса, переданных АМС "Марс-4" и "Марс-5" // Косм, исслед. 1975. - Т. 13, вып. 6. - С. 898-906.

6. Беликова Т.П., Ярославский Л.П. Использование адаптивных амплитудных преобразований для препарирования изображений // Вопросы радиоэлектроники, сер. Общетехническая. 1974, вып.14. - С. 88-98.

7. Беликова Т.П., Ярославский Л.П. Препарирование изображений в диалоговом режиме в задачах медицинской диагностики и исследования природных ресурсов // Автометрия. 1980. - №4. - С. 66.

8. Белкин Р.С. Курс криминалистики. М., Юрист, 1997.

9. Белявцев В.Г., Воскобойников Ю.Е. Алгоритмы фильтрации изображений с адаптацией размеров апертуры//Автометрия. 1998. - № 3. -С. 18-25.

10. П.Бутаков Е.А. Обработка изображений на ЭВМ. М.: Радио и Связь,1987.

11. Быстрые алгоритмы в цифровой обработке изображений / Под ред. Т.С. Хуанга. М.: Радио и связь, 1984. 224 с.

12. Бьемон Ж., Лагендейк Р.Л., Марсеро P.M. Итерационные методы улучшения изображений // ТИИЭР. 1990. - Т.78, № 5. - С. 58-84.

13. Вельтмандер П.В. Машинная графика. Учебное пособие в 3-х книгах. Новосибирский государственный университет, 1997.

14. Восстановление и реконструкция изображений: Пер. с англ. М.: Мир, 1989.-336 с., ил.

15. Гильбо Е.П., Челпанов И.Б. Обработка сигналов на основе упорядоченного выбора. М.: Сов. радио, 1976. - 344 с.

16. Гимельфарб Г.Л. Автоматизированная межотраслевая обработка снимков земной поверхности, получаемая с ИСЗ серии Landsat // Зарубежная радиоэлектроника. 1983. -N 8. - С. 56-84.

17. Гимельфарб Г.Л. Аппаратные средства и особенности программного обеспечения диалоговой цифровой обработки изображений // Зарубежная радиоэлектроника. 1985. -N10. - С.87-128.

18. Гимельфарб Г.Л. и др. Расчленение цифровых изображений на участки, однородные по локальным изменениям сигнала//Тез. докл. Всесоюз. Конф. АСОИЗ-81.-М.: Наука, 1981. С. 51.

19. Глезер В.Д. Механизмы опознания зрительных образов Академия наук СССР, Институт физиологии имени И.П. Павлова // Издательство "Наука", Москва-Ленинград, 1966.

20. Голд Б., Рэйдер Ч. Цифровая обработка сигналов: Пер. с англ. / Под ред. A.M. Трахтмана. М.: Советское радио, 1973. - 368 с.

21. Гонсалес Р., Вудс Р. Цифровая обработка изображений. Москва: Техносфера, 2006. - 1072 с.

22. Горелик A.JL, Скрипкин В.А. Методы распознавания. М., Высшая школа, 1989.

23. Гранрат Д.Дж. Роль моделей зрения человека в обработке изображений//ТИИЭР. Т. 69.-№5.- 1981.-С. 65-77.

24. Грузман И.С., Киричук B.C., Косых В.П., Перетяган Г.И., Спек-тор А.А. Цифровая обработка изображений в информационных системах. Новосибирский государственный технический университет, 2000.

25. Гуров А.А., Порфирьева Н.Н. Вопросы оценки контрастности сюжетных изображений//Труды ГОИ им. С.И. Вавилова. Т. 44, вып. 178. -JI. - 1979. - С. 31-34.

26. Гуров А.А., Порфирьева Н.Н. Обработка изображений на ЭВМ методами линейной фильтрации//Труды ГОИ им. С.И. Вавилова. -JL, 1982. -Вып. 185.-С. 33-50.

27. Даджион Д., Мерсеро Р. Цифровая обработка многомерных сигналов: Пер. с англ. под ред. Л.П. Ярославского. М.: Мир, 1988. - 488 с.

28. Дактилоскопическая экспертиза: современное состояние и перспективы развития. Красноярск, Изд-во Краснояр. ун-та, 1990.

29. Журавель И.М. Краткий курс теории обработки изображений. Электронный ресурс., matlab.exponenta.ru, 2006 Режим доступа: http://matlab.exponenta.ru/ imageprocess/ book2/index.php свободный.- Загл. с экрана. - Яз. русский.

30. Журавлев Ю.И., Гуревич И.Б. Распознавание образов и распознавание изображений // Распознавание, классификация, прогноз. Математические методы и их применение. Вып. 2. - М.: Наука. - 1989. - С. 5-72.

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

32. Зуев-Инсаров Д. Почерк и личность. Способ определения характера по почерку // Тайна характера. Чтение характера по почерку. Харьков: Фолио, 1996.-С. 325-399.

33. Колесникова М.Б., Топорова М.М., Жуйкова Г.В. Анализ электрокардиограммы у детей. Ижевск: Министерство здравоохранения УАССР, Ижевский медицинский институт, 1992. - С. 3-11.

34. Криминалистика / Под ред. Яблокова Н.П., Колдина В.Я. М.: Изд-во МГУ, 1990.

35. Криминалистика: Учебник/Под ред. Пантелеева И.Ф., Селиванова Н.А. М.: Юрид. лит., 1988.

36. Лисиченко В.К., Барабашина В.М., Варфоломеева Т.В. К вопросу об определении по почерку типологических особенностей личности // Материалы Всесоюзной научной конференции. М., 1972.

37. Литван Р.И., Аверьянов Ю.И., Быковская Ф.С. Оптимальное градационное преобразование изображений // Техника кино и телевидения. -1979,-№2.-С. 38-41.

38. Ллойд Дж. Основы тепловидения. М.: Мир, 1978.

39. Локар Э. Руководство по криминалистике. М.: Юрид. изд-во НКЮ СССР, 1941.

40. Люк Ли. Глаз да глаз нужен: робот присваивает зрение стрекозы. Электронный ресурс. Membrana, 2005. Режим доступа: http://www. membrana.ru/articles/technic/2005/ll/18/210000.html, свободный.- Загл. с экрана. - Яз. русский.

41. Микро-ЭВМ в информационно-измерительных системах / С.М. Переверткин, Н.И. Гаранин, Ю.Н. Костин, И.И. Миронов. М.: Машиностроение, 1987.-248 с.

42. Мирошников М.М. Основные этапы и результаты научных исследований в Государственном оптическом институте: Доклад на Чтениях имени академика Д.С. Рождественского, посвященных 75-летию со дня основания ГОИ // Оптический журнал. 1994. -N 4. - С. 3-110.

43. Нестерук В.Ф. Преобразование оптических изображений и оценка их качества//Успехи научной фотографии. М.: Наука. - 1985. - Т. 23. -С. 93-102.

44. Нестерук В.Ф. Принцип дуальности при нелинейных безинерцион-ных преобразованиях изображений // Труды ГОИ им. С.И. Вавилова. -1987.- Т. 64. Вып. 198. - С. 12-24.

45. Нестерук В.Ф. Структура статистических преобразований изображений в ограниченном диапазоне // Труды ГОИ им. С.И. Вавилова. 1982. -Т. 51.-Вып. 185. С. 13-22.

46. Нестерук В.Ф., Порфирьева Н.Н. Информационная оценка процесса зрительного восприятия // Оптика и спектроскопия. 1978. - Т. 44, вып. 4. -С. 801-803.

47. Нестерук В.Ф., Порфирьева Н.Н. Контрастный закон восприятия света // Оптика и спектроскопия. 1970. - Т. XXIX, вып. 6. - С. 1138-1143.

48. Нестерук В.Ф., Соколова В.А. Вопросы теории восприятия сюжетных изображений и количественной оценки их контраста // Оптико-электронная промышленность. 1980. - №5. - С. 11-13.

49. Новости. -http://www.prodtp.ru/index.php?showtopic=5579.

50. Павлидис Т. Алгоритмы машинной графики и обработки изображений. М.: Радио и связь, 1986. - 400 с.

51. Платонов К.К. Теоретические проблемы психологии личности. -М., 1976.

52. Понятия и термины геоинформатики. Электронный ресурс., ка-tori.pochta.ru, 2005. Режим доступа: http://katori.pochta.ru/htmdoczip/ termgis.htm, свободный. - Загл. с экрана. - Яз. русский.

53. Попков И.К. Векторизатор для полутоновых изображений. Электронный ресурс., www.vectoriz.narod.ru, 2004. Режим доступа: http://www.vectoriz.narod.ru/ свободный.- Загл. с экрана. - Яз. русский.

54. Прэтт У. Цифровая обработка изображений М.: Мир, 1982.790 с.

55. Путятин Е.П., Аверин С.И. Обработка изображений в робототехнике. М.: Машиностроение, 1990. - 320 с.

56. Радченко А.Н. Моделирование основных механизмов мозга. Ленинград: Изд-во "Наука", 1968. 212 с.

57. Рангаева Е., Булычев Д. Практическое руководство Spotlight Pro 6.0 /Spotlight 6.0. -http://rasterarts.ru/.

58. Розенфельд А. Распознавание и обработка изображений. М.: Мир, 1972.-230 с.

59. Семенков О.И. Обработка и отображение информации в растровых графических системах. Минск: Наука и Техника, 1989.

60. Серия программ Raster Arts. Vectory 6.0. http://rasterarts.ru.

61. Скнарев Д.Ю. Векторизатор растровых изображений "RasterVect" Версия 1.1. -http://www.cad.dp.Ua/program3.php#partl.

62. Смирнов А.Я., Белов В.Ю. Экспертные оценки качества дискрети-зированых изображений // Труды ГОИ им. С.И. Вавилова. Т. 57, вып. 191. — Л.- 1984. С. 165-167.

63. Сойфер В.А. Компьютерная обработка изображений Часть 2. Со-росовкий образовательный журнал, №3, 1996.

64. Справочник по устройствам цифровой обработки информации / Н.А. Виноградов, В.Н. Яковлев, В.В. Воскресенский и др. К.: Техника, 1988.-415 с.

65. Стокхэм мл. Обработка изображений в контексте модели зрения // ТИИЭР. 1972. - Т.60, N 7. - С. 93-108.

66. Стокхэм Т. мл., Кэннон Т.М., Ингебретсен Б.Б. Цифровое восстановление сигналов посредством неопределенной инверсной свертки // ТИИЭР. 1975. - Т.63, N 4. - С. 160-177.

67. Телевизионные методы обработки рентгеновских и гамма изображений / Н.Н. Блинов, Е.М. Жуков, Э.Б. Козловский, А.И. Мазуров. - М.: Энергоатоиздат, 1982. - 200 с.

68. Темников Ф.Е., Афонин В.А., Дмитриев В.И. Теоретические основы информационной техники. М.: Энергия. 1979.- 512 с.

69. Тьюки Дж. Анализ результатов наблюдений. М.: Мир, 1981. 160 с.

70. Тюхтин B.C., Отражение, системы, кибернетика. М.: Наука., 1972.

71. Урманцев Ю.А. Симметрия природы и природа симметрии (Философские и естественнонаучные аспекты). М., Мысль, 1974.

72. Фу К., Гонсалес Р., Ли К. Робототехника: Пер. с англ. / Под ред. В.Г. Градецкого. М.: Мир, 1989. - 624 с.

73. Харин В.В. Кинематический синтез трехмерной геометрической модели на основе связной сетки кривых. // Высокие технологии 2004: сборник трудов науч.-тех. форума с международным участием: В 4 ч. Ч. 1, с. 162-169.

74. Хьюбел Д. Мозг. М.: изд. Мир, 1981. С. 167-197.

75. Чочиа П.А. Двухкомпонентная статистическая модель фрагмента изображения // Тез. докл. Всесоюзной конф. "Обработка изображений и дистанционные исследования". Часть 1. - Новосибирск, 1984. - С. 60-61.

76. Шеперд Г. Нейро-биология. М.: изд. Мир, 1987. -Т.2. С. 419-450.

77. Шлезингер М.И. Математические средства обработки изображений. К.: Наукова думка, 1989. - 200 с.

78. Шлихт Г.Ю. Цифровая обработка цветных изображений. М., Издательство ЭКОМ, 1997. - 336 с.

79. Эргономика зрительной деятельности человека / В.В. Волков, А.В. Луизов, Б.В. Овчинников, Н.П. Травникова. Л.: Машиностроение. Ленингр. отд-ние, 1989.- 112 с.

80. Ярославский Л.П. Введение в цифровую обработку изображений. -М.: Сов. радио, 1979. 312 с.

81. Ярославский Л.П. Теория и методы цифровой обработки в оптических и голографических системах. Автореферат дис. д-ра физ.-мат. наук. -Л.: ГОИ им. С.И. Вавилова, 1982.-41 с.

82. Ярославский Л.П. Устройства ввода-вывода изображений для ЭЦВМ. М.: Энергия, 1968. - 88 с.

83. Andreas Koschan A Comparative Study On Color Edge Detection -Technical University Berlin, 1995.86. http://www.computer-museum.ru/histussr/dsp.htm.87. http://www.kosmosnimki.ru/examples.asp.88. http://www.southural.ru/experience/l 07.html.

84. Hubbel W.L., Bownds M.D. Visual transduction in vertebrate photoreceptors: Ann. Rev. Neurosci., 1979. P. 17-34.

85. Hubel D.H., Wiesel T.N. Sequence regularity and geometry of orientation columns in the monkey striate cortex. J. Сотр. Neurol., 1974. P. 267-294.

86. Hubel D.H., Wiesel T.N., Stryker M.P. Anatomical demonstration of orientation columns in macaque monkey. J. Сотр. Neurol., 1978. P. 361-380.

87. Jia X. Extending the Feature Set for Automatic Face Recognition. Электронный ресурс. University of Southampton, 1993. Режим доступа: http://www.isis.ecs.soton.ac.uk/publications/theses/xj93.ps свободный. - Загл. с экрана. - Яз. англ.

88. Pratt W.K., Davarian F. Fast Computational Techniques for Pseudoin-verse and Winer Image Restoration // IEEE Trans, on Computers. 1977. - V.C-26, N6.-P. 571-580.