PhotoShop algorithm principle analysis series - stylization - finding edges.

The reason why I don’t write titles like Series 1 and Series 2 is because I don’t know how long I can persist. I know that I am not very gifted in terms of the ability to express things and the richness of language. And a piece of code requires me to carefully describe the process from basic principles - "preliminary implementation -" optimization speed and other processes in words, which is probably not an easy task.

I cannot say that some of the algorithms in Photoshop that I have mastered are 100% correct, but judging from the execution effect, there is definitely no problem in the general direction.

At present, I may know nearly 100 PS algorithms from other people’s articles, open source codes and my own thinking. If time allows and my own patience allows, I will slowly sort out these things. Although in the eyes of many people, these algorithms have no research value. After all, they have been commercialized. It makes sense, let me just use it as a way of self-appreciation and self-satisfaction.

Today, we talk about the edge search algorithm. Maybe after I explained the principle, many people wouldn't read it, but there are a few people who have studied it carefully.

Post a rendering first:

## Principle: The results of common Sobel edge operators can be inverted.

In order to attract you to continue reading, I will first give the execution speed of my code: For digital pictures of 3000*4000*3, processing time300ms.

What is Sobel? I copied a few pictures from Baidu and modified the address:

I won’t explain too much about the above two formulas. You only need to know that A is the input image and G is the output image of A. The last step is to do: G=255-G , which is the edge search algorithm.

There is a problem with edge-finding algorithms. How to deal with the pixels at the physical edge

of the image. In daily processing codes, many people just ignore the four Edge pixels, as a professional image processing software, violate the most basic principles. Separate code processing for edges will bring redundant and cumbersome problems to the encoding. The simplest and most efficient way to solve the problem is to use sentinel boundaries.

Those who have written many special effects algorithms should know that except for the algorithm that processes a single pixel, there is no need to make a backup of the original image (not necessarily a global backup), those Algorithms that require domain information modify a pixel in the previous step of the algorithm, and the current step of the algorithm requires an unmodified pixel value. Therefore, this algorithm generally clones the original image before starting. During calculation, it needs Domain information is read from the cloned data. If the cloning process is not a complete clone, but extends the appropriate boundary and then clones it, it is possible to solve the above boundary processing problem.

For example, for the picture below, which is 19×14 pixels in size, our backup picture is expanded by one pixel in the top, bottom, left and right, and is filled with edge values ​​to become 21*16 Size:

In this way, when calculating the 3*3 area pixels of the original image, sampling from the corresponding points of the expanded clone image will not cause the problem of not being within the image range, and there will be a lot less judgment in the encoding. Readability is also enhanced.

In terms of calculation speed, it is noted that there is a square root operation in the above calculation formula G. This is a time-consuming process. Due to the particularity of the image data, it must be an integer. You can optimize the speed by using a lookup table, which requires considering the establishment of the table.

For the specific issues of this article, we will discuss it in two steps. First: Create a lookup table for all possible situations under the root number. Take a look at the calculation formulas of GX and GY, and consider what the maximum value of the sum of squares of the two is. You may want to think about it for a while. Second: Just create a lookup table within the range of 0^2 to 255^2, and then ensure that the number under the root sign is not greater than 255^2. Why this can be done is because the maximum value of image data is 255. If the number under the root sign is greater than 255^2, it still needs to be adjusted to 255 after finding the square root value. Therefore, the latter should be chosen in this algorithm.

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  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();
}

For the sake of simplicity, this is first implemented using a one-dimensional array in C#, and the timing part does not consider the image data Obtain and update, because the image data must have been obtained during the real image processing process.

For the above code, after compiling to Release mode, execute the compiled EXE. For a 3000*4000*3 color image, it takes about 480ms. If you are in IDE mode Run it first, and remember to uncheck the Cancel JIT optimization (hosting only) column when the module is loaded in Options--"Debugging--"General.

When filling in the cloned image data in the above code, a new image is not created, and then the image data is filled in , but directly fills an array. Isn't the image actually just a piece of continuous memory plus a little bit of header information? The header information is already there, so just one piece of memory is enough.

The filling of clone data uses the system Buffer.BlockCopy function, which is similar to the CopyMemory we used to use and is very fast.

