From Open Set to Closed Set: Counting Objects by Spatial Divide-and-Conquer

Haipeng Xiong; Hao Lu; Chengxin Liu; Liang Liu; Zhiguo Cao; Chunhua Shen

Source-linked AI summary

From Open Set to Closed Set: Counting Objects by Spatial Divide-and-Conquer

Haipeng Xiong, Hao Lu, Chengxin Liu, Liang Liu, Zhiguo Cao, Chunhua Shen

arXiv:1908.06473v1Aug 15, 2019cs.CV

TL;DR

Visual counting is open-set in theory but trained on finite observed counts, motivating a method that divides dense regions until closed-set sub-counts can be classified. S-DCNet implements this strategy on feature maps and is reported to generalize effectively across crowd, vehicle, and plant counting benchmarks.

Problem
Visual counting must handle counts beyond the finite closed set observed in datasets, while existing regression-based methods may struggle with unseen count ranges.
Method
S-DCNet transforms open-set counting into closed-set interval classification and applies spatial divide-and-conquer to dense regions using feature maps.
Results
S-DCNet effectively generalizes from closed training sets to open-set scenarios across standard crowd, vehicle, and plant counting evaluations.
Takeaways & Limitations
Spatial divide-and-conquer provides a way for counting models learned on finite closed sets to address open-set counting scenarios.
Takeaways & Limitations
Using CM for the final interval systematically biases counts in the last unbounded interval, although S-DC can mitigate this error.

Abstract

from arXiv · show

Visual counting, a task that predicts the number of objects from an image/video, is an open-set problem by nature, i.e., the number of population can vary in $[0,+\infty)$ in theory. However, the collected images and labeled count values are limited in reality, which means only a small closed set is observed. Existing methods typically model this task in a regression manner, while they are likely to suffer from an unseen scene with counts out of the scope of the closed set. In fact, counting is decomposable. A dense region can always be divided until sub-region counts are within the previously observed closed set. Inspired by this idea, we propose a simple but effective approach, Spatial Divide-and- Conquer Network (S-DCNet). S-DCNet only learns from a closed set but can generalize well to open-set scenarios via S-DC. S-DCNet is also efficient. To avoid repeatedly computing sub-region convolutional features, S-DC is executed on the feature map instead of on the input image. S-DCNet achieves the state-of-the-art performance on three crowd counting datasets (ShanghaiTech, UCF_CC_50 and UCF-QNRF), a vehicle counting dataset (TRANCOS) and a plant counting dataset (MTC). Compared to the previous best methods, S-DCNet brings a 20.2% relative improvement on the ShanghaiTech Part B, 20.9% on the UCF-QNRF, 22.5% on the TRANCOS and 15.1% on the MTC. Code has been made available at: https://github. com/xhp-hust-2018-2011/S-DCNet.

1. Introduction

Visual counting must generalize beyond the finite count patterns observed in datasets. S-DCNet addresses this by recursively dividing dense regions and performing divide-and-conquer on feature maps rather than repeatedly processing sub-images.

Problem: Visual counting is theoretically open-set, but datasets expose only a finite closed set and dense local patches are rare while their rMAE increases with density.The introduction frames whether regressors trained on observed counts can accurately predict counts outside that range.
Spatial divide-and-conquer: Spatial divide-and-conquer repeatedly splits dense images until every sub-region count falls within the learned closed set, then sums local predictions.For a closed set of 0–20, a single division may be insufficient, requiring further subdivision of a dense sub-region.
Efficiency: Dividing the input image directly can blur content and cause exponentially increasing computation and memory costs when feature maps are repeatedly extracted.The proposed implementation instead performs spatial division on high-resolution feature maps.
S-DCNet: S-DCNet learns from a closed set while generalizing to open-set scenarios through spatial divide-and-conquer.This is the paper’s central proposed transformation of open-set counting into a closed-set learning problem.
S-DCNet: The network combines a VGG16-based encoder, UNet-like decoder, shared counting predictor, interval classifier, and division decider.The predictor discretizes continuous counts into intervals, while the division decider selects sub-regions for division and merges counts across levels.

