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

["Nirav Patel" <olpc@xxxxxxxxxxxxxx>]

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
>
>