Лекции по "Технологии цифровой обработки сигналов"

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

- гауссовская сглаживающая  фильтрация;

- нахождение градиента  яркости в каждом пикселе;

- нахождение максимальных  пикселей;

- гистерезисная фильтрация  максимальных пикселей.

Этот алгоритм носит  названия алгоритма Кэнни и наиболее часто применяется для нахождения границ.

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

В двумерном варианте аналогом второй производной является лапласиан - скалярный оператор Ѳ(f) = (𝝏²f/𝝏x + 𝝏²f/𝝏y).

Рис. 5.2.3.

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

5.3. ВЫДЕЛЕНИЕ ОБЪЕКТОВ НА ИЗОБРАЖЕНИИ  [1i]

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

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

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

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

Алгоритм "умные ножницы" используется с 1996 году, завоевал популярность и был встроен в распространенный редактор фотоизображений Adobe Photoshop. При использовании алгоритма пользователь обводит границу между объектом и фоном, указывая точки на границе с некоторым промежутком, а "умные ножницы" проводят граничную линию между последовательно указанными точками.

Рис. 5.3.1.

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

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

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

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

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

(l/L) exp(-s r(C₂, C₂)),

где L - геометрическая длина  ребра, C₁ и C₂ - цвета вершин, соединяемых ребром, λ и σ - некоторые (положительные) параметры, r(..) – матрица чувствительности по перепаду цвета. Данный вес тем меньше, чем больше разница между цветами вершин.

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

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

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

Рис. 5.3.2.

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

Идеального разделения, естественно, быть не может. Например, участок изображения может быть похож по цвету на фон (пиксели множества B), но окружен пикселями множества A и не отделен от них резкой границей. В таких случаях выбор параметра λ в формуле веса ребер устанавливает баланс между последними двумя пунктами. При увеличении значения λ, увеличивается важность того, чтобы граница между фоном и объектом проходила между пикселями с разными цветами, а при уменьшении - увеличивается важность того, чтобы пиксели, похожие по цвету на пиксели множества A (или B), были отнесены к объекту (фону). Пример выделения объекта приведен на рис. 5.3.2.

5.4. Выделение признаков объектов [49]

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

При обработке предпочтительными являются следующие признаки объектов:

– площадь и периметр изображения объекта;

– размеры вписанных  простейших геометрических фигур (окружностей, прямоугольников, треугольников и др.);

– число и взаимное расположение углов;

– моменты инерции изображений объектов.

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

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

A=

S(x, y),      S(x, y) = ,

где L - множество координат массива S(x, y), принадлежащих выделенному объекту.

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

На основе выделенных признаков нормированный признак, инвариантный к масштабу изображения U = A/P² или V = P/ .

Определение радиусов вписанных и описанных  окружностей (рис. 5.4.1) складывается из двух этапов.

Рис. 5.4.1.

1. Определение координат  геометрического центра изображения объекта:

Х_ц =

xS(x, y) / S(x, y),  Y_ц = yS(x, y) / S(x, y),

где x и y – номера строк и столбцов всех пикселей S(x, y), входящих в объект.

2. Вычисление минимального  и максимального расстояний от  центра до границ изображения  объекта.

r(x, y) =

.

_{Rmax = r(x, ymax);  Rmin = r(x, ymin), где x, y Î P (точки периметра).}

Нормированный признак R′ = R_max ⁄ R_min инвариантен к масштабу изображения объекта.

Рис. 5.4.2.

Определение сторон описанного прямоугольника (рис. 5.4.2) выполняется следующим образом. Определяются максимальные и минимальные значения абсцисс и ординат изображения объекта x_max и x_min, y_max и y_min, после чего определяются высота и основание прямоугольника:

L = x_max - x_min,  H = y_max - y_min.

Данный признак не инвариантен к развороту изображения  объекта.

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

Рис. 5.4.3.

С практической точки  зрения предпочтительным представляется более простой алгоритм. Он заключается  в оценке расстояний между начальной и конечной точками фрагмента контура, например, между элементами контура с порядковыми номерами k – 2 и k + 2 на рис. 5.4.3.

Пусть x(k) и y(k) абсцисса и  ордината контурных элементов соответственно. Тогда решающее правило может  выглядеть следующим образом:

{|x(k-2)−x(k+2)|+|y(k−2)−y(k+2)| ≤H}.

Если условие выполняется, тогда данная точка контура принадлежит множеству угловых точек L. Здесь H – пороговое значение, выбираемое с учётом свойств объектов.

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

Рис. 5.4.4.

Обозначим главные искомые  моменты инерции изображения  объекта через J₁ и J₂. Чтобы найти J₁ и J₂, необходимо предварительно определить так называемые промежуточные моменты J_x и J_y, т.е. моменты инерции относительно вертикальной и горизонтальной осей системы координат, а также смешанный момент J_x,y (рис. 5.4.4а).

Порядок вычислений:

1. Определяются координаты  центра "тяжести" (энергетического  центра) изображения объекта.

Х_цэ =

xA(x, y) / A(x, y),  Y_цэ = yA(x, y) / A(x, y),

2. Определяются промежуточные  моменты J_x, J_y, J_x,y.

J_x =

[(x- Х_цэ)² A(x, y)],  Y_x = [(y- Y_цэ)² A(x, y)],

J_xy =

[(x- Х_цэ) (y- Y_цэ) A(x, y)].

3. Вычисляются главные  моменты.

J_1,2 =

.

5.5. обнаружение и распознавание  объектов ИЗОБРАЖЕНИЙ [49]

Обнаружение объектов. Обнаружение (выявление) образов объектов в искажённом шумами и помехами изображении может быть определено в виде процедуры проверки определенного условия сравнения двух чисел - результата преобразования анализируемого изображения и определенного порогового значения:

L[A(x, y)] ≥ П[A(x, y)].                                           (5.5.1)