Содержание к диссертации
Введение
ГЛАВА 1. Анализ методов и средств цифровой обработки изображений для автоматизированных производственных систем 16
1.1. Анализ методов распознавания изображений 16
1.2. Методы оценки качества изображений 24
1.3. Особенности построения автоматизированных систем распознавания изображений 27
1.4. Методы формирования признаков 33
1.5. Постановка цели и задачи диссертационного исследования 37
Выводы по главе 1 38
ГЛАВА 2. Исследование и разработка эвристических алгоритмов контурной сегментации изображений 40
2.1. Методы выделения контуров изображений 42
2.2. Модификация и исследование методов логического сглаживания 45
2.3. Градиентные методы на основе операторов с 46
окрестностью е х е
2.3.1. Анализ разностного оператора 51
2.3.2. Исследование оператора Робертса 53
2.3.3. Разработка методики использования метода масок 54
2.3.4. Модификация методов Собеля, Превитта, Дэвиса 65
2.4. Разработка эвристических алгоритмов контурной сегментации 68
2.4.1. Алгоритм фиксированных окон {GR1) 68
2.4.2. Алгоритм фиксированных направлений (GR2) 71
2.4.3. Алгоритм рекуррентной фильтрации (GR3) 73
2.5. Обработка результатов экспериментов 74
2.6. Методика и рекомендации по использованию методов выделения контуров и выбора порога фильтрации 79
Выводы по главе 2 82
ГЛАВА 3. Исследование и разработка квазитопологических алгоритмов контурной сегментации 84
3.1. Методы представления контуров 85
3.1.1. Организация данных в АПС 86
3.2. Квазитопологические модели связывания элементов контуров 91
3.2.1. Связность графовой модели 91
3.3. Разработка квазитопологических алгоритмов контурной сегментации 94
3.3.1 .Алгоритм блочной сегментации (ATI) 94
3.3.2. Алгоритм маркирования точек (КТ2) 96
3.3.3. Алгоритм следящей пары (АГ73) 97
3.3.4. Алгоритм поиска в глубину (АТ4) 98
3.3.5. Алгоритм прямоугольной сегментации (КТ5) 99
3.4. Использование квазитопологических алгоритмов в задачах
трассировки 103
Выводы по главе 3 105
ГЛАВА 4. Результаты экспериментальных исследований предложенных методов и алгоритмов 107
4.1. Имитационное моделирование обработки изображений в АПС 107
4.2. Проектирование систем обработки изображений 115
4.3. Результаты экспериментальных исследований алгоритмов 118 Выводы по главе 4 129
Заключение 130
Список литературы 132
- Анализ методов распознавания изображений
- Методы выделения контуров изображений
- Квазитопологические модели связывания элементов контуров
- Имитационное моделирование обработки изображений в АПС
Введение к работе
Цифровая обработка изображений приобретает в настоящее время большое значение во многих областях деятельности человека. Особая роль в технике обработки изображений принадлежит ПЭВМ, позволяющей в относительно короткие сроки и с меньшими затратами по сравнению с экспериментальным макетированием моделировать любые методы обработки. При этом обеспечиваются точность, надежность, практически абсолютная воспроизводимость результатов, возможность контроля процесса обработки на любой промежуточной стадии, гибкость в отношении типа и характера решаемых задач. Использование ПЭВМ дает возможность создавать автоматизированные производственные системы (АПС), позволяющие точнее, быстрее и надежнее человека решать различные задачи обработки визуальной информации.
Затраты на разработку АПС распределяются следующим образом: ПЭВМ -16%, периферийное оборудование - 27%, программное обеспечение - 45%, интеграция - 12%. Эти цифры свидетельствуют о том внимании, которое должно быть уделено при проектировании таких систем, разработке программного обеспечения и устройств ввода-вывода [1-6].
Среди проблем, возникающих при разработке прикладных и научно-исследовательских автоматизированных комплексов, выделяется круг задач, связанных с обработкой зрительной информации в реальном времени. Подобные задачи возникают при автоматизации контроля, управлении промышленными установками, в информационных системах мобильных роботов [1,4,5,7]. В последние годы проблема автоматического анализа формы и состояния пространственных объектов, информация о которых представлена в виде изображений (фотографий, видеосигналов и т.д.), является актуальной во многих отраслях человеческой деятельности. При создании математического обеспечения СОИз с визуальной адаптацией к среде функционирования, необходима разработка эффективных алгоритмов контурной сегментации изображений, сочетающих в себе компактный способ представления видеоинформации об объектах среды и не требующих больших вычислительных мощностей для реализации процедур выделения видеоизображений. Обработка структурированных изображений в СОИз связана с проблемой формализации задач обработки и построением адаптивных методов
5 сегментации, широко варьирующих в предметных областях и различных задачах обработки. Без решения этих проблем практически невозможно создать эффективное специализированное математическое обеспечение СОИз и средства описания процессов обработки структурированных изображений, адекватно представляющих их.
Основными этапами представления, обработки и анализа информативных сигналов, которые в совокупности или в отдельных сочетаниях могут выполняться программными средствами обработки и анализа изображений, являются следующие: фильтрация, сегментация, классификация изображения и его фрагментов, распознавание графических образов [6-9].
Несмотря на обилие существующих подходов к описанию систем контурной сегментации изображений, вид которых широко меняется в зависимости от целей исследования и предметной области, большинство из них затруднительно использовать в задачах проектирования АПС на этапах построения их описания. Важной особенностью задач обработки и анализа изображений является то, что большинство из них плохо формализованы. Сказывается отсутствие адекватных математических моделей наблюдаемых реальных ситуаций или объектов, на базе которых можно было бы вести расчеты и получать количественные и качественные выводы, а также разрабатывать соответствующее программное обеспечение [6,7,12,13].
Таким образом, исследования, направленные на создание универсальных методов и алгоритмов контурной сегментации изображений, а также программные средства, нацеленные на решение вопросов верификации и валидации широкого класса программных систем в АПС, являются актуальными.
При всех преимуществах существующие программные системы дороги, не предусматривают расширения, несовместимы по аппаратной платформе с другими системами. СОИз не включают необходимых процедур сегментации или обладают недостаточным быстродействием, особенно при визуализации изображений в АПС. Работами по созданию методов и программного обеспечения обработки изображений электронных изделий занимаются коллективы специалистов США, Западной Европы и Японии. Например, в настоящее время близкие к предлагаемому проекту по тематике исследования выполняются в научно-
6 исследовательских лабораториях IBM, Калифорнийского университета, Лоуренсовской лаборатории и научно-техническом университете Гонконга. Указанные исследования проводятся в рамках программы Applied Mathematical Sciences Research Program of Office of Energy Research под эгидой департамента энергетики США и частных научных фондов. Известен ряд систем обработки печатных плат и интегральных схем:
система Vision 105 Optotech (Израиль) представляет собой автоматизированную систему для контроля рисунков слоев многослойной печатной платы, с помощью которой возможно выявлять как малые, так и большие дефекты;
в системе P-SEE фирмы DII-MICO International (США) изображение платы сравнивается с данными САПР, хранящимися в ПЭВМ, что дает возможность обнаруживать более широкий спектр дефектов;
из систем обработки следует выделить продукты фирмы Mentor Craphics. Однако стоимость указанных систем составляет миллионы долларов США, и не все из них обладают высокими показателями по быстродействию и достоверности идентификации.
В странах бывшего Советского Союза и в России аналогов подобных систем нет, а все известные исследования и разработки представляют собой отдельные аппаратные и программные комплексы для решения лишь фрагментов указанной сложной научной проблемы. Результаты исследований, направленных на создание эффективных методов визуализации изображений, изложены в работах зарубежных и отечественных ученых: L. Davis, J.F. Jarvis, B.Lippel, M.Kurland, R.W Floyd, J.M.S. Prewitt,. A. Rosenfeld,. B.E. Bayer, T Pavlidis, W.K.Pratt, В.Ф.Нестерук, И.А.Богуславского, В.А.Сойфера, Л.П.Ярославского, Ю.И. Журавлева, СВ. Яблонского, М.Н. Вайнцвайга, В.А Абрамова [3,5,6,8,9,12].
Таким образом, проблема исследования и разработки эффективных методов визуализации изображений в гибких автоматизированных производственных системах с использованием современных математических методов и микропроцессорных средств вычислительной техники является весьма актуальной. Целью диссертационного исследования является повышение достоверности идентификации изображений при решении задач неразрушающего контроля в АПС на основе разработки моделей и алгоритмов контурной сегментации изображений
7 с априорной неопределенностью о характере шумов.
Для достижения поставленной цели необходимо решение следующих задач:
Анализ структуры и функциональных возможностей современных автоматизированных систем управления производством.
Классификация, формализация задачи, анализ методов и алгоритмов сегментации и фильтрации изображений вАПС.
Разработка новых и адаптация известных методов сегментации изображений к условиям задачи преобразования информации.
Разработка и исследование эвристических и квазитопологических алгоритмов контурной сегментации изображений.
Разработка алгоритмов контурной сегментации изображений со сложным фоном, основанных на объединении областей.
Программная реализация и верификация имитационной модели контурной сегментации изображений в АПС на основе предложенных алгоритмов.
Формулировка и обоснование критерия оптимальности в виде показателя вычислительной сложности, характеризующего эффективность используемых алгоритмов контурной сегментации в АПС.
Для решения поставленных проблем используются методы исследования, основанные на принципах системного подхода к моделированию сложных систем, методы цифровой обработки сигналов и изображений, математического и имитационного моделирования, теории вычислительных процессов, дискретной математики, теории графов, математического анализа.
Научная новизна работы состоит в создании совокупности научно-обоснованных технических разработок, моделей и алгоритмов, обеспечивающих повышенную идентифицируемость и достоверность контурной сегментации изображений в АПС. При этом получены следующие новые научные результаты:
проведен аналитический обзор функциональных возможностей АПС в контексте реализации автоматизированной обработки видеоизображений;
создана концептуальная модель функционирования системы обработки изображений как составляющая АПС, на базе разработанных математических моделей и алгоритмов;
предложен новый подход к дифференцированному сглаживанию фрагментов изображения, основанный на анализе различных областей анализируемых элементов, позволяющий в 1,5 раза повысить скорость обработки изображений, а также в 2 раза улучшить качество выделяемых контуров по сравнению с традиционными методами;
установлена функциональная зависимость, определяющая значение оптимального порога фильтрации равного (1,4-1,6) от среднего значения градиента;
на основе объектно-ориентированного подхода создана, верифицирована и программно реализована имитационная модель контурной сегментации в АПС;
разработаны эвристические и квазитопологические алгоритмы контурной сегментации, позволяющие обрабатывать изображения с зашумленностью до 20% и предложен селективный подход к их использованию;
на основе имитационной модели разработаны квазитопологические алгоритмы построения дерева детальности для иерархического представления элементов контуров изображений.
Практическая значимость заключается в расширении возможностей автоматизированной обработки изображений в АПС.
Представленные в работе эвристические и квазитопологические алгоритмы контурной сегментации изображений направлены на решение практических задач АПС. Исследования доведены до конкретных алгоритмов, методик и программных средств. Результаты имитационного моделирования подтверждают повышение эффективности контурной сегментации на основе предложенных моделей и алгоритмов по сравнению с традиционно используемыми. Разработанные методы и алгоритмы позволяют обрабатывать изображения с уровнем зашумленности до 20%, повышать в 1,5 раза скорость контурной сегментации изображений, а также увеличивать количество идентифицируемых деталей изображений в широких диапазонах яркостей.
Простота и вычислительная эффективность предложенных методов обеспечивают высокую скорость обработки данных. Модули пакета программ, разработанные на языке C++, легко интегрируются в системы обработки данных
для решения практических задач.
Полученные результаты доведены до уровня практического использования, что подтверждено актом внедрения ООО «БелАВМ.ш (. Все работы по реализации и внедрению проводились под руководством или при непосредственном участии автора. Результаты диссертационной работы используются в учебном процессе на кафедре ИПОВС в МИЭТ.
По результатам проведенных исследований разработаны программные средства визуализации изображений, которые используются при изучении вузовских дисциплин «Структуры и алгоритмы обработки данных», «Автоматизированные информационные системы», «Компьютерная практика», «Проектирование информационных систем».
Достоверность полученных результатов подтверждается результатами имитационного моделирования, доказавшими преимущества предложенных в работе методов и алгоритмов контурной сегментации изображений, выразившиеся в повышении качества нахождения контуров, а также успешным внедрением и эксплуатацией моделей и алгоритмов в 000 «БелАВМ.ш (.
Личный вклад автора. Все основные результаты получены автором лично. Главными из них являются:
проведение аналитического обзора функциональных возможностей АПС в контексте структурно-функциональной реализации автоматизированной обработки визуальной информации и формализация процесса обработки изображений;
разработка математической модели и использование объектно-ориентированного подхода для моделирования и анализа процессов обработки информации;
создание концептуальной модели функционирования системы обработки изображений на базе разработанных математических алгоритмов;
алгоритмическая реализация эвристических и квазитопологических процедур контурной сегментации изображений, основанных на дифференцированном сглаживании фрагментов изображения с различной информационной ценностью и селективный подход к их использованию;
алгоритм нахождения априорной информации о выборе порога фильтрации
изображений, теоретически и экспериментально обоснованный на изображениях произвольной формы.
построение и верификация имитационной модели контурной сегментации изображений в АПС;
автор диссертации принимал активное участие в разработке, тестировании, сопровождении, предложенных и внедренных им новых технических решений в технологический процесс ООО «БелАБМ.ру ( и во внедрении результатов диссертационной работы в учебный процесс кафедры «Информатика и программное обеспечение вычислительных систем» Московского государственного института электронной техники.
На защиту выносятся:
Формализация процесса обработки и визуализации изображений в АПС.
Технология проектирования систем контурной сегментации изображений и пространственных образов, использующая объектно-ориентированный подход для моделирования и анализа процессов обработки информации.
Созданные и модифицированные градиентные методы и алгоритмы фильтрации изображений, эвристические и квазитопологические алгоритмы контурной сегментации изображений и селективный подход к их использованию.
Метод построения минимального связывающего дерева в структуре эмпирических данных для выявления устойчивых связей между системами типовых версий об изображениях.
Алгоритм нахождения априорной информации о выборе порога фильтрации и сглаживания изображений, теоретически и экспериментально обоснованный на изображениях произвольной формы.
Имитационная модель контурной сегментации изображений в АПС, обеспечивающая увеличение в 2 раза качество выделения контуров по сравнению с традиционными методами.
Программная реализация алгоритмов фильтрации и контурной сегментации изображений в технологический процесс 000 «БелАБМ.ру (.
Апробация работы. Основные положения и результаты диссертационной работы были доложены и обсуждались на следующих научных конференциях и
11 семинарах:
VIII Всесоюзной конференции по микроэлектронике. Москва, 1978.
Всесоюзной конференции «Микропроцессоры - 85» Методы и микроэлектронные устройства цифрового преобразования и обработки информации. Москва, 1985.
Научно-технической конференции «Вклад молодых ученых и специалистов в научно- технический прогресс». Севастополь, 1985.
Научно-технической конференции «Опыт и перспективы развития ГСП в приборостроении и микроэлектроники». Москва, МГП НТО Приборпром им. акад. С.И.Вавилова, 1986.
Научно-технической конференции «Разработка систем технического зрения и их применение в промышленности». Ижевск (Устинов), 19 86.
Научном семинаре «Перспективные методы планирования, анализа и управления экспериментом в АСНИ и АСУ ТП». Севастополь, 1986.
Научно-технической конференции «Технические, технологические и организационно-экономические вопросы ГПС в приборостроении и микроэлектронике». Москва, МГП НТО Приборпром им. акад. С.И.Вавилова 1988.
Всесоюзной конференции «Системы технического зрения и их применение в САПР и робототехнике». Севастополь, 1989 .
Научно-технической конференции «Автоматизация и механизация производства в приборостроении». Москва, МГПВ научно-технического общества приборостроителей, 19 89.
10. Всероссийской межвузовской конференции «Микроэлектроника и
информатика - 98». Москва, 1998.
11. 3-й международной научно - практической конференции «Достижения ученых
XXI века». Тамбов, 2007.
Публикации. По материалам диссертации опубликовано 30 работ, в том числе 19 статей в журналах и научных сборниках, 11 тезисов докладов на Международной, Всероссийских конференциях и научно-технических семинарах. Автор принимал участие в 12 научно-технических отчетах по НИР.
Структура и объём работы. Диссертация состоит из введения, четырех глав, заключения, 2 приложений, содержит 172 страницы текста, включая 140 страниц основного текста, 65 рисунков, 15 таблиц, списка литературы из 112 наименований.
СОДЕРЖАНИЕ РАБОТЫ
Во введении обосновывается актуальность темы диссертации, формулируются общие проблемы, цели и задачи исследования, научное и практическое значение полученных результатов, рассматривается структура диссертации и взаимосвязь отдельных глав.
В первой главе проведён обзор существующих методов и средств обработки изображений. Исследованы наиболее распространенные математические модели выделения контуров и фильтрации изображений, показано, что основным их недостатком является отсутствие универсальных механизмов нахождения термов для построения связных контуров и фильтрации изображений. Отмечено, что, несмотря на многообразие методов, и алгоритмов обработки изображений, они не подходят для эффективного использования в АПС, и хотя некоторые из них можно модифицировать, но в основном, требуется создание новых эффективных методов и алгоритмов обработки и воспроизведения изображений.
Представлен аналитический обзор современных методов обработки видеоизображений. Установлено, что все существующие системы обладают следующими недостатками:
низкое качество контурной сегментации и фильтрации изображений из-за наличия аддитивных шумов при использовании в системах технического зрения;
сложность интеграции механизмов обработки изображений в структуру автоматизированной производственной системы;
изменчивость требований к программному обеспечению систем технического зрения и сложность их формализации.
В целом, большинство существующих систем плохо приспособлены для работы в производственных структурах и возникает необходимость в разработке алгоритмов, способных успешно решать задачи контурной сегментации и фильтрации и ориентированных на работу в АПС.
На основе проведенного анализа сформулированы цели и задачи
диссертационного исследования, главными из которых являются формализация задачи обработки визуальной информации и разработка моделей и алгоритмов контурной сегментации изображений.
Во второй главе рассматриваются эвристические алгоритмы выделения контуров изображений в АПС, которые наряду с общими для данных систем свойствами параллельности и временными ограничениями, характеризуется тем, что информация о внешних событиях формируется в результате программной обработки зрительных данных, представленных в цифровом виде.
В основе рассматриваемых алгоритмов распознавания используется априорная информация о характерных свойствах объекта, таких, как форма, размер, яркость, местоположение в поле зрения. Учет этих свойств позволяет сократить объем обрабатываемых зрительных данных и обеспечить функционирование АПС в режиме реального времени. Проектирование алгоритмов обработки изображений является специфической задачей, решаемой индивидуально для каждой АПС.
Для анализа изображений были разработаны 3 и модифицированы 8 эвристических алгоритмов контурной сегментации. Для каждого метода выбор порогового значения для оценки наличия контура в выбранной окрестности обычно осуществляется интуитивно, в зависимости от априорной информации об изображении и требований конкретной задачи. Поскольку пороги регулируются в зависимости от требуемой степени четкости прорисовки контуров, то, изменяя пороги, можно визуализировать изображение, постепенно прорисовывая его от более четких контуров к менее различимым.
В диссертации предложен метод определения порогов яркости в зависимости от типа изображения, требуемой четкости воспроизведения мелких деталей и используемых масок. При этом определена функциональная зависимость для оптимального порога фильтрации. С целью оценки эффективности разработанных моделей и алгоритмов было проведено вычисление доверительного интервала для порога фильтрации, указывающего на то, что оценка результатов экспериментов состоятельна и несмещена.
В третьей главе проводится исследование алгоритмов связывания элементов контуров. Предложены быстродействующие методы и алгоритмы обработки изображений с различным разрешением, глубиной цвета и шкалами
цветового охвата. Предложены методики обработки изображений в АПС с использованием квазитопологических моделей:
разработаны эффективные по быстродействию и ресурсным затратам топологические процедуры предварительной обработки изображений в программно-информационных комплексах АПС;
разработана методика использования методов обработки и формирования программно-информационных комплексов идентификации изображений с учетом точности, быстродействия и ресурсов памяти;
исследована эффективность 5 квазитопологических алгоритмов контурной сегментации в АПС и способов их реализации по сравнению с существующими методами;
разработан алгоритм иерархической аппроксимации, позволяющий осуществить контурную сегментацию исходного видеоизображения построением древовидной структуры, к терминальным вершинам которой применяют квазитопологические алгоритмы выделения и связывания контуров.
Разработанный системный подход обобщает различные способы построения описаний систем, объединяют макро - и микроподходы в проектировании, делает возможным формализацию построения модели проектируемой системы обработки изображений, а также создание формального аппарата проектирования подобных систем на стадии построения их описания.
В четвёртой главе рассматриваются вопросы программной реализации и
имитационного моделирования систем обработки изображений в АПС. При этом
особое внимание уделялется транзактному способу организации
квазипаралеллизма, при котором функциональные однотипные действия объединяются. Связь между компонентами модели устанавливается с помощью системы очередей, выбранных алгоритмов поступления и способов извлечения из них транзактов. Программная реализация имитационной модели, использующей предложенные в диссертационной работе математические модели и алгоритмы, использует объектно-ориентированный подход.
При решении задач зрительного восприятия в АПС, по сравнению с традиционными подходами к обработке изображений, возникают вопросы,
15 связанные с необходимостью комплексного описания среды функционирования на основе учета объема априорной информации, создания модели проблемной среды, анализа множества произвольно расположенных объектов, необходимостью работы в реальной динамической среде. В процессе отладки может потребоваться оперативное вмешательство в работу алгоритмов, принятие решений, настройка параметров, изменения в данных и т.п. Поэтому оперативное управление процессом обработки изображений и визуальный контроль результатов являются основной методологией этапа тестирования и отладки.
Проведен анализ результатов имитационного моделирования эвристических и квазитопологических алгоритмов контурной сегментации изображений в АПС и предложен селективный подход к использованию разработанных алгоритмов.
В заключении приведены основные результаты и выводы, полученные при работе над диссертацией.
В приложениях приведены программные модули, написанные на языке Си, построенные на основе разработанных методов и алгоритмов. Представлены практические результаты работы программных модулей и акты внедрения результатов диссертации.
Анализ методов распознавания изображений
Классическая постановка задачи выделения сигнала из аддитивной смеси сигнала с шумом сформулирована Н.Винером в 1942 г [2,3,4,6]. На вход линейной системы, характеризуемой импульсной переходной характеристикой h(f), поступает сумма статистически независимых сигнала x(t) и помехи n(t): z(f) = x(i) + n{t). (1) Как помеха, так и сигнал считаются случайными стационарными процессами (ССП), корреляционные функции которых известны. Отклик фильтра описывается интегралом свертки:
Если фильтр предназначен для восстановления сигнала x(t) из смеси (1), тогда ошибка восстановления имеет вид: є(0 = .КО- ( ) (3) Выражение для частотной характеристики Винеровского фильтра имеет вид: #(/)=——тЬтт (4) Gx(f) + Gn(f) где #(/) = F [h(t)}, G(f) = F {К(т)}, F{-} - оператор преобразования Фурье. Действительно, если спектр помехи на всех частотах мал по сравнению со спектром сигнала, т.е. Gn(f)«Gx(f), тогда #(/) = 1, т.е. фильтрация не нужна. Если же, напротив, в некоторой области частот Gn(f)»Gx(f), тогда #(/)« Gx(f)/Gn(f), т.е. фильтр подавляет помеху в этой области частот (рис. 1.1).
Характерным для систем обработки изображений является восстановление и улучшение изображений с помощью инверсной свертки, обработка массивов отсчетов с помощью алгоритмов быстрого преобразования Фурье. Особое место уделяется преобразованию контрастности, выделению контуров и статистической обработке изображений.
Рис. 1.1. Винеровская фильтрация узкополосной помехи Для сжатия информации наиболее эффективны ортогональные преобразования Фурье, Адамара и Уолша [6,14,72,84,85]. Требуемая производительность оценивается величинами 100-1000 MIPS, массивы данных -105-106 отсчетов (табл. 1.1).
Таблица 1.1. Характеристики сигналов в системах цифровой обработки Назначение Характеристика Диапазон частот, размерность Требуемое. быстродействие Радиолокационные системы Фильтрация сигналов антенны ЮМгц - 10 Ггц, до 214 точек 109 умножений в секунду Обработка звуковых сигналов Анализ и синтез речи, сжатие и распознавание 20Кгц (40 Кгц), 16 бит 10 MIPS
Системы обработки изображений Восстановление и улучшение изображений 105-106 отсчетов 100-1000 MIPS В 1970 г. В.Ф.Нестерук и Н.Н.Порфирьева [4,6] предложили контрастный закон восприятия света, в котором учтены недостатки закона Вебера - Фехнера rlr _ т2г 7 Т2г л. Т2г (5) где crQJ - приведенный сигнал ощущения; L0, Lj - величины яркостей.
С целью устранения многозначности условий, при которых достигается максимальное значение контраста, неравноправности влияния яркостей на контраст, Р.А. Воробель в 1999г. [5] предложил линейное описание локальных контрастов: С = Li\ Lit LMAX , где Lh L2 - величины яркостей элементов изображения (L\, Li є [0, LMAX\), LMAX - максимальное значение величины яркости элементов изображения. Был предложен метод определения контраста сюжетного изображения, который базируется на линейном описании локальных контрастов: cf = TF777 \2 L - Г)+ LMAX 12 L -1" - LMAX П н&№ С6) 2LMAX где L - величина яркости элементов изображения; L - среднеарифметическое значение уровней яркостей элементов изображения; H(L) - гистограмма распределения яркостей элементов изображения.
Методы обработки дискретных (цифровых) изображений можно разбить на две большие группы: непосредственные и спектральные. В непосредственных методах обработке подвергаются исходные пиксели изображения, в то время как спектральные методы имеют в своей основе применение различных дискретных унитарных преобразований (Фурье, Уолша, Хаара и др.) и производят обработку уже не исходных точек изображения, а коэффициентов преобразования (элементов дискретного спектра). Причем применяемые в спектральных методах преобразования, как правило, двухмерные, в силу двухмерности обрабатываемых сигналов (цифровых или дискретных изображений).
Постановка вопроса о применении спектральных методов для сжатия изображений стала возможной благодаря появлению в 1965 году работы Кули и Тьюки [25], содержавшей описание алгоритма быстрого вычисления дискретного преобразования Фурье. В 1969 году Прэтт, Эндрюс и Кэйн предложили использовать для кодирования изображений вместо преобразования Фурье преобразование Адамара, что во многих практических случаях позволяет значительно уменьшить объем необходимых вычислений [2,3,39,65]. После этого были предприняты исследования по применению для кодирования изображений дискретных преобразований Карунена - Лоэва и Хаара [16,17,44]. В 1971 году Шибата и Эномото предложили специально для использования в кодировании изображений так называемое наклонное преобразование векторов из 4-х или 8-ми компонент. Вскоре после этого Прэтт, Чен и Уилч разработали обобщенный алгоритм наклонного преобразования векторов большой длины и двумерных массивов [65,72,73,83]. Как показано Ахмедом и др., в применении к кодированию изображений, для которых подходит Марковская статистическая модель, дискретное косинусное преобразование (ДКП), имеющее быстрый алгоритм вычислений, приближается по эффективности к преобразованию Карунена -Лоэва [16,17,39].
Методы, базирующиеся на использовании векторного квантования (в пространственной или спектральной областях), субполосного кодирования, преобразований на основе волновых импульсов («всплесков»), а также фрактальные методы, могут обеспечить высокие уровни сжатия изображений. Система функций Крестенсона - Леви (Виленкина - Крестенсона) [6,65] является частным случаем общих мультипликативных систем и была получена в результате обобщения на комплексную плоскость хорошо известной системы функций Уолша.
Множество методов, которые решают задачу преобразования изображений с целью улучшения их визуального качества и повышения информативности, подразделяется на обработку в частотной и пространственной областях. Для обработки изображений в пространственной области наибольшее распространение получили методы, представленные на рис. 1.2.
Методы наращивания областей. Методы основаны на поиске групп пикселей с близкими значениями яркости. Наиболее простой критерий основывается на оценке максимальной разности значения яркости отдельного пикселя и средней яркости формируемой области. Среди методов наращивания областей выделяют центроидное связывание (априорная информация на основе стартовых точек), метод слияния-расщепления (предварительный выбор однородных областей и их последующее наращивание), метод водоразделов (выделение однородных областей на основе градиента интенсивности изображения), метод деформируемых шаблонов (на основе соответствия шаблонам, изменяемым под воздействием функции внутренней энергии) [77,84,85].
Ранговые методы. Существующие методы цифровой обработки изображений с позиций использования вычислительных средств можно разделить на две категории - структурированные и неструктурированные методы.
Методы выделения контуров изображений
Контур изображения представляет собой совокупность его пикселей, в окрестности которых наблюдается скачкообразное изменение функции яркости. Так как при цифровой обработке изображение представлено как функция целочисленных аргументов, то контуры представляются линиями шириной, как минимум, в один пиксель. Если исходное изображение содержит участки с плавно меняющейся яркостью, то при этом не гарантируется непрерывность контурных линий: разрывы контуров будут наблюдаться в тех местах, где изменение функции яркости не является достаточно резким. Методы выделения контуров изображений подразделяются на группы: пространственное дифференцирование; функциональная аппроксимация; высокочастотная (ВЧ) фильтрация.
Общим для всех методов является стремление рассматривать границу как область резкого перепада функции яркости изображения J[x,y), отличает их вводимая математическая модель понятия край или алгоритм поиска краевых точек [11,12,16,17,30]. Метод пространственного дифференцирования основан на предположении о том, что граничные точки имеют большую величину модуля градиента функции J[x,y). Алгоритм пространственного дифференцирования преобразует исходное изображение в скалярное поле g(x,y) по правилу [30]: g(x,y) = pf(x,y)\\, VxeX, pf(x y)\\ = дДх,у) дх + д/(х,у) ду л U Обработка градиентного изображения осуществляется с помощью порогового детектора по правилу: fl, g(x,y) T; В(х,у) = , где Т- величина порога фильтрации. [0, g(x,y) T,
Метод функциональной аппроксимации позволяет решить задачу выделения границ с помощью оптимизационных алгоритмов. Для каждой точки изображения (х\ У) рассматривается окрестность R с центром в этой точке. Для элементов этой окрестности определяется «ступенчатая» функция [28,29]: ах, схх + с2у Т, (x,y)eR; f(x,y,cuC2,t,aua2) U+a2, схх + с2у Т, (x,y)eR;, 0, (x,y)tR. Решение задачи сводится в аппроксимации функции Дх,у), введенной функцией f(x,y). Качество аппроксимации оценивается метрикой p(f,f) в пространстве функций, интерпретируемых в квадрате: R где с\, съ t - параметры, определяющие ориентацию края и его местоположение, «і, а2 - амплитудные характеристики края. Если удастся подобрать параметры аппроксимирующей функции, обеспечивающие заданное качество аппроксимации (р), то принимают решение о наличии в точке (х , у ) края.
Метод ВЧ фильтрации позволяет решить задачу выделения границ с помощью обработки изображения в области пространственных частот. Этот метод основан на том, что информацию о границах объектов несут ВЧ составляющие спектра изображения [4-6]. Пусть F(wx,wy) - спектр Фурье функции яркости изображения fix,y); H(wx,wy) - передаточная характеристика ВЧ фильтра; FR \z) -оператор обратного двумерного преобразования Фурье. Тогда уравнение g{x,y)= FR-l{F(wx,wy)-H(wx,wy)} определяет изображение с подчеркнутыми резкими перепадами яркости, т.е. контурами. Методы выделения краев изображений подразделяются на [23,30,33,84]: параллельные методы, в которых принимается решение о наличии контура в данной точке изображения на основе результатов анализа некоторой окрестности этой точки; последовательные методы - методы, в которых результат обработки точек изображения зависит от предыдущих результатов точек.
В процессе развития систем обработки изображений появилось несколько концепций и подходов к представлению изображений и большое количество структур данных для реализации этих представлений. Конечным этапом обработки, лежащим в основе процессов интерпретации и понимания, является распознавание. Суть задачи распознавания - установить, обладают ли изучаемые объекты фиксированным конечным набором признаков, позволяющим отнести их к определенному классу. В задачах распознавания можно ввести понятие аналогии или подобия объектов и сформулировать понятие близости объектов в качестве основания для зачисления объектов в один и тот же класс или разные классы. При этом оперируют набором прецедентов-примеров, классификация которых известна и которые могут быть предъявлены алгоритму распознавания в виде формализованных описаний для настройки на задачу в процессе обучения. В задачах распознавания применяются подходы, использующие корреляционные методы, основанные на принятии решений по критерию близости к эталонам, признаковые и синтаксические методы, основанные на выборе признаков и правил, и нормализацию, приближающую изображение к эталонному.
При обработке изображений необходимо учитывать возможность получения «плохой» информации: с пропусками, разнородной, косвенной, нечеткой, неоднозначной, вероятностной. Для оценки качества фильтрации вводятся понятия вероятных моделей шумовых воздействий [105-107].
Импульсный шум. Этот вид искажения данных наиболее часто возникает в результате влияния помех на информацию в процессе ее передачи по цифровым каналам связи. В процессе вычислительного эксперимента точки изображения с заданной вероятностью замещались случайным значением из допустимого диапазона.
Аддитивный шум. Этот вид искажения возникает в результате нестабильности характеристик различных технических устройств, влияния электромагнитных помех на усилительные каскады и аналоговые линии связи. Поэтому каждая точка такого изображения содержит помимо полезного сигнала некоторую шумовую составляющую. При этом к значению цвета или яркости каждого пикселя добавляется некоторая случайная величина, значения которой в каждой точке различны.
Мультипликативный шум. Значение цвета или яркости каждого пикселя умножается на некоторую случайную величину, значения которой близки к единице и в каждой точке различны. Частным случаем мультипликативного шума является спекл - шум, присутствующих на изображениях, полученных в результате отражения когерентного излучения.
Для контурной сегментации изображений используют линейные и нелинейные алгоритмы цифровой фильтрации. К линейным можно отнести трансверсальную и рекурсивную фильтрацию с помощью маски, пороговую фильтрацию, а к нелинейным - медианную фильтрацию.
В работе была предложена идея локальной динамической модели определения контура изображения, основанная на линеаризации двумерной функции яркости. Для этого разработаны 3 алгоритма - GRl,GR2,GR3, а также исследованы методы логического сглаживания и градиентные.
Квазитопологические модели связывания элементов контуров
Связывание элементов края, устранение возможных разрывов и удаление несуществующих пересечений осуществляется с использованием графовых моделей. Узлами графа или состояниями являются элементы края, определяемые двумя соседними единичными элементами изображения. Для связывания элементов контуров используются следующие методы: методы Прима и Крускала для построения основного дерева минимального веса; методы Дейкстры и динамического программирования для выбора по определенному критерию кратчайшего пути на графе [15,42,67].
Все эти методы относятся к последовательным и их недостаток в том, что ошибка, допущенная в середине края, приводит к большой погрешности в конце, так как алгоритмы не предусматривают обратного движения по графу.
Связность графовой модели
Важным подходом для описания вида структуры плоской области является ее представление в виде графа. Во многих случаях для этого определяется схема (скелет) области с помощью прореживающих (сокращающих) алгоритмов. В графе может существовать вершина, называемая точкой сочленения, или разделяющей вершиной, удаление которой вместе с инцидентными ей ребрами разъединяет оставшиеся вершины. На рис.3.7 точками сочленения являются вершины с номерами 4, 5 и 7. Максимальный двусвязный подграф (без точек сочленения) является двусвязной компонентой или блоком [42,67,70]. — — Рис.3.7. Разделимый граф и его двусвязные компоненты Каркас (V, Т) связного неориентированного графа G = (V, Е) содержит (N - 1) ребро, где N - количество вершин G. Каждое ребро, не принадлежащее Т, т.е. любое ребро из Е - Т, порождает в точности один цикл при добавлении его к Т. Поскольку каркас состоит из (N- 1) ребра, в фундаментальном множестве циклов графа G относительно любого каркаса имеется (М - N + 1) циклов, где М -количество ребер в G. Для нахождения контурного каркаса (стягивающего дерева) графовой структуры используются методы поиска в глубину и в ширину.
При поиске в глубину анализируется вершина и, смежная с v. Если на очередном шаге у вершины q нет вершин смежных с ней и не рассмотренных ранее, то осуществляется возврат из вершины q к вершине, которая была до нее.
При поиске в ширину на каждом шаге рассматриваются все вершины, связанные с текущей.
Граф и его каркасы, построенные методами поиска в глубину и в ширину, показаны на рис.3.8 (в скобках указана очередность просмотра вершин графа). а б в Рис.3.8. Граф (а) и его контурные каркасы, построенные методами поиска в глубину (б) и в ширину (в) При использовании графовых структур часто применяют методы, основанные на определении однородных цветов или текстур, либо метод водоразделов. В работе для контурной сегментации изображений предлагаются алгоритмы построения ациклических подграфов: Крускала, Прима, Дейкстра [42,102,103].
Пусть Vx = 0"і»Уі) вершина графа градиентного изображения, тогда существует вершина V2 = (i2,j2) принадлежащая контурному изображению, причем вершина Vx принадлежит окрестности {(i,./)1\i2 - і\ є, \j2 - j\ j точки V2. Введем числовую характеристику с (i,j) = , которую будем называть стоимостью вершины графа градиентного изображения, a Gr(i,j)- функцией модуля градиента изображения. Далее рассмотрим две вершины Vxn Vk и предположим, что эти вершины принадлежат контуру. Очевидно, что любой путь, соединяющий данные вершины можно рассматривать в качестве аппроксимации данного гипотетического контура. Длиной (стоимостью) пути (Vh V2, ..., Vm Vk) будет сумма D= с(ук) + с(Уд Наиболее точной аппроксимацией контура (кривой), соединяющей вершины Vx,Vk будет путь, имеющий наименьшую стоимость. С учетом этого можно сформулировать следующую оптимизационную задачу выбора контурного изображения. Наиболее оптимальное контурное изображение является частичным подграфом градиентного изображения, который имеет наименьшую стоимость из всех допустимых подграфов. Стоимость подграфа определяется как сумма стоимостей его вершин. Расстоянием dg(yx,V2) между вершинами Vx и К, на графе градиентного изображения называется стоимостью пути, соединяющего эти вершины. Аналогичным образом определяется расстояние dc(VvV2) на графе контурного изображения. Для того чтобы графы контурного и градиентного изображения имели приблизительно одинаковые метрические характеристики, необходимо, чтобы расстояние, вычисляемое по графу контурного изображения, было приблизительно такое же, как и на графе градиентного изображения, т.е. dc(Y\,V2) а dp(Vx,V2) для вершин VX,V2 контурного изображения.
Имитационное моделирование обработки изображений в АПС
Как правило, компьютерные системы проектирования производства представляют собой средства динамического моделирования различных процессов, позволяющие интерактивно проследить за течением процессов в исследуемой системе и оценить адекватность ее параметров, способность выполнять поставленную задачу. При моделировании технологических процессов необходимо чтобы модель достаточно хорошо отображала исследуемую сторону функционирования объекта. Методы математического и физического моделирования помогают решать задачи, связанные с уточнением параметров решающих правил при реализации различных алгоритмов обработки изображений в АПС. Они способствуют выявлению обоснованных требований к отдельным звеньям разрабатываемой системы, особенно в тех случаях, когда аналитические расчётные методики оказываются мало эффективными или достаточно сложными.
На начальном этапе разработки самым доступным, но вместе с тем достаточно гибким и эффективным средством представляется математическое (имитационное) компьютерное моделирование. В качестве непосредственного объекта исследования оно предполагает использование некоторой программы, представляющей собой комплексную математическую модель. Эта модель обычно включает в себя модели основных звеньев системы: изображения объекта, оптической системы, фотоприёмного узла (анализатора изображения), различных дестабилизирующих факторов (помех) и др., а также модель используемого алгоритма [33,36,38]. К числу несомненных достоинств метода математического моделирования следует отнести возможность получения за короткое время и без существенных материальных затрат большого объема данных, характеризующих поведение будущей системы, её характеристики (выделение контуров, распознавание объектов) в зависимости от каждого из интересующих параметров (рис.4.1).
Алгоритмизация информационных этапов позволяет построить сетевую модель процесса с последующим анализом входящих в нее лексем. Для построения имитационной модели в этом случае необходимо выделить исследуемую функцию реального объекта, формализовать эту функцию в виде некоторых операторов связи между входом и выходом и воспроизвести на имитационной модели данную функцию на базе математических соотношений и физической реализации процесса.
Созданная модель используется для постановки экспериментов по имитации работы реальной системы в определенных условиях. Полученные формальные результаты моделирования необходимо интерпретировать в понятия реальной системы. Если такие результаты работы реальной системы не отвечают требованиям, то имитационная модель адаптируется, и процесс симуляции работы повторяется. В конечном итоге получаем выводы и рекомендации по структуре и параметрам реальной системы.
При построении имитационной модели особое внимание уделяется организации квазипараллелизма функционирования модели. Каждое действие представимо в виде набора простейших операций, кроме того, возможно построение функциональных зависимостей их выполнения друг от друга. Для имитации поведения системы используется так называемый транзактный способ организации квазипаралеллизма, при котором однотипные функциональные действия объединяются.
