一、点、线和边缘检测

这里用的图像检测方法主要是滤波操作。模板在图像中任意一点的响应R由下式给出：

<script type="math/tex; mode=display" id="MathJax-Element-1">R=\sum_{i=1}^9 \omega_{i}z_i</script>
其中， zizi<script type="math/tex" id="MathJax-Element-2">z_i</script> 是与模板系数 ωiωi<script type="math/tex" id="MathJax-Element-3">\omega_{i}</script> 相关的像素的灰度。
下面是点检测的模板：

线检测的模板如下（分别检测水平，45度，垂直和-45度的线）：

在谈边缘检测前，先看些基础知识：
二维函数的梯度定义如下：

<script type="math/tex; mode=display" id="MathJax-Element-4"> \triangledown f=\begin{bmatrix} \frac{\partial f}{\partial x}\\ \frac{\partial f}{\partial y} \end{bmatrix} </script>
幅值定义为：mag(▽f)=[(∂f∂x)2+(∂f∂y)2]12mag(▽f)=[(∂f∂x)2+(∂f∂y)2]12<script type="math/tex" id="MathJax-Element-5">mag(\triangledown f)=[(\frac{\partial f}{\partial x})^{2}+(\frac{\partial f}{\partial y})^{2}]^{\frac{1}{2}}</script>
可以用下列两种方式近似：
mag(▽f)≈(∂f∂x)2+(∂f∂y)2mag(▽f)≈(∂f∂x)2+(∂f∂y)2<script type="math/tex" id="MathJax-Element-6">mag(\triangledown f)\approx (\frac{\partial f}{\partial x})^{2}+(\frac{\partial f}{\partial y})^{2}</script>
mag(▽f)≈|∂f∂x|+|∂f∂y|mag(▽f)≈|∂f∂x|+|∂f∂y|<script type="math/tex" id="MathJax-Element-7">mag(\triangledown f)\approx |\frac{\partial f}{\partial x}|+|\frac{\partial f}{\partial y}|</script>
边缘检测使用如下两个准则之一来找到图像中灰度快速变化的位置：

1. 寻找灰度的一阶导数的幅度大于某个指定的阈值。
2. 寻找灰度的二阶导数有零交叉的位置。

我们可以从下面的图看出为什么要使用上面两个准则。

很明显一阶导数幅度大的地方表示图像灰度变化十分剧烈，同理二阶导数的零交叉点也是灰度变化十分剧烈的位置。

又根据导数在数值上可近似为差分。我们利用如下滤波器可以达到边缘检测的目的。

LoG检测器
考虑高斯函数：

<script type="math/tex; mode=display" id="MathJax-Element-8">G(x,y)=e^{\frac{x^{2}+y^{2}}{2\sigma ^{2}}}</script>
该函数的拉普拉斯算子是（即二阶微分）：

使用它卷积的效果： 平滑图像，降低噪声，产生一幅双边缘图像。因此可以通过双边缘之间的零交叉来定位边缘。

二、霍夫变换

采用Hough变换时，我们考虑一个点 (xi,yi)(xi,yi)<script type="math/tex" id="MathJax-Element-9">(x_i,y_i)</script> 和所有通过该点的直线。很明显，有无数条经过点 (xi,yi)(xi,yi)<script type="math/tex" id="MathJax-Element-10">(x_i,y_i)</script> 的直线，这些线对某些a值和b值来说，均满足 yi=axi+byi=axi+b<script type="math/tex" id="MathJax-Element-11">y_i=ax_i+b</script> 。将该公式写为 b=−axi+yib=−axi+yi<script type="math/tex" id="MathJax-Element-12">b=-ax_i+y_i</script> 并考虑ab平面(也称为参数空间)，可对一个固定点 (xi,yi)(xi,yi)<script type="math/tex" id="MathJax-Element-13">(x_i,y_i)</script> 产生单独的一条直线。此外，第二个点 (xj,yj)(xj,yj)<script type="math/tex" id="MathJax-Element-14">(x_j,y_j)</script> 也有这样一条在参数空间上与它相关的直线，这条直线和与 (xi,yi)(xi,yi)<script type="math/tex" id="MathJax-Element-15">(x_i,y_i)</script> 相关的直线相交于点 (a′,b′)(a′,b′)<script type="math/tex" id="MathJax-Element-16">(a',b')</script> ，其中a’和b’分别是xy平面上包含点 (xi,yi)(xi,yi)<script type="math/tex" id="MathJax-Element-17">(x_i,y_i)</script> 和 (xj,yj)(xj,yj)<script type="math/tex" id="MathJax-Element-18">(x_j,y_j)</script> 的直线的斜率和截距。事实上，在这条直线上的所有点都有在参数空间中相交于点 (a′,b′)(a′,b′)<script type="math/tex" id="MathJax-Element-19">(a',b')</script> 的直线。下图说明了这些概念。

