Similarity Calculation Of Three-dimensional Models Based On Genetic Annealing Algorithm

With the development of Internet technology and computer graphics,the application of three-dimensional model is becoming more and more wide.How to retrieve models needed by users quickly and accurately from massive database is a difficult and hot problem in field of model retrieval.In order to solve the problem of model retrieval,this thesis researches on CAD model model similarity calculation based on greedy algorithm,simulated annealing algorithm and genetic annealing algorithm.By comparing experiment data of greedy algorithm,simulated annealing algorithm and genetic annealing algorithm,we will conclude that genetic annealing algorithm can evaluate similarity between two models more effectively.The main contents of this thesis can be divided into the following parts:Firstly,this thesis briefly introduces research status of model similarity calculation at home and abroad.Feature extraction and representation methods of three-dimensional models are briefly introduced.At the same time,feature extraction method and retrieval method of CAD models are listed.Summarize problems in CAD model similarity calculation and discuss some related solutions.Secondly,model similarity calculation method used in this thesis is introduced in detail.Shape similarity between source model face and target model face is computed based on the difference of face's edge number.According to faces' shape similarity and adjacency relationship,structure similarity of faces is calculated.Global similarity matrix of two models is constructed based on shape similarity of faces and structure similarity of faces.Optimization algorithm is used to find an optimal matching sequence of faces between two models.Based on this optimal matching sequence of faces,two models' global similarity is calculated.In this thesis,greedy algorithm,simulated annealing algorithm and genetic annealing algorithm are used to search optimal face matching sequence between two models.At the same time,the process of matching faces is given.Finally,the principle of greedy algorithm,simulated annealing algorithm and genetic algorithm are analyzed.The selection of solution vectors of Metropolis criterion and the essence of Markov chain in simulated annealing algorithm are introduced in detail.The methods of selecting operator,crossover operator and mutation operator in genetic algorithm are listed.Aiming at the shortcomings of simulated annealing algorithm,this thesis combines the global search ability of genetic algorithm and the local search ability of simulated annealing algorithm,and applies genetic annealing algorithm to the calculation process of 3D model similarity.For the repeated elements and cross-boundary elements produced in the process of surface matching vector updating,a detailed treatment scheme is given.Experimental results show that compared with greedy algorithm and simulated annealing algorithm,the proposed method in this thesis can measure the difference between two models accurately.