2
\$\begingroup\$

I have an algorithm that takes in an array of interections found between lines in an image. It then has to look for any instances where there are a group of intersections together, remove the middle ones and give me back all the edges of it.

I have it working as well as I need it too except for the performance... it takes waaaay to long. on my machine about 30-40 seconds for about 18000 intersections. I was wondering if anyone had any performance tips that could help me.

This is my code:

private Pixel[] RemoveBlobsOfIntersections(Pixel[] Intersections)
{
    Intersections = Intersections.OrderBy(i => i.X).ThenBy(i => i.Y).ToArray();

    List<Pixel> plAlreadyIteratedOver = new List<Pixel>();
    List<Pixel> plNoBlobsOfIntersections = new List<Pixel>();
    foreach (Pixel pIntersection in Intersections)
    {
        if (!plAlreadyIteratedOver.Any(p => p.X == pIntersection.X && p.Y == pIntersection.Y))
        {
            Pixel[] paBlob = FindBlob(pIntersection, Intersections);
            plAlreadyIteratedOver.AddRange(paBlob);

            plNoBlobsOfIntersections.AddRange(GetBlobEdges(paBlob));
        }
    }

    return plNoBlobsOfIntersections.ToArray();
}

private Pixel[] FindBlob(Pixel StartingPixel, Pixel[] PixelArray)
{
    List<Pixel> plBlob = new List<Pixel>() { StartingPixel };

    List<Pixel> plPixelsToCheck = new List<Pixel>(plBlob);
    while (plPixelsToCheck.Count > 0)
    {
        List<Pixel> plTempList = new List<Pixel>();
        foreach (Pixel pixel in plPixelsToCheck)
        {
            Pixel[] paSurroundingPixels = GetSurroundingPixels(pixel, PixelArray);
            foreach (Pixel p in paSurroundingPixels)
            {
                if (p != null && !plBlob.Any(bp => bp.X == p.X && bp.Y == p.Y) && !plTempList.Any(bp => bp.X == p.X && bp.Y == p.Y) && !plPixelsToCheck.Any(bp => bp.X == p.X && bp.Y == p.Y))
                    plTempList.Add(p);
            }

            plBlob.Add(pixel);
        }

        plPixelsToCheck.Clear();
        plPixelsToCheck.AddRange(plTempList);
    }

    return plBlob.ToArray();
}

private Pixel[] GetSurroundingPixels(Pixel StartingPixel, Pixel[] PixelArray)
{
    Pixel[] paSurroudingPixels = new Pixel[8];

    paSurroudingPixels[0] = PixelArray.FirstOrDefault(p => p.X == (StartingPixel.X - 1) && p.Y == (StartingPixel.Y - 1));
    paSurroudingPixels[1] = PixelArray.FirstOrDefault(p => p.X == StartingPixel.X && p.Y == (StartingPixel.Y - 1));
    paSurroudingPixels[2] = PixelArray.FirstOrDefault(p => p.X == (StartingPixel.X + 1) && p.Y == (StartingPixel.Y - 1));

    paSurroudingPixels[3] = PixelArray.FirstOrDefault(p => p.X == (StartingPixel.X - 1) && p.Y == StartingPixel.Y);
    paSurroudingPixels[4] = PixelArray.FirstOrDefault(p => p.X == (StartingPixel.X + 1) && p.Y == StartingPixel.Y);

    paSurroudingPixels[5] = PixelArray.FirstOrDefault(p => p.X == (StartingPixel.X - 1) && p.Y == (StartingPixel.Y + 1));
    paSurroudingPixels[6] = PixelArray.FirstOrDefault(p => p.X == StartingPixel.X && p.Y == (StartingPixel.Y + 1));
    paSurroudingPixels[7] = PixelArray.FirstOrDefault(p => p.X == (StartingPixel.X + 1) && p.Y == (StartingPixel.Y + 1));

    return paSurroudingPixels;
}

private Pixel[] GetBlobEdges(Pixel[] PixelArray)
{
    List<Pixel> plBlobEdges = new List<Pixel>();

    IGrouping<int, Pixel>[] xGroupedPixels = PixelArray.GroupBy(p => p.X).ToArray();
    foreach (IGrouping<int, Pixel> xGroup in xGroupedPixels)
    {
        Pixel[] paOrderedXGroup = xGroup.OrderBy(b => b.X).ToArray();

        if (!plBlobEdges.Any(p => p.X == paOrderedXGroup[0].X && p.Y == paOrderedXGroup[0].Y))
            plBlobEdges.Add(paOrderedXGroup[0]);

        if (!plBlobEdges.Any(p => p.X == paOrderedXGroup[paOrderedXGroup.Length - 1].X && p.Y == paOrderedXGroup[paOrderedXGroup.Length - 1].Y))
            plBlobEdges.Add(paOrderedXGroup[paOrderedXGroup.Length - 1]);
    }

    IGrouping<int, Pixel>[] yGroupedPixels = PixelArray.GroupBy(p => p.Y).ToArray();
    foreach (IGrouping<int, Pixel> yGroup in yGroupedPixels)
    {
        Pixel[] paOrderedYGroup = yGroup.OrderBy(b => b.X).ToArray();

        if (!plBlobEdges.Any(p => p.X == paOrderedYGroup[0].X && p.Y == paOrderedYGroup[0].Y))
            plBlobEdges.Add(paOrderedYGroup[0]);

        if (!plBlobEdges.Any(p => p.X == paOrderedYGroup[paOrderedYGroup.Length - 1].X && p.Y == paOrderedYGroup[paOrderedYGroup.Length - 1].Y))
            plBlobEdges.Add(paOrderedYGroup[paOrderedYGroup.Length - 1]);
    }

    return plBlobEdges.ToArray();
}

