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

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

198 J. Rivera-Rovelo et al.

Fig. 2 Example of the dense vector ﬁeld called GGVF (not the whole vector ﬁeld is shown, but

only representative samples of a grid). (a) Samples of the vector ﬁeld for a 2D image; (b) Samples

of the vector ﬁeld for volumetric data; (c) Example of streamlines for particles arranged in a 32×32

grid according to the vector ﬁeld shown in (a); (d) Points selected as input patterns according

to (22)

in position x

(assuming that it is binarized). As some streamlines can carry to the

same point or very close points, we can add constraints to avoid very close samples;

one very simple restriction is that the candidate to be included in the input set must

be at least at a ﬁxed distance d

thresh

of any other input.

Figure 2(c) shows the streamlines according to the vector ﬁeld shown in Fig. 2(a)

and the input patterns selected as described before are shown in Fig. 2.

3.2 Learning the Shape Using Versors

It is important to note that although we will explain the algorithm using points, the

versors can be applied to any entity in GA that we had selected to model the object.

The network starts with a minimum number of versors (neural units), and new units

are inserted successively. The network is speciﬁed by

• A set of units (neurons) named N , where each n

∈ N has its associated versor

; each versor is the transformation that must be applied to a point to place it

in the contour of the object. The set of transformations will ultimately describe

the shape of the object.

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

• A set of connections between neurons deﬁning the topological structure.

Also, take into account that

• There are two learning parameters, e

and e

, for the winner neuron and for the

direct neighbors of it; such parameters remain constant during all the process.

• Each neuron n

will be composed by its versor M

,thesignal counter sc

, and

the relative signal frequency rsf

. The signal counter sc

is incremented for the

neuron n

every time it is the winner neuron. The relative signal frequency rsf

deﬁned as

rsf



∀n

. (23)

This parameter will act as an indicator to insert new neural units.

With these elements, we deﬁne the learning algorithm of the GNG to ﬁnd the

versors that will deﬁne the contour as follows:

1. Let P

be a ﬁxed initial point over which the transformations will be applied.

This point corresponds to the conformal representation of p

, which can be a

random point or the centroid deﬁned by the inputs. The initial transformations

will be expressed as M =e

−

∞

in the conformal geometric algebra. The vector

t initially is a random displacement.

2. Start with the minimal number of neurons, which have associated random motors

M and a vector v

=[u

], whose magnitude is interpreted as the capacity

of learning for such neuron.

3. Select one input ζ from the inputs set I and ﬁnd the winner neuron; this means

ﬁnding the neuron n

having the versor M

which moves the point P

closer to

such input:

win

=min

∀M





−MP



. (24)

4. Modify M

win

and all others versors of neighboring neurons M

in such a way that

the modiﬁed M will represent a transformation moving the point P

nearer the

input. Note that each motor is composed by a rotation ΔR and a translation ΔT .

The rotation is computed as in (16), θ being the angle between the actual position

a and a



=a +v (v is the GGVF vector value in such position); the bivector dual

to the rotation axis is computed as in (14); the rotors and translators are deﬁned

ΔR

win

= e

η(v

win

)

θb

, (25)

ΔT = e

−

Δt

win

∞

, (26)

Δt

win

= e

η(v

, v

win

)(x

−p

) (27)

for the winner neuron, and

ΔR

= e

η(v

)

θb

, (28)

200 J. Rivera-Rovelo et al.

ΔT = e

−

Δt

∞

, (29)

Δt

= e

η(v

, v

)(x

−p

) (30)

for its direct neighbors, to obtain ΔM =ΔT ΔR. Finally, the new motor is

new

=ΔMM

old

, (31)

φ is a function deﬁning the amount a neuron can learn according to its distance

to the winner one (deﬁned as in (32)), and η(v

, v

) is deﬁned as in (33).

φ =e

−

win

−M

)

2σ

, (32)

η(v

, v

) =v

−v



, (33)

which is a function deﬁning a quantity of learning depending on the strength to

teach of the input ζ and the capacity to learn of the neuron, given in v

and v

respectively. Also update

new

win

= v

win

, (34)

new

= v

. (35)

5. Every certain number λ of iterations, determine the neuron with the rsf

with

highest value. Then, if any of the direct neighbors of that neuron is at a distance

larger than c

max

,do

• Determine neighboring neurons n

and n

• Create a new neuron n

new

between n

and n

whose associated M and v

will

new

, v

l_new

; (36)

the new units will have the values sc

new

=0 and rsf

new

=0.

• Delete the old edge connecting n

and n

and create two new edges connecting

new

with n

and n

6. Repeat Steps 3 to 5 if the stopping criterion is not achieved. The stop criterion is

