改进的随机分块模型

改进的随机分块模型（共4篇）

改进的随机分块模型 篇1

一、对 (s, S) 型随机存贮策略模型回顾

(s, S) 型存贮策略是一种随机需求的存贮策略。为了保证定期订货但订货量不确定的情况下盈利的期望值最大, 采取如下的存贮策略:每阶段初期检查存贮, 当存I (当前库存)

二、 (s, S) 型随机存贮策略模型的不足

本存贮模型是一个经典的定期订货的随机存储模型, 但是它认为经济库存总容量减去需求量就是需要存储的量, 从而忽略了需求的过程不是瞬间完成的, 而是在一段时间内持续或间断性发生的, 也就是说库存总量的削减是有一个过程的。因此, 当期的库存量不仅仅是期末残留物品的库存还应该包括整个需求过程中当时在管物资的库存量。如图1所示, 在T时间内发生的库存除了未销售完的物品Q-r需要发生库存外, 同时销售量r在T时间内也是逐步实现的, 其也占有库存成本。

三、对 (s, S) 型随机存贮策略模型的改进

随机需求从总体上来说, 它仍旧会满足一定的统计规律。在一个周期的具体需求过程中, 需求总是围绕着平均水平上下波动, 如图2所示。因此, 我们要从整体上把握一个周期的不确定的随机需求属性的时候不妨研究其平均需求的属性。这样就可以把难以把握的不确定需求转变成均匀需求。

通过统计, 我们不难获取到当前的库存量I、平均需求速率是服从概率密度为的随机变量则t时间内的需求量, 由于需求量不可能是负数, 那么显然。同时, 我们知道一个周期内单位物品存贮费用为C1, 单位物品的缺货成本为C2, 每次订购费用为C3, 货物单位成本为K。每次订货量为S-I, 临界订货点为s。那么, S和s就是我们的决策变量。

我们首先确定S。根据存储规则, 只要在期初发生了订货, 那么订货量一定是S-I, 则期初库存为S。如果期初库存S<需求量pt则会缺货 (如图3所示) , 如果期初库存S>需求量pt则m没有缺货成本 (如图4所示) 。显然, 当时不会发生缺货, 而时必定发生缺货。

那么:

一个周期的存贮成本的期望为:

一个周期的缺货成本的期望为:

一个周期内发生订货的可能性为:

则一个周期的总成本期望=货物成本+存贮成本期望+缺货成本期望+订货成本期望

由已知得, 那么

为了是总期望最小, 等式两边对S求导得:

令表达式中仅有S一个未知数, 故可以由此确定S的值。

与原模型一样, 如果本周期不需要订货, 则可以节省出C3, 显然同样存在s使得如下的不等式成立。

选取其中最小的一个s最为本改进后的 (s, S) 存贮策略的s。

经过改进后的 (s, S) 存贮策略尽管仍旧不能完全满足不断变化的现实要求, 但是相对于原模型而言已经具有了更大的适用性。

参考文献

[1]运筹学教材编写组:《运筹学》.清华大学出版社, 2002

[2]林勇:基于随机提前期的 (Q, s) 库存模型.物流技术, 2007

[3]张旭万:库存影响需求率的供应链EOQ模型.重庆工商大学学报, 2007

改进的随机分块模型 篇2

关键词：数据网格,数据复制,动态下载,带宽,模型

0 引言

数据网格是网格计算中的一种[1],数据网格管理着存储在许多计算机并扩散在许多站点的大量数据。它的目标是使在不同计算机上的不同用户能共享数据。在网格中,用户可以从本地或其他具有目标文件的计算机上并行下载文件,然而跨越Internet传输大量的数据是非常费时的。2002年,这种单并行下载模型开始提出[2],但当每个用户都使用并行下载时,他们将竞争系统资源,导致效率下降。同样,当更多用户使用并行下载模型时存在一个不公平的问题,各用户为了完成各自的工作,单个下载用户必定存在较长时间的等待。并行下载模型在管理从多个服务器下载的文件上存在一定的额外延时,因此,如果没有足够的控制机制,多服务器并行下载的效率将大打折扣。

1 相关研究

1.1 静态服务器选择模型

在网络中,当客户机找到具有目标文件的很多服务器时,下一步就是选择合适的服务器和大小合适的数据块来下载。本节概述具有一些静态因素(如网格拓扑结构、服务器资源等)的静态服务器选择。

文献[3]首先提出了通过考虑服务器—客户机带宽来选择服务器。如果服务器到客户机具有较低的带宽,那么它具有较低的优先级,选择优先级高的服务器来下载。

