離散點云原始形狀及邊界曲線提取算法

1、離散點云原始形狀及邊界曲線提取算法劉光帥 李柏林 何朝明（西南交通大學機械學院成都）摘 要 大規(guī)模離散點云包含多種類型的掃描缺陷 ：噪 聲 、異 常 數(shù) 據(jù) 、孔洞及不規(guī)則的各向異性采樣 ，大 部 分 現(xiàn) 有 的 算法不能夠很好地處理這些缺陷 ，這對點云拓撲關(guān)系的恢復及特征提取帶來了困難 。 針 對 此 問 題 ，提出了一種健 壯 有 效 的點云重構(gòu)算法 ，首 先 ，計算每個數(shù)據(jù)點的局部屬性 ；然后利用局部屬性探測點云中包含的原始形狀 ；最 后 利 用 統(tǒng) 計 優(yōu) 化方法對原始形狀中包含的邊界曲線進行提取和優(yōu)化 ，通過優(yōu)化的邊界曲線可以獲得分段光滑的網(wǎng)格曲面 。 實 例 證 明 ，該算法實用性

2、好 ，對合成點云及真實場景點云的重構(gòu)效果理想 。關(guān)鍵詞 散 亂 點 云 ，原 始 形 狀 ，邊 界 曲 線 ，特 征 點 ，多 尺 度 分 析 ，統(tǒng) 計 優(yōu) 化中圖法分類號文獻標識碼 （，） ， ， ， ， ， 確的邊界位置是不確定的。 本文提出的算法對連續(xù)曲面表達所需的強制信息進行 計 算，并對局部表面屬性（例 如 采 樣、噪 聲）進行估計，這些屬性是探測原始形狀及推斷表面邊界的依 據(jù)。 算法包含三個關(guān)鍵 步 驟：首 先，計 算 點 云局部采樣屬性， 估計點云的噪聲特征及每個數(shù)據(jù)點的粗略法矢；其次，利用隨 機抽樣一致性算法（）探測點云中包含的原始形狀； 最后，對提取的每個原始形狀包含的邊界曲

3、線進行計算及優(yōu) 化處理。 下面對算法進行詳細描述。引言大部分現(xiàn)有三維表面掃描設(shè)備能夠獲取海量的離散點云數(shù)據(jù)，但由于物理設(shè)備及測量條件的限制，獲取數(shù)據(jù)的過程會 受如下因素影響：強噪聲、模型孔洞、異常數(shù)據(jù)、配準誤差及各 向異性采樣。 這對點云重構(gòu)算法的設(shè)計至少提出了兩個方面 的挑戰(zhàn)：其一，如何重構(gòu)表面的拓撲關(guān)系；其二，如何提取散亂 點云包含的原始形狀及幾何屬性。 國內(nèi)外學者針對此問題做 了大量 的 研 究，提出了許多求解 算 法，諸如隱式曲面方 法，、最小移 動 二 乘 法、單元多層次分 解 方 法、（泊 松 流 ）曲 面 重 構(gòu)、變 分 方 法、機 器 學 習統(tǒng) 計 學 方法，其中大部分的算法不

4、能夠處理質(zhì)量較 差 的 點 集。 其 原因在于，所有的算法都對曲面做了隱式假設(shè)，故其只能用于 實驗環(huán)境下掃描系統(tǒng)獲取的具有均一點采樣及低噪聲的點 集，而不適用于真實場景數(shù)據(jù)集的處理。文獻提出了探測點云數(shù)據(jù)包含原始形狀的方法，同時 完成清除噪聲、修補不完全數(shù)據(jù)、清除異常數(shù)據(jù)的工作。 但是 利用該方法探測到的原始形狀代表掃描曲面的哪部分及其精算法描述算法的輸入數(shù)據(jù)為離 散 點 云，且點云數(shù)據(jù)不 包 含 任 何 拓撲及法矢信息。 在對輸入點云進行預處理時，將 對 每 個 點 估計采樣值 及逼近的法矢方向， 的外邊界不僅表示 鄰域的平均距 離，而且描述該鄰域包含點的最小 影 響 半 徑。 的確定依賴于

