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... | |
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.
The accumulator space is 2-dimensional and has the following features:
Parameter | Description | Dimension | Size (See Text) | Origin |
---|---|---|---|---|
ρ | Distance from Origin | Horizontal | ![]() | 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
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:
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.
LineWidth
defines a channel of a certain width, where the pixels in the original image vote for this line in Hough space.delta_phi
is the amount of angular tolerance for the line detection.
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:
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:
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 .
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().
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 |
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 |
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 | source image (IMAGE_VECTOR or IMAGE_GREY) |
This function calculates the horizontal size of the hough image by the following formula:
The size is rounded up to the next even number. The minimum horizontal size is 96.
src | Source Image. |
I32 HoughInit | ( | ) |
This function allocates and initializes a sine table needed for doing the Hough transform. Memory should be deallocated using function HoughDeinit().
ERR_MEMORY | if Memory Allocation Fails. |
ERR_NONE | On Success. |
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().
ERR_MEMORY | if Memory Allocation Fails. |
ERR_NONE | On Success. |
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.
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().
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.
src | Image Variable of Type IMAGE_GREY or IMAGE_VECTOR. |
hough32 | Hough Accumulator Image of Type IMAGE_GREY32. |
control | Control Struct; the following Parameters used for this Function:
|
The size of hough32
depends on the size of the input image:
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:
ERR_TYPE | If the Image Variables do not have the proper Type. |
ERR_FORMAT | If hough32->dx < HoughCalcDx(src ). |
ERR_FORMAT | If hough32->dy ≠ 128. |
ERR_MEMORY | If the Function is out of Memory. |
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:
ERR_TYPE | if the image variables do not have the proper type. |
ERR_FORMAT | if hough32->dx < HoughCalcDx(grad ). |
ERR_FORMAT | if hough32->dx is odd. |
ERR_FORMAT | if hough32->dx < 96. |
ERR_FORMAT | if hough32->dy ≠ 128. |
ERR_MEMORY | if the function is out of memory. |
ERR_PARAM | if parameters are out of range. |
The function has two internal error states which it may return on occasion:
ERR_HOUGH0 | an internal out-of-memory state. In this case, it might help to increase the value of Control->LineNumber. |
ERR_HOUGH1 | a 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. |
hough32
.hough32 | Hough Image of type IMAGE_GREY32 as Source Image. |
grad | Original Image with Lines in it (IMAGE_GREY or IMAGE_VECTOR), May be a Grey-Valued Image or (Recommended) Binary-Valued. |
Control | The Hough Control Struct. |
lines | Pointer List with Pointers to the individual Line Descriptors, (HLine *). |
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:
ERR_TYPE | if the image variables do not have the proper type. |
ERR_FORMAT | if hough32->dx < HoughCalcDx(grad ). |
ERR_FORMAT | if hough32->dx is odd. |
ERR_FORMAT | if hough32->dx < 96. |
ERR_FORMAT | if hough32->dy ≠ 128. |
ERR_MEMORY | if the function is out of memory. |
ERR_PARAM | if parameters are out of range. |
The function has two internal error states which it may return on occasion:
ERR_HOUGH0 | an internal out-of-memory state. In this case, it might help to increase the value of Control->LineNumber. |
ERR_HOUGH1 | a 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. |
hough32
. hough32 | Hough Image of type IMAGE_GREY32 as Source Image. |
grad | Original Image with Lines in it (IMAGE_GREY or IMAGE_VECTOR), May be a Grey-Valued Image or (Recommended) Binary-Valued. |
Control | The Hough Control Struct. |
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
ImgVec | pointer to source (vector or grey) image |
Control | The Hough Control struct |
NrLines | (output) pointer to the number of lines found |
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
phi | and |
phi_range | with 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
line | FindSingleLine() returns the standard error code. An error is detected when: |
ERR_TYPE | if the image variables do not have the proper type. |
ERR_FORMAT | if hough32->dx < HoughCalcDx(grad ). |
ERR_FORMAT | if hough32->dx is odd. |
ERR_FORMAT | if hough32->dx < 96. |
ERR_FORMAT | if hough32->dy ≠ 128. |
ERR_MEMORY | if the function is out of memory. |
ERR_PARAM | if parameters are out of range. |
If the function does not find a line with the desired properties it returns
ERR_SINGULAR. | If it did successfully find a line it returns |
ERR_NONE. |
hough32
.hough32 | Hough Image of type IMAGE_GREY32 as Source Image. |
grad | Original Image with Lines in it (IMAGE_GREY or IMAGE_VECTOR), May be a Grey-Valued Image or (Recommended) Binary-Valued. |
Control | The Hough Control Struct. |
phi | expected line angle (255 is equivalent to 359 deg.) |
phi_range | tolerance for phi |
line | line output |
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:
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:
listptr | pointer to the line list |
offset | element number in the struct |
value | value for comparison |
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:
as an example the line list is sorted according to line 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.
listptr | pointer to the line list |
offset | element number in the struct |
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.
Src | Source Image (IMAGE_VECTOR or IMAGE_GREY). |
line | Line Descriptor with Values for phi, cx, cy, b. |
Control | Hough Control Struct, Always Use Same Values for All Functions. |
xy | xy Coordinate List (Result). |