logo

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

More info
  • ReceivedApr 5, 2018
  • AcceptedOct 31, 2018
  • PublishedJul 30, 2019

Abstract

Recognizing characters in Chinese seal images is important when researching ancient cultural artworks because the seals may contain critical historical information. However, owing to large intraclass variance and a limited number of training samples, recognizing such characters in Chinese seals is challenging. Thus, this study proposes a graph-matching-based method to recognize characters in historical Chinese seal images. In the proposed method, a Chinese seal character is first modeled as a graph representing its underlying geometric structure. Then, two affinity matrices that measure the similarity of nodes and edge pairs are calculated with their local features. Finally, a correspondence matrix is calculated using a graph matching algorithm and the most similar reference is selected as the recognition result. Compared with several existing classification methods for seal image recognition, the proposed graph-matching-based method achieves better results, particularly in the case of limited samples.


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 approximationAngle threshold $\theta_{\rm~min}$ $2.36$
    Distance threshold $d_{\rm~min}$ 5
    Shape feature Step length20
    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 24
    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}$

Copyright 2020 Science China Press Co., Ltd. 《中国科学》杂志社有限责任公司 版权所有

京ICP备18024590号-1