2.1.

Preprocessing

After each image located, preprocessing is executed. The segmentation is based on the image after binarization and denoising, which converts to binary an input image having pixels defining text and background, each of its pixels is either dark or white¹⁸. Proper binarization is very important for separating the foreground object from the background for images¹⁹[19]. The foreground is with digital, character or other valid information, and the background without it. Once the foreground is separated from the background, the image can be distinguished by recognizing the shape of each foreground image one by one, such as handwritten characters and CAPTCHAs after preprocessing.

2.2.

Building standard library

All training images were annotated in advance before building standard library. There are 2 different methods when judging whether any character of each training image is to add into the standard library. One method is without any limits, i.e., the standard library contains all characters of training images, which size is always big and equal to the number of training characters. The other one is to set a maximum threshold (MXT_S), only characters are added when the similarity value between it and other existing items in standard library is less than the threshold, and the size of standard library is always smaller and depends on the threshold value, as shown in Figure 2. Generally, the bigger the threshold is set, the bigger the size of standard library, and the higher the accuracy. The method one could be seen as a special case of the method two since it means no limits when the threshold is set to 1. The framework uses the threshold configured in a configuration file or database.

Figure 2.

Design of Building Standard Library.

There are some popular algorithms of the similarity, such as Person Correlation Coefficient, Cosine Similarity²⁰, Jaccard Similarity²¹, etc. The bit-based similarity model the framework used is similar to cosine similarity. The image data after preprocessing are stored in the memory in binary form, 0 for white and 1 for black, or vice versa. Two images are same when each individual pixel is same in the same position, and they are similar when most pixels are same, only few are different. Given 2 images A and B, P(A) and P(B) represent the binary matrix of A and B, respectively. The result of bitwise-or between P(A) and P(B) indicates the largest range of foreground like union set of P(A) and P(B), and the result of bitwise-and between P(A) and P(B) indicates same range of foreground area like intersection of P(A) and P(B). The smaller the difference between both results, the bigger the similarity. The bit-based similarity model defines the similarity by dividing the number of same foreground area of P(A) and P(B) into the number of the largest range of foreground area of P(A) and P(B), i.e., dividing the bitwise-or result by bitwise-and result, as showed in equation (1). The higher the similarity value is, the closer these 2 images or characters are. Hence the similarity is some number between 0 and 1, S(A, A) = 1, in another words, A resembles itself 100%, for any size²¹.

2.3.

Image recognition

The k-NN algorithm is used to predict which category each target sample belongs to by a majority of k neighbor standard samples closest to the target. The bit-based similarity model is used and k is configured which can be changed in different scenarios. Once k is set, as candidates, the top k standard items ranked in order of similarity are cached during recognition. Standard items are compared to the target, one item a time, until a match with the similarity higher than a threshold value of “direct recognition” or no more items required to match. Among the top k standard items, the final value is determined by the majority of candidate character values. If more than one candidate character values are tied for the same majority, the value with a higher similarity is the final result. Therefore, the final result is not always with the highest similarity when k is greater than 1.

The k-NN algorithm has the advantage of being easy and practical, and with a suitable accuracy²⁰. There are some algorithms, such as CNN (Condensed Nearest Neighbor), ball-tree, kd-tree (k-dimensional tree), LSH (Locally Sensitive Hash) etc., to reduce storage space or improve the speed of locating k nearest neighbors^{20, 22, 23}. In the framework, the byte array is used for reduction of storage space consumption. Each pixel of the image data after preprocessing is indicates in binary form such as 0 and 1 for white and black separately and 8 pixels are grouped within a byte. The image data is stored in a byte array. As shown in Table 1, it lists a binary array for a six after preprocessing, which is stored as an array of byte with length 40. It needs about 7 times more storage space if each one or zero is used directly in the application since a byte is a basic unit.

Table 1.

Array for a six after preprocessing.

Besides, one more feature is designed for quick locating associated standard items, such as foreground area percentage. There are many items with small similarity value wasting time if all of items within standard library are required to be matched per recognizing a character. In order to locate the standard item with high similarity value as quick as possible, a new feature, the foreground area, is used in the framework. That is to say, on executing each recognition, items in standard library are grouped by the foreground area, as a result, different group has different priority to match, and some with low priority are skipped. Let key as the feature value, shown in equation (2), where s_i is the foreground area of item i, and f is a customized function. A proper function makes a good balance between the number of groups and the coverage percentage of characters to recognize per group. In general, the less the number of groups is, more number of items each group contains, more coverage percentage of characters each group has.

A linear function is proposed, such as shown in equation (3), where a is a coefficient between 0 and 1, such as 0.1. Given that S is the total area including foreground and background area, the domain of the function is an open range as shown in equation (4), while the range is a close range as shown in equation (5).

For some character to be recognized, it is easy to get the feature value of key according to equation (3). Once the key is calculated, the priority of all items in group key is the highest, and the priority value goes down in the direction of distance between group number and key. The priority value can be calculated according to equation (6), where gn_i is the group number of standard item i, key is the feature value of a character to be recognized, and MAX is the maximum that is greater or equal than the total number of groups.

There are 2 threshold values called MXT_E, and MXN_E in the framework. When the maximum similarity is less than MXT_E and the number of different priorities matched is less than MXN_E, more groups with next priority are involved, otherwise, the recognition stops. The image result returns when all characters are recognized, as shown in Figure 3.

Figure 3.

Design of character recognition.

3.1.

API

There are 3 main interfaces and associated classes in the framework, as shown in Figure 4.

Figure 4.

Three main classes of framework.

3.2.

Configuration values

According to the design, some common parameters are to configure in advance, as shown in Table 2.

Table 2.

Some configuration values.

Additionally, all of the possible values need being pre-configured, such as cnki, there are 27 candidates in total, as shown in Table 3. The number or index can be retrieved according to the expected or tagged character in pre-computed hash tables, and vice reverse.

Table 3.

Relationship between sequence number and char.

3.3.

Application scenarios

The framework was applied for 4 scenarios, MNIST handwriting database, CAPTCHAs built by the captcha generator, online CAPTCHAs of CNKI website, and CAPTCHAs within open source PHP DedeCMS.

On making the standard set or recognition, preprocessing is the first step, e.g., the image “E93D” was converted to 4 individual images “E”, “9”, “3” and “D”, and then the next step is locating the position of hash tables according to Table 3. With the hash tables, it is quick to locate associated group according to the tagged value, as shown in Figure 5. Table 4 lists test results for all these 4 scenarios. It is seen that the framework work well for different scenarios with the accuracy 97.05% on average. Generally, the accuracy differs a little according to the parameters configured. Take the CMS scenario as an example, the accuracy differs according to different knn and MXT_E, as shown in Figure 6.

Figure 5.

Preprocessing and locating standard items.

Figure 6.

Relationships between accuracy and MXT_E.

Table 4.

Test results for 4 different scenarios.