Anyone here clever with image processing? I'm working on a project which is using OpenCV to match a template (120 square or circle points - it's an eye test chart) and find it in another image, then translate that so the new image points line up to the template.

I'm using OpenCV's feature detection (in Java) to match the template. Only problem is (and I've only just discovered this) it doesn't work with images that aren't based off the template. It's picking up the shape of the points which are all slightly different. If I change then all to perfect squares or circles it breaks.

I asked a question on Stack Overflow and had a reply that there is no easy way to find the pattern in another image and need to make my own algorithm, but no idea where to start.

I can use contour detection to get the location of the points, then somehow need to process them to match up to the template. Does anyone have any idea how to do that?

I haven't done this sort of processing, and I don't understand your second paragraph, but your final paragraph sounds like it might just be geometry/trigonometry?

Can you post an example of the starting point and the goal, and what you've got so far?

I have images like this (squiggly lines added to test template matching):


And I was using this as the template:


OpenCV has feature detection which can detect features in one image and map it to features found in another image. This works great using that template with the top image as the template is extracted from the source image. It detects the shape of each point in the template and finds them in the source image. I've been the same images from the start and assumed it was working properly until this week.



This can then be used with affineWarp to align the first image so the positions of each point line up in the same place as the template. If I use a different image the points don't match up properly and I get this:


So now I am trying something much more complicated and manual. Currently got as far as this - threshold image, detect contours, filter depending on size:


Nearly all the points are picked out as contours, but I need to find known points that I can match up to the template for the alignment.

Ok, I think I understand the issue now.

My (possibly naive) approach would be to extract coordinates of all dot positions from the template and work out the ratios from the centerpoint, e.g. the top two dots are 1 unit high and 0.836 to either side, the bottom outer dots are 1.62 and 1.11 units away from centre, and so on.

I'm assuming the axes are consistently present, so you can do edge detection and/or a separate template to detect where the centre point is - otherwise I'd probably start by looking in the cleanest corner (bottom left) and trying each dot found until enough of them match to identify where the centre would be.

Once you've got an anchor point (the centre) and have identified enough dots that match the template ratios, you can calculate how many pixels are in a unit and resize appropriately.

Dunno if that's the best approach, and it's also assuming OpenCV can actually extract the coords of dots, but seems reasonable enough?

Well this is a project for work but I'm also using it for my dissertation. For work, apparently no, they don't always have the axis. For my dissertation I can make them all have it.

If I can work out the center of the chart bit it might be easier. Although you have given me an idea which might work. Start from each end of the list of points (yeah center coordinates are easy) and try and find a point at known distance/angle from them. Only problem is if the image is scaled more in one direction. I don't really know how similar they will be.

Thanks for the ideas. 4 months to sort it out.

I tried to do something with 3 nested for loops. The contour detection picked up 1,000 points. So (in the voice of Dr. Evil) 1 billion combinations. And got an out of memory error

There aren't a million points in your contoured image, unless perhaps you're counting individual pixels?

Even so, a million pairs of numbers shouldn't use more than ~32MB, so you may be creating unnecessary variables and/or need to scope things so the GC knows when it can throw them away. (I just checked and the image you posted only has 0.61 million pixels in total, including the blacks, so something isn't right.)

Actually, the dots in your image are ~7px in size, and the gaps are bigger - you can resize down to ~100px wide without merging them, which means you can fit coords into a byte or two (so 1-2MB of memory for a million), and at the same time simplify the threshold/contour/filter process.

For the angle/scaling issue, you can use the axes - the ends should be at the same x/y - if they're not it needs rotating. Without axes... well assuming the squares are supposed to be square, you can probably still get OpenCV to detect rotation/skewing and do the appropriate calculations/transformation.

No, not 1,000,000 points in the image, only 1,000. Some are overlapping. A bit more filtering to get rid of them bright it down to 250ish.

But when it was 1000, iterating over all 1000 inside a loop that iterates over all 1000 inside a loop that iterates over all 1000... that is a billion right? Extremely inefficient way to try and find 4 corners on the chart.

Yeah I might focus on the axis for now. And if the width and height are always the same that could give me exactly what I want.

I don't think the detection of the shapes is good enough at that size. Besides, not always any squares on an image.

Or possibly Fourier transform.

Or maybe not. I thought that found the center but doesn't look like it.

Yeah, a thousand cubed is a billion, must have misread that, and I guess if you're cloning arrays in nested loops you could create enough variables to use that much memory.

Of course, any time you find yourself nesting loops in any scenario you should take a step back and check what you're doing, especially if it's more than two levels and using the same data - there'll almost certainly be a different approach worth considering. Pretty sure detecting corner/outermost points doesn't require any nesting.

Oh I know, three nested loops is not a good idea with that many elements. I have no idea what I am doing though  8-O

I thought of one possible way around it. Just get them to upload an image of the chart without all the extra crap around it. I can easily (I think) find 4 points to match up the image then.

Is "them" the staff in a single lab/whatever who might actually listen, or does it include various clients who will blatantly ignore your hand-held instructions the moment you turn your back and go raise an issue claiming there's a bug in what you did despite it being a completely unrelated error that wouldn't occur if they did things how they were told? :@

Haha. Internal staff. Who are probably going to ignore my instructions and raise an issue despite not following instructions :D

I do have another plan though. Which I think would work up to a 9° rotation.

So. Iterate over points, pick 3, starting with two from top left and bottom right. Find the affine transform between those and my set of known points. Check how many points match.

Repeat, selecting second and third from top left with bottom right. Keep going for a bit then move in from the bottom left one with 1 and 2 from top left...

A quick check on my sample image and it's only 3000ish combinations. Not sure how fast affine warping is. I think that would pick out 3 easy to find points.

What's special about 9°?

It's more like 12°. Due to the order it detects the points while contour matching it would pick up the top two first (well last - it seems to work in reverse). Anything higher and the second point in the list would be the wrong point I want to match up to.

I think I have found a solution that works  :-O~~~ Assuming that the contour detection manages to pick out the 3 specific points that are needed.

It's a lot more computationally... er, computational. Somewhere between 10-30,000 iterations for the tests I've tried. I could probably optimise it further, some tests it's doing where the points are not far enough apart, or not the 3 points are in a straight line.

I still need to do some more testing, but initial tests are looking good.

I think I found why I was running out of memory in the big loop. OpenCV. Maybe cos it's wrapping C++ in Java. You can call release() on some objects to release it's memory.

Try Java Mission Control and/or Eclipse Memory Analyzer - helps find objects causing memory leaks. Or for stuff like seeing if you've got too many instances of something you only expect to have one of.