Holographic properties of bit reversal permutation

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

Bit Reverse and Bit Reverse Swap

Suppose there is a sequence of anything 2 ^L long . And each element of this sequence has an index of 0, 1, 2, ..., 2 ^L -1. In binary representation, the index will look like (b _L-1 b _L-2 ... b ₁ b ₀ ) ₂ . Then the reverse bits of this index will look like (b ₀ b ₁ ... b _L-2 b _L-1 ) ₂ .
For example, given the sequence a, b, c, d, e, f, g, h. Indices of this sequence
there will be 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 reverse order, taking into account the maximum length of a 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 result was a permutation of the sequence in a bit-reverse order. For the future, we note that 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, then just rearrange the bits in both coordinates of each pixel.

I note once again that bit-reversal permutation can be performed only for sequences of length exactly equal to the 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. The original image is 512x512 pixels


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


3. Bit-reversal permutation of the pixels of image No. 2 (coding) The

maximum step of the chessboard square is immediately apparent. And what was the letter “A” became smeared throughout the image, as can be seen from the black dots. If you look, then the four-pixel squares correspond to one pixel from each quarter of the original image in a rather chaotic order. The same behavior of the bit reversal permutation for the sequence was described at the very beginning.
It can be concluded that when bit-reversing permutation of image pixels, roughly speaking, large elements become small, and small large. But it's not always the case. For example, the Morse-Thue sequence, how many do not rearrange it, it will always be itself. This is because when calculating an element of this sequence, the sum of units in the binary representation of the index is used, and the reverse of the bits does not affect the sum of units.

Now, if you make a bit-reverse permutation of the encoded image No. 3, you get the original image No. 2. Since the reverse of the index bits, in which the bits are in the reverse order, gives an index with the original bit order.

Pseudo-holography

One of the properties of holography is that if a piece of a hologram is broken off, then an entire image will be visible in it. It’s almost the same here, but the piece should have a length equal to the power of two and start from a position that is a multiple of the size of the piece.

4. Bit-reversal permutation of all 8x8 squares of encoded image No. 3


5. Bit-reversal permutation of all 32x32 squares of encoded image No. 3

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

Damage

We will carry out an experiment with the removal of the image region similar to the experiments [ 1 , 2 , 3 ].
6. A large area of ​​the encoded image No. 3 is shaded (in other words, low-frequency noise is added to the image)


7. Bit-reversal permutation of the damaged image No. 6

It is seen how the low-frequency noise was converted into high-frequency noise.

8. Enlarged fragment 32x32 of reconstructed image No. 7

Chess cells are visible in their places mixed up with noise.

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

It is very clearly visible how the shape of “A” is restored even from the smallest fragments.

Practical use

This permutation is used in communication called bit-reversal interleaving . The permutation of message characters allows you to disperse all adjacent characters. Then, if during the transmission of the encoded message several characters in a row disappear (burst error), then the restored message will contain single character losses scattered throughout the message. Considering that some error correction algorithms better correct single errors than several errors in a row, this allows you to restore the original information with less difficulty. Since in practice the size of the message 2 ^{L is} not very convenient, the so-called pruned bit-reversal interleaving .

Summary

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

1. Restore an image with a lower resolution for any piece from the set of valid pieces.
2. Restore the outlines of the original image if a significant part of the encoded image is missing.

These properties are especially well manifested in low-frequency images.

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

Implementation

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