Содержание к диссертации
Введение
1. Проблема обработки изображений с сохранением локальных особенностей и основные задачи исследования 15
1.1. Рассматриваемый класс задач обработки изображений 15
1.2. Обзор и анализ существенных методов обработки изображений с сохранением локальных особенностей 18
1.3. Общая структура оператора оценивания модели массива упорядоченных данных на основе двухкомпонентного марковского случайного поля
1.3.1. Двухкомпонентное случайное поле на множестве элементов массива данных и минимизация среднего риска 24
1.3.2. Гиббсовская модель изображения 28
1.3.3. Парно-сепарабельная целевая функция для обработки изображений 32
1.4. Обзор методов минимизации парно-сепарабельной целевой функции для
оценивания марковского случайного поля 33
1.4.1. Существующие методы минимизации парно-сепарабельной целевой функции для оценивания марковского случайного поля 33
1.4.2. Процедура динамического программирования для оптимизации парно-сепарабельных целевых функций с древовидной аппроксимацией решетчатого графа смежности переменных 1.5. Обзор различных видов парных потенциалов на кликах 42
1.6. Основные цели и задачи исследования 45
2. Мультиквадратичная процедура динамического программирования для массивов упорядоченных данных 47
2.1. Новый способ задания парных потенциалов на кликах в виде функции двух соседних переменных 47
2.2. Простой случай для обработки массивов упорядоченных данных 48
2.3. Мультиквадратичная процедура динамического программирования для обработки массивов упорядоченных данных с сохранением локальных особенностей 51
2.4. Алгоритм отбора квадратичных функций 55
2.5. Алгоритмы аппроксимации набора квадратичных функций в представлении функций Беллмана 61
2.6. Выводы по главе 2 70
3. Процедуры обработки изображения на основе мультиквадратичного динамического программирования 72
3.1. Алгоритм обработки изображений на основе мультиквадратичной процедуры динамического программирования 72
3.2. Параметрические процедуры динамического программирования для обработки изображений с аппроксимацией набора квадратичных функций в представлении функций Беллмана 83
3.3. Выводы по главе 3 84
4. Экспериментальные исследования разработанных параметрических процедур 85
4.1. Постановка экспериментальных исследований и критерии оценки качества результатов 85
4.2. Описание программы устранения шума с сохранением локальных особенностей на изображении на основе мультиквадратичного динамического программирования 88
4.3. Экспериментальные исследования свойства разработанных процедур в задаче шумоподавления изображения с сохранением границ 91
4.4. Экспериментальные исследования предложенного вида парно-потенциальных функций в задаче в задаче шумоподавления изображения с сохранением границ 98
4.5. Экспериментальные сравнительные исследования свойства между разработанными процедурам и текущими методами для шумоподавления изображения с сохранением границ 107
4.6. Экспериментальные исследования свойства разработанных процедур минимизации целевой функции в задаче шумоподавления изображения с сохранением границ 113
4.7. Выводы по главе 4 117
Заключение 119
Список литературы
- Общая структура оператора оценивания модели массива упорядоченных данных на основе двухкомпонентного марковского случайного поля
- Мультиквадратичная процедура динамического программирования для обработки массивов упорядоченных данных с сохранением локальных особенностей
- Параметрические процедуры динамического программирования для обработки изображений с аппроксимацией набора квадратичных функций в представлении функций Беллмана
- Экспериментальные исследования свойства разработанных процедур в задаче шумоподавления изображения с сохранением границ
Общая структура оператора оценивания модели массива упорядоченных данных на основе двухкомпонентного марковского случайного поля
Целью сглаживания изображения с сохранением границ является эффективное удаление шума без размытия границ взаимосвязанных областей изображения. Важность данной проблемы для построения систем компьютерного зрения привела к появлению большого количества работ и исследований, в которых можно выделить следующие подходы к обработке изображений с сохранением границ: анизотропная диффузия (anisotropic Diffusion) [2], билатеральная фильтрация (bilateral filtering) [3], фильтрация на основе вейвлет–преобразования (Wavelet–Transform) [35], байесовская фильтрация (Bayes Filtering) с использованием вероятностных графовых моделей [13], медианная фильтрация [36] , фильтр Винера [37], фильтрация на основе полной вариации (total variation) [38], фильтр нелокального усреднения (non - local means, NLM) [39].
Анизотропная диффузия (anisotropic Diffusion), предложенная Пероной и Маликом [2], является одним из самых распространенных методов восстановления изображений с сохранением границ. Метод основан на теории дифференциальных уравнений в частных производных, описывающих физический процесс диффузии, служащий моделью преобразования изображения. Анизотропная диффузия создает набор параметризованных изображений. В этом наборе, каждым результирующим изображением является комбинация исходного изображения и фильтра, зависящий от локальных особенностей изображения. Диффузионный коэффициент регулирует уровень сглаживания. Каждое результирующее изображение вычислено на основе применения обобщенного уравнения диффузии предыдущего изображения в наборе параметризованных изображений. Но в анизотропной диффузии [2], диффузионные параметры не могут быть изменены непосредственно в диффузионном процессе и время остановки может быть неопределенно. Это приводит к размытию границ и наличию избыточного количество шума после обработки. Кроме этого, классический алгоритм на основе анизотропной диффузии [2] плохо подходит для сильно зашумленных изображений больного размера при использовании точечной оценки градиента [6]. В настоящее время существуют модификации анизотропной диффузии, предложенные в работах [40-45], которые позволяют хорошо сохранить границы и мелкие детали изображения в диффузионном процессе.
Билатеральный фильтр: билатеральный фильтр, предложен Томаси и Мандучи [3] для восстановления изображения. Он основан на идее гауссовской фильтрации, но использует два фильтрующих ядра: пространственное ядро для учета пространственной зависимости и ядро интенсивности для учета различий в интенсивности между центральным пикселем и его соседями. В билатеральном фильтре, значение каждого пикселя выходного фильтра вычислено средними значениями смежных пикселей входного фильтра. Билатеральный фильтр может быть рассмотрен как неитеративный и нелинейный фильтр с сохранением границ [46]. Кроме этого, билатеральный фильтр может быть рассмотрен как частные случаи анизотропной диффузии [6]. Существуют некоторые модификации билатерального фильтра в литературе [47, 48], позволявшие уменьшения времени вычисления. Тем не менее, билатеральная фильтрация не лишена рядя недостатков, присущим фильтрам с конечной импульсной характеристикой, выражающихся в появлении перепадов яркости и ложных контуров около резких границ на изображении с высоким уровнем шума.
Полная вариация (Total variation): Метод, основанный на полной вариации, первоначально был предложен Рудином, Ошером и Фатеми в работе [38], для восстановления изображения при наличии аддитивного белого гауссовского шума. Метод основан на поиске оценки исходного незашумленного изображения, обладающей наименьшей полной вариацией среди всех изображений, удовлетворяющих принятым ограничениям на дисперсию шума. Задача сводится к поиску оптимальных значений критерия, содержащего L1 норму градиента искомого незашумленного изображения. Существует тесная взаимосвязь между методами на основе максимизации апостериорной вероятности и методами на основе полной вариации [49], использующими критерии сходного вида.
Общая трудность вариационного похода для обработки изображений является том, что целевая функция является многоэкстремальной и недифференцируемой. Численные методы, применяющиеся для решения вариационной задачи часто находят лишь локальный минимум, что приводит к неточностям в восстановлении деталей обработанного изображения [50]. Кроме этого, модель полной вариации страдает от лестничного эффекта (staircase effect) [51], а именно, трансформации гладких областей в кусочно-постоянные, что может привести к образованию ложных контуров на изображения. Для решения этой проблемы в работах [51-53], предложены различные модификации метода полной вариации.
Фильтр Винера (Wiener filter): Фильтр Винера [37] является оптимальным фильтром, параметры которого рассчитываются исходя из минимума математического ожидания среднеквадратичной ошибки между «истинным» незашумленным изображением и его оценкой. Вероятностные свойства изображения и шума предполагаются известными. Одним из важных предположений при синтезе фильтра является предположение о стационарности случайного поля. Вследствие этого фильтр Винера не может обеспечить оптимальные оценки на краях изображения, а также при изменении локальных статистических свойств изображения. Поэтому данный фильтр показывает худшие результаты восстановления зашумленных изображений с сохранением локальных особенностей, чем другие современные методы обработки. Модификации фильтра Винера могут быть найдены в работах [54, 55].
Мультиквадратичная процедура динамического программирования для обработки массивов упорядоченных данных с сохранением локальных особенностей
Применение алгоритма 2 для аппроксимации набора квадратичных функций позволяет сохранить только одну квадратичную функцию с наименьшим значением в точке минимума среди всех квадратичных функций в представлении функции Беллмана, что может привести к потере точности, если функция Беллмана имеет несколько точек минимума с близкими значениями.
Для сохранения нескольких точек минимума предлагается разделить квадратичные функции на группы близких друг другу функций. Количество групп определяется количеством сохраняемых минимумов. Для разделения функций на группы воспользуемся одним из самых распространенных алгоритмов кластеризации - методом к-средних [100], содержащим преимущества быстроты и простоты реализации.
Для реализации данного метода необходимо либо определить подходящий набор признаков для представления квадратичной функции, либо определить функцию расстояния между ними.
В данной работе используется беспризнаковый вариант метода к-средних [101]. Измерение расстояния между квадратичными функциями может быть выполнено при помощи приведенного ниже способа.
Способ определения расстояния между квадратичными функциями На произвольном шаге мультиквадратичной процедуры динамического программирования, частичная функция функции Беллмана (также маргинальная функция) имеет представление: F(x) = min(F(1) ( JC), ..., F(N) (JC)), F(l) (JC) = q(l) (x - x(l) f + d(l), / 1,..., N. Можно заметить, что согласно виду критерия (1.21), оцененное значение скрытого случайного поля не может превышать максимальное значение наблюдения 6 = max(Y) и быть меньше минимального значения наблюдения tf = min(Y). Поэтому, расстояние между квадратичными функциями можно вычислить как сумму квадратов разности по ограниченной значениями [a, b\ области определения:
Для выполнения алгоритма аппроксимации набора квадратичных функций на основе кластеризации методом к-средних, воспользуемся алгоритмом кластеризации множества по расстояниям (2.20, 2.21) его элементов [101] и алгоритмом 2. Большое влияние на скорость сходимости и точность алгоритма к-средних оказывает выбор начального положения центров кластеров. В связи с особенностями процедуры, положение и значение точки глобального минимума функции Беллмана должно быть сохранено. Поэтому оно выбирается в качестве центра одного из кластеров. Центры остальных кластеров выбираются в соответствии с точками минимума составляющих квадратичных функций F( ) , N i = (H -1)—, с округлением / до целого числа. Алгоритм аппроксимации набора квадратичных функций на основе кластеризации методом к-средних имеет следующий вид. Алгоритм 3: Аппроксимация набора квадратичных функций на основе кластеризации методом к-средних
Входные данные: H N, F(x) = min(F(1)(x),...,Fw(x)) Выходные данные: F(x) = min(F(1)(x),...,F(//)(x)) 1. Инициализировать кластерные центры: gk), к = 1,.. .,Н . 2. Определить расстояния между объектами F(1) и кластерными центрами к) с выражением (2.21). Распределить объекты в их ближайший центр. Cluster, = {F(l):D(F(l\ k)) D(F(l\ l))}, k = l,...,H, 1 = 1,...,H, k l, i = l,...,N; Nk - число объектов (квадратичных функций) в Cluster,. 3. Пересчитать новые кластерные центры , к = \,...,Н по расстояниям d{F{l\ е1) i = l-..N, используя алгоритм кластеризации множества по расстояниям [101]: 1 Nk і Nk Nk 1ук р=\ ZIyk р=\ р=\ 4. Стоп, если ЙЛ) = Й2, А: = 1,.. .,# . Иначе повторить шаги (2-3). 5. По каждой из Н групп кластеров, полученных в результате работы кластеризации методом к-средних, используем алгоритм 2 для реализации аппроксимации набора квадратичных функций каждой группы одной квадратичной функцией: Cluster, =mm{F{l\x\...,F{Nk\x)) qk{x-хк)2 + d[, k = l,...,H, F(x) = min(Cluster ... ,Clusterk). Конец алгоритма 3
Нетрудно убедиться, что результат аппроксимации алгоритма 2 совпадает с результатом алгоритма 3 при Н=\. Предварительные экспериментальные исследования показывают, что для подавляющего большинства массивов исходных данных числа групп как правило, достаточно полностью отражать каждую функцию Беллмана (2.12, 2.13).
На рисунках 2.6, 2.7 представлены примеры результатов аппроксимации набора квадратичных функции и их детальных результатов сохранения точек минимума предлагаемыми методами {алгоритм 2, алгоритм 3) для маргинальных функций Беллмана Jt(xt), содержащих 121 (рисунок 2.6.а, 2.7.а), 86 (рисунок 2.6.6, 2.7.6), 58 (рисунок 2.6. в, 2.1.ъ ) и 319 (рисунок 2.6. г, 2.1 .т) квадратичных функций. На рисунке 2.8 представлены примеры результатов аппроксимации набора квадратичных функции методом кластеризации к-средних (алгоритм 3) для частичных функций Беллмана на прямом ходе по вертикали Fvt(xt), содержащих 198 (рисунок 2.8. а), 394 (рисунок 2.8. б), 593 (рисунок 2.8. в) и 1041 (рисунок 2.8. г) квадратичных функций. Для аппроксимации набора квадратичных функций в представлении частичных функций Беллмана на прямом ходе по вертикали Fvt (xt) методом кластеризации к-средних, константа в составе набора квадратичных
Параметрические процедуры динамического программирования для обработки изображений с аппроксимацией набора квадратичных функций в представлении функций Беллмана
На основе алгоритма 4 и алгоритмов (алгоритмы 2-3) аппроксимации набора квадратичных функций в представлении функций Беллмана, создаются следующие параметрические процедуры динамического программирования для обработки изображений:
Первая процедура основана на непосредственном применении алгоритма 4 за исключением того, что после шага 2 используется алгоритм 3 для аппроксимации набора квадратичных функций в представлении маргинальных функций Беллмана J(xt t ) на основе кластеризации методом к-средних.
После обработки изображения по горизонтали каждая маргинальная функция Беллмана содержит не более чем Н квадратичных функций, где Н - заданное количество групп для алгоритма к-средних.
Вторая процедура состоит из тех же шагов алгоритма 4 за исключением того, что после шага 2 используется алгоритм 2 для аппроксимации набора квадратичных функций в представлении маргинальных функций Беллмана J(xt t ) одной квадратичной функцией. После обработки изображения по горизонтали каждая маргинальная функция Беллмана содержит одну квадратичную функцию. Третья параметрическая процедура Третья процедура состоит из тех же шагов алгоритма 4 за исключением того, что после шага 3 используется алгоритм 3 для аппроксимации набора квадратичных функций в представлении частичных функций Беллмана Fvt(jct) меньшим числом квадратичных функций на каждом шаге прямого хода процедуры обработки по вертикали. При этом функция константы в составе набора квадратичных функций исключается из процесса кластеризации методом к-средних и сохраняется в результате обработки.
После обработки изображения на прямом ходе по вертикали каждая вертикальная частичная функция Беллмана Fvt(jct) содержит не более (Я +1) квадратичных функций (Н - заданное количество групп для алгоритма к-средних).
Вычислительная сложность мультиквадратичных процедур динамического программирования для обработки изображения является линейной относительно количества элементов изображений.
Предложен алгоритм обработки изображения на основе мультиквадратичного динамического программирования. Приведена реализация алгоритма обработки изображения на основе мультиквадратичного динамического программирования.
Созданы три параметрические процедуры динамического программирования с различными способами уменьшения количества квадратичных функций в представлении функции Беллмана для обработки изображений с сохранением локальных особенностей. Здесь используем одинаковые функции связи в горизонтальных направлениях \ и t2 в силу их одинакового физического смысла. В экспериментальных исследованиях рассматриваем применение разработанных процедур в прикладных задачах, частным случаем является задача шумоподавления изображений с сохранением локальных особенностей. Проводились тестирования на стандартном множестве изображений (рисунок 4.1) с различными размерами в градациях серого цвета с 8 битами на пиксель. Проводились тестирования при различных уровнях аддитивного белого гауссовского со стандартным отклонением ( т = 3...30). В этом случае, задача восстановления скрытых значений функции X = (jct) по данным наблюдения Y = (yt) поставлена формально следующем: У t =xt+t, (41) где уєШ, С- аддитивный белый гауссовский шум c средним значением 0 и дисперсией о-2, t = (t1,t2), t1 =1,...,N1, t2 =1,...,N2, N1, N2 - размеры изображения. Для оценки качества результатов шумоподавления, использованы среднее значения индекса структурного сходства (MSSIM-Mean Structure Similarity Index) [102], пиковое отношение сигнала к шуму (PSNR-peak to signal ratio), отношение сигнал/шум (SNR–signalo-noise ratio), средняя квадратическая ошибка (mean-square error–MSE), корень средней квадратической ошибки (root mean square error, RMSE) [103]. MSE определяется как: где P(i,j), QQ,j) значения пикселов соответственно исходного изображения размера МгхМ2 и его реконструированного или шумного изображения соответственно; jup, juQ -средние значения изображений; сгР,сГд- стандартные отклонения изображений; crpQ- ковариация изображений P,Q; q= 6.5025, с2= 58.5225 [102]. PSNR (дБ) определяется как:
В экспериментах определялись параметры сглаживания u=uv=uh и А = Ah = Av. Значения и и А определяются в зависимости конкретного значения стандартного отклонения а белого шума. При L = 3 выбираются фиксированные параметры Л = 0.2, d = 0.5А2 и при L = 4 выбираются фиксированные параметры Л = 0.2, dl = 0.5А2, Л2 = 0.4, d2 = 0.25А2.
На рисунке 4.1 представлены изображения различного размера, найденные в источниках [104-107], используемые для экспериментальных исследований: a) coco (256x256); б) man (300x300), в) boat (256х256),г) poulina (300x300) , д) lamp (256х256),е) cameraman (128x128), ж) elaine (200x200), з) lena (150x150).
Экспериментальные исследования свойства разработанных процедур в задаче шумоподавления изображения с сохранением границ
В этом разделе представляют собой сравнительные исследования способа шумоподавления изображений с сохранением границ между предлагаемым видом и существенными видами парно-потенциальных функции (таблица 1.1) в рамках байесовского подхода. Для экспериментальных исследований использованы существенные виды парно-потенциальных функций: функция Хубера (Huber function, HubF) [96], полу-хуберовская функция (semi-Huber, SemHubF) [97] , обобщенная гауссовская функция (generalized gaussian function, GGF) [75], функция Блейка-Зиссермана (Blake-Zisserman, BZF) [30], функция Бесага (Besag function, BesF) [18], функция Грина (Green Function, GreF) [98].
Функция Блейка-Зиссермана является частным случаем предлагаемого вида в случае L = 2 (раздел 2.1). Функция Бешага является частным случаем обобщенной гауссовской функции при p = 1. На рисунке 4.9 представлены графики видов парно-потенциальных функций для экспериментальных исследований при коэффициенте сглаживания u = 1.
Экспериментальные параметры видов парно-потенциальных функций выбраны: Av = Ah для функции HubF, Д = Д = 1 для функции SemHubF, /7 = 1.2 для функции GGF. Значения параметров u = uh=uv каждого вида парно-потенциальной функции выбраны для того, что результат измерения качества имеет максимальное значение. Для случаев видов функций связи (HubF, SeMHubF, GGF, BesF, GreenF), использована дискретная процедура динамического программирования, предложенной в работе [10], на каждом шаге у которой функции Беллмана выражаются конечным набором дискретных значений.
На рисунках 4.10 – 4.13 представлены сравнительные экспериментальные результаты между предлагаемым видом и существенными видами парно-потенциальных функций для шумоподавления изображения с сохранением локальных особенностей. В таблице 4.4 представлены сравнительные результаты измерения качества шумоподавления между предлагаемым видом и существенными видами парно потенциальных функций.
Результаты третьей процедуры Рисунок. 4.11 - Квадратичная разница между результатами шумоподавления и исходным (чистым) изображением (рисунок 4.10) при использовании парно-потенциальных функций различного вида
Квадратичная разница между результатами шумоподавления и исходным (чистым) изображением (рисунок. 4.12) при использовании парно-потенциальных функций разного вида
Экспериментальные сравнительные исследования свойства между разработанными процедурам и текущими методами для шумоподавления изображения с сохранением границ
В экспериментах сравнивались методы для шумоподавления с сохранением локальных особенностей, такие как: фильтр Винера (wiener filtering, WF) [37], нелинейная полная вариация (non - linear total variation, TV) [38], анизотропная диффузия (anisotropic diffusion filter, ADF) [2], быстрый билатеральный фильтр (fast bilateral filter, FBF) [47], байесовский метод наименьших квадратов с гауссовской смесью различных масштабов (the Bayesian least squares with Gaussians Scale Mixture, BLS-GSM) [5], фильтр нелокального усреднения (non-local means, NLM) [39] и разработанные параметрические процедуры. На рисунках. 4.14 - 4.15 представлены результаты сравнительных методов для шумоподавления изображений с сохранением локальных особенностей. В таблице 4.5 представлены сравнительные результаты измерения качества шумоподавления между разработанными процедурами и сравнительными методам.
Экспериментальные результаты показывают, что: Разработанные параметрические процедуры позволяют получить результаты шумоподавления изображения, не уступающие, а в некоторых случаях превосходящие результаты обработки изображений при помощи современных методов, известных в литературе
Методом NLM позволяет получить самое высокое качество шумоподавления изображений с сохранением локальных особенностей. Тем не менее, в некоторых случаях, результаты шумоподавления разработанных параметрических процедур не хуже, чем результаты метода NLM. Кроме того, разработанные параметрические процедуры имеют меньшее время работы по сравнению с алгоритмом NLM.
Экспериментальные исследования свойства разработанных процедур минимизации целевой функции в задаче шумоподавления изображения с сохранением границ Приведено сравнительное исследование минимизации парно-сепарабельной целевой функции разработанных мультиквадратичных процедур динамического программирования и существенных методов1 ICM, BPS, TRWS, Graphcut Expansion и Swap [24] в задаче восстановления изображений при присутствии нормального белого шума при виде функции Блэйка и Зиссермана (L = 2).
На рисунках 4.17, 4.18 представлены исходные изображения, зашумлённые изображения, результаты восстановления изображения сравнительных методов и их измерения качества PSNR. На рисунках 4.19, 4.20 представлены графики результатов минимизации значения целевой функции сравнительных методов для шумоподавления изображений с сохранением локальных особенностей (по горизонтали изображены значения времени обработки в секундах, по вертикали -значение целевой функции в процентах от значения глобального минимума).