# Consistent reconstruction of image from partial images

I am given a set of $$N = 649$$ color PNG images, each of size $$W \times H \times 3 = 586 \times 689 \times 3$$. The corresponding pixels in each image represent the same object. Many of the pixels in each image are black $$(0,0,0)$$ which corresponds to "no data" for that image. Below are the top portions of four of those images (from scans of a golf course — note the green with sand traps is on the left). Note that the corresponding colors vary a bit and some color pixels are "outliers."

I want to create a single image that contains the "best representative color" of each pixel (ignoring black pixels). For each pixel I could identify "outlier colors" (e.g. via RANSAC) and just store the mean of the inlier colors. Are there other approaches? Find dominant cluster?

EDIT:

I simply picked the color whose sum of distances from all the other colors was the smallest which is similar to the geometric median:

$$\bar{{\bf x}} = \underset{{\bf x}_j}{\operatorname{argmin}} \sum_i \left\| {\bf x}_i - {\bf x}_j \right\|_2$$

Evidently the geometric mean can handle up to half of the values being outliers which is perfect for this. Produced a very nice result:

• well, considering this closely: what is this "best" you're referring to? minimum per-pixel square error to some known ground truth? minimum global square error? Is square error even a good metric? But, to be positive about this: well, I'd start with doing something like a median of all non-zero versions of each pixel position and look at whether that's good enough. May 23, 2023 at 22:23
• Best would be the average of all the inliers. Since they are color / 3D values there is no clear median. May 23, 2023 at 22:34
• well, but if you have a mathematical description ("average" is directly applicable as a formula), what's stopping you from implementing that? (By the way, "median" is also clearly defined for anything that can be ordered, so not sure how there could be "no clear median"; unless you don't want to introduce an ordering) May 23, 2023 at 22:38
• What is stopping me is discarding outliers which will badly skew the average. You can order 3D points, but there is no obvious multidimensional ordering that effectively gives you the "center point" sans outliers. May 23, 2023 at 23:32
• @wcochran, If you try to build the image from pixels, I think there could be much better solution then working pixel pixel.
– Royi
May 28, 2023 at 6:37

OK, This is a really nice problem.

To illustrate the problem with your approach above.
I will do that in 1D so it converges to the mean.

Imagine the following data at some part of the grid:

The estimated line is the average value of available lines.
The problem is nothing keeps from the jumps when observing the data over the axis (Spatially in 2D).
There are jumps which should be suppressed.

The way to suppress this is to add some kind of of spatial regularization.
In the synthetic case I built I added an assumption which should hold for the dat you have as well.
While their base values can be different due to different lightening conditions the spatial behavior should be similar.
Namely the local gradients should be similar.

This gives us something to use.
Specifically we force the derivative of the solution to have similar derivative of the input signals which doesn't happen above.

In order to do so we can build the following optimization problem:

$$\arg \min_{\boldsymbol{x}} \frac{1}{2} \sum_{i} {\left\| \boldsymbol{x} - \boldsymbol{y}_{i} \right\|}_{2}^{2} + \frac{\lambda}{2} \sum_{i} {\left\| \boldsymbol{D} \boldsymbol{x} - \boldsymbol{D} \boldsymbol{y}_{i} \right\|}_{2}^{2}$$

Where $$\boldsymbol{D}$$ is the finite difference operator.

Basically we demand both the output value to be an average and the gradient to be an average.

Remarks:

• The problem is convex, hence the process of solving it should be pretty robust.
• You may be creative with the form above. For instance, you require equality and not only averaging of the gradient.
• For 2D you should have a term for each of the gradient directions.
• For color images you may do it per channel or build a vectroized form.

The problem, even in 2D, is very easy to solve.

• This discontinuities do yield creases and your solution would handle that. Nice. I'll need to ponder it some more. Jul 14, 2023 at 0:09
• Nice! I learned something here! Jul 14, 2023 at 3:02
• @CrisLuengo, How would you define the directional derivative over RGB image? I know the work in the context of PDE (David Tschumperl´ - Fast Anisotropic Smoothing of Multi Valued Images using Curvature-Preserving PDE’s), I wonder if there is a measure which works under ${L}_{2}$ norm which is more advanced then just take all 3 vectors.
– Royi
Jul 14, 2023 at 7:52
• That is something that doesn’t have a solution, as far as I know. The Jacobian is the generalization of the gradient to vector functions, but that is just the gradient of each channel as rows of a matrix. It doesn’t really simplify things… Jul 14, 2023 at 12:48
• Yea, I know the Jacobian, problem is under Frobenious Norm it will be just like working per channel. I am looking for something that have a real vector field like meaning.
– Royi
Jul 14, 2023 at 13:03