Graphics Reference
In-Depth Information
constraints. Compared with other dimensionality reduction methods, manifold study
approach will preserve the natural connections between data, and make the topological
difference between reconstructed triangulation and the real object surface smaller. So
we use ISOMAP[17]algorithm one of typical manifold study for the triangulation
reconstruction in this paper.
ISOMAP algorithm is proposed based on Multidimensional Scaling Analysis
(MDS). It preserves the geometric feature of manifold globally. The idea of ISOMAP is
similarity preserving, transforming data from high dimensional space to low
dimensional space, preserving the inner geometric relationship (preserving the
geodesic distance between two points) between data points. In the MDS, distance
matrix is constructed base on Euclidean distances of original data points. What is
different in ISOMAP, the distance matrix is constructed base on geodesic distances.
Because the geodesic distance is represented by integral form in continuous space, It is
impossible be used in discrete computation directly. So the in ISOMAP, shortest path
distance is used in ISOMAP for the approximation of the geodesic distance. ISOMAP
algorithm is a global method for preserving the geodesic distances for the all data
points.
ISOMAP algorithm could be described by three steps as follow:
(1)Construct the neighborhood criterion structure
Firstly, the criterion structure of neighborhood relationship is constructed in this
step. Then the adjancy graph is created based on the above mentioned criterion
structure. The neighborhood relationship is judged by the Euclidean distances between
data points. Suppose the number of data points is N . A N
N Euclidean distance matrix
G E is constructed: for any two data points x i and x j , if the Euclidean distance between
them is less than a given threshold
×
ε
, or x j is one k-neighbor of x i , G E ( i,j )= Dist E ( x i , x j )
Where Dist E (
.
,
.
) denotes the Euclidean distance between these two points. Otherwise,
G E ( i,j )=
.
(2)Compute the shortest path
This step is used to estimate the geodesic distances between data points. First, a N
N
shortest path matrix G S is created. The elements in G S is judged using the
corresponding value in G E : G S ( i,j )=
×
, if G E ( i,j )=
; otherwise G S ( i,j )= Dist S ( x i , x j ),
where Dist S (
) denotes the shortest path distance between these two points. In this
step, Dijkstra algorithm can be used for the shortest path calculation.
(3)Compute the low dimensional embedding Y
By using the classical MDS method, the low dimensional embedding Y is
calculated based on the shortest path distance matrix (the approximation of geodesic
distance matrix). Assume H =-( I n - η n η n T / n ) G S ( I n - η n η n T / n )/2 , where I n is a n-order identity
matrix, and η n =[1,…,1] T R n . Suppose ʻ 1 , ʻ 2 ,…, ʻ d are the largest d eigenvalues of H ,
and their corresponding eigenvectors are ʲ 1 , ʲ 2 ,…, ʲ d . The final low dimensional
embedding Y = diag ( ʻ 1 1/2 , ʻ 2 1/2 ,…, ʻ d 1/2 )[ ʲ 1 , ʲ 2 ,…, ʲ d ] T .
.
,
.
Search WWH ::




Custom Search