基於碎片斷面的高度圖的三維物體碎片的數字拼接方法
2023-10-05 23:58:39
專利名稱：基於碎片斷面的高度圖的三維物體碎片的數字拼接方法
技術領域：
本發明涉及一種三維物體碎片表面的數字拼接方法。
背景技術：
在歷史文物的數字拼接研究領域，涉及的待拼接實物通常是三維物體。對諸如石 碑這樣類似於薄片的物體，可以通過將三維數字拼接問題轉化為石碑碎片邊緣曲線的匹配 問題來進行簡化。在匹配時，一般採用碎片外部原始表面的邊緣。這類簡化可以大大降低 計算複雜度，而不影響薄片類物體的數字拼接的準確率。理論上，如果碎片具有平板幾何條 件且厚度足夠薄，那麼這種簡化損失的只是厚度信息。 目前現有的對三維物體碎片進行三維表面數字拼接的方法，絕大多數是利用碎片 邊緣曲線來進行二維曲線的匹配，進而完成對碎片的數字拼接的。然而許多真實物體不屬 於薄片類物體，對這類物體進行拼接時，其厚度信息是拼接的重要依據，若利用碎片邊緣曲 線來進行二維曲線的匹配，則會導致拼接的準確率降低。2002年刊登在transactions on Pattern Analysis and Machinelntelligence》第24期第1巻第114頁至121頁的 {Reconstruction ofthree-dimensional objects through matching of their parts》 中，使用斷面掃描數據點和碎片邊緣曲線的曲率及扭矩作為特徵進行三維數字拼接；而 2006年刊登在《ACM Transactions on Graphics》第25期第3巻的第569頁至578頁的 《Reassembling fractured objects by geometric matching》中，使用斷面的整合不變特 徵和碎片斷面邊緣曲線作為特徵進行數字拼接。上述兩種拼接方法都直接或間接的使用了 碎片邊緣曲線作為斷面特徵，所以它們並不是完全利用碎片斷面的某些形狀屬性作為特徵 進行碎片數字拼接的，因此仍存在拼接不準確的問題。
發明內容
本發明的目的是解決目前對三維物體碎片的拼接方法中存在的拼接不準確的問
題，提供了一種基於碎片斷面的高度圖的三維物體碎片的數字拼接方法。 基於碎片斷面的高度圖的三維物體碎片的數字拼接方法，它的過程如下 —、對待拼接的每個碎片的表面進行區域分割，獲得每個碎片的各表面區域； 二、逐一判斷步驟一獲得的每個碎片的每一個表面區域是否為斷面，獲得每個碎
片的各個斷面； 三、逐一計算步驟二獲得的每個碎片的每個斷面上的各個像素點的高度值，並將 所述高度值量化，獲得每個碎片的每個斷面的高度圖； 四、計算步驟三所獲得的所有高度圖的最優拼接方案，並按最優拼接方案對所述
所有高度圖涉及的斷面進行兩兩合併，實現對所有碎片的三維數字拼接。 本發明的三維物體碎片的數字拼接方法，完全利用碎片斷面的三維形狀特徵對各
碎片表面進行數字拼接，在運算過程中使用碎片的厚度信息，能夠準確地對三維待拼接物
進行數字拼接。
圖1為待拼接的碎片照片圖；圖2為待拼接的碎片表面的三維數據圖；圖3為表
面區域分割結果圖；圖4為圖3的A向視圖；圖5為斷面確定的結果圖；圖6為圖5中斷面
的B向視圖；圖7為圖5中斷面的C向視圖；圖8為通過計算得到的圖5中斷面的高度圖； 圖9為原始物體破碎為兩塊碎片時的待拼接的碎片照片圖；圖IO為原始物體破碎為兩塊碎 片時，利用三維雷射掃描儀獲得的待拼接的碎片表面的三維數據圖；圖11為原始物體破碎 為兩塊碎片時，經過表面分割和斷面確定後的碎片表面結果圖；圖12為圖11中斷面的高度 圖；圖13為原始物體破碎為兩塊碎片時，使用提出算法得到的最終拼接結果的兩個不同方 向的視圖；圖14為原始物體破碎為三塊碎片時的待拼接的碎片照片圖；圖15為原始物體 破碎為三塊碎片時，利用三維雷射掃描儀得到的待拼接的碎片表面的三維數據圖；圖16為 原始物體破碎為三塊碎片時，經過表面分割和斷面確定後的碎片表面結果圖；圖17為圖16 中的四個斷面的高度圖；圖18為原始物體破碎為三塊碎片時，使用提出算法得到的最終數 字拼接結果圖；圖19為具體實施方式
一的流程示意圖；圖20為具體實施方式
三的流程示 意圖；圖21為具體實施方式
四的流程示意圖。
具體實施例方式
具體實施方式
一 本具體實施方式
的基於碎片斷面的高度圖的三維物體碎片的數 字拼接方法，它的過程如下 —、對待拼接的每個碎片的表面進行區域分割，獲得每個碎片的各表面區域；
二、逐一判斷步驟一獲得的每個碎片的每一個表面區域是否為斷面，獲得每個碎 片的各個斷面； 三、逐一計算步驟二獲得的每個碎片的每個斷面上的各個像素點的高度值，並將 所述高度值量化，獲得每個碎片的每個斷面的高度圖； 四、計算步驟三所獲得的所有高度圖的最優拼接方案，並按最優拼接方案對所述
所有高度圖涉及的斷面進行兩兩合併，實現對所有碎片的三維數字拼接。 其中，步驟一所述的對表面進行區域分割的過程中，採用了基於區域膨脹策略的
三維表面數據區域分割算法。圖19為本具體實施方式
的流程示意圖。 在本具體實施方式
中，所述斷面上像素點的數量由斷面的大小和掃描儀的解析度 決定；而最終獲得的該斷面的高度圖的解析度，是指斷面的高度圖中相鄰像素對應於斷面 主平面上兩點之間的距離。根據實際的不同需要，選擇不同解析度的掃描儀，即可獲得不同 解析度的高度圖。碎片斷面的高度圖是反映碎片斷面的表面的高度起伏變化的圖像，它衡 量的是碎片斷面上各點與斷面主平面間距離的變化。根據不同的量化步長，對每個斷面上 個點的高度值量化後，可得到不同級灰度的高度圖。
具體實施方式
二 本具體實施方式
是對具體實施方式
一的基於碎片斷面的高度圖 的三維物體碎片的數字拼接方法的進一步說明，步驟二所述的判斷步驟一獲得的每個碎片 的每一個表面區域是否為斷面的具體過程為 設待判定的表面區域中包含的所有頂點的集合為V = {Vl， v2， . . . vn}，其中n為該
表面區域中頂點的數量；
利用主成分分析算法獲得該表面區域的主平面； 將V = {Vl， v2， . . . vn}中的所有頂點沿該表面區域的主平面的法線方向投影到所 述主平面上，得到V二 {Vl， v2， ...vn}中各頂點到所述主平面的垂線段的長度的集合D二
{dp d2， . dn}; 計算D = {dp d2， . . . dn}的方差，該方差即為該表面區域的粗糙度； 用T表示碎片表面區域的粗糙度閾值，當該表面區域的粗糙度大於T時，判定該表
面區域為斷面，否則，該表面區域不是斷面。 在本具體實施方式
中認為碎片斷面的粗糙度高於非斷面的粗糙度。粗糙度的閾值 與碎片的材質、碎片表面的腐蝕程度等因素有關，需要在實際應用中視待拼接碎片情況決 定，通常閾值可取圖像表面的梯度平均值，也可取紋理濾波器(或濾波器組)掃描碎片表面 紋理後輸出的平均值。 具體實施方式
三本具體實施方式
是對具體實施方式
一或二的基於碎片斷面的高 度圖的三維物體碎片的數字拼接方法的進一步說明，步驟四所述內容的具體過程為
四一、在步驟三所獲得的所有高度圖中任取兩個高度圖進行組合，並且所述兩個 高度圖所分別涉及的兩個斷面不屬於同一碎片，這樣的所有組合方式的集合記為G，逐一 計算集合G的每一種組合包含的兩個斷面的高度圖的最優匹配位置，以及在最優匹配位置
時，將該兩個斷面的高度圖進行融合後獲得的圖像的有效像素的數量^和有效像素的方
差f ;初始化參數j = 1 ; 四二、將集合G的所有組合按其對應的有效像素的數^;從大到小的順序排成一
列，並將此列記為4^ ，再將集合G的所有組合按其對應的有效像素的方差^:從小到大的順
序排成一列，並將此列記為4^ ; 四三、判斷是否有排於4^和+的前&位的組合，若判斷結果為是，則選出該組合，
設4^和今中包含的元素總數均為N"則
"'1(M-i)/2，M為奇數； 對選出的每個組合所包含的兩個斷面進行合併，並在4^和4^中刪除所有涉及所 述兩個斷面中任意一個斷面的相關參數，更新排列4^和+後，重新執行步驟四三；
若判斷結果為否，則執行步驟四四； 四四、若合併後的結果包含步驟一中所述的待拼接的每個碎片，則執行步驟四五；
否則，刪除集合G的第j個組合，並更新集合G， j = j + l ;然後返回執行步驟四二 ； 四五、將上述所有合併方式及合併順序作為最優拼接方案，按照所述最優拼接方
案對碎片進行拼接，並保證每一次合併操作所涉及的兩個斷面的主平面法向量相對，且該
兩斷面的高度圖處於最優匹配位置。 步驟四一所述的步驟二獲得的所有斷面，包含具體實施方式
一的步驟二中所述的 每個碎片的各個斷面。步驟四四中所述的等式j = j + l，為計算機語言中的賦值語句，其作 用在於計數。圖20為本具體實施方式
的流程示意圖。
6
具體實施方式
四本具體實施方式
是對具體實施方式
三的基於碎片斷面的高度圖
的三維物體碎片的數字拼接方法的進一步說明，步驟四一所述的計算集合G的每一種組合
包含的兩個斷面的高度圖的最優匹配位置，以及在最優匹配位置時，將該兩個斷面的高度
圖進行融合後獲得的圖像的有效像素的數量^和有效像素的方差f的具體過程為 四一一、對待處理的組合所包含的其中一個斷面的高度圖進行翻轉，使得該組合
包含的兩個斷面的高度圖在空間上鏡像相對，形成"面對面"姿態，將此時兩個斷面的高度
圖的相對位置記為初始相對位置； 四一二、將兩個斷面的高度圖中的一幅圖像進行旋轉和平移，使得兩幅斷面的高 度圖的相對位置不斷變換，所述變換均為剛性變換；每次變換後，將兩幅斷面的高度圖融合 成一幅圖像，並計算融合獲得的圖像的有效像素的數量Nr和有效像素的方差Vr;設共變換M 次，將第i次變換後兩幅斷面的高度圖的相對位置記為Si， i G [1， M]，將Si相對於初始相 對位置的旋轉角度和平移量分別記為A 9i和ASi，則得到兩幅斷面的高度圖的M個相對 位置的集合為{Si，i G [l，MB，M為正整數； 四一三、確定兩幅斷面的高度圖的最優匹配位置，具體過程為 將集合{Si， i G [1，M]}中所有元素按其對應的有效像素的數量Nr從大到小的順
序排成一列，並將此列記為^A ，將4^中排在前面的n2個元素按其對應的有效像素的方差l
從小到大的順序再排成一列，並將此列記為4;，將4;中排在前面的n3個元素組成的新集合
記為Q，設夂的元素數為^，則formula see original document page 7
且rvn3均為大於1的自然數； 分別計算Q中所有元素對應的旋轉角度、平移量、有效像素的數量&和有效像素 的方差Vr的平均值，分別相應地記為A^"、 A^、 i^和g; 則該種組合中兩個斷面的高度圖的最優匹配位置相對於初始相對位置的旋轉角 度和平移量分別為A^和A^，在該最優匹配位置時，所述兩個斷面的高度圖的融合圖像的
有效像素的數量和有效像素的方差分別為^;和^。 所謂剛性變換，即不改變圖像中兩像素的相對位置關係。步驟四一一中所述的待 處理的組合，是指將要用於計算其所包含的兩個斷面的高度圖的最優匹配相對位置的組 合，且所屬組合屬於集合G。 在本發明中，對於給定的兩個可能匹配的兩個斷面，對它們的對應像素的互補程 度定義如下兩斷面的高度圖在旋轉、平移到某一相對位置時，通過將對應像素對灰度值相 加後獲得的融合圖像，該融合圖像中有效像素越多、有效像素灰度變化越小，則這兩碎片斷 面的互補程度越高。由上述定義可知，兩碎片斷面的匹配程度主要衡量兩方面因素融合圖 像中有效像素的多少以及融合圖像中有效像素灰度的變化程度。因此，本發明利用融合圖 像中的有效像素和有效像素灰度兩個參數，來尋找最佳匹配斷面並將其合併，進而實現三 維物體碎片的數字拼接。圖21為本具體實施方式
的流程示意圖。
圖1-圖5為碎片表面分割和斷面確定算法的一組實驗結果。圖1為待拼接的碎片照片圖；圖2為利用Roland公司的LPX-250型號三維雷射掃描儀獲得的待拼接的碎片表 面的三維數據圖；圖3為使用基於區域膨脹策略的三維表面數據分割算法得到的表面區域 分割結果圖，最終得到五個表面區域；圖4為圖3的A向視圖；圖5是斷面確定的結果圖，圖 中區域SI為碎片原始表面，區域S2為碎片的斷面。在本具體實施方式
中，所獲得的斷面的 高度圖的灰度級為256。 圖6為圖5中斷面的B向視圖(俯視圖)；圖7為圖5中斷面的C向視圖(側視 圖)；圖8為通過計算得到的圖5中斷面的高度圖。由圖6-圖8可以看出，碎片斷面中間 部分的突起和凹陷在碎片斷面的高度圖上都得到了很好的體現，說明碎片斷面的高度圖可 以準確、高效的描述待拼接的碎片斷面的形狀。 圖9-圖13為原始物體破碎為兩塊碎片時的三維數字拼接仿真實驗結果。圖9 為原始物體破碎為兩塊碎片時的待拼接的碎片照片圖；圖IO為原始物體破碎為兩塊碎片 時，利用三維雷射掃描儀獲得的待拼接的碎片表面的三維數據圖；圖11為原始物體破碎為 兩塊碎片時，經過表面分割和斷面確定後的碎片表面結果圖，其中左側碎片的區域S3、區域 S4分別為碎片原始表面、碎片的斷面，右側碎片的區域S5、區域S6分別為碎片原始表面、碎 片的斷面；圖12為圖11中斷面的高度圖，可見兩碎片斷面的高度圖的相應位置存在很好的 對應關係；圖13為原始物體破碎為兩塊碎片時，使用提出算法得到的最終拼接結果的兩個 不同方向的視圖。圖9-圖13所示實驗的關鍵問題是確定兩斷面的相對位置，從而得到兩 碎片之間的位置關係完成三維數字拼接，也就是說，此時的拼接問題是兩幅碎片高度圖的 配準問題。 圖14-圖18為原始物體破碎為三塊碎片時的三維數字拼接仿真實驗結果。圖14 為原始物體破碎為三塊碎片時的待拼接的碎片照片圖；圖15為原始物體破碎為三塊碎片 時，利用三維雷射掃描儀得到的待拼接的碎片表面的三維數據圖；圖16為原始物體破碎為 三塊碎片時，經過表面分割和斷面確定後的碎片表面結果圖，其中左側碎片的區域S7和區 域S8分別為該碎片的原始表面和斷面，中間碎片的區域S9、區域S10和區域Sll分別為該 碎片的原始表面、第一斷面和第二斷面，右側碎片的區域S12和區域S13分別為該碎片的原 始表面和斷面；圖17為圖16中的四個斷面的高度圖，圖17中左數第一個圖對應圖16中左 側碎片的斷面，圖17中左數第二個、第三個圖分別對應圖16中的中間碎片的第一斷面和第 二斷面，圖17中左數第四個圖對應圖16中右側碎片的斷面；圖18為原始物體破碎為三塊 碎片時，使用提出算法得到的最終數字拼接結果圖。 在仿真實驗中，三塊碎片的三維數字拼接較兩塊碎片的三維數字拼接操作複雜度 大大提高。其原因在於兩塊碎片的數字拼接問題為兩幅碎片高度圖的配準問題，而在三塊 碎片拼接時，共有4個斷面，碎片兩兩匹配的可能為(^42=6種，此時的數字拼接問題不僅是
高度圖之間的配準問題，而且還要在所有可能的匹配碎片隊中尋找最優拼接方案的問題。
本算法通過衡量斷面的高度圖之間的互補程度來實現碎片斷面自動數字拼接。該 方法的基本原理與基於最大互信息的圖像配準方法類似。作為基於體素的圖像配準方法中 的一種，最大互信息配準法以其配準精度高的優點得到越來越多的重視，成為目前應用較 多的一種方法。當兩幅圖像的空間位置達到一致時，它們對應體素對的灰度值的互信息最 大。通常用聯合概率分布和完全獨立時的概率分布間的廣義距離來估計互信息。由於該方 法不需要對兩種成像模式中圖像灰度間關係的性質作任何假設，也不需要對圖像作分割、特徵提取等預處理，幾乎可以用在任何不同模式圖像的配準，並且具有較強的魯棒性，特別 是當其中一個圖像的數據部分缺損時也能得到很好的配準效果。
權利要求
基於碎片斷面的高度圖的三維物體碎片的數字拼接方法，其特徵在於它的過程如下一、對待拼接的每個碎片的表面進行區域分割，獲得每個碎片的各表面區域；二、逐一判斷步驟一獲得的每個碎片的每一個表面區域是否為斷面，獲得每個碎片的各個斷面；三、逐一計算步驟二獲得的每個碎片的每個斷面上的各個像素點的高度值，並將所述高度值量化，獲得每個碎片的每個斷面的高度圖；四、計算步驟三所獲得的所有高度圖的最優拼接方案，並按最優拼接方案對所述所有高度圖涉及的斷面進行兩兩合併，實現對所有碎片的三維數字拼接。
2. 根據權利要求1所述的基於碎片斷面的高度圖的三維物體碎片的數字拼接方法，其 特徵在於步驟二所述的判斷步驟一獲得的每個碎片的每一個表面區域是否為斷面的具體 過程為設待判定的表面區域中包含的所有頂點的集合為V = {Vl， v2，. . . vn}，其中n為該表面 區域中頂點的數量；利用主成分分析算法獲得該表面區域的主平面；將V = {Vl， v2， . . . vn}中的所有頂點沿該表面區域的主平面的法線方向投影到所述主 平面上，得到V二 {Vl， v2， ...vj中各頂點到所述主平面的垂線段的長度的集合D二 {dp d2， dn};計算D = {dp d2， . . . dn}的方差，該方差即為該表面區域的粗糙度；用T表示碎片表面區域的粗糙度閾值，當該表面區域的粗糙度大於T時，判定該表面區域為斷面，否則，該表面區域不是斷面。
3.根據權利要求1或2所述的基於碎片斷面的高度圖的三維物體碎片的數字拼接方法，其特徵在於步驟四所述內容的具體過程為四一、 在步驟三所獲得的所有高度圖中任取兩個高度圖進行組合，並且所述兩個高度 圖所分別涉及的兩個斷面不屬於同一碎片，這樣的所有組合方式的集合記為G，逐一計算集 合G的每一種組合包含的兩個斷面的高度圖的最優匹配位置，以及在最優匹配位置時，將該兩個斷面的高度圖進行融合後獲得的圖像的有效像素的數量^和有效像素的方差5 ; 初始化參數j = 1 ;四二、 將集合G的所有組合按其對應的有效像素的數量i^從大到小的順序排成一列，並將此列記為4^ ，再將集合G的所有組合按其對應的有效像素的方差巧從小到大的順序排成一列，並將此列記為4^四三、 判斷是否有排於4^和+的前&位的組合，若判斷結果為是，則選出該組合，設 4^和4^中包含的元素總數均為N"則 formula see original document page 2對選出的每個組合所包含的兩個斷面進行合併，並在4^和4^中刪除所有涉及所述兩個斷面中任意一個斷面的相關參數，更新排列4^和+後，重新執行步驟四三；若判斷結果為否，則執行步驟四四；四四、 若合併後的結果包含步驟一中所述的待拼接的每個碎片，則執行步驟四五；否 則，刪除集合G的第j個組合，並更新集合G， j = j + 1 ;然後返回執行步驟四二 ；四五、 將上述所有合併方式及合併順序作為最優拼接方案，按照所述最優拼接方案對 碎片進行拼接，並保證每一次合併操作所涉及的兩個斷面的主平面法向量相對，且該兩斷 面的高度圖處於最優匹配位置。
4.根據權利要求3所述的基於碎片斷面的高度圖的三維物體碎片的數字拼接方法，其 特徵在於步驟四一所述的計算集合G的每一種組合包含的兩個斷面的高度圖的最優匹配 位置，以及在最優匹配位置時，將該兩個斷面的高度圖進行融合後獲得的圖像的有效像素 的數量^和有效像素的方差R的具體過程為四一一、 對待處理的組合所包含的其中一個斷面的高度圖進行翻轉，使得該組合包含 的兩個斷面的高度圖在空間上鏡像相對，形成"面對面"姿態，將此時兩個斷面的高度圖的 相對位置記為初始相對位置；四一二、 將兩個斷面的高度圖中的一幅圖像進行旋轉和平移，使得兩幅斷面的高度圖 的相對位置不斷變換，所述變換均為剛性變換；每次變換後，將兩幅斷面的高度圖融合成一 幅圖像，並計算融合獲得的圖像的有效像素的數量K和有效像素的方差1 ;設共變換M次， 將第i次變換後兩幅斷面的高度圖的相對位置記為Si， i G [l，M]，將Si相對於初始相對位 置的旋轉角度和平移量分別記為A 9i和ASi，則得到兩幅斷面的高度圖的M個相對位置 的集合為{Si， i G [l，MB，M為正整數;四一三、 確定兩幅斷面的高度圖的最優匹配位置，具體過程為將集合{Si，i G [1，M]}中所有元素按其對應的有效像素的數量Nr從大到小的順序排 成一列，並將此列記為^w,，將4^中排在前面的112個元素按其對應的有效像素的方差1從小 到大的順序再排成一列，並將此列記為A;，將A;中排在前面的n3個元素組成的新集合記為 Q，設夂的元素數為N2，則formula see original document page 3且rvr^均為大於l的自然數；分別計算Q中所有元素對應的旋轉角度、平移量、有效像素的數量&和有效像素的方 差Vr的平均值，分別相應地記為^、 5、 K和巧；則該種組合中兩個斷面的高度圖的最優匹配位置相對於初始相對位置的旋轉角度和平移量分別為&和^ ，在該最優匹配位 置時，所述兩個斷面的高度圖的融合圖像的有效像素的數量和有效像素的方差分別為^ 和g 。
全文摘要
基於碎片斷面的高度圖的三維物體碎片的數字拼接方法，它涉及一種三維物體碎片的數字拼接方法，它解決了目前對三維物體碎片的拼接方法中存在的拼接不準確的問題。本發明的數字拼接方法為首先將碎片表面進行區域分割，然後判斷各表面區域是否為斷面，根據各斷面的高度圖尋找最優拼接方案，按照最優拼接方案即可實現對所有碎片的數字拼接。本發明完全利用碎片斷面的三維形狀特徵對碎片進行數字拼接，克服了已有技術的不足，保留了碎片的厚度信息，適用於三維物體碎片的自動數字拼接。
文檔編號G06T15/00GK101719282SQ200910073179
公開日2010年6月2日 申請日期2009年11月11日 優先權日2009年11月11日
發明者俞龍江, 孫聖和, 孫震, 李君寶, 李孟 申請人:哈爾濱工業大學