Лабораторная работа №3, страница 2

Желательно построить алгоритм, который обладал бы линейной сложностьюотносительно количества точек границ.Выделение прямых при помощи алгоритма ХафаРассмотрим уравнение прямой, проходящей через точку границы А(xi,yi):yi = k xi + bгде k и b — параметры искомой прямой.Пусть нас пока не смущает невозможность использования этого уравнения для описаниявертикальных прямых — этот вопрос будет рассмотрен немного ниже.В этом уравнении xi и yi являются константами, а k и b являются неизвестными. Перепишемуравнение прямой в другом виде:b = - xi k + yiЛегко убедиться, что это — тоже уравнение некоторой прямой, но в других координатах – k иb, а параметрами прямой являются -xi и yi.Введем в рассмотрение пространство параметров (ПП) прямой <k, b>.

В соответствии сприведенными выше формулами каждой точке пространства <k, b> очевидным образом соответствуетпрямая в пространстве координат изображения <x,y>, а каждой точке границы А(xi,yi) в пространствекоординат изображения соответствует прямая в пространстве параметров прямой <k, b>.

Эти двапространства являются дуальными (рис. 3.1).Предположим, что несколько точек границы лежат на одной прямой. Каждая из этих точек вПП прямой будет порождать свою прямую. Однако все эти прямые должны пересечься в точке <k*,b*>, где k* и b* - параметры прямой, проходящей через все рассматриваемые точки (рис. 3.1). Такимобразом, для обнаружения прямых на изображении надо для каждой точки границы построитьсоответствующую прямую в ПП прямых, а затем найти точки пересечения существенного количестватаких прямых.а)в)б)Рисунок 3.1 — Пространство параметров прямойа) Изображение, содержащее четыре точки границы A,B,C и D, лежащие на одной прямой;б) Пространство параметров прямой, содержащее прямые a,b,c,d, которые соответствуютточкам A,B,C, D;в) Массив счетчиков, представляющий пространство параметров прямой. Максимальныйэлемент массива M[k*,b*] = 4 соответствует прямой y=k* x+b*, проходящей через точки A,B,C и D.Для представления ПП прямых введем двумерный массив счетчиков (рис.

3.1,в) с индексами[k, b]. Каждая ячейка будет хранить количество прямых, проходящих через заданную точку (k, b). Тогдаалгоритм поиска прямых будет выглядеть следующим образом:Алгоритм поиска прямых1.Для каждой точки границы с координатами А(xi,yi):Строим прямую b = - xi k + yi в пространстве <k, b>. Для каждого возможного значения kвычисляем соответствующее значение b и увеличиваем счетчик [k, b] на единицу.2.Для каждой ячейки [k, b] массива счетчиков: если значение счетчика [k, b] большепорогового, то заносим прямую с параметрами k, b в список найденных прямых.Под пороговым значением здесь понимается минимально допустимое количество точекграницы, через которые проходит прямая.

Оно может быть задано заранее либо рассчитано,например, таким образом, чтобы находить заданное количество прямых. Такой алгоритм называетсяпреобразованием Хафа.Недостатком алгоритма Хафа является невозможность выделения вертикальных линий: дляних значение k убегает в бесконечность, а b не определено. Чтобы преодолеть этот недостаток,необходимо отдельно детектировать горизонтальные прямые (с углом наклона до 45 градусов) впространстве <x,y>, и отдельно — вертикальные (с углом наклона больше 45 градусов) в пространстве<y,x>.Такой алгоритм позволяет детектировать линии любой ориентации, однако он имеет другойнедостаток: выделяемые линии оказываются неравноценными: точность описания линий с меньшимуглом наклона выше, чем с большим. Пространство поиска <k, b> оказывается анизотропным — в немразличные направления неравноценны.Использование нормальной формы прямойСуществует ли изотропное пространство параметров прямой? Безусловно.

Для этоговоспользуемся нормальной формой параметризации прямой. Нормальная форма предусматриваетопределение прямой через ее вектор нормали (,): = x Cos + y Sinгде — длина нормали,— угол наклона нормали,x,y — координаты точки, принадлежащей прямой.Вместо пространства <k, b> будем рассматриватьдетектирования прямых изменится следующим образом:пространство<,>.АлгоритмАлгоритм детектирования прямых с использованием нормальной формы1.Для каждой точки границы с координатами А(xi,yi):Строим синусоиду  = xi Cos  + yi Sin  в пространстве <,>.

