Accurate repeat finding and object skipping using fingerprints

ABSTRACT

This paper introduces a novel and very accurate segmentation algorithm. It is very efficient and consumes less than 10% of CPU on a simple desktop PC to segment a stream in real-time. It operates on an audio stream, or on the audio portion of a audio-visual stream. It is very accurate: it accurately detects the positions and durations of objects on an over-the-air broadcast television signal, and songs on both FM and internet radio stations (as checked against labeled ground truth streams). The algorithm does not require any prior information or training. We detail the system design and present results of segmenting broadcast streams.

REFERENCES

• 1: http://www.tivo.com.
• 2: http://www.replaytv.com.
• 3: http://www.shazam.com.
• 4: A. Del Bimbo, P. Pala, and L. Tanganelli. Retrieval by content of commercials based on dynamics of color flows. Proc. ICME, pages 479--482, 2000.
• 5: Chris J. C. Burges , John C. Platt , Jonathan Goldstein, Identifying audio clips with RARE, Proceedings of the eleventh ACM international conference on Multimedia, November 02-08, 2003, Berkeley, CA, USA [doi>10.1145/957013.957104]
• 6: C. J. C. Burges, J. C. Platt and S. Jana. Distortion descriminant analysis for audio fingerprinting. IEEE Trans. on Speech and Audio Processing, 11:165--174, 2003.
• 7: P. Cano, E. Batlle, T. Kalker, and J. Haitsma. A review of algorithms for audio fingerprinting. IEEE Workshop on Multimedia Signal Processing, 2002.
• 8: M. Cooper and J. Foote. Summarizing video using non-negative similarity matrix factorization. Proc. IEEE Multimedia Signal Processing Workshop, 2002.
• 9: Dan Gusfield, Algorithms on strings, trees, and sequences: computer science and computational biology, Cambridge University Press, New York, NY, 1997
• 10: J. Haitsma, T. Kalker, and J. Oostveen. An efficient database search strategy for audio fingerprinting.
• 11: A. Hampapur and R. Bolle. Feature based indexing for media tracking. Proc. ICME, 2000.
• 12: C. Herley. ARGOS: Automatically Extracting Repeating Objects from Multimedia Streams. IEEE Trans. Multimedia.
• 13: C. Herley. Extracting repeats from streams. Proc. ICASSP, 2004.
• 14: J.-L. Hsu, C.-C. Liu, and A. L. P. Chen. Discovering nontrivial repeating patterns in music data. IEEE Trans. on Multimedia, 3(3):311--325, 2001.
• 15: J. Haitsma and T. Kalker. A highly robust audio fingerprinting system. Proc. Intl Conf on Music Information Retrieval, 2002.
• 16: H. Jiang, T. Lin, and H.-J. Zhang. Video segmentation with the assistance of audio content analysis. ICME, 2000.
• 17: S. E. Johnson and P. C. Woodland. A method for direct audio search with applications to indexing and retrieval. ICASSP, 2000.
• 18: K. Kashino, T. Kurozumi, and H. Murase. A quick search method for audio and video signals based on histogram pruning. IEEE Trans. on Multimedia, 5(4):348--357, June 2003.
• 19: C. Kuhmunch, On the detection and recognition of television commercials, Proceedings of the 1997 International Conference on Multimedia Computing and Systems (ICMCS '97), p.509, June 03-06, 1997
• 20: T. Muramoto and M. Sugiyama. Visual and audio segmentation for video streams. Proc. ICME, pages 1547--1550, 2000.
• 21: Greg Pass , Ramin Zabih , Justin Miller, Comparing images using color coherence vectors, Proceedings of the fourth ACM international conference on Multimedia, p.65-73, November 18-22, 1996, Boston, Massachusetts, United States [doi>10.1145/244130.244148]
• 22: Silvia Pfeiffer , Stephan Fischer , Wolfgang Effelsberg, Automatic audio content analysis, Proceedings of the fourth ACM international conference on Multimedia, p.21-30, November 18-22, 1996, Boston, Massachusetts, United States [doi>10.1145/244130.244139]
• 23: R. Ragno , C. J. C. Burges , C. Herley, Inferring similarity between music objects with application to playlist generation, Proceedings of the 7th ACM SIGMM international workshop on Multimedia information retrieval, November 10-11, 2005, Hilton, Singapore [doi>10.1145/1101826.1101840]
• 24: Yong Rui , Anoop Gupta , Alex Acero, Automatically extracting highlights for TV Baseball programs, Proceedings of the eighth ACM international conference on Multimedia, p.105-115, October 2000, Marina del Rey, California, United States [doi>10.1145/354384.354443]
• 25: H. Sundaram and S.-F. Chang. Video scene segmentation using video and audio features. ICME, 2000.
• 26: Erling Wold , Thom Blum , Douglas Keislar , James Wheaton, Content-Based Classification, Search, and Retrieval of Audio, IEEE MultiMedia, v.3 n.3, p.27-36, September 1996 [doi>10.1109/93.556537 ]
• 27: M. Yeung, B.-L. Yeo, and B. Liu. Extracting story units from long programs for video browsing and navigation. Proc. IEEE Conf. on Multimedia Computing and Systems, pages 296--305, June 1996.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.5 INFORMATION INTERFACES AND PRESENTATION (I.7)
      H.5.1 Multimedia Information Systems
          Subjects: Audio input/output

Additional Classification:
  H. Information Systems
  H.5 INFORMATION INTERFACES AND PRESENTATION (I.7)
      H.5.5 Sound and Music Computing
          Subjects: Methodologies and techniques; Signal analysis, synthesis, and processing

General Terms:
Algorithms, Performance

Keywords:
repeat finding, segmentation