Holographic properties of bit-reversible permutation

About experiments with computer holography was written repeatedly. [ 1 , 2 , 3 ] I am just curious about this topic. I once experimented with bit-reversal permutation of images and accidentally discovered holographic properties. But first things first.

Reverse bits and bit-reversal permutation

Suppose there is a sequence of anything of length 2 ^L. And each element of this sequence has an index of 0, 1, 2, ..., 2 ^L -1. In binary representation, the index will look like this (b _L-1 b _L-2 ... b ₁ b ₀ ) ₂ . Then the reverse of the bits of this index will look like this (b ₀ b ₁ ... b _L-2 b _L-1 ) ₂ .
For example, the sequence given is a, b, c, d, e, f, g, h. Indexes of this sequence
will be the numbers: 0, 1, 2, 3, 4, 5, 6, 7; or in binary representation: 0b000, 0b001, 0b010, 0b011, 0b100, 0b101, 0b110, 0b111. First you need to rearrange the bits of each number in the reverse order, taking into account the maximum length of the binary number (L = 3): 0b000, 0b100, 0b010, 0b110, 0b001, 0b101, 0b011, 0b111 (decimal numbers: 0, 4, 2, 6, 1, 5, 3, 7.) Then, the elements of the original sequence are rearranged in accordance with the obtained indices: a, e, c, g, b, f, d, h. Thus, the sequence was rearranged in a bit-reverse order. For the future, we note that the adjacent pairs ae, cg, bf, dh consist of elements that are located in different halves of the original sequence.
If you need to convert a two-dimensional image, it is enough to rearrange the bits in both coordinates of each pixel.

Once again, I can say that a bit-reversible permutation can be made only for sequences of length exactly equal to a power of two (i.e. 4, 8, 16, 32, etc.) - taking smaller numbers does not make sense because nothing will be rearranged .)
')
Let's move from theory to practice.

Global becomes local, and local becomes global?

1. Original image 512x512 pixels


2. For the sake of experiment, the background is filled with cells of two colors in a staggered manner with a minimum pitch


3. Bit-reversible permutation of image No. 2 pixels (encoding)

Immediately striking is the maximum pitch of the cage of the chess background. And what was the letter "A", has become smeared over the entire image, as can be seen from the black dots. If you look, the squares of four pixels correspond to one pixel from each quarter of the original image in a rather chaotic order. The same behavior of a bit-reverse permutation for the sequence was described at the very beginning.
It can be concluded that with a bit-reversible permutation of image pixels, roughly speaking, large elements become small, and small ones become large. But it's not always the case. For example, the sequence of Morse-Thue how many do not rearrange it will always be itself. This is because when calculating an element of this sequence, the sum of the units in the binary representation of the index is used, and the reverse of the bits does not affect the sum of the units.

Now, if we produce a bit-reversible permutation of the encoded image number 3, we get the original image number 2. Since the reverse of the index bits, in which the bits are in reverse order, gives an index with the original bit order.

Pseudo-holography

One of the properties of holography is that if you break a piece of a hologram, then the whole image will be visible in it. It is almost the same here, but the piece must have a length equal to the power of two and start from a position multiple of the size of the piece.

4. Bit-reversible permutation of all 8x8 squares of the coded image No. 3


5. Bit-reversible permutation of all squares of size 32x32 encoded image number 3

It is noticeable that neither the size of the squares, nor the position of the squares affect the outline "A" from the original image. Naturally, the resolution of each square is less than the resolution of the original image.

Damage

Conduct an experiment with the removal of the image area similar to the experiments [ 1 , 2 , 3 ].
6. A large area of ​​the coded image No. 3 is colored (in other words, low-frequency noise is added to the image)


7. Bit-reversible permutation of the damaged image №6

You can see how low-frequency noise is transformed into high-frequency noise.

8. Enlarged fragment of 32x32 restored image №7

One can see the chess cells in their places along with the noise.

9. Bit-reversible permutation of all the 32x32 squares of the damaged image No. 6

It is very noticeable how the outline “A” is restored even from the smallest fragments.

Practical use

This permutation is used in communication called bit-reversal interleaving . (Permutation of the message symbols allows all adjacent characters to be dispersed. Then, if several consecutive characters (burst error) disappear during the transmission of the encoded message, then the recovered message will contain unit losses of characters distributed throughout the message. Taking into account the fact that some error correction algorithms correct single errors better than several errors in a row, this allows you to restore the original information with less difficulty. Since in practice the message size 2 ^{L is} not very convenient, the so-called use is used. pruned bit-reversal interleaving .

Results

As you can see, with a bit-reverse permutation, two holographic properties are performed:

1. Restore the image with lower resolution to any piece of the set of valid pieces.
2. Restoring the outlines of the original image if there is no significant part of the encoded image.

Especially well these properties are shown on low-frequency images.

Of course, one could cite many examples with different types of images, noise and damage, but a bit-reversible image permutation is just a permutation of pixels without adding any additional information. How many pixels will be lost in the encoded image, the same number of pixels will be missed and the reconstructed image. What kind of pixels will be noise is generally unknown.

Implementation

Anyone can experiment themselves. For this, I posted ( GitHub , DropBox ) scripts in Python.