羊 發自 凹非寺
量子位 報道 | 公眾號 QbitAI

畫數學插圖令人頭禿？

現在，CMU的研究人員們開發出了一款實用工具Penrose：

以純文本的方式輸入，根據語言描述，就能自動生成數學圖表。

集合論：

幾何：

線性代數：

光線追蹤：

都不在話下。

整個過程，不需要手動進行繁瑣調整，只需在軟件中用編程語言的方式，描述數學表達式。

并且，這些表達式不僅限于基本功能，而是可以表達任何數學領域的復雜關系。

這一研究成果，入選計算機圖形學頂會SIGGRAPH 2020。

在GitHub上，也得到了3500標星，登上熱榜。

有網友認為：Penrose，就像是科學圖表中LaTeX。

純文本繪制數學圖表

用LaTeX編輯數學公式的快樂，誰用誰知道。

那么Penrose具體是怎么繪制出數學圖表的呢？

比如，要畫出這樣一個集合關系：

在軟件界面中，完成這樣的輸入就能自動生成：

如果對配色、布局不滿意，點擊「resample」，系統會提供其他不同的選擇：

也可以自己手動在「sty」文件中進行調整：

研究人員還提到，該系統支持與基于Web的應用程序集成。并且，Penrose IDE能夠提供自動語法高亮和自動補全功能。

不過，目前Penrose尚處在初期版本，未向公眾開放。研發團隊表示，他們正在快馬加鞭，希望能盡快上線公開版本。

數學符號如何變成精美圖表？

作者之一、CMU計算機科學和機器人學助理教授Keenan Crane表示，他們打造Penrose的目的，是讓所有人都能擁有數學家一般，繪制漂亮圖表的能力。

為了實現這一目標，Penrose圍繞兩個設計原則來實現：

• 通過從數學符號到視覺圖標的映射來規定圖表；
• 通過求解相關有約束的優化問題來合成圖表。

第一步，是用編程語言來規定數學對象及其可視化表示。

具體而言分為三個部分：

• Substance：類似于HTML，用來指定內容。
• Style：類似于CSS，用于調整外觀和可視化表示。
• Domain：聲明數學領域中可用的對象、關系和符號。

需要說明的是，這并不意味著用戶想要上手Penrose，必須學會三種語言。

實際上，大多數用戶只要掌握Substance語言，類似這樣：

Set A,B
intersecting(A,B)
set C := intersection(A,B)
Label A $\text{Circles}$
Label B $\text{Diagrams}$
Label C $\text{Venn Diagrams}$

Domain和Style就交給專業人士，要用的時候調用軟件包就行了。

第二步，使用約束性優化來合成滿足給定規范的圖。

該方法主要受到手繪圖的啟發。

3500星，登上GitHub熱榜

Penrose展現的效果，得到了網友們的點贊。

目前，Penrose的GitHub已經有3500標星，在Hacker News上也有399的熱度。

有網友認為，想要理解數學概念，可視化是非常重要的手段，而Penrose可能會給數學教育帶來很大的幫助。

還有網友表示，希望幾何繪圖軟件Geogebra能集成這一功能。

不過，也有網友指出，簡單的示例說明了系統的思想，但還是希望看到Penrose實現的更為復雜的數學概念可視化，以證明其確實可以表達數學領域的復雜關系。

傳送門

論文地址：http://penrose.ink/media/Penrose_SIGGRAPH2020.pdf

GitHub地址：https://github.com/penrose/penrose

官網：http://www.penrose.ink/

— 完 —

量子位 QbitAI · 頭條號簽約作者

關注我們，第一時間獲知前沿科技動態

析與處理三維形體是計算機圖形學中的一個基本任務與研究方向。近年來隨著三維數據獲取的便捷和三維數據集的迅猛增長，這個研究方向也面臨新的挑戰和契機。一方面，在新的數據形勢下，傳統算法的一些前提假設不再成立，研發新型算法的需求迫在眉睫。另一方面，大數據的出現，可以使得傳統的三維分析和機器學習更加有機地結合起來，從而幫助人們加深對三維世界的認知，有效地理解現實三維幾何世界并構建虛擬數字世界。結合近期微軟亞洲研究院網絡圖形組在這方面的一些工作，劉洋博士在文中分享了數據在三維幾何處理與分析的作用與效力。本文是該系列文章的上篇，主要介紹了三維幾何處理中的去噪問題。

從“三維去噪”談起

問題緣起

