Авторефераты по всем темам  >>  Авторефераты по техническим специальностям  

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

КОЛЬЦОВ ПЁТР ПЕТРОВИЧ

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

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

Автореферат диссертации на соискание ученой степени

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

Москва

2012

Работа выполнена в Федеральном государственном бюджетном учреждении науки Научно-исследовательском институте системных исследований  Российской академии наук  (НИИСИ РАН)

Официальные оппоненты:  доктор физико-математических наук,

                                       член-корреспондент РАН,        

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

       доктор физико-математических наук,

                                       Михаил Николаевич Устинин

       доктор физико-математических наук

                                       Юрий Михайлович Лазутин

Ведущая организация:        Федеральное государственное бюджетное учреждение науки  Институт систем обработки изображений  Российской академии наук (ИСОИ РАН)

Защита диссертации состоится л __________ 2012 г. в на заседании диссертационного совета  Д  002.017.02 при  Федеральном государственном бюджетном учреждении науки  Вычислительном  центре  им. А.А. Дородницына  Российской академии наук по адресу: 119333, г. Москва, ул. Вавилова, д. 40.

С диссертацией можно  ознакомиться  в  библиотеке  Федерального Государственного бюджетного учреждения науки Вычислительного центра им. А.А. Дородницына  Российской академии наук

Автореферат разослан л  _____________ 2012 г.

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

д.ф-м.н., профессор                                                В.В. Рязанов      

Общая характеристика работы

Актуальность темы

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

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

Цель исследования

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

Задачи исследования        

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

Объект исследования

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

Предмет исследования

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

Методы исследования

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

Научная новизна

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

Практическая значимость

Использование разработанной методологии позволяет:

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

Достоверность и обоснованность

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

ичный вклад автора

       Все результаты работы получены автором лично.

На защиту выносится:

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

Апробация работы

Основные положения диссертационной работы докладывались и обсуждались на следующих международных конференциях:

• 6th World Multiconference on Systemics, Cybernetics and Informatics (SCIТ2002), Orlando, Florida, USA, July 14-18, 2002г.
• 8th World Multiconference on Systemics, Cybernetics and Informatics (SCIТ2004), Orlando, Florida, USA, July 18-21, 2004г.
• 5th WSEAS International Conference on Signal Processing, Computational Geometry and Artificial Vision, Malta, September 15-17, 2005г.
• 6th WSEAS International Conference on Signal, Speech and Image Processing, Lisbon, Portugal, September 22-24, 2006 г.
• 8th WSEAS International Conference on Signal, Speech and Image Processing, Santander, Cantabria, Spain, September 23-25, 2008г.
• 9-ая Международная конференция Распознавание образов и анализ изображений: новые информационные технологии (РОАИ-9-2008), Нижний Новгород, 14-20 сентября 2008г.
• 13th World Multi-Conference on Systemics, Cybernetics and Informatics (WMSCI 2009), Florida, USA, July 14-13, 2009г.
• 10-ая Международная конференция Распознавание образов и анализ изображений: новые информационные технологии (РОАИ-10-2010), Санкт-Петербург, Санкт-Петербургский государственный электротехнический университет ЛЭТИ, 5-12 декабря 2010г.

Структура и объём диссертации

Работа состоит из введения, девяти глав, заключения, списка литературы из 130 наименований и Приложения. Работа изложена на 284 страницах, содержит 124 рисунка и 7 таблиц.

Публикации

       Основные работы, опубликованные по теме диссертации, содержатся в 18 журналах, трудах и тезисах международных конференций, в том числе 9 из них - в изданиях из списка ВАК.

Основное содержание работы

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

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

Первая группа методов предназначена для решения задачи реставрации изображений на основе т.н. энергетических методов. В главе приведено описание методов МамфордаЦШаха1, ГеманаЦРейнольдса2 и метода с кусочно-линейной функцией в функционале энергии3.

Пусть I(x,y) - исходное изображение, заданное в некоторой области (x,y). Это изображение требуется улучшить. Пусть u(x,y) - новое изображение, заданное в той же области и являющееся решением минимизационной задачи относительно энергии E.

В качестве функционала энергии метода МамфордаЦШаха рассмотрен функционал вида

, ,

где обозначает норму градиента u, множитель , 0< , 0< <1, определяет вклад членов, зависящих от I  и от в r, c - дополнительный нормировочный множитель.

1Mumford D., Shah J. Optimal Approximations by Piecewise Ssmooth Functions and Associated Variational Problems // Commun. Pure Appl. Math. - 1989.Ц  Vol. 52.Ц  Pp. 577-685.

2Geman D., Reynolds G. Constrained Restoration and the Recovery of Discontinuities // IEEE TPAMI. - 1992. - Vol. 14. - Pp. 376-383.

3Veksler O. Efficient Graph-Based Energy Minimization Methods in Computer Vision // PhD Thesis, Cornell University. - 1999.

В качестве функционала энергии метода ГеманаЦРейнольдса рассмотрен функционал вида

.

В качестве функционала энергии для метода с кусочно-линейной функцией рассмотрен функционал вида

,

где (r) определяется следующим образом:

(r) =.

Во вторую группу  методов цифровой  обработки изображений включены методы выделения границ, называемых по имени авторов методами Canny4, Heitger5, Rotwell6, Black7, Iverson8 и Smith9.

Метод Canny базируется на использовании т.н. фильтров Canny, имеющих следующий вид для одномерного случая:

,

где все множители и частота являются параметрами фильтра.

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

Метод Rothwell использует топологическую структуру изображения для  приближения к границам.

Метод Black  является методом, основанном  на использовании

уравнения анизотропной диффузии

4Canny J. A. Computational Approach to Edge Detection // IEEE Pattern Anal.Маchin. Intell. - 1986. - Vol. 8, no 16. - Pp. 679-698.

5Heitger E., Rosenthaler L., von der Heydt R., Peterhans E., Kubler O. Simulation of Neural Contour Mechanisms: From Simple to End-Stopped Cells // Vision Research. - 1992. - no. 32. - Pp. 963-981.

6Rothwell C.A., Mundy J.L., Hoffman W., et al. Driving Vision by Topology // Int. Symp. Computer Vision. - 1995.Ц  Pp. 395-400.

7Black M., Sapiro G., Marimont D. et al. Robust Anisotropic Diffusion // IEEE Trans. Image Process. - 1998. - Vol. 7.Ц  no. 3. - Pp. 421-432.

8Iverson L.A., Zucker, S.W. Logical/Linear Operators for Image Curves // IEEE Trans. Pattern Anal. Mach. Intell. - 1999. - Vol. 17, no. 10. - Pp. 982-996.

9Smith S.M. Flexible Filter Neighborhood Designation // Proc. 13th Int. Conf. on Pattern Recognition. - 1996. - Vol. 1. - Pp. 206-212.

где функция g обладает следующими  свойствами: при . 

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

Метод Smith использует нелинейную фильтрацию для определения связных частей изображения.

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

К этой группе методов отнесены и т.н. методы активного контура GSNAKE и GVF10, называемых также методами уточнения границ. В основе методов активного контура лежит поиск минимума т.н. функционала энергии для параметризованной подвижной кривой на плоскости изображения 11:

.

Модель, реализованная в методе активного контура  GSNAKE,

использует  аналогию с тяжелой эластичной  нитью, которая

скатывается  вниз  по рельефу  функции  z (x, y) = -|∇ I (x, y)|2, где ∇I

(x, y) - градиент яркости изображения.

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

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

10Xu Ch. Prince J. L. Snakes, Shapes and Gradient Vector Flow // IEEE Transactions on Image Processing . - 1998. - Vol. 7, no 3. - Pp. 359-369.

11Kass M., Witkin A., Terzopoulos D. Snakes: Active Contour Models // Int'l J. Computer Vision. - 1988. - Vol. 1, no 4. - Pp. 321-331.

12Karu K., Jain A.K. et al. Is There Any Texture in the Image? //Pattern Recognition. - 1996. - Vol. 29, no. 9. - Pp. 1437-1446.

13Jain A.K., Farrokhnia F. Unsupervised Texture Segmentation Using Gabor Filters // Pattern Recognition. - 1991. - Vol. 24, no. 12. - Pp. 1167-1186.

MAXDIF, анализ плотности граничных точек14, маски Лоса15, фильтры кольцо/клин16, матрицы смежности17 и авторегрессионная модель изображения18.

В четвёртую группу методов объединены методы,  предназначенные для решения задач сегментации изображений. В неё входят следующие методы сегментации, ради краткости называемых сегментаторами: EDISON19, JSEG20, EDGEFLOW21, MULTISCALE22.

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

Во второй главе  описаны принципы  сравнительного  исследо-

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

обработки изображений,  инструментальные средства,  разработанные

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

Сравнительное  исследование качества  работы алгоритмов

14Dinstein I., Fong A.C. et al. Fast Discrimination Between Homogeneous and Textured Regions // Proc. of the Seventh International Conference on Pattern Recognition. - 1984.Ц  Vol. 1. - Pp. 361-363.

15Laws K.I. Rapid Texture Identification // Proc. SPIE Conf. Image Processing for Missile Guidance. - 1980. - Pp. 376-380.

16Coggins J.M., Jain A.K. A Spatial Filtering Approach to Texture Analysis // Pattern Recognition Letters. - 1985. - Vol 3, no. 3. - Pp. 195-203.

17Haralick R., Shanmugam K. et al. Textural Features for Image>

18Mao J., Jain A.K. Texture>

цифровой обработки изображений опирается на следующие принципы:

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

Для проведения сравнительного исследование качества работы различных алгоритмов цифровой обработки изображений в соответствии с этими принципами, в качестве инструментальных средств были использованы две компьютерные системы PICASSO (PICture Algorithms Study SOftware) и PETRA (Performance Evaluation of Texture Recognition Algorithms), депонированные в архиве отдела научно-технической информации НИИСИ РАН. Эти средства  позволяют получать оценки  качества работы  алгоритмов цифровой  обработки изображений на тестовых изображениях, подвергаемых контролируемым искажениям, в том числе для различных критериев с использованием различных метрики.

       В  исследованиях, связанных с  реализацией методов,

19Christoudias C. M., Georgescu B. et al. Synergism in Low Level Vision // 16th International Conference on Pattern Recognition.Ц  2002. - Vol. 4. - Pp. 150-155.

20Deng Y., Manjunath B.S. Unsupervised Segmentation of Color-Texture Regions in Images and Video // IEEE Transactions on Pattern Analysis and Machine Intelligence (PAMIТ01). - 2001. - Vol. 23, no. 8. - Pp. 800-810.

21Ma W.-Y., Manjunath B.S. EdgeFlow: A Technique for Boundary Detection and Image Segmentation // IEEE Transactions on Image Processing. - 2002. - Vol. 9.Ц  Pp. 1375-88.

22Sumengen B., Manjunath B. S. Multi-scale Edge Detection and Image Segmentation // Proc. European Signal Processing Conference (EUSIPCO). - 2005. - Vol. CD. 05eusipcoBarisMultiscale.pdf.

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

• Уступ - точка, по разные стороны от которой интенсивности существенно различаются.
• Излом - точка, в которой производная интенсивности имеет уступ.
• Горб - короткий отрезок, такой, что интенсивность внутри него существенно отличается от интенсивности вне его (два примыкающих уступа).

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

                      (a)                 (b)

Рис.а1. Исчезающий уступ (a) и Изменяющийся горбаI (b)

                        (a)  (b)

Рис.а2. Изменяющийся горбаII (a) и Исчезающий излом (b)

  (a)  (b)        

Рис.а3. Улитка (a) и Узел (b)

Приведённый выше  набор изображений состоит из трех частей:

1. Исчезающий уступ, Исчезающий излом, Изменяющийся горб I и Изменяющийся горб II. Границы этих изображений являются прямыми,  высота уступа изменяется по линейному закону.

2. Улитка.  Граница  этого изображения  имеют переменную кривизну. Другие параметры  изображения  могут  меняться  так  же,

как и в предыдущем случае.

3. Узел. Это изображение имеет особую точку, возникающую из-за пересечения границ.

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

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

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

   

        (a)                               (b)                                 (c)        

Рис. 4. Примеры закраски фона

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

Также в набор тестовых объектов входят контуры, построенные из прямолинейных отрезков и дуг окружностей. На Рис. 6 показаны два типа контуров, построенных с использованием квадрата и окружности.

 

(a) (b)

Рис. 6. Контуры на основе квадрата (a) и окружности (b)

Для проведения сравнительного исследования методов выделения текстурных областей  на изображении был использован набор тестовых изображений, содержащих как естественные изображения, так и искусственные. На Рис. 7 приведены примеры используемых тестовых изображений. На Рис. 7a-7b - аэрофотоснимки, а на Рис.7c - искусственное изображение.        

   

  (a)  (b) (c)

Рис. 7. Примеры тестовых изображений

Сравнительное исследование качества работы методов анализа текстурных областей выполнялось на изображениях из альбома текстур,  открытой базы данных изображений и аэрокосмических снимков23.

       Для проведения сравнительного исследования качества работы сегментаторов помимо тестовых изображений, приведённых на Рис.1-3, были использованы изображения, приведённые ниже на Рис. 8-10, моделирующие иные трудные для методов  сегментации ситуации: соответственно сохранение углов, контраст объект/фон, ложные границы. Количественная оценка качества работы алгоритмов цифровой обработки изображений рассматривалась для случаев, когда в качестве меры различия между априорно заданным истинным т.н. ground truth изображением и результатом работы алгоритма  были  рассмотрены  метрики Евклида, Хаусдорфа, Пратта, чувствительность

и специфичность.

23Brodatz P. Textures: A Photographic Album for Artists and Designers. - NY.: Dover Publications, 1966. - 128 p.

Smith G., Bums I. Measuring Texture>

 

Рис. 8. Примеры тестовых изображений (углы)

    .

Рис. 9. Примеры тестовых изображений (фон/объект)

   

Рис. 10. Примеры тестовых изображений (ложные границы)

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

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

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

Пользуясь тем, что известны исходные недеградированные ground truth изображения, для каждого изображения будем рассматривать область содержащую окрестность граничных линий. Пусть - вся область изображения, указанная окрестность границ - B. Тогда оставшаяся часть изображения есть \B. Определим метрики dB и d\B , различающиеся областями определения. Метрика d\B вычисляется на основе Евклидовой нормы в области, где нет граничных линий, поэтому величина d\B характеризует, в основном, величину шума на реставрированном изображении. Метрика dB вычисляется на основе Евклидовой нормы в области, в которой находятся граничные линии. Значение dB велико, если на реставрированном изображении границы размыты, и мало, если резкие перепады яркости вблизи границ, сохранены. При сравнительном исследовании качества работы алгоритмов реставрации изображений будем использовать именно эти две метрики: dB и d\B.

На Рис. 11 показан пример  графика расстояния между реставрированным после искажения (метод Гемана-Рейнольдса) и  исходным  изображением  Изменяющийся  горб II для области \B.

Рис. 11. График d\B, метод Гемана-Рейнольдса

На Рис. 12  приведён пример графика расстояния между реставрированным после искажения (алгоритм  с кусочно-линейной функцией) и  исходным  изображением  Изменяющийся  горб II для области B.

Рис. 12. График dB. Алгоритм с кусочно-линейной функцией

На Рис. 13 приведены примеры графиков расстояния между реставрированным после искажения (метод Мамфорда-Шаха) и исходным изображением Изменяющийся  горб II для областей \B и B.  Верхний график - для области \B, нижний - для окрестности границы B. Анализ графиков, отражающих результаты работы алгоритмов с помощью метрики d\B во внеграничных областях, показывает, что при больших значениях шума метод Мамфорда-Шаха подавляет его хуже других методов. Вместе с тем,  анализ графиков для метрики dB позволяет сделать вывод, что метод Мамфорда-Шаха очень хорошо сохраняет резкие перепады границ, в случае, когда уровень шума невелик.

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

 

Рис. 13. Графики d\B (вверху) и dB (внизу), метод Мамфорда-Шаха

множество пикселов,  составляющих тестовое  изображение. Пусть A - пикселы, составляющие границу ground truth изображения, а B - пикселы границ, полученную при работе тестируемого детектора границ. Тогда чувствительность Se  и специфичность Sp определяется следующим образом:

,

где n(S) - число пикселов в S.

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

Рис. 14.аЧувствительность и специфичность для тестового изображения Исчезающий уступ (размытие)

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

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

       

Рис. 15.аЧувствительность (слева) и специфичность (справа) для тестового изображения Исчезающий уступ (зашумление)

окна размытия, дисперсия шума) для чувствительности и специфичности находились их средние значения и дисперсия. На Рис. 16 и Рис. 17 приведены соответствующие результаты тестирования. Средние значения показаны  на  как  столбцы.  Столбцы,  отвечающие

Рис. 16. Чувствительность и специфичность (размывание)

Рис. 17. Чувствительность и специфичность (зашумление)

одному и тому же алгоритму, закрашены одним и тем же паттерном. Значения дисперсии показаны как черные вертикальные отрезки над соответствующими столбцами. Данные, полученные на тестовых изображениях Исчезающий уступ, Изменяющийся горб I, Изменяющийся горб II, Исчезающий излом, Улитка и Узел, сгруппированы под цифрами 1, 2, 3, 4, 5 и 6 соответственно. Не трудно видеть, что алгоритмы Canny и Rothwell имеют хорошую специфичность  и чувствительность и при размытии, и при зашумлении.

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

Для метода GSNAKE была исследована точность решения при трёх различных способах вычисления внешней энергии. Полученные результаты представлены на Рис. 18.

Рис. 18. Среднее значение ошибки Emean в зависимости от относительного размера выступов и впадин. Слева - для шаблона 22, справа - для шаблона 33

Для вычисления внешней энергии в качестве функции использовались модуль градиента интенсивности , квадрат модуля градиента и модуль проекции градиента на нормаль . Точность полученного контура в результате применения  метода ведет себя сходным образом для любого определения энергии: она падает с увеличением размера выступов и впадин. Для разностной аппроксимации градиента интенсивности I(x, y) использовались шаблоны 22 или 33.

Примеры сравнительной оценки качества работы методов GSNAKE и GVF показаны на Рис. 19 и Рис. 20. Здесь в качестве меры ошибки решения EH бралось Хаусдорфово расстояние в пикселах между результирующим и истинным контурами. На Рис. 19 показана зависимость ошибки EH от нормализованного контраста фона и объектов С. Видно, что с ростом  С оба метода выбирают ложные границы.

Рис. 19. Ошибка EH  в зависимости от контраста

Рис. 20. Ошибка EH  в зависимости от величины углубления

На Рис. 20 показана зависимость ошибки EH  от относительной величины углубления a/H на тестовом изображении при фиксированном контрасте С. Видно, что метод GVF дает лучшие результаты при любой величине каверн на изображении.

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

Для численной оценки качества работы тестируемых алгоритмов был использован модифицированный показатель качества Пратта (FOM):

,

где N - число пикселов изображения, di - Евклидово расстояние между i-м пикселом изображения после работы алгоритма и его истинной областью (текстурной или бестекстурной), - постоянный шкалирующий множитель, который может использоваться для изменения вклада ошибок в FOM.

Значения оценки качества FOM, полученное в результате исследования алгоритмов плотности граничных точек (ED), плотности локальных экстремумов (LED) и MAXDIF (MD) отражены на Рис. 21.  Эти оценки подсчитывались отдельно на естественных и искусственных тестовых изображениях.

Рис. 21.а Диаграмма качества работы методоваED, LED и MD

На Рис. 22 приведены результаты тестирования алгоритмов, реализующих фильтр Габора (Gabor), маски Лоса (Laws), кольцо/клин (RWF), матрицы смежности (GLSM), авторегрессионную модель (MR-SAR).  Для тестирования  этих алгоритмов были  использованы

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

три набора изображений: текстуры из альбома Бродаца (Brodatz),  базы данных MeasTex23 и текстуры на наборе аэрофотоснимков.

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

В седьмой главе приведены результаты исследования качества работы детекторов границ Rothwell, Black, Smith, Heitger, Iverson и Canny при аффинных преобразованиях исходных изображений. В качестве аффинных преобразований рассматривались поворот, сдвиг и сжатие/растяжение. В качестве мер различия между  ground truth изображением и изображением, полученным в результате работы того, или иного детектора, были рассмотрены чувствительность, специфичность, метрика Пратта, Хаусдорфова метрика. В качестве исходных тестовых изображений были взяты  Исчезающий уступ, Исчезающий излом и Узел, содержащие несколько характерных типов границ. После применения набора аффинных преобразований для всех изображений был получен набор соответствующих тестовых изображений для выполнения сравнительной оценки качества работы детекторов границ при аффинных преобразованиях.

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

