System, method and apparatus for clustering features

• US 7,567,714 B2
• Filed: 11/23/2004
• Issued: 07/28/2009
• Est. Priority Date: 07/07/2004
• Status: Expired due to Fees

• Current Assignee: the united states of america as represented by the secretary of the navy
• Original Assignee: the united states of america as represented by the secretary of the navy
• Inventors: Layne, Geary J., Gendron, Marlin L., Lohrenz, Maura C.
• Primary Examiner(s): Bali; Vikkram
• Assistant Examiner(s): ENTEZARI, MICHELLE M
• Application Number:
  US10/997,091
• Publication Number:
  US 20060009955A1
• Time in Patent Office: 1,708 Days
• Field of Search: None
• US Class Current: 382/225
• CPC Class Codes: G06F 18/23 Clustering techniques

Abstract

A method, system, computer-readable medium, and apparatus for identifying a boundary of a cluster in a bitmap, the bitmap having at least one initially set bit, for applying an expansion shape to each of the initially set bits in the bitmap and identifying vertex bits on the boundary of the cluster formed by at least one expansion shape. A method system, computer-readable medium, and apparatus for identifying vertex bits in a bitmap having at least two adjacent bits with non-zero values forming a boundary of a cluster, the interior bits of the cluster having a zero value, including starting from a current non-zero bit, evaluating at least a first adjacent bit and a second adjacent bit, setting an adjacent non-zero bit as the new current bit, and identifying the current bit as a vertex bit if a direction of motion from the current bit to the new current bit changes.

Claims

1. A computer-implemented method for identifying a boundary of a cluster in a bitmap, the bitmap having at least one initially set bit, the method comprising:

applying an expansion shape to each of the initially set bits in the bitmap on a computer;

identifying vertex bits on the boundary of the cluster, the cluster including at least one expansion shape on the computer;

for a current boundary bit with a first, second, and a third adjacent bit, evaluating at least two diagonally opposite adjacent bits if at least two of the first, the second, and the third adjacent bits are set on the computer;

wherein one of the diagonally opposite adjacent bits is between the first and second adjacent bits; and

assigning the adjacent set bit that was evaluated first as the new current bit on the computer if both of the two diagonally adjacent bits are clear.

2. The method according to claim 1, wherein said applying an expansion shape includes setting each of the bits within the expansion shape.

3. The method according to claim 1, wherein the cluster includes at least two expansion shapes, the two expansion shapes having at least one bit in common.

4. The method according to claim 1, wherein the cluster includes at least two expansion shapes, the two expansion shapes having at least two bits in common.

5. The method according to claim 1, wherein each of the bits in the bitmap corresponds to a geospatial location.

6. The method according to claim 1, wherein each initially set bit in the bitmap corresponds to a feature at a physical location.

7. The method according to claim 6, wherein each initially set bit in the bitmap corresponds to only one feature.

8. The method according to claim 1, wherein the expansion shape is a polyhedron.

9. The method according to claim 1, wherein the boundary is a polyhedron.

10. The method according to claim 1, further comprising:

expanding the bitmap to a size sufficient to include all the initially set bits.

11. The method according to claim 1, further comprising:

limiting the bitmap to a size sufficient to include all the initially set bits and all the bits in the expansion shapes.

12. A method according to claim 1, wherein the cluster is a cluster of set bits in the bitmap, and at least two of the expansion shapes around each of the initially set bits combine to form the cluster of set bits.

13. A method according to claim 12, wherein said applying an expansion shape includes setting at least one bit adjacent to each of the initially set bits.

14. The method according to claim 12, wherein said applying an expansion shape to each initially set bit includes setting a plurality of bits adjacent to each initially set bit.

15. The method according to claim 13, wherein said applying an expansion shape to each initially set bit includes setting a plurality of bits around each initially set bit.

16. The method according to claim 13, wherein the bitmap comprises binary bits having states including set and off.

17. The method according to claim 13, wherein said identifying vertex bits on the boundary of the cluster of said bits is accomplished after applying the expansion shapes to each of the initially set bits.

18. The method according to claim 15, wherein the expansion shape is a circle.