In order to further increase the execution speed, we first take a look at the code of the key time-consuming part of the algorithm, that is, the code inside for (X = 0; X

<span style="font-size: 13px;"> BlueOne = ImageDataC[SpeedOne] + <span style="color: #800080;">2</span> * ImageDataC[SpeedTwo] + ImageDataC[SpeedThree] - ImageDataC[SpeedOne + <span style="color: #800080;">6</span>] - <span style="color: #800080;">2</span> * ImageDataC[SpeedTwo + <span style="color: #800080;">6</span>] - ImageDataC[SpeedThree + <span style="color: #800080;">6</span><span style="color: #000000;">];<br><br></span><span style="color: #800080;">00000302</span><span style="color: #000000;">  cmp         ebx,edi 
</span><span style="color: #800080;">00000304</span><span style="color: #000000;">  jae         0000073C 　　　　　　　　　　　　//   数组是否越界？
0000030a  movzx       eax,</span><span style="color: #0000ff;">byte</span> ptr [esi+ebx+<span style="color: #800080;">8</span><span style="color: #000000;">] 　　　//　 将ImageDataC[SpeedOne]中的数据传送的eax寄存器
0000030f  mov         dword ptr [ebp</span>-<span style="color: #000000;">80h],eax 
</span><span style="color: #800080;">00000312</span>  mov         edx,dword ptr [ebp-<span style="color: #000000;">2Ch] 
</span><span style="color: #800080;">00000315</span><span style="color: #000000;">  cmp         edx,edi 
</span><span style="color: #800080;">00000317</span><span style="color: #000000;">  jae         0000073C 　　　　　　　　　　　//     数组是否越界？　　　　　　　　　　　
0000031d  movzx       edx,</span><span style="color: #0000ff;">byte</span> ptr [esi+edx+<span style="color: #800080;">8</span><span style="color: #000000;">] 　　// 　　将ImageDataC[SpeedTwo]中的数据传送到edx寄存器</span><span style="color: #800080;">00000322</span><span style="color: #000000;">  add         edx,edx 　　　　　　　　　　　　//    计算2*ImageDataC[SpeedTwo]　　　　</span><span style="color: #800080;">00000324</span><span style="color: #000000;">  add         eax,edx 　　　　　　　　　　　　//    计算ImageDataC[SpeedOne]+2*ImageDataC[SpeedTwo]，并保存在eax寄存器中　　　　　　　　　　　</span><span style="color: #800080;">00000326</span><span style="color: #000000;">  cmp         ecx,edi 
</span><span style="color: #800080;">00000328</span><span style="color: #000000;">  jae         0000073C 
0000032e  movzx       edx,</span><span style="color: #0000ff;">byte</span> ptr [esi+ecx+<span style="color: #800080;">8</span><span style="color: #000000;">] 　　//    将ImageDataC[SpeedThree]中的数据传送到edx寄存器</span><span style="color: #800080;">00000333</span>  mov         dword ptr [ebp+<span style="color: #000000;">FFFFFF78h],edx 
</span><span style="color: #800080;">00000339</span><span style="color: #000000;">  add         eax,edx 
0000033b  lea         edx,[ebx</span>+<span style="color: #800080;">6</span><span style="color: #000000;">] 
0000033e  cmp         edx,edi 
</span><span style="color: #800080;">00000340</span><span style="color: #000000;">  jae         0000073C 
</span><span style="color: #800080;">00000346</span>  movzx       edx,<span style="color: #0000ff;">byte</span> ptr [esi+edx+<span style="color: #800080;">8</span><span style="color: #000000;">] 
0000034b  mov         dword ptr [ebp</span>+<span style="color: #000000;">FFFFFF7Ch],edx 
</span><span style="color: #800080;">00000351</span><span style="color: #000000;">  sub         eax,edx 
</span><span style="color: #800080;">00000353</span>  mov         edx,dword ptr [ebp-<span style="color: #000000;">2Ch] 
</span><span style="color: #800080;">00000356</span>  add         edx,<span style="color: #800080;">6</span> <span style="color: #800080;">00000359</span><span style="color: #000000;">  cmp         edx,edi 
0000035b  jae         0000073C 
</span><span style="color: #800080;">00000361</span>  movzx       edx,<span style="color: #0000ff;">byte</span> ptr [esi+edx+<span style="color: #800080;">8</span><span style="color: #000000;">] 
</span><span style="color: #800080;">00000366</span><span style="color: #000000;">  add         edx,edx 
</span><span style="color: #800080;">00000368</span><span style="color: #000000;">  sub         eax,edx 
0000036a  lea         edx,[ecx</span>+<span style="color: #800080;">6</span><span style="color: #000000;">] 
0000036d  cmp         edx,edi 
0000036f  jae         0000073C 
</span><span style="color: #800080;">00000375</span>  movzx       edx,<span style="color: #0000ff;">byte</span> ptr [esi+edx+<span style="color: #800080;">8</span><span style="color: #000000;">] 
0000037a  mov         dword ptr [ebp</span>+<span style="color: #000000;">FFFFFF74h],edx 
</span><span style="color: #800080;">00000380</span><span style="color: #000000;">  sub         eax,edx 
</span><span style="color: #800080;">00000382</span>  mov         dword ptr [ebp-30h],eax </span>

I only commented a little on the above assembly code, the most important of which is 0000073c Label, we followed the cash back to call another function:

# This 0000073c call 685172a4

## 标 We see that we are getting each array element Before, a cmp and jae instruction must be executed. From the analysis, I think this is to do something similar to determine whether the subscript of the array is out of bounds. If we can ensure that our algorithm will not cross the boundary, this part of the code will be very useful, won't it delay me from doing my business?

To this end, I think it is necessary to directly use pointers in C# to implement the algorithm. C# has unsafe mode and pointers, so it is very convenient, and the expression of pointers can be expressed with *, You can also use [], for example, *(P+4) and P[4] have the same meaning. Then the above code can be modified into a pointer version with very few modifications.

private void CmdFindEdgesPointer_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  65025) PowerBlue = 65025;           //  处理掉溢出值
                    if (PowerGreen > 65025) PowerGreen = 65025;                    if (PowerRed > 65025) PowerRed = 65025;

                    DataP[Speed] = LutP[PowerBlue];                     //  查表
                    DataP[Speed + 1] = LutP[PowerGreen];
                    DataP[Speed + 2] = LutP[PowerRed];

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

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

