Representation with an Unordered Point Set
(An Algorithmic Solution to Pointillism)Algorithm used:
P. Bhowmick, A. Biswas, and B. B. Bhattacharya. On the Representation of a Digital Contour with an Unordered Point Set for Visual Perception, Journal of Visual Communication and Image Representation, Vol. 22(7), pp. 590-605, 2011.Abstract: We study the problem of representing the boundary of a digital object with an unordered set of points (pixels) chosen from its 1-pixel wide contour such that its shape is visually perceptible and uniquely reconstructible. Extraction of such a set is important from the viewpoint of shape description and may also offer potential solutions to various applications like object representation, recognition, and discrimination. We propose a novel technique of determining an irredundant point set from a digital contour using the classical concept of pointillism. Pointillism, a movement of painting with dots that would blend in the viewer's eye, was developed by certain Neo-Impressionists of France late in the 19th century. In order to extract the representative point set, we first consider the digitally straight pieces constituting the contour and then obtain a digital polygon P that approximates the bounding curve in a compact form. The polygon P, defined in terms of its ordered set of vertices, is replaced, in turn, with an irredundant set P' of pseudo-vertices lying on its digital edges, so that the union of P and P' produces an unordered point set that obviates the vertex ordering but captures the underlying geometric orderliness and the neighborhood relations defining the boundary of the original object. The pseudo-vertices may be chosen by controlling a parameter called pointillist factor that governs our visual perception with the nearest-neighbor correlation of a point set. The pointillist factor can be regulated to control the prominence of the underlying object with its unordered set of points—a strong outcome that establishes the technique about its ability to capture the shape information by an order-free point set of optimal or suboptimal size. We have also given a reconstruction procedure along with an error analysis related with the concerned descriptor.
 |
 |
 |
 |
|
Shown above:
Step-by-step reconstruction from the pointillist ensemble C.
Top left: Voronoi diagram, Vor(C).
Top right: Delaunay triangulation (in red), DT(C),
as obtained from Vor(C).
Bottom left: DT(C) as a subgraph of the
Euclidean graph EG(C).
Bottom right: The reconstructed curve (in green) given by
MST(DT(C)). |
|
