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....

2006 Vol.19 Issue.2, Published 2006-04-25 Papers and Reports    Researches and Applications        Papers and Reports 129 Conjugate Gradients Support Vector Machine ZHOU ShuiSheng, ZHOU LiHua Support vector machines can be posed as quadratic programming problems in various ways. Using the technology of the Lagrangian dual, an unconstrained differentiable convex program problem is proposed as the dual of the quadratic programming, which is a simple reformulation on standard quadratic program of a linear support vector machine. The resulting problem minimizes a differentiable convex piecewise quadratic function in the input space, but not in the feature space. By the characteristic of the piecewise quadratic function and the combination with the speedy line search method, a Conjugate Gradients Support Vector Machine (CGSVM) is proposed to solve the unconstraint program problem quickly. After kernel matrix is factorized by the Cholesky factorization or incomplete Cholesky factorization, nonlinear classification problem with kernel function can also be solved by CGSVM with little increase of the complexity of the algorithms. CGSVM can be used to solve linear classification problems with millions of points and the nonlinear classification problems with three thousand points or more on normal PC. Many numerical experiments and complexity analysis demonstrate that the proposed algorithms are very efficient compared with the similar algorithms such as ASVM and LSVM. 2006 Vol. 19 (2): 129-136 [Abstract] ( 347 ) [HTML 1KB] [ PDF 2043KB] ( 410 ) 137 Perceptual Completion of Occluded Boundaries and Illusory Contours in 3D Scene WANG Yan, WANG ZengFu The perceptual completion problem of 3D scene within the framework of stereovision is discussed in this paper. An electrostatic completing field based model is presented, which refers to the laws of Gestalt psychology, the rules of visual organization and the properties of electrostatic field. In the model, stimuli are defined and arranged on the breakpoints of fragments to produce the completing field. Then the completing field matches the breakpoints naturally and connects them with proper smooth curves. The completions of occluded boundaries and illusory contours agree with the human perception. The completion results can be used for reconstructing 3D information of the scene and segmenting the scene into a set of surfaces correctly from stereo images. 2006 Vol. 19 (2): 137-142 [Abstract] ( 254 ) [HTML 1KB] [ PDF 422KB] ( 585 ) 143 Parameter Estimation in Markov Random Field Based on Evolutionary Programming SHAO Chao, HUANG HouKuan, YU Jian It’s difficult to estimate the parameters in Markov Random Field (MRF) due to the computationally intractable partition function when using Markov random field as the prior model of image in Bayesian method. So a new method based on Evolutionary Programming (EP) is presented to estimate these parameters in this paper. This method employs evolutionary programming to search for the suited parameters, from which the most similar simulated image of the original 〗image can be obtained. Using this method, the calculation of the computationally intractable partition function can be avoided. Moreover, the most similar (even the entirely identical) simulated image of the original image can be obtained, which makes this method better than other traditional methods based on the likelihood function. Finally, this method is verified by experimental results. 2006 Vol. 19 (2): 143-148 [Abstract] ( 259 ) [HTML 1KB] [ PDF 615KB] ( 508 ) 149 Properties, Improvements and Propagation of Compatibility Measurementbetween IntervalValued Fuzzy Sets XU WeiHong, ZENG ShuiLing, YANG JingYu, YE YouPei The properties of compatibility measurement between intervalvalued fuzzy sets are analyzed, and the existing compatibility measurement is improved into a new formula, so called harmoniousness, which overcomes the unsymmetry and inherits other basic characteristics of the compatibility. How fuzzy inference methods propagate the compatibility and harmoniousness is also discussed. In practical applications, when antecedent and consequence of a known rule are normal fuzzy sets, the harmoniousness between input and the antecedent is not bigger than the one between output and the consequence by Zadeh’s Compositional Rule of Inference. Our research is advantageous to neatening fuzzy rule database based on intervalvalued fuzzy sets as well as analysis and choice of fuzzy inference methods. 2006 Vol. 19 (2): 149-154 [Abstract] ( 316 ) [HTML 1KB] [ PDF 360KB] ( 374 ) 155 Detecting Salient Regions Based on “What” and “Where” Pathways of Visual Systems TIAN Mei, LUO SiWei, QI YingJian, LIAO LingZhi Inspired by the research of visual systems in neuroanatomy and psychology, a novel model for salient region detection based on “what” and “where” pathways in an image is proposed in this paper. The operation of the model can be divided into two stages: finding and shifting salient regions. Current salient region and potential targets of an image are firstly found and marked according to statistical feature saliency. Series of next salient regions are then detected by altering different current salient region and alterative attracting force computation. Experimental results with natural images demonstrate its effectiveness and robustness. 2006 Vol. 19 (2): 155-160 [Abstract] ( 381 ) [HTML 1KB] [ PDF 1314KB] ( 520 ) 161 Novel Active Contour Model for Object Tracking Based on the Potential Energy of Shape Restriction MIN Li, HUANG ShaBai, SHI ZeLin, TANG YanDong A novel active contour model for object tracking based on shape restriction is presented in this paper. Contour curvature prior is used to define potential energy of shape restriction and then integrated with region and gradient information of image to formulate the active contour model for tracking. With curvature restriction, this model can correct the wrong deformation caused by weak gradient of object boundary and cluttered background. It also maintains the overall structure of object and tracks object with irregular shape in image sequences. Furthermore, the initial contour is estimated using affine transformation based on the blockmatching. The model is applied to tracking IR car target in cluttered background and aircraft target in image sequences. Experimental results show that the proposed model has robust tracking performance in cluttered background and shapepreserving. 2006 Vol. 19 (2): 161-166 [Abstract] ( 263 ) [HTML 1KB] [ PDF 1109KB] ( 503 ) 167 MultiModal Immune Algorithm Based on Peaks Poised and Gradient Evolution Strategies YANG KongYu, WANG XiuFeng Some available multimodal optimization algorithms are analyzed and the faults of them are pointed out. Based on their same features that they all have fine search effect to functions with equivalence peaks, the peaks poised strategy is proposed. Then a new Multimodal Immune Algorithm (MIA) with mechanisms of antibody evolution in immune system and conventional gradient evolution is designed. The implementations of peaks poised strategy and main evolution operators are given, the algorithm's operating mechanisms, complete convergence and computation complicacy are analyzed. The simulation experiments are performed and the results testify that MIA has availability on solving multimodal optimization problems, especially for functions with nonequivalence peaks, complete convergence and quickly convergence ability. 2006 Vol. 19 (2): 167-172 [Abstract] ( 218 ) [HTML 1KB] [ PDF 387KB] ( 620 ) 173 An AND/OR TreeBased Algorithm for Checking Pestilent Ambiguity in Regular Expressions DENG XuBin, ZHU YangYong During the construction of regular expressions (REs) for applications, introducing some beneficial ambiguities may simplify RE construction, while leaving some pestilent ambiguities in the RE will harm the correctness of matching. In order to treat these two categories of ambiguities in different ways, an algorithm based on AND/OR tree that checks and locates the pestilent ambiguities in REs is proposed. The algorithm is helpful to reducing the workload of debugging REs. Experiments show that the algorithm outperforms the present ambiguitychecking algorithm based on automaton not only in time and space behaviors, but also in practicality. A visualized RE editing and debugging environment based on the algorithm has been applied to build the first online integrated biological data warehouse of China. 2006 Vol. 19 (2): 173-178 [Abstract] ( 210 ) [HTML 1KB] [ PDF 394KB] ( 494 ) 179 A MultiInstance Learning Based Approach to Image Retrieval DAI HongBin, ZHANG MinLing, ZHOU ZhiHua Multiinstance learning has already been employed in ContentBased Image Retrieval (CBIR) for the reason that it is good at dealing with the inherent ambiguity of images. In this paper, a ultiinstance learning based CBIR approach is presented. The whole image is regarded as a multiinstance bag. The image is partitioned into several regions using a SelfOrganizing feature Map (SOM) clustering based image segmentation method, then the regions described by color and texture features are regarded as the instances in the bag. Next, query images posed by the user are transformed into corresponding positive and negative bags and a multiinstance algorithm is employed for image retrieval and relevance feedback. Experiments show that this approach achieves comparable results to some existing approaches and is even more efficient. 2006 Vol. 19 (2): 179-185 [Abstract] ( 323 ) [HTML 1KB] [ PDF 696KB] ( 940 ) Researches and Applications 186 Application of Key Words Recommendation Based on Apriori Algorithm in ThemeOriented Personalized Search LIU Qi, BU JiaJun, CHEN Chun The application of collaborative filtering algorithm in key words recommendation is analysed and a themeoriented key words recommendation algorithm in personalized search is proposed based on Apriori algorithm in this paper. The essential of proposed method is mining the frequent itemsets of the historical key words by Apriori algorithm. Experimental result indicates that the algorithm can recommend new key words to user based on the historical key words and make the search results more accurate and individual. 2006 Vol. 19 (2): 186-190 [Abstract] ( 275 ) [HTML 1KB] [ PDF 318KB] ( 630 ) 191 Wavelet Transform for Affine Invariant Image Object Recognition ZHANG Hua, FENG XiangChu, DONG SuYuan It’s a key problem to search for affine invariant with respect to translating, scaling, rotation and skewing in multiresolution analysis. Based on affine invariants defined in Affine Invariants for Object Recognition Using the Wavelet Transform, the original absolute affine invariants are improved in this paper. After the analysis of the invariants, their limitation is pointed out and a new kind of absolute affine invariants is defined. Both experimental results and analysis show that the proposed invariants can be easily applied to image recognition. 2006 Vol. 19 (2): 191-195 [Abstract] ( 257 ) [HTML 1KB] [ PDF 538KB] ( 752 ) 196 A Method of Generating Rules with a Kernel Fuzzy Classifier YANG Ai-Min, HU Yun-Fa A method of generating rules with kernel fuzzy classifier is introduced in this paper. This method selects appropriate kernel function by the principle of SVM. Firstly, the initial sample space is mapped into a high dimensional feature space in order to simplify and separate the samples. Then in the feature space, the dynamic clustering arithmetic dynamically separates the training samples into different clusters and finds out the support vectors of each cluster. For each cluster, a fuzzy rule is defined with ellipsoidal regions. Finally, the rules are tuned by Genetic Algorithms. This method is evaluated by two typical data sets. For the classifier with this method, the learning time is short, and the accuracy and the speed of classification are relatively high. 2006 Vol. 19 (2): 196-202 [Abstract] ( 238 ) [HTML 1KB] [ PDF 432KB] ( 398 ) 203 An Alignment Algorithm of Fingerprint Image Based on Singular Points CHEN PeiHua, CHEN XiaoGuang A new fingerprint alignment algorithm is presented in this paper. A multiresolution method for singular point localization in fingerprint images is used, which can not only ensure location precision, but also decrease the probability of error and the computational time. By fingerprint orientation field analysis, the direction of the core is computed accurately and quickly. According to the location and direction of registration point, the live scanned fingerprint can be aligned with the fingerprints in the database. Compared with the common pointpattern alignment algorithm, the complexity of proposed algorithm is lower. Experimental result shows that the alignment using the proposed algorithm can get high precision and efficiency, which is practicable and advantageous to fingerprint matching. 2006 Vol. 19 (2): 203-207 [Abstract] ( 359 ) [HTML 1KB] [ PDF 759KB] ( 544 ) 208 Pattern Growth Method for Mining Embedded Frequent Trees MA HaiBing, LI RongLu, HU YunFa In this paper, an efficient pattern growth algorithm for mining frequent embedded subtrees in rooted, labeled, and ordered trees is presented. It uses rightmost path expansion schema to construct complete pattern growth space, and creats a projection database for every grow point of the treepattern. So the problem is transformed from mining frequent trees to finding frequent nodes in the projected database. Thus the complexity of the algorithm is considerably reduced. Experimental results show that it is efficient for both time and space. 2006 Vol. 19 (2): 208-214 [Abstract] ( 281 ) [HTML 1KB] [ PDF 404KB] ( 442 ) 215 A Novel Ant Colony Algorithm Based on Time Model ZUO HongHao, XIONG FanLun Basic ant colony algorithm, which is based on bionics, has been successfully used in many fields, especially on combinatorial optimization problems. Because many parameters need to be adjusted in application, it is inconvenient for many users especially those who have little experience. A novel ant colony algorithm based on real time model, which regresses to the base of ant colony algorithm is put forward. It is supposed that each ant’s velocity is equal to dmin per second and all ants are crawling in full time. Ants communicate with others by the pheromone that is left on the road. After some time the ants’ trails will be on the optimal route between the food and the nest. It is testified by the experiment that the novel algorithm is as efficient as other ant colony algorithms and it is simpler to justify the parameters. This novel algorithm also can be used in simulating application and distributed computing. 2006 Vol. 19 (2): 215-219 [Abstract] ( 253 ) [HTML 1KB] [ PDF 414KB] ( 425 ) 220 An Improvement of the RAN Learning Algorithm LI Bin An improved learning algorithm for Resource Allocating Network (RAN) is presented in this paper, which is called IRAN algorithm. It allocates hidden neurons of network by a fourpart novelty criterion, removes redundant neurons according to their error reduction rates, and updates outputlayer weights by a recursive leastsquares algorithm with GivensQR decomposition. Simulations on two Benchmark problems in the function approximation area indicate that the IRAN algorithm can provide smaller networks and consume less training time than RAN, RANEKF and MRAN algorithms. 2006 Vol. 19 (2): 220-226 [Abstract] ( 286 ) [HTML 1KB] [ PDF 1304KB] ( 687 ) 227 Image Enhancement Based on Wavelet Analysis and Human Visual System(HVS) LI ZhaoHui, CHEN Ming Based on wavelet analysis, a new image UM adaptive enhancement algorithm is presented with the combination of the analysis of a human visual system model and the UM algorithm based upon wavelet resolution. The outputs of Laplace core g(·) with a 3×3 pixel framework are used to check the local dynamic behavior of images so as to guarantee the output optimum of the adaptive framework comparator. The adjustment about human visual model coefficients regards MTF as an objective function, then makes a postprocessing upon image reconstruction vectors so that the better effect of image enhancement to the human visual system can be obtained. 2006 Vol. 19 (2): 227-231 [Abstract] ( 241 ) [HTML 1KB] [ PDF 824KB] ( 419 ) 232 Reconstruction of Handwriting Sequence Based on Stroke Segment for OffLine Handwritten Numerals LI GuoHong, SHI PengFei An approach to derive information about handwriting traces from stroke structures of handwritten numerals is proposed. An improvement to the algorithm for extracting fork points from skeleton images guarantees the completeness of extracted feature points, thus ensures the reliability of stroke restoration. The relation graph is created according to structural graph of stroke segments. The proposed algorithm for handwriting trace reconstruction is equal to the 〗algorithm of ordering the stroke segments in nature. Reconstruction is regarded as a globally optimal problem, and the handwriting trace is considered as the path with the totally minimal orientation variance, which can be resolved by searching a Hamiltonian path with minimal cost. Experimental results on UCI dataset indicate the proposed approach is effective to the reconstruction of handwriting traces of handwritten numerals. 2006 Vol. 19 (2): 232-237 [Abstract] ( 245 ) [HTML 1KB] [ PDF 379KB] ( 432 ) 238 A Moving Object Detection and Recognition Method in Video Sequences LI QingZhong, CHEN XianHua, WANG LiHong This paper focuses on automatic extraction and recognition of moving objects in video sequences for intelligent outdoor video monitoring systems. The object extraction method is based on a color image difference model and an adaptive threshold segmentation algorithm. Moreover, an image morphology filtering method and a background image updating method are described. In order to solve the recognition problems caused by shadows of objects, the number of objects and the corresponding top position of each object in the detected region are first obtained by histogrambased technique, then the invariant moment characteristics of headshoulder region are extracted. Finally, a GA based neural network is used to recognize the moving objects. Experimental results show that the proposed approach is effective for moving objects detection and recognition in complex outdoor background. 2006 Vol. 19 (2): 238-242 [Abstract] ( 333 ) [HTML 1KB] [ PDF 546KB] ( 552 ) 243 Adaptive Immune Wavelet Network Based Intrusion Detection LIU Fang, LUO Lan An adaptive immune wavelet network based intrusion detection model and the related algorithm are proposed by combining an adaptive wavelet network model with immune algorithm in this paper. The model not only avoids blindness of determing parameters and construction of neural network, but also alleviates sensitivity to initialization. The experimental results show detection rate acquired in this algorithm is higher than that in other algorithms and its convergency speed is higher than others’. Moreover, the relationship between False Negatives and False Positives can be restricted and balanced by adjusting a threshold value. 2006 Vol. 19 (2): 243-248 [Abstract] ( 267 ) [HTML 1KB] [ PDF 527KB] ( 398 ) 249 A Partition Algorithm for Huge Data Sets Based on Rough Set QIN ZhengRen, WU Yu, WANG GuoYin Processing huge data sets is an important topic in data mining nowadays. Although many serial or parallel algorithms have been developed to deal with huge data sets, most of them are not ideal to resolve the conflict between speed and accuracy. In this paper, the whole huge data set is partitioned into many small subsets for the advantage of distributed computing. At first, a definition of best partition is proposed. Then, a roughsetbased partition algorithm is developed to look for the best partition. Experimental results prove that the distributed information processing method based on the roughsetbased partition algorithm is an effective method in dealing with huge data sets. It is faster than original roughsetbased algorithms and its performance is as good as those processing the original data set as a whole. 2006 Vol. 19 (2): 249-256 [Abstract] ( 246 ) [HTML 1KB] [ PDF 535KB] ( 742 ) 257 Research on Image Segmentation Based on Snake Model of Previous Knowledge and Region Information ZHOU CangXiong, YU ShengLin, WU Chen Based on previous knowledge and region information, a novel parametric active contour model (Snake model) for image segmentation to ambiguous edge is described in this paper. In the proposed model, constant force in the balloon snake model is replaced by variable force which incorporates with previous knowledge and two regions information of foreground and background. Experiments prove that the proposed model is robust to initial contour places and it can segment ambiguous edge image automatically. In addition, result of segmentation to two regions that have identical mean and different variation is correct. 2006 Vol. 19 (2): 257-261 [Abstract] ( 264 ) [HTML 1KB] [ PDF 888KB] ( 429 ) 262 A Fast Method of Airport Runway Detection in Aerial Images WU JianXin, LI CuiHua, WU XiaoChang, KE Yu A method to fast detect airport runway in the aerial images is presented in this paper. Firstly, the binary image is generated via adaptive edge detection, so the main edges of the object in the image are extracted. Next, using the length information of the lines and gradient information of the pixels, the postprocessing is applied to eliminate the short lines and reduce the curves. Then the parallel straight lines detected by Hough transform are considered as candidate regions. At last, the candidate regions are verified by the character of runway. Experiments on dozens of the aerial images from Internet indicate that this method can detect the runway exactly and quickly, and it is robust to the disturbance of some background objects such as cloud. 2006 Vol. 19 (2): 262-265 [Abstract] ( 350 ) [HTML 1KB] [ PDF 1134KB] ( 729 ) 266 Research on Chaos Particle Swarm Optimization Algorithm GAO Shang, YANG JingYu By use of the properties-ergodicity, randomicity, and regularity of chaos, a chaos particle swarm optimization(CPSO) algorithm is proposed to solve the optimization problems. The basic principle of CPSO algorithm is that chaos initialization is adopted to improve individual quality and chaos perturbation is utilized to avoid the search being trapped in local optimum. Simulation results of typical complex function optimization show that chaos particle swarm optimization is a relatively simple and effective algorithm. 2006 Vol. 19 (2): 266-270 [Abstract] ( 427 ) [HTML 1KB] [ PDF 333KB] ( 1368 ) 271 An Geometrical Algorithm for Minimum Covering Sphere and Application in Pattern Recognition LAI JiangLiang, WANG ShouJue With the definition of HyperChord Angle a geometrical algorithm of highdimensional minimum covering ball is proposed in this paper. Combining with RBF neuron and priority order neural network, the geometrical algorithm of highdimensional minimum covering ball is applied in sample classification efficiently. The definition of HyperChord Angle also provides a new way to research other problems in highdimensional space. 2006 Vol. 19 (2): 271-276 [Abstract] ( 429 ) [HTML 1KB] [ PDF 548KB] ( 712 ) 277 BorderProcessing Technique in GridBased Clustering QIU BaoZhi, SHEN JunYi In order to improve accuracy of gridbased clustering, a borderprocessing technique is proposed, Using restricted k nearest neighbors and concept of relative density. The technique enables us to separate cluster’s border points from outliers or noises accurately. Then, a gridbased clustering algorithm with border processing (GBCB) is developed. Experiment results show high accuracy of recognition of border points. Due to the only one data scan, the GBCB algorithm is very efficient with its run time being linear to the size of the input data set, and can discover arbitrary shapes of clusters and scale well. 2006 Vol. 19 (2): 277-280 [Abstract] ( 325 ) [HTML 1KB] [ PDF 341KB] ( 568 )

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