面向手機(jī)3D動(dòng)畫(huà)自動(dòng)生成的空間分層布局規(guī)劃①

王曉飛,黃 蕾

(北京工業(yè)大學(xué) 信息學(xué)部,北京 100124)

面向手機(jī)3D動(dòng)畫(huà)自動(dòng)生成的空間分層布局規(guī)劃①

王曉飛,黃 蕾

(北京工業(yè)大學(xué) 信息學(xué)部,北京 100124)

手機(jī)3D動(dòng)畫(huà)自動(dòng)生成系統(tǒng)是將用戶發(fā)送的短信,經(jīng)過(guò)信息抽取、情節(jié)規(guī)劃等一系列的處理,最終生成一段與短信內(nèi)容相關(guān)的三維動(dòng)畫(huà)并發(fā)送給接收方這一過(guò)程.布局規(guī)劃是系統(tǒng)的一個(gè)重要組成部分,其功能是將模型放置到場(chǎng)景的可用空間上.通過(guò)對(duì)布局問(wèn)題的研究,本文提出了一種基于區(qū)域布局和模型布局的分層布局方法,其包括定性規(guī)劃和定量計(jì)算兩個(gè)部分,利用語(yǔ)義網(wǎng)技術(shù)建立分層布局知識(shí)庫(kù),基于規(guī)則的方法推導(dǎo)出分層布局定性規(guī)劃方案,并對(duì)模型位置進(jìn)行動(dòng)態(tài)計(jì)算.最后,通過(guò)實(shí)驗(yàn)驗(yàn)證了分層布局規(guī)劃的有效性和多樣性,滿足了自動(dòng)生成系統(tǒng)對(duì)布局規(guī)劃的要求.

動(dòng)畫(huà)自動(dòng)生成; 布局規(guī)劃; 區(qū)域布局; 分層布局; 語(yǔ)義網(wǎng)

1 引言

布局是對(duì)事物的全面規(guī)劃,通常是將一些物體按照一定規(guī)則放置到一個(gè)給定的區(qū)域中,如桌面物體擺放、城市建筑規(guī)劃等.生活處處離不開(kāi)布局,這也引得許多專家學(xué)者對(duì)其進(jìn)行研究,其主要集中在二維和三維規(guī)則物體的布局問(wèn)題上,如玻璃切割問(wèn)題、集裝箱裝載問(wèn)題.由于組合爆炸,這類問(wèn)題往往被描述成大規(guī)模整數(shù)規(guī)劃,已被證明是 NP-難問(wèn)題.目前,解決此類問(wèn)題主要采用模擬退火算法和遺傳算法等,由于布局問(wèn)題廣泛存在于工業(yè)生產(chǎn)和人們?nèi)粘Ｉ钪?因此對(duì)布局問(wèn)題的研究具有十分重要的實(shí)用價(jià)值.

本文中的布局指的是在手機(jī)3D動(dòng)畫(huà)自動(dòng)生成系統(tǒng)中模型在可用空間的擺放問(wèn)題,上世紀(jì)90年代,中科院陸汝鈐院士[1]提出了全過(guò)程計(jì)算機(jī)輔助動(dòng)畫(huà)自動(dòng)生成技術(shù),它底層是以圖形學(xué)為支撐,在上層運(yùn)用人工智能技術(shù)以及電影藝術(shù)實(shí)現(xiàn)的一個(gè)全新領(lǐng)域.2008年,中科院張松懋研究員[2]將此技術(shù)應(yīng)用到了手機(jī)短信上,提出了手機(jī)3D動(dòng)畫(huà)自動(dòng)生成技術(shù),該技術(shù)是將發(fā)送者的短信轉(zhuǎn)化為一段能表現(xiàn)短信內(nèi)容的三維動(dòng)畫(huà)并發(fā)送給接收方.

