December 14, 2008
Shuffling Pixels

In my "Here be Pixels" talk one of the things I showed was how to use a combination of noise and the displacementMap filter to encrypt and decrypt images or data with Flash. In case you didn't see it, here's the principle behind it as a Peacock composition:
666 54321 12345.egg by mario on Aviary The following post is about a related issue which uses a very similar technique, but I will also explain the encryption decryption method along the way.

Imagine you want to visit every pixel in an image in random order but you do not want to visit any pixel more than once. Obviously what you cannot to is to simply pick a series of random x/y coordinates and hope that you will hit non-visited pixels as often as possible. The problem is that even for a very small image of 100x100 pixels (which contains 10000 pixels) the probability that you hit a non-visited pixel will change from 100% (when you set the first pixel) to 0.01% (when you try to hit that last non-visited pixel) whilst you proceed through the image.

So another approach you might be tempted to try is to first store a list of all possible coordinates in an array then shuffle that list and finally visit the coordinates in the order they get served from that array. This will work and for small images it might even be okay to create and shuffle a list of 10000 elements. But when you get into areas of typically sized images this approach is definitely not optimum. Having to shuffle 480000 items in realtime doesn't sound like fun.

So what's the alternative? The one way to do it is actually being used internally by the Flash player - inside the notorious BitmapData.pixelDissolve() function. It uses a so called linear feedback shift register which is a really nifty numerical apparatus that produces a unique random-looking order of all integers between 1 and x. The only issue is that it's pretty hard to implement a random seed for this technique which is why you don't find that as a property in the Flash implementation. This means that for each image of the same dimension the order in which the pixels are visited will always be identical.

But there's obviously another option. Imagine an image like a gigantic 2-dimensional Rubic's Cube. Now shift each vertical pixel column by a different random amount up or down. Those pixels that end outside the image will wrap around and be reinserted on the other side. Repeat that process for all pixel rows. Then once more for the columns and for the rows again. This is the equivalent of randomly rotating a magic cube. Now the interesting part is that you will not loose a single pixel in this process. No pixel will be accidentaly overwritten by another one moving over it. This means each original pixel will still be there only on a different location. What's even nicer is that if you knew the exact order in which the columns and rows had been offset you could revert that process and unscramble the image when you just apply it backwards. That is what actually happens in the Peacock example above. BTW - this technique is not limited to bitmaps, you can use it to scramble and unscramble any kind of data.

But what I actually wanted to show you here is another class which employs no bitmapData, noise or displacementMap filters at all but just uses plain math to achieve a similar result: the CoordinateShuffler class will return you a list of uniquely shuffled coordinates for images of arbitrary sizes. Since it only needs to create two small lookup tables it is very lightweight and fast and should come handy whenver you want to check a part of an image's pixels randomly, spread elements over an image or create a random transition but want to make sure that in the end all pixels are covered.

In the demo you can set the random seed, the amount of horizontal + vertical shuffle rounds and the size of the lookup table which controls the amount of each column's and row's offset. The smaller the table size is the less random the shuffling will look, nevertheless this might be still interesting for certain graphical effects. The long slider controls the index, meaning "give me the next 500 random coordinates starting from index 10012". When you select "accumulate" it means "give me all random coordinates from index 0 up to index 53100".

In the end this might look like just a different kind of pixelDiffusion filter but believe me - it has many more interesting uses. For example the AutoPainter and the Stippling hubs inside of Peacock are using it, too.

CoordinateShuffler Demo | source

Posted at December 14, 2008 09:41 PM | Further reading
Comments

Nah, I guess if I would still care for Flash or coding this would get me all excited. But I do love your choice of imagery!

By the way here is one of my favorite Muppet skits:
http://www.youtube.com/watch?v=Jt8Q7Fsa_Vs

But the outtake is even better:
http://www.youtube.com/watch?v=UH8F0KaiipE
Dunno why they didn't use that one...

Posted by: Holger on December 16, 2008 07:14 AM

Hi Mario,
Another option for dealing with random pixels would be to use a free-list algorithm.

At first you have N = Width x Height and a free list L = {0,N} (N pixels free at position 0). Then you take a K = Random(N) pixel, and browse your free list to find the corresponding free-pixel. You then split the free list into two parts, L = {0,K-1},{K+1,N-K-1} and then loop until your free-list is empty.

Posted by: Nicolas on December 21, 2008 07:40 PM

But if I understand you correctly that would still mean I'd have to maintain a list of N pixels (or rather several lists which get consecutively smaller). I haven't tried this approach but it sounds like it might create quite some overhead for Flash for all the memory handling. My approach does only require a much smaller amount of memory.

Posted by: on December 22, 2008 02:19 PM

Hi,
Very nice and unique approach. Won't it have an issue with the memory? IMO it might be.
But again, thanks for the crispy explanation

Happy New Year

Posted by: Platfuse on January 4, 2009 11:53 PM

The whole idewa is that this method does not require that much memory - by default the shuffling lookup table is an array of 3 * 256 Numbers. But for most purposes even a smaller lookup table is entirely sufficient.

The only case where you might have a memory issue is when you use the getCoordinates() method in case you want a long list of points. But the usual approach is to just retrieve one point at a time using getCoordinate()

Posted by: Mario Klingemann on January 5, 2009 12:25 PM

Isn't there a bug in setters of width and height? I am pretty sure that the argument name shouldn't be "value" ;) Nice stuff by the way :)

Posted by: szataniol on April 29, 2009 12:49 PM

Yes, you are right, that should be "= value" instead of "= width" and "= hight".

Posted by: Mario Klingemann on April 29, 2009 04:36 PM
Post a comment
Name:


Email Address:


URL:


Comments:


Remember info?



Thank you!

Most Visited Entries
Sketches, Works & Source Code
Lectures
Contact
Backlog
In Love with
Powered by
Movable Type 2.661

© Copyright Mario Klingemann

Syndicate this site:
RSS 1.0 - RSS 2.0

Quasimondo @ flickr
Quasimondo @ LinkedIn
Quasimondo @ Twitter
Quasimondo @ Facebook
Quasimondo @ MySpace
Quasimondo is a Bright
Citizen of the TRansnational Republic
My other blog in german
Impressum


My family name is written Klingemann,
not Klingelmann, Klingeman, Klingaman, Kingemann,
Kindermann, Killingaman, Klingman, Klingmann, Klingonman
Klingemman, Cleangerman, Klingerman or Kleangerman

profile for Quasimondo at Stack Overflow, Q&A for professional and enthusiast programmers