图像插值算法及其优化

研究背景及其意义

图像放大旋转是数字图像处理中最基础的几何变换操作,其核心在于如何通过插值算法重建原始图像中不存在的像素信息。当对图像进行放大操作时,输出图像的像素网格会超出原始图像的采样范围,需要通过插值来填补这些新增像素点的颜色值;而在旋转操作中,即使保持图像尺寸不变,原始像素的整数坐标经过旋转变换后也会落在新图像的非整数位置,同样需要通过插值来重新确定每个输出像素的颜色值。

图像插值是利用原图像中的颜色值通过一定的方法计算出待插入像素点的颜色值的过程。对图像进行插值一般有两个步骤:首先定义一个图像插值公式,然后利用该插值公式计算待插入点的颜色值。常见的图像插值算法有双线性法、最近邻法、非均匀法、双三次卷积插值法、双立方法、Lagrange法、 样条插值法、 克里金(Krijing) 插值法等。这些插值方法通常定义一个插值数据点的隐式函数,再提取该函数的等值面作为图像插值方法,常用的插值核包括线性插值核、样条插值核等。

  • 最近邻插值作为最简单的算法,直接将距离待插值点最近的已知像素值作为结果,虽然计算效率极高(时间复杂度O(1)),但会产生明显的块状伪影(“马赛克”)和锯齿形边缘;
  • 双线性插值通过考虑2×2邻域内四个像素的加权平均,在计算成本(O(n))和视觉效果之间取得平衡,但仍会导致高频信息丢失和边缘模糊;
  • 更高阶的双三次插值(使用4×4邻域)和样条插值虽然能提供更平滑的结果,但计算复杂度显著增加(O(n²)),且可能引入不必要的振铃效应。

现有算法的根本局限在于采用统一的插值核函数处理整幅图像,忽视了图像不同区域的特征差异。例如,在平坦区域使用复杂插值会造成计算资源浪费,而在纹理丰富区域使用简单插值又会导致细节损失。基于此,我们希望通过改良的四平面插值算法对图像的放大与旋转效果进行优化,根据图像局部特征自适应地选择不同的插值策略,以规避用同一个插值公式对所有像素进行插值存在的不足。

常用图像插值算法

课本在6.5节中提到,在插值节点数量较多时,为避免Runge振荡现象的发生,并不提倡用高次多项式进行插值,而宁可用低次多项式作分段插值。在图像处理这一特定的应用场景中,需要处理的图像尺寸规模往往较大,且同一行(列)的所有像素颜色值显然并不具有可以用一个多项式函数显式表达的规律,但相邻的像素点颜色值之间又存在一定的关联性,因此分段插值仅考虑局部特征的特性在这里能够良好地契合所需性能。根据对于待插入像素点周围已有的像素点信息的利用情况,这里列举了几种常见的图像插值算法:

  • 最近邻法:仅利用待插值像素点转换至原图像坐标后距离其最近的一个像素点的颜色值,将其直接作为待插值像素点的颜色值
  • 双线性法:利用待插值像素点转换至原图像坐标后距离其最近的四个像素点的颜色值,加权平均后作为待插值像素点的颜色值
  • 双立方法:利用待插值像素点转换至原图像坐标后距离其最近的十六个像素点的颜色值,加权平均后作为待插值像素点的颜色值

最近邻法

一维最近邻插值示意图

如上图所示,在一维最近邻插值中,坐标轴上各点 xi-1,xi,xi+1 … 两两对半等分间隔 (红色虚线划分),从而非边界的各坐标点都有一个等宽的邻域,并根据每个坐标点的值构成一个类似分段函数的函数约束,从而使各插值坐标点的值等同于所在邻域原坐标点的值。例如,插值点 x 坐落于 坐标点 xi 的邻域,那么其值 f(x) 就等于 f(xi)。

在二维的图像插值场景中,可以对上述一维最近邻插值进行推广,如下图所示:

二维最近邻插值示意图

