# Dilated-Scale-Aware Attention ConvNet for Multi-Class Object Counting

###### Abstract

Object counting aims to estimate the number of objects in images. The leading
counting approaches focus on single-category counting task and achieve
impressive performance. Note that there are multiple categories of objects in
real scenes. Multi-class object counting expands the scope of application of
object counting task. The multi-target detection task can achieve multi-class
object counting in some scenarios. However, it requires the dataset annotated
with bounding boxes. Compared with the point annotations in mainstream object
counting issues, the coordinate box-level annotations are more difficult to
obtain. In this paper, we propose a simple yet efficient counting network
based on point-level annotations. Specifically, we first change the
traditional output channel from one to the number of categories to achieve
multi-class counting. Since all categories of objects use the same feature
extractor in our proposed framework, their features will interfere mutually in
the shared feature space. We further design a multi-mask structure to suppress
harmful interaction among objects. Extensive experiments on the challenging
benchmarks illustrate that the proposed method achieves state-of-the-art
counting performance.

11footnotetext: Equal contribution.22footnotetext: Corresponding author.

Index Terms—  Multi-Class Object Counting, Point-Level Annotation, Dilated-
Scale-Aware Module, Category-Attention Module

##  1 Introduction

Object counting is a prevalent task in the computer vision community, playing
an essential role in a wide range of applications (e.g., crowd analysis, urban
management, and wildlife conservation). Most counting methods count the number
of a single class, such as crowd counting [1], cell counting [2], and vehicle
counting [3], which can be grouped as single-class object counting methods.
Specifically, the single-class object counting methods require re-training
when changing the category to be counted.

Fig. 1: Comparisons of the proposed method with regression-based and
detection-based object counting methods. (a) The detection-based methods rely
on box-level annotations, but obtaining the box-level annotations in dense
scenes is an expensive and labor-intensive process. (b) The mainstream
regression-based methods are able to obtain the total count of all categories,
but it’s difficult to distinguish the number of each category. (c) The
proposed method estimates density maps for each category without expensive
box-level annotations.

Few methods focus on counting multiple categories with a single model, and we
define the problem as multi-class object counting. Multi-class object counting
is more practical in real-world applications. For instance, it is necessary to
count the appeared persons and cars in an image to assess the degree of
traffic congestion during rush hour.

Detection-based methods [4, 5, 6] enable multi-class object counting tasks by
counting the number of bounding boxes in each category, as shown in Fig. 1(a).
However, the detection-based methods rely on bounding box annotations, which
is impractical due to annotating the bounding boxes of each instance for
training images can be a significant challenge in dense scenes. Thus, the
mainstream counting datasets only provide point-level annotations, causing the
detectors untrainable.

The regression-based methods [7, 8, 9, 3], which only rely on point-level
annotations, have achieved significant successes by adopting the density maps.
However, the widely used density map is obtained by overlaying a series of
Gaussian Blobs. It makes the category indistinguishable so that the current
regression-based counting methods hardly implement multi-class object
counting, shown in Fig. 1(b).

To solve the problems mentioned above, we propose the Dilated-Scale-Aware
Category-Attention ConvNet (DSACA) to achieve multi-class object counting,
just relying on point-level annotations. DSACA learns multiple density maps
for multi-class object counting instead of a single density map, as shown in
Fig. 1(c). Specifically, DSACA, adopting a VGG16 [10] as the backbone,
consists of two crucial modules named Dilated-Scale-Aware Module (DSAM) and
Category-Attention Module (CAM), respectively. DSAM fuses the stage$\\_3$,
stage$\\_4$, and stage$\\_5$ feature maps from the backbone as the input and
utilizes diverse dilated rates to capture the intra-class visual responses of
big objects and tiny objects simultaneously. Sharing the same backbone, the
density maps will interfere with each other, which inspires us to design the
CAM to provide high-quality class-isolated density maps. The main
contributions of our method are summarized as follows:

  1. 1.

To the best of our knowledge, this is the first attempt to implement the
multi-class object counting task based on the point-level annotations in the
published literature.

  2. 2.

We propose a novel multi-class object counting method named DSACA consisting
of DSAM and CAM. The DSAM effectively captures the multi-scale information in
the intra-class scene, and the CAM shows strong adaptability to resist inter-
class interference among density maps.

  3. 3.

Extensive experiments demonstrate that our approach achieves state-of-the-art
performance on two challenging datasets.

Fig. 2: The pipeline of our method. The proposed approach fuse multi-scale
features via Dilated-Scale-Aware Module and suppress harmful inter-class
responses via Category-Attention Module.

##  2 Related works

The mainstream object counting methods can be categorized into detection-based
methods and regression-based methods.

###  2.1 Detection-based methods

Early traditional methods capture the handcrafted features (e.g., Haar[11] and
HOG[12]) to discriminate the person or non-person. These traditional methods
achieve limited performance due to heavy occlusions, scale variations, and
perspective distortions. Recently, the detection-based methods [4, 13, 5, 6]
usually utilize deep object detectors to locate each instance since the
advances of deep learning. Specifically, the pioneer RCNN [14] extracts region
proposals from an image and utilizes a convolutional neural network to
classify each region of interest (ROI) independently. SSD [5] is a one-stage
detector, which introduces the multi-reference and multi-resolution detection
fusion techniques. These deep-learning-based detectors rely on bounding-boxes
annotations, but obtaining bounding-boxes annotations is an expensive and
laborious process in the dense scenes.

###  2.2 Regression-based methods

Recently, various regression-based object counting methods [15, 9, 7, 16]
regress a density map through different techniques such as multi-scale network
[7, 17], attention mechanism [18, 16, 19], and perspective information [20,
21, 8], achieving remarkable progress. Specifically, Jiang et al. [17]
introduce a novel Trellis style encoder-decoder, which effectively fuse multi-
scale feature maps in the encoder. Xu et al. [7] propose the Learning to Scale
Module (L2SM) to automatically scale different region into similar densities,
reducing the pattern shift. Zhang et al. [19] propose the Attentional Neural
Field (ANF), which combines the conditional random ﬁelds with non-local
attention mechanisms to capture multi-scale features and long-range
dependencies. Yang et al. [8] propose a reverse perspective network, which is
designed to diminish the scale variations in an unsupervised way. Liu et al.
[21] utilize a auxiliary branch to integrate perspective maps into the density
maps.

Regression-based methods usually adopt MSE loss as their loss function.
However, only use the MSE loss function will cause some problems, such as blur
eﬀect, neglecting the local consistency, and losing position information.
Therefore, designing an appropriate loss function is also an essential
researching direction in the training stage, which can promote the object
counting ability. BL [15] regards the density map as a probability map,
computing the probability of each pixel. SPANet [22] proposes Maximum Excess
over Pixels (MEP) loss by ﬁnding the pixel-level subregion with the highest
discrepancy with ground truth.

In general, these regression-based methods only focus on single class object
counting (e.g., crowd counting), which limits the applications in the real-
world.

##  3 Proposed method

The overview pipeline of our method is shown in Fig. 2. The proposed method
mainly contains two crucial components: the Dilated-Scale-Aware Module (DSAM)
and Category-Attention Module (CAM). We utilize the pre-trained VGG-16 as the
backbone and discard the pooling layer between the stage$\\_4$ and stage$\\_5$
to maintain the spatial size, which follows previous works [18, 8, 7]. The
backend utilizes $3\times 3$ convolutional layers and a $1\times 1$ layer to
generate the density maps. The DSAM is designed to capture the visual context
cues by extracting features at different scales. The CAM focus on the inter-
class feature decorrelation, which can effectively reduce the bad interference
among density maps belonging to different categories.

###  3.1 Multi-Class object counting problem definition

The current single-class object counting methods apply the Gaussian kernels on
point annotations to generate density maps as ground truth and make
predictions about the number of a single class. To realize the multi-class
object counting, we generate individual density maps for each category in an
image. To be specific, given an image containing $N$ classes of objects, the
ground-truth density map $D$ can be illustrated as:

$D=\left\\{\begin{matrix}\sum_{i=1}^{C_{1}}\delta(P^{1}-P_{i}^{1})\ast
G_{\sigma^{1}}(P^{1})\\\ \vdots\\\
\sum_{i=1}^{C_{k}}\delta(P^{k}-P_{i}^{k})\ast G_{\sigma^{k}}(P^{k}),\\\
\vdots\\\ \sum_{i=1}^{C_{n}}\delta(P^{n}-P_{i}^{n})\ast
G_{\sigma^{n}}(P^{n})\end{matrix}\right.$ (1)

where $P_{i}^{k}$ represents the point annotation of the $i$-th instance
belonging to the $k$-th class. There are $C_{k}$ instances in the $k$-th
class. $\sigma^{k}$ is the kernel size for the $k$-th class in Gaussian
function $G$, and the value of $\sigma^{k}$ depends on the relative sizes of
the $k$-th class.

###  3.2 Dilated-Scale-Aware Module

Due to the perspective effect, the scales of objects change a lot in a scene.
It forms a challenge for feature extraction. To overcome this issue, we
propose the Dilated-Scale-Aware Module (DSAM) that captures multi-scale
information by fusing features from different layers of the backbone.

In the VGG16 with max-pooling layers, the receptive field of convolution
layers become progressively larger as the depth increases. The intermediate
layers of a CNN hierarchically learn visual patterns from edges and corners to
parts and objects. As shown in Fig. 2, the proposed DSAM applies different
dilated convolutions on stage$\\_3$, stage$\\_4$ and stage$\\_5$. The
expansion ratios of dilated convolutional filters are set as $2$, $3$, and
$5$, respectively. After the upsample and concatenation operation, a $3\times
3$ convolutional layer is added to fuse these multi-scale features. By doing
so, the DSAM effectively combines hierarchical features from different layers,
which indeed improves the object counting performance.

Fig. 3: Visualization results on the RSOC dataset [23] and the VisDrone-DET
dataset [24]. The given images of the two datasets contain huge differences in
viewpoint, scene, target size, and image scale, but our method shows strong
robustness as well as impressive multi-class object counting performance.

###  3.3 Category-Attention Module

Although the DSAM effectively mitigates the effect of intra-class scale
variation, mutual interference between classes exits on the density maps. This
inspires us to design the Category-Attention Module (CAM) to generate the
discriminative density maps, as shown in Fig. 2.

The CAM is designed to generate spatial attentions for each class. We generate
the pseudo ground-truth mask maps for each instance from point annotations to
supervise the learning of spatial attentions. Specifically, we first utilize
the distance transformation [25] and transform the point annotation map to a
distance map $D$, which is described as:

$P_{\left(x,y\right)}=\underset{\left(x_{i},y_{i}\right)\in
A}{\min}\sqrt{\left(x-x_{i}\right)^{2}+\left(y-y_{i}\right)^{2}},$ (2)

where $P_{\left(x,y\right)}$ represents the pixel value located at
$\left(x,y\right)$ in the distance map $D$. $A$ is the set of annotated
coordinates. The pseudo-labels for spatial attention generation can be
obtained as a $0-1$ mask by using a distance threshold $J$ to divide the
distance map into the foreground and background.

As shown in Fig. 2, the CAM adopts the feature maps of stage$\\_5$ as input
since the high-level layer learns more semantic information. Similar to the
DSAM, the CAM enhances the multi-scale information via four dilated
convolutional layers with $1$, $2$, $3$, $4$ dilation rates, respectively. The
multi-scale feature maps are combined via channel-wise concatenation operation
and several convolution layers. The number of the spatial attentions is equal
to the number of categories, and the estimated spatial attentions multiplies
the estimated density maps to obtain the final density maps, which effectively
reduces the inter-class interference.

###  3.4 Loss function

We utilize the $L_{2}$ loss to measure the difference between the ground truth
density maps and estimated density maps:

$L_{2}=\sum_{n=1}^{N}\sum_{x=1}^{W}\sum_{y=1}^{H}\left|P^{{}^{\prime}}_{(n,x,y)}-P_{(n,x,y)}\right|^{2},$
(3)

where $N$ is the total number of the categories. $W$ and $H$ represent the
width and height of the training image. $P^{{}^{\prime}}_{(n,x,y)}$ and
$P_{(n,x,y)}$ represent the pixel values located at $(x,y)$ in the estimated
density map and the ground-truth density map of the $c$-th class respectively.

We train the CAM based on the Binary Cross Entropy loss, as defined by:

$\displaystyle L_{BCE}=$ $\displaystyle-\frac{1}{W\times
H}\sum_{x=1}^{W}\sum_{y=1}^{H}\left(\left(T_{\left(x,y\right)}\times\log{R_{\left(x,y\right)}}\right)\right.$
(4)
$\displaystyle\left.+\left(1-T_{\left(x,y\right)}\right)\times\log{\left(1-R_{\left(x,y\right)}\right)}\right),$

where $T_{\left(x,y\right)}\in{\\{0,1\\}}$ denotes the pseudo-label for
spatial attention located at $(x,y)$. $R_{\left(x,y\right)}\in{[0,1]}$
represents the predicted spatial attention. The final training objective
function $L$ is defined as below:

$L=\sum_{i=1}^{2}L_{2}^{i}+\sum_{n=1}^{N}L_{BCE}^{n}.$ (5)

##  4 Experiments

###  4.1 Implementation details

The proposed network is trained in an end-to-end fashion. For the first 13
convolutional layers, we initialize them with a pre-trained VGG-16 [10]. The
other layers are initialized by a Gaussian initialization with 0.01 standard
deviation. The distance threshold $J$ is set as $20$. We flip each image and
crop the given images randomly as the data augmentation processes. The
parameters are updated by an adaptive moment estimation optimizer.

Fig. 4: In the person-vehicle counting task, both estimated density maps are
interfered by each other, as shown in the red dashed boxes. The spatial
attention masks suppressed these harmful responses effectively.

###  4.2 Datasets

Since there are no publicly available multi-class object counting datasets, we
utilize the single-class object counting dataset RSOC [23] including multiple
subsets and the object detection dataset VisDrone-DET [24] for evaluation.
Note that object detection datasets provide box-level annotations instead of
point-level annotations. We obtain the point-level annotations by computing
the center of bounding boxes. All the experiments are conducted on the point-
level annotations.

VisDrone-DET Dataset [24]. This dataset contains $10,209$ images captured by
cameras equipped on drones. There are ten categories annotated, including
pedestrian, person, car, van, bus, truck, motor, bicycle, awning-tricycle, and
tricycle. To increase the density of the counting instances and ensure the
challenge for counting task, we merge the pedestrian category into the person
category and consider car, van, bus, truck as the same category named vehicle.
The extremely small size of objects is the major challenge of this dataset.

RSOC Dataset [23]. This dataset contains $3,057$ images collected from Google
Earth and DOTA dataset [26]. It is the largest object counting dataset
collected in a remote sense. And the instances included are in high density.
There are four categories of images, including buildings, small vehicles,
large vehicles, and ships. Specifically, the small vehicles and the large
vehicles always appear in the same image, which meets the labeling
requirements for multi-class object counting tasks. In our experiments, we
choose the small vehicle and large vehicle subsets into a multi-class object
counting dataset. The most challenging issue of the RSOC dataset is the severe
background noise.

Table 1: Performance comparisons on the VisDrone-DET dataset [24]. The first
and second places are marked in red and blue respectively.

Method | Backbone | Mean | Vehicle | Person
---|---|---|---|---
MAE | MSE | MAE | MSE | MAE | MSE
MCNN [9] | - | 9.664 | 14.123 | 8.808 | 11.885 | 10.520 | 16.361
SANet [27] | - | 16.807 | 24.091 | 17.992 | 23.234 | 15.623 | 24.947
CSRNet [28] | VGG16 | 6.778 | 9.429 | 6.022 | 8.091 | 7.535 | 10.767
BL [15] | VGG19 | 7.503 | 10.504 | 6.754 | 9.021 | 8.252 | 11.988
CAN [21] | VGG16 | 6.224 | 8.831 | 5.662 | 7.667 | 6.786 | 9.994
Ours | VGG16 | 4.030 | 6.285 | 3.437 | 5.468 | 4.624 | 7.102

Table 2: Performance comparisons on the RSOC dataset [23]. The first and
second places are marked in red and blue respectively.

Method | Backbone | Mean | Small-Vehicle | Large-Vehicle
---|---|---|---|---
MAE | MSE | MAE | MSE | MAE | MSE
MCNN [9] | - | 105.600 | 425.029 | 186.913 | 814.102 | 24.288 | 35.957
SANet [27] | - | 143.670 | 500.228 | 246.830 | 939.159 | 40.509 | 61.298
CSRNet [28] | VGG16 | 87.537 | 361.727 | 154.898 | 697.101 | 20.177 | 26.353
BL [15] | VGG19 | 107.212 | 297.607 | 172.883 | 534.460 | 41.541 | 60.754
CAN [21] | VGG16 | 58.987 | 137.238 | 94.772 | 235.974 | 23.201 | 38.501
Ours | VGG16 | 42.432 | 127.441 | 65.398 | 223.578 | 19.467 | 31.305

Table 3: Ablation studies on the VisDrone-DET dataset [24]. The first and
second places are marked in red and blue respectively.

Method | Mean | Vehicle | Person
---|---|---|---
MAE | MSE | MAE | MSE | MAE | MSE
baseline | 6.823 | 9.549 | 6.242 | 8.363 | 7.405 | 10.736
baseline+DSAM | 5.066 | 7.439 | 4.233 | 6.049 | 5.900 | 8.828
baseline+CAM | 4.202 | 6.649 | 3.556 | 5.455 | 4.849 | 7.844
baseline+DSAM+CAM | 4.030 | 6.285 | 3.437 | 5.468 | 4.624 | 7.102

###  4.3 Evaluation metrics

The Mean Absolute Error (MAE) and the Mean Squared Error (MSE) are the primary
metrics in the object counting task. In the multi-class counting task, we
adopt MAE and MSE to evaluate counting performance for each class, then
average the results of all the categories to get $MAE_{Mean}$ and
$MSE_{Mean}$, which denote the multi-class counting capability:

$MAE=\frac{1}{M}\sum_{m=1}^{M}\left|Q_{m}^{{}^{\prime}}-Q_{m}\right|,MSE=\sqrt{\frac{1}{M}\sum_{m=1}^{M}\left(Q^{{}^{\prime}}_{m}-Q_{m}\right)^{2}},$
(6)
$MAE_{Mean}=\frac{1}{N}\sum_{n=1}^{N}MAE_{n},MSE_{Mean}=\frac{1}{N}\sum_{n=1}^{N}MSE_{n},$
(7)

where $M$ denotes the number of images in the testing set, $N$ is the number
of the categories. $Q_{m}^{{}^{\prime}}$ and $Q_{m}$ are the estimated and
labeling count number of the $m$-th image.

###  4.4 Comparisons with the State-of-the-art

The traditional object counting methods are designed for single-class object
counting task. While for multi-class object counting task, the previous point-
level annotations based object counting methods should train separate models
for each category. The experiments on these two datasets are two-category
object counting. For fair comparisons, we change the output channel of other
methods to $2$ to implement the multi-class object counting task. Tab. 1 and
Tab. 2 list the quantitative results of VisDrone-DET [24] and RSOC [23]
respectively, and we also tell the quality of estimated density maps in Fig.
3.

VisDrone-DET Dataset. We first compare our method with various classic object
counting methods on the VisDrone-DET dataset. The proposed method achieves the
best performance on all metrics. Specially, our method improves $35.3\%$ in
$MAE_{Mean}$, $28.8\%$ in $MSE_{Mean}$, $39.3\%$ in $MAE_{Vehicle}$, $28.7\%$
in $MSE_{Vehicle}$, $31.9\%$ in $MAE_{Person}$ and $28.9\%$ in $MSE_{Person}$
compared with CAN.

RSOC Dataset. We also compare our method with other related works on the RSOC
dataset. As we can see, the proposed method achieves $42.432$ in $MAE_{Mean}$
and $127.441$ in $MSE_{Mean}$, which is currently the best multi-class object
counting performance. Counting the Small-Vehicle, our approach improves
$31.0\%$ in $MAE_{Small-Vehicle}$ and achieves $12.396$ $MSE_{Small-Vehicle}$
dropped compared with CAN, respectively.

In summary, the proposed method shows outstanding performance on these two
datasets.

###  4.5 Ablation Studies

In this section, we conduct the ablation studies to verify the effectiveness
of DSAM and CAM on the VisDrone-DET dataset [24].

Effectiveness of DSAM. We first study the impact of DSAM, which is designed to
capture the intra-class multi-scale information. The results are listed in
Tab. 3. We find that the addition of DSAM causes $1.757$ $MAE_{Mean}$ and
$2.11$ $MSE_{Mean}$ dropped compared with the baseline.

Effectiveness of CAM. We further validate the effect of the proposed CAM. The
results are listed in Tab. 3. CAM achieves $38.4\%$ $MAE_{Mean}$ and $30.4\%$
$MSE_{Mean}$ improvement, which indicates that CAM effectively reduces the
inter-class interference on density maps. By observing Fig. 4, we can see that
the predicted results with CAM exhibit better clarity and better accuracy
compared with baseline in both crowd scenes and vehicle scenes.

##  5 Conclusion

In this paper, we propose a novel Dilated-Scale-Aware Category-Attention
ConvNet (DSACA), which achieves multi-class object counting simultaneously
only based on point-level annotations. To overcome the inter-class
interference that appears among the density maps and mitigate the effects of
intra-class scale variations, we designed Dilated-Scale-Aware Module (DSAM)
and Category-Attention Module (CAM). Extensive experiments on two challenging
benchmarks show the validity of our approach. In the future work, we will
explore the correlation of multi-class object counting and single-class object
counting systematically.

## References

  * [1] Q. Wang, J. Gao, W. Lin, and X. Li, “Nwpu-crowd: A large-scale benchmark for crowd counting and localization,” IEEE Transactions on Pattern Analysis and Machine Intelligence, 2020.
  * [2] T. Falk, D. Mai, R. Bensch, Ö. Çiçek, A. Abdulkadir, Y. Marrakchi, A. Böhm, J. Deubner, Z. Jäckel, K. Seiwald, et al., “U-net: deep learning for cell counting, detection, and morphometry,” Nature methods, 2019.
  * [3] R. Guerrero-Gómez-Olmedo, B. Torre-Jiménez, R. López-Sastre, S. Maldonado-Bascón, and D. Onoro-Rubio, “Extremely overlapping vehicle counting,” in IbPRIA, 2015.
  * [4] S. Ren, K. He, R. Girshick, and J. Sun, “Faster r-cnn: Towards real-time object detection with region proposal networks,” IEEE transactions on pattern analysis and machine intelligence, 2016.
  * [5] W. Liu, D. Anguelov, D. Erhan, C. Szegedy, S. Reed, C.-Y. Fu, and A. C. Berg, “Ssd: Single shot multibox detector,” in ECCV, 2016.
  * [6] J. Redmon, S. Divvala, R. Girshick, and A. Farhadi, “You only look once: Unified, real-time object detection,” in CVPR, 2016.
  * [7] C. Xu, K. Qiu, J. Fu, S. Bai, Y. Xu, and X. Bai, “Learn to scale: Generating multipolar normalized density map for crowd counting,” ICCV, 2019.
  * [8] Y. Yang, G. Li, Z. Wu, L. Su, Q. Huang, and N. Sebe, “Reverse perspective network for perspective-aware object counting,” in CVPR, 2020.
  * [9] Y. Zhang, D. Zhou, S. Chen, S. Gao, and Y. Ma, “Single-image crowd counting via multi-column convolutional neural network,” in CVPR, 2016.
  * [10] K. Simonyan and A. Zisserman, “Very deep convolutional networks for large-scale image recognition,” international conference on learning representations, 2015.
  * [11] C. P. Papageorgiou, M. Oren, and T. Poggio, “A general framework for object detection,” in ICCV, 1998.
  * [12] N. Dalal and B. Triggs, “Histograms of oriented gradients for human detection,” in CVPR, 2005.
  * [13] X. Zhou, D. Wang, and P. Krähenbühl, “Objects as points,” arXiv preprint arXiv:1904.07850, 2019.
  * [14] R. Girshick, J. Donahue, T. Darrell, and J. Malik, “Rich feature hierarchies for accurate object detection and semantic segmentation,” in CVPR, 2014\.
  * [15] Z. Ma, X. Wei, X. Hong, and Y. Gong, “Bayesian loss for crowd count estimation with point supervision,” in ICCV, 2019.
  * [16] N. Liu, Y. Long, C. Zou, Q. Niu, L. Pan, and H. Wu, “Adcrowdnet: An attention-injective deformable convolutional network for crowd understanding,” in CVPR, 2019.
  * [17] X. Jiang, Z. Xiao, B. Zhang, X. Zhen, X. Cao, D. Doermann, and L. Shao, “Crowd counting and density estimation by trellis encoder-decoder networks,” in CVPR, 2019.
  * [18] S. Bai, Z. He, Y. Qiao, H. Hu, W. Wu, and J. Yan, “Adaptive dilated network with self-correction supervision for counting,” in CVPR, 2020.
  * [19] A. Zhang, L. Yue, J. Shen, F. Zhu, X. Zhen, X. Cao, and L. Shao, “Attentional neural fields for crowd counting,” in ICCV, 2019.
  * [20] Z. Yan, Y. Yuan, W. Zuo, X. Tan, Y. Wang, S. Wen, and E. Ding, “Perspective-guided convolution networks for crowd counting,” in ICCV, 2019.
  * [21] W. Liu, M. Salzmann, and P. Fua, “Context-aware crowd counting,” in CVPR, 2019.
  * [22] Z.-Q. Cheng, J.-X. Li, Q. Dai, X. Wu, and A. G. Hauptmann, “Learning spatial awareness to improve crowd counting,” in ICCV, 2019.
  * [23] G. Gao, Q. Liu, and Y. Wang, “Counting from sky: A large-scale data set for remote sensing object counting and a benchmark method,” IEEE Transactions on Geoscience and Remote Sensing, 2020.
  * [24] P. Zhu, L. Wen, D. Du, X. Bian, H. Ling, Q. Hu, H. Wu, Q. Nie, H. Cheng, C. Liu, et al., “Visdrone-vdt2018: The vision meets drone video detection and tracking challenge results,” in ECCV, 2018.
  * [25] A. Rosenfeld and J. L. Pfaltz, “Distance functions on digital pictures,” Pattern recognition, 1968.
  * [26] G.-S. Xia, X. Bai, J. Ding, Z. Zhu, S. Belongie, J. Luo, M. Datcu, M. Pelillo, and L. Zhang, “Dota: A large-scale dataset for object detection in aerial images,” in CVPR, 2018.
  * [27] X. Cao, Z. Wang, Y. Zhao, and F. Su, “Scale aggregation network for accurate and efficient crowd counting,” in ECCV, 2018.
  * [28] Y. Li, X. Zhang, and D. Chen, “Csrnet: Dilated convolutional neural networks for understanding the highly congested scenes,” in CVPR, 2018.


# The Stroke Correspondence Problem, Revisited

Dominik Klein

###### Abstract

We revisit the stroke correspondence problem [13, 14]. We optimize this
algorithm by 1) evaluating suitable preprocessing (normalization) methods 2)
extending the algorithm with an additional distance measure to handle
Hiragana, Katakana and Kanji characters with a low number of strokes and c)
simplify the stroke linking algorithms. Our contributions are implemented in
the free, open-source library ctegaki and in the demo-tool jtegaki.

