Photo Consistency Check

A 3D point is photo-consistent if, when projected into several calibrated images, its observed colors are very similar across views, i.e., the per-channel color variance across views is below a given threshold. In this problem, you are given the colors of that point in multiple views and must decide, channel-wise, whether the variance is small enough.

---

1. Background Knowledge (Key Concepts)

• Multi-view stereo (MVS): MVS uses multiple calibrated images of a scene to reconstruct dense 3D geometry. Given camera parameters and images, candidate 3D points are projected into each view, and their photometric consistency (color similarity) is used as a cue for whether the 3D point is likely to be real.

• Photometric (photo) consistency: If a 3D point truly lies on a physical surface, then its projections in different views should have similar appearance (e.g., RGB values), up to lighting or noise. One common way to measure this is to compute the variance of the observed colors across views: low variance ⇒ similar colors ⇒ consistent; high variance ⇒ likely wrong 3D point (e.g., on background, occluded, or mismatched).

• Channel-wise checking: Colors are usually represented as 3 channels (e.g., R, G, B). To be strict, the point must be consistent in each channel, so you compute variance independently for each channel and fail if any channel exceeds the threshold.

---

2. Algorithm / Approach Pattern

The generic pattern to solve this problem:

1. For each color channel (R, G, B or similar):

• Collect the color values of that channel from all views.
• Compute the mean of these values.
• Compute the variance using the given formula.
• Compare the variance to the threshold squared, $\tau^2$.

2. If all channels have variance < $\tau^2$, the point is photo-consistent; otherwise, it is not.

This is essentially a per-dimension variance test on a small 1D sample (the colors across views) for each channel.

---

3. Step-by-Step Strategy

Assume:

• You have $N$ views.
• Colors are given as something like (R_i, G_i, B_i) for view i.
• Threshold is tau.

Steps:

1. Separate channels

• Create three arrays:
• R = [R_1, R_2,..., R_N]
• G = [G_1, G_2,..., G_N]
• B = [B_1, B_2,..., B_N]

2. Define a helper to compute variance (as in the formula):

• Mean: $\bar{c} = \frac{1}{N}\sum_{i=1}^{N} c_i$
• Variance (using the provided definition with divisor $N$): $\sigma^2 = \frac{1}{N}\sum_{i=1}^{N} (c_i - \bar{c})^2$

3. Compute per-channel variance

• varR = variance(R)
• varG = variance(G)
• varB = variance(B)

4. Compare with threshold

• Given tau, compute tau2 = tau * tau.
• Check:
• consistentR = (varR < tau2)
• consistentG = (varG < tau2)
• consistentB = (varB < tau2)

5. Final decision

• Point is photo-consistent if: consistentR && consistentG && consistentB
• Otherwise, not consistent.

Example-style pseudocode

def is_photo_consistent(colors, tau):
 # colors: list of (R, G, B) tuples across N views
 N = len(colors)

 # Split channels
 R = [c for c in colors]
 G = [c for c in colors]
 B = [c for c in colors]

 def variance(vals):
 n = len(vals)
 mean = sum(vals) / n
 return sum((v - mean) ** 2 for v in vals) / n # matches given formula

 tau2 = tau * tau
 varR = variance(R)
 varG = variance(G)
 varB = variance(B)

 return (varR < tau2) and (varG < tau2) and (varB < tau2)

---

4. Common Pitfalls

• Using the wrong variance formula: The problem uses $\frac{1}{N}$, not $\frac{1}{N-1}$. Make sure your implementation matches exactly.

• Comparing to $\tau$ instead of $\tau^2$: The condition is $\sigma^2 < \tau^2$, so either:

• compute variance and compare with tau * tau, or

• compute standard deviation sqrt(variance) and compare with tau. The first is simpler and avoids a square root.

• Integer division / overflow: If colors and sums are integers, convert to float before division to avoid truncation. In some languages, sum / N can be integer division if not careful.

• Threshold logic: Ensure you implement “if any channel has high variance ⇒ inconsistent” as a logical OR of failures (equivalently, AND of successes for consistency).

---

5. Time & Space Complexity

Let:

• $N$ = number of views (number of color samples for the point)

• $C$ = number of channels (typically 3)

• Time complexity:

• Computing mean for each channel: $O(N)$ per channel.

• Computing variance for each channel: another $O(N)$ per channel.

• Total: $O(C \cdot N)$, which is $O(N)$ for constant $C$ (e.g., RGB).

• Space complexity:

• If you store channel arrays explicitly: $O(C \cdot N)$.

• If you stream values and compute mean/variance on the fly (using a two-pass or online algorithm), you can reduce extra space to $O(1)$ besides input storage. For most coding problems, treating it as $O(N)$ input space and $O(1)$ extra space is sufficient.