Point-Query Quadtree for Crowd Counting, Localization, and More

To make point query scalable to sparse and dense scenes, we propose a decomposable structure, termed point-query quadtree. The quadtree follows a sparse to dense process, i.e., sparse querying points are first spanned across the image, and they are adaptively split into dense querying points in congested scenes for dense crowd prediction. A criterion is thus necessary to decide when to split sparse querying points. We consider that the splitting process should be determined by inspecting a local region, instead of relying on a single point. We therefore adopt a region-based quadtree splitter to construct the quadtree.

Quadtree Splitting. Fig. 3 illustrates the construction process of the point-query quadtree. Specifically, we first uniformly set sparse querying points on the image with a stride of $K$, which corresponds to the quadtree level $0$. A quadtree splitter is then applied to the encoded features, outputting a split map $M_{s}\in\mathbb{R}^{h^{\prime}\times w^{\prime}}$. Each element in $M_{s}$ represents the probability of a region being dense, where $1$ denotes dense regions and $0$ denotes sparse ones. The initial querying points in dense regions are split into dense querying points, forming the quadtree level $1$. This process repeats until the maximum splitting time $L$ is reached, which results in a $L+1$-layer quadtree. A multi-layer quadtree could be implemented by using multiple quadtree splitters to predict the split map of each layer. One may consider how many times the quadtree needs to split to tackle dense regions. In practice, we find that splitting once ($L$$=$$1$) is generally sufficient to deal with crowd estimation. Please refer to the supplementary for a detailed analysis.

In particular, the quadtree splitter consists of an average pooling layer and a $1\times 1$ convolution layer followed by a $\tt sigmoid$ function, so the computational cost is negligible. We show some examples of the output of the quadtree splitter in Fig. 4, in which red regions denote congested regions requiring quadtree splitting. We observe that the quadtree splitter can distinguish the congested regions. Note that the split map is binarized using a threshold of $0.5$.

Given a querying point with pixel location $(x,y)$, we need to represent it as a point query. Our intuition tells us that a point query should contain both semantic and localization information. To encode the semantics of point query, we repurpose the CNN feature. Technically, we interpolate the CNN features $\mathcal{F}$ to the original image size and sample the feature vector $\mathcal{F}_{x,y}\in\mathbb{R}^{1\times 1\times c}$. For position information, we adopt a fixed spatial positional embedding following [2]. The positional embedding and $\mathcal{F}_{x,y}$ are summed to form the point query representation.

The final step is how to predict crowd via point queries. Following the philosophy of dotted annotations (one dot per person), we represent each person by a unique point query. Specifically, we first pass the point-query quadtree through the transformer decoder to obtain the decoded representation. A prediction head is then applied to the decoded point queries, outputting a set of predicted persons $\mathcal{Q}=\{\mathbf{q}_{i}\}_{i=1}^{N}$. Note that $\mathbf{q}_{i}$ consists of the classification probability $c_{i}\in[0,1]$ and the normalized pixel location $\mathbf{p}_{i}=(x_{i}+\Delta x_{i},y_{i}+\Delta y_{i})$, where $(x_{i},y_{i})$ is the pixel location of a point query and $(\Delta x_{i},\Delta y_{i})$ is the predicted offsets. The prediction head is composed of MLP layers with ReLU activation.

We remark that the prediction head receives a varied number of queries for different images, as the queries are generated on-the-fly by the point-query quadtree. This ensures that sparse and dense point queries only operate on corresponding regions, avoiding unnecessary computation.

To encode crowd information of different scales, we adopt a progressive attention mechanism. The idea is that the transformer encoder first inspects a sufficiently large region and then focuses on a small one. Considering that the perspective change often occurs in crowd images, we compute attention within a rectangle window. More specifically, we design a horizontal window since it usually contains more people than the vertical one (Fig. 5).

