基于霍夫變換的書脊識別研究

王鈺深 黃悅恒 黃謙 劉沖

摘? 要：針對機器人自動整理圖書研究中的關鍵問題——利用機器視覺識別書脊問題展開研究。文章提出一種基于輪廓的書脊識別方法。利用Canny算子檢測書脊邊緣，根據書脊兩側輪廓為平行的線段特點，利用概率霍夫變換提取書脊兩側的輪廓，通過線段位置關系得到書脊ROI區域;根據書脊上文字與書脊顏色，亮度相差較大的特點，利用K-means對色調和亮度進行聚類，并通過判斷形態特征得到文字區域，通過文字排列方式判斷是否為書脊。將文章方法應用于實際檢測中，并與利用LSD識別書脊的方法進行對比，實驗結果表明文章方法識別正確率更高。

關鍵詞：機器視覺;書脊識別;概率霍夫變換;Canny算子

中圖分類號：TP242.6 文獻標志碼：A? ? ? ? ?文章編號：2095-2945（2020）36-0007-05

Abstract： Research on the key problem in the study of automatic book sorting by robots-the use of machine vision to identify the spine of the book. This paper proposes a method of spine recognition based on outlineand uses Canny operator to detect the edge of the spine. According to the characteristics of parallel line segments on both sides of the spine， the Probabilistic Hough Transform is used to extract the contours on both sides of the spine. The ROI area of the spine is obtained through the position relationship of the line segments; according to the text on the spine and the color of the spine， the brightness is different. The larger feature uses K-means to cluster the hue and brightness， and obtains the text area by judging the morphological characteristics， thus judging whether it is the spine by the text arrangement. The method in this paper is applied to actual detection and compared with the method of using LSD to identify the spine. The experimental results show that the method in this paper has a higher recognition accuracy.

Keywords： machine vision; spine recognition; Probabilistic Hough Transform; Canny operator

1 概述

隨著社會的發展，圖書館的使用頻率越來越高，造成了大量書籍的借閱與歸還。由于歸還量較大，工作人員無法在短時間內將圖書整理完，這給其他讀者在查詢、借閱時帶來了巨大的不便。隨著人工智能、機器人等技術的發展，越來越多的學者提出了利用機器人自動整理圖書的想法。成功識別圖書書脊是利用機器人自動整理圖書的基礎。目前書脊識別主要分為兩種思路，一種思路是利用深度學習識別書脊上文字或索書號，以此完成對書脊的識別[1，2]，另一種思路是通過書脊輪廓和顏色等特征完成對書脊的分割與識別。后一種思路的難點在于：書脊圖像比較復雜，難以區分單本圖書與相鄰圖書的輪廓;書脊顏色多樣，難以用固定的閾值進行篩選。方建軍[3]等人提出一種基于小波分析和概率Hough變換的書脊識別系統，該算法可以很好解決因運動造成的圖像模糊導致識別率下降的問題，但是需要根據書脊的厚度設置不同的Hough參數;孫繼周等人[4]提出利用顏色結合LSD檢測分割圖書，通過索書標簽進行圖書識別的算法，但該方法對閾值設置依賴較高;殷策[5]提出了基于LSD的書籍輪廓提取算法，該方法對擺放混亂的書脊識別效果較好，但是該方法耗時較長，無法滿足實時監測的需求。N.Tabassum等人[6]提出一種針對多行圖書書脊的分割方法，但是該種方法目前只能檢測較厚的排列好的書籍，無法應用于薄書籍和擺放較為混亂的書籍。曹海清等人[7]提出一種利用投影算子分割書脊，獲得索書號，利用模板匹配識別文字與數字，該方法書脊分割效果較好，識別準確率較高，但對光線條件要求較為嚴格。本文與實際項目結合，利用概率霍夫變換與K-means聚類方法，實現了一種基于輪廓的書脊識別的算法。該方法對光線條件要求較低，對閾值依賴程度較低，在與基于LSD的書籍識別方法對比中，本文方法取得了更優異的識別效果。

