Dynamic Programming Stereo: Monotonicity Check

hardPRODepth EstimationDynamic Programming, Arrays, OptimizationComputer Vision 1

Dynamic Programming stereo matching relies on the monotonicity constraint: pixel ordering is preserved between views.

A valid DP path can only move right (i+1,j), down (i,j+1), or diagonal (i+1,j+1).

Violation occurs if: i decreases OR j decreases between consecutive points.

Given a path as list of (i,j) pairs, return True if monotonicity is violated, False otherwise.

Constraints:

Examples:

| Input | Output | |-------|--------| | [(0,0),(1,1),(2,2),(3,3)] | False | | [(0,0),(1,0),(0,1)] | True | | [(0,0),(0,1),(1,1),(1,2)] | False |

Input

path = [(0,0), (1,1), (2,2), (3,3)]

Output

False

Reasoning

Input: path is a list of correspondences $(i, j)$ : $i$ is a column in the left image and $j$ the matching column in the right image. The sample has four points, $(0,0), (1,1), (2,2), (3,3)$ , so there are three moves between neighbouring points.
Math: for each move from $(i_k, j_k)$ to $(i_{k+1}, j_{k+1})$ , compute the changes $\Delta i = i_{k+1} - i_k$ and $\Delta j = j_{k+1} - j_k$ . Monotonicity is broken if either change is negative.
Every move here is diagonal: $\Delta i = 1$ and $\Delta j = 1$ for $(0,0) \to (1,1)$ , $(1,1) \to (2,2)$ and $(2,2) \to (3,3)$ . No change is negative.
Output: a single boolean that answers "was the ordering broken?", so a valid path gives False, the sample output.
Notice the contrast with $(0,0), (1,0), (0,1)$ : the move $(1,0) \to (0,1)$ has $\Delta i = -1$ . The two image columns would swap order, so the answer is True. A move with $\Delta = 0$ in one coordinate (a pure right or down step) is still allowed.

1. Background Knowledge