布局規(guī)劃是手機(jī)3D動(dòng)畫(huà)自動(dòng)生成系統(tǒng)中的模塊之一,通過(guò)設(shè)計(jì)出一種布局方式將模型動(dòng)態(tài)的放入動(dòng)畫(huà)場(chǎng)景中并且具有一定的合理性和美觀性,可以實(shí)現(xiàn)系統(tǒng)中模型和場(chǎng)景的重用,使生成的動(dòng)畫(huà)更加豐富.由此可見(jiàn),本系統(tǒng)的布局問(wèn)題是針對(duì)的是添加到動(dòng)畫(huà)場(chǎng)景中的模型,如何設(shè)計(jì)出合理的布局方式是需要研究的重點(diǎn).此前,系統(tǒng)已經(jīng)做過(guò)兩個(gè)版本的布局規(guī)劃,第一版實(shí)現(xiàn)了將模型無(wú)重疊的擺放到場(chǎng)景中,第二版設(shè)計(jì)了一些布局樣式,實(shí)現(xiàn)了將模型按照布局樣式擺放到場(chǎng)景的相應(yīng)位置.然而模型之間在布局規(guī)劃過(guò)程中并沒(méi)有聯(lián)系,布局樣式相對(duì)固定也導(dǎo)致能放置到場(chǎng)景中的模型數(shù)量有所限制,所以在設(shè)計(jì)布局方案時(shí)還要解決目前系統(tǒng)存在的這些問(wèn)題.

本文設(shè)計(jì)出了基于語(yǔ)義網(wǎng)技術(shù)的分層布局規(guī)劃系統(tǒng),分層就是對(duì)動(dòng)畫(huà)自動(dòng)生成系統(tǒng)添加的模型劃分層次,首先就是要將模型劃分區(qū)域,基于語(yǔ)義網(wǎng)技術(shù)建立的知識(shí)庫(kù)可以存儲(chǔ)模型的分類、模型間位置關(guān)系以及模型自身的屬性等信息,語(yǔ)義網(wǎng)的引入對(duì)布局方案的設(shè)計(jì)有著至關(guān)重要的作用,將模型按照這些信息劃分到各個(gè)區(qū)域中,然后分別對(duì)每個(gè)區(qū)域進(jìn)行布局,最后對(duì)所有區(qū)域進(jìn)行布局,最終完成布局規(guī)劃.系統(tǒng)包括定性規(guī)劃和定量計(jì)算兩部分,定性規(guī)劃是為模型劃分區(qū)域和設(shè)計(jì)布局,定量計(jì)算則是按照布局規(guī)劃計(jì)算出模型位置并將其添加到場(chǎng)景中.本文的分層布局規(guī)劃可以解決之前版本存在的問(wèn)題,并且使模型擺放更加合理,可以提高系統(tǒng)生成的動(dòng)畫(huà)的多樣性.

2 布局規(guī)劃整體設(shè)計(jì)

本文是基于手機(jī)3D動(dòng)畫(huà)自動(dòng)生成系統(tǒng)來(lái)研究的,系統(tǒng)的整體流程如圖1所示,以中文短信為輸入,并利用哈工大分詞系統(tǒng)對(duì)短信進(jìn)行分詞,之后通過(guò)機(jī)器學(xué)習(xí)的方法抽取出短信的主題等信息,分別對(duì)情節(jié)、攝像機(jī)、光照、布局等進(jìn)行定性規(guī)劃,然后計(jì)算出各部分定量結(jié)果,通過(guò)調(diào)用 Maya API生成動(dòng)畫(huà)文件,最后渲染出視頻文件并將其發(fā)送給接收方.

布局規(guī)劃是此系統(tǒng)的主要模塊之一,其主要功能是將模型擺放到場(chǎng)景的可用空間中.本文的分層布局規(guī)劃可以設(shè)計(jì)出多種布局方案并動(dòng)態(tài)的計(jì)算模型位置,其整體流程如圖2所示.

借助于Protégé搭建的系統(tǒng)知識(shí)庫(kù)可以方便的存儲(chǔ)和調(diào)用模型的屬性等信息,如輸入短信“公園樹(shù)下的椅子上有個(gè)西瓜”,情節(jié)規(guī)劃部分會(huì)將其中的樹(shù)、椅子、西瓜等信息抽取出來(lái),布局規(guī)劃部分將抽取到的模型信息進(jìn)行區(qū)域劃分,如椅子模型有一個(gè)平面可以用來(lái)放置模型,我們將這個(gè)平面叫做可用空間,而西瓜模型可以放置到這個(gè)空間上,所以可以將椅子和西瓜一起擺放,之后為它們選擇布局形狀和布局效果,最后計(jì)算出模型位置并將模型添加到場(chǎng)景中.

3 布局定性規(guī)劃

3.1 布局知識(shí)庫(kù)的構(gòu)建

