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

Question

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

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

Кстати, я использую язык C # - и да, я уже использую метод .LockBits. =)

Редактировать : Я кодировал реализации некоторых из приведенных предложений, и вот тесты. Настройка: две идентичные (в худшем случае) битовые карты размером 100x100 с 10 000 итераций каждая. Вот результаты:

CompareByInts (Marc Gravell) :   1107ms
CompareByMD5  (Skilldrick)   :   4222ms
CompareByMask (GrayWizardX)  :    949ms

В CompareByInts и CompareByMask я использую указатели для прямого доступа к памяти; в методе MD5 я использую Marshal.Copy для получения массива байтов и передачи его в качестве аргумента в MD5.ComputeHash. CompareByMask только немного быстрее, но, учитывая контекст, я думаю, что любое улучшение полезно.

Спасибо всем. =)

Редактировать 2 : Забыл включить оптимизацию - это дает ответ GrayWizardX еще больше поддержки:

CompareByInts   (Marc Gravell) :    944ms
CompareByMD5    (Skilldrick)   :   4275ms
CompareByMask   (GrayWizardX)  :    630ms
CompareByMemCmp (Erik)         :    105ms

Интересно, что метод MD5 вообще не улучшился.

Редактировать 3 : Написал мой ответ (MemCmp), который взорвал другие методы из воды. o.o

Answer 1

Редактировать 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);
    }
}

Answer 2

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

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

Удачи.

Answer 3

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

Answer 4

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

Благодаря Раму, вот пример реализации этой техники.

Answer 5

Если эти растровые изображения уже есть на вашей видеокарте, вы можете распараллелить такую ​​проверку, выполнив ее на графической плате с использованием языка, подобного 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;
}

Answer 6

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

Answer 7

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

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

Answer 8

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

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

Answer 9

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

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