PhotoShop算法原理解析系列 - 风格化-搜索边缘。1

Adobe Photoshop，简称“PS”，是由Adobe Systems开发和发行的图像处理软件。Photoshop主要处理以像素所构成的数字图像。使用其众多的编修与绘图工具，可以有效地进行图片编辑工作。ps有很多功能，在图像、图形、文字、视频、出版等各方面都有涉及。

之所以不写系列文章一、系列文章二这样的标题，是因为我不知道我能坚持多久。我知道我对事情的表达能力和语言的丰富性方面的天赋不高。而一段代码需要我去用心的把他从基本原理--》初步实现--》优化速度等过程用文字的方式表述清楚，恐怕不是一件很容易的事情。

我所掌握的一些Photoshop中的算法,不能说百分之一百就是正确的，但是从执行的效果中，大的方向肯定是没有问题的。

目前，从别人的文章、开源的代码以及自己的思考中我掌握的PS的算法可能有近100个吧。如果时间容许、自身的耐心容许，我会将这些东西慢慢的整理开来，虽然在很多人看来，这些算法并不具有什么研究的价值了，毕竟人家都已经商业化了。说的也有道理，我姑且把他作为自我欣赏和自我满足的一种方式吧。

今天，我们讲讲查找边缘算法。可能我说了原理，很多人就不会看下去了，可有几人层仔细的研究过呢。

　　先贴个效果图吧：

PhotoShop算法原理解析系列 - 风格化---》查找边缘。

　　原理：常见的Sobel边缘算子的结果进行反色即可。

为了能吸引你继续看下去，我先给出我的代码的执行速度：针对3000*4000*3的数码图片，处理时间300ms。

何为Sobel，从百度抄几张图过来了并修改地址后：

PhotoShop算法原理解析系列 - 风格化---》查找边缘。

　　对上面两个式子不做过多解释，你只需要知道其中A为输入图像，把G作为A的输出图像就可以了，最后还要做一步： G=255-G，就是查找边缘算法。

查找边缘类算法都有个问题，对图像物理边缘处的像素如何处理，在平日的处理代码中，很多人就是忽略四个边缘的像素，作为专业的图像处理软件，这可是违反最基本的原则的。对边缘进行的单独的代码处理，又会给编码带来冗余和繁琐的问题。解决问题的最简单又高效的方式就是采用哨兵边界。

写多了特效类算法的都应该知道，除了那种对单个像素进行处理的算法不需要对原始图像做个备份（不一定去全局备份），那些需要领域信息的算法由于算法的前一步修改了一个像素，而算法的当前步需要未修改的像素值，因此，一般这种算法都会在开始前对原始图像做个克隆，在计算时，需要的领域信息从克隆的数据中读取。如果这个克隆的过程不是完完全全的克隆，而是扩展适当边界后再克隆，就有可能解决上述的边界处理问题。

　　比如对下面的一个图，19×14像素大小，我们的备份图为上下左右各扩展一个像素的大小，并用边缘的值填充，变为21*16大小：

PhotoShop算法原理解析系列 - 风格化---》查找边缘。

　　这样，在计算原图的3*3领域像素时，从扩展后的克隆图对应点取样，就不会出现不在图像范围内的问题了，编码中即可以少很多判断，可读性也加强了。

在计算速度方面，注意到上面的计算式G中有个开方运算，这是个耗时的过程，由于图像数据的特殊性，都必须是整数，可以采用查找表的方式优化速度，这就需要考虑表的建立。

针对本文的具体问题，我们分两步讨论，第一：针对根号下的所有可能情况建立查找表。看看GX和GY的计算公式，考虑下两者的平方和的最大值是多少，可能要考虑一会吧。第二：就是只建立0^2到255^2范围内的查找表，然后确保根号下的数字不大于255^2。为什么可以这样做，就是因为图像数据的最大值就是255，如果根号下的数字大于255^2，在求出开方值后，还是需要规整为255的。因此，本算法中应该取后者。

