随机波动驱动的异步元胞自动机及其计算通用性

元胞自动机被广泛认为是基于分子自组装技术制造量子计算机、纳米计算机的基本架构,而元胞自动机的复杂度直接影响其并行分布式计算效率以及物理实现的可行性.现有复杂度最低的异步元胞自动机使用3个元胞状态和3条变迁规则能够构造所有逻辑电路,具备与图灵机等价的计算通用性(图灵通用性).为进一步降低通用异步元胞自动机的复杂度,本文提出新型电路元件以及基于该元件的逻辑电路设计方法.不同于同步电路的逻辑门元件,新型电路元件能够有效处理信号的随机波动,对单电子隧道晶体管等纳米材料技术有积极的应用价值.据此,本文提出新的异步元胞自动机模型,该模型仅需3个元胞状态和2条规则,比现有的通用模型复杂度低.除图灵通用性外,本文通过设计大规模分布式逻辑电路,进一步证明所提的异步元胞自动机具备与所有同步元胞自动机同等的计算能力.

一种基于WMF-ACA的深度图像修复算法

针对RGBD相机由于硬件条件的限制,所获取的深度图像往往存在空洞与噪声的问题,提出一种彩色图像引导的深度图像空洞填补方法.对深度图像边缘区域采用基于局部直方图的加权模式滤波器(WMF)进行处理,在有效保留深度图边缘与细节的前提下,消除图像噪声.对深度图像非边缘区域采用一种异步元胞自动机(ACA)模型算法,根据邻域和迭代规则对深度图空洞进行填补,快速、准确地完成任务.在立体匹配数据集Middlebury上测试所提算法实现性能,实验结果表明:该算法的结构相似性(SSIM)与峰值信噪比(PSNR)更高,能够准确地填补深度图空洞,同时保持深度图边缘清晰.