Segmentation-based image processing system

• US 8,260,048 B2
• Filed: 11/14/2007
• Issued: 09/04/2012
• Est. Priority Date: 11/14/2007
• Status: Active Grant

• Current Assignee: NV5 Geospatial Solutions Incorporated (L3Harris Technologies, Inc.)
• Original Assignee: Exelis Incorporated (L3Harris Technologies, Inc.)
• Inventors: Jin, Xiaoying
• Primary Examiner(s): Krasnic, Bernard
• Application Number:
  US11/984,222
• Publication Number:
  US 20090123070A1
• Time in Patent Office: 1,756 Days
• Field of Search: 382/128, 382/173, 382/190, 382/276
• US Class Current: 382/173
• CPC Class Codes: G06T 2207/20152 Watershed segmentation
• CPC Class Codes: G06T 7/11 Region-based segmentation
• CPC Class Codes: G06T 7/13 Edge detection
• CPC Class Codes: G06T 7/136 involving thresholding
• CPC Class Codes: G06T 7/155 involving morphological operators
• CPC Class Codes: G06T 7/174 involving the use of two or more images

Abstract

A digital image can be processed by an image processing method that calculates a gradient map for the digital image, calculates a density function for the gradient map, calculates a modified gradient map using the gradient map, the density function and the selected scale level, and segments the modified gradient map. Prior to segmenting the modified gradient map, a sub-image of the digital image can be segmented at the selected scale level to determine if the selected scale level will give the desired segmentation.

Claims

1. A computer-implemented method of processing a digital image at a selected scale level, the method comprising:

calculating a gradient map for a portion of the digital image greater than a size of a first preview area and including the first preview area;

calculating a cumulative relative histogram for the gradient map for the portion of the digital image greater than the size of the first preview area and including the first preview area;

selecting a location of the first preview area within the portion of the digital image greater than the size of the first preview area and including the first preview area;

receiving a selected scale level to be used for an initial segmentation of the first preview area;

(a) calculating a modified gradient map for the first preview area using the gradient map, the cumulative relative histogram and the selected scale level by determining from the cumulative relative histogram a threshold gradient value corresponding to the selected scale level and setting gradient values in the gradient map that are below the threshold gradient value to a minimum threshold;

(b) segmenting the modified gradient map for the first preview area to create a first segmented preview image;

(c) displaying the first segmented preview image;

(d) receiving an indication of whether the first segmented preview image is acceptable;

(e) receiving a new selected scale level and repeating steps (a)-(d) using the new selected scale level as the selected scale level until the indication received in step (d) indicates that the first segmented preview image is acceptable; and

(f) segmenting the portion of the digital image greater than the size of the first preview area and including the first preview area using the selected scale level used when the indication in step (d) indicates that the first segmented preview image is acceptable.

2. The method as claimed in claim 1, wherein segmenting the modified gradient map for the first preview area comprises performing a watershed transformation.

3. The method as claimed in claim 1, wherein the minimum threshold is the threshold gradient value.

4. The method as claimed in claim 1, wherein calculating a gradient map for the portion of the digital image greater than the size of the first preview area and including the first preview area comprises combining gradient data from multiple bands of multi-band data.

5. The method as claimed in claim 4, wherein combining gradient data from multiple bands of multi-band data comprises combining the gradient values of multiple bands using a SUM function.

6. The method as claimed in claim 4, wherein combining gradient data from multiple bands of multi-band data comprises combining the gradient values of multiple bands using a MAX function.

7. The method as claimed in claim 1, wherein calculating a gradient map for the portion of the digital image greater than the size of the first preview area and including the first preview area comprises applying a linear or a non-linear transform to multiple bands of multi-band data, selecting plural bands of the transformed bands and combining the gradient data on the selected plural bands.

8. The method as claimed in claim 7, wherein the linear transform comprises Principal Component Analysis.

9. The method as claimed in claim 7, wherein the selected plural bands are selected such that at least 90% to 95% of variance data is contained within the selected plural bands that are to be applied to further gradient computation.

