JP7365697B2 - Program and clustering device - Google Patents

Description

Article 30, Paragraph 2 of the Patent Act applies Date of publication: December 24, 2020, Address of publication: https://www. sciencedirect. com/science/article/abs/pii/S0167865519303782? CMX_ID=&SIS_ID=0&dgcid=STMJ_75273_AUTH_SERV_PPUB&utm_acid=15760823&utm_campaign=STMJ_75273_AUTH_SERV_PPUB&utm_dgroup=Emai l1Publishing&utm_in=DM637240&utm_medium=email&utm_source=AC_30&utm_term=Email%201%20Publishing_TLSH

The present invention relates to a program and a clustering device.

In order to develop and measure the thinking ability of test takers (answerers), society has begun to recognize the need to impose not only multiple-choice questions but also written questions. When assigning short-answer questions, it is necessary to score highly reliably in a short period of time. Using handwriting recognition technology, it becomes possible to perform scoring support that supports human scoring and automatic scoring. In arithmetic and mathematics, where there is a strong need for written answers, prototype learning systems that employ recognition of handwritten answers have been announced (for example, Non-Patent Documents 1 to 3).

Masato Suzuki et al., “Development of a basic mathematics learning support system based on handwritten formula analysis”, Institute of Electronics, Information and Communication Engineers, IEICE Techniques, ET2009-129, p.147-152 (2010) Satoshi Chiba et al., “Prototype of mathematics e-learning system on tablet PC using handwritten formula recognition”, Information Processing Society of Japan Research Report, Vol. 2014-CE-127, No. 10, p. 1-5 (2014) Wataru Konishi et al., “Arithmetic/mathematics automatic grading system using handwritten formula recognition”, Information Processing Society of Japan Research Report, Computer and Education Research Group Report, 2016-CE-133(7), 1-7 (2016)

When grading is done by humans, if answers are randomly presented to the grader, the scores often fluctuate. In large-scale exams, multiple people score the test, and if the difference in scores exceeds a certain level, a third party must score the test, which increases the cost and time of using a third party. On the other hand, automatic scoring requires an environment in which test takers can check their scoring results and point out scoring errors, but even with this as a premise, only items with high recognition confidence will be automatically scored, and test takers with low confidence will only be automatically scored. A realistic method would be to discard the items and have them scored by humans. Therefore, regardless of whether grading is supported or automatic grading is used, it is important to suppress variations in grading between graders.

The present invention has been made in view of the above-mentioned problems, and its purpose is to provide a program and clustering system that can improve scoring efficiency by reducing scoring errors and variations in scoring by scorers. The goal is to provide equipment.

(1) The present invention is a program for classifying a plurality of handwritten patterns input by hand, which reduces an image of one handwritten pattern into at least one stage, and compares the original image before reduction with at least one a scale image generation unit that generates a plurality of scale images including a reduced image; and a scale image generation unit that generates a plurality of scale images including a reduced image; a feature extraction unit that extracts a symbol position feature regarding the appearance position of the symbol; a feature vector generation unit that generates a feature vector by determining the probability of occurrence; and a feature vector generation unit that generates an integrated feature vector by taking the maximum value of the probability of occurrence of the same symbol at the same location of the feature vectors generated from each of the plurality of scale images. The present invention relates to a program that causes a computer to function as a classification unit that classifies a plurality of handwritten patterns into a plurality of groups based on a combination unit and the integrated feature vector generated from each of the plurality of images of the handwritten patterns. . The present invention also relates to a computer-readable information storage medium that stores a program for causing a computer to function as each of the above sections. Further, the present invention relates to a clustering device including the above-mentioned parts.

According to the present invention, classes (types) and positions of symbols of different sizes can be extracted by providing each of a plurality of scale images to a learning model and extracting symbol position features for each of the plurality of scale images. Can be done. In addition, by performing multiple types of partitioning on symbol position features and generating feature vectors by determining the appearance probability of each type of symbol for each partition obtained by each of the multiple types of partitioning, we can Symbols can be detected regardless of the magnitude of positional deviation. Furthermore, by performing multiple types of segmentation on each of the symbol position features extracted from each of the multiple scale images and generating feature vectors, the size of the position features can be made uniform and integrated. By classifying multiple handwritten patterns into multiple groups based on the integrated feature vector obtained by integrating the feature vectors generated from each of multiple scale images, it is possible to accurately group handwritten patterns into groups that are similar (clustering). ), it is possible to reduce grading errors and variations in grading by the grader, and improve grading efficiency.

