logo

Journals Books
Advanced Search
Sign in Register

中文

SCIENCE CHINA Information Sciences
Download PDF
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

Bin SUN 1, Shaojun HUA 1, Shutao LI 1,*, Jun SUN 2
More info
  • ReceivedApr 5, 2018
  • AcceptedOct 31, 2018
  • PublishedJul 30, 2019
Previous Table of Contents Next
Share
Rating

Abstract


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

  • Click to view Download high-quality image

    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.

  • Click to view Download high-quality image

    Figure 2

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

  • Click to view Download high-quality image

    Figure 3

    (Color online) Graph construction process.

  • Click to view Download high-quality image

    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).

  • Click to view Download high-quality image

    Figure 5

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

  • Click to view Download high-quality image

    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}$.

  • Click to view Download high-quality image

    Figure 7

    (Color online) Character sample examples.

  • Click to view Download high-quality image

    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}$