Interpolation of values on random points in 2D

This topic is 1547 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

Recommended Posts

Lets say I have input image like this:

Blacks represent lack of color (as opposed to black points). Color points are supposed to be 1px x 1px, I made them bigger to make them clearly visible. White lines (and image edges) are borders - if line from one point to another crosses the border, values in between should not be interpolated, so input like this will give following result:

As opposed to:

As you may already figured out, I want to interpolate values of those color points so I will get evenly filled image. Anyone knows how to achieve that?

I thought about approach like this:

1. First convert input image into collection of points with color values.

2. Then, perform delaunay triangulation on those points.

3. Render triangles (leave interpolation to the GPU).

4. Fill the remaining space.

But still it leaves me with problems:

1. How do I efficiently perform first step? Just use a simple iteration over every pixel?

2. How do I avoid creating triangles which edges cross the white border?

4. How do I fill the remaining space?:

Or maybe there is a better way altogether?

Now, I know it's a rather complex problem, but just maybe somebody knows the solution.

Edited by mrpyo

Share on other sites

1. How do I efficiently perform first step? Just use a simple iteration over every pixel?

This part is trivial compared to the rest. Yes, just iterate over the pixels.

2. How do I avoid creating triangles which edges cross the white border?

First I would turn the white lines into a list of segments. Then you can use "restricted Delaunay triangulation".

4. How do I fill the remaining space?

Hey, what happened to question 3? ;)

Most vertices already have colors assigned to them. For vertices on the white lines or on the edges of the image, you can try to average the colors of the neighboring vertices, or something like that. Then you do the kind of interpolation in your image.

Other alternatives:
(1) For each black pixel, find the closest colored pixel, where the distance considers white pixels to be uncrossable. This is some sort of Voronoi diagram. Now consider what happens if you consider coloring a pixel P. Some of the Voronoi regions of nearby colored pixels will be reduced in area. Compute a weighted average of the colored pixels with weights that are proportional to the amount of area lost, and assign that color to P.

(2) Use kriging. This is difficult and I am not an expert, so I won't comment any further.

(3) Consider a potential function that maps any possible coloring to a real number, which computes something like the sum of the squares of the differences between adjacent pixels, ignoring white pixels. Now start with some coloring and use some sort of gradient descent to find a minimum of the potential function, restricted to colorings that agree with the original colors of the non-originally-black pixels. (I think this is similar to computing a solution to a stationary heat equation.)

[EDIT: After thinking about this some more, I particularly like (3). A potential function that would probably work well is

sum_i(sum_j(pow(2*f[j] - f[i-1][j] - f[i+2][j], 2) + pow(2*f[j] - f[j-1] - f[j+1], 2)))

I can provide some code if you want to see how it would work.] Edited by Álvaro

1. 1
2. 2
Rutin
16
3. 3
4. 4
5. 5

• 26
• 11
• 9
• 9
• 11
• Forum Statistics

• Total Topics
633702
• Total Posts
3013451
×