Как я могу быстрее всего сравнить два растровых изображения одинакового размера, чтобы определить, идентичны ли они?

Отредактируйте 8-31-12: согласно приведенному ниже комментарию Джои, помните о формате сравниваемых растровых изображений. Они могут содержать отступы на шагах, которые делают растровые изображения неравными, несмотря на то, что они эквивалентны по пикселям. Дополнительные сведения см. В этом вопросе.

Чтение этого ответа на вопрос о сравнении байтовых массивов дало НАМНОГО БЫСТРЕЕ метод: использование P / Invoke и вызова API memcmp в msvcrt. Вот код:

[DllImport("msvcrt.dll")]
private static extern int memcmp(IntPtr b1, IntPtr b2, long count);

public static bool CompareMemCmp(Bitmap b1, Bitmap b2)
{
    if ((b1 == null) != (b2 == null)) return false;
    if (b1.Size != b2.Size) return false;

    var bd1 = b1.LockBits(new Rectangle(new Point(0, 0), b1.Size), ImageLockMode.ReadOnly, PixelFormat.Format32bppArgb);
    var bd2 = b2.LockBits(new Rectangle(new Point(0, 0), b2.Size), ImageLockMode.ReadOnly, PixelFormat.Format32bppArgb);

    try
    {
        IntPtr bd1scan0 = bd1.Scan0;
        IntPtr bd2scan0 = bd2.Scan0;

        int stride = bd1.Stride;
        int len = stride * b1.Height;

        return memcmp(bd1scan0, bd2scan0, len) == 0;
    }
    finally
    {
        b1.UnlockBits(bd1);
        b2.UnlockBits(bd2);
    }
}

Если вы пытаетесь определить, равны ли они на 100%, вы можете инвертировать один и добавить его к другому, если они равны нулю. Расширяя это с помощью небезопасного кода, возьмите 64 бита за раз и выполняйте математические вычисления таким образом, любые различия могут вызвать немедленный сбой.

Если изображения не идентичны на 100% (сравнивая png и jpeg), или если вы не ищете 100% совпадения, вам предстоит еще поработать.

Удачи.

Что ж, вы используете .LockBits, поэтому, по-видимому, вы используете небезопасный код. Вместо того, чтобы рассматривать начало каждой строки (Scan0 + y * Stride) как byte*, подумайте о том, чтобы рассматривать его как int*; int арифметика выполняется довольно быстро, и вам нужно выполнить только 1/4 объема работы. А для изображений в ARGB вы все равно можете использовать пиксели, упрощая математику.

Не могли бы вы взять хэш каждого и сравнить? Это было бы немного вероятностным, но практически нет.

Благодаря Раму, вот образец реализации этого метода.

Если исходная проблема состоит в том, чтобы просто найти точные дубликаты среди двух растровых изображений, тогда нужно будет просто сравнить битовый уровень. Я не знаю C #, но в C я бы использовал следующую функцию:

int areEqual (long size, long *a, long *b)
{
    long start = size / 2;
    long i;
    for (i = start; i != size; i++) { if (a[i] != b[i]) return 0 }
    for (i = 0; i != start; i++) { if (a[i] != b[i]) return 0 }
    return 1;
}

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

Если вы пытаетесь найти точные дубликаты среди сотен изображений, сравнивать все пары из них нет необходимости. Сначала вычислите хэш MD5 каждого изображения и поместите его в список пар (md5Hash, imageId); затем отсортируйте список по m5Hash. Затем выполняйте попарные сравнения только тех изображений, которые имеют одинаковый md5Hash.

Если эти растровые изображения уже есть на вашей видеокарте, вы можете распараллелить такую ​​проверку, выполнив ее на видеокарте, используя такой язык, как CUDA или OpenCL.

Я объясню в терминах CUDA, так как это тот, который я знаю. По сути, CUDA позволяет вам писать код общего назначения для параллельной работы на каждом узле вашей видеокарты. Вы можете получить доступ к растровым изображениям, находящимся в общей памяти. Каждому вызову функции также присваивается индекс в наборе параллельных запусков. Итак, для такой проблемы вы просто запустите одну из приведенных выше функций сравнения для некоторого подмножества растрового изображения, используя распараллеливание для покрытия всего растрового изображения. Затем просто запишите 1 в определенную ячейку памяти, если сравнение не удастся (и ничего не запишите, если оно удастся).

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

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

// kernel to run on GPU, once per thread
__global__ void compare_bitmaps(long const * const A, long const * const B, char * const retValue, size_t const len)
{
 // divide the work equally among the threads (each thread is in a block, each block is in a grid)
 size_t const threads_per_block = blockDim.x * blockDim.y * blockDim.z;
 size_t const len_to_compare = len / (gridDim.x * gridDim.y * gridDim.z * threads_per_block);
# define offset3(idx3,dim3)  (idx3.x + dim3.x * (idx3.y + dim3.y * idx3.z))
 size_t const start_offset = len_to_compare * (offset3(threadIdx,blockDim) + threads_per_block * offset3(blockIdx,gridDim));
 size_t const stop_offset = start_offset + len_to_compare;
# undef offset3

 size_t i;
 for (i = start_offset; i < stop_offset; i++)
 {
  if (A[i] != B[i]) 
  {
   *retValue = 1;
   break;
  }
 }
 return;
}

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

Или, если на то пошло, вы можете просто захотеть использовать какой-нибудь эквивалент memcmp ().

Вы можете попробовать добавить их в базу данных «blob», а затем использовать механизм базы данных для сравнения их двоичных файлов. Это даст вам только ответ «да» или «нет» на то, совпадают ли двоичные данные. Было бы очень легко сделать два изображения, которые будут воспроизводить одну и ту же графику, но имеют разные двоичные файлы.

Вы также можете выбрать несколько случайных пикселей и сравнить их, а затем, если они одинаковы, продолжить, пока вы не проверите все пиксели. Это вернет только более быстрое отрицательное совпадение, хотя поиск 100% положительных совпадений все равно займет столько же времени.

Основываясь на подходе сравнения хэшей вместо сравнения каждого пикселя, я использую вот что:

public static class Utils
{
    public static byte[] ShaHash(this Image image)
    {
        var bytes = new byte[1];
        bytes = (byte[])(new ImageConverter()).ConvertTo(image, bytes.GetType());

        return (new SHA256Managed()).ComputeHash(bytes);
    }

    public static bool AreEqual(Image imageA, Image imageB)
    {
        if (imageA.Width != imageB.Width) return false;
        if (imageA.Height != imageB.Height) return false;

        var hashA = imageA.ShaHash();
        var hashB = imageB.ShaHash();

        return !hashA
            .Where((nextByte, index) => nextByte != hashB[index])
            .Any();
    }
]

Использование простое:

bool isMatch = Utils.AreEqual(bitmapOne, bitmapTwo);