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 = ImageIO.read(new 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:
- Identify the centroid of the object.
- Measure the object radius (distance from centroid to most distant
object pixel).
- Choose a set of circles centered on the centroid with radius less
than the object radius.
- Sample the image at a fixed angular resolution (an even number of
equiangular points) to create a vector of pixel values for each
circle.
- '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.
- Sum all of the resulting vectors to obtain an overall symmetry
score for each angle considered.
- Disregard any angle that does not exceed a predetermined threshold
and which is not a local maximum.
- Of the remaining angles, calculate the score-weighted average of
adjacent angles (subject to a predefined threshold).
- 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.
- Threshold
-
- The proportion of the maximum possible score that an angle must
obtain to be considered.
Sample Output
In the images that follow:
- Blue pixels indicate pixels identified with the object.
- The green 'plus' indicates the position of the centroid.
- The green 'cross' indicates a pixel at maximum distance from the
centroid.
- Green circles indicate the circles from which samples of image
data were taken.
- Green lines indicate the lines of reflectional symmetry identified
by the algorithm.
Known Issues
The code as supplied has the following known limitations:
- The thresholding is currently hardwired 'towards white'. This is
easily changed in the code, but has not been made parameterizable.
- Angles that are adjacent, but at extreme ends of the sample
vectors (those at π and -π) are not currently aliased. Again
this should be a simple change unless one wants to leave the code
tidy.
April 2007
Available Now!
