Kushnir, Olesia A

Seredin O., Liakhov D., Lomov N., Kushnir O., Kopylov A.

The article proposes a fast method for detecting curved symmetry for binary images by greedily searching for locally symmetric nodes of a polyline inside a figure, starting from a user-specified point. The advantage is that the procedure is virtually devoid of any manually adjusted inputs. The key procedure inputs (the increment and angular range used at the next step) are estimated by an adaptive procedure. Further, the obtained fragments of the image corresponding to the found segments of the polyline are sequentially superimposed on a single axis by rotation, forming a “straightened” figure, which makes it possible to calculate the Jaccard measure of symmetry for the entire figure. The experimental results demonstrate the successful operation of the method even on images with significant curvature at a perfect calculation speed.

Lomov N.A., Seredin O.S., Liakhov D.V., Kushnir O.A.

This study proposes analytical estimate for the size of a binary raster figure region which is guaranteed to contain the rotational symmetry focus. Focus here is the point a maximum Jaccard index between initial figure and rotated one. The size of the region is determined by the lower estimate of the intersection area during the rotation of the approximating primitives, considering the sizes of the inner and outer parts of the figure relative to the primitive. The smallest circumscribed circle or ellipse and sets of concentric circles and ellipses produced by the principal component analysis were used as the approximating figure. To verify the hypothesis that the size of the region is insignificant compared to the area of the figure, we numerically simulated the proposed method with test image datasets.

Lomov N., Seredin O., Kushnir O., Liakhov D.

Lomov N.A., Seredin O.S., Kushnir O.A., Liakhov D.V.

This study determines the optimal reflection symmetry axis of an object in a binary image using the Jaccard index. We propose to find the global optimum on the grid by estimating the upper bounds of the Jaccard index with the Radon transform. Several approaches to improving the Jaccard index computation for a given line are considered. Some strategies for enumerating possible symmetry axes and selecting the initial approximation are proposed. The experiments show that the Jaccard index for the optimal axis found by the proposed method is not inferior to the exhaustive bruteforce of the axes passing through the points of the object contour considering the rasterization error. In terms of speed, the proposed method significantly exceeds the previously developed methods for limiting the exhaustive search.

Seredin O., Liakhov D., Kushnir O., Lomov N.

Finding the exact position of the rotational quasi-symmetry focus using the Jaccard index for binary images was not considered so far. The focus is the point at which the Jaccard index reaches its maximum as the figure rotates. In this paper, we deal with only order 2 rotational symmetry images. A basic extensive focus search procedure is proposed, and the symmetry function profile is subsequently estimated in the vicinity of the maximum. With the search problem analysis, we proposed a computationally efficient procedure for finding the rotational symmetry function maximum based on the quadratic approximation of the symmetry function. The seed point of the search area is the center of mass of the figure. The proposed procedure correctly identified the true rotational symmetry focus for the test image set while the performance was significantly improved compared to the extensive reference procedure.

Lomov N., Seredin O., Kushnir O.

Kushnir O.A., Seredin O.S., Fedotova S.A.

Abstract. Reflection symmetry detection for 2D shapes is a well-known task in Computer Vision, but there is a limited number of efficient and effective methods for its solution. Our previously proposed approach based on pair-wise comparison of sub-sequences of skeleton primitives finds the axis of symmetry within few seconds. In order to evaluate the value of symmetry relative to the found axis we use the Jaccard similarity measure. It is applied to the pixels subsets of a shape which are split by the axis. Often an axis found by the skeleton comparison method diverges more or less from the ground-truth axis found by the method of exhaustive search among all the potential candidates. That is why the algorithms that allow adjusting the axis found by the fast skeleton method are proposed. They are based on the idea of searching the axis which is located near the seed skeleton axis and has greater Jaccard similarity measure. The experimental study on the ”Flavia” and ”Butterflies” datasets shows that proposed algorithms find the ground-truth axis (or the axis which has slightly less Jaccard similarity value than the ground-truth axis) in near real time. It is considerably faster than any of the optimized brute-force methods.

Larin A., Gracheva I., Kushnir O., Seredin O., Kopylov A.

Fedotova S., Seredin O., Kushnir O.

