image matching, affine warp

Question

My problem is shown here: problem statement. I have one template image, which i have to detect in the camera image. After it is detected i have to normalize the camera image by using an affine transformation. The goal of my work is to identify the crosses. I tried to use SURF features for the image normalization step, but the template image is very regular and not good for SURF matching. Any ideas how this can be done? Maybe some kind of contour matching?

Answer 1

Just find the biggest(thick and long) red lines and do affine warp.

Answer 2

Direct(pixel-based) aproaches could be better in your case than feature-based.

Good tutorial on Image Alignment you can find here: http://research.microsoft.com/apps/pubs/default.aspx?id=70092

Another idea is to choose ROI. If you know that right up area on your image consisted of red squares you could try to exclude it from SURF detection. Furthermore, you can detect shape of "red squared area" and use it for transformation estimation.

Answer 3

In addition to MoarCodePlz's answer there are two keywords that are fundamental to your task: solving a homography and Hough transform.

Answer 4

So I was giving this some thought and then realized that you're looking to take a WHOLE ticket instead of a subset of that ticket and transform it to a regular rectangle. This problem (in theory at least) is not all that difficult and writing some code to do it yourself is relatively trivial.

The most difficult part of this, by far, is going to be the initial corner detection. As you are only interested in the ticket as a whole, everything on the ticket means nothing. All you are interested in are the four corners. You can see from your picture that, when a ticket is lying on top of another ticket, the corner is not obvious. If all of your pictures were a ticket laying on top of a very dark surface then this would be trivial again, but the idea is to write an application that can hopefully handle even ambiguous cases. That being said I would suggest the following approach:

1) Use image filters to lighten the light areas of the picture and darken the dark areas of the picture.

I forget what the name of this sort of filter is but basically you want to have more contrast between the darker and lighter areas of the image.

2) Sharpen all of the areas above a given brightness, gaussian blur all of the areas below a given darkness

Feature finding algorithms generally rely on "sharpness" in an image to be able to detect corners and edges. By sharpening all of the lighter areas of the image (considering your ticket is white) and blurring all of the darker areas of the image you will increase your chances of being able to algorithmically detect the corners that you're looking for.

3) Use feature detection to detect the four corners

This is where things are going to get hairy. If you have a pile of lotto tickets that you're taking a picture of and you want to be able to algorithmically find one and display it sans-distortion then you're talking about cutting edge currently-being-researched material. If this is what you are trying to do then I suggest reading some of Yanxi Liu's papers, most notably Translational Symmetry-based Perceptual Grouping with Applications to Urban Scenes. You will most likely have to create a template from a pre-made picture of the ticket and then try to match the exact features of this template with a distorted grid of the same features in your camera image. Once you have a match that is above a percentage threshold then you can try to find the four corners of it. Should you find them successfully then you can move on to the next step.

IF, on the other hand, you are not trying to do the cutting edge stuff then you can just do some by-the-book feature detections. For corner detection I would recommend using The Harris & Stephens / Plessey / Shi-Tomasi corner detection algorithm. This is the same algorithm that Yanxi uses in a number of her papers and does a pretty good job of corner detection. I am not sure whether or not the filter takes a gray-scale of the image or if it takes the current color-scale, but if it does the latter then using a Canny edge detection filter before you use the corner detection algorithm would be advantageous. Once you get the main corners of the ticket (hopefully) detected then you will need to devise some sort of smart finding algorithm (based on the perspective and content of your photo) to "guess" which corners are ACTUALLY the four corners you care about.

It is also worth noting that "Mean Shift Belief Propagation" could help you in determining the most important features after the detection algorithms. Basically you take a number of feature points within a given box, average all of their coordinates, and then center the box on the resulting coordinate. If there are new points in the box after moving it, then you do it once more. You continue doing so until you have a single interest point in the center of the box. This is a brief description of the idea so I suggest you look into it further, as I don't know the averaging details.

4) Use bi-linear interpolation to determine the colors that you need to transfer over to your final image.

It is important to note that you do not want to take the colors from the image that you have distorted. The purpose of running all of the filters and detection algorithms on the image is to find the feature points that you are interested in. Once you have those coordinates, you go back to using the original image to pull colors.

If you're asking this question then I assume you know what bi-linear interpolation means. You would consider the top and bottom edges of the distorted ticket to start at 0 (left corners) and end at 1 (right corners). You would consider the left and right edges to start at 0 (top corners) and end at 1 (bottom corners). You would apply this same logic to the dimensions of the output image. Going pixel by pixel in the output image you would find the interpolation coordinates that you need to retrieve the color for and using bi-linear interpolation you would pull the colors from the input image.

And that's it! (lol) What you're asking to do is pretty involved, and I wish you luck in doing so. Creating an algorithm that does this perfectly for all cases without any user input is, from what I can tell, pretty close to impossible. Also the fact that you're looking at lotto tickets raises the question of how ethical is this project. In any case though, hopefully this is enough to get your brain started. Here are some additional links:

Canny Edge Detection: http://en.wikipedia.org/wiki/Edge_detection

Corner Detection: http://en.wikipedia.org/wiki/Corner_detection

Yanxi Liu's papers: http://www.cse.psu.edu/~yanxi/

Mean Shift Belief propagation: Used in the paper that I told you about

EDIT

Code for level separation

int threshold = 128;
float percentChange = .5;
int oldr, oldg, oldb, newr, newg, newb, grayscale;

//Assuming that pixels is a 1D array of pixel objects that make up the image you're currently working with. Syntax is of Processing.org

for (int i=0; i<pixels.length; i++) {

    oldr = red(pixels[i]);
    oldg = green(pixels[i]);
    oldb = blue(pixels[i]);

    grayscale = Math.floor((oldr + oldg + oldb) / 3.0);

    if (grayScale >= threshold) { //Brightness is above threshold, therefore increase brightness
        newr = oldr + (255-oldr)*percentChange;
        newg = oldg + (255-oldg)*percentChange;
        newb = oldb + (255-oldb)*percentChange;
    } else { //Brightness is below threshold, therefore increase darkness
        newr = oldr - oldr*percentChange;
        newg = oldg - oldg*percentChange;
        newb = oldb - oldb*percentChange;
    }

    pixels[i] = color(newr,newg,newb);

}