精华内容
下载资源
问答
  • 几种边缘检测微分算子的比较

    千次阅读 2017-11-21 21:15:06
    预备知识: 梯度------梯度的本意是一个向量(矢量),表示某一函数在该点处的方向导数沿着该...对于图像来说,是一个二维的离散型数集,通过推广二维连续型求函数偏导的方法,来求得图像的偏导数。 梯度是一个矢量

    预备知识:

    梯度------梯度的本意是一个向量(矢量),表示某一函数在该点处的方向导数沿着该方向取得最大值

    ,即函数在该点处沿着该方向(此梯度的方向)变化最快,变化率最大(为该梯度的模)。

    该函数就称为函数 在点P(x,y)的梯度,记作grad f(x,y)


    对于图像来说,是一个二维的离散型数集,通过推广二维连续型求函数偏导的方法,来求得图像的偏

    导数。

    这里写图片描述

    梯度是一个矢量,则(x,y)处的梯度表示为这里写图片描述

    其大小为:这里写图片描述

    不同图像灰度不同,边界处一般会有明显的边缘,利用此特征可以分割图像。需要说明的是:边缘和物

    体间的边界并不等同,边缘指的是图像中像素的值有突变的地方,而物体间的边界指的是现实场景中的存在

    于物体之间的边界。有可能有边缘的地方并非边界,也有可能边界的地方并无边缘,因为现实世界中的物体

    是三维的,而图像只具有二维信息,从三维到二维的投影成像不可避免的会丢失一部分信息;另外,成像过

    程中的光照和噪声也是不可避免的重要因素。正是因为这些原因,基于边缘的图像分割仍然是当前图像研究

    中的世界级难题,目前研究者正在试图在边缘提取中加入高层的语义信息。

    以像素值为y,以坐标为x(x是二维或者一维),灰度的突变就意味着函数y=f(x)的导数或者高阶导数会

    发生突变。因此,我们可以通过检测导数来检测图像的边缘。

    在实际中往往只用到一阶和二阶导数,虽然原理上可用更高阶的导数,但因为噪声的影响,在纯粹的二阶导数操作中就会出现对噪声的敏感现象,三阶以上的导数信息往往失去了应用价值。导数操作中就会出现

    对噪声的敏感现象,三阶以上的导数信息往往失去了应用价值。二阶导数还可以说明灰度突变的类型。在有

    些情况下,如灰度变化均匀的图像,只利用一阶导数可能找不到边界,此时二阶导数就能够提供很有用的信

    息。二阶导数对噪声也比较敏感,解决的方法是先对图像进行平滑滤波,消除部分噪声,然后再对处

    的图像进行边缘检测不过,利用二阶导数信息的算法是基于过零检测的,因此得到的边缘点数比较少,

    利于后继的处理和识别工作。

    各种算子的存在就是对这种导数分割原理进行的实例化计算,是为了在计算过程中直接使用的一种计算

    单位。

          (1)Roberts算子:边缘定位准,但是对噪声敏感。适用于边缘明显且噪声较少的图像分割Roberts

    边缘检测算子一种利用局部差分算子寻找边缘的算子,Robert算子图像处理后结果边缘不是很平滑。经分析

    ,由于Robert算子通常会在图像边缘附近的区域内产生较宽的响应,故采用上述算子检测的边缘图像常需做

    细化处理,边缘定位的精不是很高。

    Robert算子是一个2x2算子模板

     

     

    具体使用

    判断f(x,y)是否是边缘点:

    建立一幅二值图像,用于保存边缘检测的结果。如果G(x,y)>T,就将像素值设为1,否则为0。

      (2)Prewitt算子:对噪声有抑制作用,抑制噪声的原理是通过像素平均,但是像素平均相当于对图像

    的低通滤波所以Prewitt算子对边缘的定位不如Roberts算子。

     具体原理和使用:

    Pv用于检测水平边缘,Ph用于检测水平边缘。

    G(i)=|[f(i-1,j-1)+f(i-1,j)+f(i-1,j+1)]-[f(i+1,j-1)+f(i+1,j)+f(i+1,j+1)]|
    G(j)=|[f(i-1,j+1)+f(i,j+1)+f(i+1,j+1)]-[f(i-1,j-1)+f(i,j-1)+f(i+1,j-1)]|
    P(i,j)=max[G(i),G(j)]或 P(i,j)=G(i)+G(j)

      经典Prewitt算子认为:凡灰度新值大于或等于阈值的像素点都是边缘点。即选择适当的阈值T,若P(i,j)

    ≥T,则(i,j)为边缘点,P(i,j)为边缘图像。P是与原图像同等大小的边缘检测结果。

            (3)Sobel算子:Sobel算子和Prewitt算子都是加权平均,但是Sobel算子认为,邻域的像素对当前像素

    产生的影响不是等价的,所以距离不同的像素具有不同的权值,对算子结果产生的影响也不同。一般来说,

    距离越远,产生的影响越小。抗噪性也比较好。

    Sobel算子也有两个,一个是检测垂直边缘的模板(通过计算水平的两个像素值之间的差),另一个是

    检测垂直边缘的模板(通过计算垂直的两个像素值之间的差)。  

        具体计算如下:

    Gx = (-1)*f(x-1, y-1) + 0*f(x,y-1) + 1*f(x+1,y-1)

          +(-2)*f(x-1,y) + 0*f(x,y)+2*f(x+1,y)

          +(-1)*f(x-1,y+1) + 0*f(x,y+1) + 1*f(x+1,y+1)

        = [f(x+1,y-1)+2*f(x+1,y)+f(x+1,y+1)]-[f(x-1,y-1)+2*f(x-1,y)

    +f(x-1,y+1)]

     

    Gy =1* f(x-1, y-1) + 2*f(x,y-1)+ 1*f(x+1,y-1)

          +0*f(x-1,y) 0*f(x,y) + 0*f(x+1,y)

          +(-1)*f(x-1,y+1) + (-2)*f(x,y+1) + (-1)*f(x+1, y+1)

         = [f(x-1,y-1) + 2f(x,y-1) + f(x+1,y-1)]-[f(x-1, y+1) 

     + 2*f(x,y+1)+f(x+1,y+1)]

     

      其中f(x,y), 表示图像(x,y)点的灰度值;


       

      如果梯度G大于某一阀值 则认为该点(x,y)为边缘点。

    与Prewitt算子相比,Sobel算子对于象素位置的影响作了加权,因此效果更好。

    然后可用以下公式计算梯度方向,从而可以推断边缘所在的方向:


    上面的算子是利用一阶导数的信息,属于梯度算子范畴。

    下面是基于二阶导数的边缘检测算子。

         (4)Laplacian算子

    Laplacian算子定义为它的差分形式为


      表示成模板的形式就是

      同理,如果是计算八邻域的二阶导数,模板就是:

      可以看出,Laplace算子对孤立象素的响应要比对边缘或线的响应要更强烈,因此只适用于无噪声

    象。首先对图像进行高斯卷积滤波进行降噪处理,再采用Laplace算子进行边缘检测,就可以提高算子对

    声和离散点的鲁棒性。也就是,先用高斯卷积核做滤波降噪,然后再求二阶导检测边缘。用公式表示如下:

    其中,上面这个式子成立的依据是:

    我们把LoG叫做高斯型Laplacian算子(Laplace of Gaussian)

      所以可以先对高斯函数进行偏导操作,然后进行卷积求解。

      高斯卷积函数定义为:



       因此,我们可以LOG核函数定义为

       滤波+高斯卷积两步结合,就是直接对有原图像做LoG卷积。高斯卷积的效果是使得图像变得平滑去噪

    同时,可以利用零交叉性质来检测边缘。如下图所示:                                  

                                                      
                                                     

       所以,使用高斯型拉普拉斯算子的步骤为:                                     1)对原图像进行Log卷积                                                  2)检测图像中的过零点( Zero Crossings,也即从负到正或从正到负,可以采用检查四邻域的方式

          3)对过零点进行阈值化。

    (6)canny算子
    与上述几种算子相比,canny算子效果最好,但同时也最复杂。
            1)生成高斯滤波系数,确定滤波器的大小。较小的滤波器产生的模糊效果也较少,这样就可以检测较
    、变化明显的细线。较大的滤波器产生的模糊效果也较多,将较大的一块图像区域涂成一个特定点的颜色
    值。这样带来的结果就是对于检测较大、平滑的边缘更加有用,例如彩虹的边缘。
       2)用生成的高斯滤波器对原图像进行平滑操作。
       3)一阶差分偏导计算梯度值和方向。
    其中f为图像灰度值,P代表X方向梯度幅值,Q代表Y方向 梯度幅值,M是该点幅值,Θ是梯度方向,
    也就是角度。

       4)抑制非极大值

      仅仅得到全局的梯度并不足以确定边缘,因此为确定边缘,必须保留局部梯度最大的点,而抑制非极大

    值。解决方法:利用梯度的方向。

        

      四个扇区的标号为0到3,对应3*3邻域的四种可能组合。在每一点上,邻域的中心像素M与沿着梯度线的

    两个像素相比。如果M的梯度值不比沿梯度线的两个相邻像素梯度值大,则令M=0。否则不变。这样就保留了

    梯度的极大值,抑制了非极大值。

     (5)用双阈值算法检测和连接边缘

      对非极大值抑制图像作用两个阈值th1和th2,两者关系th1=0.4th2 (这里的0.4是统计图像的直方图,

    对阈值进行判定得出的)。首先把梯度幅值的直方图(求出来,选取占直方图总数%多少(自己定,代码中

    定义70%)所对应的梯度幅值为高阈值,高阈值的0.4为低阈值,这只是一种简单策略。也可以采用其他的。

      我们把梯度值小于th1的像素的灰度值设为0,得到图像1。然后把梯度值小于th2的像素的灰度值设为0,

    得到图像2。由于图像2的阈值较高,去除大部分噪音,但同时也损失了有用的边缘信息。而图像1的阈值较低

    ,保留了较多的信息,我们可以以图像2为基础,以图像1为补充来连结图像的边缘。

      链接边缘的具体步骤如下:
      对图像2进行扫描,当遇到一个非零灰度的像素p(x,y)时,跟踪以p(x,y)为开始点的轮廓线,直到轮廓线

    的终点q(x,y)。
       考察图像1中与图像2中q(x,y)点位置对应的点s(x,y)的8邻近区域。如果在s(x,y)点的8邻近区域中有非

    零像素s(x,y)存在,则将其包括到图像2中,作为r(x,y)点。从r(x,y)开始,重复第一步,直到我们在图像1

    和图像2中都无法继续为止。
       当完成对包含p(x,y)的轮廓线的连结之后,将这条轮廓线标记为已经访问。回到第一步,寻找下一条轮

    廓线。重复第一步、第二步、第三步,直到图像2中找不到新轮廓线为止。

    展开全文
  • 现在给定一个计算图,请你根据所有输入变量计算函数值及其偏导数(即梯度)。 例如,给定输入,,上述计算图获得函数值 (;并且根据微分链式法则,上图得到的梯度 ∇。 知道你已经把微积分忘了,所以这里只要求你处理...

    原题链接

    “计算图”(computational graph)是现代深度学习系统的基础执行引擎,提供了一种表示任意数学表达式的方法,例如用有向无环图表示的神经网络。 图中的节点表示基本操作或输入变量,边表示节点之间的中间值的依赖性。 例如,下图就是一个函数 ( 的计算图。

    在这里插入图片描述

    现在给定一个计算图,请你根据所有输入变量计算函数值及其偏导数(即梯度)。 例如,给定输入,,上述计算图获得函数值 (;并且根据微分链式法则,上图得到的梯度 ∇。

    知道你已经把微积分忘了,所以这里只要求你处理几个简单的算子:加法、减法、乘法、指数(e​x​​,即编程语言中的 exp(x) 函数)、对数(ln,即编程语言中的 log(x) 函数)和正弦函数(sin,即编程语言中的 sin(x) 函数)。

    友情提醒:

    常数的导数是 0;x 的导数是 1;e​x​​ 的导数还是 e​x​​;ln 的导数是 1;sin 的导数是 cos。
    回顾一下什么是偏导数:在数学中,一个多变量的函数的偏导数,就是它关于其中一个变量的导数而保持其他变量恒定。在上面的例子中,当我们对 x​1​​ 求偏导数 / 时,就将 x​2​​ 当成常数,所以得到 ln 的导数是 1,x​1​​x​2​​ 的导数是 x​2​​,sin 的导数是 0。
    回顾一下链式法则:复合函数的导数是构成复合这有限个函数在相应点的导数的乘积,即若有 (,(,则 /。例如对 sin 求导,就得到 cos。
    如果你注意观察,可以发现在计算图中,计算函数值是一个从左向右进行的计算,而计算偏导数则正好相反。

    输入格式:
    输入在第一行给出正整数 N(≤),为计算图中的顶点数。

    以下 N 行,第 i 行给出第 i 个顶点的信息,其中 ,。第一个值是顶点的类型编号,分别为:

    0 代表输入变量
    1 代表加法,对应 x​1​​+x​2​​
    2 代表减法,对应 x​1​​−x​2​​
    3 代表乘法,对应 x​1​​×x​2​​
    4 代表指数,对应 e​x​​
    5 代表对数,对应 ln
    6 代表正弦函数,对应 sin
    对于输入变量,后面会跟它的双精度浮点数值;对于单目算子,后面会跟它对应的单个变量的顶点编号(编号从 0 开始);对于双目算子,后面会跟它对应两个变量的顶点编号。

    题目保证只有一个输出顶点(即没有出边的顶点,例如上图最右边的 -),且计算过程不会超过双精度浮点数的计算精度范围。

    输出格式:
    首先在第一行输出给定计算图的函数值。在第二行顺序输出函数对于每个变量的偏导数的值,其间以一个空格分隔,行首尾不得有多余空格。偏导数的输出顺序与输入变量的出现顺序相同。输出小数点后 3 位。

    输入样例:

    7
    0 2.0
    0 5.0
    5 0
    3 0 1
    6 1
    1 2 3
    2 5 4
    输出样例:
    
    11.652
    5.500 1.716
    

    题解
    将每个节点的输入节点编号存入到节点结构体中,然后先正向bfs求每个节点的输出值,然后再方向求每个节点的导数,注意求导数的时候每个节点存储的导数是其输出变量的导数,求解的时候应该按照不同路径的导数相加,同一路径上的导数相乘。
    无论是正向还是方向均应按照拓扑序求解

    #include<bits/stdc++.h>
    #include<cmath>
    #define x first
    #define y second
    #define send string::npos
    #define lowbit(x) (x&(-x))
    #define left(x) x<<1
    #define right(x) x<<1|1
    using namespace std;
    typedef long long ll;
    typedef pair<int,int> PII;
    typedef struct Node * pnode;
    const int N = 1e6 + 10;
    const int M = 3 * N;
    const int INF = 0x3f3f3f3f;
    const ll LINF = 0x3f3f3f3f3f3f3f3f;
    const int Mod = 1e9;
    int out[N],in[N];
    struct Node{
        double v,f;    //v代表此节点输出值,f代表输出值导数
        int la,lb;
        int op;
    }node[N];
    int head[N],cnt;
    int q[N],tt = 0,hh = 0;
    vector<int>s;   //起始节点
    struct Edge{
        int v,next;
    }edge[2 * M];
    void add(int u,int v){
        edge[cnt].v = v;
        edge[cnt].next = head[u];
        head[u] = cnt ++;
    }
    double op123(int t,double a,double b){
        if(t == 1)return a + b;
        if(t == 2)return a - b;
        if(t == 3)return a * b;
    }
    double op456(int t,double a){
        if(t == 4)return exp(a);
        if(t == 5)return log(a);
        if(t == 6)return sin(a);
    }
    void bfs(){
        for(int i = 0;i < s.size();i ++)q[tt ++] = s[i];
        while(hh < tt){
            int t = q[hh ++];
    //        cout<<t<<endl;
            double a = node[node[t].la].v,b = node[node[t].lb].v;
            int type = node[t].op;
            if(type == 1 || type == 2 || type == 3)node[t].v = op123(type,a,b);
            else if(type != 0)node[t].v = op456(type,a);
    //        cout<<t<<" "<<type<<" "<<node[t].v<<endl;
            for(int i = head[t];~i;i = edge[i].next){
                int v = edge[i].v;
                in[v] --;
                if(in[v] == 0)	//如果此处不按拓扑序,则会产生大量的重复节点
                    q[tt ++] = v;
            }
        }
    }
    void top(int root){
        hh = tt = 0;
        q[tt ++] = root;
        while(hh < tt){
            int t = q[hh ++];
    //        cout<<t<<endl;
            if(node[t].op == 1 || node[t].op == 2 || node[t].op == 3){
                if(node[t].op == 1){
                    node[node[t].la].f += (1 * node[t].f);
                    node[node[t].lb].f += (1 * node[t].f);
                }else if(node[t].op == 2){
                    node[node[t].la].f += (1 * node[t].f);
                    node[node[t].lb].f += (-1 * node[t].f);
                }else{
                    node[node[t].la].f += (node[node[t].lb].v * node[t].f);
                    node[node[t].lb].f += (node[node[t].la].v * node[t].f);
                }
                out[node[t].la] --,out[node[t].lb] --;
                if(out[node[t].la] == 0)q[tt ++] = node[t].la;
                if(out[node[t].lb] == 0)q[tt ++] = node[t].lb;
            }
            else if(node[t].op != 0){
                if(node[t].op == 4)node[node[t].la].f += (node[t].v * node[t].f);
                else if(node[t].op == 5)node[node[t].la].f += (node[t].f / node[node[t].la].v) ;
                else node[node[t].la].f += (cos(node[node[t].la].v) * node[t].f);
                out[node[t].la] --;
                if(out[node[t].la] == 0)q[tt ++] = node[t].la;
            }
        }
    }
    int main(){
        memset(head,-1,sizeof head);
        int n,t,a,b;
        double x;
        cin>>n;
        for(int i = 0;i < n;i ++){
            cin>>t;
            if(t == 0){
                cin>>x;
                s.push_back(i);
                node[i].v = x;
            }
            else if(t == 1 || t == 2 || t == 3){
                cin>>a>>b;
                add(a,i);
                add(b,i);
                out[a] ++,out[b] ++;
                in[i] ++,in[i] ++;
                node[i].la = a,node[i].lb = b;
            }else if(t == 4 || t == 5 || t == 6){
                cin>>a;
                add(a,i);
                out[a] ++;
                in[i] ++;
                node[i].la = a;
            }
            node[i].op = t;
        }
        int root = -1;
        for(int i = 0;i < n;i ++)
            if(!out[i])
                root = i;
    //    cout<<"root:"<<root<<endl;
        bfs();
        node[root].f = 1;		//最后一个节点的输出值导数应该为1
        top(root);
        printf("%.3f\n%.3f",node[root].v,node[s[0]].f);
        for(int i = 1;i < s.size();i ++)printf(" %.3f",node[s[i]].f);
        return 0;
    }
    
    
    展开全文

空空如也

空空如也

1 2 3 4 5
收藏数 81
精华内容 32
关键字:

偏导数几种表示方法