本體庫(kù)是以描述型方法來(lái)存貯和管理知識(shí)的機(jī)構(gòu),本體最早是在人工智能領(lǐng)域應(yīng)用的,是由Neches等人給出的定義[3],他們將本體定義為“給出構(gòu)成相關(guān)領(lǐng)域詞匯的基本術(shù)語(yǔ)和關(guān)系,以及利用這些術(shù)語(yǔ)和關(guān)系構(gòu)成的規(guī)定這些詞匯外延的規(guī)則的定義”.其用來(lái)表述領(lǐng)域知識(shí),一個(gè)本體描述了一個(gè)領(lǐng)域中的概念以及概念之間的關(guān)系,它能夠有效處理復(fù)雜的知識(shí),本系統(tǒng)就是采用基于本體的表示方法來(lái)構(gòu)建的知識(shí)庫(kù)和規(guī)則庫(kù).

圖2 分層布局系統(tǒng)流程圖

本系統(tǒng)的本體庫(kù)主要包含Topic(主題類)、Template(模板類)、AnimationScene(動(dòng)畫(huà)場(chǎng)景類)、Object(模型類)、Layout(布局類)等.主題類包含短信的主題,模板類包含所有跟短信內(nèi)容相關(guān)的模板,動(dòng)畫(huà)場(chǎng)景類包含已有的場(chǎng)景,模型類包含所有的模型,布局類包含所有的布局定性信息.

其中,布局知識(shí)庫(kù)是基于系統(tǒng)本體庫(kù)構(gòu)建的,其是用來(lái)存儲(chǔ)布局方案信息的.由于布局方案的設(shè)計(jì)需要用到場(chǎng)景和模型的信息,為此,在構(gòu)建布局知識(shí)庫(kù)時(shí)需要導(dǎo)入手機(jī)3D動(dòng)畫(huà)系統(tǒng)總的知識(shí)庫(kù),這樣就可以利用這些信息推出具體的布局方案.之后建立一個(gè)布局類,然后分別按照布局形狀和布局效果進(jìn)行分類.

布局形狀(LayoutShape)的分類如圖3所示,主要分為點(diǎn)型(PointLayout)、線型(LineLayout)、三角形(TriangleLayout)和矩形(RectangleLayout).同樣的模型按照不同的形狀進(jìn)行擺放,可以使得布局結(jié)果更富有變化性,如圖4所示為按照線型布局和三角形布局的擺放效果對(duì)比.布局規(guī)劃首要的任務(wù)是將模型都放置到可用空間中,這里說(shuō)的放置不是對(duì)模型簡(jiǎn)單的碼放,而是具有一定規(guī)則的或是有一定觀賞性的擺放.本文選用按照形狀的擺放方式,其不受模型所屬類別的限制,是一種通用的布局方案.

圖3 布局形狀類示意圖

圖4 不同布局形狀擺放效果示意圖

此外,本文的布局規(guī)劃還參考了藝術(shù)領(lǐng)域中形式美的法則,通過(guò)調(diào)整不同大小的模型的擺放順序表現(xiàn)出不同的布局效果(LayoutEffect),不同的布局效果又給人不同的視覺(jué)享受,從而使得本布局規(guī)劃在一定程度上可以抽象的表現(xiàn)短信主題和情緒.布局效果的分類如圖5所示,分為對(duì)比(CompareLayout)、秩序(OrderLayout)、隨機(jī)(RandomLayout)、韻律(RhythmLayout)、對(duì)稱(SymmetryLayout)五類,如圖6為韻律布局和對(duì)稱布局的擺放效果對(duì)比.

圖5 布局效果類示意圖

圖6 不同布局形狀擺放效果示意圖

在對(duì)模型進(jìn)行劃分區(qū)域的時(shí)候還要考慮模型類之間的關(guān)系,如樹(shù)類(Tree)與椅子類(Chair)之間有空間相鄰的位置關(guān)系可以表現(xiàn)公園的場(chǎng)景,在知識(shí)庫(kù)中的刻畫(huà)如圖7所示.此外,還有一種層疊的位置關(guān)系用來(lái)表示一種模型可以放置在另一種模型上面,如桌子上面可以放水果,這種關(guān)系還需要在知識(shí)庫(kù)中刻畫(huà)出模型上的可用空間大小、位置等信息,可用空間的刻畫(huà)如圖8所示.

圖7 模型類之間臨近關(guān)系示例

圖8 模型上可用空間的屬性示例

3.2 布局規(guī)則庫(kù)的設(shè)計(jì)

