¿Cuál es la forma más rápida de comparar dos mapas de bits de igual tamaño para determinar si son idénticos?

Question

Estoy intentando escribir una función para determinar si dos mapas de bits de igual tamaño son idénticos o no. La función que tengo ahora simplemente compara un píxel a la vez en cada mapa de bits, devolviendo falso al primer píxel no equitativo.

Si bien esto funciona, y funciona bien para pequeños mapas de bits, en la producción voy a utilizar esto en un circuito cerrado y en imágenes más grandes, así que necesito una mejor manera. ¿Alguien tiene alguna recomendación?

El lenguaje que estoy usando es C# por cierto, y sí, ya estoy usando el método .LockBits. =)

Editar: He codificado las implementaciones de algunas de las sugerencias dadas, y aquí están los puntos de referencia. La configuración: dos mapas de bits idénticos (en el peor de los casos), de 100x100, con 10.000 iteraciones cada uno. Aquí están los resultados:

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

En CompareByInts y CompareByMask que estoy usando punteros para acceder a la memoria directamente; en el método MD5 estoy usando Marshal.Copy para recuperar una matriz de bytes y pasar eso como un argumento a MD5.ComputeHash. CompareByMask es solo un poco más rápido, pero dado el contexto, creo que cualquier mejora es útil.

Gracias a todos. =)

Editar 2: se olvidó de girar optimizaciones en - haciendo que da la respuesta de GrayWizardX aún más de un impulso:

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

interesante que el método MD5 no mejoró en absoluto.

Editar 3: Publicada mi respuesta (MemCmp) que hizo saltar los otros métodos fuera del agua. o.O

Answer 1

Editar 31/08/12: por Joey's comentario a continuación, ser conscientes del formato de los mapas de bits que comparar. Pueden contener relleno en los zancadas que hacen que los mapas de bits sean desiguales, a pesar de ser equivalentes en píxeles. Vea this question para más detalles.

---

lectura this answer a una pregunta sobre comparan las matrices de bytes ha producido un método mucho más rápido: el uso de P/Invoke y la llamada a la API memcmp en msvcrt.Aquí está el código:

[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

Bueno, está usando .LockBits, por lo que presumiblemente está utilizando un código inseguro. En lugar de tratar cada origen de fila (Scan0 + y * Stride) como byte*, considere tratarlo como int*; int aritmética es bastante rápido, y usted solo tiene que hacer 1/4 de tanto trabajo. Y para las imágenes en ARGB, aún podría estar hablando en píxeles, haciendo que las matemáticas sean simples.

Answer 3

¿Podría tomar un hash de cada uno y comparar? Sería ligeramente probabilístico, pero prácticamente no.

Gracias a Ram, aquí hay un sample implementation de esta técnica.

Answer 4

Si está tratando de determinar si son 100% iguales, puede invertir uno y agregarlo al otro si es igual a cero. Extendiendo esto usando un código inseguro, tome 64 bits a la vez como un largo y haga los cálculos de esa manera, cualquier diferencia puede causar un error inmediato.

Si las imágenes no son 100% idénticas (comparando png a jpeg), o si no está buscando una coincidencia del 100%, entonces tiene más trabajo por delante.

Buena suerte.

Answer 5

Si puede implementar algo como Duff's Device en su idioma, eso podría darle un impulso de velocidad significativo sobre un bucle simple. Por lo general, se utiliza para copiar datos, pero no hay ninguna razón por la que no se pueda usar para comparar datos.

O, para el caso, es posible que desee utilizar algún equivalente a memcmp().

Answer 6

Puede intentar agregarlos a una base de datos "blob" y luego usar el motor de base de datos para comparar sus binarios. Esto solo le daría una respuesta afirmativa o negativa a si los datos binarios son los mismos. Sería muy fácil hacer 2 imágenes que producen el mismo gráfico, pero tienen diferentes binarios.

También puede seleccionar algunos píxeles aleatorios y compararlos, luego, si son los mismos, continúe con más hasta que haya verificado todos los píxeles. Sin embargo, esto solo devolvería una coincidencia negativa más rápida, aún tardaría tanto en encontrar 100% de coincidencias positivas

Answer 7

Si el problema original es encontrar los duplicados exactos entre dos mapas de bits, entonces solo tendrá que hacer una comparación de nivel de bits. hacer. No sé C# pero en CI utilizar la siguiente función:

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

Me gustaría empezar a buscar en el medio porque sospecho que hay muchas más posibilidades de encontrar trozos desiguales cerca del centro de la imagen de la comenzando; por supuesto, esto realmente dependería de las imágenes que estás desduplicando, seleccionar un lugar aleatorio para comenzar puede ser lo mejor.

Si está tratando de encontrar los duplicados exactos entre cientos de imágenes, entonces no es necesario comparar todos los pares. Primero calcule el hash MD5 de cada imagen y colóquelo en una lista de pares (md5Hash, imageId); luego ordena la lista por m5Hash. A continuación, solo haga comparaciones por pares en las imágenes que tienen el mismo md5Hash.

Answer 8

Si estos mapas de bits ya están en su tarjeta gráfica, puede paralelizar dicha comprobación ejecutándola en la tarjeta gráfica usando un lenguaje como CUDA o OpenCL.

Lo explicaré en términos de CUDA, ya que ese es el que yo sé. Básicamente CUDA le permite escribir código de propósito general para ejecutar en paralelo a través de cada nodo de su tarjeta gráfica. Puede acceder a bitmaps que están en la memoria compartida. A cada invocación de la función también se le asigna un índice dentro del conjunto de ejecuciones paralelas. Entonces, para un problema como este, ejecutaría una de las funciones de comparación anteriores para algún subconjunto del mapa de bits, utilizando la paralelización para cubrir todo el mapa de bits. Luego, simplemente escriba un 1 en una determinada ubicación de memoria si la comparación falla (y no escriba nada si tiene éxito).

Si aún no tiene mapas de bits en su tarjeta gráfica, probablemente este no sea el camino a seguir, ya que los costos de carga de los dos mapas de bits en su tarjeta eclipsarán fácilmente los ahorros que le brindará esa paralelización.

He aquí un código de ejemplo (bastante malo) (ha pasado un tiempo desde que programé CUDA). Hay mejores formas de acceder a bitmaps que ya están cargados como texturas, pero no me molesté aquí.

// 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 9

Basado en el enfoque de la comparación de los hashes en lugar de comparar cada píxel, esto es lo que yo uso:

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(); 
    } 
] 

uso es sencillo:

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