Efficient Marker Detection for Images 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
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.