一種基于星型圖的漢字鏡像對稱檢測方法

廖媛 呂肖慶,3,? 孫建伶 湯幟,2 王勇濤

?

一種基于星型圖的漢字鏡像對稱檢測方法

廖媛1呂肖慶1,3,?孫建伶4湯幟1,2王勇濤1

1.北京大學(xué)計算機科學(xué)技術(shù)研究所, 北京100871; 2.數(shù)字出版技術(shù)國家重點實驗室, 北京 100871; 3.中國文字字體設(shè)計與研究中心, 北京 100871; 4.浙江大學(xué)計算機科學(xué)與技術(shù)學(xué)院, 杭州 310027; ?通信作者, E-mail: lvxiaoqing@pku.edu.cn

結(jié)合不同類型的漢字特征——尺度不變特征變換(SIFT)和輪廓信息, 提出一種基于星型圖的漢字鏡像對稱檢測方法。該方法利用基礎(chǔ)對稱元素構(gòu)造一個加強關(guān)系有向圖來描述不同對稱元素之間的加強關(guān)系, 從而將檢測漢字的顯著對稱軸問題轉(zhuǎn)化為尋找具有局部最大權(quán)重的星型子圖問題。實驗結(jié)果表明, 與現(xiàn)有方法相比, 所提方法在漢字數(shù)據(jù)集上具有更好的檢測效果。

鏡像對稱; 漢字; 星型圖; 對稱檢測

1 Background

The natural world in which we live is characterized by miraculous phenomena involving symmetry. Symmetry is also a significant structural feature that profoundly influences the development of Chinese characters. As the foundation of an ideographic script,many Chinese characters were originally created to simulate and describe nature, including the symmetries in various objects and phenomena. Given the external morphology of symmetry, most characters not only reflect the visual effects of harmony, such as balance, stability, and massiveness, but the symmetry also enables our ancestors to distinguish and remember these characters with remarkable convenience. Many Chinese characters exhibit global and local symmetry, as shown in Fig. 1.

Throughout the long-term evolutionary process of Chinese characters, the symmetries of almost all characters have not remained static. Rather, these characters underwent complex progressive develop- ment involving inheritances and mutations. For example, we can perceive the original demand of the character “草” (grass) for symmetry through its early shapes, such as the oracle bone inscription and the warring states script depicted in Fig. 2(a) and (b).

Fig. 2(c) indicates that the small seal script of the character “草” is almost perfectly symmetrical, with a free-flowing, gracefully curved shape. The clerical script (Fig. 2(d)) inherits the symmetry from the small seal script, however, the curved strokes are replaced with straight strokes. As the standard font type of writing, the regular script (Fig. 2(e)) is in fact a hybrid of the semi-cursive and the neo-clerical scripts. To facilitate smooth writing and to achieve a beautiful and abstract appearance, the semi-cursive (Fig. 2(f)) and cursive scripts (Fig. 2(g)) eliminate angular strokes and simplify characters through highly rounded and soft shapes. This observation suggests that the effect of symmetry on regular, semi-cursive, and cursive scripts does not disappear. The symmetric structures in these scripts are progressively lenient; nonetheless, a new level of visual balance is achieved based on implicit and dynamic symmetries with width variation, stroke tip decorations, and the continuity of trajectories.

The significance of symmetry research lies in the following aspects: exploring more characteristics and regularities in typeface design and font development, providing ordinary students and professional calli- graphers with helpful advices (for instance, the guide to good handwriting, as illustrated in Fig. 3), and promoting the recognition and retrieval of Chinese characters further by simplifying feature descriptions and matching algorithms.

Accurate symmetry detection is crucial to further analysis in many cases. However, researchers encounter several challenges at present: first, the explanation for most symmetrical phenomena depends heavily on visual perception. To our knowledge, no accepted computational model that accurately simulates the perception of symmetry has been developed in general. In fact, numerous features that contribute to symmetrical perception captivate us when selecting the dominant features to represent symmetry. Second, despite our focus on some of these preferred features, describing these characteristics quantitatively is another serious problem. Last, these features are correlatively dependent and interplay with one another. To a certain extent, some combinations play a more important role in the formation of characters than the individual features themselves do.

2 Related Work

To detect symmetry effectively, a variety of methods have been proposed recently. Most of them can be classified into two categories: SIFT-based and contour-based.

