Matlab: Algorithm for voronoi diagram of ellipses

Question

Are there any algorithms to implement Voronoi diagram that bounds the ellipses? The diagram would look like the pictures here voronoi diagram of ellipses

Can anyone share some links,tutorials,codes etc related to it?

Thanks in advance.

Answer 1

Here's an algorithm that uses the distance transform together with the watershed algorithm to draw a Voronoi diagram for ellipses.

%# first, define some ellipses (for simplicity, I use 0/90 orientation)
ellipses = [10,20,5,10;30,10,10,7;40,40,8,3];

%# put the ellipses into an image (few pixels, therefore pixelated)
img = false(50);
[xx,yy]=ndgrid(1:50,1:50);
for e = 1:size(ellipses,1),img = img | (xx-ellipses(e,1)).^2/ellipses(e,3)^2 + (yy-ellipses(e,2)).^2/ellipses(e,4)^2 <= 1;end

%# perform the distance transform
dt = bwdist(img);

%# apply the watershed algorithm. 
%# ws==0 are the lines for the Voronoi diagram
ws = watershed(dt);

%# create a RGB image and display
%# note: for yellow lines, replace the last
%# "ws==0" by "zeros(size(ws))", so that you
%# only put ws into the red and green channel (=yellow)
rgb = cat(3,ws==0,ws==0,ws==0)); 
%# add the ellipses into the red channel
rgb(:,:,1) = rgb(:,:,1) | img;
imshow(rgb)

Answer 2

Just in case, this is an example from the Mathematica help system:

(*Generate ellipses*)
p= Rasterize@Graphics@Table[
          Rotate[
              Disk[RandomReal[10, 2],          (*Rnd position*)
                   RandomReal[{.3, 1.5}, 2]],  (*Rnd radii*)
          RandomReal[Pi]], {i, 10}]            (*Rnd rotation*)

(*Compute Voronoi*)

LaplacianGaussianFilter[DistanceTransform[p], 2] // ImageAdjust

It is not an exact calculation, but fair enough for practical uses.

Answer 3

Based on your recent track of questions, I understand that you've been working on drawing rasterized ellipses on top of an RGB image. You would like to be able to specify the ellipses location, shape and color. You wanted the ellipses to be clipped at the boundaries, and also to be non-overlapping. Now you are looking to draw the lines that divides the space in a manner similar to Voronoi diagrams (but with ellipses instead of points).

For this particular question, as @Jonas showed, the solution is to use the distance transform together with the watershed algorithm.

I thought I continue with my previous example, and extend it with Jonas's idea, to showcase the entire process. Hope you find it useful..

The code uses the calculateEllipse function to compute the coordinates of the points that make up an ellipse, as well as imoverlay function for setting specified pixels of an image to some chosen color.

%# color image (canvas to draw on)
I = imread('pears.png');
sz = size(I);

%# random ellipses
num = 20;
centers = bsxfun(@times, rand(num,2), sz([2 1]));   %# center x/y-coords
radii = bsxfun(@times, rand(num,2), [300 50])+10;   %# major/minor axis length
angles = rand(num,1) .* 360;                        %# angle of rotation
ex = cell(num,1);                                   %# vertices x-coords
ey = cell(num,1);                                   %# vertices y-coords

%# label image, used to hold rasterized ellipses
L = zeros(sz(1),sz(2));

%# randomly place ellipses one-at-a-time, skip if overlaps previous ones
flag = false(num,1);
for i=1:num
    %# ellipse we would like to draw directly on image matrix
    [ex{i},ey{i}] = calculateEllipse(centers(i,1),centers(i,2), ...
        radii(i,1),radii(i,2), angles(i), 100);

    %# create mask for image pixels inside the ellipse polygon
    mask = poly2mask(ex{i},ey{i}, sz(1),sz(2));

    %# check if there is no existing overlapping ellipse
    if all( L(mask)==0 )
        %# use the mask to place the ellipse in the label image
        L(mask) = sum(flag)+1;    %# assign value using an increasing counter
        flag(i) = true;
    end
end

%# filter ellipses to only those that made through the overlap test
num = sum(flag);
centers = centers(flag,:);
radii = radii(flag,:);
angles = angles(flag);
ex = ex(flag);
ey = ey(flag);

%# rasterized voroni diagram of the ellipses [Jonas]
E = (L ~= 0);                             %# ellipses as binary image
WS = watershed( bwdist(E) );              %# distance transform + watershed
WS = (WS == 0);                           %# WS==0 corresponds voronoi diagram
WS = bwmorph(WS, 'thicken',1);            %# thicken the lines

%# set pixels corresponding to voronoi diagram to white
II = I;
II = imoverlay(II, WS, [1 1 1]);          %# you can customize the color here

%# set pixels corresponding to ellipses using specified colors
clr = hsv(num);                           %# color of each ellipse
for i=1:num
    mask = bwperim(L==i,8);               %# get perimeter of the ellipse mask
    mask = bwmorph(mask, 'thicken',1);    %# thicken the ellipse perimeter
    II = imoverlay(II, mask, clr(i,:));   %# set those pixels with RGB color
end

%# show final rasterized image (image + ellipses + voronoi diagram)
figure, imshow(II, 'InitialMagnification',100, 'Border','tight')