Trouver la plus grande zone noire convexe d’une image

J’ai une image dont voici une petite découpe:

Image avec beaucoup de pixels blancs et noirs

Comme vous pouvez le voir, ce sont des pixels blancs sur fond noir. Nous pouvons tracer des lignes imaginaires entre ces pixels (ou mieux, des points). Avec ces lignes, nous pouvons inclure des zones.

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

Voici un petit exemple dessiné à la main de ce que je veux dire par la plus grande zone noire convexe:

Petit exemple

PS: l’image n’est pas du bruit, elle représente les nombres premiers sous 10000000 classés horizontalement.

Je vais dessiner un algorithme correct, poly-time. Sans aucun doute, des améliorations structurelles des données doivent être apscopes, 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 borne supérieure ad hoc sur les dimensions de la boîte contenant les données). polygone).

La boucle principale consiste à deviner le point le plus bas p du plus grand polygone convexe (en coupant les liens en faveur du point le plus à gauche) et à calculer le plus grand polygone convexe pouvant être avec p et les points q tels que (qy> py) || (qy == py && qx> px).

Le programme dynamic repose sur les mêmes faits géomésortingques que le scan de Graham . Supposons sans perte de généralité que p = (0, 0) et sortinge les points q dans l’ordre anti-horaire qu’ils font avec l’axe des abscisses (comparez deux points en considérant le signe de leur produit scalaire). Soit les points dans l’ordre sortingé q 1 ,…, q n . Soit q 0 = p. Pour chaque 0 ≤ i 0 , un sous-ensemble de q 1 ,…, 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 zone zéro q 0 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 faire cela? En premier lieu, le sortingangle q 0 q i q j ne doit pas contenir d’autres points. L’autre condition est que l’angle q k q i q j vaut mieux ne pas être un virage à droite (encore une fois, vérifiez le signe du produit scalaire approprié).

À la fin, renvoyez le plus grand polygone trouvé. Pourquoi ça marche? Il n’est pas difficile de prouver que les polygones convexes ont la sous-structure optimale requirejse par le programme dynamic et que le programme considère exactement les polygones satisfaisant à la caractérisation de la convexité par Graham.

Essayer de trouver une zone convexe maximale est une tâche difficile à accomplir. Ne seriez-vous pas d’accord pour trouver des rectangles avec une surface maximale? Ce problème est beaucoup plus facile et peut être résolu en O (n) – temps linéaire en nombre de pixels. L’algorithme suit.

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

entrer la description de l'image ici

Vous pouvez le faire très efficacement par un algorithme linéaire à deux passes (n étant le nombre de pixels):

1) dans une première passe , passez par colonnes, de bas en haut, et pour chaque pixel, indiquez le nombre de pixels consécutifs disponibles jusqu’à celui-ci:

entrer la description de l'image ici

Répète jusqu’à:

entrer la description de l'image ici

2) dans une seconde passe , passez par rangées, lisez current_number . Pour chaque nombre k notez les sums des nombres consécutifs qui étaient >= k (c.-à-d. Des rectangles potentiels de hauteur k ). Fermez les sums (rectangles de potentiel) pour k > current_number et regardez si la sum (zone ~ rectangle) est supérieure au maximum actuel – si oui, mettez à jour le maximum. À la fin de chaque ligne, fermez tous les rectangles potentiels ouverts (pour tous les k ).

De cette façon, vous obtiendrez tous les rectangles maximum. Ce n’est pas la même chose que la zone convexe maximale bien sûr, mais cela vous donnerait probablement quelques indices (quelques heuristiques) sur la recherche de zones convexes maximales.

Vous pouvez essayer de traiter les pixels comme des sumts et effectuer une sortingangulation de Delaunay du point. Ensuite, vous devrez trouver le plus grand ensemble de sortingangles connectés qui ne crée pas une forme concave et n’a pas de sumts internes.

Si je comprends votre problème correctement, il s’agit d’une instance d’étiquetage des composants connectés. Vous pouvez par exemple commencer à: http://en.wikipedia.org/wiki/Connected-component_labeling

J’ai pensé à une approche pour résoudre ce problème:

Tous les points génèrent tous les sous-ensembles à 3 points possibles. Ceci est un ensemble de tous les sortingangles dans votre espace. À partir de cet ensemble, supprimez tous les sortingangles contenant un autre point et vous obtenez l’ensemble de tous les sortingangles vides.

Pour chacun des sortingangles vides, vous le feriez alors à sa taille maximale. En d’autres termes, pour chaque point en dehors du rectangle, insérez-le entre les deux points les plus proches du polygone et vérifiez s’il y a des points dans ce nouveau sortingangle. Sinon, vous vous souviendrez de ce point et de la zone ajoutée. Pour chaque nouveau point, vous voulez append celui qui maximise la zone ajoutée. Lorsque plus aucun point ne peut être ajouté, le polygone convexe maximum a été construit. Enregistrez la superficie de chaque polygone et souvenez-vous de celle qui a la plus grande surface.

Ce qui est essentiel à la performance de cet algorithme est votre capacité à déterminer a) si un point est situé dans un sortingangle et b) si le polygone rest convexe après l’ajout d’un certain point.

Je pense que vous pouvez réduire b) pour être un problème de a) et ensuite il vous suffit de trouver la méthode la plus efficace pour déterminer si un point est dans un sortingangle. La réduction de l’espace de recherche peut être réalisée comme suit: Prenez un sortingangle et augmentez tous les bords à une longueur infinie dans les deux directions. Cela sépare la zone en dehors du sortingangle en 6 sous-régions. Ce qui est bien pour nous, c’est que seulement trois de ces sous-régions peuvent contenir des points qui adhèrent à la contrainte de convexité. Ainsi, pour chaque point que vous testez, vous devez déterminer s’il se trouve dans une sous-région à expansion convexe, ce qui est encore une fois la question de savoir si elle se trouve dans un certain sortingangle.

À mesure qu’il évolue et s’approche de la forme d’un cercle, le polygone entier aura des régions de plus en plus petites qui permettent toujours une expansion convexe. Un point une fois dans une région concave ne fera plus partie de la zone d’expansion convexe, vous pouvez donc réduire rapidement le nombre de points à prendre en compte pour l’expansion. De plus, tout en testant des points d’expansion, vous pouvez réduire davantage la liste des points possibles. Si un point est testé faux, alors il se trouve dans la sous-région concave d’un autre point et, par conséquent, il n’est pas nécessaire de prendre en compte tous les autres points de la sous-région concave des points testés. Vous devriez pouvoir réduire très rapidement une liste de points possibles.

Cependant, vous devez le faire pour chaque sortingangle vide bien sûr.

Malheureusement, je ne peux pas garantir qu’en ajoutant toujours la nouvelle région maximale, votre polygone devienne le polygone maximum possible.