如何扫描两个图像的差异？

Question

我正在尝试扫描 2 个图像（32bppArgb 格式），识别何时存在差异并将差异块的边界存储在矩形列表中。

假设这些是图像：

第二个：

我想获得不同的矩形边界（在我们的例子中是打开的目录 window）。

这是我所做的：

private unsafe List<Rectangle> CodeImage(Bitmap bmp, Bitmap bmp2)
{

    List<Rectangle> rec = new List<Rectangle>();
    bmData = bmp.LockBits(new System.Drawing.Rectangle(0, 0, 1920, 1080), System.Drawing.Imaging.ImageLockMode.ReadOnly, bmp.PixelFormat);
    bmData2 = bmp2.LockBits(new System.Drawing.Rectangle(0, 0, 1920, 1080), System.Drawing.Imaging.ImageLockMode.ReadOnly, bmp2.PixelFormat);

    IntPtr scan0 = bmData.Scan0;
    IntPtr scan02 = bmData2.Scan0;
    int stride = bmData.Stride;
    int stride2 = bmData2.Stride;
    int nWidth = bmp.Width;
    int nHeight = bmp.Height;
    int minX = int.MaxValue;;
    int minY = int.MaxValue;
    int maxX = 0;
    bool found = false;

    for (int y = 0; y < nHeight; y++) 
    {
        byte* p = (byte*)scan0.ToPointer();
        p += y * stride;
        byte* p2 = (byte*)scan02.ToPointer();
        p2 += y * stride2;
        for (int x = 0; x < nWidth; x++) 
        {

            if (p[0] != p2[0] || p[1] != p2[1] || p[2] != p2[2] || p[3] != p2[3]) //found differences-began to store positions.
            {
                found = true;
                if (x < minX)
                    minX = x;
                if (x > maxX)
                    maxX = x;
                if (y < minY)
                    minY = y;

            } 
            else 
            {

                if (found) 
                {

                    int height = getBlockHeight(stride, scan0, maxX, minY, scan02, stride2);
                    found = false;
                    Rectangle temp = new Rectangle(minX, minY, maxX - minX, height);
                    rec.Add(temp);
                    //x += minX;
                    y += height;
                    minX = int.MaxValue;
                    minY = int.MaxValue;
                    maxX = 0;
                }
            } 
            p += 4;
            p2 += 4;
        }
    }

    return rec;
}

public unsafe int getBlockHeight(int stride, IntPtr scan, int x, int y1, IntPtr scan02, int stride2) //a function to get  an existing block height.
{
    int height = 0;;
    for (int y = y1; y < 1080; y++) //only for example- in our case its 1080 height.
    {
        byte* p = (byte*)scan.ToPointer();
        p += (y * stride) + (x * 4); //set the pointer to a specific potential point. 
        byte* p2 = (byte*)scan02.ToPointer();
        p2 += (y * stride2) + (x * 4); //set the pointer to a specific potential point. 
        if (p[0] != p2[0] || p[1] != p2[1] || p[2] != p2[2] || p[3] != p2[3]) //still change on the height in the increasing **y** of the block.
            height++;
    }

    return height;
}

这实际上是我调用方法的方式：

Bitmap a = Image.FromFile(@"C:\Users\itapi\Desktop.png") as Bitmap;//generates a 32bppRgba bitmap;
Bitmap b = Image.FromFile(@"C:\Users\itapi\Desktop.png") as Bitmap;//

List<Rectangle> l1 = CodeImage(a, b);
int i = 0;
foreach (Rectangle rec in l1)
{
    i++;
    Bitmap tmp = b.Clone(rec, a.PixelFormat);
    tmp.Save(i.ToString() + ".png");
}

但我没有得到确切的矩形。我只得到了一半，有时甚至更糟。我认为代码的逻辑有问题。

@nico 的代码