private void CmdFindEdgesArray_Click(object sender, EventArgs e)
{    int X, Y;    int Width, Height, Stride, StrideC, HeightC;    int Speed, SpeedOne, SpeedTwo, SpeedThree;    int BlueOne, BlueTwo, GreenOne, GreenTwo, RedOne, RedTwo;    int PowerRed, PowerGreen, PowerBlue;
    Bitmap Bmp = (Bitmap)Pic.Image;    if (Bmp.PixelFormat != PixelFormat.Format24bppRgb) throw new Exception("不支持的图像格式.");    byte[] SqrValue = new byte[65026];    for (Y = 0; Y < 65026; Y++) SqrValue[Y] = (byte)(255 - (int)Math.Sqrt(Y));      // 计算查找表，注意已经砸查找表里进行了反色
    Width = Bmp.Width; Height = Bmp.Height; Stride = (int)((Bmp.Width * 3 + 3) & 0XFFFFFFFC);
    StrideC = (Width + 2) * 3; HeightC = Height + 2;                                 // 宽度和高度都扩展2个像素

    byte[] ImageData = new byte[Stride * Height];                                    // 用于保存图像数据，（处理前后的都为他)
    byte[] ImageDataC = new byte[StrideC * HeightC];                                // 用于保存扩展后的图像数据

    fixed (byte* Scan0 = &ImageData[0])
    {
        BitmapData BmpData = new BitmapData();
        BmpData.Scan0 = (IntPtr)Scan0;                                              //  设置为字节数组的的第一个元素在内存中的地址
        BmpData.Stride = Stride;
        Bmp.LockBits(new Rectangle(0, 0, Bmp.Width, Bmp.Height), ImageLockMode.ReadWrite (专业提供视频软件下载)

     ImageLockMode.UserInputBuffer, PixelFormat.Format24bppRgb, BmpData);

        Stopwatch Sw = new Stopwatch();                                             //  只获取计算用时        Sw.Start();        for (Y = 0; Y < Height; Y++)
        {
            System.Buffer.BlockCopy(ImageData, Stride * Y, ImageDataC, StrideC * (Y + 1), 3);        // 填充扩展图的左侧第一列像素(不包括第一个和最后一个点)
            System.Buffer.BlockCopy(ImageData, Stride * Y + (Width - 1) * 3, ImageDataC, StrideC * (Y + 1) + (Width + 1) * 3, 3);  // 填充最右侧那一列的数据
            System.Buffer.BlockCopy(ImageData, Stride * Y, ImageDataC, StrideC * (Y + 1) + 3, Width * 3);
        }
        System.Buffer.BlockCopy(ImageDataC, StrideC, ImageDataC, 0, StrideC);              //  第一行
        System.Buffer.BlockCopy(ImageDataC, (HeightC - 2) * StrideC, ImageDataC, (HeightC - 1) * StrideC, StrideC);    //  最后一行               

        for (Y = 0; Y < Height; Y++)
        {
            Speed = Y * Stride;
            SpeedOne = StrideC * Y;            for (X = 0; X < Width; X++)
            {
                SpeedTwo = SpeedOne + StrideC;          //  尽量减少计算
                SpeedThree = SpeedTwo + StrideC;        //  下面的就是严格的按照Sobel算字进行计算，代码中的*2一般会优化为移位或者两个Add指令的，如果你不放心，当然可以直接改成移位
                BlueOne = ImageDataC[SpeedOne] + 2 * ImageDataC[SpeedTwo] + ImageDataC[SpeedThree] - ImageDataC[SpeedOne + 6] - 2 * ImageDataC[SpeedTwo + 6] - ImageDataC[SpeedThree + 6];
                GreenOne = ImageDataC[SpeedOne + 1] + 2 * ImageDataC[SpeedTwo + 1] + ImageDataC[SpeedThree + 1] - ImageDataC[SpeedOne + 7] - 2 * ImageDataC[SpeedTwo + 7] - ImageDataC[SpeedThree + 7];
                RedOne = ImageDataC[SpeedOne + 2] + 2 * ImageDataC[SpeedTwo + 2] + ImageDataC[SpeedThree + 2] - ImageDataC[SpeedOne + 8] - 2 * ImageDataC[SpeedTwo + 8] - ImageDataC[SpeedThree + 8];
                BlueTwo = ImageDataC[SpeedOne] + 2 * ImageDataC[SpeedOne + 3] + ImageDataC[SpeedOne + 6] - ImageDataC[SpeedThree] - 2 * ImageDataC[SpeedThree + 3] - ImageDataC[SpeedThree + 6];
                GreenTwo = ImageDataC[SpeedOne + 1] + 2 * ImageDataC[SpeedOne + 4] + ImageDataC[SpeedOne + 7] - ImageDataC[SpeedThree + 1] - 2 * ImageDataC[SpeedThree + 4] - ImageDataC[SpeedThree + 7];
                RedTwo = ImageDataC[SpeedOne + 2] + 2 * ImageDataC[SpeedOne + 5] + ImageDataC[SpeedOne + 8] - ImageDataC[SpeedThree + 2] - 2 * ImageDataC[SpeedThree + 5] - ImageDataC[SpeedThree + 8];

                PowerBlue = BlueOne * BlueOne + BlueTwo * BlueTwo;
                PowerGreen = GreenOne * GreenOne + GreenTwo * GreenTwo;
                PowerRed = RedOne * RedOne + RedTwo * RedTwo;                if (PowerBlue > 65025) PowerBlue = 65025;           //  处理掉溢出值
                if (PowerGreen > 65025) PowerGreen = 65025;                if (PowerRed > 65025) PowerRed = 65025;
                ImageData[Speed] = SqrValue[PowerBlue];             //  查表
                ImageData[Speed + 1] = SqrValue[PowerGreen];
                ImageData[Speed + 2] = SqrValue[PowerRed];

                Speed += 3;                                  // 跳往下一个像素
                SpeedOne += 3;
            }
        }
        Sw.Stop();        this.Text = "计算用时: " + Sw.ElapsedMilliseconds.ToString() + " ms";

        Bmp.UnlockBits(BmpData);                         //  必须先解锁，否则Invalidate失败     }
    Pic.Invalidate();
}

　　为简单的起见，这里先是用的C#的一维数组实现的，并且计时部分未考虑图像数据的获取和更新，因为真正的图像处理过程中图像数据肯定是已经获得的了。

针对上述代码，编译为Release模式后，执行编译后的EXE，对于3000*4000*3的彩色图像，耗时约480ms，如果你是在IDE的模式先运行，记得一定要在选项--》调试--》常规里不勾选在模块加载时取消JIT优化（仅限托管）一栏。

上述代码中的填充克隆图数据时并没有新建一副图，然后再填充其中的图像数据，而是直接填充一个数组，图像其实不就是一片连续内存加一点头信息吗，头信息已经有了，所以只要一片内存就够了。

克隆数据的填充采用了系统Buffer.BlockCopy函数，该函数类似于我们以前常用CopyMemory，速度非常快。

为进一步调高执行速度，我们首先来看看算法的关键耗时部位的代码，即for (X = 0; X < Width; X++)内部的代码，我们取一行代码的反编译码来看看：