✨Hough Transform

The purpose of Hough Transform is to find imperfect instances of objects within a certain class of shapes by a voting procedure. This voting procedure is carried out in a parameter space, from which object candidates are obtained as local maxima in a so-called accumulator space that is explicitly constructed by the algorithm for computing the Hough transform. -- Wikipedia

Linear Hough Transform

In short, hough transform detects edge line inside the image. How to do that?

Basic idea: We have a list of points after edge filter. For each point, we draw out all lines that pass through it and repeat this procedure for all points. Thus, the line all points have in commin determines an edge.

We make use of Hough/parameter space to find these lines. Consider a edge point $(x_i, y_i)$, we denote a line equation $y_i=mx_i+c$ in image space. We can also write it in a different way: $c=-x_im+y_i$ in Hough space. Thus, a line in image space is transformed into a point in Hough space.

Image adapted from Medium.com

Thus, we realize that for the line that pass $(x_1,y_1), (x_2,y_2)$, we have $c=-x_0m+y_0, c=-x_1m+y_1$, that is a point $(m,c)$ inside the hough space. So, how to find the most likely parameters $(m,c)$ for the line in image space?

• Let each edge point in image space vote for a set of possible parameters in Hough space

• Accumulate votes in discrete set of bins; parameters with the most votes indicate line in image space.

However, usual parameter space (m,c) can take on infinite values, undefined for vertical edge lines, and it is difficult to implement. Thus, for computational efficiency, we use the Hesse normal form: $r= xcos(\theta)+ysin(\theta)$

pseudocode

1. Use a edge filter on top of the image to find all edge points

2. Create accumulator array $A(\theta,r)=0, \forall \theta,r$

3. Check each pixel to see if it is a edge points or not

4. If edge point, construct the set of lines pass this point ($\theta$=-90:90, compute correspond $r$)

   1. $A(\theta,r)=A(\theta,r)+1$

5. Repeat for the rest of points

6. Find local maxima in $A(\theta,r)$

function [himg, theta, r] = hough_trans(img)
% created by Jeanette Mumford 2/27/2017; 
% commits by vsingh Oct 5, 2021 and Sep 28, 2022; minor edits

% First, figure the max value for r (in positive direction). 
% This would be to the corner of the image (from the origin.  Solve using Pythagorean theorem
num_pos_r = ceil(sqrt(sum(size(img).^2)));

% we will store our values in himg...since r can be negative, we'll create
% an r-vector to keep track of what locations in himg correspond to the
% values of r and a theta vector that does the same

i_rng = size(img, 1);
j_rng = size(img, 2);

r = -1*num_pos_r:num_pos_r;
theta = 1:360;
himg=zeros(length(r), length(theta));
for i=1:i_rng
  for j=1:j_rng
    if img(i,j) > 0
      for ang=theta
        theta_loop=ang*pi/180; % change to radians
        r_loop=round((i*cos(theta_loop))+(j*sin(theta_loop)));
        theta_ind = find(theta == ang);
        himg(find(r_loop == r), theta_ind)=himg(find(r_loop == r), theta_ind)+1;
      end
    end
  end
end

Left: original image; Right: Image after edge detector

Linear Hough Transform Result

Circle Hough Transform

Instead of constructing lines through each edge pixel, we construct circles centered at these points. If a correct radius $r$ is chosen, the constructed circles will overlap at the center of the circle we want to identify. Thus, this time the accumulator matrix has 3 dimensions: $r,x,y$.

1. Use a edge filter on top of the image to find all edge points

2. Create accumulator matrix A=zeros([size(img),#radius])

3. For each edge (x,y)

   1. For each radius $r=r_1, r_2,...$

      1. For each $\theta=0,...,360$

         1. Calculate the candidate center point $(x',y')=(x+rcos(\theta), y+rsin(\theta))$

         2. $A(x',y',r)=A(x',y',r)+1$

Find the radius with largest length and that's the winning radius.

% parameters-
% image_width is the width of the input image that contains some circle edge we want to find
% image_height is the height of the input image that contains some circle edge we want to find
% radius_array is the array that contains several radius number that we want to try
% num_radius is the length of radius_array
function [optimal]=circleHoughTransform(image_width, image_height, radius_array, num_radius)
    % create a accumulator matrix
    accumulator=zeros(image_width,image_height,num_radius);
    radius=radius_array;
    % loop through all pixel
    for i=1:size(circleimg,1)
        for j=1:size(circleimg,2)
            % calculate circle only when the pixel is a edge point
            if circleimg(i,j)>0
                for rind=1:length(radius)
                    for angle=0:359
                        x=i+radius(rind)*cos(angle*pi/180);
                        y=j+radius(rind)*sin(angle*pi/180);
                        % round the x, y to be integer and within the image bound
                        if round(x)>0 && round(y)>0 && round(x)<=size(circleimg,1) ... 
                        && round(y)<=size(circleimg,2)
                            accumulator(round(x),round(y),rind)=accumulator(round(x),round(y),rind)+1;
                        end
                    end
                end
            end
        end
    end
    
    % find the best radius
    result=zeros(num_radius);
    for j=1:num_radius
        result(j)=max(max(accumulator(:,:,j)));   
    optimal=find(result==max(result));