A quick search method for multimedia signals using global pruning

• Published in: Systems and computers in Japan 2003-11, Vol.34 (13), p.47-58
• Main Authors: Kimura, Akisato, Kashino, Kunio, Kurozumi, Takayuki, Murase, Hiroshi
• Format: Article
• Language: English
• Subjects: global pruning; histogram intersection; L2-distance; similarity search; Time-series Active Search method
• ISSN: 0882-1666; 1520-684X
• DOI: 10.1002/scj.10472

The authors propose a new method for quickly searching for a specific audio or video signal to be detected within a long, stored audio or video stream to determine segments that contain signals that are nearly identical to the given signal. The Time‐series Active Search (TAS) method is one of the quick search methods that have been proposed previously. This signal searching technique based on histograms extracted from the signals had implemented quick searching by local pruning, that is, omitting comparisons of segments for which searching was unnecessary based on similarities in the vicinity of the matching window. In contrast, the proposed technique implements significantly quicker searching by introducing global pruning, which looks at the entire signal time‐series according to histogram classifications based on similarities of the entire signal to eliminate segments that need not be searched, in addition to local pruning. In this paper, the authors present a detailed discussion of the relationship between the degree of global pruning and the accuracy that is guaranteed. For example, the authors showed through experiments that when 128‐dimension histograms were classified to 1024 clusters, the proposed technique achieved a search speed approximately 9 times that of TAS while preserving the same degree of accuracy. The preprocessing calculation time increased by approximately 1% of the time for playing the signal. © 2003 Wiley Periodicals, Inc. Syst Comp Jpn, 34(13): 47–58, 2003; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/scj.10472