- 허프 변환 알고리즘은 영상에서 선을 감지하기 위해 개발했고, 다른 간단한 영상 구조 감지로 확장할 수 있다.
- 허브 변환은 다음 방정식을 사용해 직선을 표현.
- Θ : 선에 대한 수직 각도.
- 식에서 영상 내에 보이는 선은 0과 π(파이) 라디안 사이의 각도인 Θ를 갖고,p 반지름은 영상 대각선의 길이와 같은 최대값을 갖는다.
- 다음 선 집합을 보았을 때
- 1인 선인 수평선은 0과 동일한 Θ 각도 값을 갖고, 수평선(5인 선)은 π/2와 동일한 Θ 값을 갖음.
- 즉, 3인 선은 π/4와 동일한 각도 Θ를 갖고, 4인 선은 0.7π에 가깝다.
- 가능한 모든 선을 [0, π] 범위에 있는 Θ로 표현하기 위해서는 반지름 값을 음수로 만들 수 있음.
- 2인 선의 경우에는 p가 음수 값으로서 값이 0.8π와 동일.
- OpenCV는 선을 감지하기 위한 두 가지 허프 변환을 제공.
- 기본 버전은 cv::HoughLines 이다.
- 입력은 점집합(넌제로 화소로 표현)을 포함하는 이진 맵이고, 일부는 선 형태로 정렬. (에지 맵에서 캐니 연산자로 얻는다.)
- cv::HoughLines 함수의 결과는 cv::Vec2f 요소의 벡터로, 부동소수점 값의 각 쌍은 감지된 선 (p, Θ)의 파라미터를 표현.
- 즉, 영상 외곽선을 얻기 위해 먼저 캐니 연산자를 적용한 곳에 허프 변환을 이용해 선을 감지.
std::vector<cv::Vec2f> lines;
cv::HoughLines(contours, lines,
1,PI/180, // 단계별 크기
80); // 투표(vote) 최대 개수
- 3, 4번째 파라미터는 선을 찾기 위한 단계별 크기에 해당.
- 예제에서 이 함수는 1과 π/180에서 단계별로 가능한 모든 각도로 반지름의 선을 찾음.
- 마지막 파라미터는 다음 절에서 설명.
- 특정 파라미터 값으로는 이전 절의 도로 영상에서 열다섯 개의 선을 감지.
- 이 알고리즘은 영상 내의 선을 감지할 뿐 각 선의 마지막 점이 부여되지 않은 상태에서 선을 분할할 수 없다. (따라서 영상 전체를 가로지르는 선을 그림)
- 대부분 수직선에 대해 영상의 수평 한계(처음과 마지막 행)와 교차하는 부분을 계산하고, 두 점 간의 선을 그린다. (처음과 마지막 열을 사용)
- cv::line 함수를 사용해 선을 그림.
- cv::line 함수는 영상 한계의 바깥에 있는 점 좌표로도 작동 (즉, 영상 내부에 계산된 교차점이 없는지 확인할 필요 없음)
- Example
#include <opencv2/core/core.hpp>
#include <opencv2/highgui/highgui.hpp>
#include <opencv2/imgproc/imgproc.hpp>
#define PI 3.1415926
int main()
{
cv::Mat image= cv::imread("road.jpg", 0);
cv::namedWindow("Original Image");
cv::imshow("Original Image",image);
// 캐니 알고리즘 적용
cv::Mat contours;
cv::Canny(image, contours, 125, 350);
// 선 감지 위한 허프 변환
std::vector<cv::Vec2f> lines;
cv::HoughLines(contours, lines,
1,PI/180, // 단계별 크기
80); // 투표(vote) 최대 개수
// 선 그리기
cv::Mat result(contours.rows, contours.cols, CV_8U, cv::Scalar(255));
std::cout << "Lines detected: " << lines.size() << std::endl;
// 선 벡터를 반복해 선 그리기
std::vector<cv::Vec2f>::const_iterator it= lines.begin();
while (it!=lines.end()) {
float rho = (*it)[0]; // 첫 번째 요소는 rho 거리
float theta = (*it)[1]; // 두 번째 요소는 델타 각도
if (theta < PI/4. || theta > 3.*PI/4.) { // 수직 행
cv::Point pt1(rho/cos(theta), 0); // 첫 행에서 해당 선의 교차점
cv::Point pt2((rho-result.rows*sin(theta))/cos(theta), result.rows);
// 마지막 행에서 해당 선의 교차점
cv::line(image, pt1, pt2, cv::Scalar(255), 1); // 하얀 선으로 그리기
} else { // 수평 행
cv::Point pt1(0,rho/sin(theta)); // 첫 번째 열에서 해당 선의 교차점
cv::Point pt2(result.cols,(rho-result.cols*cos(theta))/sin(theta));
// 마지막 열에서 해당 선의 교차점
cv::line(image, pt1, pt2, cv::Scalar(255), 1); // 하얀 선으로 그리기
}
std::cout << "line: (" << rho << "," << theta << ")\n";
++it;
}
cv::namedWindow("Detected Lines with Hough");
cv::imshow("Detected Lines with Hough",image);
cv::waitKey(0);
return 0;
}
- Result
- 그림에서 처럼 허프 변환은 단순히 영상에서 정렬된 에지 화소를 찾는다.
- 잠재적으로 예기치 않은 화소 정렬로 인해 일부 잘못된 감지를 만든거나, 여러 선이 동일한 화소 정렬을 경유한 여러 개를 감지할 수 있다.
- 이런 문제의 일부를 극복하고 선 세그먼트를 감지(즉, 마지막 점과 함께)하기 위해서 제안된 것이 확률적 허프 변환이다.
- 확률적 허프 변환은 cv::HoughLinesP 함수로 구현.
- 여기에 LineFinder 클래스를 생성해 이 함수를 사용하며, 함수 파라미터를 캡슐화 함.
- Example
#include <iostream>
#include <opencv2/core/core.hpp>
#include <opencv2/highgui/highgui.hpp>
#include <opencv2/imgproc/imgproc.hpp>
#define PI 3.1415926
class LineFinder {
private:
cv::Mat img; // 원 영상
std::vector<cv::Vec4i> lines; // 선을 감지하기 위한 마지막 점을 포함한 벡터
double deltaRho;
double deltaTheta; // 누산기 해상도 파라미터
int minVote; // 선을 고려하기 전에 받아야 하는 최소 투표 개수
double minLength; // 선에 대한 최소 길이
double maxGap; // 선에 따른 최대 허용 간격
public:
LineFinder() : deltaRho(1), deltaTheta(PI/180), minVote(10), minLength(0.), maxGap(0.) {}
// 기본 누적 해상도는 1각도 1화소
// 간격이 없고 최소 길이도 없음
// 해당 세터 메소드들
// 누적기에 해상도 설정
void setAccResolution(double dRho, double dTheta) {
deltaRho= dRho;
deltaTheta= dTheta;
}
// 투표 최소 개수 설정
void setMinVote(int minv) {
minVote= minv;
}
// 선 길이와 간격 설정
void setLineLengthAndGap(double length, double gap) {
minLength= length;
maxGap= gap;
}
// 허프 선 세그먼트 감지를 수행하는 메소드
// 확률적 허프 변환 적용
std::vector<cv::Vec4i> findLines(cv::Mat& binary) {
lines.clear();
cv::HoughLinesP(binary,lines,deltaRho,deltaTheta,minVote, minLength, maxGap);
return lines;
} // cv::Vec4i 벡터를 반환하고, 감지된 각 세그먼트의 시작과 마지막 점 좌표를 포함.
// 위 메소드에서 감지한 선을 다음 메소드를 사용해서 그림
// 영상에서 감지된 선을 그리기
void drawDetectedLines(cv::Mat &image, cv::Scalar color=cv::Scalar(255,255,255)) {
// 선 그리기
std::vector<cv::Vec4i>::const_iterator it2= lines.begin();
while (it2!=lines.end()) {
cv::Point pt1((*it2)[0],(*it2)[1]);
cv::Point pt2((*it2)[2],(*it2)[3]);
cv::line( image, pt1, pt2, color);
++it2;
}
}
};
int main()
{
cv::Mat image= cv::imread("road.jpg", 0);
// 캐니 알고리즘 적용
cv::Mat contours;
cv::Canny(image, contours, 125, 350);
LineFinder ld; // 인스턴스 생성
// 확률적 허프변환 파라미터 설정하기
ld.setLineLengthAndGap(100, 20);
ld.setMinVote(80);
// 선을 감지하고 그리기
std::vector<cv::Vec4i> li= ld.findLines(contours);
ld.drawDetectedLines(image);
cv::namedWindow("Detected Lines with HoughP");
cv::imshow("Detected Lines with HoughP",image);
cv::waitKey(0);
return 0;
}
- Result
- 예제 분석
- 허프 변환의 목적은 이진 영상 내에서 충분한 개수의 점을 통과하는 모든 선을 찾는데 있음.
- 입력 이진 맵의 각 화소점을 고려해 진행하고 통과 가능한 모든 선을 식별.
- 동일한 선이 많은 점을 지난다면 이 선을 충분히 고려할 정도로 중요함을 의미.
- 허프 변환은 주어진 선을 식별하기 위해 여러 번 계산하기 위한 2차원 누산기를 사용.
- 누산기의 크기는 채택한 선 표현의 (p, Θ) 파라미터로 지정된 단계별 크기로 정의.
- 변환의 기능을 증명하기 위해 180x200 행렬(Θ은 π/180이고, p는 1인 단계별 크기에 대응)을 만들어보면
- cv::Mat acc(200,180,CV_8U,cv::Scalar(0)); // 허프 누산기 생성
- 누산기는 각 (p, Θ) 값을 매핑.
- 그러므로 행렬의 각 요소는 특정 선에 대응.
- 한 점을 고려하는데, 예제에서는 (50, 30) 좌표로 예를 든다.
- 그 다음 가능한 모든 각도인 Θ(π/180의 단계별 크기로)와 해당 (반올림) p 값을 계산해 반복하는 과정에서 해당 점을 지나는 모든 선을 식별할 수 있다.
- 소스
#include <iostream>
#include <opencv2/core/core.hpp>
#include <opencv2/highgui/highgui.hpp>
#include <opencv2/imgproc/imgproc.hpp>
#define PI 3.1415926
int main()
{
cv::Mat acc(200,180,CV_8U,cv::Scalar(0));
// 허프 누적기 생성
// uchar 영상이어야 하고, 실제로 ing이어야 함
int x=50, y=30; // 점 선택
// 모든 각도로 반복
for (int i=0; i<180; i++) {
double theta= i*PI/180.;
// 대응하는 rho 값을 찾기
double rho= x*cos(theta)+y*sin(theta);
int j= static_cast<int>(rho+100.5);
std::cout << i << "," << j << std::endl;
acc.at<uchar>(j,i)++; // 누적기 증가
}
cv::namedWindow("Hough Accumulator 1");
cv::imshow("Hough Accumulator 1",acc*100);
x=30, y=10; // 두 번째 점 선택
// 모든 각도로 반복
for (int i=0; i<180; i++) {
double theta= i*PI/180.;
double rho= x*cos(theta)+y*sin(theta);
int j= static_cast<int>(rho+100.5);
acc.at<uchar>(j,i)++;
}
cv::namedWindow("Hough Accumulator 2");
cv::imshow("Hough Accumulator 2",acc*100);
cv::waitKey(0);
return 0;
}
- 결과
- 누산기의 요소는 계산된 (p, Θ) 쌍에 대응하면 증가하고, 영상의 한 지점(또는 다른 가능한 후보 선의 집합에 대한 각 점 투표)을 지나는 모든 선을 나타냄.
- 영상(1개수가 나타나게 100을 곱함)으로 누산기를 출력해서 위와 같은 결과를 얻는다.
- 그림에서 곡선은 고려한 점을 통과하는 모든 선의 집합을 표현.
- (30, 10) 점에 대해 동일한 과정을 반복하면 2번째 결과와 같은 누산기를 갖는다.
- 그림에서 보듯 두 결과 곡선은 한 점에서 교차.
- 이 점은 두 점이 선을 통과하는 점에 해당.
- 누산기의 해당 요소는 두 투표를 받고, 두 점이 이선을 통과했음을 나타냄.
- 이진 맵의 모든 점에 동일한 과정을 반복하면 점이 주어진 선에 따라 정렬되고 누산기의 공통 요소가 여러 번 증가.
- 마지막에 하나는 누산기에서 영상 안의 선(점 정렬)을 감지하기 위한 상당한 투표 개수를 받는 지역 최대치를 식별해야 함.
- cv::HoughLines 함수 내에 지정한 마지막 파라미터는 투표 최소 개수에 대응하는 선이 감지된 것으로 간주해 받아 들여야 함.
- 예를 들어 cv::HoughLines(contours, lines, 1, PI/180, 80); 을 60으로,
즉, cv::HoughLines(contours, lines, 1, PI/180, 60); 으로 하면 더 많은 선이 나타난다.
- 소스
#include <iostream>
#include <opencv2/core/core.hpp>
#include <opencv2/highgui/highgui.hpp>
#include <opencv2/imgproc/imgproc.hpp>
#define PI 3.1415926
int main()
{
cv::Mat image= cv::imread("road.jpg", 0);
// 캐니 알고리즘 적용
cv::Mat contours;
cv::Canny(image, contours, 125,350);
// 선 감지 위한 허프 변환
std::vector<cv::Vec2f> lines;
cv::HoughLines(contours, lines,
1,PI/180, // 단계별 크기
60); // 투표(vote) 최대 개수
// 선 그리기
cv::Mat result(contours.rows, contours.cols, CV_8U, cv::Scalar(255));
std::cout << "Lines detected: " << lines.size() << std::endl;
// 선 벡터를 반복해 선 그리기
std::vector<cv::Vec2f>::const_iterator it= lines.begin();
while (it!=lines.end()) {
float rho = (*it)[0]; // 첫 번째 요소는 rho 거리
float theta = (*it)[1]; // 두 번째 요소는 델타 각도
if (theta < PI/4. || theta > 3.*PI/4.) { // 수직 행
cv::Point pt1(rho/cos(theta), 0); // 첫 행에서 해당 선의 교차점
cv::Point pt2((rho-result.rows*sin(theta))/cos(theta), result.rows);
// 마지막 행에서 해당 선의 교차점
cv::line(image, pt1, pt2, cv::Scalar(255), 1); // 하얀 선으로 그리기
} else { // 수평 행
cv::Point pt1(0,rho/sin(theta)); // 첫 번째 열에서 해당 선의 교차점
cv::Point pt2(result.cols,(rho-result.cols*cos(theta))/sin(theta));
// 마지막 열에서 해당 선의 교차점
cv::line(image, pt1, pt2, cv::Scalar(255), 1); // 하얀 선으로 그리기
}
std::cout << "line: (" << rho << "," << theta << ")\n";
++it;
}
cv::namedWindow("Detected Lines with Hough");
cv::imshow("Detected Lines with Hough",image);
cv::waitKey(0);
return 0;
}
- 결과
- 확률적 허프 변환은 기본 알고리즘에 몇 가지 수정을 가했음.
- 첫째, 체계적으로 영상을 행마다 조회하는 대신 이진 맵에서 무작위 순서로 점을 선택.
- 누산기의 항목이 특정 최소값에 도달할 때마다 해당 선을 따라 영상을 조회하고 통과하는 모든 점을 제거(아직 투표하지 않은 경우에도) 함,
- 또한 조회 과정에서 세그먼트의 길이를 결정하며 받아들임.
- 이를 위해 알고리즘은 두 개의 추가 파라미터를 정의.
- 전자는 받아들이기 위한 세그먼트의 최소 길이이고, 후자는 연속적인 세그먼트를 형성하기 위해 허용하는 최대 화소 간격.
- 이 추가 단계는 알고리즘의 복잡도를 증가시키지만, 선을 조회하는 과정에서 일부가 사라지고, 투표 과정에서 아주 작은 점을 포함하기 때문에 어느 정도 보상할 수 있음.
- 참고문헌 : OpenCV 2 Computer Vision Application Programming Cookbook
