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

Ко лд аев Виктор Дм итрие в ич

РАЗРАБОТКА ЭВРИСТИЧЕСКИХ И

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

СЕГМЕНТАЦИИ ИЗОБРАЖЕНИЙ В АВТОМАТИЗИРОВАННЫХ

ПРОИЗВОДСТВЕННЫХ СИСТЕМАХ

Специальность: 05.13.06 – Автоматизация и управление

технологическими процессами и производствами

А ВТО РЕФ ЕРА Т

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

Москва, 2007

Работа выполнена на кафедре «Информатика и программное обеспечение вычислительных систем» в Московском государственном институте электронной техники (техническом университете)

Научный руководитель Доктор технических наук, профессор Л.Г. Гагарина Официальные Доктор технических наук, оппоненты профессор А.Б. Барский Кандидат технических наук, доцент С.А. Лупин

Ведущая организация ОАО “НИИТМ”, г. Москва

Защита состоится «_»_2007 года в _:_ на заседании диссертационного совета Д 212.134.04 при Московском государственном институте электронной техники (техническом университете) по адресу:

124498, Москва, Зеленоград, проезд 4806, МИЭТ

С диссертацией можно ознакомиться в библиотеке МИЭТ.

Автореферат разослан «_»_ 2007 г.

Ученый секретарь доктор технических наук, профессор А. И. Погалов

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

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

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

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

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

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

Результаты исследований методов обработки изображений изложены в работах зарубежных и отечественных ученых: L. Davis, J.F.

Jarvis, B. Lippel, M. Kurland, R.W. Floyd, J.M.S. Prewitt, А. Rosenfeld, B.E. Bayer, Т. Pavlidis, W.K. Pratt, В.Ф. Нестерук, И.А. Богуславского, Ю.И. Журавлева, С.В. Яблонского, М.Н. Вайнцвайга, В.А. Сойфера, Л.П. Ярославского, В.А. Абрамова.

Цели и задачи диссертационной работы.

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

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

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

2. Классификация, формализация задачи, анализ методов и алгоритмов сегментации и фильтрации изображений в АПС.

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

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

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

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

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

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

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

1. Проведен аналитический обзор функциональных возможностей АПС в контексте реализации автоматизированной обработки видеоизображений.

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

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

4. Установлена функциональная зависимость, определяющая значение оптимального порога фильтрации равного (1,4–1,6) от среднего значения градиента.

5. На основе объектно-ориентированного подхода создана, верифицирована и программно реализована имитационная модель контурной сегментации в АПС.

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

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

8. Разработанные методы и алгоритмы внедрены в технологический процесс ООО «БелАБМ.ру (BelABM.ru)» и в учебный процесс МГИЭТ-ТУ.

Практическая значимость работы заключается в расширении возможностей автоматизированной обработки изображений в АПС.

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

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

Полученные результаты доведены до уровня практического использования, что подтверждено актом внедрения ООО «БелАБМ.ру (BelABM.ru)». Результаты диссертационной работы используются в учебном процессе на кафедре ИПОВС в МГИЭТ-ТУ.

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

Личный вклад автора. Все основные результаты получены автором лично. Главными из них являются:

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

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

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

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

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

• построение и верификация имитационной модели контурной сегментации изображений в АПС;

• автор диссертации принимал активное участие в разработке, тестировании, сопровождении, предложенных и внедренных им новых технических решений в технологический процесс ООО «БелАБМ.ру (BelABM.ru)» и во внедрении результатов диссертационной работы в учебный процесс кафедры «Информатика и программное обеспечение вычислительных систем» Московского государственного института электронной техники.

Реализация полученных результатов. Все работы по реализации и внедрению проводились под руководством или при непосредственном участии автора. Результаты диссертационной работы используются в технологическом процессе ООО «БелАБМ.ру (BelABM.ru)» в рамках опытной эксплуатации автоматизированной системы обработки изображений, что позволяет обеспечивать контурную сегментацию изображений с зашумленностью до 20%, повышать в 1,5 раза скорость обработки информации в графическом режиме и увеличивать в 2 раза качество выделения контуров. Разработанные и исследованные модели и алгоритмы используются в учебном процессе кафедры ИПОВС Московского государственного института электронной техники (технического университета) при чтении дисциплин «Автоматизированные информационные системы», «Структуры и алгоритмы обработки данных», «Имитационное моделирование».

