• Announcements

    • khawk

      Download the Game Design and Indie Game Marketing Freebook   07/19/17

      GameDev.net and CRC Press have teamed up to bring a free ebook of content curated from top titles published by CRC Press. The freebook, Practices of Game Design & Indie Game Marketing, includes chapters from The Art of Game Design: A Book of Lenses, A Practical Guide to Indie Game Marketing, and An Architectural Approach to Level Design. The GameDev.net FreeBook is relevant to game designers, developers, and those interested in learning more about the challenges in game development. We know game development can be a tough discipline and business, so we picked several chapters from CRC Press titles that we thought would be of interest to you, the GameDev.net audience, in your journey to design, develop, and market your next game. The free ebook is available through CRC Press by clicking here. The Curated Books The Art of Game Design: A Book of Lenses, Second Edition, by Jesse Schell Presents 100+ sets of questions, or different lenses, for viewing a game’s design, encompassing diverse fields such as psychology, architecture, music, film, software engineering, theme park design, mathematics, anthropology, and more. Written by one of the world's top game designers, this book describes the deepest and most fundamental principles of game design, demonstrating how tactics used in board, card, and athletic games also work in video games. It provides practical instruction on creating world-class games that will be played again and again. View it here. A Practical Guide to Indie Game Marketing, by Joel Dreskin Marketing is an essential but too frequently overlooked or minimized component of the release plan for indie games. A Practical Guide to Indie Game Marketing provides you with the tools needed to build visibility and sell your indie games. With special focus on those developers with small budgets and limited staff and resources, this book is packed with tangible recommendations and techniques that you can put to use immediately. As a seasoned professional of the indie game arena, author Joel Dreskin gives you insight into practical, real-world experiences of marketing numerous successful games and also provides stories of the failures. View it here. An Architectural Approach to Level Design This is one of the first books to integrate architectural and spatial design theory with the field of level design. The book presents architectural techniques and theories for level designers to use in their own work. It connects architecture and level design in different ways that address the practical elements of how designers construct space and the experiential elements of how and why humans interact with this space. Throughout the text, readers learn skills for spatial layout, evoking emotion through gamespaces, and creating better levels through architectural theory. View it here. Learn more and download the ebook by clicking here. Did you know? GameDev.net and CRC Press also recently teamed up to bring GDNet+ Members up to a 20% discount on all CRC Press books. Learn more about this and other benefits here.
Sign in to follow this  
Followers 0
Basiror

bicubic interpolation on image enlargements

16 posts in this topic

Hi I am trying to implement a few image resizing algorithms into my library I know how bicubic reducing works you calculate the destination pixel from the bicubic weights of a 4x4 pixel field around the nearest pixel coordinate in the source image [a href="http://astronomy.swin.edu.au/~pbourke/colour/bicubic/"]becubic interpolation[/a] my problem is how can i enlarge the image e.g.: having a 32*32 image and scale it to 256*256 in order to enlarge i would calculate the 4x4 pixel values out of the 32*32 image and write them to the 256*256 image but in order to do this i hade to interatively rescale 32*32->64*64->128*128->256*256 or is there a simpler solution e.g.: when i downscale i use a 4x4 field so 64*64->32*32 using 4x4 and 256x256->32*32 using a 64x64 field? so i had to distribute one pixel of the 32*32 image to a 64x64 field in the 256*256 image? any idea on how to do this correctly?
0

Share this post


Link to post
Share on other sites
Hi,

you "just" oversample the pickture.

so to go from 32*32 to 256*128 (this is to show you it could be done this way)


dx = 32 / 256;
dy = 32 / 128;

