7
$\begingroup$

I'm having trouble understanding the JFA. As far as I understood the algorithm, it walks log(n) times through every pixel (no matter if it is a seed or not) and looks at that pixel's neighbors in $(x+i, y+j)$ where $i,j \in \{-step\ length, 0, step\ length\}$.

When finding a seed (i.e., a colored pixel) among those neighbors, it checks whether the distance between the found neighbor seed and the current pixel is less than the distance the current pixel has already stored (after a previous round). If it is, the current pixel will be overwritten with the color of the found seed and the new distance and therefore serves as input seed for the next round.

So I tried to comprehend an example in some slides by the author himself but failed at step length 2, especially with the three bottommost red seeds:

complex example

For example, why does the blue circled seed keep its red color even though at step length 2 it finds two green seeds with a smaller distance (in my understanding the circled red pixel has stored a 4 and the distance to its top and bottom green neighbors is 2)? Or why does the other blue circled pixel become red, though its (x+2, y) neighbor is a green one with a smaller distance than its (x+2, y+2) red neighbor?

I also sketched another example on paper but when it comes to step length 1 the algorithm finds more than one neighbor seed with equal distances, so how will it decide? We could also think of a more simple example like this:

simple example

What are the diagonal pixels supposed to be according to the algorithm in that case? What am I getting wrong?

$\endgroup$
  • 1
    $\begingroup$ Maybe because the implementation modifies in place running LtR? That would mean the pixel above got changed and one got inserted to the left but not to the right. $\endgroup$ – ratchet freak Mar 9 '17 at 13:23
  • $\begingroup$ Ok, but modifying in place would mean that, looking at the 2nd picture, the downmost circled blank pixel turns into a red one. Then, the green seed right next to it should take that information and turn into a red one too, but it remains green... $\endgroup$ – Muad Mar 9 '17 at 15:06
  • $\begingroup$ Somewhat related but definitely not a duplicate (disclaimer: I wrote an answer to it) $\endgroup$ – trichoplax Mar 10 '17 at 21:00
5
$\begingroup$

I think that there is a bit of confusion in terminology. My understanding is that only the initially colored points, before step 1, are called seeds.

Maybe this helps clarify the algorithm as well. When the a point $ p $ with color $ s $ finds a neighbor $ q $ with color $ s' $, he compares the distance $ d(p,s) $ with $ d(p,s') $ (not $ d(p,q) $) to decide his new color. This is why each pixel crucially holds the $ (x,y) $ coordinates of his seed color (in the paper they used the r,g channels for this) and not just the distance. In each step this data is also passed to the neighbor.

So in that example, in moving from step length 4 to step length 2, that red square (the circled one that remains red) sees the green square who tells red square that the green seed is at $ (8,6) $. Red square then computes his distance to green square to be $ \sqrt{2^2 + 4^2} $, which is bigger than the distance to red ($ 4 $), and so remains red.

$\endgroup$
  • $\begingroup$ Ahh, that's it! So when a pixel finds a colored neighbor it computes the distance between that pixel and the initial seed (whose position it knows from the neighbor). This wasn't clear to me that there is a difference between a colored pixel and a seed. Thank you, you helped me a lot with that! But one question remains: what about the diagonal pixels in the 4x4 example? They have the same distance to both initial seeds... $\endgroup$ – Muad Mar 10 '17 at 21:23
  • 4
    $\begingroup$ Glad it makes sense now! The diagonals are ambiguous in the definition of the voronoi diagram: the paper mentions (on the first page) that for equidistant seeds, they choose the seeds arbitrarily. Maybe it will look nicer if you consistently choose one color over the other, I have no idea! $\endgroup$ – StinkySkunk Mar 10 '17 at 21:36
  • $\begingroup$ Alright, just overlooked it. Thanks again! $\endgroup$ – Muad Mar 10 '17 at 21:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.