Tupper自我指涉方程在图像中的原理分析及实现

67
0
2021年2月14日 09时20分

1.首先

 

这篇文章是针对Jeff Tupper在他发的paper中提及的作品:Tupper自我指涉方程的相关解读。
该Paper在线阅读地址为:点击该处
该公式的作用是在一个指定的公式里使用一个常数k就可以唯一指定一张二值图。
其公式为:

 

Tupper自我指涉方程在图像中的原理分析及实现插图
  

对于该公式,其以(x,y-k)作图,其中0\leq x\leq 106,k\leq y\leq k+17,之后再指定一个k就可以生成一个(106,17)大小的二值图,例如对k有:

 

k=4858450636189713423582095962494202044581400587983244549483093085061934704708809928450644769865524364849997247024915119110411605739177407856919754326571855442057210445735883681829823754139634338225199452191651284348332905131193199953502413758765239264874613394906870130562295813219481113685339535565290850023875092856892694555974281546386510730049106723058933586052544096664351265349363643957125565695936815184334857605266940161251266951421550539554519153785457525756590740540157929001765967965480064427829131488548259914721251530530642522971503

 

可以生成如下图(这里用的是\frac{1}{6},但是对于公式本身而言毫无影响,至于为什么请看下一部分):

 

Tupper自我指涉方程在图像中的原理分析及实现插图(1)

 但别看上面的k很长,其k的得到是一个很简单的事情(只要明白它的原理)

 

2.原理

 

现在我们这么假设:对于一张(106,17)的二值图(由1和0组成),图中所有取值为1的像素点对应的(x,y)为满足上面式子的x,y的集合,并存在一个k与之对应。下面我们来进行充要条件的寻找。

 

此处我们不妨假设17\leq k,因为这里我们只要找到那么一个k就可以了,所以这么假设下没有什么问题。然后对于这个式子:

 

Tupper自我指涉方程在图像中的原理分析及实现插图
  

需要注意的是:这里式子左侧的常数:完全不必是1/2,只要是一个(0,1)之间的任意常数均可以
因为任何常数mod2后在[0,2)之间,之后外面再套一个向下取整的符号后,其取值只有2种可能,那就是0和1。而要大于1/2的话,其取值就只能取1了。所以:

 

0.5\leq 右边的式子”等价于“1=右边的式子”。这个应该很好理解。
之后我们在考虑我们的定义域:0\leq x\leq 106,k\leq y\leq k+17

 

Tupper自我指涉方程在图像中的原理分析及实现插图(2)
  

这里我们可以注意到注意到k\leq y\leq k+17,而y-k=17这一条直线不影响最终的图像,所以不妨考虑k+17>y。左右同除17后有:\frac{k}{17}\leq \frac{y}{17}<\frac{k}{17}+1,之后我们向下取整,并令\lfloor \frac{y}{17} \rfloor=\lfloor \frac{k}{17}\rfloor=M,这个式子对于所有可能的k而言不一定成立,但是因为我们只需要找到一个满足的k就可以了,所以这里加了一个强制条件。
之后我们将原方程调整为:

 

Tupper自我指涉方程在图像中的原理分析及实现插图(3)
  

由我们M的定义可知,我们的M为非负整数且由k唯一决定

 

原方程现在形如:\lfloor mod(i2^{-j},2)\rfloor=1其中i,j为自然数的形式。对于上面的方程,我们先来思考在什么情况下会有:\lfloor mod(i2^{-j},2)\rfloor=1

 

可以知道的是,我们的j不能太大,因为当2^j>i时,显然式子左边=0。这里我们左边的式子要么等于0要么等于1,所以此处我们可以对i进行二进制形式的表示:

 

设:

 

Tupper自我指涉方程在图像中的原理分析及实现插图(4)

 则当i>2^j时,我们有:

 

Tupper自我指涉方程在图像中的原理分析及实现插图(5)
  

所以有\lfloor mod(i2^{-j},2)\rfloor=a_j (注:此处我们的q因为有向下取整,所以被忽略掉了),从而我们得知对于给定的i,对于方程\lfloor mod(i2^{-j},2)\rfloor=1的所有j的自然数解可以由i的二进制表示得到:要判断一个数k是否为满足条件的j只要看i的二进制表示中的第k+1位是否为1即可。
之后我们回到我们的式子:

 

\lfloor mod(M2^{-j},2)\rfloor=1
  

令所有满足的自然数解j构成集合S,由我们上面的结果可以知道的是:“j在S中”等价于“M的二进制表示下第j+1位是1”。因而S有限,并且由M唯一决定,从而由k唯一决定。

 

例如:
当k=17058684
M=1003452,
首先我们先求出M的二进制表示为:11110100111110111100,
发现第20, 19, 18, 17, 15, 12, 11, 10, 9, 8, 6, 5, 4, 3位为1,
所以其对应的S={2, 3, 4, 5, 7, 8, 9, 10, 11, 14, 16, 17, 18, 19}

可以看出的是,k求S、S求k都非常的简单。
之后我们来看这个式子:

 

Tupper自我指涉方程在图像中的原理分析及实现插图(6)
  

左边为一个17的倍数+一个小于17的自然数,为此当右侧的j确定的时候,左侧的x和y也会同样确定下来(因为17和1互素,例如:33=17a+b,b小于17,ab为自然数,则a和b唯一确定,简单的数论问题),我们此时左右同除17,有:

 