private unsafe List<Rectangle> CodeImage(Bitmap bmp, Bitmap bmp2) 
{
    List<Rectangle> rec = new List<Rectangle>();
    var bmData1 = bmp.LockBits(new System.Drawing.Rectangle(0, 0, bmp.Width, bmp.Height), System.Drawing.Imaging.ImageLockMode.ReadOnly, bmp.PixelFormat);
    
    var bmData2 = bmp2.LockBits(new System.Drawing.Rectangle(0, 0, bmp.Width, bmp.Height), System.Drawing.Imaging.ImageLockMode.ReadOnly, bmp2.PixelFormat);

    int bytesPerPixel = 3;

    IntPtr scan01 = bmData1.Scan0;
    IntPtr scan02 = bmData2.Scan0;
    int stride1 = bmData1.Stride;
    int stride2 = bmData2.Stride;
    int nWidth = bmp.Width;
    int nHeight = bmp.Height;

    bool[] visited = new bool[nWidth * nHeight];

    byte* base1 = (byte*)scan01.ToPointer();
    byte* base2 = (byte*)scan02.ToPointer();

    for (int y = 0; y < nHeight; y += 5) 
    {
        byte* p1 = base1;
        byte* p2 = base2;

        for (int x = 0; x < nWidth; x += 5) 
        {
            if (!ArePixelsEqual(p1, p2, bytesPerPixel) && !(visited[x + nWidth * y])) 
            {
                // fill the different area
                int minX = x;
                int maxX = x;
                int minY = y;
                int maxY = y;

                var pt = new Point(x, y);

                Stack<Point> toBeProcessed = new Stack<Point> ();
                visited[x + nWidth * y] = true;
                toBeProcessed.Push(pt);
                
                while (toBeProcessed.Count > 0) 
                {
                    var process = toBeProcessed.Pop();
                    var ptr1 = (byte*)scan01.ToPointer() + process.Y * stride1 + process.X * bytesPerPixel;
                    var ptr2 = (byte*) scan02.ToPointer() + process.Y * stride2 + process.X * bytesPerPixel;
                    //Check pixel equality
                    if (ArePixelsEqual(ptr1, ptr2, bytesPerPixel))
                        continue;

                    //This pixel is different
                    //Update the rectangle
                    if (process.X < minX) minX = process.X;
                    if (process.X > maxX) maxX = process.X;
                    if (process.Y < minY) minY = process.Y;
                    if (process.Y > maxY) maxY = process.Y;

                    Point n;
                    int idx;
                    
                    //Put neighbors in stack
                    if (process.X - 1 >= 0) 
                    {
                        n = new Point(process.X - 1, process.Y);
                        idx = n.X + nWidth * n.Y;
                        if (!visited[idx]) 
                        {
                            visited[idx] = true;
                            toBeProcessed.Push(n);
                        }
                    }

                    if (process.X + 1 < nWidth) 
                    {
                        n = new Point(process.X + 1, process.Y);
                        idx = n.X + nWidth * n.Y;
                        if (!visited[idx]) 
                        {
                            visited[idx] = true;
                            toBeProcessed.Push(n);
                        }
                    }

                    if (process.Y - 1 >= 0) 
                    {
                        n = new Point(process.X, process.Y - 1);
                        idx = n.X + nWidth * n.Y;
                        if (!visited[idx]) 
                        {
                            visited[idx] = true;
                            toBeProcessed.Push(n);
                        }
                    }

                    if (process.Y + 1 < nHeight) 
                    {
                        n = new Point(process.X, process.Y + 1);
                        idx = n.X + nWidth * n.Y;
                        if (!visited[idx]) 
                        {
                            visited[idx] = true;
                            toBeProcessed.Push(n);
                        }
                    }
                }

                if (((maxX - minX + 1) > 5) & ((maxY - minY + 1) > 5))
                    rec.Add(new Rectangle(minX, minY, maxX - minX + 1, maxY - minY + 1));
            }

            p1 += 5 * bytesPerPixel;
            p2 += 5 * bytesPerPixel;
        }

        base1 += 5 * stride1;
        base2 += 5 * stride2;
    }

    bmp.UnlockBits(bmData1);
    bmp2.UnlockBits(bmData2);

    return rec;
    
}

