grep Oct 22 2012 at 14:58

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

4 min

45K

Algorithms*

+126

Comments 30

zuborg Oct 22 2012 at 16:07

А не пробовали применить вместо бит-реверсивной перестановки какое-то другое взаимо-однозначное преобразование и поисследовать? Циклический сдвиг например. Или ещё круче — блочный шифр с размером блока L? Применение шифра к индексу переставит элемент в псевдо-случайное место — шум будет выглядеть совсем по другому.

grep Oct 22 2012 at 16:24

Интересная идея, надо будет попробовать. Жаль, что криптография — не мой конек. Я в основном интересуюсь тем, что связано с бинарным представлением числа.

zuborg Oct 22 2012 at 17:09

Поскольку блочные шифры с размером блока 16 бит не очень популярны ;), можно сделать такой самостоятельно с использованием сети Фейстеля. Хотя в данном случае, мне кажется, ещё проще будет просто воспользоваться заранее сгенерированной случайной перестановкой чисел 0,.., 2**L-1 — свойства будут аналогичны. Либо запутать биты несложной комбинацией сдвигов и XOR-в.

Кроме того, думается, что для 2D объекта свойства трансформации будут различаться для случая, когда каждый адрес трансформируется отдельно, и для случая когда трансформации подвергается объединенный адрес длинной в 2L.

grep Oct 22 2012 at 18:34

Будет та же перестановка, но поменяются местами координаты x, y, потому что реверс битов половинок останется, но добавится реверс самих половинок [(bx1|bx2)₂, (by1|by2)₂] -> (bx1|bx2|by1|by2)₂ -> (by2|by1|bx2|bx1)₂ -> [(by2|by1), (bx2|bx1)₂].

UFO just landed and posted this here

grep Oct 22 2012 at 21:32

Подскажете как реализовать дискретное преобразование пекаря без потерь?

UFO just landed and posted this here

grep Oct 22 2012 at 23:45

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

UFO just landed and posted this here

geka Oct 22 2012 at 17:04

для блочных шифров были исследования: уязвим, например, ГОСТ 28147-89

ntkt Oct 22 2012 at 17:10

Спасибо за статью, интересный пример и красивый способ проиллюстрировать interleaving.
Подобные преобразования интересно рассматривать в контексте стеганографии, когда нужно как раз работать с шумом в сигнале.

Mendel Oct 22 2012 at 19:23

Поскольку на практике размер сообщения 2L не очень удобен, то применяют т.н. pruned bit-reversal interleaving.
===
У них там вообще все что угодно можно запатентовать? Это ж самое очевидное — перемешать, а потом убрать пустоты!
Первое же что пришло в голову. И только потом пошел по ссылке…
Бред ведь. Оно ведь «на уровне техники»…

tagir_valeev Oct 22 2012 at 19:34

Патентные тролли не спят :-)

tagir_valeev Oct 22 2012 at 19:33

Спасибо, очень интересно! Конечно, с данным изображением я бы сжал исходную картинку в PNG и добил бы кодами Рида-Соломона до полного размера битмапа. Тогда зашумлять результат вообще без потерь можно будет очень круто :-) Но с произвольными изображениями это может иметь смысл.

KvanTTT Oct 23 2012 at 00:01

Что касается технической стороны вопроса, то мне очень понравился способ обратной перестановки из 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));
}

Mrrl Oct 23 2012 at 00:10

Красиво. Попытался найти его в Hacker's delight — открыл сразу на нужной странице :)

grep Oct 23 2012 at 00:14

Для того чтобы эта функция работала на индексах последовательности (изображения) длиной 2^L, нужно результат сдвинуть на 32-L бит вправо.

KvanTTT Oct 23 2012 at 00:17

Ах да, забыл дописать, я же ее дорабатывал для своих как раз таких нужд)

Mrrl Oct 23 2012 at 00:26

Интересно, табличка с развернутыми 8- или 16-битными числами не быстрее будет?

KvanTTT Oct 23 2012 at 00:34

Ну судя по ответу на SO как раз таки быстрее, но менее изящно.

Mendel Oct 23 2012 at 00:09

Ой и наигрался же я сегодня с этим эффектом :)
Пол-дня потратил.
Если кому интересно на пхп, то

мой вариант

<?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. Обе стороны приводятся к степени двойки. Небольшие искажения пропорций не так страшны ибо мы таки поиграться а не боевой скрипт.

Dimcore Oct 23 2012 at 01:21

Интересная статья. Автору спасибо! Жаль, немогу пока плюсовать

-2

Dimcore Nov 9 2012 at 18:10

Вот чисто из любопытства: за что? Я наверно чего-то непонимаю?

VMAtm Nov 9 2012 at 18:34

Некоторые люди болезненно воспринимают фразу

Жаль, немогу пока плюсовать

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

Хабр — не для попрошаек

Dimcore Nov 11 2012 at 00:42

1. Согласен, провтыкал
2. О_о Да я ж себе кармы и не просил. Просто высказал почтение автору. Видать совсем меня неправильно поняли :(

tagir_valeev Oct 23 2012 at 06:46

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

+12

Mendel Oct 23 2012 at 12:42

Круто)
Можете еще добавить загрузку готовых картинок?

tagir_valeev Oct 23 2012 at 12:50

Я не в курсе, как это сделать на чистом JS без серверной части, а писать серверную часть неохота. Мой исходник под лицензией MIT — берите и допиливайте :-)

Zibx Oct 23 2012 at 18:24

Вот забавная строка что бы поиграться с этой штукой. Делает курсор переливающегося цвета и заполняет картинку цветным шумом сначала.

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
);

dtestyk Oct 30 2012 at 02:00

вот она наглядная янус-космология!