블로그 이미지
Leeway is... the freedom that someone has to take the action they want to or to change their plans.
maetel

Notice

Recent Post

Recent Comment

Recent Trackback

Archive

calendar

 « 2024.5  »
일 월 화 수 목 금 토
1 2 3 4
5 6 7 8 9 10 11
12 13 14 15 16 17 18
19 20 21 22 23 24 25
26 27 28 29 30 31
  • total
  • today
  • yesterday

Category

virtual studio 구현: feature point identification (...ing)

2010. 4. 22. 20:50 Computer Vision
ref.
swPark_2000rti 439쪽: In the initial identification process, we first extract and identify vertical and horizontal lines of the pattern by comparing their cross-ratios, and then we compute the intersections of the lines. Theoretically with this method, we can identify feature points in every frame automatically, but several situations cause problems in the real experiments.


박승우_1999전자공학회지 94쪽: 초기 인식과정에서는 패턴 상의 교점을 인식하기 위해 패턴의 제작과정에서 설명한 것처럼 영상에서 구해진 가로선과 세로선의 Cross-ratio를 패턴의 가로선과 셀로선이 가지는 Cross-ratio와 비교함으로써 몇번째 선인지를 인식하게 된다. 이러한 방법을 이용해 영상으로부터 자동으로 특징점을 찾고 인식할 수 있지만, 실제 적용 상에서는 몇 가지 제한점이 따르게 된다.



0. NMS (Non Maximum Suppression)을 적용한 Hough transform에 의한 Line 찾기

