Регуляризирующие методы фильтрации и восстановления изображений тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат физико-математических наук Цибанов, Владимир Николаевич

• Цибанов, Владимир Николаевич
• кандидат физико-математических наук
• 2008

Оглавление диссертации кандидат физико-математических наук Цибанов, Владимир Николаевич

Введение

1 Фильтрация и выделение контуров объектов на изображениях на основе метода регуляризации Тихонова

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

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

1.3 Сравнение методов регуляризации Тихонова с различными видами стабилизаторов

2 Обработка изображений на основе метода квазирешений

2.1 Постановка задачи и численный метод.

2.2 Применение метода квазирешений для обработки изображений

2.2.1 Задача подавления шума.

2.2.2 Задача устранения эффекта Гиббса.

2.2.3 Задача восстановления смазанных изображений

2.2.4 Задача увеличения изображений.

3 Программная реализация регуляризирующих методов обработки изображений

3.1 Структура классов реализующей программы.

3.2 Диаграмма состояний.

3.3 Описание интерфейса и внешний вид программного комплекса

Введение диссертации (часть автореферата) на тему «Регуляризирующие методы фильтрации и восстановления изображений»

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

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

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

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

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

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

Основные результаты диссертации докладывались на международных конференциях "Graphicon" в 2003, 2004, 2006 годах, на открытом немецко-российском семинаре "Распознавание образов и понимание изображений" в 2007 году, на заседании кафедры математической физики факультета ВМиК МГУ им. М.В. Ломоносова в 2007 году.

По теме диссертации опубликовано пять научных работ и одна принята к печати.

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

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

Az = и, z е Z, и eU, (1) где Z и U нормированные пространства.

В качестве оператора А, как правило, рассматривают интегральный оператор Фредгольма:

Az)(x,y) = J K(x,^y,r})z(^r])d^dr}, (2) Е где Е — обозначает прямоугольную область в В2.

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

У)v) = к(х

В зависимости от типа искаженности наблюдаемого изображения используют различные виды ядер К(х,у) (см. например [1, 2]), наиболее распространенными из которых являются:

1. Смазаность изображения: **+«*)

К(х, у) = ке^ 2"'2 здесь к - нормирующая константа, а - параметр, определяющий степень размытости изображения.

2. Дефокусировка изображения: К(х,у) = < если \Jx2 + у2 < R,

7TKZ

О, в противном случае, где R - радиус дифракционного круга.

Для вполне непрерывного интегрального оператора А задача (1) является некорректно поставленной [3, 4].

Напомним, что согласно Адамару задача (1) называется корректной, или корректно поставленной, если выполнены два условия: a) уравнение (1) разрешимо для любого и G U единственным образом; b) решение уравнения (1) устойчиво относительно возмущения правой части уравнения, т.е. оператор А~1 определен на всем пространстве U и является непрерывным.

В том случае, если нарушается одно из данных условий задача является некорректно поставленной.

Для решения некорректных задач требуется разработка специальных методов их решения. В этом случае, если вместо точной правой части уравнения (1) й, соответствующей неизвестной искомой функции z, задано его приближенное значение щ такое, что ||й — и$\\и <5, то в качестве приближенного решения нельзя брать функцию являющуюся решением уравнения Az = щ. Это связано с тем, что решение z$ может не существовать, в случае нарушения первого условия корректности по Адамару, либо не стремиться к точному решению z при 5 —» 0. В таких случаях для построения приближенного решения необходимо использовать регуляризирующие методы [3].

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

Метод регуляризации А.Н. Тихонова

В методе регуляризации Тихонова в качестве устойчивого приближенного решения уравнения (1) za G Z берется функция, минимизирующая следующий функционал:

Ma(z) = \\Az-us\\2+ atl{z), (3) здесь а - положительный регуляризирующий параметр,

Q(z) - неотрицательный стабилизирующий функционал.

Определение. Неотрицательный функционал Vl{z), определенный на всюду плотном в Z подмножестве Z С Z, называется стабилизирующим функционалом, если [3]:

1. Элемент z принадлежит области определения функционала Q(z).

2. Для любого числа с > 0 множества Ос = {z : z £ Z, О(z) < с} являются компактными множествами в пространстве Z.

Определение. Будем говорить, что неотрицательный функционал О(z), определенный на множестве Z С Z, порождает метризацию множества Z с мажорантной метрикой pi(-, •), если на элементах z G Z функционал II^Hj = обладает свойствами нормы, причем для любых z\, Z2 из Z

Pi{zi:z2) = \\zi - z2\\1 > p{z1,z2) = \\zi - z2\\z.

Пусть Z\ — пространство с такой метрикой на множестве Z. Пространство Z\ будем называть пространством, порожденным функционалом ад.

А.Н. Тихоновым была сформулирована теорема сходимости, основанная на идее компактного вложения. Рассмотрим вариант этой теоремы [5].

Теорема (сходимости). Пусть А : Z —» U является непрерывным оператором. Тогда если стабилизирующий функционал является слабо полунепрерывным снизу функционалом относительно нормы гильбертова пространства Z\, то задача нахождения минимума функционала Тихонова разрешима и при выборе параметра а(5) таким образом, что Лтт < С, с > 0, —> 0 при 5 —> 0 наблюдается сходимость приближенного решения к точному по норме пространства Z: lim IIza — zsII7 = 0.

Условиям данной теоремы удовлетворяет, например, следующее задание регуляризирующего метода: mm m{\\Az-us\\l2 + a\\z\\2W2n:zeW?}.

Z = С [a, b], U = L2 [а, Ь]. Пространство Z\ = Wp [a, b] - является пространством Соболева с нормой ь 2 \z(t)\2dt+ f *<">(*) J a J a dt.

Отметим, что при использовании стабилизирующего функционала, равного квадрату нормы элемента z в гильбертовом пространстве Z, множества Ос являются слабо компактными. Поэтому для построения приближенного решения устойчивого к малым изменениям правой части выбор параметра а(5) необходимо проводить таким образом, что ^ - 0, а(6) 0 при 6-* 0 [4].

Выбор параметра регуляризации

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

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

Для решения данной задачи обычно применяется принцип невязки.

Выбор параметра регуляризации по невязке

Впервые принцип невязки был предложен В.А. Морозовым в работах [6, 7] и впоследствии был расширен А.В. Гончарским, А.С. Леоновым и А.Г. Яголой [8, 9] на случай приближенно заданного оператора А.

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

Будем рассматривать задачу восстановления неизвестной исходной функции z £ IV2 [а, Ь], исходя из заданного приближения щ £ Z^a, 6]. Для сглаживания наблюдаемой функции щ мы находим функцию иа, минимизирующую функционал Тихонова:

12 z г G W2n, (4) l2

Ea[z] = Ik- u6\\b2 + a где a > 0 — параметр регуляризации.

Отметим, что вопросы существования решения задачи (4), его единственности и сходимости регуляризированного решения к точному по норме пространства рассматриваются в общем виде в монографии В.А. Морозова [10].

Обозначим за ip(ot) функцию равную невязке уравнения (1). ср{а) = \\za -щ\\2 , где - функция, минимизирующая функционал Тихонова (4).

Согласно принципу невязки, оптимальное значение параметра регуляризации а* определяется из уравнения: р{а) = б2

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

В рассматриваемом случае <р{а) является непрерывной монотонно возрастающей функцией [10]. Поэтому параметр а можно определить, исходя из значения числа 5, характеризующего погрешность исходных данных.

При этом, согласно теоремам, доказанным для более общего случая в монографии [10], построенное таким образом приближенное решение zQ((j) сходится к точному z при 5 —0 по метрике пространства Wg

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

Используются следующие методы:

• Метод L-кривой [11];

• Метод GCV (Generalized Cross Validation) [12];

• Метод максимального правдоподобия [13].

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

Применение метода Тихонова в задачах обработки изображений.

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

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

Ea{z) = J [{Az - и6f + a ■ uj (\Vzfydx, (5) где £ - обозначает прямоугольную область в R2.

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

На практике используются следующие виды функций со [15]:

Стабилизатор w(t) u/{t) Выпуклость

Тихонова t 1 Да

Полной вариации [16] Vt 1 Да

Бауман и Сауер [17] ta 0.5 < a < 1 ata 0.5 < a < 1 Да

Ю и Кавех [18] (~.при t<T 1, при t > T где T задаваемое j^,npHt<T 0, при t > T пороговое значение Да

Перона и Малик [19] 1-е-4 Нет

Геман и МакКлури [20] e 1+t2 l (i+t)2 Нет

Герберт и Леаши [21] log(l + t) 2 1+t Нет

Грип [22] log [ch(Vi)} th(Vt) 2 уД Да

Гипер поверхности [23] y/l+t-1 1 2 VT+i Да

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

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

Если функция и) дифференцируемая, тогда функция za, минимизирующая функционал Еа(и), удовлетворяет уравнению Эйлера:

Уравнение Эйлера используется для построения численного решения задачи минимизации функционала (5). Как правило, используется метод переменных направлений. Общая схема численного решения уравнения (6) для единичного оператора А предложена в статье [27].

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

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

Пусть функция lo удовлетворяет следующим ограничениям:

• - непрерывна на любом компакте К С [0, оо);

• w(|.(2) : —* 3? - выпуклая функция;

• возрастает на [0, сю);

• существует константа е > 0 такая, что cj(s2) > es1.

6)

Теорема 1 (Корректность и регулярность). Пусть щ Е L°°(E). Тогда в пространстве Соболева Н1(Е) функционал Ea(z) достигает своей нижней грани на единственном элементе zQ. Причем, za Е H2(Ti) и || Ц^г^) непрерывно зависит от а.

Метод невязки

Важной разновидностью вариационных регуляризирующих методов является метод невязки [29], предложенный Д.Л. Филипсом [30].

В данной модели приближенное решение z§ Е Z строится как функция, минимизирующая стабилизирующий функционал О(г) и удовлетворяющая следующему ограничению \\Az — щ||2 < 52, где 8 > 0 - фиксированная константа.

Т.е. приближенное решение zs Е Z является решением следующей задачи: найти inf при \\Az — щ||2 < 52 для заданных и§ Е U, z€Z

6> 0.

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

В работе Рудина, Ошера и Фатеми [16] рассматривалась задача определения функции с минимальной вариацией ^f \Vz\ dx —> inf^ среди функций, удовлетворяющих следующим ограничениям: f Azdx = f щйх

Е Е и f\Az- щ\2 dx = 52. Е

В данной постановке первое ограничение соответствует предположению о равенстве нулю среднего значения уровня шума. Второе - задает равенство стандартного отклонения уровня шума значению 5.

Однако, постановка задач обработки изображений в данном виде не удобна для численной реализации. Поэтому в большинстве работ рассматривается эквивалентная [31] задача минимизации функционала (3) с функцией u)(t) = \fi.

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

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

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

Метод квазирешений

Метод квазирешений был предложен В.К. Ивановым [32, 33, 34]. Данный метод заключается в поиске на компактном множестве элемента, минимизирующего невязку операторного уравнения (1).

Пусть точное решение уравнения z принадлежит множеству М, которое является компактом в пространстве Z. В данном случае, если правая часть уравнения и принадлежит множеству N = AM, то для построения устойчивого к малым изменениям правой части и приближенного решения возможно использование формулы: z — А~1и.

Обоснованием подобного подхода является следующая теорема (см. например, [4]).

Теорема. Пусть множество М нормированного пространства Z взаимно однозначно отображается оператором А на множество N нормированного пространства U. Тогда, если оператор А непрерывен наМиМ - компакт, то обратный оператор А~1 непрерывен на N.

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

Для устранения данных затруднений В.К. Ивановым было предложено понятие квазирешения.

Определение. Квазирешепием уравнения (1) называется элемент z^, минимизирующий невязку \\Az — и|| на компактном множестве М. zK = arg inf \\Az - u\\ . (7) z£M

При предположении непрерывности оператора А, невязка уравнения \\Az — ii|| является непрерывным функционалом, который достигает своей нижней грани на компакте М. Таким образом, квазирешение существует, вообще говоря, не единственное для любого и G U. Множество квазирешений уравнения (1) на компакте М, соответствующих элементу щ, будем обозначать через Z5K.

Рассмотрим вопрос о применении метода квазирешений для решения уравнения (1) с приближенно заданной правой частью.

Теорема. [4] Пусть А : Z —> U - непрерывный оператор, отображающий линейное нормированное пространство Z в линейное нормированное пространство U. Пусть для точной правой части й уравнение (1) имеет единственное решение z, принадлежащее компакту М. Тогда sup \\z — z|| —0, при ||щ — й\\ —» 0. zezsK

Таким образом, задача определения квазирешения на компактном множестве является корректной.

Отметим также, что в том случае если при решении уравнения (1) известна оценка величины погрешности правой части 5 : 5 > Цг^ — й||, то для построения устойчивого к малым изменениям правой части и приближенного решения нет необходимости находить квазирешение уравнения. В качестве приближенного решение z$ можно использовать любой элемент множества Zj^ = Zjp|M, где — {z : \\Az — u<j|| < 5}, поскольку при 5 —> 0 sup \\z — z\\ —> 0 [4].

Согласно определению стабилизирующего функционала для любого числа с > 0 множество Qc = |z : z 6 Z, Q,{z) < cj компактно на Z. Поэтому постановку метода квазирешений можно изложить в виде минимизации функционала невязки ||v4z — м<$|| при ограничении на значение стабилизирующего функционала < /л.

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

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

Метод Тихонова

Найти inf |||Az — uj||2 + aft(z)| для заданных и$ € U, а > 0.

Метод невязки

Найти inf при \\Az — щ\\2 < S2 для заданных € U, 5 > 0.

Метод квазирешений

Найти inf |\\Az — щ\\21 при < /i для заданных щ £ U, [1> 0.

Пусть А является линейным оператором и стабилизирующий функционал £7(z) обладает следующими свойствами:

1. £7(;z) - выпуклый функционал;

2. £}(0) = 0; '

3. Для любого фиксированного элемента z £ Z, z ^ 0 функция j(/3) = £7(/?z) - строго возрастающая функция параметра j3 такая, что lim j(j3) = +оо.

3—»+оо

При данных ограничениях на стабилизирующий функционал f2(z) и оператор А, в работе [37] была доказана эквивалентность данных методов. В том смысле, что параметру регуляризации одного метода (скажем 5* в методе Филипса) соответствуют значения параметров других методов (а* и /л*) такие, что решения регуляризирующих методов при данных параметрах совпадают.

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

Задача выделения контуров объектов на изображении

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

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

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

Наиболее часто используемой является модель " ступенчатый контур" (рис. 1). Данная модель описывает резкий перепад функции яркости изображения, соответствующий контурам объектов, который возникает из-за разницы средних уровней яркости фона и объекта.

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

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

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

В настоящее время для нахождения контуров объектов используются три основных группы методов (детекторов):

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

2. Детекторы, использующие "коэффициент совпадения с шаблоном" [38, 39]. Как следует из названия, решение о наличии элемента делается на основании значения коэффициента совпадения с шаблоном. Осуществляется свертка изображения с набором масок, каждая из которых ориентирована в своем направлении. Если отклик на фильтрацию маской достаточно существенен, то считается, что контур найден, и направление этой маски наилучшим образом характеризует его направление.

3. Детекторы, использующие статистические методы [40, 41]. Данные методы обнаруживают контуры объектов, используя статистические гипотезы. Причём, наличие контура зависит как от статистики фильтров, свидетельствующих о наличии контура, так и от статистики фильтров, свидетельствующих об отсутствии контура (это позволяет, например, не выделять элементы текстуры).

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

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

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

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

I. Методы подавления шума

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

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

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

Свертка с функцией Гаусса соответствует линейному диффузионному процессу [45].

Для любой / £ C(R2) линейный диффузионный процесс:

Возможность использования нелинейных методов анизотропной диффузионной фильтрации, позволяющих проводить сглаживание, не устраdtu = Аи и(х, 0) = /(яг) имеет единственное решение: няющее контуры объектов на изображении, явилось причиной частого использования данных методов [19, 46].

В последнее время для сглаживания изображений широкое распространение получили регуляризирующие методы [1, 2, 15].

II. Методы выделения контуров

Проиллюстрируем задачу выделения резких перепадов в одномерном случае. На рисунке 1а представлен одномерный сигнал /(£), содержащий, так называемый, "ступенчатый контур". fro а) Исходный сигнал

-- Порог

Контур

Ь) Первая производная от функции сигнала d2m

Контур У

Нули второй производной с) Вторая производная от функции сигнала Рис. 1: Зашумленный 1-D контур и его первая и вторая производные

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

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

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

Контрастные перепады на изображении находятся в точках локального максимума модуля градиента |V/(x, у) | функции яркости. Поэтому довольно часто для определения контуров объектов используют некоторое пороговое значение, с которым сравнивают длину вектора градиента.

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

Применение детекторов, выделяющих точки контура при превышении значения модуля градиента порогового значения, довольно широ

-1 01 о 1;

0 -1

1 0 ,

-1 -1 -1

000

1 1 1

1-Х о Л

-10 1 -1 0 1

Маска Робертса

Маска Превита и -2 -Л

000

1 2 1

-1 о Л -2 0 2 -1 0 1

Маска Собеля

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

Фильтр Канни

Условием контура в одномерном случае является равенство нулю второй производной. Аналогичным критерием в двумерном пространстве является равенство нулю второй производной от функции яркости изображения по направлению п [49, 50]: дп2

1(х,у) = 0, где 1{х, у) - функция яркости сглаженного изображения, п - вектор, ориентированный в направлении ортогональном контуру.

Поскольку это направление не известно a priori, оно аппроксимируется направлением градиента. п ~ —-г, где V = (—, —).

V(/) д дп дх' ду'

Отметим, что при таком выборе вектора п, производная 1(х,у) = VI(x, у) . Таким образом, нахождение второй производной от функции яркости изображения совпадает с определением экстремального значения модуля градиента \\71(х,у)\ по направлению п.

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

Отметим, что в дискретном случае определяется не ноль оператора второго порядка, а переход через ноль.

Фильтр Марра и Хилдрета

Другой подход был предложен Марром и Хилдретом [51]. В своей работе они рассматривали детектор, не зависящий от направления и основанный на определении нулевых значений оператора Лапласа, примененного к сглаженному изображению.

Лапласиан и вторая производная по направлению градиента являются операторами второго порядка. Отметим, что представленная в работе [52] связь данных операторов, позволяет заключить, что результат выделения контуров двух рассмотренных детекторов второго порядка совпадает на контурах нулевой кривизны.

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

Так Марром и Хилдретом [51] для обнаружения нулей оператора Лапласа от сглаженной функции яркости изображения было предложено использовать свертку исходной функции яркости с Лапласианом от Гаус-сиана: 1

LoG(x,y) =

7га4 х2 + у2 е 2сг

2а2

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

В статьях [53] рассматривается применение для выделения контуров изображений коэффициентов разложения в ряд по полиномам степени п. В работе [54] предложено применение для выделения контуров изображений коэффициентов разложения в ряд Эрмита функции яркости исходного зашумленного изображения.

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

III. Методы разметки контуров

Наиболее распространенные детекторы контуров используют равенство нулю дифференциального оператора второго порядка и условие превышения модуля градиента заданного порога.

Однако, на зашумленных изображениях значение модуля градиента может сильно меняться на протяжении контура, создавая тем самым проблему пунктирных линий ('streaking' problem). Для преодоления данной сложности Канни [49] был предложен метод применения порогов с гистерезисом. Изначально выбираются два порога (Ti > Т2). Данные два порога используются для классификации контуров на два класса: "сильных" и "слабых" контуров. Слабые одиночные импульсы обычно соответствуют шуму и поэтому отбрасываются. Но если такие точки соединены с пикселами, имеющими большое значение "интенсивности" контура, то велика вероятность, что эти точки принадлежат какому-то контуру. Таким образом, "слабые" контуры отмечаются в результирующем изображении, только если они соединены с "сильными".

Заключение диссертации по теме «Математическое моделирование, численные методы и комплексы программ», Цибанов, Владимир Николаевич

Заключение

В диссертационной работе были получены следующие основные результаты:

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

2. Предложен и программно реализован регуляризирующий метод для выделения контуров объектов на зашумленных фотографиях.

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

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

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

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

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

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

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

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

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

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

Список литературы диссертационного исследования кандидат физико-математических наук Цибанов, Владимир Николаевич, 2008 год

1. Banham M.R., Katsaggelos А.К. Digital image restoration // 1.EE Signal Processing Magazine - 1997 - vol. 14, № 2, pp. 24-41.

2. Гончарский А.В., Кочиков И.В., Матвиенко А.Н. Реконструктивная обработка и анализ изображений в задачах вычислительной диагностики. М.: Изд-во МГУ, 1993.

3. Тихонов А.Н., Арсенин В.Я. Методы решения некорректных задач. М.: Наука, 1979.

4. Денисов A.M. Введение в теорию обратных задач. М.: МГУ, 1994.

5. Vasin V. V. Some tendencies in the Tikhonov regularization of ill-posed problems // J. Inv. Ill-Posed, Problems 2006 - vol. 14, № 8, pp. 813840.

6. Морозов В.А. О выборе параметра при решении функциональных уравнений методом регуляризации // ДАН СССР 1967 - т. 175, № 6, с. 1225-1228.

7. Морозов В.А. О принципе невязки при решении операторных уравнений методом регуляризации // ЖВМиМФ 1968 - т. 8, № 2, с. 295-309.

8. Гончарский А.В., Леонов А.С., Ягола А.Г. Некоторое обобщение принципа для случая оператора, заданного с ошибкой // ДАН СССР 1972 - т. 203, № 6, с. 1238-1239.

9. Гончарский А.В., Леонов А-С., Ягола А.Г. Обобщенный принцип невязки // ЖВМиМФ 1973 - т. 13, № 2, с. 294-302.

10. Морозов В.А. Регулярные методы решения некорректно постав-леннных задач. М.: Наука, 1987.

11. Hansen Р. С. Analysis of discrete ill-posed problems by means of the L-curve // SI AM Review 1992 - № 34, pp. 561-580.

12. Nguyen N., Milanfar P. Efficient generalized cross-validation with applications to parametric image restoration and resolution enhancement // IEEE Trans, on Image Proc. 2001 - vol. 10, № 9, pp. 1299-1308.

13. Wahba G. A comparison of GCV and GML for choosing the smoothing parameter in the generalized spline smoothing problem // Annals of Statistics 1985 - vol. 13, № 4, pp. 1378-1402.

14. Леонов А.С., Ягола А.Г. Можно ли решить некорректную задачу без знания погрешности данных? // Вестник Московского университета, сер. 3, Физика, Астрономия 1995 - т. 36, № 4, с. 28-33.

15. Teboul S., Blanc-Feraud L., Aubert G., Barlaud M. Variational approach for edge-preserving regularization using coupled PDE's // Trans, on Image Proc. 1998 - vol. 7, № 3, pp. 387-396.

16. Rudin L., Osher S.J., Fatemi E. Nonlinear total variation based noise removal algorithms // Physica D- 1992 № 60, pp. 259-268.

17. Воитап С., Sauer К. A generalized Gaussian image model for edge-preserving MAP estimation // IEEE Trans, on Image Proc. 1993 -vol. 2, pp. 296-310.

18. You Y.-L., Kaveh M. Ringing reduction in image restoration by orientation-selective regularization // IEEE Signal Processing Letters 1996 - vol. 3, № 2, pp. 29-31.

19. Perona P., Malik J. Scale Space and edge detection using anisotropic diffusion // IEEE Trans, on PAMI 1990 - № 12, pp. 629-639.

20. Geman S., McClure D.~E. Bayesian image analysis: An application to single photon emission tomography," in Proc. Stat. Comput. Sect. Washington, DC: Amer. Stat. Assoc., 1985, pp. 12-18.

21. Hebert Т., Leahy R. A generalized EM algorithm for 3-D Bayesian reconstruction from Poisson data using Gibbs priors // IEEE Trans. Med. Imag 1989 - vol. 8, pp. 194-202.

22. Green P.-J. Bayesian reconstruction from emission tomography data using a modified EM algorithm j j IEEE Trans. Med. Imag 1990 -vol. 9, pp. 84-93.

23. Charbonnier P., Blanc-Fferaud L., Aubert G., Barlaud M. Deterministic edge-preserving regularization in computed imaging // IEEE Trans. Image Processing 1997 - vol. 7, № 3, pp 387-396.

24. Acar R., Vogel C.R. Analysis of total variation penalty methods // Inverse Problems 1994 - vol. 10, pp.1217-1229.

25. Chan T.F., Esedoglu S.} Park F., Yip A. Recent Developments in Total Variation Image Restoration. In "Handbook of Mathematical Modelsin Computer Vision". Springer Verlag, 2005. Edt. by: N. Paragios, Y. Chen, O. Faugeras.

26. Chan T.F., Shen J. On the Role of the BV Image Model in Image Restoration // Amer. Math. Soc. Contemporary Mathematics, volume on Computational PDEs and Image Processing, accepted, 2002.

27. Weickert J. Applications of nonlinear diffusion in image processing and computer vision // J. of Math. Imaging and Vision 1994 - № 1, pp. 43-63.

28. Scherzer 0., Weickert J. Relations between regularization and diffusion filtering // J. of Math. Imaging and Vision 2000 - № 12, pp. 43-63.

29. Иванов В.К. О приблиденном решении операторных уравнений первого рода // ЖВМиМФ. 1966. Т. 6. № 6. С. 1089-1093.

30. Phillips D.L. A technique for numerical solution of certain integral equations of the first kind II J. Assoc. Comput. Math. 1962 - vol. 9, pp. 84-97.

31. Chambolle A., Lions P. Image Recovery via Total Variation Minimization and Related Problems // Numer. Math. 1997 - № 76, pp. 167 - 188.

32. Иванов В.К. О линейных некорректных задачах // ДАН СССР -1962 т. 145, с. 270-272.

33. Иванов В.К. О некорректно поставленных задачах // Математический сборник 1963 - т. 61, с. 211-223.

34. Иванов В.К., Васин В.В., Танана В.П. Теория линейных некорректных задач и ее приложения М.: Наука, 1978.

35. Тихонов А.Н., Гончарский А.В., Степанов В.В., Ягола А.Г. Регу-ляризирующие алгоритмы и априорная информация М.: Наука, 1983.

36. Тихонов А.Н., Гончарский А.В., Степанов В.В., Ягола А.Г. Численные методы решения некорректных задач М.: Наука, 1990.

37. Васин В. В. О связи некоторых вариационных методов приближенного решения некорректных задач // Математические заметки -1970 т. 7, №3, с. 265 - 272.

38. Davis Е. Machine Vision: Theory, Algorithms, Practicalities. San Diego: Academic Press, 1996.

39. Nayar S.K., Baker S., Murase H. Parametric feature detection // In Proc. of IEEE Conf. on Computer Vision and Pattern Recognition, San Francisco, 1996.

40. Field D.J. Relations between the Statistics and Natural Images and the Responses Properties of Cortical Cells // J. Optical Soc. Am. 1987 -vol. A, № 4, pp. 2379-2394.

41. Konishi S., Yuille A.L., Coughlan J.M. A Statistical Approach to MultiScale Edge Detection // In Proc. Workshop Generative-Model-Based Vision: GMBV '02, 2002.

42. Torre V., Poggio T. A. On edge detection // IEEE Trans, on PAMI -1986 № 8, pp. 147-163.

43. Малла С. Вэйвлеты в обработке сигналов. М.: Мир, 2005.

44. Krylov A.S., Kortchagine D.N. Projection filtering in image processing //In Proc. Int. Conf. "Graphicon 2000", Moscow, 2000, pp. 42-45.

45. Тихонов А.Н., Самарский А.А. Уравнения математической физики. М.: Наука, 1977.

46. Weickert J. Anisotropic Diffusion in Image Processing. Stuttgart: Teubner-Verlag, 1998.

47. Дуда P., Xapm 77. Распознавание образов и анализ сцен. М.: Мир, 1976.

48. Прэтт У. Цифровая обработка изображений. М: Мир, 1982.

49. Canny J. A computational approach to edge detection // IEEE Trans, on PAMI 1986 - vol. 8, №6, pp. 679 - 698.

50. Haralick R.M. Digital step edges from zero-crossings of second directional derivatives // IEEE Trans, on PAMI 1984 - № 6, pp. 132151.

51. Marr D., Hildreth E. Theory of edge detection // Proceedings of the Royal society of London, Series В 1980 - vol. 207, pp. 187 - 217.

52. Ziou D., Tabbone S. Edge detection techniques-an overview // J. of Pattern Recognition and Image Analysis 1998 - Vol. 8, № 4, pp. 537559.

53. Meer P., Weiss I. Smoothed differentiation filters for images // J. of Visual Communication and Image Representation 1992 - № 3, pp. 5872.

54. Крылов А.С., Наджафи M. Проекционный Метод Нахождения Границ Изображений // Труды факультета ВМиК МГУ. Прикладная математика и информатика 2004 — JV2 3, с. 87-94.

55. Сансоне Дж. Обыкновенные дифференциальные уравнения. -М.: Иностранной литературы, 1953.

56. Наймарк М.А. Линейные дифференциальные операторы. М.: Наука, 1969

57. Натансон И.П. Теория функций вещественной переменной. М.: Наука, 1974

58. Колмогоров А.Н., Фомин С.В. Элементы теории функций и функционального анализа. М.: Физматлит, 2006.

59. Васильев Ф.П. Численные методы решения экстремальных задач.- М: Наука, 1980.

60. Turkowski К. Filters for common resampling tasks. In: Graphics Gems.- San Diego:Academic Press Professional, 1990.

61. Yuan S., Abe M., Taguchi A., Kawamata M. High accuracy WaDi image interpolation with local gradient features // Proc. of Int. Symposium on Intelligent Signal Processing and Communication Systems. ISPACS'2005. Hong Kong, 2005. Pp. 85 - 88.

62. Li X., Orchard M.T. New Edge-Directed Interpolation // IEEE Trans, on Image Proc. 2001 - vol. 10, № 10, pp. 1521-1527.

63. Nasonov A., Krylov A.S., Lukin A. Post-processing by Total Variation Quasi-solution Method for Image Interpolation // Proc. of Int. Conf. of Computer Graphics and Vision. "Graphicon'2007", Moscow: MAKS Press, 2007.

64. Lukin A., Krylov A.S., Nasonov A. Image Interpolation by Super-Resolution // Proc. of Int. Conf. of Computer Graphics and Vision. "Graphicon'2006", Novosibirsk, 2006, pp. 239 — 242.

65. Chan T.F., Wong C.K. Total variation blind deconvolution 11 IEEE Transactions on Image Processing 1998 - № 7, pp. 370—375.

66. You Y.-L., Kaveh M. A regularization approach to joint blur identification and image restoration // IEEE Trans. Image Processing 1996 - vol. 5, pp. 416-428.

67. Публикации автора по теме диссертационной работы

68. Цибанов В.П., Крылов А. С. Выделение контуров человеческого тела в ортопедических исследованиях // Материалы Международной конференции по компьютерной графике, машинному зрению, обработке изображений и видео "Графикон'2003", Москва, 2003, с. 250254.

69. Tsibanov V.N., Denisov A.M., Krylov A.S. Edge detection method by Tikhonov regularization // Proceedings of Int. Conf. of Computer Graphics and Vision "Graphicon'2004", Moscow, 2004, pp. 163-165.

70. Denisov A.M., Krylov A.S., Tsibanov V.N. Second order Tikhonov regularization method for image filtering // Proceedings of Int. Conf. of Computer Graphics and Vision "Graphicon'2006", Novosibirsk, 2006, pp. 218-221.

71. Цибанов B.H., Крылов А. С. Применение метода регуляризации Тихонова для выделения контуров изображений // Вестник МГУ, сер.

72. Вычислительная математика и кибернетика 2008 - № 2, с. 1116.

73. Цибанов В.Н., Крылов А. С. Применение регуляризирующего метода квазирешений для подавления эффекта Гиббса на изображениях // Естественные и технические науки 2008 - № 1, с. 306-312.

74. Krylov A.S., Tsibanov V.N., Denisov A.M. Image enhancement by total variation quasi-solution method // Pattern recognition and image analysis 2008 - vol. 18, № 2, pp. 285-288 принята к печати].1. Список иллюстраций

75. Зашумленный 1-D контур и его первая и вторая производные 23

76. Ядро Ga(x, s), -1 < х < 1, -1 < s < 1 . 33

77. Сглаживание одномерных функций при помощи функционала Тихонова со стабилизатором первого порядка . 34

78. Фильтрация изображений при помощи функционала Тихонова со стабилизатором первого порядка. 36

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

80. Применение предложенного сглаживающего метода для выделения контуров. 42

81. Применение предложенного сглаживающего метода для выделения контуров. 43

82. Ядро Gp(x, s), -1 < х < 1, -1 < s < 1. 49

83. Сглаживание одномерных функций при помощи функционала Тихонова со стабилизатором второго порядка . 49

84. Фильтрация изображений при помощи функционала Тихонова со стабилизатором второго порядка. 51in

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

86. Применение предложенного метода сглаживания для выделения контуров. 55

87. Применение предложенного метода сглаживания для выделения контуров. 56

88. Сравнение сглаживающих свойств предложенных методов 58

89. Сравнение результатов фильтрации изображений при помощи предложенных методов. 59

90. Сравнение результатов выделения контуров объектов на изображениях при помощи предложенных методов. 60

91. Подавление шума (априорное задание параметра сглаживания равного значению полной вариации исходной функции) . 68

92. Устранение шума (задание параметра сглаживания С —2С и С = 0.8С).69

93. Устранение шума (задание параметра вариации, равного 0.75 значения полной вариации зашумленной функции) . . 70

94. Применение метода квазирешений для сглаживания изображения, содержащего текст.71

95. Иллюстрация эффекта Гиббса.74

96. Устранение эффекта Гиббса.75

97. Подавление эффекта Гиббса на изображениях.76

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

99. Применение метода квазирешений для восстановления смазанных изображений.

100. Применение метода квазирешений для интерполяции одномерных функций .

101. Схема работы алгоритма увеличения разрешения изображений .

102. Применение метода квазирешений для увеличения разрешения изображений.31 Диаграмма классов.

103. Диаграмма класса CGreylmageCore.

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

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

106. Результаты восстановления смазанного изображения с помощью метода квазирешений.

107. Результаты увеличения разрешения изображения с помощью метода квазирешений .

108. Диаграмма класса CEdgelmage.

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

110. Диаграмма состояний обработки изображений.

111. Внешний вид программы «EdgeDetector».79 8283