CODEWITHSUNDEEP
c#algorithmgraphics
powlette
powlette

Reputation: 1800

Counting unique pixels in a drawn image of shapes

I'm working on a graphics application where the user can draw any number of Lines (with some thickness from point A to point B), Rectangles, or Ellipses on a canvas.

After they're done, I have a set of shape data indicating the location of each shape and line drawn and I need to determine how many unique pixels they've colored as part of a research project.

My naive algorithm is to implement bool shape.Contains(x,y) for each shape and call it for every drawn shape for every pixel in the image to determine if that pixel was drawn by a line, rectangle or ellipse.

Working the other way, I could create void shape.SetPixels(bool[,] canvas) and have each shape set to true, each pixel it contains. This is what I've actually implemented and with large data sets, it's painfully slow.

I have a feeling that there's a more direct way to go from the raw shape data to the output that I need without examining every pixel. So my question is, given the set of shape data, is there a O(n) function bool[,] IsColored(int x, int y) {} that can generate a matrix of true/falses for colored pixels more directly than either idea I've given?

Upvotes: 0

Views: 1097

Answers (3)

jwd
jwd

Reputation: 11134

The two methods you're talking about are generally your two main options. Either check each pixel as needed, or build some kind of data structure for fast lookup beforehand.

If you have a large canvas, but only a few shapes (thus, relatively few "on" pixels), then it may be best to just record every pixel that is hit by any shape, in a hash for example.

HashSet<KeyValuePair<int,int>> listOfPixelsHitByAnyShape = new HashSet()

foreach(Shape s in allShapes)
{
    s.Draw(listOfPixelsHitByAnyShape); // will update listOfPixelsHitByAnyShape
}

// Now we can easily query if a pixel is set
bool isSet = listOfPixelsHitByAnyShape.Contains(new KeyValuePair(10,99))

This should be fast for lookup, at the expense of memory, and time to build the HashSet.

But it won't be quite as fast as your SetPixels(bool[,] canvas) version, nor using as much memory (in the sparse case we're talking about).

Upvotes: 1

CodesInChaos
CodesInChaos

Reputation: 108830

Avoid the Bitmap.GetPixel method. It is very very slow. If possible your low level access to the bitmap data with LockBits or similar techniques.

In one of my projects I used:

public void LoadFromBitmap(Bitmap bmp)
    {
        if (bmp.Width != Width || bmp.Height != Height)
            throw new ArgumentException("Size missmatch");
        unsafe
        {
            BitmapData bmpData = null;
            try
            {
                bmpData = bmp.LockBits(new System.Drawing.Rectangle(0, 0, bmp.Width, bmp.Height), ImageLockMode.ReadOnly, PixelFormat.Format32bppArgb);

                for (int y = 0; y < bmpData.Height; y++)
                {
                    uint* p = (uint*)((byte*)bmpData.Scan0 + y * bmpData.Stride);
                    for (int x = 0; x < bmpData.Width; x++)
                    {
                        this[x, y] = RawColor.FromARGB(*p);
                        p++;
                    }
                }
            }
            finally
            {
                if (bmpData != null)
                    bmp.UnlockBits(bmpData);
            }
        }
    }

https://github.com/CodesInChaos/ChaosUtil/blob/master/Chaos.Image/Pixels.cs

Another optimization is implementing a pool for your pixel containing arrays. Frequently allocating objects on the large-object-heap stresses the gc very much in my experience.

Upvotes: 2

George Duckett
George Duckett

Reputation: 32438

If you aren't using a graphics library, please, please do!

If it's a graphics application presumably you're already drawing what the user inputs. Can't you just query that? You could always draw to 2 different targets, one for the pretty user version, and another for the query (each object a unique colour).

How do you want to deal with overlaps?

How large a dataset are we talking? The rendering should be 'free' as the bitmap could be built as the user is drawing in the application.

If what you've done is really slow you could consider using the GPU to draw and query (possibly using fancy shaders).

Upvotes: 0

Related Questions