布局的定性描述存放在布局知識(shí)庫(kù)中,而具體選擇哪種布局方式則是通過(guò)布局規(guī)則庫(kù)推理而來(lái)的.推理所使用的語(yǔ)言是 SWRL(Semantic Web Rule Language)[4],它是由語(yǔ)義的方式來(lái)呈現(xiàn)規(guī)則的一種語(yǔ)言,其規(guī)則部分是由RuleML所演變而來(lái).

布局的規(guī)則包括布局效果的推理和布局形狀的推理,布局效果可以抽象的表現(xiàn)情緒,所以其主要根據(jù)短信主題和模板推理得出,部分布局規(guī)則如圖9所示.

圖9 布局規(guī)則示例

下面舉例對(duì)布局規(guī)則給出簡(jiǎn)要說(shuō)明,如:

這條推理規(guī)則表示:給出一個(gè)動(dòng)畫(huà)場(chǎng)景(Animation-Scene),短信的主題是高興(GladTopic),有一種韻律布局效果(RhythemLayout)可以表現(xiàn)此主題,那么將這種布局效果添加到場(chǎng)景中.

布局形狀作為一種通用的擺放方式,其與短信本身的關(guān)聯(lián)性不大,主要與可用空間中模型數(shù)量有關(guān),如三角形布局只能在模型至少為3個(gè)的時(shí)候才適用,規(guī)則所添加的布局形狀可以在定量計(jì)算時(shí)作為備選方案之一.如:

表示當(dāng)場(chǎng)景可用空間中模型數(shù)量為3個(gè)或者超過(guò)3個(gè)的時(shí)候就把三角形布局添加到場(chǎng)景中.

3.3 定性規(guī)劃流程

布局定性規(guī)劃接收上層情節(jié)規(guī)劃的內(nèi)容,提取其中的主題、模板、場(chǎng)景、模型等信息,結(jié)合布局知識(shí)庫(kù),通過(guò)推理得出布局定性規(guī)劃信息,具體流程如下:

第一步.如果情節(jié)規(guī)劃結(jié)果有主題或模板,則通過(guò)規(guī)則庫(kù)中的規(guī)則判斷是否有布局效果適合此主題或者模板,若能夠推出,則將布局此布局效果添加到場(chǎng)景中,若不能推出或者沒(méi)有主題和模板則隨機(jī)添加布局效果;

第二步.判斷可用空間中模型間是否存在有空間位置約束,若存在,將有位置約束的模型單獨(dú)劃分區(qū)域,對(duì)剩余模型按照其所屬類別為每一類劃分出一個(gè)區(qū)域;

第三步.對(duì)每一個(gè)區(qū)域通過(guò)規(guī)則推理出適合的布局形狀,將布局信息寫(xiě)入定性規(guī)劃文檔.

定性結(jié)果各參數(shù)的描述如表1所示.

表1 布局定性結(jié)果參數(shù)描述

例如短信“公園樹(shù)下的椅子上有個(gè)西瓜”經(jīng)過(guò)情節(jié)定性規(guī)劃,得到可用的場(chǎng)景、添加的模型等信息,如圖10所示.

圖10 部分情節(jié)定性規(guī)劃信息

首先根據(jù)短信主題選擇布局效果,由于本例沒(méi)有主題,所以就隨機(jī)選擇.然后對(duì)空間中的模型劃分區(qū)域,在本例中,樹(shù)與椅子之間具有空間位置約束,所以將它們劃分到同一區(qū)域中,之后將剩余的模型則按照所屬類別進(jìn)行劃分,最后為每個(gè)區(qū)域選擇布局形狀,得到最終的定性規(guī)劃結(jié)果如圖11所示.

圖11 布局定性規(guī)劃結(jié)果

4 布局定量計(jì)算

在布局定量計(jì)算階段,首先判斷是否由布局定性規(guī)劃信息,若有,則獲取每個(gè)可用空間的布局效果及此空間每個(gè)區(qū)域所添加的模型.根據(jù)布局效果對(duì)每個(gè)區(qū)域的模型進(jìn)行排序,然后根據(jù)可用空間大小和布局形狀計(jì)算空間中每個(gè)區(qū)域的每個(gè)模型的具體位置,最后調(diào)用Maya API將模型移動(dòng)到其位置上.

對(duì)模型位置計(jì)算,首先計(jì)算出每個(gè)區(qū)域擺放出所需布局形狀最低的空間要求,然后動(dòng)態(tài)分配各個(gè)區(qū)域所占整個(gè)可用空間的大小,最后再按照比例計(jì)算出每個(gè)模型的位置.