2. Related Work

Prior counting methods largely rely on local regression, including density-map and local-count regression, but remain limited by finite observed local patterns. S-DCNet instead combines count-interval classification with spatial divide-and-conquer.

Regression-based counting: Current CNN counting approaches mainly use local regression, divided into density-map regression and local-count regression.The related-work discussion also covers methods that reformulate regression as classification.
Density-map regression: Density-map methods represent object spatial distributions and commonly use multi-branch architectures to handle different object scales and contextual patterns.Examples include MCNN, Switching-CNN, SANet, CP-CNN, composition-loss methods, and CSRNet with dilated convolution.
Density-map regression: Existing deep counting networks target high-quality density maps, but density maps themselves remain an open-set representation.The paper notes that the open-set issue in density maps is discussed in the supplement.
Local-count regression: Local-count regression samples overlapping patches, predicts their counts, and normalizes and fuses redundant local estimates into a global count.Some methods also use spatial divisions, but they still regress open-set counts.
Classification reformulation: S-DCNet discretizes local counts into intervals and classifies them, following evidence that classification can improve optimization for continuous-variable estimation.The paper reports that classification with S-DC works better than direct regression in its experiments.

3. Spatial Divide-and-Conquer Network

S-DCNet converts local counts into intervals and combines multi-resolution predictions through spatial divide-and-conquer. Its shared classifier and division decider operate on decoded feature maps, with recursive merging producing the final image count.

3.1. From Quantity to Interval: S-DCNet discretizes local counts into intervals, classifies them, and recovers representative count values from the predicted intervals.The final interval uses its upper threshold as the recovered count, which introduces systematic error that S-DC can mitigate.
3.2. Single-Stage Spatial Divide-and-Conquer: The network combines a VGG16 encoder, UNet-like decoder, count-interval classifier, and division decider in a multi-task architecture.The classifier produces interval predictions, while the division decider generates masks used to select and merge local counts.
3.2. Single-Stage Spatial Divide-and-Conquer: A soft division mask determines whether each divided prediction replaces the upsampled previous count, with zero selecting the previous count and one selecting the sub-count.Counts are merged using averaging redistribution and elementwise masking.
3.3. Multi-Stage Spatial Divide-and-Conquer: Multi-stage S-DC recursively decodes and divides feature maps, merges successive division outputs, and integrates the final division map into the image count.VGG16 permits up to four division stages, although experiments report that two stages are adequate for satisfactory performance.
3.3. Multi-Stage Spatial Divide-and-Conquer: S-DCNet is trained with cross-entropy losses for classification outputs and an L1 loss for the final division output, summed in a multi-task objective.The final-output loss provides an implicit supervision signal for learning division masks.

4. Open Set or Closed Set? A Toy-Level Justification

A toy cell-counting experiment tests whether models trained on a closed count range generalize beyond it. Baselines degrade sharply outside the training range, whereas S-DCNet remains accurate on the open test range.

Dataset and Protocol: The toy dataset trains on 500 images whose 64 × 64 sub-regions contain 0–10 cells and tests on 500 images with counts from 0 to 20.The construction separates a closed training range from an open testing range.
Dataset and Protocol: The comparison includes a VGG16 regression baseline, a classification baseline without S-DC, and S-DCNet trained on the closed set.S-DCNet adapts to the open set through spatial divide-and-conquer.
Observations: Both regression and classification baselines perform well within the 0–10 closed range but show rapidly increasing error above 10.The result indicates that closed-set training does not by itself support accurate open-set counting.
Observations: S-DCNet achieves accurate predictions on the open test range, confirming the advantage of spatial divide-and-conquer in this experiment.The experiment evaluates mean absolute error against 64 × 64 sub-region counts and compares different S-DCNet stage counts.