Answer 1

我发现您的代码存在一些问题。如果我没理解错的话，你

找到两个图像之间不同的像素。
然后你继续从那里向右扫描，直到你找到两个图像再次相同的位置。
然后从最后一个 "different" 像素扫描到底部，直到找到两个图像再次相同的位置。
然后你存储那个矩形并从它下面的下一行开始

到目前为止我说得对吗？

这里有两个明显的问题：

如果两个矩形重叠 y-ranges，你就有麻烦了：你会发现第一个矩形很好，然后跳到底部 Y-coordinate，忽略左边或右边的所有像素你刚刚找到的矩形。
即使只有一个矩形，您也假设矩形边框上的每个像素都不同，并且所有其他像素是相同的。如果该假设不成立，您将过早停止搜索，并且只会找到矩形的一部分。

如果您的图像来自扫描仪或数码相机，或者它们包含有损压缩 (jpeg) 伪像，则第二个假设几乎肯定是错误的。为了说明这一点，这是我将每个相同的像素标记为您链接的两个 jpg 图像黑色和每个不同像素白色时得到的结果：

您看到的是不是一个矩形。相反，您要查找的矩形周围的很多像素是不同的：

那是因为 jpeg 压缩伪影。但即使您使用无损源图像，边界处的像素也可能不会形成完美的矩形，因为抗锯齿或因为背景恰好在该区域具有相似的颜色。

您可以尝试改进您的算法，但如果您查看该边界，您会发现所有种针对您所做的任何几何假设的丑陋反例。

实施此 "the right way" 可能会更好。含义：

要么实施擦除不同像素的 flood fill 算法（例如，通过将它们设置为相同或通过在单独的掩码中存储标志），然后递归检查 4 个相邻像素。
或实施 connected component labeling 算法，用一个临时整数标签标记每个不同的像素，使用巧妙的数据结构来跟踪连接了哪些临时标签。如果你只对一个边界框感兴趣，你甚至不必合并临时标签，只需合并相邻标记区域的边界框即可。

连通分量标记通常要快一些，但比洪水填充要正确一些。

最后一个建议：如果我是你，我会重新考虑你的 "no 3rd party libraries" 政策。即使您的最终产品不包含第 3 方库，如果您使用 well-documented、well-tested 库中的有用构建块，然后用您自己的代码将它们一一替换，开发速度可能会快很多. （谁知道呢，您甚至可能会找到一个具有合适许可证的开源库，它比您自己的代码快得多，以至于您最终会坚持使用它...）

ADD: 如果您想重新考虑您的 "no libraries" 立场：这是使用 AForge 的快速简单实现（它具有比 emgucv 更宽松的库）：

private static void ProcessImages()
{
    (* load images *)
    var img1 = AForge.Imaging.Image.FromFile(@"compare1.jpg");
    var img2 = AForge.Imaging.Image.FromFile(@"compare2.jpg");

    (* calculate absolute difference *)
    var difference = new AForge.Imaging.Filters.ThresholdedDifference(15)
        {OverlayImage = img1}
        .Apply(img2);

    (* create and initialize the blob counter *)
    var bc = new AForge.Imaging.BlobCounter();
    bc.FilterBlobs = true;
    bc.MinWidth = 5;
    bc.MinHeight = 5;

    (* find blobs *)
    bc.ProcessImage(difference);

    (* draw result *)
    BitmapData data = img2.LockBits(
       new Rectangle(0, 0, img2.Width, img2.Height),
          ImageLockMode.ReadWrite, img2.PixelFormat);

    foreach (var rc in bc.GetObjectsRectangles())
        AForge.Imaging.Drawing.FillRectangle(data, rc, Color.FromArgb(128,Color.Red));

    img2.UnlockBits(data);
    img2.Save(@"compareResult.jpg");
}

实际差异+blob检测部分（没有加载和结果显示）大约需要43ms，第二次运行（当然第一次需要更长的时间，由于JITting，缓存等）

结果（由于 jpeg 伪影，矩形较大）：

Answer 2

这是您的代码的基于填充的版本。它检查每个像素的差异。如果找到不同的像素，它会运行探索以找到整个不同的区域。

代码仅供参考。当然还有一些可以改进的地方。

unsafe bool ArePixelsEqual(byte* p1, byte* p2, int bytesPerPixel)
{
    for (int i = 0; i < bytesPerPixel; ++i)
        if (p1[i] != p2[i])
            return false;
    return true;
}

private static unsafe List<Rectangle> CodeImage(Bitmap bmp, Bitmap bmp2)
{
    if (bmp.PixelFormat != bmp2.PixelFormat || bmp.Width != bmp2.Width || bmp.Height != bmp2.Height)
        throw new ArgumentException();

    List<Rectangle> rec = new List<Rectangle>();
    var bmData1 = bmp.LockBits(new System.Drawing.Rectangle(0, 0, bmp.Width, bmp.Height), System.Drawing.Imaging.ImageLockMode.ReadOnly, bmp.PixelFormat);
    var bmData2 = bmp2.LockBits(new System.Drawing.Rectangle(0, 0, bmp.Width, bmp.Height), System.Drawing.Imaging.ImageLockMode.ReadOnly, bmp2.PixelFormat);

    int bytesPerPixel = Image.GetPixelFormatSize(bmp.PixelFormat) / 8;        

    IntPtr scan01 = bmData1.Scan0;
    IntPtr scan02 = bmData2.Scan0;
    int stride1 = bmData1.Stride;
    int stride2 = bmData2.Stride;
    int nWidth = bmp.Width;
    int nHeight = bmp.Height;

    bool[] visited = new bool[nWidth * nHeight];

    byte* base1 = (byte*)scan01.ToPointer();
    byte* base2 = (byte*)scan02.ToPointer();

        for (int y = 0; y < nHeight; y++)
        {
            byte* p1 = base1;
            byte* p2 = base2;

            for (int x = 0; x < nWidth; ++x)
            {
                if (!ArePixelsEqual(p1, p2, bytesPerPixel) && !(visited[x + nWidth * y]))
                {
                    // fill the different area
                    int minX = x;
                    int maxX = x;
                    int minY = y;
                    int maxY = y;

                    var pt = new Point(x, y);

                    Stack<Point> toBeProcessed = new Stack<Point>();
                    visited[x + nWidth * y] = true;
                    toBeProcessed.Push(pt);
                    while (toBeProcessed.Count > 0)
                    {
                        var process = toBeProcessed.Pop();
                        var ptr1 = (byte*)scan01.ToPointer() + process.Y * stride1 + process.X * bytesPerPixel;
                        var ptr2 = (byte*)scan02.ToPointer() + process.Y * stride2 + process.X * bytesPerPixel;
                        //Check pixel equality
                        if (ArePixelsEqual(ptr1, ptr2, bytesPerPixel))
                            continue;

                        //This pixel is different
                        //Update the rectangle
                        if (process.X < minX) minX = process.X;
                        if (process.X > maxX) maxX = process.X;
                        if (process.Y < minY) minY = process.Y;
                        if (process.Y > maxY) maxY = process.Y;

                        Point n; int idx;
                        //Put neighbors in stack
                        if (process.X - 1 >= 0)
                        {
                            n = new Point(process.X - 1, process.Y); idx = n.X + nWidth * n.Y;
                            if (!visited[idx]) { visited[idx] = true; toBeProcessed.Push(n); }
                        }

                        if (process.X + 1 < nWidth)
                        {
                            n = new Point(process.X + 1, process.Y); idx = n.X + nWidth * n.Y;
                            if (!visited[idx]) { visited[idx] = true; toBeProcessed.Push(n); }
                        }

                        if (process.Y - 1 >= 0)
                        {
                            n = new Point(process.X, process.Y - 1); idx = n.X + nWidth * n.Y;
                            if (!visited[idx]) { visited[idx] = true; toBeProcessed.Push(n); }
                        }

                        if (process.Y + 1 < nHeight)
                        {
                            n = new Point(process.X, process.Y + 1); idx = n.X + nWidth * n.Y;
                            if (!visited[idx]) { visited[idx] = true; toBeProcessed.Push(n); }
                        }
                    }

                    rec.Add(new Rectangle(minX, minY, maxX - minX + 1, maxY - minY + 1));
                }

                p1 += bytesPerPixel;
                p2 += bytesPerPixel;
            }

            base1 += stride1;
            base2 += stride2;
        }


    bmp.UnlockBits(bmData1);
    bmp2.UnlockBits(bmData2);

    return rec;
}

