ASCIIMath creating images

Sunday, February 6, 2011

Voronoi Neighbors

For a current research project, I was considering the problem of finding the neighbors of some given quantization value, basically a method to figure out if two Voronoi regions share a border, where the quantizer is specified simply by the centroids. I wrote a quick and dirty script, but it doesn't work in all cases - the problem is actually quite difficult for vector quantizers.  However, I started without checking the literature, trying to come up with my own approach; now I know better! Below, my crack at the problem, followed by the better, faster and smarter method!

The initial approach
My approach is based on drawing a line between two centroids.  If I find a point on this line that does not get quantized to either of the centroids, I declare the two regions not neighbors.
In this figure, A and B are clearly neighbors, whereas C isn't.  Testing is done using a binary search: I sample the middle of the line, check if that point gets quantized to A or B - if to B, then pick the halfway point from the middle to A, keep going until either a non-A or B point is found or 10 iterations have been done.  Generally for most checks the algorithm stops at the first check (see A and C) only for the neighboring regions will all 10 iterations be computed.

Problem is, this doesn't work very well.  Let's remove D:

Clearly, C now is a neighbor of A, but the straight line is not where the boundary between A and C is located.  So much for that...

The proper way
I found the correct way of solving this problem by looking at how Voronoi diagrams are drawn by MATLAB: using Delaunay triangulation.  Then using MATLAB functions, the lists of neighbors for the centroids can be found by calling delaunay, then TriRep, then the edges method on the resulting structure.  Here is some sample code:

% create a quantizer
V = zeros(2,8);
V(:,1) = [ 0 0 ];
for n=2:8
   V(:,n) = [ sin(2*pi*(n-1)/8) cos(2*pi*(n-1)/8) ];
tri = delaunay(V(1,:),V(2,:));
tr = TriRep(tri,V(1,:)',V(2,:)');

The resulting edges array can now be examined and turned into a list of neighbors for each centroid.  This should scale to higher dimensions, but won't work for 1-D - but there, the neighboring quantizer region problem is trivial anyways.  (Note, I have the Signal Processing Toolbox, so I'm not sure all those functions are in default MATLAB.)

So while my initial quick bit of code didn't work, it did cause me to think about the problem a bit more deeply and I learned a bit about computational geometry.