VCLib Documentation  6.12.2

Hough Line Transform

Data Structures

struct  HoughControl
 Holds Settings for doing the Hough Line Transform. More...
 
struct  HLine
 Line Information Returned by the Hough Line Transform With Additional Information. More...
 

Functions

void HoughDefaults (HoughControl *Control)
 Set Default Values for the Hough Transformation. More...
 
I32 HoughCalcDx (image *src)
 Calculate Horizontal Size of Hough Image. More...
 
I32 HoughInit ()
 Allocates and Initializes Sine Table for Hough Transform. More...
 
I32 HoughInit2 (HoughControl *Control)
 Allocates and Initializes Line Memory for Hough Transform. More...
 
void HoughDeinit ()
 Deallocates Sine Table for Hough Transform. More...
 
void HoughDeinit2 (HoughControl *Control)
 Deallocates Memory for Hough Lines. More...
 
I32 HoughTransform (image *src, image *Hough32, HoughControl *Control)
 Hough Transform for Lines. More...
 
I32 FindHoughLine_PtrList (image *Hough32, image *src, HoughControl *Control, SPtrList *lines)
 Find Lines in Hough Transform Image with SPtrList line output. More...
 
I32 FindHoughLine (image *Hough32, image *src, HoughControl *Control)
 Find Lines in Hough Transform Image. More...
 
I32 FindLines (image *ImgVec, HoughControl *Control, I32 *NrLines)
 Searches for lines in the image ImgVec. More...
 
I32 FindSingleLine (image *Hough32, image *src, HoughControl *Control, I32 phi, I32 phi_range, HLine *line)
 Find Single Lines in Hough Transform Image. More...
 
I32 HoughRank (HLine *maxptr, I32 offset, I32 value)
 Get the Number of Lines above a certain Value. More...
 
void HoughSortLine (HLine **listptr, I32 offset)
 Sort Line List according to different Sorting Criteria. More...
 
I32 GetHoughPixels (image *Src, HLine *line, HoughControl *Control, I32 *xy)
 Extract xy-List from Hough Source Image. More...
 

Detailed Description

The Hough Transform is a tool to identify a certain class of shapes in a given image. It is mostly used for finding lines, but more complex shapes like circles and ellipses may also be searched with special versions of the Hough Transform. The general idea is to use an accumulator space and a voting procedure. The Hough Transform for lines uses the polar (or normal) representation of a line.

hough_line_phi_rho.png

The accumulator space is 2-dimensional and has the following features:

Parameter Description Dimension Size (See Text) Origin
ρ Distance from Origin Horizontal $ \sqrt{dx^2+dy^2}+1$ Centered
φ Line Angle Vertical 128 Top

The size for ρ is always rounded up to the next even number.

In each column for ρ, there are 128 bins for φ, covering the range from 0° to 180°, which results in an angular resolution of 1.4°.

The Hough Transform is typically applied to edge images. Although it is possible to use images with grey levels as an input, it is recommended to set unused image pixels to zero, since this provides a significant speed improvement. This results in a particularly good performance for binary images, where the edge pixels are set to some arbitrary value in the range of 1..255 and all other pixels are zero.

The Hough Transform can be applied to an image using the function HoughTransform(). For each non-zero pixel of the input image with coordinates (x, y), the Hough Transform calulates the function

\[ \rho = x * \sin(\varphi) + y * \cos(\varphi) \]

for all 128 values of the parameter φ. The corresponding bins in the accumulator space are incremented by the grey value of the pixel (x, y).

If there are linear structures in the image, there will be corresponding peaks in the accumulator space with a height (peak strength) proportional to the number of pixels of the line. It does not matter if the line is solid, dotted or randomly distributed along its way, only the number of pixel counts for its representation in accumulator space (Hough space).

The second main task is therefore to identify peaks in Hough Space. This is done by the function FindHoughLine().

The following shows the control struct which selects the features of the Hough Transform and the line finding algorithm:

typedef struct
{
I32 HoughMode;
I32 LineNumber;
I32 delta_phi;
I32 MinPix;
I32 LineWidth;
I32 bestfit;
struct hlstruct *maxptr;
struct hlstruct *empty;
}