(2) Furthermore, in the program, information storage medium, and clustering device according to the present invention, each of the plurality of scale images is given to the learning model, a feature map is obtained for each of the plurality of scale images, and the feature map is A vector obtained by multiplying the symbol position feature obtained by inputting it to the discriminator and the feature map and averaging the result is input to the discriminator to generate a first occurrence probability vector indicating the probability of occurrence for each type of symbol. , a first integrated appearance probability vector is generated by taking the maximum value of the appearance probability of the same symbol at the same location of the first appearance probability vector generated from each of the plurality of scale images; The computer may further function as a learning section that causes the learning model to learn based on teacher data indicating whether each type of symbol appears (or may further include a learning section).

According to the present invention, a learning model is trained using a first appearance probability vector generated from a vector obtained by multiplying a symbol position feature obtained by inputting a feature map to a discriminator and a feature map. It is possible to learn by weighting the appearance of symbols that should occur, and the learning model can be learned appropriately.

(3) Furthermore, in the program, information storage medium, and clustering device according to the present invention, the learning unit provides each of the plurality of scale images to the learning model and obtains a feature map for each of the plurality of scale images. , a vector with the maximum value of the feature map is input to the discriminator to generate a second appearance probability vector indicating the appearance probability for each type of symbol, and the second appearance probability vector generated from each of the plurality of scale images is A second integrated appearance probability vector is generated by taking the maximum value of the appearance probability of the same symbol at the same location of the appearance probability vector, and a third integration is performed by averaging the first integrated appearance probability vector and the second integrated appearance probability vector. An appearance probability vector may be generated, and the learning model may be trained based on the third integrated appearance probability vector and the teacher data.

According to the present invention, the learning model can be learned more appropriately by learning the learning model using the second appearance probability vector and the first appearance probability vector generated from the vector that takes the maximum value of the feature map. Can be done.

The figure which shows an example of the functional block diagram of the clustering apparatus of this embodiment. The figure which shows the flow of the process which produces|generates an integrated feature vector from a handwritten mathematical formula pattern image. The figure which shows an example of the structure of a deep convolutional neural network and a classifier. A diagram schematically showing symbol position characteristics. FIG. 2 is a diagram schematically showing an example of hierarchical spatial pooling. The figure which shows the flow of learning processing. The figure which shows the flow of processing of global attention pooling. FIG. 3 is a diagram in which symbol position features extracted from the handwritten mathematical formula pattern image are superimposed on the handwritten mathematical formula pattern image.

This embodiment will be described below. Note that this embodiment described below does not unduly limit the content of the present invention described in the claims. Furthermore, not all of the configurations described in this embodiment are essential components of the present invention.

1. Configuration FIG. 1 shows an example of a functional block diagram of a clustering device according to this embodiment. Note that the clustering device of this embodiment may have a configuration in which some of the components (each part) in FIG. 1 are omitted.

The input unit 160 is for inputting a handwritten mathematical pattern (an example of a handwritten pattern) written on paper, etc., and its function is an optical reader that reads the handwritten mathematical pattern as an image (black and white image or grayscale image). (scanner, camera, etc.).

The storage section 170 stores programs and various data for making the computer function as each section of the processing section 100, and also functions as a work area for the processing section 100, and its functions can be realized by a hard disk, a RAM, or the like.

The display unit 190 outputs the image generated by the processing unit 100, and its function can be realized by a display such as a touch panel, LCD, or CRT, which also functions as the input unit 160.

The processing unit 100 (processor) performs processing such as classification (clustering) processing, learning processing, and display control based on data (image data) and programs from the input unit 160. This processing section 100 performs various processes using the main storage section within the storage section 170 as a work area. The functions of the processing unit 100 can be realized by hardware such as various processors (CPU, DSP, etc.), ASIC (gate array, etc.), and programs. The processing unit 100 includes a scale image generation unit 110, a feature extraction unit 111, a feature vector generation unit 112, an integration unit 113, a classification unit 114, a display control unit 115, and a learning unit 116.

The scale image generation unit 110 reduces one handwritten mathematical formula pattern image to at least one stage, and generates a plurality of scale images including an original image before reduction and at least one reduced image.

