Marker Detection for Augmented Reality Applications

Posted by Corné den Otter on 2 April 2010

Tag(s): Hobbyprojecten, Open Source

[update] We received a lot of comments requesting for the source code. At the moment we are very busy, so unfortunately we haven't had the time to clean-up the marker detection code. Because this has already been the case for quite some time now, we have uploaded the code (under the GPL). You are free to download the code in the zip file at the end of this blog post.

The code is just a prototype: it is hardly optimized and needs a lot of clean-up (and better memory management ;-)). That said: it's yours to play around with. Good luck with it and enjoy![/update]

At Infi we have something similar to Google's 20 Percent Factor. If you have a great idea or something you want to know more about, you can spend time on it during work hours. The subject we’re currently interested in is augmented reality.

We (Corné and Reinder) started with looking for existing AR frameworks and found one interesting open-source project: ARToolkit (plus). This toolkit is written in C/C++ but also ported to flash en used in many AR demos you can find on the internet.

Unfortunately, the algorithm used for the detection of markers in this toolkit has some downsides:

  • It is not very fast.
  • It is not very good in detecting markers having an edge or corner (partial) occluded.
  • It is based on a thresholding algorithm, and therefore performs not very well under changing or not homogeneous lightning conditions.

There are some successors of ARToolkit, using edge based detection algorithms (like ARTag and Studierstube Tracker) but these are closed-source libraries.

In 2008, Martin Hirzer wrote ‘Marker Detection for Augmented Reality Applications’ [1], an article explaining an edge based marker-detection algorithm. We decided to implement this algorithm  in  C++.

At the moment our code is just a prototype. Eventually (after a cleanup) we will open source our implementation and/or donate it to the ARToolkit code base.

In this blog post we explain the implemented algorithm.

[update] At the end of this post you can find a video of the marker detection in action.

Algorithm

Step 1: Divide image in regions 

First the image is divided in small regions of 40x40 pixels and each region is divided into horizontal and vertical scan lines 5 pixels apart.
The next 3 steps are executed apart inside these regions which boosts the performance dramatically.

Step 2: Detect edgels in regions

Then a derivative of Gaussian is convolved on each scan line to estimate the component of the intensity gradient along the scanline.

This Gaussian derivative is used to detect black/white edges in the image. The Gaussian derivative is based on convolving the image with a small, separable, and integer valued filter in horizontal and vertical direction and is therefore relatively inexpensive in terms of computations. Local maxima along the scanlines stronger than a certain threshold (for all three color channels!) are considered to be edgels.

The Gaussian derivative kernel used, is given by:

[ -3 -5 0 5 3] * A

If an edgel is detected, the Sobel operator is used to determine the orientation of the edgel. The sobel operator is given by:

The orientation is then saved with the edgel. In the image above, the green dots are horizontal orientated edgels and the blue ones are vertical orientated edgels. 
 

Step 3: Find segments in regions

After the detection of the edgels, a RANSAC-grouper algorithm is used to construct line segments in each region [2].

RANSAC is an abbreviation for “RANdom SAmple Consensus”. It’s an algorithm to find groups of “inliers”, i.e. points which can be fitted into a line.

The RANSAC algorithm in short:

  1. Randomly choose 2 points from the same region, whose orientations are compatible with the line joining the two points, to hypothesize a line.
  2. The number of points supporting each line is counted. To be considered part of a line an point must lie close to it and have a compatible orientation with the line.
  3. Steps 1 and 2 are repeated ~25 times before a segment is found.
  4. Lines with enough support (at least 4 segments) are considered detected lines. Steps 1 to 3 are repeated until all such lines have been found.

More about RANSAC: http://en.wikipedia.org/wiki/RANSAC.

Because we know the orientation of the edgels from step 2, we can give the linesegments an orientation. In the image above, the constructed segments are displayed as red and green arrows.

Step 4: Merge segments to lines

In this step the segments are merged to lines.

Two segments are merged if:

  1. The orientations are compatible.
  2. The segments are close to each other.
  3. If the pixels along the line between the two segments are on an edge, using the same edgel detection criteria as used in step 2.

First all segments are tested in their own region using this algorithm. When all possible segments are merged in their own region, the same operation is repeated for all segments in the whole image.

The merged lines are displayed as red/green arrows in the image above.

Step 5: Extend lines along edges

In this step the lines are extended along the edges.

