当前位置:首页 >> 能源/化工 >>

IEC-Based 3D Model Retrieval System


IEC-Based 3D Model Retrieval System
Seiji Okajima and Yoshihiro Okada

Abstract. Recently, 3D CG animations have become in great demand for movie and video game industries. As

a result, many 3D model and motion data have been created and stored. In this situation, we need any tools that help us to ef?ciently retrieve required data from such a pool of 3D models and motions. The authors have already proposed a motion retrieval system using Interactive Evolutionary Computation (IEC) based on Genetic Algorithm (GA). In this paper, the authors propose a 3D model retrieval system using the IEC based on GA and clarify the usefulness of the system by showing experimental results of 3D model retrievals practically performed by several users. The results indicate that the proposed system is useful for effectively retrieving required data from a 3D model database including many data more than one thousand.

1 Introduction
Recently, there has been the great demand for 3D CG animations in video game industries and movie productions. For the creation of 3D CG animations, the character design is very important factor but very time-consuming, laborious work. It is signi?cant to reuse already existing data to create new data by modifying them. Therefore, we are interested in providing 3D multimedia data retrieval systems that enable 3D CG creators to effectively retrieve their required data. 3D CG animation mainly consists of texture image data, 3D model data and motion data. Although there have been many researches on image data retrieval and search systems so far, there have been very few researches on motion data retrieval and search systems. We have already proposed a motion retrieval system using
Seiji Okajima · Yoshihiro Okada Graduate School of ISEE, Kyushu University, 744, Motooka, Nishi-ku, Fukuoka, 819-0395 Japan e-mail: seiji.okajima@inf.kyushu-u.ac.jp, okada@inf.kyushu-u.ac.jp

T. Watanabe et al. (Eds.): Intelligent Interactive Multimedia: Systems & Services, SIST 14, pp. 317–327. c Springer-Verlag Berlin Heidelberg 2012 springerlink.com

318

S. Okajima and Y. Okada

Interactive Evolutionary Computation [20]. This system allows the user to retrieve motion data similar to his/her required data easily and intuitively only through the evaluation repeatedly performed by scoring satisfaction points to retrieved motion data without entering any search queries. The IEC method of the system is based on Genetic Algorithm, so that motion data should be represented as genes used as similarity features for the similarity calculation in the system. This IEC-based retrieval system is very signi?cant especially in the cases that users do not have any query data can be entered to the system and they only have images of required data in their mind. Recently, we have applied the IEC method based on GA to a 3D model retrieval system. In this paper, we propose the 3D model retrieval system and introduce 3D model features we employed in the system used for the similarity calculation among 3D models. We also clarify the usefulness of the proposed 3D model retrieval system by showing experimental results of 3D model retrievals practically performed by several users. The results indicate that the proposed system is useful for effectively retrieving required data from a 3D model database including many data more than one thousand. The remainder of this paper is organized as follows: First of all, Section 2 introduces the IEC method based on GA. Section 3 describes related works. Next Section 4 introduces 3D model features we employed to use as their gene representation for GA. After that, Section 5 describes how our proposed 3D model retrieval system works. Furthermore, in Section 6, we describe user experiments and show their results to clarify the usefulness of the system. Finally, we conclude the paper in the last section.

2 IEC Method Based on GA
In this section, we explain Interactive Evolutionary Computation (IEC) based on Genetic Algorithm (GA). IEC is a general term for methods of evolutionary computation that use human interactive evaluation to obtain optimized solutions [17]. In the IEC method, ?rst of all, a system presents some candidate solutions to the user, and then the user evaluate them by giving a numerical score depending on his/her requirement. After that, the system again presents some solutions more suitable for the user requirement solved by a certain algorithm like GA. After several trials of this operation, the user obtains his/her most desirable solution. Since, in this way, the IEC method is intuitive and useful to deal with problems depending on human feelings, we decided to employ the IEC method based on GA for our 3D model retrieval system.

