una - dibujar rectangulo en c#




Escaneando imágenes para encontrar rectángulos (7)

Basado en los comentarios de aclaración, su método existente es el punto de partida perfecto, solo que, en mi opinión, debería funcionar utilizando un mapa de bits auxiliar que contenga los píxeles que no deben verificarse (en absoluto, o nuevamente).

Suponiendo que la mayoría de la imagen no es roja:

  1. borrar bitmap auxiliar a 0
  2. establecer x = y = 0, posición inicial para escanear
  3. escanee la imagen desde x, y, proceda en el orden de almacenamiento para mayor eficiencia, ubique el primer píxel rojo en la imagen donde el mapa de bits auxiliar es 0
  4. esa es la esquina de un rectángulo, encuentre sus dimensiones utilizando el enfoque existente (comience un escaneo horizontal y vertical, etc.)
  5. grabar el rectángulo (x, y, w, h)
  6. Rellene el rectángulo (x, y, w, h) en el mapa de bits auxiliar con 1-s
  7. x + = w + 1, continúe desde 2 (lo que implica que verificará si la nueva posición x aún está dentro de las dimensiones de la imagen e intentará desde 0, y + 1 si es necesario, y también reconocerá si el escaneo está listo)

Si la mayor parte de la imagen está cubierta con rectángulos rojos, cambiaría el cheque en 3 (primero verifique el mapa de bits auxiliar, y luego verifique si el píxel es rojo), y extienda el paso de llenado (6) con un píxel a la izquierda, a la derecha y direcciones inferiores (ya se han comprobado los píxeles hacia la parte superior)

Personalmente creo más en la eficiencia de la caché de leer píxeles adyacentes en orden de memoria que en saltar alrededor (debido a la idea de partición), pero aún así visitar la mayoría de los píxeles, además de tener que unir una gran cantidad de fragmentos-rectángulos al final .

Estoy intentando escanear una imagen de tamaño constante y ubicar los rectángulos dibujados en ella. Los rectángulos pueden venir de cualquier tamaño, pero solo de color rojo.

Aquí no es donde comienza el problema.

Voy a usar una función ya escrita, y la usaré como pseudo código de llamadas más adelante en mi lógica de código.

Rectangle Locate(Rectangle scanArea); // busca un rectángulo en un área de escaneo dada. Si no se encuentra un rectángulo, devuelve nulo.

Mi lógica era así:

Encuentre un primer rectángulo rojo inicial usando la función Locate() con el tamaño completo de la imagen como argumento. Ahora, divida las áreas de descanso, y siga escaneando recursivamente. El punto principal en la lógica de este algoritmo es que nunca verifica un área ya verificada, y no tiene que usar ninguna condición porque siempre el parámetro scanArea es un área nueva que no ha escaneado antes (y eso es gracias a la división técnica). El proceso de división se realiza así: área derecha del rectángulo encontrado actual, área inferior y área izquierda.

Aquí hay una imagen que ilustra ese proceso. (Los rectángulos de puntos blancos y las flechas amarillas no son parte de la imagen, los he agregado solo para la ilustración). Como se ve, una vez que se encuentra un rectángulo rojo, sigo escaneando a la derecha, abajo y a la izquierda. Recursivamente.

Así que aquí está el código para ese método:

List<Rectangle> difList=new List<Rectangle>();

private void LocateDifferences(Rectangle scanArea)
{
    Rectangle foundRect = Locate(scanArea);
    if (foundRect == null)
        return; // stop the recursion.

    Rectangle rightArea = new Rectangle(foundRect.X + foundRect.Width, foundRect.Y, (scanArea.X + scanArea.Width) - (foundRect.X + foundRect.Width), (scanArea.Y + scanArea.Height) - (foundRect.Y + foundRect.Height)); // define right area.
    Rectangle bottomArea = new Rectangle(foundRect.X, foundRect.Y + foundRect.Height, foundRect.Width, (scanArea.Y + scanArea.Height) - (foundRect.Y + foundRect.Height)); // define bottom area.
    Rectangle leftArea = new Rectangle(scanArea.X, foundRect.Y, (foundRect.X - scanArea.X), (scanArea.Y + scanArea.Height) - (foundRect.Y + foundRect.Height)); // define left area.

    difList.Add(rectFound);

    LocateDifferences(rightArea);
    LocateDifferences(bottomArea);
    LocateDifferences(leftArea);
}

