c# - manipulation - net core image processing
Maneras eficientes de determinar la inclinación de una imagen (9)
Intento escribir un programa para determinar programáticamente la inclinación o el ángulo de rotación en una imagen arbitraria.
Las imágenes tienen las siguientes propiedades:
- Consiste en texto oscuro sobre fondo claro
- De vez en cuando contiene líneas horizontales o verticales que solo se cruzan en ángulos de 90 grados.
- Sesgado entre -45 y 45 grados.
- Vea esta imagen como referencia (ha sido sesgada 2,8 grados).
Hasta ahora, he llegado a esta estrategia: Dibuje una ruta de izquierda a derecha, siempre seleccionando el píxel blanco más cercano. Presumiblemente, la ruta de izquierda a derecha preferirá seguir la ruta entre las líneas de texto a lo largo de la inclinación de la imagen.
Aquí está mi código:
private bool IsWhite(Color c) { return c.GetBrightness() >= 0.5 || c == Color.Transparent; }
private bool IsBlack(Color c) { return !IsWhite(c); }
private double ToDegrees(decimal slope) { return (180.0 / Math.PI) * Math.Atan(Convert.ToDouble(slope)); }
private void GetSkew(Bitmap image, out double minSkew, out double maxSkew)
{
decimal minSlope = 0.0M;
decimal maxSlope = 0.0M;
for (int start_y = 0; start_y < image.Height; start_y++)
{
int end_y = start_y;
for (int x = 1; x < image.Width; x++)
{
int above_y = Math.Max(end_y - 1, 0);
int below_y = Math.Min(end_y + 1, image.Height - 1);
Color center = image.GetPixel(x, end_y);
Color above = image.GetPixel(x, above_y);
Color below = image.GetPixel(x, below_y);
if (IsWhite(center)) { /* no change to end_y */ }
else if (IsWhite(above) && IsBlack(below)) { end_y = above_y; }
else if (IsBlack(above) && IsWhite(below)) { end_y = below_y; }
}
decimal slope = (Convert.ToDecimal(start_y) - Convert.ToDecimal(end_y)) / Convert.ToDecimal(image.Width);
minSlope = Math.Min(minSlope, slope);
maxSlope = Math.Max(maxSlope, slope);
}
minSkew = ToDegrees(minSlope);
maxSkew = ToDegrees(maxSlope);
}
Esto funciona bien en algunas imágenes, no tan bien en otras, y es lento.
¿Hay una manera más eficiente y más confiable de determinar la inclinación de una imagen?
¿Cuáles son tus limitaciones en términos de tiempo?
La transformada Hough es un mecanismo muy efectivo para determinar el ángulo de inclinación de una imagen. Puede ser costoso en el tiempo, pero si vas a utilizar desenfoque gaussiano, ya estás consumiendo un montón de tiempo de CPU. También hay otras formas de acelerar la transformación de Hough que implica el muestreo de imágenes creativas.
A primera vista, su código parece demasiado ingenuo. Lo que explica por qué no siempre funciona.
Me gusta el enfoque sugerido por Steve Wortham, pero podría tener problemas si tienes imágenes de fondo.
Otro enfoque que a menudo ayuda con las imágenes es desenfocarlas primero. Si difumina su imagen de ejemplo lo suficiente, cada línea de texto terminará como una línea borrosa y suave. A continuación, aplica algún tipo de algoritmo para básicamente hacer un análisis de regresión. Hay muchas formas de hacerlo y muchos ejemplos en la red.
La detección de bordes puede ser útil, o puede causar más problemas que lo que vale.
Por cierto, un desenfoque gaussiano puede implementarse de manera muy eficiente si buscas lo suficiente para el código. De lo contrario, estoy seguro de que hay muchas bibliotecas disponibles. No he hecho mucho de eso últimamente, así que no tengo ningún enlace a la mano. Pero una búsqueda de la biblioteca de procesamiento de imágenes le dará buenos resultados.
Supongo que está disfrutando la diversión de resolver esto, por lo que no hay muchos detalles de implementación reales aquí.
GetPixel es lento. Puede acelerar un orden de magnitud usando el enfoque que se detalla aquí .
He hecho algunas modificaciones a mi código, y ciertamente funciona mucho más rápido, pero no es muy preciso.
Hice las siguientes mejoras:
Utilizando la sugerencia de Vinko , evito GetPixel a favor de trabajar con bytes directamente, ahora el código se ejecuta a la velocidad que necesitaba.
Mi código original simplemente usaba "IsBlack" y "IsWhite", pero esto no es lo suficientemente detallado. El código original rastrea las siguientes rutas a través de la imagen:
http://img43.imageshack.us/img43/1545/tilted3degtextoriginalw.gif
Tenga en cuenta que varias rutas pasan por el texto. Comparando mi centro, arriba y debajo de los caminos con el valor de brillo real y seleccionando el píxel más brillante. Básicamente estoy tratando el mapa de bits como un mapa de alturas, y la ruta de izquierda a derecha sigue los contornos de la imagen, lo que resulta en una mejor ruta:
http://img10.imageshack.us/img10/5807/tilted3degtextbrightnes.gif
Según lo sugerido por Toaomalkster , un desenfoque Gaussiano suaviza el mapa de altura, obtengo incluso mejores resultados:
http://img197.imageshack.us/img197/742/tilted3degtextblurredwi.gif
Como este es solo un código de prototipo, borré la imagen usando GIMP, no escribí mi propia función de desenfoque.
La ruta seleccionada es bastante buena para un algoritmo codicioso.
Como sugirió Toaomalkster , elegir la pendiente min / max es ingenuo. Una regresión lineal simple proporciona una mejor aproximación de la pendiente de un camino. Además, debo cortar el camino corto una vez que corro fuera del borde de la imagen, de lo contrario, la ruta abarcará la parte superior de la imagen y dará una pendiente incorrecta.
Código
private double ToDegrees(double slope) { return (180.0 / Math.PI) * Math.Atan(slope); }
private double GetSkew(Bitmap image)
{
BrightnessWrapper wrapper = new BrightnessWrapper(image);
LinkedList<double> slopes = new LinkedList<double>();
for (int y = 0; y < wrapper.Height; y++)
{
int endY = y;
long sumOfX = 0;
long sumOfY = y;
long sumOfXY = 0;
long sumOfXX = 0;
int itemsInSet = 1;
for (int x = 1; x < wrapper.Width; x++)
{
int aboveY = endY - 1;
int belowY = endY + 1;
if (aboveY < 0 || belowY >= wrapper.Height)
{
break;
}
int center = wrapper.GetBrightness(x, endY);
int above = wrapper.GetBrightness(x, aboveY);
int below = wrapper.GetBrightness(x, belowY);
if (center >= above && center >= below) { /* no change to endY */ }
else if (above >= center && above >= below) { endY = aboveY; }
else if (below >= center && below >= above) { endY = belowY; }
itemsInSet++;
sumOfX += x;
sumOfY += endY;
sumOfXX += (x * x);
sumOfXY += (x * endY);
}
// least squares slope = (NΣ(XY) - (ΣX)(ΣY)) / (NΣ(X^2) - (ΣX)^2), where N = elements in set
if (itemsInSet > image.Width / 2) // path covers at least half of the image
{
decimal sumOfX_d = Convert.ToDecimal(sumOfX);
decimal sumOfY_d = Convert.ToDecimal(sumOfY);
decimal sumOfXY_d = Convert.ToDecimal(sumOfXY);
decimal sumOfXX_d = Convert.ToDecimal(sumOfXX);
decimal itemsInSet_d = Convert.ToDecimal(itemsInSet);
decimal slope =
((itemsInSet_d * sumOfXY) - (sumOfX_d * sumOfY_d))
/
((itemsInSet_d * sumOfXX_d) - (sumOfX_d * sumOfX_d));
slopes.AddLast(Convert.ToDouble(slope));
}
}
double mean = slopes.Average();
double sumOfSquares = slopes.Sum(d => Math.Pow(d - mean, 2));
double stddev = Math.Sqrt(sumOfSquares / (slopes.Count - 1));
// select items within 1 standard deviation of the mean
var testSample = slopes.Where(x => Math.Abs(x - mean) <= stddev);
return ToDegrees(testSample.Average());
}
class BrightnessWrapper
{
byte[] rgbValues;
int stride;
public int Height { get; private set; }
public int Width { get; private set; }
public BrightnessWrapper(Bitmap bmp)
{
Rectangle rect = new Rectangle(0, 0, bmp.Width, bmp.Height);
System.Drawing.Imaging.BitmapData bmpData =
bmp.LockBits(rect,
System.Drawing.Imaging.ImageLockMode.ReadOnly,
bmp.PixelFormat);
IntPtr ptr = bmpData.Scan0;
int bytes = bmpData.Stride * bmp.Height;
this.rgbValues = new byte[bytes];
System.Runtime.InteropServices.Marshal.Copy(ptr,
rgbValues, 0, bytes);
this.Height = bmp.Height;
this.Width = bmp.Width;
this.stride = bmpData.Stride;
}
public int GetBrightness(int x, int y)
{
int position = (y * this.stride) + (x * 3);
int b = rgbValues[position];
int g = rgbValues[position + 1];
int r = rgbValues[position + 2];
return (r + r + b + g + g + g) / 6;
}
}
El código es bueno , pero no excelente . Grandes cantidades de espacio en blanco hacen que el programa dibuje una línea relativamente plana, lo que da como resultado una pendiente cercana a 0, lo que hace que el código subestime la inclinación real de la imagen.
No existe una diferencia apreciable en la precisión de la inclinación seleccionando puntos de muestra aleatorios versus muestreo de todos los puntos, porque la relación de trayectos "planos" seleccionados por muestreo aleatorio es la misma que la relación de trayectos "planos" en toda la imagen.
Medir el ángulo de cada línea parece exagerado, especialmente teniendo en cuenta el rendimiento de GetPixel.
Me pregunto si tendrías un mejor rendimiento al buscar un triángulo blanco en la esquina superior izquierda o superior derecha (dependiendo de la dirección oblicua) y medir el ángulo de la hipotenusa. Todo el texto debe seguir el mismo ángulo en la página, y la esquina superior izquierda de una página no será engañada por los descensores o el espacio en blanco del contenido que está sobre ella.
Otro consejo a considerar: en lugar de difuminar, trabaje dentro de una resolución muy reducida. Eso le dará los datos más suaves que necesita y menos llamadas GetPixel.
Por ejemplo, hice una rutina de detección de página en blanco una vez en .NET para archivos TIFF enviados por fax que simplemente remuestreaban toda la página a un solo píxel y probaban el valor de un valor umbral de blanco.
Muy buena aplicación de búsqueda de ruta. Me pregunto si este otro enfoque ayudaría o perjudicaría con su conjunto de datos en particular.
Suponer una imagen en blanco y negro:
- Proyecte todos los píxeles negros a la derecha (ESTE). Esto debería dar como resultado una matriz unidimensional con un tamaño de IMAGE_HEIGHT. Llame a la matriz CANVAS.
- Mientras proyecta todos los píxeles ESTE, realice un seguimiento numérico de la cantidad de píxeles proyectados en cada contenedor de CANVAS.
- Gire la imagen un número arbitrario de grados y vuelva a proyectar.
- Elija el resultado que da los picos más altos y los valles más bajos para los valores en CANVAS.
Me imagino que esto no funcionará bien si de hecho tienes que dar cuenta de una verdadera -45 -> +45 grados de inclinación. Si el número real es más pequeño (? +/- 10 grados), esta podría ser una estrategia bastante buena. Una vez que tenga un resultado inicial, podría considerar volver a ejecutarlo con un incremento menor de grados para ajustar la respuesta. Por lo tanto, podría tratar de escribir esto con una función que aceptara un float degree_tick como parm para poder ejecutar tanto un pase grueso como fino (o un espectro de grosor o finura) con el mismo código.
Esto podría ser computacionalmente costoso. Para optimizar, puede considerar seleccionar solo una parte de la imagen para project-test-rotate-repeat on.
Primero debo decir que me gusta la idea. Pero nunca tuve que hacer esto antes y no estoy seguro de qué sugerir para mejorar la fiabilidad. Lo primero que puedo pensar de esto es esta idea de descartar anomalías estadísticas. Si la pendiente cambia repentinamente repentinamente, entonces sabrá que ha encontrado una sección blanca de la imagen que se sumerge en la inclinación del borde (sin juego de palabras) de sus resultados. Entonces querrías arrojar esas cosas de alguna manera.
Pero desde el punto de vista del rendimiento hay una serie de optimizaciones que podrías hacer y que pueden sumar.
A saber, cambiaría este fragmento de tu ciclo interno de esto:
Color center = image.GetPixel(x, end_y);
Color above = image.GetPixel(x, above_y);
Color below = image.GetPixel(x, below_y);
if (IsWhite(center)) { /* no change to end_y */ }
else if (IsWhite(above) && IsBlack(below)) { end_y = above_y; }
else if (IsBlack(above) && IsWhite(below)) { end_y = below_y; }
A esto:
Color center = image.GetPixel(x, end_y);
if (IsWhite(center)) { /* no change to end_y */ }
else
{
Color above = image.GetPixel(x, above_y);
Color below = image.GetPixel(x, below_y);
if (IsWhite(above) && IsBlack(below)) { end_y = above_y; }
else if (IsBlack(above) && IsWhite(below)) { end_y = below_y; }
}
Es el mismo efecto pero debería reducir drásticamente la cantidad de llamadas a GetPixel.
También considere poner los valores que no cambian en variables antes de que comience la locura. Cosas como image.Height e image.Width tienen una ligera sobrecarga cada vez que los llamas. Así que almacene esos valores en sus propias variables antes de que comiencen los bucles. Lo que siempre me digo a mí mismo al tratar con bucles anidados es optimizar todo dentro del bucle más interno a expensas de todo lo demás.
Además ... como sugirió Vinko Vrsalovic, puedes mirar su alternativa de GetPixel para aumentar aún más la velocidad.
Si el texto está alineado a la izquierda (derecha) puede determinar la pendiente midiendo la distancia entre el borde izquierdo (derecho) de la imagen y el primer píxel oscuro en dos lugares aleatorios y calcular la pendiente a partir de eso. Las mediciones adicionales reducirían el error al tiempo adicional.
Tu último resultado me confunde un poco. Cuando superpuso las líneas azules en la imagen de origen, ¿lo compensó un poco? Parece que las líneas azules están a unos 5 píxeles por encima del centro del texto.
No estoy seguro acerca de ese desplazamiento, pero definitivamente tiene un problema con la línea derivada "a la deriva" en el ángulo equivocado. Parece tener un sesgo demasiado fuerte hacia la producción de una línea horizontal.
Me pregunto si al aumentar la ventana de máscara de 3 píxeles (centro, uno arriba, uno abajo) a 5 podría mejorar esto (dos arriba, dos abajo). También obtendrá este efecto si sigue la sugerencia de richardtallent y remuestrea la imagen más pequeña.