\documentclass[twocolumn]{asme2e}
\bibliographystyle{asmems4}
\confshortname{DETC'04}
\conffullname{ASME Design Engineering Technical Conferences}
\confdate{September 28 - October 2}
%\confmonth{September}
\confyear{2004}
\confcity{Salt Lake City, Utah}
\confcountry{USA}
\papernum{DETC2004/CIE-XXXXX}
\usepackage[dvips]{graphicx}
\usepackage{array}
%\usepackage{amsmath}
%\usepackage{amssymb}
\usepackage{fancyheadings}
\usepackage{subfigure}
\usepackage{psfig}
\usepackage{epsfig}
\usepackage{url}
\usepackage{mathptmx}
\usepackage{bbm}
\usepackage{amssymb}
\usepackage{algorithm,algorithmic}
\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}
\begin{document}
\title{Local Feature Extraction Using Scale-Space Decomposition}
\author {
\centerline{Dmitriy Bespalov \ \ Ali Shokoufandeh \ \ William C. Regli} \\ \\
\begin{minipage}[t]{0.5\textwidth} \centering
{ Geometric and Intelligent Computing Laboratory \\
Department of Computer Science \\
College of Engineering\\
Drexel University \\
Philadelphia, PA 19104 \\
\url{http://gicl.mcs.drexel.edu}}
\end{minipage}
}
\maketitle
\begin{abstract}
In our recent work we have introduced a framework for extracting features from solid of mechanical artifacts
in polyhedral representation based on scale-space feature decomposition~\cite{BESPALOV:SCALE-SPACE}.
Our approach used recent developments in efficient hierarchical
decomposition of metric data using its spectral properties.
Through spectral decomposition, we were able to reduce the problem of
matching to that of computing a mapping and distance measure between
vertex-labeled rooted trees.
This work discusses how Scale-Space decomposition framework could
be extended to extract features from CAD models in polyhedral.
First, we give an overview of the Scale-Space decomposition approach
that is used to extract these features. Second, we discuss performance
of the technique to extract features from CAD data in polyhedral representation.
Third, we show feature extraction process on noisy data -- CAD models that were constructed using 3D scanner.
Finally, we conclude with discussion of future work.
\end{abstract}
\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.
Establishing similarity measure between two 3D models is a very
important problem. There is a number of studies done in this area
(see Section~\ref{sec:related}). In addition, feature extraction
techniques could be used compute partial similarity assessment~\cite{HAN-REGLI-PRATT:FEATURES-R-AND-A-2000,SHAH-FEATURE-DISCOURSE:ASME-JCISE-2001},
provided that an exact representations for the models are provided (i.e. Brep).
Unfortunately, these approaches can not be used if only approximate
representations (i.e. polyhedral) are available. In~\cite{BESPALOV:SCALE-SPACE}
we showed how Scale-Space decomposition could be used to extract
features from 3D models in polyhedral representation.
Our current work extends this approach to address the issue of extracting local features from
3D models in polyhedral representation. In other words, if we are
given only part of an object (for instance, a single 3D laser scan)
we want to be able to extract features from this object and then find complete
objects in our database that have similar features. In this paper,
we discuss local feature extraction process.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 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 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$,
$\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 columns 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
$t_i\in \M$ let $q_i\in \S'$ be the closets face in $\S'$ to $t_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(t_i,\S')^2 &=& \sum_{i=1}^n d(t_i,q_i)^2\\
&=& ||\D-\Q||_F^2\\
&\ge& ||\D-\D^{(k)}||_F^2\\
&=& \sum_{i=1}^n d(t_i,c_i)^2\\
&\ge& \sum_{i=1}^n d(t_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 faces
$t_i\in \M$ with $d(t_i,\S)=d(t_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 face $t_i$ in $\M$ into one of the partitions $\M_j$,
such that the angle between vector $t_i$ and basis vector $c_j$ corresponding
to the partition $\M_j$ is minimized. Figure~\ref{fig:decomp} shows
two decomposition trees of the model -- using geodesic distance and using
new distance based on angular measure.
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
$3n$ (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}
\begin{figure*}[!th]
\begin{center}
\begin{tabular}{cc}
\mbox{\psfig{figure=figs/fig3.eps, width=3.5in}}&
\mbox{\psfig{figure=figs/fig3_2.eps, width=3.5in}}\\
(a)&(b)\\
\end{tabular}
\end{center}
\caption{Feature extraction process. (a) Decomposition tree is obtained using
{\sc Feature-Decomposition($\M,k$)} algorithm. (b) Leaf nodes of the tree
correspond to the features. For illustration purposes only several features
are shown.}
\label{fig:feat_extr}
\end{figure*}
\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 some arbitrary set of faces. 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.
Let $\M$ be the original model's face set. 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$). We say that decomposition of feature $\M_1$
into sub-features $\M_2$ and $\M_3$ is significant if the following condition
is true:
\[ (\forall t_i \in \M_2, t_j \in \M_3 \ \exists t_k \rightarrow t_l \in t_i \leadsto t_j \ . \]\vspace{-0.6in}
\[ t_k \in \M_2 \wedge t_l \in \M_3 \wedge \angle(t_k, t_l)=\D(t_i,t_j)) , \]
and we continue our decomposition process using features $\M_2$ and $\M_3$.
If the condition is false, then decomposition of feature $\M_1$ stops and
this feature is considered to be final. In practice, we allow some small
number of pairs $t_i \in \M_2, t_j \in \M_3$ to not satisfy the above condition
in order for decomposition process to continue. The rationale behind such
approach to control feature extraction process, is to make sure that areas with
significant differences in curvature would get decomposed in separate features.
\section {Experimental Results}
In our experiments we wanted to determine what kind of
features can be extracted using {\sc Feature-Decomposition($\M,k$)}. For that
purpose we have recursively applied {\sc Feature-Decomposition($\M,k$)} to
each model, where $k=2$. Once decomposition trees were obtained, we have considered
leaf nodes of these trees as features. Note that union of the leaf nodes for each
decomposition tree produces initial model. Refer to Figure~\ref{fig:feat_extr}
for the illustration of feature extraction process.
\begin{figure*}[!th]
\begin{center}
\vspace{-0.5in}
\begin{tabular}{cc}
\mbox{\psfig{figure=figs/fig4_part09.eps, height=3.8in}}&
\mbox{\psfig{figure=figs/fig4_part10.eps, height=3.8in}}\\
(a) & (b) \\
\\
\mbox{\psfig{figure=figs/fig4_boeing.eps, height=3.8in}}&
\mbox{\psfig{figure=figs/fig4_cimplex.eps, height=3.8in}}\\
(c) & (d) \\
\end{tabular}
\end{center}
\caption{Extracted Features. Only subset of the features are shown in order to
illustrate what kind of features are extracted.
(a) Part 9, (b) Part 10, (c) Simple Boeing, (d) Cimplex.
}
\label{fig:cad_data}
\end{figure*}
\subsection{CAD data}
We have performed feature extraction on a number of CAD models in polyhedral
representation. These models were converted from ACIS format, which is
exact representation format. As a result, all of the models have nice structure
(i.e. no missing faces).
Figure~\ref{fig:cad_data} shows extracted features for several models.
For each model that we performed feature extraction on, we have observed
the same trend of features. All of the flat and curved surfaces become separate features.
Also, if a curved surface is closed (i.e. hole) then it will be decomposed into
two (i.e. hole) or more (i.e. surface is concave) features.
\subsection{Noisy Data -- Scanned Models}
\begin{figure*}[!th]
\begin{center}
\vspace{-0.5in}
\begin{tabular}{ll}
\mbox{\psfig{figure=figs/fig5_socket.eps, width=3.4in}}&
\mbox{\psfig{figure=figs/fig5_bracket.eps, width=3.7in}}\\
\end{tabular}
\end{center}
\caption{Scanned Data. Only subset of the features are shown in order to
illustrate what kind of features are extracted.
(a) Socket model. Features for fully-scanned model are on the left, and
for partially-scanned on the right. Features are grouped based on correspondence
between full and partial models.
(b) Bracket model. Features for fully-scanned model are on the left, and
for partially-scanned on the right. Features are grouped based on correspondence
between full and partial models.
(c) Additional features for fully-scanned models that are not present in partial scans.
}
\label{fig:scan_data}
\end{figure*}
\begin{figure*}[!th]
\begin{center}
\vspace{-0.5in}
\begin{tabular}{cc}
\raisebox{0.5in}[0pt]{\mbox{\psfig{figure=figs/fig5_ex.eps, width=3.5in}}}&
\mbox{\psfig{figure=figs/fig5_full.eps, width=3.2in}}\\
\\
(a) & (b) \\
\end{tabular}
\end{center}
\caption{Scanned Data. Only subset of the features are shown in order to
illustrate what kind of features are extracted.
(a) Ex model. Features for fully-scanned model are on the left, and
for partially-scanned on the right. Features are grouped based on correspondence
between full and partial models.
(b) Features for the models converted from exact representation format (ACIS).
Note, that features correspond to the features extracted from scanned models.
}
\label{fig:scan_data2}
\end{figure*}
We have decided to observe performance of the feature extraction technique on
the data that is obtained by laser scanner. We used three models to take two
scans -- full and partial (one scan). Once the models were scanned we faceted
them, and then extracted features. Scanned data is known to be very noisy, often
with broken connectivity and missing faces.
Figures~\ref{fig:scan_data}~and~\ref{fig:scan_data2} shows extracted features for scanned models.
The performance of the technique is certainly not as remarkable as on previous data.
Although we believe that the features that are extracted are meaningful and could
be used for partial matching. It is clear that extracted features for fully and partially scanned,
and for converted from exact representation models have correspondence between each other.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% %
% Discussion and Conclusions %
% %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Discussion and Conclusions}
We have introduced a computationally efficient approach to decompose a
3D model in polyhedral representation into features that could be used
to assess similarity between 3D models. The extracted features are invariant
to global structure of a model, as a result similar features could be
extracted even if a part of a model is provided (i.e. single 3D laser scan).
This potentially enables our technique to be used in partial matching
problem. Further, Scale-Space decomposition technique is robust to noise,
therefore it could be used on models that are constructed using devices
such as 3D laser scanners.
The notion of feature presented here is highly tuned to the
efficient identification of shape and topological categories.
Even though, features obtained using our approach could be different
from traditional CAD features, they could be used to establish partial
similarities between CAD models in polyhedral representation.
\begin{figure}[!t]
\begin{center}
\begin{tabular}{cc}
\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}}\\
%\epsffile{figs/fig3.eps}
\end{tabular}
\end{center}
\caption{Results of matching between two {\sc Swivels}, with matched
regions having similar colors. Features trees are
obtained for each model using {\sc Feature-Decomposition($\M,k$)} with
geodesic distance function.}
\label{fig:match}
\end{figure}
Our work is in its preliminary stages, and we plan to extend its scope by
introducing an efficient matching algorithm to assess partial similarity measures.
From the above experiments we conclude that in order to perform successful matching,
the technique must have the following properties: 1) be tolerant to
noise that scanned data introduce; 2) be able to perform many-to-many
matching, since it is possible that a feature could get divided in to
several features; 3) be efficient, so it could be used in the
National Design Repository database~\footnote{{\tt http://www.designrepository.org}}.
One of the main aspects of such matching technique would be
distance function that assigns numerical value to a pair of
features. Our previous work~\cite{BESPALOV:SCALE-SPACE} successfully used
such function, that is based on area and eucledian distance measurements within features.
Please see Figure~\ref{fig:match} for a sample view of two models with matched regions.
The other possible directions for our future work: 1) explore techniques to extract
features that resemble traditional CAD features; and
2) exploit the possibility of using Scale-Space features as signatures for
indexing purposes.
\section*{Acknowledgments}
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.
%The CAD models used in the experiments cover several non-trival
%classes of mechanical artifacts and include parts from several
%industry and governement sources. All of these models are available
%for download from the National Design Repository at URL
%{\tt http://www.designrepository.org/ASME-DETC-03}.
%\bibliographystyle{plain}
\bibliography{dmitriy,wcrefs,ref}
\end{document}