金字塔结构逻辑运用二值脉冲对简单图形处理

王 上

从大禹采取疏导治水的方法,到排水系统,再到化工流体设计;从踏板纺织机,到吉姆斯·瓦特的离心调速器,再到机械臂;从算盘,到布莱斯·帕斯卡尔等的齿轮驱动计算,再到William Shockley 等的晶体管电路[1-7].前述的或相似的,每种方法或设备的运用,都为人类生产、生活带来巨大效率提升及能耗降低.这些进步都源于各位先贤对事物自然规律更加深刻的认知及巧妙运用.有时进步是新的自然规律发现及应用;有时进步是多种事物根据自身不同规律,按照特定流程巧妙地组合为的复杂系统[8].复杂系统按照时间顺序自动化运行,从而完成目标任务.人类创建的自动化运行的复杂系统,除了由人按自身心理、行为规律构建的社会系统[9],还有由物体构建的各种自动化系统[5].

目前的计算机是在冯·诺依曼体系结构[10]下,按照脉冲时间顺序,进行二进制布尔运算[7]的电子自动化系统.计算机不仅能按人类给定的程序,高效完成各种复杂的十进制数学运算,还能模拟事物的自然变化规律,甚至能构建一个虚拟的平行系统[11].在虚拟平行系统里,人们不仅可以完成各种图形图像的产品和工程设计,还能创造出比现实更美妙的音乐及影像作品.计算机对图像处理和图像识别的应用,催生出各种算法进行数据分析处理.边缘检测是图像分析处理的第一步,主要是为提取图像中形状这一重要特征信息[12-13].边缘检测也是视觉通过水平细胞抑制作用处理图像的重要步骤[14].边缘检测后,图像会生成很多线性交点.如果这些交点作为特征点,应该会在图像识别、图形定位、三维重构中有较大应用价值.由于目前的图像边缘检测在视角和光照变化影响下交点位置变化较大,边缘检测最大缺点是对纹理和图像层次信息损失非常大.

1980 年,Fukushima 根据生物学家Huble和Wiesel 的层级模型,发明了由输入层、卷积层、池化层、全连接层及输出层构成的CNN 神经网络[15].CNN 神经网络,使得原有的机器学习方法下的图像识别技术取得重大进展.然而,机器学习和图像处理算法,并不符合动物记忆特性,也不符合计算机的布尔运算规则.图像学习和处理过程中,需要消耗大量的数据资源和计算资源.目前,符合计算机布尔运算的并在CAD 等平面设计软件中应用的,二维图形处理算法,是基于交点遍历的算法和简单片链算法[16-17].

早在20 世纪40 年代末,冯·诺依曼就提出了适合大型并行运算且符合布尔逻辑运算的元胞自动机模型方法[18].随着时间推移,在众多研究者的努力下,元胞自动机发展出类似于数学形态学腐蚀、膨胀的布尔逻辑规则用于图像处理[19-23].该规则除了采用原有的边缘检测用于二值图像的处理,还采用坐标逻辑把灰度图像分解成多个不同坐标系的二值图像,两者用CA 并行处理,获得了很好的实验结果[19,21].文献[24]运用不同的元胞自动机规则逐级加密生成水印图像,有效克服了部分水印算法在安全性方面存在的不足.元胞自动机不仅广泛用于图形图像处理,它对空间和时间划分方法,对于物理扩散现象研究也具有启发性意义[18,25].本文尝试根据Margolus 邻域元胞自动机模型二维网格划分方法[18],运用布尔逻辑的脉冲运算规则,采用CNN 神经网络分层结构,对图形进行边缘检测和进一步的研究.

1 金字塔结构逻辑对黑白二值图形的处理

目前,对于黑白二值图像处理的应用,主要是对形状结构有要求,而对灰度特征没有太大要求的文字识别和字迹鉴别.文献[26]中,刘成林等通过对文字二值图像多通道分解方法,使字迹鉴别的计算量有效降低,准确率有效提升.多通道分解的方法,也说明合理的图像分解非常重要.

1.1 Margolus 元胞自动机矩阵类型

