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 examination of the performances of a conditional block model which is a mixture of block model and pel-based Markov model. Related to this model, an optimum coding scheme is devised by extension of CRC, which can be applied to multi-level Markov source encoding with optimum performance.
효과적인 그래픽 영상 데이타의 감축을 위한 몇 가지 모델 및 방법이 제시되었으며, 그 성능과 특징이 검토 되었다.
첫째로 종래의 conditional runlength code (CRC)의 개선을 위해 예측방식과 line termination의 변형을 시도하였다. Conditional incremental runlength code (CIRC) 에서도 ZOH방식의 예측법과 추가적인 conditioning class를 고려함으로써 CRC, CIRC 보다 현격히 증가된 감축률을 가진 code를 얻을 수 있었다.
둘째로 대부분의 이차원 code 에서 부호화 하고 있는 incremental run들의 통계적 모델로서 run-based Markov 모델을 가정한 후 그로부터 PDR(pattern dependent runlength) 모델이라 명명 된 간소화된 모델을 얻고, 이에 대한 coding 방식을 연구하였다. 이 PDR model은 26 conditioning class의 경우 10차의 pel-based Markov model 이상의 감축률을 가지고 있다.
Run-based Markov 모델과 PDR 모델의 관계가 I-FSM (integrated finite state machine) 으로 다루어졌으며 이 PDR model은 run-based Markov 모델로부터 최적 composite state 구성을 통하여 얻어진 것이다. Composite state 구성의 최적화는 runlength 확률의 ordering 에 의해 이루어지면 보였으며, 종래의 CIRC, modified READ, 그리고 MH code 들도 이러한 composite state 구성의 관점에서 재조명해 볼 수 있었다.
PDR 모델의 성능은 26 conditioning class의 경우 CCITT standard code인 modified READ code 에 비해 이론적인 감축률에 있어서 16.5%의 높은 이득이 있었다. 이 모델은 또한 Huffman code의 fast decoding 에 필요한 ordering이 coding 방식 내에 서 이미 이루어짐으로써 fast decoding 에 필요한 추가 부담이 없으므로써, PDR code가 가지고 있는 storage 부담을 어느 정도 완화시켜 주고 있다.
또한 PDR code가 정보원의 통계적 특성의 변화에 따라 적응 할 수 있도록 adaptive coding 방식이 고안되었으며 그 효과가 통계적 특성이 다른 data 에 대한 시뮬레이션을 통해 확인되었다.
마지막으로 block 모델과 pel-based Markov model 의 복합형인 conditional block model 에 대해 검토되었다. 이 모델은 alphabet size의 증가에 따른 복잡도가 예상되나 coding 할 때 state 계산이 줄고, alphabet size의 증가는 오히려 signal modification 등의 효과적인 양자화 방법을 통해 적극적으로 이용할 수 있을 것이다.