На защиту выносятся:

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

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

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

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

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

7. Программная реализация алгоритмов фильтрации и контурной сегментации изображений в технологический процесс ООО «БелАБМ.ру (BelABM.ru)».

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

1. VIII Всесоюзной конференции по микроэлектронике. Москва, 1978.

2. Всесоюзной конференции «Микропроцессоры – 85» Методы и микроэлектронные устройства цифрового преобразования и обработки информации. Москва, 1985.

3. Научно-технической конференции «Вклад молодых ученых и специалистов в научно- технический прогресс». Севастополь, 1985.

4. Конференции НТО «Приборпром» Опыт и перспективы развития ГСП в приборостроении и микроэлектронике. Москва, 1986.

5. Научно-технической конференции «Разработка систем технического зрения и их применение в промышленности». Ижевск (Устинов),1986.

6. Семинаре «Перспективные методы планирования, анализа и управления экспериментом в АСНИ и АСУ ТП». Севастополь, 1986.

7. Научно-технической конференции «Технические, технологические и организационно-экономические вопросы ГПС в приборостроении и микроэлектронике». Москва, МГП НТО «Приборпром» им. акад.

С.И.Вавилова, 1988.

8. Всесоюзной конференции «Системы технического зрения и их применение в САПР и робототехнике». Севастополь, 1989.

9. Научно-технической конференции «Автоматизация и механизация производства в приборостроении». Москва, МГПВ научнотехнического общества приборостроителей, 1989.

10. Всероссийской межвузовской конференции «Микроэлектроника и информатика – 98». Москва, 1998.

11.3-й международной научно – практической конференции «Достижения ученых XXI века». Тамбов, 2007.

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

Структура и объем диссертации. Диссертация состоит из введения, четырех глав, заключения, 2-х приложений, содержит страницы текста, включая 140 страниц основного текста, 65 рисунков, 15 таблиц, списка литературы из 112 наименований.

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

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

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

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

Рис.1. Схема АПС распознавания изображений:

1 – наблюдаемый объект; 2 – воспринимающее устройство; 3 – блок обработки проекции; 4 – блок измерения признаков; 5 – блок принятия решения; 6 – результат распознавания; 7 – правило распознавания;

8 – обучающее устройство.

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

Рис.2. Этапы научных исследований (а) и структурная схема модульной системы автоматизации (б) На первом этапе применяются эвристические алгоритмы контурной сегментации. На втором этапе изображения подвергаются нормализации. На третьем – нормализованные изображения классифицируются одним из конструктивных способов.

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

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

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

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

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

Метод пространственного дифференцирования основан на предположении о том, что граничные точки имеют большую величину модуля градиента функции f(x,y). Алгоритм пространственного дифференцирования преобразует исходное изображение в скалярное поле g(x,y) по правилу:

g(x,y) = f ( x, y), xX, Для нахождения контурных линий используется оценка локального значение градиента или его проекции на определённое направление.

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

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

f (x, y, c1, c2, t, a1, a2) = Решение задачи сводится к аппроксимации функции f(x,y) введенной функцией f (x,y). Качество аппроксимации оценивается метрикой (f, f ) в пространстве функций, интерпретируемых в квадрате:

где c1, c2, t – параметры, определяющие ориентацию края и его местоположение; a1, a2 – амплитудные характеристики края.

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

Пусть F(wx,wy) – спектр Фурье функции яркости изображения f(x,y), H(wx,wy) – передаточная характеристика ВЧ фильтра, FR-1 – оператор обратного двумерного преобразования Фурье. Тогда уравнение определяет изображение с подчеркнутыми резкими перепадами яркости, т.е. краями.

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

Алгоритм фиксированных окон (GR1). Схема алгоритма GR приведена на рис.4.

Алгоритм фиксированных направлений (GR2). Разработаны три модификации метода фиксированных направлений для вычисления градиента в точках rd (i, j ), Sd (i, j), Ld (i, j ).

Модификация 1.

Рис.4. Схема алгоритма GR Алгоритм рекуррентной фильтрации (GR3). Дискретная интерпретация алгоритма GR3 приводит к соотношению:

