21. Метод на Уолц

(Waltz [46] обобщил и разширил идеите на Нuffman и С1ow анализ на сцени, съдържащи плоскостенни тела като: 1) Разглежда,а не само с тристенни върхове, но и с върхове, образувани с повече ot плоски стени К, V, ПИК, МУЛТИ; 2) Допълва множеството възли на, ман (фиг. 6.2а) с нови върхове с имена XX, КА, КХ - фиг. 6.2Ь; 3) 0t сенките, получени от обектите и отверстията в обектите, ако има щ 4)У величава набора от символи за маркиране на линиите, отчитайки)} че информация за физическата същност на реалната структура; 5) Оси линиите, въвежда някои маркировки за областите, например, за тяхната осветеност; 6) За маркировка на линиите предлага бърз, последователен алгоритъм за филтрация. Целта на предложената система е да се построи точно описание на - тримерната сцена по нейното двумерно изображение. Освен физическите съответствия, определени от марките, системата определя и някои отно- шения за обектите: "пред", "зад", "поддържане" и т. н. На фиг. 6.14 са показани приетите 11 маркировки на Уолц и тяхната физическа интерпретация. Смисълът на образуване на разделимите линии (техните съставящи) е показан на фиг. 6.15, а на фиг. 6.16 са дадени маркировки на сцени с едно, две и три тела, отчитайки сянката. Тези сцени потвърждават физическата интерпретация на марките. Раздвижването на телата в последната сцена показва разделимостта на съответните типове линии и нейното разлагане до отделни тела, при използуване информацията на маркировката (поточно чрез проследяване контурите с гранични линии). Всяко тяло се оказва оградено със символ стрелка.Отчитането на сенките в сцената води до по-точното определяне на пространственото разположение на обектите. Това разширява ограниченията и прави анализа по-прост. По-нататьшното подобряване на описанието на сцената е отчитането на осветеността на областите на обектите. Разглеждат се три случая (фиг. 6.17): областта е осветена (О); областта е засенчена (3); областта се самозасенчва (СЗ). За линиите, разделящи тези области са възможни 3'=9 комбинации на осветеност. Всяка комбинация е възможна за 11 типа линии, определени по-горе. Следователно възможният брой комбинации става 11 х9=99. Но срещаните комбинации в реалния свят са не повече от 50 [44]. Например, не е реална комбинацията за не изпъкналия ръб едната област да бъде осветена, а другата затъмнена. Уолц анализира и определя физически възможните комбинации на марки за линиите на възлите. На фиг. 6.18 са дадени за съответните възли [44]: 1) Възможният брой комбинации от марки; 2) Физически срещаните комбинации; 3) Отношението между възможните и срещаните комбинации. Анализирайки тези данни и сравнявайки ги с данните от фиг. 6.12 могат да се направят следните изводи: 1) С увеличаване на средствата за по-подробно описание на сцената силно растат физическите ограничения; 2) Физическите ограничения позволяват да се изгради "ограничена" база знания (каталог от маркирани възли), но достатъчна за надеждния анализ на сцените; 3) Сравнявайки ограниченията за често срещаните възли тип ВИЛА и СТРЕЛКА се вижда, че възелът СТРЕЛКА внася значително повече ограничения и по-малко нееднозначности. С това се обяснява тезисът, получен в резултат на експеримента на програмата на Гузман, че стрелките дават по-надеждни връзки за областите; 4) При анализа на възлите приоритет трябва да имат тези, които внасят по-големи ограниченБроят на различно маркираните възли, които се срещат на границата на сцената с фона е значително малък по сравнение с общия брой. Това се използува при определяне на стратегията на маркиране - най-напред да се маркират възлите, граничещи с фона. За формиране на каталога на различно маркираните възли, Уолц използува метода на Нuffman. Той запълва октантите последователно с едно, две и повече тела и наблюдава конкретния възел от свободните октанти. На фиг. 6.19 е показан пример на запълване на съответните октанти с едно, две и три тела и маркировката на централния възел, гледан от седми октант.

При маркировката на възлите Уолц използува последователен филтриращ алгоритъм. Прилага се последователно за всички възли. За първия избран възел се отчитат всички възможни маркировки за него. Маркировката на втория избран възел се съгласува с първия. За третия, маркировката се съгласува с втория и т.н. Този процес може да се разглежда като права филтрация. След определянето на маркировката на даден възел се разглежда обратното разпространение на ограничаване (филтрация) на маркировки последователно за предшествуващите възли. Алгоритъмът е ите-рационен и спира работа, когато престанат да отпадат маркировки за въз-1ите. Да разгледаме пример за възлите А, В, С, d, Е, f от сцената на |)иг. 6.20. Върховете се проследяват в реда, в който са записани. За илюст-рацията се използува ограниченото множество от възможни маркировки по Нuffman - фиг. 6.7. За стрелката А се отчитат трите възможни маркировки. Следващият връх е от тип L. За него четири маркировки се