Shape Bandwidth and the Class-Agnostic Counting Gap

Class-agnostic counters count objects of a category they never saw in training. They are given an image and one to three example boxes, and they must find every other instance that looks like the examples. These models are much better on familiar categories than on new ones, and nobody has a principled account of which new categories will be hard. This note proposes one testable account. Every object outline that radiates from a center can be described by a radius as a function of angle, and that function has a frequency content we call its angular bandwidth. Round blobs have low bandwidth. Spiky, thin, or indented objects have high bandwidth. A counter trained by gradient descent on base categories can only transfer shape knowledge in the frequency band those categories occupied. Novel categories whose outlines carry energy outside that band should fail in a predictable way, whatever their appearance.

The argument rests on a result from learning theory. Gradient descent is a statistical-query learner, meaning it touches data only through averages. Such learners provably cannot pick out targets that are nearly uncorrelated with everything they have already measured. We make that argument concrete for star-convex shapes, which are shapes where a straight line from one interior point reaches every boundary point. We then measure it on the standard few-shot counting benchmark, FSC-147, and test whether a counter that explicitly carries the exemplar's shape spectrum closes the gap where the theory says it should, and only there. If the account holds, it explains part of the generalization gap and says what the exemplar must communicate. If it fails, the failure is informative too: it would show that shape plays little role in why counting breaks on new categories.

Core Claim

Represent an instance by its polar radius function around an interior pole,

$$r(\theta) = a_0 + \sum_{1 \le |k| \le L} a_k e^{ik\theta},$$

where $\theta$ is the angle, $a_k$ are Fourier coefficients, and $L$ is the angular bandwidth. For a class $c$, define its spectral mismatch against the base training classes as

$$M_c = \mathbb{E}_{\text{instances of } c}\left[\frac{\sum_{|k| > L_{\text{base}}} |a_k|^2}{\sum_{k \ne 0} |a_k|^2}\right],$$

where $L_{\text{base}}$ is the bandwidth that holds most of the non-constant radial energy across base-class instances. The claim has three parts. First, a theoretical statement: learning planar star-convex sets of bandwidth $L$ to accuracy $\epsilon$ with statistical queries costs a number of queries and a tolerance that scale polynomially in $L$ and $1/\epsilon$. The lower bound comes from a family of radius perturbations at distinct frequencies that are pairwise nearly uncorrelated, so queries fitted to frequencies up to $L_{\text{base}}$ carry almost no information about the higher ones. Second, an empirical prediction: on FSC-147 novel classes, $M_c$ predicts per-class counting error for existing counters after controlling for appearance distance to the nearest base class, object size, aspect ratio, and count. Third, a design consequence: a counter that reads a radial spectrum from the exemplar and emits star-convex instances should cut error specifically on high-$M_c$ classes.

We state the limits of the theory upfront. In the plane, statistical-query complexity is polynomial, not exponential. The theory therefore predicts a graded, bandwidth-indexed cost, not the sharp walls known for high-dimensional problems. Its value here is the correlational structure it gives, which tells us which novel classes should be hard. Uniform-convergence bounds give no such signal.

Relation to Prior Work

The theoretical side builds on three pieces of work. Feldman's open-problem note on sparse halfspaces establishes that statistical-query complexity is governed by how many nearly uncorrelated concepts a class contains. We reuse that dimension-counting argument. The near-optimal lower bounds for intersections of halfspaces prove an $n^{\Omega(\log k)}$ bound for convex polytopes under Gaussian inputs by showing that a cube's indicator is nearly uncorrelated with low-degree polynomials. That analysis covers intersections of halfspaces in high dimension. Our analysis covers radially defined, possibly non-convex sets in the image plane, where the relevant basis is angular Fourier modes rather than Hermite polynomials. The result that gradient descent fails to learn high-frequency functions motivates the frequency framing. We carry its intuition from functions on the line to object boundaries. None of these papers touches vision, exemplars, or counting.

