Компьютерные книги
Главное меню
Главная Поиск по сайту Добавить материал О нас Карта книг Карта сайта
Реклама
computersbooks.net -> Добавить материал -> Графика -> Гонсалес Р. -> "Цифровая обработка изображений" -> 341

Цифровая обработка изображений - Гонсалес Р.

Гонсалес Р., Вудс Р. Цифровая обработка изображений — М.: Техносфера, 2005. — 1072 c.
ISBN 5-94836-028-8
Скачать (прямая ссылка): cifrovayaobrabotkaizobrajeniy2005.djvu
Предыдущая << 1 .. 335 336 337 338 339 340 < 341 > 342 343 344 345 346 347 .. 349 >> Следующая

х к
Х\ ¦¦¦
Например, рассмотрим грамматику деревьев G = (N, X, Р, г, S), у которой N = {S, X}, X = {а, Ь, с, d}, множество продукций
S —^ d X —> с X -» а X —> b
XX X
и функции ранжирования г{а) = {0}, г(Ь) = {0}, г{с) = {1} и lid) = {2}. Соответствующий автомат на деревьях, At = (Q, F, {fk \ к є X}), строится следующим образом. Полагаем Q={S,X}, F = {5} и {fk \ к є X} = = {fa’fb’fofd} с отношениями следующего вида:
12.3. Структурные методы распознавания 1051
/о={(0;ЛГ)}, как следует из продукции X —» а как следует из продукции X —» b
Л ={№*)}. как следует из продукции X —» с
X
fd ={(АГ,А";5')}, как следует из продукции S—> d
X X.
Отношение fa интерпретируется следующим образом: вершине, помеченной символом входного алфавита а, у которой нет потомков (отсюда символ 0 пустого множества), присваивается состояние X. Аналогично интерпретируется отношение fa. Интерпретация отношения fc состоит в том, что вершине, помеченной символом с, у которой имеется один потомок с состоянием X, также присваивается состояние X. Отношение fd интерпретируется так, что вершине с пометкой d и двумя потомками, каждый с состоянием X, присваивается состояние S.
Чтобы продемонстрировать, как такой автомат на деревьях распознает деревья, которые порождает описанная выше грамматика, рассмотрим дерево, показанное на Рис. 12.29(a). Вначале автомат At присваивает состояния листьям дерева а и b посредством отношений fa и flj соответственно. В данном случае обоим листьям присваивается состояние X, как показано на Рис. 12.29(6). Теперь автомат поднимается на один уровень от каждого листа, что позволяет присвоить состояние вершине с на основе отношения fc и состояний потомков этой вершины. Присваивается опять-таки состояние X, как показано на Рис. 12.29(b). Поднимаясь вверх по дереву еще на один уровень, автомат встречает вершину d, у которой обоим потомкам присвоены состояния, что позволяет применить отношение/^, требующее присвоить вершине d состояние S. Поскольку эта вершина является последней, и состояние S входит в множество заключительных состояний F, данный автомат распознает предложенное дерево, т.е. допускает его в качестве правильного представителя языка приведенной выше грамматики деревьев. На Рис. 12.29(г) показано окончательное представление последовательностей состояний, возникающих на путях от листьев к корню.
1052 Глава 12. Распознавание объектов
а б в г
и д /\
[Х\ а [X] с
\
га ъ
Рис. 12.29. Этапы работы автомата на деревьях при обработке дерева от листьев к корню: (а) Исходное дерево, (б) Присвоение состояний концевым вершинам (листьям), (в) Присвоение состояний промежуточным вершинам, (г) Присвоение состояния корневой вершине дерева.
Пример 12.13: Применение грамматик на деревьях для опознавания событий на снимках, полученных с помощью пузырьковой камеры.
¦ Снимки (изображения) с пузырьковых камер в большом количестве регистрируются в ходе экспериментов в физике высоких энергий, когда пучок элементарных частиц с определенными свойствами направляется на мишень, материал которой содержит известные ядра. Типичное событие состоит в соударении частицы с ядром и возникновении вторичных частиц, испускаемых в точке столкновения, треки (следы) которых регистрируются на изображении, как это видно на Рис. 12.30. Треки частиц входного облучающего пучка представляют собой параллельные горизонтальные линии. Обратите внимание на естественную древовидную структуру в центре фотографии, соответствующую событию соударения.
За время обычного эксперимента снимаются сотни тысяч фотографий, многие из которых не содержат интересующих событий. Ручной анализ и классификация таких снимков представляют собой трудоемкую и утомительную работу, чем и продиктована необходимость применения методов автоматического распознавания событий.
d
[X] а [Х\ с
[Х\ Ь
12.3. Структурные методы распознавания 1053
Рис. 12.30. Фотография, полученная с использованием пузырьковой камеры.
[Fu, Bhargava].
Можно построить грамматику деревьев G = (N, X, Р, г, S), которая порождает деревья, соответствующие типичным событиям, возникающим в водородной пузырьковой камере при попадании в нее пучка положительно заряженных частиц. В этом случае N = {5, Х{, Х2}, ? = {а, Ъ) и непроизводные элементы имеют следующую интерпретацию:
а: — выпуклая дуга Ь: — вогнутая дуга.
Множество Р состоит из следующих продукций:
S —> Q
X, х2
Z, X, х2 х2
Х\ —> а Х^ —> b Х2 —у b
Хг
Функции ранжирования в этой грамматике имеют вид г(а)= = {0, 1, 2, 4, 6} и г (Ь) = {0, 1}. Продукции с ветвлением представляют число треков, выходящих из точки столкновения, это число является четным и обычно не превышает шести. На Рис. 12.31(a) изображена схема столкновения в зафиксированном на Рис. 12.30 событии, разделенная
1054 Глава 12. Распознавание объектов
на выпуклые и вогнутые участки, а на Рис. 12.31(6) показано соответствующее представление в виде дерева. Это дерево, как и возможные его варианты, допускают порождение вышеприведенной грамматикой.
Автомат на деревьях, способный распознавать деревья описанного вида, задается с помощью изложенной выше процедуры. Таким образом, для построения автомата А, = (Q, F, {fk\ke I}) полагаем Q = {5, X(, Х2}, F= {iS) и {Д | к є X} = {fa,fij}. Отношения определяются следующим об-
Предыдущая << 1 .. 335 336 337 338 339 340 < 341 > 342 343 344 345 346 347 .. 349 >> Следующая
Книги
Web-программирован-
ие
Аппаратное обеспечение Графика Руководство по П.О. Самоучитель Теория программирования Фотошоп Языки программирования
Новые книги
Вирт Н. "Систематическое программирование " (Теория программирования)

Эком "Microsoft Excel 2000 шаг за шагом Русская версия самоучитель " (Самоучитель)

Поляков А.Ю. "Методы и алгоритмы компьютерной графики в примерах Vizual C++" (Графика)

Баяковский Ю.М. "Графическая библиотека Open GL " (Графика)

Валиков А. "Технология " (Языки программирования)
Авторские права © 2013 ComputersBooks. Все права защищены.