Week 1: Linear Upscaling Algorithms

Week 1: 9/25-10/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
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 shrinking 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)=(x2-x)/(x2-x1)*f(x1,y1)+(x-x1)/(x2-x1)*f(x2,y1)
  - f(x,y2)=(x2-x)/(x2-x1)*f(x1,y2)+(x-x1)/(x2-x1)*f(x2,y2)
- Compute the linear interpolation in the y directions to complete the computation
  - f(x,y)=(y2-y)/(y2-y1)*f(x,y1)+(y-y1)/(y2-y1)*f(x,y2)

-> Bilinear interpolation

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
  $p(x,y)=\sum_{i=0}^{3}\sum_{j=0}^{3}a_{ij}ix^{i}y^{j}$

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…
  $p_{x}(x,y)=\sum_{i=1}^{3}\sum_{j=0}^{3}a_{ij}ix^{i-1}y^{j}$
  $p_{y}(x,y)=\sum_{i=0}^{3}\sum_{j=1}^{3}a_{ij}jx^{i}y^{j-1}$
  $p_{xy}(x,y)=\sum_{i=1}^{3}\sum_{j=1}^{3}a_{ij}ijx^{i-1}y^{j-1}$
  - 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
  $W(x) = \begin{cases} (a+2)|x|^3-(a+3)|x|^2+1 & \text{for } |x| \leq 1 \\ a|x|^3-5a|x|^2+8a|x|-4a & \text{for } 1 < |x| < 2 \\ 0 & \text{otherwise} \end{cases}$

$b_{-1}=p(t_x,f_(-1,-1),f_(0,-1),f_(1,-1),f_(2,-1))\newline$
$b_{0}=p(t_x,f_(-1,0),f_(0,0),f_(1,0),f_(2,0))\newline$
$b_{1}=p(t_x,f_(-1,1),f_(0,1),f_(1,1),f_(2,1))\newline$
$b_{2}=p(t_x,f_(-1,2),f_(0,2),f_(1,2),f_(2,2))\newline$
$p(x,y)=p(t_y,b_{-1},f_{0},f_{1},f_{2})$

Indexes are as follows, t is a value from 0-1 similar to the unit circle and the b_{-1} represent the four points chosen by the bicubic interpolation

Thumbnail Image -> 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
- Edge-directed 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://uni-obuda.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/15462-f09/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.

Share this:

Like this:

Related

Leave a Reply Cancel reply