Theo Pavlidis' Algorithm

Idea

This algorithm is one of the more recent contour tracing algorithms and was proposed by Theo Pavlidis. He published it in his book Algorithms for Graphics and Image Processing in 1982, chapter 7 (section 5). It is not as simple as the Square Tracing algorithm or Moore-Neighbor tracing, yet it is not complicated (a property shared by most contour tracing algorithms).
We will explain this algorithm using an approach different from the one presented in the book. This approach is easier to comprehend and will give insight into the general idea behind the algorithm.

Without loss of generality, we have chosen to trace the contour in a clockwise direction in order to be consistent with all the other contour tracing algorithms discussed on this web site. On the other hand, Pavlidis chooses to do so in a counterclockwise direction. This shouldn't make any difference towards the performance of the algorithm. The only effect this will have is on the relative direction of movements you'll be making while tracing the contour.

Now let's proceed with the idea...

Given a digital pattern i.e. a group of black pixels, on a background of white pixels i.e. a grid; locate a black pixel and declare it as your "start" pixel. Locating a "start" pixel can be done in a number of ways; one of which is done by starting at the bottom left corner of the grid, scanning each column of pixels from the bottom going upwards -starting from the leftmost column and proceeding to the right- until a black pixel is encountered. Declare that pixel as the "start" pixel.
We will not necessarily follow the above method in locating a start pixel. Instead we will choose a start pixel satisfying the following restriction imposed on the choice of a start pixel for Pavlidis' algorithm:

Important restriction regarding the direction in which you enter the start pixel
You actually can choose ANY black boundary pixel to be your start pixel as long as when you're initially standing on it, your left adjacent pixel is NOT black. In other words, you should make sure that you enter the start pixel in a direction which ensures that the left adjacent pixel to it will be white ("left" here is taken with respect to the direction in which you enter the start pixel ).

Now, imagine that you are a bug (ladybird) standing on the start pixel as in Figure 1 below.
Throughout the algorithm, the pixels which interest you at any time are the 3 pixels in front of you i.e. P1, P2 and P3 shown in Figure 1.
(We will define P2 to be the pixel right in front of you , P1 is the pixel adjacent to P2 from the left and P3 is the right adjacent pixel to P2).

Like in the Square Tracing algorithm, the most important thing in Pavlidis' algorithm is your "sense of direction". The left and right turns you make are with respect to your current positioning, which depends on the way you entered the pixel you are standing on. Therefore, it's important to keep track of your current orientation in order to make the right moves.
But no matter what position you are standing in, pixels P1, P2 and P3 will be defined as above.

With this information, we are ready to explain the algorithm...

Every time you are standing on the current boundary pixel (which is the start pixel at first) do the following:

First, check pixel P1. If  P1 is black, then declare P1 to be your current boundary pixel and move one step forward followed by one step to your current left to land on P1.
(the order in which you make your moves is very important)
Figure 2 below demonstrates this case. The path you should follow in order to land on P1 is drawn in blue.






Only if P1 is white proceed to check P2...

If  P2 is black, then declare P2 to be your current boundary pixel and move one step forward to land on P2.
Figure 3 below demonstrates this case. The path you should follow in order to land in P2 is drawn in blue.



Only if both P1 and P2 are white proceed to check P3...

If P3 is black, then declare P3 to be your current boundary pixel and move one step to your right followed by one step to your current left as demonstrated in Figure 4 below.


That's it!!
3 simple rules for 3 simple cases. As you've seen, it's important to keep track of your direction as you turn since all moves are with respect to your current orientation.
But haven't we forgotten something?!
What if all 3 pixels in front of you are white?
Then, you rotate (while standing on the current boundary pixel) 90 degrees clockwise to face a new set of 3 pixels in front of you. Afterwards you do the same check on these new pixels as you've done before.
You may still ask: what if all of these 3 pixels are white?!
Well, then rotate again through 90 degrees clockwise while standing on the same pixel.
You can rotate 3 times (each through 90 degrees clockwise) before checking out the whole Moore neighborhood of the pixel. If you rotate 3 times without finding any black pixels, this means that you are standing on an isolated pixel i.e. not connected to any other black pixel. That's why the algorithm will allow you to rotate 3 times before it terminates.

Another thing: When does the algorithm terminate?
The algorithm terminates in 2 cases:
a) as mentioned above, the algorithm will allow you to rotate 3 times (each through 90 degrees clockwise) after which it will terminate and declare the pixel an isolated one, OR
b) when the current boundary pixel is your start pixel, the algorithm terminates "declaring" that it has traced the contour of the pattern.
 


Algorithm

The following is a formal description of Pavlidis' algorithm:

Input: A square tessellation, T, containing a connected component P of black cells.

Output: A sequence B (b1, b2 ,..., bk) of boundary pixels i.e. the contour.

Definitions:


Important Note: At all times, imagine that you are a bug moving from pixel to pixel following the given directions. "forward", "left" and "right" are with respect to your current positioning on the pixel.
 

Begin

End
 
 
 
 

Demonstration

The following is an animated demonstration of how Pavlidis' algorithm proceeds to trace the contour of a given pattern. Remember that you are a bug (ladybird) walking over the pixels; notice how your orientation changes as you turn left or right. We have included all possible cases of the algorithm in order to explain it as thoroughly as possible.
 
 





Analysis

If you are thinking that Pavlidis' algorithm is the perfect one for extracting the contour of patterns, think again...
It's true that this algorithm is a bit more complex than say, Moore-Neighbor tracing which has no special cases to take care of, yet it fails to extract the contour of a large family of patterns having a certain kind of connectivity .

The algorithm works very well on 4-connected patterns. its problem lies in tracing some 8-connected patterns that are not 4-connected.
The following is an animated demonstration of how Pavlidis' algorithm fails to extract the contour of an 8-connected pattern (that is not 4-connected) by missing a large portion of the boundary.

 
 



There are 2 simple ways of modifying the algorithm in order to improve its performance dramatically.

a) Change the stopping criterion
Instead of terminating the algorithm when it visits the start pixel for a second time, make the algorithm terminate after visiting the start pixel a third or even a fourth time.
This will improve the general performance of the algorithm.

OR

b) Go to the source of the problem; namely, the choice of the start pixel
There is an important restriction concerning the direction in which you enter the start pixel. Basically, you have to enter the start pixel such that when you're standing on it, the pixel adjacent to you from the left is white. The reason for imposing such a restriction is:
since you always consider the 3 pixels in front of you in a certain order, you'll tend to miss a boundary pixel lying directly to the left of the start pixel in certain patterns.

Not only the left adjacent pixel of the start pixel is at risk of being missed, but also the pixel directly below that pixel faces such a threat (as demonstrated in the counterexample above). In addition, the pixel corresponding to pixel R in Figure 5 below will be missed in some patterns. Therefore, we suggest that a start pixel should be entered in a direction such that the pixels corresponding to pixels L, W and R shown in Figure 5 below, are white.

In this way, patterns like the one in the above demonstration will be correctly traced and the performance of Pavlidis' algorithm will greatly improve.
On the other hand, finding a start pixel which satisfies the above restriction could be tough and in many cases such a pixel won't be found. In that case, the alternative method for improving Pavlidis' algorithm should be used, namely: terminating the algorithm after visiting the start pixel for a third time.
 
 

All comments and questions are welcomed...
abeer.ghuneim@mail.mcgill.ca