Голографические свойства бит-реверсивной перестановки

    Об экспериментах с компьютерной голографией писалось неоднократно. [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.
    Поделиться публикацией
    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее
    Реклама
    Комментарии 30
    • +5
      А не пробовали применить вместо бит-реверсивной перестановки какое-то другое взаимо-однозначное преобразование и поисследовать? Циклический сдвиг например. Или ещё круче — блочный шифр с размером блока L? Применение шифра к индексу переставит элемент в псевдо-случайное место — шум будет выглядеть совсем по другому.
      • +2
        Интересная идея, надо будет попробовать. Жаль, что криптография — не мой конек. Я в основном интересуюсь тем, что связано с бинарным представлением числа.
        • +1
          Поскольку блочные шифры с размером блока 16 бит не очень популярны ;), можно сделать такой самостоятельно с использованием сети Фейстеля. Хотя в данном случае, мне кажется, ещё проще будет просто воспользоваться заранее сгенерированной случайной перестановкой чисел 0,.., 2**L-1 — свойства будут аналогичны. Либо запутать биты несложной комбинацией сдвигов и XOR-в.

          Кроме того, думается, что для 2D объекта свойства трансформации будут различаться для случая, когда каждый адрес трансформируется отдельно, и для случая когда трансформации подвергается объединенный адрес длинной в 2L.
          • +1
            Будет та же перестановка, но поменяются местами координаты x, y, потому что реверс битов половинок останется, но добавится реверс самих половинок [(bx1|bx2)2, (by1|by2)2] -> (bx1|bx2|by1|by2)2 -> (by2|by1|bx2|bx1)2 -> [(by2|by1), (bx2|bx1)2].
      • НЛО прилетело и опубликовало эту надпись здесь
        • 0
          Подскажете как реализовать дискретное преобразование пекаря без потерь?
          • НЛО прилетело и опубликовало эту надпись здесь
            • +2
              Восстановление после моей реализации преобразования пекаря сразу же приводит к потере нижней половины картинки. На третей итерации остаются черные полосы.
              • НЛО прилетело и опубликовало эту надпись здесь
        • +2
          для блочных шифров были исследования: уязвим, например, ГОСТ 28147-89
          • +3
            Спасибо за статью, интересный пример и красивый способ проиллюстрировать interleaving.
            Подобные преобразования интересно рассматривать в контексте стеганографии, когда нужно как раз работать с шумом в сигнале.
            • +3
              Поскольку на практике размер сообщения 2L не очень удобен, то применяют т.н. pruned bit-reversal interleaving.
              ===
              У них там вообще все что угодно можно запатентовать? Это ж самое очевидное — перемешать, а потом убрать пустоты!
              Первое же что пришло в голову. И только потом пошел по ссылке…
              Бред ведь. Оно ведь «на уровне техники»…
              • +1
                Патентные тролли не спят :-)
              • 0
                Спасибо, очень интересно! Конечно, с данным изображением я бы сжал исходную картинку в PNG и добил бы кодами Рида-Соломона до полного размера битмапа. Тогда зашумлять результат вообще без потерь можно будет очень круто :-) Но с произвольными изображениями это может иметь смысл.
                • +1
                  Что касается технической стороны вопроса, то мне очень понравился способ обратной перестановки из stackoverflow:

                  unsigned int reverse(register unsigned int x)
                  {
                      x = (((x & 0xaaaaaaaa) >> 1) | ((x & 0x55555555) << 1));
                      x = (((x & 0xcccccccc) >> 2) | ((x & 0x33333333) << 2));
                      x = (((x & 0xf0f0f0f0) >> 4) | ((x & 0x0f0f0f0f) << 4));
                      x = (((x & 0xff00ff00) >> 8) | ((x & 0x00ff00ff) << 8));
                      return((x >> 16) | (x << 16));
                  }
                  
                  • +1
                    Красиво. Попытался найти его в Hacker's delight — открыл сразу на нужной странице :)
                    • 0
                      Для того чтобы эта функция работала на индексах последовательности (изображения) длиной 2L, нужно результат сдвинуть на 32-L бит вправо.
                      • 0
                        Ах да, забыл дописать, я же ее дорабатывал для своих как раз таких нужд)
                        • 0
                          Интересно, табличка с развернутыми 8- или 16-битными числами не быстрее будет?
                          • 0
                            Ну судя по ответу на SO как раз таки быстрее, но менее изящно.
                    • +5
                      Ой и наигрался же я сегодня с этим эффектом :)
                      Пол-дня потратил.
                      Если кому интересно на пхп, то
                      мой вариант
                      <?php
                      $in_filename = 'in.png';
                      $out_filename = 'out.png';
                      $max_log = 9; // логарифм максимального допустимого размера (ширины или высоты)
                                      // 9 == 512 точек
                      list($width, $height,$type) = getimagesize($in_filename);
                      switch ($type) {
                          case IMAGETYPE_JPEG:
                              $in = imagecreatefromjpeg($in_filename);
                              break;
                          case IMAGETYPE_PNG:
                              $in = imagecreatefrompng($in_filename);
                              break;
                          case IMAGETYPE_GIF:
                              $in = imagecreatefromgif($in_filename);
                              break;
                          default:
                              die();
                              break;
                      }
                          ///
                      $resize = 0;
                      if(floor(max(log($width,2),log($height,2)))>$max_log) $resize = floor(max(log($width,2),log($height,2))) - $max_log;
                      $newwidth =  pow(2, floor(log($width ,2))-$resize);
                      $newheight = pow(2, floor(log($height,2))-$resize);
                      // изменение размера
                      $out = imagecreatetruecolor($newwidth, $newheight);
                      imagecopyresized($out, $in, 0, 0, 0, 0, $newwidth, $newheight, $width, $height);
                      $in = $out;
                      $width = $newwidth;
                      $height = $newheight;
                      // Создадим пустое изображение, чтобы не конфликтовать с ресурсом $in
                      $out = imagecreatetruecolor($newwidth, $newheight);
                      // в цикле переместим все точки в нужное место
                      for($i=0;$i<$width;$i++) {
                          for($j=0;$j<$height;$j++) {
                              imagesetpixel($out,r($i,$width),r($j,$height),imagecolorat($in,$i,$j));
                          }
                      }
                      imagepng ($out,$out_filename);
                      die();
                      // Функция битреверсивного преобразования
                      function r($in,$max) {
                          $l = log($max,2);
                          $r = 0;
                          for($i=0;$i<=$l;$i++) if(($in & (1 << ($l-$i-1))) != 0) $r = $r | (1<<$i);
                          return $r;
                      }
                      

                      На входе две переменные — имя входного файла и имя выходного файла.
                      На входе принимает jpeg, png и gif
                      На выходе только png.

                      Поскольку в пхп для сохранения в бмп нужно много плясать с бубном, а сохранение преобразованной картинки в jpeg ужасно портило цвета, то я принял решение сохранять в индексированном виде, и png мне для этого больше нравится чем gif.

                      На входе картинка ресайзится под удобные нам размеры — $max_log указывает логарифм от максимального размера картинки по модулю 2. Обе стороны приводятся к степени двойки. Небольшие искажения пропорций не так страшны ибо мы таки поиграться а не боевой скрипт.
                      • –2
                        Интересная статья. Автору спасибо! Жаль, немогу пока плюсовать
                        • 0
                          Вот чисто из любопытства: за что? Я наверно чего-то непонимаю?
                          • 0
                            Некоторые люди болезненно воспринимают фразу
                            Жаль, немогу пока плюсовать

                            1. «Не» с глаголами пишется раздельно
                            2. В данной фразе некоторые видят скрытую просьбу добавить плюс в карму, что запрещено правилами
                              Хабр — не для попрошаек

                            • 0
                              1. Согласен, провтыкал
                              2. О_о Да я ж себе кармы и не просил. Просто высказал почтение автору. Видать совсем меня неправильно поняли :(
                        • +12
                          Сделал интерактивную демку на JS-Canvas (требуется поддержка canvas в браузере).
                          Две канвы, каждая — преобразование bitreverse от другой. Можно на любой рисовать и смотреть, как меняется другая. Внизу выбор цвета и размер пера. Можете, например, на одной что-то нарисовать, а на другой попытаться это испортить. Или нарисовать поверх другую картинку:

                          • 0
                            Круто)
                            Можете еще добавить загрузку готовых картинок?
                            • 0
                              Я не в курсе, как это сделать на чистом JS без серверной части, а писать серверную часть неохота. Мой исходник под лицензией MIT — берите и допиливайте :-)
                            • 0
                              Вот забавная строка что бы поиграться с этой штукой. Делает курсор переливающегося цвета и заполняет картинку цветным шумом сначала.
                              for(var i = 0; i < 512; i++)
                                  for(var j = 0; j < 512; j++)
                                      Math.random()>0 && (color = [Math.random()*255,Math.random()*255,Math.random()*255,255]) && setPixel(0,i,j);
                              flush();
                              var du = 0; 
                              setInterval(
                                  function(){
                                      du+=0.01;
                                      color[0] = Math.sin(du)*120+123;
                                      color[1] = Math.sin(du*3)*120+123;
                                      color[2] = Math.sin(du*7)*120+123;
                                  }, 10
                              );
                              
                              • 0
                                вот она наглядная янус-космология!

                              Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.