Лабораторная работа №3

Лабораторная работа №3Обработка границ, детектирование прямых и отрезковТеоретическая частьВведениеНа прошлой лабораторной работе мы рассматривали случай, когда цвет точек объекта и фоназаранее известен, и его точки могут быть отделены от фона, чтобы затем можно было найти ираспознать объект морфологическими методами.Однако цвет объекта известен не всегда. Более того, в ряде задач объект специально окрашенв цвета, максимально близкие к цвету фона. Что же делать в этом случае?Если объект физически отличается от окружающего фона, то при переходе от точек объекта кточкам фона яркость изменится скачком: в этом месте и находятся границы объекта. Таким образом,мы все равно имеем возможность найти границы объекта по перепаду яркости, и представить объектв виде совокупности точек его границ. Более того, точки границы можно собирать в более крупныегеометрические объекты – прямые, отрезки, окружности и т.д.

Такое представление будет обладатьследующими свойствами:-надежность: расчет признаков опирается на большое количество точек;-компактность описания: вместо сотен тысяч точек используются десятки объектов;-универсальность: большинство объектов имеют хорошо заметные и легко выделяемыеграницы.Выделение точек границПусть на изображении имеется объект, цветкоторого заранее неизвестен. Рассмотрим функциюяркости в некотором сечении А-А. Точки границыобъекта могут быть найдены как точки, в которыхяркость изменяется (возрастает или убывает)наиболее быстро. Скорость изменения яркости – этони что иное, как производная яркости по координатеI/x.Значит, для обнаружения точек границдостаточно найти точки локального экстремумапроизводной яркости.Для поиска границ с использованием этогоподхода нужно решить две проблемы:1.Изображение – дискретная функция, ипроизводная может принимать значения только0 и ±∞.

Значит, нужно найти дискретный аналогпроизводной, например – в виде разностной схемы.2.Изображение –двухмерная функция. Этозначит, что искать производную нужно не только пооси x, но и по оси y, и по всем остальнымнаправлениям. Из всех производных в точке по всемвозможнымнаправлениямнужновзятьмаксимальную по модулю.Фильтр СобелаДля построения простейшей разностной схемы можно воспользоваться определениемпроизводной:I ( x, y)I ( x  x, y)  I ( x, y) limx 0xxМинимальное значение x – это шаг сетки, равный единице. Поэтому можно записатьприближенное равенство:I ( x, y) {x  1}  I ( x  x, y)  I ( x, y)xАналогично для оси Y:I ( x, y) {y  1}  I ( x, y  y)  I ( x, y)yМожно также записать производную в виде маски фильтра. Маска фильтра для производнойпо х:M x  1  11 1Маска фильтра для производной по у: M y  Можно убедиться, что такой простой подход вполне работоспособен, однако имеетсущественные недостатки:- Крайне низкая точность определения направления градиента.

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

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

Точкисправа и слева (А1 и А5) закроются окружностью целиком, аугловые точки (А2,А4,А6,А8) – только наполовину. Дадимугловым точкам веса ±1/2, а левой и правой точке – веса -1и +1 соответственно. Центральной точке А0, верхней инижней точке (А3 и А7) дадим нулевые веса. Для полученияцелочисленной маски домножим все веса на 2.

Получим маску, которая называется маской Собела:  1 0 1 1  2  100 S x   2 0 2 , S y   0 1  1 0 121 Соответственно, формула для вычисления производной будет иметь вид:11I ( x, y )   I [ x  x, y  y]S x [x, y] ,xx  1 y  111I ( x, y )   I [ x  x, y  y ]S y [x, y] .yx  1 y  1Фильтр Собела даёт хорошую точность расчета производных и широко используется напрактике. Возможны также фильтры Собела большего размера (5х5, 7х7), которые дают еще большуюточность, но и требуют существенно больше вычислений.Использование градиента яркостиВведемврассмотрение I ( x, y ) I ( x, y ) ,G( x, y )  ,y  xвекторсоставленныйизчастных производных функции яркости изображения вданной точке.

Этот вектор представляет собой векторградиента яркости.Модуль вектора градиента будет показыватьнаибольшую скорость изменения яркости, то естьстепень выраженности границы в данной точке. Этозначит, что нам не надо искать производные по всемвозможным направлениям, достаточно производных пох и по у.Модуль градиента может быть вычислен по формуле:I ( x, y )I ( x, y )xy2G( x, y ) 2Направление градиента показывает направление, в котором яркость возрастает наиболеебыстро.

