[논문]주성분 분석과 허프 변환을 이용한 직선 검출

오정수

doi:10.6109/jkiice.2018.22.2.227

[국내논문] 주성분 분석과 허프 변환을 이용한 직선 검출
Straight Line Detection Using PCA and Hough Transform 원문보기

한국정보통신학회논문지 = Journal of the Korea Institute of Information and Communication Engineering, v.22 no.2, 2018년, pp.227 - 232

오정수 (Department of Display Engineering, Pukyong National University)

초록
AI-Helper

직선 검출을 위한 대표적인 알고리즘인 허프 변환에서 잡음이 있거나 복잡한 영상에서 생성되는 방대한 에지 화소들은 상당한 계산량과 의사직선을 야기한다. 본 논문은 기존 허프변환을 개선하기 위해 2 단계 직선 검출 알고리즘을 제안한다. 첫 번째 단계에서 제안된 알고리즘은 영상을 겹치지 않는 블록들로 나누고, 주성분 분석(PCA)을 이용해 블록 내 에지 화소들의 직선과 관련된 정보를 검출한다. 두 번째 단계에서 직선과 관련된 화소들에 기울기 제한된 허프변환을 수행하여 직선들을 검출한다. 모의실험 결과들은 제안된 알고리즘이 부가적인 계산이 다소 필요하지만 불필요한 에지 화소들을 줄이고 기울기 영역을 제한하여 ${\rho}$ 계산의 평균 94.6% 줄여주고 의사직선 검출을 방지하는 것을 보여주고 있다.

Abstract ▼ AI-Helper

In a Hough transform that is a representative algorithm for the straight line detection, a great number of edge pixels generated from noisy or complex images cause enormous amount of computation and pseudo straight lines. This paper proposes a two step straight line detection algorithm to improve the conventional Hough transform. In the first step, the proposed algorithm divides an image into non-overlapping blocks and detects the information related to the straight line of the edge pixels in the block using a principal component analysis (PCA). In the second step, it detects the straight lines by performing the Hough transform limited slope area to the pixels associated with the straight line. Simulation results show that the proposed algorithm reduces average of ${\rho}$ computation by 94.6% and prevents the pseudo straight lines although some additional computation is needed.

주제어

AI 본문요약
AI-Helper

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

문제 정의

본 논문은 허프변환을 이용한 기존 직선 검출에서 직선과 무관한 에지 화소들에 의해 계산량이 많아지고 의사직선이 생성되는 문제를 방지하기 위한 직선 검출 알고리즘을 제안한다. 제안된 알고리즘은 첫 번째 단계에서 영상을 블록으로 나누고 PCA를 수행하여 에지 화소들의 직선 관련 정보를 검출한다.
기존 직선 검출 알고리즘인 허프 변환에서 잡음이 있거나 복잡한 영상에서 생성되는 많은 에지 화소들은 방대한 계산량을 요구하고 쉽게 의사직선을 생성하는 문제를 발생시킨다. 본 논문은 허프변환의 문제를 개선하기 위해 2 단계 직선 검출 알고리즘을 제안한다. 첫 번째 단계에서 블록 단위로 PCA을 수행해 에지 화소의 직선 정보인 유효 직선 화소인지와 유효 직선 화소이면 직선 기울기를 결정한다.

제안 방법

