|
VCLib Documentation
6.12.2
|
 |
|
VCLib Documentation
6.12.2
|
|
Functions | |
| I32 | HoughCDefaults (HCirclePar *HCP) |
| Set Hough Circle Parameters to Default. More... | |
| I32 | InitHoughCircle (HCirclePar *HCP) |
| Initialize Hough Circle Transform. More... | |
| I32 | FindHoughCircle (image *Hough32, HCirclePar *HCP, HCircle *Circle) |
| Find Circles in Hough Circle Transform. More... | |
| I32 | DeinitHoughCircle (HCirclePar *HCP) |
| Deinitialize Hough Circle Transform. More... | |
| I32 | FindMaxImage8 (image *src8, I32 *ix, I32 *iy) |
| Locate and Get Maximum Value of 8 Bit Image. More... | |
| I32 | FindMaxImage16 (image *Src16, I32 *ix, I32 *iy) |
| Locate and Get Maximum Value of 16 Bit Image. More... | |
| I32 | FindMaxImage32 (image *Src32, I32 *ix, I32 *iy) |
| Locate and Get Maximum Value of 32 Bit Image. More... | |
Similar to the Hough Transform for lines, it is possible to define a Hough Transform for circles. The parameter space would be three-dimensional, since a circle is defined by three parameters: (x0, y0) and r. This adds another order of magnitude for the memory space and computation time requirements. In order to reduce memory space and computation time, we calculate the center (x0, y0) of the circle first. The radius is calculated internally as a second step. We also find only one circle at a time not a multiple, so it is up to the user to call the function as long as necessary to locate all the relevant circles. This ensures rapid execution times.
Like the Hough Transform for lines, we use a 2-dimensional accumulator space and vote for the most likely centerpoints of circles. In most cases the accumulator has the same dimensions as the original image. The Hough-space may however be larger, which is important, if the user wants to locate circles with centerpoints outside the active field.
Like the Hough Transform for lines, it is not important that the structures in the images are connected full circles. They could be any part of a circle, like a half- or quatercircle, fully or partly connected. However, unlike the transform for lines, it is not possible to detect circles consisting only of single isolated pixels. Please also keep in mind, that if you only have a small segment of a circle smaller than a quatercircle, the centerpoint must be extrapolated from the data, so centerpoint and radius will have poor accuracy.
The Hough Transform for circles uses the following twodimensional accumulator space:
| Parameter | Description | Dimension | Size (See Text) | Origin |
|---|---|---|---|---|
| x0 | Centerpoint x-Position | Horizontal | dx (Default) | Left |
| y0 | Centerpoint y-Position | Vertical | dy (Default) | Top |
Hough space may be smaller or larger than the source image to extend or restrict the search area!
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 for circles can be applied to an image using the function HoughCircleTransform().
The function increments the bins in Hough space for the possible centerpoints of potential circles by the grey value of the pixel (x, y).
If there are circular structures in the image, there will be corresponding peaks in the accumulator space with a height (peak strength) proportional to the number of pixels on the circle. It does not matter if the circle is solid, or randomly distributed along its way, only the number of pixel counts for its representation in accumulator space (Hough space). Isolated pixels, however, cannot contribute to the accumulator space.
The second main task is to identify peaks in Hough Space. This is done by the function FindHoughCircle().
The following shows the control struct which selects the features of the Hough Transform and the circle finding algorithm:
The parameters of this struct should be kept constant throughout the detection cycle including the initialization. Since additional internal parameters are used, the function DefaultParHoughCircle() must be called first to initialize the struct to the default parameters. The above parameters may then be changed to taylor the transform to specific requirements.
The function InitHoughCircle() must be called after the struct has been set to the correct values. InitHoughCircle() initializes some tables depending on the values of MinRad and MaxRad, the minimum and maximum radius defining the range of circles to be searched for.
(HoughX, HoughY) is the relative position of the Hough space in respect to the pixel space. The default value is (0, 0). Together with same dimensions for pixel- and Hough space, this results in the full coordinate range for the centerpoints of the circle. However, the centerpoints of the circle may easily lie outside the original pixel range. In this case, the Hough space may be made larger and the vector (HoughX, HoughY) should have negative values for HoughX and/or HoughY.
On the other hand, if it is clear from the application, that the centerpoints are restricted to a certain range, the Hough space may be made smaller with the positive vector (HoughX, HoughY) pointing to the left upper corner of the detection range.
This results in faster processing times since a smaller Hough Space must be searched.
The center point of the circle lies on a line perpendicular to the tangent running through the intersection point of the tangent and the circle. With this in mind, we can calculate the tangent for each edge point in the image. The Hough Space would be the coordinates (x0, y0) for the center point just like the image space used for the edge image. We then draw a line in this Hough Space, perpendicular to the calculated edge slope, where we add 1 to each accumulator element.
When enough edge points have been evaluated, it becomes clear, that the maximum value in the Hough Space corresponds to some kind of center point for a circle, quite similar to the case of the Hough Transform for lines. This method quite reliably gives us the center point for the circle. It doesn’t give us at all, however, any indication of its radius. When we have the center point, we therefore scan around it, computing a second histogram summing up the number of edge pixels that are in a certain radius around the center. Again the maximum value of this diagram will be taken as a value for the radius.
The above method works fine if there is a maximum in Hough Space that can be clearly identified. If there is an extended plateau with equal or almost equal accumulator values, this method is bound to fail. For the second histogram (number of pixels vs. radius) this could be the case for a bunch of concentric circles quite close to each other. At least, the method would find one of the circles, which is what it is supposed to produce. The situation gets worse, if the circles are only approximately concentric. This means they have different radii and also slightly different center points. This results in a fairly extended region in the Hough Space for the center points, where no correct maximum can be identified anymore.
| I32 HoughCDefaults | ( | HCirclePar * | HCP | ) |
This function sets all the internal and external parameters of the control structure HCP. The function must be executed before any other function for the Hough Circle Transform may be called.
The following values for the external parameters are set:
The external parameters may be changed to some appropriate value afterwards.
| I32 InitHoughCircle | ( | HCirclePar * | HCP | ) |
This function basically allocates and sets some tables necessary for the Hough Circle Transform. The function may take several hundred milliseconds depending on the value of MaxRad. Therefore it is recommended to call it only once at the start of the user program. Please be aware, that depending on the value of MaxRad the function may require some memory space. For the same reason, the function must be called whenever the value of MaxRad changes!
MaxRad +1)*(MaxRad +1) + 640) Bytes of Heap Memory. This function searches the 32 Bit image Hough32 for peaks representing circles in the original image ImgVec. Hough32 should be the result of the function HoughCircleTransform(). Operating modes are selected with HCP. The result is placed in the struct Circle. Unlike the function FindHoughLines(), this function returns the result one by one, i.e. it must be called several times to find all circles in an image.
| Hough32 | Hough Accumulator Image of Type IMAGE_GREY32. |
| HCP | Control Struct. |
| Circle | Result Struct. |
The result struct has the following definition:
The circle parameters are available both in integer (I32) and floating-point format. The floating-point format is quite helpful when using the bestcircle approximation (bestfit=1). The parameter strength gives an indication of the amount of pixels in the image belonging to the circle found. Like for the linear Hough Transform, it is more a rough estimate, a proportional value changing with the number of pixels contributing to the circle than an absolute pixel-counter. The sequence of circles calculated by this function when called multiple times is only partly dependent on the strength parameter. First, the function searches for the point in Hough space with the largest value, representing the centerpoint most frequently used. At this point it is, however, not clear if the large value comes from a large circle with many pixels or several smaller concentric circles with fewer pixels each. After the function has located the centerpoint, it then calculates the radius of the circle with the best pixel coverage, i.e. the best ration of pixels per radius.
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 function InitHoughCircle(). To deallocate the memory, the function DeinitHoughCircle() should be used.
| ERR_TYPE | If the Image Variables do not have the proper Type. |
| ERR_MEMORY | If the Function is out of Memory. |
| ERR_PARAM | If MinRad is out of Range. |
Hough32.| I32 DeinitHoughCircle | ( | HCirclePar * | HCP | ) |
This function releases memory space used for the tables and other structures previously allocated by the functions InitHoughCircle() and HoughCircleTransform().
This function locates the maximum absolute value in a 8 Bit image. finds the location and the value of the maximum in an image. The image must be of type IMAGE_GREY or compatible.
| [in] | src | source image of type IMAGE_GREY. |
| [out] | ix,iy | coordinates of maximum or NULL |
This function locates the maximum absolute value in a 16 Bit image.
| [in] | Src16 | source image of type IMAGE_GREY16. |
| [out] | ix,iy | coordinates of maximum or NULL |
This function locates the maximum absolute value in a 32 Bit image. This may be helpful for finding lines or circles in Hough space. It also gives an indication for the range of values in Hough space. The Vision Components Hough Transform does not rely on this function for the localization, but uses more sophisticated algorithms for this purpose. The function returns the maximum value and stores its position in (ix, iy).
| [in] | Src32 | source image |
| [out] | ix,iy | coordinates of maximum or NULL |