Transformada de Hough en MATLAB sin usar la función de hough

Question

Encontré una implementación de la transformada de Hough en MATLAB en Rosetta Code, pero estoy teniendo problemas para entenderla. También me gustaría modificarlo para mostrar la imagen original y las líneas reconstruidas (de-Houghing).

Se agradece cualquier ayuda para entenderlo y de-Houghing. Gracias

1. ¿Por qué se invierte la imagen?

   theImage = flipud(theImage);

2. No puedo hacerme a la función normal. ¿Cuál es su propósito y puede evitarse?

EDIT: norma es simplemente un sinónimo de la distancia euclídea: sqrt (anchura^2 + altura^2)

rhoLimit = norm([width height]);

1. Puede alguien proporcionar una explicación de cómo/¿Por qué se calculan rho, theta y houghSpace?

   rho = (-rhoLimit:1:rhoLimit);   
   theta = (0:thetaSampleFrequency:pi); 
   
   numThetas = numel(theta); 
   houghSpace = zeros(numel(rho),numThetas); 
   

2. ¿Cómo podría de-Hough Hough el espacio para recrear las líneas?

Llamar a la función utilizando una imagen de 10x10 de una línea diagonal creados usando la función identidad (ojo)

theImage = eye(10) 
thetaSampleFrequency = 0.1 
[rho,theta,houghSpace] = houghTransform(theImage,thetaSampleFrequency) 

La función real

function [rho,theta,houghSpace] = houghTransform(theImage,thetaSampleFrequency) 

    %Define the hough space 
    theImage = flipud(theImage); 
    [width,height] = size(theImage); 

    rhoLimit = norm([width height]); 
    rho = (-rhoLimit:1:rhoLimit);   
    theta = (0:thetaSampleFrequency:pi); 

    numThetas = numel(theta); 
    houghSpace = zeros(numel(rho),numThetas); 

    %Find the "edge" pixels 
    [xIndicies,yIndicies] = find(theImage); 

    %Preallocate space for the accumulator array 
    numEdgePixels = numel(xIndicies); 
    accumulator = zeros(numEdgePixels,numThetas); 

    %Preallocate cosine and sine calculations to increase speed. In 
    %addition to precallculating sine and cosine we are also multiplying 
    %them by the proper pixel weights such that the rows will be indexed by 
    %the pixel number and the columns will be indexed by the thetas. 
    %Example: cosine(3,:) is 2*cosine(0 to pi) 
    %   cosine(:,1) is (0 to width of image)*cosine(0) 
    cosine = (0:width-1)'*cos(theta); %Matrix Outerproduct 
    sine = (0:height-1)'*sin(theta); %Matrix Outerproduct 

    accumulator((1:numEdgePixels),:) = cosine(xIndicies,:) + sine(yIndicies,:); 

    %Scan over the thetas and bin the rhos 
    for i = (1:numThetas) 
     houghSpace(:,i) = hist(accumulator(:,i),rho); 
    end 

    pcolor(theta,rho,houghSpace); 
    shading flat; 
    title('Hough Transform'); 
    xlabel('Theta (radians)'); 
    ylabel('Rho (pixels)'); 
    colormap('gray'); 

end 

Answer 1

La transformada de Hough es un "voto "enfoque donde cada punto de imagen emite un voto sobre la existencia de una determinada línea (no una línea segmento) en una imagen. La votación se lleva a cabo en el espacio de parámetros para una línea: la representación de coordenadas polares de vectores normales.

Discretizamos el espacio de parámetros y permitimos que cada punto de imagen sugiera parámetros que serían compatibles con una línea a través del punto. Cada una de sus preguntas se puede abordar en términos de cómo se trata el espacio de parámetros en el código. Wikipedia tiene un buen artículo con ejemplos trabajados que pueden aclarar las cosas (si tiene problemas conceptuales).

Para sus preguntas específicas:

1. La imagen se gira de manera que el origen es la esquina inferior derecha. Por lo que puedo decir, este paso no es técnicamente necesario. Cambia un poco el resultado debido a problemas de discretización. Las otras implementaciones en el Código Rosetta no cambian la imagen.
2. rhoLimit tiene el radio máximo de un punto de imagen en coordenadas polares (recuerde que la norma de un vector es su magnitud).
3. rho y theta son discretizaciones del plano de coordenadas polares según una frecuencia de muestreo.houghSpace crea una matriz con un elemento para cada posible combinación de los valores discretos rho/theta.
4. La Transformada Hough no especifica las longitudes de las líneas putativas; los picos en el espacio de votación solo especifican las coordenadas polares del vector normal de la línea. Puede "eliminar" seleccionando los picos y dibujando las líneas correspondientes, o tal vez dibujando cada línea posible y usando el número de votos como un peso en escala de grises. No es posible volver a crear la imagen original de Hough Transform, solo las líneas identificadas por la transformación (y su esquema de umbralización de los votos).

Siguiendo el ejemplo de la pregunta se genera el siguiente gráfico. La colocación de líneas de cuadrícula y el cursor de información puede ser un poco engañosa (aunque los valores de las variables en la 'sugerencia son correctos). Dado que esta es una imagen del espacio de parámetros y no el espacio de la imagen, la frecuencia de muestreo que elegimos es determinar el número de contenedores en cada variable. A esta frecuencia de muestreo, los puntos de imagen son compatibles con más de una línea posible; en otras palabras, nuestras líneas tienen resolución subpixel, en el sentido de que no se pueden dibujar sin superposición en una imagen de 10x10.

Una vez que hemos elegido un pico, como el que corresponde a la línea con normal (rho,theta) = (6.858,0.9), podemos dibujar esa línea en una imagen como prefieramos. La selección automática de picos, que es el umbral para encontrar las líneas altamente votadas, es su propio problema: puede hacer otra pregunta sobre el tema en DSP o sobre un algoritmo particular aquí.

Por ejemplo, los métodos ver el código y documentation de las funciones houghpeaks y houghlines de MATLAB.