Faster Cubic Interpolation

Post your FreeBASIC tips and tricks here. Please don’t post your code without including an explanation.
Zamaster
Posts: 1024
Joined: Jun 20, 2005 21:40
Contact:

Faster Cubic Interpolation

Postby Zamaster » Nov 10, 2009 16:53

For scaling images cleanly and stuff. Usually, a pure implementation of cubic interpolation requires at least 7 multiplies in the inner loop, heres a method that (with pretty good accuracy too! though some tiny gaps at the endpoints) requires only one.

The trick treats the interpolation as a second order ODE integrated with a fudged midpoint method (the actual tracker for the input x is just assumed to be shifted by one half the step size). Of course a lot more pre-calcs have to be done but assuming there is a large enough distance to cover this shouldn't matter
(mine are currently uncoptomized anyway ; ] )

Code: Select all

#define SCRX 640   
#define SCRY 480

#define MaxPoints 5

screenres SCRX, SCRY, 32
randomize timer
Dim as double Points(MaxPoints-1)
Dim as double pt(3), term(3), lTerm, termA, termB, nStep=1, acc, n,x, acc2
Dim as integer i, q, ptIndex(3)
'compute the step sizes and mid point shift
Dim as double xPos=0, xSep = SCRX/MaxPoints, xSepDiv = 1/xSep, xSepDivHalf=xSepDiv*0.5

For i = 0 to MaxPoints-1: Points(i)=rnd*SCRY:Next i
ptIndex(0)=MaxPoints-3
ptIndex(1)=MaxPoints-2
ptIndex(2)=MaxPoints-1     
ptIndex(3)=0
For i = 1 to MaxPoints
    For q = 0 to 3
        ptIndex(q)=((ptIndex(q)+1) Mod MaxPoints)
        pt(q) = Points(ptIndex(q))
    Next q
   
    'this only has to happen once every interval... so the larger the interval the
    'better the performance (duh)
    term(0) = pt(3)-pt(2)-pt(0)+pt(1)
    term(1) = (pt(0)-pt(1)-term(0))*2*xSepDiv*xSepDiv
    term(0) = term(0)*3*xSepDiv*(xSepDiv*2)
    term(2) = (pt(2)-pt(0))*xSepDiv
    term(3) = pt(1)   
    acc = term(3)
    acc2 = term(2)
    'heres the trick!
    x = xSepDivHalf
 
 
    Circle (i*xSep,Points(i-1)),4, &HFF0000,,,,F
    For q = 0 to xSep-1
       
       
       
        'and this it it! This is all the math to compute the cubic interpolation... so no exponent garbage
        acc2 += term(0)*x+term(1)
        acc += acc2
       
       
       
        x += xSepDiv
        pset(xPos+q,acc)
        sleep 10   
    Next q
    xPos += xSep
Next i

sleep
Zamaster
Posts: 1024
Joined: Jun 20, 2005 21:40
Contact:

Postby Zamaster » Nov 15, 2009 23:39

man o man... this suuurree is cooooollll...
DaveUnit
Posts: 239
Joined: Apr 20, 2006 15:47
Location: Central MA
Contact:

Postby DaveUnit » Nov 18, 2009 20:08

screenshots will make people interested!
Zamaster
Posts: 1024
Joined: Jun 20, 2005 21:40
Contact:

Postby Zamaster » Nov 19, 2009 2:25

its a math thing... the screen shot is just a curvy line!
duke4e
Posts: 717
Joined: Dec 04, 2005 0:16
Location: Varazdin, Croatia, Europe
Contact:

Postby duke4e » Nov 19, 2009 19:07

could this be used for bicubic interpolation of images?
Zamaster
Posts: 1024
Joined: Jun 20, 2005 21:40
Contact:

Postby Zamaster » Nov 20, 2009 18:47

YES! Thats the idea, you dont have to evaluate 7 multiplications every pixel, just one. And for endpoints you only need two more multiplications than you would for full cubic interpolation, so pretty much its faster if the scale factor for a bicubic image is greater than or equal to two.

Return to “Tips and Tricks”

Who is online

Users browsing this forum: No registered users and 1 guest