Font Distribution Observation by
Network-Based Analysis
Chihiro Nakamoto1 , Rong Huang1 , Sota Koizumi1 , Ryosuke Ishida1 ,Yaokai Feng2 , and Seiichi Uchida2
1

Graduate School of Information Science and Electrical Engineering,
Kyushu University, Fukuoka 819-0395, Japan{nakamoto,rong,koizumi,ishida}@human.ait.kyushu-u.ac.jp
2
Faculty of Information Science and Electrical Engineering,
Kyushu University, Fukuoka 819-0395, Japan{fengyk,uchida}@ait.kyushu-u.ac.jp
http://human.ait.kyushu-u.ac.jp/index.html

Abstract. The off-the-shelf Optical Character Recognition (OCR)
engines return mediocre performance on the decorative characters whichusually appear in natural scenes such as signboards. A reasonable way
towards the so-called camera-based OCR is to collect a large-scale font
set and analyze the distribution of font samples for realizing some character recognition engine which is tolerant to font shape variations. This
paper is concerned with the issue of font distribution analysis by network.
Minimum Spanning Tree (MST) is employed to construct font networkwith respect to Chamfer distance. After clustering, some centrality criterion, namely closeness centrality, eccentricity centrality or betweenness
centrality, is introduced for extracting typical font samples. The network
structure allows us to observe the font shape transition between any
two samples, which is useful to create new fonts and recognize unseen
decorative characters. Moreover, unlike the Principal Component Analysis (PCA), the font network fulfills distribution visualization throughmeasuring the dissimilarity between samples rather than the lossy processing of dimensionality reduction. Compared with K-means algorithm,
network-based clustering has the ability to preserve small size font clusters which generally consist of samples taking special appearances. Experiments demonstrate that the proposed network-based analysis is aneffective way to grasp font distribution, and thus provides helpful information for decorative character recognition.
Keywords: font distribution, minimum spanning tree, centrality criterion, network-based clustering

1

Introduction

Optical Character Recognition (OCR) techniques have achieved great success inthe field of scanner-based document image analysis. However, as demonstrated
by Epshtein et al. in [1], OCR engines were thwarted in the scene character2

C. Nakamoto, R. Huang, S. Koizumi et al.

Fig. 1: Scene characters captured by camera.

recognition. This is because the scene character appearing on signboards, noticesignage, wrapper, etc. (see Fig.1), is usually designed by special decoration with
the intent to attract people’s attention. On the other hand, since camera is far
handier than scanner, camera-based OCR, which focuses on recognizing characters captured by camera, will not only extend new applications of OCR but also
brings convenience to us in our daily life. In view of this prospect, it has become
an imperative demand to develop the camera-based OCR. However, realizationof a high-performance camera-based OCR is still a hard task, although numerous
impressive methods have been proposed [2–4]. As just mentioned, one of the challenges for scene character recognition lies in the unconstrained appearances withvarious decorations. Therefore, one possible strategy towards the camera-based
OCR is to extract a topological structure that is nearly invariant to decorations.
Along this line of thought, several font-related methods have been elaborately
designed as efforts to narrow the gap between OCR and the decorative character. Zhu et al. [5] presented a font recognizer by using multichannel Gabor filters
and weighted Euclidean distance classifier. Omachi et al. [6] detected ridges andravines from multi-scale images to extract an essential structure of the decorated
character. As a subsequent work, Omachi et al. [7] matched the graphs of theabove-extracted structure and standard patterns to recognize a character image. Unlike relying on the global structure, Wang et al. [8] proposed a series ofpart-based methods which were characterized by the robustness against various
appearances of a character.
Although the above methods fulfilled the decorative character recognition tosome extents, the performance was far from ideal. A straightforward solution for
performance improvement is to collect or enumerate all types of fonts. Unfortunately, this idea is impossible since he/she always can design a new font whichtakes remarkably different shapes compared with the members of the collectedset. As a remedy, we can investigate and analyze a large-scale font set under acertain type of data structure like tree, graph, cluster or network, to grasp theFont Distribution Observation by Network-Based Analysis