2 算法流程

本文算法主要分為以下幾個步驟：

S1.圖像預處理：轉為灰度圖，利用濾波去除噪聲;

S2.利用Canny算子檢測書脊邊緣直線;

S3.利用概率霍夫變換（PPHT）提取書脊輪廓線段;

S4.對S3得到的符合條件的線段融合;

S5.進行平行線檢測，將不符合條件的線段去除，符合條件的線段進行配對，得到書脊ROI區域;

S6.將圖像轉換到HSV色彩空間，利用K-means對色彩和亮度聚類，結合形態學的篩選獲得文字輪廓，并計算文字的相對位置關系。將通過篩選的文字的所在書脊輸出，未通過的刪除。

3 邊緣檢測

本部分希望提取的輪廓符合以下要求：（1）輪廓完整;（2）不同書脊輪廓可以區分。根據經驗與各個算子的綜合表現，本算法選取Canny算子作為輪廓提取算子。

Canny算子由John F.Canny于1986年提出[8]，其主要流程如下[9，10]：

（1）對圖像進行高斯濾波去除噪聲;

（2）計算梯度幅值M和梯度方向θ：

利用Sobel算子計算水平方向梯度Gx與豎直方向梯度Gy，梯度大小為M=，梯度方向為θ=arctan（）;

（3）非極大值抑制：

為精確確定邊緣，需將圖像細化到1個像素寬度。將梯度方向歸化到圖2所示的4個方向之一，將此方向作為梯度方向。使用3*3的模板作用于幅值圖像，用模板中心像素與梯度方向上的兩個像素比較，若模板中心點處的幅值M（i，j）比梯度方向上的兩個相鄰點幅值小，則M（i，j）賦值為零;

（4）閾值化和邊緣連接：

對經過非極大值抑制的圖像Q（i，j）采用雙閾值處理，低閾值處理結果為A1，高閾值處理結果為A2。以A2為基礎，用A1補充連接邊緣。

4 輪廓提取

經典霍夫變換思想是利用點和線的對偶性，將圖像中的曲線轉換為極坐標系的一點。在笛卡爾坐標系中直線方程為：

霍夫變換利用在極坐標系中的曲線交點檢測直線。在極坐標系中越多的曲線交于一點，代表著這個交點表示的直線由越多的點組成。當交于一個點的曲線數量大于設定的閾值，即可認為這個交點代表的參數在笛卡爾坐標系中為一條直線。但是經典霍夫變換計算量較大，不能夠保證實時性，本文采用概率霍夫變換（PPHT），對書脊輪廓的直線進行檢測和提取。概率霍夫變換無需對邊緣所有像素點進行檢測，僅是從邊緣點集中隨機選取點進行計算。具體過程如下[11，12]：

（1）隨機選取前景點，并在極坐標系中繪制圖像;

（2）當極坐標系中存在交點達到閾值，將該點對應的圖像在笛卡爾坐標系中的直線L繪制出來;

（3）尋找前景點，將在直線L上的點連成線段，記錄相應參數（起始位置，終止位置，線段長度），然后將這些點刪除;

（4）重復前三步，直到前景點集為空。

通過以上4步，即可快速的提取到圖像中的直線。

5 ROI區域選取

5.1線段融合

經過PPHT提取直線后，存在許多非書脊輪廓的線段，進行線段融合，減少非目標直線。利用直線的相對位置關系進行篩選，首先通過直線方程y=kx+b或x=c描述線段。刪除長度小于30像素的線段（圖像大小640*480），刪除存在交點的線段。關注垂直方向的線段，忽略k∈（0，5）∪（-5，0）的線段;按照k值進行分組，每組限差為±10。計算同一組內線段之間的距離，依次在2條線段4個端點中選3個，共構成4個三角形，使用如下公式計算三角形的高：

（1）新的線段斜率取兩條線段斜率的平均值;

（2）用一條線段的上端點與下端點分別連接另一條線段的下端點與上端點，連線交點作為新線段中心點;

