Spatial data structure indexing for video databases

Thumbnail Image



Journal Title

Journal ISSN

Volume Title



This thesis explores the application of k-d range search data structures to digital video data. Content-based queries based on colour histogram indexing and colour space indexing for MPEG-2 video I-frames are defined and implemented. Experimentation using 100 MPEG-2 video clips comprising 5706 I-frames was carried out. Two spatial data structures (a 4-d tree and a colour space tree) can satisfy queries such as "find MPEG-2 video 1-frames with > t% pixels in colour range [R[subscript L], R[subscript H]]" or "find MPEG-2 video I-frames with > t% pixels in color range [R[subscript L], R[subscript H]], [G[subscript L], G[subscript H]], [B[subscript L], B[subscript H]], simultaneously", respectively. Prototype software was written in C++ on a UNIX system to test both histogram and colour space range search. A 4-d tree containing 5706 I-frames from 100 MPEG-2 video clips was built in 71 seconds. The average histogram range search time was 37 seconds on a Sun Microsystems ULTRA 5 workstation. A colour space tree of 300 I-frames required 5491 seconds to build, and 2 seconds to answer a colour space query on a Sun Microsystems ENTERPRISE 250 workstation.