摘 要

信息技术的飞速发展推动着条形码技术的推广与普及，其中以快捷方便的识读、强大的存储能力著称的QR码的应用更是随处可见。本文提出了一种基于特征聚类的破损QR码定位算法，这个算法是通过将带有破损QR码的图像进行SIFT特征点提取之后，再利用K-means聚类算法对特征点进行聚类划分，判断候选区域后，再以聚类中心为起点按比例进行扩大搜索，初步定位出QR码；接着再利用QR码特有的模块深浅间隔比呈1：1：3：1：1型的定位标志图案完成破损QR码的精确定位；最后，对定位的QR码进行旋正剪切。本文通过基于特征聚类的初步定位方法与基于QR定位标志的精确定位方法的有机结合，基本实现了在背景图像比较简单，QR码区域在图像中所占比例适当的情况下，破损QR码图像的成功定位。所得结果对应用于多样场合背景下的破损QR码识别具有积极意义，也对信息传播速度加快，提高经济效益具有重要作用。

关键词：SIFT；K-means聚类；QR码；定位标志

Abstract

The rapid development of information technology has promoted the popularization and popularization of bar code technology. Among them, the application of the QR code, which is known for its fast and convenient reading and powerful storage capabilities, has been seen everywhere. This paper proposes a feature-based clustering algorithm for broken QR code location. This algorithm extracts SIFT feature points from the image with broken QR code, and then uses K-means clustering algorithm to cluster the feature points. After judging the candidate area, the expanded search is performed by using the cluster center as the starting point to initially locate the QR code; then the 1:1:3:1:1 type positioning mark of the module's unique module is used. The pattern finishes the accurate positioning of the broken QR code; finally, the positioned QR code is rotated and sheared. In this paper, the combination of the preliminary positioning method based on feature clustering and the precise positioning method based on QR positioning markers basically achieves the effect of breaking the QR code image when the background image is relatively simple and the proportion of the QR code area in the image is appropriate. The successful positioning. The obtained results have positive significance for the identification of broken QR codes used in various contexts, and also have an important role in speeding up information dissemination and improving economic efficiency.

Key Words：SIFT；K-means clustering；QR code；position detection patterns

目 录

摘 要 I

Abstract II

目 录 III

第1章 绪论 1

1.1 研究的目的及意义 1

1.2 QR码定位算法的研究现状 2

1.3 特征提取与聚类的概述 3

1.3.1 特征提取 3

1.3.2 聚类 4

1.4 本课题的主要研究内容 4

第2章 相关技术综述 5

2.1 QR码简介 5

2.2 SIFT算法基本原理 7

2.3 K-means算法基本原理 9

第3章 基于特征聚类的破损QR码定位算法 11

3.1 定位算法的整体流程 11

3.2 图像预处理 12

3.2.1 灰度化 12

3.2.2 滤波 13

3.3 QR码的候选区域的初步定位算法 13

3.3.1 基于SIFT算法的图像特征点提取 13

3.3.2 基于K-means聚类算法的QR码初步定位 16

3.4 QR码的精确定位算法 18

3.5 实验结果及分析 20

3.5.1 QR码图像定位 23

3.5.2 精确定位的QR码图像旋正剪切 23

第4章 总结与展望 25

4.1 全文工作总结 25

4.2 研究工作展望 25

参考文献 27

致 谢 29

第1章 绪论

1.1 研究的目的及意义

在信息技术不断发展的今天，信息越来越丰富多样，信息的传递媒介也就显得 尤为重要。从最初用纸笔写信传递，到后来出现的各类电子媒介，信息传递的方式在科技的不断发展的推动下发生着巨大的变化。条码也就是在社会智能化、数字化发展的推动下应运而生的，并逐渐成为日常生活中必不可少的一部分。满街的大小广告上，网络购物电商的推送上，个人名片的信息获取，我们生活的方方面面都有条码的身影。从出行的票据到公交车乘车的识别付款，再从商品的信息储存到工厂的货物管理，条码无处不发挥着它的作用。

条码均由特定的连串符号构成，或是条形，或是块状，以存储特定的信息。起先，只有一维的条形码。虽然一维条码已经能完成部分商品、货物标注等任务，但由于存储的信息量有限，无法满足日益增长的需求，二维条形码便因此诞生了。具有二维存储空间的二维条形码，相较于一维条码，在信息存储量方面有着显著的提升。另外，二维条码不同之处还在于其可以脱离网络和数据库，直接通过扫描来进行信息读取。二维码制还具有一定的纠错能力，这同样是它的一大优势。随着智能手机的大范围普及，能通过智能手机轻松扫描识别的二维码广泛的应用在支付、认证、广告等各个方面。常见的二维码类型有PDF417、Code 16K、Data Matrix、Maxi Code、QR码等。而本文要研究的二维码则是1994年由日本Denso-Wave公司研发的矩阵式条形码。该码制比起其他二维码有辨别读取的速度快，信息的空间利用率高等多方面优势。QR码在其三个角上有三个寻象图形，便于识别设备快速定位到码的位置，并进行解码。

快捷方便的识读、强大的存储能力使得QR码很快就得到了大面积的推广，应用已随处可见。正因如此，其利用的情况也变得多种多样。除了大家常见的被张贴在各个店家的收款码，还有印于快递盒、包装袋上的商品信息码等等。各种细小状况的出现都可轻易地破坏这些QR码原有的模样，导致其一定程度上的扭曲、缺损、模糊、遮挡。处于各种不同的复杂环境的QR码让定位识别工作变得纷繁芜杂起来。与生产生活已息息相关的QR码，还有不够高效的QR码的识别使得各国研究人员纷纷投入到对QR码识别的研究之中。