Understanding the Ability of Deep Neural Networks to Count Connected Components in Images

A deep-neural network pixel-wise counter was trained on binary images containing numbers of individual object pixels (i.e., pixel with value 1 is the object and 0 is background) spanning the entire range from 1000 to 3000 and tested on images that included the range from 3 to 10000 pixels. The experiment was repeated 10 times, yielding an overall error rate of (0.094 $\pm$ 0.002)%. In addition, we interpreted this pixel-wise counting ability by comparing different structures and analyzing weights and data flow within neural networks. Understanding this ability is an important step toward explaining and trusting object counting with deep learning.

Unfortunately, our experiments show that DNNs cannot generally count connected components in the image. Then, we tentatively provided three explanations based on learnability to understand why DNNs cannot generally count objects but successfully work for many specific counting tasks. We consider that, for machine learning (ML) models (like DNNs), a learnable problem should have the three characteristics (ML-learnable characteristics):

1. 1.

   It has a finite domain.

2. 2.

   It has enough number of data to show its pattern (enough data).

3. 3.

   Its subsets have the similar pattern as the whole set (pattern consistency).

The first two characteristics are simple and well-known but the third one is profound and needs further studies and discussions.

In summary, around using DNNs to count connected components in image, we have done several experiments and tried to provide some insights into the DNN and data for machine learning. This study may raise other questions and discover the starting points of ways for future researchers to make progress in the understanding of deep learning.

In deep learning, previous studies have successfully applied DNNs to object counting [1, 2, 3, 4, 5]. For the leaf counting challenge [6], leaves are firstly segmented by the SegNet [7] to obtain a binary leaf image and then the number of leaves is counted by using the breadth first search (BFS) or regression. It is counting by segmentation. Object counting is also done by recognition and classification. Object counting tasks can be considered as recognition problems. Oñoro-Rubio & López-Sastre (2016) [8] applied the CNN model to transform an image with vehicles to a density map. Then, the number of vehicles is predicted by a regression model from the density (heat) map. The work of Zhang et al. (2015) [9] seems similar to ours but this work only classifies images with objects into 5 categories: 0 (no clear object), 1, 2, 3, and 4+ (four and more objects). The main drawback of counting through classification is that the countable number of objects is known and limited.

In general, the goal of automated object counting is to count any number of objects (more than the numbers for training) directly from images. The direction means the input of model is an image and its output is the object number. In this study, we examine a simplified situation; the questions are: can DNNs count the general connected components in images? Why or why not? The generalization means the connected components could be in any shapes, sizes, and positions. Nasr et al. (2019) [10] shows that in the final layer of a trained (on ImageNet) CNN model, 9.6% (3,601/37,632) units can react to the number of objects (called numerosity-selective units). By using the responses of these units can build tuning curves to estimate the number of connected components (range from 1 to 30) in images. The problem of this paper is that the numerosity-selective units are selected and tuned by other methods and experiments; the processes are manually interfered and thus the counting is neither direct nor automatic.

We suppose that $X$ is the vector of a flattened binary image whose labels for background pixels are “0” and objects are “1”:

The simplest way to obtain the number of objects is to multiply a one vector $\mathbb{1}$ by the $X$:

Hence, if the $M_{0}$ model has learned to count, we have:

Where A is the weights matrix and B is the bias of $M_{0}$ model. Obviously, one correct solution is $A=\mathbb{1}$ and $B=0$. If all weights in $A$ are equal to $z_{0}$, the loss of training $M_{0}$ is $N(1-z_{0})$. Therefore, the destination of training $M_{0}$ is:

For $M_{1}$ learning to count:

Where $r(\cdot)$ is ReLU activation function: $r(x)=\max\{0,x\}$. We suppose that $B_{1}=0$ and all weights in $A_{1}$ and $A_{2}$ are equal to $z_{1}\ (z_{1}>0)$, then:

If $X$ contains $k$ objects, then $\sum x_{i}=k$:

The loss of training $M_{1}$ is $(1-Nz_{1}^{2})$. Therefore, the destination of training $M_{1}$ is $(z_{1}>0)$:

Since the total number of pixels $N$ is a very large value, the destination of training $M_{1}$ is $z_{1}\approx 0$. From Eq. 1, the destination of training $M_{0}$ is $z_{1}=1$. Whereas the fact that all weights $(z_{0},\ z_{1})$ are initialized near 0, the destinations of $z_{1}$ for training $M_{1}$ are much closer to their initialization than that of $z_{0}$ for training $M_{0}$. Thus, the training process of $M_{1}$ is much faster then that of $M_{0}$ (see the phenomenon in Fig. 2). Eq. 1 and 2 provide answers to the two questions stated before.

We think all patterns of problems could be categorized in two types: generatable and checkable. The generatable patterns mean data with that patterns could be generated by certain rules, such as even numbers are generated by multiplying 2 and integers. And the checkable patterns mean data could be checked/verified having that patterns, but we cannot find specific rules to create such data such as the prime numbers.