文献[4]提出一种为并行下载识别服务器选择的拓扑结构。服务器传输数据到瓶颈链之后,下载速度限制了整个并行传输。即使有许多具有目标文件的服务器,传输速度也受瓶颈带宽的限制。如图1所示。在图1中,假设各服务器的带宽分别是4MB、4MB,5MB,5MB和6MB,如果没有瓶颈链,客户机将具有24MB/S的下载带宽,但如果客户机与服务器之间具有2MB/S的瓶颈带宽,则客户机的下载带宽将减到2MB/S。因此,如果客户机在瓶颈链之后选择太多的服务器,并行下载的流量将由于存在瓶颈链带宽的限制而减弱。

此外,文献[5]提出了一种考虑网络扩缩性和服务器资源的服务器选择方法,通过比较带宽和资源来选择服务器。

静态服务器选择并不可靠,因为网络环境总是变化的。用静态服务器选择实现并行下载非常容易,但只适合于所有服务器都不共享相同瓶颈链和网络环境是固定的情况。

1.2 动态服务器选择模型

动态服务器选择是为适应网络环境和服务器负载的变化而提出的。

1.2.1 Pablo Rodriguez模型[2]

Pablo Rodriguez提出了一种适应性的并行下载方法,它将目标文件分割成较小的数据块,客户机从服务器中下载以数据块作为传输单元。首先,客户机分别从每一个服务器请求下载一个数据块,如果某个服务器完成了一个数据块的下载,客户机再从该服务器请求下载一个尚未下载过的数据块,直到所有的数据块都被下载完全为止。

最小的数据块大小取决于网络环境和系统负载。理论上,划分成的数据块的大小越小,需要处理的块就越多,因此需要更多的并行机制。然而,分块越多也意味着更多的控制信息(包括请求和响应信息)。到目前为止,在并行下载开始时,还没有一种方法来定制最佳的数据块大小。本文将提出一种确定目标文件分块数量上限的机制。

1.2.2 Junchi Funasaka模型[6]

Junchi Funasaka提出了一种方法,首先计算每一个服务器流量来获得历史平均传输速率进而划分数据块,然后客户机据此速率决定下一次向该服务器请求的数据块的大小。例如,有3个服务器,从服务器C请求的数据块大小由,这里A、B、C分别是各自服务器的平均流量,Rest为被下载文件余下的尚未下载的文件大小。如果某一服务器在以往有较大的流量,系统就分配给该服务器较大的数据块。

1.2.3 Chih-Huang Chao模型[7]

Chih——Huang Chao进一步完善了Junchi Funasaka提出的并行下载方法。他把目标文件划分为大小相等的数据块,在同时请求或依次请求时,一个数据块被分配给不同的服务器来下载。假定对服务器的请求顺序都按服务器序号及目标文件分块后的逻辑顺序申请。通过使用多个服务器下载相同的数据块,最快的服务器能首先完成。例如在表1中,每一个数据块被分配给2个服务器。假定只能选择服务器1和4进行下载,且服务器4的速度比服务器1要快,那么数据块3的下载就有可能在服务器1完成数据块2的下载之前完成。因此,当服务器1完成下载数据块2后,它可以跳过下载数据块3。

此外,文献[8]研制了并行下载工具软件,它允许用户控制使用的线程数量、确定传输块的大小、确定多大的内存缓冲区专用于下载的数据块等。当大量的站点同时访问同一服务器的同一目标文件时,由于基础结构的瓶颈,复制时的性能减弱将发生。

2 基于带宽的文件分块动态并行下载模型

为了防止不同的并行下载作业同时相互影响。本文提出了一种考虑服务器输出带宽和客户机输入带宽的文件分块动态并行下载模型,我们将它划分为以下三个阶段。

2.1 初始化阶段

初始化阶段主要是确定服务器的优先级、目标文件的数据块大小以及用到的系统参数等。如表2所示。

(1)选择服务器

客户机通过复制定位服务RLS(Replica Location Service)程序将包含目标文件的服务器列出,假定有N个服务器含有这个目标文件。为了选择服务器,我们根据优先级给服务器排序。首先按下式给每个服务器分配权重:

这里,SWi为服务器i的权值,PTi JWi的含义见表2。如果服务器i与客户机在相同的站点,则PTi=0,PTi可以通过Ping实用程序来估计;服务器的权值越大,它的选择优先级就越低。假设n是目标文件等分后的数据块数,通常n远大于N,因此所有的N个服务器都可被选中以实现并行下载。如果n

