Восстановление расфокусированного изображения

 

Рис. 3.1. К определению связности:

а – кольцо;

б – неоднозначная фигура

Возвращаясь к более  общему случаю многоградационных изображений, рассмотрим рис. 3.2 (а), на котором представлен некоторый элемент (элемент А), окруженный восемью соседними элементами (от В до 1). Предположим, что элемент А обладает свойством S, установленным на основе некоторого простейшего описания (яркости, цвета, текстуры и т.д.). По определению четырехсвязности элемент А и элемент В связаны, если они обладают свойством S. Аналогично четырехсвязность можно установить между элементом А и элементами Е, С и Д, граничащими с А по ребру, при условии, что оба члена пары обладают одним и тем же свойством. Восьмисвязность позволяет связывать элемент А с одним из его соседей по диагонали, например, с элементом F, граничащим с А в точке, если оба они обладают одинаковым свойством.

На рис. 3.1 (б) в соответствии с определением четырехсвязности имеется четыре несвязных черных прямолинейных отрезка, а согласно определению восьмисвязности, изображено кольцо из связных четырех элементов. Заметим, однако, что при восьмисвязности – белые элементы, расположенные внутри кольца на рис. 3.1 (б), связаны с белыми элементами с внешней стороны кольца. Таким образом, возникает парадокс. Если бы черные элементы связывались по принципу восьмисвязности в кольцо, то следовало бы ожидать разделения внутренних и внешних белых элементов этого кольца. Чтобы разрешить эту дилемму, можно для элементов со свойством S определить восьмисвязность, а принцип четырехсвязности установить для элементов, обладающих свойством S (S – дополнение множества S), или наоборот.

 

 

 

 Рис. 3.2. Определение связных  элементов изображения

Обратимся к рис. 3.2. Пусть заштрихованный элемент обладает свойством S, а незаштрихованный – не обладает свойством S. Тогда элемент А на рис. 3.2 (б) называется изолированным, если для него не соблюдается принцип восьмисвязности относительно любого из его соседей. На рис. 3.2 (в) элемент А является внутренним элементом, для которого выполняется принцип четырехсвязности относительно каждого из его соседей В, С, Д, Е. Граничный элемент, как показано на рис. 3.2 (г), не обладает четырехсвязностью по крайней мере с одним из ближайших соседей. Следуя этому определению, элемент С из окрестности А не может быть классифицирован как граничная точка. Рис. 3.2 (д) иллюстрирует определение точки дуги; элемент А обладает четырехсвязностью только со своими верхним и нижним (или правым и левым) соседями. Дуговой концевой элемент обладает четырехсвязностью лишь с одним соседом. Наконец, минимально связная дуга по определению есть множество точек дуги, для которых каждая внутренняя точка дуги (не являющаяся ее концом) обладает восьмисвязностью лишь с двумя соседями.

1.2.3. Сжатие, утончение и построение остова

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

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

Работа простого алгоритма утончения иллюстрируется на рис. 3.4 (а) на примере утончения объекта прямоугольной формы. На первом шаге первого этапа работы алгоритма граничные элементы с левой стороны объекта, обозначенные буквой L, удаляются, если они не являются точками дуги и их удаление не ведет к нарушению восьмисвязности. На втором шаге удаляются граничные элементы с правой стороны объекта, обозначенные буквой R, если соблюдаются такие же условия, как и для левых граничных точек. Затем процесс удаления повторяется для верхних (Т) и нижних (В) граничных точек, которые удаляются, если они не являются точками дуги и их удаление не ведет к нарушению восьмисвязности. После четырех шагов первого этапа работа алгоритма повторяется до тех пор, пока нельзя будет удалить ни один элемент без нарушения связности. На рис. 3.4 (б и в) приведены примеры, иллюстрирующие работу этого алгоритма применительно к области неправильной формы, ориентированной вертикально и горизонтально. Результаты получаются различные вследствие заданной последовательности выполнения шагов.

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

 

 

 

 

 Рис. 3.3. Примеры работы алгоритма сжатия

 

 

 

 

 

 

Рис. 3.4. Примеры работы алгоритма утончения

 

