Snake模型算法的基本思想数学模型及工作原理

Snake模型简介及其编程实现Snake模型也称为主动轮廓线模型，最初由Kass等人在1987年第一届计算机国际视觉会议上提出，一经提出就成为计算机视觉领域研究的热点。

Snake的基本思想是通过人的识别能力，在图像中目标边界附近确定初始轮廓线，然后对曲线进行能量最小化变形，使其锁定在待分割目标的边界上。

Snake模型之所以能得到如此重视，是因为它将图像目标的先验知识（如大小、位置、形状等）与图像特征（灰度、梯度、纹理等）结合起来，克服了传统图像分割方法将二者分离的缺陷。

近年来，许多文章从传统Snake模型的能量函数构造和求解算法方面进行改进，在其基础上衍生出了许多新的Snake模型。

1、Snake模型的基本原理其基本思想是依据图像信息进行曲线（曲面）演化，使其最终找到目标物体的边界。

这种方法将分割问题转化为最优化问题，利用闭合曲线（或曲面）形变的特定规律，定义度量闭合曲线（曲面）形变的能量函数，通过最小化能量函数使曲线（曲面）逐渐逼近图像中目标物体的边缘。

先提供待分割图像的一个初始轮廓的位置，并对其定义个能量函数，是轮廓沿能量降低的方向靠近。

当能量函数达到最小的时候，提供的初始轮廓收敛到图形中目标的真实轮廓。

Snake能量函数是有内部能量函数和外部能量函数组成，内部能量控制轮廓的平滑性和连续性，外部能量由图像能量和约束能量组成，控制轮廓向着实际轮廓收敛，其中约束能量可根据具体的对象形态定义，使得snake具有很大的灵活性。

Snake模型发展10多年来，许多学者对于经典的snake模型做了改进，提出各种改进的snake模型，其中梯度矢量流（Gradient Vector Flow, GVF）模型扩大了经典snake的外力作用范围，加强了对目标凹轮廓边缘的吸引力，提高了传统的snake模型。

2. 基本的Snake模型数学上，将活动轮廓表示成一条参数曲线V(s,t)=(x(s,t),y(s,t))，其中，V是曲线点的二维坐标，t是时间参数，s是弧长参数。

SNAKE（2）分组密码的积分攻击作者：官翔杨晓元魏悦川刘龙飞来源：《计算机应用》2014年第10期摘要：SNAKE是一种Feistel结构的分组密码算法，它由Lee等学者在JWISC 1997上提出（LEE C， CHA Y. The block cipher： SNAKE with provable resistance against DC and LC attacks. Proceedings of 1997 KoreaJapan Joint Workshop on Information Security and Cryptology. Berlin： Springer， 1997：3-7）。

针对目前对SNAKE算法的安全性分析主要是插值攻击及不可能差分攻击，评估了SNAKE（2）算法对积分攻击的抵抗能力。

利用高阶积分的思想，构造了一个8轮区分器，利用该区分器，对SNAKE（2）算法进行了9轮、10轮积分攻击。

〖BP （〗这是首次采用积分攻击的方法对SNAKE（2）算法进行攻击。

攻击结果表明，SNAKE （2）算法对10轮积分攻击是不免疫的。

关键词：分组密码；SNAKE（2）；积分攻击；攻击复杂度中图分类号：TN918文献标志码：A引言Lee等[1]在JWISC 1997上提出了SNAKE算法，它共有SNAKE（1）、SNAKE（2）两个版本[1-2]。

文献[1]证明了SNAKE算法关于线性分析与差分分析的安全性；同时，算法也对高阶差分攻击和插值攻击免疫。

但由于SNAKE算法的非线性变换比较简单，故利用插值攻击可恢复出简化的SNAKE算法中的部分密钥[2]。

孙兵[3]利用不可能差分的思想对算法进行了攻击，基于该算法的9轮不可能差分，对简化轮数的算法实施了不可能差分攻击。

魏悦川等[4]对SNAKE（2）算法进行了中间相遇攻击，利用构造的6轮区分器，对7轮、8轮、9轮算法分别进行了攻击[5]。

Snake模型算法的基本思想数学模型及工作原理Snake模型是由Kass等人首次提出的算法，广泛地应用于计算机视觉及图像处理中的各个领域，如边缘检测、图像分割、运动跟踪等，特别应用于图像中感兴趣目标轮廓的提取。

