1
$\begingroup$

I'm attempting to implement an image processing algorithm from this white paper (p. 5), but I'm having difficulty with the math jargon, in particular this line:

If exist q that containing minimum (f(q) + h(p,q)) and (f(q) + h(p,q) < f(p)):

Can anyone translate this to English? This grammatical construction is new to me.

$\endgroup$
1
  • $\begingroup$ You're the only person I found online who posted about the phrase "If exist q that containing minimum" in the Shih and Wu paper about the two-pass Euclidean Distance Transform. Although you may have figured out the problem long ago, or moved on, I figured I'd provide an explanation. I made a guess at the meaning, implemented it, and saw that it worked. $\endgroup$
    – user148097
    May 5, 2014 at 22:26

2 Answers 2

1
$\begingroup$

Sounds like a poor translation from another language... your best bet might be to just google raster scan...

$\endgroup$
1
  • $\begingroup$ Hadn't considered that possibility – reading the rest of the paper more closely I suspect you're right. $\endgroup$
    – meetar
    Jun 15, 2013 at 14:23
0
$\begingroup$

I realize this post is nearly a year old, but since this page was the only result when I googled "If exist q that containing minimum," and since I was initially stumped, maybe some future reader will stumble across it.

The 2004 paper "Fast Euclidean distance transformation in two scans using a 3x3 neighborhood" by Shih and Wu presents a fast two-pass algorithm for calculating the Euclidean distance transform for every pixel in a foreground object. The distance transform is a standard technique in image processing.

http://en.wikipedia.org/wiki/Distance_transform

The algorithm determines the distance from a foreground pixel to the closest background pixel in a binarized image. The algorithm depends in part on comparisons of values for some pixel (x,y) to the values for the "8-neighbor" pixels surrounding the central pixel: (x-1,y), (x-1,y-1), (x,y-1), ..., (x-1, y+1). The authors label the central pixel p and its neighbors q(n) as follows:

q2   q3   q4
q1   p    q5
q8   q7   q6

The paper is generally readable, but as the original poster meeta pointed out, an apparently critical line in the description of the algorithm doesn't make sense. Here's the text, with [if] and [then] added for clarity:

for q = q1 to q4
   f(p) = min( f(p), f(q) + h(p,q) );
if exist q that containing minimum (f(q) + h(p,q)) and 
   [if] (f(q) + h(p,q) < f(p)
   [then] R(p) = R(q) + G(p,q);

The phrase "if exist q" should be translated as something like "if q is a valid pixel" or "if q is a valid element in the 2D array." The technique requires a raster scan of an image from top to bottom, and from left to right in each row. (The second pass reverses the scan order: bottom to top, right to left.) Pixels in the topmost and bottommost rows and pixels in the leftmost and rightmost columns don't have eight valid neighbor pixels.

For example, consider the point (0,0). In traditional image processing, the +X-axis points from left to right, the +Y-axis points from top to bottom. The point (0,0) is located in the upper left corner of the image, and it does not have valid pixel neighbors either above (y < 0) or to the left (x < 0).

It helps to reinterpret the text by Shih and Wu as follows:

for q = q1 to q4
   f(p) = min( f(p), f(q) + h(p,q) );
if q is a valid pixel and if (f(q) + h(p,q)) is a minimum
   [then] R(p) = R(q) + G(p,q);

In pseudocode, this may be expressed as follows:

 for each q of (q1, q2, q3, q4)
    if q is a valid pixel
       x = f(q) + h(p,q)
       if (x < f(p))
          f(p) = x
          R(p) = R(q) + G(p,q)

Based on this interpretation, my implementation of the Chih and Wu algorithm yields the expected results for Distance Transform images.

$\endgroup$

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.