如圖12所示將模型A、B、C按照線型放到可用空間S中,在計(jì)算時(shí)假設(shè)可用空間的高度大于模型的高度.圖中以可用空間的左下角為原點(diǎn)建立坐標(biāo)系,并且標(biāo)出了模型和用空間的長(zhǎng)和寬,若按圖12方案擺放,模型應(yīng)該滿足公式(1)和公式(2).

圖12 線性布局俯視圖

之后計(jì)算每個(gè)模型的位置坐標(biāo),即模型中心點(diǎn)位置,如對(duì)模型A的橫坐標(biāo)的計(jì)算為公式(3)所示,縱坐標(biāo)的計(jì)算為公式(4)所示,用同樣的方法可以計(jì)算出其他兩個(gè)模型的具體位置.

由于在計(jì)算的每一步都要考慮到模型自身的大小和可用空間的大小,所以可以避免模型之間重疊或者模型放置在可用空間外面的情況.以定性規(guī)劃部分的布局規(guī)劃結(jié)果為例,對(duì)其進(jìn)行定量計(jì)算后的布局效果如圖13所示.

圖13 布局結(jié)果渲染截圖

在計(jì)算的過(guò)程中,有可能由于可用空間大小不足以放下所有模型的情況,這時(shí)候就需要減少部分模型數(shù)量或者移除部分模型以避免布局失敗,而具體去掉哪些模型則需要考慮到多種因素.在此引入一個(gè)可以評(píng)價(jià)模型重要程度的指標(biāo)TargetLevel,綜合考慮影響動(dòng)畫(huà)表現(xiàn)力的各個(gè)因素并定量的給出分值,所有因素分值之和為模型最終得分,分值從0開(kāi)始,數(shù)值越大表示此模型越重要.

目前考慮到的因素有四個(gè),分別為模型target屬性值是否為1、模型是否為有動(dòng)作或面部表情的人物、模型是否含有可用空間、模型是否有變形效果.在定性部分,每個(gè)模型都會(huì)有一個(gè)target屬性,當(dāng)屬性值為1時(shí)表示此模型與短信相關(guān)程度較高,為此當(dāng)值為1時(shí)給此項(xiàng)因素4分,否則給0分.帶有動(dòng)作和面部表情的人物模型、帶有可用空間的模型以及變形的模型都具有一定的表現(xiàn)力,根據(jù)它們給動(dòng)畫(huà)帶來(lái)的不同表現(xiàn)效果分別給予3分、2分、1分,否則給0分.計(jì)算出每個(gè)模型的重要程度分值,當(dāng)需要減少模型數(shù)量或者移除模型的時(shí)候可以根據(jù)此分值進(jìn)行比較,先去除分值較小的模型,再對(duì)剩余模型進(jìn)行計(jì)算,這樣做可以在一定程度上減少動(dòng)畫(huà)對(duì)短信的表達(dá)所帶來(lái)的影響.

5 分層布局規(guī)劃評(píng)估

布局規(guī)劃所要達(dá)到的目標(biāo)是有效性、多樣性,同時(shí)還要有一定的美觀性.即模型放到可用空間后是不應(yīng)有模型重疊或者模型位置不在可用空間范圍內(nèi)的情況,而且布局盡量富有變化,同樣的短信甚至同樣的定性規(guī)劃也能得出不同的布局結(jié)果.

本文對(duì)系統(tǒng)近三個(gè)月的短信測(cè)試結(jié)果進(jìn)行統(tǒng)計(jì),從2016年9月1日到2016年11月30日成功生成動(dòng)畫(huà)的短信共有387條.其中添加了布局規(guī)劃并布局成功的共有379條,布局有效率達(dá)97.93%.而造成布局失敗的原因主要有兩種,一是沒(méi)有添加模型,二是添加的模型尺寸均超出可用空間范圍.從成功添加了布局的短信中選出一部分做了有效性、多樣性和觀賞性實(shí)驗(yàn).

5.1 有效性實(shí)驗(yàn)

為了驗(yàn)證布局結(jié)果是否達(dá)到目標(biāo),對(duì)布局系統(tǒng)進(jìn)行了正確性實(shí)驗(yàn),輸入一條短信,查看生成的動(dòng)畫(huà),并手動(dòng)檢查渲染文件中各個(gè)模型位置是否正確.

短信內(nèi)容:這個(gè)蘋(píng)果很甜,很開(kāi)心

