🏻 🖲️ 🏜️ 插值和离散化，为什么投影图像转换需要它们？ 🕦 👨🏾‍🌾 🌗

哈Ha！今天，我们将以一种看似简单的操作来详细讨论非显而易见的点：校正图像中的投影畸变。正如生活中经常发生的那样，我们必须选择哪个更重要：质量或速度。为了达到一定的平衡，我们想起了80-90年代积极研究的算法，这些算法是渲染结构任务的一部分，从那时起，我们很少在图像处理的背景下进行回忆。如果有兴趣，请在猫下看！

针孔相机模型实际上还可以很好地带来手机的近摄相机，它告诉我们，当相机旋转时，平面物体的图像通过投影变换相互连接。射影变换的一般视图如下：

x = \frac{t_{11} u + t_{12} v + t_{13}}{t_{31} u + t_{32} v + t_{33}}, y = \frac{t_{21} u + t_{22} v + t_{23}}{t_{31} u + t_{32} v + t_{33}},

$x = \frac{t_{11} u + t_{12} v + t_{13}}{t_{31} u + t_{32} v + t_{33}}, \ \ \ y = \frac{t_{21} u + t_{22} v + t_{23}}{t_{31} u + t_{32} v + t_{33}},$

哪里

T = (t_{i j}), i \in {1, 2, 3}, j \in {1, 2, 3}

$T = (t_{ij}), \ \ i \in \{1, 2, 3\}, \ \ j \in \{1, 2, 3\}$ 射影变换矩阵

(u, v)

$(u, v)$ 和

(x, y)

$(x, y)$ 在源图像和转换后的图像上进行坐标调整。

几何图像转换

投影图像变换是图像可能的几何变换之一（这种变换是根据一定的定律将原始图像的点移到最终图像的点）。

要了解如何解决数字图像的几何变换问题，您需要考虑由相机矩阵上的光学图像形成的模型。根据G. Wahlberg [1]，我们的算法应近似于以下过程：

从数字恢复光学图像。
光学图像的几何变换。
转换后图像的采样。

光学图像是在一组连续点上定义的两个变量的函数。这个过程很难直接复制，因为我们必须分析设置光学图像的类型并进行处理。为了简化此过程，通常使用反向映射方法：

在最终图像的平面上，选择了一个采样网格-我们将通过这些点来评估最终图像的像素值（这可能是每个像素的中心，或者每个像素几个点）。
使用逆几何变换，此网格被转移到原始图像的空间。
对于每个网格样本，估计其值。由于它不一定出现在具有整数坐标的点上，因此我们需要对图像值进行一些插值，例如，通过相邻像素进行插值。
根据网格报告，我们估计最终图像的像素值。

在此，步骤3对应于光学图像的恢复，而步骤1和4对应于采样。

插补

在这里，我们将仅考虑简单的插值类型-可以将其表示为图像与插值核心的卷积。在图像处理的背景下，保留对象清晰边界的自适应插值算法会更好，但是它们的计算复杂度要高得多，因此我们不感兴趣。

我们将考虑以下插值方法：

按最近的像素
双线性
双三次
三次b样条
三次埃尔米特样条，36分。

插值还具有诸如精度之类的重要参数。如果我们假设数字图像是通过光学方法通过在像素中心点采样而获得的，并且认为原始图像是连续的，那么频率为½的低通滤波器将是理想的重构函数（请参阅Kotelnikov定理）。

因此，我们将插值核心的傅立叶光谱与低通滤波器进行比较（图中为一维情况）。

而且，您可以只选择一个频谱范围相当好的内核并获得相对准确的结果吗？实际上不是，因为我们在上面做了两个假设：存在图像的像素值和该图像的连续性。同时，一个或另一个都不是良好图像形成模型的一部分，因为相机矩阵上的传感器不是点状的，并且图像上的许多信息都带有对象的边界-间隙。因此，a，应该理解，插值的结果将始终与原始光学图像不同。

但是您仍然需要做一些事情，因此我们将从实用的角度简要描述每种考虑的方法的优缺点。最简单的查看方法是放大图像（在此示例中为10倍）。

双线性插值

质量更好，但需要更多的计算，而且还会模糊对象的边界。

双三次插值

在连续区域中甚至更好，但在边界处会产生光晕效果（边界暗边缘处的暗条和光亮处）。为了避免这种影响，您需要使用非负卷积核，例如三次b样条。