Because we scan only pixels on scan lines 5 pixels apart, it’s inevitably that the merged lines don’t fit on the entire length of the edge of a marker. So in this step we extend the detected lines pixel by pixel until we detect a corner:

  1. Extend each end of a line and check if each pixel is on an edge, using the same edgel detection criteria as used in step 2. Do this until we hit a pixel that’s not an edge.
  2. Take a pixel a couple of pixels further. If this pixel is ‘white’, we might have a found a corner of a black on white marker.

The extended lines are displayed as yellow arrows in the image above. In step 6 and 7 only lines with at least one corner are used.

Step 6: Keep lines with corners

Keep the lines with corners.

Step 7: Find markers

Finally, we try to find all markers in the image.

To detect the markers in the image, we try to find chains of 3 to 4 lines. A chain is a list of lines where the end of one of the lines hits the start of another.

After finding such chains, we only want to keep chains which form a rectangle counter clock wise. These chains will have black ‘inside’ and are probably markers. Knowing the orientation of the lines, a cross product for each two successive line segments in a chain is used to check this condition.

After finding all markers, for each marker the 4 intersections of the lines in the chain are considered to be the corners. Calculating the positions of corners by these line-intersections gives a robust algorithm. Even if only 3 lines are detected and/or a corner is occluded, the marker will be correctly detected most of the time.

In the image above, all detected markers are displayed as red rectangles. Notice the correctly detected marker at the bottom of the image, although one edge is partially occluded by a pencil.

Now we have the coordinates of the detected markers. The next step would be to identify markers and distinguish them from each other in order to use this algorithm in an augmented reality application, but that will be a next blog :-)

Update: Marker detection in action

References

  1. Martin Hirzer, Marker Detection for Augmented Reality Applications, 2008.
  2. J.C. Clarke, S. Carlsson, and A. Zisserman. Detecting and tracking linear features efficiently, 1996.

Dowload related files:

Comments:

Posted by Lisa on 7 April 2010, 22:04:
How's the chance to port this to Java? Marker detection is a big thing for mobile devices and I'm searching for a working implementation for Android.
Posted by Reinder on 8 April 2010, 15:04:
Hi Lisa. At the moment our code is just a prototype (in C++). Eventually (after a cleanup) we will open source our implementation. After that, a port to Java should be easy, but that's not on top of our priority list.
Posted by PIerre on 8 April 2010, 17:04:
Very interesting. Could be plug also as a real time edge-let detector and so on be use as a local feature.
I'm very interested in a C++ open source code for this marker detector.
Posted by Lisa on 10 April 2010, 00:04:
Any ideas when the source is going to be released? Any Twitter account or mailing list we can subscribe to in order to get notified?
Posted by Erik on 11 April 2010, 13:04:
Very nice! Looking forward to the cleaned up code. Good job!
Posted by Lisa on 26 April 2010, 23:04:
Well, guys? Any news?
Posted by Antonios Chalkiopoulos on 12 May 2010, 00:05:
Our team would be interested into porting this application in Java once the code is finalized !
We are in fact completing a port of ARLib in Java and your algorithm looks very promising.

Please sent me a message once the code is made public!!
Posted by Sesh on 29 May 2010, 10:05:
this is interesting. can you please update if you are ready to share the C++ code.
Posted by wisrage on 18 June 2010, 04:06:
I'm interested in detecting markers. So, I'm very impressed by your running movie. Would you mind you send me your source code? If you do, I will have great helps.
Posted by gio on 19 June 2010, 09:06:
I'm currently trying to implement the same algorithm. I'm too very interested to see your code. Thanks
Posted by ArAgorrn on 21 June 2010, 14:06:
Hi,

I would also be very interested either your source code or even the detailed algorithm.

Posted by Xavier on 24 June 2010, 00:06:
Hy Guys!

Any chance on seeing that code any time soon?
Posted by Antonios Chalkiopoulos on 24 June 2010, 21:06:
Poking again about the source code ...
Posted by Reinder on 25 June 2010, 12:06:
We received a lot of comments requesting for the source code. We're still planning to release the source-code, but because we're quite busy at the moment we didn't had the time to release it yet.
Posted by Lisa on 4 September 2010, 13:09:
It seems like the source code won't be released. Are there any free alternatives out there, particularly for Android?
Posted by Reinder on 13 September 2010, 17:09:
At the moment we are very busy, so unfortunately we haven't had the time to clean-up the marker detection code. Because this has already been the case for quite some time now, we have uploaded the code (under the GPL). You are free to download the code in the zip file at the end of this blog post.

