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, this paper presents a fast algorithm for computing 2D discrete cosine transform (DCT) on the compressed grey image directly without the need to decompress 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 number of nodes in the restricted quadtree. Since commonly K < N, the proposed algorithm is faster than the indirect method by decompressing the compressed image first, then applying the conventional DCT algorithm on the decompressed image. The indirect method takes O(N-2 log N) time. (C) 2002 Elsevier Science B.V. All rights reserved.