Гонсалес Р., Вудс Р., Эддинс С. Цифровая обработка изображений в среде Matlab (2006) (1246139), страница 72
Текст из файла (страница 72)
На самом доле, у каждой точки этой прямой имеется прямая в пространстве параметров, причем все такие прямые пересекаются в точке (а', Ь'). Эти понятия иллюстрируются на рис. 10.8. а) б) ь Рис. 10.8. а) Плоскость ху. 6) Пространство пврвмотров об В принципе, можно построить на графике все параметрические прямые, соответствующие всем заданным точкам (х„у,) изображения, а затем все линии изображения можно идентифицсс1ювать г помощью точек пересечения параметрических прямых. При этом возникает вычислительная трудность, связанная с тем, что число а (угловой коэффициент) стремится к бесконечности, когда прямая близка к вертикали. Один из способов справиться с этой проблемой состоит в представлении уравнения прямой с помощью ее вектора нормали: хсовО+ угйпО = р. На рис.
10.9, а) приведена геометрическая интерпретация параметров р и О. Горизонтальная прямая имеет О = 0', а параметр р равен (положительной) координате пересечения прямой с: осью х. Анвлсогнчно, вертикальная прямая имеет О = 90", а р равно координате пересечения с положительной полуосью у или О = — 90', а р — координате пересечения с отрицательной полуосью у. Каждая синусоидальная кривая на рис. 10.9, б) отвечает семейству прямых линий, проходящих через некоторую точку (х„у,). Точка пересечения кривых (р', О') соответствует прямой, проходящей через обе точки (х„у,) и (хм ут). Привлекательность преобразования Хафа с точки зрения вычислений происходит из возможности разбиения пространства параметров рО на так называемые ячейки накопления, как показано на рис. 10.9, в), где (рнвв рвсвк) и (Ов1 и, Осввк)— предполагаемые диапазоны значений параметров.
Обычно эти значения варьируются в интервалах — 90' < О < 90' и — 1) < р < )), где )) это расстояние мелсду угловыми точками изображения. В ячейке с координатами (с,)) накапливается (баб Г б. с* б в) в 6 Вбб„с и„„„ в бб Ум а) л' Рис. 10.9. а) Парвметризапия (р,й) прямых на плоскости ху. о) Синусоиды в плоскости ра.
Точка пересечения (р',О') соответствует паралбетрам прямой, соединяющей точки (х„у,) и (х„рб]. е) Разделение плоскости рд на ячейки накопления Далее рассматривается М-функция дпя вычисления преобразования Хафа. Эта функция использует операции с разрезкеннвсми матрицами, которые имеют малое число ненулевых элементов. Свойство разреженности позволяет получить выигрыш как при хранении данных, так и при вычислениях.
Имея матрицу А, преобразуем ее в разреженный матричный формат с помощью функции вратве, которая имеет синтаксис Я = врагве(А). Например, » А= [О О О 5 О 2 О О 1 3 О О О О 4 О ); » Я = врагве(А) Я = (3,1) 1 (2,2) 2 (3,2) 3 (4,3) 4 (1,4) 5 значение А(г, )) для квадрата в пространстве параметров, соответствующего точке (0„0,.). Вначале значения всех ячеек накопления равны нулю.
Затем для каждой точки (хь, уь) выбранного множества на изображении полагаем параметр 0 равным каждому разрешенному дискретному значению О, в ячейках 0-оси и находим соответствующее ему значение, решая уравнение р = хй сов О+уй вш О. Затем найденные величины р округляются до ближайшего разрешенного дискретного значения р, из ячеек р-оси. После этого значение соответствующей ячейки накопления увеличивается на единицу: А(т',)):= А(т',)) +1. В конце процедуры ячейка А(тб)') равна числу Я, которое означает, что Я точек плоскости ху лежат на прямой х соз О, + у сйп 0 = рм Точность попадания этих точек на прямую зависит от числа ячеек накопления в пространстве р0. Здесь перечислены все ненулевые элементы Я вл~естс с их индексами строк и столбцов.
Элементы упорядочены по столбцаль Ииесгся форма обращения к функции ярагяе с пятью аргументами, которая используется чаще всего: Я = врагве(г, с„я, ш, и). Здесь г и с — это векторы индексов строк и столбцов ненулевых элементов матрицы, которую мы хотим перевести в разреженный формат. Параметр в представляет собой вектор значений, отвечающих индексным парам (г, с). а ш и и обозначают число строк и число столбцов построенной матрицы.
Например, матрицу Я из предыдущего примера можно прямо построить командой )) Я =врагве([32341], [12234], [12345], 4, 4); Существуют и другие синтаксические формы обращения к функции врагве, которые можно узнать из справочной информации по этой функции. Имея разреженную матрппу Я. порожденную любой формой функции вратве, можно вернуться к стандартному матричному представлению, применяя функцию 1и11, синтаксис которой имеет вид А = 1и11(Я).
Чтобы использовать в МАТ[.АВ детектор линий на основе преобразования Хафа. мы начнем с написания функции ЬоияЬ.ш, которая соверщаст это преобРазование 1ипсслоп [Ь, СЬеСа, гЬо] = ЬоиЯЬ(1, НСЬеса, НгЬо) %НООСН НощЬ Сгяпв1отш. % [Н, ТНЕТА, ННО] = НООСН(с, РТНЕТА, РЕНО) сошрисев СЬе НощЬ % Сгапя1отш о1 СЬе [шабе Е. РТНЕТА врес111ев СЬе врас1пб (1п % Небгеея) о1 СЬе Ноийй Стапв1огш Ь1пя а1ощ СЬе СЬеса ахлв.
РЕНО Х ярес111ев СЬе врасгпб о1 СЬе НощЬ Сгапв1огш Ь[пв а1опй СЬе гЬо % ах1я. Н Ав СЬе НощЬ Сгапв1огш шасг1х. 1С Ав ИННО-Ьу-МТНЕТА, % яЬеге ИННО = 2все11(погш(в1ае(с))/РЕНО) - 1, апй МТНЕТА = % 2ясе11(90/РТНЕТА). Мосе СЬаС 11 90/РТНЕТА 1в поС вп 1псебег, СЬе % асСиа1 ащ1е враслщ я111 Ье 90 / се11(90/РТНЕТА). Х % ТНЕТА 1я ап НТНЕТА-е1ешепС уессог сопса1п1щ СЬе ащ1е (1п % Нейгеея) соггеяроп41щ Со еасЬ со1ишп о1 Н.
ННО 1в ап '/, МКНО-е1ешепС уессог сопса1п[пЕ СЬе уа1ие о1 гЬо соггевроп41пЕ со Х еасЬ гоя о1 Н. % '/ [Н, ТНЕТА, ННО] = НООСН(Е) сошрисея СЬе НоиНЬ Сгапя1отш ив1щ % РТНЕТА = 1 апй РЕНО = 1. 11 патп1п < 3 бгЬо = 1; епй 11 пагЕ1п < 2 (Е4 1 О.С 1 6 йСЬеСа = 1; епй Т = йопЫе(г); [М,Н) = е1хе(1); СЬеса = 11перасе(-90, О, се11(90/йСЬеса) + 1); СЬеса = [СЬеса -ШР1т(СЬеса(2:епй — 1))); пСЬеСа 1епЕСЫСЬеса); 0 = ецгС((М вЂ” 1)"2 + (М вЂ” 1)"2); а = се11(0/йгЬо); пгЬо = 2*я — 1; тЬо = 11перасе(-с(ейгЬо, с(ейгпо, пгЬо); [х, у, на1) = 11пй(1); х=х-1;у=у-1; '/ 1птЫа11хе опСрпС.
Ь = хегое(пгЬо, 1ещСЬ(СЬеса)); '/ То ачо1й ехсеее1че шешогу пеаяе, ртосеее 1000 попхето р1хе1 % на1пее аС а С1ше. 1ог Ь = 1:се11(1епЯСЫна1)/1000) 11гаС = (Ь вЂ” 1)*1000 + 1; 1аеС = ш1п(11геС+999, 1епЕСЫх)); х шасгйх = гершас(хШгес:1авс), 1, псьеса); у шаСтйх = гершаС(уИ1гвс:1аеС), 1, пСЬеса); на1 шаСг1х = гершаС(на1И1геС:1аеС), 1, пСЬеСа); СЬеса шаСгйх = гершаС(СЬеса, е1хе(х шасг1х, 1), 1)эр1/180; гЬо шаСг1х = х шаст1х.асов(СЬеса шаСг1х) + у шасгтх.еейп(СЬеса шаСг1х); е1оре = (пгЬо — 1)/(гЬо(епй) - тЬо(1)); гЬо Ып 1пйех = топай(е1орее(тЬо шаст1х - гЬо(1)) + 1); СЬеСа Ып Апйех гершаС(1:пСЬеса, е1хе(х шаСгйх, 1), 1); '/ ТаЬе айнапсаЕе о1 СЬе 1асС СЬаС СЬе ЯРАКЯЕ 1ипсС1оп, иЫсЬ '/ сопеСгпссе а ератее шаСг1х, ассишп1аСее ча1пее нЬеп 1прпС '/ 1пййсее аге гереасей.
ТЬаС'и СЬе ЬеЬанйог ее напС 1ог СЬе '/ НощЬ Сгеле1отш. Не иелС СЬе оисрпС Со Ье а Тп11 (поператее) '/ шасг1х, Ьоеечег, ео ее са11 1ппсС1оп РОьь оп СЬе опсрпС о1 '/ ЯРАНЯЕ. Ь = Ь + Тп11(еретее(гЬо Ып 1пйех(:), СЬеса Ып 1пйех(:), на1 шасг1х(:), птЬо, пСЬеса)); епй Пример 10.5. Иллюстрация преобразования Хафа. Здесь мы продемонстрируем использование функции ЬопЕЬ при обработке простого двоичного изображения. Прежде всего, построим изображение, у которого имеется несколько изолированных точек переднего плана. » 1 = кетов(101, 101); »1(11)1Х(1011)1)х(1101)1 » 1(101, 101) = 1; 1(51, 81) = 1; ..огне~но, ...,, ~ ты 4Д Рис. 10.10, а) показывает наше тестовое изображение.
Теперь мы выполним преобразование Хафа и отобразим результат на графике. б) а) 80 бО 40 20 0 20 40 60 80 Рис. 10.10. а) Двоичное изображение с пятью точками (четыре точки находятся в углах изображения). 6) Преобразование Хафа, поквзаяное с помощью функции 1шваав. е) Альтернативный график с раэмеченным осями. (Точки на рис. а) были увеличен для лучшей видимости) ~~( 416 Глава )а Сегзлентаиил изображений » Н = ЬоияЬИ); » 1шяЬоч(Н, [ )) На рис. 10.10, б) приведен результат, отображенный на графике стандартной функцией 1шяЬоч.
Однако более наглядная визуализация преобразования Хафа получается на большем графике, на котором по осям отмечены координаты. В следующем программном фрагменте функция ЬоияЬ вызывается с тремя аргументами. Два вторых выходных аргумента содержат величины д и р, отвечающие каждой соответствующей паре индексов строки и столбца матрицы преобразования Хафа. Эти векторы сЬеса и гЬо можно передавать функции 1шяЬоч в виде дополнительных аргументов для разметки горизонтальных и вертикальных осей на графике.
Функции 1шяЬоч также передается опция 'посгиея1хе'. Команда ах1я подается для включения отображения осей и представления графика в прямоугольной форме. Наконец, функции х1аЬе1 и у1аЬе1 (см. 3 3.3.1) используются для помещения возле координатных осей греческих букв, представленных в стиле [4ТЕХ. » [Н, СЬега, гЬо) = ЬоияЬ(1); » 1шяЬоч[сЬеса, гЬо, Н, [ ), 'посгиея1хе') » ах1я оп, ах1в погша1 » х1аЬе1(' 1СЬега'), у1аЬе1('1гЬо') На рис.
10.10, е) показан результирующий график с соответствующей разметкой осей. Пересечение трех синусоид в точках г45' указывает на то, что на исходном изображении 1 имеется два множества, состоящие из трех колинеарных точек. Пересечение двух синусоид в точках (О, р) = ( — 90,0), ( — 90, — 100), (0,0) и (0,100) свидетельствует о присутствии четырех множеств колинеарных точек, которые лежат вдоль вертикальных и горизонтальных осей. П 10.2.1.
Нахождение максимумов преобразования Хафа Первый шаг использования преобразования Хафа для обнаружения линий и связывания состоит в нахождении локальных максимумов преобразования. Поиск множества максимумов преобразованием Хафа может быть вполне перспективным. В силу квантования пространства цифрового изображения и пространства параметров, а также по причине того, что края и перепады на типичных изображениях не являются совершенно прямыми, максимумы преобразования Хафа могут достигаться более чем в одной ячейке накопления.
Эту сложность можно преодолеть с помощью следующей стратегии. 1. Найти ячейку преобразования Хафа, в которой лежит наибольшая величина, и записать ее местоположение. 2. Опорожнить (обнулить) ячейки в ближайшей окрестности положения, найденного на шаге 1. 3. Повторять шаги 1 н 2 до тех пор, пока желаемое число максимумов не будет найдено, илн после достижения заданного порога. Функция ЬоияЬреа1ся реализует зту стратегию. 1ипсс1оп [г, с, ьпеч) = ьоияьреаья[ь, пишреакя, сьгеяьо1о, пьооо) .ОЪ пу Г б ~Ы 4Д %НОООНРЕАКЯ Оепесп реалия 1п НощЬ Сгалв1огш. У. [Н, С, ННННГ) = НОООНРЕАКБ(Н, МОМРЕАКЯ, ТННЕЯН010, МНООО) 6епеспв % реа1св 1п СЬе НоиЕЬ Сгвлв1огш шапг1х Н. МОМРЕАКЯ врес111ев СЬе % шах1шшп пшпЬег ой реа1с 1осаС1опв Со 1оо)с 1ог.
Ча1иея оХ Н Ье1ою % ТННЕЯН010 в111 поС Ье сопвгбеге6 Со Ье реа)св. МНООО 1в а % сво-е1ешепС песСог ярес11у1пЕ СЬе яхве о1 сЬе яирргевв1оп % пеАЕЬЬогЬоо6. ТЬАв 1в СЬе пе1НЬЬогЬоо6 агоип6 еасЬ реа[с СЬаС 1в % веС Со хего аХСег СЬе реа1с 1в 16епС111е6. ТЬе е1ешеппв о1 МНООО % шивС Ье ров1С1пе, о66 1ппеНегв. Н ап6 С аге СЬе гою ал6 со1ишп % соог6гпаСев о1 СЬе 16епС111е6 реа1ся. НМЕИ Ав СЬе НоиЕЬ Сгапв1огш % ВАСЬ реа1с пе1ЕЬЬогЬоо6 яирргевяе6. % % 11 МНООО 1в ош1ССе6, 1С 6е1аи1Св Со СЬе яша11евС о66 па1иея >= % яхве(Н)/50. 11 ТННЕЯН010 Ав ош1ССе6, 1С 6е1аи1Св Со % 0.5*шах(Н(;)).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