The code is just a prototype: it is hardly optimized and needs a lot of clean-up (and better memory management ;-)). That said: it's yours to play around with. Good luck with it and enjoy!
Posted by Emdad on 28 October 2010, 11:10:
Hi,
Thanks for the nice post and code. From the "start" and "end" point My question is, how to calculate and get the exact 4 corners after marker detection, because all the 4 points are somehow a start and an end point at the same time. Is it possible to get all the corner points exact and individually from your soure code? Please let me know if possible. I'm interested to implement your code for AR projection on marker. Thanks in advance.
Posted by Reinder on 28 October 2010, 11:10:
@Emdad. Markers are detected by:

std::vector<ARMarker> markers = edgelDetector->findMarkers();

(in main.cpp)

Each marker has four (public) member variables: c1, c2, c3, c4 (of type Vector2f). The four corner points of the marker are given by these variables.
Posted by Emdad on 28 October 2010, 11:10:
Hi,
Thank you so much. I got it now.
Posted by Marc on 5 January 2011, 15:01:
Are there any follow-ups on this? I really like the algorithm and I started working on some tweaks but as I'm pretty new to AR, I don't know how to display an object on the marker.

Could anyone point me in a direction of a paper / tutorial / article of actually rendering an object on the marker?
Posted by Lavi Shapiro on 2 February 2011, 21:02:
Why not use Linear Regression instead of RANSAC
Posted by Jan on 9 February 2011, 14:02:
How strong computer was used for computing markers? I have performance problems when I am computing complex picture but I have my self implementation for marker detection. My idea is implement all algorithms on GPU in future.
Sorry for my English.
Posted by Saba on 20 April 2011, 07:04:
Can I get this code of marker detection in android.Please
Posted by Wojciech Radomski on 4 June 2011, 11:06:
I found, that if you cover the camera with your finger (for example) the code crashes on line:
Vector2f(const Vector2f& rhs) { set(rhs.x, rhs.y); }
in Vector2f
Any ideas what can fix the problem?
Posted by Wojciech Radomski on 4 June 2011, 11:06:
OK, i found it. It was a trival one.
In edgelDetector there is do while loop which should be while do, so it wont make instructions if there are no lines.
Posted by wguo on 2 October 2011, 05:10:
A good job. I want to know is there any similar good job on ellipse marker detection?
Posted by min on 20 February 2012, 04:02:
i tested this prototype code in VC2008.
it is very slow.. maybe 2frame/s.
why slow? is it fast algorithm?
Posted by Rusun on 27 February 2012, 09:02:
hi, can i have full project visual studio like in video?
I'm so interest about markaer detection in artoolkit
Posted by Micheal on 28 February 2012, 01:02:
how to compile this source?
Posted by NicoX on 20 July 2012, 07:07:
Hi Corné den,
I am trying to built an AR based iPhone app.
Can you help me how to port and test your sample code in XCode. Can I get your help by emailing you back. You have my email now in the system, if you are not very busy can you revert such that I can discuss you about what exactly I am trying to develop.
Regards
NicoX
Posted by Akihiko-y on 10 August 2012, 12:08:
Hi.
I tried this program, and found that sometimes it crashes (segmentation fault).
I debugged and fixed this problem by changing the code as follows:

edgeldetector.cpp:line 220:
if(linesWithCorners.size()) do {

The segmentation fault was caused by accessing to an element of linesWithCorners when its size is zero.

Now, this code works very well, and it's very nice!
Thanks your good work!
Posted by Ari on 19 September 2012, 20:09:
Hello Guys,
This is what I was looking for in the Internet for a long time and I found it explained shortly and very well on your blog.
Thank you very much ^^
Posted by Ridwan on 25 December 2012, 19:12:
i tested this prototype code in VC2008.
but it doesn't work. how to compile this source?

thanks
Posted by Akash on 22 January 2013, 21:01:
Hi Guys,
Is there a blog on how to use the detected markers from the above code in an Augmented Reality application?

I am presently able to see the markers that I need but I would like to use them to overlay other Graphical Objects.

thanks.
Posted by Arpitha on 17 February 2013, 07:02:
Hello guys,

Can i get procedural steps about how to implement this code in VS2008. I am doing mtech project based on this. So i need help. Reply asap.

Thanks
Posted by Arpitha on 17 February 2013, 07:02:
Hi Ari,

May i know how u have implemented this?
Posted by Aamir on 25 February 2013, 06:02:
Guys, I want to know that how to implement this code in java.
and can i use it for superimpose?
Posted by maulana on 24 July 2013, 21:07:
can you send to me complete program to my email ?
i really need it ..
please send to my email ..
Posted by Salman on 1 December 2013, 05:12:
Hey plz send me the source code.
Algorithm is awesome.

Post a comment:

Name:
E-mail*:
Comment:
*optional, will not be published.