Template matching method for verification code recognition

When writing a reptile, it is inevitable to encounter the problem of verification code recognition. The common verification code identification process is as follows:

-The image is grayed out

-image denoising (such as image binarization)

-Cut the picture

-extract features

-Training

However, this method is graph cutting, and the key and difficult point to crack the verification code is whether the characters can be successfully divided.

The algorithm introduced in this paper does not need image cutting or machine training. This method is template matching: the text to be recognized is cut into templates and matched with the templates in the image to be recognized.

This paper will be divided into two parts:

The first part introduces the basic concept of template matching and an implementation algorithm of template matching: fast normalized cross-correlation matching algorithm;

The second part is a concrete example.

Template matching is one of the methods to find the target in the image, and its purpose is to find the region most similar to the template image in the image.

The general process of template matching is as follows: by sliding the image block on the input image, the actual image block is matched with the input image.

Suppose we have an input image of 100x 100 and a template image of 10x 10. The search process is as follows:

Cut a temporary image from the upper left corner of the input image (0,0) to (10, 10);

The similarity c between the temporary image and the template is obtained by some method and stored in the similarity matrix (the matrix size is 91x 91);

Cut the temporary image of the input image from (0, 1) to (10, 1 1), compare and record it in the similarity matrix;

Repeat the above steps until you reach the lower right corner of the input image.

Finally, a similar matrix is obtained, and the maximum or minimum value in the matrix is found. The temporary image corresponding to the maximum value (minimum value) is the image most similar to the template.

In step b, there are many methods to find the similarity between the template and the image, such as mean absolute difference algorithm (MAD), absolute error sum algorithm (SAD), error square sum algorithm (SSD) and normalized cross-correlation algorithm (NCC). In this paper, the normalized cross-correlation algorithm is adopted.

What is normalized cross correlation?

Geometrically, when two vectors are parallel in the same direction, the normalized cross-correlation coefficient is 1, which means that the two vectors are the most similar; When their directions are opposite and parallel, the normalized cross-correlation coefficient is-1, and when they are perpendicular, it means that they are the least similar (the same is true for representing the whole space with three mutually perpendicular vectors, which do not contain each other's information, and the correlation coefficient is 0). At a certain angle, at (-1, 1). Is it similar to cosine function, cos (0) = 1, cos (pi/2) = 0, cos (pi) =- 1? Just like this, the correlation coefficient can be regarded as the cosine function of the included angle between two vectors.

In mathematics, the cosine function is calculated like this. Assuming that the coordinates corresponding to two N-dimensional vectors x and y are (x 1, x2, … xn) and (y 1, y2, …yn) respectively, then:

(If you want to know more, please refer to Reference 2. )

However, this is one-dimensional, so we need to add another dimension to template matching (please Refer to ref. The specific algorithm is 3). Briefly talk about the content of Ref. 3. If the two-dimensional similarity is directly calculated, the computational complexity will be very high. References. 3. Fast Fourier transform and integral image fast algorithm are used to reduce the computational complexity.

Next, let's look at a specific application.

The specific steps of template matching identity verification code are as follows:

1. Find all possible characters in the picture and make a template set.

2. Image graying

3. Image denoising (binarization)

4. Template matching

5. Optimization of matching results

The picture to be recognized is as follows, taking the recognition of characters in the picture as an example:

In order to find the most matching part with the template from the image, the template image is the part cut from the image in advance. Use the match_template method in python module skimage, and the match_template method uses fast normalized cross-correlation algorithm 2.

Traverse the template image set and match it with the image. If dist is greater than the threshold value h, it is considered that the template exists in the image, otherwise it does not exist, and the next template continues to be matched until all templates are traversed.

Take template' Jia' as an example. The image size is 40x260 and the template size is 27x27. The result is a matrix of size (14,234), which is the similarity matrix mentioned above. The values in the matrix belong to [- 1, 1], and the corresponding position where the maximum value is found in the result is sum. (See Reference 4 for details. )

But this is a good situation, because all the templates are traversed when matching, and the number of templates appearing in a picture is limited. For example, the number "four" does not exist in the picture. At this time, these templates that do not appear in the picture should be removed according to certain rules: dist variable is used in the program to filter the matching results, and if dist variable is greater than a certain value, the template is considered not to exist in the image.

In the final result_list, there may be some templates that don't exist in the picture or don't match accurately. For example, the number' one' does not exist in the template, but it can still be matched, because the number' two' can be matched to' one' and needs further optimization. There are many optimization methods, such as choosing a larger template when two matching templates are too close, and leaving the rest for readers to consider.

How to use the deep learning identification verification code will be introduced later, so stay tuned ~

References:

blogs.com/beer/p/5672678.html

/blog/2065 438+03/03/cosine _ similarity . html

J.P. Lewis, "Fast Normalized Cross Correlation", Industrial Optical Magic.

http://sci kit-image . org/docsjinhqin/dev/auto _ examples/plot _ template . html

About the author: Li Hui (Dian Ronggang) graduated from Dianrong College of University of Electronic Science and Technology of China, and now works in Chengdu Data Department of Dianrong. She is a dynamic young woman who is curious about all new things and has no resistance to dancing.