Подтвердить что ты не робот

Как сканировать два изображения для различий?

Я пытаюсь отсканировать 2 изображения (формат 32bppArgb), определить, когда есть разница, и сохранить границы разностного блока в списке прямоугольников.

Предположим, что это изображения: введите описание изображения здесь

второй: введите описание изображения здесь

Я хочу получить различные границы прямоугольника (открытое окно каталога в нашем случае).

Это то, что я сделал:

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\1.png") as Bitmap;//generates a 32bppRgba bitmap;
        Bitmap b = Image.FromFile(@"C:\Users\itapi\Desktop\2.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;
    }
4b9b3361

Ответ 1

Я вижу пару проблем с вашим кодом. Если я правильно понимаю, вы

  • найдите пиксель, который отличается от двух изображений.
  • то вы продолжаете сканировать оттуда вправо, пока не найдете позицию, в которой оба изображения идентичны.
  • тогда вы сканируете с последнего "другого" пикселя на дно, пока не найдете положение, в котором оба изображения снова идентичны.
  • тогда вы сохраняете этот прямоугольник и начинаете со следующей строки ниже.

введите описание изображения здесь

До сих пор я прав?

Здесь очевидны две очевидные вещи:

  • Если два прямоугольника имеют перекрывающиеся у-диапазоны, у вас проблемы: вы найдете первый прямоугольник в порядке, затем пропустите нижнюю Y-координату, игнорируя все пиксели слева или справа от найденного прямоугольника.
  • Даже если есть только один прямоугольник, вы предполагаете, что каждый пиксель на границе прямоугольника отличается, а все остальные пиксели идентичны. Если это предположение неверно, вы перестанете искать слишком рано и найдете только части прямоугольников.

Если ваши изображения поступают со сканера или цифровой камеры или содержат артефакты с потерями сжатия (jpeg), второе предположение будет почти наверняка ошибочным. Чтобы проиллюстрировать это, вот что я получаю, когда я отмечаю каждый одинаковый пиксель двумя jpg-изображениями, которые вы связали черным, и каждый белый пиксель белого:

введите описание изображения здесь

То, что вы видите, не является прямоугольником. Вместо этого много пикселей вокруг прямоугольников, которые вы ищете, различны:

введите описание изображения здесь

Это из-за артефактов сжатия jpeg. Но даже если вы использовали исходные изображения без потерь, пиксели на границах могли бы не образовывать идеальные прямоугольники из-за сглаживания или потому, что фон просто имеет одинаковый цвет в этой области.

Вы можете попытаться улучшить свой алгоритм, но если вы посмотрите на эту границу, вы найдете все виды уродливых контрпримеров для любых геометрических допущений, которые вы сделаете.

Возможно, было бы лучше реализовать этот "правильный путь". Значение:

  • Либо реализуйте алгоритм fill fill, который стирает разные пиксели (например, устанавливая их одинаковыми или сохраняя флаг в отдельной маске), затем рекурсивно проверяет, есть ли 4 соседних пикселя.
  • Или внедрите алгоритм связанного компонента с меткой, который маркирует каждый отдельный пиксель временной меткой целого, используя умные структуры данных, чтобы отслеживать, временные метки подключены. Если вас интересует ограничивающая рамка, вам даже не нужно объединять временные метки, просто объедините ограничивающие поля соседних помеченных областей.

Маркировка подключенных компонентов в общем случае немного быстрее, но немного сложнее получить права, чем заливка заливки.

Последний совет: я бы переосмыслил вашу политику "нет сторонних библиотек", если бы я был вами. Даже если ваш конечный продукт не будет содержать сторонних библиотек, разработка может быть намного быстрее, если вы использовали хорошо документированные, хорошо проверенные, полезные строительные блоки из библиотеки, а затем заменили их один за другим своим собственным кодом. (И кто знает, вы даже можете найти библиотеку с открытым исходным кодом с подходящей лицензией, которая намного быстрее, чем ваш собственный код, который вы будете придерживаться в конце...)


ДОБАВИТЬ: Если вы хотите переосмыслить свою позицию "без библиотек": вот быстрая и простая реализация с использованием 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 (без загрузки и отображения результатов) занимает около 43 мс, для второго запуска (это первое время занимает больше времени, конечно, из-за JITting, кеша и т.д.)

Результат (прямоугольник больше из-за артефактов jpeg):

введите описание изображения здесь

Ответ 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;
}

Ответ 3

Вы можете легко достичь этого, используя алгоритм сегментации заливки на потоке.

Сначала класс утилиты упрощает быстрый доступ к растровому изображению. Это поможет инкапсулировать сложную логику указателя и сделать код более читаемым:

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

Затем класс, представляющий прямоугольник, содержащий разные пиксели, чтобы пометить их в полученном изображении. В общем, этот класс также может содержать список экземпляров 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)

Это может быть, конечно, распространено на многоуровневый иерархический подход (с использованием более разных размеров изображения, повышая точность с каждым шагом).

Ответ 4

Ах проблема алгоритма. Подобно!: -)

Здесь есть другие ответы с использованием f.ex. наводнение, которое будет работать нормально. Я только заметил, что вам нужно что-то быстро, поэтому позвольте мне предложить другую идею. В отличие от других людей, я не проверял его; это не должно быть слишком сложно и должно быть довольно быстрым, но у меня просто нет времени на то, чтобы проверить его сам. Если да, пожалуйста, поделитесь результатами. Также обратите внимание, что это не стандартный алгоритм, поэтому в моем объяснении (и отсутствии патентов), вероятно, есть некоторые ошибки.

Моя идея основана на идее среднего адаптивного порога, но с большим количеством важных отличий. Я больше не могу найти ссылку из википедии или мой код, поэтому я сделаю это из головы. В основном вы создаете новый (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.: -)

Как я уже сказал, дайте мне знать, как это получается.