System, method and apparatus for clustering features using an expansion shape

• US 7,764,840 B2
• Filed: 04/08/2009
• Issued: 07/27/2010
• Est. Priority Date: 07/07/2004
• Status: Expired due to Fees

• Current Assignee: The Government Of 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:
  US12/420,679
• Publication Number:
  US 20090196511A1
• Time in Patent Office: 475 Days
• Field of Search: None
• US Class Current: 382/225
• CPC Class Codes: G06F 18/23 Clustering techniques

Abstract

A computer-implemented 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.

Claims

1. A computer implemented method for identifying a cluster of data points, the method comprising:

mapping each of the data points into a bitmap by, for each data point, initially setting a bit in the bitmap that corresponds to that data point on the computer; and

applying a plurality of expansion shapes to the initially set bits on the computer, wherein each of said plurality of expansion shapes is applied in a one to one correspondence to each of the initially set bits, wherein said applying an expansion shape includes

setting each of the bits within the expansion shape.

2. The method according to claim 1, wherein each of the expansion shapes includes a plurality of bits adjacent to the initially set bit to which that expansion shape is applied.

3. The method according to claim 1, wherein the expansion shape is a polyhedron, a circle, a triangle, or an ellipse.

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

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

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

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

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

8. The method according to claim 1, wherein the set bits in at least two of the expansion shapes form a cluster of set bits.

9. The method according to claim 8 wherein the at least two expansion shapes have at least two set bits in common.

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

identifying vertex bits on the boundary of the cluster after said applying the plurality of expansion shapes to the initially set bits.

11. The method according to claim 10, wherein said identifying vertex bits includes traversing the boundary bits of a cluster to determine which boundary bits are vertex bits.

12. A non-transitory computer-readable medium containing computer-readable instructions for identifying a cluster of data points, the computer readable instructions comprising:

instructions for mapping each of the data points into a bitmap including, for each data point, initially setting a bit in the bitmap that corresponds to that data point on the computer; and

instructions for applying a plurality of expansion shapes to the initially set bits, wherein each of the said plurality of expansion shapes is applied in a one to one correspondence to each of the initially set bits, wherein said applying a plurality of expansion shapes includes setting each of the bits within the expansion shapes.

13. The computer-readable medium according to claim 12, wherein each of the plurality of expansion shapes includes a plurality of bits adjacent to the initially set bit to which the expansion shape is applied.

14. The computer-readable medium according to claim 12, wherein the expansion shape is a polyhedron, a circle, a triangle, or an ellipse.

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

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

17. The computer-readable medium according to claim 12, wherein the bitmap is a geospatial bitmap and each of the bits in the bitmap corresponds to a geospatial location.

18. The computer-readable medium according to claim 12, further comprising:

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

19. The computer-readable medium according to claim 12, wherein the set bits in at least two of the expansion shapes form a cluster of set bits.

20. The computer-readable medium according to claim 12, wherein the at least two expansion shapes have at least two set bits in common.

21. The computer-readable medium according to claim 12, further comprising:

instructions for identifying vertex bits on the boundary of the cluster after said applying the plurality of expansion shapes to the initially set bits, said identifying vertex bits including traversing the boundary bits of a cluster to determine which boundary bits are vertex bits.