Space-filling approach for fast window query on compressed images

Author

Chung, Kuo-Liang ; Tsai, Yao-Hong ; Hu, Fei-Ching

Author_Institution

Dept. of Inf. Manage., Nat. Taiwan Univ. of Sci. & Technol., Taipei, Taiwan

Volume

9

Issue

12

fYear

2000

fDate

12/1/2000 12:00:00 AM

Firstpage

2109

Lastpage

2116

Abstract

Based on the space-filling approach, this paper presents a fast algorithm for window query on compressed images. Given a query window of size n₁×n₂, the proposed algorithm takes O(n₁logT+P) time to perform the window query, where n₁=max(n₁, n₂) and T×T is the image size; P is the number of outputted codes. The proposed algorithm improves the naive algorithm, which needs O(n₁n₂log T+P) time, significantly. Some experimentations are carried out to demonstrate the computational advantage of the proposed algorithm. From the experimental results, it is observed that the proposed algorithm has about 72-98% time improvement when compared to the naive algorithm.

Keywords

computational complexity; data compression; image coding; query processing; visual databases; Hilbert curve; Hilbert order; algorithm; codes; compressed images; computational advantage; experimental results; fast algorithm; fast window query; image size; naive algorithm; quadtree-based image database; query window size; space-filling approach; time improvement; Books; Cryptography; Filtering; Helium; Hilbert space; Image analysis; Image coding; Image databases; Partitioning algorithms; Spatial databases;

fLanguage

English

Journal_Title

Image Processing, IEEE Transactions on

Publisher

ieee

ISSN

1057-7149

Type

jour

DOI

10.1109/83.887978

Filename

887978