Determining maximally stable external regions using a parallel processor

• US 9,626,576 B2
• Filed: 03/14/2014
• Issued: 04/18/2017
• Est. Priority Date: 03/15/2013
• Status: Expired due to Fees

• Current Assignee: Cubic Corporation
• Original Assignee: MotionDSP, Inc. (Cubic Corporation)
• Inventors: Mihajlovic, Igor, Grujic, Nemanja
• Primary Examiner(s): Dunphy, David F
• Application Number:
  US14/214,034
• Publication Number:
  US 20140286579A1
• Time in Patent Office: 1,131 Days
• CPC Class Codes: G06T 2207/20152 Watershed segmentation
• CPC Class Codes: G06T 7/11 Region-based segmentation
• CPC Class Codes: G06T 7/155 involving morphological operators
• CPC Class Codes: G06T 7/187 involving region growing; involving region merging; involving connected component labelling
• CPC Class Codes: G06V 10/34 Smoothing or thinning of the pattern; Morphological operations; Skeletonisation
• CPC Class Codes: G06V 10/955 using specific electronic processors

Abstract

Embodiments of the present invention includes a method of determining MSER on a processing system that includes a parallel processor such as a GPU, the method including method steps carried out in parallel. Embodiments of the present invention also include an apparatus that includes a parallel processor and that is operative to carry out the method, and also logic, e.g., executable instructions configured on a non-transitory computer-readable media operative to carry out the method, and a non-transitory computer-readable medium encoded with such instructions. The method includes assigning to the pixels in an image metapixels of all connected pixels at a level, carrying out watershed in parallel on metapixels to determine catchment basins, and carrying out further steps, including steps executed in parallel to determine the MSER of the image.

Claims

1. A method of operating a processing system that includes one or more parallel processors to determine MSERs of an input image, the method comprising:

accepting an input image into the processing system;

forming metapixels from the input image by labeling each respective connected region in the input image consisting of all connected pixels having the same respective intensity level as a respective metapixel;

connecting all metapixels of the input image to their corresponding local minima to determining a catchment basin for each metapixel, including carrying out a first set of operations executed in parallel on at least one of the one or more parallel processors;

identifying which of the catchment basins are connected, and connecting the catchment basins to form an MSER data structure, including carrying out a second set of operations executed in parallel on at least one of the one or more parallel processors;

determining the area of each region at each level of the MSER data structure, calculating a measure of stability and any local minimum in the calculated stability, wherein a local minimum indicates detection of an MSER,

wherein the forming of the megapixels uses a parallel method for connected component labeling using at least one of the parallel processors, and/or wherein the connecting of the metapixels includes using at least one of the parallel processors to carry out watershed operations in parallel on the metapixels to determine the catchment basins,

such that the detected MSERs of the accepted image are available to one or more computer vision tasks.

2. A method as recited in claim 1, wherein the determining of the catchment basins comprises carrying out watershed operations using topographic distance on metapixels, the watershed operations including operations in parallel on at least one of the one or more parallel processors.

3. A method as recited in claim 2, wherein the forming of the MSER data structure comprises building a watershed graph to identify which catchment basins are connected, wherein each catchment basin is a node in the watershed graph, and edges are ridge levels where two catchment basins are connected.

4. A method as recited in claim 2, wherein the forming of the MSER data structure comprises building a watershed graph to identify which catchment basins are connected, wherein each catchment basin is a node in the watershed graph, and edges are ridge levels where two catchment basins are connected, and further comprises converting the watershed graph into the MSER data structure in the form of an MSER tree, including connecting the catchment basins into the MSER tree according to level at which catchment basins are merged.

5. A method as recited in claim 1, wherein at least one of the one or more parallel processors is a GPU that has a plurality of cores that can carry out operations in parallel, and wherein the first and second sets of operations are executed in parallel on the GPU.

6. A method as recited in claim 1, wherein at least one of the one or more parallel processors is a GPU that has a plurality of cores that operate in parallel, and the processing system includes a processing subsystem that includes one or more host processing elements, wherein the combination of the GPU and the processing subsystem are programmable using a set of programming models and related programming tools.

7. A method as recited in claim 6, wherein the set of programming models and related programming tools comprises a proprietary programming model and related proprietary programming tools.

8. A method as recited in claim 6, wherein the set of programming models and related programming tools conform to the Open Computing Language royalty-free standard.

21. A method as recited in claim 1, wherein the forming of megapixels includes carrying out a parallel method for connected component labeling using at least one of the parallel processors.

9. A processing system apparatus configured to determine MSER of an image, the apparatus comprising:

one or more parallel processors each comprising a plurality of parallel processing elements that can operate in parallel;

a processing subsystem operatively coupled to the one or more parallel processors, and comprising one or more host processor elements, and,

one or more storage elements, including at least one device memory coupled to the parallel processors, and at least one host memory coupled to the host processing subsystem,

wherein the one or more storage elements comprises instructions that when executed by the combination of at least one of the parallel processors and at least one of the one or more host processor elements, cause the processing system to carry out a method of determining MSERs of an image, the method comprising;

