Line & Ellipse detection

 

 

선형패턴 vs. Ellipse 패턴

선형패턴은 주로 인공적인 물체(책상)등에 나타남

ellipse는 자연물체 (꽃)

 

 

cluttered background:

배경에 잡음이 많이 섞여있는 그림

 

 

여러그림을 이어붙이는 방법

공통의 점이나 선을 연결하여 overlap되는 부분에서 이어붙임

--> 공통의 점이나 선을 찾아야함

--> line fitting이 필요한 이유

 

 

line fitting의 어려움

1. 실제로는 직선이더라도 사진찍는 각도에 의해 사선으로 사진에서는 표현됨

2. 끊긴것처럼 사진에서는 나타날 수 있음

3. cluttered background

--> 해결책 voting/RANSAC(voting이 더좋음)

 

 

Voting방법

line fitting을 하기 위해서 두점을 이어야 하는데

모든 점의 조합을 보기에는 너무 많음

--> Look for model parameters that receive a lot of votes.

 

 

RANSAC

Random Sample Consensus

 

1. Estimate the best line

 

2. Compute transformation(fitting시킴) from seed group

3. Find inliers to this transformation

4. If the number of inliers is sufficiently large, recompute least-squares estimate of transformation on all of the inliers

 

 

RANSAC에서 얼마나 많이 수행해야하는가?

아래 표에서 50%정도의 outlier가 있을 때,

n(8개)의 sampling을 할경우(직선일경우는 2개), 99%의 정확도로 맞추려면

총 k=1177번의 수행을 해야하는 것을 경험적으로 실험하여 표로 나타낸 것

 

참고로, w만큼의 비율로 inlier가 있을 때

모두 inlier만 뽑는 확률은

k번했을때 모두 실패할 확률은 

 

 

RANSAC의 장단점

장점: 일반적인 분류모델에 잘 맞는다, 실패율을 계산하기 쉽다

단점: outlier의 비율이 많아지면 많아질 수록 적용이 어렵다.

--> 해결책: voting or Hough transform 

 

 

 

Hough Transform사용 예

1. object detection

--> correlation mask를 사용하게 되면 zoom/distortion된 이미지에서는 잘 안맞는 경우가 있음

--> 해결책: Hough Transform(robust함)

2. Circle detection

3. Straight lines and curves detection

 

 

Hough tranform - straight line detection

voting이 가장 많이 된 곳이 검은 점으로 표현된 것

accumulator를 통해 voting이 많이 된것을 검출할 수 있음

line detection은 2차원 accumulator에 voting을 함

원점에서 선까지의(edge direction방향) 수직인 거리와 theta값을 활용하여 2차원을 구성함

** accumulator : parameter 들의 space

** line detection에서는 선분이 무한대가 될 수 있으므로, constrained parameter space를 해줘야함

** parameter 표현도, s와 theta값으로 표현함

 

Hough tranform - circle detection

circle detection은 3차원(Xc, Yc, 반지름) accumulator에 voting을 함

원에서는 중심점(Xc, Yc)과 반지름을 찾아야 함

보통 반지름은 어느값일 것이라고 가정하고 시작함

 

 

 

타원의 특성을 통해 타원전체 검출하기

타원이 일부분을 찾는다면

 

1. 타원테두리의 두점을 연결한 선분2개의 가운데점을 연결하면 중심으로 이어짐

2. 타원의 한 호를 찾는다면 중점으로 대칭이 되므로 전체 검출할 수 있음 

 

 

Ellipse detection process

1. edge detection 

2. arc detection - delete noise & arc labeling

3. arc quadrant classification - assign quadrant label

4. arc selection

5. parameter estimation

6. validation

 

 

Ellipse detection 할때 어려운 점

1. incomplete edges(검출 오류로 edge detection이 완전하게 안됐을 때)

2. imperfect edges(깨지거나 crack이 있을 때)

3. Occlusion

4. Partial view 

5. Digitization 

6. Speed

7. Outlier edges

 

 

Arc detection하는 프로세스

1. arc labeling

 

방법1. CCA: Connected component analysis 수행

방법1.

처음을 다 1로 세팅

연결되는 것이 있으면 2로 update

끊기고 그다음으로 연결되면 3이렇게 계속 update하는 것

--> 단점. 오래걸림

 

방법2. 

sliding window를 통해서 CCA를 찾는 방법

단, drawback으로 표현되는 문제점이 발생할 수 있음

방법2.

 

2. Removing straight edges

arc detection이므로 직선 edge는 제외

위조건에 만족하면 직선이라고 간주

3. Removing small edges

4. Removing edges with sharp turns

 

 

 

Arc quadrant classification : find arc gradient

x, y가 증가하는 방향을 확인해서 어느 호인지를 결정

D(arc)

 

 

Arc quadrant classification : find arc convexities

 

 

Arc quadrant classifcation : assign quadratic labels

 

 

Arc selection rules

• Rule I: Decide number of arcs to select
– ellipse 정의하기 위해서는 최소 2개의 호가 필요함
• Rule II:
– Select arcs having different quadratic levels
• Rule III: Use prior information
– E.g.; If an approximate size of an ellipse is known, then select arcs
that fall under the possible geometrical positions
• Rule IV: Find the center of ellipse as given in next slides
– Select arcs, if the centers computed by the two methods coincide
or are appear within some threshold distance

 

 

Parameter estimation

타원형의 일반적 공식

x*y텀까지 있음

위 공식들을 통해, center좌표, 타원의 축, 각도등의 값을 구하고

그것을 나중에 clustering할때 사용함

 

 

성능계산 공식

€1은 정답, €2는 검증결과

 

D>0.8라면 detection의 결과가 True positive라고 한다.

 

 

 

본 내용은 서강대학교 영상인식시스템 수업을 정리한 내용입니다.