% 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]{article} %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}
\setlength{\textwidth}{6.75in} %{6.5in}
\setlength{\topmargin}{-0.5in} %{0.5in}
\setlength{\oddsidemargin}{-0.1250in}
\setlength{\textheight}{9.0in} %{8.5in}
\begin{document}
%\maketitle
%
% --- 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 and Classification of 3D Models}
%\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{
\begin{tabular}{cccc}
{{Dmitriy Bespalov}$^\dag$} & {{Ali Shokoufandeh}$^\dag$} & {{William C. Regli}$^{\dag\ddag}$} & {{Wei Sun}$^\ddag$} \\
\end{tabular}\\ \\
{Department of Computer Science$^\dag$}\\
{Department of Mechanical Engineering \& Mechanics$^\ddag$}\\
{College of Engineering}\\
{Drexel University}\\
{3141 Chestnut Street}\\
{Philadelphia, PA 19104}
}
%
% 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{\today}
\maketitle
\begin{abstract}
This paper presents a framework for shape matching and
classification through scale-space decomposition of 3D models. The
algorithm is based on recent developments in efficient hierarchical
decomposition of a point distribution in metric space $(p,d)$ 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. Lastly, a technique for comparing shape matchers and
classifiers is introduced and the scale-space method is compared
with six other known shape matching algorithms.
\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 modeling, Scale-space, Matching.}
%~\\
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Introduction
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Introduction}
\label{sec:introduction}
This paper presents a new technique for matching of 3D models using
scale-space representations. We show how this matching algorithm can
be used to encode an object classifier, which can effectively be
applied to mechanical parts created by modern computer-aided design
systems. Lastly, this paper addresses the important problem of
establishing objective metrics and shared benchmarks for comparing
shape matching and classification algorithms.
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 models' 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
technique 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 be 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. Work
in~\cite{CICIRELLO-REGLI:SMI-2001,CICIRELLO-REGLI:AI-EDAM-2002}
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.
Work of McWherter et
al.~\cite{MCWHERTER-PEABODY:ASME-DETC-2001,MCWHERTER-PEABODY:ASME-JCISE-2001,MCWHERTER-PEABODY:SM-2001}
examined other graph-based methods for model comparison, including
spectral analysis. These techniques can match models based on both
topology (i.e.,\ solid model boundary representation) and features
(i.e.,\ machining or design features).
Historically GT (Group Technology) coding was the way of indexing 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 Multiresolution 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 and Funkhouser et
al.~\cite{OSADA-FUNKHOUSER:SMI-2001-ITALY,FUNKHOUSER:TOG-2002,FUNKHOUSER:TOG-2003}
developed a method that creates an abstraction of the 3D models as
probability distribution of samples from a shape function acting on
the model. Specifically, 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. Recent work by the same
investigators includes results of using shape harmonics and symmetry
for shape
matching~\cite{FUNKHOUSER-KAZHDAN:ALGORITHMICA-2003,KAZHDAN-FUNKHOUSER:SGP-2003,KAZHDAN-FUNKHOUSER:SIGGRAPH-2003}.
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.
Ip et
al.~\cite{REGLI-IP-ET-AL:SM02-SHAPE-MATCH,REGLI-IP-ET-AL:SM03-SHAPE-MATCH-LEARN}
propose several extensions to the basic shape distribution method,
most significant of which is a method that uses machine learning to
enhance recognition of desired classes. Based on training data in the
form of classified models, a weighted distance is created using a set
of shape distributions acquired from the CAD model. These
distributions capture the internal, external and global shape
properties of the object. These are combined into a single distance
measurement that is weighted to maximize the separation of the models
across classes.
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 the 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:SHAPE-MATCHING-01}. 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 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. The 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 0$, where
$v_1 \ne v_2$, $\D(v_i,v_i) = 0$, and $\D(v_1,v_3)\le
\D(v_1,v_2)+\D(v_2,v_3)$. In general, there are many ways to define
metric distances on a 3D model. One of the best-known metric
functions is the shortest-path metric $\delta(.,.)$ (geodesic
distance) on the triangulation of $\M$ with respect to points
$\{v_1,...,v_n\}$; i.e., $\D(u,v)=\delta(u,v)$, the shortest path
distance on the triangulated surface between $u$ and $v$ for all
$u,v\in\M$ (see Figure~\ref{fig:distance}). Observe that by
construction the matrix $\D_{\M}=\left[\D(v_i,v_j)\right]_{n\times n}$
is symmetric, and the $i^{\rm th}$ row (or column) in $\D$, $p_i$, is
an $n$-dimensional vector, characterizing the distance structure of
point $v_i$ in model $\M$. We use All Pairs Shortest Path
algorithm~\cite{INTRO-ALGO} for $\D_{\M}$ construction in our
experiments.
\begin{figure}[t]
\begin{center}
%\epsfxsize=0.6\hsize
\mbox{\psfig{figure=figs/fig1_v2.eps, width=3.2in}}
\end{center}
%\vspace*{-2em}
\caption{{Distance Metric for two points of a {\sc Good-Coupling}.}}
\label{fig:distance}
\end{figure}
The problem of decomposing model $\M$ into $k$ most significant
features $\M_1,...,\M_k$ is closely related to $k$-dimensional
subspace clustering ($k$-DSC). In $k$-DSC, we are given a set
of distance vectors $p_1,...,p_n$, and the objective is to find a
$k$-dimensional subspace $\S$ that minimizes the quantity:
$$\sqrt{\sum_{1\le i\le n}d(p_i,\S)^2},$$
where $d(p_i,\S)$ corresponds
to the smallest distance between $p_i$ and any member of $\S$. In
practice, if $\S$ is given, then $\M_1,...,\M_k$ can be computed using
the principle components $\{c_1,...,c_k\}$ of $k$-dimensional subsapce
$\S$~\cite{CSVD2002}. Observe that, these $k$ vectors will also form a
basis for $\S$. Specifically, $p_i$ will belong to the feature $\M_j$ if
the angle between $p_i$ and $c_j$ is the smallest among all basis
vectors in $\{c_1,...,c_k\}$, i.e., the point $p_i$ will belong to
the feature vector $\M_j$ iff the angle between these vectors is the
smallest compared to all other basis vectors.
\begin{figure*}[!t]
\begin{center}
%\epsfxsize=0.9\hsize
\begin{tabular}{rl}
\mbox{\psfig{figure=figs/fig2.eps, width=3in}}&
\mbox{\psfig{figure=figs/fig2_4.eps, width=3in}}\\
\sc{ Fork} & \sc{Part 10}\\
\mbox{\psfig{figure=figs/fig2_2.eps, width=3in}}&
\mbox{\psfig{figure=figs/fig2_3.eps, width=3in}}\\
\sc{ANC 101} & \sc{Spring}\\
%\sc{Part 09} & \sc{Spring}\\
\end{tabular}
\end{center}
%\vspace*{-2em}
\caption{{Scale-space bisection of the sample models. Binary trees
were obtained by recursively applying {\sc
Feature-Decomposition($\M,k$)}. Red-colored regions of child
nodes represent partitions that result in the bisection of the
parent.}}
\label{fig:ssd}
\end{figure*}
%% \begin{eqnarray}
%% \label{eq_dec:1}
%% d(p_i,\S)={p_i.c_j\over ||p_i||\cdot ||c_j||},
%% \end{eqnarray}
%% where $p_i.c_j$ is the inner product of vectors $p_i$ and $c_j$, and
%% $||.||$ is the length function.
%% The quantity $d(p_i,\S)$ refers to the
%% angle between vector $p_i$ and basis vector $c_j$ and
To construct the subspace $\S$, the optimal solution of $k$-DSC, we
will use the technique commonly known as {\rm singular value
decomposition (SVD) clustering}~\cite{CSVD2002}. First, observe
that the symmetric matrix $\D\in \SR^{n\times n}$ has a
SVD-decomposition of the form
\begin{eqnarray}
\label{eq_dec:2}
\D=U\Sigma V^T,
\end{eqnarray}
where $U, V\in \SR^{n\times n}$ are orthogonal matrices and
\begin{eqnarray}
\label{eq_dec:3}
\Sigma={\rm Diag}(\sigma_1,\sigma_2,...,\sigma_n),
\end{eqnarray}
with $\sigma_1\ge \sigma_2\ge ...\ge \sigma_n' > 0$,
$\sigma_{n'+1}=...=\sigma_n=0, n' \le n$. Let us define the order $k$
compression matrix $\D^{(k)}$ of $\D$, for $k\le n'$ as:
\begin{eqnarray}
\label{eq_dec:4}
\D^{(k)}=U{\rm Diag}(\sigma_1,...,\sigma_k,0,...,0)V^T.
\end{eqnarray}
Then,
\begin{theorem}{\rm [Eckart-Young]}.
\begin{eqnarray}
\label{eq_dec:5}
||\D-\D^{(k)}||_2=\min_{rank(H)=k}||\D-H||_2.
\end{eqnarray}
\end{theorem}
That is, matrix $D^{(k)}$ is the best approximation to $\D$ among all
matrices of rank $k$. In fact, this result can be generalized to many
other norms, including {\em Forbenius} norm:
\begin{corollary}
\label{corl-1}
For $A\in \SR^{n\times n}$, let
\begin{eqnarray}
\label{eq_dec:6}
||A||_F=\left( \sum_{i,j} A_{i,j}^2\right)^{1/2},
\end{eqnarray}
then,
\begin{eqnarray}
\label{eq_dec:7}
||\D-\D^{(k)}||_F= \min_{rank(H)=k}||\D-H||_F.
\end{eqnarray}
\end{corollary}
Next, assume $\S$ is the range of matrix $\D^{(k)}$ (the subspace
spanned by the colums of matrix $\D^{(k)}$), and let $c_j$, for $1\le
j\le k$, denote the $j^{\rm th}$ column of $\D^{(k)}$. Let
$\S'\neq\S$ be any $k$-dimensional subspace of $\SR^n$. For every
$p_i\in \M$ let $q_i\in \S'$ be the closets point in $\S'$ to $p_i$.
Define $\Q\in \SR^{n\times n}$ with $i^{\rm th}$ column equal to
$q_i$. Clearly, $rank{\Q}\le k$. Using Corollary~\ref{corl-1} we
have:
\begin{eqnarray*}
\sum_{i=1}^n d(p_i,\S')^2 &=& \sum_{i=1}^n d(p_i,q_i)^2\\
&=& ||\D-\Q||_F^2\\
&\ge& ||\D-\D^{(k)}||_F^2\\
&=& \sum_{i=1}^n d(p_i,c_i)^2\\
&\ge& \sum_{i=1}^n d(p_i,\S)^2.
\end{eqnarray*}
%\vspace{0.3in}
%\pagebreak
Consequently;
\begin{proposition}.
The set $\S=range(\D^{(k)})$ is the optimal solution to $k$-DSC
problem.
\end{proposition}
\begin{algorithm}
\begin{algorithmic}[1]
\STATE Construct the distance matrix $\D\in \SR^{n\times n}$.
\STATE Compute the SVD decomposition $\D=U\Sigma V^T$, with
$\Sigma={\rm Diag}(\sigma_1,\sigma_2,...,\sigma_n)$.
\STATE Compute the order $k$ compression matrix $\D^{(k)}=U{\rm
Diag}(\sigma_1,...,\sigma_k,0,...,0)V^T.$
\STATE Let $c_j$ denote the $j^{\rm th}$ column of $\D^{(k)}$, for
$j=1,...,k$, and form sub-feature $\M_j$ as the union of points
$p_i\in \M$ with $d(p_i,\S)=d(p_i,c_j)$.
\STATE Return the set $\{\M_1,...,\M_k\}$.
\end{algorithmic}
\caption{\sc Feature-Decomposition($\M,k$)}
\label{alg:dec-algo}
\end{algorithm}
Algorithm~\ref{alg:dec-algo} summarizes one phase of scale-space
decomposition of $\M$ into its $k$ most significant features,
$\M_1,...,\M_k$. Algorithm~\ref{alg:dec-algo} returns the partitioning
of $\M$ by placing each point $p_i$ in $\M$ into one of the partitions $\M_j$,
such that the angle between vector $p_i$ and basis vector $c_j$ corresponding
to the partition $\M_j$ is minimized. The results of scale-space decomposition for
several 3D models using the recursive application of {\sc
Feature-Decomposition ($\M,k$)}, for $k=2$ is presented in
Figure~\ref{fig:ssd}.
The bottleneck of Algorithm~\ref{alg:dec-algo} is the $O(n^3)$ SVD
decomposition, for an $n\times n$ matrix. Polyhedral representation of
a model provides us with planar graph of a 2D manifold. If we
consider only neighboring vertices in the construction of the distance
matrix $\D$, the number of non-zero entries in $\D$ would be at most
$6n$ (due to planarity of the graph). Computing SVD decomposition for
sparse matrices is much faster and takes
$O(mn)+O(m\mbox{M}(n))$~\cite{GOLUB-MATRIX-COMPUTATIONS}. Where $m$
is the maximum number of matrix-vector computations required and
$\mbox{M}(n)$ is the cost of matrix-vector computations of the form
$\D x$. Since $\mbox{M}$ is a planner map and $\D$ is a sparse matrix,
$\mbox{M}(n)=O(n)$ and $m=O(n)$.
% We are given a 3D model $\M$ in polyhedral representation (in our
% experiments we used models in VRML format). Before we can proceed
% with the scale-space decomposition of model $\M$, we must choose a
% suitable distance function to capture the affinity structure of $\M$;
% i.e., we must define a distance between any two 3D points in $\M$.
% Let $\{p_1,...,p_n\}$ denote the set of points in the 3D model $\M$. We
% will say that $\D$ is a metric function for $\M$ if, for any three
% points $p_1,p_2,p_3\in \M$, $\D(p_1,p_2)=\D(p_2,p_1) > 0$,
% where $p_1 \ne p_2$,
% $\D(p_i,p_i) = 0$, and $\D(p_1,p_3)\le \D(p_1,p_2)+\D(p_2,p_3)$. In
% general, there are many ways to define metric distances on a 3D model.
% One of the best-known metric functions is the shortest-path metric
% $\delta(.,.)$ (geodesic distance) on the triangulation of $\M$ with
% respect to points $\{p_1,...,p_n\}$; i.e., $\D(p,q)=\delta(p,q)$, the
% shortest path distance on the triangulated surface
% between $p$ and $q$ for all $p,q\in\M$ (see
% Figure~\ref{fig:distance}). Observe that by construction the matrix
% $\D_{\M}=\left[\D(p_i,p_j)\right]_{n\times n}$ is symmetric, and the
% $i^{\rm th}$ row (or column) in $\D$ is an $n$-dimensional vector,
% characterizing the metric structure of point $p_i$ in model $\M$. We
% use the All Pairs Shortest Path algorithm~\cite{INTRO-ALGO}
% for $\D_{\M}$ construction in our experiments.
% \begin{figure}[t]
% \begin{center}
% %\epsfxsize=0.6\hsize
% \mbox{\psfig{figure=figs/fig1_v2.eps, width=3.2in}}
% \end{center}
% %\vspace*{-2em}
% \caption{{Distance Metric for two points of a {\sc Good-Coupling}.}}
% \label{fig:distance}
% \end{figure}
% The problem of decomposing model $\M$ into $k$ most significant
% features $\M_1,...,\M_k$ is closely related to $k$-dimensional
% subspace clustering ($k$-DSC). In $k$-DSC, we are given a set of
% points $p_1,...,p_n$ in $l$-dimentional eucledean space, and the
% objective is to find a $k$-dimensional subspace $\S$ that minimizes
% the quantity:
% $$\sqrt{\sum_{1\le i\le n}d(p_i,\S)},$$
% where $d(p_i,\S)$ corresponds to the smallest distance between the point $p_i$
% and any member of $\S$. In practice, if $\S$ is given, then the
% construction of $\M_1,...,\M_k$ is fairly straightforward. Let
% $\{c_1,...,c_k\}$ denote the $k$ basis vectors of $\S$, then $p_i$
% will belong to feature $\M_j$ iff
% \begin{figure*}[!t]
% \begin{center}
% %\epsfxsize=0.9\hsize
% \begin{tabular}{rl}
% \mbox{\psfig{figure=figs/fig2.eps, width=3in}}&
% \mbox{\psfig{figure=figs/fig2_4.eps, width=3in}}\\
% \sc{ Fork} & \sc{Part 10}\\
% \mbox{\psfig{figure=figs/fig2_2.eps, width=3in}}&
% \mbox{\psfig{figure=figs/fig2_3.eps, width=3in}}\\
% \sc{ANC 101} & \sc{Spring}\\
% %\sc{Part 09} & \sc{Spring}\\
% \end{tabular}
% \end{center}
% %\vspace*{-2em}
% \caption{{Scale-space bisection of the sample models. Binary trees
% were obtained by recursively applying {\sc
% Feature-Decomposition($\M,k$)}. Red-colored regions of child
% nodes represent partitions that result in the bisection of the
% parent.}}
% \label{fig:ssd}
% \end{figure*}
% \begin{eqnarray}
% \label{eq_dec:1}
% d(p_i,\S)={p_i.c_j\over ||p_i||\cdot ||c_j||},
% \end{eqnarray}
% where $p_i.c_j$ is the inner product of vectors $p_i$ and $c_j$, and
% $||.||$ is the length function. The quantity $d(p_i,\S)$ refers to the
% angle between the vector $p_i$ and the basis vector $c_j$; the point $p_i$ will belong to
% feature vector $\M_j$ iff the angle between these vectors
% is minimal. To
% construct the subspace $\S$, the optimal solution of $k$-DSC, we will
% use the technique commonly known as {\rm singular value decomposition
% (SVD) clustering}. First, observe that the symmetric matrix $\D\in
% \SR^{n\times n}$ has a SVD-decomposition of the form
% \begin{eqnarray}
% \label{eq_dec:2}
% \D=U\Sigma V^T,
% \end{eqnarray}
% where $U, V\in \SR^{n\times n}$ are orthogonal matrices and
% \begin{eqnarray}
% \label{eq_dec:3}
% \Sigma={\rm Diag}(\sigma_1,\sigma_2,...,\sigma_n),
% \end{eqnarray}
% with $\sigma_1\ge
% \sigma_2\ge ...\ge \sigma_n\ge 0$. Let us define the order
% $k$ compression matrix $\D^{(k)}$ for $\D$ as:
% \begin{eqnarray}
% \label{eq_dec:4}
% \D^{(k)}=U{\rm Diag}(\sigma_1,...,\sigma_k,0,...,0)V^T.
% \end{eqnarray}
% Then,
% \begin{theorem}{\rm [Eckart-Young]}.
% \begin{eqnarray}
% \label{eq_dec:5}
% ||\D-\D^{(k)}||_2=\min_{rank(H)=k}||\D-H||_2.
% \end{eqnarray}
% \end{theorem}
% That is, matrix $D^{(k)}$ is the best approximation to $\D$ among all
% matrices of rank $k$. In fact, this result can be generalized to many
% other norms, including {\em Forbenius} norm:
% \begin{corollary}
% \label{corl-1}
% For $A\in \SR^{n\times n}$, let
% \begin{eqnarray}
% \label{eq_dec:6}
% ||A||_F=\left( \sum_{i,j} A_{i,j}^2\right)^{1/2};
% \end{eqnarray}
% then,
% \begin{eqnarray}
% \label{eq_dec:7}
% ||\D-\D^{(k)}||_F= \min_{rank(H)=k}||\D-H||_F.
% \end{eqnarray}
% \end{corollary}
% Next, assume $\S$ is the range of matrix $\D^{(k)}$, and let $c_j$, for
% $1\le j\le k$, denote the $j^{\rm th}$ column of $\D^{(k)}$. Let
% $\S'\neq\S$ be any $k$-dimensional subspace of $\SR^n$. For every
% $p_i\in \M$ let $q_i\in \S'$ be the closets point in $\S'$ to $p_i$.
% Define $\Q\in \SR^{n\times n}$ with $i^{\rm th}$ column equal to
% $q_i$. Clearly, $rank{\Q}\le k$. Using Corollary~\ref{corl-1} we
% have:
% \begin{eqnarray*}
% \sum_{i=1}^n d(p_i,\S')^2 &=& \sum_{i=1}^n d(p_i,q_i)^2\\
% &=& ||\D-\Q||_F^2\\
% &\ge& ||\D-\D^{(k)}||_F^2\\
% &=& \sum_{i=1}^n d(p_i,c_i)^2\\
% &\ge& \sum_{i=1}^n d(p_i,\S)^2.
% \end{eqnarray*}
% %\vspace{0.3in}
% %\pagebreak
% Consequently;
% \begin{proposition}.
% The set $\S=range(\D^{(k)})$ is the optimal solution to $k$-DSC
% problem.
% \end{proposition}
% \begin{algorithm}
% \begin{algorithmic}[1]
% \STATE Construct the distance matrix $\D\in \SR^{n\times n}$.
% \STATE Compute the SVD decomposition $\D=U\Sigma V^T$, with
% $\Sigma={\rm Diag}(\sigma_1,\sigma_2,...,\sigma_n)$.
% \STATE Compute the order $k$ compression matrix $\D^{(k)}=U{\rm
% Diag}(\sigma_1,...,\sigma_k,0,...,0)V^T.$
% \STATE Let $c_j$ denote the $j^{\rm th}$ column of $\D^{(k)}$, for
% $j=1,...,k$, and form sub-feature $\M_j$ as the union of points
% $p_i\in \M$ with $d(p_i,\S)=d(p_i,c_j)$.
% \STATE Return the set $\{\M_1,...,\M_k\}$.
% \end{algorithmic}
% \caption{\sc Feature-Decomposition($\M,k$)}
% \label{alg:dec-algo}
% \end{algorithm}
% Algorithm~\ref{alg:dec-algo} summarizes one phase of scale-space
% decomposition of $\M$ into its $k$ most significant features,
% $\M_1,...,\M_k$. Algorithm~\ref{alg:dec-algo} returns the partitioning
% of $\M$ by placing each point $p_i$ in $\M$ into one of the partitions $\M_j$,
% such that the angle between vector $p_i$ and basis vector $c_j$ corresponding
% to the partition $\M_j$ is the smallest. The results of scale-space decomposition for
% several 3D models using the recursive application of {\sc
% Feature-Decomposition ($\M,k$)}, for $k=2$ is presented in
% Figure~\ref{fig:ssd}.
% The bottleneck of Algorithm~\ref{alg:dec-algo} is the $O(n^3)$ SVD
% decomposition, for an $n\times n$ matrix. Polyhedral representation of
% a model provides us with planar graph of a 2D manifold. If we
% consider only neighboring vertices in the construction of the distance
% matrix $\D$, the number of non-zero entries in $\D$ would be at most
% $6n$ (due to planarity of the graph). Computing SVD decomposition for
% sparse matrices is much faster and takes
% $O(mn)+O(m\mbox{M}(n))$~\cite{GOLUB-MATRIX-COMPUTATIONS}. Where $m$
% is the maximum number of matrix-vector computations required and
% $\mbox{M}(n)$ is the cost of matrix-vector computations of the form
% $\D x$. Since $\mbox{M}$ is a planner map and $\D$ is a sparse matrix,
% $\mbox{M}(n)=O(n)$ and $m=O(n)$.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% %
% Controlling Decomposition Process %
% %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\vspace*{-0.05in}
\subsection{Controlling Decomposition Process}
The decomposition process as presented in Section~\ref{sec:dec-alg}
does not allow for an explicit mechanism to stop indefinite break up
of a feature into a point-cloud. Clearly, we could use a constant to
control the decomposition depth of the feature trees, i.e.,
decomposition process will be stopped when a root branch in feature
decomposition tree reaches a prescribed depth. In this section we
will present a mechanism that will control the feature decomposition
through constant measurement of coherence through out the decomposition
paths. Intuitively, the use of this control mechanism will terminate
the decomposition process only when all significant features are
extracted.
We will assign a {\it measurement} to each iteration of
Feature-Decomposition algorithm. Specifically, Let $\M$ be the
original model's point set and $E$ denote the set of all edges
connecting points in $\M$. Assume in the decomposition process a
feature $\M_1$ in $\M$ can be decomposed into sub-features $\M_2$ and
$\M_3$ after bisection (e.g., without loss of generality assume we are
bisecting feature $\M_1$). The coherence measurement for $\M_1$ is
defined as follows:
\begin{figure}[!h]
\begin{center}
\begin{tabular}{cc}
\begin{tabular}{c}
\mbox{\psfig{figure=figs/part10_potential.eps, width=3.1in}}\\
(a)\\
\\ \\
\mbox{\psfig{figure=figs/spring_potential.eps, width=3.1in}}\\
(b)\\
\\ \\
\end{tabular} &
\begin{tabular}{c}
\mbox{\psfig{figure=figs/fork_potential.eps, width=3.1in}}\\
(c)\\
\end{tabular}
\end{tabular}
\end{center}
%\vspace*{-2em}
\caption{Feature trees for the sample models. (a), (b) Models Part 10
and Spring respectively. Views of these models are presented on the
left. (c) Illustrates decomposition process for Fork model (view is
presented). Pictures of the point sets for three bisections are
presented. Note that technique extracted a pin on one side of the
Fork (pin is not present on the other side). }
\label{fig:potential}
\end{figure}
\[
f(\M_1) = {\rho(\M_1) \over \lambda(\M_1) + \rho(\M_1)},
\]
where
\[\rho(\M_1) = \hspace{-0.1in} \sum_{\begin{array}{c} (u,v) \in E, \\ u \in \M_2, \\ v \in \M_3 \end{array}} \hspace{-0.1in} \D(u, v),\]
denotes the distance of points across sub-features, and
\[ \lambda(\M_1) = \hspace{-0.1in} \sum_{\begin{array}{c} (u,v) \in E, \\ u \in \M_2, \\ v \in \M_2 \end{array}}
\hspace{-0.1in} \D(u, v) \hspace{0.1in} + \hspace{-0.1in}
\sum_{\begin{array}{c} (u,v) \in E, \\ u \in \M_3, \\ v \in \M_3
\end{array}} \hspace{-0.1in} \D(u, v),\]
is the sum of distances within sub-features. Intuitively, the
normalized ratio in $f(\M_1)$ will account for coherence of $\M_1$ as
oppose to its constituting sub-features $\M_2$ and $\M_3$.
Specifically, we say that bisection of $\M_1$ into $\M_2$ and $\M_3$ is
good if $f(\M_1)$ is less than a prescribed threshold $\tau$. If this
threshold condition holds, the decomposition process continues for
sub-features $\M_2$ and $\M_3$, otherwise it stops at $\M_1$. In
Figures~\ref{fig:potential}.(a) and ~\ref{fig:potential}.(b) are two
examples of applying the decomposition control process to Models
Part 10 and Spring, respectively. Figure ~\ref{fig:potential}.(c)
illustrates the decomposition process for Fork model (view is presented).
Pictures of the point sets for three bisections are presented. Note
that the technique extracted a pin on one side of the Fork (the pin is not
present on the other side).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Matching
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Scale-Space Matching}
\label{sec:matching}
The scale-space decomposition of a 3D model $\M$ will give raise to a
rooted undirected tree $T_\M=(V,E)$ in a natural way. The vertex set
of this graph corresponds to the set of features produced by recursive
application of Algorithm~\ref{alg:dec-algo} to model $\M$. The
edges of $T_\M$ will capture the decomposition relation between a
feature and all its sub-features. Figure~\ref{fig:ssd} shows
several examples of degree-2 trees corresponding to 3D models. Using
this construction the problem of comparing two 3D models $\M_1$ and
$\M_2$ can be reformulated as computing a matching among the
corresponding rooted trees $T_1$ and $T_2$.
Given 3D models $\M_1$ and $\M_2$, and their corresponding scale-space
trees (SST's) $T_1$ and $T_2$, we will propose a matching algorithm
based on the dynamic programming framework proposed by Wang et.
el.~\cite{wang99}. Intuitively, the similarity between two
features $u\in \M_1$ and $v\in \M_2$ is closely related to similarity
of sub-features forming $u$ and $v$. Specifically, the similarity of
features $u$ and $v$ should be measured in terms of the similarity of
subtrees $T_1(u)$ and $T_2(v)$ rooted at $u$ and $v$.
\begin{figure}[!t]
\begin{center}
\begin{tabular}{cccc}
\mbox{\psfig{figure=figs/goodpart_compare.eps, width=1.5in, height=1.3in}}&
\mbox{\psfig{figure=figs/badpart_compare.eps, width=1.5in, height=1.3in}}&
\mbox{\psfig{figure=figs/simple_bracket_compare.eps, width=1.5in, height=1.3in}}&
\mbox{\psfig{figure=figs/swivel_compare.eps, width=1.5in, height=1.3in}}\\
(a) & (b) & (c) & (d)\\
%\epsffile{figs/fig3.eps}
\end{tabular}
\end{center}
%\vspace*{-2em}
\caption{{Results of matching between two {\sc Goodparts} (a, b) and
two {\sc Swivels} (c, d), with matched
regions having similar colors. Most significant features are
obtained for each model using {\sc Feature-Decomposition($\M,k$)} and
are used to construct binary trees $T_1$ and $T_2$.
Match-Models($T_1,T_2$) then generates a set of matched features which have been
colored similarly for this figure.}}
\label{fig:mch}
\end{figure}
The cost of matching $T_1(u)$ and $T_2(v)$ can be characterized~as:
\begin{eqnarray}
\label{eq:1}
C(T_1(u),T_2(v))= C(F_1(u),F_1(v))+\gamma(u,v).
\end{eqnarray}
That is, the cost of matching trees rooted at features $u$ and $v$ is
equal to the distance between the two features $u$ and $v$
($\gamma(u,v)$) plus the cost of matching the forests $F_1(u)$ and
$F_2(v)$, obtained from $T_1(u)$ and $T_2(v)$, after removing $u$ and
$v$, respectively. In order to deal with degenerate case,
$u=\emptyset$ (and/or $v=\emptyset$) we will use:
\begin{eqnarray}
C(T_1(u),\emptyset)=\gamma(u,\emptyset)
\label{eq:2}\\
C(F_1(u),\emptyset)=\sum_{y}\gamma(y,\emptyset),
\label{eq:3}
\end{eqnarray}
where the sum in~(\ref{eq:3}) is over the roots of all trees in
$F_1(u)$. Observe that for two features $u\in T_1$ and $v\in T_2$ to be
matched, at some level some of their sub-features in $F_1(u)$
and $F_2(v)$ should have been matched. This phenomenon is captured in
our formulation of $C(T_1(u),T_2(v))$ in~(\ref{eq:1}), using term
$C(F_1(u),F_2(v))$. To compute the cost of matching the two forests
$F_1(u)$ and $F_2(v)$, we need to compute a maximum similarity
matching among the roots of trees in these two forests. To this end,
we will form a complete bipartite graph among the sub-features forming
the roots of $F_1(u)$ and $F_2(v)$. Let $x\in F_1(u)$ and $y\in
F_2(v)$ denote two such vertices, we will associate the following as
the cost of matching $x$ and $y$ in aforementioned bipartite graph:
\begin{eqnarray}
\label{eq:4}
w(x,y)=C(x,\emptyset)+C(\emptyset, y)+C(T_1(x),T_2(y)).
\end{eqnarray}
Observe that the term $C(T_1(x),T_2(y))$ is the basis of the
recursion in this dynamic programming framework. The chain of
recursive calls will terminate at the primitive features forming the
leaves of $T_1$ and $T_2$. Consequently, the cost of matching the
forests $F_1(u)$ and $F_2(v)$ can be restated as
\begin{eqnarray}
\label{eq:4.5}
C(F_1(u),F_2(v))&=&{1\over 2}\left( \sum_x C(x,\emptyset)+\sum_y
C(\emptyset, y)\right )\nonumber\\
& &+\sum_{(x,y)\in \MP(u,v)} w(x,y).
\end{eqnarray}
The first two sums in~(\ref{eq:4.5}) run over the roots of
trees in $F_1(u)$ and $F_2(v)$, respectively, and the third sum runs
over all matched pairs in bipartite matching of sub-features of $u$
and $v$, $\MP(u,v)$.
To state our recursive algorithm we need to specify the cost function
$\gamma(u,v)$ in~(\ref{eq:1}). In our formulation of $\gamma(.,.)$
we will use the notion of topological similarity introduced
by Hilaga et. al. in~\cite{HILAGA-ET-AL:SIGGRAPH-2001}. In fact we
will set
\begin{eqnarray}
\label{eq:5}
\gamma(u,v)=e^{-sim(u,v)},
\end{eqnarray}
where $sim(u,v)$ is a convex combination of the form:
\begin{eqnarray*}
\label{eq:6}
sim(u,v)&=&w\cdot\min(\alpha(u),\alpha(v))\\
& &+(1-w)\cdot\min(\ell(u),\ell(v)),\ {\rm for\ } 0\le w\le 1,
\end{eqnarray*}
for $0\le w\le 1$, with functions $\alpha(.)$ and $\ell(.)$
representing the ratios of the area and the length of the
corresponding features in the whole 3D model, respectively (for further
details on the description of $\alpha(.)$ and $\ell(.)$
see~\cite{HILAGA-ET-AL:SIGGRAPH-2001}).
Finally, we can state the matching algorithm for two scale-space
decompositions $T_1$ and $T_2$ corresponding to 3D models $\M_1$ and
$\M_2$. The result of applying Algorithm~\ref{alg:mch-algo} to two
{\sc Goodparts} parts is represented in Figure~\ref{fig:mch}. Please
note that final distance function is not metric. It satisfies symmetry and
non-negativity properties but it does not satisfy triangle inequality by
construction. Even though we have not encountered this case in our experiments,
it is theoretically possible that matching algorithm would return similarity
values for the models such that they would not satisfy triangle inequality.
\begin{algorithm}
\begin{algorithmic}[1]
\STATE $C(\emptyset,\emptyset)\leftarrow 0$.
\STATE $\forall u\in T_1$ {\sc Compute} $C(T_1(u),\emptyset)$ and
$C(F_1(u),\emptyset)$ using~(\ref{eq:2}) and~(\ref{eq:3}).
\STATE $\forall v\in T_2$ {\sc Compute} $C(T_2(v),\emptyset)$ and
$C(F_2(v),\emptyset)$ using~(\ref{eq:2}) and~(\ref{eq:3}).
\STATE $\forall u\in T_1$ and $\forall v\in T_2$ do\\
{\sc Compute} $C(F_1(u),F_2(v))$ as in~(\ref{eq:4.5})\\
{\sc Compute} $C(T_1(u),T_2(v))$ as in~(\ref{eq:1})\\
\STATE Return the set of matched vertices:
$$\cup_{(u,v)}M(u,v),$$
and the total cost of matching $T_1$ and $T_2$:
$$C({\rm root}(T_1),{\rm root}(T_2)).$$
\end{algorithmic}
\caption{\sc Match-Models($T_1,T_2$)}
\label{alg:mch-algo}
\end{algorithm}
Based on time bound proposed by Zhang and Shasha in~\cite{wang99} for
this framework, the number of iterations of
Algorithm~\ref{alg:mch-algo} algorithm is $O(n_1 n_2 \sqrt{2}
\log{d})$, where $d$ is the maximum degree of trees obtained in
decomposition process, and $n_1$ and $n_2$ are the number of vertices
in $T_1$ and $T_2$, respectively. Observe that $n_1$ and $n_2$ are
much smaller than the initial sizes of $\M_1$ and $\M_2$. In the
computations of running time, we will also have an additional
multiplicative factor $\phi(\M_1,\M_2)$ that accounts for the
complexity of vanishing any feature in models $\M_1$ and $\M_2$ .
Also, in order for our algorithm to meet the time bound, we precompute
values of $\alpha(u)$ and $\ell(u)$ $\forall u \in T$. Complexities
for computations of $\alpha(u)$ and $\ell(u)$ are linear in terms of
the number of points in partition~$u$.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Experiments
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Experimental Results}
\label{sec:exp}
To demonstrate our approach to scale-space matching, we performed a
set of matching experiments using a database of 3D models. For a
given 3D model, its scale-space feature decomposition is first
represented by a rooted, vertex-labeled tree, in which nodes represent
{\em features} (obtained by recursive application of
Algorithm~\ref{alg:dec-algo}) and edges capture the relationships
between a feature and its sub-features. We will assume that each point
\(u\) in the tree is labeled by two attributes, values of the
functions \(\alpha(u)\) and \(l(u)\), defined in
Section~\ref{sec:matching}. These attributes were used in the
Algorithm~\ref{alg:mch-algo} to compute the distances between pairs of
nodes.
\begin{figure*}[!th]
\begin{center}
\begin{tabular}{|c|c|c|c|c|}
\hline
{\sc Shafts} &
{\sc Part} &
{\sc Linkage-arms} &
{\sc Team} &
{\sc Springs} \\
\mbox{\psfig{figure=figs/impeller.ps, width=0.5in}}
\mbox{\psfig{figure=figs/shaft62.ps, width=0.5in}}&
\mbox{\psfig{figure=figs/part10.ps, width=0.5in}}
\mbox{\psfig{figure=figs/part9.ps, width=0.5in}}&
\mbox{\psfig{figure=figs/arm42.ps, width=0.2in}}
\mbox{\psfig{figure=figs/arm43.ps, width=0.5in}}&
\mbox{\psfig{figure=figs/team.ps, width=0.5in}}
\mbox{\psfig{figure=figs/team2.ps, width=0.5in}}&
\mbox{\psfig{figure=figs/spring.ps, width=0.5in}}
\mbox{\psfig{figure=figs/spring2.ps, width=0.5in}}\\
\hline
{\sc Spacer} &
{\sc BoeingParts} &
{\sc Goodparts} &
{\sc Swivel} &
{\sc Socket} \\
\mbox{\psfig{figure=figs/spacer66.ps, width=0.5in}}
\mbox{\psfig{figure=figs/spacer67.ps, width=0.5in}}&
\mbox{\psfig{figure=figs/boeing.ps, width=0.5in}}
\mbox{\psfig{figure=figs/simple_boeing.ps, width=0.5in}}&
\mbox{\psfig{figure=figs/bad_part.ps, width=0.5in}}
\mbox{\psfig{figure=figs/good_part2.ps, width=0.5in}}&
\mbox{\psfig{figure=figs/bracket1.ps, width=0.5in}}
\mbox{\psfig{figure=figs/swivel2.ps, width=0.5in}}&
\mbox{\psfig{figure=figs/good.ps, width=0.5in}}
\mbox{\psfig{figure=figs/sipe.ps, width=0.5in}}\\
\hline
\end{tabular}
%% \begin{tabular}{|c|c|}
%% \hline
%% {\sf Groups} &{\sf Sample Views}\\
%% \hline
%% \raisebox{6.5ex}[0pt]{\sc Shafts} &
%% \mbox{\psfig{figure=figs/impeller.ps, width=0.5in}}
%% \mbox{\psfig{figure=figs/shaft62.ps, width=0.5in}}\\
%% \hline
%% \raisebox{6ex}[0pt]{\sc Part} &
%% \mbox{\psfig{figure=figs/part10.ps, width=0.5in}}
%% \mbox{\psfig{figure=figs/part9.ps, width=0.5in}}\\
%% \hline
%% \raisebox{5.5ex}[0pt]{\sc Linkage-arms} &
%% \mbox{\psfig{figure=figs/arm42.ps, width=0.2in}}
%% \mbox{\psfig{figure=figs/arm43.ps, width=0.5in}}\\
%% \hline
%% \raisebox{5.75ex}[0pt]{\sc Team} &
%% \mbox{\psfig{figure=figs/team.ps, width=0.5in}}
%% \mbox{\psfig{figure=figs/team2.ps, width=0.5in}}\\
%% \hline
%% \raisebox{4ex}[0pt]{\sc Springs} &
%% \mbox{\psfig{figure=figs/spring.ps, width=0.5in}}
%% \mbox{\psfig{figure=figs/spring2.ps, width=0.5in}}\\
%% \hline
%% \raisebox{4.5ex}[0pt]{\sc Spacer} &
%% \mbox{\psfig{figure=figs/spacer66.ps, width=0.5in}}
%% \mbox{\psfig{figure=figs/spacer67.ps, width=0.5in}}\\
%% \hline
%% \raisebox{2.5ex}[0pt]{\sc BoeingParts} &
%% \mbox{\psfig{figure=figs/boeing.ps, width=0.5in}}
%% \mbox{\psfig{figure=figs/simple_boeing.ps, width=0.5in}}\\
%% \hline
%% \raisebox{4.5ex}[0pt]{\sc Goodparts} &
%% \mbox{\psfig{figure=figs/bad_part.ps, width=0.5in}}
%% \mbox{\psfig{figure=figs/good_part2.ps, width=0.5in}}\\
%% \hline
%% \raisebox{5ex}[0pt]{\sc Swivel} &
%% \mbox{\psfig{figure=figs/bracket1.ps, width=0.5in}}
%% \mbox{\psfig{figure=figs/swivel2.ps, width=0.5in}}\\
%% \hline
%% \raisebox{3.5ex}[0pt]{\sc Socket} &
%% \mbox{\psfig{figure=figs/good.ps, width=0.5in}}
%% \mbox{\psfig{figure=figs/sipe.ps, width=0.5in}}\\
%% \hline
%% \end{tabular}
\end{center}
\caption{Sample views from 10 Groups of 3D models in our database.}
\label{fig:db}
\end{figure*}
Models with many features and parts lead to trees with many nodes. To
reduce the size of the tree, we will impose a fixed bound on the
maximum number $k$ used in the Algorithm~\ref{alg:dec-algo} for
decomposition purposes. In practice, one can optimize on parameter $k$
via an independent study of individual models. For the experiments,
we compute the scale-space tree of every model using seven layers
of decomposition (depth of the tree) with branching parameter $k=2$.
This procedure results in a database of hierarchical trees, each
representing a 3D model.
We tested our scale-space matching algorithm on the {\bf CAD\_40}
dataset, a database of 40 3D solid models. The database consists of
10 different group of objects. A set of representative 2D views of 3D
models is shown in Figure~\ref{fig:db}. These models cover several
non-trivial classes of mechanical artifacts and include parts from
several industry and government sources. These models are available
for download from the National Design Repository at URL~\\ {\tt
http://www.designrepository.org/SM03}.
%\vspace*{0.2in}
To test our approach on the {\bf CAD\_40} dataset, we have computed
distances between every 3D model in the database and each of the
remaining database entries (the distance between a view and itself is
always zero). These object distances are summarized in
Figure~\ref{fig:results}. The magnitudes of the distances are denoted
by shades of gray, with black and white representing the smallest and
largest distances, respectively.
Inter-group distances, shown along the main diagonal, are very close
to zero. Also, distances between models from different groups are
significantly larger than inter-group distances.
\begin{figure}[!th]
%\vskip 0.2in
\begin{center}
%\epsfxsize=1\hsize
%\epsffile{figs/matrix2.eps}
\mbox{\psfig{figure=figs/matrix2.eps, width=3.3in}}
\caption{Distance matrix of results for the matching process. Darker
regions correspond to closer matches. Actual values for matches
of a subset of 6 models is shown with pictures of the models.
Most of the high-valued matches occur inside the groups, although,
there are several cross-group pairs that return high similarity
values.
}
\label{fig:results}
\end{center}
%\vskip 0.2in
\end{figure}
Based on the overall matching statistics, we observed that in almost
$15\%$ of the experiments, the closest match selected by our algorithm
was not a member of the same group. We expect that with a more
appropriate $\gamma(.,.)$ function, ensuring that for each model there
exists a similar inter-group model, this error rate would decrease
significantly. Finally, it should be noted that both the feature
decomposition and matching procedures can accommodate sampling noise.
This is due to the fact that the structure of trees corresponding to
model are unaffected by sampling noise.
\section{Empirical Evaluation}
To determine the benefits and possible shortcomings of the scale-space
technique, we tested it against six (6) other approaches to shape
matching and shape retrieval. To our knowledge, there is no previous
work evaluating multiple matching techniques with one another using
common dataset\footnote{The authors would like to note that the
performance of any algorithm (i.e.,\ its ability to discriminate
objects and object classes) will vary greatly depending on the
domain of objects. Given that the process of classification is
largely subjective, here is no universal best classifier or
matcher---one can construct datasets and classifications to confound
any one matcher.}. One previous attempt to validate a single
matching algorithm was done by Funkhouser et
al.~\cite{FUNKHOUSER:TOG-2002} who proposed using an {\em information
retrieval} measure of {\em recall} to assess how well their
technique performs ``query-by-example.'' In this context, information
recall treats one's set of models as ``documents.'' {\em Recall} is
an estimate of how well the algorithm returns {\em all} relevant
documents related to the query, even if it returns irrelevant
documents. {\em Recall precision} calculates how well the a system
avoids finding documents that are irrelevant to a given query. The
goal of traditional information retrieval is to maximize both
precision and recall for normal queries entered into the system.
We are interested in measuring the performance for {\em automated
classification}, which is more intricate than just processing queries.
Hence, while the information retrieval approach is suitable for
measuring the performance of simple query-by-example interactions, it
is not sufficient for determining the overall performance of a
classifier. To assess classification, our approach is to use basic
statistical hypothesis testing to calculate of the number of errors
made by an algorithm and combine this with evaluation strategies
typically used in machine learning.
\paragraph*{The Algorithms Used.}
For this evaluation, we have implemented the following known shape and
solid model matching algorithms in addition to the algorithm described
in this paper:
\begin{itemize}
\item Reeb Graphs~\cite{HILAGA-ET-AL:SIGGRAPH-2001};
\item Shape Distributions~\cite{OSADA-FUNKHOUSER:SMI-2001-ITALY,FUNKHOUSER:TOG-2002,FUNKHOUSER:TOG-2003};
\item Enhanced Shape Distributions~\cite{REGLI-IP-ET-AL:SM02-SHAPE-MATCH};
\item Learning Shape Classifiers~\cite{REGLI-IP-ET-AL:SM03-SHAPE-MATCH-LEARN};
\item Invariant Topology Vectors~\cite{MCWHERTER-PEABODY:ASME-DETC-2001,MCWHERTER-PEABODY:ASME-JCISE-2001,MCWHERTER-PEABODY:SM-2001}.
\end{itemize}
\paragraph*{Procedure for Comparison.}
Given a set of objects $\cal M$ and a fixed set of mutually disjoint
categories, ${\cal C} = {C_1, C_2 \ldots C_k}$ (i.e.,\ $\bigcup {\cal
C}=\cal M$ and $C_1\cap C_2=\emptyset$ when $i\neq j$), we can use
any shape matching algorithm to determine which category the query
object, $M_q$, should be placed into by computing the model that is
its nearest neighbor in the set ${\cal M}$. The nearest object to
$M_q$, $M_n$, is the model for which the distance function over all
models in ${\cal M}$ is minimized. The query element is then assigned
to the same category as $M_n$.
In the case of the {\bf CAD\_40} dataset, we sequentially removed each
element from the set and computed the nearest neighbor among the
remaining 39 elements. In this way, the matching algorithm is testing
the hypothesis that objects are in the same class as their nearest
neighbors computed by the algorithm. If $M_q$ was assigned the
correct classification (i.e.,\ $M_n$ is in the same class as $M_q$),
there is no error.
A {\em type 1} error occurs when $M_q$ is placed into the incorrect
class (i.e.,\ because $M_n$ is of a different class than $M_q$ it
registers as a {\em false negative}). In this case, {\em type 2}
errors count the contrapositive condition (i.e.,\ $M_q$ is a false
positive with respect to the class of $M_n$), hence there is one type
2 (false negative) error for each type 1 error (false positive).
\begin{table}[h]
{\small \centering
\begin{tabular}[h]{|l||l|l|l|l||}
\hline
Technique & Type 1 Errors & \% Error\\
Scale-space & 12 & 30.0\% \\
\hline
Reeb Graph & 13 & 32.5\% \\
\hline
Shape Dist. & 11 & 27.5\% \\
\hline
Enhanced Dist. & 14 & 35.0\% \\
\hline
Learning & 13 & 32.5\%\\
\hline
ITV & 15 & 37.5\% \\
\hline
\end{tabular}
}
\caption{Comparison of several matching algorithms.}
\label{tab:results}
\end{table}
\begin{table}[h]
{\small
\centering
\begin{tabular}[h]{||l||c|c|c|c|c|c|c|c|c|c||}
\hline
Technique & Shafts & Parts & Linkage & Team & Goodparts & Springs &
Swivels & Spacers & Sockets & Housings \\
Category size & 13 & 2 & 4 & 2 & 4 & 2 & 4 & 2 & 5 & 2 \\
\hline
Scale-space & 3 & 1 & 1 & 1 & 2 & 1 & 1 & 1 & 1 & 0 \\
\hline
Reeb Graph & 3 & 1 & 1 & 2 & 2 & 1 & 1 & 1 & 1 & 0 \\
\hline
Shape Dist. & 2 & 2 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 0 \\
\hline
Enhanced Dist. & 5 & 1 & 1 & 1 & 1 & 2 & 1 & 1 & 1 & 0 \\
\hline
Learning & 4 & 2 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 0 \\
\hline
ITV & 2 & 2 & 1 & 1 & 3 & 2 & 1 & 1 & 2 & 0 \\
\hline
\end{tabular}
}
\caption{Type 1 errors by object class.}
\label{tab:type-1-error-by-class}
\end{table}
\begin{table}[h]
{\small
\centering
\begin{tabular}[h]{||l||c|c|c|c|c|c|c|c|c|c||}
\hline
Technique & Shafts & Parts & Linkage & Team & Goodparts & Springs &
Swivels & Spacers & Sockets & Housings \\
Category size & 13 & 2 & 4 & 2 & 4 & 2 & 4 & 2 & 5 & 2 \\
\hline
Scale-space & 0 & 0 & 2 & 1 & 1 & 0 & 1 & 0 & 4 & 3\\
\hline
Reeb Graph & 0 & 0 & 0 & 0 & 1 & 3 & 1 & 0 & 4 & 4 \\
\hline
Shape Dist. & 0 & 0 & 1 & 3 & 0 & 0 & 1 & 3 & 1 & 2 \\
\hline
Enhanced Dist. & 0 & 0 & 1 & 6 & 0 & 0 & 0 & 1 & 2 & 4 \\
\hline
Learning & 0 & 0 & 1 & 5 & 1 & 0 & 0 & 2 & 1 & 3\\
\hline
ITV & 0 & 0 & 1 & 1 & 0 & 1 & 1 & 2 & 7 & 0 \\
\hline
\end{tabular}
}
\caption{Type 2 errors by object class.}
\label{tab:type-2-error-by-class}
\end{table}
\paragraph*{Results.}
Table~\ref{tab:results} shows the overall error accumulated by each
technique across the CAD\_40 dataset. To test this dataset, forty
(40) classifications were performed, one for each model. The data in
Table~\ref{tab:results} shows the number of type 1 (and type 2) errors
over these 40 classifications.
Tables~\ref{tab:type-1-error-by-class}
and~\ref{tab:type-2-error-by-class} show the distribution of type 1
and type 2 errors by object class, respectively.
\paragraph*{Discussion of Results.}
All of the techniques perform equally well\footnote{Or poorly,
depending on your perspective.} in the overall classification task
for the CAD\_40 set, with the error ranges falling within 10\% of each
other. What is interesting to note is that while, in general, 1-in-3
classifications is in error (regardless of technique), certain
techniques clearly do better than others for certain classes of
models. For example, on the class of ``Team'' parts, the scale-space
approach has 1/2 the error rate of the original shape distribution
technique. Additional examples:
\begin{itemize}
\item The Reeb graph approach performed best on linkage-arm dataset,
where there is a strong topological consistency across shapes;
\item The enhanced distribution and learning techniques performed best
on the Swivel set, where both geometry and features are needed to
discriminate the objects;
\item The original shape distribution and ITV techniques worked best
on the Housings set, which have strong geometric signatures in
addition to having nearly identical boundary representation solid models.
\end{itemize}
The data indicates that one's choice of matching or classification
algorithm is highly dependent on the type of data one wants to work
with. There is no universal best solution, rather each algorithm
identifies a slightly different set of object invariants on which to
perform matching. No one technique appears better overall, however,
the scale space approach introduced in this paper is among the most
consistent.
Some additional observations can be made:
\begin{itemize}
\item The distinction between type 1 and type 2 errors lies in their
distribution across the classes: some classes will be more prone to
certain types of errors.
\item This dataset is not sufficiently large or representative enough
to enable any strong statistical generalizations. A dataset with
larger ($>30$) classes and (perhaps) larger ($>30$) number of
classes are needed.
\item Standard data sets and test cases are needed for shape and CAD
model matching, much in the same manner as has been established in
machine vision.
\end{itemize}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Conclusions & Future Work
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
~\\
\section{Concluding Remarks}
\label{sec:conc}
We have presented a computationally efficient approach to hierarchical
matching and classification of 3D models. The approach is based on a
combination of scale-space feature decomposition of 3D models, rooted
tree representation of these feature decompositions, and dynamic
programming matching of vertex-labeled graphs. Due to the strengths
of the these components, our approach is able to establish robust
correspondences in the presence of sampling noise. In a series of
experiments we have demonstrated the performance of our approach and
introduced a method for comparing different shape matching and
classification algorithms. In our evaluation, the scale-space
technique performs as well, or better than, existing matching
algorithms. Actual performance was shown to depend significantly on
the class of models being compared and classified. We believe that
the method for comparison is generalizable and can be built into a
set of benchmarks for the community.
This research differs significantly from previous work on 3D model
matching. The notion of feature presented here is highly tuned to the
efficient identification of shape and topological categories. What we
have demonstrated is that, in the context of 3D solid models of
mechanical parts, the scale-space decomposition technique produces a
near-exact approximation of traditional CAD features without the
issues presented by traditional feature recognition and mapping. This
enabled us to perform accurate matching of 3D solid models of
mechanical parts which preserved meaningful engineering
classifications.
%Our work is in its preliminary stages, and we plan to extend its scope
%in several directions: 1) to study the branching parameters of feature
%decomposition ($k$) in our tree abstraction; 2) to improve the
%complexity of our matching algorithm ; 3) improve the feature
%similarity metric $\gamma(.,.)$, to account for geometric point
%distribution in each feature; 4) explore techniques to add increased
%engineering and manufacturing data into the matching; and 5) to
%exploit the possibility of using the structural parameters of tree
%representation as signatures for indexing purposes.
Our work is in its preliminary stages, and we plan to extend its scope
in several directions: 1) to improve the complexity of our matching
algorithm; 2) improve the feature similarity metric $\gamma(.,.)$, to
account for geometric point distribution in each feature; 3) explore
techniques to add increased engineering and manufacturing data into
the matching; and 4) to exploit the possibility of using the
structural parameters of tree representation as signatures for
indexing purposes.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 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.
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.
%\newpage
%\scriptsize
%
% The following two commands are all you need in the
% initial runs of your .tex file to
% produce the bibliography for the citations in your paper.
\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}
total # of classifications for 40 models
40