讨鬼传2武器枪升级路线:产生递归图的算法
Generate Recursive Images
在上一篇 blog 中我提到了递归图片,还给了一个有趣的例子,这次还说递归图片,再给另一个例子:
不过这次的例子是我自己生成的,而篇 blog 就是要讲如何来生成这样一张递归图片。其实方法很简单,类推一下,多花一些功夫的话,之前给的那个“二次递归”的例子也是可以“轻松”做出来的。
秘密就在于不动点迭代。我在上一篇 blog 中已经说过了,这个递归的东西要找的其实是一个“不动点”。对于一个函数
不过,因为我见过的用不动点迭代来求解的情况
具体来说,现在我们有一张大图,里面有一个小框,这个小框里将包含这个大图本身的一个缩小版本,当然,缩小版本里还有更小的版本,如此递归。我们令
我写了简单的 Matlab 代码来验证,随便找了一张场景类似的图来做试验,代码里面硬编码了许多数字,就不要说我代码丑了啊!
ratio = 0.45;pi = 759; pj = 1496;w = 1914; h = 1254;Nit = 100;threshold = 10; img = imread('input.jpg');x = img; for iit = 1:Nit xsmall = imresize(x, ratio); xnew = img; xnew(pi:pi+h-1, pj:pj+w-1,:) = xsmall(1:h,1:w,:); diff = x-xnew; diff = sum(sum(sum(diff.*diff))); if diff < threshold break; end x = xnew; imwrite(x, sprintf('iter-%02d.jpg', iit), 'jpg');end
结果异常好,这是一张 4272×2848 的图片,在 12 步之内就收敛了,结果就是上面的图。下面再看一张迭代第二步的图:
可是,仔细一点看,有没有发现问题?作弊呀!这明明就是把图片不断缩小贴到那个地方这么一个简单的步骤嘛,什么不动点呢?所谓“收敛”其实就是图片缩小到看不清楚了为止吧!嗯,确实没错,过程就是这样的,但是并不是在作弊,因为这个就是不动点迭代呀,我想数学最美妙的地方应该就在于那些可以很直观地表现为一种简单明了的过程的一些东西了吧。
用同样的方法,加上一些复杂一些的变换,诸如旋转呀,甚至三维扭曲呀之类的,可以做出更 cool 的图来,而之前那篇 blog 里的那张双重递归的图,应该也是可以用双重嵌套迭代的方法求出来了。哎呀,好像原本很有意思的东西被这样一摆明了,倒是觉得有些无聊了。 -.-
不过,如果你感兴趣的话,关于不动点迭代,我还可以多说两句。通常讲到不动点迭代求解通常都会举的一个例子是迭代法求平方根,例如,要求
首先,第一个条件是可以证明的,由迭代公式
当
因此
接下来,关于第二个条件,我们可以直接举出一个反例
其实对于这个问题,把图画出来就很明了了,蓝线是
注意上图横纵坐标比例不一样,否则直线应该是 45 度角的。迭代的过程其实就是在 x 轴上取一个点,找出曲线上对应点的纵坐标,作过 y 轴上该纵坐标点出的斜率为 -1 的一条直线,该直线于 x 轴的交点就是新的 x 。这个值会逐渐接近不动点
那么对于其他情况呢?特别是对于我们递归图像的情况呢?这个迭代过程是否收敛呢?要证明这个收敛性似乎就变得非常复杂了。不过,如果从工程师的心态来看的话,那就先试一试好了,如果结果好,那就皆大欢喜了,管他收敛不收敛!