Margolus 的2×2 邻域元胞自动机模型划分,不同于冯·诺依曼邻域由上、下、左、右4 个元胞组成[22],也不同于摩尔邻域由上、下、左、右、左上、右上、右下、左下8 个元胞组成[22],它能使二维空间分块和规则复杂性降低[18].

如图1,有A、B、C、D黑(0)或白(1)二值点,构成二维2×2 矩阵.这4 个点分别为黑或白状态下,可构成16 个图形.这16 个图形可以分为5 种组合类型:

图1 二值点构成的2×2 矩阵所有组合图Fig.1 All combination graphs of 2×2 matrix constituted by binary points

第1 种为4 个点为黑(0)的无.

第2 种为1 个点为白(1)构成的点.

第3 种为2 个点为白(1)构成的最短相连线.

第4 种为3 个点为白(1)构成的角,或具有多个方向的最短相连线.

第5 种为4 个点为白(1)构成的单元面.

1.2 黑白点组合分类运算

单元金字塔结构(如图2) 输入的布尔逻辑对2×2 矩阵黑白点构成的5 种情况,分别列出布尔逻辑分类判断运算式:

图2 2×2 矩阵输入的单元金字塔结构图Fig.2 2×2 element pyramid structure of matrix input

判断第1 种情况,4 个点为黑(0),逻辑运算式为

判断第2 种情况,1 个点为白(1),逻辑运算式为

判断第3 种情况,2 个点为白(1),逻辑运算式为

判断第4 种情况,3 个点为白(1),逻辑运算式为

判断第5 种情况,4 个点为白(1),逻辑运算式为

1.3 二值多边形图形的边缘检测

黑白二值点构成的四边形面(如图3),每个点被四个相邻的不同2×2 输入单元金字塔逻辑连接运算,如图4.红色的金字塔逻辑是,根据式(3)运算,输入2 点为白激活状态.黄色金字塔逻辑是,根据式(5)运算,4 点为白激活状态.蓝色金字塔是1点为白或0 点为白不激活状态.

图3 黑白二值点构成的四边形面输入图Fig.3 Quadrilateral input diagram composed of black and white binary points

根据图4 分析,红色金字塔逻辑被四边形面的边激活,黄色金字塔逻辑被四边形面的面激活.如果整个单层都为根据式(3)运算的金字塔逻辑,将激活如图5 阵列的金字塔.

图4 不同特性金字塔逻辑对四边形面不同特征运算图Fig.4 Pyramid logic operational diagrams of different characteristics for quadrilateral surfaces

图5 四边形面输入的边缘检测阵列图Fig.5 Edge detection array with quadrilateral input

对直角三角形面边缘检测,如果是2 点激活的单元金字塔逻辑阵列只能被直边上的点激活.如图6 (a)三角形面上的斜边上对应的单元金字塔逻辑,有3 个输入都为白(1),不能激活根据式(3)运算的金子塔逻辑,但是能激活根据式(4)运算的金字塔逻辑.如果是2 点或3 点激活的单元金字塔逻辑阵列,就能对直角三角形进行边缘检测,构成如图6 (b)的图形.因为含有曲线的面的边可以视为多条直线段和斜线段的组合,所以2 点或3 点激活的单元金字塔逻辑阵列,不仅能处理有斜边的面,还能对含有曲线的异型面进行边缘检测.

图6 三角形面输入的边缘检测阵列图Fig.6 Edge detection array of triangle input

2 点或3 点激活的单元金字塔结构逻辑运算式为

文献[19,21]中的逻辑运算式,根据冯·诺依曼的元胞自动机模型提出,也能对异形结构的二值图形进行边缘检测.本文运算式的不同之处在于,根据不同的划分模型得出.

1.4 金字塔结构逻辑多层阵列的扩散效应

第1 层,输入层的每个点被4 个相邻的2×2 输入的单元金字塔逻辑连接,并构成阵列,如图5 轴测图.在式(6)作用下,能方便快捷地完成黑白二值面的边缘检测,并且向输入面相对位置横向和纵向各扩大1 像素位.

