1D deocclusion
- 4 mins1-D deocclusion formulation
Let $N$ be the frame width. We observe a sequence of binary frames of length $T$. We wish to recover three unknowns:
- Object mask $O \in {0,1}^N$
- Occluder support mask $M \in {0,1}^N$ (where $M_i = 1$ indicates visible, $0$ indicates occluded)
- Initial offset $a \in \mathbb{Z}$
Motion is a constant unit step: $d=+1$ for rightward, $d=-1$ for leftward. Define the shift operator $S_h$ on a length-$N$ vector by
$$ (S_h O)_i = \begin{cases} O_{i - h}, & \text{if } i - h \in \{0,\dots,N-1\} \\ 0, & \text{otherwise} \end{cases} $$
Each observed frame is generated by shifting and masking:
$$ F_t = S_{\,a + t}\,O \;\land\; M,\quad\quad t=0,1,\dots,T-1, $$
Here $\land$ is bitwise AND, forcing occluded bits to zero. The inverse problem is:
Given ${F_t}$, find all $(O, M, a)$ satisfying the above equations.
Code implementation
import numpy as np
def solve_for_OM(frames, a, d):
"""
Given frames and known a, d, solves for O and M.
Args:
frames: List of 1D numpy arrays (binary masks)
a: Known initial offset (integer)
d: Known direction (+1 or -1)
Returns:
O: Reconstructed object shape (1D numpy array)
M: Reconstructed occluder mask (1D numpy array)
"""
N = len(frames[0])
T = len(frames)
M = (np.var(frames,axis=0)>0).astype(np.int32)
# Now reconstruct minimal O using only definitely visible information
O_final = np.zeros(N, dtype=int)
for i in range(N):
# Position i should be 1 in O if it appears as 1 in any frame when shifted back
for t in range(T):
shift_amount = a + d * t
if 0 <= i - shift_amount < N:
if frames[t][i] == 1 and M[i] == 1:
O_final[i - shift_amount] = 1
# Final verification
for t in range(T):
shifted_O = shift_array(O_final, a + d * t, N)
expected_frame = shifted_O & M
if not np.array_equal(expected_frame, frames[t]):
raise ValueError("Reconstructed O and M don't match frames")
return O_final, M
def shift_array(arr, shift, N):
"""Same as before"""
result = np.zeros(N, dtype=int)
if shift >= 0:
if shift < N:
result[shift:] = arr[:N-shift]
else:
if -shift < N:
result[:N+shift] = arr[-shift:]
return result
Test case
if __name__ == "__main__":
# Test case where O[-1] = 0
N = 8
O_true = np.ones(N, dtype=int)
O_true[-1] = 0
M_true = np.array([1,1,1,0,0,0,1,1], dtype=int)
a_true = 0
d_true = 1
T = 8
# Generate frames
frames = []
for t in range(T):
shifted_O = shift_array(O_true, a_true + d_true * t, N)
frames.append(shifted_O & M_true)
# Solve for O and M
O, M = solve_for_OM(frames, a_true, d_true)
print(f"O: {O}")
print(f"M: {M}")
# Verify solution matches input
assert np.array_equal(O, O_true)
assert np.array_equal(M, M_true)
O: [1 1 1 1 1 1 1 0]
M: [1 1 1 0 0 0 1 1]
Generalization: replace $a \pm t$ by any known shift function $h(t)\in\mathbb Z$. Any binary masks $O$ and $M$ are allowed; the only requirement is that over some frames each object bit must be visible at least once.