How to traverse a shape edge at constant arc lengths?

Given a binary image representing a shape, I am interested in extracting its boundary as list of pixel coordinates. Starting from an arbitrary edge pixel, I want to construct the list by walking along the edge of the shape, taking constant arclength steps in a clockwise fashion, adding coordinates to the list for each step. I want to be able to specify the number of steps (length of the list), so the step length should equal to (shape perimeter/nSteps).

To simplify, we can assume that the shape is completely filled and that the edge pixels are known, but not how they are ordered. See images below for exaple shape and its edge:

Thankful for any help!

[Marcus Lööw]

I seem to have found a solution to the problem using a beautiful piece of code written by John D'Errico.

First, I sort my edge pixels according to the following:

1. Let e be the unsorted list of edge pixels
2. Let s be the sorted list of edge pixels and initialize it to [].
3. Let pp be the previous pixel and initialize it to the first pixel in e.
4. Remove pp from e.
5. Add pp to s.
6. Let cp be the closest pixel to pp within e.
7. Let cp equal to pp.

• Repeat 4-7 until e is empty.

This will result in the edge pixels being sorted in either clockwise or counter-clockwise orientation. For a complete solution I will have to find a way to determine which it is, and then reverse the list if is in ccw order.

To the sorted edge pixel list I apply John D'Errico's interparc function like so:

pt = interparc(n, px, py, 'spline');

where px, py are the sorted edge pixel coordinates and n is the number of uniformly spaced points along the curve represented by the edge pixels.

The image below shows 100 uniformly spaced points along the edge of the shape from my orignial submission.

Hope someone else finds this useful.

[Willem Wei-Xing Prajitno]

It worked well for me. I got some code although it is not the prettiest.

function unsorted_list = traverse_edge(binarizedImageEdges)
%%https://nl.mathworks.com/matlabcentral/answers/322501-how-to-traverse-a-shape-edge-at-constant-arc-lengths
%%https://nl.mathworks.com/matlabcentral/fileexchange/34874-interparc
% 1. Let e be the unsorted list of edge pixels
C_dupe = find(sum(binarizedImageEdges)>=1);   % finds row where white pixels are present
if ~isempty(C_dupe)
    unsorted_list = [];    % unsorted pixel list
    for k = 1:length(C_dupe)
        list_row = find(binarizedImageEdges(:,C_dupe(k))==1);
        list_col = ones(length(list_row),1).*C_dupe(k);
        unsorted_list =  [unsorted_list; list_col list_row];
    end
end
x_max = max(list_col);                                          % max column, corresponding to outer right point
y_min = find( binarizedImageEdges(:,x_max) == 1, 1 ,'last');    % find corresponding lowest right point/row.

sorted_list = []; % 2. Let s be the sorted list of edge pixels and initialize it to [].

pp =  [x_max, y_min];% 3. Let pp be the previous pixel and initialize it to the first pixel in e.
ind_begin = find(unsorted_list(:,1)== x_max & unsorted_list(:,2)==y_min);
% shift to start at most outer right bottom pixel
unsorted_list = circshift(unsorted_list,length(unsorted_list)-ind_begin+1);
ind_begin = find(unsorted_list(:,1)== x_max & unsorted_list(:,2)==y_min);

sorted_list = [sorted_list; unsorted_list(ind_begin,:)];
unsorted_list(ind_begin,:) = [];    % Remove pp from unsorted_list.

while ~isempty(unsorted_list)
    distances = zeros(length(unsorted_list(:,1)),1);
    for i = 1:length(unsorted_list(:,1))
        distances(i) = sqrt(sum(bsxfun(@minus, unsorted_list(i,:), sorted_list(end,:)).^2,2));
    end
    closest = unsorted_list(find(distances==min(distances),1,'last'),:);
    sorted_list(end+1,:) = closest;

      idx_del = find(unsorted_list(:,1)== closest(1) & unsorted_list(:,2)==closest(2));
      closest = [];

      unsorted_list(idx_del,:) = [];    % Remove pp from unsorted_list.

end
figure;
hold on

for i = 1: length(sorted_list(:,1))

      scatter(sorted_list(i,1), sorted_list(i,2))
      drawnow;
  end

px = sorted_list(:,1);
py = sorted_list(:,2);
n = 100;
pt = interparc(n, px, py, 'spline');
plot(px,py,'r*',pt(:,1),pt(:,2),'b-o')

[Guillaume]

@Willem, "it is not the prettiest."

Indeed, I don't understand why you use such a convoluted way of building the unsorted list. A single find is all that is needed. Similarly, the distance loop is not needed and since you use a loop the bsxfun that would be needed in the no-loop case is completely unnecessary.

Answer 1

[Guillaume]

@Willem, a simplification of your code. I've not bothered finding the bottom rightmost pixel, starting instead at the top leftmost pixel (default order of find)

function sorted_list = traverse_edge(binarizedImageEdges)
   %%https://www.mathworks.com/matlabcentral/answers/322501-how-to-traverse-a-shape-edge-at-constant-arc-lengths
   %%https://www.mathworks.com/matlabcentral/fileexchange/34874-interparc

     % 1. Let e be the unsorted list of edge pixels
     [unsorted_list(:, 2), unsorted_list(:, 1)] = find(binarizedImageEdges);

     % 2. Let s be the sorted list of edge pixels and initialize it to [].
     sorted_list = zeros(size(unsorted_list));   %pre-allocate array. This will be a lot more efficient than constant resizing
     current_row = 1;   %and keep track of where we're filling

     % 3. Let pp be the previous pixel and initialize it to the first pixel in e.
     pp_row = 1;
     while ~isempty(unsorted_list)
         pp = unsorted_list(pp_row, :);

         % 4. Remove pp from e
         % 5. Add pp to s
         unsorted_list(pp_row, :) = [];
         sorted_list(current_row, :) = pp;
         current_row = current_row + 1;

         % 6. Let cp be the closest pixel to pp within e
         % 7. Let cp equal to pp
         [~, pp_row] = min(sum((unsorted_list - pp).^2, 2));   %R2016b or later
         %[~, pp_row] = min(sum((bsxfun(@minus, unsorted_list, pp).^2, 2));  %earlier versions
     end
  end