Содержание к диссертации
Введение
1 Фильтрация и выделение контуров объектов на изобра жениях на основе метода регуляризации Тихонова 29
1.1 Применение метода регуляризации Тихонова со стабилизатором, содержащим производную первого порядка, для обработки изображений 30
1.2 Применение метода регуляризации Тихонова со стабилизатором, содержащим производную второго порядка, для обработки изображений 44
1.3 Сравнение методов регуляризации Тихонова с различными видами стабилизаторов 57
2 Обработка изображений на основе метода квазирешений 61
2.1 Постановка задачи и численный метод 62
2.2 Применение метода квазирешений для обработки изображений 67
2.2.1 Задача подавления шума 67
2.2.2 Задача устранения эффекта Гиббса 72
2.2.3 Задача восстановления смазанных изображений . 76
2.2.4 Задача увеличения изображений 80
3 Программная реализация регуляризирующих методов об работки изображений 85
3.1 Структура классов реализующей программы 86
3.2 Диаграмма состояний 95
3.3 Описание интерфейса и внешний вид программного комплекса 96
Заключение 99
Библиографический список использованной литературы
- Применение метода регуляризации Тихонова со стабилизатором, содержащим производную второго порядка, для обработки изображений
- Сравнение методов регуляризации Тихонова с различными видами стабилизаторов
- Применение метода квазирешений для обработки изображений
- Диаграмма состояний
Введение к работе
В последнее время одной из наиболее важных областей применения методов математического моделирования и компьютерных технологий является обработка и анализ изображений.
Широкий класс задач обработки изображений требует для своего решения разработки вычислительных методов, обеспечивающих устойчивость получаемых результатов. Примерами таких задач являются фильтрация зашумленных изображений, восстановление смазанных фотоснимков, увеличение разрешения изображений. К этому классу относится и задача выделения контуров объектов на фотографиях, приводящая к некорректно поставленной задаче численного дифференцирования.
Методы, позволяющие добиться требуемой устойчивости результатов обработки изображений, строятся на основе регуляризирующих алгоритмов. Область их применимости, наряду с созданием и модификацией методов регуляризации, постоянно растет.
В связи с этим, разработка регуляризирующих методов фильтрации и восстановления изображений, создание на их основе программного комплекса для решения современных задач обработки и анализа изображений представляет собой важную и актуальную задачу.
Целью диссертационной работы является разработка и программная реализация вариационных регуляризирующих методов решения задач повышения качества фотографий и выделения контуров объектов на за-шумленных изображениях.
В работе рассматривается.применение методов А.Н. Тихонова и квазирешений для обработки изображений. Основная часть данной работы разделена на введение и три главы: обзор регуляризирующих методов обработки изображений и описание задач выделения контуров объектов на изображениях, как предметная область применения методов регуляризации (введение), использование методов регуляризации Тихонова для обработки изображений (первая глава), применение методов квазирешений в задачах подавления шума, удаления эффекта Гиббса, увеличения разрешения зашумленных фотографий и восстановления смазанных изображений (вторая глава), и структура и описание реализующего программного комплекса (третья глава).
Основные результаты диссертации докладывались на международных конференциях "Graphicon" в 2003, 2004, 2006 годах, на открытом немецко-российском семинаре "Распознавание образов и понимание изображений" в 2007 году, на заседании кафедры математической физики факультета ВМиК МГУ им. М.В. Ломоносова в 2007 году.
По теме диссертации опубликовано пять научных работ и одна принята к печати.
В диссертационной работе рассматривается применение методов регуляризации для задач обработки изображений и выделения контуров объектов на фотографиях.
Постановка многих задач обработки изображений в общем виде может быть записана как решение следующего операторного уравнения.
Az = и, z Є Z, и Є U, (1)
где Z и U нормированные пространства.
В качестве оператора А, как правило, рассматривают интегральный оператор Фредгольма:
(Az)(x,y) = J K{x,t,yiTJ)z(t,T,)dtdTi, (2)
где Е — обозначает прямоугольную область в R2.
Во многих случаях оператор А является оператором типа свертки, т.е. ядро оператора А является функцией, зависящей от разности аргументов К{х} , у,г)) = К(х - , у - 77).
В зависимости от типа искаженности наблюдаемого изображения используют различные виды ядер К(х,у) (см. например [1, 2]), наиболее распространенными из которых являются:
1. Смазаность изображения:
К{х,у) = ке(~^\
здесь к - нормирующая константа,
а - параметр, определяющий степень размытости изображения.
——-, если \/х2 + у2 < R,
7TRz
О, в противном случае,
2. Дефокусировка изображения: К(х,у)= <
где R - радиус дифракционного круга.
Для вполне непрерывного интегрального оператора А задача (1) является некорректно поставленной [3, 4].
Напомним, что согласно Адамару задача (1) называется корректной, или корректно поставленной, если выполнены два условия:
уравнение (1) разрешимо для любого и Є U единственным образом;
решение уравнения (1) устойчиво относительно возмущения правой части уравнения, т.е. оператор Л~1 определен на всем пространстве U и является непрерывным.
В том случае, если нарушается одно из данных условий задача является некорректно поставленной.
Для решения некорректных задач требуется разработка специальных методов их решения. В этом случае, если вместо точной правой части уравнения (1) й, соответствующей неизвестной искомой функции z, задано его приближенное значение щ такое, что ||й — щ\\ц < 5, то в качестве приближенного решения нельзя брать функцию z$, являющуюся решением уравнения Az = us- Это связано с тем, что решение z$ может не существовать, в случае нарушения первого условия корректности по Адамару, либо не стремиться к точному решению z при 5 —» 0. В таких случаях для построения приближенного решения необходимо использовать регуляризирующие методы [3].
Для построения регуляризованного решения уравнения (1), устойчивого к малым изменениям правой части, широкое распространение приобрели вариационные регуляризирующие методы.
Метод регуляризации А.Н. Тихонова
В методе регуляризации Тихонова в качестве устойчивого приближенного решения уравнения (1) za Є Z берется функция, минимизирующая следующий функционал:
Ma(z) = \\Az-u5\\2 + an{z), (3)
здесь а - положительный регуляризирующий параметр, П(г) - неотрицательный стабилизирующий функционал. Определение. Неотрицательный функционал fl(z), определенный на
всюду плотном в Z подмножестве Z С Z, называется стабилизирующим
функционалом, если [3]:
Элемент z принадлежит области определения функционала l(z).
Для любого числа с > 0 множества Ос = {z : z Є Z,Q(z) < с} являются компактными множествами в пространстве Z.
Определение. Будем говорить, что неотрицательный функционал Q(z), определенный на множестве Z С Z, порождает метризацию множества Z с мажорантной метрикой р\{-, ), если на элементах z Є Z функционал Ц^ІІ! = Q}l2{z) обладает свойствами нормы, причем для любых z\, 2 из Z
Pi{zi:z2) = \\zi -z2|li > p{zi,zz) = \\Zi - z2\\z.
Пусть Z\ — пространство с такой метрикой на множестве Z. Пространство Z\ будем называть пространством, порожденным функционалом
ад.
А.Н. Тихоновым была сформулирована теорема сходимости, основан-
ная на идее компактного вложения. Рассмотрим вариант этой теоремы [5].
Теорема (сходимости). Пусть Л : Z —> U является непрерывным оператором. Тогда если стабилизирующий функционал l(z) является слабо полунепрерывным снизу функционалом относительно нормы гильбертова пространства Z\, то задача нахождения минимума функционала Тихонова разрешима и при выборе параметра а(5) таким образом, что 4тт < с, с > 0, а(5) —> 0 при 5 —> 0 наблюдается сходимость приближенного решения к точному по норме пространства Z:
lim \\za — zs\\7 = 0. <*->о
Условиям данной теоремы удовлетворяет, например, следующее задание регуляризирующего метода:
{\\Az-uL2 + a\\z\^:ZeW^)
Z = C[a,b], U = Li [a, b]. Пространство Z\ — W^ [a, b] - является пространством Соболева с нормой
dt.
fty= fb\z(t)\2dt+ Ґ z^(t)
J a J a
Отметим, что при использовании стабилизирующего функционала, равного квадрату нормы элемента z в гильбертовом пространстве Z, множества Ос являются слабо компактными. Поэтому для построения приближенного решения устойчивого к малым изменениям правой части выбор параметра а(5) необходимо проводить таким образом, что JL _> о, а(6) -> 0 при 6 -> 0 [4].
Выбор параметра регуляризации
Определение параметра регуляризации является важной задачей при практическом применении методов регуляризации. Неправильный выбор параметра а может приводить к существенным расхождениям между исходным и построенным регуляризированным решением.
Приведенная выше теорема сходимости задает лишь асимптотический порядок убывания параметра а, достаточный для построения регуляри-зирующего алгоритма, так называемый "априорный" метод выбора параметра регуляризации. Однако, при обработке реальных экспериментальных данных приходится решать задачу при конкретном уровне погрешности 5. Таким образом, возникает задача определения единственного значения параметра ос, соответствующего фиксированному уровню погрешности S.
Для решения данной задачи обычно применяется принцип невязки.
Выбор параметра регуляризации по невязке
Впервые принцип невязки был предложен В.А. Морозовым в работах [6, 7] и впоследствии был расширен А.В. Гончарским, А.С. Леоновым и А.Г. Яголой [8, 9] на случай приближенно заданного оператора А.
Приведем описание метода выбора параметра регуляризации по невязке для рассматриваемой далее в работе задачи сглаживания наблюдаемой функции щ.
Будем рассматривать задачу восстановления неизвестной исходной функции z Є W2ra[a, 6], исходя из заданного приближения щ Є Z^fa, 6]. Для сглаживания наблюдаемой функции us мы находим функцию иа, минимизирующую функционал Тихонова:
dn dxn'
Ea[z] = \\z - щ\\2г + а
, zW?, (4)
где a > 0 — параметр регуляризации.
Отметим, что вопросы существования решения задачи (4), его единственности и сходимости регуляризированного решения к точному по норме пространства W% рассматриваются в общем виде в монографии В.А. Морозова [10].
Обозначим за р((х) функцию равную невязке уравнения (1).
ср(а) = \\га-щ\\2,
где za - функция, минимизирующая функционал Тихонова (4).
Согласно принципу невязки, оптимальное значение параметра регуляризации а* определяется из уравнения:
Смысл данного уравнения заключается в том, что в качестве а* выбирается значение, при котором невязка решения (р(а) выходит на уровень погрешности правой части 5.
В рассматриваемом случае <р(а) является непрерывной монотонно возрастающей функцией [10]. Поэтому параметр а можно определить, исходя из значения числа 5, характеризующего погрешность исходных данных.
При этом, согласно теоремам, доказанным для более общего случая в монографии [10], построенное таким образом приближенное решение zQ($) сходится к точному z при 5 —-> 0 по метрике пространства Wg-
Применение принципа невязки требует наличия информации о погрешности исходных данных 5. Данная информация не всегда может быть доступна при обработке реальных данных. Поэтому в последнее время были предложены методы построения приближенного решения, не зависящего от оценок погрешности б.
Используются следующие методы:
Метод L-кривой [11];
Метод GCV (Generalized Cross Validation) [12];
Метод максимального правдоподобия [13].
Однако, выбор параметра регуляризации, не зависящего от оценок погрешности S, не позволяет построить регуляризирующий алгоритм [14], т.е. решение, построенное таким методом, не сходится к точному при стремлении уровня погрешности 5 к нулю. Более того, в работе [14] приводится пример отсутствия сходимости построенного при помощи метода L-кривой приближенного решения к точному, даже в случае корректно поставленной задачи. Поэтому указанные выше методы не использовались в данной работе.
Применение метода Тихонова в задачах обработки изображений.
Методы регуляризации, разработанные для решения неустойчивых задач, в настоящее время стали одним из основных подходов при решении широкого класса задач восстановления и фильтрации изображений.
Типичные вариационные методы, применяемые для восстановления изображений, получают приближенную версию некоторого искаженного
изображения us, как функцию za, минимизирующую следующий функционал:
Ea{z) = /[(Аг - щ)2 + а-и (, (5)
где Е - обозначает прямоугольную область в R2.
Параметр а контролирует баланс между мерой несовместности полученного решения уравнения с наблюдаемыми данными и его гладкостью.
На практике используются следующие виды функций со [15]:
Таблица 1: Виды стабилизирующих функционалов, используемых в задачах обработки изображений
Отметим, что большая часть указанных функций не являются выпуклыми, и в данном случае применение функционала (5) не приводит к корректно поставленной задаче. Однако, использование данных функций при обработке изображений приводит к хорошим результат, что обуславливает их применение. При этом наибольшее распространение приобрели метод Тихонова, приводящий к квадратичному функционалу, и
метод полной вариации [16, 24, 25, 26], используемый при восстановлении разрывных решений.
div U (|V.z|2) Vz\ . (6)
Если функция uj дифференцируемая, тогда функция za, минимизирующая функционал Еа(и), удовлетворяет уравнению Эйлера: A*Az - А*щ
Уравнение Эйлера используется для построения численного решения задачи минимизации функционала (5). Как правило, используется метод переменных направлений. Общая схема численного решения уравнения (6) для единичного оператора А предложена в статье [27].
Отметим, что метод регуляризации Тихонова используется не только для восстановления изображений, но и для решения задач фильтрации зашумленных изображений. В данном случае оператор А является единичным и функционал Тихонова принимает вид:
Ea(z)= (z ~ щ)2 + а и) (\Vzf\ dx.
При указанных ниже ограничениях на функцию и) в работе [28] доказываются теоремы, обуславливающие возможность построения приближенного решения, устойчивого к малым изменениям наблюдаемой функции, и применимость данного подхода к задачам фильтрации изображений.
Пусть функция uj удовлетворяет следующим ограничениям:
и>(.) - непрерывна на любом компакте К С [0, со);
cj(|.(2) : 3J" —» 3 - выпуклая функция;
и>(.) возрастает на [0, со);
существует константа є > 0 такая, что tu(s2) > es1.
Теорема 1 (Корректность и регулярность). Пусть щ Є L(I]).
Тогда в пространстве Соболева Я^Е) функционал Ea(z) достигает своей нижней грани на единственном элементе za. Причем, za Є Н2(Е) и Ц^аЦ^г^) непрерывно зависит от а.
Метод невязки
Важной разновидностью вариационных регуляризирующих методов является метод невязки [29], предложенный Д.Л. Филипсом [30].
В данной модели приближенное решение z Є Z строится как функция, минимизирующая стабилизирующий функционал Q(z) и удовлетворяющая следующему ограничению \\Az — щ\\ < 52, где 5 > 0 - фиксированная константа.
Т.е. приближенное решение zs Є Z является решением следующей задачи: найти inf {Q,(z)} при ||Az — щ\\" < 52 для заданных us Є U, 5>0.
Данная постановка вариационных регуляризирующих методов также используется в задачах обработки изображений.
В работе Рудина, Ошера и Фатеми [16] рассматривалась задача определения функции с минимальной вариацией ( J \Wz\ dx —> inf ] среди функций, удовлетворяющих следующим ограничениям: f Azdx = f щ<1х
Е Е
и f\Az-u6\2dx = S2.
В данной постановке первое ограничение соответствует предположению о равенстве нулю среднего значения уровня шума. Второе - задает равенство стандартного отклонения уровня шума значению 5.
Однако, постановка задач обработки изображений в данном виде не удобна для численной реализации. Поэтому в большинстве работ рас-
сматривается эквивалентная [31] задача минимизации функционала (3) с функцией co(t) = у/І.
Недостатком рассмотренных выше регуляризирующих методов является необходимость задания априорной информации об уровне погрешности правой части (в явном виде в методе невязки и в косвенном -для выбора параметра регуляризации в методе регуляризации Тихонова). Однако, данная информация не всегда может быть доступна при обработке реальных данных.
При этом использование неверных оценок приводит к неудовлетворительным результатам. Применительно к обработке изображений неверное задание оценки уровня зашумленности изображения ведет либо к пересглаживанию фотографии, либо недостаточному устранению шума.
В некоторых случаях от задания оценки погрешности правой части можно отказаться. Это верно в том случае, когда априори известно, что точное решение задачи принадлежит некоторому компактному множеству. Данное предположение используется в методе квазирешений.
Метод квазирешений
Метод квазирешений был предложен В.К. Ивановым [32, 33, 34]. Данный метод заключается в поиске на компактном множестве элемента, минимизирующего невязку операторного уравнения (1).
Пусть точное решение уравнения z принадлежит множеству М, которое является компактом в пространстве Z. В данном случае, если правая часть уравнения и принадлежит множеству N = AM, то для построения устойчивого к малым изменениям правой части и приближенного
решения возможно использование формулы:
z — А~1и.
Обоснованием подобного подхода является следующая теорема (см. например, [4]).
Теорема. Пусть множество М нормированного пространства Z взаимно однозначно отображается оператором А на множество N нормированного пространства U. Тогда, если оператор А непрерывен на, М и М - компакт, то обратный оператор А~1 непрерывен на N.
Однако, хотя точное значение правой части й, соответствующее решению уравнения z, принадлежит множеству N, ее приближенное значение us может не принадлежать данному множеству. Кроме того, как правило, не существует эффективных критериев, позволяющих установить принадлежности элемента us множеству N.
Для устранения данных затруднений В.К. Ивановым было предложено понятие квазирешения.
Определение. Квазирешением уравнения (1) называется элемент zk, минимизирующий невязку \\Az — u|| на компактном множестве М.
zK = arg inf ||Az-u|| . (7)
При предположении непрерывности оператора А, невязка уравнения \\Az — и\\ является непрерывным функционалом, который достигает своей нижней грани на компакте М. Таким образом, квазирешение существует, вообще говоря, не единственное для любого и Є U. Множество квазирешений уравнения (1) на компакте М, соответствующих элементу ug, будем обозначать через Z5K.
Рассмотрим вопрос о применении метода квазирешений для решения уравнения (1) с приближенно заданной правой частью.
Теорема. [4] Пусть A : Z —> U - непрерывный оператор, отображающий линейное нормированное пространство Z в линейное нормированное пространство U. Пусть для точной правой части й уравнение (1) имеет единственное решение z, принадлежащее компакту М. Тогда sup \\z — z\\ —> 0, при \\щ — й\\ —» 0. zezK
Таким образом, задача определения квазирешения на компактном
множестве является корректной.
Отметим также, что в том случае если при решении уравнения (1) известна оценка величины погрешности правой части 5 : 5 > \\и* — й\\, то для построения устойчивого к малым изменениям правой части и приближенного решения нет необходимости находить квазирешение уравнения. В качестве приближенного решение zx можно использовать любой элемент множества Z^ = Zxf~\M, где Zx = {z : \\Az — щ\\ < 5}, поскольку при 5 —» 0 sup \\z — z\\ —* 0 [4].
zez5M
Согласно определению стабилизирующего функционала для любого
числа с > 0 множество Qc =
Метод квазирешений является довольно распространенным методом решения некорректных задач математической физики (см., например, перечень работ на данную тему, представленный во второй главе книги [36]). Однако, в настоящее время в задачах обработки изображений данный метод не получил широкого распространения.
Нами были рассмотрены три вариационных метода построения приближенного решения, являющегося решением следующих задач минимизации функционалов.
Метод Тихонова
Найти inf \ \\Az — щ\\ + aQ(z) > для заданных us Є U, а > 0.
zeZ L J
Метод невязки
Найти inf {7(г)} при \\Az — щ\\ < 52 для заданных us Є U, 5 > 0.
z&Z
Метод квазирешений
Найти inf \ \\Az — щ\\ \ при ft(z) < /л для заданных us Є U, ji > 0.
zeZ L J
Пусть Л является линейным оператором и стабилизирующий функционал Q,(z) обладает следующими свойствами:
П(г) - выпуклый функционал;
О(0) = 0; '
Для любого фиксированного элемента z Є Z, z ^ 0 функция j(P) = Q(Pz) - строго возрастающая функция параметра /3 такая, что
lim 7(/^) = +00-
/3—Ч-оо
При данных ограничениях на стабилизирующий функционал Q(z) и оператор А, в работе [37] была доказана эквивалентность данных методов. В том смысле, что параметру регуляризации одного метода (скажем 5* в методе Филипса) соответствуют значения параметров других методов (а* и и*) такие, что решения регуляризирующих методов при данных параметрах совпадают.
Как было отмечено, вариационные регуляризирующие методы являются довольно распространенными методами решения многих задач обработки изображений. Особенно актуально применение регуляризирую-щих алгоритмов в задачах выделения контуров объектов на зашумлен-ных изображениях.
Задача выделения контуров объектов на изображении
Контуры (границы) объектов в большинстве случаев являются наиболее информативными описаниями исходного изображения. Они не содержат избыточных данных, т.е. являются довольно компактным представлением исходного изображения. Поэтому нахождение контуров (границ) объектов на фотографиях является важной начальной операцией для дальнейшей обработки изображений таких, как сегментация, отслеживание и распознавание объектов и т.п.
Достаточно сложно формально определить характеристики функции яркости изображения, на основе анализа которых осуществляется нахождение границ объектов. Поэтому в настоящее время не существует общепризнанной модели контура объекта на изображении.
В зависимости от специфики решаемой задачи выбирается одна из многих идеальных моделей контура объекта и применяется соответствующий ей критерий выделения точек контура.
Наиболее часто используемой является модель "ступенчатый контур" (рис. 1). Данная модель описывает резкий перепад функции яркости изображения, соответствующий контурам объектов, который возникает из-за разницы средних уровней яркости фона и объекта.
Другая модель"линейного контура", описывает границы, соответству-
ющие тонким линиям на изображении, например, рекам и дорогам на аэро-космических фотоснимках.
В некоторых случаях оказывается необходимым отдельное рассмотрение двумерных особенностей, например углов, формируемых при пересечении нескольких контуров.
Идеального метода не существует. Помимо выбора из множества моделей, исследователю приходится принимать решения относительно выбора подхода, в рамках которого будет осуществляться выделение контуров.
В настоящее время для нахождения контуров объектов используются три основных группы методов (детекторов):
Детекторы, использующие производные функции яркости изображения. Данные методы являются самыми распространенными типами детекторов. Дальнейшее исследование предполагает более подробное их рассмотрение.
Детекторы, использующие "коэффициент совпадения с шаблоном" [38, 39]. Как следует из названия, решение о наличии элемента делается на основании значения коэффициента совпадения с шаблоном. Осуществляется свертка изображения с набором масок, каждая из которых ориентирована в своем направлении. Если отклик на фильтрацию маской достаточно существенен, то считается, что контур найден, и направление этой маски наилучшим образом характеризует его направление.
Детекторы, использующие статистические методы [40, 41]. Данные методы обнаруживают контуры объектов, используя статистические
гипотезы. Причём, наличие контура зависит как от статистики фильтров, свидетельствующих о наличии контура, так и от статистики фильтров, свидетельствующих об отсутствии контура (это позволяет, например, не выделять элементы текстуры).
Детекторы, использующие производные функции яркости изображения
Разница средних уровней яркости фона и объекта приводит к возникновению резких перепадов (скачков) функции уровня яркости изображения, соответствующих контурам объектов. Следовательно, процедура определения контуров должна основываться на обнаружении различий между соседними точками, то есть требует некоторой фильтрующей операции, которая подчеркивает резкие изменения в значениях сигнала и подавляет области с постоянными значениями. Для этой цели хорошо подходят дифференциальные операторы (производные функции яркости изображения).
Применение дифференциальных операторов в дискретном случае приводит к задаче численного дифференцирования. Из-за некорректности данной задачи [3, 42], детекторы контуров имеют сильную реакцию на шум (чувствительны к шуму). Поэтому вычисление разностных производных без сглаживания функции не может дать достаточно надежных результатов.
Таким образом, процесс выделения контуров состоит из трех этапов: а) подавления шума (сглаживания изображения), б) вычисления производных, в) разметки контуров.
I. Методы подавления шума
Большинство методов устранения шума основано на удалении высокочастотных компонент изображения. Проведение данной операции возможно напрямую путем подавления высокочастотных компонент дискретного преобразования Фурье, косинусного преобразования, вейвлет разложения [43], разложения функции яркости изображения в ряд по функциям Эрмита [44] и т.д..
Другим методом сглаживания изображений является свертка функции яркости с низкочастотными фильтрами. Наиболее распространенным методом сглаживания является свертка с функцией Гаусса:
Параметр а данного фильтра влияет на величину размытия изображения. Его увеличение приводит к лучшему подавлению шума, но и влечет за собой удаление важных деталей изображения.
Свертка с функцией Гаусса соответствует линейному диффузионному процессу [45].
Для любой / Є C{R2) линейный диффузионный процессии = Ди
и(х, 0) = f(x) имеет единственное решение:
, f(x), при = 0
u{x,t)
(<Л/й */)(*)» приг>0 Возможность использования нелинейных методов анизотропной диффузионной фильтрации, позволяющих проводить сглаживание, не устра-
няющее контуры объектов на изображении, явилось причиной частого использования данных методов [19, 46].
В последнее время для сглаживания изображений широкое распространение получили регуляризирующие методы [1, 2, 15].
II. Методы выделения контуров
Проиллюстрируем задачу выделения резких перепадов в одномерном случае. На рисунке 1а представлен одномерный сигнал /(і), содержащий, так называемый, "ступенчатый контур".
(а) Исходный сигнал
Порог
**—.Контур
(Ь) Первая производная от функции сигнала
. d2№
Контур
*- t
Нули второй производной
(с) Вторая производная от функции сигнала Рис. 1: Зашумленный 1-D контур и его первая и вторая производные
Резкие перепады значений функции сигнала соответствуют большим
абсолютным значениям первой производной данной функции (рис. lb), поэтому процедуру выделения контуров можно проводить, сравнивая модуль первой производной с некоторым экзогенно установленным порогом. В данном случае мы предполагаем наличие контура в точках, где установленный порог был превышен.
Экстремум первой производной от функции сигнала соответствует контуру объекта. Поэтому для его обнаружения возможно также вычисление нулей второй производной от функции сигнала (рис. 1с). Однако, небольшие флуктуации исходного сигнала (вызванные шумом) также могут приводить к выделению точек, в которых вторая производная обращается в ноль, но не соответствующих контурам объектов. Как правило, для фильтрации этих ложных контуров добавляется пороговая фильтрация абсолютного значения первой производной.
В двумерном случае используются аналогичные подходы. Рассмотрим процедуры выделения контуров объектов на двумерных изображениях.
Контрастные перепады на изображении находятся в точках локального максимума модуля градиента \\7I(x, у)\ функции яркости. Поэтому довольно часто для определения контуров объектов используют некоторое пороговое значение, с которым сравнивают длину вектора градиента.
При обработке дискретных изображений дифференцирование заменяется вычислениями разностных производных, аппроксимирующих компоненты вектора градиента. Часто вычисления производных производится с помощью масок Робертса, Превитта и Собеля (табл. 2), менее подверженных влиянию шума [47, 48].
Применение детекторов, выделяющих точки контура при превышении значения модуля градиента порогового значения, довольно широ-
-1 oi
0 1;
г0 -1
л о ,
Маска Робертса
Маска Превита
Маска Собеля Таблица 2: Маски наиболее распространенных операторов дифференцирования
ко распространено при решении задач обработки изображений. Однако, как правило, абсолютная величина вектора градиента достигает больших значений вдоль широких полос на изображении, в то время как, границы объектов являются тонкими кривыми. Избавиться от этого недостатка позволяет использование дифференциальных операторов второго порядка.
Фильтр Канни
Условием контура в одномерном случае является равенство нулю второй производной. Аналогичным критерием в двумерном пространстве является равенство нулю второй производной от функции яркости изображения по направлению п [49, 50]:
где 1(х, у) - функция яркости сглаженного изображения,
п - вектор, ориентированный в направлении ортогональном контуру.
Поскольку это направление не известно a priori, оно аппроксимируется направлением градиента.
V(/) Л ,дд,
дх' dyJ
п и — , где V = (—, —).
V(7)
Отметим, что при таком выборе вектора п, производная -^1(х,у) = VI(x, у) . Таким образом, нахождение второй производной от функции яркости изображения совпадает с определением экстремального значения модуля градиента |У/(ж,г/)| по направлению п.
Для фильтрации ложных контуров выбираются только граничные точки, в которых уровень интенсивности контура (как правило, принимается равным значению модуля градиента) больше некоторого экзоген-но заданного порога.
Отметим, что в дискретном случае определяется не ноль оператора второго порядка, а переход через ноль.
Фильтр Марра и Хилдрета
Другой подход был предложен Марром и Хилдретом [51]. В своей работе они рассматривали детектор, не зависящий от направления и основанный на определении нулевых значений оператора Лапласа, примененного к сглаженному изображению.
Лапласиан и вторая производная по направлению градиента являются операторами второго порядка. Отметим, что представленная в работе [52] связь данных операторов, позволяет заключить, что результат выделения контуров двух рассмотренных детекторов второго порядка совпадает на контурах нулевой кривизны.
В последнее время были предложены методы фильтрации изображе-
ний, совмещающие в себе фильтрующие и дифференцирующие свойства, позволяющие не проводить вычисления разностных производных.
Так Марром и Хилдретом [51] для обнаружения нулей оператора Лапласа от сглаженной функции яркости изображения было предложено использовать свертку исходной функции яркости с Лапласианом от Гаус-сиана:
LoG{x,y) = -—j 1 7Г2Г- -е ^^
7ГСГ1 [ *>(J
Возможность данного подхода обусловлена свойством ассоциативности оператора свертки и оператора Лапласса.
В статьях [53] рассматривается применение для выделения контуров изображений коэффициентов разложения в ряд по полиномам степени п. В работе [54] предложено применение для выделения контуров изображений коэффициентов разложения в ряд Эрмита функции яркости исходного зашумленного изображения.
Отметим, что рассмотренное в данной работе аналитическое решение задачи минимизации функционала Тихонова, также позволяет построить метод выделения контуров, совмещающий в себе фильтрующие и дифференцирующие свойства.
III. Методы разметки контуров
Наиболее распространенные детекторы контуров используют равенство нулю дифференциального оператора второго порядка и условие превышения модуля градиента заданного порога.
Однако, на зашумленных изображениях значение модуля градиента может сильно меняться на протяжении контура, создавая тем самым
проблему пунктирных линий ('streaking' problem). Для преодоления данной сложности Канни [49] был предложен метод применения порогов с гистерезисом. Изначально выбираются два порога (Ті > Т2). Данные два порога используются для классификации контуров на два класса: "сильных" и "слабых" контуров. Слабые одиночные импульсы обычно соответствуют шуму и поэтому отбрасываются. Но если такие точки соединены с пикселами, имеющими большое значение "интенсивности" контура, то велика вероятность, что эти точки принадлежат какому-то контуру. Таким образом, "слабые" контуры отмечаются в результирующем изображении, только если они соединены с "сильными".
Применение метода регуляризации Тихонова со стабилизатором, содержащим производную второго порядка, для обработки изображений
Рассмотрим одномерный метод тихоновской регуляризации со стабилизатором, содержащим производную второго порядка.
Будем рассматривать задачу восстановления неизвестной исходной функции й Є Wf[—l,l]j исходя из заданного приближения щ -\\й — щ\\ь S. Для сглаживания наблюдаемой функции щ Є Ьг[—1,1] мы находим функцию up, минимизирующую функционал Тихонова: d2 Up dx2 Ер{ир) = \\ир - и6\\Ь2 + Р Уравнение Эйлера, записанное для данного функционала, принимает вид: j3up +ир — щ, — 1 х 1, { и" {-1) = и »{1) = 0. Отметим, что использование производных третьего порядка в граничных условиях необходимо для получения самосопряженной задачи. Формулировка необходимого и достаточного условия самосопряженности граничной задачи рассматривается в монографии [55].
Решение данного уравнения с обозначенными выше граничными условиями может быть записано в виде: і и/з{х) = I Gp(x,s)u5(s)ds, (1.8) -і где ядро Gp(x,s) (функция Грина задачи (1.7)) может быть найдено аналитически на основе схемы, описанной М.А. Наймарком [56].
В данном случае ядро Gp(x, s) записывается в виде линейной комбинации функций щ, і = 1,..., 4, образующих фундаментальную систему решений исходного дифференциального уравнения:
Данное тождество аналогично предыдущему случаю позволяет получить два важных свойства регуляризированного решения up: a) Инвариантность среднего значения функции. Для любого (3 О і среднее значение ц = J up(x)dx функции up остается постоян -1 ным и равняется среднему значению наблюдаемой функции щ: і і /І = - / us(x)dx = — / up(x)dx, для любого /3 0. -і -1 b) Принцип максимального значения. Если на отрезке [—1,1] функ ция щ(х) удовлетворяет неравенствам а щ{х) Ь, то для любого /3 0 функция ир(х) также удовлетворяет неравенствам а ир{х) b на отрезке [—1,1]. Графики ядра Gp(x, s) при разных значениях параметра J3 представлены на рисунке 1.7.
Численная реализация и результаты тестирования работы алгоритма Сглаживание сигналов. Для исследования применения данного метода для сглаживания одномерных функций будем рассматривать модельную задачу, описанную в предыдущем разделе. Результаты расчетов для зашумленной функции (1.4) при выборе параметра регуляризации в соответствии с принципом невязки приведены на рис. 1.8. Сглаживание одномерных функций при помощи функционала Тихонова со стабилизатором первого порядка Сглаживание изображений. Аналогично методу, рассмотренному в предыдущем разделе, для сглаживания двумерных функций щ{х,у), определенных на прямоугольнике 0 х т, 0 у I, будем применять следующий интегральный оператор: ( Л Ґ Гг ,2y-l 2V-l 2х-т2 -т Jo Jo її mm 0 x m,0 y
Результаты применения рассматриваемого метода для фильтрации изображений представлены на рисунке 1.9.
Полученные после фильтрации регуляризирующим методом со стабилизатором второго порядка результаты визуально не сильно отличаются от результатов метода, рассмотренного в предыдущем разделе.
Сравнение методов регуляризации Тихонова с различными видами стабилизаторов
Рассмотрим постановку некорректной одномерной задачи, задаваемой операторным уравнением вида Az = и, z Z, и в U, (2.1) где Z — L2[a,b] и U = L 2[c,d], A : Z — U — линейный непрерывный оператор такой, что обратный оператор А-1 существует, но является неограниченным.
Для построения приближенного решения, устойчивого к малым изменениям правой части, воспользуемся методом квазирешений. В качестве компактного множества будем рассматривать множество функций с закрепленным граничным значением, вариация которых не превосходит заданного значения С.
Определение. Вариацией (изменением) функции z(x) на отрезке [а, Ь] п (Уа{2)) называется точная верхняя грань сумм вида Y2 \z{xk) z(xk-i)\, где a = XQ хп = Ъ — произвольная система точек отрезка [а, 6] [57].
Поскольку V%{z) = V%(z + с), то при применении метода квазирешений на множестве функций, вариация которых не превосходит заданного значения С, естественно закрепить значение функции на одном из концов отрезка [а,Ь]. Таким образом, в дальнейшем мы будем считать, что известно одно из граничных значений точного решения z(a) или z{b). Не уменьшая общности, будем предполагать, что z(b) = 0.
Рассмотрим множество функций Vc — {z : V(z) С, z(b) — 0} с закрепленным граничным значением, вариация которых не превосходит заданного значения С.
Функции z Є Vc равномерно ограничены, так как для любой точки х из отрезка [а, Ь] справедливо неравенство \z(x)\ — \z(b) — z{x)\ V [z] С. Таким образом, согласно теореме Хелли [58] из множества функций Vc можно выделить последовательность, сходящуюся в каждой точке х Є [а, 6]. Из сходимости в каждой точке и равномерной ограниченности следует сходимость в 1/2 [а, Ь].
Следовательно, множество функций Vc = {z : V {z) С, z(b) = 0}, является компактом в пространстве [а, Ь]. Поэтому, квазирешение ZK уравнения (2.1), полученное на множестве корректности Vc, сходится к точному решению задачи z Є 1/2 при \\щ — uL — 0.
Таким образом, для нахождения приближенного решения уравнения (2.1), устойчивого к малым изменениям правой части, необходимо научиться строить последовательность, минимизирующую функционал невязки F(z) = \\Az — щ\\ на множестве функций с закрепленным граничным значением, вариация которых не превосходит заданного значе ния С.
При этом, если известна оценка величины погрешности 5: \\й — щ\\ 5, нет необходимости искать точный минимум функционала F(z) на множестве VQ- Для построения устойчивого к малым изменениям правой части решения достаточно найти элемент zs из указанного множества, такой что F(zs) S2.
Численный метод
Приведем описание численного метода для нахождения квазирешений операторного уравнения (2.1) на компактном множестве функций ограниченной вариации. Впервые он был рассмотрен в монографии [35].
Функционал невязки F(z) — \\Az — щ\\2 определен для всех z, принадлежащих VQ- Поскольку оператор А линеен, F(z) — квадратичный функционал z. Данный функционал выпуклый и дифференцируемый, причем его производная Фреше равна: F (z) = 2{A Az - А щ) здесь A : U —Z оператор, сопряженный оператору А.
Заметим, что производная Фреше функционала F(z) удовлетворяет условию Липшица с константой L = 2Л2, так как F (2i) — / () = \\A A(z1-z2)\\ 2\\Anz1-z2\\.
Таким образом, для нахождения квазирешения задачи (2.1) необходимо построить последовательность, минимизирующую некоторый выпуклый дифференцируемый функционал на замкнутом выпуклом ограниченном множестве в гильбертовом пространстве.
Применение метода квазирешений для обработки изображений
Компрессия изображений, применяемая при передаче и хранении информации, вносит различные искажения (артефакты). Так, например, наиболее широко используемый метод компрессии изображений JPEG приводит к появлению искажений в виде блочной структуры, из-за использования ограниченных и не перекрывающихся областей независимой компрессии. Современные методы сжатия изображений, к примеру, JPEG2000, использующий вейвлет аппроксимацию, и другие, позволяют устранить данные артефакты, но их применение приводит к возникновению ложных затухающих осцилляции в окрестности наиболее ярко выраженных контуров. Этот эффект получил название эффекта Гиббса (в литературе по обработке изображений также используется название "ringing").
Рассмотрим более подробно причину возникновения данных артефактов. Пусть f = f h,— отфильтрованный сигнал, полученный с помо sin(i) щью идеального низкочастотного фильтра he = (здесь и далее обозначает операцию свертки). Если / Є L2(R), то, используя формулу Планшереля, можно показать, что /с сходится к / в норме Ьг(-Й): lim ІІ/-ДЦ =0. —»00 Однако, если / разрывна в точке to, то Д имеет колебания Гиббса в окрестности 0, которые не дают supt zR \f(t) — f%(t)\ сходиться к нулю с ростом f [43].
Пусть / — функция с ограниченной вариацией, которая имеет изолированный разрыв при t = to - /(ig) — левый предел этой функции и /(Q ) — правый.
Эту функцию можно разложить в сумму непрерывной в окрестности to функции /с и функции Хэвисайда с амплитудой /(tjj") — /(-): /( ) = Mt) + [/№) - /( о )] «( - 0), ( 1, при t О где u(t) = I 0, при і О Следовательно, Л( ) = Л М ) + [/(t0+) - /( о )] и /if(i - t0), Функция /с имеет ограниченную вариацию и равномерно непрерывна в окрестности to, можно доказать, что /с /if (t) равномерно сходится к /с в окрестности точки to ft sin х Однако, при любом 0: тх /ip(t) = s(t) = f сс, где s(), -оо жх возрастающая от 0 при t = —оо до 1 при t = +оо функция. Она имеет колебания с периодом 7г/, амплитуды которых убывают с возрастанием расстояния от 0. Максимальная амплитуда колебаний Гиббса достигаете ся при t = =Ьтг/ и не зависит от : 7Г J ігх Таким образом: /( ) - Mt) = [/№) - /( о)] (( - о)) + є(е,о, где lim sup б(, t)\ = 0 в некоторой окрестности размера а О около ?- +оо i_(o a
Функция s((—10)) с центром в to создает максимальную погрешность фиксированной амплитуды, пропорциональной скачку /(Q") — /(-) Для всех частот . Рисунок 2.5 иллюстрирует возникновение эффекта Гиббса при низкочастотной аппроксимации исходного сигнала. Отметим, что удаление высокочастотных компонент приводит также и к сглаживанию контуров объектов (резких перепадов на изображении). " -ч.__/ контур Рис. 2.5: Иллюстрация эффекта Гиббса
Функция s() имеет бесконечную полную вариацию, поэтому мы предполагаем, что применение предложенного регуляризирующего метода, основанного на нахождении квазирешения операторного уравнения на компактном множестве функций ограниченной вариации, позволит устранить эффект Гиббса.
Таким образом, для подавления эффекта Гиббса нами применялся описанный в предыдущей части метод сглаживания. Как и ранее константа С является сглаживающим параметром.
Диаграмма состояний
Все методы обработки изображений и выделения контуров объектов доступны через меню. Ниже представлена иерархия команд, вызываемых через меню. Меню File: создание нового стандартного графического документа; открытие документа; закрытие документа; сохранение документа; настройка принтера; быстрый запуск ранее открываемых документов; \ выход из программы; Меню View: отображение панели инструментов; отображение строки состояния; Меню Window: создание нового окна текущего документа; расположение окон каскадом; шахматное расположение окон по горизонтали; шахматное расположение окон по вертикали; выравнивание иконок; Меню Zoom: увеличение/уменьшение изображения; Меню Smoothing: метод фильтрации SUSAN; медианная фильтрация; методы диффузионной фильтрации; регуляризирующие методы фильтрации; Меню Restoration: восстановление смазанных изображений; Меню Edge detectors: детектор Собеля; детектор Канни; детектор Мара и Хилдрета; детектор SUSAN; Меню Thresholding: пороговое выделение контуров объектов; Меню Help: информация о программе;
Задание основных параметров функций, реализующих методы обработки изображений и выделения контуров объектов, осуществляется через диалоговые панели.
В диссертационной работе были получены следующие основные результаты:
1. Разработаны методы фильтрации сигналов и подавления шума на изображениях методом регуляризации А.Н.Тихонова, основанные на аналитическом решении уравнения Эйлера.
2. Предложен и программно реализован регуляризирующий метод для выделения контуров объектов на зашумленных фотографиях.
3. Созданы методы подавления эффекта Гиббса, увеличения разрешения фотографий и восстановления размытых изображений, основанные на построении квазирешения на компактном множестве функций ограниченной вариации.
В настоящее время предложено большое количество методов подавления шума на изображениях. Однако, не существует стандартного метода оптимального решения данной задачи. Каждый из алгоритмов справляется с поставленными задачами достаточно хорошо, но со своими особенностями, положительность или отрицательность которых зависит от предпочтений восприятия конкретным индивидуумом.
Нелинейные методы фильтрации позволяют получить наилучшие результаты, однако требуют больших вычислительных ресурсов. Наибо лее распространенные линейные методы сглаживания изображений достаточно хорошо подавляют шум на изображении, но их использование приводит к размытию важных деталей изображения, например, контуров объектов.
В данной работе для решения задачи подавления шума были предложены методы, основанные на методе регуляризации Тихонова. Как уже отмечалось, методы улучшения фотографий, основанные на методах регуляризации Тихонова, довольно распространены в обработке изображений. Однако, численная реализация данных методов основывается на построении итерационного численного метода решения уравнения Эйлера. В данной же работе для одномерного случая было выписано аналитическое решение уравнения Эйлера.
Предложенные методы подавления шума, основанные на методе регуляризации Тихонова, показали результаты сравнимые по качеству с линейными методами фильтрации изображений.
Найденное аналитическое решение уравнения Эйлера позволяет в явном виде выписать производные сглаженных функций. Разработанный метод выделения контуров объектов на зашумленных изображениях, основанный на вычислении производных функции яркости изображения, записанных в явном виде, показывает лучшие результаты, по сравнению с методами, использующими разностные производные.
Как было отмечено выше, применение метода фильтрации, основанного на методе регуляризации Тихонова, позволяет достаточно хорошо удалить шум на изображении, но приводит к размытию контуров объектов. Избавиться от данного недостатка возможно при применении методов обработки изображений, основанных на нахождении квазирешений на компактном множестве функций, вариация которых не превосходит заданной константы. Апробация этого метода на тестовых изображениях показала высокую эффективность применения алгоритма для подавления эффекта Гиббса. Использование метода квазирешений достаточно перспективно для решения задач восстановления смазанных изображений и увеличения разрешения зашумленных фотографий. Рассмотренные в данной работе методы улучшения изображений и выделения контуров объектов на фотографиях могут использоваться как составная часть комплексных алгоритмов обработки и анализа изображений.
