FAST CODING ALGORITHM FOR ITERATED TRANSFORMATION THEORY-BASED CODINGBY MULTIRESOLUTION TREE-SEARCH

The digital image coding technique, iterated transformation theory-bas ed coding (ITTBC), requires an enormous amount of encoding search time compared to other coding techniques because of the requisite round-ro bin iterative code search procedure. The computational complexity of p reviously proposed ITTBC methods is on the order of O(N-2), where N is the number of blocks contained in the image. An ITTBC method that use s a multiresolution tree search to reduce code search time is proposed here. In the proposed method, a search tree is constructed by subsamp ling and this search tree is used for code searches. The images statio ned at the nodes of this search tree are formed from blocks extracted from the original image where, depending on their height in the tree, different subsampling rates are used. Thus, the constructed tree has d ifferent resolutions at different heights. By using this type of multi resolution tree search for code searches in the proposed coding method , the computational complexity of code searches becomes O(N log N), wh ich is greatly reduced compared to previously proposed ITTBC methods. From experiments with the proposed coding method, it is shown that onl y a 0.5-dB p-pSNR performance loss is experienced while the encoding t ime of the proposed method is reduced to 14 percent of that required b y previously proposed ITTBC systems.