SCIENCE CHINA Information Sciences, Volume 62 , Issue 9 : 192102(2019) https://doi.org/10.1007/s11432-018-9724-7

## Graph-matching-based character recognition for Chinese seal images

• AcceptedOct 31, 2018
• PublishedJul 30, 2019
Share
Rating

### References

[1] Roy P P, Pal U, Lladós J. Document seal detection using GHT and character proximity graphs. Pattern Recognition, 2011, 44: 1282-1295 CrossRef Google Scholar

[2] Ren C, Liu D, Chen Y B. A new method on the segmentation and recognition of Chinese characters for automatic Chinese seal imprint retrieval. In: Proceedings of International Conference on Document Analysis and Recognition, 2011. 972--976. Google Scholar

[3] Roy P P, Pal U, Llads J. Seal detection and recognition: an approach for document indexing. In: Proceedings of International Conference on Document Analysis and Recognition, 2009. 101--105. Google Scholar

[4] Yin F, Wang Q F, Zhang X Y, et al. Chinese handwriting recognition competition. In: Proceedings of International Conference on Document Analysis and Recognition, 2013. 1464--1469. Google Scholar

[5] Wang C H, Xiao B H, Dai R W. Parallel compact integration in handwritten Chinese character recognition. Sci China Ser F-Inf Sci, 2004, 47: 89 CrossRef Google Scholar

[6] Guo J, Wang C, Roman-Rangel E. Building Hierarchical Representations for Oracle Character and Sketch Recognition. IEEE Trans Image Process, 2016, 25: 104-118 CrossRef PubMed ADS Google Scholar

[7] Sebastian T B, Klein P N, Kimia B B. Recognition of shapes by editing their shock graphs. In: Proceedings of IEEE International Conference on Computer Vision, 2011. 755--762. Google Scholar

[8] Bai X, Latecki L J. Path similarity skeleton graph matching.. IEEE Trans Pattern Anal Mach Intell, 2008, 30: 1282-1292 CrossRef PubMed Google Scholar

[9] Zhang H, Mu Y, You Y H. Multi-scale sparse feature point correspondence by graph cuts. Sci China Inf Sci, 2010, 53: 1224-1232 CrossRef Google Scholar

[10] Zhang L, Yang Y, Wang M. Detecting Densely Distributed Graph Patterns for Fine-Grained Image Categorization. IEEE Trans Image Process, 2016, 25: 553-565 CrossRef PubMed ADS Google Scholar

[11] Mian A S, Bennamoun M, Owens R. Three-dimensional model-based object recognition and segmentation in cluttered scenes.. IEEE Trans Pattern Anal Mach Intell, 2006, 28: 1584-1601 CrossRef PubMed Google Scholar

[12] Jiang H, Yu S X, Martin D R. Linear Scale and Rotation Invariant Matching.. IEEE Trans Pattern Anal Mach Intell, 2011, 33: 1339-1355 CrossRef PubMed Google Scholar

[13] Zhao R, Martinez A M. Labeled Graph Kernel for Behavior Analysis.. IEEE Trans Pattern Anal Mach Intell, 2016, 38: 1640-1650 CrossRef PubMed Google Scholar

[14] Aksoy E E, Abramov A, Worgotter F, et al. Categorizing object-action relations from semantic scene graphs. In: Proceedings of IEEE International Conference on Robotics and Automation, 2010. 398--405. Google Scholar

[15] Belongie S, Malik J. Matching with shape contexts. In: Proceedings Workshop on Content-based Access of Image and Video Libraries, 2000. Google Scholar

[16] Liu C L, Kim I J, Kim J H. Model-based stroke extraction and matching for handwritten Chinese character recognition. Pattern Recognition, 2001, 34: 2339-2352 CrossRef Google Scholar

[17] Fischler M A, Bolles R C. Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography. Read Comput Vision, 1987, 24: 726--740. Google Scholar

[18] Schenker P S. Method for registration of 3-D shapes. IEEE Trans Pattern Anal Mach Intell, 2002, 14: 239--256. Google Scholar

