pxjim@althea.UUCP (James Conallen) (07/23/89)
Hi there,
I have what i hope is an easy request for a solution to an image
representation problem. I am currently working on some image processing
algorithms, specifically edge detection. I need to model a straight
line in a rectangular coordinate system. A `C' (or any other general
purpose language) function without if's, that can represent a line
in all orientations would be nice. Tha angle and shortest distance to
the origin is known. What is needed is all the X and Y points that lie
along that line. If it helps the line can be assumed to be passing
through the origin (although it would be better to have a gen purose
routine for any line). The obvious problem I am having is the infinite
slope possible with y = mx + b as the angle approaches pi/2.
Any suggestions? - I would also appreciate any help reguarding the most
efficient way to create/represent synthetic images in a rectangular
matrix. Send replys to pxjim@widener.BITNET, or to this account.
-jc
P.S. this is my first posting and i'm not quite sure what i'm doing,
pardon any inconvience.
fleming@balboa (Dennis Paul Fleming) (07/27/89)
In article <203@althea.UUCP> pxjim@althea.UUCP (James Conallen) writes: > I have what i hope is an easy request for a solution to an image > representation problem. I am currently working on some image processing > algorithms, specifically edge detection. I need to model a straight > line in a rectangular coordinate system. A `C' (or any other general > purpose language) function without if's, that can represent a line > in all orientations would be nice. Tha angle and shortest distance to > the origin is known. What is needed is all the X and Y points that lie > along that line. If it helps the line can be assumed to be passing > through the origin (although it would be better to have a gen purose > routine for any line). The obvious problem I am having is the infinite > slope possible with y = mx + b as the angle approaches pi/2. > The solution that comes to mind first is the Hough transform. The basic idea is to parametrize the line by the equation r = x * cos(theta) + y * sin(theta). This mapping transforms straight lines into points, points into sinusoidal curves. The basic algorithm consists of finding each point in the image space and mapping it onto the corresponding sinusoid in Hough space. The hough space may be limited to a range of 2 * pi for theta and the maximum distance a point can be from the origin of the image for r. Using this mapping colinear points will map onto sinusoids which cross at a particular (r, theta) value. This value corresponds to a line from the origin normal to the detected line. Its distance to the detected line is r and the angle from the origin is theta. |\ | \ | \ | \<- line that you want characterized | \ | \ | / \<- pretend this angle is 90 degrees | r/ \ | / \ | / \ |/ theta \ ------------------ This technique is derived from a patent by Hough, but was modified by Duda and Hart "Use of the Hough Transform to Detect Lines and Curves in Pictures", Communications of ACM, vol 15, pp 11-15, Jan 1972. The beauty of this approach is that, given proper restrictions on r and theta, the method is one to one and onto. I hope I haven't confused you. The technique is easily explained with a few illustrations which are difficult on a character terminal. Duda and Hart's paper is readable, so I'll leave you with that. good luck