（3）將融合前較長線段的長度作為新線段的長度。

5.2 平行線判斷

按中心點橫坐標從小到大的順序進行平行線匹配。匹配規則如下：

（1）若第一條線段向第二條線段投影的長度大于第一條線段長度的30%，則認為這兩條線段為一本書的書脊兩側直線，匹配成功;

（2）若投影長度小于第一條線段長度的15%～30%，認為它們可能為一本書的輪廓，繼續向下尋找，若存在投影長度更高的則將那兩條線段匹配;若投影長度小于第一條線段長度的15%，則將該條線段刪除;

（3）規定進行匹配的線段的中心點橫坐標之間的距離應小于第一條線段長度的40%，若在此范圍內無法匹配成功，則將該線段刪除;

（4）匹配僅在同組直線內進行;

（5）若第一條線段與第二條線段匹配成功，則使用第二條線段繼續進行匹配，直至所有直線都經過匹配。

5.3 選取書脊ROI區域

取匹配成功的線段端點縱坐標最大值與最小值的點，分別過該點做與其所在線段的垂線，延長另外一條線段，使其與垂線相交，如圖3所示。構成旋轉矩形區域，通過仿射變換得到書脊的ROI。

5.4 文字相對位置關系判斷

這部分對識別到的區域做進一步篩選，同時解決因書脊邊緣處梯度變化較小，而無法提取其輪廓的問題。

根據對書脊觀察，總結出如下特征：多數書脊上存在文字，且文字的顏色，亮度與其他部分差距較大;文字的大小、排列方式有一定規律。根據這些特征，提出如下篩選方法及步驟：

（1）將ROI從RGB轉換為HSV色彩空間;

（2）對H和S分量利用K-means聚類，將ROI區域分成3類;

（3）用矩形框選每一類圖像，認為存在文字的矩形長應小于書脊長度的20%，且矩形長寬比應在0.8至1.2之間;

（4）將矩形按中心點橫坐標分組，每組內橫坐標差值不應大于ROI寬度的20%。取ROI兩側線段斜率的平均值過每組內y值最小的矩形中心點做直線，判斷穿過矩形的情況與數量。與矩形上下邊有交點，則直線穿過該矩形。若穿過矩形的數量不小于3個，則認為矩形區域即為文字區域;

（5）若無文字區域，則該區域為非書脊區域，若有一組及以上的文字區域，則認為該區域為書脊區域。若僅有單組文字，則直接將該區域輸出，若有多組文字，則計算y值最大與最小的矩形中心點連線的斜率ki，并計算該組內矩形中心點橫坐標平均值xi。然后計算相鄰兩組之間平均橫坐標，計算平均斜率，找到ROI的中心點，取其縱坐標y，過（，y）以斜率做長度與ROI的高度相同的線段，將新的線段作為新添的書脊輪廓，與原有輪廓共同輸出。

6 實驗驗證

實驗目的：驗證本文的方法的可行性和有效性，與傳統方法對比，證明本文算法識別效果更好。

實驗說明及結果：

（1）線段融合

利用PPHT提取線段并經過本文所述方法融合的效果圖如圖4a所示。

（2）文字框選

利用本文的方法對書脊ROI中的文字進行框選，矩形框到的區域代表文字所在區域，如圖4b所示。

（4）書脊識別效果

展示本次實驗最終識別效果，證明本文程序的有效性。其中標注圓點的書脊代表識別到的書脊（圓點為程序計算書脊第一個文字的中點），線段代表分割效果，如圖4c所示。

7 結果分析

在本次實驗中，圖像中總共存在12本書，但程序總共識別出11本書的書脊。按照從左至右的順序給書脊編號，為1至12。

因為第2本書的書脊與第1本的書脊的邊緣灰度值相差較小，導致Canny算子未正確提取輪廓，如圖5a所示，進而導致在PPHT檢測線段時未檢測到。但1號與2號書的書脊上文字與書脊顏色差距較大，通過判斷文字相對位置，成功找到1號與2號的邊界。利用同樣方法成功區分第11本書與第12本書。