## The same effect, the same image, the calculation takes 330ms.

Let’s take a look at the assembly code of the same code:

<span style="font-size: 13px;">BlueOne = DataCP[SpeedOne] + <span style="color: #800080;">2</span> * DataCP[SpeedTwo] + DataCP[SpeedThree] - DataCP[SpeedOne + <span style="color: #800080;">6</span>] - <span style="color: #800080;">2</span> * DataCP[SpeedTwo + <span style="color: #800080;">6</span>] - DataCP[SpeedThree + <span style="color: #800080;">6</span><span style="color: #000000;">];<br><br></span><span style="color: #800080;">00000318</span>  movzx       eax,<span style="color: #0000ff;">byte</span> ptr [esi+<span style="color: #000000;">edi] 
0000031c  mov         dword ptr [ebp</span>-<span style="color: #000000;">74h],eax 
0000031f  movzx       edx,</span><span style="color: #0000ff;">byte</span> ptr [esi+<span style="color: #000000;">ebx] 
</span><span style="color: #800080;">00000323</span><span style="color: #000000;">  add         edx,edx 
</span><span style="color: #800080;">00000325</span><span style="color: #000000;">  add         eax,edx 
</span><span style="color: #800080;">00000327</span>  movzx       edx,<span style="color: #0000ff;">byte</span> ptr [esi+<span style="color: #000000;">ecx] 
0000032b  mov         dword ptr [ebp</span>-<span style="color: #000000;">7Ch],edx 
0000032e  add         eax,edx 
</span><span style="color: #800080;">00000330</span>  movzx       edx,<span style="color: #0000ff;">byte</span> ptr [esi+edi+<span style="color: #800080;">6</span><span style="color: #000000;">] 
</span><span style="color: #800080;">00000335</span>  mov         dword ptr [ebp-<span style="color: #000000;">78h],edx 
</span><span style="color: #800080;">00000338</span><span style="color: #000000;">  sub         eax,edx 
0000033a  movzx       edx,</span><span style="color: #0000ff;">byte</span> ptr [esi+ebx+<span style="color: #800080;">6</span><span style="color: #000000;">] 
0000033f  add         edx,edx 
</span><span style="color: #800080;">00000341</span><span style="color: #000000;">  sub         eax,edx 
</span><span style="color: #800080;">00000343</span>  movzx       edx,<span style="color: #0000ff;">byte</span> ptr [esi+ecx+<span style="color: #800080;">6</span><span style="color: #000000;">] 
</span><span style="color: #800080;">00000348</span>  mov         dword ptr [ebp-<span style="color: #000000;">80h],edx 
0000034b  sub         eax,edx 
0000034d  mov         dword ptr [ebp</span>-30h],eax </span>

Produced The assembly code is concise, has clear meaning, and lacks many instructions in comparison. Of course it will be much faster.

Pay attention to this code:

  fixed (byte* P = &ImageData[0], CP = &ImageDataC[0], LP = &SqrValue[0])
        {            byte* DataP = P, DataCP = CP, LutP = LP;

If you replace it with:

  fixed (byte* DataP = &ImageData[0], DataCP = &ImageDataC[0], LutP = &SqrValue[0])
{

The speed of the code is actually slower than the pure array version. As for why, practice is king. I haven’t analyzed it. Anyway, I know this result. You can refer to an article by Tie Ge:

Chat.Net type of public is not public, fixed cannot be fixed

Of course this You can also further optimize small actions, such as movzx eax,byte ptr [esi+edi] In this sentence, esi is actually the base address of the array. If you write DataCP[SpeedOne] like this, you will have this base address + offset every time. In terms of calculation, if a pointer variable can be directly and dynamically controlled in real time so that it points directly to the requested position, one less addition will be needed. Although the optimization is not obvious, it can basically reach the 300ms time mentioned before in the question. The specific code can be found in the attachment.

Many people may not be interested in these things of mine, saying that throwing these things to the GPU is better than what you have now... I hope these friends will not attack them too much. Everyone has their own hobbies, I only like CPU.

More PhotoShop algorithm principle analysis series - Stylization - Find edges. For related articles, please pay attention to the PHP Chinese website!