SESSION 2023 PC5IN

ÉPREUVE MUTUALISÉE AVEC E3A-POLYTECH

ÉPREUVE SPÉCIFIQUE - FILIÈRE PC

____________________

INFORMATIQUE
Durée : 3 heures
____________________

N.B. : le candidat attachera la plus grande importance à la clarté, à la précision et à la concision de la rédaction.
Si un candidat est amené à repérer ce qui peut lui sembler être une erreur d’énoncé, il le signalera sur sa copie
et devra poursuivre sa composition en expliquant les raisons des initiatives qu’il a été amené à prendre.

RAPPEL DES CONSIGNES

 Utiliser uniquement un stylo noir ou bleu foncé non effaçable pour la rédaction de votre composition ; d’autres
couleurs, excepté le vert, peuvent être utilisées, mais exclusivement pour les schémas et la mise en
évidence des résultats.
 Ne pas utiliser de correcteur.
 Écrire le mot FIN à la fin de votre composition.
______________________________________________________________________________

Les calculatrices sont interdites.

Le sujet est composé de trois parties.

L’épreuve est à traiter en langage Python sauf pour les bases de données.
Les différents algorithmes doivent être rendus dans leur forme définitive sur le Document
Réponse dans l’espace réservé à cet effet en respectant les éléments de syntaxe du langage
(les brouillons ne sont pas acceptés).
La réponse ne doit pas se limiter à la rédaction de l’algorithme sans explication, les pro-
grammes doivent être expliqués et commentés.

Énoncé et Annexe : 16 pages

Document Réponse (DR) : 12 pages

Seul le Document Réponse doit être rendu dans son intégralité.

1/16
A
 Reconnaissance optique de caractères

Introduction

La reconnaissance optique de caractères (OCR) existe depuis de nombreuses années mais

les récents travaux d’intelligence artificielle (apprentissage profond) ont considérablement
augmenté les performances de la reconnaissance de documents.

L’objectif du travail proposé est de découvrir différentes étapes de la numérisation

d’un document en explorant plusieurs algorithmes utilisés pour obtenir au final un
document éditable conforme à l’original.

Le sujet abordera les points suivants :

- acquisition d’un document et pré-traitement dans le but d’obtenir une image numérique
pertinente ;
- reconnaissance du contenu qui correspond à l’extraction du texte et de sa structure ;
- reconnaissance des caractères par identification à l’aide d’une base de données.

Partie I - Acquisition d’un document

L’acquisition du document est obtenue généralement par balayage optique. Le résultat est
rangé dans un fichier de points (pixels) dont la taille dépend de la résolution.
Une image en couleurs est stockée dans une matrice imgC de p lignes (pixels en hauteur), q
colonnes (pixels en largeur) dont chaque élément est un triplet. Chaque valeur du triplet de
couleur (rouge, vert, bleu) est un entier compris entre 0 et 255. La résolution est exprimée
en nombre de pixels par pouce (ppp). La valeur d’un pouce est environ égale à 2,5 cm.
Q1. Chaque entier représentant une couleur est représenté, en binaire, sous la forme d’un
mot constitué de bits 0 et de 1. Donner la taille de ce mot pour qu’il puisse représenter
tous les entiers compris entre 0 et 255. Indiquer les dimensions (en pixels) d’une image
en couleurs au format A4 (21 cm x 29,7 cm) pour une résolution de 300 ppp. En déduire
alors la taille en bits du fichier image correspondant.
Pour diminuer la taille du document afin de pouvoir plus facilement le traiter, on réalise tout
d’abord une conversion en niveaux de gris de l’image.
L’image en niveau de gris est une matrice imgG à p lignes et q colonnes où chaque valeur
est un entier entre 0 (pixel noir) et 255 (pixel blanc).
La formule utilisée pour déterminer la valeur d’un pixel gris en fonction des trois couleurs
d’un pixel (R rouge, G vert, B bleu) est la suivante : pixGris = 0,299 ∗ R + 0,587 ∗ G + 0,114 ∗ B.
De manière générale, on nomme le type array pour représenter une matrice sous la forme
d’une liste de listes dont les éléments de la liste interne pourront être des triplets pour les
images en couleurs ou des entiers pour les images en niveau de gris.
On introduit les fonctions :
- dimension(img:array) -> tuple qui renvoie le triplet (p, q, 3) pour une image en cou-
leurs et le triplet (p, q, 1) pour une image en niveau de gris ;
- initialise(p:int, q:int, valeur:int) -> array qui renvoie une image de dimen-
sions (p, q) où tous les pixels sont initialisés à une même valeur valeur.

2/16
On donne la fonction permettant de convertir en niveau de gris l’image en couleurs.
def c o n v e r s i o n _ g r i s ( imgC : a r r a y ) −> a r r a y :
n0 , n1 , _ = dimension ( imgC )
img = i n i t i a l i s e ( p , q , 0 )
f o r i i n range ( n0 ) :
f o r j i n range ( n1 ) :
r , g , b = imgC [ i ] [ j ]
v a l = 0.299 * r + 0.587 * g + 0.114 * b
img [ i , j ] = i n t ( v a l )
r e t u r n img

Q2. Donner la complexité de la fonction conversion_gris(imgC:array)->array.

La première étape du prétraitement est la binarisation. Cela consiste à remplacer les pixels
en niveaux de gris par des pixels noirs (valeur 0) ou blanc (valeur 255) uniquement. Pour
cela, la valeur du pixel gris est comparée à une valeur seuil notée seuil.
Q3. Proposer une fonction binarisation(imgG:array, seuil:int)->array qui convertit
une image en niveau de gris en image en noir et blanc en imposant une valeur 255
pour tout pixel de valeur strictement supérieure au seuil.
La difficulté de cette technique de binarisation est le choix de la valeur seuil pour des images
ayant des problèmes d’éclairage. Nous verrons que la technique de restauration étudiée par
la suite peut être utilisée pour remplacer la binarisation par seuil standard.

3/16
 Partie II - Reconnaissance du document

II.1 - Rotation de l’image

L’image scannée peut avoir un problème de rotation qu’il convient de corriger afin d’appliquer
l’algorithme de reconnaissance des caractères (figure 1).

Figure 1 - Image avec un problème de rotation lors de l’acquisition numérique

Le paramétrage de l’image pour la rotation est donné sur la figure 2. L’image est de dimen-
sion (p, q) (possède p lignes et q colonnes). Pour faire tourner le point de coordonnées (i, j)
autour du point O centre de l’image d’un angle α, on applique une rotation à l’aide d’une
matrice de rotation : ( ) ( )( )
ni − p//2 cos α sin α i − p//2
= .
n j − q//2 − sin α cos α j − q//2
On obtient alors un nouveau point de coordonnées (ni , n j ).

0 j nj q
0

#»
y
O

ni ×
i × α
p
#»
x

Figure 2 - Paramétrage de l’image pour la rotation

Naïvement, on pourrait penser que pour réaliser la rotation, il suffit de parcourir chaque pixel
de l’image intiale en lui appliquant la rotation définie précédemment. Mais les indices étant
des entiers, on se rend compte que certains pixels de la nouvelle image ne sont jamais cal-
culés (figure 3) et qu’il peut apparaître des problèmes de dépassement de taille d’image.

4/16
 Figure 3 - Rotation naïve de l’image intiale

L’algorithme de rotation consiste donc, pour chaque pixel de la nouvelle image de coordon-
nées (ni , n j ), à trouver ses coordonnées (i, j) par une rotation d’angle −α dans l’image initiale.
La position du pixel virtuel ainsi trouvée est en fait un couple de réels (x, y). Le pixel virtuel
est ainsi entouré de 4 pixels dans l’image initiale dont les abscisses sont comprises entre
int(x) et int(x)+1 et les ordonnées entre int(y) et int(y)+1 (figure 4).

• •
×
• •

Figure 4 - Illustration du pixel trouvé entouré des 4 pixels voisins dans l’image intiale

Pour trouver la valeur du pixel virtuel, on utilise la valeur des 4 pixels voisins en réalisant une
approximation bilinéaire qui consiste :
- en prenant les deux pixels voisins de la première ligne, à trouver la valeur du niveau
de gris du pixel virtuel en supposant une évolution linéaire selon la coordonnée y entre
le pixel de gauche et le pixel de droite ;
- à faire de même en prenant les pixels de la deuxième ligne ;
- enfin en travaillant sur la coordonnée x, à supposer une évolution linéaire entre les
deux valeurs trouvées aux deux étapes précédentes.

On dispose d’une fonction :

lineaire(x:float, x0:int, x1:int, pix0:int, pix1:int)-> float
qui renvoie le flottant val, approximation linéaire au point x des valeurs pix0 prise au point x0
et pix1 prise au point x1.
Si les coordonnées du point virtuel (x, y) se situent en dehors de l’image, alors la valeur du
pixel sur l’image tournée sera prise de couleur blanche, c’est-à-dire égale à 255.
Q4. Choisir la fonction bilineaire(im:array, x:float, y:float)->int parmi les quatre
propositions, données dans le DR, permettant de respecter les spécifications.
Q5. Compléter la fonction rotation(im:array, angle:float)->array donnée dans le
DR qui prend en argument une image en niveau de gris et un angle en degré et qui
renvoie une nouvelle image tournée de l’angle angle donné en degré. On veillera à
initialiser l’image par une image complètement blanche (pixels de valeur 255).
On suppose définie une fonction :
prod_matrice_vecteur(M: array, v: list) -> list
qui renvoie le vecteur colonne (sous forme de liste) résultat de la multiplication de la
matrice M par le vecteur colonne v.

5/16
Une manière d’implémenter la fonction lineaire est la suivante :
def l i n e a i r e ( x : f l o a t , x0 : i n t , x1 : i n t , p i x 0 : i n t , p i x 1 : i n t ) −> f l o a t :
r e t u r n ( x−x0 ) * ( pix1 − p i x 0 ) / ( x1−x0 ) + p i x 0

Il se trouve qu’en pratique, si on utilise des tableaux Numpy pour représenter les matrices,
on peut être tenté de forcer les entiers à être du type uint8 qui correspond à un entier non
signé (d’où le « u » pour « unsigned ») stocké sur 8 bits.
Q6. Donner une raison pour laquelle il serait intéressant de se contraindre à 8 bits et ex-
pliquer le gain qu’il pourrait en découler en pratique.
Expliquer quel problème pourrait apparaître en réfléchissant au résultat de la sous-
traction 18 − 23 où 18 et 23 sont tous deux des entiers non signés sur 8 bits et où le
résultat est lui aussi obligatoirement un entier non signé sur 8 bits.
En utilisant une telle structure (où pix0 et pix1 sont des entiers de type uint8), on se retrouve
avec l’image pixellisée de la figure 5, ce qui n’est effectivement pas un résultat voulu, l’image
attendue étant donnée sur la figure 6. L’angle choisi pour cette rotation n’est pas la valeur
optimale assurant l’horizontalité du texte.

Figure 5 - Problème de pixellisation lors de la rotation

Figure 6 - Figure attendue après la rotation

