¿Cómo encontrar la diferencia entre dos imágenes?

Estoy desarrollando una aplicación para compartir pantalla. En este proyecto necesito transportar imágenes a través de internet. Obviamente, no puedo enviar una nueva imagen por Internet cada pocos segundos, sería extremadamente lento. Quiero enviar una imagen de la pantalla del servidor al cliente, y luego, en lugar de enviar una nueva imagen, enviando solo los píxeles que se han cambiado desde la última imagen (la que el cliente ya tiene).

He escrito este código:

private List CompareBitmaps(Image old, Image _new) { List returnList = new List(); for(int i = 0; i < old.Width; i++) for (int j = 0; j < old.Height; j++) { if (((Bitmap)old).GetPixel(i, j) != ((Bitmap)_new).GetPixel(i, j)) { returnList.Add(((Bitmap)_new).GetPixel(i, j)); } } return returnList; } 

Sin embargo, funciona demasiado lento.

Estoy buscando un algoritmo más rápido, uno con una mejor complejidad.

Nota: No quiero una biblioteca creada que lo haga. Necesito un algoritmo.

Esta rutina encuentra las diferencias entre dos mapas de bits y los devuelve en el primer bitmap configurando todo lo demás como casi negro y prácticamente transparente. También puede restaurar el segundo archivo original al agregar el resultado a la imagen anterior.

Reduje una captura de pantalla de 800MB 1o 12k, pero solo había un pequeño cambio en las manos de Clocks 😉 Si tus imágenes difieren en muchos píxeles, la compresión no será tan espectacular … pero creo que será lo suficientemente bueno para transmitir y dudo de que todo en una base píxel por píxel se compare con las rutinas de compresión de los formatos de archivo png o jpg … (¡No transmites bmps, espero!)

La rutina usa LockBits y es bastante rápido.

El parámetro bool decide si crear el bitmap de diferencia o restaurar el bitmap modificado.

 public static Bitmap Difference(Bitmap bmp0, Bitmap bmp1, bool restre) { int Bpp = 4; // assuming an effective pixelformat of 32bpp var bmpData0 = bmp0.LockBits( new Rectangle(0, 0, bmp0.Width, bmp0.Height), ImageLockMode.ReadWrite, bmp0.PixelFormat); var bmpData1 = bmp1.LockBits( new Rectangle(0, 0, bmp1.Width, bmp1.Height), ImageLockMode.ReadOnly, bmp1.PixelFormat); int len = bmpData0.Height * bmpData0.Stride; byte[] data0 = new byte[len]; byte[] data1 = new byte[len]; Marshal.Copy(bmpData0.Scan0, data0, 0, len); Marshal.Copy(bmpData1.Scan0, data1, 0, len); for (int i = 0; i < len; i += Bpp) { if (restore) { bool toberestored = (data1[i ] != 2 && data1[i+1] != 3 && data1[i+2] != 7 && data1[i+2] != 42); if (toberestored) { data0[i ] = data1[i]; // Blue data0[i+1] = data1[i+1]; // Green data0[i+2] = data1[i+2]; // Red data0[i+3] = data1[i+3]; // Alpha } } else { bool changed = ((data0[i ] != data1[i ]) || (data0[i+1] != data1[i+1]) || (data0[i+2] != data1[i+2]) ); data0[i ] = changed ? data1[i ] : (byte)2; // special markers data0[i+1] = changed ? data1[i+1] : (byte)3; // special markers data0[i+2] = changed ? data1[i+2] : (byte)7; // special markers data0[i+3] = changed ? (byte)255 : (byte)42; // special markers } } Marshal.Copy(data0, 0, bmpData0.Scan0, len); bmp0.UnlockBits(bmpData0); bmp1.UnlockBits(bmpData1); return bmp0; } 

Notas: - He elegido un color especial para marcar los píxeles que deben restaurarse en el destinatario. Aquí elegí alpha=42 y R=7; G=3; B=2; R=7; G=3; B=2; .. No es 100% seguro, pero casi; no se perderán muchos píxeles; y tal vez no tengas tranparency de todos modos ...?

Añado dos imágenes más pequeñas, ambas PNG, alrededor de 400kB:

enter image description hereenter image description here

Esta es la imagen de diferencia (3kB):

enter image description here

La imagen restaurada es la misma que la segunda imagen.

Debe devolver todos los píxeles modificados, por lo que la complejidad tendrá que ser m * n.

  1. (Bitmap) _new) .GetPixel (i, j) se llama dos veces, usar un valor temporal para almacenarlo podría ser un poco mejor.

  2. el pixel debe tener varios valores ¿no? ¿Puedes intentar crear una función llamada comprareTwoPixel (color A, color B)? y compare todos los valores uno por uno, si uno de ellos es falso, no necesita comparar el rest, simplemente devuelva falso. (No estoy seguro si esto lo hará más rápido o no).

Me gusta:

 bool comprareTwoPixel(color A, color B) { if(Aa!=Bb) return false; if(Ab!=Bb) return false; if(Ac!=Bc) return false; return true; } 

