Mar 7 学习/总结/工具 FPGA 评论 字数统计: 3.5k(字) 阅读时长: 17(分)

（温馨提示： 本文数学公式推导较多，建议在大屏下（电脑或者平板）观看比较合适）

是一个通常采用的距离定义，指在m维空间中两个点之间的真实距离，或者向量的自然长度（即该点到原点的距离）。在二维和三维空间中的欧氏距离就是两点之间的实际距离

二维平面上两点a(x1,y1)a(x_1,y_1)a(x1​,y1​)与b(x2,y2)b(x_2,y_2)b(x2​,y2​)间的欧氏距离 d12=(x1−x2)2+(y1−y2)2d_{12}=\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}d12​=(x1​−x2​)2+(y1​−y2​)2​

三维空间两点a(x1,y1,z1)a(x_1,y_1,z_1)a(x1​,y1​,z1​)与b(x2,y2,z2)b(x_2,y_2,z_2)b(x2​,y2​,z2​)间的欧氏距离 d12=(x1−x2)2+(y1−y2)2+(z1−z2)2d_{12}=\sqrt{(x_1-x_2)^2+(y_1-y_2)^2+(z_1-z_2)^2}d12​=(x1​−x2​)2+(y1​−y2​)2+(z1​−z2​)2​

两个n维向量a(x11,x12,…,x1n)a(x_{11},x_{12},…,x_{1n})a(x11​,x12​,…,x1n​)与b(x21,x22,…,x2n)b(x_{21},x_{22},…,x_{2n})b(x21​,x22​,…,x2n​)间的欧氏距离 d12=∑k=1n(x1k−x2k)2d_{12}=\sum_{k=1}^n(x_{1k}-x_{2k})^2d12​=∑k=1n​(x1k​−x2k​)2

用来标明两个点在标准坐标系上的绝对轴距总和

如下图所示：绿线代表欧式距离，红线代表曼哈顿距离，黄线和蓝线代表等价的曼哈顿距离

二维平面两点a(x1,y1)a(x_1,y_1)a(x1​,y1​)与b(x2,y2)b(x_2,y_2)b(x2​,y2​)间的曼哈顿距离 d12=∣x1−x2∣+∣y1−y2∣d_{12}=|x_1-x_2|+|y_1-y_2|d12​=∣x1​−x2​∣+∣y1​−y2​∣

两个n维向量a(x11,x12,…,x1n)a(x_{11},x_{12},…,x_{1n})a(x11​,x12​,…,x1n​)与b(x21,x22,…,x2n)b(x_{21},x_{22},…,x_{2n})b(x21​,x22​,…,x2n​)间的曼哈顿距离 d12=∑k=1n∣x1k−x2k∣d_{12}=\sum_{k=1}^n|x_{1k}-x_{2k}|d12​=∑k=1n​∣x1k​−x2k​∣

对于连续函数，微分表达式为 f′(x)=lim⁡h→0f(x+h)−f(x)hf'(x)=\lim\limits_{h\rightarrow0}\frac{f(x+h)-f(x)}{h}f′(x)=h→0lim​hf(x+h)−f(x)​ 或者 f′(x)=lim⁡h→0f(x+h)−f(x−h)2hf'(x)=\lim\limits_{h\rightarrow0}\frac{f(x+h)-f(x-h)}{2h}f′(x)=h→0lim​2hf(x+h)−f(x−h)​

对于离散函数（图像），其导数必须用差分方程来表示， 有前向差分 Ix=I(x)−I(x−h)hI_x=\frac{I(x)-I(x-h)}{h}Ix​=hI(x)−I(x−h)​ 后向差分 Ix=I(x+h)−I(x)hI_x=\frac{I(x+h)-I(x)}{h}Ix​=hI(x+h)−I(x)​ 以及中心差分 Ix=f(x+h)−f(x−h)2hI_x=\frac{f(x+h)-f(x-h)}{2h}Ix​=2hf(x+h)−f(x−h)​

