Symmetry Detection Algorithm

This is a short presentation of an extremely simple algorithm I designed and implemented for identifying symmetries in thresholded pixelated image data. This algorithm was so simple to conceive-of that I am certain (a) it must already have been published and (b) better algorithms exist. I have released the implementation into public domain since it may be useful to someone.

Naturally more detail is available in the source code. The code has been developed using Java 6, though I anticipate that it should run fine under Java 1.5. It has no external library dependencies. If you do use this code let me know - I'd love to know about it.

Usage Example

The code supplied can be used very simply if the image data is already in suitable format (loading grayscale or black & white images encoded using JPEG or PNG is quite simple). The code below provides a simple example of how to use the SymmetryDetector class.

//obtain our image BufferedImage image = File("myimage.png")); //create the detector SymmetryDetector detector = new SymmetryDetector(); //optionally adjust parameters here detector.setScoreThreshold(0.9f); //strictly optional: observe the algorithm running BufferedImage obs = new BufferedImage(image.getWidth(), image.getHeight(), BufferedImage.TYPE_INT_RGB); detector.setObservation(obs.createGraphics()); //run the detector - symmetries are available from the returned object SymmetryDetector.Symmetry symmetry = detector.detectSymmetry(image); //the image obs will contain a graphical summary of execution

Algorithm Outline

The algorithm proceeds as follows:

  1. Identify the centroid of the object.
  2. Measure the object radius (distance from centroid to most distant object pixel).
  3. Choose a set of circles centered on the centroid with radius less than the object radius.
  4. Sample the image at a fixed angular resolution (an even number of equiangular points) to create a vector of pixel values for each circle.
  5. 'Convolve' each vector with itself to create a new set of vectors. These loosely measure the reflectional symmetry across the angle associated with each element.
  6. Sum all of the resulting vectors to obtain an overall symmetry score for each angle considered.
  7. Disregard any angle that does not exceed a predetermined threshold and which is not a local maximum.
  8. Of the remaining angles, calculate the score-weighted average of adjacent angles (subject to a predefined threshold).
  9. The resulting angles, together with the centroid, define a set of axes along which reflectional symmetry is high.

Algorithm Parameters

The important algorithm parameters are:

Angular Resolution
The number of samples within a π arc of a circle.
Angular Aliasing
The smallest angle permitted between identified axes of symmetry. Angles closer together than this value are combined into a single angle.
Radius Count
The number of different radii at which samples are taken.
The proportion of the maximum possible score that an angle must obtain to be considered.

Sample Output

In the images that follow:

Known Issues

The code as supplied has the following known limitations:

April 2007