Not all of the parameters are used in both HoughTransform() and FindHoughLine().

Parameter Description Used in functions Remark
HoughMode Hough Operating Mode (0-3) Both User Input
LineNumber Number of Lines Requested FindHoughLine() User Input
delta_phi See Text Both User Input
MinPix See Text FindHoughLine() User Input
LineWidth See Text FindHoughLine() User Input
bestfit Perform Bestfit (1=yes, 0=no) FindHoughLine() User Input
maxptr Pointer to First Element of Output List FindHoughLine() Set by HoughInit2()
empty Reserved for Internal Use FindHoughLine() Set by HoughInit2()

An important parameter for the function FindHoughLine() is MinPix. This is basically a threshold for the Hough space, corresponding to the minimum number of pixels for a line. Unfortunately, due to rounding errors and possibly to due to the different grey values in the original image, this value is far from exact. There may be up to a factor of 2 difference to the correct number of pixels. So this value must be set low enough, in order not to miss a line. On the other hand, if MinPix is set too low, the routine must search through a large number of tiny peaks, wasting computing time.

Most real lines are not straight lines. To account for this and to robustly detect somewhat noisy, wavy or disturbed lines, 2 parameter have been added to tune the search characteristics.

The accuracy for the detection of lines with reasonably good quality in the original image is about 0.2 degrees. If this is not enough, setting bestfit to 1 will force FindHoughLine() to calculate a least squares fit for all lines. For this fit, only pixels in the area specified by LineWidth and with a direction specified by delta_phi will be taken into account. As a result, outliers will not play a role for the bestfit procedure. For the bestfit, pixels with a value ≠ 0 are used, pixels with value = 0 are ignored. Therefore, it does not make much sense using grey images as an input, if bestfit = 1, unless values below a certain threshold are set to zero. We recommend using binary images, when the bestfit feature is selected.

It must be remarked, that the accuracy of the combined Hough- and Bestline algorithms (sometimes even without the Bestline) is so high, that the geometric distortion of the lens used for taking the picture might play an important role. This is certainly the case for wide angle lenses. If wide angle lenses are required for the application, the use of a correcting geometric image transform before performing the Hough Transform might be considered.

Since a number of functions work on the same data, unexpected behavior might result, if the operating modes are changed between calls of those functions. It is therefore a good idea, to set the operating modes in control at the beginning of the program and never change parameters afterwards.

For setting default values, you can use the function HoughDefaults().

In the following we present an example program:

#define BINAR_VALUE (1)
// allocate memory for the 32bit Hough image
ImageAllocate(&hough32, IMAGE_GREY32, HoughCalcDx(&src), 128);
// set defaults
HoughDefaults(&control);
// threshold for number of pixels in line
control.MinPix = 20 * BINAR_VALUE;
// allocate memory and initialize
HoughInit2(&control);
// binarize image with 0 and 1
binarize(&src, &src, thr, 0, BINAR_VALUE);
// do the Hough Transform
HoughTransform(&src, &hough32, &control);
// search Hough space for lines
FindHoughLine(&hough32, &src, &control);
// get the number of elements in the list
nr = HoughRank(control.maxptr, HL_VALUE, 0);
// step through the list of lines and draw them in the original image
p = control.maxptr;
while(p != NULL)
{
draw_lined(&src, p->cx, p->cy, p->b, 255);
p = p->next;
}
// deallocate memory
HoughDeinit2(&Control);
ImageFree(&Hough32);

If the program must work in a loop, we would have started the loop with the function binarize() ending with the while-loop that draws the lines.

FindHoughLine() outputs its results as follows: After execution, the control->maxptr points to the chained list of line descriptors, which have the following format:

typedef struct hlstruct
{
struct hlstruct *next; // pointer to next element in list
I32 state; // internal state
I32 value; // line detection value
I32 phi; // line angle
I32 rho; // distance from center of image
I32 strength; // line detection strength
float cx; // cx, cy, bparameters for
float cy; // line in normalized
float b; // vector form
}

next points to the next element in the list or to NULL for the last element in the list. value is the peak value in Hough space for the line (with a fixpoint integer format of 28.4). phi and rho are the line angle and distance from the origin, i.e. the variables φ and ρ of the Hough transform. The latter two values are scaled by 256, i.e. they have the fixpoint integer format of 24.8 .