Snake模型引入高层知识，在处理局部间断的边缘时，提取效果比传统轮廓提取方法要好。

1 Snake模型的基本思想Snake模型又称为主动轮廓线模型(active eontour model)，其基本思想是依据图像信息进行曲线(曲面)演化，使其最终找到目标物体的边界。

这种方法将分割问题转化为最优化问题，利用闭合曲线(或曲面)形变的特定规律，定义度量闭合曲线(曲面)形变的能量函数，通过最小化能量函数使曲线(曲面)逐渐逼近图像中目标物体的边缘。

Snake模型能量函数的设计原则是:有利属性要能导致能量缩小。

有利属性包括曲线(曲面)连续、平滑、与高梯度区域的接近以及其他一些具体的先验知识。

这样，活动轮廓在取值范围内移动时，就能在能量函数的指导下收敛到局部边界，而且能保持曲线(曲面)的连续和平滑。

Snake模型是在曲线(曲面)本身的内力和图像数据的外部约束力作用下的移动的变形轮廓。

作用在Snake模型上的力依据轮廓所在的位置及其形状决定如何在空间局部的变化。

内力和外力的作用是不同的:内力起平滑约束作用，外力则引导Snake模型向图像特征移动。

2 基于Snake模型的轮廓提取方法对于传统的轮廓提取方法，首先要进行基本的边缘检测，然后进行边缘连接、二值化之后，继而进行轮廓跟踪处理。

在边缘检测时，易受局部噪声影响而产生虚假边缘，或者是不连续的间断边缘，无法保证分割或者提取的结果就是连续光滑的闭合轮廓;此外，基于底层信息的轮廓跟踪，一方面对二值化过程的依赖性比较大;另一方面，对于间断的边缘，使用上述简单方法将会跟踪失败。

这些都是传统计算机视觉中分层处理模型所无法解决的问题。

Snake模型为解决轮廓提取任务提供了新的思维方法。

计算机视觉实验二——图像分割：snake轮廓模型简介Snake是Active Contour Model的一种，它以构成一定形状的一些控制点为模版（轮廓线），通过模版自身的弹性形变，与图像局部特征相匹配达到调和，即某种能量函数极小化，完成对图像的分割。

每一个Snake都是能量最小曲线，受外部限制力引导及图像力的影响使它向着线和边缘等特征移动。

Snakes是活动轮廓模型：他们自动跟踪附近边缘，准确地使曲线集中。

尺度空间（scale-space）的连续性用来去扩大对特征周围区域的捕获。

Snakes提供一种许多视觉问题的统一的解决方法，包括检测边，线及主观轮廓；移动跟踪；及立体匹配。

我们成功使用Snakes用于交互解释（interactive interpretation），即用户提出一种限制力引导Snake靠近感兴趣的特征。

基本snake性能我们的基本snake模型是一条被控制的连续曲线，其曲线受图像力和外部限制力的影响。

内部样条(splint)力用来加以分段平滑限制。

图像力把snake推向显著图像特征，如线，边，主观轮廓等等。

外部限制力负责推动snakes靠近理想的局部最小值。

例如这些力，可以来自使用者接口，自动注意机制(automatic attentional mechanisms)，或者高层解释(high-level interpretations)。