Answer 3

您可以使用洪水填充分割算法轻松实现此目的。

首先是一个实用程序 class，可以更轻松地快速访问位图。这将有助于封装复杂的指针逻辑并使代码更具可读性：

class BitmapWithAccess
{
    public Bitmap Bitmap { get; private set; }
    public System.Drawing.Imaging.BitmapData BitmapData { get; private set; }

    public BitmapWithAccess(Bitmap bitmap, System.Drawing.Imaging.ImageLockMode lockMode)
    {
        Bitmap = bitmap;
        BitmapData = bitmap.LockBits(new Rectangle(Point.Empty, bitmap.Size), lockMode, System.Drawing.Imaging.PixelFormat.Format32bppArgb);
    }

    public Color GetPixel(int x, int y)
    {
        unsafe
        {
            byte* dataPointer = MovePointer((byte*)BitmapData.Scan0, x, y);

            return Color.FromArgb(dataPointer[3], dataPointer[2], dataPointer[1], dataPointer[0]);
        }
    }

    public void SetPixel(int x, int y, Color color)
    {
        unsafe
        {
            byte* dataPointer = MovePointer((byte*)BitmapData.Scan0, x, y);

            dataPointer[3] = color.A;
            dataPointer[2] = color.R;
            dataPointer[1] = color.G;
            dataPointer[0] = color.B;
        }
    }

    public void Release()
    {
        Bitmap.UnlockBits(BitmapData);
        BitmapData = null;
    }

    private unsafe byte* MovePointer(byte* pointer, int x, int y)
    {
        return pointer + x * 4 + y * BitmapData.Stride;
    }
}

然后 class 表示包含不同像素的矩形，以在生成的图像中标记它们。通常，此 class 还可以包含 Point 个实例列表（或 byte[,] 映射），以便在生成的图像中指示单个像素成为可能：

class Segment
{
    public int Left { get; set; }
    public int Top { get; set; }
    public int Right { get; set; }
    public int Bottom { get; set; }
    public Bitmap Bitmap { get; set; }

    public Segment()
    {
        Left = int.MaxValue;
        Right = int.MinValue;
        Top = int.MaxValue;
        Bottom = int.MinValue;
    }
};

那么一个简单的算法步骤如下：

找到不同的像素
使用洪水填充算法在差异图像上找到片段
为找到的线段绘制边界矩形

第一步最简单：

static Bitmap FindDifferentPixels(Bitmap i1, Bitmap i2)
{
    var result = new Bitmap(i1.Width, i2.Height, System.Drawing.Imaging.PixelFormat.Format32bppArgb);
    var ia1 = new BitmapWithAccess(i1, System.Drawing.Imaging.ImageLockMode.ReadOnly);
    var ia2 = new BitmapWithAccess(i2, System.Drawing.Imaging.ImageLockMode.ReadOnly);
    var ra = new BitmapWithAccess(result, System.Drawing.Imaging.ImageLockMode.ReadWrite);

    for (int x = 0; x < i1.Width; ++x)
        for (int y = 0; y < i1.Height; ++y)
        {
            var different = ia1.GetPixel(x, y) != ia2.GetPixel(x, y);

            ra.SetPixel(x, y, different ? Color.White : Color.FromArgb(0, 0, 0, 0));
        }

    ia1.Release();
    ia2.Release();
    ra.Release();

    return result;
}