when a maximum number of neurons is reached or when the learning capacity

of neurons approaches to zero (is less than a threshold c

min

), and the ﬁrst that

happens stops the learning process.

Training the network, we ﬁnd the set of M deﬁning positions on a trajectory; such

positions minimize the error measured as the average distance between X

and the

result of M

χ =



∀ζ



−X

)

, (37)

where M

moves P

closer to input X

, and N is the number of inputs.

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

4 Experiments

Figure 3 shows the result when the algorithm is applied to a magnetic resonance

image (MRI); the goal is to obtain the shape of the ventricle. Figure 3(a) shows the

original brain image and the region of interest (ROI); Fig. 3(b) shows the computed

vector ﬁeld for the ROI; Fig. 3(c) shows the streamlines in the ROI deﬁned for

particles placed on the vertices of a 32×32 grid; Fig. 3(d) shows the initial shape as

deﬁned for the two initial random motors M

;Fig.3(e) shows the ﬁnal shape

obtained; and ﬁnally Fig. 3(f) shows the original image with the segmented object.

Figure 4 presents an image showing that our approach can also be used for au-

tomated visual inspection tasks; reader can observe that such image contains a very

blurred object. That image is for the inspection of hard disk head sliders. Figure 4(a)

shows the original image and the region of interest (ROI); Fig. 4(b) shows the com-

puted vector ﬁeld of the ROI; Fig. 4(c) shows the streamlines deﬁned for particles

placed on the vertices of a 32 × 32 grid; Fig. 4(d) shows the inputs selected ac-

cording the streamlines and the initial shape as deﬁned for the two initial random

motors M

and M

; and Fig. 4(e) shows the ﬁnal shape obtained overlapped with

the original image, showing that the algorithm gives good results if it is used for

segmentation.

Fig. 3 (a) Original image and region of interest (ROI); (b) Zoom of the dense vector ﬁeld of the

ROI; (c) Zoom of the streamlines in ROI; (d) Inputs and initial shape; (e) Final shape deﬁned

according the 54 estimated motors; (f) Image segmented according the results

202 J. Rivera-Rovelo et al.

Fig. 4 Application in visual inspection tasks: (a) Original image and the region of interest (ROI);

(b) Zoom of the dense vector ﬁeld of the ROI; (c) Zoom of the streamlines in ROI; (d) Inputs and

initial shape according the two initial random transformations M

and M

;(e) Final shape deﬁned

according the 15 estimated motors (original image with the segmented object)

Figure 5 shows the application of the ggvf-snakes algorithm in the same problem.

It is important to note that although the approaches of Figs. 4 and 5 use GGVF

information to ﬁnd the shape of an object, the estimated ﬁnal shape using the neural

approach is better than the one using active contours; the second approach (see

Fig. 5) fails to segment the object no matter if the initialization of the snake is given

inside, outside, or over the contour we are interested in. Additionally, the fact of

expressing such shape as a set of motors allows us to have a model best suited to

be used in further applications which can require the deformation of the model,

especially if such model is not based on points but on the other GA entities, because

we do not need to change the motors (recall that they are applied in the same way to

any other entity).

The proposed algorithm was applied to different sets of medical images. Figure 6

shows some images of such sets. The ﬁrst row of each ﬁgure shows the original im-

age and the region of interest, while the second row shows the result of the proposed

approach. Table 1 shows the errors obtained with our approach using and not using

the GGVF information. We can observe that the inclusion of GGVF information

improves the approximation of the surface.

To compare our algorithm, we use the GNG with and without GGVF information,

as well as a growing version of SOM, also using and not using the GGVF informa-

tion. These algorithms were applied to a set of 2D medical images (some obtained

with computer tomography (CT) and some with magnetic resonance (MR)). Figure

7(a) shows the average errors when GSOM stops for different examples: segment-

ing a ventricle, a blurred object, a free form curve, and a column disk. Note that

using the GGVF information the error is reduced. This means that using the GGVF

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

Fig. 5 Result obtained when using the active contour approach to segment the object in the same

image as in Fig. 4.(a) Initialization of snake inside the object; (b) Final result obtained with initial-

ization showed in (a); (c) Initialization of snake outside the object; (d) Final result obtained with

initialization showed in (c); (e) Initialization of snake over the contour; (f) Final result obtained

with initialization showed in (e)

Fig. 6 First row (upper row): original image and the region of interest. Second row:Resultof

segmentation

information, as we propose, a better approximation of the object shape can be ob-

tained. Figure 7(b) shows the average errors obtained for several examples but using

the GNG with and without the GGVF information. Note that again, the GGVF con-

