Сглаживание изображений: сравнительный анализ методов фильтрации, основанных на парзеновском оценивании

УДК 004.932

Чочиа П.А.

Институт проблем передачи информации РАН, г. Москва, Россия

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

АННОТАЦИЯ

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

КЛЮЧЕВЫЕ СЛОВА

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

Chochia P.A.

Institute for Information Transmission Problems RAS, Moscow, Russia

IMAGE SMOOTSING: COMPARATIVE ANALYSIS OF FILTERING METHODS, BASED ON PARSEN ESTIMATION

ABSTRACT

Image smoothing methods, based on Parzen estimation window are compared. The proximity of sigma filter and bilateral filter, and also the efficiency of image decomposition algorithm are demonstrated.

KEYWORDS

Image smoothing, Parzen estimation, sigma filter, bilateral filter, decomposition algorithm. Введение

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

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

Эффективным способом решения задачи нахождения сглаженного значения в точке, в ситуации смеси нескольких распределений, является применение метода парзеновских окон [1,2]. На основе данного подхода, используя анализ по локальному фрагменту, разработано несколько известных алгоритмов сглаживания изображений, сохраняющих контурные перепады: а) сигма-фильтр Ли [4]; в) билатеральный фильтр [7]; б) алгоритм декомпозиции [5,6,9]. Парзеновские методы оценивания продолжают привлекать внимание как применительно к сглаживанию, так и в других задачах обработки изображений [10,11]. Тем не менее, сравнительный анализ разработанных методов до настоящего времени проведен не был.

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

2. Модель фрагмента

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

[12], значительную долю площади изображения занимают протяженные области, содержащие от 102 до 104 и более элементов каждая. Очевидно, что произвольно взятый фрагмент может как попадать целиком внутрь некоторой большой области, так и покрывать две или более независимых областей. Один из таких вариантов показан на Рис. 1(а). Фрагмент находится на границе двух протяженных областей (и2 и и3) и целиком захватывает третью область (и1).

Рис. 1. Фрагмент, покрывающий три области,

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

Согласно модели фрагмента [5,8] изображение представимо в виде суммы трех компонент: гладкой sij, текстурной ^ и шумовой %//. При этом гладкие составляющие частей R областей, попадающих во фрагмент, описываются полиномом степени не выше ш:

Я ю р

4 =!§> НУ/;

Г=1 р=0 q=0

здесь (/,jj) — точка фрагмента Жтп, б — индикаторная функция множества: бг = 1, если (/,j) % иг и бг = 0 в остальных случаях. Вводя в (1) текстурную т и шумовую ^тп составляющие, получим:

Я ( ю р \

X = 1 §г XI«ГР/-? + + §? .

г=1 у р=0 q=0 J

На большинстве реальных изображении средние яркости областеи на протяжении типичного окна анализа меняются мало [8] и могут считаться постоянными. Такое допущение

приводит к кусочно-постояннои модели с ш = 0. Тогда (^тп ) =

и (2) преобразуется к виду:

= 1 § г (

•С + + § ?)

Это формула кусочно-постояннои модели фрагмента, представляющая участки областеи изображения, попадающие во фрагмент Жтп. При смещении фрагмента меняются доли областеи, покрываемых фрагментом и, вообще говоря, 8гтп * Ягт+Атп+дп. Считая t и % несмещенными и

нормально распределенными, их сумма т = t + % также распределена нормально: N(0, а2 ), причем а2

2

= а 2 + а§ . Тогда (3) упрощается до

= 1 § г (с+т г).

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

г

область, распределение х? будет одномодовым. Если же фрагмент покрывает участки двух или

более областеи, то число мод распределения может достигать R. Положения мод определяются средними значениями я1,...^ участков областеи и1,...,ип, попадающих во фрагмент, а мощности мод — долеи площади, занимаемои каждои областью во фрагменте (Рис. 1(б) ).

3. Методы сглаживания на основе парзеновского оценивания

Из модели фрагмента ясно, что для нахождения сглаженного значения в точке (т,п), попадающей в область и1 на Рис. 1(а), необходимо по распределению Мк) найти значение я1. Т.е.

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

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

