% This is "sig-alternate.tex" V1.3 OCTOBER 2002
% This file should be compiled with V1.6 of "sig-alternate.cls" OCTOBER 2002
%
% This example file demonstrates the use of the 'sig-alternate.cls'
% V1.6 LaTeX2e document class file. It is for those submitting
% articles to ACM Conference Proceedings WHO DO NOT WISH TO
% STRICTLY ADHERE TO THE SIGS (PUBS-BOARD-ENDORSED) STYLE.
% The 'sig-alternate.cls' file will produce a similar-looking,
% albeit, 'tighter' paper resulting in, invariably, fewer pages.
%
% ----------------------------------------------------------------------------------------------------------------
% This .tex file (and associated .cls V1.6) produces:
% 1) The Permission Statement
% 2) The Conference (location) Info information
% 3) The Copyright Line with ACM data
% 4) NO page numbers
%
% as against the acm_proc_article-sp.cls file which
% DOES NOT produce 1) thru' 3) above.
%
% Using 'sig-alternate.cls' you have control, however, from within
% the source .tex file, over both the CopyrightYear
% (defaulted to 2002) and the ACM Copyright Data
% (defaulted to X-XXXXX-XX-X/XX/XX).
% e.g.
% \CopyrightYear{2003} will cause 2002 to appear in the copyright line.
% \crdata{0-12345-67-8/90/12} will cause 0-12345-67-8/90/12 to appear in the copyright line.
%
% ---------------------------------------------------------------------------------------------------------------
% This .tex source is an example which *does* use
% the .bib file (from which the .bbl file % is produced).
% REMEMBER HOWEVER: After having produced the .bbl file,
% and prior to final submission, you *NEED* to 'insert'
% your .bbl file into your source .tex file so as to provide
% ONE 'self-contained' source file.
%
% ================= IF YOU HAVE QUESTIONS =======================
% Questions regarding the SIGS styles, SIGS policies and
% procedures, Conferences etc. should be sent to
% Adrienne Griscti (griscti@acm.org)
%
% Technical questions _only_ to
% Gerald Murray (murray@acm.org)
% ===============================================================
%
% For tracking purposes - this is V1.3 - OCTOBER 2002
\documentclass[dvipdfm,letterpaper]{sig-alternate}
\usepackage{bbm}
\usepackage{subfigure}
\usepackage{amssymb}
\usepackage{epsfig}
\usepackage{algorithm,algorithmic}
%\usepackage{mathptmx}
\usepackage{times}
\usepackage{courier}
\usepackage{helvet}
%%%%%%%%%%%%% macros and definitions.
\newtheorem{conjecture}{Conjecture}
\newtheorem{definition}{Definition}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{observation}{Observation}
\newtheorem{fact}{Fact}
\def\A{{\cal A}}
\def\B{{\cal B}}
\def\D{{\cal D}}
\def\E{{\cal E}}
\def\L{{\cal L}}
\def\M{{\cal M}}
\def\S{{\cal S}}
\def\Q{{\cal Q}}
\def\W{{\cal W}}
\def\SR{{\mathbb{R}}}
\def\MT{{\mathfrak{T}}}
\def\ME{{\mathfrak{E}}}
\def\MP{{\mathfrak{P}}}
\def\MM{{\mathfrak{M}}}
\def\cdim{{\rm cdim}}
\def\a{\alpha}
%\input{definition.tex}
\begin{document}
%
% --- Author Metadata here ---
%\conferenceinfo{WOODSTOCK}{'97 El Paso, Texas USA}
%\CopyrightYear{2002} % Allows default copyright year (2000) to be over-ridden - IF NEED BE.
%\crdata{0-12345-67-8/90/01} % Allows default copyright data (0-89791-88-6/97/05) to be over-ridden - IF NEED BE.
% --- End of Author Metadata ---
\conferenceinfo{SM'03,} {June 16--20, 2003, Seattle, Washington, USA.}
\CopyrightYear{2003}
\crdata{1-58113-706-0/03/0006}
\title{Indexing of 3D Solid Models using Scale-Space and Caterpillar Decompositions}
%\subtitle{[Extended Abstract] \titlenote{A full version of this
%paper is available as \textit{Author's Guide to Preparing ACM SIG
%Proceedings Using \LaTeX$2_\epsilon$\ and BibTeX} at
%\texttt{www.acm.org/eaddress.htm}}
%
% You need the command \numberofauthors to handle the "boxing"
% and alignment of the authors under the title, and to add
% a section for authors number 4 through n.
%
% Up to the first three authors are aligned under the title;
% use the \alignauthor commands below to handle those names
% and affiliations. Add names, affiliations, addresses for
% additional authors as the argument to \additionalauthors;
% these will be set for you without further effort on your
% part as the last section in the body of your article BEFORE
% References or any Appendices.
\numberofauthors{2}
%
% You can go ahead and credit authors number 4+ here;
% their names will appear in a section called
% "Additional Authors" just before the Appendices
% (if there are any) or Bibliography (if there
% aren't)
% Put no more than the first THREE authors in the \author command
\newfont{\smallemail}{phvr at 11pt}
\author{
%
% The command \alignauthor (no curly braces needed) should
% precede each author name, affiliation/snail-mail address and
% e-mail address. Additionally, tag each line of
% affiliation/address with \affaddr, and tag the
%% e-mail address with \email.
$\begin{array}{cccc}
\mbox{\eaddfnt{Dmitriy Bespalov}}^\dag &
\mbox{\eaddfnt{Ali Shokoufandeh}}^\dag &
\mbox{\eaddfnt{William C. Regli}}^{\dag\ddag} &
\mbox{\eaddfnt{Wei Sun}}^\ddag
\end{array}$\\
\\
\affaddr{Department of Computer Science$^\dag$}\\
\affaddr{Department of Mechanical Engineering \& Mechanics$^\ddag$}\\
\affaddr{College of Engineering}\\
\affaddr{Drexel University}\\
\affaddr{3141 Chestnut Street}\\
\affaddr{Philadelphia, PA 19104}
}
\date{30 November 2002}
\maketitle
\begin{abstract}
We have introduced a framework for shape matching through scale-space
decomposition of 3D models. This approach enabled us to construct feature
graphs of objects represented as meshes. Further, by applying hierarchical
graph matching algorithm on the feature graphs we were able to establish
mappings and distance measures between features of different models.
This work presents an efficient indexing mechanism for 3D models in
mesh representation. The indexing mechanism is based on
topological structure of graphs obtained in scale-space
decomposition. The indexing in conjunction with a matching algorithm
will be the major components in a retrieval system for a database of
3D solid models. We measure the performance of our retrieval system
using data available in National Design Repository as well as data
obtained with 3D digitizer.
\end{abstract}
% A category with the (minimum) three required fields
\category{F.2.2}{Non-numerical Algorithms and Problems}{Pattern matching
}
\category{I.3.5}{Computer Graphics}{Computational Geometry and Object
Modeling}
\category{J.6}{Computer-Aided Engineering}{Computer-aided design (CAD)}
\category{H.3.3}{Information Search and Retrieval}{Clustering}.
%A category including the fourth, optional field follows...
\terms{Algorithms Design Theory}
\keywords{Solid modelling, Scale-space, Matching.}
~\\
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Introduction
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Introduction}
\label{sec:introduction}
The problem of 3D object recognition is often formulated as that of
matching configurations of features. Such configurations are often
represented as vertex-labeled graphs, whose nodes represent 3D
features (or their abstractions), and whose edges represent spatial
relations (or constraints) between the features. The relations are
typically geometric or hierarchical, but can include other types of
information. To match two 3D models means to establish
correspondences between their constituting features. In this context,
{\em features} are intrinsic properties of the 3D shape which may
encompass local geometry and topology related to design or
manufacturing operations. To evaluate the quality of a match, one
defines an overall distance measure, whose value depends on
similarities of their graph representations.
Due to the importance of the 3D matching problem in a number of
disciplines, there has been a growing interest in developing efficient
algorithms for matching vertex-labeled graphs. Previous work on 3D
matching (see Section~\ref{sec:related}) has typically focused on the
problem of finding a correspondence between the vertices of two
graphs. However, the assumption of direct graph matching is a very
restrictive one, for it assumes that the primitive features (nodes) in
the two graphs are easy to extract and are invariant in their level of
abstraction. If there is a lesson to be learned from the feature
recognition
community~\cite{HAN-REGLI-PRATT:FEATURES-R-AND-A-2000,SHAH-FEATURE-DISCOURSE:ASME-JCISE-2001},
it is that features are not easy to extract and that they are not
invariant across different domains. This paper presents a wholly new
techniques that goes beyond existing feature-based indexing.
Several existing approaches to the problem of constructing the graph
representations of 3D models suffer from computational inefficiency
and/or from an inability to handle perturbations in models. This
paper seeks a solution to this problem while addressing drawbacks of
existing approaches. Drawing on recently-developed techniques from
the domain of spectral clustering, we have explored an
\emph{efficient} method for mapping a 3D model to a rooted tree. This
mapping not only simplifies the original 3D model representation, but
it \emph{retains important information} about both local (features) as
well as global structure of the model.
%Moreover, the mapping is
%\emph{stable} with respect to noise in the structure of 3D model.
Matching of 3D models can now be reduced to the much simpler problem of matching
rooted trees using a \emph{recursive structural} similarity framework.
We consider one such similarity measure, based on a dynamic
programming framework, and show that the framework realizes the
desired matching between components of the original 3D models. The
result is a more efficient and more stable approach to 3D matching.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Related Work
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Related Work}
\label{sec:related}
Our research aims to bring information retrieval to CAD databases,
enabling them to have indexing and query mechanisms like those
beginning to found in multimedia databases and knowledge management
systems.
\subsection{Comparing Solid Models}
The brief literature in this area consists of results from
engineering, computer science and, in particular, computer vision
communities. Elinson et al.~\cite{ELINSON-NAU-REGLI:SM97}, and
Cicirello and
Regli~\cite{REGLI-CICIRELLO:CAD00,CICIRELLO-REGLI:SM99,CICIRELLO:SOLID-MODEL-RETRIEVAL-99}
examined how to develop graph-based data structures to capture feature
relationships and create heuristic similarity measures among
artifacts. More recent work in~\cite{CICIRELLO-REGLI:SMI-2001}
examined manufacturing feature-based similarity measurement.
Elsewhere, automatic detection of part
families~\cite{DUTTA:ASME-CIE-CONFERENCE-2000} and topological
similarity assessment of polyhedral models~\cite{WYSK:DTC95} has been
examined.
Historically GT coding was the way of indexing of parts and part
families~\cite{SNEAD:89}, this facilitated process planning and
cell-based manufacturing by imposing a classification scheme (a
human-assigned alphanumeric string) on individual machined parts.
While there have been a number of efforts to automate the generation
of GT codes~\cite{AMES:SM91,SHAH89,BOND88,HENDERSON88,HAM96}, none
have been fully transitioned to commercial practice.
\subsection{Comparing Shape Models}
The computer vision and computer graphics research communities has
typically viewed shape matching as a problem in 2D. This has changed
in the past several years with the ready availability of 3D models
(usually meshes or point clouds) generated from range and sensor
data~\cite{DIGITAL-MICHELANGELO-AT-STANFORD}. A considerable body of
work has emerged to interrogate acquired datasets; we briefly review
some of this work.
Thompson et
al.~\cite{THOMPSON-RIESENFELD:DARPA96,UTAH-THOMPSON:IEEE-R-A-REV-ENG-1999}
reverse engineered designs by generating surface and machining feature
information of range data collected from machined parts. Hilaga
et al.~\cite{HILAGA-ET-AL:SIGGRAPH-2001} present a method for matching
3D topological models using Multiresolutional Reeb graphs. A Reeb
graph is a skeletal structure defined by a continuous scalar function
operating on an object. It shares properties similar to medial axes
(in 2D) and medial surfaces (in 3D), however Reeb graphs avoid the
degeneracies that minor surface perturbations can cause to medial
structures. In this work, the Reeb graphs are used to assess
distances among a set of pre-categorized shape models (i.e.,\
airplanes, cars, animals, etc). Other beneficial properties of their
approach include invariance under certain transformations and
robustness under variations in the quality of the models.
Osada et al.~\cite{OSADA-FUNKHOUSER:SMI-2001-ITALY} developed a method
that creates an abstraction the 3D models as probability distribution
of samples from a shape function acting on the model. Specifically,
the measure the similarity between two models by measuring the
similarity between their shape distributions. Shape distributions are
generated by random sampling of points on the surface of the model.
In their paper, they empirically study five different shape functions
and conclude (experimentally) that a function they call {\em D2}
(which measures the distance between two random points on the surface
of a model) results in the best shape classification method. Their
database is a set of 130 shape models in VRML format gathered from the
Internet. Elad et al.~\cite{ELAD:ITERATIVE-INTERACTIVE-RETRIEVAL-01}
introduced both iterative and interactive approach to the problem
of searching a database of 3D models in VRML format.
Cyr and Kimia~\cite{CYR:OBJECT-RECOGNITION-ASPECT-GRAPH-01}
proposed a similarity measure for comparing
two projected 2D views of 3D objects. In fact, they used the same 2D
measure to decompose the viewing sphere of 3D objects in terms of
groups of similar views that in turn can be used to generate the aspect
graph characterization of a 3D objects. They showed the performance of
their system for the task of 3D object recognition in computer vision,
where the main objective is to identify the 3D pose of an object using a
set of characteristic 2D views (view-based 3D object recognition). It is
not clear how this framework can be generalized to measure the
similarity of two distinct objects with similar components.
In computer vision community, the problem of object recognition is
often reformulated as that of matching feature graphs. Several
researchers have developed algorithms that find one-to-one
correspondences between graph nodes. Shapiro and Haralick~\cite{SHA91}
proposed a matching algorithm based on comparing weighted primitives
(weighted attributes and weighted relation tuples) using a normalized
distance for each primitive property that is inexactly matched. Kim
and Kak~\cite{KIM98} used a combination of discrete relaxation and
bipartite matching in model-based \mbox{3-D} object recognition.
Pellilo et al.~\cite{PEL99} devised a quadratic programming framework
for matching association graphs using a maximal clique reformulation,
while Gold and Rangarajan~\cite{Gold:Rangarajan:PAMI} used graduated
assignment for matching graphs derived from feature points and image
curves. Siddiqi et al. combined a bipartite matching framework with
a spectral decomposition of graph structure to match shock
graphs~\cite{SID99}, while Shokoufandeh et al.~\cite{Shoko02} extended
this framework to directed acyclic graphs that arise in multi-scale
image representations. Hancock and his colleagues have also proposed
numerous frameworks for graph matching, including~\cite{Han01}.
For a recent survey on vision and graphics-based matching techniques,
and their limitations, readers are referred
to~\cite{VELTKAMP:SMI-2001-ITALY}. In general, shape matching-based
approaches operate only on the gross-shapes of single parts (not
applicable to considering assembly structures) and does not operate
directly on the solid models or consider semantically meaningful
engineering information (i.e.,\ manufacturing or design features,
tolerances). Retrieval strategies are usually based on a
query-by-example or query-by-sketch paradigm. The Princeton 3D shape
database that has been used in a number of these
studies~\cite{HILAGA-ET-AL:SIGGRAPH-2001,OSADA-FUNKHOUSER:SMI-2001-ITALY}
contains mainly models from 3D graphics and rendering, and not any
models that are specifically engineering, solid modeling or mechanical
CAD oriented.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Construction of Feature Vectors
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Construction of Feature Vectors}
\label{sec:construction}
\subsection{Construction of Feature Trees}
Process of construction of feature trees will go here
\subsection{Construction of Feature Distance Function}
Section will talk about creating distance matrix from
feature tree.
\subsection{Tree Embedding}
\subsection{Mapping Features to Vector Space}
Catterpillar decomposition and spherical coding section
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Indexing
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Indexing}
\label{sec:indexing}
How indexing is done
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Experiments
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Experiments}
\label{sec:exp}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Conclusions & Future Work
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
~\\
\section{Concluding Remarks}
\label{sec:conc}
Conclusions go here
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Acknowledgments
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Acknowledgments}
\label{sec:ack}
This work was supported in part by National Science Foundation (NSF)
CAREER Award CISE/IIS-9733545, NSF Information Technology Research
Award ITR-0219176, and Office of Naval Research Grant
N00014-01-1-0618. Additional support has been provided by Honeywell
FM\&T, Bentley Systems and Lockheed Martin, Naval Electronics and
Surveillance Systems.
Any opinions, findings, and conclusions or recommendations expressed
in this material are those of the author(s) and do not necessarily
reflect the views of the National Science Foundation or the other
supporting government and corporate organizations.
\bibliographystyle{abbrv}
\bibliography{ref,wcrefs,dmitriy}
% sigproc.bib is the name of the Bibliography in this case
% You must have a proper ".bib" file
% and remember to run:
% latex bibtex latex latex
% to resolve all references
%
% ACM needs 'a single self-contained file'!
%
%APPENDICES are optional
%\balancecolumns
%\appendix
%Appendix A
\balancecolumns % GM July 2000
% That's all folks!
\end{document}