Home > other >  How to prune some unnecessary branches from the Voronoi diagram?
How to prune some unnecessary branches from the Voronoi diagram?

Time:05-13

I generated the Voronoi diagram using the following MATLAB code. The problem is that in the output image I obtain some useless lines that I want to remove. By useless lines, I mean like those circled in purple, so the lines that are directly attached to the polygons. I would like only the ones in green in the output image. Could someone help me? Thanks in advance.

clc; clear all; close all;

%% Input Map
RGB = imread('mappa3.png');
figure('Position',[100 0 600 700],'color','k')
imagesc(RGB);
axis image
title('Input Map','color','w');
axis off
set(gcf, 'InvertHardCopy', 'off');
hold off;

%% Convert to binary image
I = rgb2gray(RGB);
binaryImage = im2bw(RGB, 0.3);
sz  = size(binaryImage);

%% Pose
% Initial Pose
xs = 270; ys = 296; % valori iniziali 55 e 33
% Goal Pose
xg = 50; yg = 50; % valori iniziali 50 e 50
% Pose Matrix
pose = zeros(sz(1),sz(2));
pose(ys,xs) = 1;
pose(yg,xg) = 1;

%% Voronoi Road Map
figure('Position',[100 0 600 700],'color','k');
hold on;
set(gcf, 'InvertHardCopy', 'off');
sk = 1;
for i = 1:sz(1)
  for j = 1:sz(2)
    if(binaryImage(i,j) == 1 )
      xv(sk) = j;
      yv(sk) = i;
      sk = sk 1;
    end
  end
end
[vrx,vry]  = voronoi(xv,yv);
set(gca,'YDir','Reverse');
plot(xv,yv,'y.',vrx,vry,'b-')
axis tight
%axis([1 sz(2) 1 sz(1) ]) ;
axis image
title({'Voronoi Road Map';'* - Represents Starting and Goal Position '},'color','w');
axis off

spy(pose,'*r')   

mappa3.png

output image

CodePudding user response:

You are taking each individual pixel as a cell centroid, so the Voronoi diagram encircles each individual pixel. You want to take each group of connected pixels (polygon) as a centroid. And on top of that, somehow include the size of these groups of pixels so that the Voronoi diagram doesn't cut though them.

You can accomplish all of this by computing the skeleton of the background, like so:

img = imread('https://i.stack.imgur.com/TbmKp.png');
background = img(:,:,1)==0;
voronoi = bwskel(background,'MinBranchLength',1e6);

enter image description here

  • Related