The feature extraction unit 111 supplies each of the plurality of scale images to a learning model using a convolutional neural network, and extracts symbol position features regarding the appearance position of each type of symbol for each of the plurality of scale images. Symbols are elements that make up a mathematical formula, and specifically include numbers, letters (English letters, Greek letters), and operators (arithmetic operators, logical operators, set operators, and relational operators) that appear in a mathematical formula. child), symbols (addition symbol, operation symbol, multiplication symbol,
These are integral symbols, limit symbols (lim), special symbols (such as ∞), functions (log, sin, cos, tan, etc.), and parentheses (large, medium, small).

The feature vector generation unit 112 performs multiple types of partitioning on the symbol position feature, calculates the appearance probability for each type of symbol for each partition obtained by each of the plurality of types of partitioning, and generates a feature vector. do. Note that multiple types of partitioning are partitioning in which the values of n and/or m in n×m partitioning are different.

The integrating unit 113 generates an integrated feature vector by taking the maximum value of the probability of appearance of the same symbol at the same location in the feature vectors generated from each of the plurality of scale images.

The classification unit 114 classifies the plurality of handwritten mathematical formula patterns into a plurality of groups based on the integrated feature vector generated from each of the plurality of handwritten mathematical formula pattern images.

The display control unit 115 controls the display unit 190 to display a plurality of handwritten mathematical formula patterns classified into a plurality of groups by the classification unit 114 for each group.

The learning unit 116 provides each of a plurality of scale images (scale images for learning) to the learning model, obtains a feature map for each of the plurality of scale images, and inputs the feature map to a discriminator. A vector obtained by multiplying the symbol position feature and the feature map and averaging the result is input to the discriminator to generate a first appearance probability vector indicating the appearance probability for each type of symbol, which is generated from each of the plurality of scale images. A first integrated appearance probability vector is generated by taking the maximum value of the appearance probability of the same symbol at the same location in the first appearance probability vector, and training data indicating the presence or absence of the appearance of each type of symbol with the first integrated appearance probability vector. The learning model is trained based on the following. Further, the learning unit 116 provides each of the plurality of scale images to the learning model, obtains a feature map for each of the plurality of scale images, inputs a vector having the maximum value of the feature map to the discriminator, and then A second appearance probability vector indicating the appearance probability for each type is generated, and a second integration is performed by taking the maximum value of the appearance probability of the same symbol at the same location of the second appearance probability vector generated from each of the plurality of scale images. Generate an appearance probability vector, generate a third integrated appearance probability vector by averaging (integrating) the first integrated appearance probability vector and the second integrated appearance probability vector, and based on the third integrated appearance probability vector and the training data. The learning model may be trained by

2. Technique of this Embodiment FIG. 2 is a diagram showing the flow of processing for generating an integrated feature vector from an input image of a handwritten mathematical formula pattern (handwritten mathematical formula pattern image).

First, one handwritten mathematical formula pattern image (handwritten mathematical formula pattern image to be clustered) is reduced to at least one stage to generate a plurality of scaled images including an original image before reduction and at least one reduced image. In the example shown in FIG. 1, a reduced image (1/4 image) whose side length is reduced to 1/2 and a reduced image (1/16 image) whose side length is reduced to 1/4 are created from one handwritten mathematical pattern pattern image. ), three scale images (original image, 1/4 image, and 1/16 image) are generated. Note that a reduced image reduced to a smaller scale may be used, or a reduced image reduced to a different scale may be additionally used.

Next, each of the multiple scale images is given to a deep convolutional neural network (Deep CNN) and a classifier (classifier), which are learning models, and the appearance position of each symbol type (class) is determined for each of the multiple scale images. Extract symbol position features (LC features) that are related features. FIG. 3 shows an example of the configuration of a deep convolutional neural network and a discriminator. A deep convolutional neural network (Deep CNN) consists of a convolutional layer CL and a pooling layer PL (maximum pooling layer), and outputs a feature map (CNN feature map). The feature map (feature map group) includes a plurality of feature maps that are two-dimensional arrays of features obtained by applying convolution or pooling to a two-dimensional array input (scale image). The feature map is input to a classifier. Here, the feature maps output from the last two convolutional layers CL are combined and input to the classifier. The classifier consists of a convolutional layer CL and a dropout DO, and outputs symbol position features.