где a ij p ) – элемент матрицы отфильтрованного изображения; ai+, j + – элемент матрицы, принимающий в зависимости от и значения либо элемента отфильтрованной матрицы, либо искаженной помехами; – элемент апертуры. В работе были исследованы 58 масок размером и 22 маски размером 5 5.

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

Рис.6. Зависимости зашумленности изображения от порога для алгоритма GR2 (1,2 – линейные структуры; 3 – кольцевая структура) Ошибки в выборе порога фильтрации приводят к пропуску истинных краевых точек, неправильному определению их положения и принятию шумовых выбросов за элементы контура. В результате эксперимента был определен оптимальный порог фильтрации, зависящий от контрастности и количества уровней серого изображения:

где Gср – среднее значение градиента.

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

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

Сегментацию выполняет однородная, извне не синхронизированная среда клеточной структуры, базовым элементом которой является процессорный элемент (ПЭ), который находится в узлах решетки (рис.7). Среда содержит два входа управления: УПИ – установление пороговой интенсивности и УП – установление предела.

Рис.7. Структурная схема информационных и дополнительных Данная структура выполняет комбинированное кодирование границ каждого сегмента. Граф переходов, узлам которого приписаны некоторые непрерывные отображения, а дугам – условия переходов и выполняемые действия, является гибридным автоматом.

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

Рис.8. Сетевая модель системы обработки изображений Для выделения сегментов изображений и связывания элементов контуров были разработаны и исследованы 5 алгоритмов.

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

Алгоритм маркирования точек (KT2). Пусть h– начальный порог отбора контрольных точек, h – изменение порога, r– размер окрестности, I– исходное изображение. В качестве метрики ( s, k ), вычисляющей расстояние между элементами, задающими изображение и фон, можно использовать ( s, k ) = max{ s, k }, либо ( s, k ) = s 2 + k 2.

Алгоритм прослеживания контура изображения состоит из следующих шагов:

Шаг 1. Анализируем элементы матрицы ai, j и находим первый элемент ai0, j0 0, полагаем n = 0.

Шаг 2. Рассмотрим r – окрестность точки (in, jn) U = {( s, k ) : ( s in, k jn ) r}. Подсчитаем количество точек aij, (i, j ) U r, принадлежащих фону F и не принадлежащих ему:

точек) окрестности Ur(n).

Шаг 4. Если n h, то (in, jn) – контрольная точка контура. Тогда добавляем in в вектор X h = (i0, i1,...), jn - в вектор Yh = ( j0, j1,...), n – в вектор Vh = ( 0, 1,...). Осуществляем поиск первого ненулевого матричного элемента M 0, M1,..., M 7. Если такой элемент Mk найден, то полагаем n:= n +1 и M := M k 1.

Шаг 5. Если ain jn = ai0 j0, то обход контура изображения окончен и переходим к шагу 6, в противном случае – к шагу 2.

Шаг 6. Если m < Mmin (т.е. число контрольных точек невелико), то h:= h h и переходим к шагу 1. Если m Mmin, то массив контрольных точек построен. Многоугольник Im является аппроксимацией исходного изображения. В качестве оценки относительной погрешности такого представления изображения можно использовать величину R := I I m, где – символ симметрической разности множеств.

Алгоритм следящей пары (KT3). Пусть (p, q) – координаты следящей пары контура изображения: р = (рх, ру) – черная, а q = (qx, qy) – белая точки. Пробная точка r = (rх,rу) ищется следующим образом: если точки следящей пары лежат в одном столбце или в одной строке, то новая пробная точка выбирается с координатами rx = qx + py – qy, ry = qy + qx – px. В противном случае пробная точка имеет координаты rx = (px + qx + py – qy)/2, ry = (py + qy – px + qx)/2. Текущее положение следящей пары и возможные новые положения в зависимости от цвета пробной точки показаны на рис.9.

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

Алгоритм поиска в глубину (KT4). Пусть имеются двусвязные компоненты графовой структуры G1, G2, G3, G4 и G5 и точки сочленения 1, 2, 3 (рис.10).

Осуществляем поиск в глубину из вершины t*, принадлежащей G1.

Существует возможность перейти из G1 в G2, проходя через вершину 1. Из G1 попадаем в G3, затем в G4 и G5. Тогда при возвращении в G из G5 через вершину 3 все ребра G5 будут наверху стека. Таким образом, если распознать точки сочленения, то, применяя поиск в глубину и сохраняя ребра в стеке в той очередности, в какой они проходятся, можно определить двусвязные компоненты.

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

Алгоритм прямоугольной сегментации (KT5). Пусть имеется множество модулей M = {mi|i = 1, 2,…, n}. Каждый модуль характеризуется тройкой где Si – площадь модуля, а параметры li и Ui задают нижнюю и верхнюю границу li hi Ui, hi – высота модуля, Wi – ширина модуля. В данном алгоритме узлами графа являются сегменты. На дереве (рис.11) цифрами помечены вершины, соответствующие разрезам, причём V – вертикальный разрез, а H – горизонтальный разрез. Раскраска графа соответствует разбиению сегмента на минимальное число частей, достаточное для удаления циклов. Каждая область ri имеет размеры xi и yi. Очевидно, что размеры области должны соответствовать ограничениям Si xi yi и li y i Ui.

Площадь области ri определяется как xiyi. Будем считать, что связи между модулями mi и mj связывают центры соответствующих областей ri и rj.

Рис.11. Сегменты изображения и бинарное дерево Обозначим через dij длину связей между mi и mj а через сij – стоимость связей. Тогда критерий оптимизации при планировании необходимо построить кратчайший путь от вершины V до множества вершин графа G(i) методом Дейкстры. Вершины, принадлежащие этому пути, необходимо добавить к графу G(i). В результате получится граф контурного изображения Gс(i+1). Для всех пар (V1,V2 ) близко расположенных вершин V1 = (i1, j1 ), V2 = (i2, j2 ), удовлетворяющих имитационной модели был разработан алгоритм для построения дерева детальности. Схема алгоритма контурной сегментации представлена на рис.12.

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

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

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

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

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

Рис.12. Схема алгоритма контурной сегментации Для обработки изображений в АПС используется метод сравнения с эталоном, который достаточно сложно реализовать технически (т.е.

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

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

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

Таблица 1. Оценка доверительного интервала для метода GR Метод GR1 (многоградационные изображения) Квантиль распределения Стьюдента t = 2, Квантиль распределения Стьюдента t = 1, На рис.14 показаны результаты анализа функционирования разработанных алгоритмов и традиционно используемых по сравнению с «идеальным алгоритмом». Разработанные алгоритмы в (1,7–2) раза эффективнее традиционно используемых алгоритмов и по мере роста количества обрабатываемых изображений различия между традиционной методикой сегментации и предложенной становятся все более очевидными.

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

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

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

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

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

• Разработана математическая модель контурной сегментации в АПС, предназначенная для использования в среде многозадачной ОС с поддержкой многопоточности.

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

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

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

• На основе объектно-ориентированного подхода создана, верифицирована и программно реализована имитационная модель контурной сегментации в АПС.

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

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

• Материалы диссертационной работы внедрены в технологический процесс ООО «БелАБМ.ру (BelABM.ru)», а также в учебный процесс МГИЭТ-ТУ.

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

1 Колдаев В.Д. Эвристические алгоритмы контурной сегментации изображений. Научно-технический журнал «Известия высших учебных заведений. ЭЛЕКТРОНИКА» №4, 2007. – М., МИЭТ, 2007. – С.71-75.

2 Колдаев В.Д. Системный подход к анализу контурной сегментации изображений. Оборонный комплекс – научно-техническому прогрессу России: Межотраслевой научно-технический журнал / ВИМИ. – М., Вып. 4, 2007. – С.60-63.

3 Колдаев В.Д. Исследование операций доступа к линейным и нелинейным структурам. Программные средства МИЭТ. Под ред.

Савченко А.В. – М., МИЭТ,1992. – С.36-37.

4 Колдаев В.Д. Предварительная обработка и сегментация сложных многоуровневых изображений. Конференция НТО Приборпром «Опыт и перспективы развития ГСП в приборостроении и микроэлектроники». Вып.2. – М., МИЭТ, 1986. – С.15-16.

5 Колдаев В.Д. Морозова Н.В. Преобразование многоуровневого изображения в контурное методом масок. Сборник научных трудов «Проектирование и применение специализированных вычислителей и систем управления».–М., МИЭТ, 1983.– С.111-116.

6 Колдаев В.Д. Морозова Н.В. Обработка многоуровневых дискретизованных изображений с распознаванием контуров, описываемых цепными кодами. Сборник научных трудов комбинированных вычислительных устройств». – М., МИЭТ, 1984.

– С.101-108.

7 Абрамов В.А, Колдаев В.Д., Морозова Н.В. Выделение элементов контуров многоуровневых изображений градиентными методами.

Москва, Электронная техника, серия «Экономика и системы управления». – М., Вып. 4 (57), 1985. – С.48-52.

8 Абрамов В.А., Колдаев В.Д. Геометрические моменты и iпризнаки в иерархической системе машинного распознавания изображений. Межвузовский сб. научных трудов «Архитектура, схемотехника и математическое обеспечение микропроцессорных систем управления». – М., МИЭТ, 1986. – С.96-102.

9 Колдаев В.Д., Найденов И.В. Моделирование абберационных искажений реальных видеоизображений. Сборник научных трудов «Схемотехника и проектирование специализированных вычислительных систем управления ».–М.,МИЭТ, 1986.–С.124-130.

10 Абрамов В.А., Колдаев В.Д., Алевич А.В. Предварительная обработка изображений в системах технического зрения.

Межвузовский сборник научных трудов «Элементы, узлы, устройства и математическое обеспечение микропроцессорных систем управления». – М., МИЭТ, 1987. – С.5-13.

11 Колдаев В.Д. Лабораторный практикум по курсу «Структуры и алгоритмы обработки данных». Часть 1.– М., МИЭТ, 2006. – 116 с.

12 Колдаев В.Д., Хлебас А.В. Об одном подходе к организации баз данных изображений. Межвузовский сб. научных трудов «Элементы, узлы, устройства и математическое обеспечение микропроцессорных систем управления». – М., МИЭТ,1987. – С.44-52.

13 Колдаев В.Д., Алевич А.В. Система идентификации изображений на основе полярного кодирования. Межвузовский сб. научных трудов «Микропроцессорные вычислительные устройства управляющих систем». – М., МИЭТ,1988. – С.13-20.

14 Колдаев В.Д., Лушников А.В. Цифровое кодирование контуров изображений методом логического сглаживания. Межвузовский сборник научных трудов «Проектирование и применение микропроцессорных управляющих систем». – М., МИЭТ,1989. – С.97-105.

15 Алевич А.В., Колдаев В.Д. Интегрированная система обработки контурных изображений. Межвузовский сборник научных трудов «Проектирование и применение микропроцессорных управляющих систем». – М., МИЭТ,1989. – С.180-188.

16 Коньков Г.В., Колдаев В.Д. Оценка порога фильтрации при выделении контуров многоуровневых изображений. Всероссийская межвузовская конференция «Микроэлектроника и информатика 98». – М., МИЭТ,1998. – С.132.

17 Колдаев В.Д. Алгоритмы построения покрывающего дерева сети.

Информатика и управление: Межвузовский сборник/ под ред.

В.А.Бархоткина. – М., МИЭТ, 2005. – С.72-77.

18 Колдаев В.Д. Основы алгоритмизации и программирования:

Учебное пособие. Под ред. проф. Л.Г. Гагариной. – М.: ИД «Форум» – Инфра - М, 2006. – 416 с.

19 Колдаев В.Д. Лабораторный практикум по курсу «Структуры и алгоритмы обработки данных». Часть 2. – М., МИЭТ, 2007. – 126 с.

20 Колдаев В.Д. Численные методы и программирование: Учебное пособие. Под ред. проф. Л.Г. Гагариной. – М.: ИД «Форум» – Инфра - М, 2007.– 356 с.

21 Колдаев В.Д. Квазитопологический алгоритм контурной международной научно- практической конференции «Достижения ученых XXI века», Тамбов, 2007. – С.139-141.

22 Колдаев В.Д. Градиентная фильтрация изображений в системах технического зрения. Сборник материалов 3-й международной научно- практической конференции «Достижения ученых XXI века», Тамбов, 2007. – С.141-142.

Подписано в печать:

Формат 60х84 1/16. Уч.-изд.л. Тираж 100 экз. Заказ Отпечатано в типографии ИПК МИЭТ.

124498, г. Москва, Зеленоград, проезд 4806, д.5, МИЭТ