##  1 Introduction

Revisiting the _stroke correspondence problem_ is motivated by developing a
robust, freely available, open-source Japanese on-line handwriting recognition
engine, especially considering the current advance of touch-driven mobile
devices. For handwriting recognition, learning based methods have largely
replaced approaches based on template matching. Popular methods are
directional feature extraction [2] and classification by MQDF [3], or
approaches based on neural networks [7]. In order to a achieve satisfactory
performance, learning based methods however require lots of training samples
for each character [9]. Several large databases with training samples exist,
cf. [10, 8, 6], or the JEITA-HP database. To the author’s best knowledge, none
of them is available under a free license that would permit use in free/libre
open-source software. On the other hand, generating such a database from
scratch is no easy task; for example [8] write – despite being full-time
academic researchers – that they spent 4 years compiling […] databases, and
such a monumental task is difficult to achieve within an open-source project.
This is probably one main reason why none of the above mentioned high-
performing recognition approaches have been implemented and released as open
source.

It is very important for a recognition engine to be able to cope with stroke-
order and stroke-number variations. While in theory the number and the order
of strokes is uniquely defined for each kanji character, in practice they vary
widely w.r.t. individual writing styles. Native speakers for example tend to
combine several strokes into one in order to write faster (cursive style), and
foreign leaners of the language often do not know the correct stroke order. A
recognition algorithm must thus be able to recognize kanji independent on
stroke-order and stroke-number.

