Pattern Representation by Minimum String Array Approach

利用最少之串列作圖型的表示法

徐進益(Tsing-Yee Tu)

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

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

摘要

本文主要探討物體影像複雜性的問題，過去的研究大部份將物體影像拆解成基本組成方塊，本文中所運用的方法有點類似，但其表達的方式要比它們簡單了許多。我們利用可莫果洛夫對限定區域之物體複雜性的描述方法，根據物體影像出現的機率，以最低的字串長度來表達該影像。因此，如果將可莫果洛夫程序應用到二維的影像，所獲致之結果是以最低的解析度來表示該影像，以便於作最佳的資料存，影像辨認，或資料傳輸的目的。

並列摘要

This paper is concerned with the intrinsic complexity of patterns. Previous works on the decomposition of pictures into their basic building blocks form the basis upon which the current work is based. However, the work presented here will look at the simplest description over all other descriptions. For a given domain the program complexity of Kolmogorov is to represent an image pattern in minimum length according to its pixel occurrence probability. Thus, the Kolmogorov complexity program is performed so that each 2-D image pattern is reduced into minimum resolution forooptimal storage, pattern recognition, or data communication purpose.
The complexity of an image pattern is defined as the number of symbols in a given domain. For a binary image pattern, only two symbols are used which are ”0” and ”1” for object pixel or background. If the occurrence probability of a symbol in a block is the same, then it may be compacted together into a simple subblock to reduce its complexity. The complexity reduction algorithm can be performed by an automaton which reads the input pattern, measures its complexity, and transfers it into a new string array of the least complexity for data communication.