Преобразование Хафа в MATLAB без использования функции Хафа

Question

Я нашел реализацию преобразования Хафа в MATLAB на Rosetta Code , но у меня возникли проблемы с его пониманием. Также я хотел бы изменить его, чтобы показать исходное изображение и восстановленные линии (де-Хофинг).

Любая помощь в понимании этого и де-Хофинг приветствуется. Спасибо

1. Почему изображение перевернуто?

   theImage = flipud(theImage);

2. Я не могу обернуть голову вокруг функции нормы. Какова его цель и можно ли ее избежать?

РЕДАКТИРОВАТЬ: норма является просто синонимом евклидова расстояния: sqrt (ширина ^ 2 + высота ^ 2)

rhoLimit = norm([width height]);

1. Может ли кто-нибудь объяснить, как / почему вычисляются значения rho, theta и houghSpace?

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

2. Как бы я де-Хо пространство Хо, чтобы воссоздать линии?

Вызов функции с использованием изображения 10х10 диагональной линии, созданной с использованием функции идентификации (глаз)

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

Фактическая функция

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

Преобразование Хафа - это подход «голосования», при котором каждая точка изображения голосует за существование определенной линии (, а не линия сегмент ) в изображении. Голосование проводится в пространстве параметров для линии: представление полярных координат нормальных векторов.

Мы дискретизируем пространство параметров и разрешаем каждой точке изображения предлагать параметры, которые были бы совместимы с линией, проходящей через точку. Каждый из ваших вопросов может быть рассмотрен с точки зрения того, как пространство параметров обрабатывается в коде. Википедия имеет хорошую статью с проработанными примерами, которые могут прояснить ситуацию (если у вас возникли какие-либо концептуальные проблемы).

Для ваших конкретных вопросов:

1. Изображение перевернуто, поэтому начало координат находится в правом нижнем углу. Насколько я могу судить, этот шаг не является технически необходимым. Это несколько меняет результат из-за проблем с дискретизацией. Другие реализации в Rosetta Code не переворачивают изображение.
2. rhoLimit содержит максимальный радиус точки изображения в полярных координатах (напомним, что норма вектора равна его величине).
3. rho и theta являются дискретизацией полярной координатной плоскости в соответствии с частотой дискретизации. houghSpace создает матрицу с элементом для каждой возможной комбинации дискретных значений rho / theta.
4. Преобразование Хафа не определяет длины предполагаемых линий; пики в пространстве голосования просто указывают полярные координаты вектора нормали линии. Вы можете «де-Хо», выбрав пики и нарисовав соответствующие линии, или, возможно, нарисовав каждую возможную линию и используя количество голосов в качестве веса в градациях серого. Невозможно воссоздать исходное изображение из преобразования Хафа, только линии, идентифицированные преобразованием (и ваша схема установления порога по голосам).

Следуя примеру из вопроса, получается следующий график. Расположение линий сетки и курсора подсказок может быть немного обманчивым (хотя значения переменных в подсказке верны). Поскольку это изображение пространства параметров , а не пространства изображений, частота выборки, которую мы выбрали, определяет количество бинов в каждой переменной. При такой частоте дискретизации точки изображения совместимы с более чем одной возможной линией; другими словами, наши линии имеют субпиксельное разрешение в том смысле, что они не могут быть нарисованы без наложения в изображении 10x10.

Как только мы выбрали пик, такой как тот, который соответствует линии с нормальным (rho,theta) = (6.858,0.9), мы можем нарисовать эту линию на изображении, как мы выберем. Автоматическая выборка пиков, которая задает пороговые значения для поиска линий с высоким числом голосов, является собственной проблемой - вы можете задать другой вопрос по теме в DSP или о конкретном алгоритме здесь.

Примеры методов см. В коде и документации функций MATLAB houghpeaks и houghlines функций.