5、點云的 采 樣 率、采樣的各向異性因子及局部 噪聲分布，同時，需要估計每個數(shù)據(jù)點噪聲分布的 標 準 偏 差 ， 。 此外，估計方差提供了足夠的關(guān)于局部曲面 屬 性 的 信 息，這將有利于原始形狀的探測及識別，進而完成原始形狀描到稿日期： 返修日期：本文受國家自然 科 學 基 金 （），四川省科技計劃項目 （，），中央高?；究蒲袠I(yè)務(wù)費專項資金項目（）資助。述的邊界特征點提取及邊界特征曲線優(yōu)化。 最 后，提 取 每 個原始形狀邊界封閉部分的網(wǎng)格，并對網(wǎng)格進行縫合得到最終 的曲面重構(gòu)結(jié)果。 算法流程如表 所列。原始幾何形狀探測對每個點 進行噪聲 估 計，以 判 別 該 點 是否適配于某個 原始形狀

6、，假如點到某原始形狀的距離小于 ，則該點被 認 為適配于該原 始 形 狀。 給 賦 值 為 ，假 設(shè) 原 始 形 狀 有 效 及 噪聲估計正確，這意味著超過 屬于原始形狀的點 將 被 保 留。探測過程將返回原始形狀的一個集合 及對應的 數(shù)據(jù)集 。 原始形狀識別停止準則的確定是 一件困難的事情，其依賴于多種因素，諸 如 點 的 數(shù) 量、場 景 的 總體結(jié)構(gòu)以 及重構(gòu)的復雜程度。 因為探測過程不 能 自 動 終 止，當識別表面包含的點 數(shù) 量大于用戶定義的閾值 的 概 率表算法處理流程自然語言描述算法流程預處理輸入的離散點云數(shù)據(jù)； 探測原始形狀，原始形狀數(shù)記為；執(zhí)行循環(huán)：（； ）探測邊界候選特征點

7、；篩選邊界候選特征點；提取候選邊界 ；篩選候選邊界 ；初始化邊界拓撲結(jié)構(gòu)；提取邊界閉環(huán) ；優(yōu)化邊界曲線；提取閉環(huán) 的三角網(wǎng)格；小于 時，則停止搜索過程取值范圍為：。 在本文提出的算法中的特征邊界探測即使知道識別出來的原始形狀包含了曲面（或 曲 面 的 逼 近），但是這些信息對點云數(shù)據(jù)的可視化及進一步的處理依舊 不充分，因為原始幾何形狀本身不包括被描述曲面的邊界信 息。 因此，本文提出需要顯式抽取和處 理 這 些 邊 界，同 時 并行利用原始形狀及其分叉點的信息。 對 于 每 種 原 始 形 狀， 抽取一個關(guān)于邊界曲線的非空集，這些曲線通過前一段曲線 的拓撲連通性和下一鄰域的切線方向來描述點集。

8、 抽取邊界 曲線可通過下面步驟來描述。（）提取邊界候選 點。 邊界點的特點是在切 線 空 間 上 缺 少鄰接點，根據(jù)文獻中提出的方法，在 距離內(nèi)對點 的鄰域進行排序，并在切平面將 的鄰域劃成 個錐形。 假 結(jié)束循環(huán)；輸出優(yōu)化處理后的分段光滑曲面重構(gòu)結(jié)果 ；輸入數(shù)據(jù)預處理在缺乏先驗知識 的 前 提 下，搜索每個數(shù)據(jù)點的 采 樣 是一件極其困 難 的 事 情。 本文采用多尺度分析模 式 找 到 每個點 的影響半徑 ，以便獲得法矢方向的 穩(wěn) 健 估 計。 因 此，通過至 鄰域最遠點的距離來計算初始采樣參數(shù) ，同 時，采用 倍的迭代因子來遞增該半徑，對于每一次迭代， 采用主元分析法（即 法）分析 鄰域