第2 层阵列和第1 层阵列结构相同,也进行式(6)运算.由于,第1 层的边缘检测,图形已经是线性状态,并且第1 层逻辑的输出成为第2 层4 个相邻的不同单元金字塔逻辑的输入.第2 层金字塔结构逻辑阵列被激活的会是第1 层被激活金字塔逻辑阵列边缘的两侧.这样就使得第2 层金字塔结构逻辑阵列,除了将单点排除以外,仅仅具有扩散1 像素位的效应.

第3 层,将第2 层外延1 像素位,且进行了单元面的抑制去除.

通过如图7 金字塔逻辑多层阵列处理,输入层的四边形面处理后的边缘不断向内和外扩散,并且是具有波状形态扩散.由于像素点较少,方形边缘扩散的过程中外缘角很快变成了斜边.在像素点较多的情况下,扩散图形变形相对会慢些.边缘扩散,可以用作一定程度的图像缩放处理.

如果两个独立的图形在相同金字塔逻辑多层阵列中扩散,它们的相交位置会出现干涉现象.

因为后1 层输出值的位置在前1 层位置的左下角,所以图形处理过程中,后1 层的图形总是朝着前1 层左下角偏移.

1.5 图形的规则抽样池化及汇聚

1.5.1 图形的规则抽样池化

正四边形面图形,通过第1 层金字塔逻辑阵列边缘检测,再完成第2 层扩散后,将图形像素按照2×2 矩阵的形式,分为各个小组.每个小组同时抽样左上角、右上角、左下角、右下角像素形成4 幅图形,如图8 (b).将这4 幅图中比较分析,4 幅图较为相似,也和图7 第1 层的边缘检测图相似.它们都是4 条直边组成并且相对位置都是相同的,但相对于第1 层边缘图缩小了4 倍.虽然这4 幅图较为相似,但是由于之前的扩散处理和抽样位置不同,它们在细微处仍有不同.不同之处在于图形位置稍有偏移,且有个角点存在位置不同.

图7 金字塔结构逻辑多层阵列对四边形处理图Fig.7 Pyramid structural logic multilayer array for quadrilateral processing graph

图8 规则抽样池化图Fig.8 Rule sampling pooling diagram

如果将池化的图形,再进行扩散后规则抽样处理.那么之前的4 幅图像,将变为16 幅相似图像,它们会再缩小4 倍.那么1 024×1 024 像素大小的图像,经过4 次如前所述的规则抽样池化,图像将分解为256 张64×64 像素的小图像.如果图形缩小倍数太大,虽然每张图包含有不同的信息,但图形变形会偏大,以致于与输入图形完全不同.在规则抽样池化过程处理中,最好使图形保留8×8、16×16、32×32 像素,以使其图形结构信息较为完整.

对于大图中比较小的局部结构,通过多次抽样可能会损失这部分结构信息.是否可以将大图形,再分解为多个局部图形,或通过变焦的方法,依次解决局部问题.如何减少信息的损失,较大限度地保持图形图像的信息,还需要进一步研究优化.

1.5.2 多层组合金字塔结构逻辑的汇聚

图形在2×2 矩阵输入中,每4 个相邻点与1 个金字塔结构逻辑相连,且每个点只成为1 个金字塔逻辑的输入,那么后1 层图形每次会相对于前1 层图形也会缩小4 倍.如图9,由于4 个组合金字塔结构阵列,每次位置都有些许偏移,导致单元金字塔对应的输入点不同.由于单元金字塔的输入点不同,那么输入点的组合会发生变化,最终激活顶层汇聚点金字塔逻辑的形式不同.

图9 金字塔结构逻辑相连构成的组合金字塔图Fig.9 Composite pyramid diagram with logically connected pyramid structures

逻辑根据式(6)运算时,金字塔逻辑每次偏移使汇聚点下层有时会出现2 个或3 个激活状态的逻辑,激活汇聚点;有时汇聚点下层,会出现0 个、1 个、4 个逻辑被激活状态,从而无法激活汇聚点逻辑.如果是图6 的三角形结构输入也会如图9 得到汇聚点.但它们的结构重心不同,最终的汇聚点会根据重心偏移,导致不同的组合金字塔被激活.