6/16
II.2 - Segmentation
La segmentation consiste à découper l’image en plusieurs éléments de manière à pouvoir
ensuite traiter chacun des éléments. Il faut dans l’image pouvoir dissocier les lignes, les mots
puis les lettres. L’idée est de construire la liste du nombre de pixels noirs par ligne.
On peut ensuite détecter les lignes en sélectionnant les zones où il y a majoritairement des
pixels blancs, ce qui correspond aux zones sans texte.
On applique ensuite le même principe pour détecter les mots et les lettres en comptant les
pixels blancs verticalement.
On travaille sur une image binarisée, c’est-à-dire ne contenant que des pixels blancs (255)
ou des pixels noirs (0).
Q7. Proposer une fonction histo_lignes(im:array)->list qui prend en argument une
image binarisée et renvoie une liste contenant le nombre de pixels noirs de chaque
ligne sans utiliser la fonction count.
La fonction appliquée au texte précédent, après rotation, renvoie la liste présentée sous
forme d’un histogramme sur la figure 7.

Figure 7 - Histogramme de détection des lignes

On peut observer des blocs de pixels noirs correspondant bien aux lignes. Il suffit maintenant
de détecter le début d’un bloc comme étant un élément nul suivi d’un élément non nul et de
détecter la fin d’un bloc comme étant un élément nul précédé d’un élément non nul.
Q8. Compléter sur le DR la fonction detecter_lignes(liste:list)->list prenant en
argument une liste contenant le nombre de pixels noirs par ligne de l’image et qui
renvoie une liste de couples (début ligne, fin ligne).
Cette fonction appliquée à notre exemple renvoie : [[8, 36], [38, 64],
[73, 102], [102, 132], [134, 160], [167, 193], [198, 227], [232, 257],
[262, 291], [293, 322], [322, 351], [361, 382]].
En appliquant cette détection de ligne directement sur l’image mal orientée, il en résulte une
erreur de détection. En effet, si on observe l’histogramme dans ce cas (figure 8), on constate
qu’il n’y a plus de zones avec des pixels blancs détectées.

7/16
 Figure 8 - Histogramme de détection des lignes sur la figure mal orientée

Il est donc nécessaire d’implanter un algorithme permettant de détecter automatiquement

la bonne orientation en travaillant sur la maximisation du nombre de 0 dans la liste fournie
par la fonction histo_ligne. On suppose que dans l’intervalle des angles de recherche, la
fonction possède un unique maximum (pas d’extremum local).
L’algorithme peut être décrit de la manière suivante :
- partant d’un intervalle de départ [a, b] avec les angles a et b, on calcule :
• le nombre de 0 de la liste fournie par la fonction histo_ligne pour les deux orien-
tations a et b,
• le nombre de 0 de la liste fournie par la fonction histo_ligne pour l’orientation du
a+b
milieu, noté c = ;
2
- on itère tant que l’intervalle de recherche [a, b] est plus grand qu’un epsilon donné :
• on calcule le nombre de 0 pour l’orientation au milieu, noté ac, de l’intervalle [a, c],
• on calcule le nombre de 0 pour l’orientation au milieu, noté cb, de l’intervalle [c, b],
• on cherche où se situe le maximum entre ac, c ou cb,
• on en déduit le nouvel intervalle de recherche, comme étant celui entourant le
maximum. Par exemple, si le maximum est en c, alors le nouvel intervalle sera
[ac, cb].

Q9. Justifier que cet algorithme se termine.

Donner le nom de la méthode utilisée pour réaliser cet algorithme et préciser en jus-
tifiant le nombre d’itérations nécessaires pour obtenir la solution avec une précision
notée ε.

Q10. Compléter la fonction rotation_auto(im:array, a:float, b:float)->array qui

prend en argument une image im et les angles initiaux a et b et qui renvoie l’image
avec la bonne orientation.

Après avoir séparé les lignes, en appliquant une méthode similaire, on peut extraire les
caractères sur chacune de ces lignes. La figure 9 montre les premiers caractères détectés
par l’algorithme.

8/16
 Figure 9 - Premiers caractères détectés par l’algorithme

II.3 - Restauration d’image

Les images de caractères peuvent être bruitées compte tenu d’une mauvaise résolution ou
de parasites apparaissant pendant un scan. De même, la technique de binarisation proposée
initialement ne donne pas toujours un résultat correct si le seuil est mal choisi.
La méthode du flot maximal (ou méthode de la coupe minimale) reposant sur la représenta-
tion par un graphe de l’image à restaurer est souvent utilisée pour pallier ces problèmes.
La librairie maxflow disponible sous Python propose des fonctions déjà existantes pour traiter
une image bruitée.
La fonction globale de traitement de l’image est la suivante :
import numpy
import maxflow
def graph_cut ( img : a r r a y ) −> a r r a y :
img = numpy . a r r a y ( img ) # Conversion en a r r a y de Numpy pour un usage
plus f a c i l e ensuite
g = maxflow . Graph [ i n t ] ( ) # c r é a t i o n du graphe
nodeids = g . add_grid_nodes ( dimension ( img ) )
g . add_grid_edges ( nodeids , 5 )
g . add_grid_tedges ( nodeids , img , 255−img )
g . maxflow ( )
sgm = g . get_grid_segments ( nodeids )
img2 = numpy . i n t _ ( numpy . l o g i c a l _ n o t ( sgm ) )
r e t u r n img2

L’objet des questions de cette sous-partie est de comprendre chaque ligne de cette fonction
et d’illustrer la méthode sur un exemple basique d’une image test (3x3) constituée de 9 pixels
en niveau de gris (pixels compris entre 0 (noir) et 255 (blanc)).

1:0 2 : 210 3 : 190

