3
$\begingroup$

I need to detect a known number of simple markers (chessboard patterns) in a color image efficiently.

I implemented normalized cross correlation (NCC) as a pixel shader via WebGL since I need this to work in a client application in a browser. Detection works fine and is sufficiently robust, but I need better performance. It currently takes a number of seconds to calculate the NCC image, and I'm already using 'obvious' optimizations such as cropping the image (I have a rough indication where the markers should be) and reducing the resolution. I also optimized the code itself (e.g. using loop unrolling, but that is another matter and probably belongs on SO).

The image has a resolution of 900x520 pixels and the markers are 22 square pixels. The code runs on tablet computers with Intel Atom processors.

My question is: Are there algorithms that are better at utilizing what I know about the image and the marker geometry, ideally ones that are suited for almost branchless pixel shaders? For instance, I was considering a band pass filter (a fourier transformation that only leaves the frequency of the marker, so to speak) or FNCC (JP Lewis's paper), or something that utilizes the fact that the markers are black and white.

Unfortunately, it seems these approaches are comparatively expensive since the FFT of the image isn't cheap and my markers are small compared to the image resolution. Testing a ton of algorithms blindly isn't an option, unless there's a library I'm not aware of that helps me implement this in JavaScript or as glsl pixel shaders. Even then, an indication of a more efficient algorithm would be helpful.

EDIT: Added an image of the marker. The background is normally transparent, of course, i.e. the NCC will ignore those pixels

The marker image I'm looking for in the picture

|improve this question
$\endgroup$
  • $\begingroup$ Did you try OpenCV's checkerboard detection? docs.opencv.org/doc/tutorials/calib3d/camera_calibration/… $\endgroup$ – Tolga Birdal Jan 7 '15 at 11:42
  • $\begingroup$ Do you mean detecting a small chessboard image in a general image, or finding the corners of a large chessboard that covers the whole field of view? $\endgroup$ – Andrey Rubshtein Jan 7 '15 at 13:30
  • $\begingroup$ @tbirdal: Yes, but it's not really a good solution for my use case, since I need to detect multiple checkerboards and the boards only have four fields each. OpenCV's checkerboard detection is made mostly for camera calibration so you can later correct the lens distortion. Also, I can't use OpenCV because it's written in C++ and I need something in JavaScript, or implemented as a shader. I didn't look at the source to find out how they do it, though. $\endgroup$ – mnemosyn Jan 7 '15 at 15:13
  • $\begingroup$ @Andrey: I want to find 6 checkerboards that merely have four fields (much like you see on crash test dummies) in an image. The checkerboards are much, much smaller than the image. $\endgroup$ – mnemosyn Jan 7 '15 at 15:14
  • $\begingroup$ Could you provide some typical images? $\endgroup$ – Andrey Rubshtein Jan 7 '15 at 15:54
2
$\begingroup$

This is a saddle point. I would suggest using derivative operators to spot such discontinuities. In fact, Haralick presents a broad overview of these methods in his Topographic Primal Sketch.

The use of approximate Facet model would give you a speed boost. I used them for edge detection here.

There is also one implementation available here.

Even though this question and the topic is rather old, I would like to update that, the method presented in the following work contains no branching and is quite suitable for the shader:

Birdal, Tolga, Ievgeniia Dobryden, and Slobodan Ilic. X-Tag: A Fiducial Tag for Flexible and Accurate Bundle Adjustment. 3D Vision (3DV), 2016 Fourth International Conference on. IEEE, 2016.

|improve this answer
$\endgroup$
  • $\begingroup$ Thanks for your answer, that looks promising, especially the paper. Since I'll have to implement everything in JS or shaders, I'll first need to understand how to implement it (manually, so to speak), and how complex that is (in terms of amount of coding work required). Is there any information on the theoretical runtime complexity for this approach with regard to the image size? The NCC is roughly O(N * M) where N is the number of pixels in haystack, and M is the number of pixels in needle, a number that grows pretty huge. I'll read up on nonlinear programming tomorrow... $\endgroup$ – mnemosyn Jan 7 '15 at 23:28
  • $\begingroup$ Well, these are not search operators. They directly operate on image values and benefit from the specific mathematical characteristic. I would say O(kN), where k is some constant and N refers to # pixels. $\endgroup$ – Tolga Birdal Jan 8 '15 at 0:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.