Fast 2D discrete cosine transform on compressed image in restricted quadtree and shading format
✍ Scribed by Kuo-Liang Chung; Wen-Ming Yan
- Publisher
- Elsevier Science
- Year
- 2002
- Tongue
- English
- Weight
- 82 KB
- Volume
- 81
- Category
- Article
- ISSN
- 0020-0190
No coin nor oath required. For personal study only.
✦ Synopsis
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 × 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.