CV ‐ 4. Line patterns - waegari/waegari.github.io GitHub Wiki

컴퓨터 비전: 라인 패턴 및 타원 검출

1. 라인 검출 (Line Detection)

line fitting의 어려움

  • 클러터(Clutter) 문제: 불필요한 에지 포인트들이 존재
  • 다중 모델(Multiple models): 여러 선이 존재할 때 어느 점이 어느 선에 속하는지 결정 어려움
  • 불완전한 데이터: 선의 일부만 감지되고 일부는 누락됨
  • 노이즈: 측정된 에지 포인트와 방향에 노이즈 존재

Voting 기법

  • 특징점들이 호환 가능한 모든 모델에 투표하는 일반적 기법
  • 특징점들을 순환하며 호환 가능한 모든 모델 파라미터에 투표
  • 많은 투표를 받은 모델 파라미터를 찾음
  • 노이즈가 있는 특징점도 투표하지만, "좋은" 특징점들의 다수 투표와 일치하지 않음
  • 일부 특징점이 관찰되지 않아도 모델이 여러 조각을 포괄할 수 있음

RANSAC (RANdom SAmple Consensus)

  • 핵심 원리: 이상치(outlier)의 영향을 피하기 위해 "내부점(inlier)"만 찾아 사용

  • 알고리즘 단계:

    1. 무작위로 seed 포인트 그룹 선택
    2. 선택된 그룹으로 변환(모델) 계산
    3. 이 변환에 대한 내부점(inlier) 찾기
    4. 내부점 수가 충분히 많으면, 모든 내부점으로 최소제곱 변환 재계산
    5. 가장 많은 내부점을 갖는 변환 유지

  • 필요한 샘플 수 결정:

    • w = 내부점 비율 (선에 속한 점의 비율)
    • n = 가설 정의에 필요한 점 수 (선의 경우 2)
    • k = 선택한 샘플 수
    • 단일 샘플링에서 모든 n개 점이 올바를 확률: w^n
    • 모든 k 샘플링이 실패할 확률: (1-w^n)^k

  • RANSAC 이후:

    • 최소 내부점 집합에서 계산된 추정치 개선
    • 모든 내부점으로 추정치 개선 (표준 최소제곱 최소화 사용)
    • 내부점이 변경될 수 있으므로 피팅과 내부점/이상치 재분류를 번갈아 수행

  • 장점: 다양한 모델 피팅 문제에 적합, 구현 쉬움, 실패율 계산 용이

  • 단점: 이상치 비율이 높으면 비용 증가, 고율의 이상치를 처리하기 어려움

Hough Transform

  • 목적: 높은 비율의 이상치를 처리할 수 있는 투표 전략

  • 직선 검출 방법:

    • 직선 방정식: y = mx + b (매개변수 공간 [m,b]는 무한)
    • 극좌표 표현 사용: x·cos θ + y·sin θ = ρ
    • 특징(에지 포인트)이 파라미터 공간에 투표
    • 많은 투표를 받은 파라미터 값 찾기

  • 구현 방법:

    • 파라미터 공간: 이산화(discrete)
    • 에지 검출 및 임계값 처리
    • Accumulator array/cell 사용
    • 제한된 파라미터 공간

  • 원 및 타원 검출에도 적용 가능

2. 타원 검출 (Ellipse Detection)

타원 검출 알고리즘 개요

  • 모든 타원 검출 알고리즘은 이미지의 에지 포인트를 사용하여 타원의 중심 찾기
  • 타원 속성: 평행한 현(chord)의 중점들과 타원의 중심은 일직선상에 있음
  • 평행한 현 집합은 주로 Hough Transform으로 찾음

타원 검출 파이프라인

1. 에지 검출 (Edge Detection)

  • Canny나 Sobel 같은 에지 검출 방법 사용
  • 에지 검출 임계값이 결과 효율성에 중요한 역할
    • 높은 임계값: 노이즈 적지만 inlier 에지도 적어짐 → 낮은 타원 검출률
    • 낮은 임계값: 많은 노이즈와 많은 inlier/outlier 에지 → 낮은 정밀도

