图像处理（二）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、算法第二步：寻找最小能量线

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

 

[c++] view plaincopy

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

int min_x = 0;  

int width = (*Source).Width();  

int height = (*Source).Height();  

for( int x = 0; x < width; x++ )  

{  

    if( (*Source)(x,height-1)->energy < (*Source)(min_x,height-1)->energy )  

    {  

        min_x = x;  

    }  

}  

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

 

[c++] view plaincopy

 //min_x是图片最底部的一行的能量值最小的像素点 因此遍历的时候，要往上寻找  

void Generate_Path( CML_image_ptr * Energy, int min_x, int * Path )  

{  

    int min;  

    int x = min_x;//起始行的能量最小点  

    int height = (*Energy).Height();  

//从底部往上寻找最小能量线  

    for( int y = height - 1; y >= 0; y-- ) //从下往上  

    {  

        min = x; //首个顶点迭代更新  

        //计算上一行中  三个邻接像素中能量值最小的像素点 作为上一行的能量最小点  

        int Maxy=  Get_Max( Energy, min, y );  

        if( Get_Max( Energy, x-1, y ) < Maxy ) //  

        {  

            min = x - 1;  

        }  

        if( Get_Max( Energy, x+1, y ) < Maxy ) //up-right  

        {  

            min = x + 1;  

        }  

        Path[y] = min;  

        x = min;  

    }  

}  

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)的位置。

 

[c++] view plaincopy

int height=(*Source).Height();  

    int width=(*Source).Width();  

    //移除函数  

    for( int y =0; y < height; y++ )  

    {  

        int remove = (Path)[y];  

        (*(Source))(remove,y)->removed = true;  

        //移除的时候 为了让图像看起来自然，需要在移除缝线的地方进行平均，假设移除坐标为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)的位置  

        if( (remove - 1) > 0 )  

        {  

            if( (*(Source))(remove,y)->weight >= 0 )  

            {  

                (*(Source))(remove-1,y)->image = Average_Pixels( (*(Source))(remove,y)->image,  

                    (*(Source)).Get(remove-1,y)->image );  

            }  

            (*(Source))(remove-1,y)->gray = Grayscale_Pixel( &(*(Source))(remove-1,y)->image );  

        }  

  

        if( (remove + 1) < (*(Source)).Width() )  

        {  

            if( (*(Source))(remove,y)->weight >= 0 )   

            {  

                (*(Source))(remove+1,y)->image = Average_Pixels( (*(Source))(remove,y)->image,  

                    (*(Source)).Get(remove+1,y)->image );  

            }  

            (*(Source))(remove+1,y)->gray = Grayscale_Pixel( &(*(Source))(remove+1,y)->image );  

        }  

        (*(Source)).Shift_Row( remove + 1, y, -1 );  

    }  

 对于图像的放大算法原理一样，先找到最小能量线，设能量线上点的坐标为P(x,y),则在P(x,y)、P(x+1,y)中心位置插入新的像素，像素值为P(x,y)与P(x+1,y)的平均。本文地址：http://blog.csdn.net/hjimce/article/details/44916869    作者：hjimce     联系qq：1393852684              更多资源请关注我的博客：http://blog.csdn.net/hjimce                 原创文章，版权所有，转载请保留这几行信息

总结

以上是生活随笔为你收集整理的图像处理（二）Seam Carving算法-Siggraph 2007的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。