利用最小字串法即時物體之識別

Real-Time Object Recognition with Minimum String Array

馬雲龍(Yuan-Lung Ma)

《華岡工程學報》 5期 (1991/07) Pp. 225-253

https://doi.org/10.29987/CCUHKJE.199107.0010

摘要

一般言之，目標物影像之顯示與否均有其特定之複雜性存在，其邊緣之成長亦有其邏輯性之變動。以往在計算機科學應用及人工智慧處理上，將目標物之影像均以整體形態加以分析處理，但本文是在可行條件下，以簡易表達法……柯氏複性程序法，將機率複性變爲定值長度，並利用對應法則及杜林機完成辨認工作，其優點除使演算時間減少外，更能增大辨認正確率。在此使用串結法，可以直接表達出柯氏之使用結果。
利用最小串列作識別圖表法是識別最小面積的方法，它將影像分爲Σ(2*1-1)*4個元素，其中串列識別法有二：1.環層串列法，或稱爲非線性串列2.直線串列法，或稱爲線性串列，兩者同匹配使用時可節省很多時間，非線性串列可用來做物體方向的標凖化，而線性串列則應用於立即辨認工作。
爲了辨認影像是下確方向，本文中亦使用了環層編碼法從位元對映影像中摘取其特徵。相關事項：標準辨認、串結排列編碼故、環層編碼法、影像處埋、柯氏複雜性程序、杜林機、自動機、形態無關法則、推入機、平面編碼、平面樹狀碼、金字塔怯。
在傳統式之圖形識別上，可以分爲兩大類型，一爲統計式的方法，另一爲文法構式的方法。對於二維式不相接觸物體之識別可歸納成鏈碼(chaincode)、富立葉轉換(Fourier descriptor)、統計式法、符號比對法(symbolic matching)、文法關聯法(syntactic and relaxation method)等[6]。
對於形狀的表示[7]-[8]可以分成三類型來表達：第一爲利用外圍或內部[9]表示，如面積、慣量(moment)等，第二種方式爲轉換方式，例如富立葉轉換、何氏轉換(Hough trans form)等用來描述物體邊緣之變化，第三種方式爲找尋特殊之特微法，但這方法有時會遭遇一些困難。
大部份文獻中的方法[11]-[14]來表達物體形狀時相當複雜，不適合於在工業自動化領域之運用，由於其主要的問題爲物體形狀較不穩定，難訊幹擾、照度、陰影的影響等，還有記憶容量、比對法則、花費時間等諸多之因素均要考慮。
有一些轉換法，例如富立葉轉換[18]-[21]能將影像之資料轉移到頻率領域來分析，使其參數不致因物體形狀大小，位置之移動或旋轉而造成差異，但數學計算上的負荷，可能不是每一個系統所能考慮使用的。
何氏轉換法(Hough transform)轉換法[22]-[23]雖是用來描述直線的距離與角度的關係，但現在已被擴展到能描述各種線狀式圖形，些微的雜誌干擾不致於造成巖重的影響。因此，它常被用在圖形識別上。
利用文法式作形狀分析[24]-[27]，主要觀念乃是物體的形狀較簡單的形狀(sub-shapes)來表示，每一較簡單之形狀可再細分成到最簡單之單元，稱爲基本單元(primitive)，文法式分析乃是將這些基本單元之關係用文句來表達，這文句(sentence)可爲串列(string array)或樹枝。經由這樣的處理，一個二維的圖形可以編碼成一維式之串列。
文法式方法更新演進乃是將附屬參數(attributed parameters)加入其中[28]-[30]，附屬參數包括線段長度、角度等，經由這種方式，將使文法式分析更具彈性，也減少了許多文法表達上的困難。
文法式之方法過去雖有很多應用[26]，但當用在描述平面式物體影像邊緣時，它似乎有兩個缺點：(1)若影像有雜訊幹擾時，將造成很複雜的串列(2)對邊緣作文法分析時，需要使用上下文相關式文法(context sensitive grammer)才能完成。
矩型樹狀(quadtree)[31]-[46]的表達方式近來受到學者重視，它應用在電腦圖學、影像處理等相關領域，其表達方式是運用地將影像平面一直劃分成四個象限，然後以樹之結構來表示其間的關係，在大部份的情況，它能得簡捷地來表示一個圖形。
鏈狀編碼(chain coding)[49]-[50]基本上乃是將曲線轉變成數位式之表達，常用者爲八方向鏈狀碼(8 direction chain code)，就是將物體輪廓曲線編成八方向碼，它非常適合平面式曲線之表。
在大部份影像處理和模型有關[51]，實際上，特微選取所需的時間遠大於比對時間，通常在2:1至50:1之間。因此，爲了快速辨認之需求，也許一些特殊目的(special purpose)之硬體來輔助特微之選取是可行的，但其缺點是缺乏彈性，因此在本研究計劃中，我們將提一此以最少設備及最快速辨認的方法，在過去之文獻中很少涉獵到，但在今日之高科技之時代中，如快速之生産自動化系統，或運用之巡戈飛彈導航系統中，其應用尤顯得重要。

並列摘要

In this paper we shall consider the intrinsic complexity of patterns and the extent to which this notion is well defined. Past work in the computer science and artificial intelligence literature on the decomposition of pictures into their basic building blocks is consistent with our motivation, but this paper will look at the simplest description over all possible descriptions. Thus, the program complexity of kolmogorov given the domain is minimum in finite length such that a Turin Machine can compute functions in finite time. So, the string approach is well used as Kolmogorov process.
Minimum array for Recongnition Chart (MAR Chart) is created with total number of elements Σ (21-1)=4, where L is the number of layers counted from inner cell in even number.
There are two kinds of MAR array: 1. the Circular Layer String Array (CLSA), or Nonlinear String Array (NSA), and 2. Straight Line String Array (SLSA), or Linear String Array (LSA). It can save much time of matching that both of NSA and LSA are used together. The NSA is used for the direction normalization of object, and then, the LSA is applied for rapidity of recognition.
In order to recognize the incorrect-directional image, the circular- layer-code method is also proposed in this paper to extract the features from the bit-map image.

並列關鍵字

Pattern Recognition ； String Array Code ； Circular Layer Code ； Image Processing ； Kolmogorov Complexity program ； Thuring Machine ； Automaton ； Context-free Grammar ； Pushdown Machine ； Quad Coding ； Quad-tree Code ； Pyra