Here’s a somewhat ongoing port of Wai Ho Li, Alan M Zhang, and Lindsay Kleeman’s Fast Global Reflectional Symmetry Detection code in the latest OpenCV.
Symmetry detection is useful in the situation where you’re trying to find objects with strong symmetrical shapes. Weird as it sounds, this is actually very common, since human tends to create objects that have symmetrical shapes.
When it comes to classical Generalized Symmetry Transform, most literatures seem to be pointing to Reisfeld et al. , 1995’s method of symmetrical transform. However since that method calculates the symmetrical transform for all the given pixels in the scene (and for each pixel, a certain neighbourhood range is taken to consideration), the whole algorithm can be very slow.
Li et al. (is this even correct? I’m referring to Wai Ho Li and colleagues) managed to come up with a novel idea of symmetrical transform on the edge image utilising the Hough space. By performing operations only on the edges, means that the whole algorithm works faster than Generalized Symmetry Transform. You can read more about it from these following literatures:
- Fast Global Reflectional Symmetry Detection for Robot Grasping and Visual Tracking
- Real Time Object Tracking using Reflectional Symmetry and Motion
And the corresponding source code (which might be more of the implementation of the latter literature than the former) can be found here: https://code.google.com/p/cvaddon/. The original code is … quite hard to read though, so take this as a warning beforehand, if it’s too much for you, try reading my version of the code, at least it’s bit cleaner.
I decided to somewhat port the existing code to latest OpenCV. ‘Somewhat’, because I took the liberty to remove all the functionalities which I deemed to be extraneous (e.g. limiting angle, single voting, smoothing, etc), thus porting only the essential parts of the algorithm, hoping that the code could explain how the actual algorithm works.
In a (very barebone) nutshell here’s how it works:
- First apply edge detection algorithm on the image
- Each pair of the edges should contribute a vote into the Hough accumulation matrix, while ignoring edges that don’t have any partner. Thus each entry in the accumulation matrix describes the vote of each edge-pair
- Find the peaks inside the Hough accumulation matrix, and translate them back into x-y lines.
Here’s some of the results:
And here’s a clip of me applying the algorithm on the scene taken from my webcam, while waving my phone, remote control and coffee mug.
Fast Global Reflectional Symmetry is an interesting algorithm. Although it’s still dependent on the result of the edge detection algorithm, it performs way faster than Generalized Symmetry Transform due to reduced search space. I could see many way this kind be used to enhanced existing object detection algorithms. I’m definitely interested on how Li et al. integrated it with other algorithms specified in the paper in order to do fast object detection hopefully I will be able to investigate more about it in the future.
Anyway if you’re interested in my stripped down implementation of the code, you can get it here: https://github.com/subokita/Sandbox/tree/master/FSD