On the counting side, FamNet introduced FSC-147 and test-time adaptation. BMNet+ and SAFECount improved the similarity function between exemplar and image, and CounTR added masked pretraining and mosaic augmentation. All of these treat the gap as a problem of appearance matching. LOCA is the closest prior work: it separates shape queries from appearance queries. Its shape query, however, comes only from box height and width, and the authors note that finer boundary information is discarded. We replace that box-derived shape with a radial spectrum and ask whether the missing information is precisely the high-frequency part. PseCo produces instance masks by prompting the Segment Anything Model with predicted centers. It resolves conflicting part-level and whole-object masks with CLIP-driven distillation, but has no explicit shape model and no account of which classes fail.

The geometric side supplies both the method and its constraints. TextRay regresses polar contours with Chebyshev coefficients and documents failure on U-shaped text, where a ray crosses the boundary more than once. SplineDist shows that spline contours match many-ray star polygons with fewer parameters. K-convexity shape priors represent non-convex objects as overlapping unions of star-convex parts and remain tractable to optimize. We use the overlapping-union idea for concave classes and treat multiple ray crossings as a second, separately measured axis of mismatch.

Research Program

The theory component proves matching upper and lower statistical-query bounds for learning star-convex sets whose radius has bandwidth $L$ and is bounded between two positive radii, under the uniform measure on a disk. The upper bound estimates each Fourier coefficient of the radius through a small number of queries. The lower bound builds a family of sets $r_0 + \delta\cos(k\theta + \varphi)$ at distinct frequencies and phases, whose indicator differences are nearly orthogonal. We then extend the result to unions of $k$ overlapping star-convex parts and give the dependence on $kL$. The corollary we need is transfer-specific. A learner whose queries were shaped by base classes with bandwidth $L_{\text{base}}$ has expected information about frequencies above $L_{\text{base}}$ that decays with the correlation between frequencies, which is where $M_c$ comes from.

The measurement component makes FSC-147 shape-aware. FSC-147 gives dots and three exemplar boxes but no masks. We will generate instance pseudo-masks by prompting the Segment Anything Model with the ground-truth dots, using the PseCo codebase. We will hand-check a stratified sample of instances to estimate mask error. For each instance we fit a radius function and record two quantities. The first is its spectrum. The second is its star-convexity violation, defined as the mask area outside the best star-convex fit, which captures the multiple-crossing failure that TextRay reports. From these we compute $M_c$ and a violation score for every class.

The method component is a star-convex counter head that runs on a shared backbone. From each exemplar's pseudo-mask it computes the radial Fourier coefficients, and these replace LOCA's box-derived shape query. At every location the head predicts a center score and the radial coefficients up to a chosen bandwidth. Classes with a high violation score get a $k$-part overlapping union head. The count is the number of instances that survive non-maximum suppression. Because each counted object has an outline, every count can be checked instance by instance.

Baselines

The naive reference point has two parts. The first predicts the mean training count. The second, more useful one, is the same backbone and counting head with no shape conditioning at all. Comparing the second against the full model isolates what shape information contributes.

The strongest existing method on FSC-147 few-shot counting in this file is CounTR, which reports a test mean absolute error (MAE) of 11.95 in CounTR. It is the competitor to beat on aggregate count accuracy. PseCo reports 13.05 few-shot and 16.58 zero-shot MAE in PseCo. It is the strongest competitor that also outputs instances, so it is the right comparison for instance-level claims. LOCA reports a few-shot test root-mean-squared error (RMSE) of 56.97 and a CARPK MAE of 9.97 in LOCA. It is the most direct competitor because it already conditions on exemplar shape, only coarsely. The file also attributes a 9.97 CARPK figure to SAFECount in one place, so we will re-run both rather than quote either. BMNet+ (14.62 MAE) and SAFECount (14.32 MAE) are included for the diagnostic regression.

All models are re-run with public or re-implemented code. They share the same backbone family where the architecture allows it, the same FSC-147 splits and exemplars, the same training-image budget, and an equal hyperparameter search budget. Results are averaged over three seeds.

