Image Processing

Adaptive Shape Contour Tracing Algorithm

by Emad Attalla, Ph.D.

ABSTRACT

In this paper we are going to present a new shape contour tracing algorithm called

¡§Adaptive Contour Tracing Algorithm¡¨. The algorithm can trace open and closed

discontinuous digital shapes and return an ordered set of boundary points that represent

the contour of the shape. Unlike other algorithms that return boundary points that are

part of the traced shape, our algorithm returns background points that are adjacent to the

shape¡¦s contour. Furthermore, the algorithm is not hindered by shapes that are noisy

and ill-defined as it can adapt to interruptions in the shape¡¦s contour using a pre-set

tolerance and is able to scan multiple neighbors of a given point. The algorithm has a low

complexity and no restrictions on the type or size of the traced shape. The extracted

ordered set of boundary points represents the contour of a given shape and is important

for curvature-based shape descriptors.

Categories and Subject Descriptors

I.4.6 [Image Processing and Computer Vision]: Segmentation ¡V Edge and feature detection, Pixel classification

General Terms

Algorithms.

Adaptive Shape Contour Tracing Algorithm

by Emad Attalla, Ph.D.

ABSTRACT

In this paper we are going to present a new shape contour tracing algorithm called

¡§Adaptive Contour Tracing Algorithm¡¨. The algorithm can trace open and closed

discontinuous digital shapes and return an ordered set of boundary points that represent

the contour of the shape. Unlike other algorithms that return boundary points that are

part of the traced shape, our algorithm returns background points that are adjacent to the

shape¡¦s contour. Furthermore, the algorithm is not hindered by shapes that are noisy

and ill-defined as it can adapt to interruptions in the shape¡¦s contour using a pre-set

tolerance and is able to scan multiple neighbors of a given point. The algorithm has a low

complexity and no restrictions on the type or size of the traced shape. The extracted

ordered set of boundary points represents the contour of a given shape and is important

for curvature-based shape descriptors.

Categories and Subject Descriptors

I.4.6 [Image Processing and Computer Vision]: Segmentation ¡V Edge and feature detection, Pixel classification

General Terms

Algorithms.

Keywords

Image Processing; Contour Tracing; Shape Boundary Extraction.

1. INTRODUCTION

Contour tracing is an important process in boundary-based shape matching. All shapes are

represented by a pattern of pixels and the contour pixels are usually a small subset of

that pattern. Curvature-based shape matching methods rely on the contour pixels to

describe the irregularities in shapes and a reliable contour-tracing algorithm is needed

to extract the boundary of shapes. If the shape has holes then another hole search

algorithm need to be applied to extract the hole pattern and such an algorithm is not part

of this article.

We developed a sequential contour-tracing algorithm denoted the ¡§Adaptive Contour

Tracing Algorithm¡¨. The algorithm computes the surrounding contour of any shape and

adapts to all types of closed curve representations whether they are filled or partially

filled digital shapes. Any pixel, 1-pixel wide lines, and full shapes could be traced and

represented by closed curves. The algorithm also accounts for discontinuities in the shape

contour and can reach nearby pixels.

The contour trace starts from the top left point or pixel closest to the shape and

proceeds clockwise following the surrounding of the contour of the shape rather than the

contour itself. The path around the contour is traced in a look-forward sweep pattern to

Image Processing; Contour Tracing; Shape Boundary Extraction.

1. INTRODUCTION

Contour tracing is an important process in boundary-based shape matching. All shapes are

represented by a pattern of pixels and the contour pixels are usually a small subset of

that pattern. Curvature-based shape matching methods rely on the contour pixels to

describe the irregularities in shapes and a reliable contour-tracing algorithm is needed

to extract the boundary of shapes. If the shape has holes then another hole search

algorithm need to be applied to extract the hole pattern and such an algorithm is not part

of this article.

We developed a sequential contour-tracing algorithm denoted the ¡§Adaptive Contour

Tracing Algorithm¡¨. The algorithm computes the surrounding contour of any shape and

adapts to all types of closed curve representations whether they are filled or partially

filled digital shapes. Any pixel, 1-pixel wide lines, and full shapes could be traced and

represented by closed curves. The algorithm also accounts for discontinuities in the shape

contour and can reach nearby pixels.

The contour trace starts from the top left point or pixel closest to the shape and

proceeds clockwise following the surrounding of the contour of the shape rather than the

contour itself. The path around the contour is traced in a look-forward sweep pattern to

find the next surrounding point that is closest to the contour. The path is then closed

when the start point is found.

2. ADAPTIVE CONTOUR TRACING

