《一種二維碼定位方法及系統》是深圳市華漢偉業科技有限公司於2016年9月27日申請的專利，該專利的公布號為CN106485183A，授權公布日為2017年3月8日，發明人是楊洋。
《一種二維碼定位方法及系統》對輸入的圖像先利用二維碼數據區的邊緣信息對圖像數據進行預篩選，確定可能包含二維碼的圖像區域作為候選區域，對每個候選區域，利用待定位二維碼的定點陣圖形確定二維碼外邊界的大致位置，從而獲得二維碼的粗略定位，最後根據二維碼外邊界的大致位置確定出二維碼的精確邊界，從而獲得二維碼的精確定位。該發明可自動對圖像中的二維碼進行定位，使得在對二維碼定位時不需要人工進行干涉即可排除圖像中複雜背景的干擾，而且通過預篩選和粗定位，減少了自動定位過程中的數據處理量。
2020年7月14日，《一種二維碼定位方法及系統》獲得第二十一屆中國專利獎優秀獎。
（概述圖為《一種二維碼定位方法及系統》摘要附圖）
基本介紹
- 中文名：一種二維碼定位方法及系統
- 申請人：深圳市華漢偉業科技有限公司
- 申請日：2016年9月27日
- 申請號：2016108572101
- 公布日：2017年3月8日
- 公布號：CN106485183A
- 發明人：楊洋
- 地址：廣東省深圳市南山區科技園園西工業區25棟603室
- Int. Cl.：G06K7/14(2006.01)I
- 代理機構：深圳鼎合誠智慧財產權代理有限公司
- 代理人：郭燕、彭家恩
- 類別：發明專利
專利背景,發明內容,專利目的,技術方案,改善效果,附圖說明,技術領域,權利要求,實施方式,榮譽表彰,
專利背景
與條形碼相比，二維碼具有信息容量大、可靠性高、保密性及安全性好等多種優點，因此二維碼技術在工業領域獲得了飛速發展和廣泛套用。二維碼技術套用的關鍵在於二維碼識別，即通過一些掃描設備獲取條碼信息，然後進行解碼。2016年前，二維碼識別大多依賴於具體的識別設備，並且需要人工對準待識別二維碼，需要人工干預。近年來隨著數字圖像處理技術的發展，出現了基於相機攝像的二維碼識別方式，在獲取到二維碼的圖像後，對二維碼的自動識別通常包括：（1）條形碼的自動檢測定位；（2）條碼圖像處理；（3）二維碼的解碼。
二維碼的自動檢測定位是條碼識別的首要步驟，也是一個複雜的過程。由於在二維碼拍攝過程中，二維碼往往和文本或者其他圖案混合在一起，二維碼僅僅是拍攝圖像的一部分，在定位過程中，必須要過濾掉文本和其他圖案，定位出二維碼。更有甚者，一次拍攝可能拍攝到多個二維碼圖像，在後續定位過程中，必須要將此多個二維碼從背景中識別出來並逐個進行定位。因此，如何在複雜圖像中自動定位並識別二維碼是亟待解決的問題。
發明內容
專利目的
《一種二維碼定位方法及系統》提供一種二維碼定位方法及系統，能夠在複雜圖像中自動定位出二維碼。
技術方案
《一種二維碼定位方法及系統》的技術方案是：
根據第一方面，一種實施例中提供一種二維碼定位方法，包括：輸入圖像數據；利用二維碼數據區的邊緣信息對圖像數據進行預篩選，確定可能包含二維碼的圖像區域作為候選區域，所述邊緣信息是指灰度值具有突變的區域；對每個候選區域，利用待定位二維碼的定點陣圖形確定二維碼外邊界的大致位置，從而獲得二維碼的粗略定位；根據二維碼外邊界的大致位置確定出二維碼的精確邊界，從而獲得二維碼的精確定位。
根據第二方面，一種實施例中提供一種二維碼定位系統，包括：圖形獲取單元，用於輸入圖像數據；預篩選單元，用於利用二維碼數據區的邊緣信息對圖像數據進行預篩選，確定可能包含二維碼的圖像區域作為候選區域，所述邊緣信息是指灰度值具有突變的區域；粗略定位單元，用於對每個候選區域，利用待定位二維碼的定點陣圖形確定二維碼外邊界的大致位置，從而獲得二維碼的粗略定位；精確定位單元，用於根據二維碼外邊界的大致位置確定出二維碼的精確邊界，從而獲得二維碼的精確定位。
改善效果
《一種二維碼定位方法及系統》基於圖像數據進行二維碼定位，定位過程包括預篩選、粗定位和精確定位，通過將圖像的邊緣信息和紋理信息相結合，進行預篩選，獲取可能的二維碼區域，然後結合二維碼的定點陣圖形進行粗定位，最後在粗定位的基礎上確定出二維碼的精確邊界，從而獲得二維碼的精確定位。這種定位方式可自動對圖像中的二維碼進行定位，使得在對二維碼定位時不需要人工進行干涉即可排除圖像中複雜背景的干擾，而且通過預篩選和粗定位，減少了自動定位過程中的數據處理量。
附圖說明
圖1為Data Matrix二維碼的示意圖；
圖2為一種實施例的二維碼識別設備的結構示意圖；
圖3為一種實施例中二維碼定位流程圖；
圖4為預篩選的一種具體實施方式的流程圖；
圖5為將整個圖像數據劃分成若干數據塊的示意圖；
圖6為Data Matrix二維碼的定點陣圖形的示意圖；
圖7為粗定位的一種具體實施方式的流程圖；
圖8為一種具體實施例中獲得的虛邊矩形區域的示意圖；
圖9為精確定位的一種具體實施方式的流程圖；
圖10a為兩條實線外邊界的掃描區域的示意圖；
圖10b為兩條虛線外邊界的掃描區域的示意圖；
圖11為一種實施例的定位系統的結構示意圖。
技術領域
《一種二維碼定位方法及系統》圖像處理，具體涉及根據圖像對二維碼進行定位的方法及系統。
權利要求
1.一種二維碼定位方法，其特徵在於包括：輸入圖像數據；利用二維碼數據區的邊緣信息對圖像數據進行預篩選，確定可能包含二維碼的圖像區域作為候選區域，所述邊緣信息是指灰度值具有突變的區域；對每個候選區域，利用待定位二維碼的定點陣圖形確定二維碼外邊界的大致位置，從而獲得二維碼的粗略定位；根據二維碼外邊界的大致位置確定出二維碼的精確邊界，從而獲得二維碼的精確定位。
2.如權利要求1所述的方法，其特徵在於，所述利用二維碼數據區的邊緣信息對圖像數據進行預篩選包括：將圖像數據劃分成若干個數據塊；檢測各數據塊中的邊緣信息；根據邊緣信息計算各數據塊中的邊緣參數，所述邊緣參數包括邊緣頻率和邊緣角度差中的至少一個，所述邊緣頻率是指數據塊中邊緣信息的個數；根據各數據塊的邊緣參數判斷該數據塊是否是與二維碼相關的數據塊；將所有與二維碼相關的數據塊進行連通處理，得到連通區域；判斷連通區域大小是否符合第一設定閾值，如果是，則該連通區域為可能包含二維碼的候選區域。
3.如權利要求2所述的方法，其特徵在於，檢測各數據塊中的邊緣信息包括：計算各像素點在第一維度和第二維度的梯度分量；根據梯度分量計算各像素點的梯度幅值；將梯度幅值和第二設定閾值進行比較，如果像素點的梯度幅值大於第二設定閾值，則認為該像素點為一個邊緣信息；邊緣角度差通過以下步驟計算：根據像素點的梯度分量計算各像素點的邊緣角度；統計數據塊的邊緣角度並生成直方圖，計算直方圖中明顯波峰之間的角度差，該角度差為邊緣角度差。
4.如權利要求2所述的方法，其特徵在於，根據各數據塊的邊緣參數判斷該數據塊是否是與二維碼相關的數據塊包括：將數據塊內的像素進行二值化處理，統計數據塊內黑白像素的比例，得到第一比例；統計數據塊的邊緣頻率與劃分的所有數據塊數量的比值，得到第二比例；統計數據塊的邊緣角度差與90度的比值，得到第三比例；計算第一比例、第二比例和第三比例的加權和，得到該數據塊的相關性得分；將相關性得分與第三設定閾值進行比較，根據比較結果標記該數據塊是否是與二維碼相關的數據塊。
5.如權利要求1至4中任一項所述的方法，其特徵在於，所述二維碼為Data Matrix二維碼，所述二維碼的定點陣圖形包括兩條垂直相交的實線外邊界信息和兩條垂直相交的虛線外邊界信息，利用待定位二維碼的定點陣圖形確定二維碼外邊界的大致位置包括：從候選區域中提取線段；根據定點陣圖形，篩選出長度符合實線外邊界長度範圍的線段；判斷符合實線外邊界長度範圍的線段的數量是否小於兩條，如果是，則放棄該候選區域，否則對該候選區域進行以下處理；在候選區域的線段中進行“L”形線段匹配，並獲取“L”形線段的長度以及三個頂點的位置坐標，從而確定出該候選區域中所有二維碼的兩條實線外邊界的大致位置；根據“L”形線段的長度以及三個頂點的位置坐標，以及定點陣圖形中實線外邊界和虛線外邊界的位置關係確定出兩條虛線外邊界所在的矩形區域，兩條實線外邊界和兩條虛線外邊界圍合的區域為候選二維碼區域。
6.如權利要求5所述的方法，其特徵在於，通過區域增長法從候選區域中提取線段，具體包括：在候選區域中根據邊緣信息找出種子點；在種子點的八鄰域內搜尋滿足角度條件的點加入增長區域；將新增長的點作為種子點繼續增長，直至結束增長；對增長區域中的點進行直線擬合，從而提取出線段。
7.如權利要求5所述的方法，其特徵在於，在確定出兩條虛線外邊界所在的矩形區域後還包括：分別沿著所述矩形區域的短邊方向查找角點，所述角點是指兩條邊緣線的交點；判斷角點數量與虛線的矩形區域的面積比值是否大於第四設定閾值，如果是，則保留該候選二維碼區域以對其進行精確定位，否則丟棄該候選二維碼區域，不再對其進行精確定位。
8.如權利要求5所述的方法，其特徵在於，在二維碼的外邊界所在區域中確定出二維碼的精確邊界包括：分別從實線外邊界和虛線外邊界的大致位置向兩側偏移預定像素，生成掃描區域；在掃描區域內沿預定方向掃描邊緣點，並將獲取的邊緣點分組保存；將各組的邊緣點進行直線擬合，分別得到實線外邊界和虛線外邊界的精確位置；計算兩條實線外邊界和兩條虛線外邊界的四個交點的位置坐標。
9.一種二維碼定位系統，其特徵在於包括：圖形獲取單元，用於輸入圖像數據；預篩選單元，用於利用二維碼數據區的邊緣信息對圖像數據進行預篩選，確定可能包含二維碼的圖像區域作為候選區域，所述邊緣信息是指灰度值具有突變的區域；粗略定位單元，用於對每個候選區域，利用待定位二維碼的定點陣圖形確定二維碼外邊界的大致位置，從而獲得二維碼的粗略定位；精確定位單元，用於根據二維碼外邊界的大致位置確定出二維碼的精確邊界，從而獲得二維碼的精確定位。
10.如權利要求9所述的系統，其特徵在於，所述預篩選單元包括：分塊子單元，用於將圖像數據劃分成若干個數據塊；邊緣檢測子單元，用於檢測各數據塊中的邊緣信息；邊緣參數計運算元單元，用於根據邊緣信息計算各數據塊中的邊緣參數，所述邊緣參數包括邊緣頻率和邊緣角度差中的至少一個，所述邊緣頻率是指數據塊中邊緣信息的個數；第一判斷子單元，用於根據各數據塊的邊緣參數判斷該數據塊是否是與二維碼相關的數據塊；連通子單元，用於將所有與二維碼相關的數據塊進行連通處理，得到連通區域；第二判斷子單元，用於判斷連通區域大小是否符合第一設定閾值，如果是，則該連通區域為可能包含二維碼的候選區域。
11.如權利要求10所述的系統，其特徵在於，邊緣檢測子單元用於通過以下方式檢測邊緣信息：計算各像素點在第一維度和第二維度的梯度分量；根據梯度分量計算各像素點的梯度幅值；將像素點的梯度幅值和第二設定閾值進行比較，如果梯度幅值大於第二設定閾值，則認為該像素點為一個邊緣信息；邊緣參數計運算元單元用於統計數據塊內的邊緣信息，得到邊緣頻率；根據梯度分量計算各像素點的邊緣角度，統計數據塊的邊緣角度的直方圖，計算直方圖中明顯波峰之間的角度差，該角度差為邊緣角度差。
12.如權利要求10所述的系統，其特徵在於，第一判斷子單元用於：將數據塊內的像素進行二值化處理，統計數據塊內黑白像素的比例，得到第一比例；統計數據塊的邊緣頻率與劃分的所有數據塊數量的比值，得到第二比例；統計數據塊的邊緣角度差與90度的比值，得到第三比例；計算第一比例、第二比例和第三比例的加權和，得到該數據塊的相關性得分；將相關性得分與第三設定閾值進行比較，根據比較結果標記該數據塊是否是與二維碼相關的數據塊。
13.如權利要求9至12中任一項所述的系統，其特徵在於，所述二維碼為Data Matrix二維碼，所述二維碼的定點陣圖形包括兩條垂直相交的實線外邊界信息和兩條垂直相交的虛線外邊界信息，粗略定位單元包括：線段提取子單元，用於從候選區域中提取線段；實線粗定位子單元，用於根據定點陣圖形，篩選出長度符合實線外邊界長度範圍的線段；判斷符合實線外邊界長度範圍的線段的數量是否小於兩條，如果是，則放棄該候選區域，否則在候選區域的線段中進行“L”形線段匹配，並獲取“L”形線段的長度以及三個頂點的位置坐標，從而確定出該候選區域中所有二維碼的兩條實線外邊界的大致位置；虛線粗定位子單元，用於根據“L”形線段的長度以及三個頂點的位置坐標，以及定點陣圖形中實線外邊界和虛線外邊界的位置關係確定出兩條虛線外邊界所在的矩形區域；兩條實線外邊界和兩條虛線外邊界圍合的區域為候選二維碼區域。
14.如權利要求13所述的系統，其特徵在於，線段提取子單元通過區域增長法從二維碼的大致區域中提取線段。
15.如權利要求13所述的系統，其特徵在於，粗略定位單元還包括再篩選子單元，所述再篩選子單元用於在確定出兩條虛線外邊界所在的矩形區域後分別沿著所述矩形區域的短邊方向查找角點，所述角點是指兩條邊緣線的交點，判斷角點數量與矩形區域的面積比值是否大於第四設定閾值，如果是，則保留該候選二維碼區域以對其進行精確定位，否則丟棄該候選二維碼區域，不再對其進行精確定位。
16.如權利要求13所述的系統，其特徵在於，精確定位單元包括：偏移子單元，用於分別從實線外邊界和虛線外邊界的粗略位置向兩側偏移預定像素，生成掃描區域；掃描子單元，用於在掃描區域內沿預定方向掃描邊緣點，並將獲取的邊緣點分組保存；擬合子單元，用於將各組的邊緣點進行直線擬合，分別得到實線外邊界和虛線外邊界的精確位置；交點坐標計運算元單元，用於計算兩條實線外邊界和兩條虛線外邊界的四個交點的位置坐標。
實施方式
二維碼可通過各種編碼方式產生，為方便二維碼的定位，每種二維碼都有各自的定位特徵，該文中稱為定點陣圖形，定點陣圖形用於條碼符號定位和確定條碼結構信息，也可用於解決符號定位和失真問題，定點陣圖形的四周是空白區，用於將條碼與背景分離。例如Data Matrix二維碼，如圖1所示，完整的Data Matrix二維碼10呈現為一矩形的二維碼圖形，具有四條邊，兩條相互垂直的實線外邊界11和兩條相互垂直的虛線外邊界12，中間是黑白相間的數據單元構成的數據區13。在該發明實施例中，在對圖像中的二維碼進行定位時，首先將圖像的邊緣信息和紋理信息相結合，進行預篩選，獲取可能的二維碼區域，然後結合二維碼的定點陣圖形（Pattern Finder）進行粗定位，最後在粗定位的基礎上確定出二維碼的精確邊界，從而獲得二維碼的精確定位。
下面以Data Matrix二維碼為例通過具體實施方式結合附圖對該發明作進一步詳細說明。
- 實施例一
參考圖2，二維碼識別設備包括圖像採集模組20和圖像處理模組40，圖像採集模組20可以是工業相機、手機攝像頭等，將採集的圖像數據通過網口或者USB傳送給圖像處理模組40，在另外的實施例中，二維碼識別設備也可以不包括圖像採集模組20，圖像數據也可以直接從本地圖片載入到圖像處理模組40，或通過有線或無線網路從其他伺服器下載到圖像處理模組40。
圖像處理模組40包括圖像質量評估系統41、預處理系統42、定位系統43、圖像校正及增強系統44和解碼系統45。
圖像質量評估系統41對輸入圖像的對比度、光照非線性變化、模糊程度進行打分，分數的取值範圍可設為0～1，並將打分結果傳遞給預處理系統42。對比度評價採用區域對比度形式，將圖像分割為若干個部分，在每個區域中內計算灰度的最大值與最小值之差，再除以最大值，即
（1）
其中f（xi，yi）為區域j中坐標（xi，yi）處的灰度值。獲得各個區域的對比度後，對所有像素區域的對比度求平均值，作為整個圖像的對比度打分。圖像的對比度估計也可以選擇基於直方圖最暗值（最小反射率）和其最亮值（最大反射率）之間中點的一種極其簡單的方法對圖像進行打分。
對光照的非線性變化進行打分時，將圖像分解為兩部分：亮度圖像i（x，y）和反射圖像r（x，y），根據反射圖像對圖像的非線性變化進行打分。
圖像的模糊程度評價主要對邊緣的擴散寬度進行分析，通常圖像越模糊，邊緣擴散寬度越大，圖像越清晰，圖像邊緣擴散寬度越窄，根據圖像邊緣的擴散寬度進行打分。
圖像質量評估系統41的處理結果傳遞給預處理系統42。預處理系統根據圖像質量評估的得分進行判斷，若得分小於設定閾值，則進行直方圖均衡化和頻率濾波處理，增強圖像的對比度，減少光照的非線性變化。預處理後的圖像數據將傳給定位系統43。若得分大於或等於設定閾值，則預處理系統42直接將圖像數據傳給定位系統43。
定位系統43用於在圖像數據中查找二維碼區域，當在圖像數據中查找出二維碼區域後對二維碼進行定位，後面將對定位系統43進行詳細說明。
圖像校正及增強系統44根據定位系統43定位出的二維碼進行圖像校正及增強，圖像校正主要用於消除梯形畸變，進行透視校正，減小因二維碼圖像透視效果導致的解碼誤差。圖像增強主要用於增強二維碼所在圖像區域的對比度，為二值化做準備，提高二維碼解碼區域的對比度，從而提高解碼的準確率。
解碼系統45用於對二維碼的數據區進行識別，按照編碼規則對二維碼進行解碼，在一種具體實施例中，解碼按照國際標準ISO/IEC 16022進行。
該領域技術人員可以理解，在有的實施例中，圖像處理模組40也可以沒有圖像質量評估系統41、預處理系統42和圖像校正及增強系統44中的一個或多個。
該實施例中，定位系統43在圖像數據中進行二維碼定位的方法如圖3所示，包括以下步驟：
步驟100，輸入圖像數據。定位系統43得到的圖像數據中可能包含二維碼圖形，也可能不包含二維碼圖形，也可能包含多個二維碼圖形。
步驟110，預篩選。該步驟中，利用二維碼數據區的邊緣信息對圖像數據進行預篩選，確定可能包含二維碼的圖像區域作為候選區域，其中邊緣信息是指像素灰度值具有突變的區域。預篩選的一種具體實施方式如圖4所示，包括以下步驟：
步驟111，劃分數據塊。將整個圖像數據劃分成M×N個數據塊，M和N可以相等，也可以不等，如圖5所示，每個數據塊中包含c×d個像素，c和d可以相等，也可以不等。下面對每個數據塊進行分析。
步驟112，檢測各數據塊中的邊緣信息。該步驟中主要利用二維碼的數據區特徵進行邊緣檢測。相比於圖像的其他背景，數據區由若干黑白相間的數據單元構成，因此會形成大量的邊緣信息。邊緣信息可以利用一階信息或者二階信息進行檢測。若根據一階信息進行邊緣檢測，可採用例如Sobel、Canny等算法進行檢測，根據閾值進行篩選，從而檢測出邊緣信息；若根據二階信息進行邊緣檢測，則可選擇二階信息等於零的點作為邊緣點。該實施例中，為減少計算量，邊緣信息檢測可採用以下算法：首先計算每一像素的灰度梯度。對於一二維圖像而言，每一像素點可能在X維度產生灰度突變，也可能在Y維度產生灰度突變，通過以下公式計算每一像素的梯度幅值。
式中i（x，y）為圖像在像素點（x，y）處的灰度值，gx（x，y），gy（x，y）為灰度梯度在x，y方向的分量。
像素點的梯度幅值為：
（3）
像素點的邊緣角度為：
（4）
該領域技術人員應當理解，在另外的實施例中也可以採用其他的算法計算像素點的梯度幅值，例如在預定方向上將相鄰兩像素點的灰度值相減得到梯度幅值。
計算出各像素點的梯度幅值後，將像素點的梯度幅值和第二設定閾值進行比較，如果梯度幅值大於第二設定閾值，則認為該像素點為一個邊緣點，該文中也稱為一個邊緣信息。
步驟113，根據邊緣信息計算各數據塊中的邊緣參數。邊緣參數包括邊緣頻率和邊緣角度差，邊緣頻率是指數據塊中檢測到的邊緣信息的個數，即數據塊中梯度幅值大於第二設定閾值的邊緣點的個數，用fi表示第i個數據塊的邊緣頻率。第二設定閾值設定時可以按照下述原則：若對比度較強，則該閾值取值較大，若對比度較差，則該閾值較小。由於二維碼的數據區由黑白數據單元按照編碼規則混雜構成，因此數據區會形成較多邊緣信息。
邊緣角度差採用以下方法計算：
統計數據塊的邊緣角度的直方圖，可對直方圖進行濾波處理，避免噪聲的影響，然後計算直方圖中明顯波峰之間的角度差，該角度差記為邊緣角度差αi。
對於二維碼區域，其邊緣角度的直方圖會有兩個明顯的波峰，且兩個波峰的角度差接近90°。因此，統計的數據塊的邊緣角度差αi越接近90°，數據塊中含有二維碼的幾率越大。
該領域技術人員應當理解，在另外的實施例中，也可以定義邊緣參數包含更多個與邊緣信息相關的參數，或定義邊緣參數包含邊緣頻率和邊緣角度差中的一個。
步驟114，根據各數據塊的邊緣參數判斷該數據塊是否是與二維碼相關的數據塊，即判斷數據塊中是否可能含有二維碼或二維碼的一部分。該實施例中採用以下步驟判斷數據塊中是否與二維碼相關：
將數據塊內的像素進行二值化處理，統計數據塊內黑白像素的比例，得到第一比例，記為ri；
統計數據塊的邊緣頻率與劃分的所有數據塊數量的比值，得到計算邊緣所占百分比，記為第二比例，即：
（5）
統計數據塊的邊緣角度差與90度的比值，得到第三比例，即：
（6）
計算第一比例、第二比例和第三比例的加權和，得到該數據塊的相關性得分:score＝w1eratio+w2αratio+w3ri （7）
其中，w1，w2，w3分別為各比例的權重。
將相關性得分score與第三設定閾值進行比較，根據比較結果標記該數據塊，如果該數據塊的相關性得分score大於第三設定閾值，則將該數據塊的屬性標記為True，表示該數據塊中可能包含二維碼或二維碼的一部分，與二維碼相關，否則將該數據塊的屬性標記為False，表示該數據塊與二維碼無關，屬於背景部分。
該領域技術人員應當理解，在其它的具體實施例中，也可以採用其它方法判斷數據塊是否是與二維碼相關，例如只根據邊緣頻率判斷數據塊是否是與二維碼相關，如果一個數據塊中的邊緣頻率小於一定閾值，說明該數據塊中可能不含有數據區，即該數據塊中可能沒有二維碼。
步驟115，將所有與二維碼相關的數據塊進行連通處理，得到連通區域。
該實施例中，在將數據塊進行區域連通分析時，為了縮小區域連通性分析的時間，重新生成一幅圖，每個數據塊用一個灰度值代表，若數據塊屬性為True，則灰度值設定為255，若數據塊屬性為False，則灰度值設定為0。在進行連通時僅對灰度值為255的數據塊進行連通處理，獲得的連通區域記為Ri。
步驟116，判斷連通區域大小是否符合第一設定閾值，如果是，則該連通區域為可能包含二維碼的候選區域，否則對該連通區域不做處理。步驟115中獲得的連通區域可能有一個，也可能有多個，可能有的大，有的小，可能是包含二維碼的區域，也可能是雜亂的背景，為減少後續的處理量，需要對連通區域先進行判斷。該實施例中，由於Data Matrix二維碼為矩形，因此判斷連通區域是否符合矩形的邊長範圍。
例如，對獲得的第i個連通區域Ri，首先對連通區域Ri做最小外接矩形，得到其最小外接矩形的長度和寬度分別為leni和widi。
然後將leni和widi與設定閾值進行比較，若l1≤leni≤l2，w1≤widi≤w2，則連通區域Ri作為定位區域的候選區域，否則忽略該區域，其中l1，l2為區域長度的下限閾值和上限閾值，w1，w2為區域寬度的下限閾值和上限閾值。
獲得候選區域後請再次參考圖3，對候選區域執行步驟120，進行粗定位處理。
在步驟120中，對每個候選區域，利用待定位二維碼的定點陣圖形確定二維碼外邊界的大致位置，從而獲得二維碼的粗略定位。
該實施例定義的Data Matrix二維碼的定點陣圖形是一個模組的寬度，是數據區的邊界，其包括兩條垂直相交的實線外邊界信息和兩條垂直相交的虛線外邊界信息，如圖6所示，其中全部由深色模組組成的鄰邊構成了一個“L”形實線外邊界14，“L”邊對邊由交替的深淺模組組成的兩條鄰邊又構成了虛線外邊界15，實線外邊界14和虛線外邊界15圍合成的矩形的四周是空白區，用於將二維碼和背景分離。在一種具體實施例中，利用Data Matrix二維碼的定點陣圖形確定二維碼外邊界的大致位置的過程如圖7所示，包括以下步驟：
步驟121，從候選區域中提取線段。
線段提取可以有兩種方法可以選擇，一種是Hough變換法，一種是區域增長法。無論是Hough變換法還是區域增長法，處理的都是候選區域Ri所對應圖像部分的信息。區域增長法主要利用邊緣角度的方向進行增長，首先在候選區域Ri中根據邊緣信息找出種子點，具體是在候選區域中找出梯度幅值最大的點作為種子點，然後在種子點的8鄰域內搜尋滿足角度條件的邊緣點加入到增長區域，該角度條件為：|θregion-θi|≤τ （8）
式中θregion為增長區域的角度，θi為8鄰域中像素點的邊緣角度。初始的增長區域只有一個種子點，因此，增長區域的初始角度為種子點的邊緣角度。
將新增長的點作為種子點繼續增長，直至新的種子點的8鄰域中沒有像素點滿足角度條件時結束增長，對增長區域中的點進行直線擬合，例如利用最小二乘法擬合，從而提取出線段。
在候選區域Ri的未被增長的像素點中再次查找出梯度幅值最大的點作為種子點，開始下一線段的區域增長，採用同樣的方法提取出下一條線段。如此提取出候選區域Ri中的所有線段。
線段提取後可以獲得如下信息：每個線段的重心（cxi，cyi），線段的長度li，線段的單位方向向量（nxi，nyi），根據這些信息可以計算出線段的端點（px1，py1）和（px2，py2）。
將提取出的所有線段加入線段列表，然後進行線段篩選，線段篩選包括兩方面，第一是對線段長度的篩選，第二是對線段數量的篩選。
步驟122，判斷線段的長度是否符合要求。
根據定點陣圖形，實線外邊界應具有一個長度範圍，即長度上限lupper和長度下限llower，如果線段的長度大於長度上限lupper或者小於長度下限llower，則將該線段從線段列表中刪除，從而篩選出長度符合實線外邊界長度範圍的線段。
步驟123，判斷線段列表中線段的數量是否小於兩條，如果是，則放棄該候選區域，否則對該候選區域進行執行步驟124。
步驟124，“L”形線段匹配。“L”形線段匹配包括兩方面，第一是角度閾值的匹配，即在候選區域的線段中篩選出相交且夾角滿足角度閾值的兩條線段，其判斷式為：α1<α<α2，其中α1，α2為角度閾值，α為兩線段的夾角，如果是，則兩線段滿足角度閾值。第二是相對長度的匹配，即將兩條線段的長度分別記為l1，l2，l1＞l2，判斷是否滿足l1/l2<τ1，其中τ1為用戶設定的閾值。當上述兩方面都滿足時，則當前判斷的兩條線段可能是“L”形線段，然後執行步驟125，如果上述兩方面有其中一個不滿足，則當前判斷的兩條線段不是“L”形線段，則選取另外兩條線段再執行步驟124進行判斷，直到篩選出全部的“L”形線段。每兩條“L”形線段可能對應著一個二維碼。
步驟125，獲取“L”形線段的長度以及三個頂點的位置坐標。“L”形邊的三個頂點分別記為（xi，yi）（i＝1，2，3），兩條線段的長度記為len1，len2並且len1＞len2。從而確定出該候選區域中所有二維碼的兩條實線外邊界的大致位置。
步驟126，虛邊提取。該實施例中，根據“L”形線段的長度以及三個頂點的位置坐標，以及定點陣圖形中實線外邊界和虛線外邊界的位置關係確定出兩條虛線外邊界所在的矩形區域，具體包括以下步驟：
如圖8所示，根據“L”形邊信息，分別偏移一定距離獲取虛邊的矩形區域，矩形區域信息分別用矩形的左上點和右下點表示，假定“L”形邊的豎邊的上頂點坐標為（x1，y1），“L”形邊的橫邊的由頂點坐標為（x3，y3），兩邊的交點坐標為（x2，y2），偏移距離為τ，則圖8中上側的矩形區域可表示為：regionupper＝{x1-τ，y1-τ，x1+len1+τ，y1+len1-len2+τ} （10）
圖8中右側的矩形區域可以表示為：regionright＝{x1+len2-len1-τ，y1-len1-τ，x3+τ，y3+τ} （11）
其中τ為用戶設定的參數。從而獲得二維碼兩條虛線外邊界所在的大致區域，可以初步認為虛線外邊界位於矩形區域沿長度方向的中線位置。
在其它實施例中，也可以通過其它方法確定兩條虛線外邊界的大致位置。
根據上述步驟，可提取到的兩條實線外邊界和兩條虛線外邊界，將兩條實線外邊界和兩條虛線外邊界圍合的區域作為候選二維碼區域。
在優選的實施例中，在步驟126之後還可以包括步驟127，分別沿著矩形區域的短邊方向查找角點，所述角點是指兩條邊緣線的交點；判斷角點數量與虛線的矩形區域的面積比值是否大於第四設定閾值，如果是，則執行步驟128保留該候選二維碼區域以對其進行精確定位，否則執行步驟129，丟棄該候選二維碼區域，不再對其進行精確定位。
請再參考圖3，對候選二維碼區域執行步驟130，對二維碼進行精確定位。
在步驟130中，根據二維碼外邊界的大致位置確定出二維碼的精確邊界，從而獲得二維碼的精確定位，其具體處理流程如圖9所示，包括以下步驟：
步驟131，分別從實線外邊界和虛線外邊界的大致位置向兩側偏移Δa個像素，生成掃描區域。如圖10a所示，兩條水平線所夾區域16和兩條垂直線所夾區域17分別為兩條實線外邊界的掃描區域。如圖10b所示，兩條水平線所夾區域18和兩條垂直線所夾區域19分別為兩條虛線外邊界的掃描區域。
步驟132，在掃描區域內沿圖中箭頭所示方向掃描邊緣點，並將獲取的邊緣點分組分別保存在pleft，pright，pupper，plower中。
步驟133，將各組的邊緣點進行直線擬合（例如最小二乘法），經疊代可得到最優直線，從而分別得到實線外邊界和虛線外邊界的精確位置。
步驟134，計算兩條實線外邊界和兩條虛線外邊界的四個交點的位置坐標。
經過上述步驟後，可得到二維碼的四條邊的精確位置。
該領域技術人員應當理解，在其他的具體實施例中，也可採用其他的方法在實線外邊界和虛線外邊界的大致位置精確確定出兩條實線外邊界和兩條虛線外邊界的位置。
- 實施例二
該實施例中，如圖11所示，定位系統包括圖形獲取單元431、預篩選單元432、粗略定位單元433和精確定位單元434。
圖形獲取單元431用於輸入圖像數據。
預篩選單元432用於利用二維碼數據區的邊緣信息對圖像數據進行預篩選，確定可能包含二維碼的圖像區域作為候選區域，所述邊緣信息是指灰度值具有突變的區域。在一具體實例中，預篩選單元432包括分塊子單元4321、邊緣檢測子單元4322、邊緣參數計運算元單元4323、第一判斷子單元4324、連通子單元4325和第二判斷子單元4326。
分塊子單元4321用於將圖像數據劃分成若干個數據塊。
邊緣檢測子單元4322用於檢測各數據塊中的邊緣信息。在一種具體實施例中，邊緣檢測子單元4322通過以下方式檢測邊緣信息：計算各像素點在第一維度和第二維度的梯度分量，根據梯度分量計算各像素點的梯度幅值，將像素點的梯度幅值和第二設定閾值進行比較，如果梯度幅值大於第二設定閾值，則認為該像素點為一個邊緣信息。
邊緣參數計運算元單元4323用於根據邊緣信息計算各數據塊中的邊緣參數，在一具體實施例中，邊緣參數包括邊緣頻率和邊緣角度差中的至少一個，邊緣頻率為數據塊內梯度幅值大於第二設定閾值的邊緣信息的個數；邊緣角度差通過以下方式獲得：根據梯度分量計算各像素點的邊緣角度，統計數據塊的邊緣角度的直方圖，計算直方圖中明顯波峰之間的角度差，該角度差為邊緣角度差。
第一判斷子單元4324用於根據各數據塊的邊緣參數判斷該數據塊是否是與二維碼相關的數據塊。在一具體實施例中，第一判斷子單元4324用於將數據塊內的像素進行二值化處理，統計數據塊內黑白像素的比例，得到第一比例；統計數據塊的邊緣頻率與劃分的所有數據塊數量的比值，得到第二比例；統計數據塊的邊緣角度差與90度的比值，得到第三比例；計算第一比例、第二比例和第三比例的加權和，得到該數據塊的相關性得分；將相關性得分與第三設定閾值進行比較，根據比較結果標記該數據塊是否是與二維碼相關的數據塊。
連通子單元4325用於將所有與二維碼相關的數據塊進行連通處理，得到連通區域。
第二判斷子單元4326用於判斷連通區域大小是否符合第一設定閾值，如果是，則該連通區域為可能包含二維碼的候選區域。
粗略定位單元433用於對每個候選區域，利用待定位二維碼的定點陣圖形確定二維碼外邊界的大致位置，從而獲得二維碼的粗略定位。在一具體實例中，如圖11所示，粗略定位單元433包括線段提取子單元4331、實線粗定位子單元4332和虛線粗定位子單元4333，線段提取子單元4331用於從候選區域中提取線段。實線粗定位子單元4332用於根據定點陣圖形，篩選出長度符合實線外邊界長度範圍的線段；判斷符合實線外邊界長度範圍的線段的數量是否小於兩條，如果是，則放棄該候選區域，否則在候選區域的線段中進行“L”形線段匹配，並獲取“L”形線段的長度以及三個頂點的位置坐標，從而確定出該候選區域中所有二維碼的兩條實線外邊界的大致位置。虛線粗定位子單元4333用於根據“L”形線段的長度以及三個頂點的位置坐標，以及定點陣圖形中實線外邊界和虛線外邊界的位置關係確定出兩條虛線外邊界所在的矩形區域。兩條實線外邊界和兩條虛線外邊界圍合的區域為候選二維碼區域。
在另一具體實例中，如圖11所示，粗略定位單元433還包括再篩選子單元4334，再篩選子單元4334用於在確定出兩條虛線外邊界所在的矩形區域後分別沿著所述矩形區域的短邊方向查找角點，角點是指兩條邊緣線的交點，判斷角點數量與矩形區域的面積比值是否大於第四設定閾值，如果是，則保留該候選二維碼區域以對其進行精確定位，否則丟棄該候選二維碼區域，不再對其進行精確定位。
精確定位單元434用於根據二維碼外邊界的大致位置確定出二維碼的精確邊界，從而獲得二維碼的精確定位。在一具體實例中，如圖11所示，精確定位單元434包括偏移子單元4341、掃描子單元4342、擬合子單元4343和交點坐標計運算元單元4344。偏移子單元4341用於分別從實線外邊界和虛線外邊界的粗略位置向兩側偏移預定像素，生成掃描區域。掃描子單元4342用於在掃描區域內沿預定方向掃描邊緣點，並將獲取的邊緣點分組保存。擬合子單元4343用於將各組的邊緣點進行直線擬合，分別得到實線外邊界和虛線外邊界的精確位置。交點坐標計運算元單元4344用於計算兩條實線外邊界和兩條虛線外邊界的四個交點的位置坐標。
該領域技術人員可以理解，上述實施方式中各種方法的全部或部分步驟可以通過程式來指令相關硬體完成，該程式可以存儲於一計算機可讀存儲介質中，存儲介質可以包括：唯讀存儲器、隨機存儲器、磁碟或光碟等。
榮譽表彰
2020年7月14日，《一種二維碼定位方法及系統》獲得第二十一屆中國專利獎優秀獎。
