Re: [pygame] Proposed additions to Transform: connected components, upper and lower thresholding, and centroids

["René Dudfield" <renesd@xxxxxxxxx>]

Hi,

I think it should be fine to go ahead with what you need.  Then we can
possibly change them afterwards - maybe replacing them with more
generic ones if needed.

I guess the centroid isn't always the center of a rect containing those pixels?

I think allowing a Mask as a destination for threshold is a good idea.

As you say, also perhaps giving the camera what format you want the
data would be good.  So you can get the Hue plane from the HSV color
space.

Marcus what do you think of this?  Also what about storing the data in
different color spaces?



* Mask.connected_component(Mask) - Takes an input mask and returns a
Mask of the largest connected component.
I think this could be done by get_bounding_rects and sorting the list
of returned connected areas?  It might be a little slow if the number
of connected areas is quite large... however the python sort function
is quite fast.  Then afterwards you could get the centroid(see next
function).

* Mask.get_centroid(bounding_rect) -> (number_of_pixels, centroid_xy).
  Takes an input mask, and a rect and returns the number of pixels and
the centroid of those pixels.

I think this Mask.get_centroid method could be a good one, except
perhaps allow passing in a rect?  This would allow you to get the
centroid of any of the rects returned by Mask.get_bounding_rects()

Or is getting the center of a rect enough?


cheers,


On Tue, Jun 17, 2008 at 1:50 PM, Nirav Patel <olpc@xxxxxxxxxxxxxx> wrote:
> Thanks René and Charlie.  I misunderstood what theshold was doing.  It
> will work fine for what I was going for.
>
> The reason I preferred to fold something like centroid into an
> existing function is that it adds a negligable amount of execution
> time to a function that is already traversing the array, like
> threshold.  Having it seperate would mean having to go through a huge
> array again.
>
> What I want to do is basically the following:
> 1.  Capture a Surface from a camera.
> 2.  Convert it to HSV colorspace.
> 3.  Threshold out a specific hue as a mask.
> 4.  Find the largest connected component of that mask.
> 5.  Find the centroid and number of pixels in that connected component.
>
> The plan is to be able to do while having to traverse the image array
> as few times as possible.  I want to be able to run it at 30 fps on an
> OLPC XO while still leaving time to do other stuff each frame.
>
> I can fold converting to HSV into the first step.  Perhaps by having
> an option to supply threshold() with a Mask to create, that could
> eliminate one traversal.  Then with a Mask, as René suggests, there is
> much less data to deal with.  How about the following function to deal
> with the rest?
>
> Mask.connected_component(Mask) returns (pixels, (x, y)) - Takes in a
> input mask and optionally creates a new mask with the largest
> connected component?
>
> or maybe split it into:
>
> Mask.connected_component(Mask) - Takes an input mask and returns a
> Mask of the largest connected component.
> Mask.centroid() returns (pixels, (x,y)) - Takes an input mask and
> returns the number of pixels and the centroid of those pixels.
>
> Nirav
>
> On Tue, Jun 17, 2008 at 11:47 AM, Charlie Nolan <funnyman3595@xxxxxxxxx> wrote:
>> Nirav Patel wrote:
>>> For vision purposes, it would be very useful to have thresholding with
>>> both upper and lower boundaries, returning both the number of pixels
>>> within the threshold and the centroid of those pixels.  This is a
>>> trivial addition to the existing transform.threshold() function, but
>>> is it acceptable to modify the input options and the output of an
>>> existing function?  Would it break compatibility with existing pygame
>>> games?  Would it make sense to have a second function so similar to an
>>> existing one?
>>
>> transform.threshold... does not work the way you think it does.  It's
>> not a simple computer imaging "below or above value X" threshold, it's
>> "are we within X or color Y".  You can approximate a two-level threshold
>> with something like this:
>>
>> def simple_threshold(surface, min=0, max=255):
>>    dest_surface = pygame.Surface(surface.get_size(), 0, surface)
>>    avg = (min + max) // 2
>>    dist = avg - min
>>    color = (avg, avg, avg)
>>    threshold = (dist, dist, dist)
>>
>>    pygame.transform.threshold(dest_surface, surface, color, threshold)
>>    return dest_surface
>>
>> Really, the best thing to do might be to create a
>> transform.grayscale_threshold function.  As you can see, the current
>> threshold function doesn't exactly do what you need, even though the
>> name matches.
>>
>> As to the centroid, that might be best as its own function.
>>
>>> The other function, which is also similar (and could even just be an
>>> option in thresholding), is thresholding with connected component
>>> detection.  This would involve supplying an upper and lower threshold,
>>> a Surface, and optionally a mask.  The function would find the largest
>>> blob of pixels in the Surface within the threshold, make a mask of
>>> those pixels if desired, and return the centroid and number of pixels
>>> in the blob.
>>
>> Again, separate out your pieces.  What you're describing is
>> bw_threshold, followed by connected_components and get_centroids.
>>
>>> It could also be useful to have multiple connected component
>>> detection, for "multi-touch" without having to use different colored
>>> objects (or if you are using IR LEDs like the Wii does), but I'm not
>>> sure how to handle that in a single pass of the array.  Actually, I'm
>>> not really sure how I'm going to handle both detection and creating a
>>> mask in a single pass either.  It may be necessary to store the
>>> starting pixel, ending pixel, and size of each connected component on
>>> the first pass, keeping track of which was the largest yet, and then
>>> have a shorter second pass to create the mask that only starts at the
>>> starting pixel and ends at the ending pixel.
>>
>> Go look up the standard connected components algorithm.  It's two-pass,
>> by necessity.  If you try to do it in a single pass, you end up with an
>> O(n^2) algorithm instead of O(n).
>>
>> What connected components does is take a BW image and turn it into a
>> grayscale image, with each color of pixel representing a different
>> connected component.  So starting color is irrelevant, since you have to
>> process it down to BW to start with.
>>
>> -FM
>>
>>
>