Grouping and Recognition of Dot Patterns with Straight Offset Polygons
This addresses a computer vision problem for object recognition from sparse dot patterns, but it appears incremental as it builds on existing grouping and transformation techniques.
The paper tackles the problem of algorithmically grouping dot patterns into subsets to recognize objects from dot boundaries, which humans can do easily but computers could not reproduce. The authors introduce a new algorithm that connects dots into a spanning tree, applies a straight polygon transformation to generate O(n) polygons, and demonstrate its effectiveness on natural and synthetic images.
When the boundary of a familiar object is shown by a series of isolated dots, humans can often recognize the object with ease. This ability can be sustained with addition of distracting dots around the object. However, such capability has not been reproduced algorithmically on computers. We introduce a new algorithm that groups a set of dots into multiple non-disjoint subsets. It connects the dots into a spanning tree using the proximity cue. It then applies the straight polygon transformation to an initial polygon derived from the spanning tree. The straight polygon divides the space into polygons recursively and each polygon can be viewed as grouping of a subset of the dots. The number of polygons generated is O($n$). We also introduce simple shape selection and recognition algorithms that can be applied to the grouping result. We used both natural and synthetic images to show effectiveness of these algorithms.