Анализ и разлагане на 3D визуални сцени1 Печат

20. Анализ и разлагане на 3D визуални сцени

Обикновено анализът се извършва на основата на полученото двоично контурно изображение на сцената. Проблемът, който възниква като задача от областта на изкуствения интелект е да се интерпретира двумерната кар­тина като тримерна сцена. Получените резултати в тази област, макар и скромни могат да се разглеждат като теоретична основа за решаването на поставения проблем. Първите научни публикации в това направление са на Робертс [38]. След получаването на двоично контурно изображение той предлага анализът на обектите в сцената да се извърши чрез тримерни многостенни модели. Всеки обект от сцената се разглежда като съставен. Целта е той да се представи като конструиран от прости тримерни модели. На фиг. 6.1 сцената се представя посредством композиция от паралелепи-педи и призма. Когато телата в сцената се допират или закриват едно от друго въз­никва въпросът за тяхното разделяне, т.е. декомпозиция на сцената до от­делни тела. За тази цел Гузман [15] предлага програма, наречена SЕЕ (виждам), определяща контурите принадлежащи на дадено тяло и отделя-Ца тялото като цяло. Гузман обръща внимание на възлите (топологичните Признаци), които се формират от съединяването на ръбовете на телата. Той (изглежда сцени, съдържащи плоскостенни тримерни тела. Наборът от Вбобщени типове възли и обясненията за тях са показани на фиг. 6.2. Име-,Вата на възлите са определени, изхождайки от геометричните конфигура­ции на линиите във възела. Предлагат се връзки за контурните области, Йфеделени от даден възел, които могат да принадлежат на едно тяло. Нап-|^мер, областите определени от възела стрелка често принадлежат на едно |мо. Възел Т обикновено показва закриване на едно тяло от друго и т.н. Три етапа са характерни за работата на програмата на Гузман. На вия етап програмата определя (разпознава) типа на възлите и възмоz връзки между областите на възлите. Тази локална информация се ана ра на втория етап и се предлагат хипотези за отделяне на телата в сце За тази цел се използуват множество евристики. Първата от тях е: де пасти принадлежат към едни и също тяло, ако между тях има поне връзка. Очевидно е, че тази евристика не е достатъчно силна и са въз ни ситуации, например при съвпадение на възли, за които ще се по] неправилни връзки - фиг. 6.За. Втората евристика гласи: две области подлежат към едно и също тяло, ако между тях има две връзки - V тите (АВ) и (DЕ) за сцената на фиг. б.Зй. С тази евристика не се доп;

грешки характерни за първата, но тя се явява много силна за обл имащи по една връзка, например С, F, R от фиг. 6.ЗА. Отслабването извършва с евристиката: отчитайки обединяването на области на < вата на предишната евристики като цяло да се извърши обединява на области, имищи връзки с него - областите (АВ) със (С') и съответш лучаваме (АВС). Следващата евристика продължава отслабването и г, ако дадена област има саио една връзка с друга област, те се обедин, - (АВС'FR}(DЕ). Последната евристика гласи: ако от съседните върхаполучава противоречива информация за връзките между областите, то се извършва допълнителен анализ на тези връзки, като някои от тях се отхвърлят. Например, не се установяват връзки по отношение на линия, която в единия край образува външен възел тип стрелка, влиза във възел тип L, или се явява закриваща във връх тип Т—.

В процеса на определянето на връзките се формират графи. Всеки въ­зел на графа с номер съответствува на конкретна стена, а дъгите определят връзките между стените. На следващия етап възлите на всеки граф се пог­лъщат в едно ядро, определящо конкретно тяло - фиг. 6.4. На фиг. 6.5 е показана сцена ТКА1Ь, използувана от Гузман [15]. Програмата SЕЕ за тази сцена дава следния резултат (ВОDУ-тяло, 1S-е):(ВODY 1 IS:6:2:1)

(ВОDY2 IS:11:12:10)

(ВОDYЗ IS:4:9:5:7:3:8:13) Както се вижда тази програма с успех извършва декомпозиция на тримерни сцени до обектите, съдържащи се в нея. Не е трудно, обаче, да се конструират примери на сцени, за които програмата SЕЕ допуска грешки. Направените експерименти с програмата показали, че тя работи успешно за сцени с тела, чиито върхове се получават от пресичането на три плоски стени (тристенни върхове) и телата не съдържат отверстия. В този смисъл програмата на Гузман може да се разглежда като евристична теория, съг­ласно която, ако възелът се явява изображение на тристенен връх, той съ­държа съответните връзки между областите на тялото. Тя оказва силно влияние на следващите разработки в тази област. Но на тази теория й лип­сват дълбоки семантични корени, разкриващи причините за формиране на линии и връзки в тримерния свят и ограниченията, които налага този свят.

Дадена линия на изображението може да възникне поради следните причини, определени от физическата структура [45]: 1) Линията може да бъде граница на сянка, 2) Тя може да се разглежда като пукнатина меж­ду два изместени обекта; 3) Ребро за две видими стени; 4) Граница между обекта и това, което се намира зад него (фона).

