Как найти расстояние между двумя связанными точками через белые пиксели?

Question

Я хочу найти две конечные точки кривой.

Я использовал выпуклый корпус, чтобы найти 8 граничных точек, а затем для каждой точки рассчитываются расстояния со всеми остальными точками.Точки с максимальными расстояниями считаются конечными точками.Это работает для большинства случаев, когда форма проста, как показано ниже:

Я использую этот код, чтобы найти две точки:

% Calculate 8-boundary points using Convex Hull
% (points consists of all white pixels for the curve)
out=convhull(points);
extremes=points(out,:);

% Finding two farthest points among above boundary points
arr_size = size(extremes);
max_distance = 0;
endpoints = [extremes(1,:); extremes(2,:)];
for i=1:arr_size(1)
    p1 = extremes(i,:);
    for j=i+1:arr_size(1)
        p2 = extremes(j,:);
        dist = sqrt((p2(1)-p1(1))^2 + (p2(2)-p1(2))^2);
        if dist>max_distance
            max_distance = dist;
            endpoints = [p1; p2];
        end
    end
end

disp(endpoints);

В большинстве случаев это работает, но проблема возникает, когда он применяется к U-образной форме.

Я хочу узнать количество белых пикселей междудве точки.Я следовал этому Подсчет белых пикселей между 2 точками на изображении , но это помогает в случае только прямых линий, а не кривой.Любая помощь приветствуется!

РЕДАКТИРОВАТЬ 1:

Я обновил свой код на основе ответа @Rotem, и он исправил мою проблему.

Обновленный код:

for i=1:arr_size(1)
    p1 = extremes(i,:);
    distanceMap = calculate_distance_map(arr, p1);
    for j=i+1:arr_size(1)
        p2 = extremes(j,:);
        dist = distanceMap(p2(2), p2(1));
        if dist>max_distance
            max_distance = dist;
            endpoints = [p1; p2];
        end
    end
end

Однако это занимает значительно больше времени.Любые предложения о том, как сократить время расчета?

Answer 1

Я нашел решение, основанное на алгоритмах динамического программирования .

Пояснения в комментариях:

function n_points = BlueDotsDist()

I = imread('BlueDots.png');

%Fix the image uploaded to the site - each dot will be a pixel.
I = imresize(imclose(I, ones(3)), 1/6, 'nearest');

%Convert each color channel to a bynary image:
R = imbinarize(I(:,:,1));G = imbinarize(I(:,:,2));B = imbinarize(I(:,:,3));
%figure;imshow(cat(3, double(R), double(G), double(B)));impixelinfo

%Find blue dost:
[blue_y, blue_x] = find((B == 1) & (R == 0));

%Compute distance map from first blue point
P = CalcDistMap(R, blue_y(1), blue_x(1));

%Compute distance map from second blue point
Q = CalcDistMap(R, blue_y(2), blue_x(2));

%Get 3x3 pixels around second blue point.
A = P(blue_y(2)-1:blue_y(2)+1, blue_x(2)-1:blue_x(2)+1);
dist_p = min(A(:)); %Minimum value is the shortest distance from first point (but not the number of white points).

T = max(P, Q); %Each element of T is maximum distance from both points.
T(T > dist_p) = 10000; %Remove points that are more far than dist_p.

%Return number of white points between blue points.
n_points = sum(T(:) < 10000);




function P = CalcDistMap(R, blue_y, blue_x)
%Each white pixel in R gets the distance from the blue dot in coordinate (blue_x, blue_y).

%Initialize array with values of 10000 (high value - marks infinite distance).
P = zeros(size(R)) + 10000; %P - distance from blue dot

P(blue_y, blue_x) = 0; %Distance from itself.

prvPsum = 0;
while (sum(P(:) < 10000) ~= prvPsum)
    prvPsum = sum(P(:) < 10000); %Sum of "marked" dots.
    for y = 2:size(R, 1)-1
        for x = 2:size(R, 2)-1
            p = P(y, x);
            if (p < 10000) %If P(y,x) is "marked"
                A = P(y-1:y+1, x-1:x+1); %3x3 neighbors.
                A = min(A, p+1); %Distance is the minimum of current distance, and distance from p pixel + 1.
                A(R(y-1:y+1, x-1:x+1) == 0) = 10000; %Ignore black pixels.
                A(P(y-1:y+1, x-1:x+1) == 0) = 0; %Restore 0 in blue point.
                P(y-1:y+1, x-1:x+1) = A; %Update distance map.
            end
        end
    end
end

---

Иллюстрация карт расстояний (заменено 10000)с нулем):

P (расстояния от первой синей точки):

Q (расстояния от второй синей точки):

макс. (P, Q):

T: