Christopher Parrish
ECE533 Project Proposal
The Hough Transform for Vertical Object Recognition in 3D Images
Generated from Airborne Lidar Data
Background: Since the 1940s, the National Geodetic Survey (NGS) has conducted airport obstruction surveys to obtain position, elevation, and attribute data for vertical objects, such as trees, towers, poles, and buildings, on and around airfields and in runway approaches [3,7]. These data are used by the Federal Aviation Administration (FAA) and airport managers in designing runway approach procedures, determining maximum takeoff weights, performing planning studies, and a variety of related applications. Recent studies have shown that airborne light detection and ranging (lidar) may provide an inexpensive and efficient alternative to conventional airport obstruction surveying techniques for some types of surveys and runway approach types [2,3]. However, to date, several unsolved problems have prohibited the widespread adoption of airborne lidar in this particular application area.
Problem: One current challenge is the automated extraction of vertical objects of interest, such as trees, towers, and poles, from the airborne lidar data. The problem is complicated by the extremely large quantity of data (modern systems can collect upwards of nine million data points per minute of airborne data acquisition), as well as by clutter (e.g., returns from birds or other “flyers”) and noise.
Proposed Approach: In this project, I propose to investigate the use of the Hough transform for vertical object recognition in 3D images created from the airborne lidar data. The steps in the proposed method can be summarized as follows:
1) Voxelize the lidar point cloud to create a 3D image (specifically, a regularly-spaced 3D grid of laser intensity values, using 8 bits per voxel).
2) Perform edge detection on this image using a 3D Sobel operator.
3) Perform threshold segmentation to output a binary image.
4) Parameterize the vertical objects of interest (limited to poles, stacks, and towers in this project) as vertical cylinders. The assumption that the cylinders are oriented vertically (i.e., parallel with the z-axis) reduces the number of parameters to three: the cylinder radius, r, and x,y coordinates of its axis.
5) Discretize the 3D Hough parameter space.
6) Tally votes in the parameter space to identify the major vertical cylinders. If the approach is successful, these “major cylinders” should correspond to the vertical objects of interest.
The results will be assessed by investigating whether known (i.e., field surveyed) vertical objects are correctly identified. Additionally, the computational efficiency of the proposed approach will be assessed. If time permits, the project may be extended by creating parametric representations of other types of vertical objects (e.g., coniferous trees parameterized as cones) or by using the Generalized Hough Transform (GHT) for extracting airport obstructions that do not permit simple parametric representations.
References:
1. Olson, C.F., 2001. Locating Geometric Primitives by Pruning the Parameter Space, Pattern Recognition, Vol. 34, No. 6, pp. 1247-1256.
2. Parrish, C.E., G.H. Tuell, W.E. Carter, and R.L. Shrestha, 2005. Configuring an Airborne Laser Scanner for Detecting Airport Obstructions. Photogrammetric Engineering and Remote Sensing, Vol. 71, No. 1.
3. Parrish, C.E., J. Woolard, B. Kearse, and N. Case, 2004. Airborne LIDAR Technology for Airspace Obstruction Mapping. Earth Observation Magazine (EOM), Vol. 13, No. 4.
4. Rabbani, T. and F. van den Heuvel, 2005. Efficient Hough Transform for Automatic Detection of Cylinders in Point Clouds. Proceedings ISPRS WG III/3, III/4, V/3 Workshop “Laser Scanning 2005”, Sept. 12-14, Enschede, the Netherlands.
5. Simonse, M., T. Aschoff, H. Spiecker, and M. Thies, 2003. Automatic Determination of Forest Inventory Parameters Using Terrestrial Laserscanning. Proc. ScandLaser Scientific Workshop on Airborne Laser Scanning of Forests, Umeå, Sweden, pp. 251- 257.
6. Sinha, P.K., F.-Y. Chen, and R.E.N. Home, 1993. Recognition and Location of Shapes in the Hough Parameter Space. IEEE Colloquium on Hough Transforms, pp. 11/1 – 11/4, 1993.
7. Tuell, G., 1987. Technical Development Plan for the Modernization of the Airport Obstruction Charting Program. NOAA Charting Research and Development Laboratory, Office of Charting and Geodetic Services, Rockville, Maryland.
8. Vosselman, G., B.G.H. Gorte, and T. Rabbani, 2004. Recognising Structure in Laser Scanner Point Clouds. IAPRS, Vol. 36, part 8/W2, pp. 22-38.