SYSTEM, METHOD, AND APPARATUS FOR CLUSTERING FEATURES USING AN EXPANSION SHAPE

• US 20090196511A1
• Filed: 04/08/2009
• Published: 08/06/2009
• Est. Priority Date: 07/07/2004
• Status: Active Grant

• Current Assignee: The Government Of The United States Of America, As Represented By The Secretary Of The Navy
• Original Assignee: The Government of The US As Represented By The Secretary of The Navy
• Inventors: Gendron, Marlin L., Layne, Geary J., Lohrenz, Maura C.
• Granted Patent: US 7,764,840 B2
• Time in Patent Office: Days
• 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 the said plurality of expansion shapes is applied to a different one of the initially set bits.

2. The method according to claim 1, wherein said plurality of expansion shapes have a one-to-one correspondence with said initially set bits.

3. The method according to claim 1, wherein said applying an expansion shape includes

setting each of the bits within the expansion shape.

4. 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.

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

6. 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.

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

8. 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.

9. 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.

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

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

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

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

13. The method according to claim 12, wherein said identifying vertex bits includes

traversing the boundary bits of a cluster to determine which boundary bits are vertex bits.

14. A 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 to a different one of the initially set bits.

15. The computer-readable medium according to claim 14, wherein said plurality of expansion shapes have a one-to-one correspondence with said initially set bits.

16. The computer-readable medium according to claim 14, wherein said applying a plurality of expansion shapes includes

setting each of the bits within the expansion shapes.

17. The computer-readable medium according to claim 14, 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.

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

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

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

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

22. The computer-readable medium according to claim 14, 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.

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

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

25. The computer-readable medium according to claim 16, 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 said identifying vertex bits including traversing the boundary bits of a cluster to determine which boundary bits are vertex bits.