Method For Non-negative Matrix Factorization And Its Application In Ballot Image Recognition

Image recognition has been developed with the development of computer technology. In it, the objects of different patterns are identified after their images are processed by computer. It is the basis of practical technologies for image fusion, stereo vision, motion analysis, and so on.In recent years, with the wide applications of image recognition technology in natural resource analysis, physiological changes, weather forecast, navigation, map and terrain matching, environmental monitoring and so on, many theories and methods have been applied to image recognition, and Non-negative Matrix Factorization (NMF) is one of them. NMF is a current research focus. NMF has been constructed according to the point of view which perception of the whole is based on perception of its parts. A non-negative matrix is factored into two non-negative matrixes. This can be interpreted as follows:each column of basis matrix contains a basis vector while each column of weight matrix contains the weights needed to approximate the corresponding column in the original matrix. There are interpretability and clear physical meaning in the decomposition of vector combination, and less storage space is occupied. NMF is a powerful tool for non-negative data processing. From the point of view of pattern recognition, NMF is essentially a subspace analysis method, and its essence is a method for feature extraction and selection. The main idea for NMF is that:a suitable subspace (feature subspace) in the sample space is found, and the high dimensional sample is projected to low dimension subspace, and the essential features of the sample in the subspace are obtained, and then classification is realized by these features. As a data processing technique, NMF has revealed the essence of describing data, and has been widely applied to the researches on face detection and recognition, image fusion, image retrieval, image classification, image restoration, image compression, digital watermarking in grey image, text analysis and clustering, speech recognition, biomedical engineering, intrusion detection in network security and so on.In this paper, NMF is studied deeply in theory. Firstly, based on two objective functions for Frobenius norm and Kullback-Leibler divergence, the Taylor series expansion, stable point for solving and the Newton iteration formula of solving root are used and a theoretical analysis method for NMF is proposed. Secondly, three methods for NMF are derived strictly by the method and some problems are solved. Finally, structural pattern recognition and the method for NMF in this paper are applied to the recognition of special handwritten characters in ballot image, and a method for ballot image recognition is given in detail. The main contributions of the paper are the following aspects:1. A novel method for NMF is proposed.Based on Frobenius norm‖X-WH‖F2and Kullback-Leibler divergence D(X‖WH), a method, called Novel Non-negative Matrix Factorization (NNMF), is proposed. In NNMF, iterative formulas for basis matrixes and weight matrixes are derived strictly from a theoretical point of view, and derivation method is new. The proofs of algorithm convergence are provided and algorithm steps are given. Relative to standard method for NMF, auxiliary functions are found and then the iterative formulas are determined more easily. When an objective function for Frobenius norm is used, the iterative formulas which are exactly the same as the iterative formulas for standard NMF with Frobenius norm may be gotten. When an objective function for Kullback-Leibler divergence is used, the novel iterative formulas are gotten, and in the experiments of face recognition, there are higher recognition accuracies for this algorithm than for corresponding algorithm in standard NMF in most cases which the ranks of the basis matrixes are set different values when the convergent precision is not very high.2. A method for approximate orthogonal NMF is proposed.A method, called Approximate Orthogonal Non-negative Matrix Factorization (AONMF), is proposed. In AONMF, an objective function is defined to impose approximate orthogonal constraint, in addition to the non-negative constraint in standard NMF. The Taylor series expansion and stable point of solving are used. An algorithm of iterative update for basis matrix and weight matrix is derived strictly. A proof of the convergence of the algorithm is provided. The reasons of approximate orthogonality for the basis matrix are clarified. Empirical results of face recognition show that there is high recognition accuracy if only the rank of the basis matrix is set correctly.3. A method for convergent projective NMF is proposed.In order to solve the problem of algorithm convergence in Projective Non-negative Matrix Factorization (P-NMF), a method, called Convergent Projective Non-negative Matrix Factorization (CP-NMF), is proposed. In CP-NMF, two objective functions for Frobenius norm and Kallback-Leibler divergence are considered. The Taylor series expansion and the Newton iteration formula of solving root are used. Two iterative algorithms for basis matrixes are derived strictly, and the proofs of algorithm convergence are provided. Experimental results show that the convergence speeds of the algorithms are higher, however they are affected by the initial values of the basis matrixes; relative to standard NMF, the orthogonality and the sparseness of the basis matrixes are better, however the reconstructed results of data show that the basis matrixes are still approximately orthogonal; in face recognition, there are higher recognition accuracies.4. A method for linear projective NMF is proposed.In order to solve the problem that an iterative method for Linear Projection-Based Non-negative Matrix Factorization (LPBNMF) is complex, a method, called Linear Projective Non-negative Matrix Factorization (LP-NMF), is proposed. From projection and linear transformation angle, an objective function for Frobenius norm is considered. The Taylor series expansion and stable point of solving are used. An iterative algorithm for basis matrix and linear transformation matrix is derived strictly and a proof of algorithm convergence is provided. Experimental results show that the algorithm is convergent; relative to some methods for NMF, the orthogonality and the sparseness of the basis matrix are better; in face recognition, there is higher recognition accuracy.5. A method for ballot image recognition is proposed.Special handwritten characters are usually tick "(?)", circle "O", cross "X" and bars "\","—","/" in ballot images. In order to solve the problem of speedy locating and recognition of handwritten character image in voting system based on Optical Character Recognition (OCR), a method for ballot image recognition is proposed. In the method, a visual ballot design is realized based on voting information which has been taken full account of. Relevant position data recorded in the ballot design help to preprocess the ballot image, find a definite reference point, extract the position data in the ballot design, convert them to an image position data which is connected to the reference point position, then search table lines through the position data, and determine an exact position which an image will be recognized. Based on the exact position, the handwritten character image can be captured and preprocessed, and then the structure feature of the handwritten character is extracted. With the structure feature, the recognition of the handwritten character is realized through structural pattern recognition. If the handwritten character is not identified with the structure feature, it is identified with new features which have been extracted by the method for NMF in this paper. High speed of locating and accuracy of recognition in this method have been successfully proved by experiments. By this recognition method based on the ballot design, the speed of locating is higher in recognition software, and ballot layout may be more complicated. By the structural pattern recognition and the method for NMF, the recognition accuracy is higher. The system efficiency is improved, and the voting system is more comprehensive.