Region Class Reference
A compact encoding of any connected collection of voxels.
More...
#include <region.h>
Visible Fields
Routines
Region * |
Record_RegionG
(APart *image, int share, boolean iscon2n, Indx_Type leftmost, boolean with_holes, void *argt, boolean (*test)(Indx_Type p, void *argt)) |
Region * |
Record_BasicG
(APart *image, int share, boolean iscon2n, Indx_Type leftmost, boolean with_holes, Comparator cmprsn, Value level) |
Region * |
Record_Level_SetG
(Level_Tree *t, Level_Set *r, boolean with_holes, int share) |
Region * |
Record_P_VertexG
(Partition *p, int v, boolean with_holes, int share) |
void |
For_Region
(Region *reg, void *arg, void (*handler)(Indx_Type p, void *arg)) |
void |
For_Region_Outline
(Region *reg, void *arg, void (*handler)(Indx_Type p, void *arg)) |
void |
For_Region_Holes
(Region *reg, void *arg, void (*handler)(Indx_Type p, void *arg)) |
void |
For_Region_Exterior
(Region *reg, void *arg, void (*handler)(Indx_Type p, void *arg)) |
Range_Bundle * |
Region_Range
(Range_Bundle *rng RM, APart *part, Region *reg) |
Double_Vector * |
Region_COM
(Double_Vector *com RO, Region *reg) |
Double_Vector * |
Region_Select_COM
(Double_Vector *com RO, Region *reg, APart *part, Comparison cmprsn, Value level) |
Detailed Description
A Region object models any 2n- or
(3n-1)-connected
set of voxels in an n-dimension array or slice.
The basic encoding models the set as runs of consecutive voxels that are in the
region, that is, the voxels of a region are precisely
∪
{ [ raster[i], raster[i+1] ] : i ∈ [0,rastlen-1] and i even }.
That is, to perform some simple computation on a region, the following template suffices:
Region *r;
Size_Type k;
Indx_Type p;
for (k = 0; k < r->rastlen; k += 2)
for (p = r->raster[k]; p <= r->raster[k+1]; p++)
// Compute something on voxel p
Note carefully, that indices p into a particular lattice are being referred to, so while a region
isn't coupled to a particular array, it is only applicable to arrays of the same shape as that
over which the region was recorded. One may conceptually think of a region as an arbitrary
connected mask that can be applied to any array of the appropriate shape.
A given C-connected region R has an (n-1)-dimensional outer contour and may have any number
of inner countours surrounding holes. If C is 2n (connectivity), then let S be
(3n-1),
and if C is
(3n-1) then
let S be 2n.
A hole is a maximal, S-connected set of voxels not in
the region R that is completely surrounded by voxels in R.
The exterior of R is the unique, maximal, S-connected set of voxels that
cannot be surrounded by pixels of R.
The outer border of R is the C-connected set of voxels
that are S-connected to an exterior voxel.
The example below shows a 2-dimensional region of yellow voxels that is both 4- and 8-connected.
Note carefully that the outer contour, outer border, and which voxels are in a hole depends on
whether one considers the region to be 4- or 8-connected.

