-
摘要: 离线笔迹鉴别在司法鉴定与历史文档分析中有重要作用.当前的主要离线笔迹鉴别都是基于局部特征提取的方法, 其在笔迹检索中严重依赖于数据增强和全局编码, 在笔迹识别中需要较多的笔迹信息.针对这一问题, 本文提出一种基于统计的文档行分割与深度卷积神经网络相结合的离线笔迹鉴别方法(DLS-CNN).首先, 使用基于统计的文档行分割方法将笔迹材料分割成小的像素块; 然后, 用优化后的残差神经网络作为识别模型; 最后, 对局部特征使用取均值法进行编码.在ICDAR2013和CVL这两个标准数据集上的实验结果表明, 该方法能有效获得鲁棒的局部特征, 从而仅需要少量的笔迹信息就能取得较高的识别率, 而且不需依赖于数据增强和全局编码就能取得较好的检索效果.实验代码地址:https://github.com/shiming-chen/DLS-CNN.Abstract: Off-line writer identification plays an important role in forensics and historical document analysis. The current well-known off-line writer identification approaches are based on local feature extraction. They rely heavily on data augmentation and global encoding for writer retrieval, and need a great number of written contents for writer recognition. This paper proposes a new off-line writer identification method, called DLS-CNN, which combines document line segmentation in terms of statistic and deep convolutional neural network. More precisely, handwriting documents are segmented into patches using document line segmentation at first. Secondly, an improved residual neural network serves as the identification model. Finally, the mean value of all local features vectors are used as final global features for writer identification. Experimental results on ICADAR2013 and CVL benchmark datasets show that, due to the extracted robust local features, DLS-CNN achieves higher identification rate with fewer written contents, and better retrieval result without data augmentation and global encoding. All the experiment codes are available at https://github.com/shiming-chen/DLS-CNN.
-
Key words:
- Writer identification /
- writer retrieval /
- document line segmentation /
- convolutional neural network (CNN) /
- features extraction
-
本文主要研究两个工件集合同时在一台批处理机上竞争加工的生产调度问题, 其中每个集合的工件具有共同的释放时间.传统的生产调度研究主要集中在所有工件对应一个客户需求, 作为一个整体考虑一致的性能指标.随着经济的发展和人们消费水平的提高, 顾客对商品的个性化和多样化的需求越来越高, 所以这种传统的所有工件对应一致目标的生产调度问题已不能再满足多客户需求情况下的生产调度问题, 因此迫切需要研究考虑多客户为了自己的利益竞争使用共同资源的生产调度问题.此外, 在实际工业生产中为了提高机器利用率、降低能耗等目的, 经常将具有相似特征的工件组批加工.本文从钢铁企业中提炼出这类满足两个顾客需求的批处理机生产调度问题, 同时工件到达批处理机生产时具有两类不同的到达时间.在钢铁工业的初轧厂中, 经过模铸生成的钢锭要先进入均热炉中加热或保温一段时间, 使钢锭内部温度均匀达到轧制的要求, 而均热炉能同时加热多个钢锭可以看作一台批处理机, 均热炉中一批的加工时间为炉中钢锭最长的均热时间.均热后的钢锭经轧制生成的钢产品一部分直接销售给顾客, 一部分进入热轧阶段进行热轧(如图 1所示).这里直接销售给顾客与进行热轧的钢产品由于需求目的的不同, 对钢级的要求也不同, 所以在均热炉中均热的温度与时间往往是不同的, 因此一般情况下目的相同的钢锭可以组成批进行均热, 而目的不同的钢锭不组成批, 即批是不可兼容的.此外, 两个不同目的的钢锭集合到达批处理机上加工的到达时间可以看作两类不同的释放时间.基于上述初轧阶段的生产特点, 为了满足两个不同目的的生产需求, 同时也为了提高初轧阶段的生产效率、降低能耗, 如何在批处理机上对工件进行组批, 调度两个工件集合的加工顺序是至关重要的研究问题之一.
下面将给出一个具体的实例来解释我们所研究的一台批处理机上具有两类释放时间的工件集竞争调度问题.在上面描述的钢锭初轧生产过程中, 假设热轧阶段需要$\rm 3$个钢产品, 对应的钢锭工件集合为$J^A=\{J^A_1, J^A_2, J^A_3$}.顾客需要直接购买$\rm 2$个钢产品, 对应的钢锭工件集合为.每个钢锭的加热时间分别为集合$J^A$中工件的共同释放时间为$r^A=0$, 集合$J^B$中工件的共同释放时间为$r^B=2$.批处理机的能力为$b=2$, 不同集合的工件不能组成批加工.所考虑的目标函数为在满足集合$J^B$中工件的最大完工时间$C^B_{\max}$不超过一个给定上界$Q_B=7$的约束下, 最小化集合$J^A$中工件的最大完工时间$C^A_{\max}$.具体的参数介绍见第1节中问题描述.对于上述实例, 我们能获得一个最优调度$\pi$满足$C^B_{\max}=6＜Q_B$的条件下集合$J^A$工件的最大完工时间最小值为$C^A_{\max}=4$ (如图 2所示).最优调度不仅满足了顾客的需求, 同时通过最小化热轧阶段所需工件的最大完工时间, 为热轧阶段提高了生产效率.
近几年来, 两个或多个工件集竞争调度的问题作为调度领域中多目标问题的特殊情况备受学者们的关注, 其中每个工件集有各自的优化目标.不同目标工件集的存在使得问题的求解比所有工件对应一个工件集的情况更加困难.多个工件集竞争的调度问题最初由Baker等[1]以及Agnetis等[2]提出, 前者研究了单机上最小化两个工件集目标函数线性组合形式问题的复杂性, 后者研究了单机上依赖两个工件集不同目标函数的有约束优化形式及帕累托形式问题的复杂性.关于多个工件集竞争的调度问题, 读者可参阅Perez-Gonzalez等[3]以及Agnetis等[4].本文主要研究两个工件集目标函数有约束优化的形式, 即找到一个最优调度最小化一个工件集的目标函数使得另一个工件集的目标函数不超过一个给定上界的问题.下面主要针对两个工件集竞争的有约束优化调度问题进行简单综述.
关于单机批处理机上两个工件集竞争的调度问题, Li等[5]提出了多项式或伪多项式时间的算法来求解无界批处理机上批不可兼容与批可兼容两种情况下各种正则目标函数结合的调度问题, 其中针对批不可兼容问题与分别提出了时间复杂度为$\rm O$$(nn_An_B\log(Q_U-Q_L))$与$(nn_An_BP)$的算法, 这里$IF$表示批不可兼容, 具体参数请见文献[5]. Agnetis等[4]针对无界批处理机上批不可兼容的问题与分别提出了时间复杂度为与$\rm O$$(n_A+n_B^4)$的多项式时间算法. Fan等[6]针对有界批处理机上批不可兼容时问题提出了时间复杂度为$\rm O$的最优算法, 同时证明了上述问题当批可兼容情况下以及批不可兼容情况下问题均为NP—难问题.最近, Wang等[7]研究了有界批处理机上工件具有不同尺寸大小、加工时间相同的两个工件集竞争调度问题, 证明出目标函数为最小化一个工件集的最大完工时间, 使得另一个工件集的最大完工时间不超过给定上界问题, 不存在多项式时间算法具有常数的最坏情况比, 同时提出了一个有效算法获得最优解的下界以及两个启发式算法对问题进行求解.虽然上面的文献考虑了批处理机上两个工件集竞争的调度问题, 但所考虑的问题都是工件具有相同的释放时间. Tang等[8]研究了单机无界批处理机与有界批处理机上工件具有恶化加工时间的两个工件集竞争调度问题, 基于批的兼容性与工件释放时间的差异性, 作者对一些目标函数的结合给出了时间复杂性, 其中当批不可兼容且工件存在不同释放时间时, 针对批无界问题提出了时间复杂度为$(n_An_Bn\log(Q_U^\prime-Q_L^\prime))$的最优求解算法, 同时证明出批有界问题对于批可兼容与不可兼容两种情况均为NP—难问题, 具体参数请见文献[8].
关于单机上具有释放时间的两个工件集竞争调度问题, Yin等[9]证明了问题为强NP—难问题, 并提出了分支定界算法进行求解. Lee等[10]对问题提出了分支定界算法与遗传算法进行求解. Wu等[11]证明了问题为强NP—难问题, 同时提出了分支定界算法、蚁群算法以及遗传算法对问题进行求解. Cheng等[12]对问题提出了分支定界算法以及模拟退火算法进行求解.以上文献虽然考虑了工件带有不同的释放时间, 但都是利用智能算法对问题提出近优算法进行求解, 没有从理论分析的角度对具有不同释放时间的两个工件集竞争调度问题进行研究. Dover等[13]研究了单机上工件具有相同加工时间与不同释放时间的两个工件集竞争调度问题, 对各种正则目标函数的结合给出了时间复杂性.
另一方面, 关于批处理机上的调度问题也有许多学者研究.一台批处理机可以同时加工多个工件, 一批的加工时间为该批中工件加工时间最大者, 同一批的所有工件同时开始加工同时结束, 一旦一批开始加工就不能中断, 也不能再加入其他的工件到该批. Potts等[14]对批处理机上的调度问题进行了综述.根据批处理机的能力, 可以分为无界批处理机与有界批处理机. Brucker等[15]研究了单机批无界与批有界两种情况下工件具有相同释放时间的各种目标函数的时间复杂性. Lee等[16]研究了单机批处理机上工件具有不同释放时间, 目标函数为最小化工件最大完工时间问题的时间复杂性, 对批无界情况提出了多项式时间动态规划算法, 对批有界情况当工件具有两类释放时间时提出了伪多项式时间的动态规划算法进行求解, 对一般情况提出了启发式算法. Liu等[17]同样对于上述目标函数证明了批有界情况下问题为NP—难问题, 并对工件具有有限个释放时间情况提出了伪多项式时间算法, 对一般情况设计了贪婪算法. Liu等[18]针对有界批处理机上工件具有不同释放时间的最小化总完工时间问题提出了一个多项式时间近似策略, 针对无界批处理机上工件具有不同释放时间的最小化总加权完工时间问题提出了一个伪多项式时间近似策略.
综上, 目前还没有存在关于工件具有两类释放时间的两个工件集在批处理机上竞争调度问题的研究, 虽然文献[8]中针对无界批处理机上批不可兼容情况下工件具有恶化加工时间与不同释放时间时, 目标函数为最小化一个工件集的最大完工时间, 使得另一个工件集最大完工时间不超过给定上界问题的一般情况提出了伪多项式时间求解算法, 但本文基于问题的自身特征针对该目标函数在批无界与不可兼容情况下工件具有两类释放时间的特殊情况提出了多项式时间求解算法, 同时针对批无界情况下最小化最大延迟与总完工时间问题分别提出了最优求解方法.此外, 对于批有界情况下工件具有不同释放时间时, 目标函数为最小化一个工件集的最大完工时间, 使得另一个工件集的最大完工时间不超过给定上界问题, 文献[8]针对一般情况证明了问题的$\rm NP$-难性, 而本文进一步证明了当两个工件集具有两类释放时间的特殊情况也均为NP—难问题, 同时分别提出了伪多项式时间的动态规划算法对问题进行求解.这样的研究不仅为实际工业生产提供了理论指导依据, 而且从理论上丰富了多个工件集竞争调度的理论研究基础.
1. 问题描述
设有两个工件集合$J^A$和$J^B$, 其中, $J^B=\{J^B_1, J^B_2, \cdots, J^B_{n_B}\}$.设$n$表示两个集合中所有的工件数, 即$n=n_A+n_B$.两个集合中的工件同时竞争在一台批处理机上不可中断地加工, 批处理机能同时加工$b$个工件作为一批.本文假设只有来自同一集合的工件能组成批加工, 即批不具有兼容性.假设工件$J^X_j$具有加工时间$p^X_j$, 工期$d^X_j, $ 批处理机上一批$B_x$的加工时间定义为$p(B_x)=\max_{J^X_j\in{B_x}}\{p^X_j\}$, 工期为$d(B_x)=\min_{J^X_j\in{B_x}}\{d^X_j\}$.每个集合的工件具有共同的释放时间$r^X$, $X\in\{A, B\}$, 即如果工件$J_j^X\in J^X$, 那么它的释放时间为$r^X$.由于两个集合的工件具有两类不同的释放时间, 为了便于问题的分析, 不妨假设其中较小的释放时间记为0, 较大的释放时间记为$r(r>0)$.此外, 假设所有问题中参数均为非负整数.给定一个加工顺序, 定义工件$J^X_j$的完工时间为$C^X_j$, 延迟为$L^X_j=C^X_j-d^X_j$.本文基于两类释放时间的大小比较, 分别考虑了批处理机能力无界$(b>n)$情况, 即批处理机能同时加工任意多个工件作为一批, 与批处理机能力有界$(b<n)$情况, 即批处理机最多能同时加工$b$个工件作为一批.主要研究的目标函数分别为最小化集合$J^A$中工件的最大完工时间$C_{\max}^A=\max\{C^A_j\}, $最大延迟$L_{\max}^A=\max\{L^A_j\}, $总完工时间$\sum C_j^A$, 使得集合$J^B$中工件的最大完工时间$C_{\max}^B=\max\{C^B_j\}$不超过一个给定的上界$Q_B>0.$利用文献[2]提出的表示法, 所研究问题表示为
;
其中$p-batch$表示批处理机.
2. 批处理机能力无界
本节将考虑批处理机能力无界的情形.针对两个工件集各自释放时间$r^A$与$r^B$的大小关系, 分别研究了最小化工件集$J^A$中工件的最大完工时间、最大延迟以及总完工时间, 使得另一个工件集$J^B$中工件的最大完工时间不超过一个给定上界问题的时间复杂性.
2.1 $1|p-batch, r_j^A=r^A, r_j^B=r^B, b>n|C_{\max}^A:C_{\max}^B\leq Q_B$
首先对于求解本节的问题提出如下最优解性质.
性质1. 对于问题$1|p-batch, r_j^A=r^A, r_j^B=r^B, b>n|C_{\max}^A:C_{\max}^B\leq Q_B$, 如果存在一个最优调度, 那么在最优调度中工件集$J^A$与$J^B$的工件分别形成一批生产加工.
证明. 由于一批的容量是无限大的, 所以将集合$J^A$与$J^B$的工件分别在各自释放时间之后形成一批生产加工, 将不会增加各自工件的最大完工时间.
下面基于性质1, 同时针对$r^A$与$r^B$的大小比较, 分别对两种不同情况问题给出多项式时间最优求解算法.
1) $r^A=0, r^B=r$
算法1.
步骤1. 如果, 那么当$\max\{p_j^A\}\leq r$时, 在最优调度中从0时刻开始加工集合$J^A$中工件构成的一批, 从$r$时刻开始加工集合$J^B$中工件构成的一批; 当$\max\{p_j^A\}>r$时, 在最优调度中从0时刻开始加工集合$J^A$中工件构成的一批, 从$\max\{p_j^A\}$时刻开始加工集合$J^B$中工件构成的一批.如果$\max\{\max\{p_j^A\}, r\}+\max\{p_j^B\}>Q_B$, 那么转到步骤2.
步骤2. 如果$\max\{p_j^A\}\leq r$, 那么问题没有解.如果$\max\{p_j^A\}>r$, 那么在最优调度中从$r$时刻开始加工集合$J^B$中工件构成的一批, 从$r+\max\{p_j^B\}$时刻开始加工集合$J^A$中工件构成的一批.
2) $r^A=r, r^B=0$
算法2.
步骤1. 如果$r+\max\{p_j^A\}+\max\{p_j^B\}\leq Q_B$, 那么在最优调度中从$r$时刻开始加工集合$J^A$中工件构成的一批, 从$r+\max\{p_j^A\}$时刻开始加工集合$J^B$中工件构成的一批.如果$r+\max\{p_j^A\}+\max\{p_j^B\}> Q_B$, 那么转到步骤2.
步骤2. 如果$\max\{p_j^B\}\leq Q_B$, 那么在最优调度中从0时刻开始加工集合$J^B$中工件构成的一批, 从$\max\{\max\{p_j^B\}, r\}$时刻开始加工集合$J^A$中工件构成的一批.如果$\max\{p_j^B\}> Q_B$, 那么问题无解.
定理1. 算法1与2均可在$\rm O$$(n)$时间内分别找到问题$1|p-batch, r_j^A=r^A, r_j^B=r^B, b>n|C_{\max}^A:C_{\max}^B\leq Q_B$不同释放时间大小的最优调度.
证明. 由性质1可知, 工件集$J^A$与$J^B$中的工件分别在各自的释放时间之后构成一批加工.当$r^A=0<r^B=r$时, 如果问题存在最优解, 那么: a)当集合$J^A$中工件的最大加工时间$\max\{p_j^A\}\leq r$时, 所有集合$J^A$中工件能够从0时刻开始构成一批加工, 完工时间即为$\max\{p_j^A\}$, 此时集合$J^B$中的工件最早可以从$r$时刻开始构成一批加工, 其完工时间为$r+\max\{p_j^B\}$; b)当$\max\{p_j^A\}> r$时, 如果仍从0时刻先加工工件集$J^A$再加工工件集$J^B$, 能够满足工件集$J^B$的最大完工时间, 则能获得问题的最优解; 反之, 如果$\max\{p_j^A\}+\max\{p_j^B\}> Q_B$, 则最优解中只能最早从释放时间$r$开始先加工工件集$J^B$, 再接着加工工件集$J^A$.
同理, 当$r^A=r>r^B=0$时, 如果问题存在最优解, 那么此时工件集$J^A$的最早开始加工时间为$r$, 如果先加工工件集$J^A$再加工工件集$J^B$, 满足目标约束条件, 则能获得问题的最优解; 反之, 如果$r+\max\{p_j^A\}+\max\{p_j^B\}> Q_B$, 则最优解中只能从0时刻开始先加工工件集$J^B$, 再接着加工工件集$J^A$.
算法1与2中均需求出工件集$J^A$与$J^B$中最大加工时间, 因此时间复杂性均为${\rm O}(n_A)+{\rm O}(n_B)={\rm O}(n)$.
下面给出一个实例来应用算法1.假设工件集合}, 集合$J^B=\{J^B_1, J^B_2\}$.工件的加工时间分别为$p^A_1=1, p^A_2=2, p^A_3=3; p^B_1=1, p^B_2=2.$共同释放时间分别为$r^A=0$, $r^B=r=1$.集合$J^B$工件的最大完工时间上界为$Q_B=4$.
在算法1的步骤1中, 由于, 转到步骤2.又由于$\max\{p_j^A\}=3>r=1$, 所以最优调度$\pi'$为从$r=1$时刻开始加工集合$J^B$中工件构成的一批, 然后再从$r+\max\{p_j^B\}=3$时刻开始加工集合$J^A$中工件构成的一批, 最优调度如图 3所示.
2.2 $1|p-batch, r_j^A=r^A, r_j^B=r^B, b>n|L_{\max}^A:C_{\max}^B\leq Q_B$
针对问题, 给出一个最优解性质.
性质2. 对于问题$1|p-batch, r_j^A=r^A, r_j^B=r^B, b>n|L_{\max}^A:C_{\max}^B\leq Q_B$, 如果存在一个最优调度, 那么集合$J^B$中所有工件在时刻$r^B$或者$r^B$之后形成一批生产加工, 集合$J^A$中所有工件按照最短加工时间(Shortest processing time, SPT)规则生产加工.
证明. 类似于性质1的证明, 很容易得出集合$J^B$中所有工件在时刻$r^B$或者$r^B$之后形成一批生产加工, 这样既不会增加集合$J^B$中工件的最大完工时间, 也不会增加集合$J^A$中每个工件的完工时间, 进而不会增加集合$J^A$中工件的最大延迟.下面假设存在一个最优调度$\pi$, 其中批$B_x$与$B_y$是关于集合$J^A$中工件的任意两批, 且$x<y$, 工件$J_i^A\in {B_x}$, $J_j^A\in {B_y}$, 同时$p_i^A>p_j^A$.将工件$J_j^A$从批$B_y$中移动到$B_x$中, 经过这样的转移后得到一个新的调度$\pi^\prime$.我们可以看到在$\pi^\prime$中工件$J_j^A$的完工时间减少, 其他工件的完工时间都不会增加.因此得到.
由性质2可知, 如果集合$J^A$中存在两个工件$J_i^A$和$J_j^A$, 并且满足$p_i^A\leq p_j^A$, 同时$d_i^A\geq d_j^A$, 那么我们可以将工件$J_i^A$转移到与工件$J_j^A$同一批中, 而不会增加集合$J^A$中工件的最大延迟.由此, 对于问题, 我们可以假设集合$J^A$中所有工件已经按照$\cdots$$\leq p_{n_A}^A$及的顺序排列.
1) $r^A=0, r^B=r$
针对问题, 由性质2设$X_B$为集合$J^B$所有工件形成的一批.设$S_1$为在$X_B$之前加工生产的集合$J^A$中工件的子集, $S_2$为在$X_B$之后加工生产的集合$J^A$中余下工件的集合, 即问题具有最优调度形式$(S_1, X_B, S_2)$, 其中$S_1$与$S_2$中任何一个都可以是空集.
对于调度形式$(S_1, X_B, S_2)$, 集合$J^B$的最大完工时间$C_{\max}^B$由集合$S_1$中工件个数$l$及$S_1$中最后一批工件的完工时间$t$所决定, $0\leq l\leq n_A$.因此如果给定集合$S_1$中工件个数$l$, 问题就分解为在零时刻分别调度子集$S_1$与$S_2$中的工件, 分别使得$S_1$中工件对于每个$t$的最大延迟最小化以及$S_2$中工件的最大延迟最小化, 其中$S_1=\{J_1^A, J_2^A, \cdots, J_l^A$}, .因此, 调度形式的最优调度对应的最小化最大延迟值为
$$ \max\{f(l, t), C_{\max}^B+L_{\max}^A(S_2)\} $$ (1) 使得$C_{\max}^B=\max\{t, r\}+\max\{p_j^B\}\leq Q_B$成立, 其中为子集$S_1$中调度$l$个工件当最后一批工件的完工时间为$t$时的最大延迟最小值.
在式(1)中最大延迟最小值$L_{\max}^A(S_2)$, 所对应的最优调度可以利用Brucker等[15]求解问题的动态规划算法在$\rm O$$(n_A^2)$时间内获得.而最大延迟最小值$f(l, t)$, 所对应的最优调度可以通过下面构造的动态规划算法获得.
算法DP1.
初始条件:
对于每个$l=1, \cdots, n_A$对应在不同的最后一批完工时间$t$下, $t=p_l^A, \cdots, \sum_{j=1}^{l}p_j^A$有如下递归关系: , 如果满足$C_{\max}^B=\max\{t, r\}+\max\{p_j^B\}\leq Q_B$, 其中当前调度中最后一批的工件为对于任意的$h$, $0\leq h< l$.
此时对于每个$l$, 对应在不同的$t$值下, 所有的值以及对应的调度均可在时间内找到.
综上, 针对不同的$l$以及对应不同的$t$值, 在所有得到的$f(l, t)$中, 找到满足条件$C_{\max}^B=\max\{t, r\}+\max\{p_j^B\}\leq Q_B$, 同时最大延迟值最小的所对应的调度即为问题的最优调度.
定理2. 问题能够在$(n_A^2\sum_{j=1}^{n_A}p_j^A+n_B)$时间内求得最优解.
证明. 由性质2, 所研究问题的最优解具有调度形式, 并且所有集合$J^A$中的工件按照同时的顺序排列, 因此最优调度只需确定$S_1$中$l$个工件对应不同最大完工时间的最大延迟最小值, 以及$S_2$中$n_A-l$个工件的最大延迟最小值.为了确定$S_2$中工件最大延迟最小值, 我们可利用文献[15]中求解问题的最优算法从零时刻开始调度$S_2$中工件, 其时间复杂度为$\rm O$$(n_A^2)$.由于$S_2$中工件的实际开始加工时间为集合$X_B$的完工时间$C_{\max}^B$, 而$C_{\max}^B=\max\{t, r\}+\max\{p_j^B\}$, 受$S_1$中最后一批工件完工时间$t$的影响, 因此, 对于$S_1$中每个给定的工件个数$l$对应不同最大完工时间$t$构造动态规划算法DP1, 得出$S_1$中$l$个工件在不同最大完工时间$t$下对应的最大延迟最小值.进而对不同的$l$对应不同的$t$, 找到满足条件$C_{\max}^B=\max\{t, r\}+\max\{p_j^B\}\leq Q_B$, 同时最大延迟最小的所对应的调度即为问题的最优调度.
对于算法DP1, 由性质2可知, 从零时刻开始第一批工件按照SPT规则以及工期不减的顺序在机器上加工, 对应最大完工时间$t$时的最大延迟最小值为$f(l, t)$, 当前调度中最后一批工件对应的最大延迟为$t-d_{h+1}$.因此, 目标函数值为.为了使得调度形式$(S_1, X_B, S_2)$具有可行性, 需满足条件$C_{\max}^B=\max\{t, r\}+\max\{p_j^B\}\leq Q_B$.此外, 算法DP1中还满足$0\leq h< l\leq n_A$, , 所以DP1的时间复杂度为$(n_A^2\sum_{j=1}^{n_A}p_j^A+n_B)$.
综上, 问题能够在$(n_A^2\sum_{j=1}^{n_A}p_j^A+n_B)$时间内求得最优解.
2) $r^A=r, r^B=0$
如果问题存在可行调度, 那么有如下三种情况:
a) 如果$\max\{p_j^B\}\leq r$, 那么在最优调度中集合$J^B$的所有工件从零时刻开始组成一批生产加工, 集合$J^A$的所有工件从$r$时刻开始利用文献[15]中关于求解问题的动态规划算法可在$\rm O$$(n_A^2)$时间内求得最优解.
b) 如果$r<\max\{p_j^B\}\leq Q_B-r-t$, 其中, 由性质2可知, 问题仍具有最优调度形式, 其中集合$S_1$与$S_2$中工件对应的调度与上面时情况相同.而组合后调度形式的最优调度对应的最小化最大延迟值为
$$ r+\max\{f(l, t), t+\max\{p_j^B\}+L_{\max}^A(S_2)\} $$ (2) 其中, $0< t\leq \sum_{j=1}^{n_A}p_j^A$, $r+t+\max\{p_j^B\}\leq Q_B.$
因此, 该情况能够在$(n_A^2\sum_{j=1}^{n_A}p_j^A+n_B)$时间内求得问题的最优解.
c) 如果$\max\{p_j^B\}\geq Q_B-r$, 那么在最优调度中集合$J^B$的所有工件从零时刻开始组成一批生产加工, 集合$J^A$的所有工件从$\max\{p_j^B\}$时刻开始利用文献[15]中关于求解问题的动态规划算法可在$\rm O$$(n_A^2)$时间内求得最优解.
2.3 $1|p-batch, r_j^A=r^A, r_j^B=r^B, b>n|\sum C_j^A:C_{\max}^B\leq Q_B$
类似于性质2的证明, 对于问题, 给出如下最优解性质.
性质3. 对于问题$1|p-batch, r_j^A=r^A, r_j^B=r^B, b>n|\sum C_j^A:C_{\max}^B\leq Q_B$, 如果存在一个最优调度, 那么集合$J^B$中所有工件在时刻$r^B$或者$r^B$之后形成一批生产加工, 集合$J^A$中所有工件按照SPT规则生产加工.
1) $r^A=0, r^B=r$
针对问题, 由性质3, 设$X_B$为集合$J^B$中所有工件形成的一批, 同时有$p_1^A\leq p_2^A\leq\cdots\leq p_{n_A}^A$.设$S_1$为在$X_B$之前加工生产的集合$J^A$中工件的子集, $S_2$为在$X_B$之后加工生产的余下集合$J^A$中工件的集合, 即问题具有最优调度形式$(S_1, X_B, S_2)$, 其中$S_1$与$S_2$中任何一个都可以是空集.
类似于第2.2节, 对于调度形式$(S_1, X_B, S_2)$, 集合$J^B$的最大完工时间$C_{\max}^B$由集合$S_1$中工件个数$l$及$S_1$中最后一批工件的完工时间$t$所决定.因此如果给定集合$S_1$中工件个数$l$, 问题就分解为在零时刻分别调度子集$S_1$与$S_2$中的工件, 分别使得$S_1$中工件对于每个$t$的总完工时间最小化以及$S_2$中工件的总完工时间最小化, 其中$S_1=\{J_1^A, J_2^A, \cdots, J_l^A$}, .因此, 对于问题, 最优调度对应的最小化总完工时间为
$$ f(l, t)+(n_A-l)C_{\max}^B+\sum\limits_{j=l+1}^{n_A}C_j^A(S_2) $$ (3) 满足其中为子集$S_1$中调度$l$个工件当最后一批工件的完工时间为$t$时的最小总完工时间.
在式(3)中, 集合$S_2$中工件最小总完工时间所对应的最优调度可利用文献[15]提出的求解问题的动态规划算法在$\rm O$$(n_A\log{n_A})$时间内获得.而最小总完工时间$f(l, t)$可以通过下面的动态规划求出.
算法DP2.
初始条件:
对于每个$l=1, 2, \cdots, n_A$对应在不同的最后一批完工时间$t$下, $t=p_l^A, \cdots, \sum_{j=1}^{l}p_j^A$有如下递归关系: , 如果满足$\max\{t, r\}+\max\{p_j^B\}\leq Q_B, $其中当前调度中最后一批的工件为$\{J_{h+1}^A, \cdots, J_l^A\}$, 目标函数的增加值为该批的总完工时间$(l-h)t$.
对于每个$l$, 对应在不同的$t$值下, 所有的值以及对应的调度均可在$(n_A^2\sum_{j=1}^{n_A}p_j^A)$时间内找到.
综上, 针对不同的$l$以及对应不同的$t$值, 在所有得到的$f(l, t)$中, 找到满足条件$C_{\max}^B=\max\{t, r\}+\max\{p_j^B\}\leq Q_B$, 同时总完工时间最小的所对应的调度即为问题的最优调度.
定理3. 问题能够在$(n_A^2\sum_{j=1}^{n_A}p_j^A+n_B)$时间内求得最优解.
定理3的证明类似于定理2的证明, 这里不再详细赘述.
2) $r^A=r, r^B=0$
如果问题存在可行调度, 那么有如下三种情况:
a) 如果$\max\{p_j^B\}\leq r$, 那么在最优调度中集合$J^B$的所有工件从零时刻开始组成一批生产加工, 集合$J^A$的所有工件从$r$时刻开始利用文献[15]中关于求解问题的动态规划算法在$(n_A\log{n_A})$时间内求得最优解.
b) 如果$r<\max\{p_j^B\}\leq Q_B-r-t$, 其中, 由性质3可知, 问题仍具有最优调度形式, 其中集合$S_1$与$S_2$中工件对应的调度与上面时情况相同.而组合后调度形式的最优调度对应的最小化总完工时间值为
$$ \begin{align}f(l, t)\, &+(t+\max\{p_j^B\})(n_A-l)+\nonumber\\&\quad \sum\limits_{j=l+1}^{n_A}C_j^A(S_2)+n_Ar\end{align} $$ (4) 其中, $0< t\leq \sum_{j=1}^{n_A}p_j^A$, $r+t+\max\{p_j^B\}\leq Q_B.$
因此, 该情况能够在$(n_A^2\sum_{j=1}^{n_A}p_j^A+n_B)$时间内求得问题的最优解.
c) 如果$\max\{p_j^B\}\geq Q_B-r$, 那么在最优调度中集合$J^B$的所有工件从零时刻开始组成一批生产加工, 集合$J^A$的所有工件从$\max\{p_j^B\}$时刻开始利用文献[15]中关于求解问题的动态规划算法在$(n_A\log{n_A})$时间内求得最优解.
3. 批处理机能力有界
本节只考虑批处理机能力有界的情形下, 目标函数为最小化集合$J^A$工件的最大完工时间使得集合$J^B$工件的最大完工时间不超过给定上界的复杂性.针对两个工件集各自共同释放时间$r^A$与$r^B$的大小关系, 分别证明了两种情况下问题均为NP—难问题, 同时针对这两种情况分别设计了伪多项式时间算法进行求解.
1) $r^A=0, r^B=r$
定理4. 问题$1|p-batch, r^A=0, r^B=r, b<n|C_{\max}^A: C_{\max}^B\leq Q_B$是一般意义NP-难的.
证明. 我们将通过NP-难的划分问题归约来证明问题的NP-难性.划分问题(Partition problem)定义如下:
给定$m$个正整数$a_1, a_2, \cdots, a_m$, 并且满足$\sum_{j=1}^ma_j=2H$, 是否存在一个划分将下标集合分成两个不相交的子集$I_1$和$I\setminus I_1$, 使得$\sum_{j\in I_1}a_j=\sum_{j\in I\setminus I_1}a_j=H$?
给定划分问题的一个实例, 构造问题的判定问题的一个实例如下:
$$ n_B=1, r^B=r=H, p_1^B=H, Q_B=2H; $$ 批处理机一批的能力为$b=2;$
$n_A=2m, r^A=0, p_j^A=p_{j+m}^A=a_j, j=1, 2, \cdots, m;$
集合$J^A$目标的阈值为$Q_A=3H.$
接下来证明对于构造的问题的实例, 当且仅当划分问题有解时, 能够找到一个调度满足$C_{\max}^A\leq Q_A, C_{\max}^B\leq Q_B$.
$\Longrightarrow$如果划分问题有解, 即存在子集$I_1\subset I, $使得$\sum_{j\in I_1}a_j=\sum_{j\in I\setminus I_1}a_j=H$成立.对于上面问题构造的实例, 能够找到一个调度, 满足, 调度如下:工件$J_1^B$在$r^B=H$时刻开始调度, 具有相同加工时间的工件$J_j^A$与$J_{j+m}^A$组成一批加工, 即批$B_j=\{J_j^A, J_{j+m}^A\}$, $j\in {I}$, 其中对应下标的批从0时刻开始加工, 下标的批从$2H$时刻开始加工.容易验证.
$\Longleftarrow$如果对于问题构造的实例存在一个调度满足那么容易证明集合$J^B$唯一的工件$J_1^B$一定在$r^B=H$时刻开始调度.此外, 由于$\sum_{j=1}^{2m}p_j^A/b=2H, $所以调度从0到$3H$时刻之间没有空闲时间, 集合$J^A$工件构成的每一批都是满批, 并且每一批的两个工件一定具有相同的加工时间.记批, $j\in {I}$, 因此在$J_1^B$之前加工的所有批的加工时间和为, 之后加工的所有批的加工时间和为.因此划分问题有解.
下面给出求解问题的两个最优解性质.
性质4. 对于问题$1|p-batch, r^A=0, r^B=r, b<n|C_{\max}^A:C_{\max}^B\leq Q_B$, 如果存在一个最优调度, 那么集合$J^B$中所有工件在时刻$r$或者$r$之后连续生产加工, 并且加工批满足满批最大加工时间(Full batch largest processing time, FBLPT)规则.
证明. 由于集合$J^B$中所有工件的释放时间为$r$, 所以集合$J^B$中工件只能在时刻$r$或者$r$之后加工生产.在一个可行调度中, 将工件交换位置使得集合$J^B$中除最后一个工件外其他的工件向右移动到集合$J^B$中最后一个工件前与之连续加工, 再结合文献[15]中提出的求解问题$1|p-batch, b<n|C_{\max}$的调度方法, 得到的调度中集合$J^B$的工件最大完工时间不会增加, 同时集合$J^A$的每个工件的完工时间也不会增加, 进而最大完工时间不会增加.
设$X_B$为集合$J^B$工件按照FBLPT规则连续加工形成的集合.
性质5. 对于问题$1|p-batch, r^A=0, r^B=r, b<n|C_{\max}^A:C_{\max}^B\leq Q_B$, 如果存在一个最优调度, 那么集合$J^A$中所有工件可以按照FBLPT规则产生所有加工批.
证明. 通过工件交换与工件转移, 能够证明性质的结论.
由性质4和5, 设集合$J^A$与$J^B$中的工件分别按照FBLPT规则获得所有加工批, 所需时间为$\rm O$$(n\log n)$, 设批总长度为$T_X$, $X\in\{A, B\}$, 即$T_X=\sum_{i=0}^{[\frac{n_X}{b}]}p_{ib+1}^X$, 其中$[x]$表示不大于$x$的最大整数.下面针对问题提出如下算法进行求解.
算法3.
步骤1. 如果$\max\{T_A, r\}+T_B\leq Q_B$, 那么在最优调度中从0时刻开始按照FBLPT规则连续加工集合$J^A$的工件, 从$\max\{T_A, r\}$时刻开始按照FBLPT规则连续加工集合$J^B$的工件.如果$\max\{T_A, r\}+T_B>Q_B$, 那么转到步骤2.
步骤2. 如果$T_A\leq r$, 那么问题没有解.如果$T_A>r$, 那么问题的最优调度具有形式$(S_1, X_B, S_2)$, 其中$S_1$与$S_2$分别为在$X_B$前后加工生产的集合$J^A$工件的子集合, $S_1$可能为空集, 而$S_2$一定不是空集.针对这一情况, 设计如下伪多项式时间动态规划算法对问题进行求解.
算法DP3.
由性质5, 我们可以将集合$J^A$中所有工件按照FBLPT规则产生的每一个批看作一个工件.因此, 此时关于集合$J^A$工件的批生产调度问题可以转化为单机生产调度问题, 即批处理机的能力为$b=1$.假设集合$J^A$的所有工件按照加工时间不增的顺序排列如下: .定义$f(s)$为调度$n_A$个集合$J^A$的工件与全部$J^B$工件后集合$J^A$工件最大完工时间的最小值, 其中$s$是$X_B$的开始加工时间, 满足$r\leq s< r+P^A_{\max}$, 其中, $P^A_{\max}=\max\{p^A_j\}$, 因为在集合$S_1$中至多一个工件在$r$之后加工完.对于一个给定的$s$, 为了求出$f(s)$的最小值, 进一步定义为调度部分工件时集合$J^A$工件最大完工时间的最小值, 其中$t$是集合$S_1$中最后一个工件的完工时间, $t\leq s$.
定义初始条件为
$$ F(0,t)=\left\{ \begin{array}{*{35}{l}} s+{{T}_{B}}, & 若\ \ t=0 \\ +\infty , & \text{ }其他 \\ \end{array} \right. $$ 为了获得$F(h, t)$的最优值, 我们列举工件$J_h^A$的可能加工位置, 即工件$J_h^A$可能是集合$S_1$中最后一个加工的工件, 也可能是集合$S_2$中最后一个加工的工件, 于是有下面的递归关系:
$$ F(h,t)=\min \left\{ \begin{array}{*{35}{l}} F\left( h-1,t-p_{h}^{A} \right),若J_{h}^{A}\in {{S}_{1}} \\ F(h-1,t)+p_{h}^{A},若J_{h}^{A}\in {{S}_{2}} \\ \end{array} \right. $$ 因此, 对于$X_B$的每个开始加工时间$s$, $r\leq s<r+P^A_{\max}$, $f(s)$的最小值能够获得, 具有如下形式:
$f(s)=\min\{F(n_A, t): t\leq s\}$
进而, 问题的最优解值为$\min\{f(s): r\leq s < r+P^A_{\max}\}.$
定理5. 算法3可以找到问题的最优调度, 其中算法DP3的时间复杂度为$\rm O$$(n_A(r+P_{\max}^A)^2)$, 这里$P_{\max}^A=\max\{p_j^A\}$.
证明. 在算法3中, 如果问题存在最优解, 那么当时, 很显然利用性质4和5在最优解中从0时刻开始按照FBLPT规则连续加工集合$J^A$中工件, 从$\max\{T_A, r\}$时刻开始按照FBLPT规则连续加工集合$J^B$工件; 当$T_A+T_B> Q_B$时, 具有最优调度形式$(S_1, X_B, S_2)$.由性质5可知, 此时可以将关于集合$J^A$工件的批生产调度看成单机生产调度问题.对于一个给定的$X_B$的开始加工时间$s$, 工件$J_h^A$的完工时间有两种情况: a)当$J_h^A$在集合$S_1$中最后一个加工时, ; b)当$J_h^A$在集合$S_2$中最后一个加工时, .最后对于每个$s$所获得的集合$J^A$全部工件的最大完工时间最小值, 再求$\min\{f(s)\}$即为问题的最优解.又由于, 所以$s$的大小界限为$\rm O$$(r+P_{\max}^A)$.另外$0\leq h\leq n_A$, $t$是集合$S_1$中最后一个工件的完工时间, 满足$t\leq s$.因此, 算法DP3的时间复杂度为$(n_A(r+P_{\max}^A)^2)$.
2) $r^A=r, r^B=0$
定理6. 问题$1|p-batch, r^A=r, r^B=0, b<n|C_{\max}^A: C_{\max}^B\leq Q_B$是一般意义NP—难的.
证明. 类似于定理4的证明, 通过NP—难的划分问题归约来证明该问题的NP—难性.构造问题的判定问题的一个实例如下:
$n_B=2m, r^B=0, p_j^B=p_{j+m}^B=a_j, j=1, 2, \cdots, m, Q_B=3H;$
批处理机一批的能力为$b=2;$
$n_A=1, r^A=r=H, p_1^A=H;$
集合$J^A$目标的阈值为$Q_A=2H$.
在此我们忽略详细的证明过程.
针对问题, 首先设计一个动态规划算法计算出集合$J^B$所有工件最大完工时间的最小值, 然后在所有这些最小值中找到满足集合$J^B$目标函数约束条件下集合$J^A$工件的最小开始加工时间.类似于性质4的证明, 提出如下的最优解性质:
性质6. 对于问题$1|p-batch, r^A=r, r^B=0, b<n|C_{\max}^A:C_{\max}^B\leq Q_B$, 如果存在一个最优调度, 那么集合$J^A$中所有工件在时刻$r$或者$r$之后连续生产加工, 并且加工批满足FBLPT规则.
设$X_A$为集合$J^A$工件按照FBLPT规则连续加工形成的集合, 类似于性质5有下面的最优解性质:
性质7. 对于问题, 如果存在一个最优调度, 那么集合$J^B$中所有工件可以按照FBLPT规则产生所有加工批.
类似于情况$r^A=0, r^B=r$, 设$T_X$, 为集合$J^X$所有工件按照FBLPT规则获得所有加工批的批总长度.在问题中, 假设$r<T_B<Q_B$; 否则, 当$T_B\leq r$或$T_B=Q_B$时, 如果存在一个最优调度, 那么可以将集合$J^B$所有工件从零时刻开始按照FBLPT规则连续加工生产, 集合$J^A$所有工件对应在$r$或$Q_B$时刻按照FBLPT规则连续加工生产; 当$T_B>Q_B$时, 问题没有解.因此, 问题具有调度形式, 其中$S_1$与$S_2$分别为在$X_A$前后加工生产的集合$J^B$工件的子集合, $S_1$可能为空集, 而$S_2$一定不是空集.
根据以上的分析, 首先给出如下动态规划算法求出问题中集合$J^B$所有工件最大完工时间的最小值.
算法DP4.
由性质7, 我们可以将集合$J^B$中所有工件按照FBLPT规则产生的每一个批看作一个工件.因此, 此时关于集合$J^B$工件的批生产调度问题可以转化为单机生产调度问题, 即批处理机的能力为$b=1$.假设集合$J^B$的所有工件按照加工时间不增的顺序排列如下: .定义$f(s)$为调度$n_B$个集合$J^B$工件与全部集合$J^A$工件后集合$J^B$工件最大完工时间的最小值, 其中$s$是$X_A$的开始加工时间, 满足$r\leq s< r+ P^B_{\max}$.对于一个给定的$s$, 为了求出$f(s)$的最小值, 进一步定义为调度部分工件时集合$J^B$工件最大完工时间的最小值, 其中$t$是$S_1$中最后一个工件的完工时间, $t\leq s$.
定义初始条件为
$$ F(0,t)=\left\{ \begin{array}{*{35}{l}} s+{{T}_{A}}, & 若\ \ t=0 \\ +\infty , & \text{ }其他 \\ \end{array} \right. $$ 为了获得$F(k, t)$的最优值, 同样列举工件$J_k^B$的所有可能加工位置, 即工件$J_k^B$可能是集合$S_1$中最后一个加工的工件, 也可能是集合$S_2$中最后一个加工的工件, 于是有下面的递归关系:
$$ F(k,t)=\min \left\{ \begin{array}{*{35}{l}} F\left( k-1,t-p_{k}^{B} \right),若J_{k}^{B}\in {{S}_{1}} \\ F(k-1,t)+p_{k}^{B},若J_{k}^{B}\in {{S}_{2}} \\ \end{array} \right. $$ 因此, 对于$X_A$的每个开始加工时间$s$, $r\leq s<r+P^B_{\max}$, $f(s)$的最小值能够获得, 具有如下形式:
$f(s)=\min\{F(n_B, t): t\leq s\}$
为了求出满足条件下集合$J^A$工件最大完工时间的最小值, 我们在上面得到的所有$f(s)$中找到满足条件$f(s)\leq Q_B$的最小的$s$, 该调度即为问题的最优调度.
定理7. 算法DP4可以在$(n_B(r+P_{\max}^B)^2)$时间内找到问题的最优调度, 其中$P_{\max}^B=\max\{p_j^B\}$.
证明. 算法DP4的最优性证明类似于定理5中最优性的证明.由于$r\leq s< r+P^B_{\max}$, 所以$s$的大小界限为$(r+P_{\max}^B)$.另外$0\leq k\leq n_B$, $t$是集合$S_1$中最后一个工件的最大完工时间, 满足$t\leq s$.因此, 算法DP4的时间复杂度为$\rm O$$(n_B(r+P_{\max}^B)^2)$.
4. 结论
本文研究了带有两类释放时间的两个工件集在一台批处理机上竞争生产加工的有约束优化调度问题.针对两类释放时间的大小, 分别考虑了批无界与批有界情况下一些问题的时间复杂性.当批无界时, 在满足一个工件集最大完工时间不超过一个给定上界的条件下, 分别针对最小化另一个工件集的最大完工时间、最大延迟以及总完工时间问题提出了最优解性质, 设计了多项式或伪多项式时间的最优求解算法.当批有界时, 对于最小化一个工件集的最大完工时间使得另一个工件集最大完工时间不超过一个给定上界问题, 运用复杂性证明出问题为一般意义NP—难问题, 同时给出了伪多项式时间动态规划算法进行求解.批处理机上工件带有两类释放时间的两个工件集竞争调度问题的研究, 不仅为实际工业生产提高了机器生产效率、降低能耗、满足不同顾客需求, 也为多个工件集竞争调度问题的研究奠定了理论基础.未来可以进一步研究此类问题中NP—难问题的启发式算法, 并作出算法的性能分析, 也可以对问题的其他目标函数进行研究.
-
表 1 ResNet-50结构
Table 1 The structure of ResNet-50
Layer name Layers Output size Conv1 7 $\times$ 7, 64, Stride 2 112 $\times$ 112 Conv2-x1 3 $\times$ 3 Max pool, Stride 2 56 $\times$ 56 Conv2-x2 $\left[\begin{array}{c} 1 \times 1, 64\\ 3 \times 3, 64 \\ 1 \times 1, 256\end{array}\right] \times 3$ 56 $\times$ 56 Conv3-x $\left[\begin{array}{c} 1 \times 1, 128 \\ 3 \times 3, 128 \\ 1 \times 1, 512\end{array}\right] \times 4$ 28 $\times$ 28 Conv4-x $\left[\begin{array}{c} 1 \times 1, 256 \\ 3 \times 3, 256 \\ 1 \times 1, 1 024 \end{array}\right] \times 6$ 14 $\times$ 14 Conv5-x $\left[\begin{array}{c} 1 \times 1, 512 \\ 3 \times 3, 512 \\ 1 \times 1, 2 048 \end{array}\right] \times 3$ 7 $\times$ 7 Global average pool 1 $\times$ 1 Fc, Relu, Dropout, Softmax 1 $\times$ 1 
下载: 导出CSV
表 2 不同像素块大小的对比(%)
Table 2 Comparison of different patch sizes (%)
S-1 S-5 S-10 H-2 H-3 mAP 64尺度 87.8 94.7 97.0 57.3 36.7 76.5 256尺度 $\textbf{95.0}$ $\textbf{98.4}$ $\textbf{99.3}$ $\textbf{70.3}$ $\textbf{49.5}$ $\textbf{84.7}$
下载: 导出CSV
表 3 不同特征层的对比(%)
Table 3 Comparison of different feature layers (%)
S-1 S-5 S-10 H-2 H-3 mAP 全局池化层 $\textbf{95.4}$ 97.9 98.5 63.1 41.2 79.7 全连接层 95.0 $\textbf{98.4}$ $\textbf{99.3}$ $\textbf{70.3}$ $\textbf{49.5}$ $\textbf{84.7}$
下载: 导出CSV
表 4 特征数目的对比(%)
Table 4 Comparison of feature numbers (%)
S-1 S-5 S-10 H-2 H-3 mAP 128 95.2 $\textbf{98.7}$ 99.0 70.1 48.6 84.3 512 95.0 98.4 $\textbf{99.3}$ $\textbf{70.3}$ $\textbf{49.5}$ $\textbf{84.7}$ 1 024 95.0 98.4 99.0 70.0 48.8 84.1 2 048 $\textbf{96.0}$ 98.4 98.6 67.1 45.8 83.0
下载: 导出CSV
表 5 PCA白化的评估(%)
Table 5 Evaluation of PCA$\_$Whitening (%)
S-1 S-5 S-10 H-2 H-3 mAP 无PCA白化 88.9 97.1 98.0 63.9 47.6 82.1 有PCA白化 $\textbf{95.0}$ $\textbf{98.4}$ $\textbf{99.3}$ $\textbf{70.3}$ $\textbf{49.5}$ $\textbf{84.7}$
下载: 导出CSV
表 6 与其他模型的对比(%)
Table 6 Comparison with other models (%)
S-1 S-5 S-10 H-2 H-3 mAP CS-UMD-a[3] 95.1 98.6 99.1 19.6 7.1 N/A CS-UMD-b[3] 95.0 98.6 99.2 20.2 8.4 N/A HIT-ICG[3] 94.8 98.0 98.3 63.2 36.5 N/A TEBESSA-a[3] 90.3 96.7 98.3 58.2 33.2 N/A TEBESSA-b[3] 93.4 97.8 98.5 62.6 36.5 N/A Christlein[11] 97.1 98.8 99.1 42.8 23.8 67.7 Wu[9] 95.6 98.6 99.1 63.8 36.5 N/A Nicolaou[14] $\textbf{97.2}$ $\textbf{98.9}$ 99.2 52.9 29.2 N/A Fiel[8] 88.5 96.0 98.3 40.5 15.8 N/A Christlein[24] 86.8 N/A N/A N/A N/A 78.9 DLS-CNN 95.0 98.4 $\textbf{99.3}$ $\textbf{70.3}$ $\textbf{49.5}$ $\textbf{84.7}$
下载: 导出CSV
-
[1] Fiel S, Kleber F, Diem M. ICDAR2017 Competition on Historical Document Writer Identification (Historical-WI). In: Proceedings of the 14th International Conference on Document Analysis and Recognition. Kyoto, Japan: IEEE, 2018. 1377-1382 [2] Asi A, Abdalhaleem A, Fecker D. On writer identification for Arabic historical manuscripts. International Journal on Document Analysis and Recognition, 2017, 2017(3-4): 1-15 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=a2cace6f868ded2b41dc027e8943b487 [3] Louloudis G, Gatos B, Stamatopoulos N. ICDAR 2013 Competition on Writer Identification. In: Proceedings of the 12th International Conference on Document Analysis and Recognition. Washington, DC, USA: IEEE, 2013. 1397-1401 [4] Cloppet F, Eglin V, Kieu V C. ICFHR2016 Competition on the Classification of Medieval Handwritings in Latin Script. In: Proceedings of the 15th International Conference on Frontiers in Handwriting Recognition. Shenzhen, China: IEEE, 2017. 1371-1376 [5] Chawki D, Somaya A M, Imran S, Abdeljalil G, He Sheng. ICFHR 2018 Competition on Multi-Script Writer Identification. In: Proceedings of the 16th International Conference on Frontiers in Handwriting Recognition. Niagara Falls, USA: IEEE, 2018. 506-510 [6] Helli B, Moghaddam M E. A text-independent Persian writer identification based on feature relation graph (FRG). Pattern Recognition, 2010, 44(6): 229-240 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=7409e0794b32b08068f2e2eda9e786c8 [7] Bertolini D, Oliveira L S, Justino E. Texture-based descriptors for writer identification and verification. Expert Systems with Applications, 2013, 40(6): 2069-2080 doi: 10.1016/j.eswa.2012.10.016 [8] Fiel S, Sablatnig R. Writer Identification and Retrieval Using a Convolutional Neural Network. In: Proceedings of the 16th International Conference on Computer Analysis of Images and Patterns. Springer International Publishing, 2015. 26-37 [9] Wu Xiang-Qian, Tang You-Bao, Wei Bu. Offline Text-Independent Writer Identification Based on Scale Invariant Feature Transform. Information Forensics and Security, 2014, 9(3): 526-536 doi: 10.1109/TIFS.2014.2301274 [10] Xing Lin-Jie, Qiao Yu. DeepWriter: A Multi-Stream Deep CNN for Text-independent Writer Identification. In: Proceedings of the 15th International Conference on Frontiers in Handwriting Recognition. Shenzhen, China: IEEE, 2017. 584-589 [11] Christlein V, Bernecker D, Honig F. Writer Identification Using GMM Supervectors and Exemplar-SVMs. Pattern Recognition, 2017, 63: 258-267 doi: 10.1016/j.patcog.2016.10.005 [12] Christlein V, Gropp M, Fiel S, Maier A. Unsupervised Feature Learning for Writer Identification and Writer Retrieval. arXiv preprint arXiv: 1705.09369, 2017 [13] Tang You-Bao, Wu Xiang-Qian. Text-Independent Writer Identification via CNN Features and Joint Bayesian. In: Proceedings of the 15th International Conference on Frontiers in Handwriting Recognition. Shenzhen, China: IEEE, 2017. 556-571 [14] Nicolaou A, Bagdanov A D, Liwicki M. Sparse radial sampling LBP for writer identification. In: Proceedings of the 13th International Conference on Document Analysis and Recognition. Tunis, Tunisia: IEEE, 2015. 716-720 [15] Chen Shi-Ming, Wang Yi-Song, Lin Chin-Teng, Ding Wei-Ping, Cao Ze-Hong. Semi-supervised Feature Learning For Improving Writer Identification. arXiv preprint arXiv: 1807.05490, 2018 [16] 李昕, 丁晓青, 彭良瑞.一种基于微结构特征的多文种文本无关笔迹鉴别方法.自动化学报, 2009, 35(9): 1199-1208 doi: 10.3724/SP.J.1004.2009.01199Li Xin, Ding Xiao-Qing, Peng Liang-Rui. Writer identification based on improved microstructure features. Acta Automatica Sinica, 2009, 35(9): 1199-1208 doi: 10.3724/SP.J.1004.2009.01199 [17] 邹杰, 孙宝林, 於俊.基于笔画特征的在线笔迹匹配算法.自动化学报, 2016, 42(11): 1744-1757 doi: 10.16383/j.aas.2016.c150563Zou Jie, Sun Bao-Lin, Yu Jun. Online handwriting matching algorithm based on stroke features. Acta Automatica Sinica, 2016, 42(11): 1744-1757 doi: 10.16383/j.aas.2016.c150563 [18] Khan F A, Tahir M A, Khelifi F. Novel geometric features for off-line writer identification. Pattern Analysis and Applications, 2016, 19(3): 699-708 doi: 10.1007/s10044-014-0438-y [19] Bertolini D, Oliveira L S, Sabourin R. DeepWriter: Multi-script writer identification using dissimilarity. In: Proceedings of the 23rd International Conference on Pattern Recognition. Cancun, Mexico: IEEE, 2017. 3025-3030 [20] Shaus A, Turkel E. Writer Identification in Modern and Historical Documents via Binary Pixel Patterns, Kolmogorov-Smirnov Test and Fisher$'$s Method. Journal of Imaging Science and Technology, 2017, 61(1): 104041-104049 doi: 10.2352/J.ImagingSci.Technol.2017.61.1.010404 [21] He S, Schomaker L. Writer identification using curvature-free features. Pattern Recognition, 2017, 63: 451-446 doi: 10.1016/j.patcog.2016.09.044 [22] Khan F A, Tahir M A, Khelifi F. Robust off-line text independent writer identification using bagged discrete cosine transform features. Expert Systems with Applications, 2017, 71(C): 404-415 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=4bd769b41a47a54429c9a8335ef2476c [23] Bulacu M, Schomaker L. Text-Independent Writer Identification and Verification Using Textural and Allographic Features. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2007, 29(4): 1-17 doi: 10.1109/TPAMI.2007.1020 [24] Christlein V, Maier A. Encoding CNN Activations for Writer Recognition. arXiv preprint arXiv: 1712.07923, 2017 [25] Louloudis G, Stamatopoulos N, Gatos B. ICDAR 2011 Writer Identification Contest. In: Proceedings of the 11th International Conference on Document Analysis and Recognition. Beijing, China: IEEE, 2011. 1475-1479 [26] Kleber F, Fiel S, Diem M, Sablatnig R. CVL-DataBase: An Off-Line Database for Writer Retrieval, Writer Identification and Word Spotting. In: Proceedings of the 12th International Conference on Document Analysis and Recognition. Washington DC, USA: IEEE, 2013. 560-564 [27] Diem M, Kleber F, Sablatnig R. Text Line Detection for Heterogeneous Documents. In: Proceedings of the 12th International Conference on Document Analysis and Recognition. In: Proceedings of International Conference on Document Analysis and Recognition. Washington DC, USA: IEEE, 2013. 743-747 [28] Marti U V, Bunke H. The IAM-database: an English sentence database for offline handwriting recognition. International Journal on Document Analysis and Recognition, 2002, 5(1): 39-46 [29] Liu Cheng-Lin, Yin Fei, Wang Da-Han, Wang Qiu-Feng. CASIA online and offline Chinese handwriting databases. In: Proceedings of the 11th International Conference on Document Analysis and Recognition. Beijing, China: IEEE, 2011. 37-41 [30] Arivazhagan M, Srinivasan H, Srihari S. A statistical approach to line segmentation in handwritten documents. Document Recognition and Retrieval XIV, 2007, 6500(T): 1-11 [31] Liu Ji-Ming, Tang Yuan-yan. Adaptive Image Segmentation with Distributed Behavior-based Agents. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1999, 21(6): 544-551 doi: 10.1109/34.771323 [32] You Xin-Ge, Peng Qin-Mu, Yuan Yuan, Cheung Yiu-Ming, Lei Jia-Jia. Segmentation of Retinal Blood Vessels Using the Radial Projection and Semi-supervised Approach. Pattern Recognition, 2011, 44(10-11): 2314-2324 doi: 10.1016/j.patcog.2011.01.007 [33] He Kai-Ming, Zhang Xiang-Yu, Ren Shao-Qing, Sun Jian. Deep residual learning for image recognition. In: Proceedings of the 2016 IEEE Conference on Computer Vision and Pattern Recognition. Las Vegas, NV, United States: IEEE, 2016. 770-778 [34] He Kai-Ming, Zhang Xiang-Yu, Ren Shao-Qing, Sun Jian. Identity mappings in deep residual networks. In: Proceedings of the 14th European Conference on Computer Vision. Amsterdam, Netherlands: Springer International Publishing, 2016. 630-645 [35] Christlein V, Bernecker D, Angelopoulou E. Writer identification using VLAD encoded contour-Zernike moments. In: Proceedings of the 13th International Conference on Document Analysis and Recognition. Tunis, Tunisia: IEEE, 2015. 906-910 [36] Spyromitros-Xioufis E, Papadopoulos S, Kompatsiaris I Y. A Comprehensive Study Over VLAD and Product Quantization in Large-Scale Image Retrieval. IEEE Transactions on Multimedia, 2014, 16(6): 1713-1728 doi: 10.1109/TMM.2014.2329648 [37] Fiel S, Sablatnig R. Writer Identification and Writer Retrieval Using the Fisher Vector on Visual Vocabularies. In: Proceedings of the 12th International Conference on Document Analysis and Recognition. Washington DC, USA: IEEE, 2013. 545-549 [38] Christlein V, Bernecker D, Maier A. Offline Writer Identification Using Convolutional Neural Network Activation Features. In: Proceedings of the 37th German Conference on Pattern Recognition. Aachen, Germany: Springer International Publishing, 2015. 540-552 -
下载:
计量
- 文章访问数: 2153
- HTML全文浏览量: 788
- PDF下载量: 205
- 被引次数: 0