3 Related Works
There are many researches on 3D model search and retrieval systems. In general, 3D model search systems are regarded as similarity search systems for retrieving 3D model data similar to the 3D model entered as the search query. For similarity

IEC-Based 3D Model Retrieval System

319

search systems, the choice of what kinds of features as their similarity measures is signi?cant because it affects the search performances of the systems. There are several kinds of similarity features of 3D model data, i.e., parameter based features, graph based features and the others. There are some parameter based features of 3D model data have been proposed so far. Osada et al. proposed D2 shape distribution represented as a histogram of distances between any two random points on a 3D model surface [14]. Vandeborre et al. proposed curvature histogram that is a histogram of curvature values about randomly sampled points on a 3D model surface. [19] Elad et al. proposed geometric moment that is a moment of a 3D shape model [5]. Also, there are some graph based features of 3D model data have been proposed so far. McWherter et al. proposed Model Graph is a graph constructed from the component structure of a 3D model [10]. Hilaga et al. proposed the topology matching method for 3D model similarity search that uses reeb graphs of 3D models as similarity features of them [8]. As the other kinds of similarity features of 3D model data, there are appearance based features represented as 2D images. Assfalg et al. proposed to use signatures of spin images of 3D models as their similarity features [1]. Chen et al. proposed light ?eld descriptor based on silhouette images of 3D models [3]. Ohbuchi et al. proposed to use Salient Visual Feature of 3D models as their similarity features [12]. On the other hand, in general, 3D model retrieval systems are regarded as similarity search systems for retrieving 3D model data similar to the 3D models the user wants speci?ed by his/her interactive operations like selection of candidate data or browse a whole database. For browsing based data retrieval systems, how to present candidate data to the user, i.e., layout algorithms and visualization methods, is signi?cant in order to enable the user to ?nd his/her required data as fast as possible. As layout algorithms based on hierarchical structure of a database, there are tree-maps, hyperbolic trees, cone trees, etc. As dimensionally reduction methods for similarity feature based layouts, there are multidimensional scaling, principal component analysis, self-organizing maps, etc. As one of the data retrieval systems through the user’s interactive operations, there are several systems using IEC method. IEC is proposed as the interactive calculation method that the user evaluates target data interactively, and ?nally the system outputs optimized solution based on its evaluated values. The remarkable point where IEC is useful is that the necessitated operation is only the evaluation against data by the user. There are some experimental systems as IEC based retrieval systems. Takagi et al., Cho et al. and Lai et al. proposed an image and music retrieval system using Interactive Genetic Algorithm (IGA) [16, 4, 9]. Yoo et al. proposed video scene retrieval based on emotion using IGA [21]. Cho et al. proposed a music retrieval system using IGA [4]. However, there is not any 3D model retrieval system using IEC that retrieves and presents model data according to the user requirement from a model database. In this paper, we propose such a 3D model retrieval system using IEC method based on GA. In GA, 3D models should be represented as their genes and we employ D2 shape distribution and curvature histogram as similarity features of 3D models used for their gene representations

320

S. Okajima and Y. Okada

from the following reasons. In general, the graph matching needs the higher calculation cost so that graph based similarity features are not suitable for interactive systems like ours. D2 shape distribution marks good performances about not only the similarity calculation cost but also the similarity accuracy. Furthermore, curvature histogram is a completely different kind of similarity feature from D2 shape distribution so that the combined use of them can compensate their weakness each other.

4 3D Model Features for Genetic Algorithm
As described above, we have been developing a 3D model retrieval system using IEC based on GA. To use GA, it is necessary to regard 3D models as their corresponding genes represented as similarity features. In this section, we describe 3D model features we employed and genetic operations performed in the system.

