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 as g_ref=exp (-|d|), where dis 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 as A_p in Fig. 4, as the mid-perpendicular of line ($\overline {{p_1}{p_2}} $), which links the two feature points p₁ and p₂ in a PSE.

In Fig. 4, n(p₁) and n(p₂) are feature vectors. The weight of A_p is defined as

$ {w_{{A_p}}} = \cos < \boldsymbol{n}({p_1}), \;\boldsymbol{n}({p_2}) > $

(1)

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, l₁ and l₂ are 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 PSA A_l is generated. S₁ and S₂ represent the corresponding parts of l₁ and l₂ that contribute to A_l. The weight of A_l is defined as

${w_{{A_l}}} = \frac{{{D_{{A_l}}}}}{{\max ({D_{{A_l}}})}}.$

(2)

D_Al is the length of A_l, and (D_Al) is the maximum length of all PSAs generated by all PSEs. Eq. (2) assigns high weights to PSAs formed by long contours.

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 edge e_ij linking nodes i and j reflects how strong the node i can enhance the symmetry intensity represented by node j.

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:

$ {e_{ij}} = {w_i} \cdot {g_{ij}} $

(3)

Where w_i is the weight of node i, and g_ij is the position relationship between the two nodes. Eq. (3) indicates that the enhancement magnitude is proportional to the saliency of node i. g_ij is defined as

${g_{ij}} = \cos (\Delta \theta ) \cdot {\text{exp}}\left( { - \frac{{{d_{ij}}}}{\sigma }} \right), $

(4)

Where Δθis the angle between two PSAs, and d_ij is 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 subgraph S_i is defined as the sum weight of the center node i and all incoming directed edges with the following formula:

${S_i} = \alpha {w_i} + (1 - \alpha )\left( {\beta \sum\nolimits_{j \in {A_l}} {{e_{ji}}} + (1 - \beta )\sum\nolimits_{k \in {A_p}} {{e_{ki}}} } \right), $

(5)

where w_i is the weight of center node i, the current SPA (an A_l or an A_p). α and β are parameters whose values are between 0 and 1. α represents the importance of the current center when it becomes large. When β is high, the influence of line pairs is enhanced. We introduce threshold γ of g_ij to filter unimportant links and thus simplify the calculation. In short, only the edges that satisfy g_ij≥γ 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. Average P and R of LE method are P=0.5777, R=0.5202; ave-rage P and R of proposed method are P=0.5952, R=0.6401. The two methods report almost similarly accurate results (P=1, R=1); however, the proposed method generates fewer erroneous results (P=0, R=0). Furthermore, the proposed method generally produces a better overall detection result with a higher averageP and R than the LE method does. Additional details on the detection results are shown in Fig. 9.

Fig. 9 indicates that P and R generated by the proposed method are mainly located in the top right region of the PR coordinate system, whereas P and R generated 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 combining SIFT-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.