Plus Grand Carré Blanc

La représentation et l'analyse des formes sont des tâches cruciales pour une grande variété d'applications, notamment l'interprétation des scènes vidéo, la vidéosurveillance, la classification automatique des objets, le contrôle de la qualité, etc. Ainsi, des travaux sont en cours pour représenter des formes par l'ensemble de tous les rectangles maximaux qui peuvent être calés à l'intérieur de la forme.

Cette représentation a déjà été utilisée avec succès pour des tâches d'apprentissage machine.

Le Plus Grand Carré Blanc

Problématique

Étant donné une image monochrome de dimensions $n \times n$, identifier le (ou les) plus grand(s) carré(s) blanc(s) dans cette image, c'est-à-dire des carrés qui ne contiennent aucun pixel noir.

Par exemple, si l'on considère cette image de dimensions $100 \times 100$ :

Alors, le plus grand carré blanc dans cette image a pour dimension $10 \times 10$ et les coordonnées du pixel dans le coin haut/gauche sont (73, 54).

Cahier des charges

• Les images considérées seront toujours carrées : leur largeur et leur hauteur sont égales.
• Ces images seront au format L de nuances de gris. Par conséquent, la composante couleur d'un pixel noir sera 0 tandis que la composante couleur d'un pixel blanc sera 255.
• Les programmes de recherche de ces Plus Grands Carrés Blancs devront renvoyer un couple constitué :
  • La longueur d'un côté de ces carrés (en pixels) ;
  • La liste des coordonnées des pixels du coin haut/gauche de ces carrés :
    
• Des exemples sont régulièrement proposés au cours de ce travail. Le programme Creations_Images.py vous permettra de générer vos propres images et d'effectuer des tests supplémentaires.

Remarque importante

Les images que vous verrez à l'écran sont généralement des « agrandissements » des images sur lesquels vous allez travailler. Par exemple, l'originale de la première image : est en fait : . Peu visible, n'est-ce pas ?