AHiLS—An Algorithm for Establishing Hierarchy among Detected Weak Local Reflection Symmetries in Raster Images

David Podgorelec

^1,*

Ivana Kolingerová

Luka Lovenjak

and

Borut Žalik

Faculty of Electrical Engineering and Computer Science, University of Maribor, Koroška Cesta 46, SI-2000 Maribor, Slovenia

Department of Computer Science and Engineering, University of West Bohemia, Technická 8, 306 14 Plzen, Czech Republic

Author to whom correspondence should be addressed.

Symmetry2024,16(4), 442;https://doi.org/10.3390/sym16040442

Submission received: 16 January 2024 /Revised: 8 March 2024 /Accepted: 1 April 2024 /Published: 6 April 2024

(This article belongs to the SectionComputer)

Downloadkeyboard_arrow_down

Browse Figures

Versions Notes

Abstract

A new algorithm is presented for detecting the local weak reflection symmetries in raster images. It uses contours extracted from the segmented image. A convex hull is constructed on the contours, and so-called anchor points are placed on it. The bundles of symmetry line candidates are placed in these points. Each line splits the plane into two open half-planes and arranges the contours into three sets: the first contains the contours pierced by the considered line, while the second and the third include the contours located in one or the other half-plane. The contours are then checked for the reflection symmetry. This means looking for self-symmetries in the first set, and symmetric pairs with one contour in the second set and one contour in the third set. The line which is evaluated as the best symmetry line is selected. After that, the symmetric contours are removed from sets two and three. The remaining contours are then checked again for symmetry. A multi-branch tree representing the hierarchy of the detected local symmetries is the result of the algorithm.

Keywords:

computer science;algorithm;computer vision;computational geometry;shape features

1. Introduction

Symmetry is a fundamental and versatile concept with applications in mathematics [1,2,3], natural sciences [4], architecture [5], arts [6], engineering [7,8,9], and elsewhere [10,11]. Through evolution, symmetry perception has become an important integral part of an individual’s perceptual organisation process [12]. It is mostly understood as a positive and desirable property, which has been recognised in studies of mating and food choice habits of many animal species already [13]. In humans, this concept is further generalised to broader perceptions of aesthetics, health, safety, and stability. Symmetry applies to various abstractions, but is most often associated with visual perception, which is characterised by the detection and interpretation of distances (depth and size) and colours. Within the human’s visual system, symmetries facilitate the segmentation of the seen scene, object analysis and representation [14]. Unsurprisingly, computer applications of symmetries, once they have been detected, also mostly address these tasks. In computing, the symmetry phenomenon may play an important role in image processing [15], computer vision and computer graphics [16], cryptography [17], and geometric modelling [18]. However, in contrast to natural, almost self-evident symmetry perception processes in humans and several animal species, symmetry detection is anything but a simple task for a computer [19].

An object or a system (a set of points in our case) is symmetric if there is a transformation, such as a translation, rotation, reflection, or a combination of these, that maps onto itself [20]. Formally, if

P

denotes a set of points and

T

some geometric transformation, then

P

is symmetric when

\forall p \in P : T (p) \in P .

(1)

When

P

corresponds to the entire considered set of points, then Equation (1) represents global symmetry. On the other hand, local symmetry addresses a subset of the input set of points. It is also sometimes called partial symmetry [14].

In practice, however, Equation (1) is rarely satisfied exactly for all elements of

P

. Any observation of the physical world is subject to error, whether by human vision or by remote sensing. As a consequence, we can only expect an exact match between two points in a symmetric pair in the case of synthetic or rounded data. Instead of perfect (exact, strong) symmetry, we thus consider weak (or approximate) symmetry [21,22]. This can be described formally by Equation (2).

