Source-linked AI summary
How Far Can You Get By Combining Change Detection Algorithms?
Simone Bianco, Gianluigi Ciocca, Raimondo Schettini
TL;DR
Many video change-detection algorithms address different challenges, but no single one is robust and computationally efficient across them. This paper uses genetic programming to combine existing algorithms under performance-only and balanced performance/efficiency scenarios. The authors report that IUTIS-2 achieves results comparable to more complex state-of-the-art algorithms while remaining computationally affordable for real-time applications.
Problem
No single background-subtraction algorithm handles all video challenges robustly and computationally efficiently, despite many algorithms being evaluated on CDNET 2014.
Source: §1 · p. 2Method
Results
IUTIS-2 achieves results comparable to more complex state-of-the-art change-detection algorithms while remaining computationally affordable for real-time applications.
Source: §6 · p. 10Takeaways & Limitations
The approach can combine simple algorithms to improve performance while keeping computational complexity limited, as demonstrated by IUTIS-2.
Source: §6 · pp. 9–10The tested algorithms use their default parameters because CDNET 2014 requires one parameter set across all video sequences.
Source: §3 · p. 5
Abstract
from arXiv · showhide
Given the existence of many change detection algorithms, each with its own peculiarities and strengths, we propose a combination strategy, that we termed IUTIS (In Unity There Is Strength), based on a genetic Programming framework. This combination strategy is aimed at leveraging the strengths of the algorithms and compensate for their weakness. In this paper we show our findings in applying the proposed strategy in two different scenarios. The first scenario is purely performance-based. The second scenario performance and efficiency must be balanced. Results demonstrate that starting from simple algorithms we can achieve comparable results with respect to more complex state-of-the-art change detection algorithms, while keeping the computational complexity affordable for real-time applications.
1 Introduction
Change detection is needed across varied video applications, but algorithms must balance robustness with computational cost. Because no single background-subtraction algorithm handles all challenges robustly and efficiently, the paper combines existing algorithms under performance-only and performance/efficiency objectives.
1 Introduction
- Increasing algorithm complexity to address real-world challenges also raises time and memory costs, while GPU parallelization is one possible route to real-time use.Background subtraction commonly segments video into foreground and background, producing binary foreground masks.Source: §1 · p. 1
- No single background-subtraction algorithm has been shown to handle the varied video challenges robustly and efficiently, despite more than 35 algorithms evaluated on CDNET 2014.Challenges include changing environmental conditions, illumination, shadows, camera motion, and camera-induced distortions; robust detection with low false alarms is needed as a preprocessing step.Source: §1 · pp. 1–2
- The paper applies genetic programming to combine existing algorithms, examining both performance-only and performance/efficiency-balanced scenarios.A prior study combined top-performing CDNET algorithms for performance alone; this work considers efficient, though not top-performing, algorithms for the balanced scenario.Source: §1 · p. 2
2 The proposed approach
The approach uses genetic programming to evolve combinations and post-processing of binary foreground outputs from existing change-detection algorithms. Its fitness function averages ranks across videos and measures, with terms that favor stronger performance and smaller combinations.
2 The proposed approach
- Genetic programming evolves programs by selecting fitter individuals according to an objective function, representing solutions in forms such as trees or code.Here, GP receives binary foreground images from individual algorithms and operators for combining outputs and post-processing them.Source: §2 · pp. 2–3
- Solutions combine algorithm outputs using spatial and stack-domain operators, including morphological filters and logical operations.The available functionals include erosion, dilation, median filtering, OR, AND, and majority vote.Source: §2 · p. 3
- The fitness function averages candidate ranks across video sequences and performance measures, following the CDNET evaluation approach.The rank is computed against the set of algorithms for each measure.Source: §2 · p. 3
- P1 adds signed distance from the best algorithm on a measure, while P2 penalizes the number of algorithms selected in a candidate.P1 breaks ties in average rank in favor of better measures; weights w1 and w2 independently regulate P1 and P2.Source: §2 · pp. 3–4
3 Experimental setup
The experiments combine computationally efficient, above-average algorithms from BGSLibrary and evaluate them with CDNET 2014 measures across varied video categories. GP uses short training sequences, while the comparison algorithms use their default parameters under the challenge's single-parameter-set rule.
3 Experimental setup
- The candidate pool contains 11 selected BGSLibrary algorithms chosen for computational efficiency, above-average performance, and potentially diverse strategies.The library version used implements more than 30 algorithms; SigmaDelta and SJNMultiCue were included despite being slightly more computationally intensive than simpler choices.Source: §3 · p. 4
- Evaluation uses seven CDNET 2014 measures across 11 video categories, with four to six sequences per category.The challenge requires one parameter set across sequences, so algorithms use BGSLibrary configuration defaults.Source: §3 · pp. 4–5
- IUTIS-2 is the best GP solution trained on the shortest sequence in each category, using fewer than 10% of dataset images; IUTIS-1 uses Baseline sequences and is excluded from further comparison.IUTIS-1 performs worse than IUTIS-2, and its results are not directly comparable with the reported results.Source: §3 · p. 5
4 Results
The results report IUTIS-2 and compare it with performance-based variants IUTIS-3 and IUTIS-5. Each combined solution outperforms the best individual algorithm used to build it.
- IUTIS-2 combines four of the 11 available algorithms: GA, ZMM, MC, and ASB.Its solution tree also uses a sequence of MF operators, an approximation of a larger-kernel median filter.Source: §4 · p. 5
- IUTIS-2’s F-measure is 7.2% higher than MC’s.Source: Table 2 · p. 6, §4 · p. 6
- Figure 2 presents the solution trees for IUTIS-3 and IUTIS-5, built in the purely performance-based scenario.Source: §4 · p. 6, Figure 2 · p. 7
- IUTIS-3 exceeds its best component algorithm’s F-measure by 4.13%, and IUTIS-5 by 5.4%; both also outperform majority-vote solutions.IUTIS-7 and IUTIS-9 achieved performance identical to IUTIS-5.Source: Table 2 · p. 6, §4 · p. 7
5 Computational Time
IUTIS-2 is evaluated in sequential and parallel implementations, with parallel execution averaging about twice the sequential frame rate. The section also compares its computational time with other IUTIS variants and leading algorithms, using estimates for IUTIS-3 and IUTIS-5.
5 Computational Time
- IUTIS-2 timing is reported for sequential and optimized parallel implementations; IUTIS-3 and IUTIS-5 timings are estimates based on the slowest algorithm in each solution tree.Table 3 reports frames per second at 320×240 pixels on an i5-2500K@3.3Ghz computer with 16 GB RAM.Source: §5 · pp. 7, 9, Table 3 · p. 9
- FTS runs at 10 frames per second, while GPU-based AMB reaches 843 frames per second.FTS is implemented in MATLAB; the other compared algorithms are implemented in C++, and AMB uses CUDA.Source: Table 3 · p. 9, §5 · p. 9
- The parallel IUTIS-2 implementation averages about 2 times the frame rate of the sequential version.The reported parallelization uses OpenMP on a quadcore CPU.Source: §5 · p. 9
6 Conclusion
The conclusion presents genetic programming as a way to combine simple change-detection algorithms and post-process their outputs. It reports that the preferred combination depends on whether maximum performance or a balance of performance and computational complexity is sought.
6 Conclusion
- Genetic programming selects and combines subsets of simple algorithms and applies operators to post-process their outputs.The approach is presented as a way to create a more robust change-detection algorithm.Source: §6 · p. 9
- IUTIS-2 combines several simple algorithms to achieve results comparable to more complex state-of-the-art algorithms while remaining computationally affordable for real-time applications.The conclusion highlights its parallelized version as particularly performant.Source: §6 · p. 10
- When maximum performance is the priority and computational complexity is disregarded, combining a few top-performing algorithms yields the best overall performance in IUTIS-3 and IUTIS-5.Source: §6 · p. 10