![]() |
Home · Pages · Index · Overviews |
Partition Class ReferenceA graph model of a partition and routines to progressively collapse said. More... #include <water.shed.h> Structures
Descriptive Types
RoutinesPartition Routines
Merging Routines
Detailed DescriptionPartition GraphsA Partition models a partitioning of an image into connected subsets of pixels. It is primarily used in mylib to model the results of a watershed partitioning of an image (described below), but it can in fact model any partitioning or partial partitioning of an array. At the topological level a Partition is an undirected graph, where each vertex represents a subset of connected pixels or a region of an image and is modeled by a P_Vertex structure that gives the number of pixels in the region, the value of a minimal pixel in the region, and a leftmost seed pixel for the region. There is an edge for every pair of adjacent partition elements, modeled by a P_Edge, that represents the border that is common to the two touching regions. It further gives the smallest value of a pixel on one side or the other of this shared border. A Partition object maintains a reference to the image it partitions, and may optionally have a reference to a UINT8_, UINT16_, or UINT32_TYPE label array that gives a voxel-based representation of the partition in one of two forms. The label array is either (a) a labeling of the voxels of the partition where a pixel has label i if it belongs to region i-1, or (a) a coloring of the voxels in the partition such that (i) all voxels in a given region have the same strictly positive value, and (ii) this value is different from the values used to label any adjacent region. In both cases, pixels labeled 0 are not part of the partition, and their presence implies the partition is partial. Generally a coloring involves many fewer distinct values/colors, and hence can often fit in a UINT8_TYPE label array when memory is at a premium. Together with the leftmost seed of a P_Vertex, either labeling allows one to easily capture the voxels in a basin with a flood fill from the seed to all pixels with the same value (see Record_P_Vertex). A Partition's image reference can actually refer to an entire array or a slice thereof. The associated label array must have the same shape as the image in the case that it is an array. But to facilatate threaded algorithms, when the image reference is to a slice, the associated label array may have either the shape of the slice, or the shape of its underlying array, in which case the voxels of the same slice of the label array corresponds to those of the image slice. The indices stored for the leftmost seed pixel of a P_Vertex are always indices into the label array and not the image. These happen to coincide when the image is an array, or when the image is a slice and the label array has the shape of the slice's array. But note carefully that when the image is a slice and the label array has the shape of the slice, indices into the label array do not correspond to indices into the image array. Given a labeling label (not a coloring) of an image array image that has regions distinctly labeled between 1 and nregions that are iscon2n connected, Make_Partition(image,label,nregions,iscon2n,color) creates a Partition graph corresponding to the labeling. The labeling label may have zero pixels, which are ignored, and whose presence implies that the resulting partition is partial in that the union of its regions do not cover the entire domain of the label array. As mentioned immediately above, label can have the shape of either image or its underlying array if it is a slice, and this choice for the shape of label has an effect on the nature of the indices stored for the seed voxel of each P_Vertex. If requested, by setting the boolean parameter color to true, the label array (or relevant slice thereof) will be relabeled greedily to provide a coloring of the partition. Note however, that the conversion to a coloring does not have to be performed at the time of creation, but can occur at any time by invoking Color_Partition. The labeling label may on input be over small integers, e.g. a UINT8_TYPE array but may, if the construction or coloring requires it, be enlarged to be a UINT16_ or UINT32_TYPE array upon completion. The construction requires one extra bit for a sign be available, and while a coloring may use more colors than a labeling, this would be highly unusual. Thus a UINT8_TYPE labeling can be used when there are 127 or fewer regions, and a UINT16_TYPE labeling can be used when there are 32,767 or fewer regions. Given a Partition graph, p, one can retrieve the number, V, of regions or vertices, the number, E, of edges, and the number of distinct values in the label array of p (if it has one) with the routines Get_Partition_Vertex_Count, Get_Partition_Edge_Count, and Get_Partition_Label_Count, respectively. A pointer to the label array for a partition graph is return by Get_Partition_Labels and Is_Partition_Colored returns true iff and only if the label array is a coloring. A pointer to the P_Vertex structure for the i th region is return by Get_Partition_Vertex(p,i) for i ∈ [0,V-1], and a pointer to the P_Edge record for the e th edge is return by Get_Partition_Edge(p,e) for e ∈ [0,E-1]. In fact, both of these structures are consecutive in memory, so one can, for example, get the pointer b = Get_Partition_Vertex(p,0) to the first region, and then access the i th region or vertex more efficiently as b[i]. The edges adjacent to the i th region are obtained by calling a = Get_Partition_Neighbors(p,i,&n), where a[j] for j ∈ [0,n-1] is the set of indices for the edges involving i, i.e. either Get_Partition_Edge(p,a[j])->region1 = i or Get_Partition_Edge(p,a[j])->region2 = i. To further clarify, the code snippet below lists the vertices that are adjacent to each vertex in partition p: P_Edge *e, *f; int *a, n, v; int i, j; e = Get_Partition_Edge(p,0); v = Get_Partition_Vertex_Count(p); for (i = 0; i < v; i++) { a = Get_Partition_Neighbors(p,i,&n); printf(" %d:",i); for (j = 0; j < n; j++) { f = e+a[j]; if (f->region1 == i) printf(" %d",f->region2); else printf(" %d",f->region1); } printf("\n"); } The connectivity, the array or slice from which p was built, and the label array of p can be retrieved later with Is_Partition_2n_Connected, Get_Partition_APart, and Get_Partition_Labels. A Partition object can be read and written to a file, but it relies on a reference to the underlying array from which it was built, so when you read in a Partition you must re-establish this reference with Set_Partition_APart. Similarly, the label array is not a sub-object of a partition, and its pointer must be re-established with a call to Set_Partition_Labels after reading in a partition. This routine can also be used to set the label array reference to NULL, giving a partition graph that no longer refers to the label field that defined it. Lastly, with Draw_Partition one can obtain a nicely colored image of a watershed blended by a selectable factor alpha with respect to any image with the same shape as the watershed's underlying array. Collapsing PartitionsThe watershed algorithm (see the Watershed module) tends to produce partitions that oversegment an image as it is sensitive to small fluctuations in signal. A common approach to solve this problem is to progressively merge catchment basins (partition regions) for which the difference between their depth and the dam height separating them is small. To facilitate such solutions, Static_Collapse progressively merges partition regions in order of height as directed by a handler routine that for any pair of current regions, decides if they should be merged. The handler should return a value greater than 0 if the regions should be merged, 0 if they should not, and a value less than 0 if the regions should not be merged and no further merging is desired. The routine does not actually perform the merges, but rather builds a collapsing map that for each original region gives the index of the new region to which it should belong. Given such a Map_Bundle, Merge_Partition then will generate a new Partition object that models the collapsed watershed implied by the map. An example of the use of these routines, is given by Build_Seeded_Watershed, that generates a watershed for the coarsest merging of an initial watershed such that each collapsed set of basins contains exactly one pixel from a user-supplied set of seed pixels. One may also wish to consider collapsing regions of a partition in an order of edges that is dynamic and specified by the caller, as opposed to the fixed, height order of Static_Collapse. For example, for a partition w, the utility Average_Watershed_Heights (from the Watershed module) fills in vectors num and den of length Get_Partition_Edge_Count(p) so that for the jth edge, num[j] is the sum of the pixel values along the boundary separating the two basins, den[j] is the number of pixels along the boundary, and therefore num[j]/den[j] is the average height of the boundary separating the two regions of the edge. This measure of separability between two regions may be more useful in cases where there are weaknesses in the barrier, such as irregularly stained biological boundaries. One may then wish to collapse regions (catchment basins) in order of average (dam) height, where a little thought reveals that average height changes as regions are merged, because this implies region boundaries must also be merged. General_Collapse is a generalization of Static_Collapse that allows the order of collapsing decisions to be directed dynamically by the caller who supplies three handler routines that direct the process. The routine compare(a,ab,b,c,cd,d) should return true if and only if the edge with index ab is considered to be less than or equal to the edge with index cd. The indices of the regions a and b on each side of ab are also supplied, the reason being that as the collapsing progresses, the edges and vertices are really unions of merged edges and vertices, so the indices representing the merged regions on either side of the fused edge represented by ab are not simply the region1 and region2 fields of the P_Edge structure in the subject partition. The handler decide(a,ab,b) is the same as for Static_Collapse, and given vertex indices a & b and the edge index ab for the edge between them, returns a value greater than 0 if a and b should be merged, 0 if they should not, and a value less than 0 if they should not and no further merging should take place. If the regions are merged, then a is the vertex that will represent their union going forward. Furthermore, observe that there can be regions, c, that are adjacent to both a and b in which case the edges ac and bc need to be fused. Fuse(a,ac,c,cb,b) is called for each appropriate c in order to inform the caller that the edges ab and cb are being fused and their union will be represented by ab going forward. Depending on the logic of the collapsing, a given collapse can in some cases affect only the priority of edges that are fused (as in the example below), or in the most general case a collapse can effect the priority of every edge adjacent to the fused result. The later case requires more updating of the heap and is not as efficient. The boolean dynamic signals the more complex case when true, and the simpler case when false. As for Static_Collapse, General_Collapse does not actually generate a new partition, but rather fills in a map that can then be merged with Merge_Partition. The code example below, realizes a routine Average_Collapse that collapses watershed graph w in order of average dam height, merging all basin pairs for which the difference between their deepest voxel and the average dam height is less than a threshold barrier. As basins are merged and dams fused, the depth of the resulting basin, and the num and den of the fused dam boundaries must be updated. To do so a void * payload pointer pointing at an Info structure that contains arrays for each of these three attributes is initialized and then modified by the handlers during the collapsing. For example, note that when two dams ab and cb are combined in FUSE, the new dam's num and den attributes are recorded in the values for dam ab as this will be the representative index going forward. Further note that DECIDE updates the depth attribute of basin a, if a and b are going to be merged. Finally, note that the merged result will have a UINT32_TYPE labeling as its label array. This could be colored and compacted into a UINT8_ or UINT16_TYPE array if desired. typedef struct { int barrier; int *depth; int *num; int *den; } Info; #define INFO ((Info *) arg) #define AVEHGT(d) ((1.*INFO->num[d])/INFO->den[d]) tristate DECIDE(int a, int ab, int b, void *arg) { int bar; if (INFO->depth[a] < INFO->depth[b]) bar = AVEHGT(ab) - INFO->depth[b]; else bar = AVEHGT(ab) - INFO->depth[a]; if (bar <= INFO->barrier) { if (INFO->depth[b] < INFO->depth[a]) INFO->depth[a] = INFO->depth[b]; return (1); } return (0); } void FUSE(int a, int ac, int c, int cb, int b, void *arg) { INFO->num[ac] += INFO->num[cb]; INFO->den[ac] += INFO->den[cb]; } boolean COMPARE(int a, int ab, int b, int c, int cd, int d, void *arg) { return (AVEHGT(ab) <= AVEHGT(cd)); } Partition *Average_Collapse(Partition *w, int barrier) { int nbasins = Get_Partition_Vertex_Count(w); int nedges = Get_Partition_Edge_Count(w); P_Vertex *verts = Get_Partition_Vertex(w,0); Map_Bundle map; Info info; int i; into.barrier = barrier; info.depth = (int *) Guarded_Malloc(sizeof(int)*(nbasins+2*nedges),"Average_Collapse"); info.num = info.depth + nbasins; info.den = info.num + nedges; for (i = 0; i < nbasins; i++) info.depth[i] = verts[i].depth; Average_Watershed_Heights(w,info.num,info.den); map.mapto = NULL; General_Collapse(&map,w,0,&info,DECIDE,FUSE,COMPARE); wp = Merge_Partition(w,&map,Make_Array_With_Shape(PLAIN_KIND,UINT32_TYPE,AForm_Shape(w)),0); free(info.depth); free(map.mapto); return (wp); } Structure Documentation
Get_Partition_Vertex returns a pointer to a structure of this type, that provides information about a particular vertex or region in a partition. The size is the number of voxels in the region and depth is the value of the deepest (smallest) voxels in the region. For a watershed partition the set of pixels with this value in the region form a single connected minimum. The field seed is a voxel index into the underlying array for the partition, and can be used to flood-fill the region in conjunction with the label field of the partition. This seed is leftmost which implies it can be used in calls to routines such as Record_Region that require the seed to have this property. Moreover, this index is always in the framework of the label array, so in the particular case that the image is a slice, and the label array has the shape of the slice, then the seed is into the label array and is not valid in the image.
Get_Partition_Edge returns a pointer to a structure of this type, that provides information about a particular edge between two regions in a partition whose borders touch each other. region1 and region2 are the indices of the two regions or vertices separated by the edge, and height is the value of the lowest voxel along the edge boundary separating the two regions.
Consider a image partition with nregions regions. A Map_Bundle gives a map that effectively merges regions together and renumbers them consecutively from 0 to nrange-1 where nrange ≤ nregions. The field mapto[i] for i ∈ [0,nregions-1] gives the number of the new region that region i should belong to, where Ui mapto[i] is [0,nrange-1]. Static_Collapse and General_Collapse fill in such a bundle as their merging result, and Merge_Partition uses such a bundle to generate a new partition representing the collapsed result. Routine Documentation
Return true if and only if partition p was built with respect to 2n-connectivity (as opposed to (3n-1)-connectivity).
Returns true if and only if partition p's label array is a coloring (as opposed to a label field). If the label array is NULL, then the result is undefined.
Return the Array or Slice (APart) that partition p was made from.
If p has a reference to an image it is freed, and then a a new reference to image is created and set to be the image referenced by p. The somewhat awkward need for this routine is to relink the partition with its image in the event you read it in from a file. A partition object can be written and later read, but writing the object does not write the image upon which it depends, so one must take care to write the image as well. Later when you read both the image and partition from the file, one needs this routine link them back up.
Return the label field or coloring of the regions of p. The type of the array can be UINT8_, UINT16_, or UINT32_TYPE and its shape is either the same as that of the APart image over which p was produced, or its underlying array.
If p has a reference to a label array it is freed, and then the label array of partition p is set to labels, consuming the reference to said. Primarily used to relink the partition with its label array in the event you read it in from a file (see Set_Partition_APart). One can also set the label array to NULL which effectivly disassociates a partition from the label array that defined it. This is useful if memory is at a premium and the voxels of each region no longer need to be accessed.
Return the number of regions (vertices) in p.
Return the number of edges in p.
Return the number of distinct labels or colors used to color the label field of p.
Return a pointer to the P_Vertex structure for the cth region of p.
Return a pointer to the P_Edge structure for the dth edge of p.
Return a pointer to an integer vector, say a, that gives the n edges adjacent to the cth region of p. That is, a[j] is the index of an edge adjacent to the region with index c, for j ∈ [0,n-1].
Given an array or slice image and an iscon2n-connected labeling (not a coloring) labels of said with nregions strictly positive labels, generate a Partition object that encodes the (partial) partition in the label field and if color is true convert labels into a coloring of the partition encoded therein. Note carefully, that 0-labeled pixels are ignored and imply that the resulting object is a partial partition. Moreover, image must be an UINT or INT array of values with not more than 32 bits. The coloring, of the label array, if requested, is greedy (so for example more than the maximum 4 colors needed for any 2D partition may be used), but the number of colors is generally very small. The Partition object creates a new reference to image and consumes the reference to label (i.e. the object keeps an internal reference to label that it is taking from the caller). The label array may have its type enlarged if the extra sign bit required by the routine or the number of colors in a greedy coloring demands it. Conversely, if the labeling is converted into a coloring, then it may well be the case that one can compress the label array into a UINT8_ or UINT16_TYPE array. For example, Build_Watershed below is realized using Label_Watershed and Make_Partition and then compressing the coloring if possible. Partition *Build_Watershed(Pixel_APart *image, boolean iscon2n, boolean color) { Label_Array *h; Partition *s; int n; h = Make_Array_With_Shape(PLAIN_KIND,INT32_TYPE,AForm_Shape(image)); Label_Watershed(image,h,&n,iscon2n); s = Make_Partition(image,h,n,iscon2n,color); if (Get_Partition_Color_Count(s) < 256) Convert_Array_Inplace(h,PLAIN_KIND,UINT8_TYPE,8,0); else if (Get_Partition_Color_Count(s) < 0x10000) Convert_Array_Inplace(h,PLAIN_KIND,UINT16_TYPE,16,0); Pack_Array(h); return (s); }
The label array of a partition object (if present) can be converted from a labeling to a coloring at any time after its creation with this routine. A pointer to the partition is returned as a convenience.
Color the pixels of an RGB-array canvas with the partition p where alpha of the pixel range is the partition coloring and 1-alpha is whatever value is already in the canvas. If the canvas is the same shape as the shape of the APart the partition was computed over, then the partition colors the entire canvas. The other possibility is that the canvas is the shape of the underlying array of the Apart (which must be a slice) in which case the portion of the canvase covered by the slice is colored.
Fills in a collapsing map that results from progressively merging partitions in order of edge height as directed by the handler routine decide. The inputs are a partition and a user-suppled payload pointer arg that will be passed to each call of decide (ensuring re-entrant semantics if desired). When a pair of regions is considered for merging by decide, the indices a and b of the two regions to be merged is passed to decide along with the height h of the edge between them. The indices are in the range [0,V-1] where V = Get_Partition_Count_Count(p). Decide should return a value greater than 0 if the two elements are to be merged, 0 if they are not, and a value less than 0 if they are not to be merged and no further merging is desired. In the event of a merge, the left argument a will represent the combined region, so any information about the current set of regions encoded in the structure pointed at by arg should be updated by the user before returning from the handler. Elaborating further, the partition data structure is not modified during the collapsing, but rather the current set of merged regions is modeled as the collapsing progresses, where each set of currently collapsed regions is represented by one of the original regions depending on the sequence of calls to the handler. For example, suppose decide chooses to merge the region pairs (a,b), (c,d), (e,a), (c,e) in the order given, then at the end of the sequence the regions a, b, c, d, e are all merged into a single region represented by c. At the end of the collapsing, a map from each region to the index of a new region index in the collapsed partition is filled in and returned and this map can subsequently be given to Merge_Partition which actually generates a new merged partition. The map is returned in the user-supplied Map_Bundle that contains nrange, the number of basins in the collapsed result, and mapto where mapto[i] gives the number of the new region that region i now belongs to. The union Ui mapto[i] = [0,nrange-1]. If mapto is NULL on input, then the necessary integer vector is malloc'd, otherwise mapto will be enlarged to hold the result if necessary.
Fills in a collapsing map that results from progressively merging partitions as directed by the handler decide, in the order dictated by the handler compare. The inputs are a partition and a user-suppled payload pointer arg that will be passed to each of the three input handlers decide, fuse, and compare (ensuring re-entrant semantics are possible). As the collapsing progresses vertices are conceptually being merged, which further requires that edges between vertices are also being fused together. During the merging process, any merged set of regions is represented by just one of the original regions, and the index of this region/vertex is effectively known to the caller by virtue of the convention that whenever decide(a,ab,b) is called, b will be merged into a which will then be the representative index for the union of the set of regions modeled by a and the set modeled by b. Similarly, when region are merged, edges also necessarily need to be fused. Again, a set of fused edges is represented by just one of the original edges, and the index of this edge is effectively known to the caller by virtue of the convention that whenever fuse(a,ac,c,cb,b) is called, cb will be fused into ac which will then be the representative edge index for the union of the set of edge modeled by ac and the set modeled by cb. Initially, every basin is modeled by the index for itself, and every dam is modeled by the index for itself, in p, implying that the range of region indices is [0,V-1] and the range of edge indices is [0,E-1], where V is the number of vertices and E is the number of edges in p. Note that because of this dynamic process, given a region index ab representing a fusion of a set of edges, the regions on either side of this edge must be communicated to the user in case they need information about the adjacent regions to make a decision or perform an update. Therefore, compare(a,ab,b,c,cd,d), whose role is to return true if and only if edge ab should be explored for collapsing before edge cd, needs to passed the indices of the regions representing a, b, c, and d for the two edges. A heap of edges to be explore is ordered according to compare and updated as region merges and edge fusions occur. In the order implied by compare, the handler decide(a,ab,b,arg) is called with a pair of region indices a and b that should be considered for merging where ab is the index of the edge between them. Decide should return a value greater than 0 if the two elements are to be merged, 0 if they are not, and a value less than 0 if they are not to be merged and no further merging is desired. In the event of a merge, the left argument a will represent the combined region, so any information about the current set of regions encoded in the structure pointed at by arg should be updated by the user before returning from this handler. Moreover, for every vertex c that is adjacent to both a and b, the handler fuse(a,ac,c,cb,b,arg) will be called after returning from decide, where ac is the index of the edge between the vertices represented by a and c, and cb is that for regions b and c. The edges for ac and cb are conceptually being fused and ac will represent said fusion going forward, so fuse should update the information about edge ac accordingly via the payload pointer arg. Note carefully, that the partition data structure p is not modified during this collapsing. At the end of the collapsing, a map from each vertex to the index of a new vertex index in the collapsed partition is filled in and returned and this map can subsequently be given to Merge_Partition in order to actually build a new merged partition if desired. The map is returned in the user-supplied Map_Bundle which contains nrange, the number of regions in the collapsed result, and mapto where mapto[i] gives the number of the new region that region i now belongs to. The union Ui mapto[i] = [0,nrange-1]. If mapto is NULL on input, then the necessary integer vector is malloc'd, otherwise mapto will be enlarged to hold the result if necessary.
Merge_Partition merges the regions in p according to the mapping in map such as produced by Static_Collapse and General_Collapse above. A new partition object is returned in which all the regions of the input partition are merged. A new reference to the image source for p is created in building the result. If labels is not NULL, then p must have a label or coloring array and labels must have the same shape as this label array. A labeling or coloring, depending on the setting of color, for the new partition is produced in labels and its reference is given to the new partition. If the type of labels is not sufficient to contain the range of colors/labels required, then the routine adjusts the type (and hence also the size) of labels so that the resulting labeling/coloring fits in the array's values. For example, if labels is a UINT8_TYPE array and one requests a coloring, but say, 300 colors are needed, then labels will be a UINT16_TYPE array upon return. While typically labels is a new label array, it may be the label array of p as long as p no longer needs a label array after producing the merged result, as may be the case if p itself is no longer needed. For example, the small routine below performs a merge of a partition in place. While two partitions exist at a moment in time, only one label array (the most space expensive component) is needed as it is overwritten in place. Partition *Merge_Partition_Inplace(Partition *p, Map_Bundle *map, boolean color) { Partition *q = Merge_Partition(p,map,Inc_Array(Get_Partition_Labels(p)),color) Free_Partition(p); return (q); } |