Page 257 -

Chapter 6 ■ Thinning 231

on the corners act in opposite directions. Those squares containing skeletal
areas are further subdivided, and the location of the skeletal area is recursively
refined as far as necessary or possible.
The change in the direction of the force is found by computing the dot
product of each pair of force vectors on corners of the square regions:
ˆ ˆ
d 1 = f 1 · f 2
ˆ ˆ (EQ 6.6)
d 2 = f 2 · f 3
ˆ ˆ
d 3 = f 1 · f 4
If any one of d 1 , d 2 ,or d 3 is negative, then the region involved contains some
skeletal area.
To compute the force vector at each pixel location is time-consuming. For
each object pixel, a straight line is drawn to all marked pixels on the object
outline. Lines passing through the background are discarded, as illustrated
in Figure 6.21, and for each of the remaining lines a vector with length 1/r 2
and direction from the outline pixel to the object pixel is added to the force
vector at that pixel. A graphical illustration of the force calculation is given in
Figure 6.22.
This is done for all object pixels; then recursive subdivision can be used to
refine the positions of the skeletal areas. From any endpoints of the skeleton
found in the previous stage, we consider growing this skeletal line until it hits
another skeleton or an edge. If it hits itself, the loop grown thereby is deleted.

f 1 f 2

f 4 f 3

(a) (b)
Pixels exerting a force
“Invisible” pixels

Object pixels
Pixel under consideration
Figure 6.21: (a) When computing the force at a pixel, only the ‘‘visible’’ pixels are
considered. The object insulates the others from having an influence. (b) The calculation
of the dot product determines whether the force becomes zero somewhere in the pixel
being tested.