Finding rectangles of solid color in an image.

[Troy Lundin]

I am trying to find a way to determine where rectangles of solid color are in an image. Below is a sample image.



I have searched Google but I assume I am not using the correct terms. I found a couple links that kind of accomplish what I am going for but not quite.

1. http://bobpowell.net/region_from_bitmap.aspx
I tried the example in that link. It works somewhat by giving me a region object that contains the specified color. But, the way it works makes it give too many small rectangles. For example, using the image above it gives 15 rectangles for the first red rectangle each with a size of (7, 1). I assume this is because it just reads the scan-line, though I am not sure.

2. http://www.xtremevbtalk.com/showthread.php?t=248539
This link is a flood-fill algorithm that will give me the fuller rectangles that I want, but since it's a flood-fill, it doesn't scan the entire image and seems to break if I try to scan the image myself.

In summation, I wish to create an algorithm that will find all complete rectangles of a specific color (i.e. all the red or blue rectangles from the above image). So, if I wanted to find all the red rectangles, I would get the following result:


(x, y, w, h)
0, 0, 7, 15
17, 10, 2, 2
22, 10, 2, 2
12, 12, 4, 9
17, 20, 14, 3
22, 23, 9, 4

The last two rectangles make up the bottom-right red rectangle. Let me know if I need to be clearer. I think I confused myself writing this.

[boops boops]

Hi Troy,
I don't think there is any option but to scan the image line by line (or column by column, but that won't make a logical difference). For example if you find more one pixel in together on a horizontal line, check if the next line contains red pixels in the same position. It's not a question of efficiency. You could work out the logic using the "slow" way of getting pixel colours (Bitmap.GetPixel) then speed it up by using a more efficient way of getting the colours (Bitmap.Lockbits or FastPix, see my sig).

There are two questions that would make it easier to design some code. 1. Is there a minimum width and/or height for a rectangle? For example, would an isolated pixel (1 x 1 pixel "rectangle") count? 2. Can the rectangles in theory overlap one another?

BB

[Troy Lundin]

Thank you for your reply, Boops.

I always tend to focus on functionality before focusing on speed. After a bit of thinking: I wonder if I could just get all the smaller rectangles produced by the function in the first link, then analyze them to see if they neighbor each other.

To answer your questions:

1. There are no size limitations to the rectangle. Though, using the image in the first post, there is a red rectangle with a size of 2, 2. I would rather it be a single rectangle than four rectangles each with a size of 1, 1. In essence, I want the least amount of rectangles that cover the area of the image that contains the specified color.

2. The rectangles will not overlap. In my first post I mentioned the bottom-right red portion would have to be two rectangles. So, each pixel will only ever be in one rectangle.

[boops boops]

I just reread your original post and it is perfectly clear after all. Sorry for the unnecessary questions. The easiest way will be to add each pixel of the required color to a region with Region.Union, as in Bob Powell's code. Then you can get the rectangles (actually RectangleFs) with Region.GetRegionScans. If you used that, it's hard to see how you could get 15 rectangles just for the first block.

I copied your image and just to be safe filled all the "red" areas with pure red (255, 0, 0) in Paint.Net. Then I Unioned each red pixel to a Region and converted the GetRegionScans to Rectangles (see code below). The resulting output was 11 rectangles for the whole image:

{X=0,Y=0,Width=7,Height=10}
{X=0,Y=10,Width=7,Height=2}
{X=17,Y=10,Width=2,Height=2}
{X=22,Y=10,Width=2,Height=2}
{X=0,Y=12,Width=7,Height=3}
{X=12,Y=12,Width=4,Height=3}
{X=12,Y=15,Width=4,Height=5}
{X=12,Y=20,Width=4,Height=1}
{X=17,Y=20,Width=14,Height=1}
{X=17,Y=21,Width=14,Height=2}
{X=22,Y=23,Width=9,Height=4}

