X ENS Informatique Commune PSI PT 2011Sujet et corrigé

Pas encore noté

Représentation matricielle des images numériques
Manipulation de tableaux et de matrices
Histogrammes et statistiques descriptives
Algorithmique et fonctions
Seuillage et tramage d'images

Explorer les annales

BanqueX-ENS Année2011 FilièrePSI/PT MatièreInformatique

Annales X-ENS PSI/PT Informatique X-ENS PSI/PT 2011 PSI/PT Informatique Informatique 2011

Téléchargements

Télécharger le sujet (PDF)

Corrigé (Maple)

Corrigé 2 (Python)

Lire en ligne LaTeX Word

Rapport du jury : non disponible

Présentation du sujet

Traitement d'images en teintes de gris : opérations élémentaires, transferts et tramage

Le sujet de programmation étudie le traitement d'images en teintes de gris sous forme de matrices d'entiers. La partie I programme des opérations géométriques élémentaires (inversion, symétrie, juxtaposition). La partie II programme des fonctions de transfert des tons (histogramme, égalisation, réduction de profondeur). La partie III programme le tramage, conversion en noir et blanc par seuillage selon un motif répété.

1Partie I : opérations élémentairesÉcriture de fonctions inverser, flipH, poserV et poserH réalisant respectivement l'inversion des tons, une symétrie axiale et la juxtaposition verticale ou horizontale de deux images.
2Partie II : transfertsÉcriture d'une fonction générique de transfert des tons via une table de correspondance, puis construction de l'histogramme d'une image, de l'égalisation de ses tons et de la réduction de sa profondeur.
3Partie III : tramageÉcriture de fonctions de seuillage d'une image selon un motif répété (trame), notamment une trame diagonale, pour produire une image en noir et blanc de meilleur rendu visuel qu'un simple seuillage uniforme.

Ces sujets peuvent vous intéresser

Lecture du sujet en ligne

L'énoncé complet, avec les formules et les figures, sans ouvrir le PDF.

Sujet en PDF

ÉCOLE POLYTECHNIQUE

filières PSI et PT

ÉPREUVE D'INFORMATIQUE

(Durée : 2 heures)

L'utilisation des calculatrices n'est pas autorisée pour cette épreuve.
Le langage de programmation choisi par le candidat doit être spécifié en tête de la copie.
On attachera une grande importance à la concision, à la clarté, et à la précision de la rédaction.

Images en gris

Les ordinateurs et de nombreux dispositifs électroniques (caméras numériques, écrans, etc.) représentent les images comme des ma-

Image A

trices de nombres entiers. Dans ce problème, on se limite aux images rectangulaires en teintes de gris.

En machine, une telle image est la donnée d'une hauteur

H

, d'une largeur

L

, et d'une matrice

M

d'entiers de

H

lignes et

L

colonnes. L'image est divisée en éléments ou pixels définis par leurs numéros de ligne

ℓ

et de colonne

c

. Chaque entier de la matrice définit le ton de gris associé au pixel de coordonnées (

ℓ, c

). Ce ton varie entre zéro, qui rend l'absence de lumière et donc le noir, et une valeur maximale dite profondeur

P

qui rend le blanc. Les valeurs intermédiaires rendent diverses teintes de gris de plus en plus claires. On notera que le pixel de coordonnées

(0, 0)

est conventionellement situé en haut et à gauche de l'image.

Par exemple, pour cette image

◻

, une échelle de 16 teintes de gris allant du noir au blanc, on a

H = 1, L = 16, P = 15

M

ne possède qu'une seule ligne qui contient les 16 entiers de 0 à 15 en ordre croissant.

Quel que soit le langage dans lequel ils composent, les candidats créeront une image par l'appel de primitive allouer(

H, L, P

). On accédera aux composants d'une image

i

par les notations

i.H

(hauteur),

i.L

(largeur), i.P (profondeur) et

i.M

(matrice). Dans l'énoncé, on accédera aux éléments de la matrice par la notation

i.M[ℓ, c]

, sachant que les indices commencent à zéro - un indice de ligne est donc un entier

ℓ

compris entre 0 et

H - 1

au sens large, tandis qu'un indice de colonne est un entier

c

compris entre 0 et

L - 1

au sens large. Enfin les candidats qui choisissent de composer dans un langage typé pourront supposer l'existence d'un type image des images.

Partie I. Opérations élémentaires

Fig. 1: Opérations élémentaires

Question 1 Écrire une fonction inverser(

i

) qui renvoie l'image inverse de

i

. C'est-à-dire que le ton d'un pixel de la nouvelle image est

i.P - v

, où

v