实验关键步骤代码1．获取手动取点坐标，该部分代码如下14 % =========================================================================15 %获取手动取点坐标16 % =========================================================================17 %读取显示图像18 %I = imread('Coronary_MPR.jpg');19 I = imread('plane.png');20 %转化为双精度型21 %I = im2double(I);22 %若为彩色，转化为灰度23 i f(size(I,3)==3), I=rgb2gray(I); end24 f igure(1),imshow(I);25 %---------------------------26 %高斯滤波27 %---------------------------28 s igma=1;29 %创建特定形式的二维高斯滤波器H30 H = fspecial('gaussian',ceil(3*sigma), sigma);31 %对图像进行高斯滤波,返回和I等大小矩阵32 I gs = filter2(H,I,'same');33 %---------------------------34 %获取Snake的点坐标35 %---------------------------36 f igure(2),imshow(Igs);37 x=[];y=[];c=1;N=100; %定义取点个数c,上限N38 %获取User手动取点的坐标39 % [x,y]=getpts40 w hile c<N41 [xi,yi,button]=ginput(1);42 % 获取坐标向量43 x=[x xi];44 y=[y yi];45 hold on46 % text(xi,yi,'o','FontSize',10,'Color','red');47 plot(xi,yi,'ro');48 % 若为右击，则停止循环49 if(button==3), break; end50 c=c+1;51 e nd5253 %将第一个点复制到矩阵最后，构成Snake环54 x y = [x;y];55 c=c+1;56 x y(:,c)=xy(:,1);57 %样条曲线差值58 t=1:c;59 t s = 1:0.1:c;60 x ys = spline(t,xy,ts);61 x s = xys(1,:);62 y s = xys(2,:);63 %样条差值效果64 h old on65 t emp=plot(x(1),y(1),'ro',xs,ys,'b.');66 l egend(temp,'原点','插值点');2．Snake算法实现部分，代码如下：68 % =========================================================================69 % Snakes算法实现部分70 % =========================================================================71 N Iter =1000; % 迭代次数72 a lpha=0.2; beta=0.2; gamma = 1; kappa = 0.1;73 w l = 0; we=0.4; wt=0;74 [row col] = size(Igs);7576 %图像力-线函数77 E line = Igs;78 %图像力-边函数79 [gx,gy]=gradient(Igs);80 E edge = -1*sqrt((gx.*gx+gy.*gy));81 %图像力-终点函数82 %卷积是为了求解偏导数，而离散点的偏导即差分求解83 m1 = [-11];84 m2 = [-1;1];85 m3 = [1 -21];86 m4 = [1;-2;1];87 m5 = [1 -1;-11];88 c x = conv2(Igs,m1,'same');89 c y = conv2(Igs,m2,'same');90 c xx = conv2(Igs,m3,'same');91 c yy = conv2(Igs,m4,'same');92 c xy = conv2(Igs,m5,'same');9394 f or i = 1:row95 for j= 1:col96 Eterm(i,j) = (cyy(i,j)*cx(i,j)*cx(i,j) -2 *cxy(i,j)*cx(i,j)*cy(i,j) +cxx(i,j)*cy(i,j)*cy(i,j))/((1+cx(i,j)*cx(i,j) + cy(i,j)*cy(i,j))^1.5);97 end98 e nd99100 %figure(3),imshow(Eterm);101 %figure(4),imshow(abs(Eedge));102 %外部力 Eext = Eimage + Econ103 E ext = wl*Eline + we*Eedge + wt*Eterm;104 %计算梯度105 [fx,fy]=gradient(Eext);106107 x s=xs';108 y s=ys';109 [m n] = size(xs);110 [mm nn] = size(fx);111112 %计算五对角状矩阵113 %附录: 公式（14） b(i)表示vi系数(i=i-2 到 i+2)114 b(1)=beta;115 b(2)=-(alpha + 4*beta);116 b(3)=(2*alpha + 6 *beta);117 b(4)=b(2);118 b(5)=b(1);119120 A=b(1)*circshift(eye(m),2);121 A=A+b(2)*circshift(eye(m),1);122 A=A+b(3)*circshift(eye(m),0);123 A=A+b(4)*circshift(eye(m),-1);124 A=A+b(5)*circshift(eye(m),-2);125126 %计算矩阵的逆127 [L U] = lu(A + gamma.* eye(m));128 A inv = inv(U) * inv(L);3．画图部分，代码如下：130 % ========================================================================= 131 %画图部分132 % ========================================================================= 133 %text(10,10,'+','FontName','Time','FontSize',20,'Color','red');134 %迭代计算135 f igure(3)136 f or i=1:NIter;137 ssx = gamma*xs - kappa*interp2(fx,xs,ys);138 ssy = gamma*ys - kappa*interp2(fy,xs,ys);139140 % 计算snake的新位置141 xs = Ainv * ssx;142 ys = Ainv * ssy;143144 % 显示snake的新位置145 imshow(I);146 hold on;147 plot([xs; xs(1)], [ys; ys(1)], 'r-');148 hold off;149 pause(0.001)150 e nd实验步骤及结果1．读取待处理图像，若是彩色图像，必须转化为灰度，结果如图1。

图像分割之（五）活动轮廓模型之Snake模型简介在“图像分割之（一）概述”中咱们简单了解了目前主流的图像分割法。

下面咱们主要学习下基于能量泛函的分割法。

这里学习下Snake模型简单的知识，Level Set（水平集）模型会在后面的博文中说到。