Abstract. In this paper, we investigate the exact method of searching an axis of binary image symmetry, based on brute-force search among all potential symmetry axes. As a measure of symmetry, we use the set-theoretic Jaccard similarity applied to two subsets of pixels of the image which is divided by some axis. Brute-force search algorithm definitely finds the axis of approximate symmetry which could be considered as ground-truth, but it requires quite a lot of time to process each image. As a first step of our contribution we develop the parallel version of the brute-force algorithm. It allows us to process large image databases and obtain the desired axis of approximate symmetry for each shape in database. Experimental studies implemented on “Butterflies” and “Flavia” datasets have shown that the proposed algorithm takes several minutes per image to find a symmetry axis. However, in case of real-world applications we need computational efficiency which allows solving the task of symmetry axis search in real or quasi-real time. So, for the task of fast shape symmetry calculation on the common multicore PC we elaborated another parallel program, which based on the procedure suggested before in (Fedotova, 2016). That method takes as an initial axis the axis obtained by superfast comparison of two skeleton primitive sub-chains. This process takes about 0.5 sec on the common PC, it is considerably faster than any of the optimized brute-force methods including ones implemented in supercomputer. In our experiments for 70 percent of cases the found axis coincides with the ground-truth one absolutely, and for the rest of cases it is very close to the ground-truth.

Kushnir O., Fedotova S., Seredin O., Karkishchenko A.

In this paper the novel fast approach to identify the reflection symmetry axis of binary images is proposed. We propose to divide a skeleton of a shape into two parts – the “left” and the “right” sub-skeletons. The left part is traversed counterclockwise and the right one – in clockwise direction. As a result, the “left” and the “right” primitive sub-chains are achieved; they can be compared by the known shape matching procedure based on pair-wise alignment of primitive chains. So, the most similar parts of a skeleton among all possible ones correspond to the most similar parts of a figure which are considered as reflection symmetric parts. The start and the end points of skeleton division into “left” and “right” parts will be the points belonging to a symmetry axis of a figure. Also, the exact brute-force symmetry evaluation algorithm and two its optimizations are suggested for finding ground truth of symmetry axis. All proposed methods were experimentally tested on Flavia leaves dataset.

Kushnir O., Seredin O.

We introduce a new shape matching approach based on skeletonization and alignment of primitive chains. At the first stage the skeleton of a binary image is traversed counterclockwise in order to encode it by chain of primitives. A primitive describes topological properties of the correlated edge and consists of a pair of numbers: the length of some edge and the angle between this and the next edges. We offer to expand a primitive by the information about the radial function of the skeleton rib. To get the compact width description we interpolate radial function by Legendre polynomials and find the vector of Legendre coefficients. Thus the resulting shape representation by the chain of primitives includes not only topological properties but also the contour ones. Then we suggest the dynamic programming procedure of the alignment of two primitive chains in order to match correspondent shapes. Based on the optimal alignment we propose the pair-wise dissimilarity function which is evaluated on artificial image dataset and the Flavia leaf dataset.

Kushnir O., Seredin O.

A new approach for shape comparison based on skeleton matching is proposed. The skeleton of a binary image is encoded as a series of primitives (chain of primitives). Traditionally, a primitive is a pair of numbers, the first one is the length of the some edge and the second one is the angle between this and the neighbour edges. As a novelty we offer to calculate the Legendre polynomial coefficients to describe the width of shape and incorporate them as the third vector component into the primitive. The procedure of the alignment of two primitive chains is suggested and the pair-wise comparison function based on optimal alignment is built. Experiments with developed comparison function on the real-world dataset of medicinal leaves show that the results of classification are appropriate considering the difficulty of the task and disadvantages of the database.

Seredin O., Liakhov D., Lomov N., Kushnir O., Kopylov A.

The article proposes a fast method for detecting curved symmetry for binary images by greedily searching for locally symmetric nodes of a polyline inside a figure, starting from a user-specified point. The advantage is that the procedure is virtually devoid of any manually adjusted inputs. The key procedure inputs (the increment and angular range used at the next step) are estimated by an adaptive procedure. Further, the obtained fragments of the image corresponding to the found segments of the polyline are sequentially superimposed on a single axis by rotation, forming a “straightened” figure, which makes it possible to calculate the Jaccard measure of symmetry for the entire figure. The experimental results demonstrate the successful operation of the method even on images with significant curvature at a perfect calculation speed.

Lomov N.A., Seredin O.S., Kushnir O.A., Liakhov D.V.

This study determines the optimal reflection symmetry axis of an object in a binary image using the Jaccard index. We propose to find the global optimum on the grid by estimating the upper bounds of the Jaccard index with the Radon transform. Several approaches to improving the Jaccard index computation for a given line are considered. Some strategies for enumerating possible symmetry axes and selecting the initial approximation are proposed. The experiments show that the Jaccard index for the optimal axis found by the proposed method is not inferior to the exhaustive bruteforce of the axes passing through the points of the object contour considering the rasterization error. In terms of speed, the proposed method significantly exceeds the previously developed methods for limiting the exhaustive search.