for(int y=0; y < 128; y++)
{
for(int x=0; x < 256; x++)
{
float ix = x*dx;
float iy = y*dy;
float s = ix - (float)((int)(ix+.5));
float t = iy - (float)((int)(iy+.5));
int ox = (int)ix;
int oy = (int)oy;

new_pic[y*256+x] = orig_pic[oy*32+ox]*(1-s)*(1-t)
+ orig_pic[(oy+1)*32+ox]*(1-s)*t
+ orig_pic[oy*32+ox+1]*s*(1-t)
+ orig_pic[(oy+1)*32+ox+1]*s*t;
}
}


0

Share this post


Link to post
Share on other sites
isn t this the bilinear approach?


i just found this link on google
http://www.inq7.net/inf/2003/jun/10/inf_37-2.htm

there they mention SI(staired interpolation which is basically what I mentioned above with 32*32->64*64->128*128->256*256

so maybe I should implement it like that

thx
0

Share this post


Link to post
Share on other sites
just think of it as a texture mapping problem, use bilinear interpolation to smooth it out, if this is giving to blocky results you can smooth further by bluring the input image b4 you do it.
0

Share this post


Link to post
Share on other sites
the problem with bluring is that I want to use it for a heightfield generator
and too blurry heightmaps don t look that good

i just try the SI approach now maybe it delivers acceptable results
0

Share this post


Link to post
Share on other sites
I am still having problems to get this implementation of cubic interpolation to run

I used this article as a basis for the implementation

http://astronomy.swin.edu.au/~pbourke/colour/bicubic/

What I am doing:
1. I calculate the factor sourcesize/destinationsize (images are powers of 2)
2. I loop through the destination coordinates and calculate the corresponding source coordinates "i*fact" & "j*fact"
3.then I find the nearest neightbour pixel and calculate the deltas dx & dy

4. I map the is and js to the source coordinates
5. I loop through the 4x4 field of neighbouring pixes in the source image and try to add them to the destination pixel
the cubicweight function should return the blend factors for each neighbouring pixel but all it does is returning 0s i have already tries to use
"dy - n" and "n - dy" nothing changed though

any idea what's wrong here?
Addition:
In the time gamedev.net has been down I was able to get it to work for downsampling and in comparsion to photoshop the results are at least 10-20x sharper :)

Now all I can t get to work is up sampling, can I use this method for upsampling at all?
or do you just take the source pixels calculate the destination coordinate and write to the current source pixel (i,j) to the destinationpixel (id,jd) +=(i,j)*bicubicweight(parameters...)?




[source lang ="cpp"]
//sample image up( powers of 2)
template<class U, class W> void samplebicubic(const U& s, W& d)
{
uint32 i,j;
int32 is,js,m,n;
float x,y,fact,dx,dy;
float test;

fact = U::MAP_SIZE/ W::MAP_SIZE;

for(i=0;i<W::MAP_SIZE;i++)
{
//calculate source coordinates
x = i * fact;
is = static_cast<int32>(x);
dx = x - is;
is = (is + W::MAP_SIZE)%W::MAP_SIZE;

for(j=0;j<W::MAP_SIZE;j++)
{
//calculate source coordinates
y = j * fact;
js = static_cast<int32>(y);
dy = y - js;
js = (js + W::MAP_SIZE)%W::MAP_SIZE;

d.m_Map[i][j] = 0.0f;
for(m=-1;m<3;m++)
{
for(n=-1;n<3;n++)
{
test = cubicweight(m-dx) * cubicweight(n-dy);
d.m_Map[i][j] += s.m_Map[(is + m + U::MAP_SIZE)%U::MAP_SIZE][(js + n + U::MAP_SIZE)%U::MAP_SIZE]
*test;
}
}
}
}
};






cubic weight function from the article


//cubic weight function
float cubicweight(float x)
{
float result;
float tmp;

//P(x+2)^3
tmp = (x+2)>0?x+2:0;
result = tmp*tmp*tmp;


//-4*P(x+1)^3
tmp = (x+1)>0?x+1:0;
result += -4*tmp*tmp*tmp;

//6*P(x)^3
tmp = x>0?x:0;
result += 6*tmp*tmp*tmp;

//-4P(x-1)^3
tmp = (x-1)>0?x-1:0;
result += -4*tmp*tmp*tmp;

result*=0.1666666f;
return result;
};





