Bayro-Corrochano E., Scheuermann G. Geometric Algebra Computing: in Engineering and Computer Science

Подождите немного. Документ загружается.

Part III

Image Processing, Wavelets and

Neurocomputing

Geometric Neural Computing for 2D Contour

and 3D Surface Reconstruction

Jorge Rivera-Rovelo,

Eduardo Bayro-Corrochano,

and Ruediger Dillmann

Abstract In this work we present an algorithm to approximate the surface of 2D

or 3D objects combining concepts from geometric algebra and artiﬁcial neural net-

works. Our approach is based on the self-organized neural network called Grow-

ing Neural Gas (GNG), incorporating versors of the geometric algebra in its neural

units; such versors are the transformations that will be determined during the train-

ing stage and then applied to a point to approximate the surface of the object. We

also incorporate the information given by the generalized gradient vector ﬂow to

select automatically the input patterns, and also in the learning stage in order to im-

prove the performance of the net. Several examples using medical images are pre-

sented, as well as images of automatic visual inspection. We compared the results

obtained using snakes against the GSOM incorporating the gradient information

and using versors. Such results conﬁrm that our approach is very promising. As a

second application, a kind of morphing or registration procedure is shown; namely

the algorithm can be used when transforming one model at time t

into another at

time t

. We include also examples applying the same procedure, now extended to

models based on spheres.

1 Introduction

To approximate the contour or surface of an object is a task that can be carried

out by different methods. If we want to preserve the topology of the data, a good

choice is the use of self-organizing neural networks [1]. In this work we propose a

J. Rivera-Rovelo (



)

Universidad Anahuac Mayab, Carr. Merida-Progreso Km. 15.5, Merida, Mexico

e-mail: jorge.rivera@unimayab.edu.mx

E. Bayro-Corrochano (



)

Dept. Electrical Eng. & Computer Science, CINVESTAV, Unidad Guadalajara, Av. Cientíﬁca

1145, 45015 Colonia el Bajío, Zapopan, JAL, Mexico

e-mail: edb@gdl.cinvestav.mx

E. Bayro-Corrochano, G. Scheuermann (eds.), Geometric Algebra Computing,

DOI 10.1007/978-1-84996-108-0_10, © Springer-Verlag London Limited 2010

191

192 J. Rivera-Rovelo et al.

very advanced algorithm using early vision preprocessing and self-organizing neural

computing in terms of geometric algebra techniques. Other similar approaches can

be found in [3, 7]. We believe that the early vision preprocessing, together with

self-organizing neurocomputing, resembles in certain manner the geometric visual

processing in biological creatures.

The proposed approach uses the Generalized Gradient Vector Flow (GGVF) [10]

to guide the automatic selection of the input patterns and to guide the learning pro-

cess of the self-organized neural network GNG [4], to obtain a set of transforma-

tions M expressed in the conformal geometric algebra framework. In this framework

rigid body transformations of geometric entities (like points, lines, planes, circles,

spheres) are expressed in compact form as operators called versors that are applied

in a multiplicative way to any entity of the conformal geometric algebra. Thus, train-

ing the network, we obtain the transformation that can be applied to entities resulting

in the deﬁnition of the object contour or shape. The experimental results show ap-

plications in medical image processing and visual inspection tasks, conﬁrming that

our approach is very promising.

2 Geometric Algebra

The Geometric Algebra [2, 6, 9] G

p,q,r

is constructed over the vector space V

p,q,r

where p,q,r denote the signature of the algebra; if p =0 and q =r =0, the metric

is Euclidean; if only r = 0, the metric is pseudo-Euclidean; if p = 0,q= 0, and

r =0, the metric is degenerate. In this algebra, we have the geometric product which

is deﬁned as in (1) for two vectors a,b and has two parts: the inner product a ·b is

the symmetric part, while the wedge product a ∧b is the antisymmetric part:

ab =a ·b +a ∧b. (1)

The dimension of G

n=p,q,r

is 2

, and G

is constructed by the application of the

geometric product over the vector basis e

⎧

⎪

⎨

⎪

⎩

1fori =j ∈1,...,p,

−1fori =j ∈p +1,...,p+q,

0fori =j ∈p +q +1,...,p+q +r,

∧e

for i =j.

This leads to a basis for the entire algebra: {1}, {e

}, {e

∧e

}, {e

∧e

},...,{e

∧

∧···∧e

}. Any multivector can be expressed in terms of this basis. In the nD

space there are multivectors of grade 0 (scalars), grade 1 (vectors), grade 2 (bivec-

tors), grade 3 (trivectors), ..., up to grade n. This results in a basis for G

con-

taining elements of different grade called blades (e.g., scalars, vectors, bivectors,

trivectors, etc.): 1,e

,...,e

123

,...,I, which are called basis blades, where

the element of maximum grade is the pseudoscalar I = e

∧ e

···∧e

. A linear

combination of basis blades, all of the same grade k, is called k-vector. The linear