For data with generatable patterns, if the generative rules have been learned (like the rule-based machine learning [13, 14]), we consider that the patterns have been learned, even if the domain is infinite. Otherwise, for the problem has infinite domain, if the ML model cannot learn its generative rules or its patterns are not generatable, this problem is not ML-learnable.

Finite/infinite domain of the problem and finite/infinite amount of data in the problem are two different things. If a problem has finite number of data, its domain must be finite; thus, it is ML-learnable because a ML model can memorize all its data, like the k-nearest neighbors (KNN) or DNNs. On the other hand, if a problem has infinite number of data, its domain could be either finite or infinite. The problem having finite domain is ML-learnable because a non-parametric ML model (e.g., Gaussian mixtures) can learn to cover its domain. Hence, ML-learnability is related to the domain of the problem instead of the amount of data.

In summary, having finite domain is necessary to a ML-learnable problem. Although infinite domain with generatable patterns is also ML-learnable in theory, it is difficult to train a rule-based ML model to learn these patterns, and many ML models cannot learn generative rules. For example, we fitted $y=x^{2}$ by a FCNN. The set of $(x,y)$ has infinite domain and its pattern is generatable. As shown in Fig. 8, the FCNN model does not learn the pattern because the model only predicts correctly in the same range of training.

The general tasks of counting connected components have infinite domain problems because the image sizes (inputs) and the number of components (outputs) could be arbitrary. And the pattern of such problems is not generatable; there are no specific rules to generate components because their shapes, sizes and positions are arbitrary too. Therefore, general counting connected components is not ML-learnable.

Even a problem has finite domain, we need to have enough data to present its patterns. If the patterns cannot be well presented by a dataset, the ML model cannot learn the correct patterns from the dataset either. Fig. 9 shows an example that the shortage of data could fail to present the patterns.

By the well-known Curse of Dimensionality, the required amount of data to present patterns will increase exponentially in higher dimension space. For 256x256 images, its dimensionality is 65,536. Hence, the training set may not have enough data to train an effective ML model for general counting connected components.

For problems having finite domain, there is another condition that we can never obtain enough data to present its patterns; that is the problem includes infinite number of data and any finite subset does not have the similar pattern as the whole set. In other words, we obviously cannot train ML models on infinite number of data (the whole set) but any finite subset cannot grasp the real pattern of the problem. For example, the infinite random two-class data in $(0,1)^{2}$. This dataset can have infinite number of data and the decision boundaries of any two subsets of it are different (Fig. 10). Hence, the infinite random two-class data set is not ML-learnable. Some problems have finite domain and infinite number of data are ML-learnable, such as the Gaussian mixtures models because we could find a subset to present their Gaussian distributions.

For some problems, even they have finite number of data, no subset can describe their patterns unless to use the whole set. For example, the $n$-XOR problems, which to fit $y=x_{1}\oplus x_{2}\oplus\cdots\oplus x_{n};\;x_{i}\in\{0,1\}$. It has finite ($2^{n}$) data and to train models should use all of them.

We trained a FCNN to fit the 6-XOR problem. The training process in Fig. 11 show that if the training batch is the whole set (batch size $=2^{6}$), the FCNN model could learn the pattern fast and reach at 100% training accuracy. But if the training batch is a subset (batch size $=2^{6}/4$), the training accuracy increases slowly, oscillates frequently, and seems hard to reach at 100%. Thus, $n$-XOR problems are very difficult to train FCNN models by subsets.

In summary, whatever problems have infinite or finite number of data, if any finite subset does not have the similar pattern as the whole set (no pattern consistency), the problems are not ML-learnable.

By examining the cases with no pattern consistency, we could find two key features: 1) the data in dataset are distributed in high density; 2) the mixture of different-class data is complex, which means different-class data are very close to each other and each datum is surrounded by many different-class data. We suppose that the two features are evidence of problems having no pattern consistency.

Finally, we consider the problems of counting connected components have no pattern consistency because 1) the components could be any number, shapes, sizes, and positions in an image; thus, the dataset is high dense; 2) images with different numbers of connected components can be very similar to each other (close to each other in data space). Fig. 12 shows that one-pixel difference can change the number of connected components. Thus, the mixture of data is complex. Therefore, general counting connected components is not ML-learnable because of no pattern consistency.

To show DNNs cannot generally count connected components in images, more experiments in controlled conditions would strengthen this conclusion. And we could provide explanations to these results, such as to answer what leads the counting to fail.

We will refine the theory about pattern consistency to quantitatively define the similar-pattern subsets and find metrics to examine if a problem has such characteristic or not.

In addition, we will try to find the boundary between countable and non-countable problems for DNNs; that is, the boundary between specific and general counting problems in terms of the three ML-learnable characteristics or other applicable theories.