最新消息

3-D模型複雜度計量—基於資訊理論的演算法

近來人工智慧技術在各應用領域表現亮眼,大部分歸功於高速硬體效能、搭配深度學習神經網路的成果,此外,也要提供大量資料以讓深度學習網路學習到所需的任務核心特徵。然而,在真實世界的大多時候,我們要面對的任務上並沒有那~麼多的資料和標記。既然資料沒有多到讓深度學習網路學到需要的特徵,我們也可以動手設計這些特徵,並用這些特徵資料來『教』電腦判斷目標任務。設計、或決定要採用哪些特徵這個步驟,都包含在機器學習領域的「特徵工程 (Feature Engineering)」範圍。更重要的是,一開始提出的可能只是一些模糊的概念,例如「這個3-D模型做得如何?」這種美感問題。在探討電腦到底能不能學會何謂「美」、「藝術」之前,我們可能要先更具體定義美學評估的目標,例如延伸以上的問題為「這個3-D模型是簡單或複雜?結構上是否平衡?細節程度如何?」。在本文中,我們將聚焦於「3-D模型複雜度」的量化議題,並檢視這些特徵萃取的結果是否合理。

 

對於評估一個模型到底有麼多麼複雜、以及如何計算出複雜程度的數值,或許可採用資訊理論(Information Theory) 作為切入點。先前介紹過、遠古時代人工智慧研究計畫召集者之一的夏農 (C. E. Shannon)[1] 所發表的「通訊數學理論」[2],為此資訊理論的發展基礎。夏農導入物理學『熵 (Entropy)』的概念,用來計算通訊頻道的資訊量。在此簡介一下夏農熵的核心公式:                                                                                       


(1)

                                                

為了說明這個公式,舉個簡單的例子。已知我們打算破關某遊戲,要輸入某串密技,請問,表一中哪個密技的指令比較複雜?

圖一、輸入密技需要特定裝置。(圖片來源:任天堂官網[3])

 

公式(1)中的Pi對應到每個按鍵出現的機率,而整體事件機率為1;故對於密技一和二,我們可分別計算出每個密技的夏農熵 (計算過程見表一)。結果得出密技一的夏農熵為2.522,密技二為0。物理上的解釋是,熵愈大呈現內部系統愈混亂,本範例則呈現熵愈大則內含更多的資訊量。我們用人類的直覺,當場就可斷定密技1比密技2複雜;但藉由熵的計算,我們則可以直接比較兩種密技串的資訊含量孰多孰少。

 

表一、密技表與它們的夏農熵

密技一

A

B

 

 



(上、下)(左、右)(A、B)

密技2

A

A

A

A

A

A

A

A

A

A

 

 

 

 

那麼,又要如何利用熵的概念,計算3-D模型的複雜度呢?有學者[4]提出我們可以使用法向量描述3-D模型的表面,作為計算熵的基礎,如圖二所示。

 


圖二、(左)Fiolka等學者提出的法向量熵的計算概念;(右)紅色部分為模型中的法向量。

 


圖三、模型複雜度計算詳解。

 

考量到除了模型複不複雜的評估問題以外,模型的各個區域是否均衡呢?在細微處是否也很複雜呢?我們用圖三中的流程,對模型同時計算複雜度,並決定切割方向。公式(2)定義要計算的是正規後的entropy,而公式(3)則是決定切割模型的方向及位置。

   

 

          (2)

                  

 

 

 


(3)

               

做完切割流程後,我們就可得到三種複雜度的量化結果,分述如下。表二則是拿學生們繳交的部分模型作業,來計算並展示三種複雜度結果。

 

  1. 輪廓複雜度 (Cf):所有區塊的正規熵加總值,可視為此模型在輪廓上的複雜程度。值愈大愈複雜。
                                        

    (4)

     
  2. 分割複雜度 (Cp):針對切割出來的區塊檢查體積大小差異程度,可視為模型平衡程度。值愈小愈平衡。
                                   

    (5)

     
  3. 區塊比例複雜度 (Cr):對於總區塊數量,除以最大區塊數量的比例值;可視為模型的細節程度。值愈大細節愈多。

                

    (6)


 

表二、模型複雜度計算範例

上傳模型

原始模型

切割結果

複雜度計量

Cp=4.694

Cf=6.057

Cr=0.245%

Cp=5.955

Cf=5.977

Cr=0.0969%

Cp=0.93

Cf=667.294

Cr=4.024%

Cp=5.176

Cf=382.571

Cr=2.528%

 

觀察、比較表二中的結果,同學常常精心設計在模型上的顏色及花紋,但以3-D列印的結果評判,外觀、輪廓、細節才是模型設計的重點。三種模型複雜度忠實的描述3-D模型的各項細節狀態,其指標數值除了能夠做為改進模型的方向及參考,也可以作為進階美學任務的特徵,讓電腦自動判斷「這個模型是否複雜」的後續應用基礎。

 

撰文者:政大人工智慧與數位教育中心   吳怡潔研究員


[1] https://aiec.nccu.edu.tw/ai-column/15

[2] Shannon, Claude Elwood. "A mathematical theory of communication." The Bell system technical journal 27.3 (1948): 379-423.

[3] https://store.nintendo.com/special-offers/nintendo-switch-online.html

[4] Torsten Fiolka, Jörg Stückler, Dominik A Klein, Dirk Schulz, and Sven Behnke. Sure: Surface entropy for distinctive 3d features. In International Conference on Spatial Cognition, pages 74–93, Berlin, Heidelberg, 2012. Springer.