[go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Video completion using tracking and fragment merging

  • original article
  • Published:
The Visual Computer Aims and scope Submit manuscript

Abstract

Video completion is the problem of automatically filling space–time holes in video sequences left by the removal of unwanted objects in a scene. We solve it using texture synthesis, filling a hole inwards using three steps iteratively: we select the most promising target pixel at the edge of the hole, we find the source fragment most similar to the known part of the target’s neighborhood, and we merge source and target fragments to complete the target neighborhood, reducing the size of the hole.

Earlier methods were slow, due to searching the whole video data for source fragments or completing holes pixel by pixel; they also produced blurred results due to sampling and smoothing. For speed, we track moving objects, allowing us to use a much smaller search space when seeking source fragments; we also complete holes fragment by fragment instead of pixelwise. Fine details are maintained by use of a graph cut algorithm when merging source and target fragments. Further techniques ensure temporal consistency of hole filling over successive frames.

Examples demonstrate the effectiveness of our method.

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
$34.99 /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 excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

References

  1. Agarwala, A., Dontcheva, M., Agrawala, M., Drucker, S., Colburn, A., Curless, B., Salesin, D., Cohen, M.: Interactive digital photomontage. ACM Trans. Graph. 23(3), 294–302 (2004)

    Google Scholar 

  2. Arya, S., Mount, D.M.: Approximate nearest neighbor queries in fixed dimensions. In: SODA: ACM-SIAM Symposium on Discrete Algorithms, pp. 271–280 (1993)

  3. Bertalmío, M., Bertozzi, A.L., Sapiro, G.: Navier-stokes, fluid dynamics, and image and video inpainting. In: Computer Vision and Pattern Recognition, vol. 1, pp. 355–362 (2001)

  4. Bertalmío, M., Sapiro, G., Caselles, V., Ballester, C.: Image inpainting. In: SIGGRAPH, pp. 417–424 (2000)

  5. Bertalmío, M., Vese, L.A., Sapiro, G., Osher, S.: Simultaneous structure and texture image inpainting. In: Computer Vision and Pattern Recognition, vol. 2, pp. 707–712 (2003)

  6. Boykov, Y., Jolly, M.P.: Interactive graph cuts for optimal boundary and region segmentation of objects in n-d images. In: International Conference on Computer Vision, pp. 105–112 (2001)

  7. Boykov, Y., Kolmogorov, V.: An experimental comparison of min-cut/max-flow algorithms for energy minimization in vision. In: Energy Minimization Methods in Computer Vision and Pattern Recognition, pp. 359–374 (2001)

  8. Chan, T.F., Shen, J.: Mathematical models for local nontexture inpaintings. SIAM J. Appl. Math. 62(3), 1019–1043 (2002)

    Google Scholar 

  9. Comaniciu, D., Meer, P.: Mean shift: a robust approach toward feature space analysis. IEEE Trans. Pattern Anal. Mach. Intell. 24(5), 603–619 (2002)

    Google Scholar 

  10. Comaniciu, D., Ramesh, V., Meer, P.: Real-time tracking of non-rigid objects using mean shift. In: Computer Vision and Pattern Recognition, pp. 2142–2151 (2000)

  11. Criminisi, A., Pérez, P., Toyama, K.: Region filling and object removal by exemplar-based inpainting. IEEE Trans. Image Process. 13(9), 1200–1212 (2004)

    Google Scholar 

  12. DeMenthon, D.: Spatio-temporal segmentation of video by hierarchical mean shift analysis. In: Statistical Methods in Video Processing Workshop,Image and Vision Computer (2002)

  13. Drori, I., Cohen-Or, D., Yeshurun, H.: Fragment-based image completion. ACM Trans. Graph. 22(3), 303–312 (2003)

    Google Scholar 

  14. Heuer, J., Kaup, A.: Global motion estimation in image sequences using robust motion vector field segmentation. In: ACM Multimedia 1, 261–264 (1999)

  15. Jia, J., Wu, T.P., Tai, Y.W., Tang, C.K.: Video repairing: inference of foreground and background under severe occlusion. In: Computer Vision and Pattern Recognition, vol. 1, pp. 364–371 (2004)

  16. Kwatra, V., Schödl, A., Essa, I.A., Turk, G., Bobick, A.F.: Graphcut textures: Image and video synthesis using graph cuts. ACM Trans. Graph. 22(3), 277–286 (2003)

    Google Scholar 

  17. Levin, A., Zomet, A., Weiss, Y.: Learning how to inpaint from global image statistics. In: International Conference on Computer Vision, pp. 305–312 (2003)

  18. Rother, C., Kolmogorov, V., Blake, A.: “grabcut”: interactive foreground extraction using iterated graph cuts. ACM Trans. Graph. 23(3), 309–314 (2004)

    Google Scholar 

  19. Wang, J., Xu, Y., Shum, H.Y., Cohen, M.F.: Video tooning. ACM Trans. Graph. 23(3), 574–583 (2004)

    Google Scholar 

  20. Wei, L.Y., Levoy, M.: Fast texture synthesis using tree-structured vector quantization. In: SIGGRAPH, pp. 479–488 (2000)

  21. Wexler, Y., Shechtman, E., Irani, M.: Space-time video completion. In: Computer Vision and Pattern Recognition, vol. 1, pp. 120–127 (2004)

  22. Zhang, Y., Xiao, J., Shah, M.: Eurographics 2004 / Short Presentations, Region completion in a single image (2004)

  23. Zhang, Y., Xiao, J., Shah, M.: Motion layer based object removal in videos. In: IEEE Workshop on Applications of Computer (2005) (in press)

Download references

Author information

Authors and Affiliations

  1. Tsinghua University, Beijing, China

    Yun-Tao Jia & Shi-Min Hu

  2. Cardiff University, Cardiff, UK

    Ralph R. Martin

Authors
  1. Yun-Tao Jia
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Shi-Min Hu
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Ralph R. Martin
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Yun-Tao Jia.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Jia, YT., Hu, SM. & Martin, R. Video completion using tracking and fragment merging. Visual Comput 21, 601–610 (2005). https://doi.org/10.1007/s00371-005-0313-3

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00371-005-0313-3

Keywords