Seredin O., Liakhov D., Kushnir O., Lomov N.

Finding the exact position of the rotational quasi-symmetry focus using the Jaccard index for binary images was not considered so far. The focus is the point at which the Jaccard index reaches its maximum as the figure rotates. In this paper, we deal with only order 2 rotational symmetry images. A basic extensive focus search procedure is proposed, and the symmetry function profile is subsequently estimated in the vicinity of the maximum. With the search problem analysis, we proposed a computationally efficient procedure for finding the rotational symmetry function maximum based on the quadratic approximation of the symmetry function. The seed point of the search area is the center of mass of the figure. The proposed procedure correctly identified the true rotational symmetry focus for the test image set while the performance was significantly improved compared to the extensive reference procedure.

Lomov N., Seredin O., Kushnir O.

Larin A.O., Seredin O.S., Kopylov A.V.

A new version of one-class classification criterion robust to anomalies in the training dataset is proposed based on support vector data description (SVDD). The original formulation of the problem is not geometrically correct, since the value of the penalty for the admissible escape of the training sample objects outside the describing hypersphere is incommensurable with the distance to its center in the optimization problem and the presence of outliers can greatly affect the decision boundary. The proposed criterion is intended to eliminate this inconsistency. The equivalent form of criterion without constraints lets us use a kernel-based approach without transition to the dual form to make a flexible description of the training dataset. The substitution of the non-differentiable objective function by the smooth one allows us to apply an algorithm of sequential optimizations to solve the problem. We apply the Jaccard measure for a quantitative assessment of the robustness of a decision rule to the presence of outliers. A comparative experimental study of existing one-class methods shows the superiority of the proposed criterion in anomaly detection.

O. Larin A., Seredin O., Kopylov A.

A modified version of one-class classification criterion reducing the impact of outliers on the one-class classification decision rule is proposed based on support vector data description (SVDD) by D. Tax. The optimization method utilizes the substitution of nondifferentiable objective function by the smooth one. A comparative experimental study of existing one-class methods shows the superiority of the proposed criterion in anomaly detection.

Kushnir O., Fedotova S., Seredin O., Karkishchenko A.

In this paper the novel fast approach to identify the reflection symmetry axis of binary images is proposed. We propose to divide a skeleton of a shape into two parts – the “left” and the “right” sub-skeletons. The left part is traversed counterclockwise and the right one – in clockwise direction. As a result, the “left” and the “right” primitive sub-chains are achieved; they can be compared by the known shape matching procedure based on pair-wise alignment of primitive chains. So, the most similar parts of a skeleton among all possible ones correspond to the most similar parts of a figure which are considered as reflection symmetric parts. The start and the end points of skeleton division into “left” and “right” parts will be the points belonging to a symmetry axis of a figure. Also, the exact brute-force symmetry evaluation algorithm and two its optimizations are suggested for finding ground truth of symmetry axis. All proposed methods were experimentally tested on Flavia leaves dataset.

Kushnir O., Seredin O.

We introduce a new shape matching approach based on skeletonization and alignment of primitive chains. At the first stage the skeleton of a binary image is traversed counterclockwise in order to encode it by chain of primitives. A primitive describes topological properties of the correlated edge and consists of a pair of numbers: the length of some edge and the angle between this and the next edges. We offer to expand a primitive by the information about the radial function of the skeleton rib. To get the compact width description we interpolate radial function by Legendre polynomials and find the vector of Legendre coefficients. Thus the resulting shape representation by the chain of primitives includes not only topological properties but also the contour ones. Then we suggest the dynamic programming procedure of the alignment of two primitive chains in order to match correspondent shapes. Based on the optimal alignment we propose the pair-wise dissimilarity function which is evaluated on artificial image dataset and the Flavia leaf dataset.

Huang J., Stoter J., Nan L.

Symmetry widely exists in nature and man-made shapes, but it is unavoidably distorted during the process of growth, design, digitalization, and reconstruction steps. To enhance symmetry, traditional methods follow the detect-then-symmetrize paradigm, which is sensitive to noise in the detection phase, resulting in ambiguities for the subsequent symmetrization step. In this work, we propose a novel optimization-based framework that jointly detects and optimizes symmetry for 2D shapes represented as polygons. Our method can detect and optimize symmetry using a single objective function. Specifically, we formulate symmetry detection and optimization as a mixed-integer program. Our method first generates a set of candidate symmetric edge pairs, which are then encoded as binary variables in our optimization. The geometry of the shape is expressed as continuous variables, which are then optimized together with the binary variables. The symmetry of the shape is enforced by the designed hard constraints. After the optimization, both the optimal symmetric edge correspondences and the geometry are obtained. Our method simultaneously detects all the symmetric primitive pairs and enhances the symmetry of a model while minimally altering its geometry. We have tested our method on a variety of shapes from designs and vectorizations, and the results have demonstrated its effectiveness.

