Trouver des rectangles complets entourant 0

Question

Il y a divers rectangles dans des tableaux donnés de 1000 x 1000. en <Figure 1> la série "1" affichée en jaune est le motif du rectangle. La taille minimale du rectangle en <Figure 1> est 3 x 3 affiché comme cellule verte.

Il devrait y avoir au moins un '0' à l'intérieur du rectangle.

Mais, dans ce tableau, il existe aussi des formes non fermées ou des lignes droites.

(La valeur initiale du tableau est '0', et les motifs sont représentés par une série de '1'. Ils ne se chevauchent pas et ne sont pas inclus les uns dans les autres).

Quel pourrait être un algorithme efficace pour trouver les rectangles complets dans le tableau à l'exception des formes non fermées ou des lignes droites ? Par exemple, dans la figure ci-dessus, le nombre de rectangles complets est de 3.

Answer 1

C'est très simple. Si vous avez n carrés, vous pouvez compter les rectangles en O(n) .

Hypothèses :

• Les bords de chaque rectangle valide ne partagent aucune cellule avec un chemin non valide.
• Si un rectangle est à l'intérieur d'un autre, vous seriez heureux de les trouver

Vous auriez besoin d'une mémoire supplémentaire aussi grande que l'entrée. Appelons cela visited et l'initialiser avec 0.

Commençons par construire une fonction d'aide :

is_rectangle(square s)
    from s, go right while you see 1s and visited is 0
        mark them as 1 in visited
    if less than 3 steps
        return 0
    then, go down while you see 1s and visited is 0
        mark them as 1 in visited
    if less than 3 steps
        return 0
    then, go left while you see 1s and visited is 0
        mark them as 1 in visited
    if less than 3 steps
        return 0
    then, go up while you see 1s and visited is 0
        mark them as 1 in visited
    if then one above is not s
        return 0
    return 1