2. 아크 검출 (Arc Detection)

  • 아크 라벨링: 각 아크에 고유 ID 할당 → 동일한 아크에 속하는 픽셀에 동일 ID 부여
  • 노이즈 에지 제거:
    • 직선 에지 제거: Δy=0, Δx=0, Δy/Δx = 상수인 아크 제거
    • 작은 에지 제거: 같은 ID를 가진 픽셀 수 적으면 제거
    • 급격한 회전이 있는 에지 제거

3. 아크 사분면 분류 (Arc Quadrant Classification)

  • 아크 그라디언트 찾기: D(arc^m) = sign(Δy)·sign(Δx)

  • 아크 볼록성 찾기:

    • 아크를 사각형으로 둘러싸기
    • 아크 아래 영역(U)과 위 영역(O) 넓이 찾기
    • C(arc^m) = { Upper Convex(+) if Area(U) > Area(O), Lower Convex(-) if Area(O) > Area(U) }
    • Area(U) = Area(O)면 직선이므로 해당 아크 폐기

  • 사분면 라벨 지정:

    Q(arc^m) = {
  I if D(arc^m) = (+) and C(arc^m) = (+)
  II if D(arc^m) = (-) and C(arc^m) = (+)
  III if D(arc^m) = (+) and C(arc^m) = (-)
  IV if D(arc^m) = (-) and C(arc^m) = (-)
}

4. 아크 선택 (Arc Selection)

  • 타원을 형성할 가능성 있는 아크 선택 규칙 정의:
    • 규칙 I: 아크 선택 수 결정 (최소 2개 아크 필요)
    • 규칙 II: 다른 사분면 레벨을 가진 아크 선택
    • 규칙 III: 사전 정보 활용 (예: 알려진 타원 크기)
    • 규칙 IV: 두 방법으로 계산된 중심이 일치하거나 임계값 거리 내에 있는 아크 선택

5. 파라미터 추정 (Parameter Estimation)

  • 타원 속성을 이용한 중심 추정:

    • 평행 코드의 중점과 타원 중심은 동일선상에 있음
    • 평행선 쌍 생성, 중점 찾기, 기울기 계산 후 중심 계산

  • 아크에 타원 피팅으로 중심 추정:

    • 타원 방정식 풀이: ax² + bxy + cy² + dx + ey + f = 0
    • 중심 계산: x₀ = (cd-be)/(2(ae-b²/4)), y₀ = (ae-bd)/(2(ae-b²/4))
    • 반축 길이와 회전 각도도 계산 가능

6. 검증 (Validation)

  • 결과 타원이 선택된 아크들에 잘 맞는지 확인
  • 피팅 오차 계산
  • 피팅 오차가 임계값보다 크면 타원 폐기

7. 클러스터링 (Clustering)

  • 다중 유효 검출 처리
  • 중심 간 거리, 축, 회전 비교하여 유사 타원 클러스터링
  • 최종 타원 결정 방법:
    • 클러스터 내 모든 타원 평균화 또는
    • 최대 피팅 점수를 가진 클러스터 내 타원 선택

타원 검출의 어려움

  • 불완전한 에지
  • 불완전한 에지
  • 가림 현상(Occlusion)
  • 부분 뷰(Partial view)
  • 디지털화(Digitization)
  • 속도
  • 이상치 에지(Outlier edges)

핵심 암기 사항

  1. RANSAC 알고리즘 단계 및 샘플 수 계산 방법

    • 특히 내부점/이상치 계산법과 확률 공식 (w^n, (1-w^n)^k)

  2. Hough Transform의 원리와 극좌표 표현

    • x·cos θ + y·sin θ = ρ 방정식과 투표 매커니즘

  3. 타원 검출 파이프라인의 7단계

    • 각 단계별 핵심 계산식과 방법

  4. 아크 사분면 분류 방법

    • 그라디언트와 볼록성 계산 방식
    • 사분면 라벨 지정 규칙

  5. 타원 중심 추정 두 가지 방법

    • 타원 속성 이용 방법과 타원 피팅 방정식

  6. 타원 파라미터 계산 공식

    • 중심 좌표, 반축 길이, 회전 각도 계산식

  7. 타원 검출 성능 평가 지표

    • Precision, Recall, F-measure 계산법
    • XOR과 OR 연산 기반 유사도 측정법