指紋一向被視為是可以確定唯一個體的生物記號。自從電腦化影像處理(Image Processing)和圖樣識別(Pattern Recognition)的技術越來越發達之後，指紋識別在商業的存取 控制(Access Control)和司法的刑事偵查(Criminal Investigation)領域中扮演了越來越重要的角 色。在這篇文章中，我們解決了從犯罪現場採取到不完全和模糊不清的指紋(現場指紋)之鑑 識問題：如何利用電腦描述指紋的特徵，並且進行比對，以便在龐大的指紋資料庫(目前刑 事警察局約儲存8百萬組指紋)中找出某些重大嫌疑人。現今半自動化的指紋影像特徵 (Minutiae)比對，已被實現於一些(如NEC系統的)系統中。本文建議一種全自動化方法，重 點著眼於不完全圖形的比對。我們利用圖學(Graph Theory)的方法將指紋特徵，如端點(Ridge Ending)、分叉(Bifurcation)等，表示成一張圖(Graph)的節點(Node)，再計算各節點之間的紋 線(Ridge)數當作邊(Edge)。一般而言，資料庫裡的指紋是較完整的，而現場指紋是較不完全 的，於是兩個指紋之間的比對，就成了兩個圖之間的比對問題，亦即我們在求証代表現場指 紋的圖，是否為代表資料庫指紋的圖之子圖(Subgraph)。由於子圖匹配是一個複雜的計算， 我們建議了一系列的化簡方法，以加速比對。本文所提之演算法的時間複雜度理論分析已完 成，系統雛型(Prototype)已在電腦上實現，由於兩指紋特徵之間的關係是集合的包含(Inclusion) 關係，因此本算法將不會遺漏任何一個嫌疑指紋，這是鑑識科學上致力追求的目標。另外， 由模擬結果顯示，本文所建議的方法，對於大量指紋比對能於很短時間內完成，具有極高的 實用價值。