Home      About Journal      Editorial Board      Instructions      Ethics Statement      Contact Us                   中文

Judgement and Disposal of Academic Misconduct Article Copyright Transfer Agreement Proof of Confidentiality Requirements for Electronic Version More.... Chinese Association of Automation National ResearchCenter for Intelligent Computing System Institute of Intelligent Machines,Chinese Academy of Sciences More....

2009 Vol.22 Issue.6, Published 2009-12-25 Papers and Reports    Researches and Applications    Surveys and Reviews        Papers and Reports 809 Non-Negative Two-Dimensional Principal Component Analysis and Its Application to Face Recognition YAN Hui, JIN Zhong, YANG Jing-Yu Two-dimensional principal component analysis (2DPCA) is an algorithm based on the whole face and it preserves the topology of facial components. Non-negative matrix factorization (NMF) is an algorithm based on localized features and extracts local information. A method for human face recognition is proposed, namely, non-negative 2-dimensional principal component analysis (N2DPCA). N2DPCA integrates the merits of 2DPCA and NMF. And it can overcome the demerits of traditional NMF. Furthermore, the proposed method does not require transformation from a 2D image matrix into a 1D long vector. The experimental results on ORL and FERET face database show that the proposed method achieves higher recognition rate and stronger robustness than 2DPCA, NMF and LNMF. 2009 Vol. 22 (6): 809-814 [Abstract] ( 274 ) [HTML 1KB] [ PDF 418KB] ( 850 ) 815 A Complex Adaptive Search Model WANG Ru-Jing, TAN Jing-Dong, HUANG He The Internet has the characteristics of openness, hierarchy, evolution and mass, so it is a typical complex adaptive system. A new complex adaptive search model is proposed based on the theory of complex adaptive system. A multi-agent experiment environment is formed through establishing the main union of information collection, classification, cleaning and services. The learning mechanism and evolutionary mechanism are researched, thus the search engine with the proposed model can actively adapt to the complex and dynamic network environment. Meanwhile, the proposed model can be widely used to construct special search models. 2009 Vol. 22 (6): 815-820 [Abstract] ( 231 ) [HTML 1KB] [ PDF 378KB] ( 485 ) 821 k-best MIRA and Dynamic k-best MIRA CAO Jun-Kuo, SHEN Chao, HUANG Xuan-Jing, WU Li-De Margin infused relaxed algorithm (MIRA) is an improved ultraconservative algorithm, which is successfully used in classification, ranking and regression. The k-best MIRA (K-MIRA) and dynamic k-best MIRA (DK-MIRA) are proposed. The improved MIRA reduces the optimization constraints progressively as training moves forward. The experiment is carried out on the task of sentence ranking in definitional question answering with K-MIRA and DK-MIRA. The experimental results show that the proposed algorithms greatly improve the performance. 2009 Vol. 22 (6): 821-826 [Abstract] ( 415 ) [HTML 1KB] [ PDF 412KB] ( 568 ) 827 A Text Extraction Method for Image with Complex Background Based on Conditional Random Field LI Min-Hua, WANG Chun-Heng, XIAO Bai-Hua, BAI-Meng Aiming at the problem of extracting text from images with complex background, a method based on conditional random field is proposed. The proposed method integrates various features and takes context information into account, thus it can extract text information effectively from images. The text extraction performance in different color spaces and with different features is compared. Experimental results demonstrate the validity of the proposed method. 2009 Vol. 22 (6): 827-832 [Abstract] ( 243 ) [HTML 1KB] [ PDF 348KB] ( 570 ) 833 Binary Combinatorial Grammar Parsing Model Based on Local Priority and Nesting Level YANG Xiao, MA Jun, WAN Jian-Cheng Due to the lack of descriptive mechanism for syntactic functional structure, the dependency grammar can not express all complex syntactic structures explicitly. In addition, few parsing model takes the restrictive information of modifiers' nesting level into account, though it is a common sense in pragmatics. To solve these problems, a generative binary combinational grammar (BCG) parsing model is proposed which incorporates the restrictive information. In this model, the construction of sentence is regarded as the combination of adjacent chunks according to their headwords. Moreover, the symbolic local priorities between the adjacent binary relations and the modifiers' nesting levels are used to constrain the generation of parsing trees. The BCG parsing model is constructed by converting the dependency treebank to the BCG form. Then, the syntactic relations, the local priorities and the parameters of the model are induced automatically. Experimental results show that the proposed model improves the parsing accuracy. 2009 Vol. 22 (6): 833-840 [Abstract] ( 250 ) [HTML 1KB] [ PDF 491KB] ( 399 ) 841 Algebra Property and Application of Coalition Structure Graph LIU Jing-Lei, ZHANG Wei, WANG Ling-Ling The space of coalition structure is abstracted as a coalition structure graph, and two operators, union and intersection, are defined. Thus, all the coalition structures form an algebra structure, coalition structure lattice (CSL). In order to simplify the study of CSL algebra property, the integer split graph is introduced, and a mapping relation F from coalition structures to integer splits and an equivalent relation EF based on F are constructed. Therefore, during searching optimal coalition structure in CSL, the current optimal value and average value are used as prune function. When the upper bound of some equivalent class is lower than the prune function, a large number of coalition structures in equivalent class are pruned. Finally, better dynamic programming (BDP) algorithm is given, and the validity of the proposed algorithm is proved by experimental analysis. Furthermore, the results indicate that BDP decreases 43% searching numbers than dynamic programming when there are 20 agents. 2009 Vol. 22 (6): 841-847 [Abstract] ( 253 ) [HTML 1KB] [ PDF 394KB] ( 439 ) 848 Two-Stage Text Clustering Based on Collaborative Clustering WANG Ming-Wen, FU Jian-Bo, LUO Yuan-Sheng, LU Xu To take full advantage of the semantic relations for text clustering and feature selection, a kind of two-stage text clustering based on collaborative clustering is proposed. The documents and the features are clustered respectively to capture the semantic relations between features and topics, and these relations are used to adjust the clustering interactively. The experimental results show that the clustering performance is effectively improved by using the relations between features and topics. 2009 Vol. 22 (6): 848-853 [Abstract] ( 232 ) [HTML 1KB] [ PDF 454KB] ( 466 ) 854 Subpattern-Based Complete Two Dimensional Principal Component Analysis for Gait Recognition WANG Ke-Jun, BEN Xian-Ye, LIU Li-Li, LI Xue-Feng A gait recognition method based on subpattern complete two dimensional principal component analysis (SpC2DPCA) is proposed. Firstly, gait energy images are divided into small sub-images and any ineffectual subblock is removed adaptively. Then, C2DPCA approach is applied to every sub-image directly to obtain sub-feature. Finally, those sub-features are synthesized into the whole for subsequent classification using the nearest neighbor classifier. The proposed gait recognition method is evaluated on the CASIA gait database, and the number of sub-pattern division is determined through experiments. The experimental results demonstrate that the performance of SpC2DPCA is obviously superior to that of C2DPCA.The proposed method is effective in local feature extraction and person identification with clothes changing, backpacking and direction of gait changing. 2009 Vol. 22 (6): 854-861 [Abstract] ( 233 ) [HTML 1KB] [ PDF 1053KB] ( 409 ) 862 Quantum Cooperative Immune Algorithm for Dynamic Optimization Problem WU Qiu-Yi, JIAO Li-Cheng, WEI Jun, LI Yang-Yang A quantum cooperative immune algorithm is proposed for dynamic optimization problem, which is based on the synergism strategy and principles of quantum-inspired immune computing, and its global convergence is proved in theory. Individuals in a population are represented by quantum bits(qubits).In the individual's updating, the quantum rotation gate strategy and the dynamic adjusting rotation angle mechanism are applied to accelerate convergence. By using cooperative strategy, the information between the subpopulations is exchanged and the diversity of the population is improved. The stability of the proposed algorithm is strengthened to make it fit for the dynamic problem by introducing the relevance of quantum population. In the experiment, the quantum cooperative immune algorithm is tested on dynamic problem and compared with other algorithms by t test. The results indicate that the proposed algorithm has good robustness and adaptability. 2009 Vol. 22 (6): 862-868 [Abstract] ( 242 ) [HTML 1KB] [ PDF 878KB] ( 366 ) 869 A Linear Evolutionary Algorithm for Solving Constrained Optimization Problems TANG Ke-Zong YANG Jing-Yu, GAO Shang, LI Wei A linear evolutionary algorithm for solving constrained optimization problems (LEACOP) based on real-coded method is proposed, and its complexity and convergence are also analyzed. One of the main advantages of the proposed algorithm is that the search space of constrained dominance problems with high dimensions is compressed into two dimensions. A linear fitness function based on mathematic analysis is deduced in two dimension space to fast evaluate fitness value of each individual in population. A crossover operator based on density function and a new mutation operator are developed to extend the search space and extract better solution. In addition, an average linkage based on hierarchical clustering method is introduced into the LEACOP to maintain the number of individuals on Pareto set. A few benchmark multi-objective optimization problem which is divided into three groups is introduced to test this algorithm. The numerical experiments show that proposed algorithm is feasible and effective, and it provides good performance in terms of uniformity and diversity of solutions. 2009 Vol. 22 (6): 869-876 [Abstract] ( 281 ) [HTML 1KB] [ PDF 500KB] ( 533 ) Surveys and Reviews 877 Diffusion Convergence of Collective Multiagents: A Review JIANG Yi-Chuan Complex systems and complexity problem are modeled based on multiagents, thus the diffusion convergence of collective multiagents is a key issue for the related areas. Firstly, the diffusion convergence phenomenon of multiagents is introduced. Then, the related work are categorized based on three criterions: the diffusion fashions among agents, the distribution of diffusion convergence capacities of agents and the sensing scopes of agents in the diffusion convergence. With the criterions, the related work is classified into hierarchical diffusion convergence versus collective convergence, flat diffusion convergence versus non-flat convergence and neighboring diffusion convergence versus global convergence. The detailed review and comparison are made among diffusion convergence models and the future work is discussed. 2009 Vol. 22 (6): 877-883 [Abstract] ( 272 ) [HTML 1KB] [ PDF 362KB] ( 383 ) Researches and Applications 884 Image Threshold Selection Method Using Weighted Harmonic Average Maximum Entropy LEI Bo, FAN Jiu-Lun A harmonic average Shannon entropy threshold method is proposed based on the thought that the maximum entropy threshold method searches the optimal threshold of the image by maximizing the arithmetical average Shannon entropy of the object and the background. To improve the performance of the proposed method, a weighted harmonic average threshold method and a weight preferences method are proposed. The proposed weighted harmonic average threshold method searches the optimal threshold by maximizing the weighted harmonic entropy of the object and the background in an image. Experimental results show that the proposed method gets better segmentation result than the classical Shannon entropy threshold method. 2009 Vol. 22 (6): 884-890 [Abstract] ( 263 ) [HTML 1KB] [ PDF 1192KB] ( 454 ) 891 Smooth Ranking Support Vector Machine Adapting to Web Retrieval HE Hai-Jiang Cost-sensitive ranking support vector machine converts the order relation of samples into the classification relation of sample pairs, and it is particularly well suited to web information retrieval. However, learning large amounts of sample pairs takes extremely long time. A cost-sensitive smooth ranking support vector machine(cs-sRSVM) using 2-Norm error is presented. Firstly, the optimization object is transformed into unconstrained problem. Secondly, the smooth piecewise polynomial function is approximated to the hinge loss function. Finally, the unique optimal solution is obtained by applying Newton-YUAN method. The experimental results on a public dataset LETOR show that the training time of cs-sRSVM is faster than that of the existing cost-sensitive ranking algorithm, and its retrieval performance is equally impressive. 2009 Vol. 22 (6): 891-897 [Abstract] ( 284 ) [HTML 1KB] [ PDF 448KB] ( 342 ) 898 Feature Extraction Method on Maximum Margin Criterion with Locality Preserving WANG Chao, WANG Shi-Tong The maximum margin criterion (MMC) aims at maximizing the inter-class scatter and minimizing the intra-class scatter simultaneously after the projection to overcome the small sample size problem. A feature extraction method is proposed. Compared with the original MMC method, the proposed method can manifold local structure information better by multiplying the defined weight and regulating the parameter. The experimental results on ORL face database ,YALE database and UMIST database show that the proposed method is robust to illumination and pose, and it improves the recognition rate and recognizes the face images efficiently. 2009 Vol. 22 (6): 898-902 [Abstract] ( 257 ) [HTML 1KB] [ PDF 294KB] ( 498 ) 903 Multi-Feature Based Online Signature Verification ZHANG Da-Hai, WANG Zeng-Fu A multi-feature based online signature verification algorithm is presented that synthesizes global features, segment features, force series and shape series. A novel digital tablet called F_Tablet is used to capture both the shape series and the three-dimensional force series. Firstly, global features are extracted from the signature and weight function of features is defined to select the personalized global features and separate the genuine signatures from the fake ones. A probability method is used based on global features. Then, the signature is segmented and the segment features are extracted. A hidden Markov model is established based on segment features. The force series and shape series are matched with dynamic time warping. Finally, the multi-feature is synthesized to verify the test signatures and the proposed algorithm achieves equal error rate of 1.5%. 2009 Vol. 22 (6): 903-907 [Abstract] ( 375 ) [HTML 1KB] [ PDF 404KB] ( 463 ) 908 A Fast Mapping Isomap Algorithm SHENG Shao-You, LI Bin The traditional Isomap algorithm emphasizes analyzing the manifold structure of the existing dataset. It can not provide fast and direct mapping of a new sample from high dimensional space to low dimensional space, so the traditional Isomap algorithm can not be used for feature extraction and high-dimensional data retrieval. In this paper, a fast mapping Isomap algorithm is proposed, by which the low-dimensional coordinates of a new sample can be calculated with relatively low computational complexity, and the most similar sample of the query sample can be retrieved based on such low-dimensional coordinates. Experimental results on typical benchmark datasets demonstrate that the proposed algorithm accomplishes the task of fast mapping with well preserving of the neighborhood relationship. 2009 Vol. 22 (6): 908-912 [Abstract] ( 234 ) [HTML 1KB] [ PDF 1012KB] ( 801 ) 913 Image Threshold Selection Method Using Weighted Harmonic Average Maximum Entropy YANG Yang, LI Shan-Ping In the problem of imbalanced data classification, the minority class is the classification target, but it is more difficult to be recognized than the majority class. The current popular classification algorithms have two main disadvantages: the explicit setup of instances importance degrees and the indirect support of the recognition of minority class. An instance importance based learning algorithm is proposed, namely instance importance based support vector machine (IISVM). IISVM is composed of three phases. In the first two phases, one class SVM and binary SVM are used respectively. And the training instances are divided into three groups: the most important group, important group and unimportant group. In the last phase, the most important instances are employed to train the initial classifier, and then the explicit stopping criteria are adopted to control the recognition of minority class directly. The experimental results illustrate that the performance of IISVM is superior to other standard or advanced solutions. 2009 Vol. 22 (6): 913-918 [Abstract] ( 337 ) [HTML 1KB] [ PDF 407KB] ( 598 ) 919 Biometric Recognition Based on Nose Pore Features SONG Shang-Ling, KAZUHIKO Ohnuma, MEI Liang-Mo, SUN Feng-Rong Centerline of nose is extracted by Hessian matrix parameters to segment the matched region. Direction of gradient and eigenvector corresponding to the largest eigenvalue are combined to detect nose pore. The proposed method achieves an identification correct rate of 88.07% on a database of 103 persons. The experimental results show that nose pore feature can be used as one of the most efficient biometric features in recognition. 2009 Vol. 22 (6): 919-923 [Abstract] ( 294 ) [HTML 1KB] [ PDF 879KB] ( 500 ) 924 Semi-Supervised Learning Based on One-Class Classification MIAO Zhi-Min, ZHAO Lu-Wen, HU Gu-Yu,WANG Qiong A semi-supervised learning algorithm is proposed based on one-class classification. Firstly, one-class classifications are built respectively for each class of data on labeled dataset. Then, some unlabeled data are tested by these one-class classifications. The classification results are used to adjust and optimize two classification surfaces. All labeled data and some recognized unlabeled data are used to train a base classifier. According to the classifying results of the base classifiers, the label of the test sample is determined. Experimental results on UCI datasets illustrate that the average detection precision of the proposed algorithm is 4.5% higher than that of the tri-training algorithm and 8.9% higher than that of the classifier trained by pure labeled data. 2009 Vol. 22 (6): 924-930 [Abstract] ( 399 ) [HTML 1KB] [ PDF 423KB] ( 516 ) 931 A DensityNeighborsBased Incremental Outlier Detection Algorithm CAO Hui, SI Gang-Quan, ZHANG Yan-Bin, JIA Li-Xin Aiming at the problem of incremental outlier detection with the dataset being updated, a density-neighbors-based incremental outlier detection algorithm is proposed. When the dataset is updated, the proposed algorithm identifies the affected objects and establishes the density neighbor sequences of the objects based on the change of the k-density of the object and those of its neighbors. According to the density neighbor sequence cost (DNSC) of the object and the average of the DNSC of k-distance neighbors of the object, the proposed algorithm calculates the incremental outlier factor(IOF) of each affected objects and the IOF value indicates the degree of the object as an outlier. Therefore, the proposed algorithm improves the effectiveness of incremental outlier detection. Moreover, it speeds up the outlier detection since the proposed algorithm recalculates the IOF values of these affected objects. The experimental results show that the proposed algorithm has a higher quality in outlier detection than the former incremental algorithms with the decrease of the running time. 2009 Vol. 22 (6): 931-935 [Abstract] ( 254 ) [HTML 1KB] [ PDF 345KB] ( 456 ) 936 An Improved KNN Text Categorization Algorithm by Adopting Cluster Technology ZHANG Xiao-Fei, HUANG He-Yan k-Nearest Neighbor (KNN) algorithm has the advantage of high accuracy and stability. But the time complexity of KNN is directly proportional to the sample size, its classification speed is low and it is problematic to be put into practice in large-scale information processing. An improved KNN text categorization algorithm is proposed which classifies faster than the traditional KNN does. Firstly, some similar sample documents are combined into a center document through adopting automatic text clustering technology. Then, a large number of original samples are replaced with the small amount of sample cluster centers. Therefore, the calculation amount of KNN is reduced greatly and the classification is speeded up. The experimental results show that the time complexity of the proposed algorithm is decreased by one order of magnitude and its accuracy is approximately equal to those of the SVM and traditional KNN. 2009 Vol. 22 (6): 936-940 [Abstract] ( 257 ) [HTML 1KB] [ PDF 0KB] ( 135 )

Supervised by China Association for Science and Technology Sponsored by Chinese Association of Automation NationalResearchCenter for Intelligent Computing System Institute of Intelligent Machines, Chinese Academy of Sciences Published by Science Press

Copyright © 2010 Editorial Office of Pattern Recognition and Artificial Intelligence Address: No.350 Shushanhu Road, Hefei, Anhui Province, P.R. China Tel: 0551-65591176 Fax:0551-65591176 Email: bjb@iim.ac.cn Supported by Beijing Magtech 　Email:support@magtech.com.cn