No estoy seguro de lo que intenta hacer con este código, porque no está guardando los índices que han cambiado …

Es posible que desee utilizar otro constructor para su Lista, porque List () tiene una capacidad predeterminada de 0

Eso significa que volverá a asignar el búfer interno de la lista quizás muchas veces si han cambiado muchos píxeles

Tal vez registrar el número promedio de píxeles que ha cambiado y establecer la capacidad inicial de su lista en ese número puede acelerar su código. Al menos, puedes decir que, por ejemplo, el 10% del píxel cambia cada fotogtwig:

 List returnList = new List( (int)( 0.10 * numberOfPixel ) ); 

Esto puede o no funcionar perfectamente, pero aquí va. Puede paralelizar esto si lo ve conveniente añadiendo AsParallel .

También copié y pegué algunas líneas aquí, así que siéntete libre de avisarme o editar si tengo errores tipográficos o variables no coincidentes. Pero esta es la esencia de eso. Esto debería ser bastante rápido, dentro de lo razonable.

Básicamente, dado que esto puede ser un poco difícil de entender tal como está, la idea es “bloquear” los bits, luego usar ese puntero para copiarlos a un byte[] . Eso copia efectivamente todos los valores RGB (A), a los que puede acceder fácilmente. Esto es mucho más rápido que GetPixel cuando estás leyendo, como tú, más de un píxel o dos, porque toma un poco de tiempo sacar los píxeles, pero luego es simplemente lecturas contra la memoria.

Una vez que los meto en el byte[] s, es bastante fácil simplemente compararlos para cada coordenada de píxel. Elegí usar LINQ para que sea realmente fácil de paralelizar si fuera necesario, pero puede o no elegir implementarlo realmente. No estoy seguro de si será necesario.

He hecho algunas suposiciones aquí que creo que son justas, ya que parece que su implementación tiene todas las imágenes provenientes de una sola fuente. A saber, supongo que las imágenes son del mismo tamaño y formato. Entonces, si ese no es el caso, querrá abordar eso con un código adicional aquí, pero eso todavía es bastante fácil.

 private byte[] UnlockBits(Bitmap bmp, out int stride) { BitmapData bmpData = bmp.LockBits(new Rectangle(Point.Empty, bmp.Size), System.Drawing.Imaging.ImageLockMode.ReadOnly, bmp.PixelFormat); IntPtr ptr = bmpData.Scan0; stride = bmpData.Stride; int bytes = Math.Abs(bmpData.Stride) * bmp.Height; byte[] ret = new byte[bytes]; System.Runtime.InteropServices.Marshal.Copy(ptr, ret, 0, bytes); bmp.UnlockBits(bmpData); return ret; } private bool AreArraysEqual(byte[] a, byte[] b, int offset, int length) { for (int v = 0; v < length; v++) { int c = v + offset; if (a[c] != b[c]) { return false; } } return true; } private IEnumerable>> GetDifferences(Bitmap a, Bitmap b) { if (a.PixelFormat != b.PixelFormat) throw new ArgumentException("Unmatched formats!"); if (a.Size != b.Size) throw new ArgumentException("Unmatched length!"); int stride; byte[] rgbValuesA = UnlockBits(a, out stride); byte[] rgbValuesB = UnlockBits(b, out stride); if (rgbValuesA.Length != rgbValuesB.Length) throw new ArgumentException("Unmatched array lengths (unexpected error)!"); int bytesPerPixel = Image.GetPixelFormatSize(a.PixelFormat) / 8; return Enumerable.Range(0, a.Height).SelectMany(y => Enumerable.Range(0, a.Width) .Where(x => !AreArraysEqual(rgbValuesA, rgbValuesB, (y * stride) + (x * bytesPerPixel), bytesPerPixel)) .Select(x => { Point pt = new Point(x, y); int pixelIndex = (y * stride) + (x * bytesPerPixel); Color colorA = ReadPixel(rgbValuesA, pixelIndex, bytesPerPixel); Color colorB = ReadPixel(rgbValuesB, pixelIndex, bytesPerPixel); return new KeyValuePair>(pt, colorA, colorB); } } private Color ReadPixel(byte[] bytes, int offset, int bytesPerPixel) { int argb = BitConverter.ToInt32(pixelBytes, offset); if (bytesPerPixel == 3) // no alpha argb |= (255 << 24); return Color.FromArgb(argb); } public IEnumerable> GetNewColors(Bitmap _new, Bitmap old) { return GetDifferences(_new, old).Select(c => new KeyValuePair(c.Key, c.Value.Item1)); } 

En una verdadera implementación, es posible que desee pensar en la endianidad y el formato de píxeles con más profundidad que yo, pero esto debería funcionar más o menos como una prueba de concepto, y creo que debería manejar la mayoría de los casos prácticos.

Y como dijo @TaW en un comentario, también podrías intentar borrar (poniendo alfa a cero, probablemente) cualquiera que no haya cambiado. También puedes beneficiarte del deslocking de píxeles para eso. Nuevamente, hay posibles tutoriales que le dicen cómo hacerlo. Pero gran parte de esto podría permanecer igual.