但这种方法在直线趋近于垂直时，a 的值将趋于无穷大。因此我们用法线来表示直线：

<script type="math/tex; mode=display" id="MathJax-Element-20">xcos\theta +ysin\theta =\rho</script>
下图（a）说明了 ρρ<script type="math/tex" id="MathJax-Element-21">\rho</script> 和 θθ<script type="math/tex" id="MathJax-Element-22">\theta</script> 的几何意义。图（b）中每一条曲线表示通过 (xi,yi)(xi,yi)<script type="math/tex" id="MathJax-Element-23">(x_i,y_i)</script> 的一族直线。图（c）是将参数空间离散化进行计算。

霍夫变换把参数空间细分为累加器单元。其中， −D⩽ρ⩽D−D⩽ρ⩽D<script type="math/tex" id="MathJax-Element-24">-D\leqslant \rho \leqslant D </script>（D是图像中两个对角之间的最远距离）。−90度⩽θ⩽90度−90度⩽θ⩽90度<script type="math/tex" id="MathJax-Element-25">-90度\leqslant \theta \leqslant 90度 </script>。最初每一个累加器单元数值设置为0。然后对图像中的每一个点 (xk,yk)(xk,yk)<script type="math/tex" id="MathJax-Element-26">(x_k,y_k)</script> ，使用所有离散化后的 θθ<script type="math/tex" id="MathJax-Element-27">\theta</script> 值代入公式 ρ=xkcosθ+yksinθρ=xkcosθ+yksinθ<script type="math/tex" id="MathJax-Element-28">\rho=x_kcos\theta +y_ksin\theta</script> 求出相应的 ρρ<script type="math/tex" id="MathJax-Element-29">\rho</script> 值（将 ρρ<script type="math/tex" id="MathJax-Element-30">\rho</script> 值四舍五入为沿 ρρ<script type="math/tex" id="MathJax-Element-31">\rho</script> 轴最接近的允许单元值 ）。同时相应的累加器单元加1。上面的过程结束后，累加器表上记录下来的每个单元 (i,j) 的数值Q就意味着在xy平面上有Q个点位于线 xcosθj+ysinθj=ρixcosθj+ysinθj=ρi<script type="math/tex" id="MathJax-Element-32">xcos\theta_j +ysin\theta_j=\rho_i</script> 上。该表中最大的所对应的 (ρ0,θ0)(ρ0,θ0)<script type="math/tex" id="MathJax-Element-33">(\rho_0,\theta_0)</script> 就是xy平面上共线点数数目最多的直线方程的参数。

三、阈值处理

全局阈值处理

使用 Otsu 方法进行最佳全局阈值处理

类间方差最大化的思想是方差越大，越接近正确分割图像的阈值。下面给出类间方差的表达式（假设选定一个阈值k，C1是灰度级为[0,1,2,3,…,k]的一组像素，C2是灰度级为[k+1,..,.L-1]的一组像素）：

其中，p1(k)p1(k)<script type="math/tex" id="MathJax-Element-34">p_1(k)</script> 是集合C1发生的概率， p2(k)p2(k)<script type="math/tex" id="MathJax-Element-35">p_2(k)</script> 是集合C2发生的概率：
P1(k)=∑ki=0piP1(k)=∑i=0kpi<script type="math/tex" id="MathJax-Element-36">P_1(k)=\sum_{i=0}^kp_i</script>
P2(k)=∑L−1i=k+1piP2(k)=∑i=k+1L−1pi<script type="math/tex" id="MathJax-Element-37">P_2(k)=\sum_{i=k+1}^{L-1}p_i</script>

m1(k)m1(k)<script type="math/tex" id="MathJax-Element-38">m_1(k)</script> 是集合C1像素的平均灰度， m2(k)m2(k)<script type="math/tex" id="MathJax-Element-39">m_2(k)</script> 是集合C2像素的平均灰度， mGmG<script type="math/tex" id="MathJax-Element-40">m_G</script> 是全局均值：
m1(k)=∑ki=0ipim1(k)=∑i=0kipi<script type="math/tex" id="MathJax-Element-41">m_1(k)=\sum_{i=0}^kip_i</script>
m2(k)=∑L−1i=k+1ipim2(k)=∑i=k+1L−1ipi<script type="math/tex" id="MathJax-Element-42">m_2(k)=\sum_{i=k+1}^{L-1}ip_i</script>
mG(k)=∑L−1i=0ipimG(k)=∑i=0L−1ipi<script type="math/tex" id="MathJax-Element-43">m_G(k)=\sum_{i=0}^{L-1}ip_i</script>

