Fast 2D discrete cosine transform on compressed image in restricted quadtree and shading format

Given a compressed image in the restricted quadtree and shading format, thi s paper presents a fast algorithm for computing 2D discrete cosine transfor m (DCT) on the compressed grey image directly without the need to decompres s the compressed image. The proposed new DCT algorithm takes O(K-2 log K N-2) time where the decompressed image is of size N x N and K denotes the n umber of nodes in the restricted quadtree. Since commonly K < N, the propos ed algorithm is faster than the indirect method by decompressing the compre ssed image first, then applying the conventional DCT algorithm on the decom pressed image. The indirect method takes O(N-2 log N) time. (C) 2002 Elsevi er Science B.V. All rights reserved.