[19] Cho M, Lee J, Lee K M. Reweighted random walks for graph matching. In: Proceedings European Conference on Computer Vision, 2010. 492--505. Google Scholar

[20] Mateus D, Horaud R, Knossow D, et al. Articulated shape matching using Laplacian eigenfunctions and unsupervised point registration. In: Proceedings IEEE Conference on Computer Vision and Pattern Recognition, 2008. Google Scholar

[21] Zhou F, De la Torre F. Factorized Graph Matching.. IEEE Trans Pattern Anal Mach Intell, 2016, 38: 1774-1789 CrossRef PubMed Google Scholar

[22] Otsu N. A Threshold Selection Method from Gray-Level Histograms. IEEE Trans Syst Man Cybern, 1979, 9: 62-66 CrossRef Google Scholar

[23] Wang Y, Zhong B J. A scale-space technique for polygonal approximation of planar curves. In: Proceedings of IEEE International Conference on Image Processing, 2013. 517--520. Google Scholar

[24] Fukushima M. A modified Frank-Wolfe algorithm for solving the traffic assignment problem. Transpation Res Part B-Methodological, 1984, 18: 169-177 CrossRef Google Scholar

[25] Chang C C, Lin C J. LIBSVM: a library for support vector machines. ACM Trans Intell Syst Technol, 2011, 2: 1-27 CrossRef Google Scholar

[26] Lecun Y, Bottou L, Bengio Y. Gradient-based learning applied to document recognition. Proc IEEE, 1998, 86: 2278-2324 CrossRef Google Scholar

[27] You C, Robinson D P, Vidal R. Scalable sparse subspace clustering by orthogonal matching pursuit. In: Proceedings of IEEE Conference on Computer Vision and Pattern Recognition, 2016. 3918--3927. Google Scholar

[28] Qu X W, Wang W Q, Lu K. In-air handwritten Chinese character recognition using discriminative projection based on locality-sensitive sparse representation. In: Proceedings of International Conference on Pattern Recognition, 2017. 1137--1140. Google Scholar

[29] Cao J, Pang Y, Li X. Randomly translational activation inspired by the input distributions of ReLU. Neurocomputing, 2018, 275: 859-868 CrossRef Google Scholar

• Figure 1

(Color online) Examples of ancient Chinese seals. (a) Ancient personal seal; (b) different forms of the character łqłq yinrqrq (seal) in seal fonts.

• Figure 2

(Color online) Graph-matching-based character recognition for Chinese seal images.

• Figure 3

(Color online) Graph construction process.

• Figure 4

(Color online) Examples of graph construction result for Chinese seal character. (a) Missing turning points detected by polygonal approximation; (b) original character image; (c) skeleton extraction result; (d) skeleton pruning result; (e) graph model (endpoints, branch points, and new turning points calculated via polygonal approximation are represented by red, green, and blue, respectively).

• Figure 5

(Color online) Shape context feature distribution of seal character graph.

• Figure 6

(Color online) An example of seal character matching. (a) Two seal character graphs; (b) two graphs' incidence matrices ${\boldsymbol~S}$ and ${\boldsymbol~T}$, where non-zero elements in each column of ${\boldsymbol~S}$ and ${\boldsymbol~T}$ indicate the start and terminal nodes in the corresponding directed edge, respectively; (c) node affinity matrix ${\boldsymbol~K}_v$ and edge affinity matrix ${\boldsymbol~K}_e$; (d) node correspondence matrix ${\boldsymbol~X}$ and edge correspondence matrix ${\boldsymbol~Y}$.

• Figure 7

(Color online) Character sample examples.

• Figure 8

(Color online) Comparison of matching for samples from the same and different categories.

•

Algorithm 1 Graph construction of Chinese seal character

Input: Input image ${\boldsymbol~I}$; skeleton pruning threshold $l_{\rm~min}$; polygonal approximation threshold $\theta_{\rm~min}$, $d_{\rm~max}$. Output: The graph model ${\boldsymbol~G}=\{{\boldsymbol~V},~{\boldsymbol~E}\}$.

