Study And Applications Of Automaton And Chain Code

Image coding technique and image automatic recognition technique are important methods, with which people preserve digital images, get important information from original images and modify images according to human intention. They are important parts of computer graphics. Automaton is the model to realize computer program. The task of automaton theory is to study the model of the abstract machine. The finite automaton model is used in text processing, compilers, hardware design and the like.In the thesis, image processing and automaton are combined. On the basis of automaton model, a new boundary tracing algorithm to generate vertex chain code and crack code was proposed, and then the coordinate labeling automata was formulated. The transformation among image representations is a basic problem in the field of image processing, and the thesis introduced the transformation arithmetic among several chain codes. A new algorithm to obtain the region area directly from vertex chain code of some region was proposed. Two kinds of image compression format were invented by using vertex chain code. These formats were used in the storage of two-value images and resulted in a high compression ratio. With the automaton boundary tracing algorithm, a method to detect the slope of text images automatically was given. This method was efficient and robust for form images. Region filling is also a basic problem in computer graphics. On the base of automaton model, a new efficient filling algorithm by matching points on boundaries was introduced. In addition, image automatic cutting algorithm and a method to obtain the width of character stroke are proposed.Cellular automaton was used in the investigation of the urban traffic network. For the automaton models introduced in this thesis, the BML model was modified by containing a basic traffic factor: road sections. Some new models were made and simulated in detail for the traffic factors and phenomena: road sections, the random distribution of road sections with different length, and traffic police. The automaton models based on BML all had first order phase change from freely-moving phase to jamming phase in which all cars are deadly jammed, which are nonexistent non-physical results in real systems. The research shows that, with the distinction between road sections and crossings and with the police at the crossings, the low-density traffic flow and the high-density traffic flow are distinguished by second order phase change, which accords to the fact of urban traffic flow.