(2)确定数据块数量n

为了计算最合适的n值,必须考虑并行下载存在的额外延时,包括内部和外部的额外延时[9]。

●内部额外延时(10)这类额外延时指伴随每个数据块下载发生的额外延时量。如建立或重新建立TCP连接的时间、数据块的排序时间以及数据块重新组合成目标文件的时间。

●外部额外延时(EO)理论上,这类额外延时发生在整个并行下载过程中,它包括初始连接的同步时间、缓冲区准备时间以及建立其他协议的时间等等。

EO和IO的值是动态的,根据所用传输设备和传输介质的不同而不同,使用不同的网格软件获取,EO和IO的值可能不同。如果一个服务器分到m块来下载,它的总额外延时量为:EO+(m-1)×IO。

从一个服务器的下载时间最好等于该服务器的最大带宽。为了防止在最快的服务器上有太多的额外延时。总的额外延时量应小于实际的数据块的传输时间,我们据此计算目标文件被等分后的数据块的数量。假定我们分配的数据块大小适合服务器的带宽,同时设服务器f是最快的服务器(具有最大带宽),那么,分配给服务器f的数据块数为:

式中的Bki、MTi的含义见表2。为了使额外延时量小于数据块传输时间,我们有:

由式(2),可以推算出n的上限。例如,假定有4个服务器A、B、C和D,它们具有的最大带宽分别是:40MB、30MBPS、20MBPS和10MBPS。我们根据它们的最大带宽来分配数据块给服务器。本例中服务器A是最快的服务器,因此根据式(2),有:

化简后,得:

结果表明了数据块数n与目标文件大小F之间的关系。假设EO=3S,IO=1S且F=800MB,算得n≤15。也即,在最快的服务器上,为了保证网格系统的额外延时小于数据块的下载时间,数据块数不能大于15。

2.2 运行阶段

(1)并行下载开始时,选择优先级在前2位的服务器来下载目标文件这两个服务器一边传输数据,一边监测客户机的下载速度。客户机的下载速度受它所用网卡的速度和它所连接的路由器速度的限制,在互联网协议中,通过使用严格的路由选择,设置从客户机到路由器的连接及由路由器返回到客户机的路由通路,可以测到客户机端的最大流量。

(2)根据客户机带宽适时增减参与并行下载的服务器如果下载速度没有达到客户机的最大下载带宽,将增加一个服务器来下载剩下的数据块。如果客户机达到了最大的下载带宽,将不再需要分配服务器来完成并行下载作业。

(3)动态调整服务器下载数据块的数量根据服务器流量,从服务器i中分配BKi个数据块来下载,但当服务器正在下载时,网络环境在不断变化。因此,我们提出动态地改变分配给每一个服务器的数据块数量。通过计算每一个服务器已下载的块数来决定那一个服务器有较好的流量。在客户机未达到最大下载带宽的情况下,我们进一步将目标服务器划分为三种类型,即低速服务器、中速服务器和高速服务器。用hi表示服务器i实际已经传输到客户机的数据块数,假定现在使用K个服务器,那么,如果hi≤(h1+h2+…+hk)/3,则服务器i为低速服务器;如果(h1+h2+…hk)/3≤hi≤(h1+/h2+…+hk)/2,则服务器i为中速服务器;如果hi≥(h1+h2+…+hk)/2,则服务器i为高速服务器。对低速服务器,每次分配1块,对中速服务器,每次分配2块,对高速服务器,每次分配3块。为防止较快服务器变慢并锁定分配给它的块数,在下一次分配之前,服务器类型将再次检测并重新划分。

2.3 结束阶段

(1)监测最后一个数据块的请求和传输结束阶段的主要工作是尽可能地及时确认每一个服务器完成的最后请求,关注最后一块的下载效率。这一工作很重要,如果最后一块传输缓慢或服务器死机,将增加整个并行下载的时间。

(2)高速服务器帮助低速服务器完成最后一块的传输如果一个高速服务器或中速服务器完成了它的最后一块的数据传输,可能还有许多较慢的服务器还在传输各自的最后一块,已经完成的服务器将被随机地分配单一的原先已分配给低速服务器的数据块来并行下载,直到客户端已经全部下载完所有的数据块为止。

3 模拟实验与分析

3.1 网络拓扑结构