Hasta ahora todo funciona bien, encuentra todos los rectángulos rojos. Pero a veces, los rectángulos se guardan como pocos rectángulos. Por una razón tan obvia para mí: la superposición de rectángulos.

Un caso problemático por ejemplo:

Ahora, en este caso, el programa encuentra la primera región roja según lo planeado, pero luego, como el área correcta comienza solo en la mitad de la segunda región completa, ¡no escanea desde el principio del segundo rectángulo rojo!

De manera similar, puedo dividir las áreas para que el área inferior se extienda desde el inicio de scanArea hasta el final, que sería así: Pero ahora tendríamos un problema al escanear rectángulos superpuestos a la derecha y a la izquierda del rectángulo foundRect , por ejemplo, en este tipo de caso:

Necesito obtener cada rectángulo en una sola pieza. Me gustaría recibir cualquier ayuda o sugerencia combinada con mi lógica de código, ya que funciona muy bien, pero creo que solo necesita una o dos condiciones adicionales en el método de recursión. No estoy seguro de qué hacer y realmente agradecería cualquier ayuda.

Si algo no está lo suficientemente claro, solo dilo y lo explicaré lo mejor que pueda. ¡Gracias!

Por supuesto, este no es el problema real al que me enfrento, es solo una pequeña demostración que podría ayudarme a resolver el problema real en el que estoy trabajando (que es un proyecto de Internet en tiempo real).


Basado en sus requisitos:

  • Dejando la función Locate(Rectangle scanArea) sin tocar.
  • Usando un algoritmo recursivo para escanear Izquierda / Abajo / Derecha (fig)

Presentaré un argumento extra de tipo Side a la función recursiva.

internal enum Side : byte 
{
    Left,
    Bottom,
    Right
}

Supongamos que usamos la parte Bottom como la dirección de "corte", luego podríamos aumentar la eficiencia (de volver a ensamblar los rectángulos cortados) creando una envoltura que almacene información adicional para los rectángulos que se encuentran en las bottomArea .

internal class RectangleInfo
{
    public RectangleInfo(Rectangle rect, bool leftOverlap, bool rightOverlap)
    {
        Rectangle = rect;
        LeftOverlap = leftOverlap;
        RightOverlap = rightOverlap;
    }
    public Rectangle Rectangle { get; set; }
    public bool LeftOverlap { get; set; }
    public bool RightOverlap { get; set; }
}

Para una búsqueda más rápida, también podría dividir los rectángulos cortados que se encuentran en leftArea s y rightArea s en listas separadas. Lo que convertiría su código de muestra en algo como:

List<Rectangle> difList = new List<Rectangle>();

List<Rectangle> leftList = new List<Rectangle>();
List<RectangleInfo> bottomList = new List<RectangleInfo>();
List<Rectangle> rightList = new List<Rectangle>();

private void AccumulateDifferences(Rectangle scanArea, Side direction)
{
    Rectangle foundRect = Locate(scanArea);
    if (foundRect == null)
        return; // stop the recursion.

    switch (direction)
    {
        case Side.Left:
            if (foundRect.X + foundRect.Width == scanArea.X + scanArea.Width)
                leftList.Add(foundRect);
            else difList.Add(foundRect);
            break;

        case Side.Bottom:
            bottomList.Add(new RectangleInfo(foundRect, foundRect.X == scanArea.X, foundRect.X + foundRect.Width == scanArea.X + scanArea.Width));
            break;

        case Side.Right:
            if (foundRect.X == scanArea.X)
                rightList.Add(foundRect);
            else difList.Add(foundRect);
            break;
    }
    Rectangle leftArea = new Rectangle(scanArea.X, foundRect.Y, (foundRect.X - scanArea.X), (scanArea.Y + scanArea.Height) - (foundRect.Y + foundRect.Height)); // define left area.
    Rectangle bottomArea = new Rectangle(foundRect.X, foundRect.Y + foundRect.Height, foundRect.Width, (scanArea.Y + scanArea.Height) - (foundRect.Y + foundRect.Height)); // define bottom area.
    Rectangle rightArea = new Rectangle(foundRect.X + foundRect.Width, foundRect.Y, (scanArea.X + scanArea.Width) - (foundRect.X + foundRect.Width), (scanArea.Y + scanArea.Height) - (foundRect.Y + foundRect.Height)); //define right area.

    AccumulateDifferences(leftArea, Side.Left);
    AccumulateDifferences(bottomArea, Side.Bottom);
    AccumulateDifferences(rightArea, Side.Right);
}