图像I的梯度定义为 ∇(I(x,y))=[Ix=∂I∂x,Iy=∂I∂y]\nabla(I(x,y))=\left[I_x=\frac{\partial I}{\partial x},I_y=\frac{\partial I}{\partial y}\right]∇(I(x,y))=[Ix​=∂x∂I​,Iy​=∂y∂I​] 其幅值为 ∣∣∇(I)∣∣=Ix2+Iy2||\nabla(I)||=\sqrt{I_x^2+I_y^2}∣∣∇(I)∣∣=Ix2​+Iy2​​ 幅值也可用 ∣∣∇(I)∣∣≈∣Ix∣+∣Iy∣||\nabla(I)||\approx|I_x|+|I_y|∣∣∇(I)∣∣≈∣Ix​∣+∣Iy​∣ 来近似

对于连续函数（假设其二阶可导）， 其二阶导数为 f′′(x)=lim⁡h→0f′(x+h)−f′(x)hf''(x)=\lim\limits_{h\rightarrow0}\frac{f'(x+h)-f'(x)}{h}f′′(x)=h→0lim​hf′(x+h)−f′(x)​ 也就是 f′′(x)=lim⁡h→0f(x+h)−2f(x)+f(x−h)h2f''(x)=\lim\limits_{h\rightarrow0}\frac{f(x+h)-2f(x)+f(x-h)}{h^2}f′′(x)=h→0lim​h2f(x+h)−2f(x)+f(x−h)​

对于离散函数（图像），其差分方程为 Ixx=I(x+h)−2I(x)+I(x−h)h2I_{xx}=\frac{I(x+h)-2I(x)+I(x-h)}{h^2}Ixx​=h2I(x+h)−2I(x)+I(x−h)​

Roberts算子是一种斜向偏差分的梯度计算方法，梯度的大小代表边缘的强度，梯度的方向与边缘的走向垂直。Roberts操作实际上是求旋转45度两个方向上微分值的和