在我们的实验中,利用计算机通过互联网建立如图2所示的网络连接来测试这种并行下载模型。主干带宽约为2.488Gbps,交换机和路由器之间采用千兆以太网,带宽约lGbps。

3.2 本模型与静态、动态并行下载模型的比较实验

实验中有3个目标文件,文件大小分别为100MB、500MB和1GB。有9个结点并且每一个结点具有不同的文件组合类型。表3为复制分布情况。在表3中,符号“√”表示该结点上有相应的目标文件,符号“X”表示该结点无此目标文件。有6个作业请求要下载相应的目标文件。例如,网格结点S01、S03、G03和G05(表中的序号为1,3,7,8)都具有供下载的100MB的目标文件,网格结点S01、S05和G03(表中的序号为1,5,7)都具有供下载的500MB的目标文件,网格结点S01、S04、G05和G07(表中的序号为1,4,8,9)都具有供下载的1GB的目标文件;网格结点S02(表中序号为2)有作业1请求下载1GB的文件,网格结点G05(表中序号为8)的作业6请求下载500MB的文件等。

表4表示用于下载的服务器以及文件分块后划分给每个作业下载的数据块数。在表4中,对于静态并行下载,数据块数等于并行下载的服务器数。对于动态并行下载,我们使用的数据块数分别有10、12和15,并且所有的服务器都可能同时被使用。对于本文的模型,首先必须选择两个服务器来初始化下载任务,其他服务器在下载期间随时增加。以作业1为例,作业1的优先级使用式(1)计算,结果如表5所示。

由于MTi(服务器i的最大流量)不能大于该服务器网卡的带宽,假定MT1=MT2=MT3=MT4=MT5=125MB/S,MT6=MT7=MT8=MT9=50MB/S。经我们的网格环境实际测试,此时的EO≈0.6S,IO≈0.5S。

此时,BK1=[125/(125+125+50+50)×n]=0.357n,根据式(2),有:

求得n≤15.8。因此,我们的作业1和作业4最大n为15。通过相似计算,作业2和作业6的n≈7.53,因此最大数据块数n取7,作业3和作业5的n≈1.1,因此最大数据块数n取2(在我们的模型中,块数不能小于2块)。

图3给出各种模型下的实验结果。实验表明,使用10块或15块的动态并行下载的效率小于使用12块的效率。甚至,本文模型的并行下载性能优于其他动态并行下载的性能,同时还发现,较大目标文件具有较好的并行下载性能。

实现中还有两个变量可以影响并行下载的性能。一个是客户机的状态,另一个是网络环境。例如在图3中,作业2和作业4具有相似的参数,然而,作业4获得较好的性能,原因是这2个客户机归属另一个部门,除我们的网格作业之外,它们还担负其他作业的运行并且是在我们的控制之外。同样,服务器之间的连接要通过互联网,互联网环境更为复杂,这两个因素导致不同的性能。

4 小结

4.1 影响动态并行下载效率的三个主要因素

动态并行下载模型的提出是为了提高下载速度,并与其他下载模型的性能相比较。以下三个因素影响并行下载的效率:

(1)目标文件大小如果目标文件太小,并行下载的额外延时相对于下载时间就过于浪费,其结果是较大文件比较小文件具有较好的下载效率。

(2)服务器选择为了避免并行下载过程中过度使用服务器而降低效率,需使用到客户机的最大下载带宽信息。如果客户机的下载速度已经达到它获得的最大带宽,此时不再需要增加服务器。

(3)数据块大小较小的数据块更能适合多变的网络环境,因为它减少了较慢服务器获得较大部份目标文件的机会。但如果数据块太小,将增加较多额外的控制信息而增加下载时间。因此确定并行下载的最佳数据块的大小是很重要的,它直接影响并行下载的效率。

4.2 基于带宽的文件分块动态下载模型的主要步骤

以前的并行下载方法,没有考虑多并行下载过程中彼此的相互影响。为了从服务器中下载,有两个因素限制最大下载速度,一个是服务器输出的带宽以及客户机输入带宽,另一个就是目标文件大小及文件分块的数量。我们提出了一个考虑了机器带宽、目标文件大小和分块数量的动态下载模型。本模型在多并行下载环境中比单个下载提供较好的效率,且在没有降低自身并行下载效率的情况下,避免了服务器的过度使用,本模型实施的主要步骤归结如下:

(1)确定优先级以选择较好的两个或两个以上服务器来下载;

(2)根据需要,服务器一个接一个地加入并行下载,直到客户机达到它的最大下载带宽;