9、包含點的權(quán)重 收斂矩陣 ， ： （ ）（ ）， 如兩個及以上相鄰的錐形未被填充，則將 被標識為邊界候 （）補點，如圖 所示。 圖（）的中心點 為內(nèi)點，圖 （ ）的中 式中， 表示點 上影響半徑小于 的鄰 域 集， 是 的心點 為邊界候補點。 通過將與原始形狀關(guān) 聯(lián) 的 所 有 點 映質(zhì)心。 如果給定相鄰迭代和，矩陣特 征 值， 滿 足射到原始形狀空間可增強該步驟的健壯性，并可根據(jù)映射位置進行點法矢推斷。條件：， ，則接受外邊界尺度 。 此外，要， ， 求特 征 向 量 ， 和， 分 別 對 應 最 小 特 征 值 ， 和， ，并保證兩 者 充 分 并 行，即 滿 足。 ， ，其關(guān)鍵在于：假如獲

10、得充分的外邊界尺度 ，特征向量， 表示的法矢方向不再變化。為了建立采樣模型并估計每個點的噪聲方差，需對， 鄰域的一個二階多項式曲面進行擬合，描述如下：圖邊界候選點探測 （）， （）篩分邊界候選 點。 為了使下一步的拓撲 構(gòu) 造 能 夠 順利完成，需對邊界候選點定義的一維曲線進行重采樣及光順：式中，（）返回點 到擬合多項式曲面的距離。 圖 顯示了合成數(shù)據(jù)集的分析結(jié)果：圖（）顯示沿著 軸方向采樣各向 異性遞增，沿著 軸方向噪聲水平遞增；圖 （）顯 示 采 樣 點 沿著 軸和 軸同時遞增；但是圖（）顯示采樣點沿著 軸 方向遞增才能正確地 估 計 噪 聲。 注 意，該 方 法 亦 可 用 于 異 常

11、數(shù)據(jù)的識別，假如迭代模式在規(guī)定的迭代次數(shù)下不收斂或 鄰域的 點 收 斂 于 更 小 的，則可以將對應數(shù)據(jù)點進行清 剔除距離某候選 邊 界 點 小 于 的 所 有 其 它 邊 界 候 選點，并對篩分后的每個邊界候選點及其 個最近的鄰接點 進行最小二乘擬合。 擬合過程給出了每個邊界候選點的切線方 向，如圖 所示。除。 并采用點 方差 的高斯核來進行采樣場及 噪 聲 場的光順處理以提高算法的健壯性。圖遴選邊界候選點及拓撲初始化圖采樣及噪聲估計（）拓撲初始化。 對于每個邊界候選點，在通過切線方向定義的一維曲線上選取與其前后距離最近的 個鄰接點，并以拓撲圖的形式將它們連接起來。 圖 顯示了拓撲初始化過

12、程。（）邊界封閉環(huán)提取。 為了達成邊界封閉環(huán)提取之目的， 本文采用了深度 優(yōu) 先 泛 洪 （）算 法。 以任意一個邊界 點為起始點，沿著該點的所有拓撲鄰接點進行環(huán) 的 增 長。 對 于每個被遍歷到的邊 界 點，記住其遍歷路徑。 假 如 第 二 次 遍 歷到同一個點，則將通過回溯選擇更長的遍歷路徑，當遍歷達 到起始點時終止該泛洪。 再次選擇任意 個種子點，重啟該 泛洪確保提取了可能最長的封閉環(huán)。 重 復 上 述 處 理 過 程，直 至完成所有封 閉 環(huán) 的 識 別。 圖 （）顯 示 了 本 文 算 法 對 復 雜 初始拓撲的處理，因邊界候補點存在誤識別的現(xiàn)象，故處理過程中小于 個點組成的封閉環(huán)被

13、清除。如果一個邊界點， （ ）接近原始形狀 ，同時接近原始形狀 的邊界點，則該邊界點被標記為兩原始形狀的交叉邊界點，交叉邊界點同時被所屬的原始形狀及相鄰原始形狀吸引， 并保證交叉原始形狀之間一致性。 通過應用上述光滑勢到所 有的邊界點，邊界曲線上的拐角將被光順處理。 為 了 避 免 這 種影響，探測角點并將其投影到所有鄰接的原始形狀上，當排 列在相鄰原始形狀上的交叉邊界點發(fā)生改變時，角點被探測 到。 在整個優(yōu)化處理過程中，角點位置不會再發(fā)生 改 變，圖 （）的黑色小球表示被探測到 的 角 點。 如果因為其他勢能夠 將一些點移動到更靠近交叉線的地方，這將改變點的標識，則 需要對交叉邊界點或角點進

