# How do I identify repeated subimages within a larger image?

I have a large image of a microscopic die of an integrated circuit. The pixel dimensions are something like 15000 x 10000.

The image contains a number of repeated structured subimages. Some large blocks might even repeat 3 or 4 times because there was a need for duplicated functionality. (See good candidates on the left of the example image)

I'd like to identify the largest(in pixel dimensions) repeating subimage block, and then highlight the locations of those subimages. I would repeat this process looking for the next largest repeating subimage block, highlight those, and so on.

To be clear, I don't have the subimages in advance. The problem isn't only to find the location of certain subimages within an image. That's Step two. :)

While the image is in fact a color image, it could be easily turned into a gray-scale image without loss of content.

There is obviously some "noise" to an image like this, and there'd have to be some adjustable "fudge factor" on what to consider a match.

I'm not entirely sure where to start on this, or if this is even the correct SE. Would FFT be a potential solution? Using MatLab? Specific one-off image analysis tools?

I could write some simple image analysis software that breaks an image up into smaller blocks, and then searches the image for those blocks. But this sounds incredibly slow to me, and there's got to be a more efficient way to do this.

A naive approach would be to set a maximum size, .25 image width, and compare every possible square with every other possible square, in a "sliding window" fashion.

So take a 5000 by 5000 square as your reference (eg 0,0 to 4999,4999). now grab all the other possible "windows". Start by comparing your reference square to the square at (5000,0 to 9999,4999), then compare your reference square to the square at (5001,0 to 10000,4999) then to (5002,0 to 10001,4999) etc.

So your compare function could subtract the (greyscale) difference between each pixel of your reference frame and your target frame and give a score.

Next (after comparing your reference to all other possible squares), you select a new reference, the square at (1,0 to 5000,4999) and compare that reference square to all other possible squares.

Once the whole process was done at the 5000,5000 size, you would know if any structure of size 5000x5000 matches any other part of the image (to a threshold).

Then, you would make your reference square smaller, eg 4999x4999 and repeat the whole process at size 4999x4999 to see if any structure of size 4999x4999 is "duplicated"

You would proceed until your minimum size.

Then...you would want to try instead of squares...rectangles of different proportions.

As you can see, this is computationally prohibitive, so you have to make compromises:

• make the source image smaller. Only when you have a near match, check the high res map at that location
• slide by 10 pixel increments
• identify some basic reference structures yourself, and only use those as reference
• try a "monte-carlo" approach by trying random locations and getting statistics of promising locations for pixel by pixel checks
• implement on gpu
• limit the structures to only a few rectangle shapes rather than all
• preprocess the image to have higher contrast
• start by using small sizes (20x20 pixels) and once you find small matches, grow your "square" there to look for larger matches that might be the "real" duplicated structure

So there's no magic. What there is is domain heuristics. You tell your script what you think are the likely sizes/shapes/locations/orientations of structures.

However, the question of "why" you need to identify duplicate structures is actually fundamental to how you will optimize the problem.

EDIT: an entirely different approach would be to use some algorithm that's pre-tuned for "object segmentation" to go through and find anything that seems to have a defined boundary, then run a clustering algorithm on all the "objects", and it should group the most similar ones together. Then you can manually select the matches or do a final threshold step. This is likely much more similar to how the "human" brain does it as is likely to be much faster

• Thanks much. I've already implemented something similar to this, although it never occurred to me to simply subtract the two frames for comparison. I was hashing each of the sample size squares, and then comparing the hashes of the potential matches. I was using a custom hash which XOR'd each vertical line that contained the differences between average brightness for the square, and each pixel. This is different from a standard hash --- similar images produce similar hashes. Too complicated and it basically wasn't successful. – Keith M Oct 26 '15 at 0:58
• This ID of dupes is to aid in reverse engineering, easier to compare to block diagram once paired with pin locations. Structures like FIFOs, multiple channels that do the same thing, internal registers, and so on. – Keith M Oct 26 '15 at 1:05
• @KeithM yeah, there's many different comparing functions, but the most robust way is to do a trained convolutional net over the reference and target squares and compare the output of the final layer (before classification), which should output the same results regardless of small differences. However, if your images are not warped (your example image seems warped), then simple subtraction of two SCALED DOWN images should work. At full resolution isn't not likely to work because a duplicate feature might be shifted "half a pixel" from the source. This would also cause your XOR method to fail. – AwokeKnowing Oct 26 '15 at 16:02
• @KeithM correcting the warp of the source before processing is probably the single most important thing that will help your results. – AwokeKnowing Oct 26 '15 at 16:06
• Example really just shows the subject material. Original image is MUCH higher quality, flat, higher res, just needs grayscaled and contrast-enhanced. I implemented the subtraction function last night, and it reports zero-error (perfect match) when it finds the original reference. It works but is INCREDIBLY slow. I can use multiple cores and parallelize it -- plus optimize the C#. Using 64x64 pixel squares now, but should be starting much larger. I could randomly pixel compare and do early rejection to save time. – Keith M Oct 26 '15 at 18:07