Как быстрее всего сравнить два растровых изображения одинакового размера, чтобы определить, идентичны ли они?
Я пытаюсь написать функцию, чтобы определить, являются ли две битовые карты одинакового размера идентичными или нет. Функция, которая у меня есть сейчас, просто сравнивает пиксель за раз в каждом растровом изображении, возвращая ложь в первом неравном пикселе.
Хотя это работает и хорошо работает для небольших растровых изображений, на производстве я собираюсь использовать это в тесном цикле и на больших изображениях, поэтому мне нужен лучший способ. У кого-нибудь есть рекомендации?
Кстати, я использую язык C# - и да, я уже использую метод.LockBits. знак равно
Изменить: я закодировал реализации некоторых из приведенных предложений, и вот тесты. Настройка: две идентичные (в худшем случае) битовые карты размером 100x100 с 10000 итераций каждая. Вот результаты:
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), который взорвал другие методы из воды. оо
9 ответов
Изменить 8-31-12: в соответствии Joey комментарием Joey ниже, помните о формате растровых изображений, которые вы сравниваете. Они могут содержать отступы на шагах, которые делают растровые изображения неравными, несмотря на то, что они эквивалентны по пикселям. Смотрите этот вопрос для более подробной информации.
Чтение этого ответа на вопрос, касающийся сравнения байтовых массивов, привело к MUCH FASTER методу: использование P/Invoke и вызова memcmp API в 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 I использовал бы следующую функцию:
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", а затем использовать механизм базы данных для сравнения их двоичных файлов. Это только даст вам ответ "да" или "нет" на то, совпадают ли двоичные данные. Было бы очень легко сделать 2 изображения, которые производят одну и ту же графику, но имеют разные двоичные файлы.
Вы также можете выбрать несколько случайных пикселей и сравнить их, а затем, если они совпадают, продолжить с большим, пока вы не проверите все пиксели. Это только вернет более быстрое отрицательное совпадение, но все равно потребуется 100% времени, чтобы найти 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);