The only two open-source Japanese online character recognition engines the
author is aware of - zinnia111http://www.zinnia.sourceforge.net and
wagomu222http://tegaki.org use learning based approaches and employ a rather
small training data set of one sample per character. Therefore they cannot
cope with stroke-number or stroke-order variations very well.

In this paper, a simple approach of directly linking a written character to a
reference template pattern [14] is revisited. Recognition is then performed by
directly comparing the reference template with the input pattern, and the
ability to cope with stroke-order and stroke-number variations is inherent in
the comparison. Such an approach has the big advantage, that no training data
is needed, and one reference template for each character suffices. [11] used a
similar approach using directional features for reference templates, resulting
in a very high recognition rate. This comes at the cost of stroke-number free
recognition, and a sophisticated but complex data-structure and search
algorithm. In this paper the original approach [14] is extended by

  1. 1.

evaluating which image normalization techniques is the overall performance.

  2. 2.

introducing a distance measure using directional features akin to [11]. This
increases recognition performance of Hiragana, Katakana and Kanji with a low
number of strokes.

  3. 3.

Last, a simple-to-implement yet well-performing stroke linking algorithm is
introduced, replacing the two complementing algorithms defined by [14].

All techniques have been implemented in the open-source library ctegaki, which
is available under a free BSD-style license at

https://github.com/asdfjkl/ctegaki-lib

Moreover a JavaScript-based demo application is available at

https://asdfjkl.github.io/kanjicanvas

This paper is structured as follows. In Section 2 the _stroke correspondence
problem_ is reviewed and distance measures are introduced. Suitable
normalization methods are discussed in Section 3. Two complementing algorithms
were used by [14] for stroke linking. A new algorithm is introduced in Section
4. The overall recognition algorithm is presented in Section 5. The effect of
various normalization algorithms, the newly introduced directional distance
measure, and the new stroke linking algorithm, as well as overall performance
compared to the open source recognition library Zinnia, is empirically
evaluated in Section 6. Last, the presentation is concluded in Section 7.

##  2 The Stroke Correspondence Problem

A kanji character $k$ is defined as a set of strokes $k={s_{1},\ldots,s_{n}}$.
This set is ordered w.r.t. the index of the strokes which represent the order
in which the strokes were drawn. A strokes $s$ is a set of points
$s=\\{s_{1},\ldots,s_{k}\\}$, again ordered by their indices. A point $(x,y)$
is a 2D-coordinate. Let $k_{1}$ be a kanji with $n$ strokes
$s_{1},\ldots,s_{n}$, and $k_{2}$ be a kanji with $m$ strokes
$t_{1},\ldots,t_{m}$. In the following we assume w.l.o.g. $n\geq m$. Given two
sets of strokes $S$ and $T$, a _stroke distance function_ is a function
$d:S\times T\to\mathbb{R}$.

Given two kanji with the same number of strokes and a stroke distance
function, the _$n-n$ stroke correspondence problem_ is the optimization
problem to find a mapping between the strokes that minimizes the overall
distance.

######  Definition 1 ($n-n$ Stroke Correspondence Problem)

Let $k_{1}=\\{s_{1},\ldots,s_{n}\\}$ and $k_{2}$ be two kanji both of length
$n$, and $d$ a stroke distance function. The _$n-n$ stroke correspondence
problem_ is the problem to find a bijective function $f:k_{1}\to k_{2}$, that
minimizes $\sum_{1\leq i\leq n}d(s_{i},f(s_{i}))$.

The general idea for recognition is to define one template for each kanji.
Given an input kanji that should be recognized, a minimizing function is
computed for each pair of the input kanji and one template. Then the overall
distance between the input kanji and the template is calculated w.r.t. the
minimizing function, and the result of the recognition is the template with
the smallest distance. Since the minimizing function does not incorporate any
stroke order, this recognition approach is completely independent of the
stroke order.

Two problems arise with this approach. First, given a kanji and a template
with $n$ strokes, the cost of finding a minimizing function $f$ is in
$\mathcal{O}(n!)$. Fast approximation algorithms for $f$ are subject of
Section 4. Second, the definition can only cope with input kanji and templates
that have the same number of strokes. To deal with kanji of arbitrary numbers
of strokes, the definition is extended. Given two strokes $s_{1}$ and $s_{2}$,
the _concatenated stroke_ of $s_{1}$ and $s_{2}$ is defined as the union
$s_{1}\cup s_{2}$, where the order of points is extended such that all points
of $s_{1}$ are smaller than those of $s_{2}$, i.e. the points of $s_{2}$ are
appended to $s_{1}$. Concatenation is extended in the obvious way to arbitrary
numbers of strokes. Given $\\{s_{1},\ldots,s_{k}\\}$, the concatenation of all
strokes is denoted by $\mathsf{conc}(\\{s_{1},\ldots,s_{k}\\})$. In the next
definition, only surjectivity is required for $f$:

######  Definition 2 ($n-m$ Stroke Correspondence Problem)

Suppose two kanji $k_{1}=\\{s_{1},\ldots,s_{n}\\}$ and
$k_{2}=\\{t_{1},\ldots,t_{m}\\}$ are given, and let $d$ be a stroke distance
function. The _$n-m$ stroke correspondence problem_ is the problem to find an
surjective function $f:k_{1}\to k_{2}$, that minimizes $\sum_{1\leq i\leq
m}d(\mathsf{conc}(\\{s\mid f(s)=t_{i}\\}),t_{i}).$