Resize the input image ${\boldsymbol~I}$ to a normalized image ${\boldsymbol~I}^{\rm~re}$ in fixed size $100\times100$;

Obtain the binary image with Otsu's algorithm: ${\boldsymbol~I}^{\rm~bw}~=~{\rm~Otsu}(~{\boldsymbol~I}^{\rm~re}~)$;

Extract the skeleton image ${\boldsymbol~I}^{\rm~sk}$ from ${\boldsymbol~I}^{\rm~bw}$;

for each skeleton point $p_i~\in~{{\boldsymbol~I}^{\rm~sk}=1}$

Find ${\boldsymbol~V}_{\rm~branch}$ and ${\boldsymbol~V}_{\rm~end}$ with (3);

end for

for each end point $v_i~\in~{\boldsymbol~V}_{\rm~end}$

Find the path $\psi_{i~\rightarrow~j}$ for $v_i$ to the first branch point $v_j\in~{\boldsymbol~V}_{\rm~branch}$ in the skeleton images;

if ${\rm~length}(\psi_{i~\rightarrow~j})<l_{\rm~min}$ then

Delete $v_i$ and $\psi_{i~\rightarrow~j}$ from ${\boldsymbol~V}_{\rm~end}$ and ${\boldsymbol~I}_{\rm~sk}$ respectively;

end if

Let ${\boldsymbol~V}~=~\{{\boldsymbol~V}_{\rm~branch};{\boldsymbol~V}_{\rm~end}\}$;

end for

for each end point $v_i\in~{\boldsymbol~V}$

if $\exists~\psi_{i~\rightarrow~j}$ in ${\boldsymbol~I}^{\rm~sk}$ then

${\boldsymbol~E}=\{{\boldsymbol~E};(i,j)\}$;

end if

end for

for each edge $e_c=(i,j)~\in~{\boldsymbol~E}$

$n={\rm~size}({\boldsymbol~V})$;

Find candidate key point $\hat{p}$ with (4);

if $d(\hat{p})>d_{\rm~max}$ then

Calculate the path point angle $\theta(\hat{p})$ with (5);

if $\theta(\hat{p})<\theta_{\rm~min}$ then

${\boldsymbol~V}~=\{~{\boldsymbol~V};v_{n+1}=\hat{p}~\}$;

${\boldsymbol~E}=\{{\boldsymbol~E};(i,n+1);(n+1,j)\}$;

end if

end if

end for

The graph model is integrated with ${\boldsymbol~V}$ and ${\boldsymbol~E}$: ${\boldsymbol~G}=[{\boldsymbol~V},~{\boldsymbol~E}]$;

Return ${\boldsymbol~G}$.

• Table 1   Parameter settings
 Step Parameter Value Skeleton pruning Length threshold $l_{\rm~max}$ 10 Polygon approximation Angle threshold $\theta_{\rm~min}$ $2.36$ Distance threshold $d_{\rm~min}$ 5 Shape feature Step length 20 Orientation difference $0.52$ Affinity matrix calculating Spatial scale factor $\sigma_d$ 35 Orientation scale factor $\sigma_\theta$ 25
•

Algorithm 2 Factorized graph matching

Input: The node and edge affinity matrices ${\boldsymbol~K}_v$, ${\boldsymbol~K}_e$; the two input graphs' incidence matrices ${\boldsymbol~S}_1$, ${\boldsymbol~T}_1$, ${\boldsymbol~S}_2$, ${\boldsymbol~T}_2$; step length $\delta$; the initial node correspondence matrix ${\boldsymbol~X}_0$. Output: The node correspondence matrix ${\boldsymbol~X}$; the matching score between two graphs ${\boldsymbol~J}$.

Initialize ${\boldsymbol~X}$ to be a doubly stochastic matrix;

Factorize ${\boldsymbol~K}_e={\boldsymbol~U}{\boldsymbol~V}^{\rm~T}$;

for $\alpha=~0:\delta:1$

if $\alpha=0.5$ and $J_{\rm~gm}({\boldsymbol~X})~<~J_{\rm~gm}({\boldsymbol~X}_0)$ then

