Hough Transform – Basic Shape Detection


The Hough Transform is a method to find shapes in an image. The classical transformation is initially designed to identify lines in the image. Later the transform extends to identify different kind of shapes such as circles, ellipses and even arbitrary objects. Hough’s transformation uses a voting scheme in a parameter space in a way that an “accumulator” is populated with present edge points. The voting procedure helps to improve the feature detection accuracy and overcome cases of missing or noisy feature parts. Тhe following steps briefly describe the Hough’s algorithm:

  • Extract edges using e.g. Sobel edge detector
  • Choose desired transformation e.g. line transform or circle transform
  • Iterate through the image and populate the accumulator using the transform from previous step
  • Search for the local maximum values inside the accumulator space

 


Hough Line Transform

A line that pass through a point x,y can be represented using the Polar coordinate system by the following equation:

hough_line_transformHough line transform

The equation above is used in a way that every significant edge pixel (e.g. x0,y0) is processed and plot all possible family of lines. Meaning that for each such point the prepared Polar accumulator (r, theta) is filled with calculated radius values at all possible angles. After the whole image is processed and the accumulator is filled, the last step is to find local maximums and retrieve the resulting lines. It should be noted that the returned lines do not contain any information about length and further processing is required to match the exact parts of the image with corresponding lines.


Hough Circle Transform

The math behind the Hough circle transform is similar to this used for lines detection described above. The voting accumulator cells are determined by the following equation:

x = R*cos(phi);
y = R*sin(phi);

Where R is the radius of the searched circles and phi is angle in radians from 0-2PI.

Hough Transform over Canvas2D

In order to optimize the algorithm execution and reduce needed time we use a pre-calculated lookup table (LUT) with x and y values respectively. The JavaScript code snippet below shows the lookup table creation:

 


// Compute the circle kernel (LUT)
	var kernel = [{x: ~~(r*Math.cos(0)), y: ~~(r*Math.sin(0))}];
	for (var i = 1; i < 380; i++){
		var phi = i*Math.PI/180;
		var x = ~~(r*Math.cos(phi));
		var y = ~~(r*Math.sin(phi));
		var last_element = kernel[kernel.length - 1];
		if (last_element.x != x || last_element.y != y)
				kernel.push({x: x, y: y});
	}

Next step is to loop through image pixels and execute the voting procedures. At every pixel the overall sum is calculated using the lookup table. See the code fragment below:

 


	// Create buffer using pixels.data ctor
	var buff = new pixels.data.constructor(new ArrayBuffer(pixels.data.length));
	var data = pixels.data;
	var w = pixels.width - r;
	var h = pixels.height - r;
	var i, j, bpr = pixels.width*4;
	for (i = r; i < h; i++){
		for (j = r; j < w; j++){
			var sum = 0, l = kernel.length;
			for (var k = 0; k < l; k++){
				var x = j + kernel[k].x;
				var y = i + kernel[k].y;
				sum += data[bpr*y + x*4]; // Assume it's grayscale
			}
			const pos = bpr*i + j*4;
			buff[pos + 0] = buff[pos + 1] = buff[pos + 2] = ~~(sum / l);
			buff[pos + 3] = 255;
		}
	}

	pixels.data.set(buff);
}

Hough Transform using OpenGL (WebGL)

 

In case of GPU based algorithm, the Hough Circle Transform can be obtained using the following OpenGL fragment shader:


precision mediump float;

// our texture
uniform sampler2D u_image;
uniform vec2 u_textureSize;
uniform float u_r;
#define M_PI 3.1415926535897932384626433832795
#define PHI_STEP M_PI/180.0

void main() {
	vec2 onePixel = vec2(1.0, 1.0) / u_textureSize;
	vec2 textCoord = gl_FragCoord.xy / u_textureSize;
	vec4 sum = vec4(0.0);
	float phi = 0.0;
	for (int i = 0; i < 360; i++)
	{
		phi += PHI_STEP;
		sum += texture2D(u_image, textCoord + onePixel*vec2(u_r*cos(phi), u_r*sin(phi)));
	}
	
	gl_FragColor = vec4(vec3(sum / 360.0), 1.0);
}

Hough Transfrom Demo Application:

Sigma: 3

Related Articles:

Gaussian blur