04.07.2018 13:55
JungleTryne 29 11600 Источник

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


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

image

(Источник Wikipedia)

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

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

4858450636189713423582095962494202044581400587983244549483093085061934704708809928450644769865524364849997247024915119110411605739177407856919754326571855442057210445735883681829823754139634338225199452191651284348332905131193199953502413758765239264874613394906870130562295813219481113685339535565290850023875092856892694555974281546386510730049106723058933586052544096664351265349363643957125565695936815184334857605266940161251266951421550539554519153785457525756590740540157929001765967965480064427829131488548259914721248506352686630476300

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

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

Теория


(Добавлено) Как же это работает?


Давайте взглянем на саму формулу:
image
Определимся с её синтаксисом:
image — число, округленное вниз
mod(x,y) — остаток от деления числа x на число y

А дальше, вроде бы, всё и так понятно.
Заметим, что как x, так и y округляются вниз. Именно такое округление в итоге нам дает пиксельную картинку
image

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

$1/2 < [\alpha] <=> 1<= [\alpha]$



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

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

Получаем

$1 <= mod(q*2^{-17-r},2)$


Или же

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



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

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

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

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

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


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

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

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

Кодим


UPD: В комментариях народ немного улучшил код, сделал его проще и прозрачнее. В данной статье опубликованы данные обновления. Если хотите увидеть старые версии кода — идите в репозиторий гитхаба (пока не закомитил, ссылка в конце статьи) и в комментарии

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


UPD


По просьбе комментаторов, был добавлен новый способ вычисления изображения с помощью данного неравенства и 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])
<b>Давайте рисовать!</b>

<source lang="python">
#-----Рисовашки!-----#
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, которое я указал в начале статьи, и получим следующее:

image

Как видим, у нас все получилось, и мы теперь способны декодировать любой 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)

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

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

image

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

image

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

4858487703217654168507377107565676789145697178497253677539145555247620343537955749299116772611982962556356527603203744742682135448820545638134012705381689785851604674225344958377377969928942310236199337805399065932982909660659786056259547094494380793146587709009524498386724160055692719747815828234655968636671461350354316223620304956111171025410498514602810746287134775641383930152393933036921599511277388743068766568352667661462097979110006690900253037600818522726237351439443865433159187625289316917268254866954663750093103703327097252478959

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

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

image

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

Итог


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

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

Комментарии (29)


  1. phaggi
    04.07.2018 17:10
    #18847875

    Забавно!
    А подобные алгоритмы с другими параметрами (размерностями растра, например) бывают?


    1. AntonSor
      04.07.2018 18:24
      #18848285

      Легко подобрать, играясь коэффициентами. Вместо 17 в знаменателях ставите ваше число строк.


      1. thatsme
        05.07.2018 08:36
        #18849805

        Изображеня можно делать и цветные, тогда будет 3 числа к — для каждого цвета (если с альфа-каналом то 4-е), потом нужно просто после преобразования из к в битплейн, перевести из 3(4-х) битплейновых массивов в 1-н 32-х битный.


  1. xytop
    04.07.2018 17:18
    #18847903
    +3

    Пост о неравенстве Таппера… которое показано лишь на картинке в самом начале и дальше никакого упоминания о нем нет.
    Почему бы не объяснить как (и почему) работает эта формула, не написать ее в нормальном виде?
    Хоть бы в Python-коде использовали эту функцию для рисования, что ли…
    А так, любую картинку в любом предопределенном разрешении можно в число и обратно перевести, даже на 17 умножать не надо.


    1. JungleTryne Автор
      04.07.2018 17:48
      #18848061

      Если вам интересен механизм работы самого неравенства, доказательство его работы, то вам сюда ТЫК (Если руки дойдут, то и перевод возможно напишу)

      Впринципе, можно сделать реализацию через PyPlot, только остается вопрос, будет ли они быстрой и эффективной… А так, спасибо за идею для второй части :)


      1. xytop
        04.07.2018 17:52
        #18848091
        +2

        Я говорю о теме поста, и о том что идет по сути в его теле :)
        Они не взаимосвязаны никак, вообще. Ни код, ни текст не раскрывают темы.


        1. JungleTryne Автор
          04.07.2018 17:56
          #18848117

          Почему же? Джефф Таппер описал простой способ генерации числа k для каждого изображения. Да, так можно сделать с изображением любого формата, но данный пост показывает, что мы это делаем не просто так — все связано с его формулой. Как эта формула работает — я Вам уже отправил ссылку. Тема топика — реализация алгоритма на Python — алгоритм нахождения числа k был реализован, хоть и показался немного детским


    1. JungleTryne Автор
      04.07.2018 18:43
      #18848379
      +1

      Вы правы, добавил краткое разъяснение работы формулы Таппера в начало статьи. А то как то суховато получилось


  1. m03r
    04.07.2018 17:19
    #18847913

    А зачем преобразовывать число в строку?

    byte = str(image.getpixel((x,y)))
if byte == "255":
    byteset += '1'
else:
    byteset += '0'

    Лучше было бы так:
    if image.getpixel((x,y)) > 127:
    byteset += '1'