Рассмотрим способ получения остова, названный преобразованием к  срединным осям, который для каждого  заданного объекта дает однозначный  результат. Интуитивное определение такого преобразования основывается на аналогии со “степным пожаром”. Рассмотрим изображенные на рис. 3.5 области круглой и прямоугольной формы и представим себе, что это участки земли, покрытые высохшей травой. Если бы огонь возник одновременно по всему периметру участков, то он распространялся бы к их центрам до тех пор, пока не сгорела бы вся трава. В случае круглой области огонь распространялся бы к центру круга, который представляет собой точку самогашения огня. Для прямоугольной области огонь распространялся бы с каждой стороны. По мере продвижения огня слева и сверху линии огня будут встречаться, и пожар будет затухать. Геометрическое место точек самогашения огня образует линию самогашения. Точки или линии самогашения называются срединными осями или остовом фигуры. Вообще срединоосный остов состоит из множества точек, которые находятся на одинаковом расстоянии от двух ближайших к ним точек на границе фигуры. Это расстояние называется расстоянием самогашения фигуры. Границу фигуры можно восстановить по ее срединоосному остову и расстоянию самогашения. Эта граница есть огибающая окружностей с радиусом, равным расстоянию самогашения, с центрами в каждой точке срединоосного остова.

 

Рис. 3.5. Примеры преобразования к срединным осям:

а – круг;

б – прямоугольник

1.2.4. Эрозия, наращение, размыкание и замыкание

Пусть есть множественное представление двоичного входного изображения, и пусть есть компактное множество малого размера и простой формы (например, d-мерная сфера). Множество В называется структурирующим элементом. Пусть выражает векторный перенос X на . Фундаментальными морфологическими операторами для множеств являются наращение (dilation) и эрозия (erosion) – X с помощью В, которые определяются как

, (3.1)

. (3.2)

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

Другие операторы могут быть определены как комбинации эрозии и  наращения. Например, 2 дополнительных фундаментальных оператора – размыкание (opening) и замыкание (closing) X с помощью В определяются как

, (3.3)

.  (3.4)

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

1.2.5. Описание линий

Прямолинейные и криволинейные  отрезки образуют структуру многих изображений. Для таких изображений математические соотношения между выделенными точками на границе объекта дают символическое описание изображения. Мы рассмотрим один из подходов к установлению математических соотношений – подбор кривых, основанный на их аппроксимации. Рассмотрим совокуп-ность точек (x_i, y_i) при i=0, 1, 2,..., M, взятых на границе двумерного объекта, как показано на рис. 3.7. Предположим, что эти точки упорядочены в том смысле, что точки (x_i, y_i) и (x_i+1, y_i+1) – ближайшие соседи вдоль границы. Если x_i+1 > x_i, то говорят, что эти точки находятся в функциональной связи. Аппроксимация кривой на множестве точек состоит в определении некоторой функции y=g(x), для которой ошибка аппроксимации, то есть мера отклонения совокупности исходных точек (x_i, y_i) от точек [x_i, g(x_i)], принимает минимальное значение. Если точки объекта находятся в функ-циональной связи, то ошибка аппроксимации обычно измеряется по координате y. Типичными ошибками аппроксимации являются:

абсолютная ошибка

,   (3.5)

квадратическая ошибка

,   (3.6)

максимальная ошибка

.  (3.7)

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

 

Рис. 3.6. Эрозия, наращение, размыкание, замыкание Х (двоичного изображения “острова”) с помощью диска В, сцентрированного относительно начала координат

 

 

Рис. 3.7. Точки, взятые на границе объекта:

а – точки объекта;

б – точки, находящиеся в функциональной связи

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

, (3.8)

где  – коэффициенты полинома. Подстановка эксперимен-тальных точек в выражение (3.8) приводит к соотношению в векторной форме

 

, (3.9)

которое можно записать в компактном виде

.  (3.10)

Для ошибки по критерию наименьших квадратов 

 (3.11)

оптимальный набор коэффициентов  полинома получается из уравнения

. (3.12)

При М>N, то есть когда число экспериментальных точек превышает число коэффициентов полинома, псевдообратная матрица вычисляется по формуле

  (3.13)

при условии, что все экспериментальные  точки x различны. В случае линейной аппроксимации требуется определить лишь коэффициенты a₀ и a₁. В противоположном крайнем случае, когда функция представляет собой полином n-ого порядка, имеет место  

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

1.2.6. Описание формы

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

Метрические характеристики изображения основаны на измерении  расстояния между точками на его  плоскости. Расстояние – это вещественная функция d [(x_i, y_i), (x_j, y_j)] двух точек (x_i, y_i) и (x_j, y_j), обладающая следующими свойствами:

,  (3.14)

,  (3.15)

  (3.16)

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

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

,  (3.17)

 

абсолютное расстояние

,  (3.18)

максимальное расстояние

.   (3.19)

В случае дискретного  изображения разности координат x_i – x_j и y_i – y_j представляют собой целые числа, а евклидово расстояние обычно не целочисленно. Это обстоятельство неизбежно ведет к ошибке вследствие округления или усечения числа при цифровой обработке.