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

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

7

Калинин Павел Владимирович

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

Специальность 05.13.17 - «Теоретические основы информатики»

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

5 ДЕК 2013

005543602

Воронеж-2013

005543602

Работа выполнена в ФГБОУ ВПО «Воронежский государственный университет»

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

доктор технических наук, профессор

Официальные оппоненты: Базарский Олег Владимирович

доктор физико-математических наук, профессор, ВУНЦ ВВС «Военно-воздушная академия имени профессора Н.Е. Жуковского и Ю.А. Гагарина», профессор кафедры физики и химии

Куцов Руслан Владимирович

кандидат физико-математических наук, доцент, ФКОУ ВПО Воронежский институт ФСИН, заместитель начальника организационно-научного отдела

Ведущая организация ФГАОУ ВПО «Южный федеральный университет»

Защита состоится «24» декабря 2013 г. в 15:10 на заседании диссертационного совета Д 212.038.20 при Воронежском государственном университете по адресу: 394006, г. Воронеж, Университетская пл., 1, ВГУ, ауд. 335

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

Автореферат разослан «1» ноября 2013 г.

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

С. А. Шабров

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

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

Восстановление изображений и устранение негативного воздействия помех достигается путем выполнения процедур фильтрации. Изображения, искаженные аппликативными помехами (АП), являются наиболее сложными с точки зрения их восстановления. АП связаны с появлением различного рода неоднородностей, локальных областей аномальных значений, областей закрытия и пораженных участков на анализируемых изображениях. Исследования вопросов обработки изображений (сегментации и фильтрации, обнаружения объектов) в условиях помех, в том числе и АП, проводилась в ряде работ В.А. Понькина, В.А. Сойфера, А.П. Трифонова, A.A. Сироты, Е.А. Самойлина, Р.В. Куцова, В.Г. Попова, M. Н. Лантюхова, И.В. Апалькова, A.JI. Приорова, В.В. Хрящева, W. Pratt, R. Wood, R. Gonzalez, S. Gould, P. Felzenszwalb, D. Huttenlocher, X. Ren, J. Malik, J. Shi, A. Moore, I. Jermyn, H. Ishikawa, M.-Y. Liu, R. Achanta, O. Veksler, Y. Boykov и др. В то же время, комплексного эффективного решения задачи автоматического восстановления реальных изображений, искаженных АП, предложено не было. Известные алгоритмы имеют ряд ограничений. Часто, для борьбы с импульсными и аппликативными помехами небольшой площади применяются модификации медианных фильтров, малопригодные для устранения аппликативных помех большой площади. Для устранения АП в задачах фильтрации и обнаружения объектов применяются линейные и нелинейные алгоритмы обработки, синтезированные на основе представления реальных изображений как реализаций случайных гауссовских полей, что также далеко не всегда эффективно.

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

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

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

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

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

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

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

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

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

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

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

4. Разработка алгоритмов сегментации изображений, в том числе в интересах обнаружения АП, а также комбинированных алгоритмов восстановления реальных изображений, искаженных АП.

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

Основные результаты, выносимые на защиту, и их научная новизна.

На защиту выносятся следующие результаты, впервые подробно развитые или полученные в работе.

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

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

нелинейных алгоритмов фильтрации.

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

4. Комбинированные алгоритмы фильтрации реальных изображений в условиях АП.

Научная новизна полученных результатов определяется следующим.

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

2. Полученные соотношения для нижней границы дисперсии ошибки восстановления гауссовских случайных полей учитывают возможность влияния не только аддитивных, но и импульсных и аппликативных помех. При их обосновании доказано, что диагональные элеменп,I матрицы ковариации ошибки при оптимальном оценивании (восстановлении) изображения, содержащего пропуски отдельных пикселей, не превышают соответствующих диагональных элементов матрицы ковариации ошибки при оптимальном оценивании (восстановлении) изображения, содержащего вместо них ложные наблюдения (наблюдения, искаженные импульсным шумом или аппликативной помехой). Предложено два подхода к оценке НГ: первый отличается прямым применением неравенства Рао-Крамера для функции правдоподобия изображения; второй -использованием предположения о наличии информации о координатах искаженных элементов изображения и применением дополнительной процедуры статистического моделирования.

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

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