4 : 20 5 : 100 6 : 200

7 : 10 8:5 9 : 255

Figure 10 - Exemple d’image à restaurer

Les valeurs des pixels de l’exemple sont les suivantes :

[ [ 0 , 210 , 190 ] ,
[ 20 , 100 , 200 ] ,
[ 10 , 5 , 255 ] ]

9/16
La méthode utilise la représentation par graphe pondéré constitué de n sommets et m arêtes.
Chaque sommet correspond à un pixel de l’image. nodeids est donc l’ensemble des som-
mets du graphe correspondant à l’image de taille dimension(img).
Les arêtes reliant deux sommets sont ensuite construites à l’aide de l’instruction
g.add_grid_edges(nodeids, 5) entre un sommet et ses potentiels 4 voisins adjacents. À
chaque arête e reliant deux sommets, un poids w(e) de valeur fixe 5 est associé. Cette pon-
dération va représenter la capacité maximale du flot définie par la suite.
Q11. Représenter le graphe correspondant à l’image de (3x3) pixels en précisant sur
chaque arête la capacité maximale de 5.

Pour mettre en place la méthode de flot maximal, il est nécessaire d’introduire deux som-
mets supplémentaires (appelés source S et puits P) qui sont reliés par des arêtes à tous
les sommets précédents. Sur chaque arête entre le sommet S et les sommets ”pixels” on
utilise les valeurs des pixels comme poids, et sur les arêtes entre les sommets ”pixels” et
le sommet P on utilise le complément à 255 des valeurs des pixels. C’est le rôle de la ligne
g.add_grid_tedges(nodeids, img, 255-img).
Q12. Compléter sur le DR la partie supérieure de la matrice de capacités correspondant au
graphe complet de l’exemple en prenant l’ordre suivant pour les sommets : S, 1, 2,...,
9, P avec pour valeurs les poids précédemment introduits pour chaque arête. Le poids
est nul si le sommet i n’est pas relié au sommet j.

La fonction [Link]() calcule le flot maximal, ce qui permettra par la suite de partitionner
les sommets.
Le flot est une notion similaire à un flux de fluide qui s’écoulerait de la source vers le puits.
Mathématiquement, le flot est une fonction f définie de l’ensemble des arêtes e ∈ E vers
l’ensemble des réels R. Cette fonction vérifie les propriétés suivantes :
- ∀e = (p, q) ∈ E (avec p, q deux sommets), f (p, q) = − f (q, p), le flot dans le sens q vers
p est l’opposé du flot dans le sens p vers q ;
∑
- pour tout sommet p autre que S et P : f (e) = 0, la somme des flots arrivant et
e=(p,.)∈E
sortant d’un sommet est nulle, ce qui est similaire à la loi de Kirchoff ;
- pour toute arête e ∈ E, f (e) ≤ w(e), le flot ne peut pas dépasser la capacité maximale
définie initialement.
On pourrait définir une matrice de flots similaire à la matrice de capacités qui contiendrait les
valeurs des flots au lieu des capacités.
On passe du graphe non orienté que nous venons de décrire à un graphe orienté. Les arêtes
faisant intervenir la source sont alors orientées de la source vers les sommets (flot sortant
de la source) ; celles faisant intervenir le puits sont orientées des sommets vers le puits (flot
entrant dans le puits) ; les arêtes entre des sommets i et j correspondant à des pixels sont
dédoublées (une de i vers j, l’autre de j vers i) et ont chacune une capacité maximale égale
à 5. La figure 11 montre un exemple de flot sur une partie seulement du graphe de l’exemple
étudié. Les étiquettes de la forme i/ j représentent pour i la valeur du flot et pour j la valeur
de la capacité maximale.
Le flot est maximal lorsque les flots partant de la source S sont maximaux tout en respectant
toutes les règles précédentes. On dit qu’une arête est saturée lorsque le flot de cette arête
est égal à sa capacité.

10/16
 0/5
1/5
1 2
0/0 6/45
5/210 0/5 1/255
2/5
6/20 4/235
S 4 P

Figure 11 - Exemple d’extrait de graphe avec flot

Pour déterminer le flot maximal, une méthode possible consiste à saturer des arêtes. Pour
cela, on utilise un graphe complémentaire appelé graphe résiduel, obtenu à partir du graphe
de flot sur lequel on indique sur chaque arête e ∈ E la capacité résiduelle (dans un sens et
dans l’autre) : r(e) = w(e) − f (e). Si une arête est étiquetée 0 sur le graphe résiduel, alors il
n’est plus possible d’emprunter cette arête pour construire le chemin de longueur minimal.
La figure 12 montre le graphe résiduel associé au graphe avec flot de la figure 11.

5
4
1 2
0 39
205 5 254
3
14 231
S 4 P

Figure 12 - Exemple de graphe résiduel

On utilise l’algorithme d’Edmonds-Karp : à partir du flot nul, on cherche itérativement un plus

court chemin C (c’est-à-dire un chemin où la somme des étiquettes du graphe résiduel en
parcourant les arêtes le constituant est minimal et comportant le moins d’arêtes) de la source
au puits sur lequel il n’y a pas d’arête saturée (c’est-à-dire un chemin pour lequel aucune des
arêtes correspondantes du graphe résiduel n’est pondérée par 0). On rajoute alors autant
de flots que possible à ce chemin (c’est-à-dire on sature l’arête qui a une capacité résiduelle
minimale).
L’algorithme de recherche du flot maximal est le suivant en pseudo-code :
Initialisation :
poser f ( e ) = 0 pour t o u t e a r ê t e e
dé f i n i r l e graphe r é s i d u e l i n i t i a l
dé f i n i r un chemin C de S à P dans l e graphe r é s i d u e l de l o n g u e u r minimale
t a n t qu ’ i l e x i s t e un chemin C de S à P dans l e graphe r é s i d u e l f a i r e
prendre un chemin C de l o n g u e u r minimale
a = min ( r ( e ) | e dans C)
pour t o u t e dans C f a i r e
f (e) = f (e) + a
f i n pour
m e t t r e à j o u r l e graphe r é s i d u e l
f i n t a n t que