Cette fonction trace essentiellement les 1 dans les directions droite-bas-gauche-haut et vérifie si les conditions sont remplies (longueur d'au moins 3 et atteinte de la position de départ). Elle marque également les cases visitées.

La chose importante à noter à propos de cette fonction est qu'elle ne fonctionne correctement que si le carré initial est le coin supérieur gauche.

La solution à ce problème est simple :

num_rectangles = 0
initialize visited to 0 (rows x columns)
for r in rows
    for c in columns
        if visitied[r][c] or image[r][c] == 0
            continue
        num_rectangles += is_rectangle(<r,c>)
return num_rectangles

Voici comment l'algorithme s'exécute :

1. Partie ratée (et marquée) d'un mauvais rectangle

2. Trouvez (et marquez) un rectangle.

3. Échec sur une seule case (d'une ligne verticale)

4. Échec sur une seule case (d'une ligne verticale)

5. Échec sur une seule case (d'une ligne verticale)

6. Après de nombreuses étapes similaires, on a trouvé le rectangle suivant.

7. Et le rectangle suivant

8. Fin de l'algorithme

Answer 2

L'algorithme O(n) suivant fonctionnera sur toute matrice 2D de valeurs 0/1 (c'est-à-dire que les rectangles qui se croisent ou se chevauchent sont autorisés, tout comme les formes ouvertes ou fermées non rectangulaires arbitraires). La définition d'un rectangle que j'utilise ici est la suivante : "l'intérieur est entièrement constitué de cellules 0" (donc, par exemple, si un rectangle en contient entièrement un autre, seul le rectangle intérieur sera trouvé ; si des rectangles contenant des cellules doivent également être pris en compte, alors chaque rectangle trouvé peut être supprimé et l'algorithme recommencé). Il est basé sur l'observation que chaque cellule 0 peut se trouver à l'intérieur de au plus un 1-rectangle .

J'utilise la convention selon laquelle x = 0 est la position la plus à gauche et y = 0 est la position la plus en haut.

1. Trouvez le coin supérieur gauche. En commençant par la cellule en haut à gauche et en procédant de gauche à droite et de haut en bas, trouvez la prochaine cellule non visitée qui pourrait être le coin supérieur gauche d'un rectangle solide-0 : plus précisément, il doit s'agir d'une cellule 0 qui a des voisins à 1 cellule dans les positions SW, W, NW, N et NE, et des cellules 0 dans les 3 positions voisines restantes.
2. Trouvez le coin supérieur droit. Balayer les voisins à sa droite tant que ces cellules sont à 0 et ont un voisin N à 1 cellule.
3. Est-ce que ça pourrait être la ligne supérieure d'un rectangle solide de 0 ? Si la dernière cellule trouvée par la boucle ci-dessus avant qu'elle ne se termine est une cellule qui pourrait être la cellule supérieure droite d'un rectangle solide-0 (plus précisément une cellule 0 ayant des voisins de cellule 1 dans les cellules NW, N, NE, E et SE, et des cellules 0 dans les 3 positions restantes), alors nous avons établi à la fois la coordonnée y supérieure et la largeur exacte du rectangle solide-0. seule possibilité solide 0-rectangle qui utilise n'importe laquelle de ces cellules. Si la dernière cellule ne remplit pas les conditions du coin supérieur droit, alors aucune de ces cellules ne peut faire partie d'un rectangle solide à 0 : marquez-les comme visitées et allez à 1.
4. Appelez les coordonnées x de début et de fin de la bande de cellules 0 x1 et x2 ; appelez la position verticale y1.
5. Balayez vers le bas, une rangée à la fois. Définissez y2 = y1, et si la ligne entre x1 et x2 à la position verticale y2 peut faire partie du rectangle solide 0, incrémentez y2. Plus précisément, le test à chaque position verticale y2 est le suivant : les cellules à (x1 - 1, y2) et (x2 + 1, y2) doivent toutes deux valoir 1, et toutes les cellules intermédiaires doivent valoir 0.
6. Est-ce que ça pourrait être la rangée du bas d'un rectangle solide de 0 ? Si la dernière rangée trouvée par la boucle précédente avant qu'elle ne se termine est une rangée qui pourrait être la rangée inférieure d'un rectangle solide à 0 (plus précisément, il y a des cellules 1 sur tout le chemin de (x1 - 1, y2 + 1) à (x2 + 1, y2 + 1)), alors nous avons trouvé un rectangle solide à 0 complet entouré de cellules 1 : si sa taille est supérieure au plus grand découvert jusqu'à présent, alors enregistrez-le comme le nouveau plus grand rectangle. Sinon (s'il n'y a pas une rangée solide de 1-cellules dans la ligne suivante), aucune des 0-cellules examinées ne peut faire partie d'un quelconque 0-rectangle solide : marquez-les toutes comme visitées et allez à 1.

Answer 3

Si vous ne pouvez avoir que des formes rectangulaires dans votre tableau, cela équivaut à un problème classique de calcul sur des images binaires : il suffit d'appliquer un algorithme standard pour les composantes connectées. Vous n'étiquetez que les composantes connectées de 0, et vous les comptez.

Ver http://en.wikipedia.org/wiki/Connected-component_labeling par exemple. Ce type d'algorithme est assez simple sur les images mais prend un peu de mémoire (même taille que votre tableau d'entrée, de type short ou int). Attention à la connectivité : si vous choisissez la connectivité 4, vous compterez les rectangles fermés même si certains coins sont manquants. Mais l'algorithme est plus simple qu'avec une connectivité de 8.

Si vous pouvez obtenir des formes fermées plus complexes, il suffit d'ajouter un post-traitement : pour chaque composant connecté, comptez le nombre de pixels à l'intérieur de la boîte de délimitation du composant (si les deux nombres sont égaux, vous avez un rectangle).

Answer 4

J'y ai réfléchi un moment. Je suis arrivé à cette méthode :

1) éliminer tous les zéros sur les bords - changer leur valeur en 2

2) l'inondation remplit la matrice autour des 2s

il ne reste donc qu'une île de zéros, dont on peut maintenant tester la convexité. Donc pour chaque île :

3) recherchez l'étendue de la valeur 0 en X et Y - ce qui vous donne un rectangle intérieur potentiel.

4) si le rectangle intérieur contient un 1 OU le rectangle extérieur contient un 0, il faut remplir cette île avec des 2 car elle n'est pas convexe (donc pas un rectangle).