4.1 3D Model Data File Format
There are several types of 3D model data, i.e., polygonal model data (= surface model data), CSG(Constructive Solid Geometry) data and Voxel (Volume cell) data. Since polygonal model data are very popular for 3D CG contents, we employ polygonal model data for our proposed 3D model retrieval system. Polygonal model data mainly consists of vertices information and faces information. There are several ?le formats for polygonal model data. For example, Stanford Triangle Format ?le format (PLY) is employed by Stanford University, Wavefront OBJ ?le format is employed by Wavefront Technologies Inc. and 3ds ?le format is employed by Autodesk Inc. Our 3D model database used for the experiment of user evaluation explained in Sec. 6 is collected from the collection of Princeton University. Their ?le format (OFF) is very similar to PLY.

4.2 D2 Histogram (Shape Distribution) and Curvature Histogram
As 3D model features, we employ D2 histogram (Shape Distribution) and curvature histogram. Shape Distribution means a histogram of distances between any two random points on a 3D model surface and it can be used as the feature value of the model for similarity searches. Fig. 1 shows histograms of three typical shaped models obtained by applying D2 method, the histogram extraction operation for Shape Distribution. Each of (a), (b) and (c) corresponds to each of a sphere, a cylinder and a torus shaped models, respectively. As shown in the ?gure, typical shaped models have a different histogram from each other. So, the dissimilarity between two 3D models can be calculated as the error between their two D2 histograms.

IEC-Based 3D Model Retrieval System

321

Fig. 1 D2 histograms of typical shaped models, a sphere (left), a cylinder (middle) and a torus (right).

Fig. 2 Curvature histograms of typical shaped models, a sphere (left), a cylinder (middle) and a torus (right).

Curvature histogram is obtained as a histogram of curvature values of randomly sampled vertices on a 3D model surface. In this paper, we use approximate gaussian curvature for the curvature value. Curvature histogram nicely represents detail information about the surface of a 3D model. Fig. 2 shows histograms of three typical shaped models obtained by applying the curvature histogram method. These two histograms are normalized to make their bin width and range the same.

4.3 Gene Representation
We represent 3D models as their corresponding genes using the D2 and curvature model features. So, 3D models are represented as a combination histogram of D2 and curvature histograms. A chromosome, a gene and an allele are represented as a real vector, a real number and a real value, respectively. For similarity measure of chromosomes, we choose the bhattacharyya distance as a measure of gene similarity. Let x and y be feature vectors. Then the bhattacharyya distance d is de?ned as n √ (1) d(x, y) = ? log(∑ xy).
i

4.4 Genetic Operations
For selection algorithm, we employ roulette wheel selection algorithm [2] in our system because this is often used in many cases. This selection algorithm calculates

322

S. Okajima and Y. Okada

probabilities that individuals are selected by GA. We de?ne fi is a ?tness value. The probability pi of the individual i selected by GA is calculated by pi = fi N ∑k=1 fk . (2)

In addition, this expression assumes that a ?tness value is positive. When the ?tness value of an individual is higher, the probability of it becomes higher. If some ?tness values are too high rather than others, it causes early convergence which the search settles in the early stages. There are some crossover operators for real-coded GA such as BLX-α [6, 7], UNDX [13], SPX [18] and so on. In this study, we employ BLX-α because of its simplicity and fast convergence. Let C1 = (c1 , ..., c1 ) and C2 = (c2 , ..., c2 ) be parents n n 1 1 chromosomes. Then, BLX-α uniformly picks new individuals with a number of the interval [cmin ? I · α , cmax ? I · α ], where cmax = max(c1 , c2 ), cmin = min(c1 , c2 ), and i i i i I = cmax ? cmin . For a mutation operator, we choose the random mutation operator [7, 11] because this is often used in many cases. Let C = (c1 , ..., ci , ..., cn ) be a chromosome and ci ∈ [ai , bi ] be a gene to be mutated. Then, ci is an uniform number picked from the domain [ai , bi ].