14、行重新排列。權(quán)重系數(shù) 表示獨立勢高斯分布的標準偏離值， 和這兩個權(quán)重系 數(shù) 被 賦 值 為 。 因為邊界曲線是嵌在 空 間的一維曲線，故 采 用 基 于 線性搜索的共軛 梯度法對其優(yōu)化問題進行求解，并設(shè)定迭代次數(shù) 小 于 。 圖（）顯示了邊界提取及優(yōu)化結(jié)果。網(wǎng)格化處理最后，采用前向增長算法由原始形狀和優(yōu)化邊界曲線 建立三角網(wǎng)格。 對于任意原始形狀 的每個邊界區(qū)域，通過 隸屬于 且離邊界最遠的點 ，生成邊長為 的種子三角面片。 假如前向邊接近邊界（），則前向增長終止，并 將 前 向頂點與邊界點融合。 對于包含多條邊界的原始形狀，該 過 程必須執(zhí)行數(shù)次。 當所有原始形狀點集都至少接近一個三角面 片

15、（），則將終止網(wǎng)格化處理，同時完成孤立網(wǎng)格面片的縫 合操作。 網(wǎng)格化僅依賴于原始形狀和優(yōu)化后的邊 界 曲 線，而不會因輸入數(shù)據(jù)殘缺而影響其進程。圖邊界點優(yōu)化及邊界封閉環(huán)提取上述處理過程獲得的邊界曲線通常呈鋸齒狀，更 為 重 要的是，這些邊界曲線通常不等價于不同曲面間的交線。 因此，需要對邊界曲線的點位置進行優(yōu)化調(diào)整。優(yōu)化處理采用文獻提到的基于貝葉斯規(guī)則的統(tǒng)計學公式 進 行 優(yōu)化，描述如下：（）（）處理實例（）（）本文提出的算法通常處理的是分段光滑曲面，且 這 些 分段能夠被原始形狀描 述。 圖 顯示了合成點集 的 曲 面 重 構(gòu)，該點集加入了高斯噪聲（標準偏差大約是包圍盒對角線長的 ），圖 描

16、述了邊界探測和優(yōu)化的 具 體 細 節(jié)。 在 圖 （）中 顯示的是加入了高斯噪聲后的輸入點云，通過邊界候補特征 點探測建立邊界及初始拓撲結(jié)構(gòu)，采用統(tǒng)計優(yōu)化方法得到圖（）顯示的經(jīng)過優(yōu)化后的邊 界 曲 線，黑色小球代表角點。 圖（）是三角網(wǎng)格化后的效果。式中， 代表原始幾何形狀 邊界點的集合， 為包含的點集合，條件（）是 后 驗 概 率，（）是 似 然 度，（）是先驗概 率。 在 優(yōu) 化 過 程 中，舍 棄 常 判 據(jù) （）將 導致極大值后驗（）優(yōu)化問題：（）（）為了更有效率地優(yōu)化，將所有組元轉(zhuǎn)換到負對數(shù)空間，綜合勢用 表示。為了計算似然度，直接采用點集 ，懲罰任一邊界點，至其最近鄰接點 的距離 ，

17、描述如下： （） ， ，為了達到邊界曲線光順之目的，采用了兩個光滑勢：通用光滑條件 （）和原始形狀約束條件 （），光滑條件描述如下：圖合成點云處理實例 （） ， （ ）本文算法更關(guān)心的處理對象是從真實掃描系統(tǒng)中獲得的點集。 處理的關(guān)鍵在于對完整場景的識別，包括室外和室內(nèi)。 真實掃描系統(tǒng)提供的點集是各向異性的，同時包含噪聲及異 常數(shù)據(jù)或噪聲帶來的配準誤差。 圖 （）所 示 的 房 間 點 集 需 要通過安裝在豎直軸可 度旋轉(zhuǎn)的云臺上的激光掃描儀獲 得。 利用本文算法，在給定視角上成功地提取了所 有 主 要 的 原始形狀，同時成功提取了所有邊界。 提 取 的 邊 界 候 選 點 及 優(yōu)化后的邊界曲