B样条插值

b样条曲线的频谱非常窄，这意味着图像很“模糊”（而且降噪效果很好，这很有用）。

基于三次Hermite样条的插值

这样的样条需要估计图像的每个像素中的偏导数。如果为了近似我们选择一个2点差分方案，那么我们得到双三次插值的核心，因此这里我们使用4点差分方案。

我们还根据内存访问的数量（在一个点进行插值的原始图像的像素数量）和逐点相乘的数量来比较这些方法。

插补	像素数	乘法数
近	1个	0
双线性	4	8
双三次	十六	68
B样条	十六	68
埃尔米特花键	36	76

可以看出，后三种方法在计算上比前两种显着昂贵。

采样

这是最近很少引起人们注意的非常重要的一步。执行投影图像变换的最简单方法是通过将最终像素的中心反转到原始图像的平面（考虑到选定的插值方法）获得的值来评估最终图像的每个像素的值。我们称这种方法为逐像素离散化。但是，在图像被压缩的区域中，这可能导致明显的伪影，这是由于在采样频率不足时光谱重叠造成的。

我们将清楚地展示俄罗斯护照及其各个领域（出生地（阿尔汉格尔斯克市））样本上的压缩伪影，这些压缩伪影使用逐像素采样或FAST算法压缩，我们将在下面进行介绍。

可以看出，左侧图像中的文本变得不可读。没错，因为我们仅从源图像的整个区域中提取一个点！

由于我们无法按一个像素进行估算，那么为什么不为每个像素选择更多样本，并对获得的值取平均值呢？这种方法称为超级采样。它确实提高了质量，但同时，计算复杂度与每个像素的样本数量成比例地增加。

上世纪末，计算机图形学解决了将纹理叠加在平面物体上的问题，从而发明了计算效率更高的方法。这些方法之一是使用mip-map进行转换结构体。 Mip-map是由原始图像本身以及其副本减少2、4、8等组成的图像金字塔。对于每个像素，我们评估其压缩特性的程度，并根据该程度从金字塔中选择所需的级别作为源图像。有多种方法可以评估适当的mip-map级别（请参见详细信息[2]）。在这里，我们将使用基于相对于众所周知的投影变换矩阵的偏导数估计的方法。但是，为了避免在最终图像的区域中出现伪像结构的一个级别到达另一个级别的伪影，通常使用金字塔的两个相邻级别之间的线性插值（这不会大大增加计算复杂度，因为相邻级别的点的坐标是唯一连接的）。

但是，mip贴图未考虑图像压缩可能是各向异性的（沿某个方向延长）的事实。rip-map可以部分解决此问题。压缩图像的结构

2^{m}

$2^m$ 水平时间和

2^{n}

$2^n$ 垂直的时间。在这种情况下，在确定最终图像中给定点的水平和垂直压缩系数之后，在以所需次数压缩的原始图像的4个副本的结果之间执行插值。但是这种方法并不理想，因为它没有考虑到各向异性的方向不同于平行于原始图像边界的方向。

在某种程度上，这个问题可以通过FAST（足迹区域采样纹理）算法来解决[3]。它结合了mip-map和超级采样的思想。我们根据最小各向异性轴估算压缩程度，并根据最小轴与最大轴的长度之比选择样本数。

在比较这些方法的计算复杂度之前，我们保留一个观点，为了加快逆射影变换的计算，合理地进行以下更改：

q (x, y) = \frac{1}{f_{3} (x) + g_{3} (y)},

$q(x, y) = \frac{1}{f_3(x) + g_3(y)},$

u (x, y) = q (x, y) (f_{1} (x) + g_{1} (y)),

$u(x, y) = q(x, y)(f_1(x) + g_1(y)),$

v (x, y) = q (x, y) (f_{3} (x) + g_{3} (y)),

$v(x, y) = q(x, y)(f_3(x) + g_3(y)),$

哪里

f_{i} (x) = p_{i 1} x, g_{i} (y) = p_{i 2} y + p_{i 3}, P = (p_{i j}) = T^{- 1}, i \in {1, 2, 3}, j \in {1, 2, 3}

$f_i(x) = p_{i1} x, g_i(y) = p_{i2} y + p_{i3}, P = (p_{ij}) = T ^ {-1}, i \in \{1, 2, 3\}, j \in \{1, 2, 3\}$ ，