11/16
Q13. Appliquer cet algorithme sur les graphes du DR en précisant à chaque étape le che-
min choisi et la valeur de l’augmentation du flot jusqu’à sa terminaison. Le graphe
de gauche représente le graphe de flot et le graphe de droite le graphe résiduel. On
donne le graphe initial avec un flot nul ainsi que le graphe résiduel associé.
Pour transformer l’image en niveau de gris en une image noir et blanc, c’est-à-dire pour
séparer les pixels entre ceux qui prennent la valeur 0 et ceux qui prennent la valeur 255,
on va réaliser une coupe dans le graphe des pixels. On définit l’ensemble A contenant la
source S et certains sommets ainsi que l’ensemble B contenant le puits P et les sommets
restants.
La capacité de la coupe est la somme des capacités des arcs orientés de A vers B.
Par exemple, supposons que nous ayons coupé le graphe entre les ensembles A = {S, 1, 2}
et B = {P, 4}. En sommant les capacités maximales des arêtes orientées allant d’un sommet
de A vers un sommet de B, on obtient une capacité de coupe de 20+5+255+45 = 325.

0/5
1/5
1 2
0/0 6/45
5/210 1/255 coupe
0/5
2/5
6/20 4/235
S 4 P

Figure 13 - Coupe dans un graphe

L’algorithme d’Edmonds-Karp permet de construire un flot maximum, c’est-à-dire un flot dont

la somme des arêtes arrivant au puits est maximale. Le théorème du ” flot maximal et coupe
minimale ” assure que la valeur de ce flot maximal est égale à la valeur de coupe minimale.
Pour réaliser cette coupe, on met dans l’ensemble A la source S et tous les sommets ac-
cessibles, depuis S, par des arêtes non saturées ; on met dans l’ensemble B les sommets
restants.
L’appel g.get_grid_segments(nodeids) renvoie une liste indiquant, pour chacun des som-
mets, s’il appartient ou non au même ensemble que la source.
Q14. Dans l’exemple précédent, indiquer les deux ensembles A et B en précisant la valeur
du flot maximal et en vérifiant que la capacité de coupe réalisée correspond bien à
une valeur égale à celle du flot maximal.
Lorsqu’on applique la fonction précédente sur l’image d’un caractère, on obtient la nouvelle
image de la figure 14.

Figure 14 - Caractère scanné et caractère après traitement par la fonction graph_cut

Q15. Indiquer pour cette image de la figure 14 à quoi correspondent les ensembles A et B.
Analyser le résultat obtenu.

12/16
 Partie III - Détermination des caractères

Une fois les images de lettres isolées, il s’agit de reconnaître la lettre correspondante. Diffé-
rentes méthodes peuvent être employées. Nous allons étudier une méthode d’apprentissage
automatique basée sur les K plus proches voisins.
Le principe de cette méthode consiste à comparer chaque caractère à un ensemble de ca-
ractères définis dans une base de données.

III.1 - Analyse de la base de données de caractères

La base de données contient des informations sur chaque caractère selon le type de fonte,
la taille, la graisse... Trois tables sont utilisées.
FONTES
CARACTERES id
SYMBOLES
id nom
id
id_symbole famille
label
id_fonte taille
catégorie
fichier graisse
style

La table SYMBOLES contient les attributs suivants :

- id : identifiant d’un symbole (entier), clé primaire ;
- label : nom du symbole (”A”, ”a”, ”1”, ”é”, ” !” ...) (chaîne de caractères) ;
- catégorie : parmi majuscule, minuscule, chiffre, spécial (dont accent) (chaîne de ca-
ractères).
La table CARACTERES contient les attributs suivants :
- id : identifiant d’un caractère (entier), clé primaire ;
- id_symbole : identifiant du nom du symbole (entier) ;
- id_fonte : identifiant du type de fonte (entier) ;
- fichier : nom du fichier image correspondant (chaîne de caractères).
La table FONTES contient les attributs suivants :
- id : identifiant d’une fonte (entier), clé primaire ;
- nom : nom de la fonte ("Arial", "Times new roman", "Calibri", "Zurich", ...) (chaîne
de caractères) ;
- famille : nom de la famille dont fait partie la fonte ("humane", "garalde", "réale",
"didone", "scripte", ...) (chaîne de caractères) ;
- taille : dimension en hauteur des caractères en pixels (entier) ;
- graisse : type de graisse ("léger", "normal", "gras", "noir", ...) (chaîne de carac-
tères) ;
- style : type de style ("romain", "italique", "ombré", "décoratif", ...) (chaîne de ca-
ractères).
Q16. Écrire une requête SQL permettant d’extraire les identifiants des fontes dont le nom
est "Zurich", de style "romain" et dont la taille est comprise entre 10 et 16 pixels.
Q17. Écrire une requête SQL permettant d’extraire tous les noms de fichiers des caractères
qui correspondent au symbole de label "A".
Q18. Écrire une requête SQL permettant d’indiquer le nombre de caractères correspondant
à la fonte "Zurich", de style "romain" et dont la taille est comprise entre 10 et 16
pixels groupés selon les labels des symboles.

13/16
III.2 - Classification automatique des caractères

Dans la suite du sujet, on suppose qu’on dispose d’une liste fichiers_car_ref contenant
les noms des fichiers images d’un grand nombre de caractères ayant des fontes proches de
celles du texte scanné. Le nom de chaque fichier est défini de la manière suivante :
nomFonte + "_" + nomCatégorie+taillePolice + "_" + idSymbole + ".png"
Les catégories sont définies par la liste :
categories = ["majuscules","minuscules","chiffres","special"].
Les symboles considérés sont définis par la liste :
symboles = ["ABCDEFGHIJKLMNOPQRSTUVWXYZ","abcdefghijklmnopqrstuvwxyz",
"0123456789",".:,;'(!?)éèàçùêûâ"]. On compte 79 symboles différents.
Exemple : Zurich Light BT_majuscules18_10.png pour la majuscule K de la police Zurich
Light BT en taille 18.
On introduit la fonction suivante :
def l i r e _ s y m b o l e _ f i c h i e r ( nomFichier : s t r ) −> s t r :
c a r = nomFichier . s p l i t ( ’ _ ’ )
num = c a r [ 2 ] . s p l i t ( ’ . ’ ) [ 0 ]
v a r = c a r [ 1 ] [ : len ( c a r [ 1 ] ) −2]
ind = categories . index ( var )
r e t u r n symboles [ i n d ] [ i n t (num) ]

Pour une liste L, [Link](val) renvoie la position de val dans la liste L.

Q19. Indiquer ce que valent les variables car, num, var, ind et ce qui est renvoyé par la
fonction si nomFichier="Zurich Light BT_majuscules18_10.png".
Toutes les images des caractères de référence sont lues et stockées sous forme de tableaux
array. On définit un dictionnaire carac_ref dont les clés seront les symboles apparaissant
dans la liste symboles (par exemple "A", "a", ...). À chaque clé sera associée une liste de
tableaux array représentant des images.
La commande img=imread(nomFichier) permet de lire le fichier image nomFichier et de
stocker le tableau array à deux dimensions qui représente l’image dans la variable img.
Q20. Écrire une fonction lire_donnees_ref(fichiers_car_ref:list)->dict qui prend en
argument la liste des noms de fichiers images fichiers_car_ref et qui renvoie le
dictionnaire contenant tous les tableaux catégorisés.
Un caractère à identifier est également stocké sous forme d’un tableau array nommé
carac_test. On suppose que les dimensions de ce tableau et de tous les tableaux du dic-
tionnaire carac_ref sont les mêmes.
La méthode d’identification utilisée est celle des K plus proches voisins. Elle consiste à cal-
culer une distance entre l’image du caractère à identifier et toutes les images de référence.
En notant (i, j) les coordonnées d’un pixel dans le tableau représentant l’image, pi j le pixel
associé à l’image du caractère à identifier et qi j celui √
d’un caractère de référence, on calcule
pour chaque caractère de référence la distance d = Σi, j (pi j − qi j )2 .
Les distances d sont stockées dans un dictionnaire distances où, pour chaque clé égale à
un symbole de la liste symboles, on associe une liste de distances pour chaque image de
référence de ce symbole.
Q21. Écrire une fonction distance(im1:array, im2:array)->float qui calcule la distance
entre les deux images im1 et im2 supposées de même dimension.

14/16
Q22. Écrire une fonction calcul_distances(carac_ref:dict, carac_test:array)->dict
qui prend en argument le dictionnaire des tableaux catégorisés et un tableau associé
au caractère à tester et qui renvoie le dictionnaire des distances.
La suite consiste à déterminer les K plus petites distances et extraire les clés correspon-
dantes, puis parmi ces clés déterminer la clé majoritaire. Une méthode envisageable est de
trier les distances par ordre croissant pour prendre les K premiers éléments. On suppose
qu’il y a au total n images de caractères de référence sur l’ensemble des symboles.
Q23. En se plaçant dans le pire des cas, indiquer le nom d’une méthode de tri performante
envisageable, en précisant sa complexité temporelle en fonction de n.
Une méthode plus efficace est envisagée pour extraire directement les K plus petits élé-
ments. Elle consiste à construire par tri par insertion la liste de taille K. L’algorithme corres-
pondant est donné dans le DR.
Q24. Compléter les 3 zones manquantes dans cet algorithme.
Q25. Préciser la complexité temporelle asymptotique dans le pire des cas de cet algorithme
en fonction de n et de K. Comparer avec l’utilisation d’un tri classique sachant que n
est grand et K ne dépassera pas 5.
Q26. Écrire une fonction symbole_majoritaire(voisins:list)->str qui à partir de la liste
voisins renvoyée par la fonction Kvoisins renvoie le symbole majoritaire.
On teste l’algorithme sur les caractères extraits dans la partie précédente ("Beauté,").
On obtient les résultats suivants.
Nombre de Type d’éléments dans la base de Caractères
Nombre d’éléments dans la base n
voisins K données obtenus
79 images correspondant aux 79
1 fonte similaire au texte analysé "Bssi!-,"
symboles
79 images correspondant aux 79
4 fonte similaire au texte analysé "Bssi!-,"
symboles
40 fontes proches de celle du texte 40*79 images correspondant aux
1 "Bsauté,"
analysé 79 symboles
40 fontes proches de celle du texte 40*79 images correspondant aux
4 "Bsauté,"
analysé 79 symboles
320*79 images correspondant aux
1 40 fontes pour 8 polices différentes "Beauté,"
79 symboles
320*79 images correspondant aux
4 40 fontes pour 8 polices différentes "Beauté,"
79 symboles

Q27. Commenter les résultats obtenus.

15/16
 ANNEXE
Rappels des syntaxes en Python

Fonctionnalités Python
détermination du nombre de zéros dans la liste X [Link](0)
définir une chaîne de caractères mot = 'Python'
taille d’une chaîne len(mot)
extraire des caractères (avec le même fonctionne-
ment des indices que pour les extractions de sous- mot[2:7]
listes)
éliminer le \n en fin d’une ligne [Link]()
découper une chaîne de caractères selon un carac-
tère passé en argument. On obtient une liste qui
contient les caractères séparés. [Link](',')
Dans l’exemple ci-contre, on découpe à chaque oc-
currence du caractère ”,”
ouverture d’un fichier en lecture et lecture des don-
with open('nom_fichier','r') as f:
nées (data est une liste de chaînes de caractères
data = [Link]()
dont la taille est le nombre de lignes du fichier lu)

FIN

I M P R I M E R I E N A T I O N A L E – 23 1135 – D’après documents fournis

16/16
 Numéro
d’inscription
Nom : ____________________________________
Numéro
de table
Prénom : _________________________________

Né(e) le

Filière : PC Session : 2023

Emplacement

Épreuve de : INFORMATIQUE
QR Code

• Remplir soigneusement l’en-tête de chaque feuille avant de commencer à composer

• Rédiger avec un stylo non effaçable bleu ou noir
Consignes • Ne rien écrire dans les marges (gauche et droite)
• Numéroter chaque page (cadre en bas à droite)
• Placer les feuilles A3 ouvertes, dans le même sens et dans l’ordre

PC5IN

DOCUMENT RÉPONSE
Ce Document Réponse doit être rendu dans son intégralité.

Q1 - Taille du mot en bits. Dimensions en pixels d’une image. Taille en bits du fichier image

Q2 - Complexité de la fonction conversion_gris(imgC:array)->array

B
/
1/12
 NE RIEN ÉCRIRE DANS CE CADRE

Q3 - Fonction binarisation(imgG:array, seuil:int)->array

Q4 - Choix de la fonction bilineaire(im:array, x:float, y:float)->int

def b i l i n e a i r e ( im : a r r a y , x : f l o a t , y : f l o a t ) −> i n t : def b i l i n e a i r e ( im : a r r a y , x : f l o a t , y : f l o a t ) −> i n t :

x0 = i n t ( x ) x0 = i n t ( x )
x1 = x0+1 x1 = x0+1
y0 = i n t ( y ) y0 = i n t ( y )
y1 = y0+1 y1 = y0+1
a = l i n e a i r e ( y , y0 , y1 , im [ x0 ] [ y0 ] , im [ x1 ] [ y1 ] ) a = l i n e a i r e ( y , y0 , y1 , im [ x0 ] [ y0 ] , im [ x0 ] [ y1 ] )
b = l i n e a i r e ( y , y0 , y1 , im [ x1 ] [ y0 ] , im [ x0 ] [ y1 ] ) b = l i n e a i r e ( y , y0 , y1 , im [ x1 ] [ y0 ] , im [ x1 ] [ y1 ] )
c = l i n e a i r e ( x , x0 , x1 , a , b ) c = l i n e a i r e ( x , x0 , x1 , a , b )
return i n t ( c ) return i n t ( c )

def b i l i n e a i r e ( im : a r r a y , x : f l o a t , y : f l o a t ) −> i n t : def b i l i n e a i r e ( im : a r r a y , x : f l o a t , y : f l o a t ) −> i n t :

x0 = i n t ( x ) x0 = i n t ( x )
x1 = x0+1 x1 = x0+1
y0 = i n t ( y ) y0 = i n t ( y )
y1 = y0+1 y1 = y0+1
a = l i n e a i r e ( y , y0 , y1 , im [ x0 ] [ y0 ] , im [ x0 ] [ y1 ] ) a = l i n e a i r e ( y , y0 , y1 , im [ x0 ] [ y0 ] , im [ x0 ] [ y1 ] )
b = l i n e a i r e ( y , y0 , y1 , im [ x0 ] [ y0 ] , im [ x1 ] [ y0 ] ) b = l i n e a i r e ( y , y0 , y1 , im [ x1 ] [ y0 ] , im [ x0 ] [ y1 ] )
c = l i n e a i r e ( x , x0 , y1 , a , b ) c = l i n e a i r e ( y , y0 , y1 , a , b )
return i n t ( c ) return i n t ( c )

/
2/12
Q5 - Fonction rotation(im:array, angle:float)->array
def r o t a t i o n ( im : a r r a y , angle : f l o a t ) −> a r r a y :
p,q,_ = dimension ( im )
imr = ......................
angr = ......................
matR = ......................
f o r n i i n range ( . . . . . . . . . . . . . . . . . . . . . . ) :
f o r n j i n range ( . . . . . . . . . . . . . . . . . . . . . . ) :
x, y = ............................................
x = x + ............
y = y + ............
if .................................... :
....................................
return imr

Q6 - Étude de la fonction lineaire

Q7 - Fonction histo_lignes(im:array)->list

3/12
Q8 - Fonction detecter_lignes(liste:list)->list
def d e t e c t e r _ l i g n e s ( l i s t e : l i s t ) −> l i s t :
lignes = []
i = 0
deb = −1 # c o n t i e n t −1 t a n t qu ’ on p a r c o u r t des l i g n e s de p i x e l b l a n c
while . . . . . . . . . . . . . . . . . . . :
#dé b u t d ’ une s u i t e de l i g n e s c o n t e n a n t des p i x e l s n o i r s
if ........................ :
deb = ...........
# f i n d ’ une s u i t e de l i g n e s c o n t e n a n t des p i x e l s n o i r s
elif ............................. :
.....................
deb = ...........
...........
return l i g n e s

