Signal Processing: Image Communication 60 (2018) 91–99 Contents lists available at ScienceDirect Signal Processing: Image Communication journal homepage: www.elsevier.com/locate/image Multiple rotation symmetry group detection via saliency-based visual attention and Frieze expansion pattern Ronggang Huang a, *, Yiguang Liu a, *, Zhenyu Xu a , Pengfei Wu a , Yongtao Shi b a b Sichuan University, College of Computer Science, Chengdu, 610065, China China Three Gorges University, College of Computer and Information Technology, Yichang, 443002, China a r t i c l e i n f o Keywords: RSS SSD Multiple-local-region searching Multiple-model computation a b s t r a c t Global maximum symmetry center probability-based rotation symmetry detection methods are unable to identify small-scale rotation symmetry centers in real-world images and come with a costly computational burden. This paper presents a novel strategy comprised of multiple-local-region searching in the whole image and multiplemodel computation to map rotation symmetry strength (RSS) in the local region. The multiple-local-region searching method creates local regions in which the global maximum symmetry center detection method changes to a local maximum symmetry center detection method. In the local region, the multiple-model computation efficiently detects regular, small-scale, and skewed symmetry centers. This strategy improves the detection ability for regular, small-scale, and skewed rotation symmetry centers while minimizing the complexity of the algorithm based on a rotation symmetry strength (RSS) map and symmetry shape density (SSD) map. Experimental results indicate that this strategy not only allows more rotation symmetry centers to be identified successfully, but is simpler than traditional strategies as it only employs RSS maps. © 2017 Elsevier B.V. All rights reserved. 1. Introduction Symmetry is a universal phenomenon throughout nature as well as in man-made objects. It is also an important mechanism by which it is possible to identify the unique structures of objects [1–5]. Symmetry group detection is thus a basic function of the perception and recognition of periodic patterns [6]. Many recent researchers have established methods of detecting periodic patterns in the spatial domain and frequency domain. In the spatial domain, such methods are mainly based on feature (edge, angle, corner, boundary, and texture) detection [7–12]. In the frequency domain, the methods are mainly based on frequency analysis tools such as discrete Fourier transform (DFT) and wavelet transform. DFT lends particularly useful insight into periodic pattern relationships in both spatial and frequency domains [13–18]. Feature detection requires identifying common features in the local region and frequency detection in the global region for a whole image. To this effect, existing detection methods can be divided into two main categories: Local and global methods. In 2D Euclidean space, the rotation symmetry group is one of four types of primitive symmetry groups [6]; existing methods for rotation symmetry group detection can be classified similarly into these two main categories. Certain feature detectors are applied in local rotation symmetry group detection methods. Cornelius et al. [9], for example, detected rotation symmetry groups via SIFT, Harris-affine, and Hessian-affine feature detectors under affine projection. They hypothesized each feature pair as a set of centers of rotation for different tilts and orientations, then identified the dominant rotational symmetries per the centers of rotation that were close to each other in the image. Their algorithm requires texture information, however, and is thus restricted to objects with symmetrical texture. Loy et al. [8] detected rotation symmetry groups by using all orientations, scales, and locations in the image to determine rotation symmetry and bilateral symmetry in a complex background as well as multiple symmetry cases in a single image. Their algorithm is based on the robust matching of feature points generated by modern feature detectors such as SIFT. Although both of these algorithms can detect rotation symmetry, they are not sufficiently accurate overall especially in multiple rotation symmetry cases. Frequency analysis tools are typically applied in global rotation symmetry group detection methods. Though automatic and robust rotation symmetry group detection methods are rare, the Frieze-expansion pattern (FEP) [14,15] is widely considered the most important rotation symmetry detection method established to date. FEP [14] uses a rotation * Corresponding authors. E-mail addresses: happy.every.day@126.com (R. Huang), liuyg@scu.edu.cn (Y. Liu), sanxu@outlook.com (Z. Xu), wpfnihao@gmail.com (P. Wu), 151604213@qq.com (Y. Shi). https://doi.org/10.1016/j.image.2017.09.010 Received 10 January 2017; Received in revised form 24 September 2017; Accepted 25 September 2017 Available online 7 October 2017 0923-5965/© 2017 Elsevier B.V. All rights reserved. R. Huang et al. Signal Processing: Image Communication 60 (2018) 91–99 Fig. 1. Examples of period pattern in time domain and frequency domain. Left column shows signals in time domain, the length of all signals is 2. Right column shows DFT absolute values (magnitudes) of left signals in frequency domain, which is only the front half of the whole DFT magnitude as the halves are similar. (a) {2} folds sine signal. (c) {4} folds sine signal. (e) Folds shown in (a) added to folds shown in (c), forming the signal containing {2, 4} fold signals. algorithm is described in Section 3, including saliency-based visual attention, local RSS maps, segmented rotation symmetry regions and symmetry properties. The algorithm complexity is described in Section 4. Sections 5 and 6 present our experimental results and conclude the paper, respectively. symmetry strength (RSS) map and symmetry shape density (SSD) map to detect symmetry centers, and detects rotation symmetry folds via period signal relationships. The algorithm is unable to identify certain multiple symmetry centers, however, because it detects maximum peaks in a given image as a whole, i.e., it yields the highest numerical calculation values of RSS and SSD maps in the whole image. Small-scale symmetry centers have lower values than the highest numerically calculated values in the image, and are thus lost to detection. Further, the whole image must be computed twice for RSS and SSD maps, which is problematic because the computation is expensive and complex. Narrow FEP regions are also a problem, as the algorithm may eliminate real rotation symmetry regions that it regards as noise regions. A formula defect in Lee et al.’s methodology [14,15] prevents the correct RSS map from being identified over the course of repeated verification experiments. Many previous researchers have attempted to mitigate these problems. For example, Yousuke et al. [19] used an RSS map to obtain potential rotation symmetry centers and local features as a cue to rerank them and determine the maximum possible symmetry centers. Pan et al. [20] used a radius-based frieze-expansion method to obtain potential rotation symmetry centers in an RSS map. Their algorithm also suffers center loss because it utilizes the RSS map in the whole image. As a local method, Itti et al. [21] built an attention region detection algorithm suited to single or multiple symmetry center region detection that is still considered state-of-the-art. We used their codes (v2.3, July, 2013), in the symmetry center region detection algorithm described in this paper. Our algorithm exploits the advantages of both local methods and global methods to detect rotation symmetry centers. In our algorithm, the symmetry center region(s) is (are) considered to be a local region. In the local region, we compute the RSS map (global method in the local region) to obtain the highest possible numerically calculated value as the potential symmetry center. Our contribution is four-fold: (1) A saliency-based visual attention algorithm [21] is used to detect local region(s). The symmetry center in each local region can be detected with a local RSS map regardless of scale. This strategy avoids the defect of global methods. (2) Regular, small-scale, and skewed rotation symmetry centers can also be detected successfully via multiple-model computation. (3) Narrow symmetry regions can be detected successfully via the proposed algorithm. (4) Defect in the formula of RSS map can be eliminated. The remainder of this paper is organized as follows. The basic theory and research background are discussed in Section 2. The proposed 2. Basic theory background 2.1. DFT feature Chen et al. [22] denote the discrete signal (); () is the DFT coefficient. is the signal amplitude, is the sampling period, is the sample number, is the sample 2 let () = , = 0, 1, 2, … , − 1, > 0, > 0, > 0, () = ( ()), = 0, 1, 2, … , − 1. then () = = −1 ∑ =0 −1 ∑ =0 2 2 − = 2 (−) { = −1 ∑ 2 2 − =0 , = , 0, other index, and is the signal fold number indicating the number of full periods of the signal within the observed sample number. is the period length. |⋅| is the modulus operator. DFT(⋅) is the discrete Fourier transform operator. Because we are only concerned with , ∈ [1.. −1 ], the following 2 relationship holds: { max | ()| = , > 0, (1) −1 ]. = arg max | ()| = , , ∈ [1.. 2 Per Eq. (1), in a complex harmonic discrete signal, the index of the DFT maximum alternating current (AC) magnitude corresponds to the signal fold number. Based on this relationship, the single sine signal (Fig. 1(a)) contains the fold number of this signal as {2} (Fig. 1(b)). The single sine signal (Fig. 1(c)) contains the fold number of this signal as {4} (Fig. 1(d)). Per the linear feature of DFT, the compound signal (Fig. 1(e)) contains the fold numbers of this signal as {2, 4} (Fig. 1(f)). This relationship is the theoretical core of the FEP method [14,15,19,20,23]. 92 R. Huang et al. Signal Processing: Image Communication 60 (2018) 91–99 Table 1 Discrete symmetry groups in 2 [6]. Name Symbol Fold Atomic symmetry Cyclic Dihedral Orthogonal (2) 2 ∞ Rotation Rotation and Reflection Infinitesimal Rotation and Reflection to obtain potential symmetry centers (Fig. 3(i), (j)); this technique yields the results depicted in Fig. 3(e). The proposed algorithm, as mentioned above, uses a saliencybased visual attention algorithm [21] to obtain the local attention region(s) (Fig. 3(k)). In each local attention region, the local maximum of symmetry center probability from the local RSS map is used to identify potential symmetry centers (Fig. 3(l)). This technique identifies a greater number of obvious symmetry centers (Fig. 3(f)) than previously published methods [8,14,20]. A greater number of narrow symmetry regions (Fig. 3(f)) can also be found via the proposed algorithm; our algorithm is simpler, as well, as it only necessitates RSS maps (Fig. 3(l)). 3.1. Saliency-based visual attention A single topographical saliency map containing multi-scale image features can be obtained using the saliency-based visual attention algorithm [21,24,25]. Dyadic Gaussian pyramids [26] were used to create nine spatial scales which subsample the input image. These scales yield the horizontal and vertical image factors ranging from 1:1 (scale 0) to 1: 256 (scale 8). Akin to visual receptive fields, a set of linear ‘‘centersurround’’ operations compute each feature [27–31] as described by Eq. (2) [21], where ‘‘⊖’’ denotes point-by-point subtraction between two maps and ‘‘⊕’’ denotes point-by-point addition between two maps; ‘‘c, s’’ is the scale: , ∈ [0..8]. Center–surround is implemented by the difference between fine and coarse scales. Fig. 2. Examples of three types of rotation symmetry group in the 2D Euclidean space: Left: 5 is the cyclic group of fold 5 with rotation symmetries only; middle: 5 is the dihedral group of fold 2 × 5=10 with both rotation and reflection symmetries; and right: (2) is the orthogonal group of fold ∞ with infinitesimal rotation and reflection symmetries [6]. 2.2. Symmetry properties Except for detecting fold of rotation symmetry group, there are three group types need be distinguished, the cyclic ( ), the dihedral ( ) and the orthogonal (2) [6] (Table 1, Fig. 2). The fold-detection method and method for distinguishing group types are introduced in Section 3.3. = 3 1⨁ ( ) , 3 =1 4 ⨁ +4 ⎧ ⨁ ) ( ⎪ 1 = ||1 () ⊖ 1 ()|| , ⎪ =2 =+3 ⎪ 2 ⨁ 4 ⨁ +4 ( ⨁ ( )|) ⎪ | |2 () ⊖ −1 ⋅ 2 () | , = ⎨ 2 | | =1 =2 =+3 ⎪ [ 4 +4 ] ⎪ ⨁ ⨁ ⨁ ( ) ⎪ = | | |3 (, ) ⊖ 3 (, )| ⎪ 3 =2 =+3 ∈{0◦ ,45◦ ,90◦ ,135◦ } ⎩ 3. Rotation symmetry detection In the case of multiple rotation symmetry centers (Fig. 3(a), (b)), Loy et al. [8] used a feature detector to detect rotation symmetry and bilateral symmetry in a complex background (Fig. 3(g)). They were able to detect the symmetry center effectively, but not almost symmetry centers and the symmetry properties (Fig. 3(c)). Pan et al. [20] used a radius-based frieze-expansion method to obtain potential rotation symmetry centers with the same RSS map as Lee (2008) et al. [15]. Due to the defect of the RSS map in the whole image, they only detected the maximum RSS value peak (Fig. 3(h)) and thus achieved altogether unsatisfactory results (Fig. 3(d)). Lee (2010) et al. [14] also used the global maximum of symmetry center probability in RSS and SSD maps (2) 1 = , 2 = , 3 = . 1 , 2 and 3 respectively indicate intensity, color, and orientation features. With (), (), and () being red, green, and blue channels of a pixel point of the input image in scale, 1 (), 2 () and 3 (, ) are described by Eq. (3). Specially, 2 () denotes 21 () and 22 (); 3 (, ) Fig. 3. Comparison of rotation symmetry center location detection and rotation symmetry properties detection. (a) Original image. (b) Ground truth. (c) Result of Loy’s (2006) method [8]. (d) Result of Pan’s (2016) method [20]. (e) Result of Lee’s (2010) method [14]. (f) Result of proposed method. (g) Region computed by Loy’s (2006) method [8]. (h) RSS map computed by Pan’s (2016) method [20]. (i) RSS map computed by Lee’s (2010) method [14]. (j) SSD map computed by Lee’s (2010) method [14]. (k) Attended locations computed by proposed method. (l) Local RSS maps computed by proposed method. 93 R. Huang et al. Signal Processing: Image Communication 60 (2018) 91–99 is the oriented Gabor pyramid (, ). ⎧ () = 1 (() + () + ()) , ⎪ 1 3 ⎪ 3 ⎪21 () = (() − ()) , 2 ⎨ ⎪ () = 2() − (() + ()) + 1 |() − ()| , 22 ⎪ 2 ⎪ ⎩3 (, ) = (, ), ∈ [0..8], ∈ {0◦ , 45◦ , 90◦ , 135◦ }. (3) (⋅) is implemented in three steps [21]: (1) Values in the map are normalized to a fixed range [0..] to eliminate modality-dependent amplitude differences; (2) the location of the map’s global maximum is searched and the average ̄ of all other local maxima is computed; and (3) the map is globally multiplied by the value of ( − ) ̄ 2. is the saliency map computed by Eq. (2) [21]. For example, let ( ) = 1, = 2, = + 3 = 5, then ||1 (2) ⊖ 1 (5)|| yields one intensity temp map =2,=5 while other intensity temp maps can be obtained similarly: =2,=6 , =3,=6 , . . . , =4,=8 . By using ‘‘⊕’’, we can combine these maps into one intensity map. Again, other maps can be computed similarly. This process ultimately yields . The above algorithm rapidly selects region(s) in a computationally efficient manner.1 Given the default focus of attention (FOA) size and the default weight {1} to color features, the intensity features and orientation features are described accurately in the examples provided here. Per the inhibition-of-return mechanism [21,32,33], search region(s) are stopped if the same region has already been discovered (Fig. 3(k)). 3.2. Local RSS maps Based on Eq. (1), we know that the index ( ) of the DFT maximum alternating current (AC) magnitude corresponds to the signal fold number (); in other words, = . The difference of the ’s start position in DFT transform ( = 0, 1, 2, … , − 1 in the proposed method and = 1, 2, … , in Lee et al.’s work [14,15]), Lee et al. [14,15] asserted that −1 = . In this paper, we simplify the relationship and also fix a formula defect in Lee’s work [14,15]. The following algorithm reflects this simplification. A candidate rotation symmetry center, a region diameter, and an angle-step size are given and each diameter is re-aligned in array to build a horizontal FEP [14,15]. A 1D DFT is computed in each row of the FEP. At an image pixel (, ), let , (ℎ, ) represent the energy spectral density of a × FEP, where ∈ [0, − 1], ℎ ∈ [0, − 1]. and are the width and height of the FEP. The th energy spectral density of the DFT of the ℎth row, , (ℎ, ), is |−1 |2 2 | |∑ (4) , (ℎ, ) = || , (ℎ, )− || | | =0 | | where , (ℎ, ) is the th pixel value of the ℎth row. The RSS function at an image pixel (, ) is defined as follows [14] (, ) = −1 ∑ ℎ=0 where { 1, ℎ = 0, ℎ (, (ℎ, (ℎ))) (, (ℎ, )) , ( (ℎ), ( (ℎ))) = 0, otherwise. (5) Fig. 4. Comparison of the (ℎ) of Lee (2010),Lee (2008) [14,15] and the proposed method. (a) Original image. The blue circle is the indicatrix to be checked in the original image. (b) FEP of the original image. The blue line is the indicatrix to be checked. (We ignore the other symmetrical blue line.) (c) The energy spectral density of image shown in (b) row-by-row. The blue line is the indicatrix to be checked. (d) The energy spectral density row of DFT of the blue line in (c). The green line is the threshold over which , (ℎ, ) ≥ {, (ℎ, )| = 2, … , 2 } + ⋅ {, (ℎ, )| = 2, … , 2 }, = 2, = 90 is satisfied in Lee (2010),Lee (2008) [14,15]. The red circles indicate the peak indexes. (e) The energy spectral density row of DFT of the blue line in (c). The green line is the threshold for satisfying , (ℎ, ) ≥ {, (ℎ, )| = 1, 2, … , −1 }+ ⋅ 2 (6) (ℎ) is the index of alternating current (AC) magnitude of the ℎth row satisfying Eq. (7). In Lee et al. [14,15] ’s study, for Eq. (7), = 2, = 2, … , 2 , = 90, and Lee regarded (ℎ) − 1 as the correct symmetry fold but did not apply (ℎ) − 1 into operation of Eq. (6). This prevented the return of a correct RSS map over repeated verification experiments. In this paper, we use = 1, 2, … , −1 2 −1 } 2 −1 + ⋅ {, (ℎ, )| = 1, 2, … , } 2 , (ℎ, ) ≥ {, (ℎ, )| = 1, 2, … , 1 {, (ℎ, )| = 1, 2, … , −1 }, = 2, = 90 in proposed method. The red circles indicate 2 the peak indexes. (f), (g) Local RSS map with Lee (2010), Lee (2008) [14,15] methods. (h), (i) Local RSS map with proposed method. and (ℎ) as the correct symmetry fold to avoid this formula defect for Eq. (6) and to ensure accordance with the DFT algorithm. The defect is illustrated in detail in Fig. 4. Fig. 4(a), (b), and (c) show the resources of the energy spectral density of DFT in Fig. 4(d) and (e). (7) http://saliencytoolbox.net. 94 R. Huang et al. Signal Processing: Image Communication 60 (2018) 91–99 Fig. 5. Comparison of local RSS maps from different symmetry center models. Peak indicates potential symmetry center. (a) Attended locations and different symmetry center situations. (b) Results of applied (regular symmetry model). (c) Results of applied (small-scale, skewed symmetry model). (d) Results of applied fusion rule between and . Lee et al. [14,15] found that the symmetry folds respond to the − 1 in the 1D energy spectral density sequence (Fig. 4(d)) and observed the same repeated pattern indicating that all symmetry folds are multiples of the smallest symmetry fold. In the repeated verification experiment, (ℎ) = {5, 9} (Fig. 4(d)) does not satisfy Eq. (6), i.e., does not cause ℎ = 1 and makes (, ) lose the affection of the same repeated pattern (Fig. 4(f), (g)). Here, we use = 1, … , −1 ( = 0 is 2 the ignored DC magnitude) to obtain the peak indexes; (ℎ) = {4, 8}, as shown in Fig. 4(e), satisfies Eq. (6) by causing ℎ = 1 and making (, ) obtain the affection of the same repeated pattern (Fig. 4(h), (i)). In short: We fixed the formula defect. After finishing repeated verification experiments by fixing the formula defect, we found that there are two models between the regular symmetry center and small-scale, skewed symmetry center for computing a local RSS map (Fig. 5(a)). The regular symmetry center model only detects the potential regular symmetry center (Fig. 5(b)) while the smallscale, skewed symmetry center model only detects, per its namesake, potential small-scale, skewed symmetry centers (Fig. 5(c)). We used the following fusion rule (Eq. (8)) to differentiate these two models and obtain the total potential symmetry centers (Fig. 5(d)). ⎧ ⎪ , ⎪ , = ⎨ ⎪ , , ⎪0, ⎩ ∈ ̄ ∈ ∈ ̄ ∈ and ̄ and and and ̄ ∈ , ∈ , ∈ , ∈ . symmetry center position is (i.e., = ); (2) if there is in and there is not in (i.e., ̄ ∈ ), then the symmetry center position is (i.e., = ); (3) if there is in and there is in , then the symmetry center positions are and (i.e., = , ); (4) if there is not in and there is not in , then the symmetry center position does not exist in and (i.e., = 0). We adopted Eq. (2) to obtain the saliency maps of the local RSS map and used the inhibition-of-return mechanism [21] for peak visiting to extract local maxima in the local RSS map with the saliency maps asobtained in Eq. (2). ‘‘Peak visiting’’ means finding the maxima point as the peak in each saliency map from the local RSS map. We continued to extract the maxima (at the peak) above a certain threshold, () + ⋅ (), ( region was the same with the region of saliency map)( = 3.2 in our example), until the peak visiting was complete. The symmetry center position can be determined based on the extracted maxima position. There exists no extracted maxima situation, so there is no peak situation responding to ̄ or ̄ . 3.3. Segmented symmetry regions and properties In every row of FEP, a row corresponds to an index of maximum magnitude of this row. If there are the same indexes of maximum magnitude in consecutive rows of FEP, these rows are regarded as a symmetry region. We used the same gray image and FEP to segment symmetry regions (Fig. 6(a)∼(c)). In the narrow region of FEP, Lee’s method [14] eliminates the existing symmetry region regarded as noise and thus loses the real rotation symmetry region (Fig. 6(d)∼(f)). Our algorithm uses integer multiples of the smallest index method and the pipeline method to detect the real symmetry region. We observed that in the consecutive region, several rows (Fig. 6(c)) contain different indexes of maximum magnitude. Our algorithm first combines the different indexes to the same smallest index by integer multiples of the smallest index method. Thus the smallest index is regarded as the index of the row of FEP. (8) represents computing the local RSS map (Eq. (5)) with = 2, = 90 (Eq. (7)) for the regular symmetry center model. represents computing the local RSS map (Eq. (5)) with = −0.4, = 90 (Eq. (7)) for the small-scale, skewed symmetry center model. represents the symmetry center position in . ̄ indicates that the symmetry center position does not exist in . and ̄ function similarly. is the symmetry center position obtained via the fusion rule. The fusion rule requires that: (1) If there is in and there is not in (i.e., ̄ ∈ ), then the 95 R. Huang et al. Signal Processing: Image Communication 60 (2018) 91–99 Fig. 6. Detecting rotation symmetry regions and rotation symmetry properties via Lee’s (2010) method [14] versus the proposed method. (a) Gray image of original image: A pixel (the center) is regarded as a potential symmetry center. (b) FEP transformation. (c) Each row’s DFT magnitude result. DFT segmentation is only performed upon the center red line. (d) ∼ (f), Lee’s (2010) method [14]: The sum of DFT magnitudes, segmented frieze patterns, final result of rotation symmetry group detection. (g) ∼ (i), Proposed method corresponding to (d) ∼ (f). in this study contains about 108 test images.2 This dataset is available online as IEEE PAMI. The average runtime for these test images with the PC is 5 min. Some images consume more time due to complex backgrounds or larger sizes. Our comparative test results are shown in Fig. 7. The results are categorized as synthetic-single, synthetic-multi, real-single, and realmulti cases. As shown in Fig. 7(1-f), the narrow symmetry region was detected more accurately by our method than Lee’s method [14] (Fig. 7(1-e)) due to the use of integer multiples of the smallest index method and the pipeline method. As shown in Fig. 7(2-f), due to the use of the saliency-based visual attention algorithm, more obvious symmetry centers were found via our method than other methods [8,14,20] (Fig. 7(2-c), (2-d), (2-e)). As shown in Fig. 7(3-l), the use of local RSS maps by the saliency-based visual attention algorithm yielded a smaller searching scale than the global RSS/SSD map [14,20] (Fig. 7(3-h), (3-i), (3-j)). For the same reason, the obvious symmetry centers (Fig. 7(4-f)) were identified more accurately by our method than Lee’s [14] (Fig. 7(4-e)). Lee’s method [14] did yield more symmetry centers that were difficult to distinguish (Fig. 7(4-e)). These examples altogether indicate that multiple-local-region searching and multiple-model computation can be used to identify a large number of rotation symmetry centers and narrow symmetry regions successfully. As shown in Table 2, because local regions were used to detect symmetry centers, the recall rate reported here is higher than that of previous studies [8,20]. Because Lee’s method [14] uses the SSD map in a whole image, the recall rate of the proposed algorithm is lower — if the The pipeline method can then be applied to eliminate fluctuations in the presence of noise. In the given pipeline length (10 indexes length in our example), if the head and tail of sequence have the same index value (the length of head and tail is 3 indexes length in our example), we define it here as a pipeline. We used the pipeline to scan the index of the top row to that of the bottom row, each scanning along only a one-index length interval. If there was a difference in the middle of the pipeline, we defined it as noise and assigned it the same value as the head. This eliminated fluctuations and ultimately yielded stable symmetry region(s) (Fig. 6(h)) based on which the narrow symmetry region could also be detected accurately (Fig. 6(i)). Rotation symmetry properties were detected in the same manner as Lee’s method [14]. There is no vertical reflection in a frieze-expansion pattern of cyclic symmetry, while there is vertical reflection in a friezeexpansion pattern of dihedral symmetry. In the proposed method, the existence of vertical reflection in the frieze-expansion pattern is verified to differentiate cyclic symmetry from dihedral symmetry. Most of the magnitudes were zero in our experiment, signifying that there was a uniform region in the original image and further indicating the orthogonal rotation symmetry group, (2). 4. Algorithm complexity Let an image have × size. The subsampled pixels of the image are ( 2 ) and FEP is ( 1 ), thus, the complexity of the RSS map construction is ( 3 ) [15]. 5. Experimental results The proposed method was implemented in MATLAB on a PC with 3.7 GHz AMD 860 K CPU and 16 GB RAM. The test dataset we used 2 96 http://ieeexplore.ieee.org/ielx5/34/5530071/5276798/ttp2009990119.zip. R. Huang et al. Signal Processing: Image Communication 60 (2018) 91–99 Fig. 7. Comparison of rotation symmetry center location detection and rotation symmetry properties detection. 1-*: Synthetic-Single case; 2-*: Synthetic-Multi case; 3-*: Real-Single case; 4-*: Real-Multi case; (*-a) Original image. (*-b) Ground truth. (*-c) Result of Loy’s (2006) method [8]. (*-d) Result of Pan’s (2016) method [20]. (*-e) Result of Lee’s (2010) method [14]. (*-f) Result of proposed method. (*-g) Region computed by Loy’s (2006) method [8]. (*-h) RSS map computed by Pan’s (2016) method [20]. (*-i) RSS map computed by Lee’s (2010) method [14]. (*-j) SSD map computed by Lee’s (2010) method [14]. (*-k) Attended locations computed by proposed method. (*-l) Local RSS maps computed by proposed method. 97 R. Huang et al. Signal Processing: Image Communication 60 (2018) 91–99 Table 2 Quantitative Experimental Results. DataSet Method Precision Recall Number of Folds ∕ ∕(2) Synthetic (29 images/48 GT) Loy (2006) [8] Pan (2016) [20] Lee (2010) [14] Proposed Method 31∕34 = 92% 32∕37 = 87% 43∕55 = 79% 35∕42 = 84% 31∕48 = 65% 32∕48 = 67% 43∕48 = 90% 35∕48 = 73% 22∕49 = 45% 31∕54 = 58% 44∕62 = 71% 54∕73 = 74% ∕ 39∕54 = 73% 51∕62 = 83% 57∕73 = 79% Real-Single (58 images/58 GT) Loy (2006) [8] Pan (2016) [20] Lee (2010) [14] Proposed Method 50∕91 = 55% 26∕59 = 45% 44∕147 = 30% 36∕99 = 37% 50∕58 = 87% 26∕58 = 45% 44∕58 = 76% 36∕58 = 63% 16∕64 = 25% 18∕32 = 57% 35∕66 = 54% 30∕68 = 45% ∕ 21∕32 = 66% 54∕66 = 82% 47∕68 = 70% Real-Multi (21 images/78 GT) Loy (2006) [8] Pan (2016) [20] Lee (2010) [14] Proposed Method 32∕38 = 85% 19∕40 = 48% 53∕127 = 42% 47∕82 = 58% 32∕78 = 42% 19∕78 = 25% 53∕78 = 68% 47∕78 = 61% 12∕42 = 29% 13∕25 = 52% 40∕70 = 58% 46∕89 = 52% ∕ 16∕25 = 64% 53∕70 = 76% 63∕89 = 71% Overall (108 images/184 GT) Loy (2006) [8] Pan (2016) [20] Lee (2010) [14] Proposed Method 113∕163 = 70% 77∕136 = 57% 140∕329 = 43% 118∕223 = 53% 113∕184 = 62% 77∕184 = 42% 140∕184 = 77% 118∕184 = 65% 50∕155 = 33% 62∕111 = 56% 119∕198 = 61% 130∕230 = 57% ∕ 76∕111 = 69% 158∕198 = 80% 167∕230 = 73% GT, TP, FP, and FN indicate ‘‘Ground Truth’’, ‘‘True Positive’’, ‘‘False Positive’’, and ‘‘False Negative’’ in the experimental results, respectively. Precision= + , Recall= + . Rate of number of folds = number of correct folds in TP centers/number of true folds in TP centers. Rate of ∕ ∕(2) = number of correct ∕ ∕(2) in TP centers/number of true ∕ ∕(2) in TP centers. ∕ ∕(2) indicate symmetry group types: The cyclic group, dihedral group and orthogonal group [14]. An example of the failure case described above is shown in Fig. 8. We used the same gray image (Fig. 8(a)) to compare with Lee’s method [14] and the proposed method. The ground truth, artificially determined in advance, contains a certain ambiguity (Fig. 8(b)). Lee’s method [14] uses an RSS map to obtain the potential symmetry center (Fig. 8(c)). Because the RSS map is the global maximum algorithm, it loses the small-scale potential symmetry centers (marked with a blue + in Fig. 8(e)). Lee’s method [14] also uses an SSD map to obtain the potential symmetry center (Fig. 8(d)). The global maximum algorithm causes regular potential symmetry centers to be lost (marked with a red x in Fig. 8(e)). Lee’s method [14] fuses the RSS map and SSD map to yield the final result shown in Fig. 8(e). We used the saliency-based visual attention algorithm to obtain attended locations (Fig. 8(f)). The polymerization of complex objects facilitated the loss detection of the central region and the left corner region (Fig. 8(f)), but in the attended locations, the potential small-scale symmetry centers were still detected (Fig. 8(g), (h)). There were 30 failure cases in total (30∕184 = 16.3%) in which the saliency-based visual attention algorithm did not detect the symmetry center region in our experiment (108 test images, 184 ground truths). As shown in Fig. 9, the proposed algorithm’s precision is higher than Lee’s [14] when recall < 50 percentage due to the limited number local regions. Due to the defect in the saliency-based visual attention algorithm, the proposed algorithm’s recall is lower than Lee’s [14]. Pan’s [20] method’s precision is higher than that of the proposed algorithm’s when recall < 64 percentage, but Pan’s [20] recall is lower than that of the proposed algorithm. Loy’s [8] method’s precision is higher than the proposed algorithm’s when recall < 60 percentage, but Loy’s [8] recall is lower than ours. Fig. 8. Comparison of lost potential symmetry centers in previous [14] and proposed methods. (a) Original image. (b) Ground truth. (c) ∼ (e) RSS map, SSD map, and potential symmetry centers computed by Lee (2010) [14] method. In (e), true center (marked with a red x) comes from (c), and true center (marked with a blue +) comes from (d). (f) ∼ (h) Attended locations, local RSS maps, and potential symmetry centers computed by the proposed method. In (h), true center (marked with a red +) comes from (g). 6. Conclusion In this study, we exploited the advantages of both local methods and global methods to detect rotation symmetry centers. We used a novel strategy comprised of multiple-local-region searching (i.e., a saliency-based visual attention algorithm) to detect local regions and multiple-model computation to map RSS in the local region. To operate this technique, only calculations from RSS maps in local regions are necessary to detect symmetry centers. As opposed to previous methods, the proposed method allows small-scale symmetry centers and skewed symmetry centers to be successfully identified in addition to narrow symmetry regions based on the stable symmetry regions. In the future, we plan to improve the algorithm to be able to identify local regions as well. potential symmetry center region cannot be detected via the saliencybased visual attention algorithm. The proposed method would also lose the potential symmetry center in this case. Conversely, the precision rate of the proposed algorithm is higher than Lee’s [14] due to the limited number of local regions. The number of correct folds reported here is higher than that of previous methods [8,14,20] because narrow symmetry regions can be successfully detected. In a word, the proposed method can improve the number of detected symmetry centers but does lose potential symmetry centers if the saliency-based visual attention algorithm does not detect the symmetry center region. Despite this, the proposed method consistently improves the number of correct folds. 98 R. Huang et al. Signal Processing: Image Communication 60 (2018) 91–99 [7] M. Park, S. Lee, P.-C. Chen, S. Kashyap, A.A. Butt, Y. Liu, Performance evaluation of state-of-the-art discrete symmetry detection algorithms, in: IEEE Conference on Computer Vision and Pattern Recognition, 2008, CVPR 2008, IEEE, 2008, pp. 1–8. [8] G. Loy, J.-O. Eklundh, Detecting symmetry and symmetric constellations of features, in: European Conference on Computer Vision, Springer, 2006, pp. 508–521. [9] H. Cornelius, G. Loy, Detecting rotational symmetry under affine projection, in: 18th International Conference on Pattern Recognition, Vol. 2, ICPR’06, IEEE, 2006, pp. 292–295. [10] D. Shen, H. H.-S. Ip, E.K. Teoh, Robust detection of skewed symmetries, in: 15th International Conference on Pattern Recognition, 2000. Proceedings, Vol. 3, IEEE, 2000, pp. 1010–1013. [11] R.K. Yip, A Hough transform technique for the detection of parallel projected rotational symmetry, Pattern Recognit. Lett. 20 (10) (1999) 991–1004. [12] Y. Lei, K.C. Wong, Detection and localisation of reflectional and rotational symmetry under weak perspective projection, Pattern Recognit. 32 (2) (1999) 167–180. [13] A. Nasri, R. Benslimane, et al., A rotation symmetry group detection technique for the characterization of Islamic Rosette Patterns, Pattern Recognit. Lett. 68 (2015) 111–117. [14] S. Lee, Y. Liu, Skewed rotation symmetry group detection, IEEE Trans. Pattern Anal. Mach. Intell. 32 (9) (2010) 1659–1672. [15] S. Lee, R.T. Collins, Y. Liu, Rotation symmetry group detection via frequency analysis of frieze-expansions, in: IEEE Conference on Computer Vision and Pattern Recognition, 2008, CVPR 2008, IEEE, 2008, pp. 1–8. [16] Y. Keller, Y. Shkolnisky, A signal processing approach to symmetry detection, IEEE Trans. Image Process. 15 (8) (2006) 2198–2207. [17] J.H. Gunther, Simultaneous DFT and IDFT of real N-point sequences, IEEE Signal Process. Lett. 9 (8) (2002) 245–246. [18] J. Proakis, D. Manolakis, Digital Signal Processing, third ed. Prentice Hall, 1996. [19] I. Yousuke, T. Kanji, Detecting rotational symmetry via global/local image analysis, in: IAPR, 2013, pp. 387–390. [20] G. Pan, D. Sun, Y. Chen, C. Zhang, Multiresolution rotational symmetry detection via radius-based frieze-expansion, J. Electr. Comput. Eng. 2016 (2016) 2. [21] L. Itti, C. Koch, E. Niebur, A model of saliency-based visual attention for rapid scene analysis, IEEE Trans. Pattern Anal. Mach. Intell. (11) (1998) 1254–1259. [22] Y. Chen, Information Signals and Systems, Sichuan University Press, 2003. [23] S. Lee, Y. Liu, Curved glide-reflection symmetry detection, IEEE Trans. Pattern Anal. Mach. Intell. 34 (2) (2012) 266–278. [24] B.J. White, D.P. Munoz, Neural mechanisms of saliency, attention, and orienting, in: Computational and Cognitive Neuroscience of Vision, Springer, 2017, pp. 1–23. [25] J. Han, Y. Ma, J. Huang, X. Mei, J. Ma, An infrared small target detecting algorithm based on human visual system, IEEE Geosci. Remote Sens. Lett. 13 (3) (2016) 452– 456. [26] H. Greenspan, S. Belongie, R. Goodman, P. Perona, S. Rakshit, C.H. Anderson, Overcomplete steerable pyramid filters and rotation invariance, in: 1994 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 1994. Proceedings, CVPR’94, IEEE, 1994, pp. 222–228. [27] V. Casagrande, T. Norton, Lateral geniculate nucleus: a review of its physiology and function, Neural Basis Vis. Funct. 4 (1991) 41–84. [28] S. Engel, X. Zhang, B. Wandell, Colour tuning in human visual cortex measured with functional magnetic resonance imaging, Nature 388 (6637) (1997) 68–71. [29] M. Spitschan, R. Datta, A.M. Stern, D.H. Brainard, G.K. Aguirre, Human visual cortex responses to rapid cone and melanopsin-directed flicker, J. Neurosci. 36 (5) (2016) 1471–1482. [30] J. Jiang, C. Summerfield, T. Egner, Visual prediction error spreads across object features in human visual cortex, J. Neurosci. 36 (50) (2016) 12746–12763. [31] R. Arya, N. Singh, R. Agrawal, A novel combination of second-order statistical features and segmentation using multi-layer superpixels for salient object detection, Appl. Intell. (2016) 1–18. [32] C. Koch, S. Ullman, Shifts in selective visual attention: towards the underlying neural circuitry, in: Matters of Intelligence, Springer, 1987, pp. 115–141. [33] H. Pashler, Attention, Psychology Press, 2016. Fig. 9. Precision–Recall on dataset: Precision= + , Recall= + . T is the allowed maximum number of rotation symmetry centers varying from 1 to ∞. Acknowledgments The authors would like to thank Itti et al. [21] for the saliencybased visual attention algorithm source code and to Lee et al. [14] for the rotation symmetry test images. This work was supported by NSFC under Grant No. 61571313, No. U1633126, National Key Research and Development Program under Grant No. 2016YFB0800600. Appendix A. Supplementary data Supplementary material related to this article can be found online at http://dx.doi.org/10.1016/j.image.2017.09.010. References [1] S.J. Anderson, D.C. Burr, Spatial and temporal selectivity of the human motion detection system, Vis. Res. 25 (8) (1985) 1147–1154. [2] M.C. Morrone, J. Ross, D.C. Burr, R. Owens, Mach bands are phase dependent, Nature 324 (6094) (1986) 250–253. [3] P. Kovesi, et al., Symmetry and asymmetry from local phase, in: Tenth Australian Joint Conference on Artificial Intelligence, Vol. 190, Citeseer, 1997, pp. 2–4. [4] G. Heidemann, Focus-of-attention from local color symmetries, IEEE Trans. Pattern Anal. Mach. Intell. 26 (7) (2004) 817–830. [5] G. Kootstra, A. Nederveen, B. De Boer, Paying attention to symmetry, in: British Machine Vision Conference, BMVC2008, The British Machine Vision Association and Society for Pattern Recognition, 2008, pp. 1115–1125. [6] Y. Liu, H. Hel-Or, C.S. Kaplan, Computational Symmetry in Computer Vision and Computer Graphics, Now Publishers Inc., 2010. 99

1/--страниц