Snake 算法

梦里梦外; 2022-04-16 01:11 179阅读 0赞

**分享一下我老师大神的人工智能教程！零基础，通俗易懂！[http://blog.csdn.net/jiangjunshow][http_blog.csdn.net_jiangjunshow]**

**也欢迎大家转载本篇文章。分享知识，造福人民，实现我们中华民族伟大复兴！**

Snake 算法或Active Contour Models。这类算法需要给出初始的轮廓，然后进行迭代，使轮廓沿能量降低的方向靠近，最后得到一个优化的边界。能量函数包括内外力两方面，如边界曲率和梯度。由于用户无法估计迭代的最后结果，应用Snake 算法往往需要进行多次的交互工作。特别当目标比较复杂时，或与其它物体靠得较近时，初始的轮廓不易确定，而迭代的结果往往不能达到要求。

/CODE:/

bool termination\_point  
bool neighbor3by3; /\* true means 3x3 neighborhood, false means 5x5 neighborhood \*/  
int grad\_mag\[500\]\[500\]; /\* Magnitude of Gradient \*/  
int m\_Cols; /\* Number of Columns \*/  
int m\_Rows; /\* Number of Rows \*/  
int no\_of\_snake\_points;  
CPoint Snake\_points\[200\]; /\* Snake Points \*/  
double \*alpha,\*beta, \*gamma; /\* Weights for energies \*/  
double threshold\_curvature;  
int threshold\_movement;  
  
void Snake\_algorithm()  
\{  
bool flag\_change;  
int movement,i,j,iteration=0;  
double avg\_distance=0.0, max\_curvature;  
CPoint temp;  
double \*curvature;  
alpha=new double\[no\_of\_snake\_points\];  
beta=new double\[no\_of\_snake\_points\];  
gamma=new double\[no\_of\_snake\_points\];  
curvature=new double\[no\_of\_snake\_points\];  
termination\_point=false;  
  
for(i=0;i<no\_of\_snake\_points;i++)  
\{  
\*(alpha+i)=1.0;  
\*(beta+i)=1.0;  
\*(gamma+i)=1.2;  
avg\_distance+=find\_distance(i, Snake\_points\[i\]);  
\}  
j=no\_of\_snake\_points;  
pdc=GetDC();  
while(!termination\_point)  
\{  
movement=0;  
avg\_distance=avg\_distance/(double)no\_of\_snake\_points;  
max\_curvature=-1000000000.0;  
for(i=0;i<no\_of\_snake\_points;i++)  
\{  
temp=find\_min\_energy(i, Snake\_points\[i\],avg\_distance);  
flag\_change=false;  
if(temp!=Snake\_points\[i\]&&temp!=Snake\_points\[(i-1+j)%j\]&&temp!=Snake\_points\[(i+1)%j\])  
\{  
Snake\_points\[i\]=temp;  
movement++;  
\}  
curvature\[i\]=find\_curvature(i, Snake\_points\[i\]);  
if(max\_curvature<curvature\[i\])  
max\_curvature=curvature\[i\];  
\}  
avg\_distance=0.0;  
for(i=0;i<no\_of\_snake\_points;i++)  
curvature\[i\]=curvature\[i\]/max\_curvature;  
for(i=0;i<no\_of\_snake\_points;i++)  
\{  
avg\_distance+=find\_distance(i, Snake\_points\[i\]);  
if(curvature\[i\]>threshold\_curvature&&curvature\[i\]>curvature\[(i+1)%no\_of\_snake\_points\]&&curvature\[i\]>curvature\[(i-1+no\_of\_snake\_points)%no\_of\_snake\_points\])  
\*(beta+i)=0;  
\}  
if(movement<threshold\_movement)  
termination\_point=true;  
iteration++;  
if(iteration>Max\_Iterations)  
termination\_point=true;  
\}  
delete alpha;  
delete beta;  
delete gamma;  
delete curvature;  
\}  
  
  
double find\_distance(int no, CPoint point)  
\{  
int x=no\_of\_snake\_points;  
point-=Snake\_points\[(no-1+x)%x\];  
return(sqrt(point.x\*point.x+point.y\*point.y));  
\}  
  
double find\_curvature(int no, CPoint point)  
\{  
int x=no\_of\_snake\_points;  
point=Snake\_points\[(no-1+x)%x\]-point-point+Snake\_points\[(no+1)%x\];  
return(point.x\*point.x+point.y\*point.y);  
\}  
  
double find\_continuity(int no, CPoint point, double avg\_distance)  
\{  
return(pow(avg\_distance-find\_distance(no,point),2));  
\}  
  
  
CPoint find\_min\_energy(int no, CPoint point, double avg\_distance)  
\{  
CPoint p, min\_point;  
double max\_curvature, max\_continuity, max\_internal, min\_internal, min\_energy, energy;  
double curvatures\[5\]\[5\];  
double continuities\[5\]\[5\];  
double internal\_energies\[5\]\[5\];  
int i,j, limit=1;  
max\_curvature=max\_continuity=max\_internal=-1000000000000.0;  
min\_internal=1000000000000.0;  
if(!neighbor3by3)  
limit++;  
for(i=-limit;i<=limit;i++)  
\{  
p.y=point.y+i;  
if(p.y<0)  
p.y=0;  
if(p.y>=m\_Rows)  
p.y=m\_Rows-1;  
for(j=-limit;j<=limit;j++)  
\{  
p.x=point.x+j;  
if(p.x<0)  
p.x=0;  
if(p.x>=m\_Cols)  
p.x=m\_Cols-1;  
curvatures\[i+limit\]\[j+limit\]=find\_curvature(no, p); //This code can cause problem near  
continuities\[i+limit\]\[j+limit\]=find\_continuity(no,p,avg\_distance); //border of image  
internal\_energies\[i+limit\]\[j+limit\]=(double)grad\_mag\[p.y\]\[p.x\];  
if(curvatures\[i+limit\]\[j+limit\]>max\_curvature)  
max\_curvature=curvatures\[i+limit\]\[j+limit\];  
if(continuities\[i+limit\]\[j+limit\]>max\_continuity)  
max\_continuity=continuities\[i+limit\]\[j+limit\];  
if(internal\_energies\[i+limit\]\[j+limit\]>max\_internal)  
max\_internal=internal\_energies\[i+limit\]\[j+limit\];  
if(internal\_energies\[i+limit\]\[j+limit\]<min\_internal)  
min\_internal=internal\_energies\[i+limit\]\[j+limit\];  
\}  
\}  
for(i=0;i<=2\*limit;i++)  
\{  
for(j=0;j<=2\*limit;j++)  
\{  
curvatures\[i\]\[j\]=curvatures\[i\]\[j\]/max\_curvature;  
continuities\[i\]\[j\]=continuities\[i\]\[j\]/max\_continuity;  
internal\_energies\[i\]\[j\]=(internal\_energies\[i\]\[j\]-min\_internal)/(max\_internal-min\_internal);  
\}  
\}  
min\_point.x=-limit;  
min\_point.y=-limit;  
min\_energy=1000000000000.0;  
for(i=-limit;i<=limit;i++)  
\{  
for(j=-limit;j<=limit;j++)  
\{  
energy=\*(alpha+no)\*continuities\[i+limit\]\[j+limit\]+\*(beta+no)\*curvatures\[i+limit\]\[j+limit\]-\*(gamma+no)\*internal\_energies\[i+limit\]\[j+limit\];  
if(energy<min\_energy||(energy==min\_energy&&i==0&&j==0))  
\{  
min\_energy=energy;  
min\_point.x=j;  
min\_point.y=i;  
\}  
\}  
\}  
min\_point.x=min\_point.x+point.x;  
min\_point.y=min\_point.y+point.y;  
return(min\_point);  
\}  
  
  
/

参考资料：\[1\] Williams. Donna and Shah. Mubarak. "A Fast Algorithm for Active Contours and Curvature Estimation", CVGIP: Image Understanding. Vol. 55, No. 1, January 1992. pp. 14-26.  
\[2\] M. Kass, A. Witkin, D. Terzopoulos. Snake: Active Contour Models. International Journal of Computer Vision. Vol.1, No.4, pp.321-331, 1988.

#### 给我老师的人工智能教程打call！[http://blog.csdn.net/jiangjunshow][http_blog.csdn.net_jiangjunshow] ####

![这里写图片描述][SouthEast]

[http_blog.csdn.net_jiangjunshow]: https://blog.csdn.net/jiangjunshow/article/details/77338485
[SouthEast]: /images/20220416/fa6d6cea493d474fbbed9093b7151754.png