如果先通过规则抽样为多个图形,再通过组合金字塔汇聚,那么1 个图形将能被多个独立的组合金字塔结构逻辑运算.类似于多通道[26],不同组合形式进行运算.虽然有些组合金字塔不一定能激活汇聚点,通过池化处理成的多个金字塔中,总会有几种组合形式将汇聚点金字塔逻辑激活.每个被激活的汇聚点包含的组合信息都有一定的差异,并且每个被激活的汇聚点值都与金字塔下部输入范围的点相关.

这种方法的汇聚处理过程中,会使每个组合金字塔包含的信息都有所偏差,也会损失很多信息.

2 同步脉冲对灰度图像切分

现实中的物体在光照下,经常呈现为灿烂多彩、层次分明的图像.物体的形状、纹路包含了丰富的信息.色彩对图形分类的影响不是最大的,而图像的灰度所构成的多层次图形对分类起到决定性作用.在布尔逻辑运算中,无法直接运算十进制数据.十进制数据转换为二值脉冲方式,再进行逻辑电路计算,是目前计算机进行十进制运算的解决方式.灰度图像是否可以通过二值脉冲形式进行转换呢?

2.1 三角逻辑多层阵列对灰度连线的亮度统计

假设,在→E方向有像素点构成的连线AB亮度为5,BC之间连线亮度为2,连线CD亮度为3.线上各点各对应1 个光敏传感器.50 ms 内,光敏传感器根据点的不同亮度发放相应不同次数(如图10)的同步脉冲数量.光敏传感器将信号输出至如图11的多层网状结构逻辑,每个下层逻辑输出点与上层两个相邻逻辑相连.每一个三角结构逻辑运算式为

图10 灰度线AD 上各点在50 ms 内发放的脉冲数量图Fig.10 The number of pulses emitted by each point on the gray line AD in 50 ms

图11 灰度线AD 激活的多层三角结构逻辑运算图Fig.11 Gray line AD activated multilayer triangular structure logic operational graph

最终,50 ms 时间内,连线AB值 Y′将被激活统计为5,连线CD值 Y′′将被激活统计为3,连线AD值Y将被激活统计为2.

多层三角逻辑对连线亮度统计,能统计出具有灰度值的独立连线亮度和组合连线的亮度.

2.2 二维灰度图像的切分

将具有多值的亮度信号,转换为多个具有二值信息的脉冲信号,能使布尔逻辑对灰度信息图像进行处理.如图12,具有5 个亮度等级的灰度图像,通过将亮度转换为二值同步脉冲信号后,产生如图13 的4 个不同时间的图形.图12 中的灰度图像可以分解为大的方形、三角形、梯形、小的方形.图13中的图形虽然也分解为大的方形、三角形、梯形、小的方形,但缺点是分解的数量比图12 中可分解图形少.

图12 具有5 个亮度等级的灰度图Fig.12 Grayscale image with 5 brightness levels

图13 不同脉冲次数下生成的二值阵列图Fig.13 Binary array diagram generated at different pulse numbers

此种方法的处理方式,特点是先从大的轮廓到小的轮廓,因为一般图像都是局部亮度稍高.如果大的面亮度较高那么图像无法体现局部.如果图像的外周亮度较高,中心位置局部亮度较高,在图像分解过程中,将会在较后的脉冲次数中将大的轮廓和中心位置局部独立显示出来.

通过二值脉冲形式,将灰度图像切分为多个不同时间顺序的二值图形后,可以再运用二值金字塔结构逻辑对图形按时间顺序进行各种处理.

汪海明等[21]所述的通过多个坐标分解方式实现灰度图像边缘检测.本文方法不同之处在于,通过脉冲形式,只在输入层将多值数据进行时间维度二值切分,最后在输出层进行单位时间统计.这样不仅方便前述的多层处理,也减少了数据运算量.如果需要获得灰度边缘,只需通过第1 层边缘检测后,在单位时间内,对输出层每个点进行脉冲数量统计获得.亮度等级设置还需要根据应用场景,配合摄像机实时变焦、实时改变光圈大小,运算设备性能等实际情况,进行进一步研究.

3 异步脉冲对金字塔结构逻辑运算影响