(3)考虑目标文件的大小、内部和外部额外延时以及服务器的能力来计算目标文件的分块数量;

(4)在客户机未达到最大下载带宽的情况下,根据以往的下载数据将服务器分为三种类型的队列,即低速服务器队列、中速服务器队列和高速服务器队列,据此选择服务器并动态确定分配多少个数据块给该服务器来下载;

(5)及时监测最后剩余数据块的传输速度,必要时分派高速服务器并行下载最后剩余块,以避免传输过程中无限循环等待或饥饿状态的发生。

参考文献

[1]Ian Foster,Carl Kesselman,Steven Tuecke.The anatomy of the grid: Enabling scalable virtual organization[C]//Proceedings of the International Journal of Supercomputer Application,2001,15(3):200-222.

[2]Pablo Rodriguez,Ernst W Biersack.Dynamic Parallel access to replicated content in the internet[C]//IEEE/ACM Transactions on Networking, 2002,10(4):445-465.

[3]Sandra G,Dykes,Kay A Robbins,Cliton L Jeffery.An empirical evaluation of client-side server selection algorithms[C]//Proceedings of Nineteenth Annual Joint Conference of the IEEE Computer and Communications Societies,2000(3):1361-1370.

[4]Yoshinori Higashi,Shingo Ata,Chikato Fujiwara.Topology-aware the Consumer Communications and Networking Conference(CCNC)[C]. January,2005:235-300.

[5]Zhou Xu,Lu Xianliang,Hou mengshu,et al.A speed-based adaptive dynamic parallel downloading technique[C]//Proceedings of ACM Special Interest Group Operating System Review,2005,39(1):63- 69.

[6]Junchi Funasaka,Nozomi Nakawaki.A parallel download method of coping with variable bandwidth[C]//Proceedings of the 23rd International Conference on Distributed Computing System Workshops,May,2003:14 -19.

[7]Chih Hung Chao,Jung Shian Li.A novel BiB-based parallel download scheme[C]//Proceeding of the Asia-Pacific Conference on Circuits and System,December,2004:461-464.

[8]Scott Atchley,Stephen Soltesz,James S Plank,et al.Video IBPster[J]. Future Generation Computer Systems,2003,19(6):861-870.

改进的随机分块模型 篇3

为提高云存储数据中心的信息安全性, 并保证一定的可用性, 本文提出了一种动态分块的数据存储服务模型。

1.1 模型说明

(1) 模型中的各个数据中心可以是采用云存储技术的同一大型数据中心的不同存储区域, 也可以是在整个云资源池中不同地域但通过网络连接的各个相对独立的数据中心。

(2) 该模型认为一个独立的数据存储区域 (或数据中心) 是不安全的。将用户的私有数据进行重新编码, 并随机分出1/n部分数据, 存储在异地存储区域, 剩余部分存储在本地。若本地存储区域数据泄露, 则无法获得全部数据内容;泄露数据经过了重编码, 在缺少部分数据的情况下无法对原始数据还原。

(3) 数据中心之间建立两条双向的传输链路, 业务链路进行相互间业务需求的传输, 包括私有数据分出的数据块, 以及相互间业务请求的认证信息;数据传输链路进行不同数据中心备份数据的传输, 本地数据在异地数据中心进行n:1数据备份, n≥1。设立两条传输链路的目的是为了提高数据传输速率, 防止在业务高峰期产生数据拥塞。业务链路进行各数据中心间的业务请求及数据传输, 建立专用的数据传输链路。

(4) 各数据中心拥有不同的编码方式, 一个数据中心不知道另外一个数据中心的编码及存储机制;本地数据中心只对本地数据进行编码, 只负责管理存储在本地的各类数据。

(5) 本地数据中心在向异地数据中心请求获取存储在异地的本地数据块, 需要进行身份验证。若未通过身份验证, 则认为对方处于不安全状态。

(6) 各数据中心存储区域分为私有数据存储区、公共数据存储区、异地分块数据存储区和异地备份数据存储区。公共数据存储区为存储对各个用户都可见的数据存储区域;私有数据存储区存储本地数据中心客户的私有数据;异地分块数据存储区存储的是异地私有数据拆分出来的数据块;异地备份数据存储区为异地数据进行备份。

1.2 客户终端写信息过程

(1) 身份认证和数据拆分。数据中心A的客户通过身份认证后, 将要存储的私有数据发送到数据中心, 数据中心A首先将数据进行编码和数据拆分。拆分出的1/m数据块通过业务链路分别传送到数据中心B和数据中心C, 并建立路由信息。

