当前位置:   article > 正文

数字图像的距离变换算法_距离变换法 讲解

距离变换法 讲解

在这里插入图片描述

一、图像数字化

通过传感器获得的图像是平面坐标(x,y)的连续函数f(x,y),它的值图像对应位置的亮度。为了能够让计算机来处理,需要对图像进行采样,并且对亮度值进行量化。

1、采样。对连续函数f(x,y)进行采样,就是分别对x轴和y轴,按照固定间隔取值,得到平面坐标上的M×N个点,将其函数值作为元素生成M行N列的矩阵。

2、量化亮度值。将f(x,y)的值转化为等价的整数值的过程称为量化,量化的级别越高,图像越细致。通常将亮度值表示为0-255之间的整数。

这样,在计算机中通常以矩阵表示数字图像,矩阵的元素对应图像的亮度信息。

二、距离

满足以下三个条件的函数 D D D称作距离:
(1)同一性: D ( p , q ) ≥ 0 。 当 且 仅 当 p = q 时 , D ( p , q ) = 0 。 D(p,q)\ge 0。 当且仅当p=q时,D(p,q)=0。 D(p,q)0p=qD(p,q)=0

(2)对称性: D ( p , q ) = D ( q , p ) 。 D(p,q)=D(q,p)。 D(p,q)=D(q,p)

(3)三角不等式: D ( p , r ) ≤ D ( p , q ) + D ( q , r ) 。 D(p,r)\le D(p,q)+D(q,r)。 D(p,r)D(p,q)+D(q,r)

数字图像的距离有多种定义方式,包括欧式距离、城市街区距离、棋盘距离等。以下以两坐标点 a = ( i , j ) a=(i,j) a=(i,j) b = ( k , l ) b=(k,l) b=(k,l)的距离为例,来说明各种距离的定义方式。

欧式距离 D e {D_e} De就是通常所说的距离,它定义为
D e ( a , b ) = ( ( i − k ) 2 ) + ( j − l ) 2 D_e(a,b)=\sqrt{((i-k)^2)+(j-l)^2} De(a,b)=((ik)2)+(jl)2

欧式距离在事实上比较直观,但是平方根计算比较费时,且距离可能不是数。

城市街区距离 D 4 D_4 D4,它定义为在只允许横向和纵向运动的情况下,从起点到终点的移动步数。用公式表示为
D 4 ( a , b ) = ∣ i − k ∣ + ∣ j − l ∣ D_4(a,b)=|i-k|+|j-l| D4(a,b)=ik+jl

符号 D 4 D_4 D4中的 4 4 4表示在这种定义下,像素点是 4 4 4邻接的,即每个点只与它的上、下、左、右相邻的 4 4 4个点之间的距离为 1 1 1

如果允许横向、纵向和沿对角线方向移动,则可以得到棋盘距离 D 8 D_8 D8的定义
D 8 ( a , b ) = m a x { ∣ i − k ∣ , ∣ j − l ∣ } D_8(a,b)=max\{|i-k|,|j-l|\} D8(a,b)=max{ik,jl}

符号 D 8 D_8 D8中的 8 8 8表示在这种定义下,像素点是 8 8 8邻接的,即每个点只与它的上、下、左、右、四个对角线方向相邻的 8 8 8个点之间的距离为 1 1 1

显然,以上三种距离的定义都满足距离的定义条件。

三、距离变换

距离变换也叫作距离函数或者斜切算法。它是距离概念的一个应用,图像处理的一些算法以距离变换为基础。距离变换描述的是图像中像素点与某个区域块的距离,区域块中的像素点值为0,临近区域块的像素点有较小的值,离它越远值越大。

以二值图像为例,其中区域块内部的像素值为1,其他像素值为0。距离变换给出每个像素点到最近的区域块边界的距离,区域块内部的距离变换结果为0。输入图像如图1所示,D4距离的距离变换结果如图2所示。

下面来讨论距离变换算法,其核心是利用两个小的局部掩膜遍历图像。第一遍利用掩模1,左上角开始,从左往右,从上往下。第二遍利用第二个掩模,右下角开始,从右往左,从下往上。掩模形状如下图所示:

