Home  —  Kernel-Based Hough Transform 

Real-Time Line Detection Through
an Improved Hough Transform Voting Scheme


Welcome to Kernel-Based Hough Transform Home Page. Here we present an improved voting scheme for the Hough transform that allows a software implementation to achieve real-time performance even on relatively large images. Our approach operates on clusters of approximately collinear pixels. For each cluster, votes are cast using an oriented elliptical-Gaussian kernel that models the uncertainty associated with the best-fitting line with respect to the corresponding cluster. The proposed approach not only significantly improves the performance of the voting scheme, but also produces a much cleaner voting map and makes the transform more robust to the detection of spurious lines.

This project was developed by me under supervision of professor Manuel Menezes de Oliveira Neto, Ph.D.

Here you find:

- A link to the Pattern Recognition paper;
- A copy of the C++ source code;
- A copy of the MATLAB wrapper to the C++ implementation.


Journal Paper
Thumbnail image
                            for the work "Real-time line detection
                            through an improved Hough transform voting

Leandro A. F. Fernandes, Manuel M. Oliveira. Real-time line detection through an improved Hough transform voting scheme. Pattern Recognition (PR), Elsevier, 41:1, 2008. pp. 299-314. [DOI Bookmark] [Corrigendum] [Paper]

Errata - 01/14/2008
In Algorithm 3 (line 5), should be initialized with the largest possible value ( ), in order to be correctly updated in line 11.
: The authors would like to thank Siyu Guo for catching this typo.

Clarification - 01/14/2008
A vertical line in the original image would cause a division by zero operation that is not dealt within Algorithm 2, line 20 ( in Eq. 14). In such a case, however, the is zero, and and (Eq. 13) are also equal to zero. Thus, in practice, division by zero never actually happens.
: The authors would like to thank Ian (from University of Waterloo) for asking this.

Reference Implementation

You can download the source code from the SourceForge.net page of this project (https://sourceforge.net/projects/khtsandbox). It includes:

- The C++ reference implementation of the proposed Hough transform (in the 'kht_souce' directory);
- A sample application using the reference implementation (in the 'sample_app' directory); and
- A MATLAB wrapper function to the reference implementation (in the 'matlab' directory).

All code is released under the GNU General Public License, version 3, or (at your option) any later version.

We have compiled and tested the sample application and the MATLAB wrapper function on Windows. The source code is compatible with GCC, so we believe that it works on Linux, too. We compiled the sample application using Visual Studio 2005, Visual Studio 2008 Express Edition and Visual Studio 2010 (projects files are in the 'sample_app' directory). We compiled the MEX-file using Visual Studio 2005, 2008 Express Edition with MATLAB 7, and using Visual Studio 2010 with MATLAB R2011b (M-files and the source code of MEX-functions are in the 'matlab' directory).

Required Libraries
The reference implementation (in the 'kht_source' directory) does not require any external library. However, the sample application uses DevIL, GLUT or freeglut and GLEW.

Running the Sample Application
On Visual Studio, simply open the project file and run it (CTRL+F5).

Tip: compile the application using Release configuration in order to achieve better frame rates.

Running the MATLAB Wrapper Function
First, you need to compile the MEX-file used by the wrapper function:

1. Open MATLAB and set the 'matlab' directory of the downloaded source code as current directory;

2. Choose a compiler for building external interface (MEX) files by calling 'mex -setup' in MATLAB command window. If you do not know how to use the 'mex' command, call 'help mex' or 'doc mex';

3. Call the 'kht_compiler' function and wait the MEX-file compilation.

After the MEX-file compilation, the wrapper function can be used. The 'main.m' file in 'matlab' directory provides a simple example of how to use the 'kht' function. Call 'help kht' to see the function usage.

Tip: by adding the 'matlab' directory to the MATLAB search path (see 'help addpath') you can call the 'kht' function from any current directory.

Building Your Own C++ Application
To use the reference implementation of the proposed Hough transform, you should include the files from the 'kht_source' directory into your project and then call the 'kht' function declared in the 'kht.h' header file.