JungleTryne Jul 4 2018 at 16:55

Формула Таппера и реализация алгоритма на Python

6 min

45K

Вместо предисловия

Не так давно на просторах интернета узнал о такой замечательной и удивительной копии Вавилонской библиотеки как о формуле Таппера. Вернее, это больше неравенство Таппера, чем формула. Особенность данного неравенства — оно создает собственное же изображение на графике. Просто посмотрите на это чудо!

То, что Вы видите на изображении, и является формулой того самого Джеффа Таппера. Наверное, половина читателей уже понеслась в вольфраме рисовать результат выполнения данного неравенства… Но тут не все так просто. Как вы можете заметить в данном изображении, формула на графике может быть замечена на отрезке по оси OY [k; k+15]. Что же это за загадочное число k? Где же его взять? Все дело в том, что данное неравенство, по концепции Вавилонской библиотеки, способно вывести абсолютно любое изображение с разрешением 106х17! Каждое изображение, имеет собственную позицию на графике, тем самым, имеет уникальное число k. Таким образом, для каждого числа k существует единственное изображение на всем графике!

Для данного же изображения число k выглядит следующим образом:

4858450636189713423582095962494202044581400587983244549483093085061934704708809928450644769865524364849997247024915119110411605739177407856919754326571855442057210445735883681829823754139634338225199452191651284348332905131193199953502413758765239264874613394906870130562295813219481113685339535565290850023875092856892694555974281546386510730049106723058933586052544096664351265349363643957125565695936815184334857605266940161251266951421550539554519153785457525756590740540157929001765967965480064427829131488548259914721248506352686630476300

Интересно посмотреть на людей, которые будут прокручивать до такой координаты, чтобы увидеть формулу

Мне пришла в голову идея написать программу на Python3, которая позволяла бы конвертировать изображение в число k и наоборот и рассказать Вам еще об одном прекрасном способе закодировать изображение в цифру.

Теория

Как же это работает?

Давайте взглянем на саму формулу:

$\frac{1}{2} < \left \lfloor mod \left(\left \lfloor \frac{y}{17} \right \rfloor \cdot 2^{-17 \lfloor x \rfloor - mod( \lfloor y \rfloor, 17)}\right) \right \rfloor$

Определимся с её синтаксисом:
$\lfloor x \rfloor$ — число, округленное вниз
$inline$ — остаток от деления числа x на число y.
Заметим, что как x, так и y округляются вниз. Именно такое округление в итоге нам дает пиксельную картинку.

Обозначим все, что округляется в правой части неравенства за $\alpha$ .
Тогда

$1/2 < [\alpha] \Leftrightarrow 1 \le [\alpha]$

Что очевидно, ведь целое выражение округляется вниз.

Пусть y = 17r + q, где r — целая часть от деления y на 17, а r — остаток от деления. Таким образом, мы в формуле можем заменить $inline$ на r, а $inline$ на q.

Получаем

$1 \le mod(q*2^{-17-r},2)$

Или же

$1 \le mod(q/2^{17x+r},2)$

mod( $\alpha$ ,2) принимает 2 значения — 0 или 1. Соответсвенно, данное неравенство будет говорить, является ли число $q/2^{17x+r}$ четным или нет.

Заметим, что изображение рассмаривается на промежутке [N, N+16], соответственно $inline$ остается постоянным на протяжении всей высоты изображения, что нельзя сказать про число r (на протяжении всего изображения меняется от 0 до 16).

А теперь вишенка на торте. Число $[q/{2^{17x+r}}]$ будет нечетным тогда и только тогда, когда бит под номером (17x+r) в двоичном предствалении числа q будет равен 1. А так как с высотой число q постоянно меняется и его двоичное представление тоже, то мы каждый раз получаем уникальное изображение! Именно так и работает формула Таппера.

Теперь посмотрим, как же вычислить высоту, на которой мы хотим увидеть наше изображение

Принцип вычисления числа k

Сам Таппер описал вычисление числа k для любого изображения размером 106х17 (это важно!) следующим образом:

Перевести изображение в черно-белое представление
Читать каждый пиксель снизу-вверх, слева направо и класть его в буфер. Если пиксель черный — то кладем 1, если белый — 0.
Перевести двоичное число в десятичное и умножить на 17
Профит!

Чтобы получить из числа k изображение — делаем все с точностью наоборот. Ну что же, поехали кодить!

Кодим

Из k в изображение

Использование метода Таппера для декодирования числа k

Получаем от пользователя число k, ~~с закрытыми глазами~~ делим его на 17 и переводим в двоичную систему.

