Text captchas are easily recognized by deep learning neural networks

Deep learning neural networks have made great strides in pattern recognition. At the same time, text captcha is still used in some well-known free email services. I wonder if neural networks of deep learning can cope with the task of recognizing text captcha? If so, how?

What is text captcha?

CAPTCHA (English “CAPTCHA”) is a test for “humanity”. That is, a task that a person easily solves, while for a machine this task should be difficult. Often used text with stuck together letters, an example in the picture below, also the image is additionally subjected to optical distortion.



CAPTCHA is usually used on the registration page to protect against spam bots.

Full convolutional neural network

If the letters are “stuck together”, then it is usually very difficult to separate them with heuristic algorithms. Therefore, you need to search for every letter in every place of the picture. The full-convolutional neural network will cope with this task . Full-convolutional network - a convolutional network without a fully connected layer. An image is fed to the input of such a network; at the output, it produces the same image or several images (center maps).


The number of center maps is equal to the length of the alphabet of characters used in a particular captcha. On center maps, letter centers are marked. The large-scale transformation that occurs on the network due to the presence of pulling layers is taken into account. An example of a symbol map for the “D” symbol is shown below.

In this case, convolutional layers with padding are used so that the size of the images at the output of the convolutional layer is equal to the size of the images on the input layer. The spot profile on the symbol map is defined by a two-dimensional Gaussian function with widths of 1.3 and 2.6 pixels.
The full-convolutional network was originally tested on the “R” symbol:

For testing, a small network with 2 pullings was used, trained on the CPU. After making sure that the idea works somehow, I purchased a used Nvidia GTX 760, 2GB graphics card. This gave me the opportunity to train larger networks for all characters of the alphabet, and also accelerated learning (about 10 times). To train the network, the Theano library was used , which is currently no longer supported .

Generator Training

Manually marking a large dataset seemed a long and laborious affair, so it was decided to generate captcha with a special script. In this case, center maps are generated automatically. I was picked up by the font used in the service displayed in a CAPTCHA for Hotmail , generated visual CAPTCHA was similar in style to the actual CAPTCHA:

The final accuracy of training on the generated captchas, as it turned out, is 2 times lower compared to training on real captchas. Probably, such nuances as the degree of intersection of symbols, scale, thickness of symbol lines, distortion parameters, etc., are important, and these nuances could not be reproduced in the generator. A network trained on generated captcha gave an accuracy on real captcha about 10%, accuracy - what percentage of captcha was recognized correctly. Captcha is considered recognized if all the characters in it are recognized correctly. In any case, this experiment showed that the method is working, and it is necessary to increase the recognition accuracy.

Training on a real dataset

For manual markup of a real captcha dataset, a script was written in Matlab with a graphical interface:



Here you can arrange circles and move the mouse. The circle marks the center of the symbol. Manual marking took 5-15 hours, however there are services where manually set datasets for a small fee. However, as it turned out, Amazon Mechanical Turkdoes not work with Russian customers. Placed an order for the markup of the dataset on the famous freelance website. Unfortunately, the quality of the markup was not ideal, I corrected the markup myself. In addition, the search for a performer takes time (1 week) and it also seemed expensive: $ 30 for 560 tagged captchas. I refused this method, as a result I came up with the use of CAPTCHA manual recognition sites, where the lowest cost is 1 dollar for 2000 CAPTCHAs. But the answer received there is a line. Thus, manual placement of centers could not be avoided. Moreover, the performers in such services make mistakes or even act in bad faith by printing an arbitrary line in the response. As a result, I had to check and correct errors.

Deeper network

Obviously, the recognition accuracy was insufficient, so the question arose of selecting an architecture. I was interested in the question “does one pixel” in the output image “see” the entire character in the input image:



Thus, we consider one pixel in the output image, and there is a question: what pixel values ​​in the input image affect the values ​​of this pixel? I reasoned this way: if the pixel does not see the whole character, then not all information about the character is used and accuracy is worse. To determine the size of this scope (we will call it that), I conducted the following experiment: I set all the weights of the convolutional layers to 0.01 and the displacements to 0, an image is sent to the network input in which the values ​​of all pixels are 0 except for the central one. As a result, a spot appears at the output of the network:


The shape of this spot is close to the shape of a Gaussian function. The shape of the resulting spot raises the question, why is the spot round, while the convolutional kernels in the convolutional layers are square? (The network used 3x3 and 5x5 convolution kernels). My explanation is this: it looks like a central limit theorem . In it, as here, there is a desire for a Gaussian distribution. The central limit theorem states that for random variables, even with different distributions, the distribution of their sum is equal to the convolution of the distributions. Thus, if we collapse any signal by ourselves many times, then, according to the central limit theorem, the result tends to a Gaussian function, and the width of the Gaussian function grows as the root of the number of convolutions (layers). If for the same network with constant weights we see where the pixel values ​​in the output image are greater than zero, we get a square area (see the figure below), the size of this area is proportional to the sum of the convolution sizes in the convolutional layers of the network.


