Робототехника.Фу, Ли, Гонсалес (962794), страница 68
Текст из файла (страница 68)
Каждой дуге (ль л;) приписывается стоимость с(ль л,). Последовательность вершин л(, пм ..., лго где каждая вершина лг является преемником вершины гг,: ], называется путем от и, к лзо а стоимость пути определяется формулой Элемент контура мы определим как границу между двумя пикселами р и г) (рис. 8.6). В данном контексте под контуром понимается последовательность элементов контура. Для иллюстрации применения введенных понятий к определению контура рассмотрим образ размерностшо ЗХ 3, приведенный на рпс. 8.7, где цифры в скобках обозначают интенсивность, а без скобок — координаты пикселов.
Каждому элементу контура, определенному пикселами р и с), приписываем стоимость с (р, а) = Н вЂ” ((' (р) — ! (д)], (8.2-7) где Н вЂ” наибольшее значение интенсивности образа (в данном случае оно равно 7), ('(р) — значение интенсивности в точке р, а; !(с)) — значение интенсивности в тозке а. Рис. 8.8. Граф для определения нонтура образа, приведенного на рис, 8.7. Для каждой вершины пары (а, Ь) (с, о) соответствуют точнамр и д. Отметим, что если идти по образу сверху вниз, то р будет находиться справа, Путь минимальной стоимости помечен штриховыми линиями !191).
Граф для этой задачи показан на рис. 8.8. Каждая вершина графа соответствует элементу контура, и две вершины связываются дугой в том случае, если два соответствующих элемента контура, взятые последовательно, могут быть частью контура. Стоимость каждого элемента контура, рассчитанная по уравненшо (8.2-7), показана дугой, ведущей в этот элемент, а целевые вершины показаны двойными прямоугольниками. Каждый путь между начальной и целевой вершиной является возможным контуром. Для простоты предполагалось, что контур начинается в верхнем ряду и заканчивается в последнем, так что первый элемент контура может быть только ((О, 0), (О, !)] или ((О, !), (О, 2)] и последний элемент [(2, 0), (2, 1)] или ](2, !), (2, 2)], Путь минимальной стоимости, рассчитанный по уравнению 404 (82-6), показан штриховой линией, а соответствующий контур представлен на рис.
8,9. Как правило, задача определения пути минимальной стоимости непроста с иычислительной точки зрения. Обычно критерием оптимальности является быстродействие. Алгоритм, приведенный ниже, типичен для класса процедур, использующих эвристики с целью сокращения объема поиска. Пусть г(п) — оценка стоимости пути минимальной стоимости из начальной вершины з в целевую вершину, причем путь проходит Ф Ф через вершину п. Эту оценку можно (О (1) представить в виде суммы пути миним ал ь ной стоимости з в и и оценки стоимости пути из п в целевую вершину, т.
е. и г (и) = д (и) + й (и). (8.2-8) (5) (з) Рис, 8.9. Контур, соот ветствуюшпй пути мини мальной стоимости, по назанному на рис. 8.8. г(п ) = а(и)+ с (п, и ), пометить его ОРЕХ и направить указатели от него к вершине и. 408 Здесь й ( п ) является оце нкой стоимости пути наименьшей стоимост и из з в и, е и определенного ранее, а и(п) определяет- (5) (О [о) ся с помощью использования эвристической информации (например, проводя рас. ширение только некоторых вершин, основанное на предварительном вычислении стоимостей при определении путей, ведущих к вершине Й(п)).
Алгоритм поиска на графе, основанный на применении оценки г(п), приведен ниже: Шаг !. Поместить стартовую вершину ОРЕХ и положить гг(з) =О. Шаг 2. Если нет вершин, помеченных как ОРЕХ, то выход на аварийный останов; в противном случае продолжение работы. Шаг 3. Пометить СЕОБЕ7) помеченную ОРЕХ вершину и, оценка которой г(п), определенная по уравнению (8,2-8), имеет наименьшее значение. (Связи для минимальных значений г устанавливаются произвольно, но всегда в пользу целевой вершины.) Шаг 4. Если п является целевой вершиной, то выход на останов с выдачей пути, полученного в результате обратного прохождения по указателям направления; в противном случае продолжение работы.
Шаг 6. Расширение вершины п, т. е. генерирование всех ее преемников (если преемников нет, переход к шагу 2). Шаг 6, Если преемник п, не помечен, положить Шаг 7. Если преемник л; помечен СЕОЕЕ27 или ОРЕИ, изменить его значение по формуле д'(лс) = пни [д(лс), д(л)+ с(л, л)], Пометить ОРЕМ те преемники, помеченные СЕОБЕсс, значения у' которых были уменьшены таким образом. От этих вершин направить указатели к вершине п.
Перейти к шагу 2. Как правило, этот алгоритм не гарантирует нахождение пути минимальноп стоимости; его преимущество заключается в быст. казан зашумленный образ, и па рис. 8.10,б результат сегментации контура, полученный с помощью поиска на соответствующем графе путей наименьшей стоимости. В данном примере были использованы эвристики, предотвращающие расширение тех вершин, стоимости которых превышали заданное пороговое значение. 8.2.2. Определение порогового уровня Понятие порогового уровня (порога) введено в равд.?.6.5 как тест вида Т=Т[х, у, р(х, у), )(х, у)], (8.2-9) Рис.
8.!О. Зашумленный образ (а) и результат определении контура, полученного с помощью метода эвристического поиска на графе [292] (б). родействии за счет использования эврнстик. Однако можно показать, что, если ([(л) является нижней границей стоимости пути минимальной стоимости от вершины п к целевой вершине, тогда процедура действительно определит оптимальный путь к целевой вершине [!15]. Если эвристическая информация отсут. ствует, т. е.
й =— О, процедура сводится к алгоритму постоянной стоимости [59] Пример. Типичный результат, полученный в результате работы этой процедуры, приведен на рис. 8.10. На рис. 8.10,а по- лов ° з ° ! й!!»мъмм!. !»!Пъй ° ъ ° с м!аъ[ ..!м !»»! ээ»ээээ»»ъ !1!. ° - 1 ЪН1. !111[аа ,з» ° .Нине»ееь 1.. ! ° ° [меев ° ! сава 3 ! [Нна»[нее» ° 1 ! «месееа ! ! ! с ° н нннмнзее «.[[1-ммеем!«свес ° и " и авиа»а»аее ! ° и ! Эевееваани си Ъ. ° ° [! ° 1! миан а»айва! ! .Не[есме е .и! ° ° ° зс.
° .аэнзнме» !ма»а»мез»«1 .», «» с! [[ЪЪ»«нааанм..»!.ванн[а«».. [и .а 3! -ЪВ «нмваме-.еесааеее»м,в[! ° ° ° !ЪИ! .!3[»энне!Эмэс[Нам-ЕВЪ °, !». н ! .. Н»эьемьэзй !нее»ээВ!мз[»Э1 ° «1!«3 ° !манам!э»еазаеа»евсее!а ° . с ° ° * ! на аанэ»аве,маа.!аваева»»нз, ! ° ° о сс «. На»нее«еееееееаесеее»ваес».» ° ° аии! [..аамнанэемаааеэааааъее» ! ° ° »1 . саин!Э«майме»е»мнем«в!и! .». з 1, 1м»[Вне«извне !Ннавэьзэ[,.- ° и Ъ[ъз.ъ!На«аее«несемнеээин 1,.1 ° .и и йэнсмнэвэа иа» бее[[««,« ° » 3 ° 1 «3.« еиаеаее!н.
° .аман. аз». ° «![3 завам»!еен«н! "««В»м 1-,1 .3»1 Э«ВИ[ВВ! ° «1 °, 1. С ° !.!!Ъ и! . !«ниммеа»ни»- 1. ° и! ° з» з ! ° ° «! ° 13»ЪР«наев «*1м[ !«! ° — «Ъ! Ъза ! н»аваев»!ее«ъ!»и и «! ° и -с. м-:«ъв 33»аазаавъ. ы..и.-с! [1. - 1 !![11 ° энэааэм«, и «а[!1». !«!. ° ° ° ° . ° с, .«1![и[[«...[! ...,и! 1 °, »а! .. ° ° ни.аэ«.зм! и ° !., ! ° ° ° - ».!««ъ! ° 1мс ° «[и! ! ° 1-[а-а.!«. ! а- ».и, » «.11.
° ° еьа ° 6 Ь ъ э Ъ э аэ а ее е а й ° а в е а Ь ° ° В в В Э ° Ъ ° ° » 6 а ° Ь 3 ° ° Ь 3 ° э а В э а 6 Ь а а а » е В 6 В а В э Ь 6 э 6 Р В е а» в э Ь» а 3 9 а»а»» 3 а а э Э Э а В а 66 Э 6!»3 ааа где 1(х, у) — интенсивность в точке (х, у), Р(х, у) — некоторое локальное свойство, определяемое в окрестности этой точки. Пороговое изображение дается следующим выражением: ( 1, если [(х, у)>Т, ][ О, если )[(х, у)(Т, (8,2-! О) так что пикселы в д(х, у), имеющие значение 1, соответствуют объектам, а пикселы, имеющие значение О, соответствуют фону.
В уравнении (8.2-10) предполагается, что интенсивность объектов больше интенсивности фона. Противоположное условие получается путем изменения знаков в неравенствах. Глобальные и локальные пороги, Если значение Т в уравнении (8,2-9) зависит только от 1(х, у), то, как показано в разд.
7.!з.5, порог называется глобальньсм. Если значение Т зависит как от [(х, у), так и от р(х, у), порог называется локальным. Если, кроме того, Т зависит от пространственных координат .к и у, в этом случае он называется динамическим порогом. Глобальные пороги применяются в ситуациях, когда имеется явное различие между объектами и фоном и где освещенность достаточно однородна.
Методы обратной и структурированной освещенности, изложенные в равд. 7.3, обычно дают изображения, которые могут быть сегментиронаны путем применения глобальных порогов. Но, как правило, произвольное освещение рабочего пространства приводит к изображениям, которые, если исходить нз определения порогового уровня, требуют локального анализа для компенсации таких эффектов, как неоднородность освещения, тени и отражение. Ниже мы рассмотрим ряд методов для выбора порогов, используемых при сегментации.
Хотя некоторые из них могут применяться для выбора глобального порога, они обычно используются в ситуациях, требующих анализа локального порога. Выбор оптимального порога. Часто рассматривают гистограмму, состоящую из суммы значений функции плотности вероятности. В случае бимодальной гистограммы аппроксимирующая ее функция дается уравнением р(а) = Р,р,(з)+ Рере(2), (8.2-11) где интенсивность г — случайная переменная величина, р,(г) и ра(г) — функции плотности вероятности, а Р, и Ра — априорные ГГ1!!гтзгусйбй 1Сгргв В а Т ФглгэлмггХякуго э У Рис. 8,11, Гистограмма интенсивности (а) и ее аппроксимация в виде суммы двух функний плотности вероятности (6).
вероятности. В данном случае априорные вероятности означают появление двух видов уровней интенсивности на образе. Например, рассмотрим образ, гистограмма которого приведена на рис. 8.11,а. Полная гистограмма может быть аппроксимирована суммой двух функций плотности вероятности, как показано на рис. 8,11, б. Если известно, что объект состоит нз светлых пикселов и они занимают 20 % площади образа, то Р, = 0,2, Необходимо, чтобы Р, + Ра=!. (8.2-1 2) 408 В данном случае это означает, что на остальную часть образа приходится 80 % пикселов фона.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