3

font distribution so that we can approach the ideal effect of brute-force enumeration.
In this paper, we propose a network-based method built on a large-scale
font set, which allows us to analyze the font distribution in the feature space.
Specifically, the so-called font network is constructed by Minimum Spanning
Tree (MST) algorithm taking each font sample as a node. The dissimilarity between two font samples is measured by the Chamfer distance which has been
widely adopted in the field like template matching [9] and handwritten Chinese
recognition [10]. Merits of our proposal lie in that (1) unlike the well-known
Principal Component Analysis (PCA) which lossily projects feature points onto
low-dimensional space for distribution visualization, the proposed font network
built by linking neighbors can represent the actual font distribution without
information loss or distortion; (2) compared with the conventional K-means algorithm, network-based clustering can generate more reliable font cluster andtypical samples by introducing some clustering criterion (as introduced in 3.4).
This is because K-means is equivalent to Maximum a Posterior (MAP) estimation of a Gaussian mixture distribution while the font distribution is neither aGaussian nor a Gaussian mixture; (3) along a path of the font network, we canunderstand the font shape transition between any two samples, which is useful tocreate new fonts or recognize various scene characters. For example, for a given
decorative character, we can find its neighbours along transition paths of the
font network, and then combines multiple recognition results for a final decision.
All above mentioned merits are demonstrated by the subsequent experiments.
The remainder of the paper is organized as follows. Section 2 gives an introduction about large-scale font set preparation. Section 3 elaborates the detailprocedure of font network construction. In section 4, we conduct experiments andanalysis. Section 5 concludes the whole paper and outlines our future works.

2

Large-Scale Font Set Preparation

This section is devoted to a description of large-scale font set preparation. To
simplify the problem, the proposed font network is only targeted at the capitalalphabet “A” in the current trial. Note that since the process of font network
construction is independent of alphabet class, it is feasible and tractable to further accommodate arbitrary alphabet classes. We totally collected 6930 “A”s
without font duplication, and normalized each one of them to a 200 × 200 binary
image. Figure 2 (a) shows 140 normalized font samples. It should be mentionedthat we manually excluded several highly decorative font samples as well as theones whose main character parts are normal but decorated with various surroundings. We deem this pre-filtering manipulation impartial since even humans
may also be hard to make an explicit judgement whether they belong to alphabet
or not. See the examples of excluded ones in Fig.2 (b).

4

C. Nakamoto, R. Huang, S. Koizumi et al.

Fig. 2: (a) Examples of normalized font samples. (b) Examples of excluded font samples.

3

Font Network Construction

This section introduces the procedure of font network construction based on the
prepared large-scale font set. We adopt MST algorithm to build network andChamfer distance to measure the dissimilarity between two font samples. To
grasp the font distribution, font clusters and typical font samples on the network
are then extracted via introducing a distance threshold and some clustering
criterion.
3.1

Minimum Spanning Tree

Minimum Spanning Tree (MST) also called minimum weight spanning tree is apivotal concept in graph theory. Given a connected, undirected graph G(V, E)
with vertices v ∈ V and edges (vi , vj ) ∈ E corresponding to pairs of neighboring
vertices, a spanning tree T (V, E ′ ) of that graph G is a subgraph, namely E ′ ⊆E, so that all pairs of the vertices are connected by one and only one path.
Obviously, a graph can generate many different spanning trees. By assigning aweight w(vi , vj ) to each edge, MST can then be defined as a spanning tree thathas the minimal sum of the weights of the edges E ′ . In our proposal, font samples
in the large-scale set serve as vertices, and the Chamfer distance (see details in3.2) between vi and vj is regarded as the weight w(vi , vj ). We adopt Prim’s
algorithm [11] to construct MST on the large-scale font set, which iteratively

