FINDING CONVEX EDGE GROUPINGS IN AN IMAGE

In an image, there are groups of intensity edges that are likely to have resulted from the same convex object in a scene. A new method for identifying such groups is described here. Groups of edges that form a convex polygonal chain, such as a convex polygon or a spiral, are extracted from a set of image edge fragments. A key property of the method is that its output is no more complex than the original image. The method uses a triangulation of the linear edge segments in an image to define a local neighborhood that is scale invariant. From this local neighborhood a local convexity graph is constructed; this encodes which neighboring image edges could be part of a convex group. A path in the graph corresponds to a convex polygonal chain in the image, with a cyclic path corresponding to a polygon. We have implemented the method and found that it is efficient in practice as well as in theory. Examples are presented to illustrate that the technique finds intuitively salient groups, including for images of cluttered scenes.