Tupper自我指涉方程在图像中的原理分析及实现插图(7)
  

显然有:

Tupper自我指涉方程在图像中的原理分析及实现插图(8)

 从而有:

Tupper自我指涉方程在图像中的原理分析及实现插图(9)

 之后我们再进行如下的操作:

 

Tupper自我指涉方程在图像中的原理分析及实现插图(10)
  

所以有:

Tupper自我指涉方程在图像中的原理分析及实现插图(11)
  

由于y-k的范围在0-17之间,\lfloor y-k\rfloor只能是0,1,2,……16这17个互异的非负整数,所以mod(\lfloor y-k\rfloor,17就是\lfloor y-k\rfloor

 

(X)式右边可能为负数,我们考虑在mod17意义下右边的值,右边总是介于0-16的整数
如果右边计算为负数等,如-4,我们就认为右边是13,这种认定下就会有:

 

Tupper自我指涉方程在图像中的原理分析及实现插图(12)
  

所以由②③就可以表示出对于固定的各个j和k,对应的各个像素点们。
例如对于之前的例子中的k=17058684,取S中的j=18,有:

 

Tupper自我指涉方程在图像中的原理分析及实现插图(13)
  

于是由j唯一确定了不超过x的最小整数,不超过y-k的最小整数,这里需要注意的是我们最后作图是以y-k为纵坐标作图。

 

每一个属于S的j都会确定图像中的一个像素点的坐标,例如上面的(x,y-k)=(1,1),所以其对应的图中像素点为:

 

Tupper自我指涉方程在图像中的原理分析及实现插图(14)
  

对于这里而言,其对应的一个方格为:{(x,y)|1\leq x<2,1\leq y-k<2}。
注意到我们的②式,为了这个图像能够在矩形{(x,y)|0\leq x\leq 106,k\leq y\leq k+17},我们还要求有j<17*106,即:

17\leq k\leq 2^{1802}

总结

 

这个功能我们可以用Python代码来进行实现,只是需要注意的是,我们的图片中的坐标是按照左上角为(0,0)的,而我们在上述进行讨论的时候则是按照左下角(也就是一般的坐标系的零点位置)来进行的说明,所以需要进行反转一下,不过这个都是些简单的操作,提一提就好。
最后再用Tupper不等式生成我的名字,如图所示:

 

Tupper自我指涉方程在图像中的原理分析及实现插图(15)

 其对应的k值为:

 

984107829042985472604796234718239406952573306558267124934037870944567482829146390093221988350003902420037970380063906594457568676371421068434047704461047660191379664044458042915914971631073786198841819014350817387799790991913967915133414137791725109750813163520

 

这里k值得获得我觉得比较简单,就是只要把图像中所有的点的坐标得到后,进行公式②③的一个逆向操作之后就可以得到对应的k值,在此就不再进行演示了。

 

k对应的二进制展开序列为:

 

0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001000000000000000000000000000000000000000000000000000000000001111110000000000000000000000000000000000000011100000000000000000000000000000000000000000000000000000000000110001000000000000000000000000000000000000000110000000000000000000000000000000000000000000000000000000000011000000000000000000000000000000000000000000011000000000000000000000000000000000000000000000000000000000001100100111011001111000011111001111001111100001100000000000000000000000000000000000000000000000000000000000111110001110100100110011011001100110110011000110000000000000000000000000000000000000000000000000000000000011001000110000001111001101100100011011001100011000000000000000000000000000000000000000000000000000000000001100000011000001101100111100110000101100110001100000000000000000000000000000000000000000000000000000000000110001001100001100110011100001000110110011000110000000000000000000000000000000000000000000000000000000000011001100110000110111101111100110110011001100011000000000000000000000000000000000000000000000000000000000001111110111100001100101100010000110001100110011110000000000000000000000000000000000000000000000000000000000000000000000000000000011111000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010000000000000000000000000000000000000000000000000000000000011111100000000000000000000000000000000000000111000000000000000000000000000000000000000000000000000000000001100010000000000000000000000000000000000000001100000000000000000000000000000000000000000000000000000000000110000000000000000000000000000000000000000000110000000000000000000000000000000000000000000000000000000000011001001110110011110000111110011110011111000011000000000000000000000000000000000000000000000000000000000001111100011101001001100110110011001101100110001100000000000000000000000000000000000000000000000000000000000110010001100000011110011011001000110110011000110000000000000000000000000000000000000000000000000000000000011000000110000011011001111001100001011001100011000000000000000000000000000000000000000000000000000000000001100010011000011001100111000010001101100110001100000000000000000000000000000000000000000000000000000000000110011001100001101111011111001101100110011000110000000000000000000000000000000000000000000000000000000000011111101111000011001011000100001100011001100111100000000000000000000000000000000000000000000000000000000000000000000000000000000111110000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

 

不过说到底,这个公式的实用性不是很强,因为对于一张越大的图,其需要的二进制位数就越多,这就导致我们的计算机处理性能就要更强,而且如果要是看过作者原文的话就会知道作者在那篇文章中所讨论的问题比这个还要复杂的多了。

 

对于我们公式中的17、mod2都是可以进行改变的,只要符合一定的规则即可,而这里谈到的规则也就是我们在上面进行推导的时候,改变了数据后,依旧能那么推导即可。
本文到此为止,谢谢大家!

 

发表评论

后才能评论