© 2013由Elsevier B.V.发布。由美国应用科学研究所负责选择和/或同行评审可在www.sciencedirect.com在线获取ScienceDirectAASRI Procedia 5（2013）156 - 1632013年AASRI并行和分布式计算与系统基于云计算的FastDTW算法与Map-reduce编程模型相结合的大型分布式阿拉伯笔迹识别系统Hamdi Hassena，b*，Maher KhemakhemaaMir@cl Lab，FSEGS University of Sfax BP 1088，3018 Sfax，TunisiabKSA Taibah大学Al-Ola文理学院计算机科学系摘要提出了一种基于并行FastDTW算法的分布式阿拉伯手写OCR系统。采用Hadoop、MapReduce和Cascading三种技术实现了FastDTW算法的并行化。实验部署在Amazon EC2 Elastic Map Reduce和Amazon Simple Storage Service（S3）上，使用从IFN/ENIT数据库构建的大型数据集。© 2013作者。由Elsevier B. V.在CC BY-NC-ND许可下开放获取。由美国应用科学研究所负责选择和/或同行评审关键词：大型OCR系统，快速DTW，MapReduce，云计算;1. 介绍今天，有许多基于不同方法和算法的OCR系统在使用中。所有流行的OCR系统都支持高精度和最高速度，特别是那些专用于打印字符和高质量文档的系统。不幸的是，这是不是特别是阿拉伯手写字符的情况*通讯作者。电话：+966-563598400 ;传真：+216 74 278777hhassen2006@yahoo.fr2212-6716 © 2013作者由Elsevier B. V.在CC BY-NC-ND许可下开放获取。美国应用科学研究所负责的选择和/或同行评审doi：10.1016/j.aasri.2013.10.072Hamdi Hassen和Maher Khemakhem / AASRI Procedia 5（2013）156157其中OCR系统限于识别用于某些特定目的的少量和很少的中等数量的文档。处理大量文档的OCR系统非常有限，并且不够强大，例如澳大利亚报纸数字化项目[1]，OCRGrid[2]，Kirtas[3]和OCRopus [4]。在几个阿拉伯手写OCR系统上进行的实验和评估表明并证实：一方面，欧几里德距离技术用于分类。然而，这种技术的鲁棒性较低，更脆弱[5]。在第二方面，动态时间扭曲（DTW）算法是执行此类任务的最佳技术之一[6]。DTW的主要问题是其响应时间缓慢，因为要实现巨大的计算量[7]。云计算技术等分布式系统为基于DTW算法的OCR系统的时间加速提供了可行的框架。云计算主要用于提供许多服务，例如基础设施（I）、平台（P）和软件（S）即服务。所有这些服务都可以作为基于注册的服务提供给消费者，采用按消费付费的模式[8]。本文组织如下：DTW算法，特别是FastDTW和使用它们在阿拉伯字符识别的概述，在第2节。Hadoop，MapReduce和级联模型在第3节中介绍。所提出的方法在第4节中解释。第5节介绍并讨论了实验和结果。最后给出了结论和未来的工作。2. 动态时间扭曲2.1. 动态时间规整算法动态时间规整（DTW）是一种旨在计算两个不同模式序列之间的相似性的技术，即使它们在时间或空间上没有对齐[9]。让n：是序列A的特征向量。m：是序列B的特征向量。A= a1， a2，a3，an（1）B= b1， b2，b3，中文（简体）D[n，m]：距离矩阵。Cell（i，j）表示序列A的第i个元素与序列B的第j个元素之间的距离（图1）。158Hamdi Hassen和Maher Khemakhem / AASRI Procedia 5（2013）156SMK时间序列AIsIsJS时代周刊B图1. DTW机制。为了找到A和B之间的最佳对齐，我们需要找到穿过网格的路径。P = p1这将最大限度地减少它们之间的距离。P称为翘曲函数。为了计算路径的长度，简单地说，我们只需将沿着该路径访问的所有单元格（三）（四）K d（ps）wsD（A，B）=s 1（五）wsS 1D（ps）：is和js之间的距离; w s > 0：加权系数。P0：A和B之间的最佳对齐路径：P0 = argp min（D（A，B））。（六）2.2. 快速DTWDTW算法的时间复杂度和空间复杂度都是指数级的。该模型仅适用于中小型数据集（3，000），并且时间序列通常很长[11]。FastDTW算法可以作为解决这一问题的一种方法。FastDTW基于多分辨率Hamdi Hassen和Maher Khemakhem / AASRI Procedia 5（2013）156159受多级图二分算法启发的方法[12]。2.3. 快速DTW阿拉伯笔迹识别系统阿拉伯手写体识别系统的FastDTW包括准备一个参考数据库，该数据库是由R训练的阿拉伯字母和数字在给定的手写体中组成，并由Ci表示，i = 1，2，我们的方法包括使用FastDTW模式算法对字符进行分类，以识别对模板库。因此，输入字符被分类为在所有R个字符中给出最佳时间对准p的最佳字符。该技术基于三个步骤：当未达到原始分辨率时，1)设置要识别的字符的分辨率，以便成为粗分辨率。2)DTW算法Pk = min {Pr}，其中1 = r = R3)重复分辨率加倍将路径投影到更精细的分辨率上，找到穿过投影区域的路径。3. MapReduce，Hadoop an Cascading：an overview.3.1. MapReduce技术MapReduce [13]是一种用于并行化问题的工具，这些问题使用不同的计算机（节点）（分布式架构）处理大型数据集，如集群或网格计算。Amazon Elastic MapReduce提供了分析大量数据的选项。这种优势是通过将计算工作分布在亚马逊云中运行的虚拟服务器集群中来提供的。所有集群都使用一个名为Hadoop的开源框架进行管理。3.2. HadoopHadoop [14]是一种用于处理大规模数据的分布式基础设施。该基础架构可用于单机。这种架构的真正力量在于能够使用数百或数千个节点，每个节点都有不同的处理器内核。Hadoop模型还用于在不同的机器上高效地共享大量工作。Hadoop通过管理大量数据的存储层和使用协调数据子集并行执行用户应用程序的运行层来实现这一点。3.3. 级联Cascading是一个用Java语言编写的框架，可以帮助典型的开发人员轻松快速地开发数据分析和数据管理系统，这些系统可以由各种计算环境部署和管理。该模型基于称为管道的数据流和称为过滤器的数据操作的隐喻。因此，级联API允许开发人员重新组合执行许多操作（如拆分、合并）的管道程序集。在对不同的数据记录应用操作时，160Hamdi Hassen和Maher Khemakhem / AASRI Procedia 5（2013）1564. 所提出的方法为了解决可以处理大量文档的OCR系统的问题，我们选择了云计算模式，该模式通过消除机构和组织管理巨大计算能力的必要性，有望大幅减少投资。在内存分配上采用了主从模型和SPMD（Single Process，Multiple Data）结构，并将其应用到FastDTW算法中作为并行化技术。分布式FastDTW方法包括在独立的处理器上运行单个程序的每个副本，Hadoup负责处理器之间的通信。要识别的大量文档最好将其分成小部分（D1，D2，D3FastDTW算法将通过每个节点的作业流来实现。Amazon Elastic MapReduce在不同的Amazon EC2实例上自动执行OCR应用程序的Hadoop程序。首先，应用映射函数，该函数包括将作业流中的大量文档细分为较小的进程，以便它们可以并行处理。其次，应用reduce函数，将处理后的数据合并到最终输出中（图2）。Amazon Simple Storage Service（S3）是第一手数据处理源，第二手数据输出目的地。问题数据解决方案数据工作节点n工作节点2地图减少工作节点1图2. MapReduce机制5. 实验研究5.1. 数据集为了检验所提出的想法，使用了具有16000页（370个字符/页）的语料库和由345个形状形成的参考数据库，所述345个形状表示从阿拉伯手写单词图像数据集IFN/ENIT[16]中随机选择的近似不同的阿拉伯字母。对于预处理图像，IFN/ENIT数据集已经标准化[16]。小波变换[17]被用作特征提取技术。5.2. 实验环境实验在本地Intel Core 2 Duo台式机上进行，其配置为：*2、2 GB RAM执行Windows XP操作系统，Cygwin [18]是运行Linux命令的shell。我们使用Java作为编程语言，并安装了JDK 1.6。Eclipse 3.4用于编程和构建我们的应用程序。100 MG bits/s是网络容量。基于云计算技术的最新发展[19]，Amazon Elastic Computing Cloud选择了我们的方法。为了验证分布式FastDTW在云技术中的正确功能，我们在Amazon Elastic Computing Cloud服务上创建了六个正在运行的作业流。我们使用三个标准Amazon EC2内核分配了100个内核。首先，第二，大Hamdi Hassen和Maher Khemakhem / AASRI Procedia 5（2013）156161实例7.5 GB内存，850 GB实例存储，64位平台，最后是超大型实例15 GB内存，1690 GB实例存储和64位平台。S3 [20]用于管理输入和输出数据。5.3. 结果和分析为 了 证 明 云 计 算 技 术 在 基 于 FastDTW 的 方 法 的 执 行 时 间 上 的 效 率 ， 我 们 在 Amazon ElasticMapReduce Cloud上创建了六个级联运行的作业流，并进行了两个实验，以比较DTW和FastDTW在Amazon Elastic Computing Cloud服务的三个实例中的加速比。下表说明了在不同实例中使用DTW和Fast DTW的执行时间表1. DTW和FastDTW时间执行例如批核心DTW（H）FastDTW（H）小250.5630.444实例500.3000.258亚马逊弹性750.2050.174计算1000.1500.123介质250.5000.421Amazon实例 500.2730.229弹性750.1910.160计算1000.1430.119大250.4500.364实例500.2570.216亚马逊弹性750.1800.157计算1000.1360.118在使用DTW和FastDTW的顺序模式（单个计算机）中的测试时间的平均持续时间分别约为9小时和8小时，在分布式模式和100台计算机中的平均测试时间分别为0.136小时和0.118小时。这些表明，对于上述两种算法，顺序模式每秒只允许识别18和21个字符。然而，图3和图4所示的不信任模式的结果特别是：加速因子是使用单个处理器的顺序执行时间与使用多个处理器的执行时间之比，它随着所使用的核心数量和不同的标准Amazon EC2内核而同时增加。如果我们将100个核心与Amazon Elastic Computing的大型实例一起使用，则执行时间将分别达到489秒和425秒，加速因子将分别达到DTW的66和FastDTW的68。这些结果是非常重要的，因为我们的分布式OCR模式可以识别超过1200和1400（字符/秒）的DTW和FastDTW分别。162Hamdi Hassen和Maher Khemakhem / AASRI Procedia 5（2013）156100小型实例加速比 500中型实例大型实例25 50 75 100数量的核100加速500小型实例中型实例大型实例25 50 75100数量的核图3.使用Amason弹性Mapreduce图4. 使用Amason弹性Mapreduce我们的模型有几个优点，因为云计算提供了几乎所有需要的工具，为了方便分配任何贪婪算法或应用程序，数据管理，任务调度， 主机失败， 促进沟通之间 机 并且因此一切对程序员/分析师/用户都是完全透明的。6. 结论和展望性能对所提出的模型的评价证实，Mapreduce，Hadoop 和级联技术提供了一个适当的平台，以加速阿拉伯手写识别过程。此外，与现有系统相比，这种平台允许构建更强大的OCR系统[21]因为它除了提供一些有用的工具和设施之外，还提供足够的计算和存储能力在未来的工作中，我们将研究如何在多云基础设施上部署OCR应用程序，以及如何通过集成（组合）一些强大的补充方法（例如HMM，SVM）。引用[1] 网址：h t tp：//www. nla.gov.au/[2] 可从以下网址获得：http://www.ocrgrid.org/[3] 可从以下网址获得：http://www.kirtas.com/[4] 可从以下网址获得：http://code.google.com/p/ocropus/[5] Y.Jun Weng和Z. Ying，Hamdi Hassen和Maher Khemakhem / AASRI Procedia 5（2013）156163November 2003[6] M. Khemakhem和A.贝尔吉斯A P2P Grid Architecture for Distributed Arabic OCR based on the DTWalgorithm，IJCA-ACTA press，V.31，N1，2009.[7] Maher Khemakhem，Abdelfettah Belghith基于互补方法组合的分布式草书OCR系统，施普林格章，2012年[8] Sushil Bhardwaj1，Leena Jain 1，Sandeep Jain 2云计算：基础设施即服务（IAAS）的研究，国际工程与信息技术杂志2002年，第2期，第100页。1 IJEIT 2010[9] Berndt D J，Clifford J.，Finding patterns in timeseries：a dynamic programming approach.知识发现和数据挖掘的进展，AAAI/MIT，1996，229[10] M. Khemakhem et al.，Reconnaissance de Caractères Imprimés par Comparaison Dynamique，Proc. AFCET，Antibes，Sept. 一九八七年[11] Stan Salvador和Philip Chan，“FastDTW：在线性时间和空间中实现精确的动态时间弯曲”，关于挖掘时间和顺序数据的研讨会，第10页。70-80，2004年。[12] Stan Salvador和Philip Chan，“FastDTW：在线性时间和空间中实现精确的动态时间弯曲”，关于挖掘时间和顺序数据的研讨会，第10页。2004年，第70至80次会议[13] 可从以下网址获得：http://aws.amazon.com/elasticmapreduce/[14] 可从以下网址获得：http://hadoop.apache.org/[15] 网址：http：www.cascading.org/[16] M. Pechwitz，S. S. Maddouri，V. Mrgner，N. Ellouze和H.阿米里手写阿拉伯语单词数据库。InProc. of CIFED 2002，pages 129[17] Hassen Hamdi，Maher Khemakhem，阿拉伯手写体字符不变特征的比较研究。（IJACSA）国际高级计算机科学与应用杂志，第2卷，第12期，2011年[18] 可从以下网址获得：http://www.cygwin.com/[19] R. Prodan和S. Ostermann，“基础设施即服务和Web托管云提供商的调查和分类”，Proc. Int'l Conf.Grid Computing，pp. 2009年1月至10日[20] 可从以下网址获得：http://aws.amazon.com/s3/[21] M.Khemakhem和A.贝尔吉斯Towards A Distributed Arabic OCR Based on the DTW Algorithm：Performance Analysis（基于DTW算法的分布式阿拉伯语OCR：性能分析）号62，2009年4月
我的内容管理
展开