Font Distribution Observation by Network-Based Analysis

5Fig. 3: Visual structure of a font network (MST).

adds edges with smallest weights in a greedy matter, and runs in polynomial
time.
The advantages of using MST can be summarized as follows: (1) MST not
only reflects the global structure of the set via spanning all font samples, but also
naturally guarantees that each local edge connects two font samples which aremost similar to each other; (2) the path between two vertices allows us to observe
the font shape transition; (3) without using dimension reduction projection, MST
well preserves the dissimilarity between two font samples and reliably provides
a visual network structure of the font feature space (see Fig.3); (4) as one typeof network structure, MST is compatible with general graph or network theory.
3.2

Chamfer DistanceIn this proposal, Chamfer distance [12] is employed to reliably measure thedissimilarity between two font samples and the resulting value serves as theweight w(vi , vj ) for MST construction. Unlike some naive distance measurement
which directly accumulates the absolute difference of pixel intensities, Chamferdistance is average nearest distance from one image to another one so that it ismore applicable to shape matching. In the practical algorithm implementation,
distance transform is employed to reduce the computational cost of calculating
Chamfer distance. This is because distance transform directly stored the wanted
nearest distance by labeling each pixel of the image with the distance to thenearest boundary pixel as displayed in Fig.4. More specifically, given two font

6

C. Nakamoto, R. Huang, S. Koizumi et al.

(a)
















































































































































































(b)
Fig. 4: Examples of distance transform. (a) An actual example (left = original image;right = distance map). (b) Artificial examples where the numbers in the table standfor distance values (left = a capital alphabet “I”; middle = a capital alphabet “F”;
right = a number “1”).

samples P and Q which are binary images of size 200 × 200, p and q denote thecorresponding distance maps, respectively. The Chamfer distance is computed
as follows:
DChamfer(P, Q) = max(dα , dβ )dα =Pd(P (i, j); q)
and dβ =B(P )Pd(Q(i, j); p)
B(Q)where B(P ) counts the number of black pixels of an image P . The operatord(P (i, j); q) is defined asq(i, j) if P (i, j) = 0 (black pixel)d(P (i, j); q) =0
otherwise
where P (i, j) represents the pixel value in the position (i, j) of an image P . As
we can see, the nearest distance can be obtained by visiting the same positionof the corresponding distance map. Thus, distance transform helps reduce thecomputational complexity to the level of look-up table in the course of calculation.

Font Distribution Observation by Network-Based Analysis

7

Fig. 5: The internal structures of four clusters.

3.3

Network-Based Clustering

To well grasp the font distribution, we propose a network-based clustering, bywhich font samples with short Chamfer distances to each other are grouped
together. In doing so, a coarser overview of the original font network (MST) canbe obtained that allows us to investigate its global configuration on different
scales. The local details are reflected in the fact that font samples within acluster share similar shape. Note that both the global configuration and the
local details indicate the distribution of the large-scale font set. Moreover, toeffectively represent and observe font clusters, we utilize some centrality criterion(see details in 3.4) to extract typical font samples.
The clustering starts with setting a distance threshold TD . Then, traverse
the vertices throughout the font network. If w(vi , vj ) ≤ TD , the vertices vi andvj are grouped into a same font cluster.
Network-based clustering preserves the internal structure of each cluster asshown in Fig.5, and thus allows us to locally observe the font shape transitioneven after the clustering. More importantly, small size clusters survive fromthe network-based clustering as long as these clusters are essentially away fromothers in terms of Chamfer distance. On the contrary, K-means algorithm isapproximately equally divided the whole feature space into several clusters so

8

C. Nakamoto, R. Huang, S. Koizumi et al.

   

     ! " 

    



Fig. 6: An illustration indicating the different performance between the network-based
clustering and the K-means algorithm. Experimental results of comparative study canbe found in Table 1.

