2. deque
Deque = Double Ended Queue
우리말로 읽을때 발을을 "데크"라 발음한다.
Deque는 vector와 매우 유사하다. 데이터를 일렬로 저장하게 되며, 각 데이터에 대한 임의 접근이 가능하다. 연속적인 데이터의 끝에 요소를 추가하거나 삭제 하는 것은 constance time 즉 O(1) 이 걸린다. 또한 요소들의 중간에 데이터를 삽입하거나 삭제할 경우 linear time 즉 O(n) 의 time complexity 를 갖는다.
Deque 가 vector와 다른 가장 큰 이유는, deque는 sequence 즉 데이터들의 앞쪽에 데이터를 추가하거나 삭제하는데 있어서 constant time O(1)의 시간이 걸린다는 것이다. (*참고적으로 vector는 앞쪽에 데이터를 추가/삭재에 있어서 O(n) 의 시간이 걸린다).
3.cvFindContours - 외곽선생성
int cvFindContours( CvArr* image, CvMemStorage* storage, CvSeq** first_contour, int header_size=sizeof(CvContour), int mode=CV_RETR_LIST, int method=CV_CHAIN_APPROX_SIMPLE, CvPoint offset=cvPoint(0,0) );
-
외부 Contour: 흑=>백
-
내부 Contour: 백=>흑
| image | source이미지. 8-bit 1-channel. Gray 영상도 가능(non-zero: 1, zero: 0으로 간주함). 주. 함수의 수행 과정에서 원본 이미지를 변경시킴. |
| storage | 찾아진 contour들을 저장할 container |
| first_contour | 결과 매개변수. 첫 번째 외부 contour의 포인터 저장 |
| header_size | 결과는 CvSeq에 저장되는데 이 때 저장될 자료구조의 크기. - method가 CV_CHAIN_CODE이면 >= sizeof(CvChain) - 그렇지 않으면 >= sizeof(CvContour) |
| mode | 추출 방법 - CV_RETR_EXTERNAL: 최외부 contour만 추출 - CV_RETR_LIST: 모든 contour를 찾아 한 list에 저장 (hierachycal 구조가 아님) - CV_RETR_CCOMP: 모든 contour를 찾아 2-level 트리 구조로 구성. top 레벨은 외부 contour, second 레벨은 내부contour(holes) - CV_RETR_TREE: 모든 contour를 찾아 full hierachy 트리 구조 구성 - CV_RETR_RUNS: Run-type 방법으로 추출하는 듯. 자세히는 모르겠음. |
| method | Approximation 방법 (CV_RETR_RUNS는 자체 방법을 사용하므로 이를 제외한 모든 방법에서만 사용함) - CV_CHAIN_CODE: the Freeman chain code로 저장됨. (이걸 제외하고 나머지 method는 polygon 구조(sequences of vertices)로 저장함. - CV_CHAIN_APPROX_NONE: 단순히 chain code를 point 구조로 변경함 - CV_CHAIN_APPROX_SIMPLE: 수평, 수직, 대각선 성분을 압축. ending point들만 남겨둠. - CV_CHAIN_APPROX_TC89_L1, CV_CHAIN_APPROX_TC89_KCOS: Teh-Chin chain approximation 알고리즘으로 압축 - CV_LINK_RUNS: CV_RETR_LIST 모드에서만 사용됨. 자세히는 모르겠음. |
| offset | contour 포인트들이 shift될 값 ROI 설정한 경우 좋음. |
cvFindContours 함수는 이미지에서 contour를 찾은 후 contour의 갯수를 리턴
원형
int cvFindContours( CvArr* image, CvMemStorage* storage, CvSeq* first_contour,
int header_size=sizeof(CvContour), int mode, int mthod, CvPoint offset=cvPoint(0,0) );
패러미터
- image : 8비트 grayscale 영상만을 패러미터로 넘길 수 있다. 0이 아닌 픽셀은 1로, 0인 픽셀은 0으로 간주하여 자체적으로 2진 영상으로 처리하게 된다.
- storage : CvMemStorage 구조체의 포인터를 넘긴다. 실제로 contour 정보가 저장되는 공간이다.
- first_contour : 첫번째 최외곽 contour의 정보를 저장할 CvSeq 구조체의 포인터
- header_size : 시퀀스 헤더의 크기 ex) sizeof(CvContour)
- mode : contour 검출 방법
CV_RETR_EXTERNAL - 오직 최외곽 contour만을 검출한다.
CV_RETR_LIST - 모든 contour를 검출하여 list로 저장한다.
CV_RETR_CCOMP - 모든 contour를 검출한 후 2단계로 계층화한다.
상위 계층은 각 성분(component)의 외곽 경계를 나타내며 하위 계층은 성분 내부의
구멍(hole)을 나타낸다.
CV_RETR_TREE - 모든 contour를 검출한 후 각 contour를 tree 형태로 구조화한다.
- moethod : approximation(생략산) 방법이다.
생략산이란 불필요한 연산량을 줄이기 위하여 모든 contour를 구하지 않고 추정
CV_CHAIN_CODE - Freeman chain code를 사용하여 contour를 출력한다. 이것 외의 다른 모든 방법은
결과물을 polygon(다각형, 버텍스의 나열)로 출력한다.
CV_CHAIN_APPROX_NONE - 모든 contour의 점을 chain code에서 point로 변환한다.
CV_CHAIN_APPROX_SIMPLE - 가로, 세로, 대각선 으로 쪼개서 압축하며 함수는 끝점만을 출력한다.
CV_CHAIN_APPROX_TC89_L1, CV_CHAIN_APPROX_TC89_KCOS - Teh-Chin chain approximation
알고리즘에 사용된다.
CV_LINK_RUNS - 1의 수평 구획의 연결을 통해 완전히 다른 방식의 contour 검출 알고리즘을 사용한다.
CV_RETR_LIST 모드에서만 사용 가능하다.
- offset : 모든 contour 포인트 이동
예제
CvMemStorage* storage = cvCreateStorage(0); // 배열 자료형 : 점의 좌표가 들어감
CvSeq* seq = NULL; //경계 개수를 저장할 변수 선언
int numContour = cvFindContours(src, storage, &seq, sizeof(CvContour), CV_RETR_TREE,
CV_CHAIN_APPROX_SIMPLE);
[출처] cvFindContours|작성자 천재소년