Week 1: Linear Upscaling Algorithms
Week 1: 9/2510/2/16
Definitions
 Kernel: When doing image processing using matrices the kernel is a small matrix (eg 3×3) that is multiplied with a block of pixels on the image (here 3×3) which serves as a filter.
 The multiplication mentioned above takes the 3×3 matrix of the original image multiplies each element with the corresponding m x n value in the kernel and collectively sums all values computed to a total and setting that new value as the output pixel.
 Spline: A piecewise numeric function defined by polynomials. In the case of bicubic interpolation cubic hermite splines are used where each piecewise function is a cubic polynomial of the form p(t)=(a0x^3+b0x^2+c0x+d0)*p0+…+(anx^3+bnx^2+cnx+dn)*pn
Linear VS Non linear
 Linear algorithms follow the following scheme f(a+b)=f(a)+f(b)
 This means that any input will definitely vary the output linearly
 Nonlinear algorithms such as mean and median algorithms will be able to take tare of outliers in the data allowing for a more accurate computation
Linear Upscaling Algorithms$ latex \displaystyle \sum_{n=1}^\infty \frac{1}{n^2} = \frac{\pi^2}{6}. $</p> yields
Nearest Neighbor Interpolation
 Value of interpolated pixel is calculated from the nearest sample point in the input image
 Executes fast but creates a lot of artifacts
 Algorithm
 Calculate ratio of the desired increase in size of both width and height
 The ratio is orig_width/new_width
 For a 2D image use two for loops to iterate the size of the new image
 Inside for loop compute the new pixel number by doing
 pixel_x=floor(width_ratio*x_index)
 pixel_y=floor(height_ratio*y_index)
 Assign pixel to the temporary image array
 temp[x_index*new_width+y_index]=orig[pixel_y*orig_width+pixel_x]
 Return temporary image array
 Calculate ratio of the desired increase in size of both width and height
 Algorithm
 This algorithm is the fastest as it doesn’t need to use any if conditionals (which is very messy in machine code due to the branches needed
 If implemented using integers instead of floating point numbers (optimization) integer division will often lead to zero
 An example of this is shrinki￼ng the image with a ratio <.5 there would be an error factor added to the ratio conditions to ensure that it wouldn’t produce a zero
 Or if we flip the ratio and edit the assignment of the pixel values it could still produce the same result
Bilinear Interpolation
 This algorithm uses instead of one nearest neighbor but four nearest neighbors to calculate the interpolated pixels
 The closer the a neighbor is the greater the influence it has on the computed pixel values
 This performs better than the single nearest neighbor algorithm however due to the linear interpolation which does not account for sharp edges or large changes in pixel data by “averaging” we create a softer image that has been blurred
 Algorithm: Given 4 points at (x1,y1), (x1, y2), (x2, y1), (x2,y2) find interpolated pixel at (x,y) where x1<x2 y1<y2 and x1<x<x2 y1<y<y2
 Compute linear interpolation in x directions
 f(x,y1)=(x2x)/(x2x1)*f(x1,y1)+(xx1)/(x2x1)*f(x2,y1)
 f(x,y2)=(x2x)/(x2x1)*f(x1,y2)+(xx1)/(x2x1)*f(x2,y2)
 Compute the linear interpolation in the y directions to complete the computation
 f(x,y)=(y2y)/(y2y1)*f(x,y1)+(yy1)/(y2y1)*f(x,y2)
 Compute linear interpolation in x directions
Bicubic Interpolation
 Accomplished using Lagrange polynomials, cubic splines, or cubic convolution
 This is a slower algorithm than the bilinear algorithm as it needs to take into account more pixels (16 vs 4)
 Because the algorithm (like bilinear does not take into account edges) and often results in even more blurring than the bilinear interpolation algorithm
 Basic ideas:
 The whole algorithm hinges on this following equation
 The whole algorithm hinges on this following equation
 This equation represents the interpolated surface
 To obtain all the values required for this equation we need to see what variables are being used
 Using a unit square on the original image we can obtain p(0,0)…p(1,1) (4 eqs)
 Which when expanded will create 16 different “a” variables indexing from 00 to 33
 These are the 16 variables we need to solve for…
 To solve for these 16 variables we need to solve for the x, y, and xy derivatives for all 4 points. (12 eqs) this gives us a total of 16 equations to solve for “a”
 Note that the reason why the indexing starts from 1 is because when you have “i/j”==0 the derivative constant will multiply by zero
 Now that we have all 16 equations using matrices and linear algebra we can compute all 16 “a” values.

 The above uses bicubic spline interpolation where p(x,y) is a sum of cubics
 Given the above we are now able to construct an interpolated version of the image
 An easier method would be to use a kernel which simulates the model described above
 Varying the values of “a” will produce different results however the value of “0.5=a” will produce the same result as the bicubic computation performed above
 To use this kernel to compute a bicubic interpolation for 2d images apply the transformation in the x dimension then again in the y direction
 Indexes are as follows, t is a value from 01 similar to the unit circle and the b_{1} represent the four points chosen by the bicubic interpolation
>
Nonlinear Algorithms
 Unfortunately, I have not been able to fully look into any nonlinear implementations of image upscaling yet this week due to other things
 However below will be a list of algorithms I will look into next week.
 General General2
 Fourier Based Interpolation
 Edgedirected interpolation
 Curvature based
 Sinc (Lanczos3)
 NNEDI3
 Source code? May need to look into neural networks
 Jinc?
Sources:
“Bicubic Interpolation.” Wikipedia, 15 Nov. 2010. Web. 2 Oct. 2016. <https://en.wikipedia.org/wiki/Bicubic_interpolation>.
“Cubic Hermite Spline.” Wikipedia, 12 Feb. 2013. Web. 2 Oct. 2016. <https://en.wikipedia.org/wiki/Cubic_Hermite_spline>.
Miklós, Póth. “IMAGE INTERPOLATION TECHNIQUES.” N.p., n.d. Web. 1 Oct. 2016. <http://uniobuda.hu/conferences/sisy2004/Poth.pdf>.
“Nearest Neighbor Image Scaling.” Nearest Neighbor Image Scaling. N.p., 6 Oct. 2007. Web. 1 Oct. 2016.
“Parametric Curves.” N.p., n.d. Web. 2 Oct. 2016. <https://www.cs.cmu.edu/afs/cs/academic/class/15462f09/www/lec/lec6.pdf>.
Powell, Victor. “Image Kernels: Explained Visually.” Image Kernels: Explained Visually. N.p., n.d. Web. 30 Sept. 2016.
Singh, Gagandeep, and Prof. Gulshan Goyal. “Linear Image Upscaling :A Reveiw.” N.p., Jan. 2015. Web. 29 Sept. 2016.