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?
Signal Processing Stack Exchange is a question and answer site for practitioners of the art and science of signal, image and video processing. It only takes a minute to sign up.Sign up to join this community
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.
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:
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.