Fast coding algorithm for iterated transformation theory‐based coding by multiresolution tree search
Masayuki Kawamata, Masaki Nagahisa, Tatsuo Higuchi · Electronics and Communications in Japan (Part III Fundamental Electronic Science) · 1995
Abstract The digital image coding technique, iterated transformation theory‐based coding (ITTBC), requires an enormous amount of encoding search time compared to other coding techniques because of the requisite roundrobin iterative code search procedure. the computational complexity of previously proposed ITTBC methods is on the order of O(N2), where N is the number of blocks contained in the image. an ITTBC method that uses a multiresolution tree search to reduce code search time is proposed here. In the proposed method, a search tree is constructed by subsampling and this search tree is used for code searches. the images stationed 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 different resolutions at different heights. By using this type of multiresolution tree search for code searches in the proposed coding method, the computational complexity of code searches becomes O(N log N), which is greatly reduced compared to previously proposed ITTBC methods. From experiments with the proposed coding method, it is shown that only a 0.5‐dB p‐pSNR performance loss is experienced while the encoding time of the proposed method is reduced to 14 percent of that required by previously proposed ITTBC systems.