5 3D Model Retrieval System
In this section, we explain our proposed IEC-based model retrieval system. Fig.3 and Fig.4 show the overview and a screen snapshot of the 3D model retrieval system, respectively. As the preprocessing, the system generates genes as a database each of which corresponds to each data of the 3D model database. After that, the system retrieves 3D models according to the following steps (Fig.3): 1) The system randomly generates initial genes. 2) The system enters the genes as search queries in the database. 3) The database retrieves the 3D models corresponding to the queries. 4) The system receives the results of the 3D model retrieval. 5) The system displays retrieved models to the user. 6) The user evaluates each of displayed models by three stage scoring, i.e., good, normal and bad. This evaluation is performed only by mouse clicks on the thumbnails of the 3D models. 7) After the evaluation, the system applies GA operations, i.e., selection, crossover and mutation to the genes in order to generate the next generation of genes. 8) Repeat Step 2 to Step 7 until the user is satis?ed with the retrieval results. After several trials of these process, the user can obtain his/her most desirable models without any dif?cult operations and without entering any query models.

IEC-Based 3D Model Retrieval System

323

Fig. 3 Overview of 3D model retrieval system.

Fig. 4 Screenshot of 3D model retrieval system.

6 User Experiment
In this section, we present experimental results about 3D model retrievals performed using the proposed system by several subjects. Five students in Graduate School of ISEE, Kyushu University volunteered to participate in this experiment. The experiment was carried out on a standard PC with Windows XP Professional, a 2.66 GHz Core 2 Quad processor and 4.0 GB memory. As a 3D model database for the experiment, we employed Princeton Shape Benchmark [15]. It contains around 1800 model data collected from the World Wide

324

S. Okajima and Y. Okada

Web. As for the GA operators, we employed roulette wheel selection operator, BLXα crossover operator and random mutation operator. The value of α is 0.5, crossover rate is 1.0 and mutation rate is 0.01. The ?tness values of three stage scoring are 2.0 for good, 0.5 for normal and 0.05 for bad. Also, the population size is 12 determined from the results of our previous study [20]. In the experiment for evaluating the usefulness of our proposed system, the participants retrieved each of ?ve target models using the system. The ?ve target models were selected one by one from each of ?ve class models that are tire, car, dolphin, plant and human head. Each participant tried to search each of ?ve target models until 20 generations, and then, we obtained 25 trial results totally for the all participants. We measured computation and operation times, and we explored retrieved models. These trials were carried out according to the following procedure. 1. Introduction of the model retrieval system (1 minute). 2. Try to use the system for answering preparation questions (3 minutes). 3. Actual searches for target models using the system.

6.1 Performance Evaluation
We tried to measure an actual computation time spent for one GA operation and an average user operation time. First, the time spent for one GA operation is less than ten milliseconds and the average retrieval time to present next generation is 0.62 seconds in the case of about 1800 model data in a database. So, the user manipulates the system without feeling any impatience. Second, the average user operation time until 10, 15 and 20 generations are 119.3 seconds, 177.0 seconds and 233.5 seconds, respectively. Therefore, it can be said that our system allows the user to search his/her desirable models in a reasonable time.

6.2 Retrieval Results
Next, we explored retrieved models and categorized the results of trials into three types: 1) Retrieval of the same model as a target model, 2) Retrieval of the same class model as a target model, 3) Retrieval failure. Table. 1 shows the classi?cation of retrieved model results. Result 1) can be judged from a corresponding ?le name. Result 2) and 3) are judged from descriptions of Princeton Shape Benchmark. Also, Fig. 5 shows change of cumulative number of cases that same class or same 3D models are retrieved.
Table 1 Types of retrieved model results. Number of Results 1) Retrieval of the same model as a target model 11 2) Retrieval of the same class model as a target model 14 3) Retrieval failure 0 Sum 25

IEC-Based 3D Model Retrieval System

325

Fig. 5 Counts of cases that same class or same 3D models are retrieved at each generation.

From these table and chart, it is said that the system retrieve same class 3D models as the desirable model before 20th generation, and in many cases, the user retrieves same class 3D models before 10th generation. These results indicate that our proposed system is practically useful for retrieving 3D model data even in the case of a huge database including many data more than one thousand.