즉 에지 화소가 유효 직선 화소인지와 유효 직선 화소이면 직선 기울기를 계산한다. 두 번째 단계는 유효 직선 화소들에서 허용 기울기가 제한된 허프 변환을 수행하여 영상 내 직선들을 검출한다.
두 번째 단계는 첫 번째 단계에서 검출된 유효 직선 화소들에서 허용 기울기가 제한된 허프변환을 수행하해 영상의 직선들을 검출한다. 허용 기울기는 직선 모드에 따라 표 1과 같이 주어진다.
첫 번째 단계에서 블록 단위로 PCA을 수행해 에지 화소의 직선 정보인 유효 직선 화소인지와 유효 직선 화소이면 직선 기울기를 결정한다. 두 번째 단계에서 검출된 직선 정보를 근거로 유효 직선 화소에 기울기가 제한된 허프변환을 수행하여 직선들을 검출한다. 제안된 알고리즘은 부가적인 계산이 요구되지만 첫 번째 단계에서 직선과 무관한 에지 화소들을 최대 50% 정도 줄여주고 두 번째 단계에서 기울기 영역 제한은 ρ 계산의 93.
즉 에지 화소가 직선의 일부인 유효 직선 화소인지를 판단하고 유효 직선 화소가 포함된 직선의 예상 기울기를 계산한다. 두 번째 단계에서 유효 직선 화소에서 기울기가 제한된 허프변환을 수행하여 직선을 검출한다. 제안된 알고리즘은 직선과 무관한 무효 직선 화소들의 제거와 직선 기울기제한에 의해 계산량을 줄일 뿐만 아니라 의사직선의 검출을 방지할 수 있다.
mode 3블록은 검출된 직선을 경계로 두 영역으로 나누어지고 각 영역에서 PCA를 수행해 유효 직선 화소와 예상 직선 기울기를 저장한다. 미지정 블록은 PCA(validF1) 블록에서 validF1만을 이용해 PCA를 수행해 직선을 검출하고 다시 유효 직선 화소들(validF2)을 검출하여 allF와 비교한다. 일치 화소가 allF/2보다 크면 mode 4로 결정하고 직선의 유효 직선 화소들과 기울기를 저장한다.
본 논문은 허프변환을 이용한 기존 직선 검출에서 직선과 무관한 에지 화소들에 의해 계산량이 많아지고 의사직선이 생성되는 문제를 방지하기 위한 직선 검출 알고리즘을 제안한다. 제안된 알고리즘은 첫 번째 단계에서 영상을 블록으로 나누고 PCA를 수행하여 에지 화소들의 직선 관련 정보를 검출한다. 즉 에지 화소가 직선의 일부인 유효 직선 화소인지를 판단하고 유효 직선 화소가 포함된 직선의 예상 기울기를 계산한다.
제안된 알고리즘은 첫 번째 단계에서 영상을 블록으로 나누고 PCA를 수행하여 에지 화소들의 직선 관련 정보를 검출한다. 즉 에지 화소가 직선의 일부인 유효 직선 화소인지를 판단하고 유효 직선 화소가 포함된 직선의 예상 기울기를 계산한다. 두 번째 단계에서 유효 직선 화소에서 기울기가 제한된 허프변환을 수행하여 직선을 검출한다.
본 논문에서 제안되는 직선 검출 알고리즘은 두 단계로 이루어진다. 첫 번째 단계는 영상을 겹치지 않는 블록들로 나누고 PCA를 수행해 블록의 직선 모드를 결정 하면서 블록 내 에지 화소들의 직선 정보를 검출한다. 즉 에지 화소가 유효 직선 화소인지와 유효 직선 화소이면 직선 기울기를 계산한다.
본 논문은 허프변환의 문제를 개선하기 위해 2 단계 직선 검출 알고리즘을 제안한다. 첫 번째 단계에서 블록 단위로 PCA을 수행해 에지 화소의 직선 정보인 유효 직선 화소인지와 유효 직선 화소이면 직선 기울기를 결정한다. 두 번째 단계에서 검출된 직선 정보를 근거로 유효 직선 화소에 기울기가 제한된 허프변환을 수행하여 직선들을 검출한다.

대상 데이터

블록이 작으면 블록 내 직선이 짧아 검출된 직선 정보의 신뢰도가 떨어지고, 블록이 크면 블록이 다수의 직선들과 무효 직선 화소들을 포함해 검출된 직선 정보의 신뢰도가 떨어진다. PCA(allF) 블록은 블록의 에지 화소(allF)을 대상으로 PCA를 수행한다. 이때 최소 고유값 (λ_min)이 작을수록 이상적인 직선이다.

성능/효과

제안된 알고리즘에서 유효 에지 화소들만 사용하면서 직선 16, 19이 제거되고, 제한된 θ에 의해 무효 직선 화소들이 보팅에서 제외되어 직선 15, 20도 제거되고 있다.
두 번째 단계에서 검출된 직선 정보를 근거로 유효 직선 화소에 기울기가 제한된 허프변환을 수행하여 직선들을 검출한다. 제안된 알고리즘은 부가적인 계산이 요구되지만 첫 번째 단계에서 직선과 무관한 에지 화소들을 최대 50% 정도 줄여주고 두 번째 단계에서 기울기 영역 제한은 ρ 계산의 93.7%~95.4%를 줄여주고 있다. 또한 의사직선을 완전히 제거시키는 것은 물론 직선과 무관한 에지 화소를 많이 포함된 직선들의 순위를 낮추어주고 있다.
제안된 알고리즘은 예상 기울기를 이용해 제한된 영역에서 ρ를 계산하여 제안된 알고리즘의 계산량은 기존 알고리즘과 비교해 7%미만이다.
두 번째 단계에서 유효 직선 화소에서 기울기가 제한된 허프변환을 수행하여 직선을 검출한다. 제안된 알고리즘은 직선과 무관한 무효 직선 화소들의 제거와 직선 기울기제한에 의해 계산량을 줄일 뿐만 아니라 의사직선의 검출을 방지할 수 있다. 구성된 영상과 실제 영상을 대상으로 직선 검출을 수행하여 제안된 알고리즘의 유효성을 보일 것이다.

후속연구