strength, like value is the number of pixels for the line multiplied with their grey-value, but it takes into account all pixels in a stripe with width = LineWidth in the direction phi ± delta_phi. It is therefore a better characterization of the line. cx, cy and b are the parameters for the line in the normalized vector form defined by $ cx * x + cy * y - b = 0 $.

The origin of the coordinate system is located at the upper left corner of the image variable src, like usual for most functions, whereas the origin for phi and rho is right in the middle of src.

The line-list is sorted by the parameter value, highest value first.

We recommend using only the output parameters strength, cx, cy and b. The parameters value, phi and rho are more for internal use inside the function. If the user selects the chi-square bestfit feature, this also influences only cx, cy and b.

If the user prefers the list to be sorted according to their strength, this can be accomplished using HoughSortLine().


Data Structure Documentation

◆ HoughControl

struct HoughControl
Data Fields
I32 HoughMode

Hough operating mode = 0-3

I32 LineNumber

number of lines for output

I32 delta_phi

phi tolerance

I32 MinPix

threshold for number of pixels

I32 LineWidth

width of lines to be searched

I32 bestfit

bestfit line flag 1=bestfit

struct hlstruct * maxptr

pointer to active lines list

struct hlstruct * empty

pointer to empty line list

I32 sorting

sorting method, 0=none

◆ HLine

struct HLine
Data Fields
struct hlstruct * next

pointer to next element in list

I32 state

internal state

I32 value

line detection value

I32 phi

line angle

I32 rho

distance from center of image

I32 strength

line detection strength

F32 cx

float cx, cy, b-parameters for

F32 cy

float line in normalized

F32 b

float vector form

Function Documentation

◆ HoughDefaults()

void HoughDefaults ( HoughControl Control)

This function sets default values for the Hough transformation. The parameters - or some of them - may be overwritten later on by individual settings. Especially LineNumber may be chosen to be much higher since it also counts internal lines that are considered but not output. Be sure to avoid changing of the parameters during the Hough detection process consisting of functions HoughTransform(), FindHoughLine(), HoughSortLine() since this may corrupt data integrity

The parameters are set as follows:

control->HoughMode = 0;
control->LineNumber = 100;
control->delta_phi = 5;
control->MinPix = 5;
control->LineWidth = 5;
control->bestfit = 0;
control->sorting = -HL_STRENGTH; // minus for ascending sorting
Parameters
Controlsource image (IMAGE_VECTOR or IMAGE_GREY)

◆ HoughCalcDx()

I32 HoughCalcDx ( image src)

This function calculates the horizontal size of the hough image by the following formula:

HoughDx = 1 + (I32)sqrtf((float)(dx*dx + dy*dy));

The size is rounded up to the next even number. The minimum horizontal size is 96.

Parameters
srcSource Image.
Returns
dx For Hough Image.

◆ HoughInit()

I32 HoughInit ( )

This function allocates and initializes a sine table needed for doing the Hough transform. Memory should be deallocated using function HoughDeinit().

Memory Consumption
160 Bytes of Heap Memory.
See also
HoughDeinit().
Return values
ERR_MEMORYif Memory Allocation Fails.
ERR_NONEOn Success.

◆ HoughInit2()

I32 HoughInit2 ( HoughControl Control)

The function allocates and initializes memory for storing lines needed by the Hough transform. Memory should be deallocated using the function HoughDeinit2().

Memory Consumption
(2 * Control->LineNumber * sizeof(HLine)) Bytes of Heap Memory.
See also
HoughDeinit2().
Return values
ERR_MEMORYif Memory Allocation Fails.
ERR_NONEOn Success.

◆ HoughDeinit()

void HoughDeinit ( )

This function essentially calls byte_free() to release the memory for the sine table used by the Hough transform. This should be done before a function returns to the operating system.

See also
HoughInit().

◆ HoughDeinit2()

void HoughDeinit2 ( HoughControl Control)

This function essentially calls byte_free() to release the memory for the Hough lines. This should be done before a function returns to the operating system, but it can also be done before setting up a new line memory using HoughInit2().

See also
HoughInit2().

◆ HoughTransform()