private void ProcessDifferences()
{
    foreach (RectangleInfo rectInfo in bottomList)
    {
        if (rectInfo.LeftOverlap)
        {
            Rectangle leftPart =
                leftList.Find(r => r.X + r.Width == rectInfo.Rectangle.X
                                   && r.Y == rectInfo.Rectangle.Y
                                   && r.Height == rectInfo.Rectangle.Height
                             );
            if (leftPart != null)
            {
                rectInfo.Rectangle.X = leftPart.X;
                leftList.Remove(leftPart);
            }
        }

        if (rectInfo.RightOverlap)
        {
            Rectangle rightPart =
                rightList.Find(r => r.X == rectInfo.Rectangle.X + rectInfo.Rectangle.Width
                                    && r.Y == rectInfo.Rectangle.Y
                                    && r.Height == rectInfo.Rectangle.Height
                              );
            if (rightPart != null)
            {
                rectInfo.Rectangle.X += rightPart.Width;
                rightList.Remove(rightPart);
            }
        }

        difList.Add(rectInfo.Rectangle);
    }

    difList.AddRange(leftList);
    difList.AddRange(rightList);
}

private void LocateDifferences(Rectangle scanArea)
{
    AccumulateDifferences(scanArea, Side.Left);
    ProcessDifferences();

    leftList.Clear();
    bottomList.Clear();
    rightList.Clear();
}

Encontrar rectángulos adyacentes

Es posible que existan varios rectángulos con los mismos valores de X en la rightList (o los valores de X + Width en la leftList ), por lo tanto, necesitamos verificar la intersección cuando se encuentra una posible coincidencia.

Dependiendo de la cantidad de elementos, también puede usar diccionarios (para una búsqueda más rápida) en el caso de la lista leftList y la lista rightList . Use el punto de intersección superior como clave y luego verifique la Height antes de fusionar.


El enfoque más simple para utilizar algoritmos simples como:

function find(Image): Collection of Rects
   core_rect = FindRects(Image)
   split(core_rect) -> 4 rectangles (left-top, left-bottom, right-top, right-bottom)
   return Merge of (find(leftTop), find(leftBottom), ...)

function findAll(Image): Collection of Rects
   rects <- find(Image)
   sort rectangles by X, Y
   merge rectangles
   sort rectangles by Y, X
   merge rectangles
   return merged set

La fusión de dos rectángulos debe ser bastante simple: deben tener un borde compartido. Pero el enfoque dado funcionaría solo en caso de que la imagen contenga rectángulos y solo rectángulos. En el caso de figuras geométricas más complejas, sería mejor utilizar un algoritmo de escaneo línea por línea para la detección de área y en la siguiente etapa de identificación del tipo de forma.


Le pido disculpas, pero no leí su solución porque no estoy seguro de si desea una buena solución o para solucionar el problema con esa solución.

Una solución simple que utiliza bloques de construcción existentes (como OpenCV, que no sé si tengo un puerto para c #) es:

  1. toma el canal rojo (porque dijiste que solo quieres detectar rectángulos rojos)
  2. findContours
  3. para cada contorno 3.1 tome su cuadro delimitador 3.2 compruebe si el contorno es un rectángulo comparando su área total con el área total del cuadro delimitador.

La solución cambiará dependiendo de la variedad de sus imágenes de entrada. Espero haberte ayudado. Si no, por favor dirígeme a qué tipo de ayuda quieres.


No hay necesidad de reinventar la rueda. Este es un problema de etiquetado de componentes conectados.

https://en.wikipedia.org/wiki/Connected-component_labeling

Hay varias formas de abordarlo. Una de ellas es codificar las filas de la imagen y encontrar las superposiciones de una fila a otra.

Otra es escanear la imagen y realizar un relleno de inundación cada vez que se encuentra con un píxel rojo (borra todo el rectángulo).

Otra más es escanear la imagen y realizar un seguimiento de contorno cuando se encuentra con un píxel rojo (y marca cada píxel de contorno para que el blob sea más procesado).

Todos estos métodos funcionarán para formas arbitrarias, y puede adaptarlas a la forma específica de sus rectángulos.


Realiza un escaneo de líneas por píxel, sobre una imagen.

si el píxel arriba es negro y el píxel izquierdo es negro, pero el píxel mismo es rojo, entonces tiene la esquina superior izquierda (x1, y1). vaya a la derecha hasta que vuelva a ser negro (arriba a la derecha y2 + 1) Vaya al final para encontrar el negro que es x2 + 1, de modo que pueda derivar a la derecha, abajo (x2, y2)

Almacene x1, y1, x2, y2 en una estructura de lista o clase pinte el rectángulo que acaba de encontrar en negro, y continúe escaneando líneas


Un algoritmo que puede encontrar múltiples rectángulos al escanear una imagen una vez no tiene que ser complicado. La principal diferencia con lo que estás haciendo ahora es que cuando encuentras la esquina superior de un rectángulo, no debes encontrar inmediatamente el ancho y la altura y almacenar el rectángulo, sino que debes mantenerlo en una lista de rectángulos sin terminar temporalmente, hasta que Te encuentras con su esquina inferior. Esta lista se puede usar para verificar de manera eficiente si cada píxel rojo es parte de un nuevo rectángulo, o si ya lo ha encontrado. Considera este ejemplo:

Comenzamos a escanear de arriba a abajo y de izquierda a derecha. En la línea 1, encontramos un píxel rojo en la posición 10; continuamos escaneando hasta que encontremos el próximo píxel negro (o lleguemos al final de la línea); ahora podemos almacenarlo en una lista de rectángulos sin terminar como {izquierda, derecha, arriba}:

unfinished: {10,13,1}  

Al escanear la siguiente línea, iteramos sobre la lista de rectángulos sin terminar, por lo que sabemos cuándo esperar un rectángulo. Cuando llegamos a la posición 10, encontramos un píxel rojo como se esperaba, y podemos saltar a la posición 14 e iterar más allá del rectángulo sin terminar. Cuando llegamos a la posición 16, encontramos un píxel rojo inesperado, y continuamos hasta el primer píxel negro en la posición 19, y luego agregamos este segundo rectángulo a la lista sin terminar:

unfinished: {10,13,1},{16,18,2}  

Después de haber escaneado las líneas 3 a 5, obtenemos esta lista:

unfinished: {1,4,3},{6,7,3},{10,13,1},{16,18,2},{21,214}  

Tenga en cuenta que insertamos rectángulos recién encontrados mientras estamos iterando sobre la lista (usando, por ejemplo, una lista enlazada), para que estén en orden de izquierda a derecha. De esa manera, solo tenemos que mirar un rectángulo sin terminar a la vez mientras escaneamos la imagen.

En la línea 6, después de pasar los dos primeros rectángulos sin terminar, encontramos un píxel negro inesperado en la posición 10; Ahora podemos eliminar el tercer rectángulo de la lista sin terminar, y agregarlo a una matriz de rectángulos completos como {izquierda, derecha, arriba, abajo}:

unfinished: {1,4,3},{6,7,3},{16,18,2},{21,21,4}  
finished: {10,13,1,5}  

Cuando llegamos al final de la línea 9, hemos completado todos los rectángulos que quedaron sin terminar después de la línea 5, pero hemos encontrado un nuevo rectángulo en la línea 7:

unfinished: {12,16,7}  
finished: {10,13,1,5},{16,18,2,5},{1,4,3,6},{6,7,3,8},{21,21,4,8}  

Si seguimos hasta el final, el resultado es:

unfinished:  
finished: {10,13,1,5},{16,18,2,5},{1,4,3,6},{6,7,3,8},{21,21,4,8},  
          {12,16,7,10},{3,10,10,13},{13,17,13,14},{19,22,11,14}  

Si quedan rectángulos sin terminar en este punto, bordean el borde inferior de la imagen y se pueden completar con bottom = height-1.

Tenga en cuenta que saltarse rectángulos sin terminar significa que solo tiene que escanear los píxeles negros y el borde superior e izquierdo de los rectángulos rojos; En el ejemplo omitimos más de 78 de los 384 píxeles.

Haga clic en [aquí] para ver una versión simple de C ++ en acción en rextester.com (lo siento, no hablo C #).

(Rextester parece haber sido pirateado en este momento, así que quité el enlace y pegué el código C ++ aquí).

#include <vector>
#include <list>
#include <iostream>

struct rectangle {int left, right, top, bottom;};

std::vector<rectangle> locate(std::vector<std::vector<int>> &image) {
    std::vector<rectangle> finished;
    std::list<rectangle> unfinished;
    std::list<rectangle>::iterator current;
    int height = image.size(), width = image.front().size();
    bool new_found = false;                  // in C++17 use std::optional<rectangle>new_rect and check new_rect.has_value()

    for (int y = 0; y < height; ++y) {
        current = unfinished.begin();        // iterate over unfinished rectangles left-to-right
        for (int x = 0; x < width; ++x) {
            if (image[y][x] == 1) {          // red pixel (1 in mock-up data)
                if (current != unfinished.end() && x == current->left) {
                    x = current->right;      // skip through unfinished rectangle
                    ++current;
                }
                else if (!new_found) {       // top left corner of new rectangle found
                    new_found = true;
                    current = unfinished.insert(current, rectangle());
                    current->left = x;
                }
            } else {                         // black pixel (0 in mock-up data)
                if (new_found) {             // top right corner of new rectangle found
                    new_found = false;
                    current->right = x - 1; current->top = y;
                    ++current;
                }
                else if (current != unfinished.end() && x == current->left) {
                    current->bottom = y - 1; // bottom of unfinished rectangle found
                    finished.push_back(std::move(*current));
                    current = unfinished.erase(current);
                }
            }
        } // if there is still a new_rect at this point, it borders the right edge
    } // if there are unfinished rectangles at this point, they border the bottom edge
    return std::move(finished);
}

int main() {
    std::vector<std::vector<int>> image { // mock-up for image data
        {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,0,0,1,1,1,1,0,0,0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,0,0,1,1,1,1,0,0,1,1,1,0,0,0,0,0},
        {0,1,1,1,1,0,1,1,0,0,1,1,1,1,0,0,1,1,1,0,0,0,0,0},
        {0,1,1,1,1,0,1,1,0,0,1,1,1,1,0,0,1,1,1,0,0,1,0,0},
        {0,1,1,1,1,0,1,1,0,0,1,1,1,1,0,0,1,1,1,0,0,1,0,0},
        {0,1,1,1,1,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0},
        {0,0,0,0,0,0,1,1,0,0,0,0,1,1,1,1,1,0,0,0,0,1,0,0},
        {0,0,0,0,0,0,1,1,0,0,0,0,1,1,1,1,1,0,0,0,0,1,0,0},
        {0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,0,0,0,0,0,0,0},
        {0,0,0,1,1,1,1,1,1,1,1,0,1,1,1,1,1,0,0,0,0,0,0,0},
        {0,0,0,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,1,1,1,1,0},
        {0,0,0,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,1,1,1,1,0},
        {0,0,0,1,1,1,1,1,1,1,1,0,0,1,1,1,1,1,0,1,1,1,1,0},
        {0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,0,1,1,1,1,0},
        {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}
    };

    std::vector<rectangle> rectangles = locate(image);
    std::cout << "left,right,top,bottom:\n";
    for (rectangle r : rectangles) {
        std::cout << (int) r.left << "," << (int) r.right << "," << (int) r.top << "," << (int) r.bottom << "\n";
    }

    return 0;
}

Si encuentra que la implementación de la lista enlazada de C # no es lo suficientemente rápida, podría usar dos matrices de ancho de imagen de longitud, y cuando encuentre la parte superior de un rectángulo entre las posiciones x1 y x2 en la línea y, almacene el rectángulo incompleto como ancho [x1] = x2-x1 y superior [x1] = y, y restablézcalos a cero cuando almacene el rectángulo completo.

Este método encontrará rectángulos tan pequeños como 1 píxel. Si hay un tamaño mínimo, puede escanear la imagen usando pasos más grandes; con un tamaño mínimo de 10x10, solo tendría que escanear alrededor del 1% de los píxeles.







computer-vision