High order fractal feature extraction for classification of objects in images

• US 5,787,201 A
• Filed: 04/09/1996
• Issued: 07/28/1998
• Est. Priority Date: 04/09/1996
• Status: Expired due to Fees

• Current Assignee: The United States of America As Represented By The Secretary of Agriculture
• Original Assignee: the united states of america as represented by the secretary of the navy
• Inventors: Nelson, Susan R., Tuovila, Susan M.
• Primary Examiner(s): CHANG, JON CARLTON
• Assistant Examiner(s): Nguyen, Ha Tran
• Application Number:
  US08/629,709
• Time in Patent Office: 840 Days
• Field of Search: 382/224, 382/270, 382/249, 382/108, 382/109
• US Class Current: 382/224
• CPC Class Codes: G06V 10/255 Detecting or recognising potential candidate objects based on visual cues, e.g. shapes
• CPC Class Codes: G06V 10/42 Global feature extraction by analysis of the whole pattern, e.g. using frequency domain transformations or autocorrelation

Abstract

A method of identifying and classifying pre-detected target candidates in an image using pixel intensity and a fractalization process applied to the image. A raw analog image is digitized and normalized. The normalized pixel intensity content of the image is converted to fractal dimensions using a small and a large fractal box, sequentially. An array of special fractal features satisfying predetermined classification thresholds is prepared from the fractal dimensions for each box centered about each pre-detected target candidate in the image, thus classifying the detected objects as targets.

Claims

1. A method for discriminating objects such as targets from non-targets or background in a raw analog image which is pre-processed by being digitized and normalized and consisting of pixels, each of which having its intensity level valued between 0 and 255 where zero is black and 255 is white, and then subjected to a detector capable of identifying possible objects of interest based on appropriate characteristics such as size and brightness for further processing, and providing the x and y center coordinates of each such object in said image, said method having filenames, arrays, and parameters, and said method comprising the steps of:

(a) initializing all filenames, arrays, and parameters;

(b) inputting normalized image data of pixel intensities;

(c) entering input variables consisting of the sizes of a large fractal box, a small fractal box and predetermined threshold test levels;

(d) entering the x and y center coordinates of each object detected in said image in the fractal feature array;

(e) calculating Sdim, the small box fractal dimension, Bdim, the big box fractal dimension and Fdif, the magnitude of the dimensional differences of Bdim and Sdim for each detected object center; and

(f) subjecting said calculated fractal data for each detected object in each said image to classification thresholding where;

(1) minimum thresholds for object acceptance using a counter TARGET1; and

(2) thresholds for target classification using a counter TARGET.

2. The process of claim 1 wherein four minimum threshold tests are performed and must be passed for object acceptance as a possible target.

3. The method of claim 2 wherein the four minimum threshold tests comprise:

(a) minimum threshold test 1;

Sdim>

MINBDIM and Fdif≧

MINFDIF, where Sdim is the small box fractal dimension, MINBDIM is the big box fractal dimension minimum threshold, Fdif is the fractal dimension difference, and MINFDIF is the fractal difference minimum threshold;

(b) minimum threshold test 2;

Perpix<

MAXPERCENT, where Perpix is the percentage of pixels within the small fractal box above the pixel intensity threshold and MAXPERCENT is maximum percentage of pixels allowed greater than maximum allowable pixel intensity threshold, MAXINTEN;

(c) minimum threshold test 3;

Slope≦

LESSMINSLOPE, where Slope is the average slope of the small box fractal dimension in the vicinity of the detected object less the minimum slope;

(d) minimum threshold test 4;

(1) first configuration

Tsum≧

MINTSUM where Tsum is the small box fractal dimension distribution sum and MINTSUM is the small box fractal dimension distribution sum minimum threshold; and

Dsum≧

MINDSUM, where Dsum is the big box and small box fractal dimension difference distribution sum and MINDSUM is the fractal difference distribution sum minimum threshold;

(2) second configuration

Tsum≧

MIDTSUM and Dsum<

MINDSUM where Tsum is the small box fractal dimension distribution sum and MIDTSUM is the small box fractal dimension distribution sum median threshold;

Dsum is the big box and small box fractal dimension difference distribution sum and MINDSUM is the fractal difference distribution sum minimum threshold;

