Beyond the Hough Transform: Further Properties of the R-Theta Mapping and Their Applications

Abstract

The Hough transform is a standard technique for finding features such as lines in images. Typically, points or edgels are mapped into a partitioned parameter or Hough space as individual votes where peaks denote the feature of interest. The standard mapping used for line detection is the Rθ mapping and the key property the Hough transform exploits is that lines in the image map to points in Hough space. In this paper we introduce and explore three further properties of the Rθ mapping and suggest applications for them. Firstly, we show that points in Hough space with maximal R forany value of θ are on the convex hull of the object in image space. It is shown that approximate hulls of 2D and 3D hulls of objects can be constructed in linear time using this approach. Secondly, it is shown that a simple relationship exists between the occluding contour of an object and the Rθ mapping and that this could in principle be used to generate approximate aspect graphs of objects whose geometry was known. Thirdly, it is shown that antipodal points on object boundaries, (which are optimal robot grasp points), can be found by translation and reflection of the Rθ representation. In addition we show the relationship between the Rθ mapping used in the Hough transform and the classical mathematical theory of duals. We use this analysis to prove formally stated properties of the Rθ mapping from image space to Hough space and in particular the relationship to the convex hull.