The outer hull of a region R is R plus all the voxels in all the holes surrounded by R.
One often needs only the outer hull of R, which can also be
encoded as a region as it is appropriately connected.
The recording routines can be directed to compute the outer hull versus the region with
holes by appropriately setting the boolean parameter with_holes.
Note carefully, that the class routines compute the outer hull in time proportional to the
surface area of the outer contour, whereas the proper detection of any holes requires time
proportional to the volume of the outer hull.
The hidden portion of a region object contains
(a) the shape of the array over which the region was recorded,
(b) the surface area of the outer contour, i.e. the number of (n-1)-dimensional hyper
faces in the outer contour,
(c) an encoding of the set of voxels in the outer border of the region, and
(d) an enoding that determines whether an exterior run (a run of non-R voxels between two
runs of R voxels) are in a hole or not.
The coding of this information is
sufficiently complex that it remains hidden, but it is still effectively available through
the routines of the class.
A region can be "recorded" by Record_Region for any set of voxels in a given array or slice
that are connected to a leftmost seed and satisfy a user-definable predicate. A voxel is
leftmost if a step in the negative x-direction takes one to a voxel that is not in the region
and not in a hole surrounded by the region. The voxel in a region with the minimum index
is always leftmost and can be computed with Find_Leftmost_Seed if necessary. A region can
also more simply be recorded by Record_Basic as the set of voxels connected to the leftmost
seed and satisfying a given comparison, i.e. < ≤ ..., with respect to a given, fixed
value. One can also record a region of any Partition or Level_Set, with Record_P_Vertex
and Record_Level_Set.
Once recorded, the connectivity under which a region was recorded and the shape of the array
over which it was recorded can be fetched with Get_Region_Connectivity,
Get_Region_Dimensionality, and Get_Region_Dimensions.
One can iterate over the voxels in a region with For_Region, but when speed matters
we suggest one use the simple code template above with respect to the visible fields of
the region. For iterating over the voxels in the outline, the holes, or the exterior of
a region, one can use For_Region_Outline, For_Region_Holes, For_Region_Exterior.
One can fill in a Range_Bundle giving the minimum and maximum values in a particular array
(and not necessarily the one over which the region was recorded), with Region_Range.
One can get the volume, area, and center of mass with Region_Volume, Region_Area, and
Region_COM. The center of mass is returned as an n-dimensional Double_Vector as it
need not lie on an integer lattice point. One can round this vector to a Coordinate
with routines such as Floor_Coord. One can also compute the center of mass with respect
to a subset of voxels defined by a comparison and a level (as for Record_Basic) with
Region_Select_COM. Finally, one can compute the rectalinear extent of a region with
Region_Extent and inquire as to whether that implies the region touches the boundary
of an array or slice thereof with Touches_Boundary.
Visible Fields Documentation
Most of a Region object is hidden, but for efficiency purposes, one is given direct access
to the run length encoding of the set of voxels in the region. The set of voxels in a
region is precisely
∪
{ [ raster[i], raster[i+1] ] : i ∈ [0,rastlen-1] and i even }.
In terms of code, one would perform a computation on each voxel as follows:
Region *r;
Size_Type k;
Indx_Type p;
for (k = 0; k < r->rastlen; k += 2)
for (p = r->raster[k]; p <= r->raster[k+1]; p++)
// Compute something on voxel p
Routine Documentation
Region * |
Record_RegionG (APart *image, int share, boolean iscon2n, Indx_Type leftmost, boolean with_holes, void *argt, boolean (*test)(Indx_Type p, void *argt)) |
Generate a Region object that compactly models the set of voxels in image that are
iscon2n connected to a leftmost seed pixel leftmost and satisfy the predicate
test(p,argt). If image is a slice, then the region is limited to the volume of the
slice, albeit defined with respect to the underlying array of the slice. If with_holes is
false then a description of the outer hull of the defined region is returned, otherwise an
encoding of the region, properly excluding any holes within it, is returned. When with_holes
is false, the region is computed in time proportional to the surface area of the outer
hull, and when it is true, the routine is less efficient, taking time proportional to the
volume of the outer hull. The parameter
share determines how the surface flood fill, Flood_Surface, called by this routine,
uses the resource pool of working storage for said operation. This parameter can be safely
set to 0, but if one wishes to write a threaded application they should understand the
details that are described in the Connectivity module page
here.
Finally, note that the Region only records the dimensionality and shape of the underlying
array of apart, but does not reference it. In this way, a region can be though of as an
irregular mask that can be applied to any other array of the same dimensionality and shape.
A simplified version of Record_Region above, that defines the region as all pixels that
satisfy 'val[p] cmprsn level' where val[p] is the value of pixel p in image. For
example, if cmprsn = GE_COMP and level = 12, then the region is all pixels iscon2n
connected to leftmost that are greater than or equal to 12.
Generate a Region for level set r in level tree t. The parameters with_holes and
share are as for Record_Region above.
Region * |
Record_P_VertexG (Partition *p, int v, boolean with_holes, int share) |
Generate a Region for region or vertex v of the Partition p. The parameters
with_holes and share are as for Record_Region above.
Regions * |
Fill_Region_Holes (Region *reg RM) |
Modify the value of reg so that all holes within the region are filled, giving one
a region representing the outer hull of the region.
boolean |
Get_Region_Connectivity (Region *reg) |
Return true if the region was recorded with 2n-connectivity, and false if it was
recorded with
(3n-1)-connectivity.
int |
Get_Region_Dimensionality (Region *reg) |
Return the dimensionality of the region reg.
Return the dimensions of the arrays to which reg can be applied.
void |
For_Region (Region *reg, void *arg, void (*handler)(Indx_Type p, void *arg)) |
For each voxel p in the region reg, call handler(p,arg) on the voxel.
void |
For_Region_Outline (Region *reg, void *arg, void (*handler)(Indx_Type p, void *arg)) |
For each voxel p in the outer border of reg, call handler(p,arg) on the voxel.
void |
For_Region_Holes (Region *reg, void *arg, void (*handler)(Indx_Type p, void *arg)) |
For each voxel p in a hole of reg, call handler(p,arg) on the voxel.
void |
For_Region_Exterior (Region *reg, void *arg, void (*handler)(Indx_Type p, void *arg)) |
For each voxel p not in the outer hull of reg, call handler(p,arg) on the voxel.
Determines the range of values in the region reg super-imposed on part and places the
values in rng. The array underlying part must have the same shape as the reg (which
is the shape of the underlying array over which it was recorded).
Returns the number of pixels in reg.
Returns the surface area of the outer contour, i.e. the number of (n-1)-dimensional hyper
faces in the outer contour.
Returns the center of mass (com) of the region reg as a double vector that can, if desired, be
rounded to a nearest Coordinate with routines such as Floor_Coord.
Returns the center of mass of the pixels within reg that satisfy the given comparison
cmprsn with value level in the array or slice part, i.e.
all pixels p that satisfy 'val[p] cmprsn level' where val[p] is the value of
pixel p in the array underlying part.
The array underlying part must have the same shape as the reg (which
is the shape of the underlying array over which it was recorded).
Determines the extent of the region reg and fills in the bundle ext with the minimum
and maximum coordinates of the extent box. Note that these are a pair of n-dimensional
opposing corners of the n-dimensional extent box where n is the dimensionality of the
region. If the min and max fields of the Extent_Bundle are NULL on input,
then the routine generates Coordinates of the appropriate size, otherwise whatever array
they point to is converted to an n-element Coordinate if they are not already thus,
and then filled in with the extent values. The caller is responsible for freeing or
killing these coordinates.
Given an extent ext in an Extent_Bundle (presumably filled in by Region_Extent), this
routine returns true only if the extent box touches the boundaries of the array underlying
part, i.e. AForm_Array(part).
|