I used to think that due to the associative property of convolutiontwo consecutive 3x3 convolutions are equivalent to 5x5 convolution, and therefore, if you collapse 2 3x3 cores, you get one 5x5 core. However, then he came to the conclusion that this is not equivalent if only because two convolutions have 3x3 9 * 2 = 18 parameters, and one 5x5 has 25 parameters, so the 5x5 convolution has more degrees of freedom. As a result, at the output of the network, a Gaussian function is obtained with a width less than the sum of the sizes of the convolution in the layers. Here I answered the question which pixels at the output are affected by a single pixel at the input. Although initially the question was posed the opposite. But both questions are equivalent, which can be understood from the figure:


In the figure, you can imagine that this is a view of the images from the side or that our image height is 1. Each of the pixels A and B has its own influence zone on the output image (marked in blue): for A it is DC, for B it is CE , the values ​​of pixels C are affected by the values ​​of pixels A and B and the values ​​of all pixels between A and B. The distances are: AB = DC = CE (taking into account scaling: there are pulling layers in the network, so the input and output images have different resolutions). As a result, the following algorithm is obtained for finding the size of the scope:

1. we set constant weights in convolutional layers, weights-offsets we set values ​​0
2. input images with one nonzero pixel
3. we get the spot size at the exit
4. we multiply this size by a coefficient that takes into account different resolutions of the input and output layers (for example, if we have 2 poolings in the network, then the output resolution is 4 times less than the input, then this size must be multiplied by 4).

In order to see what signs the network uses, I conducted the following experiment: we upload a captcha image to the trained network, we get images with marked symbol centers at the output, we select some detected symbol from them, we leave only the card that matches the one under consideration on the map images of centers symbol. We remember such an output of the network as , then by gradient descent we minimize the function:



Here is the input image of the network, are the output images of the network, is some constant that is selected experimentally ( ). With this minimization, the input and output of the network are considered variables, and the network weights are constant. The initial value of the variablethis captcha image is the starting point for the optimization of the gradient descent algorithm. With this minimization, we reduce the pixel values ​​at the image input, while restraining the pixel values ​​on the output image, as a result of optimization, only those pixels that the network uses in character recognition remain on the input image.
What happened:
For the “2”

symbol : For the “5”

symbol : For the “L”

symbol : For the “u” symbol:

The images on the left are the original captcha images, the images on the right are the optimized image. The square on the images indicates the visibility region output> 0, the circles in the figure are the level lines of the Gaussian function of the visibility region. Small circle - level 35% of the maximum value, large circle - level 3%. Examples show that the network sees within its scope. However, the “u” symbol has an out-of-scope behavior; this is possibly a partial false response to the “n” symbol.

Many experiments with network architecture were carried out, the deeper and wider the network, the more complex captcha it can recognize, the most universal architecture turned out to be the following:

In blue, on top of the arrows, the number of images (feature maps) is shown. c - convolutional layer, p - max-pooling layer, the sizes of the cores are shown in green below. In convolutional layers, 3x3 and 5x5 kernels are used without strade, the pulling layer has a 2x2 patch. After each convolutional layer there is a ReLU layer (not shown in the figure). One image is input, the output is 24 (the number of characters in the alphabet). In convolutional layers, padding is selected so that at the output of the layer the image size is the same as at the input. Padding adds zeros, but this does not affect the network in any way, because the value of the background captcha pixel is 0, since a negative image is always taken (white letters on a black background). Padding only slightly slows down the network. Since there are 2 pulling layers in the network,

Enhancements

The transition from SGD solver to ADAM solver gave a noticeable acceleration of training, and the final quality became better. ADAM solver imported from lasagne moduleand used inside theano-code, the learning rate parameter set to 0.0005, the regularization of L2 was added through the gradient. It was noticed that the result is different from training to training. I explain it this way: the gradient descent algorithm gets stuck in an insufficiently optimal local minimum. I partially overcame it as follows: I started the training several times and chose some of the best results, then I continued to train them for several more eras, after which I chose one best result and already this only best result trained for a long time. Thus, it was possible to avoid getting stuck in insufficiently optimal local minima and the final value of the error function (loss) turned out to be quite small. The figure shows a graph - the evolution of the value of the error function:

The x axis is the number of epochs, the y axis is the value of the error function. Different colors show different workouts. The training procedure is approximately the following:

1) we start 20 workouts over 10 eras
2) select the 10 best results (by the lowest loss value) and train them for another 100 eras
3) select one best result and continue to train it for another 1,500 eras.

