Об экспериментах с компьютерной голографией писалось неоднократно. [1, 2, 3] Мне эта тема просто любопытна. Я как-то экспериментировал с бит-реверсивной перестановкой (bit-reversal permutation) изображений и случайно обнаружил голографические свойства. Но обо всем по порядку.


Реверс битов и бит-реверсивная перестановка


Допустим, есть последовательность чего угодно длиной 2L. И каждый элемент этой последовательности имеет индекс 0, 1, 2, …, 2L-1. В двоичном представлении индекс будет выглядеть так (bL-1bL-2…b1b0)2. Тогда реверс битов этого индекса будет выглядеть так (b0b1…bL-2bL-1)2.
Например, дана последовательность a, b, c, d, e, f, g, h. Индексами этой последовательности
будут числа: 0, 1, 2, 3, 4, 5, 6, 7; или в двоичном представлении: 0b000, 0b001, 0b010, 0b011, 0b100, 0b101, 0b110, 0b111. Сначала нужно переставить биты каждого числа в обратном порядке с учетом максимальной длины двоичного числа (L=3): 0b000, 0b100, 0b010, 0b110, 0b001, 0b101, 0b011, 0b111 (десятичные числа: 0, 4, 2, 6, 1, 5, 3, 7.) Затем элементы исходной последовательности переставляются в соответствии с полученными индексами: a, e, c, g, b, f, d, h. Таким образом, получилась перестановка последовательности в бит-реверсивном порядке. На будущее заметим, что смежные пары ae, cg, bf, dh состоят из элементов, которые расположены в разных половинках исходной последовательности.
Если нужно преобразовать двухмерное изображение, то достаточно переставить биты в обоих координатах каждого пикселя.

Еще раз отмечу, что бит-реверсивную перестановку можно произвести только для последовательностей длиной строго равной степени двойки (т. е. 4, 8, 16, 32 и т. д. — брать меньшие числа не имеет смысла потому, что ничего не будет переставляться.)

Перейдем от теории к практике.

Глобальное становится локальным, а локальное становится глобальным?


1. Исходное изображение 512х512 пикселей


2. Ради эксперимента фон заполнен клетками двух цветов в шахматном порядке с минимальным шагом


3. Бит-реверсивная перестановка пикселей изображения №2 (кодирование)

Сразу бросается в глаза максимальный шаг клетки шахматного фона. А то, что было буквой «А», стало размазанным по всему изображению, как это видно по черным точкам. Если р��зобраться, то квадратикам из четырех пикселей, соответствует по одному пикселю из каждой четверти исходного изображения в довольно хаотичном порядке. Такое же поведение бит-реверсивной перестановки для последовательности было описано в самом начале.
Можно сделать вывод, что при бит-реверсивной перестановке пикселей изображения, грубо говоря, крупные элементы становятся мелкими, а мелкие крупными. Но это не всегда так. Например, последовательность Морса-Туэ сколько не переставляй она всегда будет самой собой. Это происходит потому, что при вычислении элемента этой последовательности используется сумма единиц в двоичном представлении индекса, а реверс битов на сумму единиц не влияет.

Теперь, если произвести бит-реверсивную перестановку закодированного изображения №3, то получится исходное изображение №2. Поскольку реверс битов индекса, в котором биты в обратном порядке, дает индекс с исходным порядком бит.

Псевдоголография


Одно из свойств голографии состоит в том, что если отломать кусочек голограммы, то в нем будет видно целое изображение. Здесь почти тоже самое, но кусочек должен иметь длину равную степени двойки и начинаться с позиции кратной размеру кусочка.

4. Бит-реверсивная перестановка всех квадратиков размером 8х8 закодированного изображения №3


5. Бит-реверсивная перестановка всех квадратиков размером 32х32 закодированного изображения №3

Заметно, что ни размер квадратиков, ни положение квадратиков не влияет на очертание «А» из исходного изображения. Естественно, разрешающая способность каждого квадратика меньше разрешающей способности исходного изображения.

Повреждение


Проведем эксперимент с удалением области изображения аналогичный экспериментам [1, 2, 3].
6. Закрашена крупная область закодированного изображения №3 (другими словами, к изображению добавлен низкочастотный шум)


7. Бит-реверсивная перестановка поврежденного изображения №6

Видно как низкочастотный шум преобразовался в высокочастотный шум.

8. Увеличенный фрагмент 32x32 восстановленного изображения №7

Видно шахматные клетки на своих местах вперемешку с шумом.

9. Бит-реверсивная перестановка всех квадратиков 32х32 поврежденного изображения №6

Очень хорошо заметно как восстанавливается очертание «А» даже из мельчайших фрагментов.

Практическое применение


Данная перестановка применяется в коммуникации под названием бит-реверсивное чередование (bit-reversal interleaving.) Перестановка символов сообщения позволяет рассредоточить все смежные символы. Тогда, если при передаче закодированного соо��щения пропадает несколько символов подряд (burst error), то восстановленное сообщение будет содержать единичные потери символов, рассредоточенные по всему сообщению. С учетом того, что некоторые алгоритмы коррекции ошибок лучше исправляют единичные ошибки, чем несколько ошибок подряд, это позволяет восстанавливать исходную информацию с меньшими трудностями. Поскольку на практике размер сообщения 2L не очень удобен, то применяют т.н. pruned bit-reversal interleaving.

Итоги


Как видно, при бит-реверсивной перестановке выполняется два голографических свойства:
  1. Восстановление изображения с меньшим разрешением по любому кусочку из множества допустимых кусочков.
  2. Восстановление очертаний исходного изображения, если отсутствует значительная часть закодированного изображения.

Особенно хорошо эти свойства проявляются на низкочастотных изображениях.

Конечно, можно было бы привести множество примеров с различными видами изображений, шумов и повреждений, но бит-реверсивная перестановка изображения это всего лишь перестановка пикселей без добавления какой-либо дополнительной информации. Сколько пикселей будет утрачено в закодированном изображении, столько же пикселей будет не хватать и восстановленном изображении. Какие именно пиксели будут шумом — в общем случае неизвестно.

Реализация


Все желающие могут сами поэкспериментировать. Для этого я выложил (GitHub, DropBox) скрипты на Python.