Archived

This topic is now archived and is closed to further replies.

dnagcat

patch a rectangle...should be easy?

Recommended Posts

I have an array of pixels...greyscale of which I have the values of the border pixels, ie: 2 3 2 7 3 4 2 3 0 0 0 0 0 8 9 0 0 0 0 0 5 5 0 0 0 0 0 2 9 0 0 0 0 0 3 3 7 1 1 9 3 4 so the goal is to fill the 0s in such a away that all borders are smooth... I tried linear interpolation but this works well in only one direction or the other (ie left to right, or top to bottom)... I tried a custom version of bilinear interpolation but the weights don't work right... ie... ........4.. ........0.. 9 0 0 0 x 5 ........0.. ........0.. ........3.. a = x / width - 1; b = y / height - 1; for the four points I used 4, 3, 5, 9 I need to know from somebody with this type of experience what might be the best strategy... Thanks, DNAGCAT [edited by - dnagcat on May 20, 2004 1:31:22 PM]

Share this post


Link to post
Share on other sites
that is a good idea, and actually that was my first attempt to solve the problem...but the edges aren''t continuous with the given pixels around the "hole"... instead of divide by 2 I multiplied horiz and vert linear interpolations by weights in an attempt to fix this, but it looked very artificial (kind of like a square pyramid)...

In researching all over google this doesn''t seem like an easy problem...I wish somebody knew of a good resource or keyword that better explains this problem...

Share this post


Link to post
Share on other sites
Hey!

VERY NICE PROBLEM!!!

The thing you're looking for is Laplace's equation with Dirichlet boundary conditions.

Well, I guess you are not a mathematician, so a few words might help here.

There is a very nice and very smooth way to connect all these vertices. But to get the inner greyscales, you need to solve a so-called Laplace problem:

u_xx (x,y) + u_yy (x,y) = 0 for (x,y) in Omega
u(x,y) = u_0(x,y) for (x,y) in boundary(Omega)

u(x,y) is the function of your greyscales (not discretized yet) and u_xx and u_yy is the second derivative in x and y direction, resp. The domain Omega is just a square. The function u_0 lives on the boundary of the square and contains the boundary values you gave above.

The goal is to solve the equations above. It's a linear partial differential equation. The boundary values are "Dirichlet", that means their function value is given. (Alternatively, one could also give normal derivatives --> Neumann boundary conditions).

You solve it by first discretizing the derivatives.
For example

u_xx --> u(x+1,y )-2*u(x,y)+u(x-1,y )
u_yy --> u(x ,y+1)-2*u(x,y)+u(x ,y-1)

Imagine u(x,y) as a matrix now. The size of this matrix coincides with the size of your grayscale image. If you plug this into the equations above, you will (after a while) obtain a linear system of equations. So if you have a solver for this, it's not a problem.

This is the result I obtained with MATLAB (a software for mathematical stuff). The program is about 10 lines in MATLAB.


2.0 3.0 2.0 7.0 3.0 4.0 2.0
3.0 1.6 1.6 3.4 4.0 3.7 8.0
9.0 3.0 1.6 1.7 3.0 3.1 5.0
5.0 4.6 2.6 2.2 1.7 2.8 2.0
9.0 4.4 2.3 3.7 3.5 2.1 3.0
3.0 7.0 1.0 1.0 9.0 3.0 4.0


Laplace's equation is actually not the most straight-forward method, I admit. But it will give you the smoothest results - I will guarantee you.

If you need it just for one image, please be free to tell me where I can download it. Then I can plug it into my program and give you the result.


[edited by - Lutz on May 21, 2004 4:19:02 AM]

Share this post


Link to post
Share on other sites
In your particular case, you should find a "bezier like curve" for each side.
With such curves defined you should be able to use a patch.

In this case, the "bezier like curve" should be something like f(t) = a*t^6 + b*t^5 + c*t^4 + d*t^3 + e*t^2 + f*t + g where a,b,c,d,e,f & g are the unknowns. This is true as long as you keep the same size for the rectangle sides (7 values for each side)
You will have to find a way to solve the previous equation, I dont know precisely how to do it but it should be using determinant and stuff.

I didnt experienced all this, I just deduced it from all I rode on the patch and bezier curves subjects so I''mnt sur it works

Share this post


Link to post
Share on other sites
quote:
Original post by MV
You will have to find a way to solve the previous equation

I mean you will have to find the a,b,c,d,e,f&g unknowns.

Share this post


Link to post
Share on other sites
Interesting information Lutz... Looks like some linear algebra and calculus...Damn, I knew there was no easy answer... Actually this is for a patch tool feature my boss wants me to add to our software...a 2D/3D modeller.

Thanks everybody!

Share this post


Link to post
Share on other sites
If you don''t want to use a linear system solver, you can also approximatively solve the problem using this pseudo code:


for eyery inner node v (the ones filled with 0 at the beginning)
v = ( node left of v
+ node right of v
+ node above of v
+ node below of v
+ 4*v) / 8


Do this maybe 10-100 times and you should get a good approximation to the "true" solution. It is actually very easily implemented.

Share this post


Link to post
Share on other sites
I see. An interesting strategy...

I''ve sent you an email to request your matlab code. Hope to hear from you soon.

DNAGCAT

Share this post


Link to post
Share on other sites