圖14 情節(jié)定性規(guī)劃部分文檔

如圖14所示為短信的定性規(guī)劃文檔,從圖中可以看出,此場(chǎng)景有一個(gè)可用空間SP_room2_D,要在此空間中放入的模型為三個(gè)蘋(píng)果(M_restaurantFruit_apple.ma)、一個(gè)茶壺(M_teapot.ma)、一個(gè)一半的西瓜(M_halfwatermelon.ma)、四個(gè)整個(gè)的西瓜(M_fullwatermelon.ma).通過(guò)對(duì)此文檔進(jìn)行分析,可以得到短信的主題是喜悅(GladTopic),通過(guò)定性規(guī)則可以推出布局效果應(yīng)該是韻律(RhythmLayout),接著對(duì)模型分類,所有水果為一類,茶具為另一類,接著分別統(tǒng)計(jì)每一類中模型的數(shù)量并設(shè)置布局形狀分別為三角形布局(Triangle)和點(diǎn)狀布局(point).最后生成的布局定性規(guī)劃結(jié)果如圖15所示.

圖15 定性規(guī)劃結(jié)果

接著通過(guò)定量計(jì)算部分得到每個(gè)模型的位置,并將模型放置到場(chǎng)景中,最終的布局結(jié)果如圖16所示.

圖16 布局結(jié)果渲染圖

5.2 多樣性實(shí)驗(yàn)

選取50條短信,對(duì)每條短信的定性規(guī)劃結(jié)果運(yùn)行10次定量計(jì)算,最后統(tǒng)計(jì)出每條短信不同布局結(jié)果的數(shù)量,最好的結(jié)果是十條結(jié)果都不相同,最終添加的模型不同或者模型位置的不同都算作不同結(jié)果,統(tǒng)計(jì)結(jié)果如圖17所示.

圖17 布局規(guī)劃多樣性測(cè)試結(jié)果

由圖中可以看出,不同布局方式個(gè)數(shù)超過(guò)5種的短信為40條,占80%,說(shuō)明分層布局具有較好的多樣性,即使是同樣的定性規(guī)劃也能得出不同的布局樣式,如短信“來(lái)吃點(diǎn)水果吧”的不同布局結(jié)果有6種,效果如圖18所示.

圖18 短信“來(lái)吃點(diǎn)水果吧”的布局結(jié)果

5.3 觀賞性實(shí)驗(yàn)

系統(tǒng)最終是以動(dòng)畫(huà)的方式來(lái)呈現(xiàn)的,這就要求布局不僅要將模型放到場(chǎng)景中,還要擺放的盡量美觀,為了評(píng)估布局規(guī)劃的效果,本文設(shè)計(jì)了調(diào)查問(wèn)卷并從成功添加了布局規(guī)劃的短信中隨機(jī)選取了100條進(jìn)行開(kāi)放性評(píng)估.問(wèn)卷設(shè)計(jì)了五個(gè)評(píng)價(jià)指標(biāo),分別為“我認(rèn)為動(dòng)畫(huà)的觀賞性很好”、“我認(rèn)為動(dòng)畫(huà)內(nèi)容與短信內(nèi)容相符”、“我認(rèn)為動(dòng)畫(huà)中的物體擺放能夠反映短信內(nèi)容”、“我認(rèn)為動(dòng)畫(huà)中的物體擺放合理”、“我認(rèn)為動(dòng)畫(huà)中物體擺放的比較美觀”,所有指標(biāo)都采用計(jì)分制,最高分10分表示十分認(rèn)同此觀點(diǎn),最低分0分表示強(qiáng)烈反對(duì)此觀點(diǎn).由于動(dòng)畫(huà)數(shù)量較多,將100條短信分為5 組,每組短信發(fā)放 4 張問(wèn)卷,一共發(fā)放 20 張,收回20張.對(duì)調(diào)查結(jié)果進(jìn)行統(tǒng)計(jì),結(jié)果如圖19所示.

圖19 評(píng)價(jià)指標(biāo)的平均得分

由圖中可以看出,“我認(rèn)為動(dòng)畫(huà)中的物體擺放合理”指標(biāo)得分較高,為8.3分,說(shuō)明使用分層布局規(guī)劃進(jìn)行物體擺放的效果不錯(cuò),具有一定的合理性.“我認(rèn)為動(dòng)畫(huà)中物體擺放的比較美觀”得分較低,為6.2分,說(shuō)明要達(dá)到藝術(shù)領(lǐng)域的美學(xué)要求還是有一定難度,系統(tǒng)仍有較大的改進(jìn)空間.

