허프 변환을 이용한 이미지 내 원 검출 알고리즘 구현
- openCV 등의 외부 라이브러리 사용 x
- 연산량, 메모리 사용량, 실행 시간 관점을 고려한 고속 알고리즘
- 직선 검출과 같은 방식으로 구현시 (x,y,r)로 3차원 좌표 필요
-
$O(N^3)$ 의 메모리, 시간 소요로 프로그램이 무거워짐
-
- 원 위 임의의 점에서 접선과 수직인 직선은 원의 중심을 반드시 지나는 수학적인 성질 이용
- Canny edge detection 과정에서 구한 gradient를 이용, gradient 방향으로 직선을 누적하면서 vote
- 화소는 이산적인 위치이므로 특정 범위 이내에 가장 vote가 많이 된 점을 중심으로 채택
- 중심을 고정하면 r 차원에 대한 값만 찾으면 완료
-
$r \leq H,W$ 이므로$O(N^2)$ 의 시간/공간 복잡도로 원 검출 가능
-
- 직선 검출과 같은 방식으로 구현시 (x,y,r)로 3차원 좌표 필요