计算机视觉
图像处理

图像处理(二)Seam Carving算法-Siggraph 2007

一、相关理论
Seam Carving 算法是2007年Siggraph上的一篇paper,名为《Seam Carving for Content-Aware Image Resizing》, 这篇paper提出了一种内容感知的图像缩放算法,继这篇paper的思想,后来近几年siggraph上面也有好几篇都是内容感知的图像缩放算法。内容 感知的图像缩放算法一般用于图像的裁剪,就是有的时候,你觉得一张照片有点大,你希望把它裁剪的小一些,但是你又想保留照片中的物体,这个时候就要用到内 容感知的突刺昂缩放算法了。
    
原图                                                                                                               裁剪结果
垂直方向裁剪
该 开始学习这个算法的时候,看起来好像很高深莫测的样子,理论看起来好像牛逼哄哄,什么能量,动态规划,都把我吓到了,最后理论的东西我实在是受不鸟了,于 是果断直接解读代码,看了代码以后,才知道这个算法其实非常简单,难度就比普通的图像缩放难那么一点点,其实算法的原理很简单。废话不多说,这边只介绍缩 小算法,且是图像宽度缩小的算法,对于图像高度缩小,只需对图像转置处理,总之paper中其它功能的实现,大同小异,整个过程说的简单一点就是通过寻找 一条线,如上面的图1所示,找到了线以后,把那条线上的像素点全部删除,从而实现缩小操作。

该过程是通过迭代实现的,每次只能移除一列,迭代直到宽度满足要求。下面介绍寻找移除能量线的方法,需要注意的是,每次移除一列,都要重新计算能量图,也就是说,梯度图要重新计算,才能进行下一轮的移除工作。

算法流程

1、算法第一步:计算图像能量图

能量图一般是图像像素的梯度模值,为了简化计算可先转换成灰度图像,然后直接采用如下公式(直接用x、y方向上的差分取绝对值,然后相加),其实这一步就是相当于边缘检测算法一样:

2、算法第二步:寻找最小能量线

最小能量线指的是需要被移除的那一列:首先需要以图像第一行或最后一行为开始行进行迭代。下面实现的为从图像最后一行开始,往上迭代,

//先找出图片最底部的一行中,能量最小的像素点作为起始点

  1. int min_x = 0;
  2. int width = (*Source).Width();
  3. int height = (*Source).Height();
  4. forint x = 0; x < width; x++ )
  5. {
  6.     if( (*Source)(x,height-1)->energy < (*Source)(min_x,height-1)->energy )
  7.     {
  8.         min_x = x;
  9.     }
  10. }

找出最后一行需要被移除的像素点后,设其坐标为P(x,y),然后往上一行寻找,寻找的点为P点的在y-1行中的三个相邻像素点中的能量最小值像素。也就是寻找的坐标为(x-1,y-1)、(x,y-1)、(x+1,y-1);

  1.  //min_x是图片最底部的一行的能量值最小的像素点 因此遍历的时候,要往上寻找
  2. void Generate_Path( CML_image_ptr * Energy, int min_x, int * Path )
  3. {
  4.     int min;
  5.     int x = min_x;//起始行的能量最小点
  6.     int height = (*Energy).Height();
  7. //从底部往上寻找最小能量线
  8.     forint y = height – 1; y >= 0; y– ) //从下往上
  9.     {
  10.         min = x; //首个顶点迭代更新
  11.         //计算上一行中  三个邻接像素中能量值最小的像素点 作为上一行的能量最小点
  12.         int Maxy=  Get_Max( Energy, min, y );
  13.         if( Get_Max( Energy, x-1, y ) < Maxy ) //
  14.         {
  15.             min = x – 1;
  16.         }
  17.         if( Get_Max( Energy, x+1, y ) < Maxy ) //up-right
  18.         {
  19.             min = x + 1;
  20.         }
  21.         Path[y] = min;
  22.         x = min;
  23.     }
  24. }

3、算法第三步:移除得到的最小能量线,让图片的宽度缩小一个像素

移除最小能量线,同时所有位于最小能量线右边的像素点左移一个单位,从而实现图像缩小宽度缩小一个单位。

移除的时 候 为了让图像看起来自然,需要在移除缝线的地方进行平均,假设移除坐标为P(x,y),那么移除后P(x-1,y)的像素值为P(x-1,y)与 P(x,y)的像素值的平均。P(x+1,y)的像素值为P(x-1,y)与P(x,y)的像素值的平均,然后才能把P(x+1,y)移动到P(x,y) 的位置。

  1. int height=(*Source).Height();
  2.     int width=(*Source).Width();
  3.     //移除函数
  4.     forint y =0; y < height; y++ )
  5.     {
  6.         int remove = (Path)[y];
  7.         (*(Source))(remove,y)->removed = true;
  8.         //移除的时候 为了让图像看起来自然,需要在移除缝线的地方进行平均,假设移除坐标为P(x,y),那么
  9.         //移除后P(x-1,y)的像素值为P(x-1,y)与P(x,y)的像素值的平均
  10.         //P(x+1,y)的像素值为P(x-1,y)与P(x,y)的像素值的平均,然后才能把P(x+1,y)移动到P(x,y)的位置
  11.         if( (remove – 1) > 0 )
  12.         {
  13.             if( (*(Source))(remove,y)->weight >= 0 )
  14.             {
  15.                 (*(Source))(remove-1,y)->image = Average_Pixels( (*(Source))(remove,y)->image,
  16.                     (*(Source)).Get(remove-1,y)->image );
  17.             }
  18.             (*(Source))(remove-1,y)->gray = Grayscale_Pixel( &(*(Source))(remove-1,y)->image );
  19.         }
  20.         if( (remove + 1) < (*(Source)).Width() )
  21.         {
  22.             if( (*(Source))(remove,y)->weight >= 0 )
  23.             {
  24.                 (*(Source))(remove+1,y)->image = Average_Pixels( (*(Source))(remove,y)->image,
  25.                     (*(Source)).Get(remove+1,y)->image );
  26.             }
  27.             (*(Source))(remove+1,y)->gray = Grayscale_Pixel( &(*(Source))(remove+1,y)->image );
  28.         }
  29.         (*(Source)).Shift_Row( remove + 1, y, -1 );
  30.     }

对于图像的放大算法原理一样,先找到最小能量线,设能量线上点的坐标为P(x,y),则在P(x,y)、P(x+1,y)中心位置插入新的像素,像素值为P(x,y)与P(x+1,y)的平均。

参考文献:《Seam Carving for Content-Aware Image Resizing》

转载注明来源:CV视觉网 » 图像处理(二)Seam Carving算法-Siggraph 2007

分享到:更多 ()
扫描二维码,给作者 打赏
pay_weixinpay_weixin

请选择你看完该文章的感受:

3不错 0超赞 0无聊 0扯淡 0不解 0路过

评论 3

评论前必须登录!