This optimization problem depends on the definition of the stroke distance
function. These are subject of the next section.

###  2.1 Stroke Distance Functions

Three distance functions were originally introduced by [14].

######  Definition 3 (Endpoint Distance)

Suppose two strokes $s_{1}=\\{(x_{1},y_{1}),\ldots,(x_{n},y_{n})\\}$ and
$s_{2}=\\{(u_{1},v_{1}),\ldots,(u_{m},v_{m})\\}$ are given. The _endpoint
distance_ is defined as

$d_{\mathsf{ep}}(s_{1},s_{2})=|x_{1}-u_{1}|+|y_{1}-v_{1}|+|x_{n}-u_{m}|+|y_{n}-v_{m}|.$

In the original definition, the calculation used division by some constant.
This is omitted here. Since the computation of the endpoint distance is quite
efficient, it can be used for a quick coarse classification to find suitable
candidates. For fine classification, the next two distance measures were
introduced. In the next definition, it is assumed that $m,n\in\mathbb{Q}$.
Hence, division results in a real number.

######  Definition 4 (Initial Stroke Distance)

Suppose two strokes $s_{1}=\\{(x_{1},y_{1}),\ldots,(x_{n},y_{n})\\}$ and
$s_{2}=\\{(u_{1},v_{1}),\ldots,(u_{m},v_{m})\\}$. Let $n\geq m$. The _initial
stroke distance_ is defined as

$d_{\mathsf{in}}(s_{1},s_{2})=\frac{n}{m}\;\cdot\sum_{i=1}^{m}|x_{i}-u_{i}|+|y_{i}-v_{i}|$

The next distance measure is the most precise one.

######  Definition 5 (Whole-Whole Stroke Distance)

Suppose $s_{1}=\\{(x_{1},y_{1}),\ldots,(x_{n},y_{n})\\}$ and
$s_{2}=\\{(u_{1},v_{1}),\ldots,(u_{m},v_{m})\\}$. Let $n\geq m$. The _whole-
whole stroke distance_ is defined as

$d_{\mathsf{ww}}(s_{1},s_{2})=\frac{1}{m}\cdot\sum_{i=1}^{m}|x_{i}-u_{j(i)}|+|y_{i}-v_{j(i)}|$

Here $j(i)=\left(\frac{n-1}{m-1}\cdot(i-1)\right)+1$, integer division is used
for the calculation of $i(j)$, and the division $1/m$ for $d_{\mathsf{ww}}$ is
in $\mathbb{Q}$.

None of these stroke distances emphasize the actual stroke _direction_. [11]
used directional features for stroke order independent (but not stroke number
independent) recognition. Directional features are especially important when
recognizing kanji with low number of strokes, or hiragana and katakana
characters. Consider for example し and 乙. If the stroke of these characters is
represented by only a few points, all above mentioned stroke distances will
result in a low overall distance, and hence distinguishing these characters is
difficult. On the other hand, the two characters have very distinct
directional features. This motivates the next definition, which is new
compared to those introduced by [14].

######  Definition 6 (Directional Stroke Distance)

Let $s_{1}=\\{(x_{1},y_{1}),\ldots,(x_{n},y_{n})\\}$ and
$s_{2}=\\{(u_{1},v_{1}),\ldots,(u_{m},v_{m})\\}$, and let $n\geq m$. The
_directional stroke distance_ is defined as

$\displaystyle d_{\mathsf{dd}}(s_{1},s_{2})=\frac{1}{m}\cdot\sum_{i=2}^{m}$
$\displaystyle~{}\Big{(}|(x_{i}-x_{i-1})-(u_{j(i)}-u_{j(i-1)})|$
$\displaystyle+|(y_{i}-y_{i-1})-(v_{j(i)}-v_{j(i-1)})|\Big{)}$

where $j(i)=\left(\frac{n-1}{m-1}\cdot(i-1)\right)+1$ and $j(i)$ is computed
with integer division, whereas the $1/m$ in $d_{\mathsf{dd}}$ is division in
$\mathbb{Q}$.

##  3 Normalization Methods

Image Normalization is an important pre-processing step in character
recognition. Given an image with height $h_{1}$ and width $w_{1}$ (i.e. a
bounding box around the drawn character), image normalization projects this
image to a an image with pre-defined height $h_{2}$ and width $w_{2}$.
Throughout this section, we will consider a kanji as binary image (function)
$f(x,y)$.

######  Definition 7 (Linear Normalization)

Let $(x,y)$ be an input coordinate. Supposed $h_{1}$ and $w_{1}$ are the
height and width of the input image, and $h_{2}$ and $w_{2}$ the height and
width of the normalized image. The transformed coordinate
$(x^{\prime},y^{\prime})$ is defined as: $x^{\prime}=x{w_{2}}/{w_{1}}$ and
$y^{\prime}=y{h_{2}}/{h_{1}}$.

In the recognition approach of this paper, linear normalization is used only
when the width and height of a character are very different. It then makes
sense to keep the aspect ratio, and multiply only by the minimum of
$w_{2}/w_{1}$ and $h_{2}/h_{1}$ (cf. Section 5).

Figure 1: From left to right: Original Image, Linear Normalization, Moment
Normalization, Line Density Equalization, Dot Density Equalization with
$\alpha=2,3,4$.

Moment normalization was originally formulated by [1], but here the simplified
variant introduced by [5] is used. Recall that given an image (function)
$f(x,y)$, (raw) image moments are defined as
$m_{ij}=\sum_{x}\sum_{y}x^{i}y^{j}f(x,y)$. Components of the centroid are
$x^{\prime}_{c}=m_{10}/m_{00}$ and $y^{\prime}_{c}=m_{01}/m_{00}$, and
_central moments_ of the image are defined as
$\mu_{pq}=\sum_{x}\sum_{y}(x-x^{\prime}_{c})^{p}\;(y-y^{\prime}_{c})^{q}\;f(x,y)$.

######  Definition 8 (Moment Normalization)

Let $(x,y)$ be an input coordinate. Supposed $h_{1}$ and $w_{1}$ are the
height and width of the input image, and $h_{2}$ and $w_{2}$ the heigth and
width of the normalized image. Let $\delta_{x}=\sqrt{\mu_{20}}$ and
$\delta_{y}=\sqrt{\mu_{02}}$. Distinct from other normalization methods, the
bounding box of the input image is first reset to
$\left[x_{c}-\frac{\delta_{x}}{2},x_{c}+\frac{\delta_{x}}{2}\right],\left[y_{c}-\frac{\delta_{y}}{2},y_{c}+\frac{\delta_{y}}{2}\right].$
The transformed coordinate $(x^{\prime},y^{\prime})$ is defined as:

$x^{\prime}=\frac{w_{2}}{\delta_{x}}(x-x_{c})+x^{\prime}_{c},\quad\quad
y^{\prime}=\frac{h_{2}}{\delta_{y}}(y-y_{c})+y^{\prime}_{c}$

The effect on normalization techniques has been studied before especially in
the context of directional feature extraction [4, 5]. As can be seen in the
latter, the introduction of advanced pseudo 2D normalization techniques
improves recognition rates. However non-linear normalization [15, 12] is a
simple and fast technique that achieves a significant improvement over no or
linear-normalization. The investigation is thus restricted here to the non-
linear normalization techniques introduced by [15]. The next two methods rely
on feature projection functions $H(x)$ and $V(y)$.

######  Definition 9 (Dot Density Equalization)

Let $\alpha_{H}$ and $\alpha_{V}$ be given constants, and let $f(x,y)$ denote
the input image, and $h_{1},w_{1},h_{2},w_{2}$ the height and width of the
input and normalized image. The projection functions are defined as:
$H(x)=\sum_{y=1}{h_{1}}f(x,y)+\alpha_{H}$ and
$V(y)=\sum_{x=1}{w_{1}}f(x,y)+\alpha_{W}$ The normalized image is defined as:

$\displaystyle x^{\prime}$
$\displaystyle=\sum_{k=1}^{x}H(k)\cdot\frac{w_{2}}{\sum_{k=1}^{w_{1}}H(k)},$
$\displaystyle
y^{\prime}=\sum_{l=1}^{y}V(l)\cdot\frac{h_{2}}{\sum_{l=1}^{h_{1}}V(l)}$ (1)

Line density equalization works similar as dot density equalization, but
employs a more advanced density projection.

######  Definition 10 (Line Density Equalization)

To define feature projections, first four types of edges $E$ are defined for a
given point $(i,j)$. Below $\overline{f(i,j)}$ denotes the inverted pixel
$f(i,j)$.

