用Delaunay三角形做资料的比对

DataMatchingwithTheDelaunayTriangulation

用Delaunay三角形做資料的比對

Rui-ChingWang王瑞慶DepartmentofAppliedMathematicsNationalSunYat-SenUniversityKaohsiung,Taiwan1大綱前言Delaunay

三角形資料比對演算法實驗結果結論2前言目的:

利用Delaunay三角形的特性發展出一可應用在影像資料比對的方法.動機:

Delaunay三角形可將影像資料切割的比矩形切割更加自然.3建構:依照影像之特性建構三角形.主要特徵:

用正規化的三角形面積(normalizedtriangulararea)分佈作為比對時的主要特徵.4影像分割:將影像資料中有相同特徵的區域分類.減少資料儲存量便於影像特徵的比對5舊有影像分割方法:固定大小正方形切割如MPEG固定8*8非固定大小正方形切割quad-tree矩形切割floorplantree6固定大小切割缺點方塊效應大無法充分反應影像的特性切割數目大7Quad-tree切割缺點方塊效應切割數大(右圖方塊數:4895)易受位移影響8Floorplantree切割缺點與方向有關易受雜訊影響切割速度慢9Delaunay三角形切割唯一性(unique)區域重建(localre-meshing)不受大小、方向及位置的改變影響(arrangementinvariance)切割數目少較能適應影像中的邊(edges).

三角形數:72610應用:郵局、消防隊森林資料取樣Delaunay三角形11為Delaunay三角形三頂點所圍成的外接圓.12

Delaunay三角形13(a)(b)(a)原始的點所產生的Delaunay三角形圖形(b)將原所有點往左上角平移後所產生的Delaunay三角形圖形14(c)(d)(c)將原所有點旋轉45度後所產生的Delaunay三角形圖形(d)在原所有點的距離縮小後所產生的Delaunay三角形圖形15(e)(e)在原所有點中加入一新點後所產生的Delaunay三角形圖形16建立Delaunay三角形Bowyer’salgorithm區域重建時間:O(n)17資料比對演算法建構Delaunay三角形使用分裂與合併演算法(SplitandMergeAlogrithm)導出正規化的三角形面積分佈(normalizedtriangulararea).使用平方差計算，找出差值最小的影像做為比對結果.18SplitandMergealgorithm初始值:

在影像資料上建立一些初始點並找出其Delaunay三角形.19(a)格子點的初始點.20Split:對每一個三角形若此三角形非同性質(homogeneous)則於其重心加入一點.重覆計算Delaunay三角形直到收斂(converges).21(a)(b)(a)分裂前(b)在三角形重心加入一點後重建Delaunay三角形.22三角形分裂過程的一個例子.23Merge:

移除所有無用的(useless)點後重新計算Delaunay三角形.24(a)(b)(a)合併前(b)移除無用的點Q後重建Delaunay三角形.Q25合併後的結果.26normalizedtriangulararea三角形fi的正規化三角形面積=

三角形面積

fi/整張影像面積

.

代表在影像資料I

中有相同正規化面積的個數.27正規化的三角形面積分佈之histogram.28我們使用平方差計算欲辨識的影像A與資料庫中之影像B.29實驗結果資料庫內容:30張不同的灰階人臉影像資料30張不同的灰階印章影像資料89張不同的灰階字元影像資料大小:256x256所有影像的正規化三角形面積分佈資料30加拿大的標準數字與字元集合.31人臉資料庫正規化三角形面積分佈.32印章資料庫正規化三角形面積分佈.33字元資料庫正規化三角形面積分佈.34353637Rota