Take the 2-minute tour ×

I need to find the position of a smaller image inside a bigger image. The smaller image is a subset of the bigger image. The requirement is also that pixel values can slightly differ for example if images were produced by different JPEG compressions. I've implemented the solution by comparing bytes using the CPU but I'm now looking into any possibility to speed up the process. Could I somehow utilize OpenGLES and thus iPhone GPU for it?

Note: images are grayscale.

share|improve this question

1 Answer 1

up vote 1 down vote accepted

@Ivan, this is a pretty standard problem in video compression (finding position of current macroblock in previous frame). You can use a metric for difference in pixels such as sum of abs differences (SAD), sum of squared differences (SSD), or sum of Hadamard-transformed differences (SATD). I assume you are not trying to compress video but rather looking for something like a watermark. In many cases, you can use a gradient descent type search to find a local minimum (best match), on the empirical observation that comparing an image (your small image) to a slightly offset version of same (a match the position of which hasn't been found exactly) produces a closer metric than comparing to a random part of another image. So you can start by sampling the space of all possible offsets/positions (motion vectors in video encoding) rather coarsely, and then do local optimization around the best result. The local optimization works by comparing a match to some number of neighboring matches, and moving to the best of those if any is better than your current match, repeat. This is very much faster than brute force (checking every possible position), but it may not work in all cases (it is dependent on the nature of what is being matched). Unfortunately, this type of algorithm does not translate very well to GPU, because each step depends on previous steps. It may still be worth it; if you check eg 16 neighbors to the position for a 256x256 image, that is enough parallel computation to send to GPU, and yes it absolutely can be done in OpenGL-ES. However the answer to all that really depends on whether you're doing brute force or local minimization type search, and whether local minimization would work for you.

share|improve this answer
Thanks for this exhaustive answer! At the moment I'm doing the sum of abs differences. I'm not dealing with video. It's a bit specific. I get two images from a service and I need to be able to zoom in on a bigger image at the exact point where the smaller image is located(and then the user can zoom out at will). What I did not mention is that the smaller image can be in different resolutions, so I pretty much brute force all resolutions until I find a match. I believe that could be parallelized on GPU? But I wish I could get some idea where to start looking at how it can be done. –  Ivan Kovacevic Nov 17 '12 at 9:57
@IvanKovacevic - The comparison itself can easily be done on the GPU using a difference blending of the two images (my GPUImage framework will do that pretty simply, for example), and a relative measure of difference could be found by taking the average luminance of the result (again, an operation that could be performed on the GPU). A more robust approach might be to use feature matching, but that would require a lot more coding effort to accomplish. –  Brad Larson Nov 18 '12 at 5:05
Thanks Brad your framework looks awesome! I will try the technique with blending and luminance, however I'm a bit suspicious that the bottleneck will be sending/initializing images in the GPU since I need to move in the original image pixel by pixel and create a crop image of the same size as the sub image (that I'm comparing with), and then send both to your diff blending filter. Maybe it is possible to write a custom filter that does all that on the GPU? –  Ivan Kovacevic Nov 18 '12 at 10:36
My question was a bit too broad so I accept this answer as a correct one. Also Brad Larson's comment was very useful! –  Ivan Kovacevic Mar 7 '13 at 18:03

Your Answer