而第二步和第三步覆盖了以下三个函数：

static List<Segment> Segmentize(Bitmap blackAndWhite)
{
    var bawa = new BitmapWithAccess(blackAndWhite, System.Drawing.Imaging.ImageLockMode.ReadOnly);
    var result = new List<Segment>();

    HashSet<Point> queue = new HashSet<Point>();
    bool[,] visitedPoints = new bool[blackAndWhite.Width, blackAndWhite.Height];

    for (int x = 0;x < blackAndWhite.Width;++x)
        for (int y = 0;y < blackAndWhite.Height;++y)
        {
            if (bawa.GetPixel(x, y).A != 0
                && !visitedPoints[x, y])
            {
                result.Add(BuildSegment(new Point(x, y), bawa, visitedPoints));
            }
        }

    bawa.Release();

    return result;
}

static Segment BuildSegment(Point startingPoint, BitmapWithAccess bawa, bool[,] visitedPoints)
{
    var result = new Segment();

    List<Point> toProcess = new List<Point>();

    toProcess.Add(startingPoint);

    while (toProcess.Count > 0)
    {
        Point p = toProcess.First();
        toProcess.RemoveAt(0);

        ProcessPoint(result, p, bawa, toProcess, visitedPoints);
    }

    return result;
}

static void ProcessPoint(Segment segment, Point point, BitmapWithAccess bawa, List<Point> toProcess, bool[,] visitedPoints)
{
    for (int i = -1; i <= 1; ++i)
    {
        for (int j = -1; j <= 1; ++j)
        {
            int x = point.X + i;
            int y = point.Y + j;

            if (x < 0 || y < 0 || x >= bawa.Bitmap.Width || y >= bawa.Bitmap.Height)
                continue;

            if (bawa.GetPixel(x, y).A != 0 && !visitedPoints[x, y])
            {
                segment.Left = Math.Min(segment.Left, x);
                segment.Right = Math.Max(segment.Right, x);
                segment.Top = Math.Min(segment.Top, y);
                segment.Bottom = Math.Max(segment.Bottom, y);

                toProcess.Add(new Point(x, y));
                visitedPoints[x, y] = true;
            }
        }
    }
}

下面的程序将你的两张图片作为参数：

static void Main(string[] args)
{
    Image ai1 = Image.FromFile(args[0]);
    Image ai2 = Image.FromFile(args[1]);

    Bitmap i1 = new Bitmap(ai1.Width, ai1.Height, System.Drawing.Imaging.PixelFormat.Format32bppArgb);
    Bitmap i2 = new Bitmap(ai2.Width, ai2.Height, System.Drawing.Imaging.PixelFormat.Format32bppArgb);

    using (var g1 = Graphics.FromImage(i1))
    using (var g2 = Graphics.FromImage(i2))
    {
        g1.DrawImage(ai1, Point.Empty);
        g2.DrawImage(ai2, Point.Empty);
    }

    var difference = FindDifferentPixels(i1, i2);
    var segments = Segmentize(difference);

    using (var g1 = Graphics.FromImage(i1))
    {
        foreach (var segment in segments)
        {
            g1.DrawRectangle(Pens.Red, new Rectangle(segment.Left, segment.Top, segment.Right - segment.Left, segment.Bottom - segment.Top));
        }
    }

    i1.Save("result.png");

    Console.WriteLine("Done.");
    Console.ReadKey();
}

产生以下结果：