def from_k_to_bin(k: int) -> list:
    k //= 17
    binary = bin(k)[2:]

Понимаем, что некоторые начальные пиксели могут быть белыми (равны 0), соответственно у нашего двоичного числа первые биты будут нулями, а при переводе числа в десятиричную систему эти начальные нули потеряются. Поэтому проверяем размер полученного двоичного числа, если он будет меньше 1802, то добавляем в начало нули.

def from_k_to_bin(k: int) -> list:
    k //= 17
    binary = bin(k)[2:]

    #Спасибо за исправление RadicalDreamer
    binary = ("0" * (1802 - len(binary))) + binary

Далее объявим двумерный список, в котором будем хранить информацию о каждой строчке изображения. Затем записываем туда все те биты, которые прочитали (не забываем алгоритм, по которому создается число k — снизу-вверх, слева-направо)

lists = [[] for x in range(17)]

#Cпасибо за исправление RadicalDreamer
for x in range(1802):
    lists[-(x % 17)].append(binary[x])

#-----Рисовашки!-----#
image = Image.new("1", (106,17), (0)) #Создаем черно-белое изображение 106х17
draw = image.load()
for y in range(17):
    for x in range(106):
        image.putpixel(xy=(105-x,16-y), value=(int(lists[y][x]),)) #каждый пиксель окрашиваем в цвет, который хранится в двумерном списке lists
image.save("image.png") #сохраняем изображение

Давайте попробуем запихнуть в нашу программу число k, которое я указал в начале статьи, и получим следующее:

Как видим, у нас все получилось, и мы теперь способны декодировать любой k!

Использование неравенства для генерации картинки из числа k

Для начала запишем функцию в питоне:

def f(x,y):
    return ((y//17)//(1 << (17*x+(y%17))))%2

Благодаря операторам // и << реализация функции была сильно упрощена. Гарантируется, что числа x и y будут целыми!

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

lists = [[] for x in range(17)]
for y in range(16,-1,-1):
            for x in range(105,-1,-1):
                lists[y].append(int(f(x,y+k) > 1/2))

И далее как и в предыдущем примере рисуем картинку с помощью библиотеки PIL.

Полностью функция выглядит вот так:

def from_k_to_bin(k: int) -> list:
    lists = [[] for x in range(17)]

    for y in range(16,-1,-1):
        for x in range(105,-1,-1):
            lists[y].append(int(f(x,y+k) > 1/2))

    return lists

Изображение в k

Чтож, теперь научимся любое изображение кодировать в число k.

Cначала получим само изображение

def get_image() -> Image:
    name = input("Введите название изображения (должно находится в одной папке со скриптом):")
    try:
        im = Image.open(name)
    except Exception:
        print("Неудача!")
        exit(0)
    return im

Проверим его размер

_SIZE_WIDTH = 106
_SIZE_HEIGHT = 17

image = get_image()
width, height = image.size

flag_okay = False
if width == _SIZE_WIDTH and height == _SIZE_HEIGHT:
    flag_okay = True

if not flag_okay:
    print("Недопустимый размер изображения")
    print(width, height)
    exit(0)

print("Все ок!")

Делаем изображение черно-белым и начинаем читать попиксельно:

image = image.convert('1')

byteset = ""
for x in range(105,-1,-1):
    for y in range(0,17):
        #cпасибо m03r за исправление
        if image.getpixel((x,y)) > 127:
            byteset += '1'
        else:
            byteset += '0'

Остается только перевести в десятичную систему и умножить на 17.

k = int(byteset,2)*17
print("Все готово:")
print(k)

Ну что же, пошли тестировать!

Я решил закодировать логотип хабра. Вот исходное изображение:

Запускаем программу и указываем имя изображения:

Мы получили следующее k:

4858487703217654168507377107565676789145697178497253677539145555247620343537955749299116772611982962556356527603203744742682135448820545638134012705381689785851604674225344958377377969928942310236199337805399065932982909660659786056259547094494380793146587709009524498386724160055692719747815828234655968636671461350354316223620304956111171025410498514602810746287134775641383930152393933036921599511277388743068766568352667661462097979110006690900253037600818522726237351439443865433159187625289316917268254866954663750093103703327097252478959

Давайте же его проверим на нашей же программе.

Вот изображение, которое мы получили:

Оно было немного изкажено из-за немного кривого перевода изображения в черно-белые цвета.

Итог

Исходный код программы

Источники: Статья на вики

Tags:

Hubs: