skip to main content
10.5555/1839214.1839232guideproceedingsArticle/Chapter ViewAbstractPublication PagesgiConference Proceedingsconference-collections
research-article
Free access

Background estimation using graph cuts and inpainting

Published: 31 May 2010 Publication History

Abstract

In this paper, we propose a new method, which requires no interactive operation, to estimate background from an image sequence with occluding objects. The images are taken from the same viewpoint under similar illumination conditions. Our method combines the information from input images by selecting the appropriate pixels to construct the background. We have two simple assumptions for the input image sequence: each background pixel has to be disclosed at least once and some parts of the background are never occluded. We propose a cost function that includes a data term and a smoothness term. A unique feature of our data term is that it has not only the stationary term, but also a new predicted term obtained using an image inpainting technique. The smoothness term guarantees that the output is visually smooth so that there is no need for post-processing. The cost is minimized by applying graph cuts optimization. We apply our algorithm to several complex natural scenes as well as to an image sequence with different camera exposure settings, and the results are encouraging.

References

[1]
A. Agarwala, M. Dontcheva, M. Agrawala, S. M. Drucker, A. Colburn, B. Curless, D. Salesin, M. F. Cohen. Interactive digital photomontage. In Proc. of ACM SIGGRAPH, 2004.
[2]
Y. Boykov, V. Kolmogorov. An experimental comparison of min-cut/max-flow algorithms for energy minimization in vision. IEEE Transactions on Pattern Analysis and Machine Intelligence, 26(9), Sept. 2004, 1124--1137.
[3]
Y. Boykov, O. Veksler, R. Zabih. Fast approximate energy minimization via graph cuts. IEEE Transactions on Pattern Analysis and Machine Intelligence, 23(11), Nov. 2001, 1222--1239.
[4]
Y.-Y. Chuang, A. Agarwala, B. Curless, D. H. Salesin, R. Szeliski. Video matting of complex scenes. ACM Transactions on Graphics, 21(3), July 2002, 243--248.
[5]
S. Cohen. Background estimation as a labeling problem. In Proc. of the 10th IEEE International Conference on Computer Vision (ICCV), 2005, pp. 1034--1041.
[6]
A. Colombari, M. Cristani, V. Murino and A. Fusiello. Exemplar-based background model initialization. In Proc. of the third ACM International Workshop on Video Surveillance & Sensor Networks, pp.29--36, 2005
[7]
A. Colombari, A. Fusiello, V. Murino. Background initialization in cluttered sequences. In Proc. of the 2006 Conference on Computer Vision and Pattern Recognition Workshop (CVPRW'06), 2006.
[8]
R. Cucchiara, C. Grana, M. Piccardi, A. Prati. Detecting moving objects, ghosts and shadows in video streams. IEEE Transactions on Pattern Analysis and Machine Intelligence, 25(10), 2003, 1337--1342.
[9]
P. E. Debevec, J. Malik. Recovering high dynamic range radiance maps from photographs. In SIGGRAPH 97 Conference Proceedings, Aug. 1997, pp. 369--378.
[10]
I. Drori, D. Cohen-Or and H. Yeshurun. Fragment-Based Image Completion. In Proc. Of ACM SIGGRAPH, vol.22, pp.303--312, 2003.
[11]
A. Elgammal, D. Harwood, L. Davis. Non-parametric model for background subtraction. In Proc. of Sixth European Conference on Computer Vision, 2000, pp. 751--767.
[12]
M. Granados, H. Seidel, H. Lensch. Background estimation from non-time sequence images. In Graphics Interface, 2008, pp. 33--40.
[13]
W. E. L. Grimson, C. Stauffer, R. Romano, L. Lee. Using adaptive tracking to classify and monitor activities in a site. In IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 1998, pp. 22--29.
[14]
D. Gutchess, M. Trajkovic, E. Cohen-Solal, D. Lyons, A. K. Jain. A background model initialization algorithm for video surveillance. In Proc. of the International Conference on Computer Vision (ICCV), 2001, pp. 733--740.
[15]
E. A. Khan, A. O. Akyuz and E. Reinhard. Ghost Removal in High Dynamic Range Images. In Proc. of IEEE International Conference on Image Processing, 2006.
[16]
V. Kolmogorov, R. Zabih. What energy functions can be minimized via graph cuts? IEEE Transactions on Pattern Analysis and Machine Intelligence, 26(2), Feb. 2004, 147--159.
[17]
V. Kwatra, A. Schodl, I. Essa, G. Turk, A. Bobick. Graphcut textures: Image and video synthesis using graph cuts. ACM Transactions on Graphics, SIGGRAPH 2003, July 2003, 277--286.
[18]
W. Long, Y.-H. Yang. Stationary background generation: An alternative to the difference of two images. Pattern Recognition, 23, 1990, 1351--1359.
[19]
N. Mcfarlane, C. Schofield. Segmentation and tracking of piglets in images. Machine Vision and Applications, 8(3), 1995, 187--193.
[20]
M. Piccardi, T. Jan. Mean-shift background image modeling. In Proc. of the International Conference on Image Processing (ICIP), 2004, pp. 3399--3402.
[21]
E. Reinhard, M. Stark, P. Shirley, J. Ferwerda. Photographics tone reproduction for digital images. In Proc. of ACM SIGGRAPH, 2002, pp. 267--276.
[22]
C. Ridder, O. Munkelt, H. Kirchner. Adaptive background estimation and foreground detection using kalman filtering. In Proc. of the International Conference on Recent Advances in Mechatronics (IJRAM'95), 1995, pp. 193--199.
[23]
C. Stauffer, W. E. L. Grimson. Adaptive background mixture models for real-time tracking. In Proc. of the 1999 Conference on Computer Vision and Pattern Recognition (CVPR), 1999, pp. 2246--2252.
[24]
R. Szeliski, R. Zabih, D. Scharstein, O. Veksler, V. Kolmogorov, A. Agarwala, M. Tappen, C. Rother. A comparative study of energy minimization method for markov random fields with smoothness-based priors. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2008.
[25]
M. F. Tappen, W. T. Freeman. Comparison of graph cuts with belief propagation for stereo, using identical MRF parameters. In Proc. of the Ninth IEEE International Conference on Computer Vision (IEEE 2003), 2003, pp. 900--907.
[26]
M. Uyttendaele, A. Eden and R. Szeliski. Eliminating ghosting and exposure artifacts in image mosaics. In IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR), pp. 509--516, Kauai, Hawaii, 2001.
[27]
J. Wang and M. F. Cohen. An Iterative Optimization Approach for Unified Image Segmentation and Matting. In Proc. of Sixth European Conference on Computer Vision, 2005.
[28]
X. Xu, T. S. Huang. A loopy belief propagation approach for robust background estimation. In IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR), 2008.

Recommendations

Comments

Information & Contributors

Information

Published In

cover image Guide Proceedings
GI '10: Proceedings of Graphics Interface 2010
May 2010
291 pages
ISBN:9781568817125
  • Program Chairs:
  • David Mould,
  • Sylvie Noël

Publisher

Canadian Information Processing Society

Canada

Publication History

Published: 31 May 2010

Author Tags

  1. background estimation
  2. graph cuts
  3. image inpainting

Qualifiers

  • Research-article

Acceptance Rates

GI '10 Paper Acceptance Rate 35 of 88 submissions, 40%;
Overall Acceptance Rate 206 of 508 submissions, 41%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • 0
    Total Citations
  • 72
    Total Downloads
  • Downloads (Last 12 months)27
  • Downloads (Last 6 weeks)3
Reflects downloads up to 17 Feb 2025

Other Metrics

Citations

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media