The idea of the progressive encoder attention is illustrated in Fig. 6. Given an input image, we first compute attention within a relatively large rectangle window in the first few encoder layers. Each window is with a size of $s_{e}\times r_{e}s_{e}$, where $s_{e}$ is the height of the rectangle window, and $r_{e}$ is the aspect ratio. Then, a small rectangle window (with a size of $\frac{1}{2}s_{e}\times\frac{1}{2}r_{e}s_{e}$) is adopted to perform attention in the subsequent encoder layers. The encoder attention is computed as:

	$\displaystyle\hat{\mathbf{x}}^{l}$	$\displaystyle=\texttt{LN}(\texttt{RectWin-SA}(\mathbf{x}^{l-1})+\mathbf{x}^{l-1})\,,$
	$\displaystyle\mathbf{x}^{l}$	$\displaystyle=\texttt{LN}(\texttt{FFN}(\hat{\mathbf{x}}^{l})+\hat{\mathbf{x}}^{l})\,,$		(1)

where $\mathbf{x}^{l-1}$ and $\mathbf{x}^{l}$ are the output features of the encoder layer $l-1$ and the layer $l$, respectively. Note that $\mathbf{x}^{0}$ is initialized with $\mathcal{F}$. RectWin-SA, FFN, and LN denote rectangle window self-attention, feed-forward network, and layer normalization, respectively. Benefiting from the design of progressive rectangle window attention, we can achieve efficient computation with linear complexity, which is particularly helpful when processing high-resolution images. Detailed architecture of the encoder can be found in the supplementary.

The transformer decoder receives the point-query quadtree and encoded image features as input, outputting decoded point queries. It reasons crowd by modeling the relation between point queries under the guidance of image context. Intuitively, we decide whether a point query is a person based on its surrounding point queries and context. We therefore propose to compute decoder attention within local windows. Considering the hierarchy structure of quadtree, we also adopt progressive attention when decoding point queries.

Technically, the attention of sparse point queries is computed in a relatively large rectangle window (with a size of $\frac{1}{2}s_{e}\times\frac{1}{2}r_{e}s_{e}$), and the window size of dense point queries is reduced to $\frac{1}{4}s_{e}\times\frac{1}{4}r_{e}s_{e}$. In particular, the decoder attention is computed as:

	$\displaystyle\hat{\mathbf{z}}^{l}$	$\displaystyle=\texttt{LN}(\texttt{RectWin-SA}(\mathbf{z}^{l-1})+\mathbf{z}^{l-1})\,,$
	$\displaystyle\hat{\mathbf{z}}^{l}$	$\displaystyle=\texttt{LN}(\texttt{RectWin-CA}(\hat{\mathbf{z}}^{l},\mathbf{x}^{N})+\hat{\mathbf{z}}^{l})\,,$
	$\displaystyle\mathbf{z}^{l}$	$\displaystyle=\texttt{LN}(\texttt{FFN}(\hat{\mathbf{z}}^{l})+\hat{\mathbf{z}}^{l})\,,$		(2)

where $\mathbf{x}^{N}$ is the final output of the transformer encoder, $\mathbf{z}^{l-1}$ and $\mathbf{z}^{l}$ are the output features of the decoder layer $l-1$ and the layer $l$, respectively. Note that $\mathbf{z}^{0}$ is initialized with the representation of point queries. RectWin-SA and RectWin-CA denote the rectangle window self-attention and the rectangle window cross-attention, respectively.

The output of PET is a set of candidate persons $\mathcal{Q}=\{\mathbf{q}_{i}\}_{i=1}^{N}$. We optimize the network using bipartite matching [2] between the predictions and ground truth points $\mathcal{Y}={\{\mathbf{y}_{i}\}_{i=1}^{M}}$. The loss is computed as:

$$\ell_{pq}=\frac{1}{N}\sum_{i=1}^{N}\ell_{cls}(c_{i},c_{i}^{*})+\lambda_{1}\frac{1}{M}\sum_{i=1}^{M}\ell_{loc}(\mathbf{p}_{\sigma(i)},\mathbf{y}_{i})\,,$$

(3)

where $i$ is the index of a point query, $c_{i}$ is the predicted classification probability, $\lambda_{1}$ is a hyperparameter, and $\sigma(i)$ denotes the index of point query that is matched with the ground-truth point $\mathbf{y}_{i}$. $\sigma$ is obtained by bipartite matching [2]. The classification label $c_{i}^{*}$ equals to $1$ only if the point query is matched with a ground-truth point, and $0$ otherwise. For the classification loss $\ell_{cls}$ and localization loss $\ell_{loc}$, we employ cross entropy loss and smooth $\ell_{1}$ loss [7]. In addition, the quadtree splitter is supervised by:

$$\ell_{split}=\mathbbm{1}(\texttt{dense})(1-\max(M_{s}))+\min(M_{s})\,,$$

(4)

where ${M_{s}}$ is the split map, and $\mathbbm{1}(\texttt{dense})$ equals $1$ if the input image has dense regions, otherwise $0$. We consider an image has dense regions if its crowd density is high. Recall that each element in ${M_{s}}$ represents the probability of a region being dense. Eq. (4) functions as a minimum supervision for the quadtree splitter to discriminate dense and sparse regions. We retain the second term as sparse regions generally exist in an image. The final loss function is:

$$\ell_{total}=\ell_{pq}+\lambda_{2}\ell_{split}\,,$$

(5)

where $\lambda_{2}$ is a weight-balancing hyperparameter.

Dual Supervision. To prevent the loss from being diluted by samples with few people, we introduce dual supervision. Given a mini-batch of samples, we divide them into sparse and dense packs according to crowd density, and separately compute $\ell_{total}$ on these two packs. The losses are then summed for backpropagation.

During testing, the point-query quadtree is dynamically constructed based on the split map $M_{s}$. The final predictions are obtained by thresholding the classification probability of point queries, e.g., a threshold of $0.5$.

We evaluate our approach on four crowd counting datasets, including ShanghaiTech [42], UCF-QNRF [9], JHU-Crowd++ [28], and NWPU-Crowd [35]. Following previous work [12, 42], we use mean absolute error (MAE) and mean square error (MSE) as the evaluation metrics.

ShanghaiTech [42] has two subsets, including PartA ($300/182$ images for train/test) and PartB ($400/316$ images for train/test). UCF-QNRF [9] contains $1535$ images with diverse crowd density ($1201/334$ for train/test). JHU-Crowd++ [28] is a large-scale crowd counting dataset with $4372$ images ($2272$/$500$/$1600$ images for train/val/test), which covers various scenarios. NWPU-Crowd [35] is also a large-scale dataset, which contains $3109$, $500$, and $1500$ images for training, validation, and testing, respectively.

PET is optimized using the Adam optimizer [22] with the weight decay of $5\times 10^{-4}$. The initial learning rate of $10^{-5}$ is set for the CNN backbone (we use VGG16 [27]), and $10^{-4}$ for the transformer. The point-query quadtree has a maximum depth of $2$, and the initial stride of sparse point queries is set to $K=8$. The layer number of transformer encoder and decoder is $4$ and $2$, respectively. Note that our point-query quadtree shares the same decoder. We set window parameters as $s_{e}=16$ and $r_{e}=2$. For loss coefficients, we set $\lambda_{1}=5.0$ and $\lambda_{2}=0.1$ to balance the contribution of different terms.

Regarding data augmentation, we randomly crop $256\times 256$ patches from each image as training samples, and perform random scaling and random flipping. For datasets that contain high-resolution images, we resize the image and keep the original aspect ratio. The longer side of each image is constrained within $1536$, $2048$, and $2048$ pixels for UCF-QNRF, JHU-Crowd++, and NWPU-Crowd, respectively.

We compare PET with state-of-the-art methods on four datasets, in the context of fully-supervised crowd counting and localization.

Table 1 reports the crowding counting results on ShanghaiTech [42], UCF-QNRF [9], and JHU-Crowd++ [28]. Our method not only achieves state-of-the-art results but also outputs localization information. In particular, PET significantly outperforms existing methods on ShanghaiTech PartA, with an MAE of $49.34$. The good performance on UCF-QNRF and JHU-Crowd++ also supports the adaptation of PET to dense scenes, because these datasets contain images with extremely dense crowd.

For the NWPU-Crowd [35] dataset, the crowd counting results in Table 2(a) show that PET performs favorably against state-of-the-art methods. It is worth noticing that PET outperforms existing localization-based approaches by a considerable margin, as indicated in Table 2(b). This validates the localization accuracy of PET.