The key ablation keeps our head fixed and varies only its shape input. The three variants use box height and width (LOCA's information), a generic mask-pooled embedding of the exemplar, and the radial spectrum truncated at $L_{\text{base}}$. The truncated variant should reproduce the gap on high-$M_c$ classes if the theory is right.

Beating the baselines means two things. First, an overall MAE within the seed variance of CounTR or better. Second, a statistically reliable error reduction on the top tercile of $M_c$ classes that is clearly larger than the reduction on the bottom tercile. A uniform improvement would not support the claim.

Why not just…?

Why not just prompt the Segment Anything Model and count the masks? PseCo shows that raw point prompts return conflicting part and whole masks and need a trained CLIP distillation stage to resolve. PseCo's zero-shot MAE of 16.58 is also worse than the best density counters. The Segment Anything Model is still a real threat on high-bandwidth classes, because it has no bandwidth limit. Our stratified analysis will report PseCo's error against $M_c$. If PseCo shows no dependence on $M_c$ while density counters do, that supports the theory's mechanism, a bandwidth ceiling inherited from base classes. It would also mean our head's advantage has to come from efficiency and from verifying individual instances, not from accuracy.

Why not just use density-map regression like CounTR, which already has the best MAE? For raw accuracy, it may be enough. The question here is different: which novel classes fail, and why. Density maps are a useful test of that, because they never represent shape explicitly and should still show the $M_c$ dependence. If CounTR's per-class error is flat in $M_c$ after controls, our main hypothesis is wrong for the strongest model. We will report that outcome as a negative result.

Why not just give LOCA a richer, generic shape embedding from the exemplar mask? This is the most serious alternative. If a learned mask embedding closes the high-$M_c$ gap as well as the explicit radial spectrum, then the star-convex parameterization adds nothing to the method. In that case only the diagnostic and the theory survive. The ablation described under Baselines tests exactly this, and we commit to reporting whichever way it falls.

Why not just use VC or Rademacher bounds? Those bounds describe how many samples suffice for any learner. They do not predict which novel classes a gradient-trained model will miss, which depends on how correlated the new targets are with what training already measured. The statistical-query view gives a per-class prediction, $M_c$, that can be falsified directly.

Why not just blame object size or crowding? High-bandwidth outlines often belong to small or crowded objects, and error on FSC-147 is known to rise with density. We will regress per-image error on $M_c$ with log count, instance area, aspect ratio, and appearance distance as covariates and class as a random effect. We will also run the synthetic experiment below, where size and count are held fixed by construction.

Proposed Experiments

The first experiment is a synthetic check of the theory. We render images of random star-convex shapes with controlled bandwidth, size, and count on textured backgrounds. We train counters on shapes with bandwidth up to $L_{\text{base}}$ and test on held-out bandwidths. The prediction is that error rises as test energy moves above $L_{\text{base}}$, in the graded way the bound predicts, while appearance and size are held fixed. The same setup, with deliberately concave shapes, tests whether the $k$-part union head removes the failure that the violation score predicts.

The second experiment is the FSC-147 diagnostic. We fit the regression described above for FamNet, BMNet+, SAFECount, CounTR, LOCA, and PseCo on novel test classes. FSC-147 splits categories between train and test, so we also hold out images from training categories to measure the seen-class reference. We found no reported seen-versus-unseen gap on Lacuna for FSC-147, so this gap is measured here, not quoted. The decisive check is whether $M_c$ keeps a significant partial effect after the covariates, and whether that effect replicates across at least four of the six models.

The third experiment evaluates the method on FSC-147 with MAE and RMSE, reported overall and by $M_c$ tercile. We also test zero-shot transfer to CARPK, where near-rectangular cars have low bandwidth, and to BBBC038 nuclei, where the method should show no special gain. The Data Science Bowl reports 0.712 F1 at IoU 0.7 for its top fully supervised model in Caicedo et al.; we use it as a ceiling for instance quality on nuclei, not as a comparison target. For completeness, SCUT-CTW1500 serves as a stress test for multiple ray crossings, with TextRay's class-specific 81.56% F-measure as an upper reference.

The proposal fails if either of two outcomes occurs: $M_c$ carries no effect once size and appearance are controlled, or the generic mask embedding matches the radial spectrum on high-$M_c$ classes.