Using string matching to detect video transitions | Pattern Analysis and Applications Skip to main content
Springer Nature Link
Log in

Using string matching to detect video transitions

  • Theoretical Advances
  • Published:
Pattern Analysis and Applications Aims and scope Submit manuscript

Abstract

The detection of shot boundaries in videos captures the structure of the image sequences by the identification of transitional effects. This task is important in the video indexing and retrieval domain. The video slice or visual rhythm is a single two-dimensional image sampling that has been used to detect several types of video events, including transitions. We use the longest common subsequence (LCS) between two strings to transform the video slice into one-dimensional signals obtaining a highly simplified representation of the video content. We also developed a chain of mathematical morphology operations over these signals leading to the detection of the most frequent video transitions, namely, cut, fade, and wipe. The algorithms are tested with success with various genres of videos.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5

Similar content being viewed by others

Notes

  1. 2001 TREC Video Retrieval Test Collection, available at http://www.open-video.org.

  2. http://www.vision.scs.carleton.ca/ awhitehe/vidproc/discuss.htm

References

  1. Aigrain P, Joly P (1994) The automatic real-time analysis of film editing and transition effects and its applications. Comp Graphics 18(1):93–103

    Article  Google Scholar 

  2. Bezerra FN (2004) A longest common subsequence approach to detect cut and wipe video transitions. In: Proceedings of Brazilian symposium on computer graphics and image processing. Brazilian Computer Society, IEEE Computer Society, pp 154–161.

  3. Bezerra FN, Leite NJ (2003) Video transition detection using string matching: preliminary results. In: Proceedings of Brazilian symposium on computer graphics and image processing. Brazilian Computer Society, IEEE Computer Society, pp 339–346

  4. Browne P, Smeaton A, N Murphy N, N O’Connor N, Marlow S, Berrut C (2000) Evaluating and combining digital video shot boundary detection algorithms. In: IMVIP 2000—Irish machine vision and image processing conference

  5. Bèscos J (2004) Real-time shot change detection over online mpeg-2 video. IEEE Transactions on circuits and systems for video technology 14(4):475–484

    Article  Google Scholar 

  6. Cooper M, Foote J (2001) Scene boundary detection via video self- similarity analysis. In: IEEE international conference on image processing (3), pp 378–381

  7. Deardoff E, Little TDC, Marshall JD, Venkatesh D, Walzer R (1994) Video scene decomposition with the motion picture parser. In: Proceedings of the IS&T SPIE Symposium on electronic imaging science and technology (digital video compression and processing on personal computer: algorithms and technologies), vol 2187. pp 44–55

  8. del Bimbo A (1999) Visual information retrieval. Morgan Kaufmann

  9. Demarty CH (2000) Segmentation et structuration d’un document Vidéo pour la Charactérisation et l’Indexation de son Contenu Sémantique. PhD thesis, ENSMP, France

  10. Chung MG et al. (1999) Automatic video segmentation based in spatio-temporal features. Korea Telecom J 4(1):4–14

    Google Scholar 

  11. Fernando WAC, Canagarajah CN, Bull DR (1999) Fade and dissolve detection in uncompressed and compressed video sequences. In: Proceedings of the IEEE ICIP, pp 299–303

  12. Grimaud M (1992) A new measure of contrast: the dynamics. SPIE Image algebra and morphological processing III 1769:292–305

    Google Scholar 

  13. Guimarães SJF, Couprie M, Araújo AA, Leite NJ (2003) Video segmentation based on 2d image analysis. Patt Recogn Lett 24:947–957

    Article  Google Scholar 

  14. Hampapur A, Jain R, Weymouth TE (1995) Production model based digital video segmentation. J Multimedia Tools Appl 1(1):9–46

    Article  Google Scholar 

  15. Kim H, Lee J, Yang J, W. Kim S. Sull, Song SM (2001) Visual rhythm and shot verification. Multimedia Tools Appl 15:227–245

    Google Scholar 

  16. Kim H, Park S-J, Lee J, Kim WM, Song SM-H (1999) Processing of partial video data for detection of wipes. In: Proceedings of storage and retrieval for Image and video databases VIII, vol 3656. SPIE, pp 280–289

  17. Nagasaka A, Tanaka Y (1992) Automatic video indexing and full video search for object appearances. IFIP Transactions, Visual Database Systems II, pp 113–127

  18. Navarro G (2001) A guided tour to approximate string matching. ACM Comp Surveys 33(1):31–88

    Article  Google Scholar 

  19. Ngo CW, Pong TC, Chin RT (1999) Detection of gradual transitions through temporal slide analysis. In: IEEE CVPR, pp 36–41

  20. Ngo CW, Pong TC, Chin RT (2001) Video partitioning by temporal slice coherency. IEEE Trans Circuits, Syst Video Technol 11(8):941–953

    Article  Google Scholar 

  21. Osian M, Van Gool L (2003) Video shot characterization. TREC Video Retrieval Evaluation, NIST

  22. S. Sorgi P. Campisi, Neri A (2002) Wipe effect detection for video sequences. In: Proceedings of the IEEE 2002 workshop on multimedia signal processing, pp 9–11

  23. Soille P (2003) Morphological image analysis: principles and applications, 2nd edn. Springer, Berlin Heidelberg New York

  24. Tonomura Y, Akutsu A, Otsuji K, Sadakata T (1993) Videomap and videospaceicon: tools for anatomizing video content. In: ACM Interchi, pp 131–136

  25. Whitehead A, Bose J, Laganière R (2004) Feature based cut detection with automatic threshold selection. In: International symposium on signal processing and applications, pp 410–418, Paris

  26. Wu M, Wolf W, Liu B (1998) An algorithm for wipe detection. In: IEEE international conference on image processing, pp 893–897

  27. Yuan J, Li J, Lin F, Zhang B (2005) A unified shot boundary detection framework based on graph partition model. In: Proceedings of the 13th annual ACM international conference on multimedia, pp 539–542

  28. Zabih R, Miller J, Mai K (1995) A feature-based algorithm for detecting and classifying scene breaks. In: Proceedings of the 3rd international ACM international conference on multimedia, pp 189–200

  29. Zhang HJ, Kankanhalli A, Smoliar S (1993) Automatic partitioning of full-motion video. Multimedia Syst 1(1):10–28

    Article  Google Scholar 

  30. Zhang HJ, Low CY, Gong Y, Smoliar S (1994) Video parsing using compressed data. In: Proceedings SPIE image and video processing II, vol 2172. pp 142–149

  31. Zhang HJ, Smoliar SW (1994) Developing power tools for video indexing and retrieval. In: storage and retrieval for image and video databases II, vol 2185 of SPIE proceedings series, pp 140–149

Download references

Author information

Authors and Affiliations

  1. Universidade de Fortaleza, UNIFOR, Washington Soares, 1321/J30, 60811-905, Fortaleza, CE, Brazil

    Francisco Nivando Bezerra

  2. Universidade Estadual de Campinas, UNICAMP, Caixa Postal 6176, 13084-971, Campinas, SP, Brazil

    Neucimar Jerônimo Leite

Authors
  1. Francisco Nivando Bezerra
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Neucimar Jerônimo Leite
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Francisco Nivando Bezerra.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Bezerra, F.N., Leite, N.J. Using string matching to detect video transitions. Pattern Anal Applic 10, 45–54 (2007). https://doi.org/10.1007/s10044-006-0049-3

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10044-006-0049-3

Keywords

Search

Navigation