Multi-resolution tree search for iterated transformation theory-based coding

Iterated transformation theory-based coding (ITTBC) suffers from very high computational complexity in the encoding phase. This is due to its exhaustive search. This paper proposes a multiresolution tree search ITTBC (MTS-ITTBC) to reduce the encoding complexity. MTS-ITTBC searches the ITT-code using a multiresolution search-tree. The computational load of MTS-ITTBC is O(NlogN), while that of full search ITTBC is O(N² ), where N is the number of range blocks or domain blocks in an image. Numerical examples show that the encoding time of MTS-ITTBC can be reduced to 14% of that of the full search ITTBC, while the loss in quality relative to the full search ITTBC is about 0.5 dB in p-pSNR, which is visually negligible