[vtkusers] get range of binary image data

[David Gobbi]

Hi Jonathan,

There isn't any way of doing it without doing a lot of pixel-checks.
I would recommend that you do the checks in Z first, then Y, and
finally X.  That at least will ensure that no pixel has to be checked
twice.

For example, for the Z check, just start at the first memory address
in the image, and march forward linearly through the memory until the
first non-zero pixel is found.  Save the slice indices for that pixel.
 Do the same thing marching back from the last memory address in the
image.  This gives the Z range.

Within that range, check the Y slices, starting first from one end,
and then from the other end.  This seems obvious enough, but the main
trick is to make sure that you traverse the memory in the right
direction, i.e. in a direction that does not require any strides.
This isn't difficult, it just means going along the rows of the image
instead of across the rows, and you were probably already doing that.

The X slices are the trickiest to do efficiently.  If you go in
slice-by-slice, then you won't have any option except to use strides,
which will kill the memory performance.  So you could go inwards by
several pixels a time instead of going slice-by-slice, i.e. check 16
pixels along each row at a time and have a "|=" accumulator for the
non-zero checks.  Having a constant loop-size allows the compiler to
unroll the loop, the accumulator avoids branches within the body of
the loop, and covering chunks of contiguous memory makes the best use
of the CPU cache lines.  The trick is doing all of this without making
the code incomprehensible.

Not sure if I did a good job of explaining all that.  Just my 2 cents.

 - David

On Tue, Feb 15, 2011 at 12:41 PM, Jonathan Morra <jonmorra at gmail.com> wrote:
> I implemented a way which steps in from the end of each axis until it
> reaches a value of 1, but this is too slow, is there a faster way?
>
> On Wed, Feb 2, 2011 at 12:12 PM, Jonathan Morra <jonmorra at gmail.com> wrote:
>>
>> I have a vtkImageData that is all binary data.  Is there a quick way to
>> get the smallest rectangular bounding box that contains all voxels equal to
>> 1?
>
> _______________________________________________
> Powered by www.kitware.com
>
> Visit other Kitware open-source projects at
> http://www.kitware.com/opensource/opensource.html
>
> Please keep messages on-topic and check the VTK FAQ at:
> http://www.vtk.org/Wiki/VTK_FAQ
>
> Follow this link to subscribe/unsubscribe:
> http://www.vtk.org/mailman/listinfo/vtkusers
>
>