基于能量泛函的分割法：该类法主要指的是活动轮廓模型（active contour model）以及在其基础上发展出来的算法，其基本思想是使用连续曲线来表达目标边缘，并定义一个能量泛函使得其自变量包括边缘曲线，因此分割过程就转变为求解能量泛函的最小值的过程，一般可通过求解函数对应的欧拉(Euler．Lagrange)程来实现，能量达到最小时的曲线位置就是目标的轮廓所在。

主动轮廓线模型是一个自顶向下定位图像特征的机制，用户或其他自动处理过程通过事先在感兴趣目标附近放置一个初始轮廓线，在部能量（力）和外部能量（外力）的作用下变形外部能量吸引活动轮廓朝物体边缘运动，而部能量保持活动轮廓的光滑性和拓扑性，当能量达到最小时，活动轮廓收敛到所要检测的物体边缘。

一、曲线演化理论曲线演化理论在水平集中运用到，但我感觉在主动轮廓线模型的分割法中，这个知识是公用的，所以这里我们简单了解下。

曲线可以简单的分为几种：曲线存在曲率，曲率有正有负，于是在法向曲率力的推动下，曲线的运动向之间有所不同：有些部分朝外扩展，而有些部分则朝运动。

这种情形如下图所示。

图中蓝色箭头处的曲率为负，而绿色箭头处的曲率为正。

简单曲线在曲率力（也就是曲线的二次导数）的驱动下演化所具有的一种非常特殊的数学性质是：一切简单曲线，无论被扭曲得多么重，只要还是一种简单曲线，那么在曲率力的推动下最终将退化成一个圆，然后消逝（可以想象下，圆的所有点的曲率力都向着圆心，所以它将慢慢缩小，以致最后消逝）。

描述曲线几特征的两个重要参数是单位法矢和曲率，单位法矢描述曲线的向，曲率则表述曲线弯曲的程度。

曲线演化理论就是仅利用曲线的单位法矢和曲率等几参数来研究曲线随时间的变形。

图像分割-传统方法所谓图像分割指的是根据灰度、颜色、纹理和形状等特征把图像划分成若干互不交迭的区域，并使这些特征在同一区域内呈现出相似性，而在不同区域间呈现出明显的差异性。

多数的图像分割算法均是基于灰度值的不连续和相似的性质。

1、基于阈值的分割方法阈值法的基本思想是基于图像的灰度特征来计算一个或多个灰度阈值，并将图像中每个像素的灰度值与阈值相比较，最后将像素根据比较结果分到合适的类别中。

因此，该类方法最为关键的一步就是按照某个准则函数来求解最佳灰度阈值。

固定阈值分割:固定某像素值为分割点。

直方图双峰法：Prewitt 等人于六十年代中期提出的直方图双峰法(也称 mode 法) 是典型的全局单阈值分割方法。

该方法的基本思想是：假设图像中有明显的目标和背景，则其灰度直方图呈双峰分布，当灰度级直方图具有双峰特性时，选取两峰之间的谷对应的灰度级作为阈值。

如果背景的灰度值在整个图像中可以合理地看作为恒定，而且所有物体与背景都具有几乎相同的对比度，那么，选择一个正确的、固定的全局阈值会有较好的效果.算法实现：找到第一个峰值和第二个峰值,再找到第一和第二个峰值之间的谷值，谷值就是那个阀值了。

迭代阈值图像分割:1．统计图像灰度直方图,求出图象的最大灰度值和最小灰度值，分别记为ZMAX和ZMIN，令初始阈值T0=(ZMAX+ZMIN)-2；2．根据阈值TK将图象分割为前景和背景，计算小于TO所有灰度的均值ZO，和大于TO的所有灰度的均值ZB。

3．求出新阈值TK+1=(ZO+ZB)-2；4．若TK==TK+1，则所得即为阈值；否则转2，迭代计算。

自适应阈值图像分割: 有时候物体和背景的对比度在图像中不是处处一样的，普通阈值分割难以起作用。

这时候可以根据图像的局部特征分别采用不同的阈值进行分割。

只要我们将图像分为几个区域，分别选择阈值，或动态地根据一定邻域范围选择每点处的阈值，从而进行图像分割。

大津法 OTSU （最大类间方差法）：日本学者大津在1979年提出的自适应阈值确定方法。