else:
    byteset += '0'


    Заодно монохром будет выглядеть немножко лучше.


    1. JungleTryne Автор
      04.07.2018 17:48
      #18848063

      Да, действительно, спасибо за исправление.
      Когда писал программу, думал, что функция getpixel вернет мне 1 или 0, т.к. изображение черно белое, потом понял, что это не так работает. Так и появился этот костыль


  1. kamiLLxiii
    04.07.2018 17:44
    #18848023

    Для тех, кому интересно, как оно работает www.youtube.com/watch?v=_s5RFgd59ao


    1. GeMir
      05.07.2018 11:10
      #18850381

      Numberphile вызывает зависимость :)


  1. RadicalDreamer
    04.07.2018 20:06
    #18848669
    +2

    Забавно.
    Но позвольте сделать несколько замечаний к самому коду.

    if len(binary) < 1802:
	new_binary = ""
	for i in range(1802-len(binary)):
		new_binary += "0"
	binary = new_binary + binary


    Можно упростить до 
    binary = ("0" * (1802 - len(binary))) + binary

    А чтобы не сортировать список lists в обратном порядке, поменяйте знак индекса на противоположный, т.е.
    for x in range(1802):
	lists[x%17].append(binary[x])

lists.reverse() #Немножко костылей - без этого изображение будет отзеркаленным


    можно заменить на 
    for x in range(1802):
	lists[-(x % 17)].append(binary[x])


    1. JungleTryne Автор
      04.07.2018 20:29
      #18848747
      +1

      Спасибо за исправление


      1. RadicalDreamer
        04.07.2018 21:03
        #18848835

        Пожалуйста!

        binary = ("0" * (1802 - len(binary))) + binary


        Возможно, здесь меня поправят, так что замечу, что вариант
        binary = binary.rjust(1802, "0")

        будет чище и куда уместнее первого.


      1. goiliago
        05.07.2018 15:39
        #18851767

        Ещё можно заменить


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

if not flag_okay:

        На просто


        if  width != _SIZE_WIDTH or height != _SIZE_HEIGHT:


    1. AntonyMcGreen
      05.07.2018 18:01
      #18852413

      Противоположный индекс не сгодится, ведь lists[-0]==lists[0], а должен быть lists[-1]. Я бы предложил lists[16-(x%17)]


      1. RadicalDreamer
        05.07.2018 19:09
        #18852637

        Да, Вы правы. Проверял свой код на изображении хабра в статье, и там баг не выявился, т.к. первый и последний элементы списка совпали.


        1. RadicalDreamer
          05.07.2018 19:24
          #18852687

          Более обобщенно, здесь подойдет lists[-(x % 17) - 1]
          JungleTryne, сорри за внесенную путаницу.


  1. JungleTryne Автор
    04.07.2018 21:29
    #18848915
    +1

    UPD: Добавлен новая реализация функции from_k_to_bin, которая использует непосредственно функцию. Также были исправлены кусочки кода и заменены на более красивые, которые были предложены комментаторами. Добавлена теория про само неравенство в самое начало статьи


  1. begemot_sun
    05.07.2018 09:44
    #18850017

    К сожалению, формула Таппера — это просто способ закодировать изображение, а не как-нибудь его сжать.
    Число К из статьи — 1807 бит. Количество пиксель в картинке 106*17 = 1802.
    Для сжатия не пойдет, и практической ценности видимо не имеет. Или всё же имеет?


    1. thatsme
      05.07.2018 10:17
      #18850119
      +1

      А само число сжимается или у него слишком высокая энтропия?


      1. begemot_sun
        05.07.2018 15:51
        #18851845

        Ну тут надо смотреть на энтропию изображения и энтропию его числа. Думаю что порядок величин одинаковый, так что не выстрелит.


        1. thatsme
          06.07.2018 05:28
          #18853823

          Ну строковое представление числа, отлично сжимается, там энтропия априори низкая (и чем длинее число тем ниже). Сжатие строкового представления числа «хабр» более чем в два раза с помощью bz2. Если число перевести в 256 бит то уже не нужно сжимать — 32 байта. Только нет гарантии, что для любой картинки нам хватит 256 бит.


    1. trapwalker
      05.07.2018 17:06
      #18852221

      Да, это даже не квайн, просто способ обфускации. А вот циклический многоязыковой квайн, который бы в одной из фаз был визуальным представлением формулы и QR-кода с числом к.


  1. iamoverit
    05.07.2018 17:59
    #18852405
    +1

    Интересен другой момент, ведь эта формула описывает и свастику в том числе, и как привели выше если ее расширить до цветной и содержащий большее количество пикселей, то и детское порно можно найти, должна ли быть данная формула заблокирована РКНом?


    1. JungleTryne Автор
      05.07.2018 18:00
      #18852409
      +1

      Ответ такой же, как и на следующий вопрос: В Вавилонской Библиотеке есть все совпадения симоволов. Одни из них могут содержать гос тайну всех стран. Должно ли РКН заблокировать Вавилонскую библиотеку?


    1. BubaVV
      05.07.2018 18:04
      #18852423

      Скажите, доктор, а откуда у вас такие картинки?


  1. SCINER
    06.07.2018 01:02
    #18853685

    Не понимаю, в чем ценность данного действия?
    Можно ведь просто изображение сохранить в двухцветном *.BMP файле и полученный файл без заголовка просто принять за большое число сконвертировав его Base10 алгоритмом.