Source-linked AI summary
Max-Margin Object Detection
Davis E. King
TL;DR
Object detectors typically learn from only a subset of image windows and therefore may not optimize the final detection system. MMOD instead optimizes over all windows with a convex max-margin formulation, producing substantial gains across three datasets and enabling a rigid HOG filter to outperform a deformable part model on FDDB.
Problem
Training on subsampled windows optimizes classifier accuracy as a proxy, rather than the final detector’s missed detections and false alarms.
Method
MMOD learns detector parameters by optimizing over all windows in a convex max-margin formulation, with an efficient optimization algorithm.
Results
MMOD produced substantial improvements across three public datasets, including a rigid HOG filter that beat a state-of-the-art deformable part model on FDDB.
Takeaways & Limitations
On FDDB, MMOD efficiently used all 300 million sliding-window positions and accounted for partial overlaps and non-maximum suppression during training.
Takeaways & Limitations
The method currently uses a linear window scoring function; extending it to more-complex scoring functions is left for future research.
Abstract
from arXiv · showhide
Most object detection methods operate by applying a binary classifier to sub-windows of an image, followed by a non-maximum suppression step where detections on overlapping sub-windows are removed. Since the number of possible sub-windows in even moderately sized image datasets is extremely large, the classifier is typically learned from only a subset of the windows. This avoids the computational difficulty of dealing with the entire set of sub-windows, however, as we will show in this paper, it leads to sub-optimal detector performance. In particular, the main contribution of this paper is the introduction of a new method, Max-Margin Object Detection (MMOD), for learning to detect objects in images. This method does not perform any sub-sampling, but instead optimizes over all sub-windows. MMOD can be used to improve any object detection method which is linear in the learned parameters, such as HOG or bag-of-visual-word models. Using this approach we show substantial performance gains on three publicly available datasets. Strikingly, we show that a single rigid HOG filter can outperform a state-of-the-art deformable part model on the Face Detection Data Set and Benchmark when the HOG filter is learned via MMOD.
1. Introduction
Object detection commonly trains a binary classifier on selected positive and negative windows, then adds false alarms through hard-negative retraining. This procedure underuses available windows and optimizes classifier accuracy rather than the final detector, motivating MMOD’s all-window, detector-level optimization.
- Standard detection trains a binary classifier on selected positive and negative image windows, then iteratively adds false alarms found on target-free images.
- Subsampling wastes training data and leaves partially overlapping windows difficult to label as either false alarms or true detections.
- The conventional objective uses classifier accuracy on subsampled windows as a proxy instead of optimizing the complete detection system.
- MMOD optimizes over all windows for missed detections and false alarms, using a convex formulation with an algorithm that finds globally optimal parameters.
- MMOD substantially improves learned-detector accuracy on three public datasets, including a case where one rigid HOG filter outperforms a state-of-the-art deformable part model.
2. Related Work
Related work largely improves feature representations while retaining binary classification on positive and negative windows. The closest prior approach trains on all window locations but assumes each image contains at most one object, unlike the present general multi-object setting.
- HOG and later object detectors primarily improve feature representations, while still training binary classifiers on positive and negative image windows.
- Blaschko and Lampert’s structured output regression is the closest related approach because it uses a structural support vector machine trained on all window locations.
- That prior training procedure assumes an image contains either zero or one object, whereas this work addresses images containing any number of objects.
- The detection pipeline uses a window scoring function, retains positive-scoring rectangles, sorts them by score, and greedily selects non-overlapping detections.
3. Problem Definition
The detector searches for a highest-scoring set of mutually non-overlapping windows under a specified overlap rule. Because exact optimization is infeasible, the usual greedy procedure can be suboptimal, motivating a learning objective aligned with final detector outputs.
- A valid labeling is a subset of scanned rectangles whose pairwise overlap ratio is below 0.5 under the paper’s non-overlap definition.
- The detector seeks the highest-scoring set of sliding-window positions subject to mutual non-overlap.
- Greedy peak sorting selects detections by descending score while rejecting windows that overlap already selected rectangles.
- Exact solution of the detector objective is computationally infeasible, so the greedy algorithm can return a suboptimal result.
- In the three-window example, the optimal detector selects the two outside rectangles for total score 12, while the greedy detector selects the center rectangle for total score 7.
4. Max-Margin Object Detection
MMOD learns a linear window-scoring detector by maximizing margins over structured object-detection outputs, using a convex objective optimized with cutting planes and loss-augmented detection.
- MMOD uses a linear scoring function whose feature vector is extracted from each sliding-window location and whose parameters are learned jointly.
- The objective requires correct training labelings to score above incorrect labelings with a large margin, while weighting missed detections and false alarms through Lmiss and Lfa.
- The soft-margin MMOD formulation handles noisy, nonseparable, or outlier-containing data, with C controlling the fit-versus-margin trade-off.
- The empirical-risk term is convex, and each slack variable upper-bounds the loss incurred by its corresponding training example.
- Cutting planes progressively tighten a tangent-plane lower bound on the convex objective until the optimizer approaches the global optimum within ε.
- Each cutting-plane subproblem is solved as a quadratic program, while loss-augmented detection greedily searches for rectangles maximizing total score plus loss under the detector's procedure.
- The loss-augmented detection algorithm may fail to find the optimal labeling because it is greedy, but it mirrors the greedy detection method used at test time.
5. Experimental Results
MMOD was evaluated on three detection datasets using shared feature extraction settings for the cows and INRIA experiments, while FDDB used a HOG sliding-window classifier. Across these experiments, MMOD achieved strong detection performance, including improvements over prior methods and a rigid-filter comparison with a deformable model.
- MMOD was evaluated on TU Darmstadt cows, INRIA pedestrians, and FDDB using two feature representations.
- 5.1. TU Darmstadt Cows: Perfect detection with no false alarms was obtained on TU Darmstadt cows, compared with 98.2% accuracy at equal error rate for the best previous result.
- 5.2. INRIA Pedestrians: MMOD scanned approximately 930,000 windows per negative INRIA testing image while optimizing the detector over the sliding-window search space.
- 5.2. INRIA Pedestrians: The INRIA detection tradeoff curve showed superior performance despite using a basic bag-of-visual-word feature set instead of more recent feature representations.
- 5.3. FDDB: On FDDB, a single HOG filter learned via MMOD substantially outperformed traditional HOG and Viola–Jones methods and slightly exceeded a deformable part model.
6. Conclusion
The paper concludes that MMOD is a convex-optimization method for learning object detectors and that it produced substantial improvements across three datasets. Its strongest reported result is that a single rigid HOG filter learned with MMOD beat a state-of-the-art deformable part model, while the current method remains limited to linear window scoring.
- MMOD uses convex optimization and an efficient solution algorithm to learn object detectors across the INRIA, TU Darmstadt cows, and FDDB datasets.
- MMOD produced substantial improvements on all three evaluated datasets using two feature representations.
- A single rigid HOG filter learned via MMOD beat a state-of-the-art deformable part model on FDDB.
- The reported gains are attributed to using all training windows and optimizing detector accuracy with partially overlapping windows and non-maximum suppression included.
- The current method uses a linear window scoring function, with future work targeting more-complex scoring functions.