SIFT is adopted in many symmetry detection algorithms due to its scale invariant property. Park et al.[1]evaluated the performance of three state-of- the-art symmetry detection algorithms. The LE algorithm proposed by Loy et al.[2]is a classic method on the basis of matching symmetric pairs of feature points. It adopted SIFT to describe the feature points and voted potential pairs of symmetry point in Hough space to find the dominent symmetry axes. Cho et al.[3]improved the LE algorithm using symmetry- growing. Sun et al.[4]established a symmetry axis matrix that described the relationship betwween an original region and its symmetrically reflected region. Hauagge et al.[5]presented a technique to extract local features for image matching on the basis of detecting local symmetries. Xiang et al.[6]proposed a centripetal-SIFT edge descriptor to detect the location of symmetric object. Lee et al.[7]adopted a gradient filter and a Canny edge detector to increase the quantity of SIFT feature points.

Many symmetry detection models are mainly based on contour information[8-10]. Ming et al.[11]constructed a directed graph of symmetry interaction. Each symmetric element, which is a trapezoid consisting of a pair of line segments and a corresponding symmetric axis, is represented as a node in a graph. An edge between two nodes is added when the two symmetric axes are close enough. The symmetric objects are detected with a search method of subgraphs.

In addition to the detection of symmetry axis, the assessment of symmetry magnitude also attracts many researchers. Lee et al.[12]defined the symmetry intensity asref= exp(-||), whereis the Euclidean distance between each point and corresponding symmetry axis. Dalitz et al.[13]introduced an intensity for rotational symmetry and obtained the sizes of symmetry region. Fu et al.[14]defined a symmetry magnitude map by estimating the symmetry intensity of each point in an image.

To summarize, the SIFT-based algorithms are more robust than other methods, but they also have obvious drawbacks, for example, relying too much on the effect of SIFT detection. The Contour-based algorithms sometimes outperform the SIFT-based methods. However the low accurancy of countor detection also limits the efficience of such algori- thms. Combining different types of feature leads to the more accurate detetion of symmetry.

3 Symmetry Detection via Mutual Enhancement of Double Types of Feature

3.1 Workflow

Symmetry perception is a complex procedure that combines different features. Recent studies in the field of cognitive psychology suggest that humans observe symmetric objects by processing features in different layers, such as edges and points. Point features represent the local information on color and texture, whereas edge features represent shape information. These features complement each other mutually. Thus, a new model can be established based on the combination of SIFT-based features with contour- based features.

In this model, a potential symmetry element (PSE) is defined as a pair of point features or a pair of edge features that correspond to a potential symmetry axis (PSA) on the basis of regular symmetry transformation. To describe the relationship among PSAs, a directed star graph with symmetry weight (S-graph) is introduced. The nodes of this graph are PSAs, and its edges represent the mutual influences among these axes. As part of the S-graph, the single-PSA-centered subgraph can be adopted to calculate local symmetry intensity.

The main workflow consists of following steps. First, we derive all of the SIFT points and edges from a preprocessed image. Second, we select PSEs and their corresponding PSAs. Then, a S-graph is constructed to describe the symmetry information on the image. Each salient symmetric object can be represented as a star subgraph. Next, the local symmetry detection problem is transformed into a problem with determining the subgraph that exhibits the local maximum magnitude. Last, the magnitudes of all the star subgraphs are projected to Hough space, and the most significant symmetric axes are detected as the maximum points.

3.2 PSE and PSA

Two kinds of PSE are adopted in our approach: contour-based and SIFT-based PSEs.

3.2.1 SIFT-based PSE

A SIFT-based PSE is converted from a pair of similar feature vectors in LE[2]. In our model, we define a PSA generated by a SIFT-based PSE, such asin Fig. 4, as the mid-perpendicular of line (), which links the two feature points1and2in a PSE.

In Fig. 4,(1) and(2) are feature vectors. The weight ofAis defined as

Eq. (1) assigns a high weight to PSAs that are formed by similar SIFT feature point pairs.

3.2.2 Contour-based PSE

Contour symmetry is a significant feature for symmetric objects. Contours are generaly irregular curves, therefore, the line-fitting algorithm is adopted to segment and to represent contours. Two line segments with enough probability of a boundary (Pb value)[15]are selected to form a PSE. The angular bisector of each line pair is regarded as a PSA. Fig. 5 illustrates an example of a contour-based PSE and its corresponding PSA.

In Fig. 5,1and2are two lines that are regarded as PSEs. An angular bisector is positioned between these lines, and they project themselves to this bisector. If the overlap area of the projections is not empty, then a PSAAis generated.1and2represent the corresponding parts of1and2that contribute toA. The weight ofAis defined as

3.3 Directed graph of enhancement relation