第9本書兩側的輪廓成功提取，并通過線段位置關系的檢測，但在檢測文字相對位置關系時未通過。書脊上的文字與書脊其他部分在色調和亮度上差距較小，在K-means聚類時未成功區分出文字與書脊其他區域，導致檢測失敗，如圖5b所示。在圖4c中，第9本書兩側的輪廓為它旁邊兩本書的輪廓，并非它本身的輪廓。

從實驗結果來看，本算法效果較理想。緩解了顏色相近兩本書之間輪廓無法提取的缺陷。通過對書脊色調和亮度的聚類識別文字區域，并利用其空間位置關系進行篩選，提高了基于輪廓識別書脊的準確性，降低了對閾值的依賴，提高了算法的魯棒性。

8 實驗對比

相機分辨率：640*480。

采用引文5中基于LSD書脊識別的方法與本文所述方法進行對比，識別結果如表1所示。

9 總結

本文提出了一種基于霍夫變換的書脊識別方法，通過Canny算子提取邊緣，利用PPHT檢測書脊輪廓線段，利用線段的空間位置關系得到書脊ROI區域，通過對色調和亮度的聚類，配合對文字輪廓的檢測，得到文字區域，利用文字排列關系進一步檢測書脊。實驗結果表明，本文識別效果優于傳統基于輪廓的識別方法。但本文算法也存在一定缺陷，若書脊色彩過于復雜，文字之間顏色亮度不統一或與書脊的顏色亮度差距較小，會導致無法正常識別。下一階段將進一步完善本文算法，解決目前存在的缺陷，降低算法用時，并將算法應用于機器人，進行實際的書籍整理實驗，提高算法的實際應用價值。

參考文獻：

[1]Anegawa R，Aritsugi M. Text Detection on Books Using CNN Trained with Another Domain Data[J].2019 IEEE Intl Conf on Dependable， Autonomic and Secure Computing：170-176.

[2]Cao Li-na， Liu Ming-di， Dong Zhu-qing， Yang Hua. Book SpineRecognition Based on OpenCV and Tesseract[J].201911th International Conference on Intelligent Human-MachineSystemsan

dCybernetics （IHMSC）： 332-336.

[3]方建軍，杜明芳，龐睿.基于小波分析和概率Hough變換的書脊視覺識別[J].計算機工程與科學，2014，36（01）：126-131.

[4]孫繼周，王小雄，羅佳佳.基于圖像識別的錯位圖書檢測技術研究[J].現代電子技術，2016，39（05）：58-62.

[5]殷策.基于計算機視覺的書脊識別算法研究[D].江西理工大學，2016.

[6]曹海青，王丹煜，姚志英，等.基于投影算子的圖書索書號自動識別[J].計算機系統應用，2018，27（03）：240-245.

[7]Tabassum N，ChowdhuryS， Hossen M K，Mondal S U.An approach to recognize book titlefrom multi-cell bookshelf images[J].ICLVPR， Dhaka， 2017：1-6.

[8]Canny J. A computational approach to edge detection[J].IEEE-PAMI，1986：679-698.

[9]WojciechM， Marek S. Canny edge detection algorithm modification[J]. Computer Vision and Graphics-International Conference， ICCVG 2012， Proceedings.533-540.

[10]Rong Wei-bin， Li Zhang-jing， Zhang Wei， Sun Li-ning. An improved Canny edge detection algorithm[J]. 2014 IEEE International Conference on Mechatronics and Automation （ICMA），2014，25（12）：60-63.

[11]Mochizuki.Y， Torii.A， Imiya.A. N-point Hough transform for line detection[J]. Journal of Visual Communication and Image Representation，2009，20（4）：242-253.

[12]Mu Zi-xin， Li Zi-fan. A Novel Shi-Tomasi Corner Detection Algorithm Based on Progressive Probabilistic Hough Transform[J]. 2018 Chinese Automation Congress （CAC）： 2918-2922.