Input Data: A square tessellation, Q, of Q-width x Q-height containing cells that belong

to the shape and cells that belong to the background of the shape. A Tessellation is a

group of cells (pixels in images) that has the same shape and size.

Definitions:

1- Each cell is represented by an x-y coordinate point p = (x, y)

2- The terms ¡§cell¡¨, ¡§point¡¨ and ¡§pixel¡¨ all refer to the same definition of a cell.

3- Define 8-neighbor(cell, direction) as Moore¡¦s neighborhood which is a common concept

that defines the 8-neighboring cells of any cell as shown in

4- Define i-order neighbor of any cell i-order(cell, direction) as the set of (i*8) cells,

where i > 0, that are i-1 cells away from that cell. Moore¡¦s Neighbor corresponds to

our 1-order notation. The 2-order neighbor contains 16 cells and 3-order neighbor contains

24 cells as shown in Figure 2.

5- Define 4 orientations to read cells around any cell p: (LR-Direction, RL-Direction,

DU-Direction and UD-Direction) as shown in Figure 3.

when the start point is found.

2. ADAPTIVE CONTOUR TRACING

Input Data: A square tessellation, Q, of Q-width x Q-height containing cells that belong

to the shape and cells that belong to the background of the shape. A Tessellation is a

group of cells (pixels in images) that has the same shape and size.

Definitions:

1- Each cell is represented by an x-y coordinate point p = (x, y)

2- The terms ¡§cell¡¨, ¡§point¡¨ and ¡§pixel¡¨ all refer to the same definition of a cell.

3- Define 8-neighbor(cell, direction) as Moore¡¦s neighborhood which is a common concept

that defines the 8-neighboring cells of any cell as shown in

4- Define i-order neighbor of any cell i-order(cell, direction) as the set of (i*8) cells,

where i > 0, that are i-1 cells away from that cell. Moore¡¦s Neighbor corresponds to

our 1-order notation. The 2-order neighbor contains 16 cells and 3-order neighbor contains

24 cells as shown in Figure 2.

5- Define 4 orientations to read cells around any cell p: (LR-Direction, RL-Direction,

DU-Direction and UD-Direction) as shown in Figure 3.

6- The top-left cell of Q has (x, y)= (1,1) and the x-axis increases from left to right

and the y-axis increases from top to bottom.

7- Let s denotes any shape cell, p denotes any background cell, c and d denote any cell, C

and D are the set of cells of i-order around cells c and d respectively.

8- When disregarding 1-pixel shapes, Define a stranded point s as a cell where all 8-neighbor or 1-order cells = p.

9- Define neighborhood tolerance factor T as the maximum i-order where the trace algorithm

should keep looking for a contour boundary.

Output Data: An ordered sequence P (p1, p2, ¡K, pn) of n contour boundary points.

The Algorithm:

- Set P to be empty.

- From top to bottom and left to right scan the cells of Q until the leftmost shape pixel

s1 with (x1, y1) coordinate is found as shown in figure 4.

- Insert p1=(x1-1,y1), left background cell next to s1, in P.

- Set startpoint = p1, previouspoint = p1, currentdirection = DU, i-order = 1

- Set p2 = getNextPoint (1, p1 , DU) and Insert p2 in P.

- Set n = 3

- While true do

(Comment: Scan all i-orders up to maximum tolerance T)

For i = 1 to T

Set pn = getNext (i, pn-1 , pn-2)

If pn = p1 then exit while loop

If pn is not empty Then

Insert pn in P

Set n = n 1

Exit For Loop

End If

Next i

End While

Function getNext

Input Parameters: i-order i, currentpoint, previouspoint

Output Parameters: nextpoint

Begin

(Comment: the direction of movement is switched between the four directions depending on

the increase and decrease in the x and y coordinate values of the previous and current

points)

If currentpoint.x > previouspoint.x Then

nextpoint = getNextPoint (i, currentpoint, LR-direction)

Else If currentpoint.x previouspoint.y Then

For i = 1 to T

Set pn = getNext (i, pn-1 , pn-2)

If pn = p1 then exit while loop

If pn is not empty Then

Insert pn in P

Set n = n 1

Exit For Loop

End If

Next i

End While

Function getNext

Input Parameters: i-order i, currentpoint, previouspoint

Output Parameters: nextpoint

Begin

(Comment: the direction of movement is switched between the four directions depending on

the increase and decrease in the x and y coordinate values of the previous and current

points)

If currentpoint.x > previouspoint.x Then

nextpoint = getNextPoint (i, currentpoint, LR-direction)

Else If currentpoint.x previouspoint.y Then