[發明專利]一種對離散點云數據微分幾何量的估計方法

無效

• 申請號: 200910079802.5
• 申請日: 2009-03-11
• 公開（公告）號: CN101833666A
• 公開（公告）日: 2010-09-15
• 發明（設計）人: 張曉鵬;程章林;李紅軍
• 申請（專利權）人: 中國科學院自動化研究所
• 主分類號: G06K9/62
• 分類號: G06K9/62
• 代理公司: 中科專利商標代理有限責任公司 11021
• 代理人: 梁愛榮

技術領域

本發明涉及計算機圖形學和計算機視覺技術領域，特別涉及一種通過對物體或空間場景進行激光掃描得到三維空間中的離散點云數據，在這樣一類三維點云數據上估計法向量、主曲率(即最大主曲率和最小主曲率)、高斯曲率、平均曲率和主方向(即最大主曲率和最小主曲率對應的方向)這一階、二階微分幾何量的方法。

背景技術

隨著三維激光掃描設備和技術的發展，現實世界中越來越多的復雜物體和場景都可以通過激光掃描建立其三維離散點云(或稱為采樣點集)數據模型，并且這種基于實物測量的數字化建模方法正逐漸成為一種發展趨勢。近幾年來，隨著工業產品設計、影視娛樂、電子商務、文物保護、城市規劃等各方面需求的驅動，三維離散點云數據模型得到了學術界和工業界越來越多的關注，并且有望成為繼數字音頻、數字圖像、數字視頻之后的第四種數字多媒體形式。

三維離散點云數據模型的大量出現和廣泛應用推動了學術界在數字幾何處理方面的研究。而研究的基礎課題之一就是三維離散點云數據模型的底層局部微分幾何量的估計。

曲面的微分幾何量，包括一階微分量法向、二階微分量法曲率、最大主曲率和最小主曲率和主方向等，對于三維形狀的感知與理解發揮著非常重要的作用。其中曲面法向在計算機圖形學領域是一個很基本的幾何量，很多問題的處理效果，例如三維模型處理、造型、繪制等，都緊緊依賴于法向的準確估計。曲率則表征了曲面每一點處的彎曲程度，兩個主方向分別指明發生最大和最小彎曲的方向。這些局部幾何量具有正交不變性，作為物體外形的內在特征廣泛地應用于計算機視覺、計算機圖形學、計算機輔助設計等各個領域，例如，三維模型的分割、配準、檢索，物體表面去噪光順、特征線及輪廓提取、三維重建，非真實感繪制等等。

對于具有解析表達式的連續曲面，微分幾何中有一套理論來直接計算一、二階微分幾何量，因此是一個完全解決了的問題。但是，對于離散曲面來說，如何從離散采樣數據中快速、準確地估計出這些離散采樣數據所代表曲面的局部微分幾何量，一直受到計算機圖形學和計算機視覺相關領域專家們的關注。就已發表的論文來看，出現了很多不同的方法來估計一、二階微分量，其中法向量、最大主曲率、最小主曲率及其對應的主方向、高斯曲率、平均曲率、任意切方向的法曲率都是常用的微分量。大部分的估計方法都是針對深度圖像或多邊形網格數據。這些方法從解決問題的思路上來看大致可以分為兩大類：基于最小二乘準則的估計方法和連續函數離散化方法。

基于最小二乘準則的估計方法，將每個離散采樣點看作是對連續曲面的一個觀測，考察各點某一觀測值，比如點的位置、法曲率等之間的聯系，建立函數關系，然后以此函數為約束建立模型(一般都歸結為一個線性系統)，并在最小二乘意義下對模型求解，進而得到各微分幾何量的估計。

基于最小二乘準則的估計方法中最直觀最常用的一類方法是從采樣點中擬合出一個連續曲面，然后由該連續曲面估計各點的一階、二階甚至高階微分量。曲面擬合中的距離度量一般采用代數距離或幾何距離。基于代數距離的多項式曲面擬合方法都可以線性求解，但是當初始法向不準確或在曲面比較尖銳的地方估計精度可能不高；而基于幾何距離的曲面擬合方法一般都是非線性優化問題，只能通過迭代求解，時間復雜度高，但是相對來說，基于幾何距離的曲面擬合方法計算微分幾何量的準確度最高。得到擬合曲面后，根據連續曲面的一、二階微分量計算公式計算得到曲面各點處的微分幾何量。該類方法最主要的區別就在于擬合曲面的選取不同，一般來說為了計算方便多采用多項式曲面，多項式曲面的階次不少于待估計微分量的階次。對于法向估計，一般都采用一次曲面(平面)擬合，對于二階微分量估計常用的擬合曲面有不帶一次項和常數項的二階多項式曲面、帶一次項或常數項的二階多項式曲面、三階多項式曲面、廣義二次曲面等。這類方法的另外一個區別體現在是否對法向進行修正，因為曲面擬合一般建立在以法向為Z軸的局部坐標系下進行，法向的準確度直接影響了曲面擬合的效果，為了得到更精確的擬合曲面，可以采用帶一次項的多項式曲面去擬合各離散點，然后根據擬合曲面的解析式求出新的法向來替代初始法向，最后基于修正后的新法向進行后續工作。除了用曲面方程作為約束外，還有一種方法采用歐拉公式作為約束函數來計算二階微分量：首先根據各鄰域采樣點計算該點所在切線方向的法曲率，然后根據歐拉公式(描述曲面不同切方向上法曲率與這些法曲率的最大值、最小值，即兩個主曲率之間的關系)在所有采樣點對應的切線方向建立約束關系得到一個方程組(通過變量代換該方程組可以轉化為線性方程組)，采用最小二乘方法計算最大主曲率、最小主曲率及其對應的主方向。