5. Experiments on Real-World Datasets

Experiments evaluate S-DCNet through ablations and comparisons across crowd, vehicle, and plant counting datasets. The results show robustness to Cmax, benefits from S-DC and merging supervision, and strong performance across sparse, dense, global, and local counting settings.

Experimental setup: S-DCNet is evaluated with MAE and MSE on five public datasets, following implementation details and an ablation study on ShanghaiTech Part A.The experiments include interval-partition and data-augmentation settings, followed by comparisons with state-of-the-art methods.
Cmax robustness: S-DCNet remains robust across a wide range of Cmax values, while the classification baseline’s MAE increases rapidly as Cmax decreases.The maximum training count is not necessarily optimal; some smaller quantiles perform better, and Two-Linear Partition is slightly better than One-Linear Partition.
Effect of S-DC: S-DC significantly reduces counting errors, especially for dense 64 × 64 patches with local counts above 100.Direct single-branch classification without S-DC performs worse than regression, whereas two-stage S-DC fuses predictions across multiple resolutions.
Loss functions: Merging-loss supervision improves S-DCNet and helps the division decider learn reasonably good divisions, including cases where counts are not larger than Cmax.Without merging-loss supervision, multi-stage predictions are averaged because the division decider receives no training signal.
State-of-the-art comparisons: 5.5% relative improvement in ShanghaiTech Part A and 20.2% in Part B are reported over prior state-of-the-art methods.The results suggest that S-DCNet adapts to both highly congested and relatively sparse crowd scenes.
State-of-the-art comparisons: 20.9% boost in MAE on UCF-QNRF is achieved despite training with Cmax = 8.0, while TRANCOS improves GAME(3) by 22.5%.The UCF-QNRF result demonstrates generalization to very large counts, and the TRANCOS results show strong local as well as global predictions.

6. Conclusion

The paper reframes open-set counting as a closed-set problem through spatial divide-and-conquer, realizing this strategy in S-DCNet. Extensive benchmark evaluations support generalization to open-set scenarios, while adaptability to other architectures remains future work.

S-DC transforms open-set counting into a closed-set problem by exploiting the spatially decomposable nature of counting.The approach divides dense regions until local counts fall within the observed range.
S-DCNet effectively generalizes to open-set scenarios despite training on a closed set, according to toy experiments and extensive benchmark evaluations.
Testing S-DC's adaptability to other network architectures is identified as future work.

7. Supplementary Materials

The supplementary material discusses S-DCNet's motivation, related ideas, attention-based division, implementation choices, and qualitative results across five datasets. It emphasizes why local counts are spatially divisible, how division behaves, and where performance differences arise.

Further Discussions on S-DCNet: Density maps also form an open set because kernel sizes and nearby-object configurations produce diverse, sparsely observed density patterns.
Further Discussions on S-DCNet: Local counts, unlike density maps, are spatially divisible and therefore are used by S-DCNet for divide-and-conquer.
Further Discussions on S-DCNet: S-DCNet's implicit supervision lets its division decider learn when to divide, whereas the attention baseline focuses on the highest-resolution features without observable division.On ShanghaiTech Part A, the attention baseline obtains 64.1 MAE and 109.9 MSE, worse than S-DCNet.
Further Discussions on S-DCNet: Ground-truth local counts are generated by integrating density maps so cropped partial objects are handled during training, while point annotations remain used for validation errors.
Further Discussions on S-DCNet: Higher-stage C2 tends to perform worse because its loss emphasizes scarce high-density patches, which also helps explain why three- and four-stage models underperform the two-stage model.
Qualitative Results of S-DCNet: Qualitative results visualize original images, ground-truth count maps, and predicted count maps across ShanghaiTech, UCF CC 50, UCF-QNRF, TRANCOS, and MTC.Each local count-map element represents a 16×16 local area; zero-padding makes image dimensions multiples of 64.