可以看到,(x0, y0)、(x0, y1)、(x1, y0)、(x1, y1) 都是原图像上的坐标点,颜色值分别对应为 Q11、Q12、Q21、Q22。而颜色值未知的插值点 (x, y)(需转换至原图像坐标),根据最近邻插值方法的约束,其与坐标点 (x0, y0) 位置最接近 (即位于 (x0, y0) 的邻域内),故插值点 (x, y) 的颜色值 P = Q11。

总而言之,最近邻法的基本思想即:将待插入点的坐标进行四舍五入,再以该行列坐标都是整数点的颜色值(灰度值)替代待插入点(x, y)处的颜色值。事实上,这也正是机器学习中KNN(K-Nearest Neighbor)算法在K=1时的情形。

基于以上算法思想,编写python函数代码实现图像放缩与旋转过程中的最近邻法插值:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
# 最近邻法插值实现图像放缩
def nearest_neighbor_interpolation(image, scale_factor):
h, w, channel = image.shape
new_h, new_w = int(h * scale_factor), int(w * scale_factor)
resized_image = np.zeros((new_h, new_w, int(channel)), dtype=image.dtype)

for i in range(new_h):
for j in range(new_w):
src_i = int(round((i + 1) / scale_factor, 0))
src_j = int(round((j + 1) / scale_factor, 0))
resized_image[i, j] = image[src_i - 1, src_j - 1]

return resized_image

# 最近邻法插值实现图像旋转
def nearest_neighbor_rotation(image, angle):
h, w, channel = image.shape
angle_rad = math.radians(angle)

# 计算旋转后的图像尺寸
cos_theta = abs(math.cos(angle_rad))
sin_theta = abs(math.sin(angle_rad))
new_w = int(h * sin_theta + w * cos_theta)
new_h = int(h * cos_theta + w * sin_theta)

# 旋转中心
cx, cy = w / 2, h / 2
new_cx, new_cy = new_w / 2, new_h / 2

rotated_image = np.zeros((new_h, new_w, channel), dtype=image.dtype)

for i in range(new_h):
for j in range(new_w):
# 将新图像坐标转换回原图像坐标
x = (j - new_cx) * math.cos(angle_rad) + (i - new_cy) * math.sin(angle_rad) + cx
y = -(j - new_cx) * math.sin(angle_rad) + (i - new_cy) * math.cos(angle_rad) + cy

# 最近邻插值
if 0 <= x < w and 0 <= y < h:
src_x = int(round(x))
src_y = int(round(y))
rotated_image[i, j] = image[src_y - 1, src_x - 1]

return rotated_image

双线性法

一维线性插值示意图

如上图所示,在一维的线性插值中,坐标轴上各点 xi-1,xi,xi+1 … 的值“两两直接相连”为线段,从而构成了一条连续的约束函数。而插值坐标点例如 x,根据约束函数其值应为 f(x)。因为每两个坐标点之间的约束函数曲线是一次线性的线段,对插值结果而言是“线性” 的,所以该方法称为线性插值。基于线性函数的特性,可以便捷地求取原图像上的两个像素点间任一待插值点的颜色值:

一维线性插值计算示意图

可以看到,图中 x0 和 x1 都是原有的坐标点,颜色值分别对应为 y0 和 y1,此时根据线性插值法约束,在 (x0, y0) 和 (x1, y1) 构成的一次函数上,颜色值未知的插值点 x的颜色值 y 即为:
$$
y=y_0+(x-x_0)\frac{y_1-y_0}{x_1-x_0}=y_0+\frac{(x-x_0)y_1-(x-x_0)y_0}{x_1-x_0}
$$
实际上,即便 x 不在 x0 与 x1 之间,该公式也成立(此时为线性外插),但图像处理中不需涉及此情形。

从一维的线性插值出发,很容易拓展到二维图像的双线性插值,通过三次一阶线性插值(本质为加权求和)获得最终结果,下图便展示了该过程的定性斜视与定量俯视示意图:

二维线性插值定性斜视示意图

二维线性插值定量俯视示意图

阅读更多