The boxes shown as symbol position features (LC features) in FIG. 2 collectively represent a plurality of planes as shown in FIG. 4. The symbol position feature is represented by multiple planes corresponding to multiple types (classes) of symbols, and each plane indicates the probability of appearance of that class at each position on the input surface (scale image). Depth D (number of planes lined up in the depth direction) indicates the number of classes (#classes), height H indicates the height of the input surface (number of vertical pixels), and width W indicates the width of the input surface (horizontal (number of pixels in the direction).

Next, hierarchical spatial pooling (HSP) is performed on a plurality of symbol position features extracted from each of a plurality of scale images. In hierarchical spatial pooling, multiple types of partitioning are performed on each plane of symbol position features, and the probability of appearance for each symbol type (class) is determined for each partition obtained by each of the multiple types of partitioning. A hierarchical spatial feature vector (HS features, corresponding to the feature vector of the present invention) is generated. FIG. 5 is a diagram schematically showing an example of hierarchical spatial pooling. In this example, three types of partitioning (1x1 partitioning, 3x5 partitioning, and 5x7 partitioning) are applied to each plane of the symbol position feature, and three types of partitioning are applied. From each division, the maximum value of the appearance probability of each class is determined for each division (maximum pooling is performed for each division), and a k-dimensional feature vector is generated for each division. k is the number of classes (#classes), and the k-dimensional feature vector is a vector whose elements are the appearance probabilities of each of k types of symbols. Then, the k-dimensional feature vectors for the number of divided sections are concatenated, and the feature vectors for the number of types of section division are concatenated to generate a hierarchical spatial feature vector. From 1×1 partitioning, a 1×k=k-dimensional feature vector (probability of appearance for each class on the input surface) is obtained, and from 3×5 partitioning, a 3×5×k=15k-dimensional feature vector is obtained. (the appearance probability of each class in each section when the input surface is divided into 3 x 5 sections) is obtained, and from the 5 x 7 section division, a 5 x 7 x k = 35 k-dimensional feature vector (the input surface is When divided into 5×7 sections, the probability of appearance for each class in each section is obtained, and by connecting these, a hierarchical space feature vector of k+15k+35k=51k dimensions is obtained. The feature vector obtained from 1×1 partitioning does not represent position information because each plane of the symbol position feature is not divided, but the feature vector obtained from other partitioning does express position information. Note that any one of the above three types of partitioning may be excluded, or another type of partitioning may be added.

Next, the maximum value of the appearance probability of the same symbol (same class) at the same location of the hierarchical spatial feature vector generated from each of the multiple scale images is taken (maximum aggregation (MA) is performed) to integrate the feature. Generate a vector (multi-scale hierarchical spatial feature vector, MHS features). In the example shown in FIG. 2, three hierarchical spatial feature vectors generated from each of the original image, 1/4 image, and 1/16 image are integrated to generate an integrated feature vector.

In clustering handwritten mathematical equation patterns, first, the degree of similarity between handwritten mathematical equation patterns (distance between integrated feature vectors) is determined based on integrated feature vectors generated from each of a plurality of handwritten mathematical equation pattern images. For example, a cosine distance function can be used as a function for determining the distance between integrated feature vectors. Then, the distance between the integrated feature vectors of the two handwritten mathematical formula pattern images is determined for all combinations of handwritten mathematical formula patterns to be clustered, and clustering is performed for each similar handwritten mathematical formula pattern. For clustering, methods such as the K-means++ method can be used.

In mathematical equations, symbols change size depending on their role. For example, subscripts and superscripts are smaller than baseline symbols. In the example shown in FIG. 3, "x"s of different sizes appear in the handwritten mathematical formula pattern image. This makes it difficult to detect symbols in mathematical expressions. In the method of this embodiment, each of a plurality of scale images is fed to one deep convolutional neural network (Deep CNN), and symbol position features (LC features) are extracted for each of the plurality of scale images. It is possible to extract classes and positions of different symbols. This is because scale images of any scale are suitable for extracting the class and position of a certain symbol. In other words, a small-scale image is suitable for extracting the class and position of a symbol that is written in a large scale, and a large-scale image (such as the original image) is suitable for extracting the class and position of a symbol that is written in a small scale. suitable for

Furthermore, in mathematical expression recognition, the positional relationship of symbols is important. For example, recognizing parentheses and fractional rules requires not only the shape of the symbol but also the context of the surrounding symbols. Therefore, in the method of this embodiment, in order to obtain not only information about the symbol but also information about its vicinity, in a deep convolutional neural network, the feature maps output from the last two convolutional layers CL are combined and input to the discriminator. .

In addition, in the method of this embodiment, the symbol position feature is divided into multiple types of partitions, and the probability of appearance for each type of symbol is determined for each partition obtained by each of the plurality of partitions, and the hierarchical spatial feature is By employing processing (hierarchical spatial pooling) that generates vectors (HS features), symbols can be detected regardless of the magnitude of symbol positional deviation. In other words, even if the positional deviation of a symbol is large, it is possible to detect the symbol at its approximate position using the feature vector obtained from partitioning with a small number of partitions. The feature vector obtained from multiple partitions allows the symbol to be detected at a more precise location. Note that in hierarchical spatial pooling, in order to deal with positional shifts of symbols, a Gaussian function centered on the section may be superimposed on the probability of appearance of each symbol in each section.

Furthermore, if the size of the scale image differs, the size of the symbol position feature also differs, but in the method of this embodiment, hierarchical spatial pooling is applied to a plurality of symbol position features extracted from each of a plurality of scale images. This allows features to be unified by making them the same size. Then, by classifying multiple handwritten math patterns into multiple groups based on the integrated feature vector (MHS features) obtained by integrating the hierarchical spatial feature vectors generated from each of the multiple scale images, the handwritten math patterns can be classified into similar groups. It is possible to cluster each item with high accuracy, reduce scoring errors by scorers and variations in scoring, and improve scoring efficiency.

Next, learning of a deep convolutional neural network (learning model) will be explained. FIG. 6 is a diagram showing the flow of learning processing. During learning, an appearance probability vector indicating the appearance probability of each type of symbol is extracted by global attention pooling (GAtP) without using symbol position information.

First, as in the case of clustering, one handwritten mathematical formula pattern image (handwritten mathematical formula pattern image for learning) is reduced to at least one stage to create multiple scaled images including the original image before reduction and at least one reduced image. generate. Next, each of the plurality of scale images is applied to a deep convolutional neural network (Deep CNN) to obtain a feature map (CNN feature map) output from the last two convolutional layers CL. The depth (D) of the box shown as a feature map indicates the number (#features) of features included in the feature map (feature maps included in the feature map group).

Next, global attention pooling (GAtP) is performed on the feature map. In this process, features are extracted from all positions where a certain symbol appears, but weights are given to the appearance of noteworthy classes. FIG. 7 is a diagram showing the flow of global attention pooling processing. First, the feature map (F) is input to a classifier to obtain symbol position features (M _i , i=1..k). k is the number of classes (#classes). Next, for each symbol, the feature map (F) is multiplied by the symbol position feature to obtain k class attention feature maps (F×M ₁ to F×M _k ). If the symbol position feature (probability of appearance of class c at each position on the input surface) of class c (c-th class) is M _c , then the feature map (F) is multiplied by the symbol position feature (M _c ). , obtain a class attention feature map (F×M _c ). The class attention feature map (F×M _c ) is a feature map in which the appearance of class c is weighted. Next, for each of the class attention feature maps (F×M ₁ to F×M _k ), the values of height H and width W are averaged (averaged for each feature), and the class attention vector (Att _F1 ~ _AttFk ). A class attention vector (Att _Fc ), which is obtained by multiplying the feature map (F) by the symbol position feature (M _c ) and averaging the results, can be obtained using the following equation (1).

ここで、ｘ，ｙは、特徴マップ（Ｆ）やシンボル位置特徴（Ｍ_ｃ）の高さＨと幅Ｗの次元を示す。

Here, x and y indicate the dimensions of the height H and width W of the feature map (F) and symbol position feature (M _c ).

Next, the vectors (f(Att _F1 ) to f(Att _Fk )) obtained by inputting each of the class attention vectors (Att _F1 to Att _Fk ) to a classifier are diagonalized. , a first appearance probability vector (vector y whose elements are y ₁ to y _k ) indicating the appearance probability for each class is determined. The c-th element of the vector (f(Att _Fc )), y _c (probability of appearance of class c), can be determined by the following equation (2).

ここで、ｕ_ｃは、クラスｃのOne-hotベクトル（ｃ番目の要素だけ１で他の要素が０で
あるベクトル）であり、＜ａ,ｂ＞は、ベクトルａとベクトルｂの内積演算を示す。

Here, u _c is a one-hot vector of class c (a vector in which only the c-th element is 1 and the other elements are 0), and <a, b> is the inner product operation of vector a and vector b. show.

Next, as shown in FIG. 6, maximum aggregation (MA) is performed by taking the maximum value of the probability of occurrence of the same symbol at the same location in the first occurrence probability vector (y) generated from each of the multiple scale images. ) A first integrated appearance probability vector (My) is generated.

Next, a learning model (deep Convolutional neural network). Figure 6
In the example shown in , the symbols "a", "b", "2", "+", and "frac" appear in the handwritten formula pattern for learning, so the occurrences of these classes are used as training data. A vector is prepared in which the probability is "1" and the appearance probability of other classes is "0".

Note that global attention pooling (GAtP) may take a long time to converge, or may not converge in the worst case, if no prior learning is performed. Furthermore, there is a possibility that a certain probability will be given for a class that does not exist in the handwritten mathematical formula pattern image. Therefore, in order to solve this problem, the appearance probability (second appearance probability vector) for each class is determined by global maximum pooling (GMP), and the second appearance probability vector is generated from each of the plurality of scale images. A second integrated appearance probability vector is generated by taking the maximum value of the appearance probability of the same symbol at the same location, and the second integrated appearance probability vector and the first integrated appearance probability vector (My) are integrated (averaged). A third integrated appearance probability vector may be generated, and the learning model may be trained based on the third integrated appearance probability vector and the teacher data. In global maximum pooling, a d (depth, #features)-dimensional vector of equation (3) is obtained by taking the maximum value for x and y for each feature of the feature map (F).

このベクトルを識別器（Classifier）に入力して第２出現確率ベクトルを求める。この処理では、それぞれのクラスに対して、最もそれらしいものの位置からその特徴を抽出する。第１統合出現確率ベクトルと第２統合出現確率ベクトルの統合により、深層畳み込みニューラルネットワークは、大域注目プーリングと大域最大プーリングのそれぞれの損失関数の両方を低減する方向で学習を進める。学習の初期段階では、大域最大プーリングの利点を活用して学習が進み、それが進行した段階では、大域注目プーリングの機能が発揮される。

This vector is input to a classifier to obtain a second appearance probability vector. In this process, the features of each class are extracted from the most likely position. By integrating the first integrated appearance probability vector and the second integrated appearance probability vector, the deep convolutional neural network advances learning in the direction of reducing both the loss functions of global attention pooling and global maximum pooling. At the initial stage of learning, learning progresses by taking advantage of global maximum pooling, and at an advanced stage, the function of global attention pooling is demonstrated.

3. Evaluation Experiment An experiment was conducted to evaluate the clustering method (and learning method) of this embodiment. Purity shown in the following equation (4) was used as an evaluation index for clustering. Considering that each cluster is scored, it is better for the purity to be close to 1.

ここで、Ｋは、クラスタの数であり、Ｊは、実際のクラスの数であり、Ｈは、サンプルの数であり、Ｇ＝｛ｇ_１，ｇ_２，…，ｇ_Ｋ｝は、結果のクラスタであり、Ｃ＝｛ｃ_１，ｃ_２，…，ｃ_Ｊ｝は、実際のクラスである。

Here, K is the number of clusters, J is the actual number of classes, H is the number of samples, and G={g ₁ , g ₂ , ..., g _K } is the result cluster, and C={c ₁ , c ₂ , . . . , c _J } is the actual class.

In this experiment, we used the CROHME 2016 dataset (H. Mouchere, C. Viard-Gaudin, R. Zanibbi, U. Garain, ICFHR2016 CROHME: Competition on Recognition of Online Handwritten Mathematical Expressions, in: 2016 15th Int) as a sample of handwritten mathematical expression pattern images. Conf. Front. Handwrit. Recognit., IEEE, 2016: pp. 607-612. doi:10.1109/ICFHR.2016.0116.). 101 types of symbols appear in this. Also, this includes 8,
There are 834 training samples, 986 validation samples, and 1,147 test samples.
In this experiment, a test sample is not used, but 620 samples of 36 types of mathematical expressions, which are part of the learning samples, are used as test samples. This is because the original test sample has only one sample per formula. On the other hand, among the 620 samples selected from the training samples, there are 15 to 22 samples per formula. These 620 samples were removed from the original 8,834 training samples, resulting in 8,214 samples used for learning. The verification sample was used as is. Hereinafter, this sample set will be referred to as S-CROHME.

In this experiment, we fixed the aspect ratio of all samples (mathematical formula images) and normalized them to 128 pixels in the vertical direction. As a result, those larger than 800 pixels in the horizontal direction were linearly compressed to 800 pixels in the horizontal direction. Note that those with less than 800 pixels in the horizontal direction were left unchanged. In order to generate images with multiple resolutions (multiple levels of reduced images), average pooling using a 2×2 mask was performed twice. As a result, mathematical formula images (three scale images) of 128 pixels, 64 pixels, and 32 pixels in the vertical direction were generated. In addition. In mathematical formulas, multiple symbols appear, and in order to be able to read them, it is normal for the number of pixels to be 128 pixels in the vertical direction and more than that in the horizontal direction. If the number of pixels is small (for example, 64 pixels), this can be handled by preparing formula images with 64 pixels, 32 pixels, or 16 pixels in the vertical direction, or reducing the number of partitions for partitioning.

Table 1 shows the specific configuration of the deep convolutional neural network used in this experiment. In Table 1, #maps is the number of feature maps, k is the number of kernels (filters), s is the stride size, and p is the padding size. Moreover, ReLU is an activation function.

階層的空間プーリング（ＨＳＰ）では、１×１の区画分割、３×５の区画分割、３×７の区画分割及び５×７の区画分割を行った。また、２つの数式画像の統合特徴ベクトル間
の距離を算出するために、コサイン距離関数を用いた。クラスタリング手法としては、K-means++法を採用した。

Hierarchical spatial pooling (HSP) involved 1×1 partitioning, 3×5 partitioning, 3×7 partitioning, and 5×7 partitioning. Furthermore, a cosine distance function was used to calculate the distance between the integrated feature vectors of two mathematical expression images. The K-means++ method was used as the clustering method.

High purity can be easily obtained by increasing the number of clusters K. For example, if the number of clusters K is equal to the number of samples H, the purity will be 1. However, this is the same as not performing clustering, and the scoring efficiency does not improve. Therefore, the number K of clusters must be about the same as the number of types of mathematical expressions. However, in actual scoring situations, the number of types cannot be known unless accurate mathematical formula recognition is performed. Here, for evaluation, the number of types of formulas known in advance was set as the number of clusters K. That is, S-CROHME was clustered into 36 clusters.

First, hierarchical spatial pooling (
HSP) was evaluated. If no partitioning is performed (only 1x1 partitioning), if a single partitioning (3x5, 3x7, or 5x7 partitioning only), multiple types of partitioning. In each case of compartmental fractionation (hierarchical spatial pooling), S-CROHME test samples were clustered to determine purity. The evaluation results are shown in Table 2.

区画分割を行わない場合の純度０．９２に対して、単一の区画分割を行う場合はいずれの区画分割でも０．９６以上の純度を達成した。また、複数種類の区画分割を行う場合、いずれの区画分割の組み合わせでも、単一の区画分割を行う場合より高い純度を達成した。これは、単一の区画分割を行うより、複数種類の区画分割を行う方が効果的であることを示している。特に、１×１の区画分割と３×５の区画分割の組み合わせで純度０．９９を達成した。

In contrast to the purity of 0.92 when no partitioning was performed, a purity of 0.96 or higher was achieved in any partitioning when a single partitioning was performed. Furthermore, when performing multiple types of partitioning, any combination of partitioning achieved higher purity than when performing a single partitioning. This indicates that performing multiple types of partition division is more effective than performing a single partition division. In particular, a purity of 0.99 was achieved with a combination of 1 x 1 and 3 x 5 partitions.

Next, we evaluated the effects of differences in global pooling. During learning, purity was determined for each of the following cases: Global Average Pooling (GAP), Global Maximum Pooling (GMP), and Integration of Global Attention Pooling and Global Maximum Pooling (GAtP+GMP). The evaluation results are shown in Table 3. Global average pooling is a method that calculates the appearance probability vector by inputting the average value for each feature of the feature map (F) to a classifier. Extract the feature from the appearance position.

区画分割を行う場合、ＧＡｔＰ＋ＧＭＰは、若干ではあるがＧＭＰ単独より良く、ＧＡＰよりは明らかに良い性能を示している。一方、区間分割を行わない（１×１の区間分割を行う）場合、ＧＡＰでは０．２８の純度しか得られない。

When partitioning is performed, GAtP+GMP shows slightly better performance than GMP alone and clearly better than GAP. On the other hand, when no interval division is performed (1×1 interval division is performed), a purity of only 0.28 can be obtained with GAP.

The difference in global pooling appears not only in clustering but also in the average recognition rate of symbols. The average recognition rates of GAtP+GMP, GMP, and GAP were 0.94, 0.93, and 0.17, respectively. The merits of GAtP+GMP could also be confirmed in recognition performance.

FIG. 8 is a diagram in which symbol position features (probability of appearance at each position on the image for each type of symbol) extracted from the handwritten mathematical formula pattern image (scale image) are superimposed on a certain handwritten mathematical formula pattern image (scale image). . The symbol position feature is shown with higher brightness as the probability of appearance of the symbol is higher. The image in the first column on the far left in FIG. 8 is an image obtained by superimposing the symbol position feature extracted from the original image on the original image, and the image in the second column is an image obtained by superimposing symbol position features extracted from the original image on the original image. The image in the third column is an image in which the symbol position features extracted from the 1/16 image are superimposed on the 1/16 image. The image is an image obtained by combining these three images (taking the maximum value at the same position). In addition, each symbol that appears in the formula ("x", "Σ", "P", "n", "j", "i", "a", It shows the probability of appearance at each position of "0", "=", ")", "("), and the image in the 12th row at the bottom is an image that combines these (each of all symbols (probability of appearance at that location). In addition, in FIG. 8, the reduced images (1/4 image, 1/16 image) and their symbol position characteristics are enlarged to the size of the original image and displayed.

From FIG. 8, it can be seen that symbols of different sizes are well processed in any of the three scale images. Small size symbols such as 'x', 'n', 'j', 'a' are detected in the original image, while intermediate size symbols such as '(', ')', '=", 'P' etc. The symbol is detected in a 1/4 image, and the large size symbol "Σ" is detected in a 1/16 image.

The position of the symbol is also estimated correctly. However, as shown in the images on the 10th and 11th lines, both the symbol "(" and the symbol ")" are detected at the same location. The symbol "(" and the symbol ")" appear as a pair in a mathematical formula, so semi-supervised learning, which uses only class information without using position information, does not distinguish them into separate positions. However, the negative effect on clustering is minor.

Note that the present invention is not limited to the above-described embodiments, and various modifications are possible. The present invention includes configurations that are substantially the same as those described in the embodiments (for example, configurations that have the same functions, methods, and results, or configurations that have the same objectives and effects). Further, the present invention includes a configuration in which non-essential parts of the configuration described in the embodiments are replaced. Further, the present invention includes a configuration that has the same effects or a configuration that can achieve the same objective as the configuration described in the embodiment. Further, the present invention includes a configuration in which a known technique is added to the configuration described in the embodiment.

In the above embodiment, an offline method (image input method) in which a handwritten mathematical pattern is read as an image by an optical reader is described. The present invention can also be applied to an online method of detection (pen coordinate input method). In the case of an online method, the above embodiment can be applied as is by connecting time-series lines of pen points and adding thickness and fleshing out the image to convert it into an image. Alternatively, features of time-series one-dimensional data may be extracted, and symbol position features (LC features) may be extracted as in the offline method. In the case of the online method, unlike the offline method, there is no need to reduce the handwritten mathematical pattern image and prepare multiple scale images, and instead, a neural network of LSTM (Long Short-Term Memory) is used to create symbol position characteristics for each symbol. can be extracted. Then, by one-dimensional hierarchical spatial pooling, the symbol position feature is divided into multiple types of partitions, the appearance probability of each symbol type is determined for each partition, a feature vector is generated, and all types of partitions are Concatenate the feature vectors from the splits to generate a hierarchical spatial feature vector. Since multiple scale images are not prepared, there is no need to perform maximum aggregation (MA) of hierarchical spatial feature vectors.

Further, in the above embodiment, a case has been described in which handwritten mathematical expression patterns are classified, but the present invention is not limited to this. The present invention can be applied to the classification of structures in which symbols are arranged in a two-dimensional space (handwritten patterns such as structural formulas of chemical substances, chemical reaction formulas, logical formulas, etc.).

DESCRIPTION OF SYMBOLS 100... Processing part, 110... Scale image generation part, 111... Feature extraction part, 112... Feature vector generation part, 113... Integration part, 114... Classification part, 115... Display control part, 116... Learning part, 160... Input part , 170... Storage section, 190... Display section

Claims (4)

A program for classifying multiple handwritten patterns input by hand,
a scale image generation unit that reduces an image of one handwritten pattern to at least one stage to generate a plurality of scale images including an original image before reduction and at least one reduced image;
a feature extraction unit that applies each of the plurality of scale images to a learning model using a convolutional neural network and extracts a symbol position feature regarding the appearance position of each type of symbol for each of the plurality of scale images;
a feature vector generation unit that performs a plurality of types of partitioning on the symbol position feature and generates a feature vector by determining the appearance probability for each type of symbol for each partition obtained by each of the plurality of types of partitioning; ,
an integrating unit that generates an integrated feature vector by taking the maximum value of the probability of appearance of the same symbol at the same location of the feature vectors generated from each of the plurality of scale images;
A program that causes a computer to function as a classification unit that classifies a plurality of handwritten patterns into a plurality of groups based on the integrated feature vector generated from each of the plurality of images of the handwritten patterns. In claim 1,
Each of the plurality of scale images is given to the learning model to obtain a feature map for each of the plurality of scale images, and the symbol position feature obtained by inputting the feature map to a discriminator and the feature map are The multiplied and averaged vectors are input to the discriminator to generate a first appearance probability vector indicating the appearance probability for each type of symbol, and the first appearance probability vector generated from each of the plurality of scale images is A first integrated appearance probability vector is generated by taking the maximum value of the appearance probability of the same symbol at the same location, and the learning is performed based on the first integrated appearance probability vector and training data indicating whether or not each type of symbol appears. A program characterized by causing a computer to further function as a learning section for learning a model. In claim 2,
The learning department is
Each of the plurality of scale images is given to the learning model, a feature map is obtained for each of the plurality of scale images, and a vector that takes the maximum value of the feature map is input to the discriminator to distinguish each symbol type. A second appearance probability vector indicating the appearance probability of the symbol is generated, and a second integrated appearance probability is obtained by taking the maximum value of the appearance probability of the same symbol at the same location of the second appearance probability vector generated from each of the plurality of scale images. generate a third integrated appearance probability vector by averaging the first integrated appearance probability vector and the second integrated appearance probability vector, and generate the third integrated appearance probability vector based on the third integrated appearance probability vector and the teacher data. A program characterized by learning a learning model. A clustering device that classifies a plurality of handwritten patterns input by hand,
a scale image generation unit that reduces an image of one handwritten pattern to at least one stage to generate a plurality of scale images including an original image before reduction and at least one reduced image;
a feature extraction unit that applies each of the plurality of scale images to a learning model using a convolutional neural network and extracts a symbol position feature regarding the appearance position of each type of symbol for each of the plurality of scale images;
a feature vector generation unit that performs a plurality of types of partitioning on the symbol position feature and generates a feature vector by determining the appearance probability for each type of symbol for each partition obtained by each of the plurality of types of partitioning; ,
an integrating unit that generates an integrated feature vector by taking the maximum value of the probability of appearance of the same symbol at the same location of the feature vectors generated from each of the plurality of scale images;
A clustering device comprising: a classification unit that classifies the plurality of handwritten patterns into a plurality of groups based on the integrated feature vector generated from each of the plurality of images of the handwritten patterns.

Images