I am trying to implement the generalized Hough transform in matlab. The algorithm requires the gradient direction at each point in the shape. How can I measure $ \phi $ as shown in the figure below?
$\begingroup$
$\endgroup$
1
-
$\begingroup$ Cross-link to post on SO: stackoverflow.com/questions/10176157/generalized-hough-r-table/… $\endgroup$– molaCommented Jun 7, 2012 at 16:17
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
6
Assuming you are using discrete inputs and that s(0..n-1) (or s(1...n) in Matlab) is an array of x,y points along the boundary of a 2d shape ...
Gradient(i) = (s(i).x, s(i).y) - (s(i-1).x, s(i-1).y)
Amplitude(i) = sqrt(Gradient(i).x^2 + Gradient(i).y^2)
Angle(i) = atan(Gradient(i).y / Gradient(i).x)
To make you calculations relative to (Xc,Yc) substract (Xc,Yc) from each point in s prior to calculations.
If your calculations are continuous, replace the above s(i)-s(i-1) with limit(s)/limit(sigma) and use the symbolic toolkit.
-
$\begingroup$ I have a list of all points (x,y) on the shape, but they are not in any particular order. This wouldn't work with that would it? $\endgroup$ Commented Apr 23, 2012 at 17:50
-
$\begingroup$ No, you would have to sort them, however, without information of the edges between them or the function that was used to create them or some additional information (e.g. that the shape in convex) you will not be able to sort them. Also, if the same rate along the boundary is not constant, you will have to divide by the distance between the points. $\endgroup$ Commented Apr 23, 2012 at 19:23
-
$\begingroup$ @Danny Varod How about in 3D? the magnitude i assumed it to be an extra component. How about the angle? Thanks. $\endgroup$ Commented Nov 16, 2013 at 8:06
-
$\begingroup$ @GaryTsui. In 2D the calculations are of (sub-)pixel amplitudes above a 2D domain (the calculations are 3D if your calculations are of the 3D colorspace above the 2D domain). In 3D you have to be more specific, are you calculating the shape of a mesh (3D gradients of the normal of the surface of the mesh), the color of the mesh (3D colorspace above the 3D mesh or 2D texture coordinates) or of a voxel shap (3D shapes made out of small 3D cubes which are the 3D equivalent of pixels)? $\endgroup$ Commented Nov 16, 2013 at 19:06
-
$\begingroup$ @Danny Varod, gradient and gray-scale. In this case, it would be the 3D magnitude and 3D direction? Thanks. $\endgroup$ Commented Nov 18, 2013 at 5:50
$\begingroup$
$\endgroup$
If the points are sorted or can be, by means of some contour-following, than the approach suggested above is fine. However, depending on noise and outliers, it may well be advisable to use a larger support-region, i.e. N points"left"/"right" of the point, and fit a line to those points using linear regression possibly with preceding outlier-rejection using RANSAC/MSAC. The resulting line-normal presents the estimated/approximated gradient-direction. Off course, higher order polynomials, i.e. quadratic or cubic, can be used for the fitting as well.
If the points are unsorted, the above approach could still be used by finding the nearest neighbors either by brute-force-search or by means of a suitable data-structure like, for example, kd-trees. The search-radius depends on the data, but can also be dynamically adjusted. Depending on the actual nature (distribution, constellation) of the points, the nearest-neighbor search might also allow to perform the contour-following, i.e. sorting of the points along the contour (sequence of points), see below.
In any case, with unsorted points, there's always the chance for ambiguity whenever the shape/contour comes close to itself - in particular, closer than the distance between neighbors on the contour. Clearly, nearest-neighbor-search picks up those points, which are not actual neighbors with respect to the shape/contour. Even worse are contour-crossings that would have to be accounted for in addition to all of the above. The gradient-direction at the crossing-point is undefined. Robust fitting using RANSAC/MSAC as suggested above could help with such ambiguities and crossing-detection by taking the outliers, if there are "plenty", and repeating the robust fitting step, then decide.
Just a suggestion along the lines of the above:
- Compute the approximate gradient-direction using the nearest neighbors and polynomial fitting for all points, keep the standard-deviation of the fit for each point.
- Find the point on the contour with the smallest standard-deviation. Hoping/Assuming that this means that all it's nearest neighbors are actual neighbors along the shape (?).
- Follow the contour using the nearest neighbors, gradient-directions and/or tangential directions making adjustments/corrections to the gradient-directions as necessary.
Essentially, the purpose of the last step is to enforce local smoothness for the gradient-directions, where applicable, i.e. not at crossings etc. Also, the last step effectively performs contour-following. Finally, depending on the range of the point-coordinates, it may be possible to simply render them into a binary image with appropriate resolution and use image-based contour-following directly. This might require to scale the points appropriately and keep a mapping between the original and image points. Also the contour-following might have to account for significant gaps, depending on the data. However, afterwards the connectivity of the points is known, and the neighbor-based approximation becomes relatively straightforward.
Hope that helps, kind regards, Derik.