Tsum and Dsum calculations continue, and

(3) third configuration

Tsum≧

MAXTSUM and Dsum<

MINDSUM where Tsum is the small box fractal dimension distribution sum;

MAXTSUM is the small box fractal dimension distribution sum maximum threshold;

Dsum is the big box and small box fractal dimension difference distribution sum and MINDSUM is the fractal difference distribution sum minimum threshold.

4. The process of claim 3 wherein for each minimum threshold test passed by a detected object, a variable TARGET1 is incremented by one.

5. The process of claim 1 wherein the thresholds for target classification are in three precise tests applied to each detected object.

6. The method of claim 5 wherein the three precise tests comprise:

(a) precise test 1;

MINSDIM≦

Sdim≦

MAXSDIM for elimination of certain non-targets certain non-targets where MINSDIM is a small box fractal minimun threshold;

Sdim is the small box fractal dimension, and MAXSDIM is the small box fractal maximun threshold

(b) precise test 2;

MINBDIM<

Bdim≦

MAXBDIM and Fdif≧

SIGNDIFF indicates that an object of some kind is definitely present and not just background;

where MINBDIM is the big box fractal dimension minimum threshold;

Bdim is the big box fractal dimension;

MAXBDIM is the big box fractal maximum threshold;

Fdif is the fractal dimension difference, and SIGNDIFF is significant fractal difference threshold and

(c) precise test 3;

Slope≦

MINSLOPE to determine if the slope is both negative and steep enough to consider qualifying the object as a possible target, where slope is the average slope of the small box fractal dimension in the vicinity of the detected object and MINSLOPE is small box fractal dimension minimum slope.

7. The process of claim 6 wherein for each precise test passed, the variable TARGET is incremented by one.

8. The method of claim 1 wherein said minimum thresholds for object acceptance using TARGET1 comprise four minimum threshold tests and said thresholds for target classification using the counter TARGET comprise three precise tests.

9. The process of claim 8 wherein objects that pass four minimum threshold tests and at least two out of three precise tests are tentatively identified as targets and assigned a confidence value of one.

32. The method of claim 9 step (f) wherein the application of a final target classification test means that two variables used as counters, that is, incremented by one whenever a certain condition is met, are submitted to minimum score tests.

33. The method of claim 32 wherein the first variable TARGET keeps a count of the number of times a precise threshold test is passed.

34. The method of claim 32 wherein the second variable TARGET1 keeps a count of the number of times a minimum threshold test is passed.

35. The method of claim 32 wherein the variable TARGET must be greater than or equal to a minimum value and the variable TARGET1 must be greater than or equal to a maximum value.

10. A method for discriminating objects such as targets from non-targets or background in a raw analog image which is pre-processed by being digitized and normalized and consisting of pixels, each of which having its intensity level valued between 0 and 255 where zero is black and 255 is white, and then subjected to a detector capable of identifying possible objects of interest based on appropriate characteristics such as size and brightness for further processing, and providing the x and y center coordinates of each such object in said image, said method having filenames, arrays, and parameters, and said method comprising the steps of:

(a) initializing all filenames, arrays, and parameters;

(b) inputting normalized image data;

(c) entering input variables consisting of size of a large and size of a small fractal box and predetermined threshold levels for the input parameters, as defined in Table 4 hereinabove and as identified below comprising;

(1) SIGNDIFF, (2) MINSDIM, (3) MAXSDIM, (4) MINBDIM, (5) MAXBDIM, (6) MINFDIF, (7) MINSLOPE, (8) LESSMINSLOPE, (9) MAXPERCENT, (10) MAXINTEN, (11) MINTSUM, (12) MIDTSUM, (13) MAXTSUM, (14) MINDSUM, (15) MINTARGET, (16) MINTARGET2, (17) MAXTARGET1.

(d) entering the x and y center coordinates of each object detected in said image in the fractal feature array;

(e) calculating Sdim, the small box fractal dimension, Bdim, the big box fractal dimension and Fdif, the magnitude of the dimensional differences of Bdim and Sdim for each detected object center;

(f) testing Sdim, the small box fractal dimension, to a threshold level target test for a predetermined type of target MINSDIM≦

Sdim≦

