Creating and combining rectangles based on a result of an edge detection

Question

Context

In an imageprocessing project of mine, I needed to do some edge detection and implemented the Theo Pavlidis algorithm which works quite well. A problem had been to get the next "good" position. Assuming an image like this (where the 1 represent the needed pixel value)

011110  
111111  
111111  
011110  

this would result in the following edges found

011110  
100001      1111  
100001      1111    
011110  

because the algorithm is searching for values which hadn't been visited and have the desired value 1 in it.

So I was in the need to find the enclosed area to exclude it from the algorithms position search area.

The algorithm returns a IEnumerable<Position> for each found value on the edge, where the Position struct looks like so

public struct Position
{
    public int X;
    public int Y;

    public Position(int x, int y)
    {
        X = x;
        Y = y;
    }

    private static readonly Position empty = new Position(-1, -1);
    public static Position Empty
    {
        get
        {
            return empty;
        }
    }

    public static bool  operator ==(Position p1, Position p2){

        return (p1.X == p2.X) && (p1.Y == p2.Y);
    }

    public static bool operator !=(Position p1, Position p2)
    {
        return !(p1.X == p2.X) && (p1.Y == p2.Y);
    }

}  

So, nothing fancy at all.

My idea was to first create an IEnumerable<Int32Rect> out of the IEnumerable<Position> using the Min of Position.X of all positions with the same value of Position.Y to create the rectangles line by line form top to bottom.

The meat

The creation of the IEnumerable<Int32Rect> is done like so

private IEnumerable<Int32Rect> ToRectangles(IEnumerable<Position> positions)
{
    foreach (Position position in positions.Distinct(new PositionComparerY()).OrderBy(p => p.Y))
    {
        IEnumerable<Position> positionsWithSameY = positions.Where(p => p.Y == position.Y);
        int minX = positionsWithSameY.Min(x => x.X);
        int maxX = positionsWithSameY.Max(x => x.X);

        yield return new Int32Rect(minX, position.Y, maxX - minX + 1, 1);
    }
}  

with the help of the PositionComparerY class which looks like so

private class PositionComparerY : IEqualityComparer<Position>
{
    public bool Equals(Position x, Position y)
    {
        return x.Y == y.Y;
    }

    public int GetHashCode(Position position)
    {
        return position.Y.GetHashCode();
    }
}  

The next step I needed to take, was to combine the resulting Int32Rect's if they have the same width and start at the same x position.

I implemented this by grouping the rectangles based on the Width property of the Int32Rect like so

private IEnumerable<Int32Rect> CombineRectangles(IEnumerable<Int32Rect> rectangles)
{
    var groupedRectangles = rectangles.OrderBy(r => r.Y)
                        .GroupBy(r => r.Width, rect => rect, (key, Rectangles) => new { Rectangles });

    Int32Rect emptyRect = new Int32Rect();

    foreach (var groupedRectangle in groupedRectangles)
    {

        Int32Rect lastRectangle = emptyRect;
        bool isFirstRectangleInRectangles = true;
        int y = 0;
        int rectangleHeight = 1;
        foreach (Int32Rect rectangle in groupedRectangle.Rectangles)
        {
            if (isFirstRectangleInRectangles)
            {
                lastRectangle = rectangle;
                y = rectangle.Y + 1;
                isFirstRectangleInRectangles = false;
                continue;
            }

            if (rectangle.Y != y)
            {
                yield return new Int32Rect(lastRectangle.X, lastRectangle.Y, lastRectangle.Width, rectangleHeight);
                lastRectangle = rectangle;
                rectangleHeight = 1;
            }
            else
            {
                rectangleHeight += 1;
            }
            y = rectangle.Y + 1;

        }

        if (lastRectangle != emptyRect) { yield return new Int32Rect(lastRectangle.X, lastRectangle.Y, lastRectangle.Width, rectangleHeight); ; }

    }
}  

The simple tests

The needed edge positions 011110  
                          100001
                          100001
                          011110  

will be produced like so

private IEnumerable<Position> GetTestPositions()
{

    List<Position> testPositions = new List<Position>();

    testPositions.Add(new Position(2, 3));
    testPositions.Add(new Position(3, 3));
    testPositions.Add(new Position(1, 3));
    testPositions.Add(new Position(4, 3));

    testPositions.Add(new Position(2, 0));
    testPositions.Add(new Position(3, 0));
    testPositions.Add(new Position(1, 0));
    testPositions.Add(new Position(4, 0));

    testPositions.Add(new Position(0, 1));
    testPositions.Add(new Position(1, 1));
    testPositions.Add(new Position(4, 1));
    testPositions.Add(new Position(5, 1));

    testPositions.Add(new Position(0, 2));
    testPositions.Add(new Position(1, 2));
    testPositions.Add(new Position(4, 2));
    testPositions.Add(new Position(5, 2));
    return testPositions;
}  

and a test for the ToRectangles() method

