Recadrage automatique de formes arbitraires

14

J'ai une forme arbitraire définie par un masque binaire (gris = forme, noir = fond).

Je voudrais trouver un plus grand rectangle possible contenant uniquement des pixels gris (ce rectangle est représenté en jaune):

entrez la description de l'image ici

La forme est toujours «monobloc» mais elle n'est pas nécessairement convexe (toutes les paires de points sur la frontière de la forme ne peuvent pas être reliées par une ligne droite passant par la forme).

Parfois, plusieurs de ces "rectangles maximaux" existent, puis d'autres contraintes peuvent être introduites, telles que:

  • Prendre le rectangle avec son centre le plus proche du centre de masse de la forme (ou centre de l'image)
  • Prendre un rectangle avec un rapport d'aspect le plus proche d'un rapport prédéfini (c.-à-d. 4: 3)

entrez la description de l'image ici

Ma première réflexion sur l'algorithme est la suivante:

  1. Calculer la transformation de distance de la forme et trouver son centre de masse
  2. Agrandir la zone carrée alors qu'elle ne contient que des pixels de forme
  3. Agrandir le rectangle (à l'origine un carré) en largeur ou en hauteur alors qu'il ne contient que des pixels de forme.

Cependant, je pense qu'un tel algorithme serait lent et ne conduirait pas à une solution optimale.

Aucune suggestion?

Libor
la source
@AtulIngle Extactly! Merci. Pourriez-vous ajouter la réponse pour que je puisse l'accepter? Je vais ensuite essayer de modifier la réponse pour en savoir plus sur l'algorithme - mais je ne veux pas simplement répondre à ma propre question en utilisant le lien que vous avez fourni ...
Libor
Génial! J'attends avec impatience de lire votre réponse élaborée car je n'ai pas lu le code.
Atul Ingle
@AtulIngle OK, j'ai ajouté une discussion dans la réponse et un lien vers un de mes articles complets.
Libor

Réponses:

10

Il existe un code sur Matlab Fileexchange qui est pertinent pour votre problème: http://www.mathworks.com/matlabcentral/fileexchange/28155-inscribedrectangle/content/html/Inscribed_Rectangle_demo.html

Mise à jour

J'ai écrit cet article tutoriel sur le calcul des plus grands rectangles inscrits sur la base du lien ci-dessus d'Atul Ingle.

L'algorithme recherche d'abord les plus grands carrés sur un masque binaire. Cela se fait à l'aide d'un algorithme de programmation dynamique simple. Chaque nouveau pixel est mis à jour en utilisant les trois voisins déjà connus:

squares[x,y] = min(squares[x+1,y], squares[x,y+1], squares[x+1,y+1]) + 1

entrez la description de l'image ici

L'exemple de masque binaire et la carte calculée ressemblent à ceci:

entrez la description de l'image ici entrez la description de l'image ici

Prendre le maximum sur la carte révèle le plus grand carré inscrit:

entrez la description de l'image ici

L'algorithme de recherche de rectangle analyse le masque deux fois de plus en recherchant deux classes de rectangles:

  • largeur supérieure à la taille du carré (et hauteur éventuellement plus petite)
  • hauteur supérieure à la taille du carré (et largeur éventuellement plus petite)

Les deux classes sont délimitées par les carrés les plus grands, car aucun rectangle à un point donné ne peut avoir les deux dimensions supérieures au carré inscrit (bien qu'une dimension puisse être plus grande).

Il faut choisir une métrique pour les tailles de rectangle, comme la surface, la circonférence ou la somme pondérée des dimensions.

Voici la carte résultante pour les rectangles:

entrez la description de l'image ici entrez la description de l'image ici

Il est pratique de stocker la position et la taille du meilleur rectangle trouvé jusqu'à présent dans une variable au lieu de créer des cartes, puis de rechercher des maxima.

entrez la description de l'image ici

L'application pratique de cet algorithme est le recadrage d'images non rectangulaires. J'ai utilisé cet algorithme dans ma bibliothèque d'assemblage d'images SharpStitch :

entrez la description de l'image ici

Atul Ingle
la source