Содержание к диссертации
Введение
ГЛАВА 1. Исследование методов сегментации в системах анализа изображений 12
1.1 Формулировка задачи сегментации 13
1.2 Анализ методов сегментации изображений
1.2.1 Анализ подходов к классификации методов сегментации и синтез классификационной системы 16
1.2.2 Контурно-ориентированные методы сегментации 20
1.2.3 Сегментно-ориентированные методы сегментации 22
1.2.4 Сегментно-ориентированные методы связной сегментации 25
1.2.5 Классификация методов сегментации 30
1.3 Анализ перспективных подходов к использованию методов сегментации в системах анализа изображений 31
1.3.1 Особенности методов контурного анализа 32
1.3.2 Модификации сегментно-ориентированных методов сегментации 37
1.3.3 Разновидности методов связной сегментации 39
1.3.4 Концептуальный синтез схемы метода сегментации
1.4 Анализ способов количественной оценки эффективности процесса сегментации 49
1.5 Выводы по главе 52
1.6 Постановка задачи исследования 54
ГЛАВА 2. Синтез высокоуровневых моделей и методов системы анализа изображений 55
2.1 Иерархическая модель системы анализа изображений 55
2.2 Многомерная модель представления исходных данных в системе сегментации изображений
2.2.1 Способ многомасштабного спектрального представления исходных данных сегментации 60
2.2.2 Способ текстурного анализа изображений на основе многомасштабного анализа и вейвлет-преобразования 64
2.2.3 Способ многомасштабного контурного анализа на основе вычисления оператора Собела 70
2.3 Метод сегментации изображений на основе выращивания и слияния областей 74
2.3.1 Способ автоматического определения центров кристаллизации 74
2.3.2 Способы реализации процессов выращивания и слияния областей 77
2.3.3 Способ автоматического определения оптимального состояния процесса слияний областей 83
2.4 Выводы по главе 84
ГЛАВА 3. Разработка и исследование оптимизированных алгоритмов реализации методов выращивания и слияния областей 86
3.1 Методика экспериментального исследования быстродействия алгоритмов 87
3.2 Исследование быстродействия процессов в составе системы анализа изображений 88
3.3 Разработка и оптимизация алгоритмов выращивания областей
3.3.1 Исследование классического алгоритма реализации метода выращивания областей 89
3.3.2 Оптимизация алгоритма реализации метода выращивания областей 95
3.4 Экспериментальное исследование алгоритмов выращивания и слияния областей 105
3.4.1 Определение основных исследуемых величин 105
3.4.2 Построение статистических оценок временной сложности алгоритмов 107
3.5 Выводы по главе 112
ГЛАВА 4. Разработка программной системы анализа изображений и экспериментальное исследование разработанных методов и алгоритмов 114
4.1 Целевые прикладные эффекты реализации системы анализа изображений 115
4.2 Исследовательская программная система анализа изображений 117
4.3 Исследование вспомогательных алгоритмов системы сегментации
4.3.1 Алгоритм реализации способа многомасштабного спектрального представления изображений 123
4.3.2 Алгоритм реализации способа текстурного анализа на основе вычисления вейвлет-статистики 126
4.3.3 Алгоритм реализации способа многомасштабного контурного анализа на основе вычисления оператора Собела 128
4.3.4 Алгоритм реализации способа автоматического определения центров кристаллизации 130
4.3.5 Алгоритм реализации способа автоматического определения оптимального состояния процесса слияний областей 131
4.4 Экспериментальное исследование системы анализа изображений в промышленных применениях 134
4.4.1 Исследование характеристик пластических деформаций биметаллической пластины 134
4.4.2 Исследование стратегии слияния областей на основе локального правила к-то порядка 139
4.5 Перспективные возможности расширения системы сегментации 142
4.5.1 Анализ изображений радиальных структур 142
4.5.2 Анализ формы объекта, восстановленной по одиночному изображению 147
4.5.3 Анализ семантической структуры железоуглеродистых сплавов 149
4.5.4 Расширение модели представления исходных данных в системе сегментации 151
4.6 Выводы по главе 151
Заключение 153
Список использованных источников
- Анализ перспективных подходов к использованию методов сегментации в системах анализа изображений
- Способ многомасштабного спектрального представления исходных данных сегментации
- Разработка и оптимизация алгоритмов выращивания областей
- Экспериментальное исследование системы анализа изображений в промышленных применениях
Введение к работе
Актуальность работы. Системы анализа изображений применяются во многих научно-технических и производственных отраслях, где требуется повысить эффективность процедур обработки визуальных данных: медицине, промышленности, аэрофотосъёмке, системах безопасности и охраны правопорядка, робототехнике и других. В промышленности системы анализа изображений используются в металлографии, дефектоскопии, при оценке качества обработки поверхностей, исследовании эксплуатационных свойств материалов и в других прикладных областях. Как правило, под анализом в данных системах понимается выявление объектов, представленных на изображении, и расчёт их характеристик, заданных методикой конкретного исследования и основанных на различных геометрических и статистических признаках. Следовательно, важнейшим этапом обработки визуальных данных в системах анализа изображений является процесс сегментации - выделения однородных по какому-либо признаку областей (сегментов) на исходном цифровом растровом изображении.
На данный момент существует множество методов и подходов к анализу изображений, описанных в работах сотрудников научных школ В. А. Сойфера, С. С. Садыкова, Р. С. Гонсалеса (R. С. Gonzalez), Л. Шапиро (L. Shapiro), Ю-Дж. Жанга (Y.-J. Zhang), М. Баатца (М. Baatz), сотрудников лаборатории компьютерного зрения университета Беркли (UC Berkeley) и других. Однако на практике лишь немногие из них, наиболее изученные и удобные в реализации, используются в технических системах при решении прикладных задач. При этом применение интеллектуальных методов с высокой степенью организации вычислительной системы должно дать эффект оптимизации, включающий: а) качественное расширение возможностей системы анализа изображений для обработки изображений сложных структур объектов; б) повышение точности анализа изображений; в) совершенствование управления процессом анализа; г) снижение затрат времени на анализ изображений. К данным методам относятся методы сегментации, использующие информацию о связности областей, в том числе методы, основанные на технике выращивания областей. Их исследования являются актуальными, так как они позволяют значительно более эффективно решать прикладные задачи, где до этого применялись классические подходы, к примеру, пороговая сегментация.
Цель и задачи исследования. Цель исследования состоит в повышении эффективности процесса сегментации в составе системы анализа изображений за счёт разработки новых высокоорганизованных методов сегментации, комплекса связанных способов и алгоритмов обработки визуальных данных на основе техники выращивания областей и многомасштабных преобразований.
Для достижения поставленной цели необходимо:
- на основе системного подхода исследовать теорию методов сегментации в контексте их влияния на эффективность функционирования технических си-
стем анализа изображений;
разработать метод сегментации изображений как систему вычислительных операций с высокой степенью организации и интеграции связанных способов обработки визуальных данных;
разработать и исследовать оптимизированные унифицированные алгоритмы реализации оригинального метода сегментации;
провести экспериментальное исследование разработанного метода сегментации и комплекса связанных способов обработки визуальных данных в составе системы анализа изображений.
Объектом исследования является процесс сегментации изображений в составе систем анализа изображений неоднородной сегментной структуры.
Предметом исследования являются методы повышения эффективности системы сегментации, оптимизации её вычислительных процессов и комплекса связанных способов обработки визуальных данных.
Методы исследования. В работе используются методы системного подхода в контексте теории обработки изображений; диалектики; теории множеств; многомасштабного анализа; вейвлет-преобразований; математической морфологии; теории алгоритмов; аппроксимации; математической статистики; компьютерного моделирования.
Достоверность и обоснованность результатов работы, а также адекватность предложенных моделей подтверждается корректностью использованных методов исследования; систематичностью анализа и синтеза моделей, методов, алгоритмов; сходимостью теоретических выводов и данных экспериментов.
Научная новизна работы выражается в следующих пунктах:
предложена классификационная система методов сегментации с использованием бинарных оппозиций и формализма теории множеств, отличающаяся от традиционных, основанных на принципе обобщения по используемым в процессе обработки средствам; разработанный подход к классификации позволил выявить перспективные направления проектирования нового метода сегментации изображений;
построена многомерная модель представления исходных данных в системе сегментации, основанная на концепции многомасштабного анализа;
разработан унифицированный подход к созданию алгоритмических систем, используемых при сегментации изображений методом выращивания и слияния областей.
Основные положения, выносимые на защиту:
способы преобразования изображений в многомерной модели: способ многомасштабного спектрального представления; способ текстурного анализа при помощи вычисления вейвлет-статистики; способ многомасштабного контурного анализа на основе вычисления оператора Собела;
метод сегментации изображений на основе выращивания и слияния об-
ластей, включающий разработанный способ определения центров кристаллизации и оригинальный критерий определения оптимального состояния процесса слияний областей, отличающийся усовершенствованной организацией;
- алгоритм реализации разработанного метода сегментации с временной
оптимизацией и унифицированной структурой.
Практическая ценность работы заключается в следующем:
разработанная многомерная модель представления исходных данных в системе сегментации позволяет выполнять корректную сегментацию изображений неоднородной сегментной структуры, что обеспечивает универсальность применения в прикладных задачах;
реализация разработанного метода сегментации позволяет оптимизировать функционирование системы анализа изображений по показателям точности, временных затрат и управляющих воздействий;
разработано программное обеспечение количественного анализа растровых изображений, позволяющее повысить эффективность исследований образцов различных материалов в промышленных применениях.
Реализация и внедрение полученных результатов. Основные результаты использованы на производствах ОАО «НПО «Сатурн», ЗАО «ВолгАэро», ООО «Литейно-механический завод» и внедрены в учебном процессе ФГБОУ ВПО «РГАТУ имени П. А. Соловьёва».
Апробация работы. Основные положения диссертации докладывались и обсуждались на следующих форумах: I Всероссийская научная конференция молодых учёных «Теория и практика системного анализа» (Рыбинск, 2010); XI Международная научно-техническая конференция «Кибернетика и высокие технологии XXI века» (Воронеж, 2010); Всероссийская межвузовская научная конференция «III Всероссийские научные Зворыкинские чтения» (Муром, 2011); Международная молодёжная конференция «XI Королёвские чтения» (Самара, 2011). Научно-исследовательские работы проводились при поддержке государственного Фонда содействия развитию малых форм предприятий в научно-технической сфере по программе «Участник молодёжного научно-инновационного конкурса».
Публикации. По теме диссертации опубликовано 12 научных работ: 4 статьи в научных журналах, в том числе 3 статьи в журналах, рекомендуемых ВАК РФ для публикации основных результатов диссертаций; 5 докладов в сборниках трудов конференций; патент РФ на изобретение № 2440609 от 20.10.2010; 2 свидетельства о государственной регистрации программ для ЭВМ: № 2009613898 от 20.07.2009, № 2010614091 от 23.06.2010.
Структура и объём работы. Диссертация содержит введение, 4 главы, заключение, изложенные на 150 страницах машинописного текста, список использованных источников, состоящий из 108 наименований, 4 приложения. Материал работы включает 80 рисунков, 13 таблиц.
Анализ перспективных подходов к использованию методов сегментации в системах анализа изображений
На первом принципе построены классификации, определяющие, например, следующие группы: методы выделения контуров, методы пороговой обработки, методы выращивания областей, методы на основе теории графов, нейросетевые методы и другие. Следует отметить, что здесь используются наименее универсальные признаки алгоритмов, что и порождает большое разнообразие данных групп, уже не пригодных для построения иерархических связей классификаций. Для построения более высоких уровней обобщений в данных классификациях [13, 15] используются свойства, выделенные в рамках второго принципа.
На втором принципе основаны классификации Ю-Дж. Жанга (Y.-J. Zhang) [14] и С. В. Поршнева, А. О. Левашкиной [5]. В основе данных классификаций лежат свойства алгоритмов сегментации, сформулированные в других работах, такие как: - начальное выделение контуров или областей [2]; - параллельная или последовательная обработка информации [5]; - приложение к монохромным или цветным изображениям [5]; - присутствие в алгоритме встроенного критерия качества сегментации [5]. Кроме перечисленных свойств уже включённых в указанные классификации в работах других авторов можно найти следующие выделенные классификационные свойства: - выполнение сегментации как выделения определённого объекта от фона или полная сегментация изображения на ряд областей без определённых предпочтений в выборе объекта [4, 17]; - сегментация на основе свойств пикселов или областей [14, 16]; -сегментация в автоматическом или интерактивном режиме [4]. После анализа обзора методов сегментации, выполненного в монографии Р. С. Гонсалеса и Р. Э. Вудса [2], в дополнение данного списка сформулируем ещё одно свойство: сегментация с использованием информации о связности пикселов или без использования.
Анализ представленных классификационных признаков показал, что все они на практике по своей сути являются бинарными оппозициями, противопоставлениями. Использование данных разделений является вполне естественным при анализе сложных объектов, таких, например, как системы (методы) сегментации. Это положение можно вывести как следствие одного из законов диалектики [18] - единства и борьбы противоположностей, который является источником существования и развития объектов различной природы.
Противоречия, в свою очередь, делятся на основные и неосновные, причём в разные периоды своего существования пребывают либо в стадии острого конфликта, либо его разрешения. Применив данное правило к методам сегментации в свете выделенных противоречий, можно видеть, что, действительно: - некоторые оппозиции являются менее существенными, к примеру, наличие встроенного критерия качества (при его принципиальном теоретическом отсутствии), некоторые - более существенными: использование информации о связности пикселов позволяет значительно повысить точность сегментации, а также избежать известного недостатка сегментации - дефекта «соли и перца» [19]; - одни противоречия являются менее острыми, например, разделение на автоматические и интерактивные методы (здесь скорее отражается степень автоматизации, выражение которой в виде бинарного значения будет сильным упрощением), другие - более острыми и существенными: начальное выделение контуров или областей является пока достаточно сильным классификационным признаком, отражающим весьма важную сторону метода-объекта.
Таким образом, классификацию можно построить на основе некоторого переменного набора классификационных признаков, которые, кроме того, могут быть упорядочены по приоритету в зависимости от их важности для классификации и текущего состояния исследуемой области знаний. Выполнение любой классификации можно представить как задачу разделения единого множества на подмножества [14]. Тогда классификацию С, основанную на предложенном подходе, зададим группой С = {М,СО,$, (1.4) где М = {М\,М2 } - множество методов сегментации; СО - {С\,02, . Оп) - множество используемых классификационных признаков (оппозиций); Ъ, - оператор классификации. Каждый классификационный признак Ох является множеством, состоящим из двух элементов {ах,Ъх} - противоположных свойств метода сегментации. Тогда декартово произведение CG всех используемых оппозиций 0\,02, .-Оп даст набор классификационных групп-кортежей {Gj\ i = \,2,...2n} CG = (...{{Olx02)x03)x04..) = {Gi\i = l,2,...2n} = = {{ai,a2...an),...(bi,a2...bn),...(bi,b2...bn)}. В таком случае оператор классификации есть отображение множества методов сегментации М во множество классификационных групп CG .M- CG, t{My)=Gt. (1.6) Сформулировав правила для построения классификации методов сегментации, можно составить список классификационных признаков, упорядоченных по приоритету (табл. 1.2). Определим первые три признака в качестве основных при последующем анализе методов сегментации по причине их наибольшей важности для характеристики текущего состояния рассматриваемой области, то есть наивысшей комплексной оценки существенности и остроты заложенных в них противоречий для дальнейшей классификации существующих методов сегментации.
Способ многомасштабного спектрального представления исходных данных сегментации
Наибольшую функциональную и вычислительную нагрузку в системе анализа изображений с представленной структурой несут процессы восстановления, улучшения и сегментации изображений. При этом процессы восстановления и улучшения выполняют подготовку (предобработку) данных к сегментации. Из этого следует, что: - в случае удовлетворительного качества исходного изображения процессы предобработки могут быть исключены из последовательности вычислений; - основным критерием оптимальности при выборе методов предобработки является их способность обеспечивать необходимое качество изображений для последующей сегментации; - проектирование методов сегментации является первичным шагом при создании системы анализа изображений; - функциональность методов предобработки может быть сокращена при условии пониженной чувствительности методов сегментации к искажениям изображения, что возможно, если алгоритмы, эквивалентные схемам предобработки, интегрированы в метод сегментации. Таким образом, определив приоритет разработки процесса сегментации в проектировании системы анализа изображений, перейдём к определению состава и структуры системы сегментации.
Первым обязательным этапом обработки визуальных данных в системе сегментации является преобразование исходного изображения в модель представления данных системы сегментации. Для этого могут быть использованы следующие преобразования: - перевод изображения в выбранную цветовую модель, оптимальную с точки зрения эффективной сегментации целевого класса изображений; - текстурный анализ изображения, позволяющий выявить различные статистические, квазипериодические зависимости изменения цвета и яркости выделяемых сегментов; - контурный анализ, состоящий из вычисления градиентных операторов с возможностью выделения приоритетных ориентации границ объектов; - и другие преобразования. Выбор модели представления исходных данных сегментации в значительной мере определяет качество и точность последующей сегментации. Наибольший эффект при этом достигается, когда корректно выделенные объекты в выбранной модели представления обладают максимальной внутренней однородностью признака сегментации и минимальным подобием между собой. Но в то же время выбор модели представления исходных данных сегментации напрямую зависит от используемых методов сегментации -возможности использования определённых моделей и структур данных в алгоритмах сегментации.
Из постановки задачи исследования следует, что система сегментации, основанная на методе выращивания областей должна в автоматическом режиме выполнять полное разбиение всего изображения на сегменты. Поэтому следующей необходимой составляющей системы сегментации является метод определения центров кристаллизации.
Задачей данного этапа является расстановка на исходном растровом изображении точек роста (центров кристаллизации) таким образом, чтобы каждой потенциально выделяемой области изображения соответствовала одна точка роста, находящаяся на наиболее однородном участке сегмента.
Выдвижение требований при выборе и проектировании метода определения центров кристаллизации зависит от выбранной стратегии выращивания областей, использования локального либо глобального правила выращивания. Так при выборе глобального правила выращивания областей требования к выполнению сформулированной задачи максимальны. При выборе локального правила выращивания областей центры кристаллизации необязательно должны соответствовать выделяемым объектам, однако в этом случае в структуру системы сегментации необходимо включать процесс завершающей сегментации на основе метода слияния областей.
Следующий этап обработки - процесс выращивания областей - занимает центральное место в системе сегментации, являясь отправной точкой, от которой происходит выбор остальных компонентов и структур управления системы сегментации.
Исходя из требований, предъявляемых к системе анализа изображений, для процесса выращивания областей необходимо выбрать стратегию квазипараллельного попиксельного выращивания сегментов из центров кристаллизации по глобальному правилу анализа состояния сцены сегментации до полного заполнения сегментами всей площади изображения.
Практические исследования показали, что в общем случае метод выращивания областей совместно с методом автоматического определения центров кристаллизации не позволяет проводить корректную сегментацию изображения, так как центров кристаллизации, а значит и сегментов, выделяется значительно больше, чем областей, воспринимаемых человеком. В результате это приводит к избыточной сегментации.
Данную проблему можно решить с помощью включения в структуру системы сегментации операции слияния областей. Сутью данного процесса является попарное объединение смежных сегментов по выбранному признаку подобия с целью достижения оптимального состояния сегментации, которое определяется с помощью встроенного в систему сегментации критерия окончания процесса слияний. Функциональная схема системы сегментации, объединяющая введённые процессы обработки данных и последовательную структуру вычислений, представлена на рис. 2.2.
Разработка и оптимизация алгоритмов выращивания областей
Первостепенное свойство центра кристаллизации (точки роста) - она должна находиться внутри области, подлежащей выделению. Из описания метода выращивания областей (подпункт 1.2.4.4) следует, что одной точке кристаллизации соответствует одна область и никак иначе. Если в области, воспринимаемой человеком однородной, будут выделены две точки кристаллизации, то в итоге работы метода на месте предполагаемой одной области будут присутствовать две; если же в потенциальной области вообще нет центров кристаллизации, то эта область будет разделена на части соседними сегментами.
Правильный выбор количества и положения центров образования областей является условием успешной сегментации, не приводящей к грубым ошибкам анализа. Если привлечь к выбору центров кристаллизации оператора, то проблема была бы решена, но задачей в данном случае является минимальное использование труда человека. Основным способом автоматического определения центров кристаллизации является поиск локальных минимумов на градиентном изображении, полученном с помощью одного из дифференциальных операторов.
Используем для расчёта градиентного изображения введённый в данной работе способ вычисления вейвлет-статистики (пункт 2.2.2). Для получения двумерной функции UW {х,у) многомасштабного градиентного изображения просуммируем значения вейвлет-статистики г на Va3nbix масштабах / для каждого пиксела (х,у) Ш2{х,у)=\т1 (2.18) 1=1 С целью устранения шумовых локальных минимумов функции UW (х,у) введём операцию её квантования (огрубления). На следующем шаге процесса определения центров кристаллизации сегментов необходимо решить задачу минимизации для функции UW {х,у). Так как исследуемая функция определена на двумерном дискретном пространстве, то использование классических методов оптимизации функций многих переменных здесь будет неэффективно. В данном случае возможно использование метода подавления немаксимумов [10] применительно к задаче минимизации. Данный метод предполагает сканирование изображения с помощью маски 3x3 с целью определения точек, окружённых пикселами с наибольшими значениями. Но в такой постановке окажутся потерянными точки нестрогого локального минимума, а, исходя из требований, предъявляемых к задаче обнаружения центров кристаллизации, в области равно малых значений функции должна быть определена как минимальная одна точка, лежащая в центре области равных значений. Для этого предполагается после нахождения точки нестрогого локального минимума выполнить морфологическую заливку связной с ней области того же уровня с целью определения и сохранения средней точки выделенной компоненты как центра кристаллизации. Кроме того, необходимо предусмотреть операцию проецирования найденной средней точки компоненты связности на саму выделенную область, так как она может иметь форму кольца.
Метод предполагает поиск точек, в окрестности которых нет элементов меньших, чем сама эта точка, и есть хотя бы один больший элемент. Если анализируемая точка имеет 8-связную окрестность, все элементы которой имеют большие значения, то локальный минимум найден. Во всех остальных случаях из найденной точки начинается процесс морфологической заливки области равных значений.
Математическое описание морфологических операций, как правило, даётся в формализме теории множеств [2]. Для выделения компоненты связности в морфологии используется операция дилатации Ф, то есть расширение множества на его границах.
Если известная точка с находится внутри искомой области, то операция выделения компоненты связности Су- на множестве значений функции UW (х, у) выглядит как Ск=(Ск_1ФВ)пА, = 0,1..., A = {uWZ(x,y)\{uWZ(x,y) = c)} , (2.19) с0 = Н где В - примитив дилатации, в данном случае квадрат 3x3 пике; к - шаг дилатации. Выполнение алгоритма завершается по условию Q- = Ск_\. Точки множества Q- представляют изображение связной области равных значений, для которого необходимо определить центр тяжести. Центр тяжести для области, где все значения равны, можно определить путём нахождения точки внутри ограничивающего область прямоугольника, в которой пересекаются горизонтальная и вертикальная линии так, что по обе стороны от каждой из них лежат равномощные подмножества исследуемой области С#. Далее необходимо найти ближайшую в смысле евклидова расстояния от центра тяжести точку, принадлежащую С , то есть произвести проецирование центра тяжести на область С . Вычисленную точку будем считать новым центром кристаллизации.
В процессе сегментации может быть использовано локальное либо глобальное правило выращивании сегментов (пункт 1.3.3). Для проектируемой системы сегментации используем глобальное правило выращивания и поставим задачу разработки высокоэффективных алгоритмов реализации метода выращивания областей. При формализации действий с данными для метода выращивания будем исходить из условия эквивалентности пиксела рху и элементарного сегмента Se, введённого в пункте 2.2.1. Все пикселы-кандидаты, претендующие на включение в какой-либо сегмент, должны быть смежными со своими областями, то есть находиться на внешней их границе. Тогда для данного сегмента и его граничного пиксела (обозначим эту пару Ц , = р/, ,] ) предикат смежности N\Sj,Sj) = 1.
Экспериментальное исследование системы анализа изображений в промышленных применениях
Для определения оптимальной связи на каждом шаге выращивания необходимо проводить поиск записи-связи с минимальным значением функции гетерогенности в активной части списка связей (в приведённом примере (рис. 3.7) связь Z/) является оптимальной).
В момент слияния двух сегментов их списки связей должны объединяться и переходить к результирующему сегменту. При сопутствующем пересчёте зависимых связей указатели на сегменты-предки должны заменяться указателем на новый сегмент. Анализ данного процесса показывает, что замена указателей в списке связей нового сегмента часто будет приводить к образованию записей-дубликатов. Данный процесс недопустим, так как является причиной возможных ошибочных попыток повторного объединения сегментов и увеличивает общие временные затраты. Следовательно, при объединении списков связей и их обновлении необходимо выполнять поиск и удаление записи-дубликата в результирующем списке зависимых связей, а именно в той его части, которая получена от другого сегмента-предка.
Процесс выращивания должен продолжаться до тех пор, пока в активной части списка связей присутствуют записи-связи. Формализуем описанный алгоритм в виде схемы (рис. 3.11).
Основным объектом анализа, как и в предыдущем случае, станет основной цикл выращивания (блоки 4-12). Очевидно, что оценка количества итераций QA (формула (3.1)) внешнего цикла выращивания для нового алгоритма осталась неизменной, так как процесс выращивания состоит в строго последовательном увеличении областей по одному пикселу. Также остаётся неизменной оценка количества анализируемых пар «сегмент - граничный пиксел» QP(n) (выражения (3.4) -(3.8)). Однако равенство QP{ri) = QD{ri) здесь нарушается, так как в процессе анализа пар «сегмент - граничный пиксел» (активных записей-связей; рис. 3.11, блок 4) происходит лишь поиск оптимальной записи-связи, но не пересчёт записей с вычислением значений функции гетерогенности. Поэтому отдельно рассчитаем теоретическую оценку количества вычислений QD{n) функции гетерогенности.
В оптимизированном алгоритме вычисление функции гетерогенности (рис. 3.11, блок 9) на каждом шаге выращивания производится только для связей, ассоциированных с последним выросшим сегментом. Следовательно, по сравнению с предыдущим расчётом количество вызовов функции гетерогенности уменьшится пропорционально числу активных сегментов. Число активных сегментов задаётся в самом начале процесса сегментации количеством центров кристаллизации т. Тогда для максимально плотной расстановки центров кристаллизации получим _2А -yjnj Можно заметить, что среднее количество связей одного сегмента в начале сегментации при максимально плотной расстановке по рис. 3.4, справа, как и по формуле (3.9), равно 6. Для случая минимально плотной расстановки (рис. 3.6) оценка величины QD{ri) по формуле (3.7) имеет силу и для оптимизированного алгоритма, так как количество сегментов в данном случае равно 1.
Запишем асимптотические оценки временной сложности задачи вычисления функции гетерогенности QD(ri) в зависимости от различных расстановок центров кристаллизации для нового алгоритма. ez g = 6 ax=3—=„з, (ЗЛО) ( Ъ\ Зп-5-Jn 3—1, 3V". (3.11) QD(n)=QA-QDg = 101 QD(n)eo(nl 5), iV (ЗЛ2) Таким образом, аналитическая оценка временной сложности алгоритма показала, что в результате оптимизации алгоритма выращивания областей удалось существенно (на п ) снизить количество вычислений QD{n) функции гетерогенности. Кроме того, максимальное снижение временной сложности (на п ) достигнуто для начальных конфигураций сегментации с высокими значениями степени заполнения центрами кристаллизации SR, при которых значительно возрастает размер задачи сегментации, и, следовательно, увеличивается эффект от проведённой оптимизации.
В оптимизированном алгоритме выращивания (рис. 3.11) присутствуют процессы и структуры управления, аналогов которым нет в оригинальном алгоритме (рис. 3.2), что делает невозможным комплексное сравнение обеих версий на основе теоретических оценок временной сложности.
Экспериментальная оценка времени работы оптимизированного алгоритма показала, что наиболее затратным с вычислительной точки зрения является процесс поиска оптимальной связи в активной части списка связей (рис. 3.11, блок 4) в составе основного цикла выращивания. Отношение по времени выполнения для данного блока к сумме всех остальных операций выращивания находится в диапазоне 6/1 ... 35/1 (при сегментации изображения 128035.jpg (рис. 3.1) с размерами 30-150 Кпикс). Следовательно, именно данный процесс требует дальнейшей оптимизации.
Назначением блока поиска является определение оптимальной связи для последующего объединения записанной в ней пары сегментов. Критерием оптимальности здесь является минимальное значение функции гетерогенности - расстояния в выбранном для сегментации пространстве признаков сегментов. Тогда для определения оптимальной связи, необходимо просмотреть весь список активных связей и сравнивать сохранённое значение Delta функции гетерогенности с временным оптимумом. Однако данный поиск можно не делать вовсе, если задаться условием постоянной упорядоченности активной части списка связей. В таком случае оптимальная связь всегда находится в начале (или в конце) списка (рис. 3.12).
Похожие диссертации на Повышение эффективности процесса сегментации в системах анализа изображений на основе метода выращивания областей и многомасштабных преобразований