Lomov N., Seredin O.

Abstract. This study proposes a method for detecting curved reflection symmetry in binary and grayscale images. The crucial step is to construct a curvilinear symmetry axis generating a nonlinear transformation of the image coordinates that projects the curve on the Y axis and makes the image maximally symmetric about this axis in terms of the Jaccard index. We proposed analytical estimations for the symmetry axis curvature to make the transform bijective. We applied dynamic programming to construct the curvilinear symmetry axis. The axis points are generated one by one with a local direction change at each point. To improve the computational efficiency of the method for images of a given size, we construct a graph of possible transitions in advance. To estimate the symmetry in grayscale images, we proposed two analogs to the Jaccard index. The experiments with image libraries demonstrated that the method correctly handles images containing a single object on a homogeneous background.

Seredin O., Liakhov D., Kushnir O., Lomov N.

Finding the exact position of the rotational quasi-symmetry focus using the Jaccard index for binary images was not considered so far. The focus is the point at which the Jaccard index reaches its maximum as the figure rotates. In this paper, we deal with only order 2 rotational symmetry images. A basic extensive focus search procedure is proposed, and the symmetry function profile is subsequently estimated in the vicinity of the maximum. With the search problem analysis, we proposed a computationally efficient procedure for finding the rotational symmetry function maximum based on the quadratic approximation of the symmetry function. The seed point of the search area is the center of mass of the figure. The proposed procedure correctly identified the true rotational symmetry focus for the test image set while the performance was significantly improved compared to the extensive reference procedure.

Lomov N., Seredin O., Kushnir O.

Nguyen T.P., Truong H.P., Nguyen T.T., Kim Y.

• A solid theoretical foundation of R-signature and LIP-signature about symmetric properties of a given shape is represented. • A verification process is theoretically justified to remove the false candidates based on an efficient symmetry measure. • Two novel datasets (UTLN-SRA & UTLN-MRA) with single & multiple reflections are designed for evaluating symmetry detectors. • A new evaluation protocol based on a lost measure is presented to evaluate reflectional symmetry detectors. • Comprehensive evaluations have verified that our proposed detectors perform well on binary images compared to state of the art. We present two novel shape signature-based reflection symmetry detection methods with their theoretical underpinning and empirical evaluation. LIP-signature and R-signature share similar beneficial properties allowing to detect reflection symmetry directions in a high-performing manner. For the shape signature of a given shape, its merit profile is constructed to detect candidates of symmetry direction. A verification process is utilized to eliminate the false candidates by addressing Radon projections. The proposed methods can effectively deal with compound shapes which are challenging for traditional contour-based methods. To quantify the symmetric efficiency, a new symmetry measure is proposed over the range [0, 1]. Furthermore, we introduce two symmetry shape datasets with a new evaluation protocol and a lost measure for evaluating symmetry detectors. Experimental results using standard and new datasets suggest that the proposed methods prominently perform compared to state of the art.

Lomov N., Tiras K., Mestetskiy L.

Aguilar W., Alvarado-Gonzalez M., Garduño E., Velarde C., Bribiesca E.

We present a new approach based on the Slope Chain Code to determine whether a curve is rotational symmetrical and its order of symmetry. The proposed approach works for open and closed perfectly symmetrical or quasi-symmetrical 2D curves. Simple operations on the SCC and its invariant properties are central to our methodology. To evaluate the proposed methodology, we use 1400 curves from a public database. For the symmetrical/asymmetrical classification task, a recall (R) of 0.86, a balanced accuracy (BA) of 0.92, and a precision (P) of 0.87 were obtained. For the quasi-symmetrical/quasi-asymmetrical classification task, R=0.77, BA=0.83, and P=0.70 were obtained. For the order of rotational symmetry detection task, the following performance was achieved: R=0.97, BA=0.98, and P=0.95 for a symmetrical set of curves, and R=0.98, BA=0.98, and P=0.90 for a quasi-symmetrical set of curves. We conclude our presentation demonstrating the usefulness of our methodology with three practical applications

Seredin O., Kushnir O., Fedotova S.

Corballis M.C.