10. The method as claimed in claim 1, wherein calculating a gradient map for the portion of the digital image greater than the size of the first preview area and including the first preview area comprises normalizing data from multiple bands of multi-band data before gradient computation and combining the normalized gradient data.

11. The method as claimed in claim 1, wherein calculating a gradient map for the portion of the digital image greater than the size of the first preview area and including the first preview area comprises filtering the digital image before calculating the gradient map.

12. The method as claimed in claim 11, wherein the filtering comprises filtering using an edge-preserving filter.

13. The method as claimed in claim 1, wherein the portion of the digital image used to calculate the gradient map and the cumulative relative histogram is greater than a size of the first preview area and a second preview area and including the first and second preview areas, and wherein the step (f) of segmenting further comprises:

(g) calculating a modified gradient map for the second preview area using the gradient map, the cumulative relative histogram and the selected scale level by setting gradient values in the gradient map that are below the threshold gradient value to the minimum threshold;

(h) segmenting the modified gradient map for the second preview area to create a second segmented preview image;

(i) displaying the second segmented preview image;

(j) receiving an indication of whether the second segmented preview image is acceptable;

(k) receiving a new selected scale level and repeating steps (a)-(j) using the new selected scale level as the selected scale level until the indications received in steps (d) and (j) indicate that the first and second segmented preview images are acceptable; and

(l) segmenting the portion of the digital image greater than the size of the first and second preview areas and including the first and second preview areas using the selected scale level used when the indications in steps (d) and (j) indicate that the first and second segmented preview images are acceptable.

14. The method as claimed in claim 1, wherein the portion of the digital image greater than the size of the first preview area and including the first preview area comprises the whole digital image.

15. A computer-implemented method of processing a digital image at a selected scale level comprising:

calculating a gradient map for the digital image;

calculating a density function for the gradient map;

calculating a modified gradient map using the gradient map, the density function and the selected scale level; and

segmenting the modified gradient map, wherein segmenting the modified gradient map comprises;

selecting a first sub-portion of the modified gradient map;

segmenting the first sub-portion of the modified gradient map;

selecting a second sub-portion of the modified gradient map different from the first sub-portion; and

segmenting the second sub-portion of the modified gradient map using the selected scale level used to segment the first sub-portion of the modified gradient map.

16. The method as claimed in claim 15, wherein segmenting the modified gradient map for the first and second sub-portions comprises performing watershed transformations on the first and second sub-portions.

17. A computer system for processing a digital image at a selected scale level, the system comprising:

a processor; and

a memory, wherein the memory comprises computer code stored therein for causing the processor to perform the steps of;

calculating a gradient map for a portion of the digital image greater than a size of a first preview area and including the first preview area;

calculating a cumulative relative histogram for the gradient map for the portion of the digital image greater than the size of the first preview area and including the first preview area;

selecting a location of the first preview area within the portion of the digital image greater than the size of the first preview area and including the first preview area;

receiving a selected scale level to be used for an initial segmentation of the first preview area;

(a) calculating a modified gradient map for the first preview area using the gradient map, the cumulative relative histogram and the selected scale level by determining from the cumulative relative histogram a threshold gradient value corresponding to the selected scale level and setting gradient values in the gradient map that are below the threshold gradient value to a minimum threshold;

(b) segmenting the modified gradient map for the first preview area to create a first segmented preview image;

(c) displaying the first segmented preview image;

(d) receiving an indication of whether the first segmented preview image is acceptable;

(e) receiving a new selected scale level and repeating steps (a)-(d) using the new selected scale level as the selected scale level until the indication received in step (d) indicates that the first segmented preview image is acceptable; and

(f) segmenting the portion of the digital image greater than the size of the first preview area and including the first preview area using the selected scale level used when the indication in step (d) indicates that the first segmented preview image is acceptable.

18. The computer system as claimed in claim 17, wherein

segmenting the modified gradient map for the first preview area comprises performing a watershed transformation.

19. The computer system as claimed in claim 17, wherein the portion of the digital image used to calculate the gradient map and the cumulative relative histogram is greater than a size of the first preview area and a second preview area and including the first and second preview areas, and wherein the step (f) of segmenting further comprises:

(g) calculating a modified gradient map for the second preview area using the gradient map, the cumulative relative histogram and the selected scale level by setting gradient values in the gradient map that are below the threshold gradient value to the minimum threshold;

(h) segmenting the modified gradient map for the second preview area to create a second segmented preview image;

(i) displaying the second segmented preview image;

(j) receiving an indication of whether the second segmented preview image is acceptable;

(k) receiving a new selected scale level and repeating steps (a)-(j) using the new selected scale level as the selected scale level until the indications received in steps (d) and (j) indicate that the first and second segmented preview images are acceptable; and

(l) segmenting the portion of the digital image greater than the size of the first and second preview areas and including the first and second preview areas using the selected scale level used when the indications in steps (d) and (j) indicate that the first and second segmented preview images are acceptable.

20. The computer system as claimed in claim 17, wherein the portion of the digital image greater than the size of the first preview area and including the first preview area comprises the whole digital image.

21. The computer system as claimed in claim 17, wherein calculating a gradient map for the portion of the digital image greater than the size of the first preview area and including the first preview area comprises combining gradient data from multiple bands of multi-band data.

22. A computer program product comprising:

a computer readable non-transitory medium; and

computer code embedded in the computer readable non-transitory medium for causing a processor reading the computer code embedded in the computer readable non-transitory medium to perform the steps of;

calculating a gradient map for a portion of a digital image greater than a size of a first preview area and including the first preview area;

calculating a cumulative relative histogram for the gradient map for the portion of the digital image greater than the size of the first preview area and including the first preview area;

selecting a location of the first preview area within the portion of the digital image greater than the size of the first preview area and including the first preview area;

receiving a selected scale level to be used for an initial segmentation of the first preview area;

(a) calculating a modified gradient map for the first preview area using the gradient map, the cumulative relative histogram and the selected scale level by determining from the cumulative relative histogram a threshold gradient value corresponding to the selected scale level and setting gradient values in the gradient map that are below the threshold gradient value to a minimum threshold;

(b) segmenting the modified gradient map for the first preview area to create a first segmented preview image;

(c) displaying the first segmented preview image;

(d) receiving an indication of whether the first segmented preview image is acceptable;

(e) receiving a new selected scale level and repeating steps (a)-(d) using the new selected scale level as the selected scale level until the indication received in step (d) indicates that the first segmented preview image is acceptable; and

(f) segmenting the portion of the digital image greater than the size of the first preview area and including the first preview area using the selected scale level used when the indication in step (d) indicates that the first segmented preview image is acceptable.

23. The computer program product as claimed in claim 22, wherein

segmenting the modified gradient map for the first preview area comprises performing a watershed transformation.

24. The computer program product as claimed in claim 22, wherein the portion of the digital image greater than the size of the first preview area and including the first preview area comprises the whole digital image.

25. The computer program product as claimed in claim 22, wherein the portion of the digital image used to calculate the gradient map and the cumulative relative histogram is greater than a size of the first preview area and a second preview area and including the first and second preview areas, and wherein the step (f) of segmenting further comprises:

(g) calculating a modified gradient map for the second preview area using the gradient map, the cumulative relative histogram and the selected scale level by setting gradient values in the gradient map that are below the threshold gradient value to the minimum threshold;

(h) segmenting the modified gradient map for the second preview area to create a second segmented preview image;

(i) displaying the second segmented preview image;

(j) receiving an indication of whether the second segmented preview image is acceptable;

(k) receiving a new selected scale level and repeating steps (a)-(j) using the new selected scale level as the selected scale level until the indications received in steps (d) and (j) indicate that the first and second segmented preview images are acceptable; and

(l) segmenting the portion of the digital image greater than the size of the first and second preview areas and including the first and second preview areas using the selected scale level used when the indications in steps (d) and (j) indicate that the first and second segmented preview images are acceptable.

26. The computer program product as claimed in claim 22, wherein calculating a gradient map for the portion of the digital image greater than the size of the first preview area and including the first preview area comprises combining gradient data from multiple bands of multi-band data.