Image Restoration via Numerical Interpolation

This project demonstrates the application of numerical analysis techniques, specifically Newton Linear Interpolation and Quadratic Interpolation (Divided Differences) to restore images corrupted by salt-and-pepper noise.

Project Overview

In signal processing, an image can be viewed as a discrete 2D function $f(x, y) = I$, where $I$ is the pixel intensity. Salt-and-pepper noise introduces extreme outliers (0 or 255). This project treats these outliers as missing data points and reconstructs them using surrounding "clean" pixels.

Key Features

• Noise Simulation: Adds configurable salt-and-pepper noise to grayscale images.
• Newton Linear Interpolation: Reconstructs pixels using the nearest horizontal neighbors.
• Bi-Directional Quadratic Interpolation:
  • Fits a second-degree polynomial $P_2(x)$ using three points.
  • Performs both vertical (y-axis) and horizontal (x-axis) approximations.
  • Averages the two approximations for a more robust estimation.
• MSE Evaluation: Quantifies restoration quality using Mean Squared Error.

Methodology

Newton Linear Interpolation

The first-degree interpolating polynomial is defined as: $$P_1(x) = y_0 + f[x_0, x_1](x - x_0)$$ Where the first divided difference is: $$f[x_0, x_1] = \frac{y_1 - y_0}{x_1 - x_0}$$

Quadratic Interpolation (Newton Form)

The second-degree interpolating polynomial is defined as: $$P_2(x) = b_0 + b_1(x - x_0) + b_2(x - x_0)(x - x_1)$$ Where coefficients $b_i$ are calculated using divided differences:

• $b_0 = f[x_0]$
• $b_1 = f[x_0, x_1]$
• $b_2 = f[x_0, x_1, x_2] = \frac{f[x_1, x_2] - f[x_0, x_1]}{x_2 - x_0}$

Results

The quadratic method significantly reduces MSE compared to standard linear methods by capturing the local curvature of the image intensity surface.

Method	MSE (Approx)
Noisy Image	1091.75
Linear Restoration	392.48
Quadratic (Averaged)	1.36

Dependencies

• Python 3.x
• NumPy
• OpenCV
• Matplotlib