Home · Pages · Index · Overviews

Region Class Reference

A compact encoding of any connected collection of voxels. More...

 #include <region.h>

Visible Fields

rastlen : Size_Type
raster : Indx_Type *
Length of the raster pair vector (always even)
Voxels are [raster[i],raster[i+1]] for i in [0,rastlen) and i even

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)

Regions * Fill_Region_Holes (Region *reg RM)

boolean Get_Region_Connectivity (Region *reg)
int Get_Region_Dimensionality (Region *reg)
Dimn_Type * Get_Region_Dimensions (Region *reg)

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)

Size_Type Region_Volume (Region *reg)
Size_Type Region_Area (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)

Extent_Bundle * Region_Extent (Extent_Bundle *ext RO, Region *reg)
boolean Touches_Boundary (Extent_Bundle *ext, APart *part)

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

rastlen: Size_Type
raster: Indx_Type *

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.

Region * Record_BasicG (APart *image, int share, boolean iscon2n, Indx_Type leftmost,
                            boolean with_holes, Comparator cmprsn, Value level)

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.

Region * Record_Level_SetG (Level_Tree *t, Level_Set *r, boolean with_holes, int share)

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.

Dimn_Type * Get_Region_Dimensions (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.

Range_Bundle * Region_Range (Range_Bundle *rng RM, APart *part, Region *reg)

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

Size_Type Region_Volume (Region *reg)

Returns the number of pixels in reg.

Size_Type Region_Area (Region *reg)

Returns the surface area of the outer contour, i.e. the number of (n-1)-dimensional hyper faces in the outer contour.

Double_Vector * Region_COM (Double_Vector *com RO, Region *reg)

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.

Double_Vector * Region_Select_COM (Double_Vector *com RO, Region *reg,
                                      APart *part, Comparison cmprsn, Value level)

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

Extent_Bundle * Region_Extent (Extent_Bundle *ext RO, Region *reg)

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.

boolean Touches_Boundary (Extent_Bundle *ext, APart *part)

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