$\displaystyle E_{1}$ $\displaystyle=\mathsf{max}\\{i^{\prime}\mid
i^{\prime}<i,f(i^{\prime},j)\cdot\overline{f(i^{\prime}+1,j}=1\\}$
$\displaystyle E_{2}$ $\displaystyle=\mathsf{min}\\{i^{\prime}\mid
i^{\prime}\geq i,f(i^{\prime},j)\cdot\overline{f(i^{\prime}+1,j}=1\\}$
$\displaystyle E_{3}$ $\displaystyle=\mathsf{max}\\{i^{\prime}\mid
i^{\prime}<i,\overline{f(i^{\prime}-1,j)}\cdot f(i^{\prime},j=1\\}$
$\displaystyle E_{4}$ $\displaystyle=\mathsf{min}\\{i^{\prime}\mid
i^{\prime}\geq i,\overline{f(i^{\prime}-1,j)}\cdot f(i^{\prime},j=1\\}$

Note that there is a case where $i^{\prime}$ is not defined. Based on these
four types of edges, horizontal and vertical _line intervals_ are defined. Let
$w_{1},h_{1}$ denote width and height of the input image. $L_{x}$ is defined
as 1) $4w_{1}$, if all $E_{1},E_{2},E_{3},E_{4}$ are not defined, 2) $2w_{1}$,
if only $E_{1},E_{3},$ are not defined, 3) $2w_{1}$, if only $E_{2},E_{4}$ are
not defined, 4) $2w_{1}$, if only $E_{1},E_{4}$ are not defined, 5)
$E_{4}-E_{3}$, if only $E_{1}$ is not defined, 6) $E_{2}-E_{1}$, if only
$E_{4}$ is not defined, and finally $((E_{2}-E_{1})+(E_{4}-E_{3}))/2$,
otherwise.

The line interval $L_{y}$ for the vertical direction is defined analogously,
where $h_{1}$ is taken instead of $w_{1}$, and edge definitions are changed
w.r.t. vertical directions. Line densities are defined as:
$\rho(i,j)=\mathsf{max}(w_{1}/L_{x},h_{1}/L_{y})$ if $L_{x}$ \+
$L_{y}<6w_{1}$, and $\rho(i,j)=0$, otherwise. Projection function are defined
by

$\displaystyle H(x)=\sum_{y=1}\rho(i,j),$ $\displaystyle
V(y)=\sum_{x=1}\rho(i,j)$ (2)

The actual mapping coordinates $(x^{\prime},y^{\prime})$ are then obtained by
inserting the projection functions of $(2)$ in equation $(1)$ of Definition 9.

##  4 Stroke Linking Algorithms

The goal of a stroke linking algorithm is to find a (surjective) mapping
function $f$ that meets the condition of Definition 2. In the original paper
by [13], the following approach was proposed: First, find a mapping from $n$
out $m$ strokes of kanji $k_{1}$ to the $n$ strokes of kanji $k_{2}$. Second,
if $n\not=m$, the remaining strokes of $k_{1}$ are then concatenated with
their preceding or following strokes. For the first step they propose two
complementing algorithms, _excessive mapping dissolution (EMD)_ and _deficient
mapping dissolution (DMD)_. The motivation to introduce two algorithms is
shown in Figure 2. Considering a distance measure that simply computes the
manhattan distance of two points, two $n/n$ mapping cases are depicted. For
one case, EMD succeeds to find the optimal mapping whereas DMD fails, and in
the other case, the reverse is true.

Figure 2: Examples of 2D-Point linking for the presented linking algorithms.
DMD solves the left, but not the right example, EMD solves the right, but not
the left one, and iterative improvement solves both.

Both from the perspective of run-time and implementation complexity, it is
desirable to have only one single algorithm. A simple approach is just to use
a greedy strategy, where, iterating over all $n$ strokes from $k_{2}$, given
stroke $i$ from $k_{1}$, an unassigned stroke $j$ out of the $m$ stroke of
$k_{1}$ is chosen for which the distance $d(i,j)$ is minimal. Manual
inspection of such computed $n/n$ stroke maps revealed that in practice
usually only very few excessive local minima cause a mapping that does not
yield a global minimum. The typical cause of such local minima are strokes of
very short length, which yield a very short local minimum with almost every
nearby stroke, such as the first two strokes of 字. This is the motivation to
introduce the _iterative improvement_ algorithm. Technically this is one
algorithm, but for the ease of presentation, the greedy initialization part as
described above is shown separately as Algorithm 1, whereas the remaining part
of the algorithm is shown as Algorithm 2. Algorithm 2 loops a fixed set of $L$
times over the initialized stroke map, and in each loop switches the current
assignment to another assigned stroke (line 9 to 17), or to another unassigned
stroke (line 18 to 25), if the resulting distance can be improved by
switching.

Algorithm 1 Greedy Initialization

1:procedure init(kanjis $k_{1},k_{2}$,distance function $d$)

2: $\text{map}\leftarrow\text{new array($m$)}$

3: for $i\leftarrow 1,n$ do

4: $\text{map}[i]\leftarrow-1$

5: end for

6: $\text{free}\leftarrow\\{1,\ldots,n\\}$

7: for $i\leftarrow 1,m$ do

8: $\text{min}_{\text{dist}}=\textsc{Maxvalue}$

9: $\text{min}_{j}=-1$

10: for $j\leftarrow 1,n$ do