如您所见，给定图像之间存在更多差异。您可以根据大小过滤生成的片段，例如删除小的人工制品。在错误检查、设计和性能方面当然还有很多工作要做。

一个想法是按如下方式进行：

1) 将图像重新缩放到更小的尺寸（下采样）

2) 运行上面的小图片算法

3) 运行在原始图像上使用上述算法，但仅限于在步骤 2) 中找到的矩形

这当然可以扩展到多级分层方法（使用更多不同的图像尺寸，每一步都提高准确性）。

Answer 4

啊算法挑战。像！ :-)

这里还有其他使用 f.ex 的答案。 floodfill 可以正常工作。我只是注意到你想要快速的东西，所以让我提出一个不同的想法。与其他人不同，我还没有测试过；它不应该太难而且应该很快，但我现在根本没有时间自己测试。如果你这样做，请分享结果。另外，请注意，它不是标准算法，因此在我的解释中可能存在一些错误（并且没有专利）。

我的想法源自均值自适应阈值化的想法，但有很多重要差异。我再也无法从维基百科或我的代码中找到 link，所以我会从头开始做这件事。基本上你为两个图像创建一个新的（64 位）缓冲区并填充它：

f(x,y) = colorvalue + f(x-1, y) + f(x, y-1) - f(x-1, y-1)
f(x,0) = colorvalue + f(x-1, 0)
f(0,y) = colorvalue + f(0, y-1)

主要技巧是你可以快速计算图像的一部分的总和值，即：

g(x1,y1,x2,y2) = f(x2,y2)-f(x1-1,y2)-f(x2,y1-1)+f(x1-1,y1-1)

换句话说，这将给出与以下相同的结果：

result = 0;
for (x=x1; x<=x2; ++x) 
  for (y=y1; y<=y2; ++y)    
    result += f(x,y)

在我们的例子中，这意味着只有 4 个整数运算，这将为您提供相关块的一些唯一编号。我会说那太棒了。

现在，在我们的例子中，我们并不真正关心平均值；我们只关心某种独特的数字。如果图像改变，它应该改变——就这么简单。至于颜色值，通常使用一些灰度值来进行阈值处理——相反，我们将使用完整的 24 位 RGB 值。因为只有很少的比较，所以我们可以简单地扫描直到找到不匹配的块。

我提出的基本算法工作原理如下：

for (y=0; y<height;++y)
    for (x=0; x<width; ++x)
       if (src[x,y] != dst[x,y])
          if (!IntersectsWith(x, y, foundBlocks))
              FindBlock(foundBlocks);

现在，IntersectsWith 可以类似于四叉树，如果只有几个块，您可以简单地遍历块并检查它们是否在块的边界内。您还可以相应地更新 x 变量（我愿意）。如果块太多，您甚至可以通过为 f(x,y) 重建缓冲区来平衡事情（更准确地说：将找到的块从 dst 合并回 src，然后重建缓冲区）。

FindBlocks 是它变得有趣的地方。使用 g 的公式现在非常简单：

int x1 = x-1; int y1 = y-1; int x2 = x; int y2 = y; 
while (changes)
{
    while (g(srcimage,x1-1,y1,x1,y2) == g(dstimage,x1-1,y1,x1,y2)) { --x1; }
    while (g(srcimage,x1,y1-1,x1,y2) == g(dstimage,x1,y1-1,x1,y2)) { --y1; }
    while (g(srcimage,x1,y1,x1+1,y2) == g(dstimage,x1,y1,x1+1,y2)) { ++x1; }
    while (g(srcimage,x1,y1,x1,y2+1) == g(dstimage,x1,y1,x1,y2+1)) { ++y1; }
}

就是这样。请注意，FindBlocks 算法的复杂度为 O(x + y)，这对于查找 2D 块 IMO 来说非常棒。 :-)

正如我所说，让我知道结果如何。

如何扫描两个图像的差异？

How to scan two images for differences?

c#

screenshot

image-processing