On s'intéresse dans cette partie à un problème de transformation de matrice binaire. On peut voir ces matrices comme des grilles où certaines cases contiennent un point (les 1) et où d'autres sont vides (les 0). Il est possible de contracter deux lignes voisines ou deux colonnes voisines en fusionnant les cases adjacentes à la seule condition que deux points ne se retrouvent pas dans la même case. Autrement dit, deux lignes voisines contenant des 1 sur la même colonne ne peuvent être fusionnées, de même pour deux colonnes voisines contenant des 1 sur la même ligne. Par exemple, sur l'image de droite, il n'est pas possible de fusionner les lignes 1 et 2 de la matrice M1. Par contre, on peut contracter, comme c'est fait dans l'image, les colonnes 1 et 2, puis les lignes 2 et 3 pour obtenir la matrice M3.
L'objectif est de contracter la matrice le plus possible. On mesure la contraction avec la densité de la matrice : le nombre de paires de 1 voisins, diagonales comprises. Par exemple, la densité de la matrice M3 est 6. On cherche une suite de contractions de lignes et de colonnes qui maximise la densité de la matrice résultante.