# Fast Symmetry Detection

Standard

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:

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

## 14 thoughts on “Fast Symmetry Detection”

1. Dan Miller

I just wanted to start by saying I really enjoyed the article, so keep up the good work. I’m running your code from VS2012. I keep running into the issue on line 61 of FastSymmetryDetector.cpp “*(reRows[rho]++) = r0 * edge.x + r1 * edge.y + fourth_rho.” Access violation writing location 0xABABABAB. Have any thoughts on how I might fix this error? I’m very interested in experimenting with your code. Appreciate your time!

• Hi Mr. Miller, thanks for the kind words.

Btw, I don’t own a Windows PC nor Visual Studio, so I don’t really know whether it’s actually a library issue, or it’s actually bug in the code. I just fired up my version on Xcode and Mac, but it seems to be working fine. You should try it on the sample.jpg included in github repo first, that one should work with the preset parameters.

If I recalled correctly, reRows is supposed to be pointer to each row of rotEdges grid, that stores the rotated edges. If you suspect that there’s an array out of bounds issue with the code, you could try to increase the size of the rotEdges and reRows by modifying these lines of codes:

rotEdges = Mat::zeros( rhoDivision, diagonal, CV_32FC1 );
reRows.resize( rhoDivision );

If it doesn’t work, then sadly it might be issue pertaining to Visual Studio, I’ve seen people complaining about access violation errors on Visual Studio, because VS wasn’t loading the libraries properly.

• Dan

I really appreciate you getting back to me! I’ll take a look at it. I have had quite a few issues with VS so this isn’t incredibly surprising.

2. Dan

Whenever you get a chance, could you also share what c++ standard (I think C++11 based on the for each calls) you’re using and version of opencv? I’m using C++11 & OpenCV 2.4.8. The vote function finishes but then produces some deallocation errors just as the function is returning.

• Dan

Actually, I figured it out. So this code uses C++11 standards. My system path had both opencv’s vc11 dlls and vc10 and got confused. The program works great otherwise!!!

• Ach so, that’s the issue! Thanks a lot for pointing this out, I’d never be able to figure it out on my own.

I’d received couple of emails from readers regarding random errors on VS similar to yours, now probably I could point out that you have resolved similar issue!

Thanks a lot!

3. Hey Saburo,

It’s Wai Ho here. Found this blog via a friend who’s a postdoc at KU Leuven (Punarjay Chakravarty).

I wrote (well, hacked together) the code for Fast Symmetry and related applications during my PhD to show that bilateral symmetry could be used for (soft) real time robotic applications like visual tracking. Apologies for the code quality 🙂

The code was later used in a real time robotic system

Regarding the “extraneous” features, they were mainly done for two reason: Improved robustness in visually cluttered scenes and better computational performance. The latter was in relation to a Pentium M 1.7GHz laptop, so you may not need to consider this constraint depending on your compute platform and application area.

I found that the single (convergent) voting helped with performance as the bottleneck at the time was memory access into the hough accumulator. It also made the system more robust in visually cluttered scenes with a lot of edges as it (seems to) help reduce the effects of weaker symmetries.

The angle limits sped things up linearly (smaller angle, faster performance) and it is a very nice feature for visual tracking as it helps reject unwanted symmetry lines (like the ones that appear sporadically in your video).

The smoothing helped with vote aliasing in the hough accumulator, which made tracking more accurate when votes were aliased across multiple bins.

I hope the above help explain things a bit more. My IJRR paper might also be of interest if you plan to dig deeper

Note that there has been quite a bit of work on bilateral symmetry detection since my work in the mid 2000’s. Some of the modern approaches look for symmetry SIFT or SURF feature pairs; will be more robust in many real world scenarios (but might not run real time on all platforms).

Give me a ping via email if you want to discuss more. I am looking to port my code onto a Tegra Jetson to see how it runs, might give your version a try first 🙂

• Hi Mr Li (or maybe Wai is your first name?)

Firstly I understand that when you’re rushing to submit your project before due date or dissertation defense, it’s inevitable that the code will be messier, no doubt about it.

Actually, I’m the one who needs to thank you for opening up your code to the public. I learnt a lot from you.

Anyway, social niceties aside. Please be careful when you’re using my version, since I might have made mistakes here and there. I plan to read more about symmetry detection in the future, but right now I’m trying to learn (by porting) to create my own bundle adjustment system first. Then maybe symmetry detection will come llater.

• waihoRobot

Li is my family name. I was born in Hong Kong so I have the usual two-syllable Southern Chinese given name (Wai-Ho). Just Wai Ho is fine 🙂

Is it Saburo-san or Okita-san? I assumed the former.

No worries about the open code repo. I wish I can do so more often but I have been working on mainly biomedical and industrial projects; still trying to convince my partners to let me open up my code bases 😦

No worries, I am always careful with repos in the wild. I think using symmetries (radial and other forms of symmetry may be handy too) for bundle adjustment sounds like a good way to improve robustness and “compress” features. Good luck with your project!

• Ah 香港人, I’m actually Indonesian Chinese, but due to complex history, my name is Japanese.

Let’s keep in touch in the future, although my current work barely has anything to do with computer vision. Maybe in the future.

4. benjamin

muy buen proyecto donde se deja ver la importancia de la programación en paralela para la detección de objetos en tiempo real; me parecio extraordinario en articulo.
Intente levantar el codigo que se describe en el link en el visual estudio 2017 con opencv 4; pero al tratar de compilar me sale que no existe el archivo tbb/tbb.h; investigue en Internet pero no explican hacer la integración de TBB con opencv.
alguna idea de como hacer la integración o es que no estoy en el concepto correcto

• sub

Gracias, pero mi español no es bueno.
Por lo que recuerdo, solo agrego TBB a Visual Studio, nada más. Podrías usar CMAKE o Make para lograr lo mismo.

As far as I remembered, I only add TBB to Visual Studio, nothing more. You could use CMAKE or Make to accomplish the same thing

• Benjamin S Cespedes

En primera instancia agradecerle por haber respondido a mi pregunta; efectivamente encontre un plugin para visual estudio 2017 para instalar TBB he aqui el link https://www.nuget.org/packages/tbb_oss/ ; despues de instalar ya no me salio el error descrito anteriormente; sin embargo me sale este mensaje de error en la linea 237 del archivo
FastSymmetryDetector.cpp
float min_d = std::numeric_limits::max();

Por lo que revise esta función recibe dos parámetros; los cuales quisiera saber para poder ejecutar el programa; ya que quizás si pongo cualquier variable puede que se altere los resultados.
De ante mano agardecerle por el apoyo brindado.

• sub

es solo el Floating Point mas grande posible

Debe estar alrededor de 3.40282e+38
Debe estar alrededor de 3.40282e + 38, o cualquier número grande como punto de partida.

así que tal vez podrías usar
float min_d = 3.40282e + 38f;

It is only the largest Floating Point possible

It should be around 3.40282e + 38
It should be around 3.40282e + 38, or any large number as a starting point.

so maybe you could use
float min_d = 3.40282e + 38f;