Независимо един от друг Нuffman и Сlowes предложили сис­тематичен, семантичен подход при анализа на тримерни сцени. Те приемат ред ограничения и изхождат от физическия смисъл на линиите. Ограниче­нията за линейните изображения са следните: 1) Обектите в сцената са плоскостенни, в които всеки връх се образува от пресичането на три стени;2) Обектите са в такава (основна) позиция, че нейното незначително изме­нение не води до изменение на типовете на върховете в линейното изобра­жение; 3) Точката на наблюдение е избрана така, че нейното незначително изменение не води до изменение на типовете на върховете в линейното изображение. Първото ограничение е много важно и силно, тъй като по същество за изображението се избягват върхове от типа К, Y, ПИК, МУЛТИ, които се формират от пресичането на повече от три плоскости -фиг. 6.2. Възможни са върхове от тип L, ВИЛА, СТРЕЛКА, Т, което значи­телно опростява разглеждането. Осветеността на сцената се приема такава, че не се появяват сенки. Линиите на изображението се класифицират в три типа, съгласно с техния физически смисъл, определящ се от структу­рата. Всеки тип се отбелязва с конкретна марка: 1) Изпъкнала линия (ръб), определяща се от две видими стени се отбелязва с "+"; 2) Неизпькнала ли­ния, определяща се от две видими стени, се отбелязва с "-"; 3) Гранична линия, определяща се от една видима стена, закриваща друга стена се отбе-лязва с една от стрелките —> или <— . Посоката на стрелката е такава, че при движение по нея закриващият обект остава отдясно. Линиите могат да се разделят на гранични и вътрешни. Граничните линии разделят области, принадлежащи на различни обекти, а вътрешните линии разделят области, отнасящи се към един и същ обект [44]. От своя страна вътрешните линии се разделят на изпъкнали и неизпъкнали. Съгласно с приетата маркировка, всяка линия може да се маркира по един от четирите начина. Следовател­но, връх, имащ две линии може да се маркира по 4 =16 начина, а връх с три линии по 4^=64 начина. Приемайки горните ограничения, че линейното изображение съдържа върхове от тип Ь, ВИЛА, СТРЕЛКА, Т, то възмож­ният брой различно маркирани върхове ще бъде 1.42+3.43= 16+192=208. Но някои от тези върхове са невъзможни за реалните изображения, както е показано на фиг. 6.6. От това множество различно маркирани върхове за реалните 30 изображения са характерни 16: шест за връх Ь, три за връх ВИЛА, три за връх СТРЕЛКА и четири за връх Т (фиг. 6.7). Това се доказ­ва, изхождайки от ограничението, че всеки връх се получава от пресича­нето на три плоскости. Пресичането на три плоскости разделя пространст­вото на осем части (октанта) - фиг. 6.8. На фигурата е приета конкретна номерация на октантите. Един или повече октанти се запълват с материал, даващ реален обект. Образуваният централен тристенен връх се наблюдава от незапълнените октанти. Той се изобразява като се маркират линиите, влизащи в него в зависимост от физическия им смисъл в структурата.

На фиг. 6.9(3 е показано запълването на един октант, а именно първия. Резултатът от наблюдението от останалите седем незапълнени октанти е показан на фиг. 6.9Ь, започвайки от осмия към седмия, шестия и т.н. Инте­ресно е да се отбележи, че типът на върха и маркировката не се изменят при изменение на точката на наблюдение в дадения октант, макар че ъгли­те между линиите се изменят. Анализирайки получените типове върхове и техните маркировки се вижда, че те се свеждат съответно до един връх ВИЛА, СТРЕЛКА и 1^, с конкретни маркировки. Изключва се разглежда­нето на обекти, получени в резултат на запълването на два, четири или шест октанта. В този случай или не се получава централен връх за наблю­дение, или той се получава в резултат на пресичането на повече от три по­върхнини (фиг. 6.10). По разбираеми причини трябва да се изключи и за­пълването на осемте октанта. На фиг. 6.11 е показано запълването на три, пет и седем октанта. Резултатът от наблюдението от свободните октанти дава по две нови маркировки за върхове тип ВИЛА и СТРЕЛКА и пет нови

Фиг. 6.6. Нереални върхове

+/ \+

Maркировки за връх тип L. Частичното закриване на приетите основни ти-poве линии във връх тип Т, дава четири различни маркировки за този връх. С това се показва получаването на 16-те различно маркирани върхове за реалните изображения - фиг. 6.7. Вижда се, че е реалния физически свят са Сшlно ограничени комбинациите на маркировка на линиите, образуващи pajличнu върхове.

Г Това е фундаментален въпрос, който принципно и ресурсно (по време 1 памет) опростява автоматичния анализ на изображенията. Вместо марки­рането на линиите на върховете да се извърши при използуване на знания й физическата структура на реалните обекти, може и обратното - използу-Цвйки знанията за възможната маркировка на върховете и съгласуването й Я съседни върхове, да се получи информация за реалната структура на вената и обектите в известна степен отговаряща на естествената интуи-!р|вна интерпретация. Може да се използува следната стратегия при марки­рането на изображението: 1) Маркират се граничните линии по посока на Часовниковата стрелка; 2) Линиите, влизащи във върхове с гранични ли-^йи, се маркират съгласно възможното множество маркирани върхове [г. 6.7). Съгласува се маркировката на всеки два съседни върха, изхож-|ки от важното свойство, че линия, свързваща два върха не може да има ична маркировка в двата края.Да разгледаме пример за маркиране на изображението, дадено на [г.6.13. Маркировката на граничните линии е показана на фиг. 6.136. .рховете В, О, Р,] са тип СТРЕЛКА с по две гранични линии. Съгласно с южеството допустими марки (фиг. 6.7) третата линия може да има марка ио "+". За върха С от типа ВИЛА с две гранични линии, третата линия юже да бъде маркирана само с "-". На вътрешните върхове К и М, тип ВИЛА. двете линии са маркирани с "+". Третата линия също трябва да| де маркирана с "+". Двата плюса за върха Ь се потвърждават и от минуca) този връх. Ако СТРЕЛКА има един минус другите две линии трябaм бъдат с "+". На фиг. 6.13с е показана окончателната маркировка. Аналзд райки маркировката може да се разкрие структурата на обекта. Ако г положим, че обектът лежи на дадена повърхнина, то линиите ЕF и F1 moxe да се маркират с "-", което не противоречи на останалите маркирo