定义类间方差与图像总灰度方差的比值为：η(k)=σ2B(k)σ2Gη(k)=σB2(k)σG2<script type="math/tex" id="MathJax-Element-44">\eta(k)=\frac{\sigma^2_B(k)}{\sigma^2_G}</script>

使用移动平均值的图像阈值处理

令 zk+1zk+1<script type="math/tex" id="MathJax-Element-45">z_{k+1}</script> 表示第 k+1 步扫描时所遇到的点的灰度，那么这个新点处的移动平均由下式给出：

<script type="math/tex; mode=display" id="MathJax-Element-46">m(k+1)=m(k)+\frac{1}{n}(z_{k+1}-z_{n-k})</script>
使用下式实现分割：
<script type="math/tex; mode=display" id="MathJax-Element-47"> f(x,y)=\left\{\begin{matrix} 1, f(x,y)>Km_{x,y}\\ 0,\ other\ situation \end{matrix}\right. </script>
其中K是[0,1]区间的常数， mxymxy<script type="math/tex" id="MathJax-Element-48">m_{xy}</script> 是输入图像中点（x,y）处的移动平均。

四、分水岭图像分割

构建大坝（Dam Construction）

最简单的构建大坝的方法就是利用形态学运算——膨胀。
下图展示了第n-1步淹没的两个集水盆地：

接着展现了第 n 步淹没的结果：

最后构建水坝：

为了说明下文，令M1和M2表示两个区域中的最小值点坐标的集合。将集水盆地点的坐标集合与这两个在溢出的第n-1步的最小值点的坐标集合联系起来，在第n-1步溢出处，两个最小值分别表示为 Cn−1(M1)Cn−1(M1)<script type="math/tex" id="MathJax-Element-207">C_{n-1}(M_1)</script> 和 Cn−1(M2)Cn−1(M2)<script type="math/tex" id="MathJax-Element-208">C_{n-1}(M_2)</script>。它们代表上图第一幅图的两个灰色区域。再令C[n-1]表示这两个集合的并集。上图第一幅图有两个连通分量，第二幅图只有一个连通分量。令q表示第二幅图的连通分量。注意到，第一幅图的两个连通分量可以由“与”操作（q∩C[n−1]q∩C[n−1]<script type="math/tex" id="MathJax-Element-209">q\cap C[n-1]</script>）从q中提取出来。

分水岭算法

令 M1M1<script type="math/tex" id="MathJax-Element-1870">M_1</script>, M2M2<script type="math/tex" id="MathJax-Element-1871">M_2</script> ……<script type="math/tex" id="MathJax-Element-1872">\ldots</script> 表示图像g(x,y)的区域最小值的坐标的集合， C(Mi)C(Mi)<script type="math/tex" id="MathJax-Element-1873">C(M_i)</script> 表示与区域最小值 MiMi<script type="math/tex" id="MathJax-Element-1874">M_i</script> 联系的集水盆地的点的坐标集合。令Cn(Mi)Cn(Mi)<script type="math/tex" id="MathJax-Element-1875">C_n(M_i)</script> 表示集水盆地与淹没阶段n的区域最小值 MiMi<script type="math/tex" id="MathJax-Element-1876">M_i</script> 联系的的点的坐标集合，最后令T[n] 表示满足 g(s,t)<ng(s,t)<n<script type="math/tex" id="MathJax-Element-1877">g(s,t)Cn(Mi)Cn(Mi)<script type="math/tex" id="MathJax-Element-1878">C_n(M_i)</script> 是由下式给出的一幅二值图像：

<script type="math/tex; mode=display" id="MathJax-Element-1879">C_n(M_i)=C(M_i)\cap T[n]</script>
接下来，我们令C[n]表示在阶段n 中已被水淹没的集水盆地的并：
<script type="math/tex; mode=display" id="MathJax-Element-1880">C[n]=\cup_{i=1}^RC(M_i)</script>
我们可以理解为：C[n-1]中的每一个连通分量都恰好包含在T[n]的一个连通分量。下面是分水岭算法的步骤：