Learning with partial annotations [39] is a new problem setting in crowd counting, in which only a partial region of each image is annotated. It aims to reduce the annotation cost and leverages data captured under various scenes. PET is applicable to this task because it can infer unlabelled regions based on the annotated ones, owing to the design of the point query. In particular, we follow the setting of [39] and simply adopt a two-step training process. We first train PET with partial annotations, then we infer the annotations around annotated regions and retrain PET with a fusion of ground-truth points and inferred annotations. In contrast to [39], we do not require a specifically designed consistency criterion to constrain model training. Table 3 shows the quantitative results on the ShanghaiTech dataset. Despite the simplicity of our training process, our approach outperforms [39] by a large margin, especially on SH PartA. In addition, PET also performs favorably against fully-supervised methods. This validates the effectiveness of PET on limited data and also the universal property of point-query modeling.

Learning with noisy annotations [16, 32] is a recent emerging topic. Existing crowd counting benchmarks typically use a dot to represent a person. However, the noise may arise during the annotation process [32], leading to inaccurate head points. In this context, another interesting application of PET is point annotation refinement. In practice, we first train PET with original annotations and validate the quality of annotations by setting annotated points as queries. Fig. 7 shows some examples of the refined annotations. We observe that PET can distinguish ‘noisy’ annotations and calibrate these points to the center of the head. To further investigate whether the refined annotations can benefit counting performance, we retrain PET with them. Our results show that the MAE on SH PartA improves from $49.34$ to $48.52$. While the improvement seems marginal at first glance, we remark that this is because most annotations are reasonable in the dataset. However, the visualizations in Fig. 7 do imply the ability of PET for annotation refinement, which could make a difference in more challenging scenarios when accurate annotations are difficult to acquire.

Fig. 8 shows the outputs of the quadtree splitter during training. One can observe that the initial split map (epoch $1$) is meaningless. After a few training epochs, e.g., $10$ epochs, the quadtree splitter can output a reasonable split map. This suggests that Eq. (4) works well in supervising the quadtree splitter.

Here we verify the effectiveness of the quadtree structure. For comparison, we train PET using only sparse point queries or dense point queries. Table 4 reports the results. Although sparse point queries can achieve promising results on SH PartA, it is far from satisfactory on UCF-QNRF. In addition, the inferior results of dense point queries could be attributed to the ambiguity during bipartite matching, because a ground-truth point may correspond to several similar point queries when dealing with sparse regions. This impedes the model from discriminating valid points.

Comparatively, by adopting the point-query quadtree, we obtain notable improvements on both SH PartA ($\sim$4 MAE) and UCF-QNRF ($\sim$11 MAE). The quadtree structure ensures that sparse and dense regions can be processed by corresponding querying points, thus achieving better results.

To justify the effectiveness of the progressive rectangle window attention, we train with different configurations of PET as in Table 5. One can observe that: i) progressive attention works, which significantly outperforms its non-progressive counterpart; ii) applying rectangle window to the encoder and decoder achieves the best performance. We notice that replacing either encoder or decoder with square window deteriorates performance. The reason perhaps is that a rectangle window could capture more useful information about the crowd due to the perspective prior.

We also compare our attention with existing attention mechanisms. As shown in Table 6, while global attention and deformable attention obtain promising results, their performance fall behind our window attention. The inferior results of global attention could be attributed to the varied resolution of testing images, as the global-wise attention may not adapt well to arbitrary resolution. In addition, performing global attention can easily exceed the memory limit of the GPU when dealing with high-resolution images.

Table 7 compares the model parameters and inference time of different models. Our PET owns the fewest parameters, and operates at a similar speed to existing methods. Note that the computational bottleneck lies in the backbone, instead of the querying process.

Here we show what is learned by the transformer encoder and decoder. Fig. 9(a) illustrates the self-attention maps of the transformer encoder for some reference points. The encoder can capture similar crowd within a rectangle window, thus can encode valuable context information. Fig. 9(b) shows the decoder attention maps of two point queries. One can observe that higher attention value also occurs in similar crowd. Interestingly, the attention map of the encoder and decoder seems similar. This may attribute to the single-class nature of the crowd, i.e., the model only needs to distinguish human heads.