新的物形比對技術及其應用

Abstract

物形比對在影像處理及圖形識別領域中是一個極其重要的課題。很多的應用中都牽涉到比對的問題。由於應用的不同及物形表示方式的差異，比對問題的本質也不盡相同。本論文針對物形的大部比對及細部比對問題提出新的比對技巧。 首先，本論文對於旋轉對稱物形的定向問題提出新的方法。傳統以主軸來定物體方向是相當好的方式，但其對於旋轉對稱物形卻遭遇困難。針對此，我們將主軸的定義擴充，使之適合於旋轉對稱物形，而且得到一個類似原來公式的數學式子來求新的主軸。接著，我們又提出一個新的觀念一褶展物形,來定義諀對稱物形的方向,其基本概念是將旋轉對稱物形的一褶展開到360度，形成褶展物形。對於褶展物形，可利用傳統的方法求得主軸，然後在據之定義旋轉對稱物形的方向。本論文中，我們將傳統主軸的觀念應用到褶展物形，然後導出了褶主軸來定義旋轉對稱物形的方向。本論文中，我們將此兩種新的大部比對方法應用於旋轉對稱物體的辦認與偵測，效果相當不錯。 除了上述定義物形方向做為物形大部比對之用外，本論文還提出兩種新的細部比對方法。此方法首先假設對方式為一對一或一對零的對應，然後以重覆更新比對強度的方式來調整全體的對應關係，最後以互為最佳對應策略來決定比對結果。在此假設及策略下，給定初始的比對關係，比對個體之間就會彼上競爭，以求得到最佳對應，而每個個體的競爭能力則視其其它對應中之最佳對應與其所競爭之對象兩者之比對強度的差值而定。根據每個比對個體的競爭力，就可以更新各個對應的比對強度。經過重覆的競爭，逐次地更新各個對應的比對強度，最後等整個對應關係可達穩定狀態，再利用互為最佳對應策略求出最後的比對結果。若比對問題中有一對多的對應關係存在，則可以利用簡單的後處理解決。此新的細部比對技巧與鬆弛法以較具有相當多的優點，如計算量較少，不需定義支持及支援範圍，同時又沒有不對稱的特性。 此兩新的細部比對方法為一般化的比對技巧，可應用於不同的比對問題上。本論文中，此方法實際應用於手寫中文文字的辨認及立體影像線段比對問題上，結果相當良好。

Shape matching is an important problem and arises in many applications of image processing, pattern recognition, and computer vision. Shape matching problems in different applications usually have their own distinct characteristics and cannot be solved uniformly. In this dissertation, two new global matching techniques are proposed for registration of rotationally symmetric shapes, and two new iterative matching schemes are proposed for detailed shape matching. The applications of the proposed new matching schemes are also investigated. Due to the inapplicability of the definition of the conventional principal axis to rotationally symmetric shapes high-order principal axes are first defined to specify the orientations of rotationally symmetric shapes. An analytic formula like that for conventional principal axis, in terms of high-order momeut functions is derived for computing the directions of high-order principal axes. Alternatively, the concept of fold-expanded shape is proposed for computing the directions of rotationally symmetric shapes. A fold-expanded shape is generated by expanding one fold of a rotationally symmetric shape to the full angle span of 2n. After computing the conventional principal axis of a fold-expanded shape, the fold priucipal axis is then defined accordingly to specify the orientation of the rotationally symmetric shape. The application of these new global matching techniques for recognition and detection of rotationally symmetric shapes is performed and good results have been obtained. As for detailed shape matching, the proposed new iterative matching schemes are based on the premise of one-to-one or many-to-one mapping as well as the mutually-best match strategy for deciding correspondences. Two iterative procedures, one no-discrete and the other discrete type, for updating similarity measures between feature entities is developed. Siinila.r entities in a shape are considered to compete with one another for their best matches during the iterations. As a result, useful information can be derived from the competition to update the match link strengths so that the interference among the feature entities is reduced. By updating the match link strengths iteratively, the match relationships will reach a stable stale finally. The discrete type of iterative matching scheme is suitable for inherent simpler iiiatcliiiig problems. These ma.tching schemes are compared with the well-known relaxation matching technique and several advantages over the latter are identified. The proposed new iterative matching schemes are general matching techniques, and can be applied to solve any matching problem provided that the assumption of one-to-one or one- to-zero match mapping is appropriate. In this dissertation study, they are applied to three appliications, namely, stereo line segment correspondence, and off-line and on-line handwrit- ten Chinese character recognition. In stereo line segment correspondence, geometric con- straints are derived for pruning impossible matches of line segments. Simple line segment attributes, including lengths, orientations, and locations, are used to define a similarity mea- sure function. With the initial similarity measures, the first proposed iterative matching scheme is applied to find correspondences. In the off-line Chinese character recognition application, a stroke-segment similarity measure function, like that for stereo line segmentcorrespondence, is defined first, and the first proposed iterative matching scheme is againapplied to determine the stroke-segment correspondences. Based on the similarity values oftlie stroke-segment correspondences as well as the structural relationships among the corre-spondences, a character similarity measure is defined In the on-line character recognition, tlieproposed discrete type of matching scheme is used to guarantee real-time responses. Withthe initial similarity measures, defined by simple attributes of line segments such as lengths,orientations and locations, the proposed discrete iterative matching scheme is applied tofind the correspondences. Experimental results show that the proposed itcrative matchingschemes are effective and produce good matching results in these applications.