18、線如圖（）所示，黑色小球代表角點。 式中， 和 是邊界點， 的兩個最近鄰接點。 （）將確保探測到的原始形狀的 幾 何 連 續(xù) 性，描 述如下： （） （， ） 式中，（）是點 到原始形狀 距離函數(shù)的返 回 值；初 始 時，勢 （）僅吸引與其對應原始形狀關(guān)聯(lián)的 邊 界 點。 然 而，： ， ， （）： ， ， （ ）： ， ，： 胡事民，楊永亮，來煜坤數(shù)字幾何處理研究進展 計 算 機 學 報，（）： ，（）：， ， ， （），（）：， ，：， ，：， ，：圖真實場景點云處理實例結(jié)束語 本文提出了一種離散點云原始幾何形狀及特征曲線抽取算法，這將有利于分段光滑的表面網(wǎng)格 建 立。 該 算 法能夠正確

19、地估計離散點云的法矢及噪聲，高效地抽取任意 原始形狀，并利用統(tǒng)計優(yōu)化模式處理原始形狀邊界及原始形 狀交叉處的尖銳特征 線。 在將來的工作中，可 考 慮 將 本 文 提 出的算法與其他重構(gòu)技術(shù)融合以對曲面區(qū)域的細部特征進行 處理，以避免細部原始形狀探測失敗及遺失問題。參 考 文 獻 ， ，： 邱航，陳雷霆基于點的計算機圖形學研究與進展計算機科學，（）： ， ，： ， ，結(jié)束語 本文通過對現(xiàn)有分水嶺算法的分析，將 進 化 規(guī)劃和標記提取方法結(jié)合使用對圖像進行預處理，再進行分水 嶺分割。 這種方法有效地解決了過分割問題，同 時 采 取 的 所 有措施都放在分水嶺分割之前的預處理中進行，分水嶺變換 之

20、后沒有區(qū)域合并操作，方法比較簡便。 同時，本方法基于進 化規(guī)劃的概念進行區(qū)域標記符的提取，快捷而有效；其演化規(guī) 則還可以對內(nèi)外標記符進行預先整合，使其更加符合分割的 視覺特性。 該方法既有效解決分水嶺算法的過分 割 問 題，又 保留了顯著區(qū)域的重 要 目 標。 另 外，可以根據(jù)圖像 特 點 和 具 體的分割要求，調(diào)整分割過程中所選參數(shù)，得到不同的圖像分 割效果，具有一定的靈活性。（上 接 第 頁 ）結(jié)構(gòu)元素的最大半徑 、 鄰域像素中活著的像素數(shù) 以 及 演化所用時間。 如果分割過程中選用的參數(shù)不同，分割結(jié)果 也有很大不同。 如 的選取將影響圖像 分割的區(qū)域個數(shù)和 分割細節(jié)，參數(shù)取值越小，被形態(tài)學開閉重構(gòu)運算濾除的小于 結(jié)構(gòu)元素的細小成分越少，在標記過程中標記出的大于閾值 的極小值越多，所以圖像分割出的區(qū)域數(shù)目越多，分割出的細 節(jié)越多。 在此試驗中， 依據(jù)所選圖像的 灰度直方圖的最小 閾值來選取，對于圖（）的“”圖像，。 結(jié)構(gòu) 元素 的選擇，由于提取的是區(qū)域的邊緣特征，所 以 需 要 把 的值固定化。 當 時，對于提取區(qū)域的邊 緣 特 征 比 較 有利。 而 和 的選擇是緊密相連的，如式（）那樣。 經(jīng)過算 法自動進化試驗，證明當 時，所提取出的區(qū)域邊緣特征 連續(xù)性最佳，過小則邊緣上的斷點增加，過大則會產(chǎn)生大量的 不必要的特征。 至于 演