From: Kim Madsen <kbm@optical.dk>
Subject: Re: Hough Transform Help please
Date: 19 Nov 1999 00:00:00 GMT
Message-ID: <812uuq$65d$1@nnrp1.deja.com>
References: <80v7ko$lvn$1@nclient15-gui.server.virgin.net> <38343239.14015D69@home.com>
X-Http-Proxy: 1.0 x41.deja.com:80 (Squid/1.1.22) for client 194.192.22.33
Organization: Deja.com - Before you buy.
X-Article-Creation-Date: Fri Nov 19 07:41:14 1999 GMT
X-MyDeja-Info: XMYDJUIDkimbomadsen
Newsgroups: sci.image.processing
X-Http-User-Agent: Mozilla/4.0 (compatible; MSIE 4.01; Windows NT)

Hi,

Its actually very simple,

You have two known variables x,y and two unknown , r and theta.

You do:

// For all rows in image.
for y:=0 to ImageHeight-1 do
begin

   // For all pixel in one row.
   for x:=0 to ImageWidth-1 do
   begin

      // Is there a point there or not. If not, just skip the pixel.
      if IsPoint[x,y] then
      begin
           // Now you need to iterate for one of the unknown variables,
           // theta, to be able to determine the other unknown, r.
           for theta:=0 to 360-1 do
           begin
                r:=x*cos(theta*PI/360) + y*sin(theta*PI/360);

                // Plot the finding (theta,r) into an array.
                // Ignore negative values... trust me... its ok!
                if r>=0 then Inc(HoughArray[theta,r]);
           end;
      end;
   end;
end;

The size of the array can be calculated as:
HoughArray:Array [MaxTheta,MaxR] of integer;
where MaxTheta due to the loop naturally is 360 (we determine that
ourselves)
and MaxR=Sqrt(ImageHeight*ImageHeight + ImageWidth*ImageWidth)

         /--------------------------
MaxR=   /           2             2
       / ImageHeight  + ImageWidth
      V

best regards

Kim Madsen
kbm@optical.dk


In article <38343239.14015D69@home.com>,
  brian crowley <bcrow@home.com> wrote:
> Martin Philpott wrote:
>
> > I understand that the Hough transform is the conversion from x,y
space to
> > r,theta space. My question is from where do you measure r and
theta? It
> > makes a difference!
>
> I haven't actually programmed this myself but my understanding is
that you
> are trying to correlate the angle of the maximum gradient of each
pixel with
> the adjacent pixels.  In practice, the gradients for some subsample
of the
> angles,
> maybe 4 or 8, is determined and the maximum chosen.
>
> >
> > Do you consider the problem from the centre of the image or from
one corner
> > or from all points within the image?
>
> All the pixels are being considered with themselves as the origin,
but part of
> the algorithm is throwing away all those pixels with no "significant"
> gradients,
> that is picking out pixels that are part of a line from foreground or
> background
> pixels.
>
> >
> > Having decided on this what do you do with a grey scale image?
>
> Calculate gradients with one value, instead of worrying about multiple
> channels.
>
> >
> > Do you just put the value of the pixel at the new r, theta position?
>
> I think the goal is to abstract lines from rasters.
>
> >
> > And if you do this surely there are numerical errors in the Hough
tansform
> > unless you us floating point numbers ? Perhaps I need double
precision
> > numbers!
>
> Maybe not.
>
> >
> > Can you help here?
> > martin.philpott@virgin.net
> > Thankyou for your time.
>
> Good luck,
> Brian C.
>
>

--
Kim Madsen
kbm@optical.dk