combination of such k-vectors is called multivector, and multivectors with certain

Geometric Neural Computing for 2D Contour and 3D Surface Reconstruction 193

characteristics represent different geometric objects (as points, lines, planes, circles,

spheres, etc.), depending on the GA where we are working on. Given a multivec-

tor M, if we are interested in extracting only the blades of a given grade, we write

M

, where r is the grade of the blades we want to extract (obtaining a homoge-

neous multivector M



or an r-vector).

The reverse of a multivector is given by



†



=(−1)

i(i−1)

M

. (2)

That is, the reversion is a linear mapping that inverts the geometric product’s order

and stays in the same space.

2.1 The OPNS and IPNS

In Geometric Algebra, the blades have geometric meaning based on their interpre-

tation as linear subspaces. For example, suppose that you have a vector a ∈R

;we

deﬁne the function O

:x ∈R

→x ∧a ∈G

where G

is the Clifford Algebra over the space R

.Thekernel of this function

is the set of vectors in R

such that O

maps to zero. This kernel is named Outer

Product Null Space (OPNS) of a and is denoted by NO(a). From the wedge product

deﬁnition we know that x ∧a =0 given that x and a are linearly dependent. Thus,

NO(a) can be expressed in terms of a as

NO(a) ={αa :α ∈R}.

In general, the OPNS of a k-blade A

∈ G

is a k-dimensional linear subspace

of R



A





x ∈R

:x ∧A



. (3)

The Inner Product Null Space (IPNS) of a blade A

∈G

, denoted as NI(A

is the kernel of the function I

A

deﬁned as

A

:x ∈ R

→x ·I

A

∈G

. (4)

Thus, the kernel is



A





x ∈R

A

(x) =0 ∈G



. (5)

For example, consider a vector a ∈R

; then NI(a) is given by

NI(a) :=



x ∈R

:x ·a =0



194 J. Rivera-Rovelo et al.

That is, all vectors that are perpendicular to the vector a belong to its IPNS. The

representation of an entity expressed in the IPNS can be obtained from its corre-

sponding OPNS representation by multiplying the latter by the pseudo-scalar of the

GA we are working on. Sometimes the OPNS representation is called dual repre-

sentation.

2.2 Conformal Geometric Algebra

To work in Conformal Geometric Algebra (CGA) G

4,1,0

means to embed the Eu-

clidean space in a higher-dimensional space with two extra basis vectors which have

particular meaning; in this way, we represent particular objects of the Euclidean

space with subspaces of the conformal space. The vectors we add are e

and e

−

which square to 1 and −1, respectively. With these two vectors, we deﬁne the null

vectors

−

−e

), e

∞

=(e

−

), (6)

interpreted as the origin and the point at inﬁnity, respectively. From now and in the

rest of the paper, points in the 3D-Euclidean space will be denoted in lowercase

letters, while conformal points in uppercase letters; also the conformal entities will

be expressed in the Inner Product Null Space (IPNS, Sect. 2.1) and not in the Outer

Product Null Space (OPNS, Sect. 2.1) unless it is speciﬁed explicitly. To map a point

x ∈V

to the conformal space in G

4,1

,weuse

X =x +

∞

. (7)

As mentioned before, we can use CGA to represent particular objects of the 3D-

Euclidean space; the spheres are specially interesting because they are the basic

entities in CGA from which other entities are derived. Spheres with center c and

radius ρ are represented as

S =c +



−ρ



∞

. (8)

In fact, we can think in conformal points X as degenerated spheres of radius ρ =0.

Let X

be two conformal points. If we subtract X

from X

, we obtain

−X

=(x

−x

) +



−x



∞

, (9)

and if we square this result, we obtain

−X

)

=(x

−x

)

. (10)

Geometric Neural Computing for 2D Contour and 3D Surface Reconstruction 195

So, if we want a measure of the Euclidean distance between the two points, we

can apply (10). To obtain the 3D magnitude of a vector, we simply multiply its

conformal representation X as follows:

|x|=



−2(X ·e

). (11)

The dot product between two conformal vectors X

and X

results in X

· X

·x

) −

−

; therefore,

·x

·X

. (12)

Then, the angle θ between two vectors X

and X

in their conformal representation

can be computed using (12) and (11):

θ =arccos



·X

||x



. (13)

On the other hand, to compute the perpendicular vector x

∈ E

to the vectors X

and X

, we ﬁrst compute the wedge product A = X

∧ X

, and then we take the

coefﬁcients of the components e

, represented as A

, A

which deﬁne the plane b dual to the vector, to ﬁnally obtain the perpendicular vector

multiplying by I

∧e

x3 =I

(b) =I



A

∧e

+A

∧e

+A

∧e



. (14)

Note that the bivector b =A

∧e

+A

∧e

+A

∧e

can be used to

build a rotor as explained further. Reader is encouraged to see the CGA representa-

tion of other entities consulting [9]. All such entities and its transformations can be

managed easily using the rigid body motion operators described further.

2.3 Rigid Body Motion

