Convex grouping Source Code
Vision List Digest:
Article 2,
Volume 14, Issue 42
From: David Jacobs
Post-Followup: submission@VISLIST.com
Common Lisp code is now publicly available for finding salient convex
groups of line segments. The code may be retrieved by anonymous ftp
to: ``external.nj.nec.com'', in the file ``/pub/dwj/src/convex-grouping.tar'',
or from my web page:
http://www.neci.nj.nec.com/homepages/dwj.html.
This grouping system is described most fully in: MIT AI lab Technical
Report #1416, "Recognizing 3-D Objects Using 2-D Images" (available
through my web page). The system is also described in a forthcoming
paper in IEEE Trans. PAMI (also available from my web page), in
``Finding Salient Convex Groups'', Proc.\ of the DIMACS Workshop on
Partitioning Data Sets. pp.~{237--269}, 1995, and, very briefly, in
``Robust and Efficient Detection of Convex Groups'', IEEE Conf.\ on
Computer Vision and Pattern Recognition. pp.~{770--771}, 1993. Here
is the abstract of the PAMI paper:
This paper describes an algorithm that robustly locates {\em salient}
convex collections of line segments in an image. The algorithm is
guaranteed to find all convex sets of line segments in which the
length of the gaps between segments is smaller than some fixed
proportion of the total length of the lines. This enables the
algorithm to find convex groups whose contours are partially occluded
or a missing due to noise. We give an expected case analysis of
the algorithm's performance. This demonstrates that salient convexity
is unlikely to occur at random, and hence is a strong clue that
grouped line segments reflect underlying structure in the scene. We
also show that our algorithm's run time is $O(n^2\log(n) + nm)$, when
we wish to find the $m$ most salient groups in an image with $n$ line
segments. We support this analysis with experiments on real data, and
demonstrate the grouping system as part of a complete recognition
system.
http://www.vislist.com