3.1 脉冲延时对逻辑运算的影响

假设,有A、B、C、D这4 个逻辑电路输出至Y逻辑电路,而每个逻辑电路至Y逻辑电路的路径上各有1 个延时继电器.该逻辑电路系统有下述特点:

1) 4 个逻辑和Y逻辑,脉冲输出特性是相同的,脉冲幅宽3 ms,1 个脉冲周期为10 ms.

2) 延时继电器将每个输入脉冲信号延迟5 ms时间.如果,延时继电器在5 s 时间内,被激活大于100 次,延时继电器突然失效,脉冲信号延迟0 ms时间.

3) 如图14,A逻辑脉冲输出至延时继电器A′,延时5 ms (图14 红色部分).B逻辑脉冲输出至延时继电器B′,延时5 ms.C逻辑脉冲输出至延时继电器C′,由于延时继电器C′单位时间内经过多次激活而失效,延时继电器C′延时0 ms.D逻辑脉冲输出至延时继电器D′,由于延时继电器D′单位时间内经过多次激活而失效,延时继电器D′延时0 ms.

4) 逻辑Y在不响应期结束后,进入等待期.不响应期7 ms.当逻辑Y的输入条件满足激活条件时,等待期进入反应期.等待期可以是极短的.反应期也不再对其他输入响应.

5) 逻辑Y在等待期,根据式(6)被2 个或3 个同步脉冲高电平激活.逻辑Y被激活后进入反应期,产生1 个3 ms 幅宽的脉冲信号,然后进入7 ms不响应期.不响应期逻辑Y保持低电平,不对输入产生任何反应.

根据式(6)分析,由于0～ 60 ms 时间内,有4个同步脉冲输入,逻辑Y在这段时间内,不应被激活.如图14,逻辑Y在105 ms 时间内却产生10 个脉冲,前6 个脉冲由C′和D′的同步脉冲共同激活产生,后4 个脉冲却是由A′和B′的同步脉冲共同激活产生.

根据上述假设现象分析,逻辑Y虽然是根据式(6)进行运算.但由于延时继电器的延时和延时失效作用,逻辑Y对逻辑A、B、C、D这4 个逻辑输入的反应发生了变化.如图14,逻辑Y将只被逻辑A和逻辑B、逻辑C和逻辑D,产生的同步脉冲激活.逻辑Y将不被逻辑A和逻辑C、逻辑A和逻辑D、逻辑B和逻辑C、逻辑B和逻辑D,产生的同步脉冲激活.

图14 逻辑Y 在延时脉冲输入情况下的脉冲输出图Fig.14 Pulse output diagram of logic Y in the case of delayed pulse input

如果,有A、B、C、D这4 个逻辑输出构成的2×2 矩阵输入中,逻辑Y根据式(4)运算,只被3个同步脉冲激活,且逻辑Y的输入路径上存在延时继电器有A′、B′、C′、D′.当A′延时继电器延时失效和B′、C′、D′延时继电器未失效;A′延时继电器延时未失效和B′、C′、D′延时继电器都失效,逻辑Y将只被有B、C、D这3 个逻辑输出的同步脉冲激活.那么,可以将逻辑Y的该种情况,视为对B、C、D这3 个点构成的角进行了记忆.如图9 中的多层组合金字塔结构逻辑,由于输入的图形进行了边缘检测和规则抽样,4 个点同时存在同步脉冲的情况,概率很小.对于延时记忆方法,边缘检测和规则抽样具有一定的必要性,否则金字塔逻辑输入路径上的延时继电器会经常性的一起失效.如果2×2 金字塔逻辑输入路径的4 个延时继电器都失效后,金字塔逻辑将只具有边缘检测或扩散的作用.

具有正向延时记忆的金字塔结构逻辑,再次被激活的方式是必要的输入条件满足.然而,脉冲在多层金字塔结构中,经过多次延时处理后,可能会导致本来不同步的脉冲同步,激活有延时记忆的单元金字塔.虽然出现的概率较低,但此种情况是延时记忆的最大缺陷.

3.2 线性交点的检测

