c# - vectoriales - ¿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?

que es un mapa de bits en corel draw

Question

Estoy intentando escribir una función para determinar si dos bitmaps 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 ciclo 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 estoy usando punteros para acceder directamente a la memoria; 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 : Olvidé activar las optimizaciones; al hacerlo, la respuesta de GrayWizardX es aún más estimulante:

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

Es interesante que el método MD5 no haya mejorado en absoluto.

Editar 3 : publicó mi respuesta (MemCmp) que hizo volar los otros métodos fuera del agua. oO

Answer 1

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

Gracias a Ram, aquí hay una implementación de muestra de esta técnica.

Answer 2

Basado en el enfoque de comparar hash en lugar de comparar cada píxel, esto es lo que 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();
    }
]

El uso es directo:

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

Answer 3

Bueno, estás usando .LockBits , así que presumiblemente estás usando código inseguro. En lugar de tratar cada origen de fila ( Scan0 + y * Stride ) como un byte* , considere tratarlo como int* ; int arithmetic es bastante rápido, y solo tienes 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 4

Editar 8-31-12: según Joey''s comentario Joey''s continuación, tenga en cuenta el formato de los mapas de bits que compara. Pueden contener relleno en los zancadas que hacen que los mapas de bits sean desiguales, a pesar de ser equivalentes en píxeles. Vea esta pregunta para más detalles.

La lectura de esta respuesta a una pregunta sobre la comparación de matrices de bytes ha producido un método MUCHO MÁS RÁPIDO: el uso de P / Invoke y la llamada a la API de 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 5

Podría tratar de agregarlos a una base de datos "blob" y luego usar el motor de la 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 encontrar coincidencias positivas al 100%.

Answer 6

Si el problema original es solo encontrar los duplicados exactos entre dos mapas de bits, entonces solo tendrá que hacer una comparación de nivel de bits. No sé C # pero en CI usaría 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;
}

Empezaría a buscar en el medio porque sospecho que hay muchas más probabilidades de encontrar bits desiguales cerca de la mitad de la imagen que al principio; 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 7

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ás buscando un 100% de coincidencia, entonces tienes más trabajo por delante.

Buena suerte.

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 .

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 todavía no tiene los mapas de bits en su tarjeta gráfica, probablemente este no sea el camino a seguir, ya que los costos de cargar los dos mapas de bits en su tarjeta eclipsarán fácilmente los ahorros que dicha paralelización le brindará.

Aquí hay algún 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

Si puede implementar algo como el Dispositivo de Duff 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, tal vez solo desee usar algún equivalente a memcmp ().