Hiding and recovering an image using Linear Algebra
(This is a continuation of the previous post on morphing images (here). Since the concepts and code presented here build on the previous code, it is highly recommended to view the previous post first.)
In the previous post where we morphed one image into another, it was visually noticeable that during the transition, the two original images were discernable at the same time. In other words, the morphing process retained information for both images as one image dissolved while the other faded in. The image that is fading out was effectively being hidden away as we saw more of the new image.
The obvious question then arises: given the new image and the morphing process, can we recover the hidden image fully? Let's figure this out.
Back to linear algebra
If we think about the difference vector between the two images and the general parametric equation of a line, we might notice that for the equation of the line running along the vector direction, the length of the difference vector is irrelevant.
$$\begin{align}\ell_3 &=\{\mathbf v_1 + t*(\mathbf v_2-\mathbf v_1)\,:\, t \in \mathbb R \}\\ &=\{\mathbf v_2 + t*(\mathbf v_1-\mathbf v_2)\,:\, t \in \mathbb R \}\end{align}$$We could have a shorter (or longer) vector $\mathbf v_3^{'}$ (whereas $\mathbf v_3=\mathbf v_2-\mathbf v_1$), yet we would always find the correct vector length for $t*\mathbf v^{'}_3$ to get to $\mathbf v_2$ exactly, by searching for just the right value of the scalar $t$. This is the same intuition we could use to recover another image along the difference vector (in fact, any image along the line that runs through this vector, even those outside the vector itself).
We therefore need two points along the difference vector to form a shorter vector. We could select any two points, but we will pick the last two images in the morphing sequence so the images will look similar. We can then calculate a scalar that would bring us to the other image exactly, recreating that other image. And then we are done.
So, let's write the code. This would be mostly similar to the previous code.
# import libraries
%matplotlib inline
import numpy as np
import matplotlib.pyplot as plt
#from scipy import misc
from PIL import Image
def get_image(fname):
im=Image.open(fname)
y,x=im.size
img_dim=(x,y)
img=np.array(im)
# convert RGB to grayscale
r,g,b=img[:,:,0],img[:,:,1],img[:,:,2]
img=0.2989*r+0.5870*g+0.1140*b
img=np.abs(img-255) # invert colors
img=img.flatten() # flatten arrays
return img,img_dim
img1,im_dim=get_image('img_A.jpg')
img2,_=get_image('img_B.jpg')
With pictures of happy people loaded (copyright reserved :) ), let's display the sequence of morphed images, just like in the previous post.
def display_vector(img,im_dim,pix_size=1):
plt.figure(figsize=(img.shape[0]*pix_size,img.shape[0]*pix_size))
for i,im in enumerate(img):
ax=plt.subplot(1,len(img),i+1)
#ax.set_title(img)
ax.set_axis_off()
a=np.reshape(im,(im_dim))
ax.imshow(a,cmap='Greys',interpolation='nearest')
plt.show()
# build a line segment/set of 'point images' via a parameterized line equation
img3_set=np.array([img1+t*(img2-img1) for t in np.linspace(0,1,num=11,endpoint=True)])
display_vector(img3_set,im_dim)
The idea is to generate the equation of the line $\ell_3$ by using two of these images. This gives us the correct vector direction to get to $\mathbf v_1$. We then extrapolate by scaling $\ell_3$ to get to $\mathbf v_1$ exactly, in theory anyway.
To show that we are indeed going to recover the first image, without using its existing loaded copy, we should delete it.
# delete img1 and check references
print('Deleting img1...')
del img1
print('Printing img1... (an ERROR message line will print if there is an error.)')
try:
print(img1.shape)
except Exception as e:
print('ERROR:',e)
Now we are sure that there is no trace of the first image.
Next, let us try to recover it. Since we generated 11 images while morphing, we can use the 11th image (which is the second of the source images, the target of the morphing), and the 10th image in the sequence (the last morphed image). We want the closest neighbors possible so the images would look alike naturally and would not show a superimposed outline of the image we are trying to recover.
To recover the first image in the morphing sequence (which is the first of the source images, the starting point of the morphing), we need to calculate $t$. This is simply $t=10$.
# reconstruct img1 from img2 and a member of img3
img4=np.array([img2+10*(img3_set[9]-img2)])
display_vector(np.array([img2,img3_set[9],img4]),im_dim,pix_size=4)
So there. We recovered the first image. We extracted a relatively clean image from a grainy source. We can prove this also at the pixel level by comparing the two images.
img1,_=get_image('img_A.jpg')
img_delta=img1-img4
print('Difference of the two image vectors:',img_delta)
print('Count of non-zeroes, threshold of 1e-5:',np.sum(img_delta>1e-5))
The above result proves that the two images are approximately equal. The insignificant differences are due to computational limits.
Let's see if we can do the opposite, that is, recover a grainy image from a clean source. We know this is possible --the math is exactly the same-- but I want to show a side effect that is not obvious above because of the grainy source image.
img1,_=get_image('img_B.jpg')
img2,_=get_image('img_A.jpg')
# build a line segment/set of 'point images' via a parameterized line equation
img3_set=np.array([img1+t*(img2-img1) for t in np.linspace(0,1,num=11,endpoint=True)])
display_vector(img3_set,im_dim)
# delete img1 and check references
print('Deleting img1...')
del img1
print('Printing img1... (an ERROR message line will print if there is an error.)')
try:
print(img1.shape)
except Exception as e:
print('ERROR:',e)
# reconstruct img1 from img2 and a member of img3
img4=np.array([img2+10*(img3_set[9]-img2)])
display_vector(np.array([img2,img3_set[9],img4]),im_dim,pix_size=4)
We recovered the first image, but the middle picture is obviously fake, with apparition-like artifacts from the first image superimposed (hard to see at this resolution, but we can still see the Batman cowl over the headboard). Can we avoid this?
Sure, we can. We simply create a shorter line segment. We can do that by morphing with more images, so the penultimate image in the morphing sequence will be very similar to the source image.
Let's try it below. We will not show the intervening morphed images since we plan to create a lot. [On second thought, we do not have to create all the interim morph images. We just need the last morph.]
img1,_=get_image('img_B.jpg')
# build a line segment/set of 'point images' via a parameterized line equation
#img3_set=np.array([img1+t*(img2-img1) for t in np.linspace(0,1,num=101,endpoint=True)])
#display_vector(img3_set,im_dim)
# we do not need to create the whole set, just the penultimate member of the set
print(np.linspace(0,1,num=101,endpoint=True))
img3_set=img1+0.99*(img2-img1)
We delete the first image once again.
# delete img1 and check references
print('Deleting img1...')
del img1
print('Printing img1... (an ERROR message line will print if there is an error.)')
try:
print(img1.shape)
except Exception as e:
print('ERROR:',e)
Then we re-construct the little dude in the Batman costume (and quite frankly, he needs to adjust the cowl if he wants to successfully find baddies, fight crime and deliver the hammers of justice).
# reconstruct img1 from img2 and a member of img3
img4=np.array([img2+100*(img3_set-img2)])
display_vector(np.array([img2,img3_set,img4]),im_dim,pix_size=4)
Success! As you will notice, the second image no longer shows the ghostly apparition of Kid Batman.
How can we use this to hide images?
Consider two persons, Person A and Person B. Person A sends Person B image #1. Person B wants to send image #2 to Person A discreetly. Person B hides image #2 inside image #1, creating image #3. Person B sends image #3 to Person A, along with the number to recover image #2 via a separate channel. This number could perhaps also be embedded inside image #3. Person A can then easily extract image #2.
But we have to consider one more problem. We demonstrated a recovery sequence that uses the same full image array throughout, without saving and loading from an image file in the interim. The communications scenario described above will require the Numpy arrays to be saved into an image file before being sent across. Most files are created based on lossy compression algorithms, so the receiver might not be able to rebuild exactly the same full image array.
I am not sure about this assertion. I am unfamiliar with how image compression algorithms compress and extract images, and if different variants/versions of the same decoders produce different extracts from the same file, even if by only a few pixels, or if different compression algorithms ultimately create the same image array. For example, in the array->jpeg->array->png->array sequence, would the first and last arrays similar? I leave this to readers. These differences, if any, would cause distortions in the recovery portion, which might compound underflow/overflow risks.
Numerical stability
Basing the recovery on a morphed image that is only very slightly shifted might create some problems, if the difference becomes too small. As the vector difference becomes small, computational limits might cause accumulate rounding discrepancies (underflow/overflow) where the resulting vector $\mathbf v_3$ will not exactly reach $\mathbf v_2$. For instance, if two pixels are different by 100, dividing into 100 morphs would mean a gradual increase of 1 each time. But this might cause other pixels to increase by less than 1.0 each time, and integer rounding (RGB and grayscale are integers from 0 to 255) might cause some instabilities. We have even seen small differences even with just 10 morphed images, so 100 would definitely veer farther from $\mathbf v_2$. For simple purposes, as we did here, this is not a big concern.