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