OpenCV 라이브러리의 HoughLines2() 함수는 전에 기술한 바( http://leeway.tistory.com/801 )와 같이 실제 패턴에서는 하나의 직선 위에 놓인 점들에 대해 이미지 프레임에서 검출된 edges을 가지고 여러 개의 직선을 찾는 결과를 보인다. 이는 HoughLines2() 함수가 출력하는, 직선을 정의하는 두 파라미터 rho와 theta에 대해 ( x*cos(theta) + y*sin(theta) = rho ) 계산된 값들이 서로 비슷하게 나오는 경우에 최적값을 선별하는 과정을 거치지 않고 모든 값들을 그대로 내보내기 때문이다. 그래서 OpenCV의 이 함수를 이용하지 않고, 따로 Hough transform을 이용하여 선을 찾는 함수를 만들되 여기에 NMS (Non Maximum Suppression)를 적용하도록 해 보았다. 하지만 이 함수를 실시간 비디오 카메라 입력에 대해 매 프레임마다 실행시키면 속도가 매우 느려져 쓸 수 없었다. 그래서, 속도 면에서 월등한 성능을 보이는 OpenCV의 HoughLines2() 함수를 그대로 따 오고 대신 여기에 NMS 부분을 추가하여 수정한 함수를 매 입력 프레임마다 호출하는 방법을 택하였고, 실시간 처리가 가능해졌다. (->소스코드)


http://en.wikipedia.org/wiki/Feature-point_detection



1. 직선의 순서 매기기

산출된 수직선들을 이미지 프레임의 왼쪽에서부터 오른쪽으로 나타난 순서대로 번호를 매기고 (아래 그림의 붉은색 번호), 수평선들을 위로부터 아래로 나타난 순서대로 번호를 매긴다 (아래 그림의 푸른색 번호). 이 과정에서 수직선의 경우 x절편, 수평선의 경우 y절편의 값을 기준으로 하여 계산하였다. 



아래 코드에서 "line.x0"가 "line" 직선의 x절편임
// rearrange lines from left to right
void indexLinesY ( CvSeq* lines, IplImage* image )
{   
    // retain the values of "rho" & "theta" of found lines
    int numLines = lines->total;
    // line_param line[numLines]; 이렇게 하면 나중에 이 변수를 밖으로 빼낼 때 (컴파일 에러는 안 나지만) 문제가 됨.
    line_param *line = new line_param[numLines];

    for( int n = 0; n < numLines; n++ )
    {
        float* newline = (float*)cvGetSeqElem(lines,n);
        line[n].rho = newline[0];
        line[n].theta = newline[1];
    }
   
    // rearrange "line" array in geometrical order
    float temp_rho, temp_theta;
    for( int n = 0; n < numLines-1; n++ )
    {
        for ( int k = n+1; k < numLines; k++ )
        {
            float x0_here = line[n].rho / cos(line[n].theta);
            float x0_next = line[k].rho / cos(line[k].theta);
            if( x0_here > x0_next ) {
                temp_rho = line[n].rho;        temp_theta = line[n].theta;
                line[n].rho = line[k].rho;        line[n].theta = line[k].theta;
                line[k].rho = temp_rho;        line[k].theta = temp_theta;
            }
        }
    }
    // calculate the other parameters of the rearranged lines
    for( int n = 0; n < numLines; n++ )
    {
        line[n].a = cos(line[n].theta);
        line[n].b = sin(line[n].theta);
        line[n].x0 = line[n].rho / line[n].a;
        line[n].y0 = line[n].rho / line[n].b;
       
        cout << "x[" << n << "] = " << line[n].x0 << "    y[" << n << "] = " << line[n].y0 ;
        cout << "    rho[" << n << "] = " << line[n].rho << "    theta[" << n << "] = " << line[n].theta << endl;
       
        char txt[100]; sprintf(txt, "%d", n);
        cvPutText(image, txt, cvPoint(line[n].x0, 10+n*10), &cvFont(0.8), CV_RGB(255,50,50));
    }
}

초록색으로 칠한 줄에 대한 설명:
void indexLinesY( CvSeq* lines, IplImage* image ) 함수를 line_param* indexLinesY( CvSeq* lines, IplImage* image )라고 바꾸어 structure로 선언한 line_param 형태의 배열을 출력하도록 하고, 이 출력값을 교점을 구하는 함수의 입력으로 하면
line_param line[numLines];
이렇게 함수 안에서 선언했던 부분이 함수 밖으로 출력되어 다른 함수의 입력이 될 때 입력값이 제대로 들어가지 않는다. 다음과 같이 바꾸어 주어야 함.
line_param *line = new line_param[numLines];

ref. http://cplusplus.com/reference/std/new/



상기 0-1의 과정을 적용한 코드의 실행 결과




그런데 다음과 같은 문제를 발견함.

x방향 DoG 필터링한 영상

y방향 DoG 필터링한 영상

Hough transform에 NMS를 적용하여 검출한 직선에 순번을 매긴 결과


이미지 프레임에서 찾은 수평선들을 보면 제일 위쪽의 직선이 0번이 아니라 4번부터 순번이 매겨져 있다. 프레임 바깥에 (위쪽에) 세 개의 직선이 더 있다는 뜻인데...

수직성 상의 edges 검출 영상

수평선 상의 edges 검출 영상

수직선들을 왼쪽부터 오른쪽으로, 수평선들을 위에서 아래로 정열한 결과


왼쪽 두 개는 line detection에 입력으로 쓰인 영상이고, 마지막 것은 이로부터 순서대로 정열한 직선을 규정하는 매개변수 출력값이다. 0번부터 3번 수평선의 y절편 값이 음수로 나타나고 있다.



2. 교점의 순서 매기기

격자 무늬의 직선들의 교점(intersections)을 과정1에서 계산한 직선의 순번을 이용하여 indexing한다. 빨간 세로선 0번과 파란 가로선 0번의 교점은 00번, 이런 식으로.

// index intersection points of lines in X and Y
CvPoint* indexIntersections ( line_param* lineX, line_param* lineY, int numLinesX, int numLinesY, IplImage* image )
// find intersections of lines, "linesX" & "linesY", and draw them in "image"
{
    int numPoints = (numLinesX+1) * (numLinesY+1);
    CvPoint *p = new CvPoint[numPoints]; // the intersection point of lineX[i] and lineY[j]
    char txt[100]; // text to represent the index number of an intersection
   
    for( int i = 0; i < MIN(numLinesX,100); i++ )
    {
        for( int j = 0; j < MIN(numLinesY,100); j++ )
        {             
            int indexP = i*numLinesY + j;     
            float Px = ( lineX[i].rho*lineY[j].b - lineY[j].rho*lineX[i].b ) / ( lineX[i].a*lineY[j].b - lineX[i].b*lineY[j].a ) ;
            float Py = ( lineX[i].rho - lineX[i].a*Px ) / lineX[i].b ;
            p[indexP].x = cvRound(Px);
            p[indexP].y = cvRound(Py);
           
            // display the points in an image
            cvCircle( image, p[indexP], 3, CV_RGB(0,255,50) /* , <#int line_type#>, <#int shift#> */ );   
            sprintf(txt, "%d", indexP);   
            cvPutText(image, txt, p[indexP], &cvFont(0.7), CV_RGB(50,255,250));           
        }
    }       
    return p;
}


입력 영상 input을 단일 채널 temp로 바꾸어 1차 DoG 필터링을 하여 검출된 edges를 양 방향 세기 비교와 NMS를 통해 수평 방향과 수직 방향으로 나눈 영상 detected edges를 입력으로 하여 Hough transform에 NMS를 적용하여 line detection을 한 결과를 input 창에 그리고, 이미지 프레임 좌표를 기준으로 검출된 직선들에 순서를 매겨 이로부터 교차점의 위치와 순번을 계산하여 input 창에 표시한다.



현재 상태의 문제점: (1) 패턴과 카메라 모두 정지하여 입력 영상(상좌)이 고정된 경우에, DoG 필터링한 결과(중)는 비교적 안정적이지만 수평, 수직 방향 세기 비교와 NMS를 통해 각 방향에 대해 뽑은 edges를 표시한 영상(하)은 프레임이 들어올 때마다 변화가 있다. 그래서 이 두 영상을 입력으로 하여 직선 찾기를 한 결과(상좌 빨간색 선들)와 이로부터 계산한 교차점들의 위치 및 순번(상좌 연두색 동그라미와 하늘색 숫자)도 불안정하다. (2) 또한 패턴과의 거리에 대해 카메라 렌즈의 초점이 맞지 않으면 결과가 좋지 않다.     





3. 교점의 cross ratio 구하기

각 교점에서 수평 방향으로 다음 세 개의 교점, 수직 방향으로 다음 세 개의 교점을 지나는 직선에 대한 cross ratios를 구한다. 

직선 검출에 오차나 오류가 적을 경우, 아래 테스트 결과에서 보듯 입력 영상의 교차점에 대해 실제 패턴의 직선을 1대 1로 즉각적으로 찾는다.



matching 시험 결과 영상 (위: 실제 패턴 / 아래: 입력 영상)




http://en.wikipedia.org/wiki/Sum_of_squares


저작자표시 비영리 동일조건

'Computer Vision' 카테고리의 다른 글

virtual studio 구현: pattern design  (0) 2010.04.27
virtual studio 구현: grid pattern generator  (0) 2010.04.27
virtual studio 구현: line fitting (Hough transform + non maximal suppression)  (0) 2010.04.22
GML C++ Camera Calibration Toolbox  (0) 2010.04.22
OpenCV 2.1 설치 on Mac OS X  (0) 2010.04.14
posted by maetel

virtual studio 구현: line fitting (Hough transform + non maximal suppression)

2010. 4. 22. 20:14

보호되어 있는 글입니다.
내용을 보시려면 비밀번호를 입력하세요.

OpenCV: cvHoughLines2() 연습 코드

2010. 4. 7. 00:16 Computer Vision
OpenCV 라이브러리의 Hough transform에 의한 직선 찾기 함수


CvSeq* cvHoughLines2(CvArr* image, void* storage, int method, double rho, double theta, int threshold, double param1=0, double param2=0)

Finds lines in a binary image using a Hough transform.

Parameters:
  • image – The 8-bit, single-channel, binary source image. In the case of a probabilistic method, the image is modified by the function
  • storage – The storage for the lines that are detected. It can be a memory storage (in this case a sequence of lines is created in the storage and returned by the function) or single row/single column matrix (CvMat*) of a particular type (see below) to which the lines’ parameters are written. The matrix header is modified by the function so its cols or rows will contain the number of lines detected. If storage is a matrix and the actual number of lines exceeds the matrix size, the maximum possible number of lines is returned (in the case of standard hough transform the lines are sorted by the accumulator value)
  • method –

    The Hough transform variant, one of the following:

    • CV_HOUGH_STANDARD - classical or standard Hough transform. Every line is represented by two floating-point numbers $(\rho , \theta )$, where $\rho $ is a distance between (0,0) point and the line, and $\theta $ is the angle between x-axis and the normal to the line. Thus, the matrix must be (the created sequence will be) of CV_32FC2 type
    • CV_HOUGH_PROBABILISTIC - probabilistic Hough transform (more efficient in case if picture contains a few long linear segments). It returns line segments rather than the whole line. Each segment is represented by starting and ending points, and the matrix must be (the created sequence will be) of CV_32SC4 type
    • CV_HOUGH_MULTI_SCALE - multi-scale variant of the classical Hough transform. The lines are encoded the same way as CV_HOUGH_STANDARD
  • rho – Distance resolution in pixel-related units
  • theta – Angle resolution measured in radians
  • threshold – Threshold parameter. A line is returned by the function if the corresponding accumulator value is greater than threshold
  • param1 –

    The first method-dependent parameter:

    • For the classical Hough transform it is not used (0).
    • For the probabilistic Hough transform it is the minimum line length.
    • For the multi-scale Hough transform it is the divisor for the distance resolution $\rho $. (The coarse distance resolution will be $\rho $ and the accurate resolution will be $(\rho / \texttt{param1})$).
  • param2 –

    The second method-dependent parameter:

    • For the classical Hough transform it is not used (0).
    • For the probabilistic Hough transform it is the maximum gap between line segments lying on the same line to treat them as a single line segment (i.e. to join them).
    • For the multi-scale Hough transform it is the divisor for the angle resolution $\theta $. (The coarse angle resolution will be $\theta $ and the accurate resolution will be $(\theta / \texttt{param2})$).

Memory storage is a low-level structure used to store dynamicly growing data structures such as sequences, contours, graphs, subdivisions, etc.


입력 이미지가 8비트 단일 채널이어야 하므로,
다음과 같이 "IPL_DEPTH_32F"로 생성했던 입력 이미지 (iplDoGx)를 바꾸어 "8" 비트 depth짜리 새로운 이미지 (iplEdgeY)에 저장한다.

            cvConvert(iplDoGx, iplEdgeY);


두번째 인자 " void* storage" 는 탐지된 직선을 저장할 메모리. 이 함수의 아웃풋에 해당한다.

CvMemStorage

Growing memory storage.

typedef struct CvMemStorage

{

    struct CvMemBlock* bottom;/* first allocated block */

    struct CvMemBlock* top; /* the current memory block - top of the stack */

    struct CvMemStorage* parent; /* borrows new blocks from */

    int block\_size; /* block size */

    int free\_space; /* free space in the \texttt{top} block (in bytes) */

} CvMemStorage;



CvMemStorage* cvCreateMemStorage(int blockSize=0)

Creates memory storage.

Parameter:blockSize – Size of the storage blocks in bytes. If it is 0, the block size is set to a default value - currently it is about 64K.


 그 아웃풋을 다음의 CvSeq 형태의 자료 구조체 안에 저장한다.

CvSeq

Growable sequence of elements.

#define CV_SEQUENCE\_FIELDS() \

    int flags; /* micsellaneous flags */ \

    int header_size; /* size of sequence header */ \

    struct CvSeq* h_prev; /* previous sequence */ \

    struct CvSeq* h_next; /* next sequence */ \

    struct CvSeq* v_prev; /* 2nd previous sequence */ \

    struct CvSeq* v_next; /* 2nd next sequence */ \

    int total; /* total number of elements */ \

    int elem_size;/* size of sequence element in bytes */ \

    char* block_max;/* maximal bound of the last block */ \

    char* ptr; /* current write pointer */ \

    int delta_elems; /* how many elements allocated when the sequence grows

                  (sequence granularity) */ \

    CvMemStorage* storage; /* where the seq is stored */ \

    CvSeqBlock* free_blocks; /* free blocks list */ \

    CvSeqBlock* first; /* pointer to the first sequence block */



typedef struct CvSeq

{

    CV_SEQUENCE_FIELDS()

} CvSeq;

The structure CvSeq is a base for all of OpenCV dynamic data structures.


그 저장된 값을 읽는 함수

char* cvGetSeqElem(const CvSeq* seq, int index)

Returns a pointer to a sequence element according to its index.

#define CV_GET_SEQ_ELEM( TYPE, seq, index )  (TYPE*)cvGetSeqElem( (CvSeq*)(seq), (index) )
Parameters:
  • seq – Sequence
  • index – Index of element




accumulator value 란?







"detected edges" 이미지에 대해 Hough transform에 의한 line fitting 한 결과를 "input" 이미지에 그리고 있음




opencv/opencv/src/cv/cvhough.cpp 를 열면, 다음의 네 부분으로 나뉘어 정의되어 있다.
Classical Hough Transform
Multi-Scale variant of Classical Hough Transform 
Probabilistic Hough Transform      
Circle Detection

이 중 "Classical Hough Transform" 부분은 다음과 같음.
typedef struct CvLinePolar
{
    float rho;
    float angle;
}
CvLinePolar;
/*=====================================================================================*/

#define hough_cmp_gt(l1,l2) (aux[l1] > aux[l2])

static CV_IMPLEMENT_QSORT_EX( icvHoughSortDescent32s, int, hough_cmp_gt, const int* )

/*
Here image is an input raster;
step is it's step; size characterizes it's ROI;
rho and theta are discretization steps (in pixels and radians correspondingly).
threshold is the minimum number of pixels in the feature for it
to be a candidate for line. lines is the output
array of (rho, theta) pairs. linesMax is the buffer size (number of pairs).
Functions return the actual number of found lines.
*/
static void
icvHoughLinesStandard( const CvMat* img, float rho, float theta,
                       int threshold, CvSeq *lines, int linesMax )
{
    int *accum = 0;
    int *sort_buf=0;
    float *tabSin = 0;
    float *tabCos = 0;

    CV_FUNCNAME( "icvHoughLinesStandard" );

    __BEGIN__;

    const uchar* image;
    int step, width, height;
    int numangle, numrho;
    int total = 0;
    float ang;
    int r, n;
    int i, j;
    float irho = 1 / rho;
    double scale;

    CV_ASSERT( CV_IS_MAT(img) && CV_MAT_TYPE(img->type) == CV_8UC1 );

    image = img->data.ptr;
    step = img->step;
    width = img->cols;
    height = img->rows;

    numangle = cvRound(CV_PI / theta);
    numrho = cvRound(((width + height) * 2 + 1) / rho);

    CV_CALL( accum = (int*)cvAlloc( sizeof(accum[0]) * (numangle+2) * (numrho+2) ));
    CV_CALL( sort_buf = (int*)cvAlloc( sizeof(accum[0]) * numangle * numrho ));
    CV_CALL( tabSin = (float*)cvAlloc( sizeof(tabSin[0]) * numangle ));
    CV_CALL( tabCos = (float*)cvAlloc( sizeof(tabCos[0]) * numangle ));
    memset( accum, 0, sizeof(accum[0]) * (numangle+2) * (numrho+2) );

    for( ang = 0, n = 0; n < numangle; ang += theta, n++ )
    {
        tabSin[n] = (float)(sin(ang) * irho);
        tabCos[n] = (float)(cos(ang) * irho);
    }

    // stage 1. fill accumulator
    for( i = 0; i < height; i++ )
        for( j = 0; j < width; j++ )
        {
            if( image[i * step + j] != 0 )
                for( n = 0; n < numangle; n++ )
                {
                    r = cvRound( j * tabCos[n] + i * tabSin[n] );
                    r += (numrho - 1) / 2;
                    accum[(n+1) * (numrho+2) + r+1]++;
                }
        }

    // stage 2. find local maximums
    for( r = 0; r < numrho; r++ )
        for( n = 0; n < numangle; n++ )
        {
            int base = (n+1) * (numrho+2) + r+1;
            if( accum[base] > threshold &&
                accum[base] > accum[base - 1] && accum[base] >= accum[base + 1] &&
                accum[base] > accum[base - numrho - 2] && accum[base] >= accum[base + numrho + 2] )
                sort_buf[total++] = base;
        }

    // stage 3. sort the detected lines by accumulator value
    icvHoughSortDescent32s( sort_buf, total, accum );

    // stage 4. store the first min(total,linesMax) lines to the output buffer
    linesMax = MIN(linesMax, total);
    scale = 1./(numrho+2);
    for( i = 0; i < linesMax; i++ )
    {
        CvLinePolar line;
        int idx = sort_buf[i];
        int n = cvFloor(idx*scale) - 1;
        int r = idx - (n+1)*(numrho+2) - 1;
        line.rho = (r - (numrho - 1)*0.5f) * rho;
        line.angle = n * theta;
        cvSeqPush( lines, &line );
    }

    __END__;

    cvFree( &sort_buf );
    cvFree( &tabSin );
    cvFree( &tabCos );
    cvFree( &accum );
}






저작자표시 비영리 동일조건

'Computer Vision' 카테고리의 다른 글

OpenCV 2.1 설치 on Mac OS X  (0) 2010.04.14
Hough transform  (0) 2010.04.12
OpenCV: cvFitLine() 연습 코드  (0) 2010.04.06
virtual studio 구현: line fitting test  (0) 2010.04.06
virtual studio 구현: gradient filtering  (0) 2010.04.04
posted by maetel

티스토리툴바