按照某种距离(如: D 4 D_4 D4距离或 D 8 D_8 D8距离)对大小为 M × N M×N M×N的图像中的区域块作距离变换,算法过程如下:

1、建立一个大小为 M × N M×N M×N的数组 F F F,作如下的初始化:将区域块中的元素设置为 0 0 0,其余元素设置为无穷;

2、利用掩模1(mask1),左上角开始,从左往右,从上往下遍历数组,将掩模中P点对应的元素的值作如下更新:
F ( P ) = m i n q ∈ m a s k 1 { F ( P ) , D ( P , q ) + F ( q ) } F(P)=\underset{{q\in mask1}}{min}\{F(P),D(P,q)+F(q)\} F(P)=qmask1min{F(P),D(P,q)+F(q)}

3、利用掩模2(mask2),右下角开始,从右往左,从下往上遍历数组,将掩模中P点对应的元素的值作如下更新:
F ( P ) = m i n q ∈ m a s k 2 { F ( P ) , D ( P , q ) + F ( q ) } F(P)=\underset{{q\in mask2}}{min}\{F(P),D(P,q)+F(q)\} F(P)=qmask2min{F(P),D(P,q)+F(q)}

最终得到的更新后的数组即为距离变换的结果。

这个算法过程在图像编边界需要做出调整,因为在边界处,掩模不能全部覆盖图像,这时可以将掩模中没有对应元素的位置的值当作0来处理。

四、OpenCV代码实现

这个算法过程经过很多的改进,但基本原理并没有区别。开源计算机视觉库OpenCV中,距离变换算法有相应的实现,声明如下:

CV_EXPORTS_W void distanceTransform( InputArray src, OutputArray dst,
                                     int distanceType, int maskSize, int dstType=CV_32F);
  • 1
  • 2

参数详解:

  • InputArray src:输入图像,一般为二值图像;
  • OutputArray dst:输出的图像,距离变换结果;
  • int distanceType:用于距离变换的距离类型(欧氏距离:DIST_L2 = 2; D 4 D_4 D4距离:DIST_L1 = 1; D 8 D_8 D8距离:DIST_C = 3等);
  • int mask_size:距离变换掩模的大小,一般为3或5;
  • int dstType:输出图像的数据类型,可以为CV_8U或CV_32F。

下面我们用一个具体的例子来展示距离变换的效果。将大小为 480 × 480 480\times480 480×480,其中有三个像素点设置为1,其余都为0的一张图片作为输入图像,分别在欧式距离、 D 4 D_4 D4距离和 D 8 D_8 D8距离下,距离变换的结果。

效果如下图所示:

下面是代码实现:

#include<opencv2/opencv.hpp>
using namespace cv;
using namespace std;

int main()
{
    //初始化输入图像和变换结果图像
    Mat mat(480, 480, CV_8UC1, Scalar(0)), transMatE, transMatD4, transMatD8;

    //给输入图像指定三个像素点作为距离变换原点(区域块)
    mat.at<uchar>(100, 200) = 1;
    mat.at<uchar>(200, 100) = 1;
    mat.at<uchar>(300, 300) = 1;

    //将将输入图像中1和0调换,使得原点距离为0
    mat = 1 - mat;

    //显示原始图像(显示为黑色)
    imshow("原始图片", mat);

    //分别利用欧式距离、D4距离和D8距离作距离变换,将结果存入transMatD4、transMatD8和transMatE
    distanceTransform(mat, transMatE, DIST_L2, 0);
    distanceTransform(mat, transMatD4, DIST_L1, 0, CV_8U);
    distanceTransform(mat, transMatD8, DIST_C, 0);

    //欧式距离与D8距离作变换后,值为32位浮点数,以下代码将其值转为uchar类型
    transMatE.convertTo(transMatE, CV_8U);
    transMatD8.convertTo(transMatD8, CV_8U);

    //显示距离变换结果
    imshow("欧式距离变换后的图片", transMatE);
    imshow("D4距离变换后的图片", transMatD4);
    imshow("D8距离变换后的图片", transMatD8);


    waitKey();

    return 0;
  • 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
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/weixin_40725706/article/detail/407036
推荐阅读
相关标签
  

闽ICP备14008679号