Sign in to follow this  
mrpyo

Interpolation of values on random points in 2D

Recommended Posts

Lets say I have input image like this:

 

X5r87Tr.png

 

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:

 

jHAZ3as.png

 

As opposed to:

 

jhyQJ01.png

 

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?:

 

FYpXEcb.png

 

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 this post


Link to post
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[i][j] - f[i-1][j] - f[i+2][j], 2) + pow(2*f[i][j] - f[i][j-1] - f[i][j+1], 2)))

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

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this