tributes to obtain a better approximation to the object surface. Also note that the

average errors obtained with the GNG algorithm are smaller than the errors ob-

204 J. Rivera-Rovelo et al.

Table 1 Errors obtained by

the algorithm with and

without the GGVF

information. ε

: error without

GGVF; ε

: error with GGVF

Example ε

Ventricle 1 3.29 2.51 Eye 1 7.63 6.8

Eye 2 3.43 2.98 Column disk 1 4.65 4.1

Tumor 1 3.41 2.85 Tumor 2 2.95 2.41

Free form curve 2.84 1.97 Column disk 2 2.9 2.5

Fig. 7 (a) Average errors for different examples using the GSOM algorithm with and without

GGVF information; (b) Average errors for different examples using the GNG algorithm with and

without GGVF information; (c) Comparison between the errors obtained with GSOM and GNG

using and without using GGVF information. Note that both are improved with GGVF information,

although GNG gives better results

tained with the GSOM, as can be seen in Fig. 7(c) and that both are improved with

GGVF information, although GNG gives better results.

It is necessary to mention that the whole process is quick enough; in fact, the

computational time required for all the images showed in this work took only few

seconds. The computation of the GGVF is the most time-consuming task in the

algorithm, but it only takes about 3 seconds for 64 × 64 images, 20 seconds for

256 ×256 images, and 110 seconds for 512 × 512 images. This is the reason why

we decide not to compute it for the whole image but only for selected region of

interest. The same criterion was applied to 3D examples.

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

Fig. 7 (Continued)

206 J. Rivera-Rovelo et al.

Fig. 8 The algorithm for 3D object’s shape determination. (a) 3D model of the patient’s head

containing a tumor in the marked region; (b) Vectors of the dense GGVF on a 3D grid arrangement

of 32 × 32 ×16; (c) Inputs determined by GGVF and edge map and the initialization of the net

GNG; (d)–(e) Two stages during the learning; (f) Final shape after training has ﬁnished with a total

of 170 versors M (associated with 170 neural units)

Figure 8(a) shows the patient head with the tumor which surface we need to

approximate; Fig. 8(b) shows the vectors of the dense GGVF on a 3D grid arrange-

ment of size 32 × 32 × 16; Fig. 8(c) shows the inputs determined by GGVF and

edge map and also shows the initialization of the net GNG; and Figs. 8(d)–(f) show

some stages of the adaptation process, while the net is determining the set of trans-

formations M (Fig. 8(f) is the ﬁnal shape after training has ﬁnished with a total of

170 versors M (associated with 170 neural units)).

Figure 9 shows another 3D example, corresponding to a pear, and the surface

is well approximated. Figure 9(b) shows the inputs and the initialization of the net

with nine neural units (the topology of the net is deﬁned as a sort of pyramid around

the centroid of input points); while Fig. 9(c) shows the result after the net has been

reached the maximum number of neurons, which was ﬁxed to 300; ﬁnally, Fig. 9(d)

shows the minimization of the error according to (37).

Another useful application of the algorithm using the gradient information of the

GGVF during the training of the GNG neural net in the geometric algebra frame-

work is the transformation of one model obtained at time t

into another obtained at

time t

(a kind of morphing of 3D surfaces).

Figure 10(a) shows the initial shape which will be transformed into the one

showed in Fig. 10(b); Figs. 10(c)–(f) show some stages during the process. Note

that Fig. 10(f) looks like Fig. 10(b), as expected.

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

Fig. 9 3D object shape deﬁnition for the case of a pear. (a) Inputs to the net selected using GGVF

and streamlines; (b) Inputs and the initialization of the net with nine neural units; (c) Result after

the net has been reached the maximum number of neurons (300 neurons); (d) Error measurement

using (37)

Fig. 10 The 3D surface shown in (a) is transformed into the one shown in (b). Different stages

during the evolution are shown in (c)to(f), where (f) is the ﬁnal shape (that is, the ﬁnal shape of

(a)) after ﬁnishing the evolution of the net, which should look like (b)

In the case shown in Fig. 11, we have one 3D model with an irregular shape

which will be transformed to take a shape similar to a pear; Fig. 11(a) shows the

initial shape which will be transformed into the one showed in Fig. 11(b); Figs.

11(c)–(f) show some stages during the process. Again, the resulting volume looks

like the one expected (Fig. 11(b)).

To illustrate the application of the presented algorithm in cases having mod-

els based on entities different to the points, we show in Fig. 12 models based on

spheres [8]. The goal is the same: morphing the model shown in Figs. 12(a) and

12(d) to the one showed in Figs. 12(b) and 12(e), respectively. The results are shown

in Figs. 12(c) and 12(f).