Sandbox/Realazthat/Hough transform
Implement the Hough transform, which is used as part of feature extraction with digital images. It is a tool that makes it far easier to identify straight lines in the source image, whatever their orientation.
![Task](http://static.miraheze.org/rosettacodewiki/thumb/b/ba/Rcode-button-task-crushed.png/64px-Rcode-button-task-crushed.png)
You are encouraged to solve this task according to the task description, using any language you may know.
The transform maps each point in the target image, , to the average color of the pixels on the corresponding line of the source image (in -space, where the line corresponds to points of the form ). The idea is that where there is a straight line in the original image, it corresponds to a bright (or dark, depending on the color of the background field) spot; by applying a suitable filter to the results of the transform, it is possible to extract the locations of the lines in the original image.
![](http://static.miraheze.org/rosettacodewiki/thumb/c/c6/Pentagon.png/300px-Pentagon.png)
The target space actually uses polar coordinates, but is conventionally plotted on rectangular coordinates for display. There's no specification of exactly how to map polar coordinates to a flat surface for display, but a convenient method is to use one axis for and the other for , with the center of the source image being the origin.
There is also a spherical Hough transform, which is more suited to identifying planes in 3D data.
C
This solution has no libraries specified.
Code: <lang c>
- include <stdio.h>
- include <stdlib.h>
- include <stdint.h>
- include <string.h>
- include <math.h>
- include <cairo.h>
- ifndef M_PI
- define M_PI 3.1415927
- endif
- define GR(X,Y) (d[(*s)*(Y)+bpp*(X)+((2)%bpp)])
- define GG(X,Y) (d[(*s)*(Y)+bpp*(X)+((1)%bpp)])
- define GB(X,Y) (d[(*s)*(Y)+bpp*(X)+((0)%bpp)])
- define SR(X,Y) (ht[4*tw*((Y)%th)+4*((X)%tw)+2])
- define SG(X,Y) (ht[4*tw*((Y)%th)+4*((X)%tw)+1])
- define SB(X,Y) (ht[4*tw*((Y)%th)+4*((X)%tw)+0])
- define RAD(A) (M_PI*((double)(A))/180.0)
uint8_t *houghtransform(uint8_t *d, int *w, int *h, int *s, int bpp) {
int rho, theta, y, x, W = *w, H = *h; int th = sqrt(W*W + H*H)/2.0; int tw = 360; uint8_t *ht = malloc(th*tw*4); memset(ht, 0, 4*th*tw); // black bg for(rho = 0; rho < th; rho++) { for(theta = 0; theta < tw/*720*/; theta++) { double C = cos(RAD(theta)); double S = sin(RAD(theta)); uint32_t totalred = 0; uint32_t totalgreen = 0; uint32_t totalblue = 0; uint32_t totalpix = 0; if ( theta < 45
Template:Requires-output Property "Is solution of" (as page type) with input value "{{{task}}}" contains invalid characters or is incomplete and therefore can cause unexpected results during a query or annotation process.