(A) study for improved graphic imagine coding based on new source models

Abstract

In this dissertation, new methods for improving the performances of the graphic image data compressions have been investigated. To remove the redundancies in binary graphic image data of black and white, the following works have been carried out. First, a novel graphic image model named pattern dependent runlength (PDR) model has been investigated, which is derived from a run-based Markov model. This model is found to yield much lower pel entropies than other two-dimensional coding schemes. The actual compression performance for simple 3-composite states is also much better than conventionals. From the run-based Markov model formulated as a finite state machine, the optimum coding strategy has been obtained. It is a method of optimum composite state construction in a finite state machine model, which yields the lowest entropy. From this point of view, the conventional schemes such as modified READ or CIRC are reviewed and their gains over the one dimensional runlength code are explained. The problem of composite state construction may provide a unified view point to the coding schemes such as CIRC, PDQ, modified READ, and so on, which encode incremental runs in different ways. An interesting property of this model is that the fast decoding of Huffman code is easily implemented due to the ordered distributions. Secondly, to make the proposed model and the coding algorithm be more flexible to the changing statistics of source documents, two kinds of adaptive coding strategies have been developed. One is a cumulative adaptation is a local adaptation. Their good adaptation performances have been confirmed by simulations. Finally, some methods have been devised for the improvement of performance in CRC and CIRC by some modifications. CRC has been improved by the zero-order-hold prediction and by a separate line termination codeword. CIRC is also improved by the zero order-hold prediction and additional classifications of incremental runs. Another result is the exami...