 |
Description  |
|
|
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a method, apparatus, and computer readable storage for implementing a recursive hierarchical segmentation algorithm on parallel computers. More particularly, the present invention enables a computer system to
utilize parallel processes to perform the hierarchical segmentation algorithm, therein decreasing computation time and enabling the creation of hierarchical segmentations on large data sets that would be impracticable just using serial processing.
2. Description of the Related Art
Image segmentation is a partitioning of an image into sections or regions. These regions may be later associated with ground cover type or land use, but the segmentation process simply gives generic labels (i.e. region 1, region 2, etc. . . . )
to each region. The regions consist of groups of multispectral or hyperspectral image pixels that have similar data feature values. These data feature values may be the multispectral or hyperspectral data values themselves and/or they may be derivative
features such as band ratios or textural features.
FIG. 1 illustrates a satellite image of the Baltimore, Md. region. FIG. 2 illustrates the image of FIG. 1 after undergoing segmentation into two region sets. As can be seen by FIG. 2, like regions have been joined. The darker colored region
corresponds to bodies of water, while the lighter colored region represents the land. FIG. 3 illustrates the image of FIG. 1 after undergoing segmentation into three region sets. As can be seen by FIG. 3, the image is colored into three image sets,
each image set containing a like region. The dark colored region corresponds to land, the medium colored region corresponds to water, and the light colored regions correspond to the industrial or dense urban regions.
As can be seen by the FIGS. 1-3, the hierarchical image segmentations can be useful in a multitude of applications, including earth science applications where delineation of the spatial coverage of water or land is required. It can also be used
as substitute ground reference data for the validation of the analysis of lower resolution global coverage remotely sensed data.
There are numerous algorithms for achieving image segmentation, including recursive algorithms. However, most of these algorithms do not employ any form of optimization in performing segmentations. The following is the classic definition of
image segmentation: Let X be a two-dimensional array representing an image. A segmentation of X can be defined as a partition of X into disjoint subsets X.sub.1, X.sub.2, . . . , X.sub.N, such that ##EQU1## 2) X.sub.i, i=1, 2, . . . , N is connected.
3) P(X.sub.i)=TRUE for i=1, 2, . . . , N and 4) P(X.sub.i.orgate.X.sub.j)=FALSE for i.noteq.j, where X.sub.i and X.sub.j are adjacent. P(X.sub.i) is a logical predicate that assigns the value TRUE or FALSE to X.sub.i, depending on the image data values
in X.sub.i.
S. W. Zucker, "Region growing: childhood and adolescence," Computer Graphics and Image Processing, Vol. 5, pp. 382-399, 1976, summarized the above definition as follows: The first condition requires that every picture element (pixel) must be in
a region. The second condition requires that each region must be connected, i.e. composed of contiguous image pixels. The third condition determines what kind of properties each region must satisfy, i.e. what properties the image pixels must satisfy to
be considered similar enough to be in the same region. The fourth condition specifies that, in the final segmentation result, any merging of any adjacent regions would violate the third condition.
A problem with this classic definition of image segmentation is that the segmentation so defined is not unique. The number, N and shape of the partitions, X.sub.i, X.sub.2, . . . , X.sub.N, depend on the order in which the image pixels are
processed. In addition, there is no concept of optimality contained in this definition of image segmentation. Under this classic definition, all partitions that satisfy the conditions represent equally good or valid segmentations of the image.
An ideal definition of image segmentation would be as follows: Let X be a two-dimensional array representing an image. A segmentation of X into N regions can be defined as a partition of X into disjoint subsets X.sub.1, X.sub.2, . . . ,
X.sub.N, such that ##EQU2## 2) X.sub.i, i=1, 2, . . . , N is connected. ##EQU3## over all partitions into N regions and 4) G(X.sub.i.orgate.X.sub.j)>G(X.sub.i)+G(X.sub.j) for i.noteq.j, where X.sub.i and X.sub.j are adjacent. G(X.sub.i) is a
function that assigns a cost to partition X.sub.i, depending on the image data values in X.sub.i.
These conditions can be summarized as follows: The first condition requires that every picture element (pixel) must be in one of N regions. The second condition requires that each region must be connected, i.e. composed of contiguous image
pixels. The third condition states that the partition must produce a minimum cost aggregated over all N regions. The fourth condition specifies that, in the final segmentation result, any merging of adjacent regions increases the minimum cost obtained
in the third condition.
As a result of these conditions, the order dependence problem is eliminated because the global minimum solution is found and this solution is the optimal solution. In practice, this ideal image segmentation is difficult, if not impossible, to
find. The third condition implies that all possible image partitions consisting of N regions must be searched to find the minimum cost. Further, the question of the proper value for N is left undetermined.
B. J. Schachter, L. S. Davis and A. Rosenfeld, "Some experiments in image segmentation by clustering of local feature vectors," Pattern Recognition, Vol. 11, No. 1, pp. 19-28, 1979, suggest that an iterative parallel region growing process be
used to eliminate the order dependence problem. R. L. Kettig and D. A. Landgrebe, "Computer classification of remotely sensed multispectral image data by extraction and classification of homogeneous objects," LARS Information Note 050975, Laboratory for
Applications of Remote Sensing, Purdue University, West Lafayette, Ind., 1975, suggest an alternative partitioning logic in which the most similar neighboring region is merged first, but found this approach too difficult to implement in a sequential
manner with the computing resources they had at that time. J. C. Tilton and S. C. Cox, "Segmentation of remotely sensed data using parallel region growing," Digest of the 1983 International Geoscience and Remote Sensing Symposium, San Francisco, Calif.,
pp. 9.1-9.6, Aug. 31-Sep. 2, 1983, propose implementing an iterative parallel approach to region growing on parallel processors in order to overcome the computational demands of this approach. In their approach, the most similar pair(s) of spatially
adjacent regions is (are) merged at each iteration. This approach solved the order dependence problem (assuming a deterministic tie-breaking method is employed), but did not fully address the optimal segmentation problem. Merging the most similar
pair(s) of spatially adjacent regions at each iteration does not guarantee that the segmentation result at a particular iteration is the optimal partition of the image data for the number of partitions obtained at that iteration. J.-M. Beaulieu and M.
Goldberg, "Hierarchy in picture segmentation: A stepwise optimization approach," IEEE Trans. on Pattern Analysis and Machine Intelligence, Vol. 11, No. 2, pp. 150-163, February 1989, provide a theoretical basis for Tilton and Cox's iterative parallel
region growing approach in their theoretical analysis of their similar Hierarchical Stepwise Optimization algorithm (HSWO). They show that the HSWO algorithm produces the globally optimal segmentation result if each iteration is statistically
independent. Even though each iteration will generally not be statistically independent for natural images, the HSWO approach is shown to still produce excellent results. Beaulieu and Goldberg also point out that the sequence of partitions generated by
this iterative approach reflect the hierarchical structure of the imagery data: the partitions obtained in the early iterations preserve the small details and objects in the image, while the partitions obtained in the latter iterations preserve only the
most important components of the image. They further note that these hierarchical partitions may carry information that may help in identifying the objects in the imagery data.
The definition of image segmentation as followed by the HSWO algorithm is defined recursively as follows: Let X be a two-dimensional array representing an image and let X.sub.i, X.sub.2, . . . , X.sub.N-1, X.sub.N be a partition of X into N
regions such that ##EQU4## 2) X.sub.i, i=1, 2, . . . , N is connected. Let G(X.sub.i) be a function that assigns a cost to partition X.sub.i, depending on the image data values in X.sub.i. Reorder the partition X.sub.i, X.sub.2, . . . , X.sub.N-1,
X.sub.N such that G(X.sub.N-1.orgate.X.sub.N).ltoreq.G(X.sub.i.orgate.X.sub.j) for all i.noteq.j where X.sub.N-1 and X.sub.N are adjacent and X.sub.i and X.sub.j, are adjacent. The segmentation of X into N-1 regions is defined as the partition X'.sub.1,
X'.sub.2. . . , X'.sub.N-1 where X'.sub.i =X.sub.i for i=1, 2, . . . , N-2 and X'.sub.N-1 =X.sub.N-1.orgate.X.sub.N.
The initial partition may assign each image pixel to a separate region, in which case the initial value of N is the number of pixels in the image (N.sub.p). Any other initial partition may be used, such as a partitioning of the image into
n.times.n blocks, where n.sup.2 <<N.sub.p, or any pre-segmentation with another algorithm.
The region growing approach utilized by the hierarchical image segmentation algorithm, HSEG, is the same as that employed by Beaulieu and Goldberg's HSWO algorithm except that HSEG may optionally alternate spectral clustering iterations with
region growing iterations to merge non-adjacent regions. Such spectral clustering adds robustness to the segmentation result and eliminates the bookkeeping overhead of separately accounting for essentially identical non-adjacent regions.
A problem with implementing segmentation algorithms based on HSWO region growing is that these algorithms are processor intensive. A large high-resolution high-bit image can take a very long time to undergo segmentation using the prior art HSWO
region growing algorithms and related technology.
An additional problem common to all recursive segmentation algorithms is the requirement of large amounts of memory, making it likely that large images may require more memory than available, preventing large images from being segmented.
SUMMARY OF THE INVENTION
Accordingly, it is an object of the present invention to implement a recursive hierarchical segmentation algorithm on a parallel-computing platform, decreasing computation time.
The foregoing object of the present invention is achieved by a method of implementing a recursive hierarchical segmentation algorithm on a parallel computing platform, including (a) setting a bottom level of recursion that defines where a
recursive division of an image into sections stops dividing; (b) setting an intermediate level of recursion where the recursive division changes from a parallel implementation into a serial implementation; and (c) implementing the segmentation algorithm
according to the set levels.
BRIEF DESCRIPTIONS OF THE DRAWINGS
These and other advantages of the invention will become apparent and more readily appreciated from the following description of the preferred embodiments, taken in conjunction with the accompanying drawings of which:
FIG. 1 is an example of a satellite image before segmentation;
FIG. 2 is an example of the satellite image in FIG. 1 after segmentation into two region sets;
FIG. 3 is an example of the satellite image in FIG. 1 after segmentation into three region sets;
FIGS. 4A, 4B, 4C, and 4D are diagrams illustrating one example of how an image can be divided into quarters and sub-quarters recursively;
FIG. 5 is a diagram illustrating an example of serial implementation;
FIG. 6 is a diagram illustrating in more detail the significance of the inb_levels parameter;
FIG. 7 is a diagram illustrating an example of processing a 512 by 512 image with fnb_levels=2, inb_levels=3, and rnb_levels=5.
DESCRIPTION OF THE PREFERRED EMBODIMENTS
Reference will now be made in detail to the present preferred embodiments of the present invention, examples of which are illustrated in the accompanying drawings, wherein like reference numerals refer to like elements throughout.
The Basic Hierarchical Segmentation (HSEG) algorithm is as follows: 1. Give each image pixel a region label and set the global criterion value, critval, equal to zero. If a pre-segmentation is provided, label each image pixel according to the
pre-segmentation. Otherwise, label each image pixel as a separate region. 2. Calculate the dissimilarity criterion value between each spatially adjacent region. 3. Find the smallest dissimilarity criterion value, and merge all pairs of spatially
adjacent regions with this criterion value. 4. Calculate the dissimilarity criterion value between all pairs of non-spatially adjacent regions. 5. Merge all pairs of non-spatially adjacent regions with dissimilarity criterion value less than or equal
to the criterion value found in operation 3. 6. If the number of regions remaining is less than the preset value chkregions, go to operation 7. Otherwise, go to operation 2. 7. Let prevcritval=critval. Calculate the current global criterion value
and set critval equal to this value. If prevcritval=zero, go to operation 2. Otherwise calculate cvratio=critval/prevcritval. If cvratio is greater than the preset threshold convfact, save the region label map from the previous iteration as a "raw"
segmentation result. Also, store the region number of pixels list, region mean vector list and region criterion value list for this previous iteration. (Note: The region criterion value is the portion of the global criterion value contributed by the
image pixels covered by the region.) If the number of regions remaining is two or less, save the region label map from the current iteration as the coarsest instance of the final hierarchical segmentation result, and stop. Otherwise, go to operation 2.
Dissimilarity Criterion: The dissimilarity criterion can be any measure of distance between two vectors. The widely used vector norms, 1-norm, 2-norm and Infinity-norm (see G. W. Stewart, Introduction to Matrix Computations, p. 164, Academic
Press: New York, N.Y., 1973), are implemented as options.
Global Criterion: The global criterion is used to identify significant changes in the segmentation results from one iteration to the next. This criterion is same as the dissimilarity criterion, except that it compares the original image data
with the region mean image from the current segmentation. The value of the global criterion is calculated by computing the dissimilarity function at each image point between the original image values and the region mean image and averaging the result
over the entire image.
The above algorithm can be implemented recursively using the Recursive Hierarchical Segmentation Algorithm (RHSEG) as follows: 1. Specify the number of levels of recursion required (rnb_levels), and pad the input image, if necessary, so that the
width and height of the image can be evenly divided by 2.sup.rnb.sup..sub.-- .sup.levels-1. (A good value for rnb_levels results in an image section at level=rnb_levels consisting of roughly 500 to 2000 pixels.) Set level=1. 2. Call
recur_hseg(level,image).
Outline of recur_hseg(level,image): A. If level<rnb_levels, divide the image data into quarters (in half in the width and height dimensions) and call recur_hseg(level+1,image/4) for each image quarter (represented as image/4). Otherwise, go
to operation C. B. After all four calls to recur_hseg( ) from operation A complete processing, reassemble the image segmentation results. C. Execute the HSEG algorithm as described in the HSEG Basic Algorithm Description above (except that the
reassembled segmentation results are used as the pre-segmentation when level<rnb_levels), but with the following modification: If level>1, terminate the algorithm when the number of regions reaches the preset value minregions, and do not check for
critval or output any "raw" segmentation results.
FIGS. 4A, 4B, 4C and 4D illustrate one example of how an image can be divided into quarters and sub-quarters recursively. FIG. 4A illustrates a starting image. FIG. 4B illustrates how an image is first divided into quarters labeled 1, 2, 3, and
4. FIG. 4C illustrates the subsequent level of recursion, where quarter 1 of FIG. 4B is divided up into sub-quarters labeled 5, 6, 7, and 8. FIG. 4D illustrates the subsequent level of recursion, where sub-quarter 5 of FIG. 4C is further divided up
into additional sub-quarters labeled 9, 10, 11, 12. Note that while we use quarters to divide the image, the image could be divided using other shapes and other dividing methods as well.
In order to implement the segmentation algorithm recursively, the parameter rnb_levels should be specified, which indicates the number of levels of recursion to be processed. If rnb_levels is set to equal 4, then the above algorithm will divide
the image as illustrated in FIG. 4A (level 1), FIG. 4B (level 2), FIG. 4C (level 3) and FIG. 4D (level 4). When the current level becomes 4, because 4 is not <rnb_levels (which is equal to 4), the recursive dividing will stop and then the lower
recursion levels will subsequently return values to the higher levels, or the recursion will "come back up."
The algorithms described above can be implemented serially, using only one processor. FIG. 5 illustrates the serial implementation of the above example. Referring now to FIG. 5, item 1 represents the first level of recursion, which then goes to
item 2 which represents the second level of recursion, which then goes to item 3 which represents the third level of recursion, which then goes to item 4 which represents the last level of recursion. The recursion "stops" at item 4, because rnb_levels
is set to equal 4 in our example.
As stated previously, the serial implementation of the above algorithm requires a large amount of computing time and resources. The implementation of the RHSEG algorithm on a parallel-processing platform is superior to the serial method with
regard to computation time and computing resources.
In the implementation of the RHSEG algorithm on a parallel computer, besides setting the above described rnb_levels (recursion levels), two other levels are specified, inb_levels (intermediate levels) and fnb_levels (final levels). It is
required that fnb_levels<=inb_levels<=rnb_levels. Quarters and subsequent sub-quarters are initially processed in parallel, but when the level of recursion reaches inb_levels the sub-quarters are then processed serially instead of in parallel.
FIG. 6 illustrates in more detail the significance of the inb_levels parameter and the parallel processes. In FIG. 6, recursion levels 1, 2, 3, 4 are illustrated. The inb_levels parameter is set to 2, and the rnb_levels parameter is set to 4.
As stated above, the rnb_levels parameter is where the recursion stops dividing the image, and returns to the higher levels using information calculated from the lower levels.
Recursion level 1 can be associated with FIG. 4A. Since recursion level 1 is less than 2 (inb_levels), the next level of recursion is performed in parallel. Thus, at recursion level 2 (inb_levels), four new processes are spawned which are
performed in parallel. Recursion level 2 can be associated with FIG. 4B. At recursion levels 3 and 4, since these are higher than 2 (inb_levels), these levels of recursion are performed serially. Thus, at these levels, no new parallel processes are
spawned. Instead, the previous process is used sequentially. Recursion level 3 can be associated with FIG. 4C, and recursion level 4 can be associated with FIG. 4D.
Thus, as illustrated in FIG. 6, there are four processes operating in parallel (five if you include the first process). Thus, the quarters labeled 1, 2, 3, and 4 in FIG. 4B are all initially processed in parallel. The sub-quarters labeled 5, 6,
7, 8 in FIG. 4C, and the sub-quarters labeled 9, 10, 11, 12 in FIG. 4D are all processed serially, using the process spawned to process section 1 of FIG. 4B. Note of course there are additional sub-quarters (and their processes), which have not been
labeled in FIG. 4C and FIG. 4D, for simplicity.
As can be seen by FIG. 6, the parallel implementation of the RHSEG algorithm can save time by first spawning parallel processes until the inb_levels of recursion is reached, and then using those parallel processes to process the further levels of
recursions serially until rnb_levels is reached. The inb_levels should be set after taking into consideration how many processes the current computing platform can simultaneously handle.
The third parameter to be specified in the parallel implementation of the RHSEG algorithm is fnb_levels. The fnb_levels parameter relates to the convergence checking (item #7 in the above Basic Hierarchical Segmentation (HSEG) algorithm). At
the fnb_levels of recursion the passing of data to higher levels is different than before (more on this in the example given below). In addition, when the current level of recursion reaches the first level, the processes at fnb_levels calculate and send
their contribution to the value of critval to level 1. The process running at level 1 computes the value of critval as the average dissimilarity value over the entire image and calculates cvratio=critval/prevcritval. If cvratio is greater than a preset
threshold, then the slave tasks running at fnb_levels to send their region label map data to the master program. More on the convergence checking and fnb_levels will be presented later on.
FIG. 7 illustrates an example of processing a 512 by 512 image with fnb_levels=2, inb_levels=3, and rnb_levels=5.
As can be seen by FIG. 7, there are five (rnb_levels) recursion levels, L1, L2, L3, L3, and L5. In this example there are also 21 processes. Process 0 at recursion level L1 spawns processes 1, 2, 3, and 4 at recursion level L2. Process 1
spawns processes 5, 6, 7, and 8, while process 2 spawns processes 9, 10, 11, and 12, while process 3 spawns processes 13, 14, 15 and 16, while process 4 spawns processes 16, 18, 29 and 20. At L3 (inb_levels), each spawned process proceeds to process the
lower levels of recursion serially. Therefore, when a new process is spawned to process another divided section of the image, this can be considered a parallel implementation. When a same process processes another divided section of the image, this can
be considered a serial implementation.
Also illustrated in FIG. 7, the image size of recursion level L1 is 512.times.512, while the image size of recursion level L2 is 256.times.256, while the image size of recursion level L3 is 128.times.128, while the image size of recursion level
L4 is 64.times.64, while the image size of recursion level L5 is 32.times.32.
Regarding convergence checking, since fnb_levels is equal to two, processes 1, 2, 3, and 4 will calculate the sum of the dissimilarity criterion over each region contained in the processing window, and send these values back to process 0
operating at recursion level L1. Process 0 computes critval as the average value of the values of dissimilarity function over the entire image from the dissimilarity function values obtained from processes 1, 2, 3 and 4 and calculates cvratio. If
cvratio is greater than a preset threshold, the region map from the previous iteration is saved as a raw segmentation result.
The designation of fnb_levels<inb_levels reduces the amount of interprocessor communications required for the convergence criterion calculations. This is important for less expensive parallel processing systems such as the Beowulf systems
constructed using relatively slow (but inexpensive) Ethernet connections to network off-the-shelf PCs together. In addition, the designation of fnb_levels>1 reduces the RAM requirements for the parallel processing system. While the optimal setting
for inb_levels varies depending upon the computing platform being used, on a 201 processor HIVE system (one master process plus 200 slave nodes), the optimum value of inb_levels is 5.
We will now walk through an example of processing a large Landsat Thematic Mapper (TM) data set to illustrate how the system works. This TM data set has 7680 columns, 6912 rows and 6 spectral bands. Based on our prior experience with these
parameters for the Hive Parallel System, we preset the values for the three levels of recursion as rnb_levels=9, inb_levels=5 and fnb_levels=3. When the master program on the parallel computing system calls the first slave task (the 0.sup.th task), it
sends to that task several task specific parameters. Included among these parameters are:
first_sec first data section to be processed by the slave task last_sec last data section to be processed by the slave task calling_tid current task ID level current level of recursion + 1 ncols number of columns in current section of data
nrows number of rows in current section of data
The first data section processed, first_sec, is the 0.sup.th section. The last data section processed is determined by the value of inb_levels through the formula:
Since in this case, since inb_levels=5, last_sec=255 (i.e., the data is processed in 256 sections at the recursive level inb_levels). The calling_tid is the task ID of the master program (the first slave task uses this to determine where to send
its results back to). The recursion level, level, is equal to 1 for the 0.sup.th task (the master program is considered to at recursion level 0). For our TM data set, ncols=7680 and nrows=6912.
Since the slave program for the 0.sup.th task is operating at a level of recursion less than inb_levels (its recursion level is "1" which is less than inb_levels=5), it sends a request to the master program for four branch slave task IDs. Upon
receiving these four branch slave task IDs, the 0.sup.th task slave program initiates the 1.sup.st, 2.sup.nd, 3.sup.rd and 4.sup.th tasks, respectively, on these four branch slave task IDs, with the task specific parameters again including first_sec,
last_sec, calling_tid, level, ncols and nrows. The values of first_sec and last_sec are determined so as to process the 1.sup.st quarter of the data sections on the 1.sup.st task, the 2.sup.nd quarter of the data sections on the 2.sup.nd task, the
3.sup.rd quarter of the data sections on the 3.sup.rd task and the 4.sup.th quarter of the data sections on the 4.sup.th task. The calling_tid is the task ID of the recursion level=1 slave task (the called slave tasks use this to determine where to send
their results back to). The recursion level, level, is equal to 2 for the 1.sup.st, 2.sup.nd, 3.sup.rd and 4.sup.th tasks. For our TM data set, ncols=3840 and nrows=3456 for the tasks at recursion level 2.
Since the slave programs operating at recursion level 2 are operating at a level of recursion less than inb_levels (=5), each of these tasks send a request to the master program for four branch slave task IDs. Upon receiving these four branch
slave task IDs, each of the slave programs at recursion level 2 initiate 4 tasks, resulting in the initiation of 16 tasks (tasks 5 through 20). Each slave task at recursion level 2 calls 4 slave tasks at recursion level 3 with task specific parameters
again including first_sec, last_sec, calling_tid, level, ncols and nrows. The values of first_sec and last_sec are determined so as to process the one-quarter of the data sections on each of the 4 tasks called. The calling_tid is the task ID of the
recursion level=2 slave task (the called slave tasks use this to determine where to send their results back to). The recursion level parameter, level, for the branch tasks is equal to 3. For our TM data set, ncols=1920 and nrows=1728 for the tasks at
recursion level 3.
Again, since the slave programs operating at recursion level 3 are operating at a level of recursion less than inb_levels (=5), each of these tasks send a request to the master program for four branch slave task IDs. Upon receiving these four
branch slave task IDs, each of the slave programs at recursion level 3 initiate 4 tasks, resulting in the initiation of 64 tasks (tasks 21 through 84). Each slave task at recursion level 3 calls 4 slave tasks at recursion level 4 with task specific
parameters again including first_sec, last_sec, calling_tid, level, ncols and nrows. The values of first sec and last_sec are determined so as to process the one-quarter of the data sections on each of the 4 tasks called. The calling_tid is the task ID
of the recursion level=3 slave task (the called slave tasks use this to determine where to send their results back to). The recursion level parameter, level, for the branch tasks is equal to 4. For our TM data set, ncols=960 and nrows=864 for the tasks
at recursion level 4.
Yet again, since the slave programs operating at recursion level 4 are operating at a level of recursion less than inb_levels (=5), each of these tasks send a request to the master program for four branch slave task IDs. Upon receiving these
four branch slave task IDs, each of the slave programs at recursion level 4 initiate 4 tasks, resulting in the initiation of 256 tasks (tasks 85 through 340). Each slave task at recursion level 4 calls 4 slave tasks at recursion level 5 with task
specific parameters again including first_sec , last_sec, calling_tid, level, ncols and nrows. The values of first_sec and last_sec are determined so as to process the one-quarter of the data sections on each of the 4 tasks called. The calling_tid is
the task ID of the recursion level=4 slave task (the called slave tasks use this to determine where to send their results back to). The recursion level parameter, level, for the branch tasks is equal to 5. For our TM data set, ncols=480 and nrows=432
for the tasks at recursion level 5.
For this example, the slave programs operating at recursion level 5 are operating at the intermediate recursion level, inb_levels (=5), each send a request to the master program for the input data for its section (section=first_sec=last_sec).
Each of these programs then call the subroutine, lrhseg, which is a sequential implementation of the recur_hseg subroutine described above (for details on lrhseg see the section of this document entitled "IMPLEMENTING A RECURSIVE HIERARCHICAL
SEGMENTATION ALGORITHM ON A COMPUTER. " At recursion level 6, lrhseg initiates the processing of the data with ncols=240 and nrows=216. At recursion level 7, lrhseg initiates the processing of the data with ncols=120 and nrows=108. At recursion level
8, lrhseg initiates the processing of the data with ncols=60 and nrows=54. Finally, at recursion level 9, lrhseg initiates the processing of the data with ncols=30 and nrows=27.
At recursion level 9, lrhseg calls the hseg subroutine, which is an implementation of the basic HSEG algorithm described above, but without convergence checking (for details on hseg see the section of this document entitled "IMPLEMENTING A
RECURSIVE HIERARCHICAL SEGMENTATION ALGORITHM ON A COMPUTER. When the number of regions reaches minregions (a preset parameter), the results are returned to the lrhseg subroutine at recursion level 8. After all four calls are made and completed to
lrhseg at recursion level 9, the lrhseg subroutine at recursion level 8 calls the hseg subroutine. After all four calls are made and completed to lrhseg at recursion level 8, the lrhseg subroutine at recursion level 7 calls the hseg subroutine. After
all four calls are made and completed to lrhseg at recursion level 7, the Irhseg subroutine at recursion level 6 calls the hseg subroutine. After all four calls are made and completed to lrhseg at recursion level 6, the lrhseg subroutine at recursion
level 5 calls the hseg subroutine.
When the slave programs operating at recursion level 5 complete their calls to the hseg subroutine, they each return their results and their input data to the slave programs that called them at recursion level 4. When the slave programs at
recursion level 4 receive the results from each of their four branch tasks, each of them then call the hseg subroutine. When the slave programs operating at recursion level 4 complete their calls to the hseg subroutine, they each return their results
and their input data to the slave programs that called them at recursion level 3.
When the slave programs at recursion level 3 receive the results from each of their four branch tasks, each of them then call the hseg subroutine. Now since these slave programs are operating at the final recursion level, fnb_levels=3, upon
completion of the call to the hseg subroutine, they do not return their input data to the slave programs that called them at the recursion level 2, and only return their segmentation results except for the region label map.
When the slave programs at recursion level 2 receive the results from each of their four branch tasks, each of them then call the hseg subroutine. Upon completion of the call to the hseg subroutine, these slave programs make a special call to
the slave programs at recursion level fnb_levels below them that updates the region label map based on the results from the hseg subroutine. Then these slave programs return their segmentations results (except for the region label map) to the slave
program that called them at recursion level 1 (in this case, the slave program running task 0).
When the slave program at recursion level 1 (this is the slave program running task 0) receives the results from each of its four branch tasks it calls the hseg subroutine, with minregions reset to the value of chkregions (see the HSEG Basic
Algorithm Description above). Upon completion of the call to the hseg subroutine, this slave program makes a special call to the slave programs at recursion level fnb_levels to update the region label map based on the results from the hseg program.
Then this slave program calls the phseg subroutine, which is an implementation of the basic HSEG algorithm with convergence.
In lhseg the region label map data are not updated (the region label map data are updated all at once after lhseg exits). However, in phseg the region label map data, which is maintained by the slave programs running the tasks at recursion level
fnb_levels, is updated after each group of region growing and spectral clustering merges (steps 2 through 5 of the basic HSEG algorithm described above). In addition, the global criterion value, critval, is calculated after each group of region growing
and spectral clustering merges from information calculated by the slave programs running the tasks at recursion level fnb_levels and accumulated by the slave program running task 0 at recursion level 1. When a convergence iteration is found, phseg sends
its results to the master program and causes the slave programs running the tasks at recursion level fnb_levels to send their region label map data to the master program.
If we had not used the above-described parallel implementation, it would not have been possible to process our example Landsat TM image on any presently available parallel computing platform. To simulate this situation, consider the case where
rnb_levels=inb_levels=fnb_levels=9 and we try to process our 7680 columns by 6912 row Landsat TM image.
In this case, the initialization portions of the descriptions for recursion levels 1 through 4 will the same as above with the following exception: last_sec would equal 65,535 (the data would be processed in 65,536 sections at the new value for
inb_levels). In addition, at recursion level 5 (the previous value of inb_levels), no request for input data would be made. Instead, a request would be made to the master program for four-branch slave task IDs. This would result in the initiation of
1024 tasks for recursion level 6. Similarly 4096 tasks would be initiated at recursion level 7, 16,384 tasks would be initiated at recursion level 8 and 65,636 tasks would be initiated at recursion level 9. This would result in a total of 87,381 slave
tasks being initiated on the on the parallel computing system. This would either not be allowed by the parallel computing system, or would totally swamp the system, probably resulting in a system failure.
Consider also the significance of setting the value of fnb_levels to a value less than inb_levels. To simulate this situation, consider the case where rnb_levels=9, inb_levels=fnb_levels=5. In this case, the phseg subroutine would have to
communicate with 256 slave tasks at recursion level 5 to update the region label map, perform convergence checking, or cause the region label map results to be sent to the master program. When fnb_levels=3 as in the original example, the phseg
subroutine only has to communicate with 16 slave tasks at recursion level 3 to perform these tasks, significantly reducing the interprocessor communication requirements of the program.
Finally, consider yet another pathological situation where fnb_levels=1. In this case the slave task 0 would have to maintain in memory the full Landsat TM data set plus the full region label map. For our example, the data volume of just these
items is about 425 megabytes. On the augmented HIVE system, if the RAM is distributed evenly among the processors, the Dell PCs have 125 megabytes RAM per processor, the Gateway PCs have 250 megabytes RAM per processor and the Pentium Pro PCs have just
under 220 megabytes RAM per processor. Thus, slave task 0 would crash due to memory constraints on any of these processing nodes if fnb_levels was set to 1 for a Landsat TM data set of this size (7680 columns by 6912 rows).
The description that follows is intended to assist one of ordinary skill in the art implement the present invention. The following description is merely one approach, and it can be appreciated by one of ordinary skill in the art that numerous
other approaches are possible as well. The below materials assume familiarity with the "C" programming language, and with programming parallel computers using "PVM" software.
While the implementation described here is the implementation for the HIVE, this implementation has also been applied, with minor modifications, to other MIMD parallel computers including the Cray T3E and IBM NetFinity computers. Based on this
description, individuals should also be able to implement this approach using other programming languages and/or other system software for parallel computers on other parallel computers.
The recursive hierarchical image segmentation algorithm, RHSEG, is implemented in three distinct parts: i. a generic interface program that sets up a remote call to a parallel comp | | |
