Advanced
Automatic Coin Calculation System using Circular Hough Transform and Post-processing Techniques
Automatic Coin Calculation System using Circular Hough Transform and Post-processing Techniques
Journal of Korea Multimedia Society. 2014. Apr, 17(4): 413-419
Copyright © 2014, Korea Multimedia Society
  • Received : December 30, 2013
  • Accepted : March 27, 2014
  • Published : April 28, 2014
Download
PDF
e-PUB
PubReader
PPT
Export by style
Share
Article
Author
Metrics
Cited by
TagCloud
About the Authors
수환 채
Dept. of Embedded-Systems Engineering, Incheon National University
경구 전
Dept. of Embedded-Systems Engineering, Incheon National University

Abstract
In this paper, we develop an automatic coin calculation system by using digital image processing. Existing schemes have the problem that is not able to exclude non-circular shape from the calculation. We propose a method to detect only coins which have circular form by applying the circular Hough transform(CHT). However, the CHT has the drawback that detects multiple circles even for just one coin because of shadow noise, the patterns on coins, and non-circular edge detection. We propose a post processing algorithm to overcome these limitations. The proposed system was implemented and successfully calculated the coin amount in the case that non-circular objects are mixed with coins.
Keywords
1. 서 론
본 논문은 디지털 영상처리를 이용하여 동전 종류를 자동으로 인식하여 총액을 계산하는 시스템 개발에 관한 것이다. 계산해야 할 동전 개수가 많을 경우에는 주화계수기 [1 , 2] 를 이용할 수 있다. 하지만 소량의 동전일 경우 이러한 기계를 이용하는 것은 실용적이지 않다. 일상생활의 거래인 편의점이나 마트에서 소량의 동전을 지불금액이나 거스름돈으로 사용하는 경우가 여기에 해당된다.
이러한 소량의 동전계산을 위해 디지털 영상처리를 이용한 방법이 [3 , 4] 에서 제안되었다. 바닥에 서로 겹쳐지지 않게 놓인 동전들을 촬영한 후 일련의 영상처리 알고리즘을 적용하여 금액을 계산한다. 알고리즘은 동전 에지를 검출한 후, 원의 지름 크기에 따라 동전을 구별한다. 하지만 이 방법은 영상 안의 모든 물체가 동전임을 가정하기 때문에, 별도로 원 모양을 검출하는 단계가 없다. 이러한 가정 때문에 원 모양이외의 물체도 동전 지름과 일치하는 길이나 폭을 가지고 있다면 동전으로 판별하는 문제점을 가진다.
본 논문에서는 기존 방식의 문제점을 보완하기 위해 원 모양 이외의 물체를 배제할 수 있는 동전 자동계산 시스템을 개발한다. 영상에서 원 모양의 에지만을 대상으로 하여, 원 지름의 크기에 따라 동전을 분류하는 방법을 사용한다.
본 논문에서는 원 모양을 검출하기 위해 Circular Hough Transform (CHT) [5] 을 이용한다. Hough 변환은 많은 연구에서 활용되고 있으며, 활용 범위는 크게 직선 검출 [6] 및 원 검출인 Generalized Hough Transform(GHT) [7] 등으로 나뉠 수가 있다. 또한, 원을 검출하는 방법에는 [8 - 10] 등의 연구가 있다.
하지만 CHT를 적용하면 Fig. 1 과 같이 하나의 동전에 대해 중심점과 지름이 차이가 나는 복수 개의 원이 검출되는 문제점이 있다. 이는 조명 때문에 생기는 음영, 노이즈와 동전 문양 때문이다. 이러한 복수 개의 원들은 조명 변화와 종류에 따라 다양하게 나타나기 때문에 이를 효과적으로 처리할 수 있는 방법이 필요하다. 논문에서는 복수의 원들로부터 하나의 동전에 해당하는 원형을 추출하는 방법을 제안한다.
PPT Slide
Lager Image
CHT results (a) before and (b) after postprocessing.
본 논문은 다음과 같이 구성된다. 2장에서는 CHT를 이용한 동전 검출 방식과 이를 이용한 동전 계산 시스템의 개발을 설명한다. 3장에서는 이 시스템을 이용한 실험과 그 결과를 제시한다. 4장에서는 논문을 결론짓는다.
2. CHT를 이용한 동전 자동 계산 시스템
제안하는 동전 계산 방법의 순서도는 Fig. 2 와 같다. 카메라를 통해 입력된 영상은 그레이스케일 변환과 잡음제거를 위한 가우시안 필터링, 그리고 Canny 에지검출 [11] 의 과정을 순서대로 거쳐 CHT 적용을 위한 준비를 마친다. 그 후 CHT 적용과 후처리를 통해 동전들의 종류와 위치를 검출하여 금액을 결정한다. 우리는 카메라를 동전이 놓인 바닥으로부터 일정거리 위에 고정시키는 것을 가정한다. 따라서 영상에서 동전은 그 종류에 따라 동일한 지름을 가지며, 그 값은 사전실험을 통해서 얻을 수 있다.
PPT Slide
Lager Image
Flowchart of the automatic coin calculation system.
CHT는 투표방식을 이용하여 영상 내의 특정 형태를 검출하는 방법이다. 투표는 형태를 모델링하는 파라미터 공간에 대해 이뤄지는 데, 투표 결과는 파라미터 공간을 나눈 축적셀에 저장된다. 예를 들어, 2차원 파라미터 공간의 좌표 ( i , j )가 파라미터 pi pj 에 해당된다고 할 때, 축적셀 A ( i , j )는 이들 파라미터에 대한 투표결과를 저장한다. 따라서 검출은 임계값 이상을 갖는 축적셀에 해당하는 파라미터들을 찾는 것이 된다. 본 논문에서는 별다른 혼동이 없는 한 A ( i , j )와 A ( pi , pj )를 동일하게 사용한다.
CHT를 이용한 원 검출은 동전의 유효 반지름 범위(24≤ r <45(pixel))에서 0≤ θ ≤2 π 에 대해, 에지 추출된 픽셀좌표 ( x , y )를 이용하여 식 (1)을 만족시키는 원의 중심 ( i , j )와 반지름 r 를 구하는 과정이다.
PPT Slide
Lager Image
좌표 ( x , y )값, θ , 그리고 r 을 식 (1)에 대입하여 계산된 i j 에 해당하는 A ( i , j , r )의 값을 1씩 증가시킨다. 이 때 하나의 좌표 ( xt , yt )에 대해 θ r 을 변화시켜가면서 i j 값을 계산한다. θ 는 0≤ θ ≤2 π 까지 일정량씩 증가시키고, r 은 검출대상인 동전들의 반지름 길이로 한다. 모든 좌표에 대해 계산이 종료되면 A ( i , j ,r) > κ 에 대해서, 원이 검출되었다고 판정한다. κ 는 임계값으로, 값이 클수록 원 검출 확률이 낮아진다.
동전에 해당하는 원을 나타내는 파라미터를 ( Cx , Cy , r )라 하자. ( Cx , Cy )는 원의 중심점 좌표이고, r 은 반지름이다. 앞서 설명한 바와 같이 하나의 동전에 대해 음영과 동전 문양 때문에 복수 개의 원 에지들이 생기고, 이들은 CHT 적용과정을 통해 모두 다른 원으로 검출된다. 특히, 하나의 원 에지일지라도 원방정식과 일치하지 않아, 복수 개의 원으로 검출되는 경우도 있다.
이러한 점들을 감안하면, 하나의 동전에 대해 원의 중심이나 반지름이 다른 n 개의 원들이 생기므로, 이들을 처리하여 하나의 원 방정식에 해당하는 파라미터 값 ( Cx , Cy , r )을 구하는 후처리 과정이 필요하다.
CHT가 하나의 동전에 대해 검출한 n 개의 파라미터들의 집합을 C라고 하자.
PPT Slide
Lager Image
이 때 n 개의 원들의 중심에 대해 식 (3)을 가정할수 있다.
PPT Slide
Lager Image
여기에서 ρ 는 상수이다. 즉 이 가정은 하나의 동전때문에 생기는 원들은 일정범위 내에 형성된다는 것을 의미한다. 이제 이러한 가정 아래 후처리 과정을 설명한다.
후처리 과정의 1단계는 동전에 해당하는 원이 아닌 것들을 제거한다. 이를 위해, 동전에 해당할 확률이 가장 높은 원과 비교해서 중심점의 위치나 반지름 차이가 임계값 이상인 원들을 제거한다. 원이 동전에 해당할 확률은 A ( i , j , r )에 비례하여 커진다. 따라서 가장 큰 축적셀 값을 갖는 파라미터 ( Cmx , Cmy , rm )를 기준 원으로 삼는다. 이 때
PPT Slide
Lager Image
기준 원 ( Cmx , Cmy , rm )과 비교해서 중심점 위치나 반지름 크기가 각각 임계값 α β 이상으로 차이가 나는 원들을 집합 C 에서 제거한 새로운 집합 C 1 을 구성한다.
PPT Slide
Lager Image
후처리 2단계는 직관적이다. 동전을 나타내는 원들로 구성된 집합 C 1 을 산술평균 한다. 즉, 동전에 해당하는 원 ( Cx , Cy , r )을 식 (6)과 같이 결정한다.
PPT Slide
Lager Image
이러한 2단계는 원을 나타내는 에지들의 픽셀들이 원 방정식에 완벽하게 일치하는 모양으로 배열되지 않으며, 픽셀들의 좌표가 정수이기 때문에 실제 방정식 값과 차이가 생기는 것을 피할 수 없다는 점을 고려하여, 산술평균을 이용하였다.
Fig. 1 은 두 단계로 구성된 CHT 후처리 과정 전과 후의 결과를 보여준다. 7개의 동전을 놓고 촬영한 영상에 대해 Fig. 1 (a)는 후처리 과정 전의 결과이다. 음영과 문양의 영향으로 하나의 동전에 대해 여러개의 원들이 형성된다. 일부 원들은 중심점의 위치나 반지름의 차이가 현저한 것을 볼 수 있다. 특히, 작은 원이 큰 원 안에 포함된 것은 문양 때문에 생기는 것으로 판단된다. 또한 중심점의 위치만 다른 원들은 서로 간에 겹쳐져 나타난다. Fig. 1 (b)는 후처리를 거친 후의 결과이다. 일단 문양으로 인해 생겼던 작은 원들은 후처리 1단계를 통해 모두 제거 되었다. 2단계에서는 겹쳐진 원들을 평균하여 최종적인 원 파라미터를 도출해 냈다. 이러한 원들의 위치는 실제 동전의 위치와 일치하였고, 이는 Ⅲ(3장)의 실험결과에서 보다 자세히 설명한다.
마지막 단계에서는 반지름 r 에 따라 동전을 분류한다. 우리는 한국 동전 4종류, 500원, 100원, 50원, 10원을 사용하였다. 카메라와 동전간 거리가 고정되어 있으므로, 동전 종류는 반지름에 해당하는 픽셀 개수로 구분할 수 있다. Table 1 은 반지름에 해당하는 픽셀 개수에 따른 동전 분류를 보여준다.
Coin classification according to the number of pixels on radius
PPT Slide
Lager Image
Coin classification according to the number of pixels on radius
3. 동전 자동 계산 시스템 실험
본 장에서는 제안한 동전 자동 계산 시스템을 구현하여, 성능을 평가하기 위한 실험을 진행한다. 우선 시스템은 하드웨어적으로 웹캠과 PC로 구성되며, 자세한 사양은 Fig. 3 에 보여 진다. PC에서 동작하는 자동 계산 소프트웨어는 OpenCV 2.4.6 [12] 를 이용하여 구현하였으며, C++ 언어를 사용하였다.
PPT Slide
Lager Image
Experiment environment.
Fig. 3 은 실험을 위한 환경을 보여준다. 동전들을 바닥에 놓고, 그 위에 일정 거리를 두고 카메라를 설치하였다. 실험에 사용된 동전들은 지름이 모두 다른 4종류, 대한민국 500원, 100원, 50원, 10원 주화들이다. 동전의 앞뒷면을 구분 없이 배치하였고, 서로 겹쳐지지 않게 배열하였다.
Fig. 4 는 Ⅱ(2장)에서 설명한 동전 계산 과정 수행에 따른 중간결과들을 순서대로 보여준다.
PPT Slide
Lager Image
Sequence of coin detection. (a) The original image is converted to gray image, (b) gaussian filtering for noise reduction, (c) canny edge detection, and (d) circular shape detection.
Fig. 5 는 최종적으로 시스템에 의해서 동전을 분류한 결과이다. 최초 영상 위에 분류에 따른 표식을 표시하였다. 500원 동전은 원 모양, 100원은 사각형, 50원은 일자 직선, 10원은 십자가 모양이다.
PPT Slide
Lager Image
The coin recognition results. (a) Original image, (b) coin classification.
제안 방식의 성능을 확인하기 위해 동전들의 배치와 조도를 변화시키면서 실험을 수행하였다. Fig. 6 은 동전들의 개수, 위치, 동전사이의 간격 등 배치를 다양하게 하면서 실험한 결과로, 간격이 없을 때만 인식율이 95%에서 80%로 감소하였다. 이는 인접 원들간의 중복으로 인해 적절한 원 검출이 이뤄지지 않기 때문이다. Fig. 7 은 조도변화가 에지 감지에 미치는 영향과 그에 따른 인식율 변화를 보여준다. 동전 윤곽만이 검출되는 경우인 D의 동전 인식율이 가장 높은 반면, 에지 검출이 미흡하거나 과다한 경우는 인식율이 감소하는 것을 볼 수 있다.
PPT Slide
Lager Image
Recognition results according to various coin placement.
PPT Slide
Lager Image
The recognition rate changes according to detected edges.
Fig. 8 은 동전 이외 물체를 포함하여 실험을 수행하였다. 삼각형, 사각형 및 원 검출 범위에 해당하지 않는 크기의 원형을 이용하였으며, 실험한 결과 동전이외 물체가 포함된 경우에도 인식률이 95%로 변화가 없었다.
PPT Slide
Lager Image
Non-coin objects mixed with coins.
에지만 검출하는 기존 방식과 비교하기 위해 동전이외 물체가 포함된 동일한 환경에서 동전 인식을 수행하였다. Fig. 9 는 동전 인식 수행 결과로, 기존 방식에서만 1690원으로 잘못된 합계를 표시하였다. 이는 크기를 만족하는 동전 이외 물체도 동전으로 인식했기 때문이다. 기존 방식과의 비교 결과, 제안방식은 CHT의 사용으로 10배 이상 느린 처리속도를 보였지만 동전 인식률에서 70%이상 높은 정확도를 보였다.
PPT Slide
Lager Image
The recognition results of (a) the existing edge-based system and (b) the proposed system.
4. 결 론
본 논문에서는 영상처리를 이용한 동전 자동 계산 시스템을 개발하였다. 기존 방식은 원 모양을 구별하지 못하는 단점 때문에 동전 이외의 것들도 계산에 포함했다. 논문에서는 CHT를 이용하여 다른 모양의 도형들과 동전을 구분해낼 수 있었다. 음영과 동전문양 때문에 생기는 복수의 원들의 정보를 처리하는 방법도 제안하였다. 개발된 시스템은 소량의 동전 계산 업무 뿐만 아니라 관련 학습 컨텐츠 제작에도 응용될 수 있을 것으로 기대된다. 향후 연구에서는 동전의 문양을 인식하지 않고 반지름의 길이만으로 판별하기 때문에 생기는 문제점 개선에 대해 노력한다.
BIO
채 수 환
2014년 2월 인천대학교 임베디드시스템공학과 학사
2014년 2월~현재 인천대학교 임베디드시스템공학과 석사과정
관심분야 : 영상처리, 임베디드 시스템
전 경 구
1996년 2월 서강대학교 전자계산학 학사
1998년 5월 M.S. in Computer Science, Purdue Univ.
2001년 5월 Ph.D. in Computer Science, Purdue Univ.
2001년 6월~2001년 12월 Ashley Laurent Inc. SW engineer
2002년 1월~2004년 2월 삼성전자 책임연구원
2004년 3월~인천대학교 임베디드시스템공학과 부교수
관심분야: 임베디드시스템, 네트워크, 컴퓨터 비전, 기계 학습
References
2007 Kyungbang Clover http://www.kbclover.co.kr
2007 Merit http://meritoa.com
Lee J. , Lee J. , Hyun C. 2012 “Coin Recognition and Classification using Digital Image Processing," Journal of Korean Institute of Intelligent Systems 22 (1) 7 - 11    DOI : 10.5391/JKIIS.2012.22.1.7
Kim G. , Lee J. , Hyun C. 2013 “The Development of Coin Calculation Systems based on Realtime Image Processing," Proceeding of KI IS Spring Conference Vol. 23, No. 1 248 - 249
Hough P. 1962 Methods and Means from Recognizing Complex Patterns U.S Patent 3,069,654
Choi J. , Kim 2013 “Interval Hough Transform For Prominent Line Detection," Journal of Korea Multimedia Society 16 (11) 1288 - 1296    DOI : 10.9717/kmms.2013.16.11.1288
Ballard D.H. 1981 “Generalizing the Hough Transform to Detect Arbitrary Shapes,” Pattern Recognition 13 (2) 111 - 122    DOI : 10.1016/0031-3203(81)90009-1
Ioannou Dimitrios , Huda Walter , Laine Andrew F. 1999 "Circle Recognition through a 2D Hough Transform and Radius Histogramming," Image and Vision Computing 17 (1) 15 - 26    DOI : 10.1016/S0262-8856(98)00090-0
Lym J. , Lee Y. , Moon S. , Yang S. 2008 “Detection of Circle and Rectangle Image by Hough Transform for a Tape Substrate Alignment,” Journal of Institute of Control, Robotics and Systems 37 140 - 144
Won H. , Lee K. 2010 "Fast Hough Circle Detection using Motion in Video Frames," Journal of Korean Society for Internet Information 11 (6) 31 - 39
Canny John 1986 "A Computational Approach to Edge Detection," IEEE Transactions on Pattern Analysis and Machine Intelligence 8 (6) 679 - 698    DOI : 10.1109/TPAMI.1986.4767851
2014 OpenCV http://opencv.org