제안된 알고리즘은 직선과 무관한 무효 직선 화소들의 제거와 직선 기울기제한에 의해 계산량을 줄일 뿐만 아니라 의사직선의 검출을 방지할 수 있다. 구성된 영상과 실제 영상을 대상으로 직선 검출을 수행하여 제안된 알고리즘의 유효성을 보일 것이다.
향후 연구는 부가적인 PCA 수행의 횟수를 감소시키는 알고리즘 개선에 대한 연구가 진행될 것이다.

질의응답

핵심어	질문	논문에서 추출한 답변
	허프 변환에서 어떠한 경우에 문제가 발생하는가?	직선 검출을 위한 대표적인 알고리즘인 허프변환은 에지 화소들에서 발생 가능한 모든 직선들의 매개변수들을 매개변수 공간으로 대응시켜 보팅(voting)하는 알고리즘으로 보팅된 매개 변수 중 요구 조건을 만족하는 매개변수를 유효 직선으로 검출한다[1-4]. 허프 변환은 직선 형태의 에지 화소로 구성된 영상에서는 이상적인 알고리즘이지만 복잡하거나 잡음을 포함하는 영상에서는 직선과 무관한 에지 화소들이 많이 생성되어 계산량을 크게 증가시킬 뿐만 아니라 의사직선 (pseudo straight line)을 생성하는 문제를 발생시킨다.
	허프변환이란 무엇인가?	직선 검출은 영역의 경계인 에지를 근간으로 허프변환 (hough transform)[3,4]에 의해 주로 수행되고 있고, 고유값(eigenvalue)[5]이나 주성분 분석(PCA)[6]을 활용한 직선 검출도 소개되고 있다. 직선 검출을 위한 대표적인 알고리즘인 허프변환은 에지 화소들에서 발생 가능한 모든 직선들의 매개변수들을 매개변수 공간으로 대응시켜 보팅(voting)하는 알고리즘으로 보팅된 매개 변수 중 요구 조건을 만족하는 매개변수를 유효 직선으로 검출한다[1-4]. 허프 변환은 직선 형태의 에지 화소로 구성된 영상에서는 이상적인 알고리즘이지만 복잡하거나 잡음을 포함하는 영상에서는 직선과 무관한 에지 화소들이 많이 생성되어 계산량을 크게 증가시킬 뿐만 아니라 의사직선 (pseudo straight line)을 생성하는 문제를 발생시킨다.
	에지 블록의 크기에 따른 특성은 어떻게 되는가?	여기서 에지는 캐니에지 검출기로 생성되고, N은 15이다. 블록이 작으면 블록 내 직선이 짧아 검출된 직선 정보의 신뢰도가 떨어지고, 블록이 크면 블록이 다수의 직선들과 무효 직선 화소들을 포함해 검출된 직선 정보의 신뢰도가 떨어진다. PCA(allF) 블록은 블록의 에지 화소(allF)을 대상으로 PCA를 수행한다.

참고문헌 (8)

R. C. Gonzalez and E. W. Richard, Digital Image Processing, 3rded. New Jersey, NJ:Prentice Hall, 2008.
C. W. Kim, H. S. Jeong and H. D. Yang, Digital Image Processing, Life & Power Co., Ltd., Paju, 2016.
R. O. Duda, and P. E. Hart. "Use of the Hough transformation to detect lines and curves in pictures," Communications of the Association for Computing Machinery, vol. 15, no. 1, pp.11-15, Jan. 1972.

상세보기
P Mukhopadhyay, and B. B. Chaudhuri, "A survey of Hough Transform," Pattern Recognition, vol. 48, no. 3, pp.993-1010, Mar, 2015.

상세보기
S. H Park, J. H. Kim and E. S. Kang, "Effective Line Detection of Steel Plates Using Eigenvalue Analysis," Journal of The Korea Institute of Information and Communication Engineering, vol. 15, no. 7, pp.1479-1486, Jul. 2011.

원문보기 상세보기
J. S. Oh, "Analysis of Straight Line Detection Using PCA," Journal of The Korea Institute of Information and Communication Engineering, vol. 19, no. 9, pp.2161-2166, Sep. 2015.

원문보기 상세보기
J. H. Kim, S. W. Lee, and S. M. Cha, "Environmental Statistics & Data Analysis, Hannarae Publishing Co., Seoul, 2016.
H. Y. Han, Introduction to Pattern Recognition, Hanbit Academy, Inc., Seoul, 2015.

저자의 다른 논문 :

표제어: PCR

동의어: Packet Collision Rate

용어 설명 출처 목록 (6)

용어 설명: PCR은 세균 특이성이 있는 primer를 이용하여 적은 수의 세균이 있을지라도 쉽게 검출할 수 있는 유용한 방법이며, 이를 이용하여 구강 내 치면세균막이나 타액에서 직접 세균을 검출할 수 있게 되었다[8].

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증