It takes about 12 hours. Of course, in order to save memory, these trainings were carried out sequentially, for example, in point 2) 10 trainings were carried out sequentially one after another, for this I modified the Lasam ADAM solver in order to be able to save and load the solver state into variables.

Dividing the dataset into 3 parts made it possible to track network retraining:

Part 1: training dataset - the initial one, on which the network is trained;
part 2: test dataset, on which the network is tested during the training;
part 3: the delayed dataset, the quality of training after training is checked on it

Datasets 2 and 3 are small, in my case there were 160 captchas in each, also dataset 2 determines the optimal response threshold, the threshold that is set on the output image. If the pixel value exceeds the threshold, then the corresponding symbol is found in this place. Typically, the optimum threshold value is in the range 0.3 - 0.5. If the accuracy on the test dataset is significantly lower than the accuracy on the training dataset, this means that retraining has occurred and the training dataset needs to be increased. If these accuracy are approximately the same, but not high, then the architecture of the neural network needs to be complicated, and the training dataset should be increased. There are two ways to complicate the network architecture: increase the depth or increase the width.

Image pre-processing also increased recognition accuracy. An example of preprocessing:

In this case, the least squares method is used to find the middle line of the rotated line, rotate and scale it, and scale it by the average height of the line. Service Hotmail often makes a variety of distortions:

These distortions must be compensated.

Bad ideas

It is always interesting to read about the failures of others, I will describe them here.

There was a problem with a small dataset: for high-quality recognition, a large dataset was required, which was required to be manually marked (1000 captchas). I have made various attempts to somehow train the network qualitatively on a small dataset. I tried to train the network on the results of recognition of another network. at the same time, he selected only those captcha and those places of images in which the network was sure. Confidence was determined by the value of the pixel in the output image. Thus, you can increase the dataset. However, the idea did not work, after several iterations of training, the recognition quality deteriorated greatly: the network did not recognize some characters, confused them, that is, recognition errors accumulated.

Another attempt to learn on a small dataset is to use Siamese networks, the Siamese network on the input requires a couple of captchas, if we have a dataset of N captchas, then the pair will be N ² , we get much more training examples. The network converts captcha to a vector map. I chose the scalar product as a metric of similarity of vectors. It was assumed that the Siamese network will work as follows. The network compares part of the image on the captcha with some reference image of the symbol, if the network sees that the symbol is the same, taking into account distortion, then it is considered that there is a corresponding symbol in this place. The Siamese network trained with difficulty, often stuck in a sub-optimal local minimum, the accuracy was noticeably lower than the accuracy of a regular network. Perhaps the problem was in the wrong choice of the metric of similarity of vectors.

It was also an idea to use an auto-encoder to pre-train the bottom of the network (the one closest to the entrance) to speed up learning. An auto encoder is a network that learns to produce the same output as the input image, while a narrow section is organized in the architecture of the auto encoder. Coaching an encoder is training without a teacher.

Example of auto-encoder operation:

The first image is input, the second is output.
From the trained auto-encoder, they take the lower part of the network, add new untrained layers, all this is trained for the required task. In my case, the use of an auto encoder did not speed up the training of the network.

There was also an example of a captcha that used color:



On this CAPTCHA, the described method with a full-convolutional neural network did not give a result, it did not appear even after various image preprocessors increasing the contrast. I suppose that full-convolutional networks do poorly with non-contrast images. Nevertheless, this captcha was recognized by an ordinary convolutional network with a fully connected layer, an accuracy of about 50% was obtained, the coordinates of the characters were determined using a special heuristic algorithm.

Result

Examples	Accuracy	Comment
	42%	Captcha Microsoft , jpg
	61%
	63%
	93%	captcha mail.ru , 500x200, jpg
	87%	captcha mail.ru , 300x100, jpg
	65%	Captcha Yandex , the Russian words, gif
	70%	CAPTCHA Steam , PNG
	82%	captcha world of tanks , numbers, png

What else could be improved

It would be possible to automatically mark the centers of the characters. Manual captcha recognition services give out only recognized lines, so automatic marking of centers would help to fully automate the marking of a training dataset. The idea is this: to select only those captcha in which each symbol occurs once, to train a separate ordinary convolutional network for each symbol, such a network will only answer the question: is there a symbol in this captcha or not? Then see what signs the network uses, using the method of minimizing the pixel values ​​of the input image (described above). The obtained signs will allow to localize the symbol, then we train the full-convolution network on the received symbol centers.

conclusions

Text captchas are recognized by a full-convolutional neural network in most cases. Probably the time has come to abandon text captcha. Google has not used text captcha for a long time, instead of text, pictures with various objects that a person needs to recognize are offered:

However, such a task seems to be solved for the convolution network. It can be assumed that in the future there will be centers for registering people, for example, a person will interview a person on Skype, check passport scans and the like, then a person will be given a digital signature with which he can automatically register on any site.
© Maxim Vedenev