英语原文共 7 页，剩余内容已隐藏，支付完成后下载完整资料
用于读取一维条形码的贝叶斯算法
作者：恩德·泰克史密斯 - 凯特韦尔眼科研究所
詹姆斯·科布兰史密斯 - 凯特韦尔眼科研究所
摘要：
一维条形码是一种普遍存在的标签技术，在美国大约99％包装商品用诸如UPC之类的符号标示，让消费者能够很方便使用条形码阅读便携式摄像机（例如移动电话），但质量有限使得分辨这些照相机拍摄的图像难以准确地读取条形码。 我们用一维条形码的贝叶斯框架模拟条形码的形状和外观，允许几何失真和图像噪声，且冗余信息包含在奇偶校验位中。 这个框架的一个重要特点是它不需要在图像中检测每个条形码边缘。 实验是在公开的条形码图像数据集上探索可读和比较的图像范围并展现出我们的算法的优势。
1、介绍
一维条码是作为包装标签开发的可以通过激光扫描仪快速准确地读取。它已经变得无所不在，在美国，像UPC这样的符号用于标签所有包装商品的约99％ [1]。 系统需要阅读由便携式摄像机拍摄的一维条形码（如在手机上），但是一维模式往往很难解决由于运动模糊和相机无法聚焦的问题。因此各种二维条形码被设计成更适合于相机捕获像素 [2，3]，但在未来几年一维条形码将仍然是大多数包装的主要类型的标签产品。
我们简要介绍一下，已经对算法进行了各种研究阅读一维条码。过去大多数的工作已经处理了扫描线数据（通常通过激光扫描仪被采集），使用波形分析，去模糊和其他信号处理技术来检测边缘[4，5，6]。 [7]中的方法与我们使用类似的HMM建模，但其中它假定每一个在扫描线数据中检测到条形码的边缘，是我们在算法中删除的一个假设。 （TheHMM方法将边缘过渡状态分配给整个扫描线中观察到的边缘序列，而我们的方法是一个使用隐藏变量的可变形模板以对每个条形码边缘的位置进行建模，无论那些边缘是否可见的。）另一个区别是我们的方法联合执行解码和纠错。还有从图像读取一维条形码的信息而不是激光扫描仪数据，其中一些使用二维分析如霍夫变换检测边缘[8]。
最近的一些研究令人印象深刻的是准确性[9,10]，但是测试算法的图像数据集尚不可用（[10]指出数据将可用对公众而言，但写作时并非如此）。然而，我们强调条形码的可读性根据图像质量而有很大差异，在某些情况下（例如使用相机电话，有限的分辨率和焦点特写能力）使许多图像模糊不清。例如，在[9]中，条形码被拍摄以用那种模块（宽度为最窄）约4.5像素宽，这可能是相机电话实现最高的分辨率。因此，用于评估的图像至关重要，条形码读取算法可公开提供。
我们的原理是贝叶斯可变形模板用于阅读条形码的模型，由于不均匀的照明，几何和透视变形并丢失边缘和低分辨率导致图像噪声强大。我们将数据集在线发布供公众使用，并计划添加数据集让项目继续。
我们还没有解决凌乱的图像中的条形码的识别问题，但是有关于这个问题的工作[11，9]我们将来会借鉴。
2、贝叶斯模型
我们设计了一个贝叶斯变形模板[12]结合先前知识的条形码模型条形码几何，包括允许的配置有条件并允许几何扭曲，有证据基于强度梯度的边缘。我们的模型也是通过利用嵌入的校验和信息来加强条形码，这限制了编码数字，从而允许我们检测和纠正错误。在本文中，我们专注于一个特定的北美常用的符号系统UPC-A，但需要强调的是我们的方法将泛化直接向任何一维条形码图案。
2.1条码结构
UPC-A条形码（见图1）编码一串十二进制数字（每个数字是0到9的整数），其中最后一个数字是作为函数的校验位。条形码图案由条和白色间隙（我们将两者称为条）。有29条白和30条黑，总共N = 60边。边缘具有交替的极性，从左到右的极性的边（-1）i（其中i = 1，...，N）。每个边缘都有一个四个可能的宽度：Delta;，2Delta;，3Delta;或4Delta;，Delta;是模型或者条形码的基本宽度。
每个数值由四个条的序列编码（总宽度为7Delta;）。 除了十二位数的区域外，条形码中有三个“守卫”区域：开始区域（由白色条分隔的两个黑色条纹）左边，第六和第七数字之间的中间分隔区（由两个黑色条分隔开的三个白色条），以及右侧的结束区域（与起始区域相同的模式）。见图2用于说明这些区域的条形码总宽度为95Delta;。
条形码中的60个边缘分为两类，固定和可变。 固定边缘是相关联的带有保护带（也如图2所示），其位置独立于编码数字。 可变边是位置定义数位的数字区域中的边编码。
2.2 模型基础
在本文中，我们假设条形码已从图像中分段，我们知道大概方向，这允许我们构建几个扫描线横跨条形码。 我们首先描述一个单一的条形码从左到右切割的模型扫描线; 后来我们将把模型扩展到多个扫描线。 此外，在后面的章节中，我们将介绍基本的两个模型1和2。
扫描线定义了一个x坐标系，沿着扫描线的强度表示为I（x）。 边缘强度e（x）被定义为强度导数dI / dx。e（x）的局部最大值和最小值定义边缘位置在扫描线，以及第一个和最后一个观察到的边缘位置跨越整个条形码（宽度为95Delta;）用于估计Delta;用于扫描线。 我们把所有的信息都表示出来扫描线由S.
所有N = 60边的位置由一系列X =（x1，x2，...，xN）。 我们表示固定边在X中由Xf，并且可变边由Xv，我们可以写出X =（Xf，Xv）。
未知数字由序列D =（d1，d2，...，d12），其中diisin;{0,1， 。 。 ，9}。
基本模型P（X，D | S）可以被描述为一个像素（见图3）：
（1）
其中L（X，S）是对数似然项边缘位置位于扫描线的高梯度部分，而G（X，D）是强制空间的几何项给定数字序列的不同边缘之间的关系。
首先，我们描述更多的似然项L（X，S）详情。 它被定义为：
（2）
其中Li的精确形式在模型 1和模型2（见下一小节的细节）。 在这两种情况下它强制边缘xi必须具有的极性约束（-1）i,如果dI / dx（xi）有错，则Li（xi，S）=infin;,。
我们可以将L（X，S）重写为两个项，一个包含固定边缘，另一个包含可变边缘：
（3）
接下来我们描述几何先验项G（X，D）：
（4）
第一项，Gf（Xf），规定适当的间距在固定边缘之间：例如，我们预期x2-x1asymp;Delta;这个间隔距离表示为二次能量项（x1，x2）= beta;f（x2-x1-Delta;）2H（x2-x1），类似地所有其他边连续固定。H（x）是一个函数对于正值x和infin;，连续边缘排序的事实从左到右，而不是从右到左;beta;f是积极的不变。另外，由于每个数字区域包含宽度为7Delta;，我们被迫使用：（x4，x8）= beta;f（x8-x4-7Delta;）2H（x8-x4）,做第一个数字，并且其他数字类似。
第二项，Gv（Xf，Xv，D），改变可变边缘位置之间的适当间距编码的数值。每个数字值（0-9）对应到四个宽度的序列。从0到9，相关的宽度序列是：（3,2,1,1），（2,2,2,1），（2，1，2，2），（1,4,1,1），（1,1,2,3）（1，2，3，1），（1,1,1,4），（1，3,1,2），（1，2，1，3），（3,1,1,2）。这些间距由（x4，x5，d1）= beta;v（x5-x4-w1（d1））2H（x5-x4），其中w1（d1）是对应于数字d1的第一个宽度（v是正数）。
接下来的两个小节描述了这两个变体我们实施的模式。
2.3模型1
模型1是两个模型中更简单的。 在这个模型中，我们首先使e（x）= dI / dx归一化，使其重新缩放绝对值最大等于1。 然后我们提取边缘作为e（x）的局部最小值和最大值，并表示序列为Y =（y1，y2，...，yM）。yi是通过建模的值估计为亚像素精度e（x）的二次方。 该序列定义了该集合允许的边缘（Mge;N，意味着我们已经观察到的边缘至少与条形码中所需的边缘一样多），即允许的xi的值。 然后定义每个边缘数据作为Li（xi，S）=alpha;| e（xi）| H（e（xi）（ - 1）i），其需要xi具有正确的极性。
在模型1中，我们使用以下方法估计边缘位置。 首先我们使用维特比算法[13]计算固定边缘位置：
（5）
然后使用这个结果，再次使用维特比计算可变边缘位置：
（6）
我们估计了所有的边缘位置数字值。（模型2边缘化相反，它相对于模型1有自己的优点和缺点）
对任何给定数字的边际概率我们使用以下表达式：
（7）
RHS上的D表示di指定的值LHS，指定字符串i中要被估计的数字。Ei（X，D，S）包括L（X，S）中的所有项， G（X，D）其取决于定义di的边缘位置。如果使用多条扫描线，那么我们只需要平均超过每个扫描线到达的总体边际概率。
2.4模型2
模型2具有与模型1相同的结构。最重要的区别在于我们允许边缘位置X在像素点阵上假设任何值，而不是限制在e（x）= dI / dx的局部峰上。因为在嘈杂的图像中真正的位置边缘可能不与峰值相关联，即我们没有能够检测每个条形码边缘。我们在每个扫描线上定义像素量化，使得估计的基本宽度大约5像素，并使用线性值估计e（x）。
我们不再局限于边缘位置在dI / dx的峰值中，我们也使用二阶导数e2（x）= d2I / dx2寻找最大值或最小值附近的点（e（x）以相同的方式归一化）。然后我们定义边缘的可能性为Li（xi，S）=-gamma;log（| e（x）|（1-| e2（x）|）H（e（xi）（-1）i），其边缘强度为接近边缘幅度的峰值（由于e2（x）在局部最大值或最小值达到0）。（这里是积极的常数）再次，H（.）因子梯度xi具有正确的极性。
与模型1的第二个区别是模型2使用因子图置信传播（BP）[14]进行估计每个数字的边际概率，而不是估计最可能的边缘位置,然后估计基于这些位置的数字。模型2中的因素是通过指数函数定义。2.2,BP估计每个变量的边际概率在模型中，包括P（di | S）。
2.5使用校验
条形码数字序列中的数字不是独立的但是被约束遵循以下奇偶等式：
（8）
因此，前十一位数字是独立选择的，第十二位是选择满足的奇偶校验位。这种机制允许验证条形码读入。为了找到一致的最可能的数字序列与数据且满足奇偶校验约束，我们创建一个新的随机变量序列ci isin;{0，... ，9}其中i = 1，...，12，对应于运行奇偶校验数字。
（9）
显而易见：
（10）
这里我们使用边际概率P（di | S）（等式7）来定义ci变量的相关概率（我们在一个或多个地方省略条件扫描线简洁）。（例如，由于c1和c2共同确定d2的值，由P（d2 | S）确定P（c2 | c1））。由于序列c1，c2，...，c12形成a马可夫链，我们可以使用维特比（采取日志之后）转化为能量域）以找到最可能的序列的ci。此外，还使用多路维特比算法计算第二个最可能的序列，用于评估最高估计的置信度（见下一节）。
2.6型号选择
在我们的实验中，我们发现模型 1更适合于干净的图像，模型2更适合嘈杂的图像。我们还没有调查贝叶斯的可能性模型选择程序，而是设计了一个简单的算法来决定哪个模型适合给定条形码图像。
我们的算法如下。模型1首先运行使用一条扫描线，如果它太低，一个置信标准（如下所述）计算，则另一个扫描线是使用（总共15个扫描线）。如果一条或多条扫描线已被使用，然后每个的总体概率条形码数字通过简单的平均来计算扫描线。
如果使用模型1满足置信度标准该算法，否则我们继续运行模型2，再次从一条扫描线开始。需要更多的扫描线（最多可以15个扫描线，即不聚合多个扫描线或平均数字概率），以及置信度标准对任何扫描线都符合，那么算法就完成了，否则算法失败。
置信度标准评估数字序列比其他序列的可能性高。具体来说，只有两个置信度标准符合才能实现测试满意。在第一个测试中，前两位数字序列的比较来自校验和程序的估计。如果顶部序列的概率的比率被第二个最可能的序列划分的概率也是小，然后测试失败。（该测试评估的边际是对顶级解决方案的置信度）如果第一次测试成功，然后进行第二次测试。替代数字序列计算出每个数字被选择为最大化边际数字概率的方法校验和程序。如果替代数字序列不同，从最可能的序列选一个数字，第二个测试成功并且整体置信度符合标准。
3.实验结果
模型1和模型2在Matlab中
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[27886]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