Изображения	Чувстви-тельность	Специ-фичность	Пратт	Хаусдорф
Исходное	0.367	0.98	0.32	79.0
Поворот 5o	0.746	1.00	0.26	63.5
Поворот 90o	0.35	1.00	0.17	57.0
Поворот 180o	0.39	0.99	0.33	69.6
Сдвиг	0.38	0.94	0.37	71.0
Сжатие (0.9)	0.687	1.00	0.67	54.1

Таблица 1. Оценка качества работы детектора Rothwell, примененного к  изображению Исчезающий излом

В Таблице 2 представлены результаты применение детектора Smith к изображению Узел.

Изображения	Чувстви-тельность	Специ-фичность	Пратт	Хаусдорф
Исходное	0.869	1.00	0.76	26.1
Поворот на 45o	0.5969	0.86	0.43	126

Таблица  2. Оценка качества работы детектора Smith, примененного к изображению Узел.

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

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

При построении оценки качества работы сегментаторов, в качестве меры близости между истинным и деградированным изображением были рассмотрены Евклидова метрика, метрика Хаусдорфа и её модификация.

Пусть X и Y - два множества точек. Если Хаусдорфово расстояние (X, Y) между множествами X и Y определяется как 

,

где (x, y) обычное Евклидово расстояние между точками x и y, а , то модифицированная метрика Хаусдорфа d(X, Y) определяется следующим образом.

Пусть множества X и Y содержат NX и NY точек. Тогда

  .

Отметим, что если величина (X, Y) дает скорее максимальное расстояние между точками множеств, то d(X, Y), то d(X, Y) дает в некотором роде среднее расстояние. Очевидно, d(X, Y) 0,  d(X, X) =0 и  d(X, Y) = d(Y, X).

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

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

На Рис. 23 приведены результаты работы сегментаторов EDISON и MULTISCALE на изображениях с углами. Можно видеть, что сегментаторы сохраняют углы практически идеально.

Рис. 23. Сохранение углов  сегментаторами EDISON и MULTISCALE

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

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

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

Рис. 24. Линии тренда для различных сегментаторов при сегментации регионов с медленно изменяющейся яркостью

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

 

Рис. 25. Зашумление изображений, Хаусдорфово расстояние (пикс.)

Из анализа этих графиков становится очевидным преимущество сегментатора JSEG относительно остальных сегментаторов при зашумлении и сегментатора EDISON при размытии.

Рис. 26. Размытие изображений, среднее расстояние (пикс.)

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

Рис. 27. Зашумление изображений, Хаусдорфово расстояние (пикс.)

Рис. 28. Размытие изображений, среднее расстояние (пикс.)

Из анализа графиков трендов видно преимущество результатов работы сегментаторов EDISON и JSEG при зашумлении и сегментатора JSEG при размытии.

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

24Rank K., Lendl M., Unbehauen R. Estimation of Imagenoise Variance // IEEE Proc. Vis. Image Signal Process.Ц  1999.Ц  Vol. 146, no. 2. - Pp. 80Ц84.

Luxen M., Forstner W. Characterizing Image Quality: Blind Estimation of the Point Spread Function from a Single Image // ISPRS Commission III: Theory and Algorithms. - 2002. - Vol. 34, part 3A. - Pp. 205Ц210.

Portilla J. J., Strela V. et al. Image Denoising Using Scale Mixtures of Gaussians in the Wavelet Domain // IEEE Transactions on Image Processing. - 2003. - Vol. 12, no. 11.Ц  Pp. 1338Ц1351.

Stefano A., White P. et al. Training Methods for Image Noise Level Estimation on Wavelet Components // EURASIP Journal on Applied Signal Processing. - 2004. - no. 16.Ц  Pp. 2400 - 2407.

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

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

изображения,  при  помощи дополнительного  Гауссова размытия  с

заданным окном , получены формулы, позволяющие найти размеры окон размытия соответственно x и a:

, ,

где , - функция, обратная к функции .

На Рис. 29 приведены графики функций , и .

Рис. 29. Функции для определения окна размытия a

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

25Zucker S., Elder J. Scale Space Localization, Blur, and Contour-Based Image Coding // CVPR Proc. - 1996. - Pp. 27Ц34.

всех требуемых функций. Как можно видеть, функция   практически не отличается от функции y=x уже при значениях аргумента x= d/ , больших 1.5. Таким образом, при этих значениях x  имеем , то есть, ad.

Для  изображения  Исчезающий  уступ был  выполнен  эксперимент  по  определению  истинного окна Гауссова размытия

x заданное. Вычисленный параметр размытия x вычисленное был получен по одномерному графику яркости. Результаты измерений приведены в таблице 3

x заданное	x вычисленное
0.0	0.12
0.5	0.61
1.0	1.13
1.5	1.62
2.0	2.12
2.5	2.56
3.0	3.11

Таблица 3. Значения истинного и вычисленного параметров размытия

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

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

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

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

• При решении задачи реставрации метод, использующий кусочно-линейную функцию, проявляет нестабильность работы на зашумленных изображениях.
• Алгоритмы выделения границ Heitger и Canny обладают наилучшей чувствительностью, а  алгоритмы Canny и Rothwell - наилучшей специфичностью при работе на размытых изображениях простой структуры.
• Для изображений со сложной структурой  границ только алгоритмы Canny и Rothwell проявили достаточно хорошие специфичность и чувствительность на размытых изображениях.
• Все тестированные реализации методов выделения границ  имеют схожую чувствительность и являются устойчивыми к белому шуму.
• Характер поведения энергетических методов выделения границ Мамфорда-Шаха, Гемана-Рейнольдса и с использованием кусочно-линейной функции при Гауссовом зашумлении для чувствительности и специфичности примерно одинаков.
• Методы уточнения границ GSNAKE и GVF ведут себя одинаково при зашумлении и размытии границ.
• Среди методов текстурного анализа ни одна из реализаций исследуемых методов не показала абсолютного превосходства над другими.
• При аффинных преобразованиях изображений все исследованные реализации различных методов детектирования границ продемонстрировали одинаковый характер поведения на тестовых изображениях.
• Выделение слабоконтрастных областей рассмотренными  в работе сегментаторами позволяет выявлять особенности их реализаций.

Приведённые выше выводы вместе с результатами исследования позволяют сделать следующие рекомендации по применимости исследованных методов.

• При решении задач реставрации изображений метод Гемана-Рейнольдса предпочтителен при работе с сильным зашумлением, а метод Мамфорда-Шаха - при слабом.
• При работе на размытых изображениях как  простой, так и сложной структуры для достижения наилучшей чувствительности и специфичности предпочтительно использовать алгоритм выделения границ Canny.
• Для зашумленных белым шумом изображений при одинаковой чувствительности всех тестированных алгоритмов, для достижения наилучшей чувствительности предпочтительно использовать алгоритмы выделения границ Canny и Rothwell.
• Использование исследованной реализации метода выделения границ Мамфорда-Шаха при Гауссовом зашумлении  нецелесообразно.
• Метод уточнения границ GVF предпочтителен  при наличии больших каверн на изображении.
• Метод уточнения границ GSNAKE предпочтителен в случае, если граница изменяется плавно, а уровень шума невелик.
• Для предварительной сегментации предпочтительно использовать алгоритм плотности граничных точек.
• При отсутствии искажений сегментаторы EDISON и MULTISCALE предпочтительны при обработке изображений с углами.
• При малой контрастности при работе на изображениях с плавно изменяющейся яркостью предпочтителен сегментатор MULTISCALE.
• Сегментатор JSEG предпочтителен при работе на зашумлённых  и сложных размытых изображениях.
• Сегментатор EDISON предпочтителен при работе на простых размытых изображениях.

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

В Приложении приведена структурная схема использованных компьютерных систем PICASSO и PETRA, их архивный номер и децимальный индекс НИИСИ РАН.

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Koltsov P.P. A Comparative Study of Image Processing Algorithms // Pattern Recognition and Image Analysis . - 2011. - Vol. 21, no.  2. - Pp.  148Ц151.

2. Кольцов П.П. Использование метрик при сравнительном исследовании качества работы алгоритмов сегментации изображений // Информатика и её применения. - 2011. - Т. 5, вып. 3. - С. 51Ц61.

3. Кольцов П.П. Оценка качества работы алгоритмов цифровой обработки изображений // Доклады РАН. - 2011. - Т. 440, № 3. - С. 1Ц3.

4. Кольцов П.П. Оценка размытия изображения // Компьютерная оптика. - 2011. - Т.  35, №  1. - С. 95Ц102.

5. Кольцов П.П. Эмпирический подход к оценке алгоритмов выделения границ // Информационные технологии и вычислительные системы. - 2011. - № 2. - С. 50Ц57.

6. Кольцов П.П. Сравнительное изучение алгоритмов выделения и классификации текстур // Журнал вычислительной математики и математической физики. - 2011. - Т. 51, № 8.Ц  С. 1561Ц1568.

7. Koltsov P.P. Comparative Analysis of Image Processing Algorithms // Pattern Recognition and Image Analysis. - 2012. - Vol. 22, no. 1. - Pp. 39Ц43.

8. Gribkov I.V., Koltsov P.P. et al.  Robustness of Noisy and Blurry Images Segmentation // Pattern Recognition and Image Analysis. - 2009. - Vol. 19, no. 3. - Pp. 484Ц490.

9. Gribkov I.V., Koltsov P.P. et al. PICASSO - A System for Evaluating Edge Detection Algorithms // Pattern Recognition and Image Analysis. - 2003. - Vol. 13, no. 4. - Pp. 617-622.

10. Gribkov I.V., Koltsov P.P. et al. Performance evaluation of Texture Segmentation Methods // Proc. 13th World MultiConf. on Systemics, Cybernetics and Informatics. - 2009. - Vol. 4. - Pp. 137-142.

11. Gribkov I.V., Koltsov P.P. et al. Study of Noisy and Blurry Images Segmentation // Proc. 9 Int. Conf. on Pattern Recognition and Image Analysis: New Information Technologies (PRIA-9-2008). - 2008. - Vol. 1. - Pp.193Ц196.

12. Gribkov I.V., Koltsov P.P. et al. Comparative Study of Image Segmentation Algorithms // Proc. 8th WSEAS Int. Conf. on Signal, Speech and Image Processing. - 2008. - Pp. 21Ц28.

13. Gribkov I.V., Koltsov P.P. et al. Affine Invariance Study of Edge Detection Algorithms by Means of PICASSO 2 System // Proc. 6th WSEAS Int. Conf. on Signal, Speech and Image Processing. - 2006. - Pp. 11Ц16.

14. Gribkov I.V., Koltsov P.P. et al. Edge Detection Under Affine Transformations: Comparative Study by the PICASSO 2 System // WSEAS Trans. on Signal Processing. - 2006. - Vol. 2, no. 9. - Pp. 1215Ц1222. 

15. Gribkov I.V., Koltsov P.P. et al.  PICASSO 2 - a System for Performance Evaluation of Image Processing  Methods // Proc. 5th WSEAS Int. Conf. on Signal Processing, Computational Geometry and Artificial Vision. - 2005. - Pp. 88Ц93.

16. Gribkov I.V., Koltsov P.P. et al.  Empirical Evaluation of Image Processing Methods Using PICASSO 2 System // WSEAS Trans. on Systems. - 2005. - Vol. 4, no. 11. - Pp. 1923Ц1930.

17. Gribkov I.V., Koltsov P.P. et al. Testing of Energy Minimizing Methods in Image Preprocessing Using the PICASSO System // Proc. 8th World MultiConf. on Systemics, Cybernetics and Informatics. - 2004.ЦVol. 6. - Pp. 233-238.

18. Gribkov I.V., Koltsov P.P. et al. PICASSO - Edge Detectors Evaluation System based on the Comprehensive Set of Artificial Images // Proc. 6th World MultiConf. on Systemics, Cybernetics and Informatics. - 2002. - Vol. 9.ЦPp. 88Ц94.

       Работы с 1 по 9 опубликованы в изданиях, рекомендуемых ВАК РФ.

  Авторефераты по всем темам  >>  Авторефераты по техническим специальностям