(2) 数据备份和数据传输。数据中心B和数据中心C将该数据块存储到本地的异地分块数据存储区, 两者互为备份。拆分后剩余的 (m-1) /m部分数据, 存储在本地私有数据存储区, 并通过数据传输链路传输到数据中心D进行备份。备份数据可以在n处数据中心进行备份, 但不能在存有拆分出的1/m数据块在同一数据中心中。

1.3 客户终端读信息过程

(1) 公共数据的读取。数据中心A的客户在读取其公共数据时, 首先由客户发送数据读取请求。客户请求通过验证后, 将请求发送到公共数据存储区, 并将请求读取的数据发送给客户终端。

(2) 私有数据的读取。数据中心A的客户在读取客户私有数据时, 由客户发送私有数据读取请求。客户请求通过验证后, 一是将请求发送到本地私有数据存储区, 读取存储在本地的私有数据;二是通过异地存储的分块数据路由信息, 向数据中心B发送读取异地分块数据的请求, 通过数据中心间的身份认证后, 数据中心B将存储在本地的1/m数据块经由业务链路发送到数据中心A。数据中心A通过将本地的 (m-1) /m的本地存储数据块和1/m的异地存储数据块进行数据整合, 经过解码后发给客户终端。

2、存储模型的性能分析

2.1 安全性分析

该存储模型的安全性能提升主要在于客户数据分为了两部分, 存储在不同的数据中心中, 若一个数据中心发生数据泄露, 则泄露出的数据是不完整的, 其数据还原仅仅利用泄露的部分数据是无法实现的。

若要获得全部信息, 必须获得被拆分出去的部分数据块。假设各个数据中心被攻破的难度一样, 整个云环境下的数据中心有n个, 分出的数据块有k个备份, 为满足上述安全模型, n≥4, k≥2。在最好的情况下, 第一次就攻破含有拆分出去的数据块的数据中心, 其几率为k/n。一般情况下, 在攻破i (i≥2) 个数据中心能够获得所需数据块的概率为p (i) :

则在一个云存储环境下, 在上述模型中, 在攻破一个数据中心的情况下, 要获得完整的数据信息, 还要再攻破云中数据中心的平均个数为M:

根据式 (2) , 取几组 (n, k) 取值进行分析比较如下:

表1不同 (n, k) 取值分析对比

由表可以看出, 当n一定, k越小, M越大;当k一定, n越大, M越大。即在上述云存储环境模型中, 数据中心越多, 客户私有数据异地存储数据块的备份数越少, 则其安全性就越高。

2.2 可用性分析

在上述模型中, 数据中心可以进行数据的冗余备份, 当本地数据中心遇到故障或误删除等操作失误时, 可以从异地的备份数据进行读取。但必须注意的是, 由于信息安全性要求, 备份的同一私人数据分出的本地存储数据块和异地存储数据块不能在同一数据中心中备份。

2.3 数据服务性能

改进的随机分块模型 篇4

人工智能(Artificial Intelligence)是近年来计算机领域研究的新兴问题,它是让计算机通过已编写的程序来模拟人类行为的一门科学。该领域的研究包括机器人、语言识别、图像识别、自然语言处理和专家系统等。人工智能的应用,可以提高现代复杂单一工业的工作效率以及工作水平。计算机视觉是人工智能的一个很重要、应用广泛的领域。

计算机视觉是一种给予机器视觉的学科,更进一步说,就是机器或者计算机通过摄像头或者现有的图像获取信息,并对外界做出相应分析的一门学科。其应用领域非常广泛,包括监控录像中的人员自动辨别,道路交通限速违章拍照中的车辆车牌的自动识别,保密部门的生物特征识别门禁系统等。特别是随着移动网络平台商品交易的日益流行,一个可靠的脸部识别功能可以进一步提高移动APP支付平台交易支付的安全性。

人脸特征提取是人脸识别的关键问题之一。近年来,研究者将局部二值模式(LBP)的方法引入到人脸特征提取中[1,2,3],取得了很大的成功。但是LBP算子本身并不完善,特别是在训练样本的维度高达几千甚至上万维的时候,其性能会急剧下降。针对此问题,本文采用分块技术,将分块后的LBP直方图串联起来形成一个高维的直方图特征矢量,接着利用经典的主成分分析(PCA)方法降维,最后利用相似度计算方法进行相似度对比。该方法针对不同的图像进行不同的分块,使得维数的约简更加方便,实验结果表明有效提高了特征提取的准确性。

2 LBP算法与LBP算法分块的实现

2.1 初始LBP算法

图像是由基本的像素点构成的,每一个像素点就会有一个对应的色值,彩色图像就会有三个对应红、绿、蓝的色值。如图(1)所示,取一个3X3的像素点阵,以中间的一个像素点作为阈值参考,剩下8个像素点进行比较,按照公式(1)(2)的算法,可以得出一个8bit的二进制数列G(其中gx为第x位像素色值,gc为中心点像素色值)[4]。

将数列G进行十进制转换得到一个0~255区间的数字,这个数字就是一个LBP数值,如下图[5]:

中间像素点的色值为6,以左上方点为起始点开始的色值分别为6,5,2,1,7,8,9,7,将此数列与色差6进行比对,带入公式(1),(2)得到数列{1,0,0,0,1,1,1,1},将数列进行二进制转换得241,这就是此3x3方格的LBP值。

一张图片中有很多的3x3像素点阵,每一个点阵代表一个LBP值,将这些LBP值统计起来得到一个维度为0~255的直方图,这个直方图就是我们用来图像识别的模式依据,即LBP矩阵(LBPMat)。

2.2 适应旋转性LBP算法

在现实生活中,用初始LBP算法进行比对时,由于图片的角度问题会造成误判和错判,于是就提出了适应旋转性的LBP算法。

在2.1中,二进制数列的起始位置是以左上起始,那么,可以考虑从8个像素点的任意一个起始点开始进行二进制序数列的排列,一个3X3的像素点阵就可以得到8个二进制数列,按照既定好的规则选择一个二进制数列,这个二进制数列就作为该3X3像素点阵计算LBP的依据,例如下图:

2.3 均匀LBP算法

为了提高运算的效率,在提取图片特征值的过程时,往往纹理平滑的像素阵要占少数,而有决定性因素的纹理分明的像素阵要占大多数部分,可以用这些多数的纹理分明的二进制数列的LBP值来进行比对图片,提高运算效率。

一个二进制数列中,其中0,1交替出现3次以内,就可以认为是一个uniform,3次及3次以上,就可以认为不是一个uni⁃form,如下图,属于uniform的二进制排列顺序有58种,再算上所有的不属于uniform的排列顺序,全部为59种[6]。

统计出这59种二进制串出现的频率,得到一个59维度的LBP矩阵,很大一方面提高比对的效率。

2.4 LBP比对过程

通过以上的LBP算法对图像的分析之后,即可获得LBP矩阵。两张图片的相似度比对,即为两张图片的LBP矩阵的对比。基于此,本文提出一种比较算法,将两张图片的矩阵通过统计学中的矩阵相似公式(3)计算相似度,从而定量的计算两张图片的相似程度。(其中dis是两矩阵之间定量的差值,LBPMat1与LBPMat2分别为两个相互比较的矩阵)

得到距离dis后,本文确定两个界值,dis等于0为相似度100%,dis等于LBP矩阵里LBP数值的个数(num)为相似度0%,则可以根据公式(4)计算出相似度(reg)的值。

确定了相似度reg后,则可以根据实际情况制定阈值。如果reg值高于阈值时,则两个矩阵有相似性,反之,没有相似性。

在确定阈值时,不同的应用场合要求也是不同的。需要很强的容错率的人脸支付系统则需要制定很高的阈值,而容错率相对较低的图片相似度搜索引擎则需要制定较低的阈值。

通过reg与阈值的差值对矩阵进行定量的分析后,就可以定性地判断出两张图像是否有相似性。

2.5 LBP算法的分块实现

为了能够优化和改善LBP算法在维数大就比对率和运算率很低的缺点,本文提出对图片进行分块处理。具体过程如下图4:

虚线为图片的分块的线,将图片平分成虚线的几块。将每一块看做单另的图片,进行LBP算法处理。实例图5。

图5是一个3X3分块处理的举例,9个小块,每一个小块可以由LBP算法处理成一个LBP矩阵,然后将每个矩阵叠加成一个LBP矩阵,这个最后的LBP矩阵将作为整个图片的LBP矩阵,可以用公式(3)进行相似度比较。

分块时还解决了一个算法细节,分完块的小块之后,横纵的像素点个数可能不是3的倍数(因为LBP的算法还是要3X3的九宫格来处理)。解决的方法是进行像素的扩充,当分块前检测到像素点个数不是3X分块行数的倍数的情况,就会将前几排像素复制粘贴扩充到图片的后面。再进行图片分块,解决了像素分块除不尽的问题,图6举例。

3 实验验证与结论

3.1 实验策略

拟定一个人脸图片比对样本,分别是20个人在117种不同光照,不同表情的条件下的人脸图片,总共是2340张图片,图片的大小为120X142。如下图所示。

其次就是训练样本,20个人每个人抽出3张表情,总共60张图片。如下图所示。

要进行测试的方法是用2340张图片与这60张图片进行模式匹配,也就是说2340中的每一张图片都要比较60遍,那么总次数就是2340×60=140400遍,很好地达到了实验次数。并且在比对之后用程序判断是否是同一个人,来进行准确度的测试。在测试结束后进行准确度和速度的统计,并且进行分析。

3.2 实验结果

3.2.1 准确度

图(9)是利用0×0到10×10分块对LBP的四种不同的算法每个算法进行分块处理后的准确性的一个统计表,横坐标代表的是将图片分成大块的块数,从1×1到10×10,纵坐标是准确度,图例为初始LBP算法(org LBP),旋转适应性LBP(rev LBP),均匀LBP(uni LBP),旋转适应性均匀LBP(unirev LBP),从这张表中可以看到以下几点。

第一点从横坐标来看,也就是从分块技术提高准确度来看,每一个算法都是曲线的变化率从分块数1×1到10×10变化的越来越平缓的,并且曲线无限接近于100%的准确度。但是,每个算法在10X10分块处理的准确度要比在1X1分块的准确度高40%。也就说明,采用分块技术之后,图片的识别率有了提高。并且从10×10再往上走,就是再进行更多的分块,准确性的提升开始变得微乎其微的。

第二点从纵坐标来看,也就是从同样的分块级别下,算法的选择来看,很明显的上面两根线和下面两根线在10×10分块之前差别特别大,从图例可以看出,下面两条线是包含了旋转不变性的LBP算法的准确性,上面的两条线是不包容旋转不变性的LBP算法的准确性。说明了在同样的分块级别下,不包容旋转不变性的LBP算法的准确性更高。

第三点可以看出的是org LBP的准确率变换曲线与Uni LBP曲线变换趋势差不多一致,带了旋转不变性的两个LBP算法的准确度的变换趋势相一致。

表1是之前那个折线图的数据形式,经市场调查,现在的人脸识别能做到95%就算合格,那么可以看出从10×10分块起几种算法全部可以达到95%的识别率。

3.2.2 运行效率

这里的纵坐标的时间是以毫秒做单位,之前也说过了,实验总共的比对次数大概是2340*60=140400次,并且这个时间统计也包括了将60张拟定数据库图片存入内存的时间,所以平均时间大概在1700/140400=0.012l108毫秒。根据表3横坐标显示,10×10分块以内,四个算法所用的时间是相差无几的,到了更细的分块处理后,算法运行的时间会越来越长。

4 结论

本文提出了一种基于分块技术的改进的LBP算法和一种高效的计算矩阵相似度的方法。根据不同的客户需求定制不同的分块等级,来提高图片的辨识率。所提出的算法在高维度的实际实验中,在10X10分块的处理下,4种改进后的LBP算法的准确度都达到95%。实验数据表明,该改进方法可以有效地提高人脸识别率。

摘要：人脸识别是人工智能科学的重要问题,局部二值模式(LBP)算法是已知的比较精准的用于人脸识别的图像特征提炼算法。在对org LBP(初始LBP),rev LBP(旋转适应性LBP),uni LBP(均匀LBP),unirev LBP(旋转适应性均匀LBP)等几种LBP算法研究的基础上,通过大量实验比对和研究,设计了基于分块技术的改进LBP算法,有效提高了算法的鲁棒性。

关键词：人工智能,计算机视觉,信息安全,LBP

参考文献

[1]Timo Ojala,Matti Pietikainen,David Harwood[J].Pattern Recog-nition Society.1996(29):51-59.

[2]王宪,张彦,慕鑫,张方生.基于改进的LBP人脸识别算法[J].光电工程,2012(7).

[3]房德峰.浅谈改进的LBP算法[J].现代企业教育,2013(16).

[4]M.PIETIKÄINEN,T.OJALA,Z.XU.ROTATION-INVARI-ANT TEXTURE CLASSIFICATION USING FEATURE DIS-TRIBUTIONS.

[5]MäenpääTopi,Pietikäinen Matti,Ojala Timo.Texture Classifi-cation by Multi-Predicate Local Binary Pattern Operators.