We belong to a clade of species known as the bilateria, with a body plan that is essentially symmetrical with respect to left and right, an adaptation to the indifference of the natural world to mirror-reflection. Limbs and sense organs are in bilaterally symmetrical pairs, dictating a high degree of symmetry in the brain itself. Bilateral symmetry can be maladaptive, though, especially in the human world where it is important to distinguish between left and right sides, and between left-right mirror images, as in reading directional scripts. The brains of many animals have evolved asymmetries, often but not exclusively in functions not dependent on sensory input or immediate reaction to the environment. Brain asymmetries in humans have led to exaggerate notions of a duality between the sides of the brain. The tradeoff between symmetry and asymmetry results in individual differences in brain asymmetries and handedness, contributing to a diversity of aptitude and divisions of labor. Asymmetries may have their origin in fundamental molecular asymmetries going far back in biological evolution.

Nguyen T.P.

A novel method for reflection symmetry detection is addressed using a projection-based approach that allows to deal effectively with additional noise, non-linear deformations, and composed shapes that are not evident for classic contour-based approaches. A new symmetry measure is also proposed to measure how good the detected symmetry is. Experiments validate the interest of our proposed method.

Mestetskiy L., Zhuravskaya A.

Abstract. In this paper we solve the problem of finding the symmetry axis of the object in a digital binary image. A new axial symmetry criterion is formulated for a connected discrete object. The problem of determining the symmetry measure and finding the symmetry axes arises in a variety of applications. In discrete images, exact symmetry is possible only in special cases. The disadvantage of the existing methods solving this problem is the high computational complexity. To improve computational efficiency, it is proposed to use the so-called Fourier descriptor. A new method for estimating the asymmetry of a discrete silhouette is proposed. The described algorithm for calculating the measure of asymmetry and determining the axis of symmetry is quadratic by the number of contour points. Methods for reducing the volume of calculations using a convex hull and taking into account the values of the modules of Fourier coefficients are proposed. Computational experiments are conducted with silhouettes of aircraft extracted from earth remote sensing images. The reliability of the described solution is established.

Kushnir O.A., Seredin O.S., Fedotova S.A.

Abstract. Reflection symmetry detection for 2D shapes is a well-known task in Computer Vision, but there is a limited number of efficient and effective methods for its solution. Our previously proposed approach based on pair-wise comparison of sub-sequences of skeleton primitives finds the axis of symmetry within few seconds. In order to evaluate the value of symmetry relative to the found axis we use the Jaccard similarity measure. It is applied to the pixels subsets of a shape which are split by the axis. Often an axis found by the skeleton comparison method diverges more or less from the ground-truth axis found by the method of exhaustive search among all the potential candidates. That is why the algorithms that allow adjusting the axis found by the fast skeleton method are proposed. They are based on the idea of searching the axis which is located near the seed skeleton axis and has greater Jaccard similarity measure. The experimental study on the ”Flavia” and ”Butterflies” datasets shows that proposed algorithms find the ground-truth axis (or the axis which has slightly less Jaccard similarity value than the ground-truth axis) in near real time. It is considerably faster than any of the optimized brute-force methods.

Kushnir O., Fedotova S., Seredin O., Karkishchenko A.

In this paper the novel fast approach to identify the reflection symmetry axis of binary images is proposed. We propose to divide a skeleton of a shape into two parts – the “left” and the “right” sub-skeletons. The left part is traversed counterclockwise and the right one – in clockwise direction. As a result, the “left” and the “right” primitive sub-chains are achieved; they can be compared by the known shape matching procedure based on pair-wise alignment of primitive chains. So, the most similar parts of a skeleton among all possible ones correspond to the most similar parts of a figure which are considered as reflection symmetric parts. The start and the end points of skeleton division into “left” and “right” parts will be the points belonging to a symmetry axis of a figure. Also, the exact brute-force symmetry evaluation algorithm and two its optimizations are suggested for finding ground truth of symmetry axis. All proposed methods were experimentally tested on Flavia leaves dataset.

Ricca G., Beltrametti M.C., Massone A.M.

The Hough transform is a standard pattern recognition technique introduced between the 1960s and the 1970s for the detection of straight lines, circles, and ellipses with several applications including the detection of symmetries in images. Recently, based on algebraic geometry arguments, the procedure has been extended to the automated recognition of special classes of algebraic plane curves. This allows us to detect curves of symmetry present in images, that is, curves that recognize midpoints maps of various shapes extracted by an ad hoc symmetry algorithm, here proposed. Further, in the case of straight lines, the detection of lines of symmetry allows us, by a pre-processing step of the image, to improve the efficiency of the recognition algorithm on which the Hough transform technique is founded, without loss of generality and additional computational costs.