11: if $j\in\text{free}\textbf{ and
}d(k_{1}[i],k_{2}[j]<\text{min}_{\text{dist}}$ then

12: $\text{min}_{\text{dist}}=d(k_{1}[j],k_{2}[i])$

13: $\text{min}_{j}=j$

14: end if

15: end for

16: $\text{free}\leftarrow\text{free}\setminus\\{\text{min}_{j}\\}$

17: $\text{map[$\text{min}_{j}$]}=i$

18: end for

19: return $map$

20:end procedure

Algorithm 2 $L$-Iterative Improvement

1:procedure improvement(kanji $k_{1},k_{2}$,distance function $d$)

2: $\text{map}\leftarrow\textsc{init}(k_{1},k_{2},d)$

3: for $1,\ldots,L$ do

4: for $i\leftarrow 1,\text{map.length}$ do

5: if $\text{map}[i]\not=-1$ then

6: $d_{\text{ii}}\leftarrow d(k_{1}[i],k_{2}[\text{map[i]}])$

7: for $j\leftarrow 1,\text{map.length}$ do

8: if $\text{map}[i]\not=-1$ then

9: if $\text{map}[j]\not=-1$ then

10: $d_{\text{jj}}\leftarrow d(k_{1}[j],k_{2}[\text{map[j]}])$

11: $d_{\text{ij}}\leftarrow d(k_{1}[j],k_{2}[\text{map[i]}])$

12: $d_{\text{ji}}\leftarrow d(k_{1}[i],k_{2}[\text{map[j]}])$

13: if $d_{\text{ji}}+d_{\text{ij}}<d_{\text{ii}}+d_{\text{jj}}$ then

14: $\text{mapj}=\text{map}[j]$

15: $\text{map}[j]=\text{map}[i]$

16: $\text{map}[i]=\text{mapj}$

17: $d_{\text{ii}}=d_{\text{ij}}$

18: end if

19: else

20: $d_{\text{ij}}\leftarrow d(k_{1}[j],k_{2}[\text{map[i]}])$

21: if $d_{\text{ij}}<d_{\text{ii}}$ then

22: $\text{map}[j]=\text{map}[i]$

23: $\text{map}[i]=-1$

24: $d_{\text{ii}}=d_{\text{ij}}$

25: end if

26: end if

27: end if

28: end for

29: end if

30: end for

31: end for

32: return $map$

33:end procedure

Two examples are given in the style of [13]. Originally they illustrated the
complementary nature of EMD and DMD, and here it is shown how iterative
improvement succeeds in both cases. For the ease of illustration, the examples
consider strokes that contain only one point. Also for simplicity, the
distance between two strokes is defined as the manhattan distance between the
corresponding two points, and for that the example is slightly modified
compared to the original example.

###### Example 1

Consider the left example of Figure 2. Greedy initialization results in the
following stroke map: $m[1]=2,\;m[2]=3,\;m[3]=1.$ Here the index of the array
denotes a stroke of $k_{1}$, and the content is a stroke of $k_{2}$: Next,
Algorithm 2 iterates over strokes of $k_{1}$, and tests whether switching
strokes decreases overall cost. First:

$\displaystyle d(1,m[1])+d(2,m[2])\overset{?}{<}d(1,m[2])+d(2,m[1])$

Since $4+4<7+5$, nothing is changed. The next comparison is:

$\displaystyle d(1,m[1])+d(3,m[3])\overset{?}{<}d(1,m[3])+d(3,m[1])$

Since $4+12=16\not<6+8=14$, the assignments are switched and result in
$m[1]=1,\;m[2]=3,\;m[3]=2.$ It is not difficult to see that one additional
iteration will result in the optimal assignment $m[1]=1,\;m[2]=2,\;m[3]=3$.

###### Example 2

Consider the right example of Figure 2. Greedy initialization results in:
$m[1]=1,\;m[2]=2.$ The first step of iterative improvement compares

$\displaystyle d(1,m[1])+d(2,m[2])\overset{?}{<}d(1,m[2])+d(2,m[1])$

Since $3+4=7\not<4+1=5$, the optimal map $m[1]=2,\;m[2]=1$ is immediately
found.

##  5 Recognition Algorithm

Putting all previous sections together and taking into account the original
approach by [13], the algorithm presented below is used for recognition. The
input is an unknown kanji $k$. It is assumed that templates
$t_{1},t_{2},\ldots$ exist, where one templates corresponds to one unique
kanji character.

###  5.1 Recognition Algorithm

Interpolation: The input kanji’s resolution might not be dense enough. For
example for a straight line, only the input and end coordinate might be
specified. To get a higher resolution, intermediate points between each given
point and its successor are computed using Bresenham’s line algorithm.

Normalization: The input kanji is normalized to an area of 256x256 pixels. To
avoid excessive distortions for kanji characters that have a large difference
w.r.t. length and heigth (such as e.g. 一), linear normalization is used
whenever 3*heigth $>$ width or vice versa. Otherwise one of the following is
used: linear normalization, moment normalization, normalization by line
density equalization, or normalization by dot density equalization with
$\alpha=2,3$ or $4$.

Interpolation: Normalization can decrease the resolution, and thus again
intermediate points are interpolated using Bresenham’s line algorithm.

Feature Point Extraction: For each stroke, feature points are extracted. The
initial and end point of a stroke are always extracted. Intermediate points
are extracted in a way such that the euclidian distance between two
consecutive points is close to a fixed global value. In the implementation, a
fixed value of 20.0 is used. The result of this step is a kanji $k^{\prime}$
with the same number of strokes as the input kanji, but each stroke has a much
lower number of (extracted feature) points.

Coarse Classification: It is assumed that each template has been preprocessed
in the same way as described above. Next coarse classification finds a
predefined set (in our implementation: 100) of candidates, in the following
way:

For each template $t$, a stroke map of $k^{\prime}$ and $t$ is computed.
First, the stroke map is initialized by Algorithm 1, and improved in $L$ steps
by Algorithm 2. In both cases endpoint distance is used. If both $k^{\prime}$
and $t$ have the same number of strokes, the overall endpoint distance between
$k^{\prime}$ and $t$ is calculated using the computed stroke map. Otherwise,
the stroke map $m$ is completed in the following way:

  1. 1.

Let $(i,m[i])$ be the smallest $i$ where $m[i]\not=-1$. Then all strokes $j<i$
are mapped to $m[i]$.

  2. 2.

Let $(i,m[i])$ be the largest $i$ such that $m[i]\not=-1$ and all $j>i$ have
$m[j]=-1$. Then all strokes $j>i$ are mapped to $m[i]$.

  3. 3.

Suppose that there are $i,j$ with $j>i$, $m[i]\not=-1$, $m[j]\not=-1$, and for
all $k$ with $i<k<j$ there is $m[k]=-1$. A split point $l$ can be chosen among
all $k$ in the following way: $m[k]$ is set to $m[i]$ for all $k\leq l$, and
$m[k]$ is set to $m[j]$ for all $k>l$. The split point $l$ is chosen in a way
such that the overall computed distance is minimal.

The result of the coarse classification are those 100 templates, that yield
the smallest overall $n-m$ stroke correspondence between $k^{\prime}$ and the
template with the above computed stroke map using the endpoint distance
measure.

Fine Classification: During fine classification, ten templates are chosen
among those 100 that are selected by coarse classification. First a stroke map
between $k^{\prime}$ and each template is computed using Algorithm 1 and 2
with the initial distance measure. If template and $k^{\prime}$ do not possess
the same number of strokes, the stroke map is completed as in coarse
classification. However instead of using the endpoint distance measure, the
following approach is used:

  1. 1.

If the input $k^{\prime}$ has less than a predefined number $S$ of strokes,
then the stroke map is completed using the directional distance measure.

  2. 2.

Otherwise, the whole-whole distance measure is used. The predefined number is
chosen empirically, cf. Table 2.

Finally a weight for each template is computed. Let
$\gamma=\gamma_{1},\ldots,\gamma_{m}$. Below, $W_{k^{\prime},t,\gamma,d}$ is
written for $\sum_{1\leq i\leq m}\gamma_{i}\cdot d(\mathsf{conc}(\\{s\mid
f(s)=t_{i}\\},t_{i}).$ Using the above computed stroke map, the following
weight $W$ is computed:

$W=\begin{cases}\frac{1}{\text{min}(n,m)}W_{k^{\prime},t,\gamma,d_{\mathsf{ww}}}&\text{if
$k^{\prime}$ has less than $S$ strokes}\\\\[10.00002pt]
\frac{1}{\text{min}(n,m)}W_{k^{\prime},t,\gamma,d_{\mathsf{dd}}}&\text{if
$k^{\prime}$ has less than $S$ strokes}\end{cases}$

Here, for two strokes $s_{i},t_{i}$ containing $l$ and $o$ points,
$\gamma_{i}=\text{max}(l,o)/\text{min}(l,o)$, if $s_{i}$ or $t_{i}$ resulted
from concatenation, and $\gamma=1.0$, otherwise. The result of the fine
classification are those ten templates, that yield the lowest weights $W$.

Table 1: Comparison of different normalization methods.

| Linear | Moment | DotDensity | DotDensity | DotDensity | LineDensity
---|---|---|---|---|---|---
|  |  | $\alpha=2$ | $\alpha=3$ | $\alpha=4~{}$ |
Kanji (79) |  |  |  |  |  |
Top 1 | 63 | 62 | 61 | 62 | 60 | 60
Top 5 | 72 | 73 | 70 | 71 | 72 | 70
Top 10 | 74 | 75 | 73 | 73 | 74 | 71
Hiragana (46) |  |  |  |  |  |
Top 1 | 30 | 37 | 35 | 33 | 29 | 26
Top 5 | 43 | 44 | 45 | 45 | 45 | 49
Top 10 | 45 | 45 | 45 | 45 | 45 | 32
Katakana (46) |  |  |  |  |  |
Top 1 | 32 | 41 | 32 | 33 | 32 | 35
Top 5 | 46 | 46 | 46 | 46 | 46 | 46
Top 10 | 46 | 46 | 46 | 46 | 46 | 46

Table 2: Comparison of DMD, EMD, and iterative improvement. | Stroke Linking Algorithm
---|---
| Kanji (79) | Timing (ms)
| Top1 | Top5 | Top10 | Min. | Max. | Avg.
Original [13] |  |  |  |  |  |
DMD | 62 | 73 | 74 | 5 | 207 | 16
EMD | 59 | 68 | 71 | 4 | 135 | 13
combined | 62 | 73 | 75 | 7 | 294 | 24
$L$-Iterative Improvement |  |  |  |  |
(1,1) | 59 | 68 | 73 | 4 | 137 | 16
(1,2) | 62 | 73 | 75 | 4 | 136 | 15
(1,3) | 62 | 73 | 75 | 4 | 142 | 18
(2,1) | 59 | 69 | 73 | 5 | 148 | 19
(2,2) | 62 | 73 | 75 | 5 | 171 | 21
(2,3) | 62 | 73 | 75 | 5 | 171 | 22
(3,1) | 59 | 69 | 73 | 6 | 168 | 25
(3,2) | 62 | 73 | 75 | 6 | 168 | 26
(3,3) | 62 | 73 | 75 | 6 | 176 | 28
Table 3: Overall performance, and directional stroke distance measure. |  | Directional vs. Whole-Whole |
---|---|---|---
|  zinnia | S=0 | S=1 | S=2 | S=3 | S=4 | S=5
Kanji (79) |  |  |  |  |  |  |
Top 1 | 36 | 63 | 63 | 63 | 62 | 61 | 61
Top 5 | 46 | 76 | 76 | 76 | 76 | 76 | 74
Top 10 | 47 | 76 | 76 | 76 | 76 | 76 | 74
Hiragana (46) |  |  |  |  |  |  |
Top 1 | 27 | 35 | 35 | 34 | 33 | 33 | 33
Top 5 | 35 | 42 | 42 | 43 | 43 | 45 | 45
Top 10 | 37 | 44 | 44 | 46 | 46 | 46 | 46
Katakana (46) |  |  |  |  |  |  |
Top 1 | 34 | 37 | 37 | 39 | 44 | 46 | 46
Top 5 | 41 | 45 | 45 | 45 | 46 | 46 | 46
Top 10 | 42 | 45 | 45 | 45 | 46 | 46 | 46

##  6 Experiments

To evaluate the implemented recognition algorithm, 2264 templates were
created. This set contains one template each for all _jouyou kanji_ (kanji
characters for every day use defined by the Japanese Ministry of Education),
as well as one template each for all hiragana and katakana characters. To test
the recognition performance, a test set of 79 characters was prepared. These
include 49 characters from the distribution of Tegaki-
Lab333https://github.com/cburgmer/tegaki/tree/master/tegaki-lab, and the
remaining characters include various characters that were deliberately written
in a sloppy semi-cursive style with stroke concatenations on the one hand, and
on the other hand with mistakes in stroke order and style that a typical
foreign learner of the language would make. Normalization experiments and
stroke linking experiments were conducted with a graphical prototype
application written in Java. The recognition part was then ported to pure C,
and the remaining experiments were done with that C-Library. All tests were
run on an Intel Core i5 @ 2.5 Ghz with 8 GB RAM running Mac OS X 10.9.4.

#### Normalization Methods

For normalization, the recognition method described in Section 3 was used. For
fine classification, only the initial stroke distance (as the input to
Algorithm 1 and 2) as well as whole-whole stroke distance (for computation of
the weights) was used. The directional stroke distance was not utilized. The
results are depicted in Table 1. Whereas in statistical classification using
directional features non-linear normalization is known to significantly
improve recognition performance [2], contrary to what was conjectured by [13],
the recognition performance is actually not increased by non-linear
normalization methods. In fact for kanji characters, simple linear
normalization outperforms all non-linear normalization methods. On the other
hand, when it comes to hiragana and katakana characters, which are more
similar in style to western handwriting, it can be seen that moment
normalization significantly outperforms all other methods. The performance of
non-linear normalization methods can be explained by the fact that they put
more emphasis on and unify directional features at the cost of introducing
distortions. Statistical classification methods that depend on directional
features are not affected by this, but the distortions cause misrecognition
for template matching. Thus in the implemented library and in further
experiments, moment normalization was used due to its good overall
performance.

###  6.1 Stroke Linking Algorithms

Next the performance of $L$-iterative improvement was tested. Fine
classification was conducted with the same distance measures as in the
previous section. However computation of the stroke map was done once with the
algorithms by [13], i.e. only DMD, only EMD, and combined, and once with
iterative improvement. The results are depicted in Table 2. Note that each
combination is run twice, once for the computation of a stroke map during
coarse classification and fine classification each. The first (second) number
in brackets for iterative improvement denote what the value $L$ was set to
during coarse (fine) classification.

As can be seen, DMD itself performs quite well but fails in some examples. EMD
itself performs not very well, but complements DMD and improves overall
recognition performance. As for $L$-iterative improvement, a combination of
$L=(1,2)$ suffices to recognize all those characters that can be recognized by
DMD & EMD. But the average recognition time compared to the combination of DMD
& EMD is improved by $(1,2)$-iterative improvement by more than one third, and
for particular time intensive characters with a large number of strokes, the
maximal recognition time is decreased by more than 50 percent.

###  6.2 Overall Performance and Directional Stroke Distance

Last, the recognition part of the Java prototype was ported to C. Due to
different rounding results, especially w.r.t. to feature point extraction,
slightly different recognition results compared to the Java prototype were
obtained. Coarse classification was run with endpoint distance and $3$
iterative improvement, and fine classification was run also with $3$ iterative
improvement but initial distance to get an $n-n$ strokemap, and the the stroke
map was completed either using directional distance if the input character has
less than $S$ strokes, or by using using directional distance, otherwise.
Also, the performance was compared to the open-source online Japanese
handwriting recognition library Zinnia, which uses a learning based approach
with support vector machines. Zinnia was trained with exactly the same
templates, and the same test data was supplied for recognition. The results
are depicted in Table 3. As can be seen, a larger factor of $S$ improves
recognition for hiragana and katakana characters, since they can be better
distinguished using directional features. On the other hand, recognition
performance of kanji characters decreases slightly. Nevertheless, the
presented template based matching approach significantly outperforms the
learning based approach of Zinnia, which performs poorly due to having only
one training sample per character.

##  7 Conclusion and Future Work

Ideally, a large set of training samples for Japanese on-line character
recognition would be available under an open-source (BSD-style) license, and a
learning based approach could then be used for open-source Japanese on-line
handwriting recognition. Since this is not the case, and such a database is
unlikely to appear in near future due to the significant cost and logistics
required, the focus here was on a template based matching approach. By
empirically studying different normalization methods, extending the original
approach by a new distance measure, and simplifying and unifying the
underlying stroke linking algorithms, a fast and highly accurate
implementation was achieved. Moreover it could be shown that in the present
test set, the template based approach significantly outperforms competing
learning-based implementations.

## References

  * [1] Casey, R.: Moment normalization of handprinted characters. IBM Journal of Research and Development 14(5), 548–557 (Sep 1970)
  * [2] Kawamura, A., Yura, K., Hayama, T., Hidai, Y., Minamikawa, T., Tanaka, A., Masuda, S.: Online recognition of freely handwritten Japanese characters using directional feature densities. In: Pattern Recognition, 1992. Vol.II. Conference B: Pattern Recognition Methodology and Systems, Proceedings., 11th IAPR International Conference on. pp. 183–186 (Aug 1992)
  * [3] Kimura, F., Takashina, K., Tsuruoka, S., Miyake, Y.: Modified quadratic discriminant functions and the application to Chinese character recognition. Pattern Analysis and Machine Intelligence, IEEE Transactions on PAMI-9(1), 149–153 (Jan 1987)
  * [4] Lee, S.W., Park, J.S.: Nonlinear shape normalization methods for the recognition of large-set handwritten characters. Pattern Recognition 27(7), 895 – 902 (1994)
  * [5] Liu, C.L., Marukawa, K.: Pseudo two-dimensional shape normalization methods for handwritten Chinese character recognition. Pattern Recognition 38(12), 2242 – 2255 (2005)
  * [6] Liu, C.L., Yin, F., Wang, D.H., Wang, Q.F.: CASIA online and offline Chinese handwriting databases. In: Proceedings of the 2011 International Conference on Document Analysis and Recognition. pp. 37–41. ICDAR ’11 (2011)
  * [7] Liu, C.L., Yin, F., Wang, Q.F., Wang, D.H.: ICDAR 2011 Chinese handwriting recognition competition. In: Document Analysis and Recognition (ICDAR), 2011 International Conference on. pp. 1464–1469 (Sept 2011)
  * [8] Nakagawa, M., Matsumoto, K.: Collection of on-line handwritten Japanese character pattern databases and their analyses. Int. J. Doc. Anal. Recognit. 7(1), 69–81 (2004)
  * [9] Rowley, H., Goyal, M., Bennett, J.: The effect of large training set sizes on online Japanese Kanji and English cursive recognizers. In: Frontiers in Handwriting Recognition, 2002. Proceedings. Eighth International Workshop on. pp. 36–40 (2002)
  * [10] Saito, T., Yamada, H., Yamomoto, K.: On the data base ETL9 of handprinted characters in JIS chinese characters and its analysis (in japanese). Transactions IECE Japan J68(D(4)), 757–764 (1985)
  * [11] Shin, J.p.: Optimal stroke-correspondence search method for on-line character recognition. Pattern Recogn. Lett. 23(5), 601–608 (Mar 2002)
  * [12] Tsukumo, J., Tanaka, H.: Classification of handprinted Chinese characters using nonlinear normalization and correlation methods. In: Pattern Recognition, 1988., 9th International Conference on. pp. 168–171 vol.1 (Nov 1988)
  * [13] Wakahara, T., Suzuki, A., Nakajima, N., Miyahara, S., Odaka, K.: On-line cursive kanji character recognition as stroke correspondence problem. In: Document Analysis and Recognition, 1995., Proceedings of the Third International Conference on. vol. 2, pp. 1059–1064 (Aug 1995)
  * [14] Wakahara, T., Suzuki, A., Nakajima, N., Miyahara, S., Odaka, K.: Stroke-number and stroke-order free on-line kanji character recognition as one-to-one stroke correspondence problem. IEICE Transactions on Information and Systems E79-D(5), 529–534 (1996)
  * [15] Yamada, H., Yamamoto, K., Saito, T.: A nonlinear normalization method for handprinted kanji character recognition—line density equalization. Pattern Recognition 23(9), 1023 – 1029 (1990)