Data Matching with The Delaunay Triangulation 用Delaunay三角形做資料的比對 Rui-Ching Wang 王 瑞 慶 Department of Applied Mathematics National Sun Yat-Sen University Kaohsiung, Taiwan
大綱 前言 Delaunay 三角形 資料比對演算法 實驗結果 結論
前言 目的: 利用Delaunay三角形的特性發展出一可應用在影像資料比對的方法.
建構: 依照影像之特性建構三角形. 主要特徵: 用正規化的三角形面積(normalized triangular area)分佈作為比對時的主要特徵.
影像分割:將影像資料中有相同特徵的區域分類. 減少資料儲存量 便於影像特徵的比對
舊有影像分割方法: 固定大小正方形切割 非固定大小正方形切割 矩形切割 如MPEG固定8*8 quad-tree floorplan tree
固定大小切割 缺點 方塊效應大 無法充分反應影像 的特性 切割數目大
Quad-tree 切割 缺點 方塊效應 切割數大 (右圖方塊數:4895) 易受位移影響
Floorplan tree切割 缺點 與方向有關 易受雜訊影響 切割速度慢
Delaunay三角形切割 唯一性(unique) 區域重建(local re-meshing) 不受大小、方向及位置 的改變影響(arrangement invariance) 切割數目少 較能適應影像中的邊(edges). 三角形數:726
Delaunay三角形 應用: 郵局、消防隊 森林資料取樣
為Delaunay三角形三頂點所圍成的外接圓.
Delaunay 三角形
(a) (b) (a) 原始的點所產生的 Delaunay 三角形圖形 (b) 將原所有點往左上角平移後所產生的 Delaunay 三角形圖形
(c) (d) (c)將原所有點旋轉45度後所產生的 Delaunay 三角形圖形 (d)在原所有點的距離縮小後所產生的 Delaunay 三角形圖形
(e)在原所有點中加入一新點後所產生的 Delaunay 三角形圖形
建立Delaunay三角形 Bowyer’s algorithm 區域重建 時間:O(n)
資料比對演算法 建構Delaunay三角形使用分裂與合併演算法(Split and Merge Alogrithm) 導出正規化的三角形面積分佈(normalized triangular area ). 使用平方差計算，找出差值最小的影像做為比對結果.
Split and Merge algorithm 初始值: 在影像資料上建立一些初始點並找出其Delaunay三角形.
(a)格子點的初始點.
Split: 對每一個三角形若此三角形非同性質(homogeneous)則於其重心加入一點. 重覆計算Delaunay三角形直到收斂(converges).
(a) (b) (a)分裂前 (b)在三角形重心加入一點後重建Delaunay 三角形.
三角形分裂過程的一個例子.
Merge: 移除所有無用的(useless)點後重新計算Delaunay三角形.
(b)移除無用的點Q後重建Delaunay 三角形. (a) (b) (a)合併前 (b)移除無用的點Q後重建Delaunay 三角形.
合併後的結果.
normalized triangular area 三角形fi 的正規化三角形面積 = 三角形面積 fi /整張影像面積 . 代表在影像資料 I 中有相同正規化 面積 的個數.
正規化的三角形面積分佈之histogram.
我們使用平方差計算欲辨識的影像A與資料庫中之影像B.
實驗結果 資料庫內容: 30張不同的灰階人臉影像資料 30張不同的灰階印章影像資料 89張不同的灰階字元影像資料 大小: 256 x 256 所有影像的正規化三角形面積分佈資料
加拿大的標準數字與字元集合.
人臉資料庫正規化三角形面積分佈.
印章資料庫正規化三角形面積分佈.
字元資料庫正規化三角形面積分佈.
Rotation
Scale
Motion blur
Noise
結論 將Delaunay三角形應用於影像資料比對上. 一種不受方向、位置、大小及雜訊影響的比對方法. 已於人臉、印章及字元的辨識.