I32 HoughTransform ( image src,
image hough32,
HoughControl control 
)

This function calculates the Hough Transform for the source image src. The 32 Bit image hough32 is the output of the function. Operating modes are selected with control. The source image (should be edge image) is Hough-transformed (analyzed for lines). The resulting Hough image hough32 must be of type IMAGE_GREY32 and must have the following format: Dst32->dx = HoughCalcDx(Src), and Dst32->dy = 128 or 256 depending on the HoughMode selected.

It is recommended to use a vector image as Src since this provides a substantial speed improvement.

Parameters
srcImage Variable of Type IMAGE_GREY or IMAGE_VECTOR.
hough32Hough Accumulator Image of Type IMAGE_GREY32.
controlControl Struct; the following Parameters used for this Function:
  • HoughMode Operating Mode, Must be 0 or 3.
  • delta_phi ± Angular Detection Tolerance in Units of 1.4 Degrees.

The size of hough32 depends on the size of the input image:

$ \texttt{hough32.dx} = \sqrt{ \texttt{src.dx}^2 + \texttt{src.dy}^2} + 1, $

$ \texttt{hough32.dy} = 128. $

The value of hough32->dx is then rounded to the next higher even number. For convenience, we provide the function HoughCalcDx() which returns the horizontal hough image size for a given source image. It is recommended to set HoughMode to 0 and to use an image of type IMAGE_VECTOR. This allows you to make use of the parameter delta_phi and also results in a considerable speed advantage. Setting HoughMode to 3 or using an image of type IMAGE_GREY as input, automatically sets delta_phi to 64 (= +/- 64), essentially switching off the angular tolerance feature.

The function requires some tables for the calculation which can be allocated and initialized using the function HoughInit(); This function returns the standard error code. To deallocate the memory, the function HoughDeinit() should be used.

HoughTransform() also works, if HoughInit() is not called beforehand. It does the memory allocation and initialisation, but this may take some time, the first time the function is called, so the user might like to do the initialisation at the time when the program starts to guarantee equal processing times.

HoughTransform() returns the standard error code. An error is detected when:

Return values
ERR_TYPEIf the Image Variables do not have the proper Type.
ERR_FORMATIf hough32->dx < HoughCalcDx(src).
ERR_FORMATIf hough32->dy ≠ 128.
ERR_MEMORYIf the Function is out of Memory.
Memory Consumption
(640 + 4 * src->dx) Bytes, including HoughInit().
See also
FindHoughLine().

◆ FindHoughLine_PtrList()

I32 FindHoughLine_PtrList ( image hough32,
image grad,
HoughControl Control,
SPtrList lines 
)

This function searches the 32 Bit image hough32 for peaks representing lines in the original image grad. hough32 should be the result of the function HoughTransform(). Operating modes are selected with control.

The function requires some heap memory for the storage of the line descriptors and for some tables. The memory allocation and initialization should be done using the functions HoughInit() and HoughInit2().

Be sure to set the control struct control before calling HoughInit2(), since the amount of memory allocated, depends on the parameter control->LineNumber.

To deallocate the memory, the functions HoughDeinit() and HoughDeinit2() should be used.

FindHoughLine_PtrList() also works, if HoughInit() and HoughInit2() is not called beforehand. It does the memory allocation and initialization, but this may take some time when the function is called for the first time, so the user might like to do the initialization at the time when the program starts to guarantee equal processing times.

The function outputs a pointer list SPtrList *lines containing pointers to the individual line descriptors, for example, PtrList_getPtr() returns a (HLine *). The list is sorted according to the "sorting" field in the HoughControl struct.

FindHoughLine_PtrList() returns the standard error code. An error is detected when:

Return values
ERR_TYPEif the image variables do not have the proper type.
ERR_FORMATif hough32->dx < HoughCalcDx(grad).
ERR_FORMATif hough32->dx is odd.
ERR_FORMATif hough32->dx < 96.
ERR_FORMATif hough32->dy ≠ 128.
ERR_MEMORYif the function is out of memory.
ERR_PARAMif parameters are out of range.

The function has two internal error states which it may return on occasion:

Return values
ERR_HOUGH0an internal out-of-memory state. In this case, it might help to increase the value of Control->LineNumber.
ERR_HOUGH1a maximum iteration error. This error can only occur, if the control-struct is inconsistent for the functions HoughTransform() and FindHoughLine() or otherwise some tables have been damaged.
Remarks
FindHoughLine_PtrList() changes the contents of hough32.
Parameters
hough32Hough Image of type IMAGE_GREY32 as Source Image.
gradOriginal Image with Lines in it (IMAGE_GREY or IMAGE_VECTOR), May be a Grey-Valued Image or (Recommended) Binary-Valued.
ControlThe Hough Control Struct.
linesPointer List with Pointers to the individual Line Descriptors, (HLine *).
Returns
Standard Error Code.
See also
FindHoughLine().

◆ FindHoughLine()

I32 FindHoughLine ( image hough32,
image grad,
HoughControl Control 
)

This function searches the 32 Bit image hough32 for peaks representing lines in the original image grad. hough32 should be the result of the function HoughTransform(). Operating modes are selected with control.

The function requires some heap memory for the storage of the line descriptors and for some tables. The memory allocation and initialization should be done using the functions HoughInit() and HoughInit2().

Be sure to set the control struct control before calling HoughInit2(), since the amount of memory allocated, depends on the parameter control->LineNumber.

To deallocate the memory, the functions HoughDeinit() and HoughDeinit2() should be used.

FindHoughLine() also works, if HoughInit() and HoughInit2() is not called beforehand. It does the memory allocation and initialization, but this may take some time when the function is called for the first time, so the user might like to do the initialization at the time when the program starts to guarantee equal processing times.

The function outputs a chained list of line descriptors with the pointer (Hline *) control->maxptr pointing to the start of the list. The list is sorted according to the "sorting" field in the HoughControl struct.

FindHoughLine() returns the standard error code. An error is detected when:

Return values
ERR_TYPEif the image variables do not have the proper type.
ERR_FORMATif hough32->dx < HoughCalcDx(grad).
ERR_FORMATif hough32->dx is odd.
ERR_FORMATif hough32->dx < 96.
ERR_FORMATif hough32->dy ≠ 128.
ERR_MEMORYif the function is out of memory.
ERR_PARAMif parameters are out of range.

The function has two internal error states which it may return on occasion:

Return values
ERR_HOUGH0an internal out-of-memory state. In this case, it might help to increase the value of Control->LineNumber.
ERR_HOUGH1a maximum iteration error. This error can only occur, if the control-struct is inconsistent for the functions HoughTransform() and FindHoughLine() or otherwise some tables have been damaged.
Remarks
FindHoughLine() changes the contents of hough32.
It is recommended to use the similar function FindHoughLine_PtrList() instead
Parameters
hough32Hough Image of type IMAGE_GREY32 as Source Image.
gradOriginal Image with Lines in it (IMAGE_GREY or IMAGE_VECTOR), May be a Grey-Valued Image or (Recommended) Binary-Valued.
ControlThe Hough Control Struct.
Returns
Standard Error Code.
See also
FindHoughLine_PtrList().

◆ FindLines()

I32 FindLines ( image ImgVec,
HoughControl Control,
I32 NrLines 
)

This function searches for lines in the image ImgVec. ImgVec is supposed to be a gradient image (IMAGE_VECTOR) but it can also be an image of type IMAGE_GREY with less performance.

steps for finding the lines:

(1) HoughTransform() (2) FindHoughLine() (3) sort the lines for HL_STRENGTH (4) calculate number of lines with HoughRank()

The HoughControl parameters must be set beforehand. The Hough system should also be initialized before calling the function

Parameters
ImgVecpointer to source (vector or grey) image
ControlThe Hough Control struct
NrLines(output) pointer to the number of lines found
Returns
standard error code

◆ FindSingleLine()

I32 FindSingleLine ( image hough32,
image grad,
HoughControl Control,
I32  phi,
I32  phi_range,
HLine line 
)

This function searches the 32 Bit image hough32 for the maximum peak representing the dominant line in the original image grad. hough32 should be the result of the function HoughTransform().

Operating modes are selected with control.

The function requires some heap memory for the storage of some tables. The memory allocation and initialization should be done using the function HoughInit().