/

к=1 V у )

где F(x) — ядро анализа, w — параметр ширины ядра. На этои идее основаны многие алгоритмы классификации, в частности, метод ближаиших соседеи. При этом известно, что вид функции ядра F практически не влияет на точность классификации, а определяющим является параметр его ширины w [3]. Парзеновскии подход можно применить для оценивания положения моды по множеству элементов Хк (1 < к < К) области анализа:

Smn =

к=1 / к=1

где F(z) — весовая функция, а Хо — опорное значение в точке (т,п).

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

рассматриваемые ниже алгоритмы сглаживания: сигма-фильтр Ли, алгоритм

билатеральной фильтрации и алгоритм декомпозиции.

Сигма-фильтр

В случае выбора прямоугольных форм области анализа Штп и весовой функции, когда F(z) = 1 для хо-5 < z < хо+5, и F(z) = 0 для остальных z, а также использовании значения центрального элемента области анализа Хтп в качестве хо, получим известный сигма-фильтр Ли [4]:

1 ^

S = —У х' , Хти - 5, < х' < Хти + 5.

тп 0 тп ' ' тп ^

К г =1

Здесь R - число точек области Штп, попадающих в диапазон Хти ± 5 . Предлагается использовать 5 = 2а, где а2 - дисперсия шума [4]. В [14] сигма-фильтр отмечен как один из лучших фильтров, дающих удовлетворительное сглаживание при сохранении контуров.

Билатеральная фильтрация

Алгоритм билатеральной фильтрации [7], по сути, является расширением сигма-фильтра (7) возможностью выбора форм весовой функции F(z) и области анализа w(d). Для предлагаемых в [7] гауссовых форм F(z) и w(d) получим:

1 (?-х0)2 1

= е 24 ; *) = 24 , где = (т-т )2 + (п-п )2.

Тогда:

_((у'-ч? , 1 / ((у'-ч? , 1

S = У е ^ 2<^ ^х' У е ^ 2<^ 2<*) .

тп/ тп / / . ^ J

геШтп / геШтп

Декомпозиция

Алгоритм декомпозиции [5,6,9] принципиально отличается приведенных выше тем, что анализ проводится не в один, а в два этапа: сначала по малой окрестности Утп размерами 3-5 шагов дискретизации, а затем по большому фрагменту, превышающему размеры окрестности в 2-4 и более раз.

Формулировка алгоритма декомпозиции следующая. Изначально задаются размеры /х/ окрестности Утп и ¿хЬ (/ < ¿) фрагмента Штп, ширина яркостных интервалов анализа 5У и 5Ш, а также параметры отсечения пУ< /2/2 и пШ< ¿2/2. Для каждой точки (т,п) изображения выполняются следующие операции:

1. Находятся распределения значении элементов (гистограммы) по окрестности н¥п и фрагменту с центрами в (т,п).

2. По гистограмме н¥п и значению пУ вычисляются ранговые параметры = RV(nV//2) и К¥ = RV(1 - пУ//2), где R(x) — решение уравнения ЕЕ=(0Х)hVn (г') = Х. Усеченное значение Х¥ находится сравнением Хтп с К и К¥г : Х¥ = хтп, если е¥<хтп<К¥ ; Х¥ = К¥, если хтп<К¥; и =К¥г , если хтп>К¥ .

3. По значениям х^х Vтп (г=1,...,к) в интервале хг ± 5Уподсчитывается среднее:

х™ = ЧГтп,х^,п^) = хгтп/к, х^ - 5V < х! < х^ + 5".

4. Аналогично п. 2, по гистограмме фрагмента н-п и заданному пш находятся R1,r = RW(nW/L2) и ^Г = RW(1 - nW/L2). Сравнением х« с R1,r и Щ определяется усеченное значение хГ : хГ = хтп, если RW < х«п* RГ ; хГ = RW , если х«п< RГ ; и х- =2 RW , если х««> R2Г .

5. Сглаженное значение Smn определяется по н Гп как среднее значение К элементов из Wmn, попадающих в интервал хГ ± 5Г :

5™ = А

Полученная величина Smn считается сглаженным значением в точке (т,п). 4. Сравнение методов сглаживания

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

На Рис. 2 приведены результаты сглаживания указанного тестового изображения, которые сопровождены графиками одной и той же строки. На рисунке (а) приведено зашумленное изображение, подвергаемое сглаживанию. Изображения (б), (в) и (г) обработаны соответственно сигма-фильтром (7), билатеральным фильтром (8) и алгоритмом декомпозиции (9) с размерами фрагмента сглаживания 21х21 элементов при четырех итерациях. Для сравнения на (д) и (е) показаны результаты сглаживания хорошо известными фильтрами локального среднего и локальной медианы по фрагменту того же размера.

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

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

Зависимости точности восстановления сигнала (среднеквадратического отклонения, СКО) от вида фильтра и размеров окна сглаживания, измеренные для того же изображения на Рис. 2(а),

показаны графиками на Рис. 3. Нетрудно заметить, что каждый из трех видов сглаживания формирует отдельный пучок линий. При этом линии сигма-фильтра и билатерального фильтра расположены сравнительно близко — их точности отличаются всего на 15-20%, в то время как линии, соответствующие фильтру декомпозиции, располагаются отдельно и демонстрируют в 2-3 раза более точное восстановление. 30-> СКО 28 Н

Decomp 5 Decomp 9 Decomp 15 Sigma 5 Sigma 9 Sigma 15 Bilater 2ст= 6 Bilater 2ct=10 Bilater 2ct=20

26 -24 -22 20 -18 -16 -14 12 10 8 6 4 2 0

Рис. 3. Зависимость точности восстановления сигнала от изменения эффективной шириной окна для

различных методов сглаживания

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

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

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

wi(f) = J vo(et)dt,

w2(f ) = J vx(et)dt.

Здесь множество et — это t - уровень функции/х,у), т.е. множество тех точек (х,у), в которых /(х,у) = £ vo(et) — число компонент множества vl(et) — длина et (по Хаусдорфу). Тем самым значение И1 характеризует число и выраженность локальных экстремумов функции. В случае дискретнои функции /(;,/), двумерные вариации (10) выражаются следующими формулами [16]:

(т-1 Л С т-1 Л

Wif ) = |Ev„(et )/T

V x=0

-1 и ^и) = 1^1

У Ч*=0 У

где Т — число возможных значении функции /(;,/) (для изображения — число градации яркости), а Рф) — периметр области, по которои производится измерение. Будучи нормированным на величину диапазона Т, значение И1 является характеристики числа и амплитуды объектов изображения, образующих в сечениях отдельные компоненты. Поэтому удобно назвать значение И1 показателем числа объектов изображения.

Значение первой вариации И1 отражает число и контраст деталей на изображении, а значение второй вариации, — сумму периметров деталей. Наряду с этим, важным является соотношение вариаций Цш(/) = И2(/)/и1(/), которое отражает средний периметр деталей на изображении [16] (полагаем И1(/) > 0, иначе Ци(/) = 0). В дискретном изображении наименьшим возможным объектом является один элемент. Значит минимально возможная компонента, из числа входящих в множество уровня е^ имеет линейный размер равный одному шагу дискретизации, а ее периметр равен 4 — значению, которое есть аналог числа п в метрике ¿1 и является минимально

возможным для соотношения периметр/площадь объекта. Предполагая, что в дискретном случае длина границ компонент, составляющих vl{et), измеряется в метрике ¿1, очевидно, что для также существует минимально возможное значение, которое тоже равно 4, причем минимум достигается, когда все компоненты множеств уровня et для всех t являются одноэлементными. В связи со сказанным удобно ввести нормированную характеристику