如果我们沿如下图方向角度求其交叉方向的偏导数，则得到Roberts于1963年提出的交叉算子边缘检测方法(这个结论是我根据推导的结果总结得到的，并非预先就知道的）。该方法最大优点是计算量小，速度快。但该方法由于是采用偶数模板，如下图所示，所求的(x,y)点处梯度幅度值，其实是图中交叉点处的值，从而导致在图像(x,y)点所求的梯度幅度值偏移了半个像素（见下图）

∂f∂x≈f(x+1,y)−f(x,y)≈f(x+1,y+1)−f(x,y+1)\frac{\partial f}{\partial x}\approx f(x+1,y)-f(x,y)\approx f(x+1,y+1)-f(x,y+1)∂x∂f​≈f(x+1,y)−f(x,y)≈f(x+1,y+1)−f(x,y+1) ∂f∂y≈f(x,y+1)−f(x,y)≈f(x+1,y+1)−f(x+1,y)\frac{\partial f}{\partial y}\approx f(x,y+1)-f(x,y)\approx f(x+1,y+1)-f(x+1,y)∂y∂f​≈f(x,y+1)−f(x,y)≈f(x+1,y+1)−f(x+1,y) ∣∣∇f(x,y)∣∣=(∂f∂x)2+(∂f∂y)2≈∣∂f∂x∣+∣∂f∂y∣||\nabla f(x,y)||=\sqrt{(\frac{\partial f}{\partial x})^2+(\frac{\partial f}{\partial y})^2}\approx |\frac{\partial f}{\partial x}|+|\frac{\partial f}{\partial y}|∣∣∇f(x,y)∣∣=(∂x∂f​)2+(∂y∂f​)2​≈∣∂x∂f​∣+∣∂y∂f​∣ ①≈∂f∂x+∂f∂y≈(f(x+1,y)−f(x,y))+(f(x+1,y+1)−f(x+1,y))=f(x+1,y+1)−f(x,y)①\approx \frac{\partial f}{\partial x}+\frac{\partial f}{\partial y}\approx (f(x+1,y)-f(x,y))+(f(x+1,y+1)-f(x+1,y))=f(x+1,y+1)-f(x,y)①≈∂x∂f​+∂y∂f​≈(f(x+1,y)−f(x,y))+(f(x+1,y+1)−f(x+1,y))=f(x+1,y+1)−f(x,y) ②≈∂f∂x−∂f∂y≈(f(x+1,y)−f(x,y))−(f(x,y+1)−f(x,y))=f(x+1,y)−f(x,y+1)②\approx \frac{\partial f}{\partial x}-\frac{\partial f}{\partial y}\approx (f(x+1,y)-f(x,y))-(f(x,y+1)-f(x,y))=f(x+1,y)-f(x,y+1)②≈∂x∂f​−∂y∂f​≈(f(x+1,y)−f(x,y))−(f(x,y+1)−f(x,y))=f(x+1,y)−f(x,y+1) ③≈∂f∂y−∂f∂x≈(f(x,y+1)−f(x,y))−(f(x+1,y)−f(x,y))=f(x,y+1)−f(x+1,y)③\approx \frac{\partial f}{\partial y}-\frac{\partial f}{\partial x}\approx (f(x,y+1)-f(x,y))-(f(x+1,y)-f(x,y))=f(x,y+1)-f(x+1,y)③≈∂y∂f​−∂x∂f​≈(f(x,y+1)−f(x,y))−(f(x+1,y)−f(x,y))=f(x,y+1)−f(x+1,y) ④≈−∂f∂x−∂f∂y≈−(f(x+1,y)−f(x,y))−(f(x+1,y+1)−f(x+1,y))=f(x,y)−f(x+1,y+1)④\approx -\frac{\partial f}{\partial x}-\frac{\partial f}{\partial y}\approx -(f(x+1,y)-f(x,y))-(f(x+1,y+1)-f(x+1,y))=f(x,y)-f(x+1,y+1)④≈−∂x∂f​−∂y∂f​≈−(f(x+1,y)−f(x,y))−(f(x+1,y+1)−f(x+1,y))=f(x,y)−f(x+1,y+1)

即Roberts算子为

G'x= \left\[ \begin{matrix} {1} & {0} \\ {0} & {-1} \end{matrix} \right\]

和

G'y= \left\[ \begin{matrix} {0} & {1} \\ {-1} & {0} \end{matrix} \right\]

Sobel算子考虑了水平、垂直和2个对角共计4个方向对的梯度加权求和，是一个3×3各向异性的梯度算子 （* 注： 并不是现行教科书上描述的简单的隔行/列的差分运算，中心像素位置也并未参与运算*）

笛卡尔网格

前向差分

距离反比的4方向对梯度加权

城市街区距离 （* 注： 这些概念已经在上面准备知识部分进行了部分说明*）

（1）定义一个给定邻域方向梯度矢量g的幅度为 ∣g∣=/|g| = /∣g∣=/

（2）Sobel采用的像素距离是一种城市街区距离而并非通常的欧式距离。因此，对角方向相邻像素之间的距离值为2

（3）矢量g的方向可以通过中心像素z5z_5z5​相关邻域的单位矢量给出，这里的邻域是对称出现的，即四个方向对：(z1,z9),(z2,z8),(z3,z7),(z6,z4)(z_1, z_9),(z_2, z_8),(z_3, z_7),(z_6, z_4)(z1​,z9​),(z2​,z8​),(z3​,z7​),(z6​,z4​)。沿着4个方向对上求其梯度矢量和，可以给出当前像素z5z_5z5​的平均梯度估计，则有

G=(z1−z9)⋅14⋅[−1,1]+(z2−z8)⋅12⋅[0,1]+(z3−z7)⋅14⋅[1,1]+(z6−z4)⋅12⋅[1,0]G=(z_1-z_9)\cdot\frac{1}{4}\cdot[-1,1]+(z_2-z_8)\cdot\frac{1}{2}\cdot[0,1]+(z_3-z_7)\cdot\frac{1}{4}\cdot[1,1]+(z_6-z_4)\cdot\frac{1}{2}\cdot[1,0]G=(z1​−z9​)⋅41​⋅[−1,1]+(z2​−z8​)⋅21​⋅[0,1]+(z3​−z7​)⋅41​⋅[1,1]+(z6​−z4​)⋅21​⋅[1,0] =[(z3−z7−z1+z9)⋅14+(z6−z4)⋅12,(z3−z7+z1−z9)⋅14+(z2−z8)⋅12]=[(z_3-z_7-z_1+z_9)\cdot\frac{1}{4}+(z_6-z_4)\cdot\frac{1}{2},(z_3-z_7+ z_1-z_9)\cdot\frac{1}{4} + (z_2-z_8)\cdot\frac{1}{2}]=[(z3​−z7​−z1​+z9​)⋅41​+(z6​−z4​)⋅21​,(z3​−z7​+z1​−z9​)⋅41​+(z2​−z8​)⋅21​]

式中, 4个单位向量 [1, 1]，[-1, 1]，[0, 1], [1, 0] 控制差分的方向，系数1/4, 1/2为距离反比权重。 （4）理论上应该对G除以4得到平均梯度估计，除法会丢失低阶的重要字节, 更方便的是把向量乘于4，而不是除于4，以保留低阶字节。因此，计算出的估计值比平均梯度在数值上扩大了16倍。

G′=4⋅GG'=4\cdot GG′=4⋅G

=[z3−z7−z1+z9+2⋅(z6−z4),z3−z7+z1−z9+2⋅(z2−z8)]=[z_3-z_7-z_1+z_9+2\cdot (z_6-z_4),z_3-z_7+z_1-z9+2\cdot (z_2-z_8)]=[z3​−z7​−z1​+z9​+2⋅(z6​−z4​),z3​−z7​+z1​−z9+2⋅(z2​−z8​)]

=[z3+2⋅z6+z9−z1−2⋅z4−z7,z1+2⋅z2+z3−z7−2⋅z8−z9]=[z_3+2\cdot z_6+z_9-z_1-2\cdot z_4-z_7,z_1+2\cdot z_2+z_3-z_7-2\cdot z_8-z_9]=[z3​+2⋅z6​+z9​−z1​−2⋅z4​−z7​,z1​+2⋅z2​+z3​−z7​−2⋅z8​−z9​]

（5）按x-y方向，可分别写成：

G′x=(z3+2⋅z6+z9)−(z1+2⋅z4+z7)G'x = (z_3 + 2\cdot z_6 + z_9) - (z_1 + 2\cdot z_4 + z_7)G′x=(z3​+2⋅z6​+z9​)−(z1​+2⋅z4​+z7​)

G′y=(z1+2⋅z2+z3)−(z7+2⋅z8+z9)G'y = (z_1 + 2\cdot z_2 + z_3) - (z_7 + 2\cdot z_8 + z_9)G′y=(z1​+2⋅z2​+z3​)−(z7​+2⋅z8​+z9​)

即Sobel的横向和纵向的滤波矩阵为

G'x= \left\[ \begin{matrix} {-1} & {0} & {1} \\ {-2} & {0} &{2} \\ {-1} & {0} & {1} \end{matrix} \right\]

和

G'y= \left\[ \begin{matrix} {1} & {2} & {1} \\ {0} & {0} &{0} \\ {-1} & {-2} & {-1} \end{matrix} \right\]

拉普拉斯算子是n维欧式空间的一个二阶微分算子，其定义为两个梯度向量算子的内积（也就是梯度的散度）： Δ=∇⋅∇\Delta=\nabla\cdot\nablaΔ=∇⋅∇ =(∂∂xi⃗+∂∂yj⃗)⋅(∂∂xi⃗+∂∂yj⃗)=\left(\frac{\partial }{\partial x}\vec{i}+\frac{\partial }{\partial y}\vec{j}\right)\cdot\left(\frac{\partial }{\partial x}\vec{i}+\frac{\partial }{\partial y}\vec{j}\right)=(∂x∂​i+∂y∂​j​)⋅(∂x∂​i+∂y∂​j​) =∂2∂x2+∂2∂y2=\frac{\partial^2 }{\partial x^2}+\frac{\partial^2 }{\partial y^2}=∂x2∂2​+∂y2∂2​ 其在二维空间上的表达式为 Δf=∂f2∂x2+∂f2∂y2\Delta f=\frac{\partial f^2 }{\partial x^2}+\frac{\partial f^2 }{\partial y^2}Δf=∂x2∂f2​+∂y2∂f2​

（注：对于离散函数而言，导数退化为差分，因为相邻点像素距离均为1，故下面分母上的1均被省略）

对于一维离散来说， 一阶差分为 ∂f∂x=f(x+1)−f(x)\frac{\partial f}{\partial x}=f(x+1)-f(x)∂x∂f​=f(x+1)−f(x) 二阶差分为 ∂2f∂x2=f(x+1)−2f(x)+f(x−1)\frac{\partial^2 f}{\partial x^2}=f(x+1)-2f(x)+ f(x-1)∂x2∂2f​=f(x+1)−2f(x)+f(x−1)

因此，1维拉普拉斯运算可以通过1维卷积核[1,-2,1]实现

对于二维离散来说，f(x,y)对x右侧的一阶差分为 ∂f∂x=f(x+1,y)−f(x,y)\frac{\partial f}{\partial x} = f(x+1,y)-f(x,y)∂x∂f​=f(x+1,y)−f(x,y) f(x,y)对x左侧的一阶差分为 ∂f∂x=f(x,y)−f(x−1,y)\frac{\partial f}{\partial x} = f(x,y)-f(x-1,y)∂x∂f​=f(x,y)−f(x−1,y) f(x,y)对x的二阶差分(右侧一阶减左侧一阶，分母仍然是1略去)为 ∂2f∂x2=(f(x+1,y)−f(x,y))−(f(x,y)−f(x−1,y))\frac{\partial^2 f}{\partial x^2}=(f(x+1,y)-f(x,y))-(f(x,y)-f(x-1,y))∂x2∂2f​=(f(x+1,y)−f(x,y))−(f(x,y)−f(x−1,y)) =f(x+1,y)+f(x−1,y)−2f(x,y)=f(x+1,y)+f(x-1,y)-2f(x,y)=f(x+1,y)+f(x−1,y)−2f(x,y) 同理对f(x,y)对y的二阶差分为 ∂2f∂y2=f(x,y+1)−f(x,y)−(f(x,y)−f(x,y−1))\frac{\partial^2 f}{\partial y^2}= f(x,y+1)-f(x,y)-(f(x,y)-f(x,y-1))∂y2∂2f​=f(x,y+1)−f(x,y)−(f(x,y)−f(x,y−1)) =f(x,y+1)+f(x,y−1)−2f(x,y)=f(x,y+1)+f(x,y-1)-2f(x,y)=f(x,y+1)+f(x,y−1)−2f(x,y) 将上述两式子相加得（注：拉普拉斯算子是2个维上二阶差分的和） ▽2f=f(x+1,y)+f(x−1,y)−2f(x,y)+f(x,y+1)+f(x,y−1)−2f(x,y)\bigtriangledown^2 f= f(x+1,y)+ f(x-1,y)-2f(x,y)+f(x,y+1)+f(x,y-1)-2f(x,y)▽2f=f(x+1,y)+f(x−1,y)−2f(x,y)+f(x,y+1)+f(x,y−1)−2f(x,y) =(f(x+1,y)+f(x−1,y)+f(x,y+1)+f(x,y−1))−4f(x,y)=(f(x+1,y)+f(x-1,y)+f(x,y+1)+f(x,y-1))-4f(x,y)=(f(x+1,y)+f(x−1,y)+f(x,y+1)+f(x,y−1))−4f(x,y)

因此，2维拉普拉斯运算可以通过以下2维卷积核实现

\left\[ \begin{matrix} {0} & {1} & {0} \\ {1} & {-4} &{1} \\ {0} & {1} & {0} \end{matrix} \right\]

本文链接 : https://www.aye.ink/posts/e344f8d4/

本博客所有文章除特别声明外均为原创，采用 CC BY 4.0 CN协议 许可协议。转载请注明出处