關于三維網格去噪或點云去噪的問題，圖形學的初學者一定不會陌生。舉一個例子，利用微軟的Kinect設備掃描三維物體（圖一(a)），我們可以獲得三維網格（圖一(b)）。但由于Kinect設備的低精度，三維網格存在著大量的噪聲。去除這些噪聲并盡量恢復物體的原貌（如圖一(c)）就是三維去噪需要解決的問題。從簡單的拉普拉斯平滑到復雜點的譜分析去噪，從熱門的 平滑到便捷的雙邊濾波， 林林總總有非常多的算法可以使用，也有非常多的圖像域上的去噪方法可以借鑒。但遺憾的是對于類似圖一的噪聲，已有的算法并不能很好地去除。問題出在何處？

圖 一：三維網格去噪

三維去噪問題的前生今世

在回答上述具體問題之前，我們先從一個更大的范疇來考察三維去噪問題。 首先我們做了一個有意思的文獻調研，看看這些年有多少在這方面的研究成果。我們在文獻搜索引擎上以“點云去噪”、“點云平滑”、“網格去噪”、“網格平滑”、“曲面去噪”、“曲面平滑”等關鍵詞聯合搜索近三十年的相關文獻。得到的文獻數目相當驚人—— 超過一萬篇。雖然其中一部分文獻弱相關，但該數目也反映了去噪問題的重要性及其在實際中的需求。我們對文獻數目和文獻年份也做了一個簡單的分析（見下圖），可以看到相關文獻呈遞增趨勢。這一方面與三維掃描、游戲、虛擬現實、增強現實的發展有關，另一方面也說明去噪問題還沒有完美的解決方案。

去噪問題難在何處？我們對該問題有以下幾點認識：

● 去噪問題本質上是求解一個病態的逆問題：在噪聲的類型和程度未知、真實模型的幾何特性未知的前提下，如果要把噪聲從輸入中完美剝離，必然需要引入各種假設來輔助求解。

● 很多去噪算法對真實物體的幾何特性做了很強的假設，比如曲面是光滑，或者曲面類似CAD模型具有分片光滑和含有大量平面的特性。 然而這一類的曲面只占三維物體類型中一小部分。

● 眾多算法顯式或隱含地對噪聲模型做了假設，這些模型基本以高斯噪聲為主，更廣義一點，算法假設噪聲是獨立同分布。然而真實噪聲的成因復雜，這些假設在很多情況下并不成立。針對高斯噪聲的去噪方法在實際中也表現一般。

● 很多算法的機理和評測是有缺陷的，呈現理論和實際脫節的情況。以三角網格曲面去噪為例，很多算法在已知網格上加若干噪聲，然后用去噪結果和已知曲面的差異來比較算法的優劣。這些算法有兩大缺陷：（1）噪聲類型人為給定，與真實不符。（2）已知網格和加噪網格共享相同的網格連接關系，與真實情況不符。如無視這些缺陷，就無助于解決真實去噪問題。

● 實用中各個算法的參數需要人為調配，根據不同輸入反復嘗試。對于用戶而言，調參顯然是一門痛苦且頗具經驗色彩的苦力活。

讓數據說話

不同采集設備由于精度和三維數據獲取方式的差異會導致數據噪聲的不同（比如Kinect一代和二代的噪聲迥異），噪聲在相異幾何特征和不同物體材質上的表現也會有所不同。真實噪聲是與數據以及設備相關的，簡單的噪聲模型不可能刻畫出真實的噪聲。因此，我們提出用數據驅動的方式來學習噪聲和數據的關系，從而幫助解決去噪這一問題。

眾所周知，數據驅動不能盲目地進行，數據本身要有內在并自洽的聯系。在假定了三維數據獲取方式的一致性、物體材質的相似性之后，我們認為符合這些前提獲取的數據集可以用來揭示其中噪聲的特點，并有效地幫助去除這類數據的噪聲。

算法概略

我們對無噪聲三維曲面做一個合理的假設：曲面局部光滑并且任意一點的法方向可以由其局部鄰域的法方向構成的函數刻畫。進一步假設局部鄰域的法方向可以構造一個特征描述子并且存在一個函數使得。如果該特征描述子對噪聲不敏感，那么在該曲面相對應的噪聲曲面上，可以尋找類似的函數并使得來近似真實的法方向（是噪聲曲面上對應 的區域）。

描述子。注意到雙邊法向濾波算子具有一定的抗噪性，我們提出整合不同參數下的雙邊法向濾波算子來構造上述的特征描述子，并稱之為“法方向描述子”(FND)。FND在不同噪聲下具有很好的抗噪性，并且可以用來區分不同的幾何特征。下圖是我們用FND來聚類噪聲曲面的面片（每一類用不同顏色繪制）。可以看到，具有不同幾何特征的噪聲區域被明顯地區分開來，在不同噪聲下（高斯噪聲、均勻噪聲）劃分也具有比較一致的相似性。