To deallocate the memory, the function HoughDeinit() should be used.

FindSingleLine() also works, if HoughInit() is not called beforehand. It does the memory allocation and initialization, but this may take some time when the function is called for the first time, so the user might like to do the initialization at the time when the program starts to guarantee equal processing times.

It is possible to restrict the search to lines within a certain range of angles. This is done using

Parameters
phiand
phi_rangewith an angle-step resolution of 1.4 degrees. This search restriction also results in a faster execution of the function.

The function outputs a Hough line pointer

Parameters
lineFindSingleLine() returns the standard error code. An error is detected when:
Return values
ERR_TYPEif the image variables do not have the proper type.
ERR_FORMATif hough32->dx < HoughCalcDx(grad).
ERR_FORMATif hough32->dx is odd.
ERR_FORMATif hough32->dx < 96.
ERR_FORMATif hough32->dy ≠ 128.
ERR_MEMORYif the function is out of memory.
ERR_PARAMif parameters are out of range.

If the function does not find a line with the desired properties it returns

Return values
ERR_SINGULAR.If it did successfully find a line it returns
ERR_NONE.
Remarks
FindSingleLine() does not changes the contents of hough32.
Parameters
hough32Hough Image of type IMAGE_GREY32 as Source Image.
gradOriginal Image with Lines in it (IMAGE_GREY or IMAGE_VECTOR), May be a Grey-Valued Image or (Recommended) Binary-Valued.
ControlThe Hough Control Struct.
phiexpected line angle (255 is equivalent to 359 deg.)
phi_rangetolerance for phi
lineline output
Returns
Standard Error Code.
See also
FindHoughLine().

◆ HoughRank()

I32 HoughRank ( HLine listptr,
I32  offset,
I32  value 
)

With this function it is possible to get the number of lines with a value above a certain threshold, e.g. the number of lines above a certain strength.

Please note, that the lines have to be sorted first with the function HoughSortLine() according to the selected criterion.

HoughRank searches for the first element in the list with a value less than "value". rank is the number of elements in the list with a value higher than or equal to "value"

vclib.h provides a number of predefined values for offset that you can choose from:

#define HL_VALUE (2)
#define HL_PHI (3)
#define HL_RHO (4)
#define HL_STRENGTH (5)

For the struct values that are always positive, namely line->value and line->strength, calling HoughRank( , , 0) will return the total number of lines in the list.

as an example the rank is computed according to line strength:

HoughSortLine(&(control->maxptr), HL_STRENGTH);
count = HoughRank(control->maxptr, HL_STRENGTH, 200);
Parameters
listptrpointer to the line list
offsetelement number in the struct
valuevalue for comparison
Returns
number of points in list (positive value) or standard error (negative)

◆ HoughSortLine()

void HoughSortLine ( HLine **  listptr,
I32  offset 
)

With this function the user can sort the line list according to different sorting criteria. listptr is a handle for the line list and offset is the element number in the struct. 'vclib.h' provides a number of predefined values for offset that you can choose from:

#define HL_VALUE (2)
#define HL_PHI (3)
#define HL_RHO (4)
#define HL_STRENGTH (5)

as an example the line list is sorted according to line strength:

HoughSortLine(&(control->maxptr), HL_STRENGTH);

Please note, that HoughSortLine() might change the value of control->maxptr if it needs to point to a different first element in the list.

Parameters
listptrpointer to the line list
offsetelement number in the struct
Memory Consumption
None.
See also
HoughRank().

◆ GetHoughPixels()

I32 GetHoughPixels ( image Src,
HLine line,
HoughControl Control,
I32 xy 
)

The Hough Transform can detect lines in an image which can consist of an arbitrary set of pixels on a line. This function returns an exact list of the pixels which contribute to the Hough line.

Be sure to provide a large enough buffer for xy since the number of points found can be quite considerable, especially for high "width" values.

Parameters
SrcSource Image (IMAGE_VECTOR or IMAGE_GREY).
lineLine Descriptor with Values for phi, cx, cy, b.
ControlHough Control Struct, Always Use Same Values for All Functions.
xyxy Coordinate List (Result).
Returns
Number of Points in List (Positive Value) or Standard Error Code (Negative).