6 相關(guān)工作

布局問(wèn)題一直存在于人們的日常生活中,很多專家學(xué)者也在對(duì)其進(jìn)行研究,研究主要集中在工程領(lǐng)域和藝術(shù)領(lǐng)域兩個(gè)方面.

在工程領(lǐng)域中,布局問(wèn)題[5-7]是指對(duì)物體進(jìn)行最優(yōu)組合優(yōu)化擺放的問(wèn)題,主要出現(xiàn)在機(jī)械制造、玻璃切割、皮革服飾及大規(guī)模集成電路等領(lǐng)域,其涉及多學(xué)科、多領(lǐng)域的知識(shí),屬于復(fù)雜組合最優(yōu)化問(wèn)題.工業(yè)生產(chǎn)中的布局問(wèn)題主要集中在三維空間中,如機(jī)床組合夾具的自動(dòng)拼裝、主軸箱內(nèi)傳動(dòng)件的布置等,由于其復(fù)雜多樣性和在實(shí)際工業(yè)生產(chǎn)中的廣泛應(yīng)用而得到各個(gè)領(lǐng)域?qū)W者和研究人員的關(guān)注.目前對(duì)此類問(wèn)題的研究,大都采用啟發(fā)式算法和混合啟發(fā)式算法[8,9].

在藝術(shù)領(lǐng)域也存在布局問(wèn)題,室內(nèi)設(shè)計(jì)中的陳設(shè)藝術(shù)就屬于其中之一.“陳設(shè)”可理解為擺設(shè)品、裝飾品,也可以理解為對(duì)物品的陳列、擺設(shè)布置、裝飾[10].在室內(nèi)空間設(shè)計(jì)中,空間成為設(shè)計(jì)表達(dá)的重點(diǎn)內(nèi)容,現(xiàn)代的陳設(shè)設(shè)計(jì)也逐步滿足功能性、藝術(shù)性,而不再是將家裝配飾隨便的擺放.設(shè)計(jì)師在對(duì)室內(nèi)物體進(jìn)行布局設(shè)計(jì)的時(shí)候也會(huì)遵循形式美的法則,這些法則主要包含對(duì)比與統(tǒng)一、對(duì)稱與均衡、比例與尺度、節(jié)奏與韻律[11].

由此可見(jiàn),不同領(lǐng)域?qū)Σ季中Ч囊笠灿兴煌?工程領(lǐng)域注重功能性,藝術(shù)領(lǐng)域則偏向美觀性.而在手機(jī)3D動(dòng)畫(huà)自動(dòng)生成系統(tǒng)中的布局則需要同時(shí)兼顧這兩方面,既需要把模型擺放的合理,也期望布局更加美觀.

目前課題組內(nèi)已經(jīng)做了兩版的布局系統(tǒng),第一版是由朱珊[12]完成的,其實(shí)現(xiàn)了將模型放入可用空間中并且保證了模型之間不會(huì)發(fā)生碰撞,使得生成的場(chǎng)景富有變化性,在第二版系統(tǒng)中,倪德娟[13]設(shè)計(jì)出了多種布局樣式,在一定程度上提高了布局的美觀性,然而也存在布局相對(duì)固定、模型之間沒(méi)有相關(guān)性等問(wèn)題.

7 結(jié)語(yǔ)

布局問(wèn)題是在滿足一定約束條件下將物體擺放到一個(gè)布局空間中,在工程領(lǐng)域中屬于復(fù)雜組合最優(yōu)化問(wèn)題.而手機(jī)3D動(dòng)畫(huà)自動(dòng)生成系統(tǒng)中的布局問(wèn)題是將給定的模型放置到場(chǎng)景的可用空間中,本文為滿足系統(tǒng)對(duì)布局規(guī)劃的要求,提出了分層布局的概念.首先將可用空間中的模型分類,為每一類劃分一個(gè)區(qū)域,之后對(duì)所有區(qū)域進(jìn)行布局規(guī)劃,此為第一層布局,最后對(duì)每個(gè)區(qū)域進(jìn)行布局規(guī)劃,此為第二層布局.通過(guò)本系統(tǒng)可以實(shí)現(xiàn)將模型自動(dòng)擺放到場(chǎng)景的可用空間中,并且具有一定觀賞性.