級聯回歸網絡。 在給定無噪聲曲面和其對應的含噪聲曲面數據下，我們通過構造一個簡單的神經網絡來尋找。該神經網絡是一個單隱層的RBF網絡，其輸入是噪聲數據的法方向，損失函數由和其對應的真實法方向的差異構造。為了進一步減少回歸誤差，我們針對由FND分類的區域分別尋找各自的。回歸出來的法方向結果，用來指導噪聲曲面頂點位置的更新，從而達到減少噪聲的效果。注意到單隱層網絡的擬合能力有限，我們利用級聯的方式將當前去噪后曲面的法方向作為輸入，訓練新的網絡降低逼近誤差。我們發現，級聯若干個單隱層網絡可以極大程度地減少噪聲并不失計算的便捷性。在實際中，三次級聯就可以帶來非常優秀的去噪結果。訓練出來的網絡在實際運用時也不再有調參之苦。

去噪實戰

我們的算法在人工合成的噪聲數據和真實掃描數據上都表現卓越。比起現有的去噪算法以及它們最佳的參數搭配，在質量和速度上都有很大程度的提高。下圖中展示的是我們使用的真實三維物體（樹脂石膏材料）。我們用高精度的三維掃描儀獲取這些雕像的真實幾何模型并當作無噪聲數據（groundtruth）。

我們準備了三種噪聲數據：1.利用 Kinect 一代的單幀深度數據構成的三角網格；2. 利用Kinect 二代的單幀深度數據構成的三角網格；3. 利用Kinect Fusion 技術重構的三角網格。前面提到，噪聲跟數據、設備都相關，因此對于這三個來源不同的數據，我們分別訓練不同的級聯回歸網絡用來去噪。以下各圖展示了典型的噪聲數據和它們對應的無噪聲數據。

我們的算法可以很好地針對以上數據去噪。以下各圖展示了我們的算法在這三類數據的測試集上的表現。左右兩端分別是噪聲數據和真實數據。可以看到與其他算法（雙邊法向濾波bilateral normal、引導法向濾波 guided normal、光順等）相比，我們算法的輸出更忠實于真實結果：噪聲引起的曲面波動明顯減少，曲面也無過分光滑和過強的劇烈變化。圖下方數值表示的網格法方向與真實值的平均誤差也進一步說明了我們數據驅動下的算法優越性。

Kinect V1 數據上的去噪比較結果

KinectV2 數據上的去噪比較結果

KinectFusion 數據上的去噪比較結果

小結

從數據中學習噪聲與三維數據之間的復雜關系是我們去噪方法的核心思想。從這項工作中我們也認識到：忽略真實數據去研發一個放之四海而皆準的去噪算法是不可行的。既然噪聲來自數據，我們就應該從數據中探究其中的奧秘。我們的工作也體現了數據的威力。感興趣的讀者不妨參考我們發表在Siggraph Asia 2016的文章[1]并試試附帶的Matlab代碼。

值得一提的是，我們的算法假設了物體某點噪聲只和該點附近區域的數據相關。這個局部相關的假設并不總是成立。比如Kinect二代這樣飛時測距的設備，光線由于物體幾何形狀不同可以產生多次反射，從而造成全局位置偏差。我們的算法并不能很好地去除這樣的偏差。是否可以從數據中挖掘其中的規律，還是一個值得探討的問題，歡迎大家在文章下方留言與我們交流探討。

附錄：

[1]:Peng-Shuai Wang, Yang Liu and Xin Tong: Mesh Denoising via Cascaded Normal Regression, ACM Transactions on Graphics (Siggraph Asia 2016), 35(6). Project webpage: http://wang-ps.github.io/denoising.html (點擊閱讀原文，訪問項目主頁)

注：在下篇中，劉洋博士將繼續分享網絡圖形組在三維幾何處理領域的研究工作 – 如何利用卷積神經網絡高效處理三維數據，敬請期待。

作者簡介

劉洋，微軟亞洲研究院主管研究員。2000年和2003年于中國科學技術大學數學系獲得理學學士及碩士學位。2008年于香港大學計算機系獲得博士學位。2008年至2010年于法國INRIA/LORIA研究所從事博士后工作。2010年至今工作于微軟亞洲研究院網絡圖形組。研究興趣包括幾何建模與處理、計算機圖形學、CAGD、建筑幾何等方向。

在高水平學術會議和期刊上發表論文五十余篇，在多個國際圖形學會議上擔任或曾擔任程序委員會委員，如SiggraphAsia 2014、Symposium on Geometry Processing(2014-2016)、Pacific Graphics(2013-2017)、Geometric Modeling and Processing(2014-2017)等。

你也許還想看：

感謝你關注“微軟研究院AI頭條”，我們期待你的留言和投稿，共建交流平臺。來稿請寄：msraai@microsoft.com。微軟小冰進駐微軟研究院微信啦！快去主頁和她聊聊天吧。