Для  от 0 до 360 градусоввычисляем соответствующее значение  и увеличиваем счетчик H[,] на единицу.2.Для каждой ячейки H[,] массива счетчиков: если значение счетчика H[,] большепорогового, то заносим прямую с параметрами , в список найденных прямых.Данный алгоритм очень похож на предыдущий,но вместо прямых в пространстве параметров строятсясинусоиды.Одной прямой на изображении в пространстве<,> будут соответствовать два максимума: (,) и (,+180), один из которых следует исключить. Для этогоследует либо отбрасывать отрицательные значения ,либо изменять  от 0 до 180 градусов.Максимальное значение мах для верхнейграницы массива счетчиков найти достаточно легко: этомаксимально возможное расстояние до прямой наизображении.

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

Например, этомогут быть координаты концов отрезка.Предположим для начала, что на одной прямой может лежать только один отрезок. В этомупрощенном случае отрезок может быть однозначно идентифицирован прямой, проходящей черезнего. Тогда идентификационные параметры отрезка можно сократить с четырех до двух, например,до параметров нормали < ρ,φ >Что же делать с другими параметрами, необходимыми для полного описания отрезка? Мыотнесем их к дескриптивным параметрам. Для их учета и накопления расширим ячейки счетчика: пустькаждый счетчик теперь содержит не только количество точек в отрезке, но и дополнительнуюдескриптивную информацию, например – максимальную и минимальную координаты x и y отрезка.Получим расширенное пространство поиска: оно по-прежнему двумерно, но имеет более сложнуюструктуру из-за учета дескриптивных параметров.

Помимо максимальных и минимальных координат,расширенное пространство поиска может хранить и другую информацию, например, направлениеградиента вдоль отрезка.Необходимо отметить, что максимальная и минимальнаякоординаты – это не совсем концы отрезка, это – координатыминимальной по размеру прямоугольной области, содержащейотрезок. Координаты углов нижнего левого и верхнего правогоуглов этой области не обязательно совпадают с концами отрезков.Однако получить координаты концов отрезков не составляеттруда. Если угол φ принадлежит первой или третьей четверти, тодля получения координат концов отрезка нужно поменятьместами ymin и ymaxАлгоритм поиска в расширенном пространстве поиска можно записать в следующем виде:1.Для каждой точки границы А(xa,ya) с градиентом G(gx,gy) рассчитываем <ρ,φ> находим ячейку H[ρ,φ] увеличиваем счетчик: H[ρ,φ].C++ корректируем концы отрезка:если H.xmin > xa то H.xmin = xaесли H.xmax < xa то H.xmax = xaесли H.ymin > ya то H.ymin = yaесли H.ymax < ya то H ymax = ya2.Находим локальные максимумы H* [ρ*,φ*].C, соответствующие наиболее длинным ичетким отрезкам; если φ* принадлежит первой или третьей четверти, то меняем местамиφmin и φmax .Очевидно, что алгоритм является модификацией алгоритма поиска прямых.

Добавляютсятолько операции сравнения концов, удельный вес которых в общей доле вычислений достаточно мал.Ход работыЧасть 1. Поиск границЗапустите графический редактор Paint (или любой другой) и нарисуйте черный пятиугольник.Сохраните изображение в формате BMP или PNG в рабочей папке со скриптом.В Матлабе создайте новый скрипт, загрузите изображение с пятиугольником (imread),убедитесь, что оно загрузилось и может быть отображено на экране (imshow).

Обратите внимание, чтоматрица изображения – трёхмерная, она содержит три цветовые плоскости. Преобразуем его вполутоновое серое (rgb2gray). Убедитесь, что матрица изображения стала двухмерной.Будем считать, что яркость объекта нам неизвестна, и попробуем найти его границы.Зададим маску фильтра Собела в виде матрицы 3х3: Sx=[-1 0 1;-2 0 2;-1 0 1], Sy=Sx'и найдем производные по обеим координатам (imfilter). Обратите внимание, что в процесседифференцирования могут появляться отрицательные числа, которые не могут быть представлены вбайтовом формате (uint8). Поэтому изображение нужно преобразовать в знаковый формат, например– double (im2double).A=im2double(A);Dx=imfilter(A,Sx);Dy=imfilter(A,Sy);%Производная по х даст вертикальные границы%Производная по у даст вертикальные границыОтобразите найденные границы на экране, убедитесь, что они отображены верно.

Обратитевнимание, что отрицательные производные (переход от белого к черному) отобразятся в виде черныхточек, а положительные – в виде белых. Точки, не содержащие границ, отобразятся как серые.Найдите модуль и фазу градиента яркости по формулам:|G|=sqrt(Dx^2+Dy^2);=atan2d(Dy,Dx);Отобразите модуль градиента на экране и рассмотрите его. Можно увидеть, что линии границ– достаточно толстые. Давайте уменьшим толщину границ до единицы (edge):E=edge(A);Внутри функции edge уже есть фильтр Собела и расчет градиента. Эта функция включает в себявсе операции поиска границ, далее мы будем пользоваться в основном ею.Далее приведен полный код первой части.