№ = ^

которую по аналогии с показателем числа компонент И1 в (11) естественно назвать показатель размеров объектов изображения; для нее будет выполняться соотношение ё{/) > 1.

Таблица 1. Изменение значений СКО, показателя числа объектов иг и показателя размеров объектов d при сглаживании изображения

Оценка\Изображение ходное а б в г д е

СКО (градаций) 0,0 29,84 6,37 8,71 3,03 14,15 10,93

W1 0,39 380,8 14,67 33,93 0,43 1,37 1,70

d 22,5 1,41 1,84 1,42 25,11 9,85 8,82

Как видно из Таблицы 1, сигма-фильтр (б) и билатеральный фильтр (в) оставляют существенную часть шумовых выбросов неизменными (большие значения иг, малые d и значительные значения СКО). Локальное среднее (д) и медиана (е) показывают хорошее сглаживание (малые И1 и большие d), но сам сигнал значительно отличается от оригинала (большие СКО). Наилучшие результаты по всем параметрам, близкие к значениям неискаженного изображения, показывает алгоритм декомпозиции (г).

4. Пример сглаживания реального изображения

Иллюстрация сглаживания изображения (аэрофотоснимок) алгоритмом декомпозиции (9) приведена на Рис. 4. В нижнеи части изображении показаны графики однои и тои же строки, положение которои отмечено рисками на изображении (а). Кроме того в левом верхнем углу исходного изображения (а) показан размер фрагмента Жтп сглаживания, равньш 25x25 элементов. Изображение (б) получено сглаживанием изображения (а) алгоритмом декомпозиции (9). На (в) приведены разность изображении (а) и (б), а также график разности для тои же строки.

Рис. 4. Сглаживание реального изображения: а) исходное изображение

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

5. Выводы

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

Литература

1. Parzen E. On Estimation of a Probability Density Function and Mode // Annals of Mathematical Statistics, 1962, Vol. 33, pp. 1065-1076.

2. Дуда Р., Харт П. Распознавание образов и анализ сцен. - М.: Мир, 1976. 511 с.

3. Лагутин М.Б. Наглядная математическая статистика: Учебное пособие. - М.: Бином. Лаборатория знаний, 2007. -472 с.

4. Lee J.-S. Digital Image Smoothing and the Sigma Filter // Computer Vision, Graphics, Image Processing, 1983, vol. 24, no. 2. pp. 255-269.

5. Чочиа П.А. Обработка и анализ изображений на основе двухмасштабной модели: Препринт ИППИ АН СССР. М.: ВИНИТИ, 1986. - 69 с.

6. Чочиа П.А. Сглаживание изображения при сохранении контуров // Кодирование и обработка изображений. - М.: Наука, 1988, С. 87-98.

7. Tomasi C., Manduchi R. Bilateral filtering for gray and color images // Proc. IEEE 6th Int. Conf. on Computer Vision. -Bombay, India, Jan. 4-7, IEEE, 1998, pp. 839-846.

8. Чочиа П.А. Двухмасштабная модель изображения // Кодирование и обработка изображений. - М.: Наука, 1988, С. 69-87.

9. Chochia P.A. Image Enhancement Using Sliding Histograms // Computer Vision Graphics Image Processing, 1988, vol. 44, no. 2, pp. 211-229.

10. Kass M., Solomon J. Smoothed Local Histogram Filters // ACM Transactions on Graphics (Proceedings of ACM SIGGRAPH 2010) Vol. 29, Issue 4, 2010. Article no. 100. DOI: 10.1145/1778765.1778837.

11. Singh M., Ahuja N. Regression based Bandwidth Selection for Segmentation using Parzen Windows // Proc. Ninth IEEE International Conference on Computer Vision (ICCV 2003), vol.1, pp. 2-9.

12. Nishikawa S., Massa R.J., Mott-Smith J.C. Area Properties of Television Pictures // IEEE Trans. IT-11, 1965, no. 3, pp. 348352.