[Edited by - Basiror on August 5, 2005 6:32:38 AM]
0

Share this post


Link to post
Share on other sites
If you know how to linearly interpolate from 32,32 to 256,256 then you can do it using cubic, cosine, any other method that uses t from 0 to 1 as a parameter.

For linear interpolation you have

lerp(x,y,t)

to return a value between x and y based on t.

For cubic you have

cubic(a,b,c,d,t)

to return a value between b and c based on t.
0

Share this post


Link to post
Share on other sites
If you're using it for heightfield resizing, and you want "more detail" and don't care whether it's perfect or not, you could try introducing fractal noise to generate some bumpy looking terrain in the expansion gaps.

You can probably look up "Fractal random heightfield generator" in google and find the algorithm that produces random mountains without any source bitmap... and just modify it so that it works to fill in expansion gaps instead.
0

Share this post


Link to post
Share on other sites
I am still having trouble with the bicubic interpolation

i have 2 functions now
one with cubic interpolation and one with b spline cubic interpolation
the first function delivers results comparable with bilinear interpolation
and the second function which uses b splines delivers smoother results than photoshops implementation



here the cubic function:
i get the coordinates in the source image

then i calculate the weights of 4 pixels in a column

and once this is done i calculate the weighted value of the 4 weights
illustrated here

http://www.olympusmicro.com/primer/java/digitalimaging/processing/geometricaltransformation/
any idea what i am doing wrong here?

do i need another interpolation factor or whats wrong here?



//sample image up( powers of 2)
template<class U, class W> void sample_bicubic2(const U& s, W& d)
{
uint32 i,j;
int32 is,js;
float x,y,fact,dx,dy;
int32 XCoords[4];
int32 YCoords[4];
float weights[4];

fact = static_cast<float>(U::MAP_SIZE)/ static_cast<float>(W::MAP_SIZE);

for(i=0;i<W::MAP_SIZE;i++)
{
//calculate source coordinates
x = i * fact;
is = static_cast<int32>(x);
dx = x - is;

XCoords[0] = is-1;
XCoords[1] = is;
XCoords[2] = is+1;
XCoords[3] = is+2;

for(j=0;j<W::MAP_SIZE;j++)
{
//calculate source coordinates
y = j * fact;
js = static_cast<int32>(y);
dy = y - js;

YCoords[0] = js-1;
YCoords[1] = js;
YCoords[2] = js+1;
YCoords[3] = js+2;

weights[0] = cubicweight2(
s.m_Map[(XCoords[0] + U::MAP_SIZE)%U::MAP_SIZE][(YCoords[0] + U::MAP_SIZE)%U::MAP_SIZE],
s.m_Map[(XCoords[0] + U::MAP_SIZE)%U::MAP_SIZE][(YCoords[1] + U::MAP_SIZE)%U::MAP_SIZE],
s.m_Map[(XCoords[0] + U::MAP_SIZE)%U::MAP_SIZE][(YCoords[2] + U::MAP_SIZE)%U::MAP_SIZE],
s.m_Map[(XCoords[0] + U::MAP_SIZE)%U::MAP_SIZE][(YCoords[3] + U::MAP_SIZE)%U::MAP_SIZE],
0.5f);

weights[1] = cubicweight2(
s.m_Map[(XCoords[1] + U::MAP_SIZE)%U::MAP_SIZE][(YCoords[0] + U::MAP_SIZE)%U::MAP_SIZE],
s.m_Map[(XCoords[1] + U::MAP_SIZE)%U::MAP_SIZE][(YCoords[1] + U::MAP_SIZE)%U::MAP_SIZE],
s.m_Map[(XCoords[1] + U::MAP_SIZE)%U::MAP_SIZE][(YCoords[2] + U::MAP_SIZE)%U::MAP_SIZE],
s.m_Map[(XCoords[1] + U::MAP_SIZE)%U::MAP_SIZE][(YCoords[3] + U::MAP_SIZE)%U::MAP_SIZE],
0.5f);

weights[2] = cubicweight2(
s.m_Map[(XCoords[2] + U::MAP_SIZE)%U::MAP_SIZE][(YCoords[0] + U::MAP_SIZE)%U::MAP_SIZE],
s.m_Map[(XCoords[2] + U::MAP_SIZE)%U::MAP_SIZE][(YCoords[1] + U::MAP_SIZE)%U::MAP_SIZE],
s.m_Map[(XCoords[2] + U::MAP_SIZE)%U::MAP_SIZE][(YCoords[2] + U::MAP_SIZE)%U::MAP_SIZE],
s.m_Map[(XCoords[2] + U::MAP_SIZE)%U::MAP_SIZE][(YCoords[3] + U::MAP_SIZE)%U::MAP_SIZE],
0.5f);
weights[3] = cubicweight2(
s.m_Map[(XCoords[3] + U::MAP_SIZE)%U::MAP_SIZE][(YCoords[0] + U::MAP_SIZE)%U::MAP_SIZE],
s.m_Map[(XCoords[3] + U::MAP_SIZE)%U::MAP_SIZE][(YCoords[1] + U::MAP_SIZE)%U::MAP_SIZE],
s.m_Map[(XCoords[3] + U::MAP_SIZE)%U::MAP_SIZE][(YCoords[2] + U::MAP_SIZE)%U::MAP_SIZE],
s.m_Map[(XCoords[3] + U::MAP_SIZE)%U::MAP_SIZE][(YCoords[3] + U::MAP_SIZE)%U::MAP_SIZE],
0.5f);

d.m_Map[i][j] = cubicweight2(weights[0],weights[1],weights[2],weights[3],0.5f);
}
}
};



