$\require{color}$ $\require{xcolor}$ $\require{cancel}$ $\newcommand{\myfbox}[1]{\fcolorbox{red}{white}{$\textrm{#1}$}}$ $\require{stmaryrd}$ $\newcommand{\ient}{[\![}$ $\newcommand{\rrbracket}{]\!]}$ $\newcommand{\llbracket}{[\![}$ $\newcommand{\fient}{]\!]}$ $\newcommand{\R}{\mathbb R}$ $\newcommand{\K}{\mathbb K}$ $\newcommand{\N}{\mathbb N}$ $\newcommand{\C}{\mathbb C}$ $\newcommand{\P}{\mathbb P}$ $\newcommand{\E}{\mathbb E}$ $\newcommand{\V}{\mathbb V}$ $\newcommand{\Z}{\mathbb Z}$ $\newcommand{\dt}{\mathrm d}$ $\newcommand{\sh}{\operatorname{sh}}$ $\newcommand{\ch}{\operatorname{ch}}$ $\newcommand{\id}{\operatorname{Id}}$ $\newcommand{\mat}{\operatorname{mat}}$ $\newcommand{\sp}{\operatorname{Sp}}$ $\newcommand{\In}{\operatorname{I}}$ $\newcommand{\vect}{\operatorname{Vect}\ }$ $\newcommand{\rg}{\operatorname{rg}}$ $\newcommand{\tr}{\operatorname{Tr}}$ $\newcommand{\dis}{\displaystyle}$ $\renewcommand{\Im}{\operatorname{Im}}$ $\newcommand{\im}{\operatorname{Im}}$ $\newcommand{\bordermatrix}[3]{ \begin{matrix} \begin{matrix}#1\end{matrix} & \\ #3 & \hspace{-1em} \begin{matrix}#2\end{matrix} \end{matrix}}$ $\newcommand{\fonction}[5]{#1\ \colon \left\{\begin{array}{ccl}#2 & \longrightarrow & #3\\#4 & \longmapsto & #5\end{array}\right.}$ $\newcommand{\fonctionsansnom}[4]{\left\{\begin{array}{ccl}#1 & \longrightarrow & #2\\#3 & \longmapsto & #4\end{array}\right.}$ $\newcommand{\revdots}{\mathinner{\mkern1mu\raise1pt{\kern7pt\hbox{.}}\mkern2mu\raise4pt\hbox{.}\mkern2mu\raise7pt\hbox{.}\mkern1mu}}$ $\newcommand{\tendvers}[2]{\xrightarrow[#1\to#2]{}}$
import matplotlib.pyplot as plt
import numpy as np
def conv_binaire(n):
"""
Entrée : un entier naturel n
Sortie : la chaîne de caractères correspondant à sa décomposition binaire
"""
if n == 0:
return "0"
else:
binaire = ""
while n > 0:
binaire = str(n % 2) + binaire
n = n // 2
return binaire
conv_binaire(6)
'110'
Pour la conversion "réciproque", on peut utiliser la méthode de Hörner, qui minimise le nombre de multiplications à faire :
def conv_decimal(L):
"""
Entrée : une chaîne de caractères de 0 et de 1
Sortie : l’entier en base 10 correspondant.
"""
s = len(L)
n = int(L[0])
for i in range(1,s):
n = n * 2 + int(L[i])
return n
def conv_decimal(L):
"""
Entrée : une chaîne de caractères de 0 et de 1
Sortie : l’entier en base 10 correspondant.
"""
s = int(L[0])
for l in L[1:]:
s = s * 2 + int(l)
return s
conv_decimal("100")
4
def inverse(S):
R = ""
for s in S:
if s == "1":
R = R + "0"
else:
R = R + "1"
return R
inverse("10011")
'01100'
Pour obtenir la représentation de $-n$ (avec complément à $2$) :
def oppose(n, b):
assert n > 0 and n <= 2**(b - 1)
S = conv_binaire(n) # on convertit n en binaire sur b bits
S = "0" * (b - len(S)) + S # on utilise exactement b bits
S = inverse(S) # on inverse les bits
R = "" # le résultat à renvoyer
k = 1
while S[-k] == "1":
R = "0" + R
k +=1
R = "1" + R
R = S[0:b-k] + R
return R
oppose(120,8)
'10001000'
np.binary_repr(-120, width=8)
'10001000'
for k in range(1,128):
if oppose(k,8) != np.binary_repr(-k, width=8):
print(k)
def conv_binaire_r(n, b):
assert n >= -2**(b - 1) and n <= 2**(b - 1) - 1
if n >= 0:
S = conv_binaire(n)
return "0" * (b - len(S)) + S
else:
return oppose(-n,b)
conv_binaire_r(-1, 8)
'11111111'
conv_binaire_r(1, 8)
'00000001'
for k in range(-128,127):
if conv_binaire_r(k, 8) != np.binary_repr(k, width=8):
print(k)
def conv_decimal_r(S, b):
if S[0] == "0":
return conv_decimal(S)
else:
return conv_decimal(S[1:]) - 2**(b - 1)
conv_decimal_r('00000101', 8)
5
conv_decimal_r('11111111', 8)
-1
def stegano(S1, S2):
return S1[:4] + S2[:4]
M = plt.imread("eleves.png")
M = (M * 255).astype(np.uint8)
N = plt.imread("paysage.png")
N = (N * 255).astype(np.uint8)
M[12][24]
array([ 14, 30, 54, 255], dtype=uint8)
plt.figure(figsize=(4, 4))
plt.imshow(M)
plt.axis("off")
plt.show()
On va «cacher» les élèves dans l'image du paysage :
taille = len(M)
P = [[[0, 0, 0] for i in range(taille)] for j in range(taille)]
for i in range(taille):
for j in range(taille):
for k in range(3):
S1 = np.binary_repr(N[i][j][k], width=8)
S2 = np.binary_repr(M[i][j][k], width=8)
P[i][j][k] = conv_decimal(stegano(S1, S2))
plt.figure(figsize=(4, 4))
plt.imshow(P)
plt.axis("off")
plt.title("Les élèves sont cachés dans cette image")
plt.show()
On peut chercher à la comparer à l'image originale :
plt.figure(figsize=(6, 6))
plt.subplot(1, 2, 1) # sous-figure n°1 (1 ligne, 2 colonnes, position 1)
plt.imshow(N)
plt.axis('off')
plt.title("Image originale")
plt.subplot(1, 2, 2) # sous-figure n°2 (1 ligne, 2 colonnes, position 2)
plt.imshow(P)
plt.axis('off')
plt.title("Image perturbée")
plt.show()
On peut maintenant chercher à retrouver l'image cachée dans l'image précédente :
L = [[[0, 0, 0] for i in range(taille)] for j in range(taille)]
for i in range(taille):
for j in range(taille):
for k in range(3):
S = np.binary_repr(P[i][j][k], width=8)
S = S[4:] + 4 * "0"
L[i][j][k] = conv_decimal(S)
# taille et résolution des figures
plt.rcParams['figure.figsize'] = [4, 4]
plt.imshow(L)
plt.axis("off")
plt.show()
On peut la comparer avec l'image originale :
plt.figure(figsize=(6, 6))
plt.subplot(1, 2, 1) # sous-figure n°1 (1 ligne, 2 colonnes, position 1)
plt.imshow(M)
plt.axis('off')
plt.title("Image originale")
plt.subplot(1, 2, 2) # sous-figure n°2 (1 ligne, 2 colonnes, position 2)
plt.imshow(L)
plt.axis('off')
plt.title("Image retrouvée")
plt.show()
u, v = 0, 1
L = []
for k in range(12):
u, v = v, u + v
L.append(v)
print(L)
[1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233]
def zeckendorf(n):
m = n
S = ""
i = len(L) - 1
while m > 0:
while L[i] > m:
i -= 1
S = S + "0"
S = S + "1"
m = m - L[i]
i -= 1
return S + "0" * (12 - len(S))
zeckendorf(240)
'100000001010'
M = plt.imread("eleves.png")
M = (M * 255).astype(np.uint8)
N = plt.imread("paysage.png")
N = (N * 255).astype(np.uint8)
def stegano_fib(S1, S2):
return S1[:6] + S2[:6]
def conv_decimal_fib(S):
return sum(L[len(L) - i - 1] * int(S[i]) for i in range(len(L)))
taille = len(M)
P = [[[0, 0, 0] for i in range(taille)] for j in range(taille)]
for i in range(taille):
for j in range(taille):
for k in range(3):
S1 = zeckendorf(N[i][j][k])
S2 = zeckendorf(M[i][j][k])
P[i][j][k] = conv_decimal_fib(stegano_fib(S1, S2))
plt.figure(figsize=(4, 4))
plt.imshow(P)
plt.axis("off")
plt.show()
Clipping input data to the valid range for imshow with RGB data ([0..1] for floats or [0..255] for integers).
Effectivement, on peut, avec cette méthode, dépasser la valeur $255$. Python tronque alors la valeur à $255$ avant d'afficher l'image... Cela peut provenir de deux problèmes :
"11"
, qui ne sont pas des représentations de Zeckendorf valides.Le second point se règle au moment de l'affichage, en prenant le minimum entre la valeur de chaque couleur de chaque pixel et $255$, à l'aide de la fonction np.minimum()
qui s'applique composante par composante.
Le premier point est plus problématique : la conversion inverse ne redonne pas les bits initiaux. On peut régler ce problème de la manière suivante :
def stegano_fib(S1, S2):
if S1[5] == "1" and S2[0] == "1":
return S1[:5] + "0" + S2[:6]
else:
return S1[:6] + S2[:6]
taille = len(M)
P = [[[0, 0, 0] for i in range(taille)] for j in range(taille)]
for i in range(taille):
for j in range(taille):
for k in range(3):
S1 = zeckendorf(N[i][j][k])
S2 = zeckendorf(M[i][j][k])
P[i][j][k] = conv_decimal_fib(stegano_fib(S1, S2))
plt.figure(figsize=(4, 4))
plt.imshow(np.minimum(P, 255))
plt.axis("off")
plt.show()
On peut désormais essayer de retrouver l'image cachée :
C = [[[0, 0, 0] for i in range(taille)] for j in range(taille)]
for i in range(taille):
for j in range(taille):
for k in range(3):
S = zeckendorf(P[i][j][k])
S = S[6:] + 6 * "0"
C[i][j][k] = conv_decimal_fib(S)
plt.figure(figsize=(4, 4))
plt.imshow(C)
plt.axis("off")
plt.show()