% 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.
\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{Scale-Space Representation of 3D Models and Topological Matching}
%\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}
Reeb graphs have been shown to be effective for topology matching of
3D objects. Their effectiveness breaks down, however, when the
individual models become very geometrically and topologically
detailed---as is the case for complex machined parts. The result is
that Reeb graph techniques, as developed for matching general shape
and computer graphics models, produce poor results when directly
applied to create engineering databases.
This paper presents a framework for shape matching
through scale-space decomposition of 3D models. The
algorithm is based on recent developments in efficient hierarchical
decomposition of metric data using its spectral properties.
Through spectral decomposition, we reduce the problem of
matching to that of computing a mapping and distance measure between
vertex-labeled rooted trees. We use a dynamic programming scheme to
compute distances between trees corresponding to solid models.
Empirical evaluation of the algorithm on an extensive set of 3D
matching trials demonstrates both robustness and efficiency of
the overall approach.
\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.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Feature Decomposition
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Feature Decomposition}
\label{sec:segmentation}
During the last decade, hierarchical segmentation has become recognized
as a very powerful tool for designing efficient algorithms. The most
common form of such hierarchical segmentations is the scale-space
decomposition in computer vision. Intuitively, an inherent property of
real-world objects is that they only exist as meaningful entities over
certain ranges of scale. This fact, that objects in the world appear
in different ways depending on the scale of observation, has important
implications if one aims at describing them. Specifically, the need
for multi-scale representation arises when designing methods for
automatically analyzing and deriving information from real-world
measurements.
In the context of solid models, the notion of scale can be simplified
in terms of the levels for the 3D features. The notion of {\em
feature} in this sense draws from the computer vision literature
rather than the CAD literature. Namely, given an object $\M$, we are
interested in partitioning $\M$, into $k$ features $\M_1$,...,$\M_k$,
with $\M_i\cap \M_j=\emptyset$, for $1\le i