ALGORITHM OF BINARY IMAGE PROCESSING - Fundamentals of Three-Dimensional Digital Image Processing - page 160

Input: skeleton image K ).

f ijk = squared distance value, if a voxel ( i, j, k ) is a skeleton voxel
0 ,

F = { f ijk } ( 1 ≤ i ≤ M, 1 ≤ j ≤ N, 1 ≤ k ≤

otherwise

Output: : squared reverse distance transformation image (all voxels

are initialized as 0 ).
Work array:

G = { g ijk }

G = g ijk }

(all voxels are initialized as 0 ).
(The outside of an input image is regarded as being filled with the value 0
during the processing. Arrays

{

G are assigned physically to the same

G and

memory area.)

[STEP 1] (Fig. 5.14)
(1-1) Input image:

F = { f ijk } ,

Output image: g ijk }

Perform the following procedure row by row, increasing the value of i from
1 to M (forward scan).
(a) If f ijk <f ( i− 1) jk (Fig. 5.7 (a)), perform the following procedure for all
n such as 0

G = {

≤ n ≤ ( f ( i− 1) jk − f ijk − 1 ) / 2 (See Note).

( n + 1 ) 2 , go to the next i .
(a-2) If otherwise and ( g ( i + n ) jk <f ( i− 1) jk −

(a-1) If f ( i + n ) jk ≥ f ( i− 1) jk −

( n + 1 ) 2 ),

( n + 1 ) 2 , and go to the next n .
(a-3) Except the above (a-1) and (a-2), go to the next n .
(b) If f ijk ≥

g ( i + n ) jk ← f ( i− 1) jk −

f ( i− 1) jk (Fig. 5.7 (b)),
(b-1) If g ijk <f ijk ,then g ijk ← f ijk andgotothenext i .

(b-2) If otherwise go to the next i .
(1-2) Input image: G = { g ijk } .

G =

g ijk }

Output image: .

Perform for each row the following procedure, decreasing the value of the
sux i from M to 1 (backward scan).
(a) If g ijk

{

<g ( i +1) jk , perform the following procedure for all n such as

0 ≤ n ≤ ( g ( i +1) jk − g ijk − 1 ) / 2 .

( n + 1 ) 2 , go to the next i .
(a-2) If otherwise and g ( i−n ) jk <g ( i +1) jk −

(a-1) If g ( i−n ) jk ≤ g ( i +1) jk −

( n + 1 ) 2 ,

( n + 1 ) 2 , and go to the next n .
(a-3) Except (a-1) and (a-2) go to the next n .
(b) If ( g ijk ≥

then g ( i−n ) jk ← g ( i +1) jk −

g ( i +1) jk ),
(b-1) If ( g ijk <g ijk ),
g ijk ← g ijk , and go to the next i .

(b-2) If otherwise, go to the next i .

[STEP 2]
Input image: G =

g ijk }

{ .

Note: Here the value n =( f ( i− 1) jk − f ijk − 1 ) / 2 is a crossing point of the square
functions C 1 ( n )= f ijk − n 2 and C 2 ( n )= f ( i− 1) jk − ( n + 1 ) 2 such as n> 0 .