polygon can be determined concurrently in the net-
work.
Let a;; represent the output of the neuron at posi-
tion (i,j),where 0<<i,j<n. The best match out of
the 2 comparisons can be determined by the following
procedures.
Step 1: Calculate the number of active neurons
from each of the » comparisons by the following e-
quation :
Aa-l »—1
Match (k) — D> Surman is OK «n. (19)
i=0 j=0
Step 2: Determine the best match by
Maz Maích(m) — maz [Match (k)], 0sk«n.
Step 3: If the best match measure Maz match (m)
is larger than a threshold 6,then the original vertex
correspondenee matrix as follows :
15 if ài= (j —m)mod n
otherwise (20)
0 xx$,j «Cm and Os;mo« n.
In the first step, (19)is used to calculate the number
of active neurons in each of the » comparisons. In the
second step,the results derived from Step 1 are com-
pared and the one that contains the largest number of
active neurons is selected. In the third step,it is inted-
ed to generate the best vertex correspondence matrix
by removing all ambiguities. All the neurons corre-
sponding to the best match are activated by applying
(17). Those neurons irrelevant to the activated neu-
ron set are then inactivated.
a;; = 0,
D, Discussion
Being designed as a constraint satisfaction net-
work ,the Hopfield net may encounter problems such
as multiple active neurons in a row or column after it
is stabilized. This is because the given set of con-
straints is not adequate for singling out the optimal
solution. However ,a procedure which takes advan-
tage of the fact that the vertex ordering of a polygon
is preserved under any rotation in 2-D space is de-
signed to determine the best vertex correspondences.
This procedure is valid even if some intermediate ver-
tices are not matched due to distortion caused by
changing viewpoints.
We have mentioned that ‚at the surface correspon-
dence stage,a set of object models are selected from
the model database due to higher surface matching
measures. The vertex correspondence establishment
can be considered as a fine search process. At this
stage, we eliminate those object models unable to est-
blish any consistent vertex correspondence with the
input image. The discarded object models may include
the folliwing:l1)those which are actually the projec-
tions of different objects but were accidentally picked
up;and 2)those which are projections of the same ob-
ject but are quite different from the input image.
of the features for surface matching. Among the ob-
ject models whose vertices of the kernel region match
those of the input image,the one with the highest
surface matching score and the largest number of ver-
tex correspondences is finally selectde as the largest
number of vertex correspondences is finally selected
as the best matched model. Since the pose of the
viewpoint where the best matched object model is vi-
sualized is predetermined in the modeling phase , the
pose of the unknown object can be obtained by com-
puting a 2-D rotation which brings the vertices in the
input image to align with thcir corresponding vertices
in the best matehed object model.
V.CONCLUSIONS
In this paper, we use Hopfield networks to solve
both the surface and vertex correspondence problems
for 3-D object recognition. The proposed scheme can
be considered as a coarse-to-fine search process. In a
3-D object recognition system adopting multiple-view
approach ‚the database is usually a set of 2-D projec-
tions which are topologically different. By calculating
the surface matching score between the input image
and each object model in the model database ‚a set of
2-D models with higher surface matching score is se-
lected. This phase can be considered as a coarse
search process. The object models selected from the
first stage are then fed into the Hopfield net for es-
tablishing the vertex correspondences between the in-
put image and each of these models. This phase is the
fine search process. The object model that has the
best vertex and surface correspondences with the in-
put image is finally selected. Once an object model is
identified , we can use the model coordinate frame as
the reference frame to derive the pose of the un-
known object.
In comparison with conventional methods, there
are several advantages in using Hopfield nets for im-
age matching. Image matching can be regarded as a
process of finding homomorphisms between two rela-
tional structures and is basically an NP-complete
problem. In the worst case,its time complexity is ex-
pected to be exponential. In order to speed up the
performance, several methods adopting look-ahead or
relaxation [19], [20] schemes have been proposed.
However, in general, it takes more effort to manage
a look-ahead table or devise a relaxation algorithm. A
Hopfield network takes advantage of its massively
parallel structure to deal with matching problems in
an elegant and systematic manner and quantitatively
reflects the degree of similarity in the final states of
the neurons. The formulation of the network struc-
ture is simple and the matching process is easy to im-
plement.
1016
International Archives of Photogrammetry and Remote Sensing. Vol. XXXI, Part B3. Vienna 1996
They were mistakenly selected due to the roughness
[1]P. J.»d
object
vol. 17
[2]M. Osh
ing t
T rans.
MI-5,
[3]R. T^€
nition
vol. 1
[4 ]I. Chal
views
recogn
Eng ,
[5]H. Fr
charac
mensic
Eds. ,
dam :
277-2
[6]L. Sta
graph:
recogr
Sion » |
507.
[7] Y.Zh:
minim
tion",
pp. 13
[8]J. J. H
tion o
olog .
[9]— ‚°C
Scienc
[10] W. ]
based
field -s