7 Conclusion and Remarks
In this paper, we proposed the 3D model retrieval system using IEC based on GA. Our proposed system allows the user to retrieve 3D models similar to his/her required models easily and intuitively only through the interactive operation of evaluating retrieved models without any dif?cult operations. Furthermore, we performed user experiment for evaluating the usefulness of our proposed 3D model retrieval system. The results indicate that our proposed system is useful for effectively retrieving 3D model data even in a huge database including many data more than one thousand. As future work, we will investigate more ef?cient similarity features of 3D models for improving the performance of our proposed model retrieval system. In addition, we will improve GUI of the system to make it more useful.

References
1. Assfalg, J., Del, B.A., Pala, P.: Spin images for retrieval of 3D objects by local and global similarity. In: Proc of the 17th International Conference on Pattern Recognition, ICPR 2004 (2004), doi:10.1109/ICPR.2004.1334675 2. Baker, J.E.: Reducing bias and inef?ciency in the selection algorithm. In: Proc. of the Second International Conference on Genetic Algorithms on Genetic Algorithms and their Application, pp. 14–21 (1987)

326

S. Okajima and Y. Okada

3. Chen, D.Y., Tian, X.P., Shen, Y.T., Ouhyoung, M.: On visual similarity based 3D model retrieval. In: Proc. of Eurographics Computer Graphics Forum, EG 2003 (2003), doi:10.1111/1467-8659.00669 4. Cho, S.B.: Emotional image and musical information retrieval with interactive genetic algorithm. Proc. of the IEEE 92(4), 702–711 (2004), doi:10.1109/JPROC.2004.825900 5. Elad, M., Tal, A., Ar, S.: Content based retrieval of VRML objects - an iterative and interactive approach. EG Multimedia, 97–108 (2001) 6. Eshelman, L.J., Schaffer, J.D.: Real-Coded Genetic Algorithms and Interval-Schemata. In: Foundations of Genetic Algorithms 2, pp. 187–202. Morgan Kaufman Publishers, San Mateo (1993) 7. Herrera, F., Lozano, M., Verdegay, J.L.: Tackling Real-Coded Genetic Algorithm: Operators and Tools for Behavioural Analysis. Journal of Arti?tial Intelligence Review 12(4), 265–319 (1998), doi:10.1023/A:1006504901164 8. Hilaga, M., Shinagawa, Y., Kohmura, T., Kunii, T.L.: Topology matching for fully automatic similarity estimation of 3D shapes. In: Proc. of the 28th Annual Conference on Computer Graphics and Interactive Techniques, SIGGRAPH 2001 (2001), doi:10.1145/383259.383282 9. Lai, C.-C., Chen, Y.-C.: Color Image Retrieval Based on Interactive Genetic Algorithm. In: Chien, B.-C., Hong, T.-P., Chen, S.-M., Ali, M. (eds.) IEA/AIE 2009. LNCS, vol. 5579, pp. 343–349. Springer, Heidelberg (2009), doi:10.1007/978-3-642-025686 35 10. McWherter, D., Peabody, M., Regli, W.C., Shokoufandeh, A.: Solid Model Databases: Techniques and Empirical Results. Journal of Computing and Information Science in Engineering (2001), doi:10.1115/1.1430233 11. Michalewicz, Z.: Genetic Algorithms + Data Structures = Evolution Program. Springer (1994) 12. Ohbuchi, R., Osada, K., Furuya, T., Banno, T.: Salient local visual features for shapebased 3D model retrieval. In: IEEE International Conference on Shape Modeling and Applications 2008 (2008), doi:10.1109/SMI.2008.4547955 13. Ono, I., Kobayashi, S.: A real-coded genetic algorithm for function optimization using the unimodal normal distribution crossover. In: Proc. of the Seventh International Conference on Genetic Algorithms, pp. 246–253 (1997) 14. Osada, R., Funkhouser, T., Chazelle, B., Dobkin, D.: Shape distributions. Journal of ACM Transactions on Graphics (TOG) 21(4) (2002), doi:10.1145/571647.571648 15. Shilane, P., Min, P., Kazhdan, M., Funkhouser, T.: The Princeton Shape Benchmark. In: Proc. of Shape Modeling Applications 2004 (2004), doi:10.1109/SMI.2004.1314504 16. Takagi, H., Cho, S.B., Noda, T.: Evaluation of an IGA-based image retrieval system using wavelet coef?cients. In: IEEE International Conference on Fuzzy Systems (1999), doi:10.1109/FUZZY.1999.790176 17. Takagi, H.: Interactive Evolutionary Computation: Fusion of the Capacities of EC Optimization and Human Evaluation. Proc. of the IEEE 89(9), 1275–1296 (2001), doi:10.1109/5.949485 18. Tsutsui, S., Yamamura, M., Higuchi, T.: Multi-parent Recombination with Simplex Crossover in Real Coded Genetic Algorithm. In: Proc. of the 1999 Genetic and Evolutionary Computation Conference (GECCO 1999), pp. 657–664 (1999), doi:10.1007/3540-45356-3 36

IEC-Based 3D Model Retrieval System

327

19. Vandeborre, J.P., Couillet, V., Daoudi, M.: A practical approach for 3D model indexing by combining local and global invariants. In: Proc. of 1st International Symposium on 3D Data Processing Visualization and Transmission, pp. 644–647 (2002), doi:10.1109/TDPVT.2002.1024132 20. Wakayama, Y., Okajima, S., Takano, S., Okada, Y.: IEC-Based Motion Retrieval System Using Laban Movement Analysis. In: Setchi, R., Jordanov, I., Howlett, R.J., Jain, L.C. (eds.) KES 2010. LNCS (LNAI), vol. 6279, pp. 251–260. Springer, Heidelberg (2010), doi:10.1007/978-3-642-15384-6 27 21. Yoo, H.W., Cho, S.B.: Video scene retrieval with interactive genetic algorithm. Multimedia Tools and Applications(2007), doi: 10.1007/s11042-007-0109-8


相关文章:
3090411002-罗莹-数据挖掘
Yang[1] defines that a basic content-based 3D model retrieval system should contain several parts, including feature ext raction, similarity search and ...
英文翻译1
3. Integrate the surface model retrieval system with CBR methodology to ...[39] developed a technique based on a graphic representation of 3D model ...
立体模型动画检索系统软件设计 论文
3D model retrieval system software design of animation Abstract 3D model ...A shadow handler in a video-based real-time traffic monitoring system. In...
基于Flexsim的自动化立体仓库仿真与优化
3D model of Automatic Storage & Retrieval System is build on the basis of...Bo Yan(2009)在《AS/RS Simulation and Optimization Based on Flexsim》一文...
Matching 3D Models with Shape Distributions
Matching 3D Models with Shape Distributions_互联网_IT/计算机_专业资料。对...objectrecognition system or in an interactive content-based retrieval ...
生物信息期末考试重要文件
Based within the National Library of Medicine at ...component of the NCBI's Entrez retrieval system....using Cn3D, an interactive 3D graphic modeling ...
三角网格曲面可视轮廓提取的快速算法
3D Face Authentication and Recognition Based in ...Method for 3D model retrieval using circle ray ...Journal of System Simulation, 2006,18(10):2847~...
CAD模型局部区域分割与检索技术研究
The popularity of three-dimensional (3D) CAD systems in industry has ...(3) Global and partial retrieval approach for CAD models based on multi-...
三维船体曲面模型的信息获取与管理
3D design of Parasolid solid modeling based on ...On this basis, through the system integration and... retrieval, add or delete operation, as well as...
三维图形的表达和分析及其在三维仿真和模型检索中的应用
system: From computational strategies to a complete clinical validation.Medical...“3D Model Retrieval with Morphing-based Geometric and Topological Feature ...
更多相关标签:
retrieval system | agent based model | model based | model based design | energy based model | part based model | tree based model | model based test |