Question

Consider the following arrangement of pixels P, P₁, P₂, P₃ and P₄ as shown in the figure. Assume that P, P₂ and P₄ have a value of 1, and P₁ and P₃ have a value of 0. If we consider adjacency of pixels as \(V=\{1\}\), what is the length of the shortest m-path between P and P₄?

• A. 2
• B. 1
• C. 3
• D. 4

Hint:

Plot the pixel positions on a grid, note that P1 and P3 both equal 0 so they cannot be used, and check whether P-P2 and P2-P4 each satisfy the no-common-V-neighbour condition for m-adjacency.

Answer 1

The Correct Option is A

Step 1: Set up grid coordinates for the five pixels.
Reading the figure, place the pixels on a (row, column) grid with row increasing downward: \(P_3\) at \((0,1)\), \(P_4\) at \((0,2)\); \(P_1\) at \((1,0)\), \(P_2\) at \((1,1)\); and \(P\) at \((2,0)\). The given values are \(P=1\), \(P_2=1\), \(P_4=1\) (in \(V=\{1\}\)) and \(P_1=0\), \(P_3=0\) (not in \(V\)). All other surrounding grid cells are background, with value \(0\).
Step 2: Recall the definition of m-adjacency.
Two pixels \(p\) and \(q\), both with values in \(V\), are m-adjacent if either (i) \(q\) is a 4-neighbour of \(p\), or (ii) \(q\) is a diagonal neighbour of \(p\) AND the common 4-neighbours of \(p\) and \(q\) contain no pixel with a value in \(V\). Condition (ii) removes the ambiguity of multiple equal-length 8-paths when a "bridging" V-valued pixel sits between two diagonal V-valued pixels.
Step 3: Check whether P is m-adjacent to P2.
P at \((2,0)\) and \(P_2\) at \((1,1)\) are diagonal neighbours, both value \(1\). The 4-neighbours of P are \((1,0)=P_1\) and \((2,1)=\text{background}\); the 4-neighbours of \(P_2\) are \((0,1)=P_3\), \((2,1)=\text{background}\), \((1,0)=P_1\), \((1,2)=\text{background}\). The common ones are \((1,0)=P_1\) (value 0) and \((2,1)\) (value 0) - neither is in \(V\). So P is m-adjacent to \(P_2\).
Step 4: Check whether P2 is m-adjacent to P4.
\(P_2\) at \((1,1)\) and \(P_4\) at \((0,2)\) are also diagonal neighbours, both value \(1\). Their common 4-neighbours are \((0,1)=P_3\) (value 0) and \((1,2)\) (background, value 0) - neither is in \(V\). So \(P_2\) is m-adjacent to \(P_4\).
Step 5: Determine the shortest m-path length.
Because \(P_1\) and \(P_3\) both equal \(0\), they cannot serve as connecting pixels, and P is not directly adjacent to \(P_4\) (they are two grid steps apart diagonally). The only valid m-connected route is \(P \to P_2 \to P_4\), using two m-adjacency steps. \[ \boxed{\text{Shortest m-path length} = 2} \]