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:

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);
}
```