13. Журавлев Ю.И., Гуревич И.Б. Распознавание образов и анализ изображений // Искусственный интеллект: в 3-х книгах. Книга 2. Модели и методы: Справочник. М.: Радио и связь, 1990.

14. Mastin G.A. Adaptive Filters for Digital Image Noise Smoothing: An Evaluation // Computer Vision, Graphics, Image Processing, 1985, vol. 31. no. 1. pp. 103-121.

15. Кронрод А.С. О функциях двух переменных // УМН, 1950, т. 5, № 1, С. 24-134.

16. Chochia P.A., Milukova O.P. Comparison of Two-Dimensional Variations in the Context of the Digital Image Complexity Assessment. // Journal of Communications Technology and Electronics, 2015, vol. 60, no. 12. pp. 1432-1440.

References

1. Parzen E. On Estimation of a Probability Density Function and Mode // Annals of Mathematical Statistics, 1962, Vol. 33, pp. 1065-1076.

2. Duda R.O., Hart P.E. Pattern Classification and Scene Analysis. - N.-Y.: Wiley, 1973.

3. Lagutin M.B. Illustrative mathematical statistic: the Tutorial. - Moscow.: Binom. Knowledge laboratory, 2007. - 472 p.

4. Lee J. S. Digital Image Smoothing and the Sigma Filter // Computer Vision, Graphics, Image Processing, 1983, vol. 24, no. 2. pp. 255-269.

5. Chochia P.A. Image Processing and Analysis on the Base of Two-Dimensional Image Model: Preprint IITP USSR. Moscow: VINITI, 1986. - 69 p.

6. Chochia P.A. Image Smoothing Under Contour Preservation // Image coding and processing. - Moscow: Science, 1988, pp. 87-98.

7. Tomasi C., Manduchi R. Bilateral filtering for gray and color images // Proc. IEEE 6th Int. Conf. on Computer Vision. -Bombay, India, Jan. 4-7, IEEE, 1998, pp. 839-846.

8. Chochia P.A. Two-Dimensional Image Model // Image coding and processing. - Moscow: Science, 1988, pp. 69-87.

9. Chochia P.A. Image Enhancement Using Sliding Histograms // Computer Vision Graphics Image Processing, 1988, vol. 44, no. 2, pp. 211-229.

10. Kass M., Solomon J. Smoothed Local Histogram Filters // ACM Transactions on Graphics (Proceedings of ACM SIGGRAPH 2010) Vol. 29, Issue 4, 2010. Article no. 100. DOI: 10.1145/1778765.1778837.

11. Singh M., Ahuja N. Regression based Bandwidth Selection for Segmentation using Parzen Windows // Proc. Ninth IEEE International Conference on Computer Vision (ICCV 2003), vol.1, pp. 2-9.

12. Nishikawa S., Massa R.J., Mott-Smith J.C. Area Properties of Television Pictures // IEEE Trans. IT-11, 1965, no. 3, pp. 348352.

13. Jouravlev Yu.I., Gourevich I.B. Pattern Recognition and Image Analysis // Artificial intelligence: in 3 books. Book 2. Models and Methods: Handbook. Moscow: Radio and Communication, 1990.

14. Mastin G.A. Adaptive Filters for Digital Image Noise Smoothing: An Evaluation // Computer Vision, Graphics, Image Processing, 1985, vol. 31. no. 1. pp. 103-121.

15. Kronrod A.S. On the Functions of Two Variables // Progresses of mathematical sciences, 1950, vol. 5, no1, pp. 24-134.

16. Chochia P.A., Milukova O.P. Comparison of Two-Dimensional Variations in the Context of the Digital Image Complexity Assessment. // Journal of Communications Technology and Electronics, 2015, vol. 60, no. 12. pp. 1432-1440.

Поступила 15.10.2016

Об авторе:

Чочиа Павел Антонович, кандидат технических наук, старшии научныи сотрудник Института проблем передачи информации РАН, chochia@iitp.ru.