P

$P$ 是逆射影变换的矩阵。如

f (x)

$f(x)$ 和

g (y)

$g(y)$ 一个参数的函数，我们可以预先计算出它们与图像的线性大小成比例的时间。然后，计算最终图像一点反图像的坐标

(u, v)

$(u, v)$ ，只需要1个除法和2个乘法。可以使用偏导数执行类似的技巧，偏导数用于确定mip-map或rip-map结构中的级别。

现在，我们准备按照计算复杂度比较结果。

方法	每像素计数	每个计数的乘法数	用于结构的附加内存（仅占原始图像的一部分）
像素采样	1个	2	0
超采样	ñ	2	0
贴图	2	7	1/3
翻录地图	4	7	3
快速	<= n	7	1/3

并进行视觉比较（从左到右逐个像素采样，49个采样的超级采样，mip-map，rip-map，FAST）。

实验

现在，让我们通过实验比较我们的结果。我们结合了5种插值方法和5种离散化方法（总共25种选择）构成了一种投影变换算法。拍摄20张裁剪为512x512像素的文档图像，生成10组3个投影变换矩阵，这样，每组通常等效于相同的变换，我们将比较原始图像和转换后的图像之间的PSNR。回想一下，PSNR是

10 \log \frac{M A X^{2}}{M S E}

$10 \log \frac{MAX^2}{MSE}$ 哪里

M A X

$MAX$ 这是原始图像中的最大值

M S E

$MSE$ -最终版本与原始版本的标准差。PSNR越高越好。我们还将使用ARM Cortex-A15处理器（2000 MHz和2GB RAM）在ODROID-XU4上测量投影转换的运行时间。

可怕的结果表：

采样	插补	时间（秒）	信噪比（dB）
逐像素	近	0.074	23.1
	双线性	0.161	25.4
	双三次	0.496	26.0
	B样条	0.517	24.8
	埃尔米特花键	0.978	26.2
超级采样（x49）	近	4.01	25.6
	双线性	7.76	25.3
	双三次	23.7	26.1
	B样条	24.7	24.6
	埃尔米特花键	46.9	26.2
贴图	近	0.194	24.0
	双线性	0.302	24.6
	双三次	0.770	25.3
	B样条	0.800	23.9
	埃尔米特花键	1.56	25.5
翻录地图	近	0.328	24.2
	双线性	0.510	25.0
	双三次	1.231	25.8
	B样条	1.270	24.2
	埃尔米特花键	2.41	25.8
快速	近	0.342	24.0
	双线性	0.539	25.2
	双三次	1.31	26.0
	B样条	1.36	24.4
	埃尔米特花键	2.42	26.2

可以得出什么结论？

通过最近的像素或逐像素采样使用插值会导致质量较差（从上述示例中可以明显看出）。
36 — .
b- , , .
Rip-map FAST , 9 ( , ?).
mip-map b- PSNR , .

如果要以不太低的速度获得良好的质量，则应考虑将双线性插值与使用mip-map或FAST的离散化结合使用。但是，如果可以肯定地知道投影失真非常微弱，则为了提高速度，可以使用逐像素离散化与双线性插值或什至最接近像素的插值配对。而且，如果您需要高质量且运行时间不是非常有限的话，则可以使用双三次插值或自适应插值以及适度的超级采样（例如，根据局部压缩率也可以自适应）。

PS该出版物基于以下报告：A. Trusov和E. Limonova，“用于移动设备上图像识别的投影变换算法的分析”，ICMV 2019，11433年版。一月 2020卷 11433，ISSN 0277-786X，ISBN 978-15-10636-43-9，卷。11433，11433 0Y，pp。2020年1月1日至8日，DOI：10.1117 / 12.2559732。

使用的资料清单

G. Wolberg, Digital image warping, vol. 10662, IEEE computer society press Los Alamitos, CA (1990).
J. P. Ewins, M. D. Waller, M. White, and P. F. Lister, “Mip-map level selection for texture mapping,” IEEE Transactions on Visualization and Computer Graphics4(4), 317–329 (1998).
B. Chen, F. Dachille, and A. E. Kaufman, “Footprint area sampled texturing,” IEEE Transactions on Visualizationand Computer Graphics10(2), 230–240 (2004).

插值和离散化，为什么投影图像转换需要它们？