由于組合爆炸,布局問(wèn)題已被證明是NP-難問(wèn)題.與之相比,本文采用的是基于知識(shí)的方法,可以把復(fù)雜度控制在線性時(shí)間內(nèi),但由于其覆蓋面較小,如何設(shè)計(jì)出更加多樣的布局方式以進(jìn)一步提高豐富度將是以后研究的重點(diǎn).

1Lu RQ,Zhang SM.Automatic generation of computer animation.Berlin Heidelberg:Springer-Verlag,2002:33–35.

2陸汝鈐,張松懋.從故事到動(dòng)畫(huà)片—全過(guò)程計(jì)算機(jī)輔助動(dòng)畫(huà)自動(dòng)生成.自動(dòng)化學(xué)報(bào),2002,28(3):321–348.

3鄧志鴻,唐世渭,張銘,等.Ontology 研究綜述.北京大學(xué)學(xué)報(bào)(自然科學(xué)版),2002,38(5):730–738.

4Reynares E,Caliusco ML,Galli MR.A set of ontology design patterns for reengineering SBVR statements into OWL/SWRL ontologies.Expert Systems with Applications,2015,42(5):2680–2690.[doi:10.1016/j.eswa.2014.11.012]

5查建中,唐曉君,陸一平.布局及布置設(shè)計(jì)問(wèn)題求解自動(dòng)化的理論與方法綜述.計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào),2002,14(8):705–712.

6劉椿年,張昊.Seed-matrix 三維場(chǎng)景布局系統(tǒng).北京工業(yè)大學(xué)學(xué)報(bào),2008,34(1):97–102.

7Dowsland KA,Dowsland WB.Packing problems.European Journal of Operational Research,1992,56(1):2–14.[doi:10.1016/0377-2217(92)90288-K]

8Leung TW,Chan CK,Troutt MD.Application of a mixed simulated annealing-genetic algorithm heuristic for the two-dimensional orthogonal packing problem.European Journal of Operational Research,2003,145(3):530–542.[doi:10.1016/S0377-2217(02)00218-7]

9Bortfeldt A,Gehring H.A hybrid genetic algorithm for the container loading problem.European Journal of Operational Research,2001,131(1):143–161.[doi:10.1016/S0377-2217(00)00055-2]

10田園.室內(nèi)陳設(shè)藝術(shù)與環(huán)境裝飾.北京:清華大學(xué)出版社,2014.

11張綺曼,潘吾華.室內(nèi)設(shè)計(jì)資料集-2:裝飾與陳設(shè)編.北京:中國(guó)建筑工業(yè)出版社,1999.

12朱珊.手機(jī)3D動(dòng)畫(huà)自動(dòng)生成系統(tǒng)中動(dòng)畫(huà)定量計(jì)算的設(shè)計(jì)與實(shí)現(xiàn)[碩士學(xué)位論文].北京:北京工業(yè)大學(xué),2012.

13倪德娟.手機(jī)3D動(dòng)畫(huà)自動(dòng)生成系統(tǒng)中空間布局規(guī)劃的設(shè)計(jì)與實(shí)現(xiàn)[碩士學(xué)位論文].北京:北京工業(yè)大學(xué),2014.

Spatial Hierarchical Layout Planning for Mobile 3D Animation Generation

WANG Xiao-Fei,HUANG Lei
(Information Science Division,Beijing University of Technology,Beijing 100124,China)

Based on messages sent by users,the 3D animation automatic generation system of mobile phone,after a serial process of information extraction,plot planning,would generate a video animation and send it to the receivers.The layout planning is an important part of the automatically generated system,which can place the model to the space on the animation scene.Through the study of layout problems,this paper proposes a hierarchical layout method based on the regional and model layout.It includes qualitative planning and quantitative calculation,using semantic web technology to build hierarchical layout knowledge base,derivation of hierarchical layout qualitative planning scheme based on rule,dynamic calculation of model location.Finally,experimental results show that the hierarchical layout planning is effective and diverse,and it meets the requirements of automatic generation system for layout planning.

animation automatic generation; layout planning; regional layout; hierarchical layout; semantic web

王曉飛,黃蕾.面向手機(jī)3D動(dòng)畫(huà)自動(dòng)生成的空間分層布局規(guī)劃.計(jì)算機(jī)系統(tǒng)應(yīng)用,2017,26(10):110–117.http://www.c-s-a.org.cn/1003-3254/6018.html

2017-01-12; 采用時(shí)間:2017-02-23