\forall p \in P, \exists p^{'} \in P : (T (p^{'}) \in P) \land (∥ T (p) - T (p^{'}) ∥ < ϵ),

(2)

where

ϵ

is a small positive tolerance value. Note that Equation (2) does not require

T (p) \in P

The distinction between weak and perfect symmetry concerns both global and local symmetry. Local symmetries can contain patterns and repetitions that are often not identified easily by humans, in contrast to global symmetry, where humans are extremely skilful at its detection [19,23]. Similarly, humans can easily detect and interpret local symmetries of isolated objects and their exposed parts in a similar way to global symmetries. On the other hand, no symmetry is trivial for a computer, but computer algorithms can use a lot of processing power even in situations with a huge number of less noticeable symmetries, which can also intersect, nest inside each other, or extend over individual tiny details. The algorithm from [14], for example, detects more than 8500 local reflection symmetries in a complex 3D scene of floor, buildings, and trees with more than 270,000 LiDAR points in 3 min by using a single-threaded CPU processing on a regular personal computer. In a slightly simpler scene with 125,000 points and no trees, it finds almost 25,000 symmetries in less than half a minute, which of course drastically exceeds the capabilities of a human. However, to use the detected symmetries in, e.g., scene segmentation or object analysis, it is not enough for the algorithm to find as many symmetries as possible, but it also needs to structure them appropriately. This is precisely the aim of this paper. The proposed algorithm for detecting and establishing a hierarchy of the weak local symmetries in raster images (the acronym AHiLS is used from here on), thus, also determines hierarchical relationships among the found weak local reflection symmetries, if they exist. The aim of this paper is not only to find weak local symmetries, but also hierarchical relationships among them, if they exist. We consider weak symmetry when talking about symmetry from here on.

To our knowledge, no methods in the past have addressed the same challenges as the proposed approach. The main novelties introduced by AHiLS are the following:

a new algorithm for weak local symmetry detection in raster images;
performing symmetry detection on extracting contours previously extracted from the raster image;
using a convex hull of contours to determine the positions of potential symmetry line candidates;
representing hierarchical dependencies by a multi-branch tree for further processing.

This paper consists of five Sections.Section 2 gives an overview of the most similar previous works. The proposed method is described inSection 3 and its results are given inSection 4. A discussion and suggestions for future work are given inSection 5.

2. Related Works

Most of the previous work concentrates on perfect symmetry. Some methods compare either two halves of the contours or skeletons of the object [24,25,26,27], or analyse halftone images [28]. Zahn and Roskies [29] and Yip at al. [30] find symmetries in geometric objects segmented from high-quality images. However, in real life, images can be undersampled, which introduces additional errors. The algorithm by Loy and Eklundh [31] extracts feature points first from an image using SIFT transform [32], which is invariant on scaling and rotation. SIFT also constructs a descriptor for each feature point. A reflected image is generated after that, and SIFT is applied to it too. A new set of feature points and their descriptors are obtained in this way. These descriptors are reflected after that, and faced for matching against the descriptors obtained from the original, non-reflected image. The matched descriptors form pairs. These pairs are used to define the symmetry lines, which are accumulated into the Hough-style voting space [33]. The most dominant symmetry lines are then selected. O’Mara and Owens in [34] present a method for the detection of the dominant plane of symmetry in medical images of an arbitrary dimension with the aim of measuring the degree of detected symmetries. Sun and Si published a reflectional symmetry detection algorithm for greyscale images [35]. Axes of symmetry for an object in the image are detected on the basis of the gradient information of the image and the Fourier transformation. The algorithm described in [36] generates the candidates for the axes of symmetry and then searches for the optimal axis by reflecting the candidates against these axes. Hauagge and Snavely [37] extracted local features from images of architectural scenes, based on local symmetries’ detection and extraction. They matched pairs of photos of urban scenes according to these features. The features were based on the measures of the local reflection and rotational symmetries, computed by the so-called local image operations.

Van Gool et al., in [38], discuss the detection and usage of symmetry in planar shapes. Symmetry is interpreted as repeated, coplanar shape fragments. These fragments are tested on whether they are symmetric. The so-called arc length space is proposed, in which the symmetric shape fragments correspond to straight-line segments, which are detected and analysed easily. The algorithm proposed by Derrode and Ghorbel [39] uses the analytical Fourier–Mellin transform to assess motion parameters between grey-level objects having the same shape with distinct scales and orientations. Both rotational and reflection symmetries can be detected and estimated in objects. Karkischenko and Mnukhin [28] propose an algorithm for rotational symmetry detection in grey-level digital images, based on the concept of Gaussian fields and a special log-polar representation of digital images. Gnutti et al. [40] address the problem of reflection symmetry detection. A metric is designed that extracts subsets of consistently oriented candidate segments. These segments are ranked on the basis of the surrounding gradient orientation specularity. The used operations are considered to be related to the way the human brain detects symmetry.

In comparison to the existing approaches, the proposed algorithm handles more general types of input data and is simple to understand. Although it is demonstrated on raster images, it can also be applied directly to geometric objects, whose borders are represented by contours. In addition, it detects the hierarchies of the local symmetries and returns this information explicitly in the multi-branch tree. Hierarchical dependencies between symmetries have been considered less often. The algorithm in [41] combines a continuous symmetry measure with a multiresolution scheme to detect hierarchical symmetry and almost-symmetrical patterns. Ref. [42] presents a symmetry hierarchy constructed from the initial graph via recursive graph contraction, which either groups parts by symmetry or assembles connected sets of parts. The method is designed for meshed man-made models. In [19], 2D or 3D objects with or without holes are found using the algorithm, where a uniform grid and a symmetry estimation function are utilised. Li et al. [43] predict poses of a 3D assembly by using a single 2D image with the assembly in a considered pose and a set of point clouds of individual parts of the assembly. The reflection symmetry is an important, but is not the only feature used to describe the poses. Paschalidou et al. [44] address a similar problem of learning and predicting an unsupervised decomposition of a 3D object, extracted from a single 2D image, into a hierarchical structure of parts. Xue et al. [45] proposed a novel unsupervised approach to process urban LiDAR point clouds to a hierarchy of objects based on their characteristic symmetric cross-sections. The method, called Clustering Of Symmetric Cross-sections of Objects (COSCO), was primarily used to detect and classify cars, which are then replaced by free 3D car models in a digital twin city. Villanueva et al. [46] use symmetries for compression of sparse voxel grids. Originally, two subtrees could be merged on the basis of similarity or connectivity, which they extended to the use of reflection symmetries as well. In this manner, the concept of Sparse Voxel Directed Acyclic Graphs (SVDAGs) was upgraded into the Symmetry-Aware Sparse Voxel Directed Acyclic Graphs (SSVDAGs), which were further analysed by Madoš et al. [47]. Although all these methods use a similar concept of symmetry-aware hierarchical organisation of spatial data, they were designed for different purposes, and thus, none of them is directly comparable to AHiLS. Some allow only a hierarchical division perpendicular to the symmetry axis or plane [19,45], some are designed from the bottom up and use other principles of grouping subtrees together with symmetry [42,43,44], and some are restricted to global symmetry detection [19].

3. Materials and Methods

In the following section, the elements of

P

correspond to pixels

p_{x, y}

in a colour raster image, i.e.,

p_{x, y} \in P

0 \leq x < X

0 \leq y < Y

, whereX andY define the image resolution, while the transformation

T

is restricted to the reflection/mirroring. AHiLS executes several steps to determine the hierarchy among the weak local reflection symmetries. The pseudocodes in Algorithms 1 and 2 give the sequence of these steps, which are explained afterwards.

Algorithm 1 The main algorithm of the AHiLS

1:: function AHiLS( $P$ )
2:: ▹ Function accepts a colour image $P$ and returns the multi-branch tree $T$ representing the weak local symmetries.
3:: InitialiseParameters( $R_{c}$ ,t,b,d);
4:: $S$ = ApplyColourSegmentation( $R_{c}$ );
5:: $S$ = Filter( $S$ );
6:: $C$ = ExtractsContours( $S$ );
7:: $l e v e l = 0$ ;
8:: $T = N I L$ ;
9:: repeat
10:: $(Γ, T) =$ DFS( $C$ , $l e v e l$ ,b,d, $T$ );
11:: $C = C - Γ$ ;
12:: until $Γ = \emptyset$ ;
13:: return $T$ ;
14:: end function

AHiLS accepts

P

(for example, the image shown in Figure 1a) and performs the initialisation steps within lines 3–8 in Algorithm 1 as follows:

The necessary parameters, explained in the following, are set in line 3.
$P$ is segmented based on colours (line 4 in Algorithm 1), where a user specifies the range $R_{c}$ of the desired colours. Pixels with colours outside $R_{c}$ are set to black. The segmented image $S$ , suitable for further processing, is obtained in this way (seeFigure 1b). The segment consists of a set of four connected pixels and should be large enough. In our implementation, the segment is accepted when it contains at least 1% of all pixels in $S$ .
$S$ is converted into greyscale, filtered to reduce the noise, and smoothed in line 5. For this, Gaussian blur and morphological erosion are applied [48].
The set $C$ of contours $C_{i}$ , $0 \leq i < | C |$ , bordering the segments, is extracted from $S$ using a $5 \times 5$ kernel [48] in line 6. Fifty contours were obtained in our case (Figure 1c).
The level of the hierarchy and the multi-branch tree $T$ are initialised in lines 7 and 8.

Algorithm 2 A depth-first search investigation of contours

1:: function DFS( $C$ , $l e v e l$ ,b,d, $Γ$ , $T$ )
2:: H = DetermineConvexHull( $C$ );
3:: $A$ = PlaceAnchorPointsOnHull(H,d);
4:: $Γ = \emptyset$ ; $Γ_{A} = \emptyset$ ; $Γ_{B} = \emptyset$ ; $Γ_{P} = \emptyset$ ;
5:: for $a \leftarrow 0$ to $| A | - 1$ do ▹ for all bundles of lines
6:: $L$ = PlaceBundleOfLinesInAnchorPoint( $p_{a}$ ,b);
7:: for $s \leftarrow 0$ to $b - 1$ do ▹ for all lines in a bundle
8:: ( $C_{A}$ , $C_{B}$ , $C_{P}$ ) = ClassifyContours( $C$ , $l_{s} \in L$ );
9:: if $C_{A} \neq \emptyset$ and $C_{B} \neq \emptyset$ then
10:: $C_{B}^{R} =$ Reflect( $C_{B}$ , $l_{s}$ );
11:: ( $L i s t O f P a i r s$ , $L i s t O f C o v e r a g e s$ ) = FindSymmetricPairs( $C_{A}$ , $C_{B}^{R}$ ,t);
12:: $Γ_{P} = Γ_{P} \cup$ StorePairsAndCoverages( $L i s t O f P a i r s, L i s t O f C o v e r a g e s$ );
13:: end if
14:: end for ▹ for all lines in a bundle
15:: for $q \leftarrow 0$ to $| C_{P} | - 1$ do ▹ for all contours in $C_{P}$
16:: $c_{q} =$ CalculateSelfSymmetricCoverage( $C_{q} \in C_{P}$ );
17:: if $c_{q} > t$ then
18:: $(Γ, T) =$ StoreSelfSymContourAndAddItToTree( $c_{q}, l_{s}$ , $Γ$ , $T$ );
19:: end if
20:: end for ▹ for all contours in $C_{P}$
21:: end for ▹ for all bundles of lines
22:: $l_{b e s t} =$ SelectBestLineFromStorage( $Γ_{P}$ );
23:: if $l_{b e s t} \neq N I L$ then
24:: $(Γ, T) =$ FormPairsAndAddThemToTree( $l_{b e s t}$ , $l e v e l$ , $Γ$ , $T$ );
25:: ( $C_{A}$ , $C_{B}$ , $C_{P}$ ) = ClassifyContours( $C$ , $l_{b e s t}$ );
26:: $(Γ_{A}, T) =$ DFS( $C_{A}$ , $l e v e l + 1$ ,b,d, $T$ );
27:: $(Γ_{B}, T) =$ DFS( $C_{B}$ , $l e v e l + 1$ ,b,d, $T$ );
28:: end if
29:: return $(Γ \cup Γ_{A} \cup Γ_{B}, T)$
30:: end function

The algorithm enters the main loop after that. Function DFS (line 10) finds in the depth-first search order the symmetric contours and returns them in set

Γ

, together with the constructed multi-branch tree

T

. The found symmetric pairs of contours are removed from

C

in line 11 and the whole process repeats with the reduced set of contours. The loop terminates when DFS returns an empty

Γ

. The multi-branch tree is returned at the end (line 13).

The core of AHiLS is realised in the recursive function DFS, shown in Algorithm 2.Figure 2a is used to clarify the explanation.

Convex hullH [49] is constructed from contours $C_{i}$ , $0 \leq i < | C |$ at first (line 2 in Algorithm 2). The set $A$ of so-called anchor points $p_{a}$ is placed along the convex hull’s edges uniformly (line 3), as shown inFigure 2b. The distanced between the consecutive anchor points onH is specified heuristically (in our case $d = 5$ was used as a default) or entered by the user. The number of anchor points is reduced drastically by placing them onH instead of, for example, distributing them uniformly inside the whole $S$ .
A bundle $L$ of potential symmetry lines $l_{s}$ , $0 \leq s < 180 / b$ , $b \in {1, 2, 4, 5, 10}$ , with slopes $α = b \cdot s$ , is laid through $p_{a}$ (seeFigure 3a) in line 6.b is set by default to 5, resulting in $| L | = 36$ lines.
The contours in $C$ are classified according to $l_{s} \in L$ . Namely, $l_{s}$ determines two half-planes, and (in some cases) splits $C$ into three sets (seeFigure 3b):
- set $C_{A}$ contains contours being located completely in the first half-plane;
- set $C_{B}$ includes contours from the opposite half-plane;
- set $C_{P}$ stores those contours that are pierced by $l_{s}$ .
Those sets are obtained by the function in line 8. If one of the sets $C_{A}$ or $C_{B}$ is empty, $l_{s}$ is not the line of symmetry for any pairs of contours. Otherwise, $C_{A}$ and $C_{B}$ must be tested additionally as follows.
- Contours from $C_{B}$ are reflected over $l_{s}$ to obtain set $C_{B}^{R}$ in line 10 (seeFigure 4a).
- The similarity of the contours in $C_{A}$ and $C_{B}^{R}$ is checked. The coverage percentage of the two considered contours is calculated for this. The two contours are paired and returned in the $L i s t O f P a i r s$ in line 11 if the coverage percentage is greater than the thresholdt. The percentage of coverage is returned in the list $L i s t O f C o v e r a g e s$ . The thresholdt is set at $90 %$ in our implementation. However,t can be determined interactively by the user. Its effect is demonstrated later inSection 4.
- This information is then stored in a temporal storage $Γ_{P}$ in line 12 of Algorithm 2.
The algorithm selects the best line of symmetry $l_{b e s t}$ in line 22 after processing all $l_{s}$ candidates from all $p_{a} \in A$ . The criterion for selection is the highest number of reflection contour pairs determined by this line. The line with the highest percentage of contour coverage is selected if more lines have the same number of pairs.
The contours in $C_{P}$ are checked for self-symmetry (seeFigure 4b) in lines 15–20. Those that are symmetric are stored in $Γ$ and inserted into $T$ .
If $l_{b e s t}$ exits, the DFS is called recursively with sets $C_{A}$ and $C_{B}$ in lines 26 and 27 in Algorithm 2.
The information about the found symmetries stored in $Γ$ is, together with the multi-branch tree, returned to the main part of the algorithm at the end. The multi-branch tree for our example is shown inFigure 5.

4. Results

Figure 6 shows AHiLS’s results when varying the parametert, which represents the coverage percentage. This is the most important of the three user-defined parameters in AHiLS. Setting it would require intensive study from the human-sense perspective to obtain the most expected results. Namely, humans are not very skilful at determining local symmetries in contrast to global ones. The other two parameters,b andd, were set as a compromise between AHiLS’s accuracy and its spent CPU time, as they directly affect the number of symmetry line candidates in each bundle and the number of anchor points along the convex hull, respectively. They are set to

b = 2

and

d = 5

in the test example inFigure 6. Only one symmetry line was detected when

t = 50

%. The symmetric contours are plotted in red while the others are in grey (seeFigure 6a). However, there were more lines of symmetry discovered by increasingt, as seen inFigure 6b. Different colours are used to show which contours and axes of symmetry belong together. In addition, some contours were also detected as being self-symmetric whent was further increased (Figure 6c,d).

Figure 7 shows the multi-branch tree obtained for

t = 70

%. Note that the symmetry lines at level 1 are similar, but not exactly the same. Consequently, three branches were obtained instead of a single one, which corresponds toFigure 6b.

Finally, a comparison was made with the method proposed by Loy and Eklundh [31]. As already mentioned, we have not found any comparable method that would hierarchically organise the detected symmetries in a 2D image in a similar way as AHiLS. Therefore, we were looking for a method that would at least pre-segment and filter the image, or otherwise incorporate some semantic relations in the symmetry detection rather than pixel colours alone. Thus, the Loy and Eklundh (L&E in continuation) method was chosen, which bases the detection on a prior identification of feature points. However, this approach does not filter out the background, which often appears dominant in at least one of the detected symmetries. Since the L&E method does not build a hierarchical structure but only finds a selected number of the strongest symmetries, we used only the topmost level in the multi-branch tree in AHiLS to make the comparison fairer. The numbers of symmetries in the L&E method were set to the number of tree nodes considered in AHiLS (increased by 1 for the strongest background symmetry). Different colours inFigure 8b,d,f are used to bind the symmetry lines to the corresponding contours.

The symmetries found in the butterfly example (Figure 8a,b) are quite similar for both methods. Here, the background is highly asymmetrical (predominantly blue in the left half of the image and green in the right half), so the strongest symmetries are dominated by parts of the butterfly even in the L&E method. In the case of dandelion flowers, however, the L&E algorithm detected two strong symmetries with the vertical axes near the centre ofFigure 8c. The left one refers to the symmetry of the green leaves, while the right one additionally takes into account the soil. The least steep symmetry axis also refers to the green leaves and the soil, while the fourth, steeper, axis roughly bisects the flower on the bottom left and the stone below it. On the other hand, AHiLS, where

R_{c}

was restricted to shades of yellow, first found symmetry through the two flowers on the left, indicated by magenta, and then found the self-symmetry of the third flower, indicated by cyan inFigure 8d. If AHiLS was not a hierarchical algorithm, it would also find the symmetries through the remaining two pairs of the trio of flowers. In the third example, showing three seagulls flying under blue sky, the L&E algorithm detected two strong symmetries nearly through the centre ofFigure 8e, where the vertical one corresponds to the background, while the oblique one considers both the sky and the birds. The third symmetry axis considers the rightmost seagull and its local surroundings. Note that this and the leftmost seagull are two identical copies, but the local symmetry of the latter is only at the tenth position due to the higher influence of the middle bird. As expected, AHiLS found here the local self-symmetries of the two identical seagull copies, highlighted in magenta and light green inFigure 8f. It should be noted that the light green axis is not identical to the third red axis of symmetry from the L&E algorithm, as the latter is also affected by the adjacent seagull and the background.

As can be seen, AHiLS not only found more meaningful lines of symmetries, but it was also able to define the exact regions of the symmetry in

S

. However, the price for this is a much slower performance. The L&E method needs 0.69 s, 1.19 s, and 0.40 s for the results inFigure 8a,Figure 8c, andFigure 8e, respectively. On the other hand, AHiLS needs 825.22 s, 189.13 s, and 166.88 s for the results inFigure 8b,d,f. Deeper levels of the tree in principle take less time, as we no longer have to deal with objects pierced by the axis of symmetry at a higher level. Also, the convex hulls are becoming shorter, which means far fewer anchor points. Nevertheless, run times are increased by a further factor of 2 to 3 when DFS is performed recursively.

The tests were run on a laptop computer with an 11th Gen Intel(R) Core(TM) i7-1165G7 processor @ 2.80 GHz, 2803 MHz, with four cores, eight logical processors, and with 16.0 GB RAM, under the Microsoft Windows 11 Home operating system. The software was written in Python. The resolution of the butterfly image was

1600 \times 915

pixels, while the other two test images had resolutions of

1200 \times 900

pixels.

5. Conclusions

This paper introduces a novel method for determining weak local reflection symmetries and their hierarchical dependencies in raster images and returns the information about them in a multi-branch tree. Although the method was tested on raster images, it can also be applied without any changes to non-rasterised cases, when the geometry of the presented shapes is described by their boundaries (by contours in AHiLS terminology). The obtained multi-branch tree allows a comprehensive analysis of the detected symmetries in the later post-processing phases.

In addition to the original idea to hierarchically detect and organise symmetries from top to bottom, the main advantage of AHiLS is its flexibility. Three user-defined parameterst,b, andd play an important role in the symmetry detection. Furthermore, a user can also set the colour range

R_{c}

for filtering and segmentation of the image prior to symmetry detection. However, with so many parameters, the challenge for future work is to automatically recommend their values based on image and user characteristics. An obvious weakness of AHiLS is its slowness. The method can, however, be parallelised easily. A divide and conquer approach, as suggested in [19], should thus also be tried within AHiLS. Furthermore, calculation of coverages could be avoided if the two contours already differ in length by more than the set thresholdt. Note that a coverage between the same pair of contours is calculated separately for every symmetry line candidate through each anchor point. Testing the anchor points is also highly time consuming, therefore a smarter anchor point selection could significantly improve the performance. Finally, the AHiLS methodology should also be adapted for other types of symmetries, first of all for rotational symmetry.

Author Contributions

Conceptualisation, B.Ž. and I.K.; methodology, B.Ž. and L.L.; software, L.L.; validation, B.Ž. and D.P.; investigation, B.Ž., I.K., L.L. and D.P.; resources, I.K.; writing—original draft preparation, L.L. and I.K.; writing—review and editing, B.Ž. and D.P.; visualisation, L.L.; supervision, B.Ž.; project administration, I.K.; funding acquisition, I.K. All authors have read and agreed to the published version of the manuscript.

Funding

This research was funded by the Slovene Research and Innovation Agency under Research Project N2-0181 and Research Programme P2-0041, and the Czech Science Foundation under Research Project 21-08009K.

Data Availability Statement

No new data were created or analysed in this study. Data sharing is not applicable to this article.

Conflicts of Interest

The authors declare no conflicts of interest.

Abbreviations

The following abbreviations and symbols are used in this manuscript:

$α$	Slope angle of a considered $l_{s}$ , i.e., $α = b \cdot s$ , $0 \leq s < 180^{\circ} / b$
$Γ$	Set of symmetric contours
$Γ_{A}$	Output set of symmetric contours from the recursive call DFS( $C_{A}$ ,…)
$Γ_{B}$	Output set of symmetric contours from the recursive call DFS( $C_{B}$ ,…)
$Γ_{P}$	Temporal storage of symmetric pairs and coverage values
$ϵ$	Small positive tolerance value
a	Loop index for anchor points
A	Set of anchor points along the convex hullH
AHiLS	Algorithm for establishing hierarchy of weak local symmetries in raster images
b	User parameter for setting the slope step ( $180^{\circ} / b$ ) for lines $l_{s}$ in a bundle
$C$	The set of contours (borders of segments from $S$ ; formal parameter of DFS)
$C_{A}$	Set of contours completely in one half-plane defined by line $l_{s}$
$C_{B}$	Set of contours from the opposite half-plane to the one containg $C_{A}$
$C_{i}$	Contours from the set $C$ , $0 \leq i < \| C \|$
COSCO	Clustering of Symmetric Cross-Sections of Objects
$C_{P}$	Set of contours being pierced by $l_{s}$
CPU	Central processing unit
$c_{q}$	Self-symmetry coverage percentage of the contour $C_{q}$ (line 16 of Algorithm 2)
$C_{q}$	Contour from $C_{P}$ , $0 \leq q < \| C_{P} \|$ (line 16 of Algorithm 2)
$C_{B}^{R}$	Set of contours obtained by reflecting $C_{B}$ over $l_{s}$
d	User parameter for the distance step between two consecutive anchor points
DFS	Depth-first search
H	Convex hull created from the contours of $C$ (input parameter of DFS)
$L$	Bundle of potential symmetry lines through a considered anchor point
L&E method	The Loy and Eklundh method
$l e v e l$	Index of the considered level in the multi-branch tree $T$
$l_{b e s t}$	Best symmetry line of all $l_{s}$ from all $p_{a} \in A$
LiDAR	Light detection and ranging
$L i s t O f P a i r s$	List of symmetric pairs of contours from $C_{A}$ and $C_{B}$
$L i s t O f C o v e r a g e s$	List of coverage percentage values of pairs of contours from $C_{A}$ and $C_{B}^{R}$
$l_{s}$	Line in a bundle through a considered $p_{a}$ , $0 \leq s < 180^{\circ} / b$
p	Point
$P$	Set of points (raster image)
$p^{'}$	Point (close top in the weak symmetry definition)
$p_{a}$	Anchor point
$p_{x, y}$	Pixel in thex-th column andy-th row of the raster image $P$
q	Loop index for contours in $C_{P}$
$R_{c}$	Range of colours
s	Loop index for lines in a bundle
$S$	Segmented (and filtered) image
SIFT	Scale-invariant feature transform
SSVDAG	Symmetry-Aware Sparse Voxel Directed Acyclic Graph
SVDAG	Sparse Voxel Directed Acyclic Graph
t	User-defined coverage percentage threshold for pairing two contours
$T$	Geometric transformation
$T$	Multi-branch tree of week local symmetries
X,Y	Image resolution (numbers of columns and rows)

References

Barker, W.H.; Howe, R.Continuous Symmetry: From Euclid to Klein; American Mathematical Society: Providence, RI, USA, 2007. [Google Scholar]
Jäntschi, L.; Bolboacã, S.D.Symmetry in Applied Mathematics; MDPI: Basel, Switzerland, 2020. [Google Scholar]
Dias, G.; Liberti, L. Exploiting symmetries in mathematical programming via orbital independence.Ann. Oper. Res.2021,298, 1–34. [Google Scholar] [CrossRef]
Evans, C.S.; Wenderoth, P.; Cheng, K. Detection of Bilateral Symmetry in Complex Biological Images.Perception2000,29, 31–42. [Google Scholar] [CrossRef] [PubMed]
Mehaffy, M.W. The Impacts of Symmetry in Architecture and Urbanism: Toward a New Research Agenda.Buildings2020,10, 249. [Google Scholar] [CrossRef]
McManus, I.C. Symmetry and Asymmetry in Aesthetics and the Arts.Eur Rev.2005,13, 157–180. [Google Scholar] [CrossRef]
Glowacz, A.; Królczyk, G.; Antonino-Daviu, J.A.Symmetry in Mechanical Engineering; MDPI: Basel, Switzerland, 2020. [Google Scholar]
Modrea, A.; Munteanu, V.M.; Pruncu, I. Using the Symmetries in the Civil Engineering. An overview.Procedia Manuf.2020,46, 906–913. [Google Scholar] [CrossRef]
Montoya, F.G.; Navarro, R.B.Symmetry in Engineering Sciences; MDPI: Basel, Switzerland, 2019. [Google Scholar]
Qui, W.; Yuan, J.; Ukwatta, E.; Sun, Y.; Rajchl, M.; Fenster, A. Prostate Segmentation: An Efficient Convex Optimization Approach With Axial Symmetry Using 3-D TRUS and MR Images.IEEE Trans. Med. Imaging2014,33, 947–960. [Google Scholar]
Wu, Y.; He, F.; Han, S. Collaborative CAD Synchronization Based on a Symmetric and Consistent Modeling Procedure.Symmetry2017,9, 59. [Google Scholar] [CrossRef]
Tyler, C.W.Human Symmetry Perception and its Computational Analysis; Psychology Press: Abingdon, UK, 1996. [Google Scholar]
Bertamini, M.; Makin, A.D. Brain activity in response to visual symmetry.Symmetry2014,6, 975–996. [Google Scholar] [CrossRef]
Podgorelec, D.; Lukač, L.; Žalik, B. Reflection symmetry detection in Earth observation data.Sensors2023,23, 7426. [Google Scholar] [CrossRef]
Wang, Z.; Tang, Z.; Zhang, X. Reflection Symmetry Detection Using Locally Affine Invariant Edge Correspondence.IEEE Trans. Image Process.2015,24, 1297–1301. [Google Scholar] [CrossRef]
Mitra, N.J.; Pauly, M.; Wand, M.; Ceylan, D. Symmetry in 3D Geometry: Extraction and Applications.Comput Graph Forum.2013,32, 1–23. [Google Scholar] [CrossRef]
Abu-Faraj, M.; Al-Hyari, A.; Alqadi, Z. A Complex Matrix Private Key to Enhance the Security Level of Image Cryptography.Symmetry2022,14, 664. [Google Scholar] [CrossRef]
Chen, Y.; Zhan, S.; Xu, W.; Martin, R.R.; Cheng, Z.-Q. Parametric 3D modeling of a symmetric human body.Comput Graphic.2019,81, 52–60. [Google Scholar] [CrossRef]
Žalik, B.; Strnad, D.; Kohek, Š.; Kolingerová, I.; Nerat, A.; Lukač, N.; Podgorelec, D. A Hierarchical Universal Algorithm for Geometric Objects’ Reflection Symmetry Detection.Symmetry2022,14, 1060. [Google Scholar] [CrossRef]
Petitjean, M. A definition of symmetry.Symmetry Cult. Sci.2007,18, 99–119. [Google Scholar]
Prantl, M.; Váša, L.; Kolingerová, I. Symmetry-aware Registration of Human Faces. In Proceedings of the 14th International Joint Conference on Computer Vision, Imaging and Computer Graphics Theory and Applications (VISIGRAPP 2019), Prague, Czech Republic, 25–19 February 2019; Cláudio, A.P., Bouatouch, K., Braz, J., Eds.; Science and Technology Publications: Setúbal, Portugal, 2019; pp. 185–192. [Google Scholar]
Hruda, L.; Kolingerová, I.; Lávička, M.; Mañak, M. Rotational symmetry detection in 3D using reflectional symmetry candidates and quaternion-based rotation parameterization.Comput Aided Geom D.2022,98, 102138. [Google Scholar] [CrossRef]
Zhang, D.; Lu, G. Review of shape representation and description techniques.Pattern Recogn.2004,37, 1–19. [Google Scholar] [CrossRef]
Van Otterloo, P.J.A Contour Oriented Approach to Shape Analysis; Pearson Education Limited: London, UK, 1991. [Google Scholar]
Sheynin, S.; Tuzikov, A.; Volgin, D. Computation of symmetry measures for polygonal shapes. In Proceedings of the 8th International Conference on Computer Analysis of Images and Patters (CAIP’99), Ljubljana, Slovenia, 1–3 September 1999; Lecture Notes in Computer Science 1689. Solina, F., Leonardis, A., Eds.; Springer: Berlin, Germany, 1999; pp. 183–190. [Google Scholar]
Yang, X.; Adluru, N.; Latecki, L.; Bai, X.; Pizlo, Z. Symmetry of shapes via self-similarity. In Proceedings of the 4th International Symposium on Advances in Visual Computing (ISVC 2008), Las Vegas, NV, USA, 1–3 December 2008; Lecture Notes in Computer Science 5359. Bebis, G., Boyle, R., Parvin, B., Koracin, D., Remagnino, P., Porikli, F., Peters, J., Klosowski, J., Arns, L., Chun, Y.K., et al., Eds.; Springer: Berlin, Germany, 2008; pp. 561–570. [Google Scholar]
Kushnir, O.; Fedotova, S.; Seredin, O.; Karkishchenko, A. Reflection symmetry of shapes based on skeleton primitive chains. In Proceedings of the 5th International Conference on Analysis of Images, Social Networks and Text (AIST 2016), Yekaterinburg, Russia, 7–9 April 2016; Communications in Computer and Information Science 661. Ignatov, D.I., Khachay, M.Y., Labunets, V.G., Loukachevitch, N., Nikolenko, S.I., Panchenko, A., Savchenko, A.V., Vorontsov, K., Eds.; Springer: Cham, Switzerland, 2016; pp. 293–304. [Google Scholar]
Karkischenko, V.; Mnukhin, V. Fourfold symmetry detection in digital images based on finite Gaussian fields. In Proceedings of the First International Scientific Conference Intelligent Information Technologies for Industry (IITI’16), Sochi, Russia, 16–21 May 2016; Advances in Intelligent Systems and Computing 451. Abraham, A., Kovalev, S., Tarassov, V., Snášel, V., Eds.; Springer: Cham, Switzerland, 2016; pp. 153–162. [Google Scholar]
Zahn, C.T.; Roskies, R.Z. Fourier descriptors for plane closed curves.IEEE Trans. Comput.1972,C-21, 269–281. [Google Scholar] [CrossRef]
Yip, R.; Tam, P.; Leung, D. Application of elliptic Fourier descriptors to symmetry detection under parallel projection.IEEE Trans. Pattern Anal.1994,16, 277–286. [Google Scholar] [CrossRef]
Loy, G.; Eklundh, J.-O. Detecting Symmetry and Symmetric Constellations of Features. In Proceedings of the Computer Vision (ECCV 2006), Graz, Austria, 7–13 May 2006; Lecture Notes in Computer Science 3952. Leonardis, A., Bischof, H., Pinz, A., Eds.; Springer: Berlin, Germany, 2006; pp. 508–521. [Google Scholar]
Lowe, D.G. Distinctive image features from scale-invariant keypoints.Int. J. Comput. Vision2004,60, 91–110. [Google Scholar] [CrossRef]
Duda, R.O.; Hart, P.E. Use of the Hough Transformation to Detect Lines and Curves in Pictures.Comm ACM.1972,15, 11–15. [Google Scholar] [CrossRef]
O’Mara, D.; Owens, R. Measuring bilateral symmetry in digital images. In Proceedings of the Digital Processing Applications (TENCON ’96), Perth, Australia, 26–27 November 1996; IEEE: Piscataway, NJ, USA, 1996; pp. 151–156. [Google Scholar]
Sun, C.; Si, D. Fast reflectional symmetry detection using orientation histograms.Real-Time Imaging1999,5, 63–74. [Google Scholar] [CrossRef]
Mestetskiy, L.M.; Zhuravskaya, A. Mirror symmetry detection in digital images. In Proceedings of the 15th International Joint Conference on Computer Vision, Imaging and Computer Graphics Theory and Applications–VISIGRAPP 2020 (4: VISAPP), Valletta, Malta, 27–29 February 2020; Farinella, G.M., Radeva, P., Braz, J., Eds.; Science and Technology Publications: Setúbal, Portugal, 2020; pp. 331–337. [Google Scholar]
Hauagge, D.C.; Snavely, N. Image matching using local symmetry features. InConference on Computer Vision and Pattern Recognition (CVPR 2012), Providence, RI, USA, 16–21 June 2012; IEEE: Piscataway, NJ, USA, 2012; pp. 206–213. [Google Scholar]
van Gool, L.; Moons, T.; Ungureanu, D.; Pauwels, E. Symmetry from shape and shape from symmetry.Int. J. Robot Res.1995,14, 407–424. [Google Scholar] [CrossRef]
Derrode, S.; Ghorbel, F. Shape analysis and symmetry detection in gray-level objects using the analytical Fourier–Mellin representation.Signal Process.2004,84, 25–39. [Google Scholar] [CrossRef]
Gnutti, A.; Guerrini, F.; Leonardi, D. Combining appearance and gradient information for image symmetry detection.IEEE Trans. Image Process.2021,30, 5708–5723. [Google Scholar] [CrossRef] [PubMed]
Zabrodsky, H.; Peleg, S.; Anvir, D. Hierarchical symmetry. In Proceedings of the 11th IAPR International Conference on Pattern Recognition, The Hague, The Netherlands, 30 August–1 September 1992; IEEE: Piscataway, NJ, USA, 1992. Volume III Conference C: Image, Speech and Signal Analysis. pp. 9–12. [Google Scholar]
Wang, Y.; Xu, K.; Li, J.; Zhang, H.; Shamir, A.; Liu, L.; Cheng, Z.; Xiong, Y. Symmetry hierarchy of man-made objects.Comput Graph Forum.2011,30, 287–296. [Google Scholar] [CrossRef]
Li, Y.; Mo, K.; Shao, L.; Sung, M.; Guibas, L. Learning 3d part assembly from a single image. In Proceedings of the Computer Vision–ECCV 2020: 16th European Conference, Glasgow, UK, 23–28 August 2020; Proceedings Part VI 16. Springer International Publishing: New York, NY, USA; pp. 664–682. [Google Scholar]
Paschalidou, D.; Gool, L.V.; Geiger, A. Learning unsupervised hierarchical part decomposition of 3d objects from a single rgb image. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, Seattle, WA, USA, 23–29 June 2020; Curran Associates, Inc.: Red Hook, NY, USA, 2020; pp. 1060–1070. [Google Scholar]
Xue, F.; Lu, W.; Chen, Z.; Webster, C.J. From LiDAR point cloud towards digital twin city: Clustering city objects based on Gestalt principles.ISPRS J. Photogramm. Remote Sens.2020,167, 418–431. [Google Scholar] [CrossRef]
Villanueva, A.J.; Marton, F.; Gobetti, E. Symmetry-aware Sparse Voxel DAGs (SSVDAGs) for compression-domain tracing of high-resolution geometric scene.J. Comput. Graph. Tech. (JCGT)2017,6, 1–30. [Google Scholar]
Madoš, B.; Chovancová, E.; Chovanec, M.; Ádám, N. CSVO: Clustered Sparse Voxel Octrees—A Hierarchical Data Structure for Geometry Representation of Voxelized 3D Scenes.Symmetry2022,14, 2114. [Google Scholar] [CrossRef]
Gonzalez, R.C.; Woods, R.E.Digital Image Processing, 4th ed.; Pearson: New York, NY, USA, 2018. [Google Scholar]
De Berg, M.; van Kreveld, M.; Overmars, M.; Schwarzkopf, O.Computational Geometry: Algorithms and Applications, 2nd ed.; Springer: Berlin, Germany, 2000. [Google Scholar]

Figure 1. (a) Input raster image (credit: Paul Reeves Photography/https://www.shutterstock.com, accessed on 7 March 2024); (b) segments of interest; (c) detected contours.

Figure 2. (a) Set of contours and (b) their convex hull with the anchor points.

Figure 3. (a) Bundle of potential lines of symmetry placed in an anchor point; (b) considered line of symmetry

l_{s}

passes through an anchor point

p_{a} \in A

and splits

C

into three sets:

C_{A} = {1, 2, 3, 6, 7}

C_{B} = {5, 9, 10, 11, 13, 14, 15}

, and

C_{P} = {4, 8, 12}

Figure 3. (a) Bundle of potential lines of symmetry placed in an anchor point; (b) considered line of symmetry

l_{s}

passes through an anchor point

p_{a} \in A

and splits

C

into three sets:

C_{A} = {1, 2, 3, 6, 7}

C_{B} = {5, 9, 10, 11, 13, 14, 15}

, and

C_{P} = {4, 8, 12}

Figure 4. (a) Contours from

C_{B}

(plotted in red) are reflected according to

l_{s}

and checked for matching with the contours from

C_{A}

. (b) Contours in

C_{C}

are checked for self-symmetry with regards to

l_{s}

Figure 4. (a) Contours from

C_{B}

(plotted in red) are reflected according to

l_{s}

and checked for matching with the contours from

C_{A}

. (b) Contours in

C_{C}

are checked for self-symmetry with regards to

l_{s}

Figure 5. The obtained multi-branch tree of detected local symmetries.

Figure 6. The found symmetric contours are plotted with the same colour in regards to varyingt: (a) 50%, (b) 70%, (c) 80%, (d) 90%.

Figure 7. Butterfly example reflection hierarchy.

Figure 8. Results of L&E [31] (a,c,e) and AHiLS (b,d,f) methods, where

t = 70

b = 2

, and

d = 5

. (credit: Paul Reeves Photography/https://www.shutterstock.com, accessed on 7 March 2024, for (a,b), andhttps://www.pexels.com/, accessed on 7 March 2024, for (e,f)).

Figure 8. Results of L&E [31] (a,c,e) and AHiLS (b,d,f) methods, where

t = 70

b = 2

, and

d = 5

. (credit: Paul Reeves Photography/https://www.shutterstock.com, accessed on 7 March 2024, for (a,b), andhttps://www.pexels.com/, accessed on 7 March 2024, for (e,f)).

Disclaimer/Publisher’s Note: The statements, opinions and data contained in all publications are solely those of the individual author(s) and contributor(s) and not of MDPI and/or the editor(s). MDPI and/or the editor(s) disclaim responsibility for any injury to people or property resulting from any ideas, methods, instructions or products referred to in the content.

© 2024 by the authors. Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (https://creativecommons.org/licenses/by/4.0/).

Share and Cite

MDPI and ACS Style

Podgorelec, D.; Kolingerová, I.; Lovenjak, L.; Žalik, B. AHiLS—An Algorithm for Establishing Hierarchy among Detected Weak Local Reflection Symmetries in Raster Images.Symmetry2024,16, 442. https://doi.org/10.3390/sym16040442

AMA Style

Podgorelec D, Kolingerová I, Lovenjak L, Žalik B. AHiLS—An Algorithm for Establishing Hierarchy among Detected Weak Local Reflection Symmetries in Raster Images.Symmetry. 2024; 16(4):442. https://doi.org/10.3390/sym16040442

Chicago/Turabian Style

Podgorelec, David, Ivana Kolingerová, Luka Lovenjak, and Borut Žalik. 2024. "AHiLS—An Algorithm for Establishing Hierarchy among Detected Weak Local Reflection Symmetries in Raster Images"Symmetry 16, no. 4: 442. https://doi.org/10.3390/sym16040442

APA Style

Podgorelec, D., Kolingerová, I., Lovenjak, L., & Žalik, B. (2024). AHiLS—An Algorithm for Establishing Hierarchy among Detected Weak Local Reflection Symmetries in Raster Images.Symmetry,16(4), 442. https://doi.org/10.3390/sym16040442

Note that from the first issue of 2016, this journal uses article numbers instead of page numbers. See further detailshere.

Article Metrics

Article Access Statistics

For more information on the journal statistics, clickhere.

Multiple requests from the same IP address are counted as one view.

Abstract

1. Introduction

2. Related Works

3. Materials and Methods

4. Results

5. Conclusions

Author Contributions

Funding

Data Availability Statement

Conflicts of Interest

Abbreviations

References

Share and Cite

Article Metrics

Article Access Statistics

Movatterモバイル変換

Journals

Topics

Information

Author Services

Initiatives

About

Notice

Notice

Article Menu

Need Help?

Support

Feedback

Information

JSmol Viewer

AHiLS—An Algorithm for Establishing Hierarchy among Detected Weak Local Reflection Symmetries in Raster Images

Cite

Further Information

Guidelines

MDPI Initiatives

Follow MDPI

Share Link

Share