=Paper=
{{Paper
|id=Vol-210/paper-9
|storemode=property
|title=Ontology Based Shape Annotation and Retrieval
|pdfUrl=https://ceur-ws.org/Vol-210/paper9.pdf
|volume=Vol-210
|dblpUrl=https://dblp.org/rec/conf/ecai/SymonovaDUA06
}}
==Ontology Based Shape Annotation and Retrieval==
https://ceur-ws.org/Vol-210/paper9.pdf
Ontology Based Shape Annotation and Retrieval
Olga Symonova and Minh-Son Dao and Giuliana Ucelli and Raffaele De Amicis 1
Abstract. In this paper, 3D shape retrieval methodology suited for 3D shapes are annotated and become well-defined structure under
search in special category of 3D shape is presented. The proposed human-perspective.
approach employs a fully unsupervised segmentation algorithm to
decompose 3D models into components. Shape distribution vectors
describing the resulting components are extracted and together with
2 PROPOSED METHODOLOGY
connectivity relations identify a 3D model. The 3D-shapes we are in- 2.1 Problem of shape similarity and appropriate
terested in this paper are models of furniture. Ontology of furniture assumptions
that we started building will be used in annotation and then key word
Content retrieval is a difficult task which is affected by the prob-
based retrieval of furniture models. A mapping between low level
lem of ambiguity of words and shapes. It can be explained by va-
features extracted by the above mentioned algorithm and ontology
riety of words, images and 3D models which have equal or similar
concepts is performed. The proposed approach bridges the gap be-
spelling, shape but different meaning in different domains. This task
tween keyword-based approaches and query-by-example approaches
became even more complicated while dealing with 3D models. The
by using not only the low-level features but also a domain ontology.
file containing a 3D model often lacks any description, its name can
be ambiguous, misleading or not carrying any useful information. As
1 INTRODUCTION a result descriptors containing geometrical and/or topological infor-
mation are defined to be used in shape retrieval. The research in this
Shape description and retrieval problem arose with the growth of field has proved that searching 3D graphical objects using words has
available information in Internet and development of technologies worse results than while using shape descriptors [13]. However shape
allowing easy creation of 3D models. However modern search en- descriptors do not solve the problem of shape ambiguity. According
gines allow only textual search of information in Internet. This ap- to the domain where a model is used, it can have different semantic
proach is not effective for graphical objects [13]. Special structures meaning, e.g. the model with the shape of human hand can be con-
describing geometrical and/or topological characteristics were sug- sidered as a part of human body in the domain of human models or as
gested to substitute verbal description of a shape. The authors of a glove in the domain of clothing models. To solve similar problems
[15] group shape descriptors into three large groups: feature based existing in natural language (like words with different meanings) the
methods, graph based methods and other methods which can be as current research suggests to build ontologies of different domains
well compositions of the former two approaches. We refer interested and interpret a word within the chosen domain. In order to transfer
reader to [14], [11], [17], [8], [3]. In our work we use the shape de- this approach to the field of shape retrieval we build ontology for
scriptor proposed in [14]. The descriptor is a vector of the distribution 3D models, assuming that a model can be completely described by
of the function defined over the shape. As the authors of [14] exam- connectivity relations between its constituents and their shape. Re-
ined D2 function of the distance between two random points of the stricting our models’ domain to the one of furniture, we explain how
shape gives the best results. The shape distribution based descriptor we build the ontology of furniture, how we extract feature vectors
can be used for categorizing 3D models into wide classes, because it from shapes, and using the latter, how we annotate the model and
is able to detect major differences between shapes, but cannot capture retrieve 3D objects within the same category.
detailed features. According to the chosen furniture domain we can assume that
Although geometry and topology based descriptors have improved models are created using Constructive Solid Geometry (CSG) ap-
content based 3D shape retrieval, they still deal with low-level fea- proach. Thus the furniture models are assemblies of meaningful
tures and this leads to a big gap between low-level and high-level atoms that are similar to geometric primitives. To prove that this
features. Moreover, geometrical-based matching does not consider assumption does not constrict too much the number of 3D models
the semantics of the object to be retrieved [12]. which can be used in the proposed approach we performed a search
The research in the field of knowledge structuring suggests to use of 3D furniture models in Internet. We downloaded 98 furniture mod-
ontology for describing knowledge of a chosen domain. [5]. The els from Princeton Shape Benchmark [2] and Free Stuff of 3D Cafe
author of [7] defines ontology as a specification of a representa- [1]. After analysis we found that 63% of furniture models are com-
tional vocabulary for a shared domain of discourse which may in- pound models (here we notice that 88% of models from Princeton
clude definitions of classes, relations, functions and other objects. Benchmark are compound), and 75% of compound models are mod-
Therefore, if we know the domain in which the 3D shapes are con- els composed from geometrical primitives. We suppose that these fig-
structed, the ontology of the domain can be built. Then mapping be- ures can increase when a 3D database is created by designers from
tween low level features and ontology concepts is performed. Finally, the same industrial domain. As consequence our assumptions will
be valid for the majority of CAD models, because assembly mod-
1 GraphiTech, 38050 Villazzano (TN), Salita Dei Molini 2, Italy
elling is effective approach, which allows designers to work together
Figure 1. Geometrical primitives used for composition of 3D models and
their shape distributions. Figure 2. Feature vector extraction. 1) Input model. 2) Model decomposi-
tion. 3) Shape distributions of the model’s constituents. 4) Labelling model’s
on a complex model and gives a possibility of the further reuse of constituents as shape primitives. 5) Output feature vector.
designed objects.
ues of angles between model constituents where n is the number of
2.2 Feature vector extraction connected components.
To clarify the shape analysis process we consider the example of a
Given a query 3D model we start analyzing it. Considering the as- 3D model of a table. Figure 2 shows this process. As a result we pass
sumption that models are compositions of conceptual parts, we start the feature vector identifying the query model to the Table 1, which
the model analysis from its decomposition into the constituents. We describes the ontology of the domain . In the next chapter we explain
load the triangle mesh, representing the given model, and then we how having the feature vector we obtain the vector of semantic labels.
perform its decomposition into connected components. The decom-
position process has the complexity O(|V | + |E|). Then we analyze
the shape of each constituent of the model using the approach sug- 2.3 Mapping feature vector to semantic labels
gested in [14]. For each constituent we construct the vector of shape using knowledge domain
distribution. The choice of using a descriptor based on shape distribu- In order to map geometrical and topological features of an object
tion is determined by simplicity of construction, invariance to affine from a specific domain to semantically meaningful constituents of
transformations and good discriminative results for the models sim- the object we should create a database describing all models of the
ilar to geometrical primitives, like cubes, spheres, cylinders, etc [9]. domain. Table 1 illustrates the description of the models of the table
According to the assumptions stated before, we consider models that of Figure 2.
are the compositions of geometrically simple objects. As a conse-
quence we can build the finite set of the geometric primitives, which
can be used to construct CAD models. For each of such geometri- Table 1. Mapping from low-level features to semantic labels.
cal primitives we extract the distribution based shape descriptor, and Component Geometrical Connectivity Semantic
primitive (pairwise label
we label primitives with the corresponding name. At this stage the angle between
construction of the database of geometrical primitives and labeling components
them with corresponding names are done manually. The number of 1 rect sheet {90,90,90,90} top
geometrical primitives which can be used for the composition of fur- 2 rect rod {90,0,0,0} leg
niture model is finite, thus once the database has been constructed it 3 rect rod {90,0,0,0} leg
4 rect rod {90,0,0,0} leg
can be used later without user intervention. Figure 1 illustrates which
5 rect rod {90,0,0,0} leg
geometric primitives we have considered along with their shape de-
scriptions. Having decomposed the given 3D model into constituents,
we start to compare each part with geometrical primitives from Fig-
The database should describe all concepts present in the ontology
ure 1. The smallest distance between the vectors of shape descriptors
of the domain. Thus, querying it by the feature vector we can output
identifies the shape of the analyzed constituent. In the current work
as a result the vector of semantic labels. For instance taking the model
we calculate Euclidean distance; however the other types of metrics,
of the table of the previous example, we get {top,leg,leg,leg,leg}, and
like Earth Mover and the Kolmogorov-Smirnov distances [14] can
we can pass the given semantic vector to the domain ontology in
be used. The constituent inherits the label with the name of the most
order to identify the category the model belongs to.
similar geometric primitive. The process continues for all parts of
the model. As a result we output the vector, which has as compo-
nents the names of constituent parts of the query model. For better 2.4 Ontology for shape annotation
description of the model we also analyze the connectivity relations
between the parts. We compute the principal eigenvectors of the tri- Before building an ontology we should define its scoping, that is its
angulations representing each part of the model and we calculate the domain, and its purpose, that is its intended usage [16]. In our case
angle between them in pairs. In this way we obtain n × (n − 1) val- the domain that our ontology will formalize is that of furniture. In the
first phase the intended usage of the furniture ontology is the anno-
tation of models in the database with ontology concepts. In a second
phase we want to investigate the possibility of retrieving the models
by textual queries. We regard the 3D models as a syntactic domain
and the ontology language as a semantic domain. An interpretation
this way we can say that a certain 3D model is a ”Chair”, while an-
other 3D model is a ”Table”, where ”Chair” and ”Table” are concepts
syntactic level by the feature vectors extracted and explained in the
above sections, there are two interesting questions that an ontology
based shape annotation system should answer:
1. What is the system precision? The precision of the system is de-
MCadn
P = × 100% (1)
where MCadn - is the number of correctly annotated models and
Madn is the number of annotated models. Since the system is still
not fully operational we cannot quantify its precision, but we can
make an interesting observation. The upper boundary of what can
be achieved is already known. If the properties that distinguish two
features that the above component can extract then the system will
that there are in our ontology two concepts named ”YellowChair”
and ”BlueChair”. Both concepts have as their superclass the con-
cept ”chair” and they are distinguished only by the color they
have: respectively yellow and blue. Because the above mentioned
fail to correctly annotate ”BlueChair” and ”YellowChair” mod-
els. However, assuming that for designers the shape of a model is 4
model.
2. The second relevant parameter is the recall of the system.
Madn
R= × 100% (2)
MT
The above OWL representation says that a ”BackRestChair” has
where MT is the total number of models we have. If all models as a part exactly one ”BackRest” and that a ”BackRestChairWith-
are well formed the recall will be 100%. FourLegs” IS-A ”BackRestChair” and has exactly four legs. The
only kind of inference needed in the example is the ”inheritance”
We started building the furniture ontology using Wordnet Domains
of properties from super-classes to their subclasses.
[4]. Developed at IRST, Wordnet Domains, is PWN (Princeton
Wordnet) 1.6 [6] augmented with a set of Domain Labels. PWN
1.6 synsets have been semi-automatically linked with a set of 200 2.5 Retrieval through annotations
domain labels taken from Dewey Decimal classification, the world
most widely used library classification system. The domain labels After we annotated the 3D models with ontology concepts users have
are hierarchically organized and each synset received one or more two possibilities. First they can make retrieval of 3D objects by tex-
domain labels. We are interested in the synsets that are annotated tual query. A query can be typed by the user or can be formed by
with the domain ”furniture”. Because PWN is a linguistic resource ontology browsing. For example a user interested in barber chair
and many concepts found there are not suitable for building an ontol- models can input the concept in a text box. Alternatively he can
ogy of furniture we want to make use in our work of other ontologies browse the ontology and select the appropriate concept. The system
and specialized thesauri. will answer the user query by returning all the models annotated with
We decided to encode our ontology in OWL language. At the mo- the input concept or with a subconcept of the input concept. An en-
ment the ontology is a simple taxonomy enriched with a relation hanced retrieval system based on textual queries can take advantage
”hasPart” that specifies the parts of objects in the furniture domain. of Boolean operators.
We make use also of cardinality restrictions as the following exam- The second possibility is to query by an example model. Here a
ple, which describes the entry for the concepts ”BackRestChair” and user can browse all models within the category of the input model
Back Rest Chair ”BackRestChairWithFourLegs”, shows: and autonomously search for more similar models. Such approach
groups all objects into quite large classes. The other way to search for [10] Cheuk Yiu Ip, Daniel Lapadat, Leonard Sieger, and William C. Regli,
similar models is to find the smallest dissimilarity measure (i.e. the ‘Using shape distributions to compare solid models’, in SMA ’02: Pro-
ceedings of the seventh ACM symposium on Solid modeling and appli-
smallest distance value) between feature vectors of the constituents cations, New York, NY, USA, (2002).
of a sample model and corresponding parts of models from the same [11] Michael Kazhdan, Thomas Funkhouser, and Szymon Rusinkiewicz,
category. Such approach reduces the number of comparisons needed ‘Rotation invariant spherical harmonic representation of 3d shape
to retrieve similar models. Furthermore, as was pointed out in [10] descriptors’, in SGP ’03: Proceedings of the 2003 Eurograph-
the descriptors based on shape distribution do not give good discrim- ics/ACM SIGGRAPH symposium on Geometry processing, Aire-la-
Ville, Switzerland, Switzerland, (June 2003).
inative results for models with detailed shape properties. Decompo- [12] Patrick Min, A 3D Model Search Engine, Ph.D. dissertation, Princeton
sition of the model and shape understanding allows to perform com- University, January 2004.
parison between each constituent part separately. As a result the over- [13] Patrick Min, Michael Kazhdan, and Thomas A. Funkhouser, ‘A com-
all dissimilarity measure will be the sum of dissimilarities between parison of text and shape matching for retrieval of online 3d models’,
in Research and Advanced Technology for Digital Libraries: 8th Euro-
corresponding constituent parts. pean Conference, Bath, UK, (September 2004).
[14] Robert Osada, Thomas Funkhouser, Bernard Chazelle, and David
Dobkin, ‘Matching 3d models with shape distributions’, in SMI ’01:
3 CONCLUSIONS AND FUTURE WORK Proceedings of the International Conference on Shape Modeling & Ap-
In the current work we presented the methodology for the the new plications, Washington, DC, USA, (2001).
[15] Johan W.H. Tangelder and Remco C. Veltkamp, ‘A survey of content
synthesis of shape description and ontology-based annotation and re- based 3d shape retrieval methods’, in Shape Modeling International,
trieval. Performing shape analysis we decompose a 3D model into its Genoa, Italy, (June 2004).
constituent and we analyze the shape and connectivity between each [16] Mike Uschold and Martin King, ‘Towards a methodology for build-
of the parts of the model. As a result we output the feature vector ing ontologies’, in IJCAI95 Workshop on Basic Ontological Issues in
describing the 3D model. Using a database defining all concepts of Knowledge Sharing, Montreal, Canada, (August 1995).
[17] Dejan V. Vranic and Dietmar Saupe, ‘3d shape descriptor based on 3d
the ontology of the given domain (here furniture), we map the ex- fourier transform’, in ECMCS ’01: Proceedings of the EURASIP Con-
tracted feature vector to the vector of semantic labels. Finally, the ference on Digital Signal Processing for Multimedia Communications
ontology of the considered domain will be used in model annotation and Services, Budapest, Hungary, (September 2001).
and then key word based retrieval of furniture models. The proposed
method offers two options to the user: textual query and query by a
sample model. As a result, the proposed method succeeded in term
of shape-to-text (shape annotation) and text-to-shape (query shape by
text) schemes. In the future, the database will be enriched not only
in terms of number of 3D models but also by number of other spe-
cific domains. Beside that, the ontology will be constructed in more
details to improve the accuracy of the query process.
ACKNOWLEDGEMENTS
We thank Eduard Barbu for the useful discussions and comments on
ontology construction.
This work has been supported by the CFP6 IST NoE 506766
AIM@SHAPE.
REFERENCES
[1] 3d cafe. http://www.3dcafe.com.
[2] Princeton shape benchmark. http://shape.cs.princeton.
edu/search.html.
[3] Marco Attene, Silvia Biasotti, and Michela Spagnuolo, ‘Shape under-
standing by contour driven retiling’, The Visual Computer, 19(2-3),
127–138, (2003).
[4] Magnini Bernardo and Cavaglia Gabriela, ‘Integrating subject field
codes into wordnet’, in 2nd International Conference on Language Re-
sources & Evaluation, Athens, Greece, (May-June 2000).
[5] Balakrishnan Chandrasekaran, John R. Josephson, and Richard V. Ben-
jamins, ‘What are ontologies, and why do we need them?’, IEEE Intel-
ligent Systems, 14(1), 20–26, (1999).
[6] Christiane Fellbaum (Ed.). Wordnet: An electronical lexical database.
MIT Press, May 1998.
[7] Thomas R. Gruber, ‘A translation approach to portable ontology speci-
fications’, Knowledge Acquisition, 5(2), 199–220, (1993).
[8] Masaki Hilaga, Yoshihisa Shinagawa, Taku Kohmura, and Tosiyasu L.
Kunii, ‘Topology matching for fully automatic similarity estimation of
3d shapes’, in SIGGRAPH ’01: Proceedings of the 28th annual confer-
ence on Computer graphics and interactive techniques, New York, NY,
USA, (August 2001).
[9] Taesik Hong, Kunwoo Lee, Sungcnan Kim, Chongnam Chu, and Hyun-
chan Lee, ‘Similarity comparison of mechanical parts’, Computer-
Aided Design and Applications, 2(6), 759–769, (2005).