est le ton du pixel correspondant de l'image d'origine. Par exemple, l'image B de la figure 1 résulte de l'application de inverser à l'image A de l'introduction.

Question 2 Écrire une fonction flipH

(i)

qui renvoie la transformée de l'image

i

par la symétrie d'axe vertical passant par le milieu de l'image. Par exemple, l'image C de la figure 1 résulte de l'application de flipH à l'image A de l'introduction.

Question 3 Écrire une fonction poserV

(i_1, i_2)

qui prend en arguments deux images

i_1

i_2

de même largeur et profondeur, et qui renvoie la nouvelle image obtenue en posant

i_1

sur

i_2

. Par exemple, l'image D de la figure 1 résulte de l'application de poserV aux images B et C .

Question 4 Écrire une fonction poserH(

i_1, i_2

) qui prend en arguments deux images

i_1

i_2

de même hauteur et profondeur, et qui renvoie la nouvelle image obtenue en posant

i_2

à droite de

i_1

. Par exemple, l'image E de la figure 1 résulte de l'application de poserH aux images B et C .

Partie II. Transferts

Certaines transformations des images sont simplement l'application d'une fonction aux tons, dont on rappelle qu'ils sont des entiers compris entre 0 et

P

(profondeur de l'image) au sens large. Une telle fonction de transfert peut s'appliquer vers des images dont la profondeur n'est pas nécessairement

P

, mais une nouvelle profondeur. Une fonction de transfert est représentée par la donnée de la profondeur cible

P^'

et d'un tableau d'entiers

t

de taille

P + 1

, dont les cases contiennent des entiers entre 0 et

P^'

au sens large.

Question 5 Écrire une fonction transferer

(i, P^', t)

qui prend en arguments une image

i

, ainsi qu'une fonction de transfert donnée par un entier

P^'

et un tableau d'entiers

t

. La fonction transferer renvoie une nouvelle image, de même taille que

i

, de nouvelle profondeur

P^'

et dont chaque pixel (

ℓ, c

) a pour ton

t[i.M[ℓ, c]]

Question 6 Écrire une nouvelle fonction inverser (Question 1) qui utilise la fonction transferer de la question précédente.

Fig. 2: Transferts

L'histogramme d'une image de profondeur

P

est un tableau

h

d'entiers de taille

P + 1

tel que

h[v]

compte le nombre de pixels de l'image dont le ton est

v

Question 7 Écrire une fonction histogramme

(i, h)

qui prend en arguments une image

i

et un tableau d'entiers

h

correctement dimensionné, et qui affecte les cases de

h

pour en faire l'histogramme de

i

. On notera que le contenu initial des cases de

h

est inconnu.

Soit

i

une image de hauteur

H

, de largeur

L

et de profondeur

P

. Soit

h

son histogramme et soit

v_(min)

le ton de gris le plus sombre se trouvant dans l'image

i

. On égalise les tons en transformant chaque ton

v

v^'

défini ainsi :

v^' = P \times ((\sum_(k = 0)^(k = v)h[k]) - h[v_(min)])/(H \times L - h[v_(min)]), pour v_(min) \leq v \leq P.

On note que

v^'

n'est pas défini pour

v

tel que

0 \leq v < v_(min)

, ce qui n'a pas d'importance, ces tons

v

étant absents de l'image. On note surtout que la valeur de

v^'

ci-dessus n'est généralement pas un entier. Les candidats seront attentifs à cette difficulté, qu'ils résoudront dans le langage choisi. Ils pourront utiliser la primitive arrondir(

x

) qui prend un nombre flottant

x

ou un rationnel en argument et renvoie l'entier le plus proche de

x

Question 8 Écrire la fonction egaliser(i) qui prend une image

i

en argument et qui renvoie une nouvelle image qui est

i

dont les tons de gris sont égalisés. Par exemple, l'image F de la figure 2 résulte de l'application de egaliser à l'image A.

Question 9 Que renvoie la fonction egaliser appliquée à une image uniformément blanche?

On cherche maintenant à réduire la profondeur d'une image de

P

vers

P^'

, avec

P^' \leq P

. Une technique consiste à remplacer un ton

v

par

v^'

, tel que

v^'/P^'

est le plus proche possible de

v/P

Question 10 Écrire une fonction reduire(

i, P^'

) qui renvoie une nouvelle image qui est

i

dont la profondeur est réduite à

P^'

. Par exemple, les images

G, H

et I de la figure 2 résultent des réductions à 1,4 et 16 de la profondeur de l'image A,

Partie III. Tramage

Fig. 3: Tramage

Lorsqu'il s'agit d'imprimer nos images, on se retrouve confronté à une difficulté : l'encre est noire, le papier est blanc. Il faut donc transformer les images en tons de gris en images en noir et blanc au sens strict. L'appel reduire

(i, 1)

est un moyen de procéder, toutefois le résultat n'est pas très satisfaisant - voir l'image G de la figure 2. Cette partie examine la technique du tramage qui produit des images en noir et blanc (c'est-à-dire de profondeur 1) plus plaisantes, telles les images

L, M

et N de la figure 3.

On peut voir l'image G comme produite par seuillage, les tons de gris plus grands qu'un certain seuil deviennent blancs, tandis que les autres deviennent noirs. Une idée pour améliorer le rendu des images consiste à faire varier le seuil selon les pixels. Cela revient à représenter les seuils par une matrice, en fait par une image que l'on appelle une trame. Une trame est le plus souvent constituée par la répétition d'une petite image, dite motif, répétition selon les axes de coordonnées qui finit par paver toute l'image Par la suite, le seuillage selon une trame sera simplement désigné comme le seuillage selon le motif dont dérive cette trame.

Par exemple, l'image J de la figure 3 est une échelle de gris verticale de profondeur 3 (

H = 4

L = 1, P = 3

et la matrice

M

est un vecteur colonne contenant les entiers de 0 à 3 du haut vers le bas). Sa répétition produit l'image K. On notera que l'image J est présentée agrandie par rapport à l'image K . Le motif J est adéquat pour seuiller les images de profondeur 4, par exemple l'image H de la figure 2, ce qui donne l'image L de la figure 3.

Question 11 Écrire une fonction tramer

(i, m)

qui prend deux images

i

m

en arguments, et qui renvoie l'image de profondeur 1 obtenue en seuillant l'image

i

selon le motif

m

. Le seuillage est défini précisément ainsi : étant donnés un ton

v

de l'image et un ton

w

de la trame, on obtient un pixel blanc si et seulement si

v > w

, et un pixel noir sinon.

Question 12 Écrire une fonction tramerTelevision

(i)

qui prend en argument une image

i

de profondeur

P

, et qui renvoie l'image de profondeur 1 obtenue en seuillant l'image

i

selon l'échelle de gris verticale de profondeur

P - 1

En imprimerie on utilise rarement des trames constituées de lignes horizontales comme la trame

K

. On préfère les trames constituées de lignes inclinées de points, ou trames diagonales. On obtient une trame diagonale de profondeur 15 par répétition du motif

16 \times 16

représenté ci-dessous, à droite :

(1, 5, 10, 14; 3, 7, 8, 12; 13, 9, 6, 2; 15, 11, 4, 0) = ? \to ^?

Le motif de droite dérive de l'image

4 \times 4

représentée à gauche. On supposera par la suite qu'une variable globale deuxQuarts contient l'image de gauche.

Question 13 Écrire une fonction tramerJournal(i) qui prend en argument une image

i

de profondeur 16, et qui renvoie l'image de profondeur 1 obtenue en seuillant l'image

i

selon la trame diagonale de profondeur 15. Par exemple, l'image M de la figure 3 résulte de l'application de tramerJournal à l'image I de la figure 2.

Question 14 Indiquer un procédé simple qui permet d'obtenir l'image N de la figure 3 à partir de l'image I de la figure 2 et à l'aide de la trame diagonale de profondeur 15. On notera que l'image N est bien une image de profondeur 1, et qu'elle est représentée réduite (d'un facteur 2) par rapport à l'image M. Coder ensuite votre procédé comme une fonction qui prend une image de profondeur arbitraire en argument.

Questions fréquentes

3 questions

Sur quels chapitres porte l'épreuve d'informatique commune X-ENS PSI-PT 2011 ?

Le sujet porte sur l'algorithmique et la manipulation de matrices, appliquées au traitement d'images en teintes de gris : opérations géométriques, transferts de tons et tramage.

Les trois parties du sujet sont-elles indépendantes ?

Les parties s'enchaînent progressivement : la partie II réutilise les fonctions élémentaires de la partie I, et la partie III sur le tramage s'appuie sur les fonctions de réduction de profondeur de la partie II pour proposer une alternative de meilleure qualité.

Qu'est-ce que le tramage étudié dans la partie III du sujet ?

C'est une technique consistant à convertir une image en teintes de gris en une image en noir et blanc (profondeur 1) en comparant chaque pixel à un seuil variable donné par un motif répété (trame), plutôt qu'à un seuil uniforme, pour obtenir un rendu visuel plus satisfaisant.

Pas de description pour le moment

Commentaires• X ENS Informatique Commune PSI PT 2011

Connectez-vous pour participer aux discussions

Partagez vos avis, posez des questions et échangez avec la communauté

Chargement des commentaires...