Update ${\boldsymbol~X}leftarrow{{\boldsymbol~X}_0}$;

end if

Optimize (23) via MFW to obtain ${\boldsymbol~X}^*$;

Update ${\boldsymbol~X}$ $\leftarrow$ ${\boldsymbol~X}^*$;

end for

Calculate $J_{\rm~gm}({\boldsymbol~X})={\rm~tr}({\boldsymbol~K}_v^{\rm~T}{\boldsymbol~X})+{\rm~tr}({\boldsymbol~K}_e^{\rm~T}({\boldsymbol~S}_1^{\rm~T}{\boldsymbol~X}{\boldsymbol~S}_2\circ~{\boldsymbol~T}_1^{\rm~T}{\boldsymbol~X}{\boldsymbol~T}_2))$;

Return ${\boldsymbol~X}$, ${\boldsymbol~J}$.

• Table 2   Recognition accuracy of top 1, 3 and 5 with the proposed method
 Top 1 Top 3 Top 5 Accuracy (%) 83.42 88.52 91.33
• Table 3   Recognition results of different methods
 Category 不 个 之 书 二 人 佛 刘 北 千 午 南 印 启 堂 Test/train 4/3 3/3 17/17 5/5 4/4 8/7 3/2 7/7 3/2 25/24 3/2 3/2 19/19 6/5 7/7 SVM[25] 0 0 14 0 3 1 0 1 0 12 2 0 4 1 0 CNN[26] 2 0 10 0 4 5 0 6 0 17 1 1 16 2 4 MPSC[27] 2 0 11 1 4 4 1 5 0 14 1 1 14 0 0 SRC[28] 2 0 11 1 4 4 1 5 0 15 1 1 14 0 0 GMCSCR 4 0 16 4 4 4 3 7 0 21 3 2 18 6 5 Category 墨 士 大 天 好 季 宁 家 寿 居 山 己 巳 年 庐 Test/train 3/2 5/5 32/32 3/3 3/2 3/2 7/6 3/3 5/4 6/5 3/2 3/2 3/2 3/3 3/2 SVM[25] 0 2 9 0 1 0 0 0 0 0 1 1 0 0 0 CNN[26] 0 3 26 0 0 0 0 0 3 3 2 1 0 0 0 MPSC[27] 1 2 30 0 0 0 0 0 0 5 3 1 0 0 0 SRC[28] 1 3 30 0 0 0 0 0 0 5 3 1 0 0 1 GMCSCR 2 4 31 3 2 1 6 1 5 4 2 2 0 1 3 Category 张 心 戊 成 我 摩 斧 海 爰 王 生 画 真 石 私 Test/train 26/25 3/3 3/2 5/5 4/3 3/3 8/7 21/21 22/22 6/5 3/3 6/5 3/2 3/3 5/5 SVM[25] 3 0 0 0 2 0 0 2 7 5 0 0 0 0 0 CNN[26] 19 0 0 1 1 0 3 19 15 1 0 2 1 0 3 MPSC[27] 20 0 0 1 1 1 4 12 14 3 0 1 0 0 4 SRC[28] 20 0 0 1 1 1 4 12 14 3 0 1 0 0 4 GMCSCR 24 1 1 4 1 3 5 21 20 6 3 2 3 2 3 Category ?m 粟 翁 老 腐 花 藏 蜀 西 贤 进 ? 长 风 Overall Test/train 3/2 13/13 7/6 7/7 3/2 3/2 3/2 3/3 4/3 5/5 3/2 3/3 7/6 5/5 Accuracy (%) SVM[25] 0 1 0 0 0 0 0 0 0 0 0 0 0 0 18.37 CNN[26] 0 9 3 1 0 0 1 1 1 2 0 1 2 2 49.23 MPSC[27] 0 9 1 0 1 0 1 0 1 2 1 1 1 1 46.17 SRC[28] 0 9 1 0 1 0 1 1 1 3 0 2 1 1 47.45 GMCSCR 3 12 7 7 2 0 3 1 4 5 1 2 5 3 $\mathbf{83.42}$

Citations

Altmetric