Dynamic Programming Stereo: Monotonicity Check
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:
- 3 ≤ path length ≤ 1000
- 0 ≤ i, j < 1000
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 |
Example:
path = [(0,0), (1,1), (2,2), (3,3)]
False
- We scan consecutive pairs in the path and check if either coordinate ever decreases: from (ik​,jk​) to (ik+1​,jk+1​), a violation occurs if ik+1​<ik​ or jk+1​<jk​.
- For (0,0)→(1,1): 1≥0 and 1≥0, so no violation.
- For (1,1)→(2,2): 2≥1 and 2≥1, so no violation.
- For (2,2)→(3,3): 3≥2 and 3≥2, so no violation.
- Since no step decreases in i or j, monotonicity is not violated, so the output is False.
1. Background Knowledge
Monotonicity constraint in stereo matching ensures the ordering of points is preserved between views. If point A appears to the left of point B in the left image, A's correspondence must also appear left of B's correspondence in the right image.
Violation occurs when:
- Left coordinate decreases: pi+1​<pi​
- Right coordinate decreases: pi+1​<pi​
This constraint is fundamental in Dynamic Programming stereo (e.g., scanline optimization) where paths through the disparity space must be monotonic.
2. Algorithm Approach
Continue the full explanation
You're reading the free preview. Unlock the complete walkthrough, the code editor, test runner and reference solution with Premium.
Editor locked
The code editor is locked for Pro problems. It is only available for free problems. Please upgrade to gain access to the code editor for all problems.