Q9 - Justification de la terminaison et nom de la méthode. Nombre d’itérations nécessaires

4/12
 Numéro
d’inscription
Nom : ____________________________________
Numéro
de table
Prénom : _________________________________

Né(e) le

Filière : PC Session : 2023

Emplacement

Épreuve de : INFORMATIQUE
QR Code

• Remplir soigneusement l’en-tête de chaque feuille avant de commencer à composer

• Rédiger avec un stylo non effaçable bleu ou noir
Consignes • Ne rien écrire dans les marges (gauche et droite)
• Numéroter chaque page (cadre en bas à droite)
• Placer les feuilles A3 ouvertes, dans le même sens et dans l’ordre

PC5IN

Q10 - Fonction rotation_auto(im:array, a:float, b:float)->array

def nb_zeros ( im : a r r a y , angle : f l o a t ) −> i n t :

i m r = r o t a t i o n ( im , angle )
l i g n e = h i s t o _ l i g n e ( imr )
f = l i g n e . count ( 0 )
return f

def r o t a t i o n _ a u t o ( im : a r r a y , a : f l o a t , b : f l o a t ) −> a r r a y :
c = ( a+b ) / 2
f c = nb_zeros ( im , c )
while b−a > 0.1 : # p l u s grand que 0 . 1 degr é

ac = .............

fac = ............

cb = .............

fcb = . . . . . . . . . . . .
maxi = max( fac , f c , f c b )

if . . . . . . . . . . . . . == maxi :
b = c
c = ac
fc = fac

elif . . . . . . . . . . . . . == maxi :
a = ac
b = cb
else :
a = .............

c = .............

fc = . . . . . . . . . . . . .
r e t u r n r o t a t i o n ( im , ( b+a ) / 2 )

C
/
5/12
 NE RIEN ÉCRIRE DANS CE CADRE

Q11 - Graphe de l’exemple de taille 3x3

Q12 - Compléter la partie supérieure de la matrice de capacités

S 1 2 3 4 5 6 7 8 9 P

S
1 -
2 - -
3 - - -
4 - - - -
5 - - - - -
6 - - - - - -
7 - - - - - - -
8 - - - - - - - -
9 - - - - - - - - -
P - - - - - - - - - -

/
6/12
Q13 - Compléter les graphes de flot à gauche et résiduel à droite. Pour chaque étape, pré-
ciser le chemin choisi et la valeur de l’augmentation du flot

0/5 5
0/5 5
1 2 1 2
0/0 0/45 0 45
0/210 0/5 0/255 210 5 255
0/5 5
0/20 0/235 20 235
S 4 P S 4 P

Chemin choisi :
.../5 ...
.../5 ...
1 2 1 2
.../0 .../45 ... ...
.../210 .../5 .../255 ... ... ...
.../5 ...
.../20 .../235 ... ...
S 4 P S 4 P

Chemin choisi :
.../5 ...
.../5 ...
1 2 1 2
.../0 .../45 ... ...
.../210 .../5 .../255 ... ... ...
.../5 ...
.../20 .../235 ... ...
S 4 P S 4 P

Chemin choisi :
.../5 ...
.../5 ...
1 2 1 2
.../0 .../45 ... ...
.../210 .../5 .../255 ... ... ...
.../5 ...
.../20 .../235 ... ...
S 4 P S 4 P

Q14 - Ensembles A et B. Flot maximal. Coupe choisie et capacité de coupe

Q15 - Correspondance ensembles A et B. Analyse

7/12
Q16 - Requête SQL

Q17 - Requête SQL

Q18 - Requête SQL

Q19 - Contenu des variables car, num, var, ind. Retour de la fonction
car : var :
num : ind :
Retour de la fonction :

8/12
 Numéro
d’inscription
Nom : ____________________________________
Numéro
de table
Prénom : _________________________________

Né(e) le

Filière : PC Session : 2023

Emplacement

Épreuve de : INFORMATIQUE
QR Code

• Remplir soigneusement l’en-tête de chaque feuille avant de commencer à composer

• Rédiger avec un stylo non effaçable bleu ou noir
Consignes • Ne rien écrire dans les marges (gauche et droite)
• Numéroter chaque page (cadre en bas à droite)
• Placer les feuilles A3 ouvertes, dans le même sens et dans l’ordre

PC5IN

Q20 - Fonction lire_donnees_ref(fichier_car_ref:list)->dict

Q21 - Fonction distance(im1:array, im2:array)->float

D
/
9/12
 NE RIEN ÉCRIRE DANS CE CADRE

Q22 - Fonction calcul_distances(carac_ref:dict, carac_test:array)->dict

Q23 - Méthode de tri performante envisageable et complexité temporelle

Q24 - Compléter les 3 zones manquantes

def K v o i s i n s ( d i s t a n c e s : d i c t , K : i n t ) −> l i s t :
v o i s i n s = [ ( f l o a t ( ” i n f ” ) , ” ” ) f o r k i n range ( K ) ]
for l e t t r e in distances :
d = distances [ l e t t r e ]
f o r j i n range ( . . . . . . . . . . . . . . . ) :

if .......................... :
k =len ( v o i s i n s ) −1

while . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . :
v o i s i n s [ k ] = v o i s i n s [ k −1]
k = k − 1
voisins [ k ] = [d[ j ] , l e t t r e ]
return v o i s i n s

/
10/12
Q25 - Complexité en fonction de n et K. Comparaison

Q26 - Fonction symbole_majoritaire(voisins:list)->str

11/12
Q27 - Commentaires

FIN

12/12