En supposant que vous puissiez trouver un bon algorithme de remplissage (pas comme le mien), cela devrait être efficace pour réduire rapidement l'espace de recherche.

Et maintenant, le code (désolé, c'est du Do dièse) :

using System;
using System.Collections.Generic;

namespace Test
{
class MainClass
{
    static private int [,] matrix = new int[,] {
        {0,0,0,0,0,0,0,0,1,1,1,1,0,0,0},
        {0,1,1,1,1,1,1,0,1,0,0,1,0,1,0},
        {0,1,0,0,0,0,1,0,1,0,0,1,0,1,0},
        {0,1,0,0,0,0,1,0,1,0,0,1,0,1,0},
        {0,1,0,0,0,0,1,0,1,0,0,0,0,1,0},
        {0,1,0,0,0,0,1,0,1,0,0,0,0,1,0},
        {0,1,1,1,1,1,1,0,1,0,0,1,0,1,0},
        {0,0,0,0,0,0,0,0,1,1,1,1,0,0,0},
        {0,0,1,1,1,1,0,0,0,0,0,0,0,0,0},
        {0,0,1,0,0,1,0,0,1,1,1,0,1,1,0},
        {0,0,1,1,1,1,0,0,1,0,1,0,0,0,0},
        {0,0,0,0,0,0,0,0,1,1,1,0,0,0,0}
    };

    static private int width = matrix.GetLength(0);
    static private int height = matrix.GetLength(1);

    private const int DEAD = 2;
    private const int RECT = 3;

    public static void Main (string[] args)
    {
        //width = matrix.GetLength(0);
        //height = matrix.GetLength(1);

        PrintMatrix ();
        EliminateFromEdges (DEAD);
        PrintMatrix ();
        FloodFill (DEAD); // very inefficient - find a better floodfill algorithm
        PrintMatrix ();

        // test each island of zeros for convexness
        for (int i = 0; i < width; i++) {
            for (int j = 0; j < height; j++) {
                if (matrix[i,j] == 0)
                {
                    if (TestIsland(i,j) == false)
                    {
                        // eliminate this island as it is not convex
                        matrix[i,j] = DEAD;
                        FloodFill(DEAD);
                        PrintMatrix ();
                    }
                    else
                    {
                        // flag this rectangle as such
                        matrix[i,j] = RECT;
                        FloodFill(RECT);
                        PrintMatrix ();
                    }
                }
            }
        }

        // We're done, anything flagged as RECT can be expanded to yield the rectangles
        PrintMatrix ();
    }

    // flag any zero at edge of matrix as 'dead'
    static private void EliminateFromEdges(int value)
    {
        for (int i = 0; i < width; i++) 
        {
            if (matrix [i, 0] == 0) 
            {
                matrix [i, 0] = value;
            }
            if (matrix [i, height - 1] == 0)
            {
                matrix [i, height - 1] = value;
            }
        }
        for (int j = 1; j < height - 1; j++)
        {
            if (matrix [0, j] == 0)
            {
                matrix [0, j] = value;
            }
            if (matrix [width - 1, j] == 0)
            {
                matrix [width - 1, j] = value;
            }
        }
    }

    // propagte a value to neighbouring cells
    static private void FloodFill (int value)
    {
        bool change_made = true; // set to true to start things off
        while (change_made) {
            change_made = false;
            for (int i = 1; i < width - 1; i++) {
                for (int j = 1; j < height - 1; j++) {
                    if ((matrix [i, j] == 0) &&
                        ((matrix [i - 1, j] == value) || 
                        (matrix [i + 1, j] == value) ||
                        (matrix [i, j - 1] == value) || 
                        (matrix [i, j + 1] == value))) {
                        matrix [i, j] = value;
                        change_made = true;
                    }
                }
            }
        }
    }

    static private bool TestIsland (int x, int y)
    {
        // find convex extend of island
        int x2 = x;
        int y2 = y;
        while (matrix[++x2, y] == 0);
        x2--;
        while (matrix[x,++y2] == 0);
        y2--;

        // check inner cells (want all zeroes)
        for (int i = x; i <= x2; i++) 
        {
            for (int j = y; j <= y2; j++) 
            {
                if (matrix[i,y] != 0)
                {
                    return false;
                }
            }
        }

        // check surrounding cells (want all ones)
        x--; y--;
        x2++; y2++;
        for (int i = x; i <= x2; i++) 
        {
            if ((matrix[i,y] != 1) || (matrix[i,y2] != 1))
            {
                return false;
            }
        }
        for (int j = y + 1; j <= y2 - 1; j++) 
        {
            if ((matrix[x,j] != 1) || (matrix[x2,j] != 1))
            {
                return false;
            }
        }

        return true;
    }

    // for debug purposes
    static private void PrintMatrix ()
    {
        for (int i = 0; i < width; i++) {
            for (int j = 0; j < height; j++) {
                switch(matrix[i,j])
                {
                case DEAD:
                    Console.Write("-");
                    break;
                case RECT:
                    Console.Write("+");
                    break;
                default:
                    Console.Write(matrix[i,j]);
                    break;
                }
            }
            Console.WriteLine();
        }
        Console.WriteLine();
    }
}
}

La sortie de ce code

000000001111000
011111101001010
010000101001010
010000101001010
010000101000010
010000101000010
011111101001010
000000001111000
001111000000000
001001001110110
001111001010000
000000001110000

--------1111---
-1111110100101-
-1000010100101-
-1000010100101-
-1000010100001-
-1000010100001-
-1111110100101-
-0000000111100-
-0111100000000-
-0100100111011-
-0111100101000-
--------111----

--------1111---
-111111-1--1-1-
-100001-1--1-1-
-100001-1--1-1-
-100001-1----1-
-100001-1----1-
-111111-1--1-1-
--------1111---
--1111---------
--1001--111-11-
--1111--101----
--------111----

--------1111---
-111111-1--1-1-
-1++++1-1--1-1-
-1++++1-1--1-1-
-1++++1-1----1-
-1++++1-1----1-
-111111-1--1-1-
--------1111---
--1111---------
--1001--111-11-
--1111--101----
--------111----

--------1111---
-111111-1--1-1-
-1++++1-1--1-1-
-1++++1-1--1-1-
-1++++1-1----1-
-1++++1-1----1-
-111111-1--1-1-
--------1111---
--1111---------
--1++1--111-11-
--1111--101----
--------111----

--------1111---
-111111-1--1-1-
-1++++1-1--1-1-
-1++++1-1--1-1-
-1++++1-1----1-
-1++++1-1----1-
-111111-1--1-1-
--------1111---
--1111---------
--1++1--111-11-
--1111--1+1----
--------111----

--------1111---
-111111-1--1-1-
-1++++1-1--1-1-
-1++++1-1--1-1-
-1++++1-1----1-
-1++++1-1----1-
-111111-1--1-1-
--------1111---
--1111---------
--1++1--111-11-
--1111--1+1----
--------111----

Answer 5

C'est ce que je pense, ça pourrait être assez inefficace en termes de ressources. Je ne suis pas sûr de ça.

1. Traversez une rangée jusqu'à ce que vous trouviez un minimum de 3. 1 s.
2. Traverse vers le bas et fais boolean & opération avec les lignes ci-dessous --> elles devraient donner le format suivant 100..001 si c'est un rectangle valide. (En supposant que vous puissiez faire toutes les boolean opérations)
3. Vous avez trouvé un rectangle lorsque vous avez trouvé au moins une ligne à l'étape 2, et enfin toutes les lignes de l'étape 3. 1 s.
4. Répétez avec l'élément suivant de la rangée !