# Necessary image processing operations before template matching

Well, this may show I didn't take image processing class.

I have this template to match an object in images. But real object in images, for example, does not look like that but the second image. What operations do I need to take for the images like the second one to be ready for template matching? FYI, the third image shows a ideal matching.

In another idea, I fit the template to the image. That is, I give four corner coordinates on the image to match those in the template. Then it will compute a way to fit the template to the area.

UPDATE: Problem solved. Thanks to the answer I selected below. I successfully managed to apply my template on the image. The last image shows the result.

• you're not going to match that white grid, are you? You want to match the actual colorful grid in your second image, right? – endolith Apr 12 '12 at 20:37
• @endolith I think either way is fine. – Tae-Sung Shin Apr 12 '12 at 20:41
• can you share the basic concept of your algorithm? i need to do the same for a chart. – Gilad Feb 14 '14 at 15:25

The sample image you posted has relatively strong perspective (it is not imaged straight from the direction of surface normal) which can cause problems with template matching techniques witch use block processing. I assume that you have to take the image with strong perspective so first thing we want to do is estimate image transformation which will remove the perspective projection and will result rectified image ("straight image").

## Correcting perspective projection when shape is known

The ultimate goal of the preprocessing is to find corners of that gray rectangle which is the background the color chart. I started by simply thresholding with constant value. Literature/web has lots of information on how to do thresholding when the image has uneven lighting, but if you can, try to correct the imaging setup such that the lighting is relatively even.

I assumed that the color chart takes quite large portion of the screen, so the it is probably biggest continuous region of the image. There exist many black and white labeling functions (MATLABs bwlabel, IPPs LabelMarkers, OpenCV has external library cvblob) which will give each distinct connected region its own index. After the labeling you can calculate the areas of the connected components using a histogram and then choose the component with largest area.

It is usually good idea to fill the components such that component does not have holes, this reduces the number of edge pixels.

Now we can use edge finding operators (I used gradient based method, but you can also trace the edge by following white pixels that are connected to black pixels) to get pixels belonging to the boarder.

As the object we are interested is rectangle, I fitted four lines to the edge pixels using robust line fitting (RANSAC). After finding new line, I removed all the points that were close to the found line, this forces subsequent fitting operations to return other edges of the object. Finally when all the edges were found, I computed all possible intersections between the set of lines. From the set of resulting points I removed all points outside of the image.

Now we have the corners of the color chart and as we know the dimensions of the chart, we can calculate the transformation matrix $H$ (homography, projection between two planes. use direct linear transformation (DLT) to solve $H$) between the millimeter coordinates and the pixel coordinates.

$\textbf{x} = H\textbf{X}$

This transformation matrix can be then used to transform the original image such that color chart is imaged straight from the direction of the surface normal.

As can be seen only radial distortion is left. When we used transformation $H$ for image transformation (2D interpolation), we chose the interpolation coordinates such, that the we know the precise resolution of the image, meaning that we now know for example the size of the letters.

If we still want to do some template matching, we can use any decent template matching method. The method does not have to be rotation/scale invariant as the image is already rectified.

Start with edge detection. Then use Hough transform to detect straight lines. Then figure out which lines are parallel and which ones should be perpendicular. Then estimate the projective transformation so that the lines that should be perpendicular actually are perpendicular.