MSDIM where MINSDIM is the small box fractal minimum threshold and MAXSDIM is the small box fractal maximum threshold, such that if true, TARGET is incremented by 1;

(g) performing the fractal difference threshold target test such that if MINSDIM≦

Sdim≦

MAXSDIM and Fdif≧

SIGNDIFF are true, where Fdif is the fractal dimension difference, the value of TARGET is incremented by 1 to establish that an object of some kind and not just background is present;

(h) applying a minimum threshold test to look for the minimum fractal feature values to detect an object qualifying as a possible target such that, if Sdim>

MINBDIM or Fdif≧

MINFDIF are false, where MINBDIM is the big box fractal minimum threshold, the detected object is classified as a non-target and the confidence variable Conf is set to zero and another detected object center is selected for processing, but the test is true the variable TARGET1 is incremented by one and the variable Perpix, the percentage of pixels within the small fractal box above the pixel intensity threshold, is calculated;

(i) applying an intensity threshold to the variable Perpix such that if Perpix<

MAXPERCENT is true, where MAXPERCENT is the maximum percentage of pixels allowed greater than maximum allowable pixel intensity threshold MAXINTEN, the value of TARGET1 is incremented by one meaning that the object in the defined area is probably a target and not image clutter;

(j) calculating fractal slope Slope, the average slope of small box fractal dimension in the vicinity of the detected object;

(k) performing a target slope test Slope≦

MINSLOPE, the small box fractal dimension minimum slope, to determine if value of Slope is both negative and steep enough to qualify object as possible target and if true incrementing TARGET by one;

(l) performing minimum slope test Slope≦

LESSMINSLOPE, the small box fractal dimension less minimum slope, to tentatively qualify the object as a target, if true and, incrementing TARGET1 by one, if not true, classifying object as non-target, setting confidence level variable Conf to zero, and going to next detected object center coordinates;

(m) performing the minimum score test TARGET≧

MINTARGET≧

2 and TARGET1≧

MINTARGET1≧

3 if minimum slope test is true, such that, if the result is false, the detected object is classified as a non-target, the confidence level variable Conf is set to zero, and the next detected object center coordinates are selected for processing, or if the result is true, distribution sums of the small box fractal dimension distribution sum Tsum and the fractal difference sum Dsum are calculated;

(n) calculating the small box fractal dimension distribution sum Tsum and the fractal difference distribution sum Dsum for an area around the detected object center to determine target sustainability using the offset matrix of numbered pixels

space="preserve" listing-type="tabular">______________________________________ 71 72 73 74 75 46 47 48 49 50 60 70 45 35 21 22 23 24 25 30 40 65 69 44 34 11 12 13 14 15 29 39 64 68 43 33 1 2 3 4 5 28 38 63 67 42 32 6 7 8 9 10 27 37 62 66 41 31 16 17 18 19 20 26 36 61 51 52 53 54 55 56 57 58 59 76 77 78 79 80 ______________________________________

and starting at pixel #1 and sequentially progressing through pixel #80 or until after Sdim, the small box fractal dimension, and Fdif, the fractal dimension difference, are calculated as centered on a pixel, pass their threshold tests MINSDIM≦

SDIM≦

MAXSDIM and MINBDIM<

Bdim≦

MAXBdim and Fdif≧

SIGNDIFF, and applying a first Tsum Dsum threshold test Tsum≧

MINTsum and Dsum≧

MINDSUM are true so that processing of pixels ceases, a tentative target is declared, TARGET1 is incremented by one, and processing proceeds to target classification; and

(o) applying a second Tsum, small box fractal dimension distribution sum, and Dsum, big box and small box fractal dimension difference distribution sum, threehold test where said first threshold test is false indicating the detected object may be a weak target, where in said second test said Tsum is greater than or equal to a median value Tsum≧

MIDTSUM, the small box fractal dimension distribution sum median threshold, and Dsum is less than a minimum Dsum<

MINVDSUM, and where if the result is false, the process proceeds to target classification, and where is the result is true Tsum and Dsum, distribution calculations are performed looping through pixels #1 through #40 using the offset matrix of numbered pixels

