Trouver la plus grande zone noire convexe dans une image

Question

J'ai une image dont ceci est une petite coupe :

Comme vous pouvez le voir, il s'agit de pixels blancs sur un fond noir. Nous pouvons tracer des lignes imaginaires entre ces pixels (ou mieux, ces points). Ces lignes permettent de délimiter des zones.

Comment trouver la plus grande convexo Quelle est la zone noire de cette image qui ne contient pas de pixel blanc ?

Voici un petit exemple dessiné à la main de ce que j'entends par la plus grande zone noire convexe :

P.S. : L'image n'est pas un bruit, elle représente les nombres premiers inférieurs à 10000000 classés horizontalement.

Answer 1

Je vais esquisser un algorithme correct et polytemporel. Il y a sans aucun doute des améliorations à apporter à la structure des données, mais je pense qu'une meilleure compréhension de ce problème en particulier sera nécessaire pour rechercher de très grands ensembles de données (ou, peut-être, une limite supérieure ad hoc sur les dimensions de la boîte contenant le polygone).

La boucle principale consiste à deviner le point p le plus bas dans le plus grand polygone convexe (en départageant les égalités en faveur du point le plus à gauche), puis à calculer le plus grand polygone convexe possible avec p et des points q tels que (q.y > p.y) || (q.y == p.y && q.x > p.x).

Le programme dynamique s'appuie sur les mêmes faits géométriques que Le scanner de Graham . Supposons sans perte de généralité que p = (0, 0) et classons les points q dans l'ordre de l'angle qu'ils font avec l'axe des x dans le sens inverse des aiguilles d'une montre (comparez deux points en considérant le signe de leur produit de points). Soit les points dans l'ordre trié q ₁ , , q _n . Soit q ₀ \= p. Pour chaque 0 ≤ i < j ≤ n, nous allons calculer le plus grand polygone convexe sur les points q ₀ un sous-ensemble de q ₁ , , q _{i - 1} , q _i et q _j .

Les cas de base où i = 0 sont faciles, puisque le seul "polygone" est le segment de surface nulle q ₀ q _j . Inductivement, pour calculer l'entrée (i, j), nous allons essayer, pour tout 0 ≤ k ≤ i, d'étendre le polygone (k, i) avec (i, j). Quand pouvons-nous le faire ? En premier lieu, le triangle q ₀ q _i q _j ne doit pas contenir d'autres points. L'autre condition est que l'angle q _k q _i q _j n'a pas intérêt à être un virage à droite (une fois de plus, vérifiez le signe du produit de points approprié).

A la fin, renvoyer le plus grand polygone trouvé. Pourquoi cela fonctionne-t-il ? Il n'est pas difficile de prouver que les polygones convexes ont la sous-structure optimale requise par le programme dynamique et que le programme considère exactement les polygones qui satisfont la caractérisation de Graham de la convexité.

Answer 2

Il est difficile de trouver la surface convexe maximale. Ne vous contenteriez-vous pas de trouver rectangles avec une surface maximale ? Ce problème est beaucoup plus simple et peut être résolu en O(n) - temps linéaire en nombre de pixels. L'algorithme est le suivant.

Disons que vous voulez trouver le plus grand rectangle de pixels libres (blancs) (Désolé, j'ai des images avec des couleurs différentes - le blanc est équivalent à votre noir, le gris est équivalent à votre blanc).

Vous pouvez le faire de manière très efficace par deux moyens linéaire O(n) temps (n étant le nombre de pixels) :

1) lors d'un premier passage Pour chaque pixel, indiquer le nombre de pixels consécutifs disponibles jusqu'à celui-ci :

répéter, jusqu'à ce que :

2) lors d'un second passage , aller par rangs, lire current_number . Pour chaque nombre k garder la trace des sommes des nombres consécutifs qui ont été >= k (c'est-à-dire des rectangles potentiels de hauteur k ). Fermer les sommes (rectangles potentiels) pour k > current_number et regarder si la somme (~ surface du rectangle) est supérieure au maximum actuel - si oui, mettre à jour le maximum. À la fin de chaque ligne, fermer tous les rectangles potentiels ouverts (pour tous les k ).

Vous obtiendrez ainsi tous les rectangles maximums. Ce n'est pas la même chose que la surface convexe maximale, bien sûr, mais cela vous donnera probablement des indications (une certaine heuristique) sur l'endroit où chercher les surfaces convexes maximales.

Answer 3

Vous pouvez essayer de traiter les pixels comme des sommets et d'effectuer les opérations suivantes Triangulation de Delaunay de l'ensemble de points. Vous devez ensuite trouver le plus grand ensemble de triangles connectés qui ne crée pas de forme concave et qui n'a pas de sommets internes.

Answer 4

Si je comprends bien votre problème, il s'agit d'une instance de Connected Component Labeling. Vous pouvez commencer par un exemple à l'adresse suivante http://en.wikipedia.org/wiki/Connected-component_labeling

Answer 5

Je pense que la première étape consiste à créer une fonction qui, à partir d'un pixel, renvoie la zone noire de ce pixel :

int blackArea(Pixel* pixel, PixelArray* outputArray)
    {
    int area = -1;
    if (pixel.color == whitePixel)
    {
         return area;
    }
    else //it is black
    {
        // use the definition you gave on your answer and implement it on code so 
        // that you save the area value here. Save the pixels that are boundary of your area in the "outputArray".

        return area;
    }
}

Une méthode appropriée consisterait à utiliser la fonction blackArea pour trouver la limite de la zone qu'elle calcule. Vous effectuerez ensuite un cycle for pour tous les pixels, mais pendant que vous effectuez le for, vous ne calculez pas les pixels qui se trouvent à l'intérieur des limites, car vous avez déjà obtenu leur surface.

La plus grande zone peut être sauvegardée pendant le cycle for, et le tableau avec ses limites également, de sorte que vous avez la réponse à votre problème.

Compte tenu de cela, je pense que ce problème équivaut à trouver la plus grande surface d'une couleur donnée d'une image. La définition de la limite et de la couleur est cependant un peu différente.

J'espère que cela vous aidera