Method for implementation of recursive hierarchical segmentation on parallel computers
View Patent ↗A method, computer readable storage, and apparatus for implementing a recursive hierarchical segmentation algorithm on a parallel computing platform. The method includes setting a bottom level of recursion that defines where a recursive division of an image into sections stops dividing, and setting an intermediate level of recursion where the recursive division changes from a parallel implementation into a serial implementation. The segmentation algorithm is implemented according to the set levels. The method can also include setting a convergence check level of recursion with which the first level of recursion communicates with when performing a convergence check.
1. A method of implementing a recursive hierarchical segmentation algorithm on a parallel computing platform, comprising:
setting a bottom level of recursion that defines where a recursive division of an image into sections stops dividing;
setting an intermediate level of recursion where the recursive division changes from a parallel implementation into a serial implementation; and
implementing the segmentation algorithm according to the set bottom level and the set intermediate level.
2. A method as recited in claim 1 , further comprising setting a convergence check level of recursion, wherein after the recursive division is complete, a convergence check is performed which communicates data between processes running at the convergence check level and a top level.
3. A method as recited in claim 2 , wherein when the convergence check results in a favorable result, the convergence check level processes send their region label map data to a master program.
4. A method of implementing a recursive hierarchical segmentation algorithm on a parallel computer, comprising:
dividing an image from a first level of recursion to a bottom level of recursion, by:
when a current level of recursion is less than a preset intermediate level, recursively dividing an image into sections and spawning a new parallel process for each of the divided sections;
when a bottom level of recursion is greater than the current level of recursion which is greater than or equal to the preset intermediate level, recursively dividing the image into sections serially; and
implementing the segmentation algorithm using the divided sections and each section's respective process.
5. A method as recited in claim 4 , further comprising performing a convergence check when the current level of recursion equals the first level, and communicating between a preset convergence check level of recursion and the first level in performing the convergence check.
6. A method as recited in claim 5 , wherein the convergence check farther comprises communicating dissimilarity criterion values (critvals) from each process at the convergence check level of recursion to a process at the first level of recursion.
7. A method as recited in claim 6 , wherein the convergence check further comprises using the process at the first level of recursion, receiving the communicated critvals, summing the received critvals, and calculating a ratio of the summed critvals and the previously summed critvals.
8. A method as recited in claim 7 , wherein if the calculated ratio is higher than a preset threshold then the image data from the convergence check level processes are saved by a master program.
9. A method of implementing a recursive hierarchical segmentation algorithm on a parallel computer, comprising:
recursively dividing an image into sections from a top level of recursion to an intermediate level of recursion using parallel processes;
recursively dividing the image into sections from the intermediate level of recursion to a bottom level of recursion using serial processing; and
implementing the segmentation algorithm from the bottom level of recursion to the top level of recursion for each divided section using the section's respective process.
10. A method as recited in claim 9 , further comprising:
performing a convergence check when a current level of recursion reaches the first level, and communicating between a preset convergence check level of recursion and the first level in performing the convergence check.
11. A method as recited in claim 10 , further comprising:
sending, by processes running at the convergence check level, region label map data to a master program if the convergence check results in a favorable result.
12. A computer readable storage medium, storing a method of implementing a recursive hierarchical segmentation algorithm on a parallel computing platform, the computer readable storage medium instructing a computer to perform:
setting a bottom level of recursion that defines where a recursive division of an image into sections stops dividing;
setting an intermediate level of recursion where the recursive division changes from a parallel implementation into a serial implementation; and
implementing the segmentation algorithm according to the set bottom level and the set intermediate level.
13. A computer readable storage medium as recited in claim 12 , further comprising setting a convergence check level of recursion, wherein after the recursive division is complete, a convergence check is performed which communicates data between processes running at the convergence check level and a top level.
14. A computer readable storage medium as recited in claim 13 , wherein when the convergence check results in a favorable result, the convergence check level processes send their region label map data to a master program.
15. A computer readable storage medium, storing a method of implementing a recursive hierarchical segmentation algorithm on a parallel computing platform, the computer readable storage medium instructing a computer to perform:
dividing an image from a first level of recursion to a bottom level of recursion, by:
when a current level of recursion is less than a preset intermediate level, recursively dividing an image into sections and spawning a new parallel process for each of the divided sections;
when a bottom level of recursion is greater than the current level of recursion which is greater than or equal to the preset intermediate level, recursively dividing the image into sections serially; and
implementing the segmentation algorithm using the divided sections and each section's respective process.
16. A computer readable storage medium as recited in claim 15 , further comprising performing a convergence check when the current level of recursion equals the first level, and communicating between a preset convergence check level of recursion and the first level in performing the convergence check.
17. A computer readable storage medium as recited in claim 16 , wherein the convergence check further comprises communicating dissimilarity criterion values (critvals) from each process at the convergence check level of recursion to a process at the first level of recursion.
18. A computer readable storage medium as recited in claim 17 , wherein the convergence check further comprises using the process at the first level of recursion, receiving the communicated critvals, summing the received critvals, and calculating a ratio of the summed critvals and the previously summed critvals.
19. A computer readable storage medium as recited in claim 18 , wherein if the calculated ratio is higher than a preset threshold then the image data from the convergence check level processes are saved by a master program.
20. A computer readable storage medium, storing a method of implementing a recursive hierarchical segmentation algorithm on a parallel computing platform, the computer readable storage medium instructing a computer to perform:
recursively dividing an image into sections from a top level of recursion to an intermediate level of recursion using parallel processes;
recursively dividing the image into sections from the intermediate level of recursion to a bottom level of recursion using serial processing; and
implementing the segmentation algorithm from the bottom level of recursion to the top level of recursion for each divided section using the section's respective process.
21. A computer readable storage medium as recited in claim 20 , further comprising:
performing a convergence check when a current level of recursion reaches the first level, and communicating between a preset convergence check level of recursion and the first level in performing the convergence check.
22. A computer readable storage medium as recited in claim 21 , further comprising:
sending, by processes running at the convergence check level, region label map data to a master program if the convergence check results in a favorable result.
23. An apparatus comprising:
an input unit, inputting a bottom level of recursion that defines where a recursive division of an image into sections stops dividing, and an intermediate level of recursion where the recursive division changes from a parallel implementation into a serial implementation;
a processing unit, implementing a recursive hierarchical segmentation algorithm using the levels input from the input unit.
24. An apparatus as recited in claim 23 , wherein the input unit further comprises inputting a convergence check level of recursion, wherein after the recursive division is complete, a convergence check is performed which communicates data between processes running at the convergence check level and a top level.