Boundary identification and characterization through density differencing

• US 6,697,497 B1
• Filed: 12/06/1999
• Issued: 02/24/2004
• Est. Priority Date: 12/22/1998
• Status: Expired due to Term

• Current Assignee: RPX Corporation
• Original Assignee: Novell Incorporated (Open Text Corporation)
• Inventors: Carter, Stephen R., Reed, Edwards E., Jensen, Del
• Primary Examiner(s): Patel, Jayanti K.
• Assistant Examiner(s): CARTER, AARON W
• Application Number:
  US09/455,572
• Time in Patent Office: 1,541 Days
• Field of Search: 382/195, 382/199, 382/205, 382/100, 382/130, 382/225, 382/228, 382/170, 382/266, 382/269
• US Class Current: 382/100
• CPC Class Codes: G06T 7/12 Edge-based segmentation
• CPC Class Codes: G06T 7/143 involving probabilistic approaches, e.g. Markov random field [MRF] modelling

Abstract

Methods and systems are provided for identifying and characterizing boundaries in digital images and other digital data sets. At least two points within a digital image are selected. Clusters of sample points around the points are chosen. A pixel value histogram is generated for each sample point cluster. These histograms define frequency functions. The distance between the frequency functions, called a “density distance” is calculated and analyzed. The nature of the density distance is then used to determine if the two areas are relatively uniform, or if they indicate a presence of a boundary. To further refine the procedure, the method may be applied iteratively by modifying cluster variances, sizes, and distributions, and then reanalyzing the frequency functions generated.

Claims

1. A computer-implemented method for boundary analysis in a digital data set, the method comprising the steps of:

associating a first JRC function with a first point in the digital data set;

associating a second JRC function with a second point in the digital data set;

calculating a distance between the two JRC functions; and

using the distance to perform boundary analysis on at least a portion of the digital data set.

2. The method of claim 1, wherein the first associating step comprises choosing a cluster of sample points distributed around the first point, and the second associating step comprises choosing a cluster of sample points distributed around the second point, and each cluster contains the same number of sample points distributed according to the same distribution function and the same variance.

3. The method of claim 1, wherein the first associating step comprises choosing a cluster of sample points distributed around the first point, and the second associating step comprises choosing a cluster of sample points distributed around the second point, and the clusters differ from one another in at least one of the number of sample points in the cluster, the distribution which distributes the sample points, and the variance of the distribution of sample points.

4. The method of claim 1, wherein each JRC function is a frequency function.

5. The method of claim 1, wherein the calculating step calculates distance according to a standard Lebesgue measure.

6. The method of claim 5, wherein the using step associates a positive or negative sign with distance by associating a positive sign with a distance when the statistical variance (sigma squared) is increasing and by associating a negative sign with the distance when the statistical variance is decreasing.

7. The method of claim 1, wherein the step of using the distance to perform boundary analysis comprises obtaining and analyzing frequency derivatives.

8. The method of claim 1, wherein the step of using the distance to perform boundary analysis comprises obtaining and analyzing frequency gradients.

9. The method of claim 1, wherein the digital data set includes pixels, each associating step utilizes a division of the range of possible pixel values into intervals, and at least one of the intervals covers more than one possible pixel value.

10. The method of claim 1, wherein the first point and the second point have spatial coordinates which are separated by an adjustable increment.

11. The method of claim 1, wherein the associating steps and the calculating step are repeated a plurality of times with additional points before the resulting distances are used to perform boundary analysis.

12. The method of claim 1, wherein the associating steps and the calculating step are repeated a plurality of times on the same points with different cluster size, cluster distribution, and/or cluster variances, and the results are correlated during the using step.

13. A boundary analysis computer system comprising:

a digital data set memory capable of holding at least a portion of a digital data set;

at least one processing unit configured to associate a first JRC function with a first point in the digital data set, associate a second JRC function with a second point in the digital data set, and calculate a distance between the two JRC functions; and

an output device configured to transmit an output signal from the processing unit.

14. The system of claim 13, wherein the processing unit comprises a microprocessor and a program memory containing executable instructions, and execution of the instructions calculates a frequency derivative.

15. The system of claim 13, wherein the memory holds a digital data set representing a medical image.

16. The system of claim 13, wherein the memory holds a digital data set representing a high-altitude or satellite image.

17. The system of claim 13, wherein the memory holds a digital data set representing a sonar image.

18. The system of claim 13, wherein the memory holds a digital data set representing a radar image.

19. The system of claim 13, wherein the memory holds a digital data set representing a retouched image.

20. The system of claim 19, wherein the retouched image includes an air brushed portion.

21. The system of claim 19, wherein the retouched image includes a pasted portion.

22. The system of claim 19, wherein the retouched image includes a watermark portion.

23. The system of claim 19, wherein the retouched image includes a steganographically hidden message, and the system identifies patterns of superimposed apparent noise.

24. The system of claim 13, wherein the memory holds a digital data set representing a weather system image.

25. A computer storage medium having a configuration that represents data and instructions which will cause performance of method steps for boundary analysis, the method comprising the steps of:

associating a first frequency function with a first point in the digital data set;

associating a second frequency function with a second point in the digital data set;

calculating a distance between the two frequency functions; and

using the distance to perform boundary analysis on at least a portion of the digital data set.

26. The configured storage medium of claim 25, wherein the first associating step comprises choosing a cluster of sample points distributed around the first point, and the second associating step comprises choosing a cluster of sample points distributed around the second point, and each cluster contains the same number of sample points distributed according to the same distribution function and the same variance.

27. The configured storage medium of claim 25, wherein the first associating step comprises choosing a cluster of sample points distributed around the first point, and the second associating step comprises choosing a cluster of sample points distributed around the second point, and the clusters differ from one another in at least one of the number of sample points in the cluster, the distribution which distributes the sample points, and the variance of the distribution of sample points.

28. The configured storage medium of claim 25, wherein the associating steps and the calculating step are repeated a plurality of times with additional points before the resulting distances are used to perform boundary analysis.

29. The configured storage medium of claim 25, where in the associating steps and the calculating step are repeated a plurality of times on the same points with different cluster size, cluster distribution, and/or cluster variances, and the results are correlated during the using step.

30. An edge detection data signal embodied in a computer readable medium, the signal comprising at least one pair of points from a digital data set, and a distance between at least one pair of JRC functions, each of the JRC functions associated with one of the points from the digital data set.

31. The signal of claim 30, further comprising at least one pair of sample point clusters corresponding to the at least one pair of points.

32. The signal of claim 30, further comprising the digital data set from which the at least one pair of points was obtained.

33. The signal of claim 32, wherein the digital data set comprises pixels.

34. The signal of claim 30, further comprising the at least one pair of JRC functions.