Bilinear Resampling

Blitz3D Forums/Blitz3D Programming/Bilinear Resampling

Krischan
 #1
For my current project I need a bilinear resampling function which is NOT based on Tformfilter and Resizeimage. The goal is to stretch a 64x64 bank to a 256x256 or higher dimensioned bank with bilinear interpolated values. I've setup a quick test with a 4x4 "data image" but there is an error I cant identify. The target size is shown in the green rectangle and you'll notice that the blob is distorted a little bit (it will get even worse if you increase the s# scale variable)

Where is the error? I added some kind of debug logging and the correct results should be:

0, 32, 96,128,128, 96, 32, 0
32, 64,128,160,160,128, 64, 32
96,128,191,223,223,191,128, 96
128,160,223,255,255,223,160,128
128,160,223,255,255,223,160,128
96,128,191,223,223,191,128, 96
32, 64,128,160,160,128, 64, 32
0, 32, 96,128,128, 96, 32, 0

but they are

0, 32, 64, 64, 64, 32, 0, 0
32, 96,160,160,160, 96, 32, 16
64,160,255,255,255,160, 64, 32
64,160,255,255,255,160, 64, 32
64,160,255,255,255,160, 64, 32
32, 96,160,160,160, 96, 32, 16
0, 32, 64, 64, 64, 32, 0, 0
0, 16, 32, 32, 32, 16, 0, 0

Please help, I'm stuck there :-/

Graphics 400,300,32,2

width=4
Height=4
s#=2.0

Restore Image
Dim Heightmap(width,Height)

For Y=0 To width-1
	For X=0 To Height-1
		Read Heightmap(x,y)
	Next
Next

Scale(s,width,Height)
Color 0,128,0 : Rect 16,16,64*s,64*s,0

While Not KeyHit(1)
	
	rgb=(ReadPixel(MouseX(),MouseY(),FrontBuffer()) And $ff0000) / $10000
	
	Color   0,  0,  0 : Rect 0,0,24,16,1
	Color 255,255,255 : Text 0,0,rgb
	
	Flip
	
Wend

End

Function Bilinear#(x#,y#)
	
	Local x0#=Floor(x)
	Local y0#=Floor(y)
	Local dx#=x-x0
	Local dy#=y-y0
	
	Local r0=Heightmap(x0,y0)
	Local r1=Heightmap(x0+1,y0)
	Local r2=Heightmap(x0+1,y0+1)
	Local r3=Heightmap(x0,y0+1)
	
	Return LinearInterpolate(LinearInterpolate(r0,r1,dx),LinearInterpolate(r3,r2,dx),dy)
	
End Function

Function Scale(ratio#,width%,height%)
	
	Local x%,y%,c%
	
	For y=0 To (height*ratio)-1
		
		out$=""
		
		For x=0 To (width*ratio)-1
			
			Local u# = x*1.0/ratio
			Local v# = y*1.0/ratio
			
			c=Bilinear(u,v)
			
			Color c,c,c
			Rect (x+1)*16,(y+1)*16,16,16,1
			
			out$=out$+Fill(c,3)
			If x<(width*ratio)-1 Then out$=out$+","
			
		Next
		
		DebugLog out
		
	Next
	
End Function

Function LinearInterpolate#(x1#,x2#,mu#=0.5)
	
	Return (x1*(1.0-mu)+x2*mu)
	
End Function

Function Fill$(number%,lenght%=2)
	
	Local r$=""
	
	For i=1 To lenght-Len(Str(number))
		
		r$=r$+" "
		
	Next
	
	Return r$+Str(number)
	
End Function

.Image
Data   0, 64, 64,  0
Data  64,255,255, 64
Data  64,255,255, 64
Data   0, 64, 64,  0


Subirenihil
 #2
First off, your target values are a little off (on the edges, how can {0,64,64,0} expand into {0,32,96,128,128,96,32,0} - linear interpolation is about {0,32,64,64,64,64,32,0} while spline interpolation is about {0,36,64,80,80,64,36,0}).

What it looks like you are trying to do is expand the image from
0.0 _ 1.0 _ 2.0 _ 3.0
to
0.0 _ 0.4 _ 0.9 _ 1.3 _ 1.7 _ 2.1 _ 2.6 _ 3.0
but you are coding it to expand to
0.0 _ 0.5 _ 1.0 _ 1.5 _ 2.0 _ 2.5 _ 3.0 _ 3.5
which shifts it off center.

The following is what you (inadvertently) are doing (the xx's are the interpolated values, the numbers are what you have in your array):
 00  xx  64  xx  64  xx  00  xx (00)
 XX  xx  XX  xx  XX  xx  XX  xx (00)
 64  xx 255  xx 255  xx  64  xx (00)
 XX  xx  XX  xx  XX  xx  XX  xx (00)
 64  xx 255  xx 255  xx  64  xx (00)
 XX  xx  XX  xx  XX  xx  XX  xx (00)
 00  xx  64  xx  64  xx  00  xx (00)
 XX  xx  XX  xx  XX  xx  XX  xx (00)
(00)(00)(00)(00)(00)(00)(00)(00)(00)

The parentheses are around array values that you didn't think you were accessing (they are also the pixels that are beyond the edge of the image).

I have modified your code 2 ways; the first is scaling the same amount you were scaling it but centered, the second scales it so that the corners are still in the corners.

Version 1 gives:
-0.25 _ 0.25 _ 0.75 _ 1.25 _ 1.75 _ 2.25 _ 2.75 _ 3.25
Version 2 gives:
0.0 _ 0.4 _ 0.9 _ 1.3 _ 1.7 _ 2.1 _ 2.6 _ 3.0

Version 1:
Graphics 400,300,32,2

Global width=4				;<----- Made this global
Global Height=4				;<----- Made this global
s#=2.0

Restore Image
Dim Heightmap(width,Height)

For Y=0 To width-1
	For X=0 To Height-1
		Read Heightmap(x,y)
	Next
Next

Scale(s,width,Height)
Color 0,128,0 : Rect 16,16,64*s,64*s,0

While Not KeyHit(1)
	
	rgb=(ReadPixel(MouseX(),MouseY(),FrontBuffer()) And $ff0000) / $10000
	
	Color   0,  0,  0 : Rect 0,0,24,16,1
	Color 255,255,255 : Text 0,0,rgb
	
	Flip
	
Wend

End

Function Bilinear#(x#,y#)
	
	Local x0#=Floor(x)
	Local y0#=Floor(y)
	Local x1#=Floor(x+1)					;<----- Added this line (Looks redundant, but isn't - these variables
	Local y1#=Floor(y+1)					;<----- Added this line    prevent reading from the wrong pixel.
	Local dx#=x-x0						;                          For example: x=-.25, y=-.25
	Local dy#=y-y0						;                              x0=-1, y0=-1, x1=0, y1=0
								;                          The problem comes when <x0> and <y0> get changed to 0
	x02x=1							;<----- Added this line    because negative numbers are not allowed to access
	x03x=1							;<----- Added this line    an array. If I didn't use <x1> and <y1>, I would read from
	y02x=1							;<----- Added this line    <Heightmap(x0+1,x0+1)> i.e. <Heightmap(1,1)>, not from
	y03x=1							;<----- Added this line    <Heightmap(0,0)> like we should
								;<----- Added this line
	If x0<0 Then x02x=0					;<----- Added this line
	If x1>width-1 Then x03x=0				;<----- Added this line
	If y0<0 Then y02x=0					;<----- Added this line
	If y1>height-1 Then y03x=0				;<----- Added this line
								;<----- Added this line
	If x02x=0 Then x0=0					;<----- Added this line ("r-whatever" is going to be zero, so just make sure we
	If y02x=0 Then y0=0					;<----- Added this line    don't get a "array out of bounds" error)
	If x03x=0 Then x1=0					;<----- Added this line ("r-whatever" is going to be zero, so just make sure we
	If y03x=0 Then y1=0					;<----- Added this line    don't get a "array out of bounds" error)
								;<----- Added this line
	Local r0=Heightmap(x0,y0)*x02x*y02x			;<----- Added "*x02x*y02x" to this line (makes it 0 if either value is out of bounds)
	Local r1=Heightmap(x1,y0)*x03x*y02x			;<----- Added "*x03x*y02x" to this line (makes it 0 if either value is out of bounds)
	Local r2=Heightmap(x1,y1)*x03x*y03x			;<----- Added "*x03x*y03x" to this line (makes it 0 if either value is out of bounds)
	Local r3=Heightmap(x0,y1)*x02x*y03x			;<----- Added "*x02x*y03x" to this line (makes it 0 if either value is out of bounds)

	Return LinearInterpolate(LinearInterpolate(r0,r1,dx),LinearInterpolate(r3,r2,dx),dy)
	
End Function

Function Scale(ratio#,width%,height%)
	
	Local x%,y%,c%
	
	For y=0 To (height*ratio)-1
		
		out$=""
		
		For x=0 To (width*ratio)-1
			
			Local u# = ((x+.5)*1.0/ratio)-.5	;<----- Changed the formula to be centered on the pixel
			Local v# = ((y+.5)*1.0/ratio)-.5	;<-----  rather than the upper-left corner of the pixel
						
			c=Bilinear(u,v)
			
			Color c,c,c
			Rect (x+1)*16,(y+1)*16,16,16,1
			
			out$=out$+Fill(c,3)
			If x<(width*ratio)-1 Then out$=out$+","
			
		Next
		
		DebugLog out
		
	Next
	
End Function

Function LinearInterpolate#(x1#,x2#,mu#=0.5)
	
	Return (x1*(1.0-mu)+x2*mu)
	
End Function

Function Fill$(number%,lenght%=2)
	
	Local r$=""
	
	For i=1 To lenght-Len(Str(number))
		
		r$=r$+" "
		
	Next
	
	Return r$+Str(number)
	
End Function

.Image
Data   0, 64, 64,  0
Data  64,255,255, 64
Data  64,255,255, 64
Data   0, 64, 64,  0


Version 2:
Graphics 400,300,32,2

Global width=4				;<----- Made this global
Global Height=4				;<----- Made this global
s#=2.0

Restore Image
Dim Heightmap(width,Height)

For Y=0 To width-1
	For X=0 To Height-1
		Read Heightmap(x,y)
	Next
Next

Scale(s,width,Height)
Color 0,128,0 : Rect 16,16,64*s,64*s,0

While Not KeyHit(1)
	
	rgb=(ReadPixel(MouseX(),MouseY(),FrontBuffer()) And $ff0000) / $10000
	
	Color   0,  0,  0 : Rect 0,0,24,16,1
	Color 255,255,255 : Text 0,0,rgb
	
	Flip
	
Wend

End

Function Bilinear#(x#,y#)
	
	Local x0#=Floor(x)
	Local y0#=Floor(y)
	Local x1#=Floor(x+1)					;<----- Added this line (Looks redundant, but isn't - these variables
	Local y1#=Floor(y+1)					;<----- Added this line    prevent reading from the wrong pixel.
	Local dx#=x-x0						;                          For example: x=-.25, y=-.25
	Local dy#=y-y0						;                              x0=-1, y0=-1, x1=0, y1=0
								;                          The problem comes when <x0> and <y0> get changed to 0
	x02x=1							;<----- Added this line    because negative numbers are not allowed to access
	x03x=1							;<----- Added this line    an array. If I didn't use <x1> and <y1>, I would read from
	y02x=1							;<----- Added this line    <Heightmap(x0+1,x0+1)> i.e. <Heightmap(1,1)>, not from
	y03x=1							;<----- Added this line    <Heightmap(0,0)> like we should
								;<----- Added this line
	If x0<0 Then x02x=0					;<----- Added this line
	If x1>width-1 Then x03x=0				;<----- Added this line
	If y0<0 Then y02x=0					;<----- Added this line
	If y1>height-1 Then y03x=0				;<----- Added this line
								;<----- Added this line
	If x02x=0 Then x0=0					;<----- Added this line ("r-whatever" is going to be zero, so just make sure we
	If y02x=0 Then y0=0					;<----- Added this line    don't get a "array out of bounds" error)
	If x03x=0 Then x1=0					;<----- Added this line ("r-whatever" is going to be zero, so just make sure we
	If y03x=0 Then y1=0					;<----- Added this line    don't get a "array out of bounds" error)
								;<----- Added this line
	Local r0=Heightmap(x0,y0)*x02x*y02x			;<----- Added "*x02x*y02x" to this line (makes it 0 if either value is out of bounds)
	Local r1=Heightmap(x1,y0)*x03x*y02x			;<----- Added "*x03x*y02x" to this line (makes it 0 if either value is out of bounds)
	Local r2=Heightmap(x1,y1)*x03x*y03x			;<----- Added "*x03x*y03x" to this line (makes it 0 if either value is out of bounds)
	Local r3=Heightmap(x0,y1)*x02x*y03x			;<----- Added "*x02x*y03x" to this line (makes it 0 if either value is out of bounds)

	Return LinearInterpolate(LinearInterpolate(r0,r1,dx),LinearInterpolate(r3,r2,dx),dy)
	
End Function

Function Scale(ratio#,width%,height%)
	
	Local x%,y%,c%
	Local ratio2w#=(ratio#*width-1)/(width-1.0)		;<----- Added this line
	Local ratio2h#=(ratio#*height-1)/(height-1.0)		;<----- Added this line
	
	For y=0 To (height*ratio)-1
		
		out$=""
		
		For x=0 To (width*ratio)-1
			
			Local u# = x*1.0/ratio2w#	;<----- Changed the formula to be corner to corner
			Local v# = y*1.0/ratio2h#	;<-----  rather pull a bit of black from beyond the edges
						
			c=Bilinear(u,v)
			
			Color c,c,c
			Rect (x+1)*16,(y+1)*16,16,16,1
			
			out$=out$+Fill(c,3)
			If x<(width*ratio)-1 Then out$=out$+","
			
		Next
		
		DebugLog out
		
	Next
	
End Function

Function LinearInterpolate#(x1#,x2#,mu#=0.5)
	
	Return (x1*(1.0-mu)+x2*mu)
	
End Function

Function Fill$(number%,lenght%=2)
	
	Local r$=""
	
	For i=1 To lenght-Len(Str(number))
		
		r$=r$+" "
		
	Next
	
	Return r$+Str(number)
	
End Function

.Image
Data   0, 64, 64,  0
Data  64,255,255, 64
Data  64,255,255, 64
Data   0, 64, 64,  0


I'm not going to try to make a spline interpolation function right now, its a bit more complex and it's getting late for me. Hope one of these works for ya (I personally prefer version 1, but that's just me)

Krischan
 #3
Thank you! For my test data I compared the debug entries with the results I got in Photoshop, dunno which bilinear filter they use. But after hours of testing I found that your second solution is brilliant for my needs. I am now able to "resize" a 64x64 heightmap part to 512x512, blend it with a fractal image and get 8 times higher resolution with it and maintaining the basic heightmap structure (in just 200ms). And it is still tileable after that!

Subirenihil
 #4
Ah, Photoshop likely (don't know if you changed any setting when you resized your test image) used a fancier function to enlarge it.

My code could probably be optimized to be more efficient, but glad to have helped.

Now...which version goes in the code archives....?