Реферат: Вариационный подход к сглаживанию и определению характерных точек черно-белых изображений

А.Н. Каркищенко, А.Г. Броневич, Н.С. Зюзерова

1. Основные определения

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

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

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

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

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

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

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

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

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

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

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

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

2. Непрерывная модель для гладкой функции яркости

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

Вариационный подход к сглаживанию и определению характерных точек черно-белых изображений| Вариационный подход к сглаживанию и определению характерных точек черно-белых изображенийВариационный подход к сглаживанию и определению характерных точек черно-белых изображений - Вариационный подход к сглаживанию и определению характерных точек черно-белых изображений| Вариационный подход к сглаживанию и определению характерных точек черно-белых изображений?.

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

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

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

С учетом этого можно ввести в рассмотрение следующий функционал по критерию гладкости:

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

3. Дискретная модель для выбора наиболее гладкой функции яркости

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

|Вариационный подход к сглаживанию и определению характерных точек черно-белых изображенийВариационный подход к сглаживанию и определению характерных точек черно-белых изображений- Вариационный подход к сглаживанию и определению характерных точек черно-белых изображенийВариационный подход к сглаживанию и определению характерных точек черно-белых изображений| Вариационный подход к сглаживанию и определению характерных точек черно-белых изображений?, Вариационный подход к сглаживанию и определению характерных точек черно-белых изображений=1,2,...,N1,  Вариационный подход к сглаживанию и определению характерных точек черно-белых изображений=1,2,...,Вариационный подход к сглаживанию и определению характерных точек черно-белых изображений.           (1)

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

Вариационный подход к сглаживанию и определению характерных точек черно-белых изображений|Вариационный подход к сглаживанию и определению характерных точек черно-белых изображенийВариационный подход к сглаживанию и определению характерных точек черно-белых изображенийВариационный подход к сглаживанию и определению характерных точек черно-белых изображенийВариационный подход к сглаживанию и определению характерных точек черно-белых изображений-Вариационный подход к сглаживанию и определению характерных точек черно-белых изображенийВариационный подход к сглаживанию и определению характерных точек черно-белых изображений, Вариационный подход к сглаживанию и определению характерных точек черно-белых изображений|Вариационный подход к сглаживанию и определению характерных точек черно-белых изображений? Вариационный подход к сглаживанию и определению характерных точек черно-белых изображений-Вариационный подход к сглаживанию и определению характерных точек черно-белых изображений,

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

Заменяя интегрирование  конечной суммой, получаем:

Вариационный подход к сглаживанию и определению характерных точек черно-белых изображений.  (2)

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

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

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

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

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

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

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

Вариационный подход к сглаживанию и определению характерных точек черно-белых изображений+ Вариационный подход к сглаживанию и определению характерных точек черно-белых изображений.                  (3)

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

Вариационный подход к сглаживанию и определению характерных точек черно-белых изображений  =  Вариационный подход к сглаживанию и определению характерных точек черно-белых изображений Вариационный подход к сглаживанию и определению характерных точек черно-белых изображений  Вариационный подход к сглаживанию и определению характерных точек черно-белых изображений? (знак «+» или «-»).

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

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

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

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

Вариационный подход к сглаживанию и определению характерных точек черно-белых изображений> 0.

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

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

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

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

Нетрудно заметить, что последняя оптимизационная задача имеет явное решение:

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

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

Вариационный подход к сглаживанию и определению характерных точек черно-белых изображений.                                                           (4)

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

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

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

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

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

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

Список литературы

Lee D. Coping with discontinuities in Computer Vision: Their Detection, Classification and Measurement// IEEE Transactions on Pattern Analysis and Machine Intelligence, vol.12, № 4, 1990.

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

Павлидис Т. Алгоритмы машинной графики и обработки изображений. - М.: Радио и связь, 1986.