Advanced
Interval Hough Transform For Prominent Line Detection
Interval Hough Transform For Prominent Line Detection
Journal of Korea Multimedia Society. 2013. Nov, 16(11): 1288-1296
Copyright © 2013, Korea Multimedia Society
  • Received : August 31, 2013
  • Accepted : October 01, 2013
  • Published : November 30, 2013
Download
PDF
e-PUB
PubReader
PPT
Export by style
Share
Article
Author
Metrics
Cited by
TagCloud
About the Authors
진모 최
전자부품연구원 소프트웨어 디바이스 센터
창익 김
한국과학기술원 전기전자공학부

Abstract
단일 영상에서 배경선은 공간 구조를 이해하거나 심미적 평가를(Aesthetic scoring) 내리는데 중요한 판단 기준이 된다. 본 논문에서 소개하는 배경선 추출은 소실점을 분석하거나 3차원 공간의 재구성, 영상의 기울어짐을 판단하는데 도움을 준다. 또한 삼등분 법칙(Rule of thirds)을 계산하는데도 용이하게 해준다. 본 논문은 크게 구간 허프 변환 매핑과 배경선 우선순위 결정, 배경선 선택으로 구성되어 있으며 각 기술은 차선 추출이나 건물 구조 분석, 소실점 추출, 문서의 직선 추출과 같은 다양한 분야에 응용될 수 있게끔, 기술이 세분화되어 있다. 이는 사용자가 객체의 특성과 조명 환경등을 고려하여 선택적으로 기술을 구성할 수 있게끔 해준다. 본 논문에서 소개하는 방법은 허프 변환을 사용하는 만큼, 원 추출과 같은 허프 변환의 응용에도 적용될 수 있다. 구간 허프 변환은 추출하고자 하는 배경선의 개수를 설정할 수 있다. 또한 영상 내에서 중요한 배경선의 개수를 분석하여 중요한 배경선만을 추출할 수 있다. 본 논문은 실험결과를 통해 배경선 추출결과를 볼 수 있다.
Keywords
1. 서 론
단일 영상에서 배경선은 공간 구조를 이해하는데 중요한 요소 중에 하나이다. 배경선 추출은 소실점을 분석하는데 이용되며 3차원 공간 재구성, 영상의 기울어짐을 판단하는데 사용된다. 또한 영상의 구도를 이해하는데도 사용된다.
본 논문은 다양한 환경에서 효율적으로 배경선을 추출하기 위한 전략을 설명한다. 이를 위해 구간 허프 변환 매핑, 배경선 우선순위 결정, 배경선 선택과정이 수행된다. 구간 허프 변환 매핑은 관심 대상 선택과 Edge 추출, 배경선 추출 과정으로 이루어지며 각 과정은 관심 대상 및 응용 분야에 따라 세부 기술이 변경된다. 이에 대해서는 본문에서 소개한다.
2. 관련 연구
영상으로부터 공간 정보를 추출하는 방법은 Stereo Vision, Depth Image, 단일 영상의 구조 분석 등이 있다. Stereo Vision은 복수의 카메라의 시점 차이를 이용하는 방법이며, Depth Image는 Time of Flight 나 Infrared Pattern 등을 이용하는 방법이다. 반면 단일 영상의 구조 분석은 영상을 구성하는 특징 정보를 이용하는 방법이다.
공간 구조를 분석하는데 사용되는 특징 정보는 소실점이나 배경선 등이 있으며 이를 이용하여 차선을 추출 [1 , 2] 하거나 기울어지고 왜곡된 사진을 수성시키거나, 영상의 일부 영역을 Retargeting [3] 하는 등 다양한 분야에 사용될 수 있다.
PPT Slide
Lager Image
단일 영상에서 공간 구조 분석의 예
영상 내에 직선 선분은 공간 구조를 분석하는데 유용하다. 직선 선분의 교점은 소실점의 후보로써 원근감의 기준점이 된다. 그러나 자연 영상의 일반적인 선분은 어느 정도 휘어짐을 가지며 직선으로 이루어진 각 픽셀의 방향 정보는 직선의 기대 값과 일치하지 않는다.
논문 [1] 은 Gabor Wavelet Kernel을 이용하여 소실점을 추출하였다. 이후 소실점과 Canny Edge 사이의 방향정보를 이용하여 차선을 추출한다. 이는 Edge 자체의 방향 정보를 신뢰하지 못하기에 대안책으로 소실점과 Edge 사이에 가장 많이 겹치는 직선선분을 추출한 것이다. 논문 [2] 는 차선의 Edge 선분을 논문 [1] 에 비하여 적극적으로 사용한다. 그러나 추출된 Edge의 방향 정보는 사용되지 않는다.
본 논문은 Edge의 방향 정보를 이용하여 배경선을 추출하는 방법을 설명한다. 이를 위해 안정적인 방향 정보를 추출하는 전략에 대해서도 설명한다. 이는 기존의 방법에 비하여 강건한 소실점 추출이 가능하다.
3. 구간 허프 변환
구간 허프 변환은 크게 3단계로 구성된다. 첫 번째 단계는 구간 허프 변환에 매핑하는 과정으로 관심 대상 선택, Edge 추출, 배경선 추출 과정으로 이루어진다. 첫 번째 단계에서 추출된 배경선은 Scoring 단계를 거쳐 배경선의 중요도를 계산한다. 이중에 임계 값을 넘는 배경선만을 최종 배경선으로 선택한다.
PPT Slide
Lager Image
구간 허프 변환 흐름도
- 3.1 구간 허프 변환 매핑
구간 허프 변환 매핑은 관심 대상 선택, Edge 추출, 배경선 추출과정으로 이루어진다. 관심 대상 선택은 차후 과정인 Edge 추출에서 보다 노이즈에 강건한 정보를 추출하기 위해 입력 영상을 변화시키는 과정이다. 본 논문에서는 색차 거리 측정을 위한 CIE Lab color 변환과 칼라 기반 이진화, Decolorize에 대해 설명한다. 각 변환은 다음과 같은 특징을 가지고 있다.
색차 거리 측정은 국제조명위원회(CIE)에서 정의한 CIE Lab color 모델에 의해 이루어진다. CIE Lab color 모델은 명도를 나타내는 L=[0, 100]과 Red와 Green의 정도를 나타내는 a, Yellow와 Blue의 정도를 나타내는 b로 구성되어 있다.
각 관심 대상 선택 기술의 장단점
PPT Slide
Lager Image
각 관심 대상 선택 기술의 장단점
PPT Slide
Lager Image
CIE Lab color 모델
RGB모델에서 CIE Lab Color 모델로의 변환은 그림 4 와 같이 정의된다. 모든 색상에 대하여 플로팅 연산을 하게 되므로 CIE Lab Color모델은 영상 변환에 높은 비용을 요구한다. 그러나 CIE Lab Color모델은 인간의 눈이 감지할 수 있는 색차와 색공간좌표를 적용하여 만든 Color 모델이기 때문에 Edge의 크기 값과 방향 정보에 대하여 높은 구분 능력을 보여준다. 두 색상 간에 L의 차이를 Δ L * 이라고 정의하고 a의 차이를 Δ a * 라고 정의하며 b의 차이를 Δ b * 라고 정의할 경우 색차 Δ E * 는 다음과 같이 정의 된다.
PPT Slide
Lager Image
RGB에서 CIE Lab color 모델로 변환
PPT Slide
Lager Image
PPT Slide
Lager Image
PPT Slide
Lager Image
PPT Slide
Lager Image
색차 정보는 이후, Edge의 크기값으로 사용된다.
칼라 기반 이진화는 관심 객체의 색상을 일반화 할 수 있는 경우에 사용된다. 예를 들어 “붉은” 신호등이나 “푸른”하늘과 같은 경우이다. 또는 차선을 추출할 경우에, “검은 색이 아닌” 면적 등으로 나타낼 수 있다. 이와 같은 방법은 관심 객체와 비관심 객체의 이분화가 비교적 잘 이뤄지는 환경에서 사용해야 한다.
본 논문에서 소개하는 칼라 기반 이진화는 CIE Lab Color 공간과 K-NN(K-nearest neighbor)을 이용하여 휴리스틱하게 구성한다. 전체적인 흐름도는 그림 5 와 같다.
PPT Slide
Lager Image
칼라 기반 이진화 흐름도
칼라 기반 이진화 학습부는 CIE Lab Cell(이하 Lab Cell)을 구성하는 것으로부터 시작한다. Lab Cell은 Lab 공간을 L축과 a축, b축을 균등하게 나눈 것이다. 예를 들어, L축을 8등분하고 a축을 8등분하며 b축을 8등분하면 총 512(8×8×8)개의 Cell이 완성 된다. Lab공간 내에서의 Cell은 각 Cell간에 색차가 균등하므로 각 Cell의 중심값은 이진화될 수 있다. 즉, 각 색상을 c 라고 정의할 경우에 n 개의 색상에 대한 cn 은 1과 0으로 구분될 수 있다.
본 논문은 칼라 기반 이진화의 학습기로 K-NN classifier를 선택했는데 이 때 K의 값은 1로 설정하였다. 즉, Cell의 중심값에 대한 RGB 값과 실험 대상이 되는 RGB 값 사이의 유클리디안 거리로 클러스터링이 이루어지는 것이다. 실험 대상이 되는 RGB 값과 가장 가까운 Cell의 중심값이 1일 경우에는 실험 대상의 RGB는 1이 되며, 0일 경우에는 실험 대상의 RGB는 0이 된다. 이와 같이 클러스터링 된 RGB 이진화 값은 Cell의 개수에 반비례하여 잘못 분류된 값이 생성된다. 이를 해결하기 위하여 중심값을 휴리스틱하게 추가한다. 완성된 이진화 Table은 검출부에서 적은 연산 비용으로 색상 정보 이진화에 사용된다.
Decolorize는 색상정보를 이용하여 enhance된 흑백 영상을 구성하는 방법이다. 크게 Color enhancement 이후에 흑백 영상으로 전환하는 방법과 color 정보를 직접 사용하여 enhance된 흑백 영상을 추출하는 방법이 있다.
본 논문은 Decolorize를 위해 power transform을 사용하는 방법은 피했다. power transform을 이용한 방법은 색상 정보를 효율적으로 enhance시키는 장점이 있지만 매우 높은 연산량을 요구한다. 대신에 YPQ 칼라 모델을 이용하여 Chrominance 및 Saturation 정보로 enhance 시키는 방법을 사용하였다. 이는 실시간 환경에 적합한 모델이다 [4] .
PPT Slide
Lager Image
칼라 기반 이진화에 의한 후미등 추출 예
Edge의 크기와 방향성을 추출하기 위하여 본 논문은 HOG(Histograms of Oriented Gradients)의 Cell추출 방법과 Canny filter의 Non-maximum suppression방법을 사용하였다.
HOG는 Edge의 크기와 방향정보를 추출하기 위하여 그림 7 의 (b)와 같은 mask를 사용한다. Gx x 방향의 크기값이고 Gy y 방향의 크기값이다.
PPT Slide
Lager Image
Ridge 정보 추출
그림 7 의 (b)와 같은 mask가 Sobel이나 Prewitt, Robert mask보다 방향 정보를 더 잘 표현하는 이유는 Ridge정보를 더 잘 표현하기 때문이다. Edge drawing [5] 이나 Histograms of Oriented Gradients for Human Detection [6] 는 Edge를 추출할 때 Ridge의 중요성에 대하여 잘 묘사하고 있다. 본 논문은 조금이라도 더 Ridge정보를 정확하게 추출하기 위하여 그림 (c)와 같이 최대한 mask의 중심으로부터 가까운 픽셀만을 사용하였다.
본 논문은 Edge를 추출할 때 논문 [7] 과 같이 별도로 Edge의 방향정보를 안정화시키기는 작업을 하지 않는다. 반면에 논문 [6] 과 같이 그림 7 의 (b)의 마스크에만 의존하지도 않는다. HOG에서 사용하는 mask는 mask의 중심부와 측정하고자 하는 픽셀의 거리가 가까운 만큼 노이즈에 취약하다. 이는 Robert mask의 단점이기도 하다. 그렇기에 Edge정보를 추출하기 전에 Gaussian smoothing 작업을 수행한다 [8] .
그림 8 은 Edge 추출 과정의 흐름도이다. Edge의 크기값과 방향 정보 추출은 다음과 같이 이루어진다.
PPT Slide
Lager Image
Edge 추출 흐름도
PPT Slide
Lager Image
PPT Slide
Lager Image
Edge를 추출하는 과정은 mask를 Sobel 대신 HOG mask를 사용한다는 점을 제외하고 Canny filter의 과정과 동일하다. Non-maximum suppression은 Edge의 방향정보를 4방향의 대표 방향 정보로 라운딩시킨 다음에 이웃 기울기 크기값과 비교하여 클 경우만을 Edge로 만드는 작업이다. 예를 들어 현재 위치의 기울기 방향정보가 5일 경우에는 0값으로 라운딩되고 기울기 방향정보가 42일 경우에는 45로, 기울기 방향정보가 87일 경우에는 90으로, 기울기 방향정보가 133일 경우에는 135로 라운딩 된다. 이와 같이 라운딩 된 기울기는 다음조건에 의하여 Thinning 작업이 이루어진다.
• 라운딩 된 기울기의 방향 정보가 0일 경우, 왼쪽과 오른쪽의 기울기 크기값보다 큰 경우에만 Edge로 선정
• 라운딩 된 기울기의 방향 정보가 45일 경우, 남서쪽과 북동쪽의 기울기 크기값보다 큰 경우에만 Edge로 선정
• 라운딩 된 기울기의 방향 정보가 90일 경우, 위쪽과 아래쪽의 기울기 크기값보다 큰 경우에만 Edge로 선정
• 라운딩 된 기울기의 방향 정보가 135일 경우, 북서쪽과 남동쪽의 기울기 크기값보다 큰 경우에만 Edge로 선정
Edge Tracking은 두 개의 임계값에 의하여 확실한 Edge만을 추출하는 작업이다. 높은 임계값을 만족시키는 Edge중에서 연결성이 보장된 낮은 임계값을 만족시키는 Edge만을 선별하는 작업이다. Edge Tracking은 추출하고자 하는 객체가 정규화 될 경우에 유효한 방법이다. 특히 본 논문에서 소개하는 배경선 추출방법은 영상 내에서 강한 Edge 크기값을 가지는 순서대로 배경선을 추출하기 때문에 Edge Tracking의 전재가 유효하다.
그러나 본 논문의 Edge 추출 방법은 Edge Tracking을 객체의 특성이나 환경에 따라 선별적으로 선택하게끔 구성했다. 이는 다양한 조명 환경과, 객체의 속성에 따라 기울기의 크기값을 정규화하기 어려운 경우를 고려했기 때문이다.
다음은 배경선 추출과정이다. 본 논문은 허프 변환을 기반으로 배경선을 추출한다. 그러나 기존의 허프 변환과 다르게 본 논문에서 소개하는 방법은 Edge의 방향정보를 이용하여 허프맵의 셀에 누적시킨다.
기존의 허프 변환이 Edge의 방향정보를 이용하여 각 셀에 해당 정보를 누적시키지 않은 이유는 그림 9 와 같이 Edge의 방향 정보가 안정화되지 않기 때문이다. 그러나 본 논문은 Edge의 방향정보를 최대한 활용하기 위하여 Edge추출단계에서 HOG mask를 사용하였다. 또한 그림 10 과 같이 방향 정보의 기대 값을 정의하여 Edge의 방향정보에 대한 신뢰도를 높였다.
PPT Slide
Lager Image
수평 Edge의 방향 정보
PPT Slide
Lager Image
허프 변환과 구간 허프 변환의 비교
허프 변환은 한 픽셀에 대하여 0°≤ θ < 180°내의 모든 각을 고려하여 허프맵의 각 Cell에 누적시킨다. 이는 방향정보를 고려하지 않음으로써 노이즈 정보도 누적된다는 뜻이다. 반면 구간 허프 변환은 Edge 로부터 방향 정보 θ' 를 구한 이후에 ± α 범위 내에서만 방향정보를 Cell에 누적시킨다. 즉 θ' 는 현재 픽셀의 방향정보에 대한 기대값이다. ω ( θ )는 θ 에 대한 가중치로 가우시안 분포를 띄며 ω min 은 최소 가중치이고 ω max 는 최대 가중치이다. ω ( θ )는 방향정보에 대한 기대값 θ' 에서 최대 가중치값을 갖는다.
그림 11 은 배경선 추출과정을 나타낸 그림이다. 허프맵에서 최대값을 가지는 선분을 추출한 이후에 해당 선분과 관련된 Cell값을 허프맵에서 삭제한다. 위 방법은 원하는 개수의 배경선이 추출될 때까지 재귀적으로 반복된다.
PPT Slide
Lager Image
배경선 추출 과정
- 3.2 배경선 우선순위 결정 및 배경선 선택
추출된 배경선은 허프맵에 누적된 픽셀 정보를 이용하여 공간 도메인상의 Edge를 재구성시킬 수 있다. 그림 12 는 Edge를 재구성한 결과를 나타낸 그림이다. 이와 같이 재구성된 Edge는 기울기 값이나 Texture 등을 이용하여 배경선 사이의 우선순위를 결정하는데 사용된다. 본 논문은 Edge 추출에 사용된 기울기 값을 이용하여 배경선의 우선순위를 결정하였다. 또한 중요도가 떨어진다고 생각되는 배경선이 있을 경우에는 배경선에서 제외시켰다. 예를 들어 입력 영상에서 10개의 배경선을 추출했는데 그 중에서 5개만이 배경선을 판단하는 임계값을 넘을 경우에 5개의 배경선만을 선택하였다.
PPT Slide
Lager Image
배경선 우선순위 결정 및 배경선 선택
4. 실험 결과
본 논문에서 사용한 실험결과는 모두 동일한 세부기술과 임계값에 의한 결과이다. 관심 대상 선택에서는 Decolorize 방법을 선택하였으며 Edge 추출과정에서는 Edge tracking을 사용하였다. 허프맵에 사용된 Angle cell은 0° ≤ θ < 180°이며 거리 cell은 영상의 대각선 거리에 2를 나눈 값을 사용하였다. 방향정보 구간은 α = 18°로 정의했으며 배경선은 15개를 추출하여 그 중에서 중요한 배경선이라고 판단된 값만을 선택하였다
PPT Slide
Lager Image
5. 결 론
단일 영상에서 배경선은 공간 구조를 이해하거나 심미적 평가를 내리는데 중요한 판단기준이 된다.
본 논문은 배경선을 추출하기 위하여 구간 허프변환 매핑과 배경선 우선순위 결정, 배경선 선택에 대하여 정의하고 이에 대해 설명하였다. 또한 본 논문에서 사용하는 기술은 다양한 환경에 적용될 수 있도록 기술을 세부적으로 나누었다. 본 논문에서 소개하는 기술은 배경선 추출에 의미 있는 결과값을 도출하였다. 향후, 목표로는 심미적 영상 재구성 및 객체 추출에 위 기술을 응용하는 것이다.
BIO
최 진 모
2003년 2월 한양대학교 전자컴퓨터공학부 학사 졸업
2005년 8월 한양대학교 컴퓨터공학과 석사 졸업
2011년 8월~2013년 8월 전자부품연구원 연구원
관심분야 : 영상처리, 패턴인식
김 창 익
1989년 2월 연세대학교 전기공학과 학사 졸업
1991년 2월 포항공대 전자전기공학과 석사 졸업
2000년 12월 워싱턴 대학교 전기공학과 박사 졸업
2009년~현재 카이스트 대학교 전기공학과 부교수
References
Zhou Shengyan , Jiang Yanhua , Xi Junqiang , Gong Jianwei , Xiong Guangming , Chen Huiyan 2010 “A Novel Lane Detection based on Geometrical Model and Gabor Filter” Intelligent Vehicles Symposium 59 - 64
Wang Yue , Teoha Eam Khwang , Shen Dinggang 2004 “Lane Detection and Tracking using B-Snake” Image and Vision Computing 22 (4) 269 - 280    DOI : 10.1016/j.imavis.2003.10.003
Liu Ligang , Chen Renjie , Wolf Lior , Cohen-Or Daniel 2010 “Optimizing Photo Composition” EUROGRAPHICS 29 (2) 469 - 478
Grundland M , Dodgson NA 2007 Decolorize: Fast, Contrast Enhancing, Color to Grayscale Conversion Elsevier http://www.elsevier.com/
Topal C , Akinlar C 2010 “Edge Drawing: A Heuristic Appoach to Robust Real-time Edge Detection” ICPR 2424 - 2427
Dalal N , Triggs B 2005 “Histogram of Oriented Gradients for Human Detection” CVPR 1 886 - 893
Ben-Shahar O , Zucker SW 2003 “The Perceptual Oraganzation of Texture Flow” PAMI 25 (4) 401 - 417    DOI : 10.1109/TPAMI.2003.1190568
신 충호 2009 멀티미디어학회논문지 12 (2) 191 - 199
송 주호 , 박 제훈 , 김 은주 , 김 선정 , 송 창근 2010 한국멀티미디어학회 추계학술발표대회 논문집 13 (2) 439 - 441