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:

Screen Shot 2014-05-06 at 11.51.20

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

Advertisements

10 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.

      You might also want to try out the original code from https://code.google.com/p/cvaddon/source/browse/#svn%2Fcvaddon_fast_sym

      • 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
    http://www.researchgate.net/publication/220122775_Bilateral_Symmetry_Detection_for_Real-time_Robotics_Applications/file/e0b49528de96aea906.pdf

    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.

      Keep up your good work, many people who read my blog really like your work.

      • 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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s