space="preserve" listing-type="tabular">______________________________________ 11 7 3 30 10 6 2 o o o o o 16 17 18 38 28 9 5 1 o o o o o o 14 15 36 27 o o o o o o o o o o o 34 24 o o o o o o o o o o o 32 23 o o o o Xc,Yc o o o o o o 31 25 o o o o o o o o o o o 33 26 o o o o o o o o o o o 35 29 12 o o o o o o o o o 19 37 40 13 8 4 o o o o o 21 22 20 39 ______________________________________

11. The method of claim 10 wherein the small box fractal dimension distribution sum Tsum and the fractal difference distribution sum Dsum are calculated for an area around the detected object center.

12. The method of claim 10 wherein the distribution sums Tsum and Dsum are near zero for background areas and have a large value over target areas.

13. The method of claim 10 wherein said Tsum distributions are calculated by sequentially forming a small fractal box and a big fractal box of the same sizes entered in step (c), co-located with and around each pixel in the offset matrix starting with pixel #1.

14. The method of claim 10 wherein the minimum threshold test 4 is performed after each small box fractal dimension distribution sum Tsum and big box and small box fractal dimension difference distribution sum Dsum calculation after each pixel is tested.

15. The method of claim 10 wherein the small fractal box and big fractal box can be any 2-dimensional shape.

16. The method of claim 10, step (e) wherein the fractal dimension difference Fdif is calculated by subtracting the small box fractal dimension Sdim from the big box fractal dimension Bdim.

17. The method of claim 10, step (e) wherein after the three calculations are performed, three threshold tests are performed.

18. The method of claim 17 wherein for the first of said three tests, the small box fractal dimension Sdim threshold level target test (a precise threshold test), the value of the small box fractal dimension Sdim must be greater than or equal to a minimum value and must be less than or equal to a maximum value.

19. The method of claim 17 wherein for the second of said three tests, the fractal dimension difference Fdif threshold target test (a precise threshold test), the value of the big box fractal dimension Bdim must be greater than a minimum value and must be less than or equal to a maximum value, and the fractal dimension difference must be greater than or equal to a significant difference.

20. The method of claim 17 wherein for the third of said three tests, the small box fractal dimension Sdim and fractal difference minimum threshold test (a minimum threshold test), the small box fractal dimension Sdim must be greater than a minimum value and the fractal difference Fdif must be greater than or equal to a minimum value.

21. The method of claim 10, step (h) wherein after calculating the percentage of pixels in an area formed around one detected object center that have an intensity greater than or equal to a threshold intensity, the percentage is subjected to a threshold test (a minimum threshold test).

22. The method of claim 21 wherein the percentage of high intensity pixels must be less than a maximum allowable percentage.

23. The method of claim 10, step (i) wherein after calculating the slope of the small box fractal dimension in the vicinity of one detected object center, two slope threshold tests are performed.

24. The method of claim 23 wherein for the first test, the target slope threshold test (a precise threshold test), the slope must be less than or equal to a minimum value.

25. The method of claim 23 wherein for the second test, the minimum slope test, the slope must be less than or equal to an even stricter minimum value (a minimum threshold test).

26. The method of claim 10, step (m) wherein the application of a minimum score test means that two variables used as counters, that is, incremented by one whenever a certain condition is met, are submitted to minimum score tests.

27. The method of claim 26 wherein the first variable TARGET keeps a count of the number of times a precise threshold test is passed.

28. The method of claim 26 wherein the second variable TARGET1 keeps a count of the number of times a minimum threshold test is passed.

29. The method of claim 26 wherein the variable TARGET must be greater than or equal to a minimum value and the variable TARGET1 must be greater than or equal to a minimum value.

30. The method of claim 10, step (n) wherein the calculated values of the distribution sums of the small box fractal dimension and the fractal difference across a preset pattern of pixels, with the detected object center in the center of the pattern, are repeatedly submitted to threshold tests.

31. The method of claim 30 wherein the threshold tests state that the distribution sum of the small box fractal dimension must be greater than or equal to a minimum value and the distribution sum of the fractal difference must be greater than or equal to a minimum value;

or, that the distribution sum of the small box fractal dimension must be greater than or equal to a median value and the distribution sum of the fractal difference must be less than a minimum value;

or, that the distribution sum Tsum of the small box fractal dimension must be greater than or equal to a maximum value and the distribution sum Dsum of the fractal dimension difference must be less than a minimum value.