And the Pixel class:

public class Pixel
{
    public int X { get { return _nX; } }

    public int Y { get { return _nY; } }

    public bool IsBlack { get { return _bIsBlack; } }

    public float Confidence { get { return _fConfidence; } }

    private int _nX;
    private int _nY;
    private bool _bIsBlack;
    private float _fConfidence;

    public Pixel(int x, int y, bool isBlack, float confidence)
    {
        _nX = x;
        _nY = y;
        _bIsBlack = isBlack;
        _fConfidence = confidence < 0 ? 0 : confidence;
    }
}

EDIT:

A blob is a group of pixels in an image - the pixels I am searching on are the intersections found in the image between horizontal and vertical lines. However as you can imagine if a few horizontal and vertical lines meet in the same area a group (blob) of intersections are joined together. I am trying to remove these blobs by finding the edges.

An image of the stages of the process1]

An image of the stages of the process. From top to bottom. 1: initial 2: Found lines (Green horizontal, Blue vertical) 3: With found intersections(Orange), With edges of blobs/groups(Purple).

As you can see I initially find all the lines in the image, followed by finding the intersections within it. On the one on the right however 9 intersections are found in a group and so I am trying to remove unnecessary ones by going to an outline of them (Note in the actual image the groups are much larger e.g. the largest of which is about 70 x 50 pixels is size)

\$\endgroup\$

migrated from programmers.stackexchange.com Oct 29 '15 at 10:47

This question came from our site for professionals, academics, and students working within the systems development life cycle.

  • \$\begingroup\$ The reason that this algorithm takes so long is because of how many times you traverse the array of pixels. Just a spot check on the number of operations has me believe you are around O(16n^6) number of operations worst case performance. \$\endgroup\$ – maple_shaft Oct 29 '15 at 11:05
  • \$\begingroup\$ @maple_shaft I know it does it a lot but I can't see how to lessen the amount of times I do it \$\endgroup\$ – TheLethalCoder Oct 29 '15 at 11:06
  • \$\begingroup\$ I see, so a blob is a bunch of lines grouped together to form pretty much a rectangle. Would an alternative technique work where your grid of pixels, possibly a distinct set, had pixels that have a reference to Lines that already contain them? When a Line is created you have a process that for each of its pixels, adds references to itself for each of the pixels. \$\endgroup\$ – maple_shaft Oct 29 '15 at 12:01
  • \$\begingroup\$ @maple_shaft I don't understand what you're getting at and it won't always be a rectangle this is just there for an easy example \$\endgroup\$ – TheLethalCoder Oct 29 '15 at 12:05
1
\$\begingroup\$

So a blob is a bunch of lines grouped together to form pretty much a rectangle, and you want the edges of the rectangle that forms that intersection.

Would an alternative technique work where your grid of pixels, possibly a distinct set, had pixels that have a reference to Lines that already contain them? When a Line is created you have a process that for each of its pixels, adds references to itself for each of the pixels. Now the lookup of line intersections becomes at worst O(n) operations.

Start with your vertical line at the 0th pixel width wise and iterate down each pixel until you find one that has more than line in its intersection reference.

That line belongs to a horizontal blob (rectangle). The edges can be determined mathematically without further iteration.

Top and bottom edges are W sub V pixels long starting at your top left corner where you stopped iterating, where W sub V is the width of the vertical blob.

Left and Right edges are W sub H pixels long starting at your top left corner where you stopped iterating, where W sub H is the height of the horizontal blob.

Computing your edges is trivial after you find the top left corner of the intersection, but it involves storing additional data about pixels in memory. I hope this makes sense.

\$\endgroup\$
  • \$\begingroup\$ It does make sense and I've realised I must have left out some information, The lines can be in the form of a grid and so this wouldn't work \$\endgroup\$ – TheLethalCoder Oct 29 '15 at 12:13
  • \$\begingroup\$ Oh no wait after a certain number of intersections not joined I can reset the blob and start again, thanks :), i'll try and implement this and if it works I'll mark this as the answer \$\endgroup\$ – TheLethalCoder Oct 29 '15 at 12:14
  • \$\begingroup\$ I may not completely understand every scenario here, but the greater point is that you don't want to be wasteful in computing answers to smaller problems. Solve your subproblems and memoize the answers. Refer to solutions to your subproblems where needed. If you were taking an Object Oriented approach you would be more explicit about object creation, and setting certain derived properties and references of your objects on the construction of them. Factory pattern might be good for instance in creating your pixels and your lines. \$\endgroup\$ – maple_shaft Oct 29 '15 at 12:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.