and here with b splines


//sample image up( powers of 2)
template<class U, class W> void sample_bicubic(const U& s, W& d)
{
uint32 i,j;
int32 is,js,m,n;
float x,y,fact,dx,dy;
float test;

fact = static_cast<float>(U::MAP_SIZE)/ static_cast<float>(W::MAP_SIZE);

for(i=0;i<W::MAP_SIZE;i++)
{
//calculate source coordinates
x = i * fact;
is = static_cast<int32>(x);
dx = x - is;
//is = (is + W::MAP_SIZE)%W::MAP_SIZE;

for(j=0;j<W::MAP_SIZE;j++)
{
//calculate source coordinates
y = j * fact;
js = static_cast<int32>(y);
dy = y - js;
//js = (js + W::MAP_SIZE)%W::MAP_SIZE;

d.m_Map[i][j] = 0.0f;
for(m=-1;m<3;m++)
{
test = cubicweight(dx-m);
for(n=-1;n<3;n++)
{

d.m_Map[i][j] += s.m_Map[(is + m + U::MAP_SIZE)%U::MAP_SIZE][(js + n + U::MAP_SIZE)%U::MAP_SIZE]
*test* cubicweight(dy-n);;
//std::cout<<std::endl;
}

}
}
}
};
//cubic weight function
float cubicweight(float x)
{
float result;
float tmp;

//P(x+2)^3
tmp = (x+2)>0?x+2:0;
result = tmp*tmp*tmp;


//-4*P(x+1)^3
tmp = (x+1)>0?x+1:0;
result += -4*tmp*tmp*tmp;

//6*P(x)^3
tmp = x>0?x:0;
result += 6*tmp*tmp*tmp;

//-4P(x-1)^3
tmp = (x-1)>0?x-1:0;
result += -4*tmp*tmp*tmp;

result*=0.1666666f;
return result;
};

0

Share this post


Link to post
Share on other sites
Your t=0.5 is not right, the value of t depends on the source size, dest size, and the current dest pixel, so most definitely you shouldn't hard code it to 0.5.