Это направление всегда перпендикулярно направлению границ, и может быть использованодля его определения. Направление градиента может быть вычислено по формуле:arg G  arctanIIyxВ приложениях, чувствительных к объему вычислений, модуль градиента яркости может бытьвычислен по приближенным формулам без использования квадратного корня: I ( x, y ) I ( x, y )  (низкая точность),G( x, y )  max ,y  x I ( x, y) I ( x, y) I ( x, y) I ( x, y)  (средняя точность).G( x, y )  1 2  max ,xyxyКак правило, точное значение модуля градиента в дальнейших вычислениях не используется(производится только его сравнение с порогом), и такая аппроксимация вполне допустима.Для вычисления направления градиента удобно использовать функцию atan2(y,x), котораяреализована в большинстве современных языков программирования. Она рассматривает (x,y) какточку и вычисляет угол направления на нее в диапазоне от 0 до 360 градусов.

Матлаб дополнительноимеет функцию atan2d с теми же аргументами, но возвращает результат в градусах (от -180 до +180).Для ускорения вычислений также можно использовать и значения арктангенса, заданныетаблично с требуемой точностью.Обработка границЕсли рассмотреть амплитуды градиента яркости в различных точках, то можно заметитьинтересную особенность — он будет больше нуля не только в точках границы, но и в точках фона илиобъекта, которые границами не являются. Это происходит из-за небольшой разности освещенностисоседних точек, из-за наличия у объекта текстуры и мелких деталей, из-за влияния шума и помех.Кроме того, ширина граничной области может составлять несколько пикселей, особенно длянедостаточно резких границ.

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

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

Такие точки необходимо удалять.Однако этот принцип будет справедлив только в сечении градиента яркости. Если мырассмотрим двухмерный профиль градиента яркости, то увидим, что в окрестностях центральнойточки границы будут присутствовать как точки с меньшей амплитудой градиента (в направленииградиента), так и с примерно одинаковой или даже большей (в направлении контура). Таким образом,для поиска центральных точек границы необходимо анализировать только точки, лежащие внаправлении градиента яркости.Алгоритм немаксимального подавления можно записать следующим образом.Для каждой точки изображения (х,у), х=2..ширина-2, у=2..высота-2 с известнымградиентом яркости G:по углу направления градиента яркости выбираем соседние точки в сеченииградиентом (например — берем их из таблицы)если хоть в одной из этих соседних точек амплитуда градиента яркости больше,чем в текущей, то текущую точку помечаем как не содержащую границ (разметка выполняется вотдельном массиве)если хоть в одной из этих соседних точек амплитуда градиента яркости равнаамплитуде в текущей точке и соседняя точка лежит выше либо правее текущей, то текущуюточку помечаем как не содержащую границ (разметка выполняется в отдельном массиве)если ни одно из этих условий не выполнилось, текущую точку помечаем как точкуграницы.Алгоритм может быть применен только к точкам, отстоящих на две точки от края изображения,поскольку для крайних точек нельзя посчитать градиент, а для их соседей нельзя применить алгоритмнемаксимального подавления, поскольку для этого нужно знать градиент в крайних точках.Разметка точек выполняется в отдельном массиве.Для упрощения алгоритма список соседних точек для каждого направления градиентарассчитывается заранее и заносится в таблицу.Алгоритм выполняется за один проход, не требует сложных вычислительных операций ивыполняется достаточно быстро.Выделение линийПрежде всего необходимо отметить, что прямые линии на изображении могут проходитьтолько через границы изображения.

Внутри самого объекта, а также на фоне — линий, как правило,нет. Единственное исключение — случай, когда объект является протяженным (например, провода,треки частиц и т.д.). В этом случае прямая будет проходить не по границам, а параллельно им и междуними.Таким образом, детектирование прямых всегда начинается с этапа получения и обработкиточек границ, который мы рассмотрели выше.Пусть имеется набор точек границы. Для каждой точки границы известны ее координаты иградиент яркости. Наша задача — найти прямые, проходящие через заданное количество точекграниц.Наиболее простой и очевидный алгоритм заключается в просмотре комбинаций пар точек.Каждая пара точек однозначно задает прямую, и после расчетов ее параметров легко определить,через какое количество точек пройдет прямая. Однако количество возможных пар точек наизображении очень велико (если точки контура составляют 13% точек изображения, то количество парравно 0,017N4, где N — размер стороны изображения), и такой алгоритм будет вычислительнонеэффективным.