Theo Pavlidis' Algorithm in C#

BoundaryTracing.cs

using System;
using System.Collections.Generic;
using System.Drawing;
using System.Linq;

using BitSets; // Magic to make bitmaps quicker

namespace Imaging
{
    /// <summary>
    /// http://www.imageprocessingplace.com/downloads_V3/root_downloads/tutorials/contour_tracing_Abeer_George_Ghuneim/theo.html
    /// </summary>
    public class BoundaryTracing
    {

        /*
        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:

            Define p to be the current boundary pixel i.e. the pixel you are standing on.
            Define pixels P1, P2 and P3 as follows: (also see Figure 1 above)
            P2 is the pixel in front of you adjacent to the one you are currently standing on i.e. pixel p.
            P1 is the left adjacent pixel to P2.
            P3 is the right adjacent pixel to P2.
            Define a "step" in a given direction as moving a distance of one pixel in that direction.


        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

            Set B to be empty.
            From bottom to top and left to right scan the cells of T until a black start pixel, s, of P is found (see Important restriction concerning direction you enter start pixel above)
            Insert s in B.
            Set the current pixel, p, to be the starting pixel, s.
            Repeat the following


            If pixel P1 is black
                Insert P1 in B
                Update p=P1
                Move one step forward followed by one step to your current left
            else if P2 is black
                Insert P2 in B
                Update p=P2
                Move one step forward (see Figure 3 above)
            else if P3 is black
                Insert P3 in B
                Update p=P3
                Move one step to the right, update your position and move one step to your current left (see Figure 4 above)
            else if you have already rotated through 90 degrees clockwise 3 times while on the same pixel p
                terminate the program and declare p as an isolated pixel
            else
                rotate 90 degrees clockwise while standing on the current pixel p


            Until p=s  (End Repeat)

        End 
    */

        private enum TheoMovement
        {
            P1,
            P2,
            P3
        };

        private enum TheoDirection
        {
            North,
            East,
            South,
            West
        }

        private static readonly Dictionary<TheoDirection, TheoDirection> P1TheoDirection =
            new Dictionary<TheoDirection, TheoDirection>
            {
                {TheoDirection.North, TheoDirection.West},
                {TheoDirection.West, TheoDirection.South},
                {TheoDirection.South, TheoDirection.East},
                { TheoDirection.East, TheoDirection.North}
            };

        // <image src=".\images\theodem.GIF"/>
        private static readonly Func<PointEx, PointEx>[] TheoMove =
        {
            // Face North
            point => new PointEx(point.X - 1, point.Y - 1),  // Up Left
            point => new PointEx(point.X, point.Y - 1),      // Up
            point => new PointEx(point.X + 1, point.Y - 1),      // Up Right
            // Face East
            point => new PointEx(point.X + 1, point.Y - 1),  // Right Up
            point => new PointEx(point.X+1, point.Y),      // Right
            point => new PointEx(point.X + 1, point.Y + 1),      // Right Down
            // Face South
            point => new PointEx(point.X + 1, point.Y + 1),  // Down Right
            point => new PointEx(point.X, point.Y+1 ),      // Down
            point => new PointEx(point.X - 1, point.Y + 1),      // Down Left
            // Face West
            point => new PointEx(point.X - 1, point.Y + 1),  // Left Down
            point => new PointEx(point.X-1 , point.Y),      // Left
            point => new PointEx(point.X - 1, point.Y - 1)      // Left Up
        };

        /// <summary>
        /// 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. 
        /// </summary>

        /// <summary>
        /// 
        /// </summary>
        /// <param name="image">A square tessellation, T, containing a connected component P of 'on' cells</param>
        /// <returns></returns>
        public static PointEx[] Trace(AbsBitSet2D image)
        {
            Size size = image.Size;
            // Output: A sequence B (b1, b2 ,..., bk) of boundary pixels i.e. the contour.
            // Set B to be empty.

            HashSet<PointEx> found = new HashSet<PointEx>();

            // Note that there is a "Feature of this algorithm that shows that you must start with nothing on the left and facing "North" into the object
            PointEx s = null;
            // From bottom to top and left to right scan the cells of T until a black start pixel, s, of P is found (see Important restriction concerning direction you enter start pixel above)
            for (int y = size.Height - 1; y >= 0; y--)
            {
                BitSet xRow = image[y];
                int x = xRow.NextSet(-1);
                if (x != -1)
                {
                    s = new PointEx(x, y);
                    // Insert s in B.
                    found.Add(s);
                    break;
                }
            }

            if (s == null)
            {
                // Nothing found, break out early
                return found.ToArray();
            }
            // Define p to be the current boundary pixel i.e. the pixel you are standing on.
            PointEx p = s;

            // <image src=".\images\theopic1.GIF"/>
            // 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.
            // No matter what position you are standing in, pixels P1, P2 and P3 will be defined as above.
            // Define pixels P1, P2 and P3 as follows: (also see Figure 1 above)
            //PointEx p1 = TheoMove[(int)TheoMovement.P1](p);
            //PointEx p2 = TheoMove[(int)TheoMovement.P2](p);
            //PointEx p3 = TheoMove[(int)TheoMovement.P3](p);

            // Define a "step" in a given direction as moving a distance of one pixel in that direction.
            int directionOffset = 0;
            int stationaryRotations = 0;
            TheoDirection lastDirection = TheoDirection.North;
            do
            {
                // <image src=".\images\theopic2.GIF"/>
                PointEx p1 = TheoMove[(int)TheoMovement.P1 + directionOffset](p);
                if (image.Get(p1.X, p1.Y))
                {
                    // 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.
                    p = p1;
                    found.Add(p1);
                    stationaryRotations = 0;
                    lastDirection = P1TheoDirection[lastDirection];
                    directionOffset = (int)lastDirection * 3;
                }
                else
                {
                    PointEx p2 = TheoMove[(int)TheoMovement.P2+ directionOffset](p);
                    if (image.Get(p2.X, p2.Y))
                    {
                        found.Add(p2);
                        // <image src=".\images\theopic3.GIF"/>
                        p = p2;
                        stationaryRotations = 0;
                    }
                    else
                    {
                        PointEx p3 = TheoMove[(int)TheoMovement.P3+ directionOffset](p);
                        if (image.Get(p3.X, p3.Y))
                        {
                            found.Add(p3);
                            // <image src=".\images\theopic4.GIF"/>
                            p = p3;
                            stationaryRotations = 0;
                        }
                        // if you have already rotated through 90 degrees clockwise 3 times while on the same pixel p
                        else if (stationaryRotations >= 3)
                        {
                            // terminate the program and declare p as an isolated pixel;
                            break;
                        }
                        else
                        {
                            // rotate 90 degrees clockwise while standing on the current pixel p
                            lastDirection = (TheoDirection) (((int)lastDirection + 1) % 4);
                            stationaryRotations++;
                            directionOffset = (int)lastDirection * 3;
                        }

                    }
                }


            } while (p != s);

            return found.ToArray();
        }
    }
}

hey Smurf, I think there could be a bug in the algorithm.
If for whatever reason the first pixel of the image is in the bottom left corner, and the only coloured pixel is set to its right, it's going to get to the end of the while loop, p is going to be equal to s and it's going to exit, even tho it still has 3 more rotations to test.
An easy fix would be to change the exit clause by while (p != s || found.Count <= 1). That would force it to cover the rest of the directions, and in case there's a feature with just one pixel, it'd exit in the if (stationaryRotations >= 3) return; clause.

Regards ;)