指導教授：蔣依吾教授 研究生：楊孟哲 國立中山大學應用數學系 Delaunay三角化 於臉部辨識之應用 指導教授：蔣依吾教授 研究生：楊孟哲 國立中山大學應用數學系 1999/6/4
大綱 前言 Delaunay分割 人臉辨識演算法 實驗結果 結論 1999/6/4
前言 人臉辨識： 特徵臉 空間轉換 最大特徵向量 1999/6/4
訓練 M張訓練影像 image difference eigenvectors Maximization Quadratic Form 1999/6/4
特徵臉 1999/6/4
Voronoi圖的歷史 結晶學(Niggli,1927) 氣象學-估計更精準的平均區域雨量(Thiessen,1911) 生態學-估計森林中樹的密度(Brown,1965) 經濟學-市場區域(Shieh,1985) 1999/6/4
Delaunay分割 唯一性(unique) 區域重建 (local re-meshing) 不受大小、方向及位置的改變影響(arrangement invariance) 較能適應影像中的邊(edges). 1999/6/4
1999/6/4
矩形分割的缺點 方塊效應 與方向有關 易受雜訊影響 1999/6/4
Delaunay分割 Planar Voronoi Diagram P={p1,p2,…pn} R2 ，2n<∞ and xixj for i j, i,jIn Voronoi Polygon 1999/6/4
Voronoi圖 1999/6/4
1999/6/4
Dual Graph 1999/6/4
Delaunay Tessellation Voronoi diagram V(p) P={p1,p2,…pn} R2， 3n<∞ Q={q1,q2,…,qn} in V(p) location vector of vertex qi：xil,…,xiki Delaunay Triangulation D={T1,…,Tn} 1999/6/4
人臉辨識演算法 建構Delaunay三角形 導出正規化的三角形面積分佈(normalized triangular area ) 計算長條圖，並且依插入分割點之數目，將長條圖之面積軸放大。 使用平方差計算，篩選出相似影像集合，以此為下一階層之輸入 重覆以上步驟，達到預設門檻時停止 1999/6/4
1999/6/4
影像三角化啟始 1999/6/4
在三角形重心插入點後重建之Delaunay三角形 1999/6/4
經過分割後之影像 1999/6/4
正規化三角形面積 三角形經過正規化處理後的面積 = 三角形的面積 / 影像的總面積 放大正規化三角形面積 相似性測量 1999/6/4
經過放大後部分面積較大 之三角形將會排除在 Histogram外 正規化且經過放大 之面積分佈 1999/6/4
使用階層式查詢之動機 保留部份“位置”資訊 人類視覺由“模糊”→”清楚” 加快辨識速度 1999/6/4
1999/6/4
實驗結果 人臉資料庫 麻省理工學院媒體實驗室(MIT Media Laboratory)取得http://vismod.www.media.mit.edu/vismod/demos/photobook 144位不同人正面影像，每個人有二到四張不同之臉部正面影像，共有308張影像 1999/6/4
人臉資料庫中包含 不同角度 不同位置 不同大小 不同光線 不同表情 不同髮型 有沒有戴眼鏡等變化 1999/6/4
1999/6/4
1999/6/4
1999/6/4
1999/6/4
無法辨識影像 光線 1999/6/4
臉部表情及髮型 1999/6/4
角度 1999/6/4
百分比檢定 α=0.05 H0 :p0.74 vs. H1 :p<0.74 相似影像排名在前20名之機率為0.789 拒絕域c={z|z>1.645} 檢定 1999/6/4
結論 將Delaunay應用於人臉辨識 不受方向、位置、大小及雜訊影響 未來可利用三角形結構作為類神經網路之輸入 1999/6/4