Patch-based Background Initialization

A. Colombari, A. Fusiello, and V. Murino Department of Computer Science
University of Verona, Verona - Italy


In this paper we propose a patch-based technique for robust background initialization (PBI) that exploits both spatial and temporal consistency of the static background. The proposed technique is able to cope with heavy clutter, i.e, foreground objects that stand still for a considerable portion of time. It can process sequences acquired with either a stationary camera or a moving camera, provided that one can compensate for camera motion with respect to the background, as in the case of mosaicing. First the sequence is subdivided in patches that are clustered along the time-line in order to narrow down the number of background candidates. Then, a tessellation is grown incrementally by selecting at each step the best continuation of the current background. The method rests on sound principles in all its stages, and only few, intelligible parameters are needed.

PBI algorithm

  1. In the case of moving camera, compute the projective transformations between frames and compensate for the camera motion.
  2. Estimate the image noise as the (robust) sample variance of frames difference.
  3. Subdivide the spatial domain into overlapping windows (footprints).
  4. On each footprint, cluster image patches along the timeline using single linkage agglomerative clustering, using SSD as the distance and a cutoff based on the Chi-square test.
  5. Compute cluster representative by averaging.
  6. Select the clusters of maximal length, insert their representatives in the background B.
  7. Select a patch in B, select a neighbouring footprint which is not represented in B.
  8. For each cluster representative in the selected footprint evaluate the degree of overlap with B (using SSD) and select candidate patches for insertion in B.
  9. The candidate patches enter a round robin tournament, where the comparison between two of them is done according to cost of the cut defined by their binarized difference. The higher cost wins. The winner of the tournament in inserted in B.
  10. Repeat from step 7 until the background image is complete.


Two images case

Starting images Median background PBI result Extracted object Background growing

Stationary camera case

Original sequence Median background PBI result Moving objects Background growing

Moving camera case

Original sequence Compensated sequence Median background PBI result Moving objects Background growing