Python 3.4
- Bonus 1: Self inverse: repeating restores the original image.
- Optional key image: original image can only be restored by using the same key image again.
- Bonus 2: Producing pattern in the output: key image is approximated in the scrambled pixels.
When bonus 2 is achieved, by using an additional key image, bonus 1 is not lost. The program is still self inverse, provided it is run with the same key image again.
Standard usage
Test image 1:
Test image 2:
Running the program with a single image file as its argument saves an image file with the pixels scrambled evenly over the whole image. Running it again with the scrambled output saves an image file with the scrambling applied again, which restores the original since the scrambling process is its own inverse.
The scrambling process is self inverse because the list of all pixels is split into 2-cycles, so that every pixel is swapped with one and only one other pixel. Running it a second time swaps every pixel with the pixel it was first swapped with, putting everything back to how it started. If there are an odd number of pixels there will be one that does not move.
Thanks to mfvonh's answer as the first to suggest 2-cycles.
Usage with a key image
Scrambling Test image 1 with Test image 2 as the key image
Scrambling Test image 2 with Test image 1 as the key image
Running the program with a second image file argument (the key image) divides the original image into regions based on the key image. Each of these regions is divided into 2-cycles separately, so that all of the scrambling occurs within regions, and pixels are not moved from one region to another. This spreads out the pixels over each region and so the regions become a uniform speckled colour, but with a slightly different average colour for each region. This gives a very rough approximation of the key image, in the wrong colours.
Running again swaps the same pairs of pixels in each region, so each region is restored to its original state, and the image as a whole reappears.
Thanks to edc65's answer as the first to suggest dividing the image into regions. I wanted to expand on this to use arbitrary regions, but the approach of swapping everything in region 1 with everything in region 2 meant that the regions had to be of identical size. My solution is to keep the regions insulated from each other, and simply shuffle each region into itself. Since regions no longer need to be of similar size it becomes simpler to apply arbitrary shaped regions.
Code
import os.path
from PIL import Image # Uses Pillow, a fork of PIL for Python 3
from random import randrange, seed
def scramble(input_image_filename, key_image_filename=None,
number_of_regions=16777216):
input_image_path = os.path.abspath(input_image_filename)
input_image = Image.open(input_image_path)
if input_image.size == (1, 1):
raise ValueError("input image must contain more than 1 pixel")
number_of_regions = min(int(number_of_regions),
number_of_colours(input_image))
if key_image_filename:
key_image_path = os.path.abspath(key_image_filename)
key_image = Image.open(key_image_path)
else:
key_image = None
number_of_regions = 1
region_lists = create_region_lists(input_image, key_image,
number_of_regions)
seed(0)
shuffle(region_lists)
output_image = swap_pixels(input_image, region_lists)
save_output_image(output_image, input_image_path)
def number_of_colours(image):
return len(set(list(image.getdata())))
def create_region_lists(input_image, key_image, number_of_regions):
template = create_template(input_image, key_image, number_of_regions)
number_of_regions_created = len(set(template))
region_lists = [[] for i in range(number_of_regions_created)]
for i in range(len(template)):
region = template[i]
region_lists[region].append(i)
odd_region_lists = [region_list for region_list in region_lists
if len(region_list) % 2]
for i in range(len(odd_region_lists) - 1):
odd_region_lists[i].append(odd_region_lists[i + 1].pop())
return region_lists
def create_template(input_image, key_image, number_of_regions):
if number_of_regions == 1:
width, height = input_image.size
return [0] * (width * height)
else:
resized_key_image = key_image.resize(input_image.size, Image.NEAREST)
pixels = list(resized_key_image.getdata())
pixel_measures = [measure(pixel) for pixel in pixels]
distinct_values = list(set(pixel_measures))
number_of_distinct_values = len(distinct_values)
number_of_regions_created = min(number_of_regions,
number_of_distinct_values)
sorted_distinct_values = sorted(distinct_values)
while True:
values_per_region = (number_of_distinct_values /
number_of_regions_created)
value_to_region = {sorted_distinct_values[i]:
int(i // values_per_region)
for i in range(len(sorted_distinct_values))}
pixel_regions = [value_to_region[pixel_measure]
for pixel_measure in pixel_measures]
if no_small_pixel_regions(pixel_regions,
number_of_regions_created):
break
else:
number_of_regions_created //= 2
return pixel_regions
def no_small_pixel_regions(pixel_regions, number_of_regions_created):
counts = [0 for i in range(number_of_regions_created)]
for value in pixel_regions:
counts[value] += 1
if all(counts[i] >= 256 for i in range(number_of_regions_created)):
return True
def shuffle(region_lists):
for region_list in region_lists:
length = len(region_list)
for i in range(length):
j = randrange(length)
region_list[i], region_list[j] = region_list[j], region_list[i]
def measure(pixel):
'''Return a single value roughly measuring the brightness.
Not intended as an accurate measure, simply uses primes to prevent two
different colours from having the same measure, so that an image with
different colours of similar brightness will still be divided into
regions.
'''
if type(pixel) is int:
return pixel
else:
r, g, b = pixel[:3]
return r * 2999 + g * 5869 + b * 1151
def swap_pixels(input_image, region_lists):
pixels = list(input_image.getdata())
for region in region_lists:
for i in range(0, len(region) - 1, 2):
pixels[region[i]], pixels[region[i+1]] = (pixels[region[i+1]],
pixels[region[i]])
scrambled_image = Image.new(input_image.mode, input_image.size)
scrambled_image.putdata(pixels)
return scrambled_image
def save_output_image(output_image, full_path):
head, tail = os.path.split(full_path)
if tail[:10] == 'scrambled_':
augmented_tail = 'rescued_' + tail[10:]
else:
augmented_tail = 'scrambled_' + tail
save_filename = os.path.join(head, augmented_tail)
output_image.save(save_filename)
if __name__ == '__main__':
import sys
arguments = sys.argv[1:]
if arguments:
scramble(*arguments[:3])
else:
print('\n'
'Arguments:\n'
' input image (required)\n'
' key image (optional, default None)\n'
' number of regions '
'(optional maximum - will be as high as practical otherwise)\n')
JPEG image burn
.jpg files are processed very quickly, but at the cost of running too hot. This leaves a burned in after image when the original is restored:
But seriously, a lossy format will result in some of the pixel colours being changed slightly, which in itself makes the output invalid. When a key image is used and the shuffling of pixels is restricted to regions, all of the distortion is kept within the region it happened in, and then spread out evenly over that region when the image is restored. The difference in average distortion between regions leaves a visible difference between them, so the regions used in the scrambling process are still visible in the restored image.
Converting to .png (or any non-lossy format) before scrambling ensures that the unscrambled image is identical to the original with no burn or distortion:
Little details
- A minimum size of 256 pixels is imposed on regions. If the image were allowed to split into regions that are too small, then the original image would still be partially visible after scrambling.
- If there's more than one region with an odd number of pixels then one pixel from the second region is reassigned to the first, and so on. This means there can only ever be one region with an odd number of pixels, and so only one pixel will remain unscrambled.
- There is a third optional argument which restricts the number of regions. Setting this to 2 for example will give two tone scrambled images. This may look better or worse depending on the images involved. If a number is specified here, the image can only be restored using the same number again.
- The number of distinct colours in the original image also limits the number of regions. If the original image is two tone then regardless of the key image or the third argument, there can only be a maximum of 2 regions.
The question is a very long-winded way of saying "Write an encryption algorithm for images, whose output is an image." – David Richerby – 2014-07-24T09:10:42.543
3@DavidRicherby … that uses the same pixels/colors. Five black pixels in the "plain image" -> five black pixels in the "cipher image". – Daniel Beck – 2014-07-24T09:34:30.993
What's the meaning of your "bonus"? – Martin Ender – 2014-07-24T10:54:56.157
@MartinBüttner I thought if two answers will have same votes count, the one with more bonuses will be chosen as accepted. Pretty rare situation I think)) – Somnium – 2014-07-24T11:08:57.253
2@user2992539 All right, in that case you might want to explicitly state that this is used as the tie-breaker. Otherwise, just saying it's a bonus isn't very meaningful. – Martin Ender – 2014-07-24T11:11:45.980
.jpg isn't helpful as a test image, as saving the output as .jpg again can lose some of the quality so that the pixels no longer match. Is it worth posting a .png version of your Test image 1? I know we could write programs to take account of that and write lossless .jpg files but that seems like a separate challenge. – trichoplax – 2014-07-25T00:03:15.907
3
This question made me think of Arnold's cat map. I don't think it's quite suitable for this purpose but it's interesting in the same way - repeating the map enough times gets you back to the original image.
– trichoplax – 2014-07-25T00:30:48.623@githubphagocyte Oops seems like I have taken wrong image from my computer) It should be PNG). About Arnold's cat map, cool, didn't know about, however, I don't understand how much iterations do you need to reverse image to original. – Somnium – 2014-07-25T06:01:08.190
The total number of iterations to get back to the original image can be hundreds even for a small image with Arnold's cat map. You could perform half this many iterations, then repeating that would give you the original again. However, for some image sizes half way through just gives you the original image upside down, which isn't much use here... Also it's only for square images - you'd have to expand it to accept arbitrary rectangles to use it here. – trichoplax – 2014-07-25T08:08:27.857
@githubphagocyte Ok, likely it's too hard to apply this algorithm here, however, thanks anyway for mentioning it. – Somnium – 2014-07-25T08:15:01.160
Could you edit the question to replace the accidental jpg image with the png image you had originally intended? – trichoplax – 2014-07-27T09:20:07.787
@githubphagocyte I can't, CodeGolf converts it automatically to JPG. It seems first time it also was auto-converted. – Somnium – 2014-07-27T18:58:24.777
It wasn't you - I've realised in uploading my scrambled images that they are being automatically converted to jpg when uploading png, but only for the larger file sizes - I'm guessing anything over 500 KB. Test image 2 is more compressed and uploads as png. The jpg format did give some interesting distortion in my output images though... – trichoplax – 2014-07-27T20:44:15.527
Ah - I see you already worked this out... – trichoplax – 2014-07-27T20:44:41.107
A similar problem was exposed to me as a introductory student in an assignment and we used a method that completely obscured the image, as opposed to some of the solutions here. I can't post my solution, as it would violate our Honor Code, but I encourage you to take a look at how we did it. If you do use this method, please do not post any code, unless you significantly alter the technique. It's a really cool little assignment for beginners that I had a lot of fun with and I would hate to have it spoiled for anyone else by being able to access a solution online. http://www.cs.princeton.edu/co
– the_hands_that_thieve – 2014-07-28T12:18:08.4604
Now elsewhere on the Stack Exchange network: Security.SE of all places
– Doorknob – 2014-07-29T06:34:33.323I'm bit puzzled as why don't I see the FFT as a solution here. – PermanentGuest – 2014-07-29T08:34:26.973
@PermanentGuest a Fast Fourier Transform wouldn't be self inverse for the first bonus but I'd still like to see a solution using it, and what patterns emerge in the output for the second bonus... – trichoplax – 2014-07-29T11:05:33.840
@PermanentGuest a Hartley Transform would be self inverse but neither transform would maintain the original pixel colours so both would be invalid answers here.
– trichoplax – 2014-07-29T11:08:53.513@githubphagocyte : Ah, I forgot about the color aspect for a moment. – PermanentGuest – 2014-07-29T12:34:07.527