accepting an input image into the processing system apparatus;

forming metapixels from the input image by labeling each respective connected region in the input image consisting of all connected pixels having the same respective intensity level as a respective metapixel;

connecting all metapixels of the input image to their corresponding local minima to determining a catchment basin for each metapixel, including carrying out including carrying out a first set of operations executed in parallel on at least one of the one or more parallel processors;

identifying which of the catchment basins are connected, and connecting the catchment basins to form an MSER data structure, including carrying out a second set of operations executed in parallel on at least one of the one or more parallel processors;

determining the area of each region at each level of the MSER data structure, calculating a measure of stability and any local minimum in the calculated stability, wherein a local minimum indicates detection of an MSER,

wherein the forming of the megapixels uses a parallel method for connected component labeling using at least one of the parallel processors, and/or wherein the connecting of the metapixels includes using at least one of the parallel processors to carry out watershed operations in parallel on the metapixels to determine the catchment basins,

such that the detected MSERs of the accepted image are available to one or more computer vision tasks.

10. A processing system apparatus as recited in claim 9, wherein the determining of the catchment basins comprises carrying out watershed operations using topographic distance on metapixels, the watershed operations including operations in parallel on at least one of the one or more parallel processors.

11. A processing system apparatus as recited in claim 10, wherein the forming of the MSER data structure comprises building a watershed graph to identify which catchment basins are connected, wherein each catchment basin is a node in the watershed graph, and edges are ridge levels where two catchment basins are connected.

12. A processing system apparatus as recited in claim 10, wherein the forming of the MSER data structure comprises building a watershed graph to identify which catchment basins are connected, wherein each catchment basin is a node in the watershed graph, and edges are ridge levels where two catchment basins are connected, and further comprises converting the watershed graph into the MSER data structure in the form of an MSER tree, including connecting the catchment basins into the MSER tree according to level at which catchment basins are merged.

14. A processing system apparatus as recited in claim 9, wherein at least one of the one or more parallel processors is a GPU that has a plurality of cores that operate in parallel, and the processing system includes a processing subsystem that includes one or more host processing elements, wherein the combination of the GPU and the processing subsystem are programmable using a set of programming models and related programming tools.

13. A processing system apparatus as recited in 9, wherein at least one of the one or more parallel processors is a GPU that has a plurality of cores that can carry out operations in parallel, and wherein the first and second sets of operations are executed in parallel on the GPU.

15. A non-transitory computer-readable storage medium encoded with instructions that when executed in a processing system that includes at least one parallel processor and may include a host processing subsystem, cause the processing system to carry out a method of determining MSER of an image, the method comprising:

accepting an input image into the processing system;

forming metapixels from the input image by labeling each respective connected region in the input image consisting of all connected pixels having the same respective intensity level as a respective metapixel;

connecting all metapixels of the input image to their corresponding local minima to determining a catchment basin for each metapixel, including carrying out including carrying out a first set of operations executed in parallel on at least one of the one or more parallel processors;

identifying which of the catchment basins are connected, and connecting the catchment basins to form an MSER data structure, including carrying out a second set of operations executed in parallel on at least one of the one or more parallel processors;

determining the area of each region at each level of the MSER data structure, calculating a measure of stability and any local minimum in the calculated stability, wherein a local minimum indicates detection of an MSER,

wherein the forming of the megapixels uses a parallel method for connected component labeling using at least one of the parallel processors, and/or wherein the connecting of the metapixels includes using at least one of the parallel processors to carry out watershed operations in parallel on the metapixels to determine the catchment basins,

such that the detected MSERs of the accepted image are available to one or more computer vision tasks.

16. A non-transitory computer-readable storage medium as recited in claim 15, wherein the determining of the catchment basins comprises carrying out watershed operations using topographic distance on metapixels, the watershed operations including operations in parallel on at least one of the one or more parallel processors.

17. A non-transitory computer-readable storage medium as recited in claim 16, wherein the forming of the MSER data structure comprises building a watershed graph to identify which catchment basins are connected, wherein each catchment basin is a node in the watershed graph, and edges are ridge levels where two catchment basins are connected.

18. A non-transitory computer-readable storage medium as recited in claim 16, wherein the forming of the MSER data structure comprises building a watershed graph to identify which catchment basins are connected, wherein each catchment basin is a node in the watershed graph, and edges are ridge levels where two catchment basins are connected, and further comprises converting the watershed graph into the MSER data structure in the form of an MSER tree, including connecting the catchment basins into the MSER tree according to level at which catchment basins are merged.

19. A non-transitory computer-readable storage medium as recited in claim 15, wherein at least one of the one or more parallel processors is a GPU that has a plurality of cores that can carry out operations in parallel, and wherein the first and second sets of operations are executed in parallel on the GPU.

20. A non-transitory computer-readable storage medium as recited in claim 15, wherein at least one of the one or more parallel processors is a GPU that has a plurality of cores that operate in parallel, and the processing system includes a processing subsystem that includes one or more host processing elements, wherein the combination of the GPU and the processing subsystem are programmable using a set of programming models and related programming tools.