Дуда Р., Харт П. - Распознование образов и анализ сцен (1033979), страница 100
Текст из файла (страница 100)
Простые эвристические правила, которые мы обсуждали, для объединения областей картинки в объекты были придуманы Гузманом (1968); он развил эти простые методы до высокой степени совершенства и построил алгоритм, способный анализировать идеальные картинки, достаточно сложные, чтобы вызвать по крайней мере кратковременное замешательство у человека. Брайс и Феннема (1970) включили простую версию этих правил 'в программу, использующую области в качествеосновноговидадаиных на протяжении всего анализа сцены. Определение трехмерной структуры по расширенной монокулярной информации было исследовано Фальком (1970), который разработал метод дуальных графов для определения количества необходимой дополнительной информации.
В неопубликованном отчете Хорна (1968) обсуждается использование данных фокусировки для определения информации о дальностии. Читатель, видимо, уже заметил, что некоторые методы, обсуждавшиеся в этой главе, в конце концов приводят к некоторому виду комбинаторного поиска. Грамматический разбор представляет собой существенно поисковый процесс; процедура разметки линий использует дерево поиска; и, хотя мы не показали это ясно, метод дуальных графов, анализирующий степени свободы в трехмерной структуре трехгранного тела, также связан с процессом поиска. Задачи комбинаторного поиска такого рода часто возникают в области искусственного интеллекта, и были исследованы общие методы для их эффективного решения.
Превосходное введение в этот класс методов дано в монографии Нильсона (1971). СПИСОК ЛИТЕРАТУРЫ Барроу, Поппльстоун (Вагго» Н. О., Рорр1е«1опе й. Л) («е1а11опа! деасг|риопг |и ре1иге ргосеаа!пх. |и Ма«|нов lа/в!!!раисе, 6, рр. 377— 396, В. Мецгег апб 1). М!сЫе, оба. (Агпег!сап Е!аеч|ег РиЬВаыпх Со., Нет« 'г'огас, 1971). Браяс, Феннема (Вгке С. м., Реппееа С. Ы) 5сепе апа!увм иа(пн гея(опа, Агц/!с|а1 /а/е/!/квасе, 1, № 3, 205 — 226 (Рап 1970). [Русский перевод в сб. «Интегральные роботы», вып. 2, «Мнр», М., !975, стр. 136 — 159.1 Букнайт (Вои)сп!яж 'вг. Л) А ргосебиге 1ог яепегапоп о| |вгее-гдеепа|опа! Ьаплопеб согпрйег ягарыса ргеаеп|а1|опв, Солил.
АСМ, 13, 527 — 536 (5ер1ееЬег !970). Гренандер (Огепапбег (),) Роипбацопа о| рапегп апа|уанч Яиаг/ег!у о/ Арр!мй Мам., 27, 2 — 55 (Арп! 1969). Гримсдейл (Опеьба|е (1. 1..) Аи!огпа1|с ра||егп гесояпп|оп — пе»ч гпогрьо1ох!са! «уйегп иа(пи а б!6|(а! сое. ри1ег, (Р!ге!вгг )Рог!й 65, 499 — 50! (ХочегпЬег 1959). Гуаман (Сеггпап А,) 1)есоероа!1(оп о| а ч|аиа! асепе |п1о !Ьгее-йеепа|опа| Ьойеа; Ргос. Р/СС» ЗЗ, Список лигаературы 291 — 304 (|968). [Русский перевод в сб. «Интегральные роботы», «Мир», М., 1973, стр. 241 — 268.] Дуда, Харт (Она К.
О., Наг! Р. Е.) Ехрег(веп(ь (п ксене апа1уыь, Ргос. Р!гзр НаИ. 5увр. !пдиь|г(а! КоЬоЬЬ рр, 119 — 130 (Арп| 1970). Кирш (К|гьсЬ К. А.) Соври|ег |п|егрге(аНоп о$ Епй!ВЬ 1ех1 апд р|с1иге ра11егпз, /ЕЕЕ Тгалз. Е!ес. Сотар., ЕС-|3, 363 — 376 (Аийиь|1964). Клоуна (С)отче» М. В.) Оп ьее|»»81Ыпйь, А гг|]|с(а$ Упге($|йепсе, 2, № 1, 79 — 1 |6 (5рг!пд 1971). $ Русский перевод в сб. «Интегральные роботы», вып, 2, «Мир», М., 1975, стр. 89 — 135,) Ледли (Ьеб1еу К. 5.) Н|й№ьрееб аи1ова1|с апа|уьы о$ ЬвгпесИса! р)с!иге», 5сгеасе, 146, 216 — 223 (Ос$оЬег 9, 1964).
Лоутрел (1.ошге| Р. Р.) А ьо|иНоп 1о 1Ье Ь|бдеп.Ипе ргоЫев 1ог соври(ег-бган ро]уйедга, УЕЕЕ Тганз. Совр., С-19, 205 — 213 (МагсЬ |970). Миллер, Шоу (М|11ег %. Р., 5Ьа» А. С.) ]Апдикй|с веИюдь !и р(с1иге ргссеьь!пй — а ьигчеу, Ргос. ГУСС, рр. 279 — 290 (ОесевЬег 1968). Нарасимхан (Ь]агаь!вйап К.) ЬаЬеИ|пй зсЬева1а апб зуп$асНс деьспрНоп о1 р|с1игеь, Ул[огтайол ал«$ Сои|го!, 7, 15$ — 179 (Уипе 1964). [Русский перевод в сб. «Автоматический анализ сложных изображений», «Мнр», М., 1969, стр.
87 — 110.] Нарасимхан (Ь[агаь|вйап К.) Оп 1Ье дезсг|рИоп, йепегаИоп, апд гесойпИюп о1с!аььеь о| р|с$игеь, (п Аи|огпа1|с 1п1егрге1аИоп апд С|ашйсаНоп о|1вайез, рр. ! — 42, А. Огаьье!И, еб. (Асабепис Ргеш, $(е»ч Уогй, 1969). Нильсон (Н|Вьоп Ь]. У.) РгоЫев-5о1ч|п5 Ме(йобз |п АгШЫ|а! 1п1еИ|йепсе (Мсбга«ч-НИ1, Ь[е»г Уогй, 197!). [Русскин перевод, Нильсон Н., Искусственный интеллект. Методы поиска решений, «Мир», М., 1973.] Пфальц, Розенфельд (Р|аИг У. 1., Коьеп(е!б А.] %еЬ йтапипагь, Ргос.
Уа|. Уо|л| Сопй оа А гг. Уаг., рр. 609 — 619, О. Е. %а]йег апд 1.. М. Р]ог1оп; ейы (Мау $969). Робертс (КоЬег1ь Ь. О.), МасЫпе регсер(|оп о! (Ьгее-б(вень|она! за| Ыь, $п ОрИса| ап«$ Е|ес(го-Ор||са! !и|оппаИоп Ргосеьь!пй, рр. 159 — |97, У. Т. Т|рре1, е1 а!., ебы (М|Г Ргезз, СлвЬпбйе, Мам., !965). [Русский перевод в сб. «Интегральные роботы», «Мир», М., |973, стр. 162 — 208.] Уинстон (%|па!оп Р.) Ьеагп|пй Ыгис1ига! безас(р1$опз 1гов ехавр1еь, ТесЬп|са! Керог1 МАС ТК-76, Рго|ес1 МАС, Маззасйиье($» |пь1Ии1е о1 ТесЬпо(ойу, СавЬг|бйе (5ер1евЬег 1970).
Уорнок (%агнией У. Е.) А ЬЫбеп-Ипе а]йогИЬв $ог ЬаШопе р|с1иге гергеьеп!а||оп, ТесЬп|са! Керог1 4 — 5, Оераг1гпеп| о$ Соптри1ег 5с|епсе, 1)п|чегзйу о1 Ь$(аи, 5аИ Ьайе СИу, (йаЬ (Мау |968). Фальк (Га]Ь (Ь) Соври|ег |п|егрге|аИоп о| ]врет(ес( Ипе ба!а аь а $Ьгее-б(гпепь!опа! ьсепе, 5!ап[огб Аг($$(с|а! |п1еИ|йепсе.
Рго]ес1, Мегпо А|М-!32, Соври1ег 5с|епсе Оераг|веп|, 5!ап(огб Ып(чег»$!у, 51ап(огд, СаШ. (Аийиь| !970). Фельдман, Грнс (Ее№птап У., От|ее О,) Тгапь(а|от»«гй|пй зуь!епгь, Солил. АСМ, $1, 77 — 1|3 (ГеЬгиагу 1968). [Русский перевод в сб. «Алгоритмы и алгоритмические языки», вып. 5, ВЦАН СССР, М,, |971, стр. |05 — 2|4.[ Фу, Свайн (Ги К. 5., 5»ча(п Р. Н.) Гл. 12. Состгмлоиио и обработка оиасаний Оп ьуп1ас||с раИегп гесойпйюп, |п бой|гаге Епй!пеег!пй, Чо(. 2, рр. 155 — !82, 3. Т.
Тои, еб. (Асабев(с Ргеьь, Ыечг Уогй, 197!). Хаффмаи (Нийвап Р, А.) |вроел|Ые оЬ)ес(ь аз попьепье ьеп1епсеып Масй!по !а!о!!!аеасе 6, рр. 295— 323, В. МеИгег апб Р. М|сЫе, ебж (Авег|сап Е1ьеч|ег РиЫ!ьЫпй Со., Нем Уогй 1971). Хорн (Ногп В.) Госил|пд, Аг|И|с|а1 1п!еИ(йепсе Мево № 150, Рго!ес1 МАС, МаььасЬиьеИь 1пь1Ии1е о| ТесЬпо!ойу, СавЪг!бйе, МаььасЬиьеИз (Мау !958).
Шоу (бйам А. С.) А |оппа| р|с|ше беьсг!рыоп ьсЬегпе аь а Ьаь|ь |ог р|с|иге ргосеьь|пй ьуь|егпь, !и/отта!!оа али Сол!го!, 14, 9 — 52 (1989). Шоу, Алан (5Ьатч А. С., А|оп С.) Рагь|пй о| йгаРЬ вЂ” геРгеьеп1аЫе Р|с|игеь, /. АСМ, 17, 453 — 481 (Ли!У 1970). Эванс (Ечапь Т. С.) Сггапнпа(!са1 |п!егепсе (есЬп!циеь |п раиегп апа!уь|ь, (п 5оИъаге Епй!пеег1пя, тго! 2, рр. 183 — 202, Ю. Т. Тои, еб. (Асаг!епис Ргеьь, Мети г'ог|г, 1971). Эрли (Еаг!еу 1.) Ап еИ|с|еп| соп|ех( Атее рагь|пй а)йогИЬв, Сотт. АСМ, 13, 94 — !02 (ГеЬгиагу 1970). Задачи 1.
Построив дерево грамматического разбора, покажите, что аабйа не является предложением языка, грамматика которого обсуждалась в равд. 12.2. 2. Используя подход, основанный иа стандартных точках притяжения, по. стройте грамматику, язык которой включает по крайней мере три различных контурных рисунка куба. 3. Придумайте решающее правило для определения, связаны ли два произвольных неперекрывающихся объекта оглашением слева/справа. Правило должно давать решения, соответствующие человеческому здравому смыслу. и ие должно быть слишком простым, таким, например, что для выполнения отношения потре.
бовалось бы, чтобы один объект находился полностью слева от другого. Придумайте другое решающее правило для определения, связаны ли объекты отношением сверху/снизу, Идентичны ли зги правила во всем, за ясключеиием изменения в ориентаиии иа 90'? 4. Разработайте алгоритм для определения по картинке, связаны ли два многогранника отношением поддерживает/поддерживается. 5. Найдите матрииу 5 размерностью 4Х4, которая масштабирует каждую компоненту трехмерного вектора ч в произвольное число раз. (Мы полагаем, что вектор ч сначала преобразуется в однородную форму ч и что произведение бч преобразуется снова в обычные координаты.) Покажите, как можно использовать иатрииу 5, чтобы единственная модель куба служила моделью произвольного прямоугольного параллелепипеда.
6. Выведите формулы (!) и (2), дающие решение задачи подбора модели по минимуму среднекваиратичной ошибки. 7. Постройте в общих чертах алгоритм для решения проблемы невидимых линий. Можно ли существенно упростить алгоритм, если ои должен примеияться только к картинкам многогранников? к изображениям пряиоугольиых тел? 8. Начертите несколько трехгранных тел, чтобы продемонстрировать все типы вершин каталога рис.
|2.9. Пометьте каждую вершину указателем ее типа Задачи 497 по каталогу и пометьте каждую линию плюсом, минусом или должным образом ориентированной стрелкой. 9. Постройте дерево поиска для каждого из тел, начерченных в предыдушей задаче. Задайте хорошее эвристическое правило выбора порядка, в котором должны осматриваться вершины. 1О.
Почему не может быть вершин типов 2, 4, 6 или 8» 11. Начертите сцену, 'которая изображает по крайней мере четыре многогранных объекта и содержит по крайней мере одну вершину типа «Х» и по крайней мере одну пару согласованных вершин типа «Т». Объедините области сцены в объекты, используя эвристический метод, описанный в данной главе. (Используйте либо правило 1, либо правило 1' по вашему выбору.) !2. Начертите сцену с многогранными объектами, для которой эвристические правила, обсуждавшиеся в этой главе, обьединяют области в объекты неправдоподобно.
Предложите модификации и депо«пения к правилам, чтобы улучшить их действие. Вы должны рассматривать модификацим как правил введения связей между областями, так и правил объединения областей. 13. Нарисуйте дуальный граф многогранника рис. 12,10, г и проанализируйте его сливаемость. 1Считайте, что объект представляет собой единый многогранник.) 14. Начертите трехгранное тело, содержащее по крайней мере одно «отвер. стие».
Проанализируйте его слнваемость. Постройте дерево поиска. необходимое для разметки вершин тела, и посмотрите, сушествует лн здесь более чем одна совместимая интерпретация; 15. Можно ли распространить интерпретацию посредством дуального графа нд многогранники степени ботьшей чем 3, и если можно, то каким образом? ИМЕННОЙ УКАЗАТЕЛЬ Абсид (АЬепд К.) 48, 91, 138 Абрамсон (АЬгагпяоп Х.) 89 Августсон (Ацйця!яоп Л. б.) 272 Агмон (Айшоп 5.) 202 Агреула (Айгаяча!а А,) !8, 270 Айзерман М.
А. 203 Албрехт (А1ЬгесЫ И.) 47 Альт (АИ Р.) 401 Андерсон (Апдегяоп Е.) 239 Андерсон (Апдегяоп Т, %.) 47, 48, 200 Аоки (АоЫ М.) 90 Аркадьев А. Г. 138 Атрубин (А!гцЫп А, Л.) 27! Атгиив (Абпеаче Р.) 363, 399 Байснер (Веыпег Н. М.) 89 Барии (Вагпеа О. 1.) 315 Барроу (Ваггояч Н. б.) 403 Барус (Вагця С.) 137 Бахадур (Вайабцг К.
К.) 48, 138, 200 Башкиров О. А. 203 Бейли (ВаИу О. Е.) 273 Блайдон (В!аубоп С. С.) 138, 203 Блекуэлл (В!ас)гячеИ О.) 47 Блок (В1осЬ Н. О.) 201 Блюм (В1шп М.) 400 Болл (ВаИ б. Н.) 270, 271, 272, 401 Большев Л, Н. 270 Боигард М. М. 18 Боннер (Воппег К. Е.) 272 Браверман (Вгачегшап О.) 89, 203 Браверман Э. М. 138, 202 Брайан (Вгуап Л. б.) 138 Брайс (Вг!се С. К.) 315, 494 Браун (Вгони О. Т.) 138 Брилл (ВНИ Е, 1..) 389, 390, 401 Брннгхэм (Вг!п8Ьаш Е. 0.) 345 Бродац (Вгода!х Р.) 315 Брэйсвелл (Вгасешей И. Ы.) 344 Букиайт (Воцйп!8Ы %. Л.) 430, 493 Бутц (Вц!х А, И ) 201 Вагнер (%айпег Т, Л.) 137 Вазан (%ваап М.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
