Abstract
Image template matching is a fundamental step in many image-processingapplications. It is, however, a time-consuming task for the conventionalsingle-processor computer. Even though various fast algorithms have beendeveloped to reduce the computational complexity of template matching, itis always a bottleneck to the realization of a practical image-processingsystem that demands a real-time outcome of template matching. An effectiveway to solve this problem is to develop parallel matching algorithms andthe modular architectures to carry out template matching in a real-timespeed. Through the utilization of storage elements and the algorithmtransform via symmetrically repositioning the template data, a modular andflexible architecture that realizes a cyclical parallel processingstructure for real-time template matching is obtained. This parallelprocessing structure and the corresponding architecture can be consideredas a specific application of a generalized parallel processing structurefor the moving-window process. The applications of this generalizedparallel processing structure to the realization of real-time image edgedetection and high-speed 2-D FIR and IIR digital filters are presented.Aside from the full-search template matching, many efforts have been madeto develop efficient search strategies to estimate the interframe motionvector for low bit-rate image transmission. The main difficulty ofrealizing the existing motion search algorithms in parallel architecturesis that regular data flows and computations cannot be extracted from thesearch procedure. To overcome this difficulty, a parallel block matchingalgorithm is developed by modifying the simplified conjugate directionsearch. From this algorithm, regular data flows and computations can beobtained, and by which a systolic array architecture is designed to carryout these regular computations for real-time motion estimation. To furtherreduce the computational complexity of template matching and therefore thecost of hardware implementation, an accurate similarity measure evaluatedon binary feature maps with logical operations is highly desired. Based onthe concepts of pairing function and moment-presserving quanitization, themethod of moment-preserving pattern matching (MPPM) is introduced tosimplify the measure of similarity while maintaining a good performance.MPPM can be applied to various template matching methods, such astwo-stage matching, sequential matching, and hierarchical matching toimprove search efficiency. The moment-preserving binary features can alsobe used to locate a circular template in a rotated image with the templatedimension large enough.影像樣版比對在許多影像處理的應用中是一個基本而不可缺少的步驟。然而檥版比對是一個計算量非常高而耗時的運算。對於許多需要即時效果的影像係統而言，此步驟乃是整體處理流程的瓶頸。為解決這個問題，本論文之研究係朝二方向進行。其中一個方向係發展樣版比對之平行演算法則，另一方面則為減低相似度量測之計算複雜度。經由記憶單元的利用及樣版資料的對稱換位轉換，吾人可得一循環式的平行處理結構，以及一具有高平行性及導流性，高模組性及規則性，高處理速度，低輸出入頻寬的樣版比對VLSI架構。此一平行處理架構，除了可以即時速度完成樣版比對運算外，尚可被擴展成為一個通用的平行處理架構來處理例如影像旋積，二維FIR 及IIR 數位濾波的運算。相似度量測之簡化研究係根據Pairing函數及矩量保持量化的觀念而進行的。吾人可得一精確而利用邏輯運算操作的相似度量測法則。其可使影像比對的速度加快，而又能降低硬體製作的成本。此演算法則除了可以降低計算複雜度外，亦可被應用於其他的樣版比對演算法則而提高比對處理的效率。另外針對樣版比對在影像通訊應用中的重要性，在論文中亦提出一個用來預估動態影像間之位移量的平行演算法則及收縮式陣列處理器架構。