Introduction
============


Le but de ce projet est de reconstituer un document passé à la broyeuse.  

Une broyeuse est un appareil qui permet de découper verticalement une (ou plusieurs) feuille de
papier en fines bandelettes, dans le but de faire disparaître l'information contenue sur la
feuille.  

Toutefois, avec beaucoup de patience, un humain peut reconstituer le document en repositionnant les
bandelettes pour qu'elles correspondent bien entre elles.

L'Allemagne a d'ailleurs lancé en 2000 un programme à grande échelle pour accélerer la
reconstitution de très nombreux documents broyés par la Stasi ([Article
RFI](http://www.rfi.fr/europe/20120114-ordinateur-archives-anciens-stasi-est-allemande-allemagne)).

Votre mission, si vous l'acceptez, sera d'écrire un programme permettant de reconstituer une page
ayant été découpée en bandelettes.

Nous ferons quand même des hypothèses simplificatrices :

-   les bandelettes sont déjà **verticales** et **orientées** dans le bon sens ;
-   les bandelettes proviennent d'**une seule feuille**.

**Voici 10 bandelettes (numérotées de 0 à 9)**

Ces bandelettes ont été mélangées. Vous trouverez les fichiers correspondant dans le répertoire `images`.


<table class="bande">
<colgroup>
<col style="width: 10%" />
<col style="width: 10%" />
<col style="width: 10%" />
<col style="width: 10%" />
<col style="width: 10%" />
<col style="width: 10%" />
<col style="width: 10%" />
<col style="width: 10%" />
<col style="width: 10%" />
<col style="width: 10%" />
</colgroup>
<thead>
<tr class="row-odd"><th class="head"><p>0</p></th>
<th class="head"><p>1</p></th>
<th class="head"><p>2</p></th>
<th class="head"><p>3</p></th>
<th class="head"><p>4</p></th>
<th class="head"><p>5</p></th>
<th class="head"><p>6</p></th>
<th class="head"><p>7</p></th>
<th class="head"><p>8</p></th>
<th class="head"><p>9</p></th>
</tr>
</thead>
<tbody>
<tr class="row-even"><td><p><a class="reference internal" href="../images/shred-complainte-0.png"><img alt="i0" class="align-bottom" src="../images/shred-complainte-0.png" style="width: 45.0px; height: 344.0px;" /></a></p></td>
<td><p><a class="reference internal" href="../images/shred-complainte-1.png"><img alt="i1" class="align-bottom" src="../images/shred-complainte-1.png" style="width: 45.0px; height: 344.0px;" /></a></p></td>
<td><p><a class="reference internal" href="../images/shred-complainte-2.png"><img alt="i2" class="align-bottom" src="../images/shred-complainte-2.png" style="width: 45.0px; height: 344.0px;" /></a></p></td>
<td><p><a class="reference internal" href="../images/shred-complainte-3.png"><img alt="i3" class="align-bottom" src="../images/shred-complainte-3.png" style="width: 45.0px; height: 344.0px;" /></a></p></td>
<td><p><a class="reference internal" href="../images/shred-complainte-4.png"><img alt="i4" class="align-bottom" src="../images/shred-complainte-4.png" style="width: 45.0px; height: 344.0px;" /></a></p></td>
<td><p><a class="reference internal" href="../images/shred-complainte-5.png"><img alt="i5" class="align-bottom" src="../images/shred-complainte-5.png" style="width: 45.0px; height: 344.0px;" /></a></p></td>
<td><p><a class="reference internal" href="../images/shred-complainte-6.png"><img alt="i6" class="align-bottom" src="../images/shred-complainte-6.png" style="width: 45.0px; height: 344.0px;" /></a></p></td>
<td><p><a class="reference internal" href="../images/shred-complainte-7.png"><img alt="i7" class="align-bottom" src="../images/shred-complainte-7.png" style="width: 45.0px; height: 344.0px;" /></a></p></td>
<td><p><a class="reference internal" href="../images/shred-complainte-8.png"><img alt="i8" class="align-bottom" src="../images/shred-complainte-8.png" style="width: 45.0px; height: 344.0px;" /></a></p></td>
<td><p><a class="reference internal" href="../images/shred-complainte-9.png"><img alt="i9" class="align-bottom" src="../images/shred-complainte-9.png" style="width: 45.0px; height: 344.0px;" /></a></p></td>
</tr>
</tbody>
</table>

**Reconstitution**

Ces Bandelettes peuvent être permutées. En utilisant la permutation `[9,5,7,2,0,8,1,4,6,3]`, on obtient :

![image](../images/complainte.png){.width="300px"}

**objectif**

réaliser un script python permettant de reconstituer l'image d'origine.

     
Principe général
================

Le principe repose sur une opération clé: savoir si deux bandelettes données coincident ou pas. Si
on sait détecter cela, on peut rassembler une par une les bandelettes et reconstituer la feuille.

Afin de tester si deux bandelettes coincident, on définit sur les bandelettes une notion de
score.


Calcul des scores entre les bandelettes
---------------------------------------

Comment calculer un score entre deux bandelettes nommées `g` (comme gauche) et `d` (comme droite) ?

Plus le score sera elevé, meilleure sera la correspondance entre les deux bandelettes.

Plusieurs méthodes sont possibles :

- en comparant les pixels situés sur la bordure droite de `g` avec ceux situés sur la bordure gauche
  de `d`.
- en collant les deux bandes et en identifiants les motifs ainsi créés : 
    - on construit une base contenant les caractéristiques des motifs (lettres) situés à l'intérieur
      des bandes ;
    - on compte le nombre de motifs créés lorsque l'on colle `g` à `d` et qui "ressemblent" à des
      motifs de la base.

La première méthode est la plus simple et donne de bons résultats (à condition de s'y prendre
correctement !)

on place la bandelette `g` à gauche de la bandelette `d` de telle sorte que
les deux bords se touchent.

* si un pixel noir du bord droit de `g` touche un pixel noir du bord
gauche de d, alors le score doit croître ;

* si un pixel blanc du bord droit de `g` touche un pixel noir du bord
  gauche de `d` ou si un pixel noir du bord droit de `g` touche un pixel
  blanc du bord gauche de d, alors le score doit décroître ;

* si un pixel blanc du bord droit de `g` touche un pixel blanc du bord gauche de g, alors le score
  n'est pas modifié (cela se justifie par le fait que les bandelettes proviennent de feuilles
  blanches sur lesquelles des caractères (noirs) sont imprimés. La majorité des pixels sont donc
  blancs et leur alignement n'est pas significatif.
   
nous allons proposer une méthode de calcul des scores un peu plus loin.

Calcul de la table des scores et reconstitution
-----------------------------------------------

Maintenant qu'on sait calculer un score entre deux bandelettes, on peut calculer les scores de tous les couples de bandelettes différents.  
Il faut bien remarquer aussi que le score entre deux bandelettes `b1` et `b2`, est différent de celui entre `b2` et `b1`.

Supposons que nous disposions de 10 bandelettes représentées par une liste `bandelettes`. 
Si on fait varier l'indice de ligne `i` entre 0 et 9, et l'indice de colonne `j` entre 0 et 9, on peut représenter l'ensemble des scores entre `bandelettes[i]` et `bandelettes[j]` par une table des scores : 

|   | 0    | 1    | 2    | 3    | 4    | 5    | 6    | 7    | 8    | 9    |
|---|------|------|------|------|------|------|------|------|------|------|
| 0 | 0.00 | 0.12 | 0.50 | 0.05 | 0.28 | 0.12 | 0.03 | 0.38 | 0.74 | 0.00 |
| 1 | 0.11 | 0.00 | 0.35 | 0.03 | 2.67 | 0.12 | 0.04 | 0.07 | 0.33 | 0.00 |
| 2 | 0.89 | 0.27 | 0.00 | 0.03 | 0.18 | 0.17 | 0.03 | 0.24 | 0.08 | 0.00 |
| 3 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 |
| 4 | 0.26 | 0.09 | 0.09 | 0.12 | 0.00 | 0.22 | 3.56 | 0.04 | 0.08 | 0.00 |
| 5 | 0.15 | 0.11 | 0.22 | 0.03 | 0.05 | 0.00 | 0.01 | 1.86 | 0.05 | 0.00 |
| 6 | 0.03 | 0.00 | 0.04 | 0.33 | 0.00 | 0.04 | 0.00 | 0.02 | 0.04 | 0.00 |
| 7 | 0.02 | 0.14 | 0.88 | 0.00 | 0.27 | 0.08 | 0.04 | 0.00 | 0.31 | 0.00 |
| 8 | 0.34 | 2.23 | 0.14 | 0.00 | 0.12 | 0.16 | 0.07 | 0.56 | 0.00 | 0.00 |
| 9 | 0.85 | 0.23 | 0.01 | 0.07 | 0.09 | 1.16 | 0.16 | 0.02 | 0.01 | 0.00 |
 

Cette table des scores permet de retrouver l'ordre des bandelettes par la méthode suivante :

- on choisit un numéro `n0` de bandelette candidate pour être la bandelette de gauche : il s'agit de
  la bandelette ayant la colonne de zéros (ou une colonne ayant des scores les plus faibles
  possibles);
- on cherche l'indice du maximum des scores sur la ligne `n0` : cela fournit `n1`
- on cherche l'indice du maximum des scores sur la ligne `n1` : cela fournit `n2`
- ...
- on répète l'opération précédente jusqu'à épuiser l'ensemble des bandelettes


## exemple 

on choisit `n0`=9

- Le maximum de la ligne 9 se trouve à l'indice `n1`=5.
- Le maximum de la ligne 5 se trouve à l'indice `n2`=7.
- Le maximum de la ligne 7 se trouve à l'indice `n3`=2.
- Le maximum de la ligne 2 se trouve à l'indice `n4`=0.
- Le maximum de la ligne 0 se trouve à l'indice `n5`=8.
- Le maximum de la ligne 8 se trouve à l'indice `n6`=1.
- Le maximum de la ligne 1 se trouve à l'indice `n7`=4.
- Le maximum de la ligne 4 se trouve à l'indice `n8`=6.
- Le maximum de la ligne 6 se trouve à l'indice `n9`=3.
   
On a parcouru toutes les bandelettes, et on a trouvé une solution potentielle :
`[9,5,7,2,0,8,1,4,6,3]`.
   