To combine contour-based and SIFT-based PSEs, we construct a directed graph of enhancement relation, i.e., the S-graph, to describe the symmetry information of an image. Each PSA is abstracted as a node in the S-graph, and the directed edgeelinking nodesandreflects how strong the nodecan enhance the symmetry intensity represented by node.

If two PSAs generated by two PSEs are close enough, then the reliability of symmetry will be mutually enhanced. Specifically, small angle and short distance between two PSAs will lead to their enhanced intensity of symmetry for each other. The magnitude of the enhancement for each edge is calculated using the following formula:

Wherewis the weight of node, andgis the position relationship between the two nodes. Eq. (3) indicates that the enhancement magnitude is proportional to the saliency of node.gis defined as

Where Δis the angle between two PSAs, anddis the distance between the centers of the two PSAs. Eq. (4) assigns a large value to a pair of PSAs with close relationships.

As the PSA nodes are added from both SIFT-based and contour-based PSEs, the enhancement between different types of features can be obtained in this model. Fig. 6 is an example of a directed graph of enhancement relation. Our approach is different from existing methods that mainly depend on a single type of feature because it adopts more image context to achieve more accurate symmetry intensity.

3.4 Extract star subgrap as symmetry object

A symmetric object consists of a set of symmetric elements. Correspondingly, PSEs that contribute the same symmetry axis strongly enhance one another. Therefore, we translate the identification of a symmetry object to find a subgraph with strong enhancement relations.

We undertake several topologies of subgraphs, including star, chain, and tree[11,16-17]. Our experiments verify that the star subgraph outperforms the other types of subgraphs. The star subgraph ensures that all the leave nodes close to the center node contribute the same symmetry axes. However, the nodes in a chain or tree may share different axes. The larger the number of nodes becomes, the more calculations have to be performed for the irrelevant axes.

The symmetry magnitude of star subgraphSis defined as the sum weight of the center nodeand all incoming directed edges with the following formula:

wherewis the weight of center node, the current SPA (anAor anA).andare parameters whose values are between 0 and 1.represents the importance of the current center when it becomes large. Whenis high, the influence of line pairs is enhanced. We introduce thresholdofgto filter unimportant links and thus simplify the calculation. In short, only the edges that satisfyg≥are regarded as the relative edges that possibly share the same axis.

3.5 Symmetry axis detection

A star subgraph should have a local maximum magnitude in the directed graph. To find the local maximum magnitude, a star subgraph is projected to Hough space as a point. The magnitude of a star subgraph corresponds to the weight of the Hough space point. When the local maximum points in the Hough space are detected, the corresponding symmetry axes are also detected.

4 Experiment

The proposed method is implemented in Matlab 2012. In our experiments, the parameter values for the algorithm are set as follows:= 20 in Eq. (4), and reliable edge threshold= 0.75. We set the value for parameter,in Eq. (5) as 0.3 to ensure the optimal performance of our method in the experiment dataset. Moreover, we construct a dataset that consists of 6713 images of Chinese characters presented in the Hei typeface and evaluate our method on the dataset. The symmetric axes in the ground truth dataset are represented by the two endpoints of a line segment. A detected axis is considered to be correct if the angle between the ground truth axis and the axis in question is less than 5°, and the distances between the endpoints of a ground truth axis and the corresponding endpoints of a detected axis are less than 8% of char size.

Examples of the experiments are shown in Fig. 7. The detected axes are represented by gray lines.

The proposed method generates better axis detection results than the LE method does, especially when the images contain less effective SIFT points. Fig. 8 depicts the comparison.

We compare the precision and recall rates of our results with those of LE method findings[2]. Table 1 shows the statistical results on the dataset. Averageand R of LE method are P=0.5777, R=0.5202; ave- rageandof proposed method are=0.5952,=0.6401. The two methods report almost similarly accurate results (=1,=1); however, the proposed method generates fewer erroneous results (=0,=0). Furthermore, the proposed method generally produces a better overall detection result with a higher averageandthan the LE method does. Additional details on the detection results are shown in Fig. 9.

Table 1 Statistical results of P and R for the LE and the proposed methods

Fig. 9 indicates thatandgenerated by the proposed method are mainly located in the top right region of the PR coordinate system, whereasandgenerated by LE method are primarily distributed at the bottom left region. This scenario implies that our method outperforms LE method given characters whose symmetry can be only partially detected.

Nonetheless, the proposed method does not detect all of the symmetry axes of Chinese characters correctly. In fact, this technique fails on some complicated Chinese characters, such as when the main symmetry axis is affected by many overlapping strokes, as illustrated in Fig. 10.

To overcome the weaknesses of the current method, future works should explore more symmetry features, improve the efficiency of the graph model, and refine the selection process of candidate axes.