полученной на основе предложенного АСС.

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

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

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

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

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

Реализация результатов работы. Полученные в диссертации результаты в части разработай алгоритмов анализа изображений использованы в учебном процессе ВГУ и при выполнении НИР «Разработка моделей, методов и алгоритмов обработки информации для создания информационных технологий и систем нового поколения», номер государственной регистрации № 01201263910, 2012-2013 г.г.

Личный вклад автора. Основные результаты по теме диссертации получены лично автором и опубликованы в соавторстве с научным

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

Публикации. По теме диссертации опубликовано 11 работ, из них 3 работы - в изданиях, рекомендованных ВАК.

Апробация работы. Результаты диссертационной работы докладывались на XII, Х1П и XIV Международной научно-технической конференции «Кибернетика и высокие технологии XXI века» (Воронеж) в 2011, 2012 и 2013 годах; на X, XI, XII Международных конференциях «Информатика: проблемы, методология, технологии» (Воронеж) в 2010, 2011 и 2012 годах; на региональной научно-практической конференции студентов, аспирантов и молодых ученых «Инновационные технологии на базе фундаментальных научных разработок» в 2011 и 2012 годах.

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

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

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

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

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

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

Изображение в присутствии АП рассматривается как реализация случайного поля, заданного на квадратной дискретной решетке:

fix,у) = !](x,y)s(.x,y) + [1 - T)(x,yj\w(x,y) , Х,у = 1,7Я, где s(x,y) - реализация исходного случайного поля; r¡(x,y)- реализация случайного поля, определяющего расположение локальных областей закрытия с

любыми параметрами периодичности, площади и формы (?ХХ><)е[0,1]); w(jc,_y) -реализация случайного поля, характеризующее значение яркосшых характеристик элементов областей закрытия.

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

Предложен и обоснован новый алгоритм генерации ЛОЗ, позволяющий одновременно моделировать ее форму и прозрачность, а также зависимость между формой и прозрачностью. Предполагается, что генерация производится на бесконечной квадратной сетке, где каждому уже искаженному узлу v=(i,j) ставится в соответствие значение прозрачности Jv е [0,1]. Вводится дополнительная величина IveR, связанная с Iv некоторым однозначным отображением М . Например, в роли lv может выступать концентрация вещества физической среды в узле. Тогда Iv определяется как случайная величина, с условным распределением pIv(x\I), отражающим зависимость значений

прозрачности АП в данной точке от значений уже искаженных пикселей.

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

себя битовую маску, которая СВОИМ центром ...................: LJ.., U.;....;

(черный цвет) помещается на уже искаженные Рис.1

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

плотности pDv(x\D,Iv).

С учетом приведенных соображений, алгоритм генерации ЛОЗ выглядит следующим образом (вход: координаты v = (г, j) порождаю идей точки, условия останова).

1. Определить для искажаемого пикселя значения IV,DV на основе

: ■

3

Л

■

некоторых начальных (х), (х \ Iv).

2. Если вьшолнено условие останова, перейти к шагу 6.

3. Пересчитать вероятности искажения неискаженных пикселей Рdistortion(v I £0 в соответствии с маской расширения С/ .

4. В соответствии с ^/логНоиН-0) выбрать следующий элемент для последующего искажения.

5. Для выбранного элемента (с координатами v' = (i,j)) определить значения /„>,£>„. на основе р1у,(х\/), pD , (х\D,IV.) и перейти к шагу 2.

6. Произвести постобработку значений I (сглаживание, масштабирование, повороты). Вычислить / =М{1) . Преобразовать / в г).

Значения tjv на основе iv можно определить двумя способами. Первый способ - случайно, где вероятность значения 1 равна Д,, 0 - l-/v. Согласно второму способу, помеха просто смешивается с изображением: rjv =IV.

Предложен частный алгоритм, реализующий обобщенную модель на основе следующих параметров: (х | Iv) = р^ (х \ DJV) = pD(x),

р%(х) = pi(x\Iv) = 8(x-\), где S(x) - дельта функция Дирака. Используется маска расширения U4. Вместо явного задания Р£,(х) используется генерация х на основе следующего выражения: х = Х", р(Х) = а ехр(-аХ), где и = 8, а = 2. Далее, для каждого пикселя с координатами v = (i,j), являющегося кандидатом на искажение, определяются величины, вычисляемые по формуле:

v'eC

где С - множество уже искаженных пикселей, Р= 1.5. Рdistortion(v\V) получается путем нормализации данных величин к 1. Пример генерации помех (площадь 2500 пикселей) приведен на рис.2.

В третьей главе описываются результаты исследования потенциальных характеристик восстановления изображений, искаженных аддитивными, импульсными и аппликативными помехами, базирующиеся на применении неравенства Рао-Крамера для оценки НГ. Проводится сравнение получаемых оценок НГ и характеристик линейных и нелинейных (нейросетевых) алгоритмов фильтрации. Изображения рассматриваются как реализации однородных, в частности, гауссовских случайных полей. Моделирование АП проводится на основе алгоритмов, предложенных во второй главе диссертации.

Рис. 2

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

Для определения НГ используется функция правдоподобия изображения, искаженного импульсными и аддитивными помехами:

N

/=1 I V2х<

-ехр

2а2

+а-Ув)/„

где в = (ви...,0н)Т - ненаблюдаемый вектор, развертка реализации исходного изображения; X е {Хх,...,Хы)т - вектор реализации наблюдаемого изображения; р' - вероятность искажения ¿-го элемента импульсным шумом; N - количество пикселей изображения; су2- дисперсия аддитивного шума, /„ - плотность

распределения значений импульсного шума.

Согласно результатам Рао-Крамера, матрица рассеяния при оценке

компонентов вектора в = (вх,...,вп)т удовлетворяет неравенствуД(рс)> ^х(рс),

где ./(рс)- информационная матрица Фишера, причем

-00 ' 3

где

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

(0гх,)2

Ыв>Рс) =

/ ; \2 +<»

ехр

2(7

¿ко

Рс л/2жс

-ехр

(в,-х,У 2а2

-ск,-. к = 1

+ (1 -Ро)/„

О, к Ф /.

Значения диагональных элементов матрицы ./(^вычисляются численно. В качестве примера рассмотрен случай равномерно распределенного импульсного шума: £>(/„) = 1 / (¿-д),а </„ <Ъ, иначе 0. Исследования полученной НГ в зависимости от рс, су показали, что она является достаточно точной при больших значениях <т, однако при малых а дает сильно заниженный результат. Это можно

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

к

где Ак - к-ая комбинация импульсной помехи - вектор из N элементов, г'-ый элемент которого равен 0, если для данной комбинации г'-ый элемент наблюдаемого вектора X поражен импульсной помехой, 1 - иначе; ШАк) -матрица рассеяния, определяющая НГ для комбинации Ак импульсной помехи; р(Ак,рс)- вероятность реализации Ак при заданных вероятностях искажения пикселей рс. Значение суммы оценивается методом статистического моделирования. Учитывая, что для конкретных реализаций элементы Ак принимают значения 0 и 1:

а. 0.8 -

Л,(/>=4)=

I т - *

двт ^ к

—СО ' ]

■ Н,р'=1

о 0.4

й-0.2

— -—•— Граница1 —*— Граница2 —— ИС --»- ЛФ в\ Ш 1

• — <ЛГ 1 г / )

! 1 >

..»Т.-«-- я

дЩ

Проведено экспериментальное

О О]

(рис.

3)

сравнение

„ 0.2 0.4 0.6 0.8 Вероятность поражения пикселя

импульсным шумом

Рис.3

рассчитанной теоретической НГ

первым способом (Граница!), вторым способом (Граница2) с практическими результатами оптимального линейного фильтра (ЛФ) и нейросетевого фильтра (НФ, многослойный персептрон), реализующего с определенным приближением оптимальный нелинейный алгоритм фильтрации. Как видно, результат НФ близок к НГ, а результат ЛФ ему несколько уступает.

Для изображения, искаженного аппликативными помехами и аддитивным