In GA there exist speciﬁc operators named versors to model rotations, translations,

and dilations and are called rotors, translators, and dilators, respectively. In general,

aversorG is a multivector which can be expressed as the geometric product of

nonsingular vectors,

G =±a

...a

. (15)

In CGA, such operators are deﬁned by (16), (17), and (18), R being the rotor, T the

translator, and D

the dilator:

R = e

θb

, (16)

T = e

−

∞

, (17)

= e

−log(λ)∧E

, (18)

196 J. Rivera-Rovelo et al.

where b is the bivector dual to the rotation axis, θ is the rotation angle, t ∈E

is the

translation vector, λ is the factor of dilation, and E =e

∞

∧e

Such operators are applied to any entity of any dimension by multiplying the

entity by the operator from the left and by the reverse of the operator (Sect. 2)from

the right. Let X

be any entity in CGA; then to rotate it, we do X



=RX

R, while

to translate it, we do X



=TX

T , and to dilate it, we use X



3 Determining the Shape of an Object

To determine the shape of an object, we can use a topographic mapping which uses

selected points of interest along the contour of the object to ﬁt a low-dimensional

map to the high-dimensional manifold of such contour. This mapping is commonly

achieved by using self-organized neural networks as Kohonen’s Maps (SOM) or

Neural Gas (NG) [5]; however, if we desire a better topology preservation, we

should not specify the number of neurons of the network a priori (as speciﬁed for

neurons in SOM or NG, together with its neighborhood relations) but allow the net-

work to grow using an incremental training algorithm, as in the case of the Growing

Neural Gas (GNG) [4]. In this work we follow the idea of growing neural networks

and present an approach based on the GNG algorithm to determine the shape of ob-

jects by means of applying versors of the CGA, resulting in a model easy to handle

in post processing stages; a scheme of our approach is shown in Fig. 1. The neural

network has versors associated to its neurons, and its learning algorithm determines

their parameters that best ﬁt the input patterns, allowing us to get every point on the

contour by interpolation of such versors.

Additionally, we modify the acquisition of input patterns by adding a prepro-

cessing stage which determines the inputs to the net; this is done by computing the

Generalized Gradient Vector Flow (GGVF) and analyzing the streamlines followed

by particles (points) placed on the vertices of small squares deﬁned by dividing

the 2D/3D space in such squares/cubes. The streamline or the path followed by a

particle that is placed on x = (x,y,z) coordinates will be denoted as S(x).The

Fig. 1 A block diagram of our approach

Geometric Neural Computing for 2D Contour and 3D Surface Reconstruction 197

information obtained with GGVF is also used in the learning stage as explained

further.

3.1 Automatic Samples Selection Using GGVF

In order to select automatically the input patterns, we use the GGVF [10], which is a

dense vector ﬁeld derived from the volumetric data by minimizing a certain energy

functional in a variational framework. The minimization is achieved by solving lin-

ear partial differential equations, which diffuses the gradient vectors computed from

the volumetric data. To deﬁne the GGVF, the edge map is deﬁned at ﬁrst as

f(x) :Ω →R. (19)

For the 2D image, it is deﬁned as f (x,y) =−|∇G(x,y) ∗I(x,y)|

, where

I(x,y) is the gray level of the image on pixel (x, y), G(x,y) is a 2D Gaussian

function (for robustness in presence of noise), and ∇ is the gradient operator.

With this edge map, the GGVF is deﬁned as to be the vector ﬁeld v(x,y,z) =

[u(x,y,z),v(x,y,z),w(x,y,z)] that minimizes the energy functional

E =





|∇f |



∇

v −h



|∇f |



(v −∇f), (20)

where



|∇f |



−

|∇f |

and h



|∇f |



=1 −g



|∇f |



, (21)

and μ is a coefﬁcient. An example of such dense vector ﬁeld obtained in a 2D image

isshowninFig.2(a), while an example of the vector ﬁeld for a volumetric data is

showninFig.2(b). Observe the large range of capture of the forces in the image. Due

to this large capture range, if we put particles (points) on any place over the image,

they can be guided to the contour of the object. The automatic selection of input

patterns is done by analyzing the streamlines of points on a 3D grid topology deﬁned

over the volumetric data. This means that the algorithm follows the streamlines of

each point of the grid, which will guide the point to the more evident contour of

the object; then the algorithm selects the point where the streamline ﬁnds a peak in

the edge map and gets its conformal representation X as in (7) to make the input

pattern set. Additionally to the X (conformal position of the point), the inputs have

the vector v

=[u, v, w] which is the value of the GGVF in such pixel and will be

used in the training stage as a parameter determining the amount of energy the input

has to attract neurons. This information will be used in the training stage together

with the position x for learning the topology of the data. Summarizing, the input set

I will be

I =



, v

∈S







and f(x

) =1



, (22)

where X

is the conformal representation of x

; x

∈S(x



) means that x

is on the

path followed by a particle placed in x



, and f(x

) is the value of the edge map