Finding subpattern position in an image/pattern

Question

Lets say I have an image or two dimensional pattern similar to QRcode and call it a template. Now I have a set of subimages that I want to match with my template and what's important - find their precise location in the template. I think similar problem is being solved in 'smart papers' http://en.wikipedia.org/wiki/Anoto and in kinect's grid of infrared dot pattern.

Does anyone have some clues how something similar can be implemented (even just keywords to look up)?

I had few ideas:

• opencv template matching method - poor results when rotated, scaled, skewed
• SURF feature detection and matching - it's pretty good but result is worse when subimage is a really small chunk of the template. Besides I think that specificly picked up pattern would improve location finding rather than arbitary image. Also I think SURF is an overkill and I need something efficient that can handle real time mobile camera streams.
• creating an image consisting of many QRcodes that only stores coordinates as data - drawback i that QRcodes will have to pretty small to allow fine-grained positioning but then it's difficult to recognise them. Pros - they use only black color and have many white spaces (ink conservation)
• 2-dimensional colorful gradient image (similar to color model map) - I think this will be sensitive to lightness

Answer 1

QRCodes are square. Using feature detection to find the grid, you can unproject it. Then opencv's template matching will work fine.