採用四元樹搜尋方法進行多重標型比對

Abstract

在許多辨識系統中，我們常常必須做多次且大量的資料比對，例如在 中文文字辨識系統中要確認某一個字，此時這個字的特徵必須先跟系統資 料庫中所有字的特徵比過一次，以決定結果。有時候這種動作是很浪費時 間的。 本文據此提出一個方法來增進二維空間上多重資料的比對速度 。也就是利用四元樹的資料結構來建立系統的資料庫；再利用四元樹的快 速空間搜尋法配合QIC(Quad Intersec-tion Checking)與OIC(Object Intersection Checking)分開的技巧代替線性比對的動作。實驗結果顯示 這種方法只多花費15%的記憶體便可加快比對的速度達7倍以上。 In many recognition systems, we usually perform pattern matching operationsmany times in order to achieve our target. For instance, if we want to identifyone character in a Chinese character recognition system, we must collate this word*s characteristic with thousands of characteristics stored in the system'sdatabase. This often take too much time. This paper proposes a method to speed up the multiple matching operationfor two-dimensional data characteristics. We use the Quad Tree data structureto replace with the system database, and further use the Quad Tree RegionQueries with QIC(Quad Intersection Checking) and OIC(Object IntersectionChecking) to complete matching operations. From the experimental results,this algorithm wastes only 15% more memory space and speeds up the multiplepattern matching operation above 7 times.