I'll post some code that works a little later if you can't figure it out, don't have time now.
0

Share this post


Link to post
Share on other sites
0.5f would actually be the same as bilinear interpolation

i could find anything about the correct blend factors :(

i have search on google for hours and couldn t find any decent article that doesn t only give your the formula

the only think i found was the b spline approach which works but delivers too smooth results

thx in advance
0

Share this post


Link to post
Share on other sites
Alright, here goes


// x,y coords for pixels in old and new images
float ox,oy;
int nx,ny;

// temp
pixel t[4];

dx = oldwidth / newwidth;
dy = oldheight / newheight;

for (ny = 0; ny < newheight; ++ny)
{
oy = ny * dy;

for (nx = 0; nx < newwidth; ++nx)
{
ox = nx * dx;

// ox.frac, oy.frac represent fractional portions of ox,oy
// i.e. for ox=4.15, ox.frac=0.15
// oimg, nimg are image buffers

t[0] = interpolate(oimg[ox - 1,oy - 1], oimg[ox,oy - 1], oimg[ox + 1,oy - 1], oimg[ox + 2,oy - 1], ox.frac);
t[1] = interpolate(oimg[ox - 1,oy], oimg[ox,oy], oimg[ox + 1,oy], oimg[ox + 2,oy], ox.frac);
t[2] = interpolate(oimg[ox - 1,oy + 1], oimg[ox,oy + 1], oimg[ox + 1,oy + 1], oimg[ox + 2,oy + 1], ox.frac);
t[3] = interpolate(oimg[ox - 1,oy + 2], oimg[ox,oy + 2], oimg[ox + 1,oy + 2], oimg[ox + 2,oy + 2], ox.frac);

nimg[nx,ny] = interpolate(t[0],t[1],t[2],[3], oy.frac);
[Edit]// Sorry, should have been interpolate() not cubic(), in case anyone else is looking at this.
}
}

pixel interpolate(pixel a,b,c,d, t)
{
return pixel(
cubic(a.r, b.r, c.r, d.r, t),
cubic(a.g, b.g, c.g, d.g, t),
cubic(a.b, b.b, c.b, d.b, t),
);
}

cubic(v0,v1,v2,v3, t)
{
int p = (v3 - v2) - (v0 - v1);
int q = (v0 - v1) - p;
int r = v2 - v0;
int s = v1;
float tSqrd = t * t;

return (p * (tSqrd * t)) + (q * tSqrd) + (r * t) + s;
}


[Edited by - outRider on August 8, 2005 11:43:19 AM]
0

Share this post


Link to post
Share on other sites
thx it works now

I searched on google for some information on cubic interpolation and especially the weight factors and there s absolutely no useful information maybe one should write a little tutorial about it

this is when I swap the interpolation factors, e.g.: xfrac for y axis
it uses SI (stepping interpolation) size*2 per step
after the cubic filter I applied 4 smooths to get this result

here are the results
1. my cubic filter

2. photoshop's cubic filter



without swapping it get results a little bit sharper then photoshop's
0

Share this post


Link to post
Share on other sites
Using xfrac on the y-axis and vice versa will give you incorrect results, your result looks a little stretched to me, but if that's what you prefer it won't matter as much for something like a greyscale heightmap, but for enlarging images I think it won't look good at all.

And if you use something like what I posted you don't need to size by stepping, you can directly go from 32,32 to 256,256. It should be much faster.
0

Share this post


Link to post
Share on other sites
yeah right it looks a little bit streched, the next thing ill do is blend it with several octaves as descriped in the simple clouds tutorial this should result in a decent heightmap for terrains and with exponential filter i can use it for clouds
0

Share this post


Link to post
Share on other sites
The quoted code for "cubic" cannot be correct. cubic(255,255,255,85,0.811) = 276
no way can a correct interpolated result be greater than any of the inputs.
0

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  
Followers 0