that scattered font samples with special shape are forced to merge into dissimilarlarge clusters. This contrast is illustrated in Fig.6 and a subsequent experiment.
Here, the size of a cluster refers to the number of samples belonging to thatcluster.

3.4

Typical Font Sample Extraction by Centrality Criterion

To extract a typical font sample from each cluster, this subsection introduces
three centrality criteria, namely closeness centrality, eccentricity centrality andbetweenness centrality, which are widely employed in the network analysis [13].
The centrality criterion estimates the degree of center for each vertex, and returns comparable scores. In this proposal, we adopt the centrality criterion to
extract the typical font sample from each cluster. In the following, three centrality criteria are explained in turn.
Closeness centrality is based on the natural distance metric between all pairsof vertices as given below.
n−1, i = 1, 2, · · · , n,
j=1 d(vi , vj )CC (vi ) = Pn

where n denotes the size of a font cluster. The distance d(vi , vj ) takes the sumof w(vi , vj ) along the path from vi to vj . Recall that w(vi , vj ) is the Chamferdistance between two directly connected vertices. A vertex vi with largest CC (vi )is considered as the typical font sample.

Font Distribution Observation by Network-Based Analysis

9Fig. 7: Font shape transition along paths.

Eccentricity centrality selects the center sample by comparing all pairs of
maximum distances. That is
CE (vi ) =1, i, j = 1, 2, · · · , n.
max d(vi , vj )The denominator max d(vi , vj ) can be defined as the degree of eccentricity sothat a larger CE (vi ) indicates a more compact extent that the vertices vj (wherej = 1, 2, · · · , n) gather around vi .
Betweenness centrality quantifies the number of times that a vertex acts
as a bridge along the path between two other vertices. More specifically, thebetweenness centrality can be represented as follows.
CB (vi ) =Xn

s6=i6=t=1

σvs vt (vi ), i = 1, 2, · · · , n,σvs vtwhere σvs vt is total number of edges from vs to vt (∀s 6= t ∈ {1, 2, · · · , n}) andσvs vt (vi ) accumulates the number of times that all these paths pass through vi .
The betweenness centrality relies on the natural fact that the center vertex has
a greater opportunity to be passed through by paths. Therefore, the vertex vi
having the largest CB (vi ) corresponds to the typical font sample.

10

C. Nakamoto, R. Huang, S. Koizumi et al.

<
;
3
:
9
8
7
6
+
2
5
4
3
2
1
0
/
.
,
+

#$%&$' ($)%$$*

Fig. 8: Vertex degree histogram.

4

Experiment and Analysis

4.1

Font Network

In this experiment section, the MST algorithm and the Chamfer distance wereapplied to construct the font network of the large-scale alphabet “A” set. The
global structure of the built network was displayed in Fig.3. Further, according
to the metric of dissimilarity, the network-based clustering algorithm divided
the feature space into several clusters without affecting their internal structures(see Fig.5). In addition, figure 7 exhibited the font shape transition between two
vertices, which was useful to generate new fonts or recognize various scene characters. It was worthwhile to point out that we could still observe the font shapetransition even after the clustering processing, which benefited from the above
mentioned structure preservation property. Moreover, after introducing some
centrality criterion like closeness centrality, eccentricity centrality or betweenness centrality, the typical font sample could be extracted from each cluster.
Note that the typical font sample provided an effective representation for eachfont cluster. All above investigations allowed us to grasp the distribution of alarge number of font samples.
4.2

Vertex Degree Histogram

The degree of a vertex is defined as the number of edges incident to the vertex.
Figure 8 showed the histogram of vertex degree and provided another aspect ofFont Distribution Observation by Network-Based Analysis

11

(a)

(b)
Fig. 9: The hub font samples. (a) The font samples having degree 7; (b) the font samples
having degree 8.

the font distribution. As we could see, the maximum vertex degree is eight. In
addition, the number of vertices diminished with the increase of degree, which
implied that the vertices having highest degree could be considered as the hubs ofa network. See the hub font samples in Fig.9. Note that the hub font samples weredifferent from the typical ones. The former was selected from the whole networkand reflected the global distribution while the latter was the local representative
extracted from each font cluster using some centrality criterion.
4.3

Font Cluster

Since the distance threshold TD had a great impact on clustering, in this subsection, we analyzed the configuration evolution of font clusters. We displayed theevolution of the maximum size and the number of clusters versus the increase of
TD in Fig.10, which demonstrated the existence of the font cluster.
Table 1 listed the size of the top five largest font clusters with respect to eachdistance threshold TD . Furthermore, the result of K-means algorithm (K =5) was given in the last row of Table 1. The results listed in Table 1, also
illustrated in Fig.6, indicated that the network-based clustering could preserve
small size font clusters which contained samples taking special shapes, while
K-means approximatively equally divided the feature space.
4.4

Typical Font Sample

Typical font samples were extracted by introducing some centrality criterion,
namely closeness centrality, eccentricity centrality or betweenness centrality, as
described in 3.4. The selected font samples from the top five largest clusters were
exhibited in Fig.11. The digits printed above each sub-picture stood for the sizeof the cluster from which the typical font sample was extracted. As we could
observe, when the distance threshold TD was small, for example TD = 0.30, the12

C. Nakamoto, R. Huang, S. Koizumi et al.

[
\
]
^

Z
U
P
N
Z
R
Y
X
W
V
U
P
T

_
`
a
^
b
^
c
a
d
]
e
f
g
h
b
c
[
]
i
c

S
R
Q
P
O
N

=>?@ABCD @EFD?EGH= IJ KGF CHL?@DF>BMj klm nopqmr st uvowkmrw
jklm pxyzpop wz{m st uvowkmrw

Fig. 10: The evolution of the maximum size and the number of clusters versus theincrease of TD .

typical font samples shared small dissimilarity to each other. With the increaseof TD , the great dissimilarity among the typical font samples emerged as shownin Fig.11 (c). Moreover, the typical font sample from the largest cluster shared
the similar standard shape regardless the change of TD , which indicated that nomatter how protean a font sample was, its appearance would hold approximately constant structures. In addition, applying three centrality criteria leaded tosimilar results. In other words, centrality criterion would not sharply affect theprocess of typical font sample extraction.

5

Conclusion

In this paper, we analyze the font distribution of a large-scale set by network,
which opens a new door to the camera-based OCR engines. To construct the font
network, we adopt MST algorithm under the dissimilarity measurement using
Chamfer distance. Font clusters are formed though setting distance threshold.
After that, we extract typical font samples from clusters by introducing some
centrality criterion, namely closeness centrality, eccentricity centrality and betweenness centrality. Benefitting from the network structure, both the global
configuration and the font shape transition can be observed. Compared with theFont Distribution Observation by Network-Based Analysis

|}}

~~



}



Closeness centrality

Eccentricity centrality

Betweenness centraility(a) Distance threshold TD = 0.30.











Closeness centrality

Eccentricity centrality

Betweenness centraility(b) Distance threshold TD = 0.60.











Closeness centrality

Eccentricity centrality

Betweenness centraility(c) Distance threshold TD = 1.25.

Fig. 11: The typical font samples extracted by centrality criterion.

13

14

C. Nakamoto, R. Huang, S. Koizumi et al.
Table 1: The size of font clusters.




¢£

¤¥¦

§¨©

ª«©

¬¦­

®¦­

¯°¤¯

¤¯

±

²

³

®

¯°§¯

³²

³³

ª²

ª§

§ª

¯°ª¯

®³³

¤¤¬

ªª

§³

§¬

¯°ª®

²´³

§ª±

³ª

§¤

¤±

¯°¬®

¤³ª¯

§³

§§

§§

§§

¯°³¯

§®³¯

¤´

¤±

¤²

¤³

¯°²¯

§´®ª

§®

¤±

¤±

¤²

¯°±¯

ªªª¯

¬§

¤±

¤²

¤²

¤°¯¯

ª´®²

²´

¤²

¤¬

¤¯

¤°§®

¬¬³´

´²

¤²

¤¯

¤¯

¤°³®

®¤¬´

§ª

¤¯

¤¯

¤¯

§°§®

®±¤³

§±

¤¤

±

±

ª°§®

³¬¯ª

³

³

®

®

®°¯¯

³±¤ª

®

ª

ª

§

· ¸ ®

§¤§±

¤¬¬¬

¤ª¯±

¤¤§±

´§§

 ¡µ¶ conventional PCA, the proposed font network realizes distribution visualization
through Chamfer distance rather than the process of dimensionality reduction.
Moreover, as verified by experiments, the network-based clustering preserves
small size font clusters, while K-means algorithm will produce an approximately
equal division. The existence of font cluster and the effectiveness of networkbased analysis are also demonstrated by experiments. Our future work is to
extract the internal structures from font clusters, and to design regularization
approaches based on the path of font shape transition.

Acknowledgment
The authors would like to thank the support of Creation of Human-Harmonized
Information Technology for Convivial Society, which is a CREST project organized by Japan Science and Technology Agency (JST).

Font Distribution Observation by Network-Based Analysis

15

References
1. B. Epshtein, E. Ofek, and Y. Wexler, Detecting Text in Natural Scenes with Stroke
Width Transform, IEEE Conference on Computer Vision and Pattern Recognition,
2010.
2. K. Wang and S. Belongie, Word Spotting in the Wild, European Conference on
Computer Vision, 2010.
3. K. Wang, B.Babenko and S. Belongie, End-to-End Scene Text Recognition, IEEE
International Conference on Computer Vision, 2011.
4. A. Mishra, K. Alahari and C. Jawahar, Top-Down and Bottom-Up Cues for Scene
Text Recognition, IEEE Conference on Computer Vision and Pattern Recognition,
2012.
5. Y. Zhu, T. Tan, and Y. Wang, Font Recognition Based on Global Texture Analysis,IEEE Transactions on Pattern Analysis and Machine Intelligence, vol.23, no.10,
pp.1192-1200, 2001.
6. S. Omachi, M. Inoue, and H. Aso, Structure Extraction from Decorated Characters Using Multiscale Images, IEEE Transactions on Pattern Analysis and MachineIntelligence, vol.23, no.3, pp.315-322, 2001.
7. S. Omachi, S. Megawa, and H. Aso, Decorative Character Recognition by Graph
Matching, IEICE Transactions on Information and Systems, vol.E90-D, no.10,
pp.1720-1723, 2007.
8. S. Wang, S. Uchida, and M. Liwicki, Part-Based Recognition of Arbitrary Fonts,
International Conference on Document Analysis and Recognition, 2013.
9. G. Borgefors, Hierarchical Chamfer Matching: A Parametric Edge Matching Algorithm, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol.10,
no.6, pp.849-865, 1988.
10. D. Shi, S. Gumm, and R. Damper, Handwritten Chinese Radical Recognition Using Nonlinear Active Shape Models, IEEE Transactions on Pattern Analysis andMachine Intelligence, vol.25, no.2, pp.277-280, 2003.
11. T. Cormen, C. Leiserson, R. Rivest and C. Stein, Section 23.2: The algorithms of
Kruskal and Prim, Introudction to Algorithms, Third Edition, MIT Press, pp.631638, 2009.
12. H. Barrow, J. Tenenbaum, R. Bolles and H. Wolf, Parametric Correspondence andChamfer Matching: Two New Techniques for Image Matching, International Joint
Conference Artificial Intelligence, 1977.
13. T. Opsahl, F. Agneessens and J. Skvoretz, Node Centrality in Weighted Networks:
Generalizing Degree and Shortest Paths, Social Networks, vol.32, no.3, pp.245-251,2010.