假设,有如第3.1 节所述特性的逻辑电路系统,它的区别在于,A、B、C、D这4 个逻辑电路输出至Y逻辑电路的脉冲信号是断续的.该逻辑电路系统的延时继电器的延时功能,不是突然性的失效,而是根据单位时间内延时继电器激活次数与延时时间线性相关的缩短.逻辑Y根据式(4)运算,在等待期内有3 个高电平同时存在被激活.

如图15,该逻辑电路系统的脉冲输入输出,在时间轴上的脉冲信号是凌乱不同步的.4 个逻辑的脉冲输入,使逻辑Y在105 ms 内产生了6 次脉冲.如果,将4 个逻辑输入任意减少1 个,都将使逻辑Y在105 ms 内产生的脉冲次数少于6 次.说明,该逻辑系统在不规则输入的情况下,处于等待期的逻辑被激活概率,与多个高电平在3 ms 时间内相互重合概率相关.有效输入路径越少,多个高电平在3 ms时间内相互重合概率越低,逻辑被激活概率也越低.

图15 逻辑Y 在不规律的延时脉冲输入情况下的脉冲输出图Fig.15 Logic Y pulse output diagram with irregular delay pulse input

类似于摩尔邻域元胞自动机划分的3×3 矩阵模型,对于已经进行了边缘检测的图形,只会面对7 种组合类型,就是无、点、直线、斜线、曲线、相交线、平行线.如果是面对零散点,通过再次边缘检测或边缘扩散处理后,能予以消除.简化后的组合类型,也能通过逻辑运算进行大致区分.

3 ×3 矩阵输入构成的金字塔逻辑,在如图16排布中,R1有效输入点2 个,R2有效输入点4 个,R3有效输入点3 个,R4有效输入点3 个.如果3×3 矩阵输入金字塔结构逻辑也是被3 个同步脉冲高电平激活,那么R1不被激活,而R2、R3、R4将被激活.如果R2、R3、R4的有效输入点,在100 ms 内产生的脉冲次数大致相同,脉冲都是不规律的异步脉冲.那么,有效输入点4 个的R2金字塔逻辑输出的脉冲次数,很大概率比R3、R4金字塔逻辑输出的脉冲次数多.

图16 3×3 矩阵输入金字塔结构逻辑在二值图形矩阵中的排布图Fig.16 3×3 matrix input pyramid structure logic arrangement in binary graphic matrix

根据上述假设现象分析,线性相交点对应的3×3 矩阵输入金字塔结构逻辑R2由于有效输入点更多,在异步脉冲输入情况下,输出的脉冲次数相对更多.R4逻辑虽然也处于线性相交点附近,由于位置稍微偏移,有效输入点仍然只有3 个.R4逻辑与处于线上位置的R3逻辑,在100 ms 时间内,被各有效点具有相同次数的异步脉冲输入,激活的概率接近.根据这个特性,在紧密排布的3×3 矩阵输入金字塔结构逻辑中,图形线性交点可以很方便地被检测.

4 结论与展望

金字塔结构逻辑阵列不仅能高效、可靠地对具有二值特性的图形进行边缘检测、扩散.金字塔结构逻辑构成的二值图形,还能通过规则抽样池化的方法,较为准确地形成多个相似图形,并且能有效缩小二值图形.同步脉冲方式,能将灰度图像处理为不同时间维度的多个二值图形.该方法较大限度地保留了灰度图像的信息,按时间顺序逻辑处理后,经过单位时间统计,能得到灰度边缘,但仍然有部分信息损失.金字塔结构逻辑输入路径上加入延时继电器,在组合金字塔结构下,对图形具有一定的记忆特性.不同输入刺激,产生不同组合金字塔结构性记忆.这种记忆模式不是很稳定,也不易被提取,更加难以局部复制,否则会导致混乱.

本文所述的方法,便于计算机程序模拟实现,且方便整体复制,但是运行效率会比通过电子电路实现效率低.电子电路实现的难点,在于带有计数功能的可变延时继电器大规模、小型化的实现和脉冲同步性的协调,更重要是它难以被标记和复制信息.本文的方法,还有很多不足和未考虑到部分,期望下一步,能进行实质性应用探索和更深入细致研究.