5 Conclusion

Limited texture features make traditional sym- metry detection methods not effective for Chinese character symmetry detection. For this matter, a detection method of bilateral symmetry combiningSIFT-based and contour-based features is proposed in this paper. A directed graph of enhancement relation is constructed, and each symmetric element is represented as a node in the graph. A star subgraph search method is also proposed to identify the potential symmetry objects. Our experiment on Chinese character images shows that the proposed approach outperforms the existing single-type-feature-based methods.

References

[1]Park M, Lee S, Chen P C, et al. Performance evaluation of state-of-the-art discrete symmetry detection algorithms // Computer Vision and Pattern Recognition, CVPR 2008. Anchorage, AK, 2008: 1–8

[2]Loy G, Eklundh J O. Detecting symmetry and symmetric constellations of features // Computer Vision–ECCV 2006. Berlin: Springer, 2006: 508–521

[3]Cho M, Lee K M. Bilateral symmetry detection via symmetry-growing // BMVC. London, 2009: 1–11

[4]Sun Y, Bhanu B. Reflection symmetry-integrated image segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2012, 34(9): 1827–1841

[5]Hauagge D C, Snavely N. Image matching using local symmetry features // IEEE Conference on Computer Vision and Pattern Recognition (CVPR). Providence, RI, 2012: 206–213

[6]Xiang Y, Li S. Symmetric object detection based on symmetry and centripetal-SIFT edge descriptor // 21st International Conference on Pattern Recognition (ICPR). Tsukuba, 2012: 1403–1406

[7]Lee S, Liu Y. Curved glide-reflection symmetry detection. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2012, 34(2): 266–278

[8]Prasad V, Yegnanarayana B. Finding axes of symmetry from potential fields. IEEE Transactions on Image Processing, 2004, 13(12): 1559–1566

[9]Stahl J S, Wang S. Globally optimal grouping for symmetric closed boundaries by combining boundary and region information. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2008, 30(3): 395– 411

[10]Yl?-J??ski A, Ade F. Grouping symmetrical structures for object segmentation and description. Computer Vision and Image Understanding, 1996, 63(3): 399– 417

[11]Ming Y, Li H, He X. Symmetry detection via contour grouping // 20th IEEE International Conference on Image Processing (ICIP). Melbourne, VIC, 2013: 4259–4263

[12]Lee S, Liu Y. Symmetry-Driven Shape Matching [R]. University Park: Pennsylvania State University, 2009

[13]Dalitz C, Pohle-Fr?hlich R, Bolten T. Detection of symmetry points in images // VISAPP. Barcelona, 2013: 577–585

[14]Fu H, Cao X, Tu Z, et al. Symmetry Constraint for Foreground Extraction. IEEE Transactions on Cyber- netics, 2014, 44(5): 644–654

[15]Arbelaez P, Maire M, Fowlkes C, et al. Contour detection and hierarchical image segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2011, 33(5): 898–916

[16]Ishikawa H, Geiger D, Cole R. Finding tree structures by grouping symmetries // Tenth IEEE International Conference on Computer Vision. Beijing, 2005: 1132–1139

[17]Liu Y, Hel-Or H, Kaplan C S. Computational symmetry in computer vision and computer graphics. Hanover, MA: Now publishers Inc, 2010

A Star-Graph-Based Detection Method for Reflection Symmetry of Chinese Characters

LIAO Yuan1, Lü Xiaoqing1,3,?, SUN Jianling4, TANG Zhi1,2, WANG Yongtao1

1. Institute of Computer Science and Technology, Peking University, Beijing 100871; 2. State Key Laboratory of Digital Publishing Technology, Beijing 100871; 3. Center for Chinese Font Design and Research, Beijing 100871; 4. College of Computer Science and Technology, Zhejiang University, Hangzhou 310027; ? Corresponding author, E-mail: lvxiaoqing@pku.edu.cn

This study proposes a detection method of bilateral symmetry for Chinese characters that combines different types of character features, such as scale invariant feature transform (SIFT) and contour information. A directed graph is constructed with the basic symmetric elements of a character to describe the enhancement relationships among the elements. Furthermore, the detection of the most significant axes of symmetry in one character is transformed into the problem of finding star subgraphs with local maximum weight. Experiment results show that the proposed method outperforms the existing methods on Chinese characters database.

reflection symmetry; Chinese character; star graph; symmetry detection

10.13209/j.0479-8023.2016.015

TP391

2015-06-05;

2015-08-17; 網(wǎng)絡(luò)出版日期: 2015-09-29

國家自然科學(xué)基金(61300061)和863計劃(2012AA013102)資助