19. The method according to claim 15, wherein the expansion shape is a triangle.

20. The method according to claim 15, wherein the expansion shape is an ellipse.

21. The method according to claim 15, wherein the expansion shape has a size proportional to a distance between a reference point and a point corresponding to the initially set bit.

22. A computer-implemented method for identifying a boundary of a cluster in a bitmap, the bitmap having at least one initially set bit, the method comprising:

applying an expansion shape to each of the initially set bits in the bitmap on a computer;

identifying vertex bits on the boundary of the cluster on the computer, the cluster including at least one expansion shape;

evaluating at least two diagonally opposite adjacent bits if at least two of the first, second, and third adjacent bits are set on the computer;

wherein one of the diagonally opposite adjacent bits is between the first and second adjacent bits; and

assigning the adjacent set bit that was evaluated last as the new current bit on a computer if at least one of the two diagonally adjacent bits are not clear.

23. A computer-readable medium containing computer-readable instructions for defining a boundary of a cluster in a bitmap having at least one initially set bit, the computer readable instructions comprising:

instructions for applying an expansion shape to each of the set bits in the bitmap; and

instructions for identifying vertex bits on the boundary of the cluster formed by at least one expansion shape, instructions for evaluating at least two diagonally opposite adjacent bits if at least two of a first, a second, and a third adjacent bit are set;

wherein one of the diagonally opposite adjacent bits is between the first and second adjacent bits; and

instructions for assigning the adjacent set bit that was evaluated first as the new current bit if both of the two diagonally adjacent bits are clear.

24. The computer readable medium according to claim 23, wherein said instructions for applying an expansion shape includes instructions for setting each of the bits within the expansion shape.

25. The computer readable medium according to claim 23, wherein the cluster includes at least two expansion shapes, the two expansion shapes having at least one bit in common.

26. The computer readable medium according to claim 23, wherein the cluster includes at least two expansion shapes, the two expansion shapes having at least two bits in common.

27. The computer readable medium according to claim 23, wherein each of the bits in the bitmap corresponds to a geospatial location.

28. The computer readable medium according to claim 23, wherein each initially set bit in the bitmap corresponds to a feature at a physical location.

29. The computer readable medium according to claim 23, wherein each initially set bit in the bitmap corresponds to only one feature.

30. The computer readable medium according to claim 23, wherein the expansion shape is a polyhedron.

31. The computer readable medium according to claim 23, wherein the boundary is a polyhedron.

32. The computer readable medium according to claim 23, further comprising:

instructions for expanding the bitmap to a size sufficient to include all the initially set bits.

33. The computer readable medium according to claim 23, further comprising:

instructions for limiting the bitmap to a size sufficient to include all the initially set bits and all the bits in the expansion shapes.

34. The computer readable medium according to claim 23, wherein said instructions for identifying said vertex bits on the boundary of a cluster includes instructions for identifying the current bit as a vertex if a direction from the current bit to the new current bit is different than a current direction of motion, wherein the current direction of motion is a direction is a direction from an immediately previous bit to the current bit.

35. The computer readable medium according to claim 23, wherein the cluster is a cluster of set bits in the bitmap, and at least two of the expansion shapes around each of the initially set bits combine to form the cluster of set bits.

36. The computer readable medium according to claim 35, wherein said applying an expansion shape to each initially set bit includes setting a plurality of bits adjacent to each initially set bit.

37. The computer-readable medium according to claim 35, wherein said applying an expansion shape to each initially set bit includes setting a plurality of bits around each initially set bit.

38. The computer-readable medium according to claim 35, wherein the bitmap comprises binary bits having states including set and off.

39. The computer-readable medium according to claim 35, wherein said identifying vertex bits on the boundary of the cluster of said bits is accomplished after applying the expansion shapes to each of the initially set bits.

40. The computer-readable medium according to claim 37, wherein the expansion shape is a circle.

41. The computer-readable medium according to claim 37, wherein the expansion shape is a triangle.

42. The computer-readable medium according to claim 37, wherein the expansion shape is an ellipse.

43. The computer-readable medium according to claim 37, wherein the expansion shape has a size proportional to a distance between a reference point and a point corresponding to the initially set bit.