[TestMethod]
public void TestToRectangles_Success()
{

    IEnumerable<Position> testPositions = GetTestPositions();

    List<Int32Rect> rectangles = ToRectangles(testPositions).ToList();

    int expectedRectangleCount = 4;
    string message = "Number of rectangles does not match. Expected {0} Found {1}";

    Assert.IsTrue(rectangles.Count == expectedRectangleCount, message, expectedRectangleCount, rectangles.Count);

    int expectedWidth = 4;
    message = "{0} rectangle width assert failed. Expected {1} found {2}";
    Assert.IsTrue(expectedWidth == rectangles[0].Width, message, "First", expectedWidth, rectangles[0].Width);
    Assert.IsTrue(expectedWidth == rectangles[3].Width, message, "Forth", expectedWidth, rectangles[1].Width);

    expectedWidth = 6;
    Assert.IsTrue(expectedWidth == rectangles[1].Width, message, "Second", expectedWidth, rectangles[2].Width);
    Assert.IsTrue(expectedWidth == rectangles[2].Width, message, "Third", expectedWidth, rectangles[3].Width);

}

and for the CombineRectangles() method

[TestMethod]
public void TestCombineRectangles_Success()
{
    IEnumerable<Int32Rect> rectangles = ToRectangles(GetTestPositions());
    List<Int32Rect> combinedRectangles = CombineRectangles(rectangles).ToList();

    string message = "Number of rectangles does not match. Expected {0} found {1}";
    int expectedRectanglesCount = 3;
    Assert.IsTrue(expectedRectanglesCount == combinedRectangles.Count, message, expectedRectanglesCount, combinedRectangles.Count);

    // Because the rectangles will be grouped based on the width
    // we expect the first and second rectangle to have height 1
    message = "{0} rectangle height assert failed. Expected {1} found {2}";
    int expectedHeight = 1;
    Assert.IsTrue(expectedHeight == combinedRectangles[0].Height, message, "First", expectedHeight, combinedRectangles[0].Height);
    Assert.IsTrue(expectedHeight == combinedRectangles[1].Height, message, "Second", expectedHeight, combinedRectangles[1].Height);

    expectedHeight = 2;
    Assert.AreEqual(expectedHeight, combinedRectangles[2].Height, message, "Third", expectedHeight, combinedRectangles[2].Height);

    message = "{0} rectangle assert failed. Expected {1} found {2}";
    Int32Rect expectedRectangle = new Int32Rect(1, 0, 4, 1);
    Assert.IsTrue(expectedRectangle == combinedRectangles[0], message, "First", expectedRectangle.ToString(), combinedRectangles[0].ToString());

    expectedRectangle = new Int32Rect(1, 3, 4, 1);
    Assert.IsTrue(expectedRectangle == combinedRectangles[1], message, "Second", expectedRectangle.ToString(), combinedRectangles[1].ToString());

    expectedRectangle = new Int32Rect(0, 1, 6, 2);
    Assert.IsTrue(expectedRectangle == combinedRectangles[2], message, "Third", expectedRectangle.ToString(), combinedRectangles[2].ToString());

}

Conclusion

Because this is used in imageprocessing speed is a major requirement, so my primary concern is performance wise (but in a readable and maintainable way), but feel free to point out any flaw you find.

Clarifications based on comments

did you run a performance analysis on your code?

No, because I didn't implement this. These methods live at the moment only in a unit test to see if I am doing it correctly. The performance concerns are just of a general type to know if I use some obvious stupid approach which could be done much faster by some different algorithm.

is there a reason why you don't use the already built-in Point struct (other than it's less meaningful name in your case)?

Not really, the only reason is the name and that I have full control over it.

Answer 1

Life could be so easy if everything would work like expected. The shown code is good and work successful for the given array, but fails for e.g

000011110  without the `0`     1111  
001001000                    1  1 
011110000                   1111
011110000                   1111

So we still need to find the enclosed area to exclude it from the algorithm.

For this problem a IMHO good approach is to use the PathGeometry class which has the FillContains() method to examine if a given point is inside the "path".

So I have created one extension methods like so

public static bool Contains(this IEnumerable<PathGeometry> geometries, Position position)
{
    Point point = new Point(position.X, position.Y);
    return geometries.Any(g=> g.FillContains(point));
}

to check if a given Position is contained in an IEnumerable<PathGeometry>.

The ToPathGeometry() extension method allows me to create a PathGeometry object by providing a starting position and the found positions like so

public static PathGeometry ToPathGeometry(this Position startPosition, IEnumerable<Position> foundPositions)
{

    IList<LineSegment> segements = new List<LineSegment>();
    foreach (Position p in foundPositions.Where(p => p != startPosition))
    {
        segements.Add(new LineSegment(new Point(p.X, p.Y), true));
    }

    PathFigure figure = new PathFigure(new Point(startPosition.X, startPosition.Y), segements, true);
    IList<PathFigure> figures = new List<PathFigure>();
    figures.Add(figure);

    return new PathGeometry(figures);

}

Which leads me also to the conclusion that it would be better to skip the Position class and instead use the Point class.

Update

Profiling my application resulted that the shown extension method

public static bool Contains(this IEnumerable<PathGeometry> geometries, Position position)
{
    Point point = new Point(position.X, position.Y);
    return geometries.Any(g=> g.FillContains(point));
}  

is a bottleneck. So I changed it to

public static bool Contains(this IEnumerable<PathGeometry> geometries, Position position)
{
    Point point = new Point(position.X, position.Y);
    return geometries.Any(g=> g.Bounds.Contains(point));
}   

which reduced the execution time to 1/15 .