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

Thumbnail Image->Nearest-neighbor interpolation

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)

Thumbnail Image->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}

            • 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

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

Sources:

“Bicubic Interpolation.” Wikipedia, 15 Nov. 2010. Web. 2 Oct. 2016. <https://en.wikipedia.org/wiki/Bicubic_interpolation&gt;.

“Cubic Hermite Spline.” Wikipedia, 12 Feb. 2013. Web. 2 Oct. 2016. <https://en.wikipedia.org/wiki/Cubic_Hermite_spline&gt;.

Miklós, Póth. “IMAGE INTERPOLATION TECHNIQUES.” N.p., n.d. Web. 1 Oct. 2016. <http://uni-obuda.hu/conferences/sisy2004/Poth.pdf&gt;.

“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&gt;.

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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s