That's clearly more than the 6 you asked for: the Region code is dividing some of the rectangles horizontally. It looks like it should be easy to identify which of those rectangles are the same horizontally and are touching vertically; or are the same vertically and touching horizontally. And then union those to get the final list of rectangles. But in practice it could take a bit of working out.

Here's my code for getting the region rectangles:

	Private Function GetRegionRects(bmp As Bitmap, clr As Color) As Rectangle()
		Dim rectangles As New List(Of Rectangle)
		Dim rgn As New Region(Rectangle.Empty)
		For y As Integer = 0 To bmp.Width - 1
			For x As Integer = 0 To bmp.Height - 1
				If bmp.GetPixel(x, y).ToArgb = clr.ToArgb Then
					rgn.Union(New Rectangle(x, y, 1, 1))
				End If
			Next
		Next
		For Each rf As RectangleF In rgn.GetRegionScans(New Drawing2D.Matrix)
			rectangles.Add(Rectangle.Round(rf))
		Next
		Return rectangles.ToArray
	End Function

[Troy Lundin]

Exactly! The extra rectangles are what happened when I used the example from the first link in the first post. The union-ing is what I was talking about in my previous post.

After a bit of thinking: I wonder if I could just get all the smaller rectangles produced by the function in the first link, then analyze them to see if they neighbor each other.

The code you provided in your previous post was very clean and I'll use it as a base. I'll work on some rectangle union code sometime today (chore day, yay!) and see if I can get something working.

Edit: I got it working for the most part. Here is the code.

    Friend Shared Sub GetRectangles(e as Entry)
        Dim finalRectList As New Dictionary(Of Int32, List(Of Rectangle))

        Dim data As BitmapData = e.Bitmap.LockBits(New Rectangle(0, 0, e.Bitmap.Width, e.Bitmap.Height), ImageLockMode.ReadOnly, PixelFormat.Format32bppArgb)

        For Each c In e.ColorTable
            Dim rectangles As New List(Of Rectangle)
            Dim rgn As New Region(Rectangle.Empty)

            ' Create a region comprised of all the pixels matching the specified color: c.
            For y As Integer = 0 To e.Bitmap.Width - 1
                For x As Integer = 0 To e.Bitmap.Height - 1
                    If Marshal.ReadInt32(data.Scan0, (data.Stride * y) + (4 * x)) = c Then
                        rgn.Union(New Rectangle(x, y, 1, 1))
                    End If
                Next
            Next
            For Each rf As RectangleF In rgn.GetRegionScans(New Drawing2D.Matrix)
                rectangles.Add(Rectangle.Round(rf))
            Next

            Dim newList As New List(Of Rectangle)
            Dim alreadyFound As Boolean = False

            ' Check if any of the found rectangles can be combined.
            For Each r As Rectangle In rectangles

                ' Check if the rectangle was already combined.
                For Each item In newList
                    If item.Contains(r) Then
                        alreadyFound = True
                        Exit For
                    End If
                Next

                ' If it's a new rectangle, find any matching neighbors.
                If Not alreadyFound Then
                    newList.Add(FindNeighbors(rectangles, r))
                End If

                alreadyFound = False
            Next

            finalRectList.Add(c, newList)
        Next

        e.Bitmap.UnlockBits(data)
    End Sub

And here is the code for FindNeighbors.

    Friend Shared Function FindNeighbors(ByRef rects As List(Of Rectangle), rc As Rectangle) As Rectangle
        For Each r In rects

            ' We want to skip rc if we find it.
            If r = rc Then
                Continue For
            End If

            If r.X = rc.X AndAlso r.Width = rc.Width Then ' Same width and left position.

                ' If edges touch.
                If r.Top = rc.Bottom Then ' If rc is above r, just extend the height.
                    rc.Height += r.Height
                End If

            End If
        Next

        Return rc
    End Function

Let me know if you see anything that could possible be improved on, either functionality or speed-wise. Thanks.