Робототехника.Фу, Ли, Гонсалес (962794), страница 76
Текст из файла (страница 76)
Скелет об- ласти можно определить через преобразование средних осей (ПСО), предложенное в работе [24]. ПСО области )7 с грани- цей В определяется следующим образом. Для каждой точки р из 77 мы определяем ближайшую к ней точку, лежащую на В. Если р имеет больше одной такой точки, тогда о ней говорится, что она располагается на средней оси (скелете) области Важно отметить, что понятие «ближайшая точка» зависит от определения расстояния (равд.
7.5.3), и поэтому на результаты операции ПСО будет влиять выбор метрики. Некоторые при- меры применения евклидовой метрики даны на рис. 8.38. Хотя ПСО дает довольно удовлетворительный скелет обла- сти, его прямое применение затруднительно с вычислительной точки зрения, поскольку требуется определение расстояния между каждой точкой области и границы, Был предложен ряд алгоритмов построения средних осей, обладающих большей вычислительной эффективностью. Обычно это алгоритмы про- реживания, которые итеративно устраняют из рассмотрения точки контура области так, чтобы выполнялись следующие ограничения: 1) не устранять крайние точки; 2) не приводить к нарушению связности; 3) не вызывать чрезмерного размывания области, 448 Хотя были сделаны некоторые шаги в применении скелетов для задач распознавания черно-белых образов с несколькими уровнями интенсивности ]70], (256], этот тип представления обычно связывается с бинарными данными.
Ниже мы рассмотрим алгоритм, разработанный Накаши и Шингалом !204]. Эта процедура быстрая, проста в реализации и, как показано ниже, во многих случаях дает более хорошие результаты, чем другие алгоритмы прорсживання. Сначала введем несколько определений. Используя бинарные данные, й' б Рис. 8.38. Средние оси трех простых областей, обозначим точки области единицами, а точки фона — нулями. Назовем их соответствс>шо темнылш и светлыми точками.
Точкой контура называется темная точка, которая имеет в своей окрестности, состоящей из четырех точек, по меньшей мере одну светлую. Конечной точкой называется темная точка, которая в своей окрестности, состоящей из восьми точек, имеет одну и только одну темную точку, Точкой разрыва называется темная точка, устранение которой привело бы к нарушению связности области.
Для всех алгоритмов прореживания шум и другие ложные изменения границы могут приводить к значительным отклонениям определяемого скелета (наиболее явно это показано на рис. 8.38,б). Поэтому предполагается, что границы всех областей перед процессом прореживания были предварительно сглажены, например, с помощью процедуры, рассмотренной в равд. 7.6,2. В соответствии с приведенным на рис. 8.39 расположением точек окрестности точка контура р, используемая в алгоритмах прореживания, может быть следующего вида: !) левая точка контура, у которой левая соседняя точка я4 светлая; 2) правая точка контура, у которой соседняя точка я, светлая; 3) верхняя точка контура, у которой соседняя точка пх свет- 447 449 15 К.
Фу в аж лая; 4) нижняя гочка контура, у которой соседняя точка ав светлая. Иногда точку можно одновременно отнести сразу к нескольким из этих видов. Например, темная точка р, у которой ао и нч светлые, будет одновременно правой и левой точками контура. Затем сначала рассматривается процесс идентификации левых точек контура, которые должны быть устранены, и уже потом процедура распространяется на другие виды точек. Рис. 8.39.
Обозначение для соседних с точкой р пикселов, которое используется в алгоритме прореживания (204). Точка контура р помечается, если она не является конечной точкой или точкой разрыва, а также если ее устранение не вызовет чрезмерного размытия (как показано ниже), Проверка этих условий осуществляется путем сравнения окрестности точки р, состоящей из восьми точек с окнами, приведенными Рис. 8.40. Разметив окрестности из восьми соседних точек темной точки р. Лля приведенных окон точка р не помечается, Звездочкой обозначена тем. ная гочка, а и и е могут быть либо темными, либо светлыми (204). на рис. 8.40, где р и звездочка являются темными точками, а г( и е могут быть либо темными, либо светлыми точками, Если окрестность точки р соответствует окнам, показанным на рис.
8.40, а — в, возможны два случая: !. Если все точки гх' светлые, тогда р является конечной точкой. 2. Если хотя бы одна точка д темная, тогда р является точкой разрыва. В любом из этих случаев точка р не должна помечаться. Анализ окна, представленного на рис. 8.40,г, более сложный. Если хотя бы одна из точек д и е темная, тогда точка р является точкой разрыва и не должна помечаться. Однако необходимо рассмотреть другое расположение точек.
Предположим, что все точки д светлые, а точки е могут быть либо темными, либо светлыми. Это условие дает восемь вариантов, показан- ных на рис. 8.4Е Для конфигураций а — в точка р конечная, а для конфигурации г она является точкой разрыва. Если бы р была устранена в конфигурациях д и е, то на примере легко показывается, что это устранение вызвало бы чрезмерное размытие наклонных областей шириной 2, На конфигурации и точка р относится к так называемой иьчоре, обычно появляющейся вследствие короткого ответвления или выступа области.
Поскольку предполагается, что граница области вначале сглажена, появление шпоры во время процесса прореживання рассматривается как важный элемент описания формы области, ху е о/с а Рис 8.41. Возможные конфигурации, когда на рис. 8,40 точка о светлая, а и может быть темной, * или светлой (204).
и поэтому точка р не должна быть устранена. Наконец, если все изолированные точки были устранены ранее, появление во время процесса прореживания конфигурации з означает, что область свелась к единственной точке; се устранение означало бы ликвидацию последней остающейся части области. Аналогичные рассуждения применяются, когда точки д и е меняются местами или же когда они могут быть как темными, так и светлыми.
Главным является то, что каждая левая точка контура р, имеющая окрестность нз восьми точек, соответствующую окнам, показанным на рис. 8.40, не должна быть устранена. Проверка окрестности точки р на соответствие четырем окнам (рис. 8.40) осуществляется по формуле булевой алгебры логики: В4 =- ао ' (% + аз + па+ нт) ' (аз + нз) ' (нз + па) (8.3-6) где индекс у В означает, что пч является светлой (т. е. р — лв. вая точка контура), точка — логическое И, плюс — логическое т,= ~ ~~' хлуо)(х, у), (8.3-!О) и ...:.1.!.... оо». мо ° о оооо ° $ о о о о м ° по о а (8.3-1 Н где — впо х= —, тоо ' тоо у =— тро (8.3-1 2) про Ч ря о роо (8.3-!3) где (8.3-14) 1$» 451 ИЛИ, минус — логическое отрицание, а по 1= 1, 2, 3, 4 определены на рис.
8.39. Ранее непомеченным темным точкам присваивается значение 1 (ИСТИНА), светлым, а также помеченным точкам — значение 0 (ЛОЖЬ). Тогда, если В4=! (ИСТИНА), мы помечаем точку р. В противном случае точка р остается непомеченной. Легко показать, что зти условия, наложенные на В4, одновременно выполняются для всех четырех окон, приведенных на рис.
8.40. Подобные выражения получаются для правых точек кон- тура Во — — гго ' (па+ па+ па+ па) ° (па+ и,) (и, + пя), (8.3-7) для верхних точек контура Вя = па ' (по + гг4+ пя + пг) ' (по + %) ' (па + гг4) (8 3 8) и для нижних точек контура Ва — †(по + п1 + па + по) .(по + па) (пя + йг).
(8.3.9) Используя эти уравнения, алгоритмы прореживания работают итеративным образом, два раза сканируя данные. Сканирование может осуществляться либо вдоль строк, либо вдоль столбцов образа, но этот выбор обычно влияет на конечный результат. В первом случае для пометки левых и правых точек контура применяются В4 и В,; при втором сканировании для пометки верхних и нижних точек контура применяются Вя и Вя. Если после второго сканирования нс появилось новых помеченных точек контура, алгоритм прекращает работу, а искомый скелет состоит из непомеченных точек; в противном случае процедура повторяется.
Отметим, что предварительно помеченным темным точкам при вычислении булевых выражений присваивается значение О. Альтернативная процедура состоит в присвоении любой помеченной точке значения 0 во время работы алгоритма, и следовательно, обработка точек фона и создание скелета происходят в конце работы процедуры. Этот метод более прост в реализации за счет отбрасывания всех других точек области. Пример. На рис. 8.42,а приведена бинарная область, а на рнс. 8.42,б — скелет, полученный с помощью описанного выше алгоритма.
Для сравнения на рис. 8.42, в приведен скелет, полученный на основе тех же данных с помошью хорошо известного алгоритма прореживания (233]. Различие в результатах очевидно. Инварианты моментов, В равд. 8.3.1 говорилось, что для описания границы области можно использовать дескрипторы Фурье, инвариантные относительно перемешения, поворота и изменения масштаба.
В том случае, когда область задается множеством точек, она может быть описана моментами, инвариантными относительно этих действий. Обозначим через 1(х, у) интенсивность в точке области (х, у). Тогда для данной области момент (р+ д) порядка определяется выражением где суммирование провод1пся по всем пространственным координатам (х, у) точек области. Центральный момент порядка Рис. 8,42.
Бинарная область (о). Скелет, полученный с помощью одного ал. горитма орорежиаания !б), и скелет, полученный с помощью другого алгоритма нрорежиааиия !в) !2041„ (р+ 1)) определяется следующей формулой: )яро = х„х„(х — х)р (у — у)'1(х, у), х Ворлшрованный центральный момент порядка,,$)у+ д) опреде- ляется выражением яо=" 'сд-~'+1 дЛя (1г+д)=2 3,... Используя только нормированные центральные моменты 2- и 3-го порядков, можно вывести следующий набор инвариамтов зоаиентов: Ф~ = Что+ Чол 4~х — (т[го Чоз)з + 4Ч Фз = (Чзо — ЗЧи)'+ (ЗЧл — Чоз)' та=(Чзо+Чм) +(Чл+Чоз) тз=(Чзо ЗЧи)(Чзо+ Чга)((Чзо+Чм) З(Чл+Чоз)1+ + (оЧл — Чоз) (Чл + Чоз) Р(Чзо+ Чл)' — (Чл + Чоз)'), (8.3-10) 'таз=(Ч»з Чоз)((Чзо+ Чм)' (Чл+ Чез) тт+ + 4т[п (т[л+ Ч,а)(т[л+ Чоз), (8.3-20) 'тат =(ЗЧл Чоз)(Ъо+ Чм) ((Чзо+ Чм) 3(т1л + Чоз) ) + + (ЗЧга — Чзо)(Чл + Чоз)(3(Чзо+ Чм) (Чл + Чоз) ) (8 3 21) Как показано в работе (1281, этот набор моментов инвариантен относительно перемещения, поворота и изменения масштаба.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