гауссовым белым шумом с дисперсией сг2, функция правдоподобия определяется следующим образом. Пусть Р(А) - априорная вероятность реализации А аппликативной помехи, накрывающей полезное изображение, где А = {х^у^, x¡,yj,t¡ - координаты и индекс конфигурации /' -ой ЛОЗ, - количество ЛОЗ. Тогда

{А}

Р(.Х\9уАк) = 1\ 1=1

р'Мк)

-ехр

г

+ (1 -р!с(Ак)¥'(ъ\Ак)

где Р(Х \ в,Ак) - функция правдоподобия изображения, искаженного вариантом Ак аппликативной помехи; р'с(Ак) определяет вероятность искажения ;-го элемента вектора изображения; /г(х| Ак) - плотность распределения значений искажения для г -го пикселя изображения. Вычислить НГ на основе неравенства Рао-Крамера напрямую на основе данного выражения не представляется возможным. Однако, при использовании предположения о том, что можно точно определить реализацию Ак, функция правдоподобия принимает вид, характерный для функции правдоподобия импульсного и аддитивного шума. Соответственно, оба подхода, разработанные для импульсного шума, являются применимым и для АП. Исходя из этого, матрица рассеяния ЯА при воздействии АП определяется в виде

0.8 ! 0.7

| 0.5 ю

5 0.4 3

0 0.3

| 0.2 о. £ 0.1

1 0

-- —•— Грзница1 —Граница2 —■— НС --*- ЛФ

А

яг

4*'........

Я; Сравнение

0.05 0.1

Вероятность появления в пикселе порождающей точки

Рис. 4

КА = £ Я{рМкШАк).

{Ак}

Значение данной суммы

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

7=1

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

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

В работе рассматриваются два подхода к реализации этапов (2), (3) и (4). Они основаны на представлении изображения I в виде графа G = {V,E}, где вершины V -пиксели изображения, а ребра Е связывают соседние пиксели и задают вероятность наличия между ними границы.

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

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

C(L) = A2>(/V|v) + (1-A) Z тЛ'|v,v')

vev (v.v'Je.E

где X - некоторая константа; lv - метка, присвоенная вершине v; Ф и 1* можно определигь, например, как Ф(/,, | v) = - log p(lv | v,7),

¥(/„,/„. | v,v')=-log p(lvJv. |v,v',7) = -log pQv \vy,I)-[lv*lv,], p(Jv\v,I) - вероятность назначения пикселю метки lv, a p(lvJ=lv<\v,v,I) -вероягность несовпадения меток пикселей.

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

Рис. 5

Каждая пара терминалов Ц,12 разбивает контур изображения на 2 связные части: С\ и С2. В работе предлагается производить нормализацию значения каждого ребра е на ширину сегмента в нем (длину минимального пути от С\ к С2, проходящего через соответствующее ребро Лгефе5(е)). Таким образом, разрезы,

проходящие через меньшее количество ребер, не имеют преимущества перед ^

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

с(р=ле 2Ф(Л|у) .(і-Я)^^1*1'^

^Щ/, еєЕ л'ес18е8(е)

где 1)(г1,г2)- расстояние между терминалами ^,г2 = а Ф(/,,|у) назначает бесконечные веса

меткам, соответствующим

терминалам, и регуляризирующие веса остальным пикселям сегмента. Сравнения

эффективности предложенного подхода с известными

алгоритмами суперпиксельной сегментации продемонстрировали его высокую эффективность. Пример суперпиксельной

сегментации, произведенной алгоритмом, приведен на рис. 6. Для выделения АП на основе Рис. 7

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

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

Разработанные в работе подходы реализованы в виде программного комплекса в средах MATLAB и С++.

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

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

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

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

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

Статьи в изданиях, рекомендованных в ВАК

1. Калинин П.В. Моделирование аппликативных искажений с различной степенью прозрачности и случайной формой / П.В. Калинин, A.A. Сирота // Цифровая обработка сигналов. - 2013. - №1. - С. 28-33.

2. Калинин П. В. Статистические, нейросетевые и комбинированные алгоритмы фильтрации аппликативных помех на изображениях / П. В. Калинин, А. А. Сирота / Автометрия. - 2012. - №6. - С. 18-28.

3. Сирота A.A. Анализ потенциальных и реальных характеристик оценивания случайных полей (изображений) в условиях аддитивных и импульсных помех / A.A. Сирота, П.В. Калинин // Вестник Воронежского государственного университета. Серия: «Системный анализ и информационные технологии». -2011.-№1.-С. 41-50.

Статьи в сборниках научных трудов и материалах конференций

4. Калинин П.В. Модели и алгоритмы суперпиксельной сегментации изображений в интересах выделения аппликативных помех / П.В. Калинин, A.A. Сирота // Материалы XIV международной научно-технической конференции «Кибернетика и высокие технологии 21 века». -2013. -С. 190-199.

5. Калинин П.В. Комбинированный алгоритм фильтрации аппликативных

помех на изображениях / П.В. Калинин, A.A. Сирота // Материалы ХШ международной научно-технической конференции «Кибернетика и высокие технологии 21 века». -2012. - С. 128-142.

6. Калинин П.В. Анализ потенциальных и реальных характеристик оценивания случайных полей (изображений) в условиях аддитивных и аппликативных помех / П.В. Калинин, A.A. Сирота // Материалы ХП международной научно-технической конференции «Кибернетика и высокие технологии 21 века». - 2011. С. 115-126.

7. Калинин П.В. Комбинированный алгоритм устранения аппликативных закрытий на изображениях / П.В. Калинин, A.A. Сирота // XI Международная конференция "Информатика: проблемы, методология, технологии". - 2012. - С. 164-166.

8. Калинин П.В. Анализ потенциальных и реальных характеристик оценивания случайных полей (изображений) в условиях аддитивных и аппликативных помех / П.В. Калинин, A.A. Сирота // XI Международная конференция "Информатика: проблемы, методология, технологии". - 2011. - Т. 1. - С. 339-344.

9. Калинин П.В. Алгоритмы фильтрации импульсного шума на изображениях / П.В. Калинин, A.A. Сирота // X Международная конференция "Информатика: проблемы, методология, технологии". - 2010. - Т. 1. - С. 288-292.

10. Калинин П.В. Разработка алгоритмов и программных средств улучшения качества изображений с использованием нейросетевых технологий / П.В. Калинин, A.A. Сирота // Инновационные технологии на базе фундаментальных научных разработок: сб. тр. регион, науч.-практ. конф. студентов, аспирантов и молодых ученых. - 2012. - С. 52-54.

11. Калинин П.В. Разработка алгоритмов и программных средств улучшения качества изображений с использованием нейросетевых технологий обработки информации / П.В. Калинин, A.A. Сирота // Инновационные технологии на базе фундаментальных научных разработок: сб. тр. регион, науч.-практ. конф. студентов, аспирантов и молодых ученых. - 2011. - С. 48-49.

Подписано в печать 14.11.13. Формат 60x84 1/ц. Усл. печ. л. 0,93. Тираж 100 экз. Заказ 1198.

Отпечатано с готового оригинал-макета в типографии Издательско-полиграфического центра Воронежского государственного университета. 394000, Воронеж, ул. Пушкинская, 3

Воронежский государственный университет

Калинин Павел Владимирович

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

Специальность 05.13.17 - «Теоретические основы информатики»

Диссертация на соискание ученой степени кандидата физико-математических наук

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

04201453045

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

доктор технических наук, профессор А. А. Сирота

Воронеж, 2013

Содержание

Введение.............................................................................................4

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

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

1.2. Алгоритмы обнаружения объектов и их границ на изображениях..........27

1.3. Алгоритмы закраски отсутствующих фрагментов изображений............31

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

2. Моделирование аппликативных помех...................................................43

2.1. Обобщенная модель аппликативных помех......................................43

2.2. Алгоритмы моделирования аппликативных помех для различных частных случаев.........................................................................................52

2.3. Анализ предлагаемой модели и реализующих ее алгоритмов................58

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

3. Оценка потенциальных и реальных характеристик восстановления изображений в условиях импульсных и аппликативных помех......................................................66

3.1. Исходные понятия и соотношения для определения потенциальных характеристик восстановления случайных полей в условиях импульсных и аппликативных помех......................................................................66

3.2. Анализ потенциальных и реальных характеристик восстановления

случайных полей, искаженных импульсными помехами...........................70

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

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

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

3.3. Анализ потенциальных и реальных характеристик восстановления

случайных полей, искаженных аппликативными помехами.......................83

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

4. Предлагаемые подходы и алгоритмы восстановления реальных изображениях в условиях аппликативных помех..................................................................................91

4.1 Общая схема обработки изображения в рамках комбинированного подхода........................................................................................91

4.2. Нейросетевой детектор границ аппликативных помех на изображениях..94

4.3. Алгоритм выделения аппликативных помех на основе поиска кратчайшего пути вдоль контура помехи..............................................................99

4.4. Алгоритм выделения аппликативных помех на основе процедуры

суперпиксельной сегментации изображений........................................115

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

4.4.2. Выделение аппликативных помех на основе иерархии суперпикселей .................................................................................................133

Заключение...........................................

Список использованных источников............

Список сокращений и условных обозначений

.150 160

Введение

Непрерывное развитие технологий в области получения и анализа изображений и значительное повышение вычислительного потенциала современных компьютеров обуславливают появление новых методов и алгоритмов машинного обучения [36], автоматической обработки цифровых изображений и видео [6,18]. Задачи обработки изображений возникают в системах видеонаблюдения и регистрации изображений, технической и медицинской диагностики, цифровой фотографии, системах дистанционного мониторинга [6,18,49]. Цифровые изображения могут иметь самые различные источники. Это могут быть системы, устанавливаемые на летательных аппаратах с целью выполнения задач навигации, мониторинга, визуального контроля объектов, спутниковые системы дистанционного зондирования и мониторинга, медицинское оборудование, различного рода сканеры, применяющиеся как в промышленности, так и в домашних условиях, а также видеокамеры, фотоаппараты, мобильные телефоны. Несмотря на множество возможных источников происхождения изображений, перед разработчиками систем встают одинаковые проблемы. Основными задачами, связанными с обработкой изображений в данных системах, являются задачи улучшения их качества и тематического анализа [6,18,96]. К ним относятся, например, задачи сегментации изображений на независимые составляющие компоненты, представляющие различные объекты сцены; задачи улучшения качества изображений, например, повышение контрастности, устранение шумов и искажений; задачи объединения множества изображений одной и той же сцены в одно панорамное изображение; различные задачи получения ЗБ реконструкций как на основе видеоряда, так и на основе множества снимков одного и того же объекта под разными углами; задачи классификации изображений и распознавания объектов [96].

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

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

Как правило, устранение негативных последствий наличия помех достигается путем выполнения фильтрации [2,6,18,19,42,45,51,89]. При осуществлении данной процедуры, интенсивность искаженных пикселей изображения заменяется некоторым значением яркости, наилучшим образом аппроксимирующим реальное значение пикселя. Стандартным подходом к фильтрации помех является проведение локальной обработки: для каждого искаженного пикселя аппроксимирующее значение ищется на основе небольшого количества окружающих его «соседних» пикселей, входящих в так называемое «скользящее окно» [18], зачастую фиксированной, обычно квадратной, формы, размер которого мал по сравнению с размером всего изображения. При реализации данного подхода пиксели, находящиеся на некотором удалении от обрабатываемого пикселя считаются нерелевантными, и их значения игнорируются. Это легко обосновывается тем, что функции изображений, с которыми приходится иметь дело на практике, обычно более гладкие по сравнению с функцией помех, а значит, функция изображения меняется медленнее, чем функция помехи, что позволяет при оценке сигнала принимать во внимание лишь множество соседних точек сигнала, оставляя без внимания остальные.

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

«фильтрация» и термин «восстановление» используются взаимозаменяемо. Обычно в качестве целевой функции выбирается среднеквадратичная ошибка, определяемая как средний квадрат разности между неискаженным и аппроксимированным значением пикселя изображения [6,18]. В такой постановке оптимальной фильтрацией будет считаться фильтрация, которая минимизирует заданную квадратичную функцию потерь. Так, при фильтрации аддитивных помех, при определенных предположениях о функции распределения изображения существуют подходы, позволяющие производить оптимальную фильтрацию при использовании линейных фильтров [6,18]. Тем не менее, часто даже в столь простом случае не всегда возможно получить оптимальный фильтр с полиномиальным временем работы, и задача может свестись к перебору возможных вариантов искажений и экспоненциальному времени поиска оптимального решающего правила.

Более того, понятие оптимальной фильтрации жестко зависит от предполагаемого вида функции распределения изображения. Данный факт снижает значимость оптимальной фильтрации для реальных изображений ввиду того, что не существует точной статистической модели реальных изображений [65]. Также, сложности, связанные с выполнением вероятностного вывода в статистических моделях [69], не позволяют надеяться на существование быстрого общего алгоритма оптимальной фильтрации. Поэтому оптимальная фильтрация не всегда реализуема на практике и возможно применение приближенных алгоритмов, зачастую позволяющих добиться достаточно качественных результатов за приемлемое время.

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

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

Важным вопросом, тесно связанным с задачей устранения помех является построение статистической модели изображения. Развитие данной области неразрывно связанно с областью анализа зрительной системы человека [65]. Тем не менее, ввиду сложностей, встающих перед исследователями, анализ зрительной системы преимущественно ограничивается только несколькими зонами - до первичной зрительной коры (VI) включительно, преимущественно выполняющими первичную обработку данных (такую как подавление шума и

извлечение ребер) [65]. Простейший подход к моделированию распределения изображений состоит в использовании нормального распределения. Для моделирования изображений на основе данного подхода могут применяться как методы генерации случайного поля на основе заданной матрицы ковариации [1], так и применение метода анализа главных компонент (РСА) для выявления характерных векторов в пространстве изображений, вносящих наибольший вклад в дисперсию [65]. Как показано [65], так как изображения обладают свойством инвариантности к сдвигу, РСА эквивалентно разложению изображения в ряд синусоид. Существует тесная связь между применением гауссовой модели и анализом спектральной мощности изображений [65]. Гауссовская модель изображения не всегда позволяет получить адекватное описание изображений, в связи с чем зачастую используются более продвинутые методы. Основным подходом к построению моделей изображений является использование статистических моделей в рамках байесовского подхода [65, 69]. Использование байесовского подхода позволяет включить в статистическую модель априорное распределение, содержащее некоторую информацию о структуре моделируемого изображения. Принципиальным фактом, часто использующимся в данных моделях является выраженная негауссовость реальных изображений [65]. Базовым компонентом извлечения необходимых параметров модели часто является метод анализа независимых компонент (independent components analysis -ICA) [64], основанный на идее поиска разреженного представления изображений.

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

нелинейные фильтры, синтезированные на эвристическое основе, например, медианные фильтры и их многочисленные модификации [2,19,42,45,51,89].

Аппликативные помехи (АП) являются наиболее сложными с точки зрения их фильтрации. Они связаны с появлением различного рода неоднородностей, локальных областей аномальных значений, областей закрытия и пораженных участков на анализируемых изображениях. В простейших случаях для восстановления изображений, описываемых как реализации случайных полей, применяются имеющие простую интерпретацию методы и алгоритмы линейной фильтрации [6,18]. Однако использование линейной фильтрации во многих приложениях не позволяет добиться приемлемых результатов. Оптимальная нелинейная фильтрация в условиях АП сопряжена с существенным повышением сложности выполняемой обработки и обычно сопровождается «катастрофическим» увеличением используемых вычислительных ресурсов. Определенные возможности в плане реализации алгоритмов нелинейной фильтрации с приемлемым быстродействием предоставляют нейросетевые технологии обработки информации [24,53].

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

Исследования вопросов обработки изображений (обнаружения объектов, фильтрации) в условиях аппликативных помех проводилась в ряде работ В.А. Понькина, В.А. Сойфера, А.П. Трифонова, A.A. Сироты, Е.А. Самойлина, Р.В. Куцова, В.Г. Попова, M. Н. Лантюхова, И.В. Апалькова, А.Л. Приорова, В.В. Хрящева, W. Pratt, R. Wood, R. Gonzalez, S. Gould, P. Felzenszwalb, D. Huttenlocher, X. Ren, J. Malik, J. Shi, A. Moore, I. Jermyn, H. Ishikawa, M.-Y. Liu, R. Achanta, O. Veksler , Y. Boykov и др., однако комплексного эффективного решения задачи автоматического восстановления реальных изображений, искаженных аппликативными помехами предложено не было.

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

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