Dreamer GUNDAM의 블로그::무료로 뉴타입이 되는 별까지 앞으로 356광년

(주) 언제나 그렇듯이 지극히 개인적인 관점이 포함되어 있습니다.

(주) 인텔 C++ 컴파일러는 Evaluation version을 다운받아서 테스트 해볼 수 있습니다.

      등록하면 한달짜리 라이센스를 보내줍니다.

인텔 C++ 컴파일러의 최적화 능력을 테스트 해보도록 하겠습니다.

프로젝트로 최적화에 관련된 프로젝트가 있는데, 이리저리 손파일러로 최적화를 하고 있지만,

속도올리기가 힘들어져서 아예 이번에는 플랫폼을 바꾸어서 하기로 하였습니다.

인텔 기반 최적화에 관해서는 지원해주는 툴셋이 여러가지가 있지만,

intel c++ 컴파일러에서 최적화를 수행하기로 하였습니다.

몇가지 장점이 있지만, 무엇보다도, visual c++에서 통합하여 개발 할 수 있고

(그렇다고 하지만 저는 Text Base에서 코딩합니다.)

또 코드상에 숨어있는 vector 연산등을 찾아내어서 최적화시켜주는 능력등이 탁월합니다.

일단 대상으로 선정한 것은 그래픽도 나오는 이쁘장한 것으로 Intel TBB의 예제로 주어지는 tachyon입니다.

화면상에 7000여개의 오브젝트를 그리는 프로그램인데요, TBB의 예제로서 제공되기 때문에

Serial과 TBB도 함께 비교할 수 있습니다.

Serial이란 것은 Thread를 생성하지 않고 순차적으로 프로그램을 실행하는 방식입니다.

TBB는 프로그램을 thread로 잘라서 실행하는 것을 도와주는 라이브러리입니다.

Makefile을 가지고 컴파일하면 g++을 이용해서 컴파일하도록 되어 있습니다.

그래서 g++로 컴파일하는 코드를 인텔 C++컴파일러인 icc로 바꾸어서 최적화 옵션을 주어가면서

최적화 결과를 보도록 하겠습니다.

다만, 다른 코드도 테스트를 겸하기 위해서 tbb 라이브러리를 호출해서 사용하는 것을 사용하기로 하였습니다.

지금 진행하는 프로젝트에서도 tbb도 중요한 최적화의 포인트이기 때문입니다.

아래와 같은 경우를 모두 테스트 해봅니다.

g++로 할 경우

g++ + Thread Building Block 1d를 이용 할 경우

g++ + Thread Building Block 2d를 이용 할 경우

intel c++로 할경우

intel c++ + Thread Building Block 1d를 이용 할 경우

intel c++ + Thread Building Block 2d를 이용 할 경우

intel c++ + parallel optimzation 을 수행 할경우

intel c++ + parallel optimzation 을 수행+ Thread Building Block 1d를 이용 할 경우

intel c++ + parallel optimzation 을 수행+ Thread Building Block 2d를 이용 할 경우

intel c++ + performance guide optimizaton + parallel optimzation 을 수행 할경우

intel c++ + performance guide optimizaton + parallel optimzation 을 수행+ Thread Building Block 1d를 이용 할 경우

intel c++ + performance guide optimizaton + parallel optimzation 을 수행+ Thread Building Block 2d를 이용 할 경우

을 할 경우로 한다. 모두 12가지 경우를 테스트 하는 것이 되네요

아래 그림은 Serial로 그리는 경우에 대한 그림입니다.

한번에 하나씩 차례로 그려 나갑니다.

마지막 그림은 TBB2D를 사용한것입니다.

일정 블럭단위로 쪼개서 계속 그려나가는 그림입니다.

다만 정확하게 할려면 같은 프로그램을 100번 이상 수행해서 그 평균을 내야 하지만,

귀차니즘이 있어서리.. 그냥 한 두번 수행한 결과임을 미리 밝힙니다. (개인적인 참고 자료여서 굳이 100번이상이나 할 필요가..  )

대상으로 하는 프로그램은 TBB의 예제중 하나인 tachyon 이다.

각각의 것으로 실행하여 수행시간을 측정한 결과는 아래에 표시된 것과 같습니다.

g++ intel c++ intel c++ + parallel     icc + parallel + pgo

serial 26.640 20.617 20.635                  19.673             

tbb1d 10.243 9.635         9.459                    8.646

tbb2d 9.733         9.068         8.885                    7.921

최종 최적화 결과와 최초의 결과를 비교하면

3.36배가 빨라졌습니다.   가장 느린것 대비  29.7%의 수행 시간을 가집니다.

컴파일러를 바꾸고 옵션을 바꾸어서 최적화를 수행하면 코드를 건드리지 않고도 위와 같이 3배 이상 빨라진다는 것을 알수 있습니다. 음.. 코드를 바꾸지 않은것은 아니네요,  serial 에서 tbb1d로 바꾸는것이나 tbb2d로 바꾸는 것은 최적화를 위해서 코드를 바꾸는 것이 됩니다.

같은 레벨의 코드에서 그냥 icc+parallel+pgo 를 하였을때 약 20% 정도 빨라지는 것을 알 수 있습니다.

pgo란 profile guided optimization의 약자로서,  컴파일을 두번해서 최적화 하는 것입니다.

1차 컴파일시에 컴파일러는 여러가지 예측을 통해서 최적화를 시도하지만, 그 결과가 예측이 안되는 경우가 많습니다. 상황에 따라서 알쏭달쏭 한 부분을 모두 기억하고 있다가, 프로그램이 실행되면 실제 동작되는 정보를 얻습니다. 그리고 그걸 기반으로 2차 컴파일시에 확신을 가지고 최적화 선택을 하게 됩니다. 이런 방식으로 동일한 코드에서도 20%정도 빨라진 효과를 거둘 수 있는 것입니다.

우숩게 보일지 모르지만 초당 20fps를 할 수 있는 h.264 code를 손도 안되고 20% 빨리 하여서 초당 24fps를 달성 할 수 있는 것입니다. 최적화는 해보신 분들만 아실수 있는 문제가 어느정도 최적화를 진행하다 보면 진도가 잘 나가지 않아서  1% 올리는 것도 정말 힘들게 됩니다. 열심히 해도 표시도 잘 안나는 영역에 도달하면, 개발자도 관리자도 모두 힘들어지는 것입니다.

그 숨겨진 1%를 찾기 위해서 엄청난 고생을 해야할 때가 많습니다. 그것을 도구를 (어찌보면 반칙일 수 있는..) 사용해서 달성하는 것이 가능하다면 그만큼 가치가 있다고 생각합니다.

그외에도, 숨겨진 최적화 옵션을 찾아서 적용해보면 더욱 빨라 질수 있을것입니다.

물론 최고의 최적화는 사람의 머리입니다.(일명 손파일러, 헤드파일러). 아무리 툴이 발달하고, 좋아져도, 결국 궁극의 최적화는  사람의 머리에서 나오는 알고리듬 효율의 극대화입니다.  하지 않아도 되는 일을 열심히하는 컴파일러의 작업을 최적화하는 것 보다는 그런것을 찾아서 삭제하는 사람의 머리에서 나오는 최적화가 훨씬 좋다는 것은 당연하겠지요.

(주) OpenCV를 ICC로 빌드해놓긴 헀습니다만 속도 비교할 만한 예제를 찾지 못하였습니다.

      - 빠른지 어떤지를 확인하기 위해서는 가능하면 무거운 프로그램을 가지고 테스트를 해야 하는데요

        그정도로 무거운 프로그램을 돌리지 않아서 비교하지 못하였습니다

사실대로 말하자면, 맥에서 개발하는 것은 C/C++ 프로그램 정도입니다.

GUI가 필요하면 QT를 불러서 해결하지 코코아 라이브러리 부르지 않습니다.

일반 터미널에서 코딩하는 정도여서 윈도우즈에서 시그윈을 써서 개발하는 것과 큰 차이는 없습니다.

맥용 인텔 컴파일러를 써서 빠르다고 하여도, 리눅스용이나 윈도우즈 용이 없는 것도 아니고..

더구나 VTUNE이 매킨토시 용은 없기 때문에 프로파일링 하기에는 오히려 불편하지요...

마지막엔 개발이 다 끝나면 호환성 문제로 윈도우즈나 리눅스용으로 다시 옮겨야 하기때문에 복잡한 시스템 함수는 가급적 배제하고 코딩합니다.

일전에 H.264 SVC 프로그램을 맥북 프로에서 인터넷에서 구한 소스 코드 그대로 컴파일하여 테스트 해보았습니다.

그 결과 윈도우즈 시그윈에서 컴파일한것 보다 2배 정도 빨라졌습니다. 소스는 거의 손도 안되었는데 말이죠.

거짓말이라고 생각하시는 분들은 한번 맥에서 컴파일 해보세요 정말 빠르거든요.

물론 이것은 쓰레드를 잘 지원하는 MAC OS의 능력에 힘입은 바가 큽니다.

주요 Job인 ASIC 설계용 프로그램들은 대부분 서버에서 동작하니까 서버를 불러오면 되는거라서

결국 맥에서는 맥다운 프로그램을 하지 못하는 게 되네요

그럼 맥을 개발 시에는 언제 쓸까요 ?

우선 C/C++을 이용해서 대용량 그래픽 처리 시스템을 개발할때 쓰면 정말 좋아요.

플랫폼이 인텔 플랫폼과 완전히 틀려서 속도 잘 나옵니다.

QT하고 OpenCV를 써서 GUI하고 그래픽 처리를 하게 하니, 속도 잘 나옵니다.

이런 경우외에는 그닥.. 쓸만한데가

아, 하지만 누가 뭐래도 가장 큰 만족은 “가오” 이펙트..

폼생 폼사 맥으로 사는 것이 그래서 결국은 “가오” 이펙트가 커서 입니다.

왜 "가오"라고 이야기하냐 하면은..

그 외에도 맥이 안정성이 뛰어나고 GUI가 정말 유저 "쁘랜드리" 하다고 하여도, Mail.app가 가지는 편리함이 이렇쿵 저렇쿵, iCAL이 얼마나 좋은지.. 써보지 않고는 알수 없는거라서

내가 코딩한 프로그램이 얼마나 빨리 도는지 설명을 하여도 믿지 않아서.. (T  T)

그냥 사람들에게 이야기할 때는 가오라고 이야기합니다. (OTL)

그래야 "맥을 써보지도 않은" 사람들이 납득하더라구요.

그런사람들에게 침이 튀도록 이야기해도 잘 안되기 때문에 더욱 그렇습니다.

제발 "써보고" 아니라고 이야기해주면 좋을텐데 말이죠

토요일에는 정말 오래간만에 시간이 되고 마침 마나님과, 애기들이 외근나가셔서, 시간이 났습니다.

뒹굴거리던 중에 맘잡고 건담 박스를 꺼내서 맘놓고 편하게 만들었습니다.

덕분에 개별적으로 만들어 왔던 팔과 다리 등등이 이제는 완전하게 합쳐저서 어느정도 형태를 갖추는데 까지

진행을 하였습니다.

그동안 만든 건담도 많지만, 아무래도 애기들이 집에 있으니까.. 스프레이를 뿌려대야 하는 컬러링은 못하고 있습니다. 애기들이 못들어올 전용 공방도 가지고 있지 않으니 계속 컬러링이 그렇게 심하게 필요하지 않는 PG급 건담만 만들고 있습니다.

조금씩 조금씩 만들어가면서 완성시키는 재미에 건담 하나 완성시키는데에는 평균적으로 6개월 넘게  걸리는 것 같습니다.

요근래 만드는 것은 원형 건담인 RX-78입니다.

뒷북이라 생각할수 있지만,

산 순서대로 만들어가기 때문에 지금에서야 원형 건담을 만들고 있습니다.

아무로 레이 전용기이고,

아무래도, 오리지널로서의 가치가 충분한 건담이지요.

이거 다 만들고 나면 뒤에 대기하는 것들은  RX-78 GUNDAM GP1 + Zephyranthes 와 Strike Rouge GUNDAM의 귀여운 박스들이 대기하고 있습니다. 둘째가 스트라이크건담 박스위에서 뛰는 바람에 조금 찌그러져 있습니다. (흑흑..)

이거 다 만들면 또 쉽게 1년을 넘길텐데 하고 있습니다.

- 그래도 **쿠 적인 습성이 있어서인지 새로운 PG급 제품을 하나더 질르려고 이리저리 찾아보고 있습니다.

- 다음은 그분 전용의 샤크하나를 사야 할듯..

이번에 새로 나온다는 PG급 건담인 "아스트레이 레드 프레임"은 예전의 모 게임에서 보았던 로봇이랑 비슷한 디자인이 되어서 그닥 끌리지는 않네요

건담은 건담으로서의 맛이 있어야 하는데, 요새 나오는 건담들은 게임에서 튀어나오는 것 같아서 씁쓸합니다.

            - 무엇보다도 저 긴 칼을 발도한다는 "건담 발도제" 가 가능한 진보된 프레임이 특징입니다.

건담은 전장에서 뛰쳐나온듯한 느낌이 정말 매력인데 말이죠.

시대가 전쟁을 겪지 못한 세대이니만큼 아무래도 감정 이입이 전쟁이라는 테마보다는 게임이라는 테마에 익숙한 사람들이어서

건담 역시 전쟁을 가장한 게임이라는 느낌으로 만들어지고 있는것도 무시못할 영향입니다.

무엇보다도 반다이의 엄청난 건담 물량전 상술로 인해서,

애니메이션 한편에 건담 한부대씩은 나와야 장사가 될거라는 압박감이 건담으로서의 희소가치와 존재 가치를 떨어트리고 있습니다. 개인적으로는 건담 한부대 보다는 미소녀 호감도가 (라고 쓰고 헨타이 포인트 라고 읽습니다.) 높은 미소녀 한부대 애니가 더 장사가 될거라는 믿음을 가지고 있습니다.

샤아의 박력을 계승하지 못하는 붉은색 장난감들

아무로의 고뇌를 느끼지 못하는 건담들을 보면, 아쉽기도 합니다.

그나저나 PG급으로 KOG라던다, 레드 미라쥐를 만들면 대박일텐데, 이건 안되겠죠.

PG라는 좋은 시스템에, 좋은 컨텐츠를 올릴 생각을 하지 않는지 쩝..

FSS의 팬의 한사람으로서 아쉽습니다.

여담이지만,

친구들과 오래간만에 등산을 가면서 이런 저런 이야기들을 했다가 들은 이야기가

요새 세대들은  FSS에 아무런 관심이 없다는 충격적인 (?) 이야기를 들었습니다.

나가노 선생이 딴짓거리 해서 발생한 일이지만, 쩝..  

시대를 초월하는 힘이 있을거라 생각했던 F.S.S.도

사라져가는 것 같아 아쉽습니다.

(주) 글을 읽기 전에 

이 글은 저와 같은 OpenCV초보자를 위해서 정리하는 것입니다.

전문가시라면 굳이 읽을 필요가 없습니다.

공부하면서 정리하는 글이라서 서툰 부분이 많이많이 보입니다.

이번에는 이미지 마스킹을 수행합니다.

마스킹이라는 것은  한장의 이미지에서 원하는 부분만을 추출해 내는 역활을 합니다.

이것은 앞서의 이미지 추출과는 조금 틀립니다.

이미지 추출은 정해진 영역에서 그냥 추출해 내는 것이고

마스킹은 필요없는 정보를 걸러내어서 원하는 이미지를 찾는 것입니다.

마스킹을 한다면 당연히 AND연산입니다.

OpenCV에서는 And연산을 2가지 종류로 제공해 줍니다.

cvAnd와

cvAndS입니다. 끝에 S가 붙어 있다는 점이 틀린것 이외에도 두 함수의 차이는

전자는 이미지와 이미지를 대상으로 하지만, 후자는 이미지와 Scalar값을 대상으로 한다는 점이 틀립니다.

일단 이번에는 cvAnd를 가지고 하여 보도록 하겠습니다.

코드는 갈수록 단순해지네요..

프로젝트 따라서 필요한 기능을 찾아가면서 정리하는 거라.. 복잡한 쪽으로 이동하지 않고 단순한 쪽으로 이동해서 그렇습니다.

===========

결과 이미지는 아래에 올려둡니다.

(주) 글을 읽기 전에 

이 글은 저와 같은 OpenCV초보자를 위해서 정리하는 것입니다.

전문가시라면 굳이 읽을 필요가 없습니다.

공부하면서 정리하는 글이라서 서툰 부분이 많이많이 보입니다.

이미지에서 특정 부분 추출하기

cvCopy(

const CvArr * src,

CvArr *          dst,

const CvArr * mask = NULL

);

이것은 원본과 복사 대상이 같은 크기와 , 같은 타입의 이미지라는 전제하에서 이루어 집니다.

이미지의 크기가 틀리다면, 다음 함수를 써서 원본의 이미지중에 일부를 추출할 수 있습니다.

void cvSetImageROI( IplImage* image, CvRect rect );

CvRect는 사각형 영역을 설정하는 것입니다.

cvRect는 다음과 같이 정의되어 있습니다.

그럼 이제 이미지를 복사하여 만들어 보는 것을 해보겠습니다.

소스는 간단해서 그닥 어려운 부분이 없습니다.

원본에서 ROI를 지정한 뒤에 복사하면 잘 됩니다.

--------------------------------------------------------------------------------

아래 그림은 결과 이미지입니다

(주) 글을 읽기 전에
이 글은 저와 같은 OpenCV초보자를 위해서 정리하는 것입니다.
전문가시라면 굳이 읽을 필요가 없습니다.
공부하면서 정리하는 글이라서 서툰 부분이 많이많이 보입니다.

OpenCV로 하는 Rotate를 해보도록 하겠습니다.

1) 공간 확보와 정리
먼저 생성될 공간을 확보해야 하는데요
IplImage *image = cvCreateImage(cvSize(width, height), depth, nChannels);
size는 말 그대로 창의 크기를 말합니다.
depth는 영상을 표현하는 정보의 내용을 의미합니다.
 • IPL_DEPTH_1U : 1비트 양의 정수영상
 • IPL_DEPTH_8U : 8비트 양의 정수영상
 • IPL_DEPTH_16U : 16비트 양의 정수영상
 • IPL_DEPTH_32U : 32비트 양의 정수영상

이 됩니다.

nChannels는 색의 종류를 의미하는 것으로 1이면 흑백 3이면 컬러가 됩니다.

사용을 다 하면 정리해줘야 합니다.
물론 프로그램을 빠져나갈때 정리를 하지 않아도 O/S가 뒤져서 찾아가는 경우도 있지만
원칙은 사용한 프로그램이 다시 그것을 O/S에 돌려줘야 한다는 것입니다.

cvReleaseImage(&image);

를 하여서 정리합니다.

(2) cvPoint2D32f
 2차원 좌표 상에서 32비트 플로팅 포인트로 x와 y좌표를 설정합니다.

(3) WrapAffine
affine transform을 수행합니다.
인자는 다음과 같습니다.

void cvWarpAffine(
 const CvArr* src,  당연히 원본 이미지
 CvArr* dst,    이것도 당연히 결과를 받아내는 이미지
 const CvMat* map_matrix, affine transform을 하는 매트릭스
    int flags=CV_INTER_LINEAR+CV_WARP_FILL_OUTLIERS, 이것은 인터폴레이션을 선택
    CvScalar fillval=cvScalarAll(0)     채워지는 값
);

결과 그림은 아래와 같습니다.

http://homepage.mac.com/bradster/iarchitect/shame.htm

제목이 특이한데요.. 예전부터 유저 인터페이스에 쬐끔 관심을 가지고 있어서 이것 저것 살펴보다 발견한 사이트입니다.

제목 그대로 그렇게 좋은 인터페이스가 아닌 것들만 모아서 발표한 것입니다. 사이트는 mac.com에 있습니다.

역쉬 맥이라서 그런지 인터페이스에 자신감을 팍팍 가지고 있으니까.. 이런 사이트도 만들어 두는 것 같습니다.

1. 예제로 찾아보면 인터페이스 가이드라인에 따르면, 화면상의 버튼은 활성화가 안되면 활성화가 안되어 있다는 것이 버튼의 이미지로

나타나는 것이 좋다고 합니다. 그래야 유저가 아예 그 버튼 근처로 마우스를 움직이지 않고 다른 해결책을 찾는다는 것입니다.

그런데 아래 그림에서 처럼 MSOffice 95에서는 이런 기능을 아예 고려하지 않았습니다.

“아마 MS의  GUI 디자이너가 이런 비 활성화 그림을 싫어한것 같아서 이렇게 했다” 라는 추측성 글까지 달아놓을 정도로

안좋은 인터페이스의 예가 되었습니다.

2. 아래 글을 읽을 수 있곘습니까 ?

폰트의 가독성이 얼마나 중요한지 나타내는 예제입니다.

위의 그림은 큰 조직의 커다란 소프트웨어 관리 시스템을 위한 교육 자료에 나오는 예제입니다.

이것은 배경에서 부터 폰트 , 색깔 등으 완벽하게 어우러져 가장 안좋은 자료의 예제가 됩니다.

3. 잘못된 GUI

아래 그림을 한번 보시고 잘못된 부분을 찾아보시기 바랍니다.

어디가 잘못되었을까요 ?

바로 탭 윈도우 ( 다이얼로그 박스 위에 있는 선택 탭을 말합니다.) 내에 OK와 Cancel같은 버튼을 배치하였습니다.

그럼 만약 유저가 Character Spacing에가서 이리저리 조절한 뒤에 다시 Font로 와서 OK를 눌러야 하는

불상사가 발생합니다.

아니면 이런 불상사를 방지하기 위해서는 OK 버튼을 양쪽 탭에 모두 배치해야 합니다.

이 예제는 바로 MSWord 6.0에 있던 것입니다.

신기하죠..

그런데 이런 버튼 배열이 없어지지 않고 Office 95까지 내려옵니다.

이런 오류(?)가 지속적으로 살아남는 것은

뭔가 내부에 정확하고 지조 있는 관리 지침이 있으니까 이런 것도 가능하겠구나 생각되는 예제이죠.

4. 탭 윈도우의 또다른 예제

다음 그림은 어디가 잘못되었을까요 ?

어디가 대분류고 어디가 소분류인지 아예 모르도록 디자인 된것이 잘못입니다.

또한 화면의 크기를 고려하면 TAB이 너무 많이 배열되어 있어서 정작 필요한 내용 채우기는

부족해진다는 것이 잘못된 부분입니다.

이것은 IBM에서 만든 주소록 관리 프로그램입니다.

대기업도 이런 실수를 한다는 전형적인 예입니다.

- 음.. 에전에 이 프로그램을 써본적이 있는데

마지막으로

마지막은 인터페이스가 아니고 프레젠테이션에서 수치스러운 / 가장 못난 작품을 이야기할때 항상 나오는 사진입니다.

유명한 빌게이츠의 졸음을 부르는 프레젠테이션 사진입니다.

뭘 설명하는지 본인은 알까요 ?

유클리드 제곱 거리

이 부분의 구성은 이곳에서 인용하였습니다.

http://www.cherrynet.co.kr/bbs_view.php?s=37&pseq=11&mnid=1

다차원 공간 상에서 두점 사이의 거리를 구하는 것을 말합니다.

다차원이라고 해도 2차원상의 거리를 구하는 것과 비슷한 방법입니다.

두 점을 (p₁, p₂, p₃, p₄,...)와 (q₁, q₂, q₃, q₄, ...)로 표기한 경우 유클리디안 거리 공식은 아래와 같습니다.

def euclidean(p,q) :

     sumSq = 0.0

     # 차의 제곱을 더함

       for i in range( len(p) ) :

                sumSq += ( p[i] - q[i] ) **2

     # 루트를 취함

       return ( sumSq**0.5 )

Rob Hess의 SIFT 

1. kd-tree 란..

http://snisni.net/98

http://zupet.tistory.com/272  - Kd-Tree 구현 참고 사항

http://zupet.tistory.com/395   kd-tree <- 꼭 참고 ~~ 

에 있는 자료를 기반으로 하여서 정리하였습니다. 

개인적으로 이해를 위해서 정리한 자료이니, 이해가 가지 않으시는 분들은 위의 사이트에서

참고하여주시기 바랍니다.

제목인 kd-tree에서 k란 다차원 인 k차원의 공간을 의미합니다.

즉 다차원 트리를 만들고 정리하는 것을 말합니다.

실제로는 binary-tree의 확장 버전으로 이해하시면 됩니다.

공간을 다루는 dB로서 문자 기반의  dB와는 다르게 됩니다.

key 값을 matching 시키는 문제이고, 공간 기반에서 검색합니다.

공간 기반의 검색이란 range 로 표현되는 질의어를 기반으로 검색한다는 뜻입니다.

spatial data는 (공간 데이터는) 점과 선, 다각형 등을 포함하고 있습니다. 이러한 공간상의 데이터를 뒤져서 원하는 값을 찾아내어야 하는데

공간 데이터를 효율적으로 처리하기 위해서는 다음과 같은 특징적 어려움을 알아야 합니다.

① First, spatial data are latge in quantity, complex in structures and relationships

    첫번쨰, 공간 데이터는  크고, 복잡한 구조와 관계를 가지고 있습니다.

② Second, the retrieval process employs complex spatial operators like intersection, adjacency, and containment

   둘째로, 탐색 과정은 복잡한 공간 연산을 기반으로 구현됩니다. 예를들어서

   교차점 탐색, 인접 물 탐색, 묶어 탐색 등등..

③ Third, it is difficult to define a spatial ordering, so conventional techniques cannot be employed for spatial operations

→ spatial indices 필요!

3번째는, 공간상에 순서를 정하는 것이 어렵다는 점이다. 그래서 일반적인 방식으로는 공간상에서 dB를 구성하는 것이 쉽지 않다.

- 공간 인덱스가 필요해진다.

1.1  kd-tree : Binary-tree based indexing

kd-tree는 multi-attribute data index를 binary search하는 tree로, 

k는 표현될 데이터 공간의 차원을 가리킵니다.

각 depth에서, 어떤 branch로 갈 것인가를 결정하는 데에 다른 attribute가 사용이 됩니다.

예를 들어, 2-d (x,y) tree에서는 짝수 depth에서 x 좌표가 branch 기준이라면, 

홀수 depth에서는 y 좌표가 branch 방향의 기준이 됩니다.. 

마지막으로, 이 tree는 꼭 균형을 이룰 필요는 없습니다. 

위의 그림을 보면 제일 먼저 X값을 기준으로 중앙에 있는 A를 선택합니다.

따라서 최초 분리자는 ROOT이며 이것이 A가 됩니다.

이제 다시 A를 가지고 Y축으로 값을  분리합니다. 그럼 B와 E가 선택이 됩니다.

{ 

NOTE : 

의문 사항 : A다음에 B와 E를 택하는 이유는 무엇일까 ?

F와 C가 되지 않고 말이지...

답   : B 가 선택이 되는 이유는 A를 중심으로 좌우를 분리하면

좌측에 B/C/D가 존재한다. 이 점에서 Y값을 기준으로 정렬해보면

B가 가운데 온다. 따라서 B가 선택이 되는 것이다.

우측은 그냥 E와 F가 있다 2개의 값이므로 아무값이나 하나 선택

한것이다.

의문사항    : 정말 아무값이나 선택해서 E일까 ?? 

}

B와 E에서 다시 X 축 기반으로 각각 C/D 및 F를 분리합니다.

위의 사항을 그림으로 표현하면 다음과 같습니다.

1.2  Principle

각각의 Node는 각각의 실제 data point를 나타내고, 검색 방향의 지표가 됩니다. 

(left, right 두 개의 child가 있습니다.→ 현재 노드 값 보다 작은가? 큰가?)

한 Node는 5개의 field로 구성되어 있습니다. 

LEFT  Node를 가리키는 포인터 : LOSON(작은 값을 가진 left 자식), 

Right Node를 가리키는 포인터  : HISON(큰 값을 가진 right 자식), 

좌표 값 (x,y,...), : 차원에 따라서 그 차원의 개수만큼 늘어납니다. 

NAME(해당 노드에 대한 정보. 포인터가 들어갈 수도 있다.), 

DISC(좌표 이름을 가리킨다. 즉, 이 노드는 x를 기준으로 했느냐 y를 기준으로 했느냐. 등. ).

1.3  삽입 Insertion

Tree Build에 해당합니다.

Binary search tree에서의 insertion 방법과 유사합니다.

다른 점이 있다면, 앞에서 설명 했듯이, depth마다 비교하는 attribute가 다르다는 것입니다.

 tree의 bottom에 도달하면, 거기에 새 node를 삽입(Insertion)합니다. 

2개의 함수를 먼저 정의합니다.

1) 비교 주어진 노드의 값을 비교하여 값을 반환합니다.

2) 삽입

      2개의 노드 포인터가 주어집니다. 

      하나는 삽입해야할 즉 추가 해야 할 노드 이며,

      다른 하나는 그때 참조하는 값에 해당하는 노드입니다.

Procedure KD_COMPARE(P,Q)

/* 주어진 노드 Q를 기준으로 P가 붙어야할 위치가 어딘지 판단한다.*/

value pointer node P,Q

direction D

기준값을 X축 값을 가지고 해야 한다면 

{

P의 X 좌표가 Q의 X 좌표 보다 작다면

노드의 왼쪽에 붙어야 하고

아니면 오른쪽에 붙어야 한다.

}

아니면

{

P의 Y 좌표가 Q의  Y 좌표 보다 작다면

노드의 왼쪽에 붙어야 하고

아니면 오른쪽에 부터야 한다.

}

붙어야 할 방향 정보를 반환한다.

삽입 ( Insertion)

KD_INSERT(P,R)

value pointer note P : 삽입해야할 노드 이다.

reference pointer note R :  기준 노드를 의미한다.

pointer note F,T

direction Q

만약 R이 NULL 이면,  즉 기준 노드가 없다면 

{

R <- P // 기준 노드는 P가 되고

DISC(P) <- 'X'; // P의 기준 값은 X축 값으로 한다고 표시한다.

}

아니면 즉 기준 노드가 있다면, 

{

   T <- R  /* 

기준 노드인 R을 임시 값으로 복사한다. 이것은

아래 트리 탐색을 위한 반복문에서 반복시 사용되는 인자를

세팅하기 위함이다.

*/

   임시 노드 T가 NULL이 아니고, EQUAL_COORD(P,T) 가 아닌 동안 계속 해서

   {

          F <- T ; /* 직전 노드값을 기억하여 두고 */

  Q <- KD_COMPARE(P,T); /* 삽입할 값과 비교하여 방향을 

    찾아낸다.*/

  T <- SON(T,Q); /* 찾아낸 방향의 노드를 다시 꺼낸다. */

....

/* 꺼낸 노드가  NULL이 아닐때 까지 반복...*/

   }

만약 T가 NULL 이면, /* 즉 트리최종 말단까지 도착하면  */

  {

SON(F,Q) <- P; /* 직전노드의 찾아낸 방향에 P를 삽입한다.

DISC(P) <- NEXT_DISC(F); /* P의 참조 기준 값은 직전 노드의 다음 값이 된다. 

    즉 F의 참조 기준 값이 X였다면, Y가 되고     Y였다면, X (혹은 3차원일 경우 Z) 가 된다.

*/

  }

}

차근 차근 따라가면서 읽어보면 이해 할수 있는 내용입니다.

1.4 탐색 Search

Search 역시 매우 straightforward하다. 흐흐 BST 처럼 찾아 내려가면 된다. 

여기에서 역시, 다른점은 depth마다 비교 기준의 attribute이 다르다는 점 뿐. 

참 그리고, 질의가, 조건 질의가 가능하다는 것이 또 하나 틀린데, 

예를 들어, 'Y>20인 점들을 찾아라' 라든지, '(75,15)에 가까운 점들을 찾아라' 등이 가능하다는 것이다. 

Region Search는 Euclidean distance를 이용하여 구할 수있다. 

node (a,b) 근처 거리 d안에 있는 점들을 다 구하라는 질의가 들어오면, 

우선 (a-d) ≤ x ≤ (a+d), (b-d) ≤ y ≤ (b+d) 안의 점들을 다 구한다. 

그런데 이렇게 구한 점은, 반지름 d인 원 안에 있는 점이 아니라, 

한 변이 2d인 정사각형 안에 들어오는 점이므로, 점들을 구한 다음에 range안에 들어오는 게 

맞는지 확인이 필요하다. 

우선 다음과 같이 트리가 준비되어 있다고 가정하고요

(88,6)을 기준으로 3개의 점 범위 내에 있는 모든 도시를 찾아라 라고 한다면

(85~91 , 3~9)까지가 된다.

따라서 좌측 상단은 ( 85,3 ) 이 되고 우측 하단은 (91,9)가 된다.

우선 처음에 찾는 값은 85,3으로 찾는다. 기준값과 비교해서 오른쪽에 해당함을 확인할 수 있다.

91,9를 가지고 MOBILE을 참조값으로 하여 찾으면 왼쪽 값이 나온다. 

이때 사용되는 참조 변수는  Y축 값인 9이다.

마지막 노드의 값이 NULL이고, 

좌우 범위 내에 들어간다면, OK이다.

최종 그림은 아래와 같이 된다.

붉은색 점선 원이 탐색 범위이고, 마이애미가 범위내에 들어감을 확인할 수 있다.

1.5  삭제 : Deletion

앞에 insert나 search는 BST와 비슷하기 때문에 쉽지만 , deletion은 복잡합니다. 

각 depth마다, DISC가 달라서, 원래 tree의 root는 DISC가 x 지만, subtree의 root는 y가 될 수도 있기 때문에, 

모든 subtree가 kd-tree가 아니다. 그래서 그냥 마구 삭제해 버리면 문제가 생긴다. 

kd-tree로 부터 (a,b) 노드를 삭제한다고 할 때, (a,b)의 두 subtree가 empty tree이면 그냥 삭제하면 되고, 

아니면 (a,b)의 subtree들 중에서 가장 적절한 대체 노드 (c,d)를 찾아서, replace시킨킵니다. 

이 (c,d)는 recursive하게 다시 삭제되는 것이다. 그렇다면, 이 대체 노드는 어떻게 찾는 것일까? 

오른쪽 subtree에서 가장 작은 값을 가진 노드나, 왼쪽 subtree에서 가장 큰 값을 고르면 된다. 

그러면 다음의 예를 보자. 

그림과 같이 A가 최상위 노드로 되어 있는 상태이다.

여기서 하나의 노드를 삭제한다. 하필이면 A를 삭제하기로 한다.

그럼 A가 삭제된 상태에서 노드를 구성하는 동작을 하게 된다.

우선 A가 삭제되었으므로, A의 X축 값에서 가장 가까운 노드의 값을 선택한다. 

예제의 경우 C가 되고 우연히도 C가 A의 바로 밑에 있으므로 개념상 C를 올린다.

{

의문 사항 :

최소값이라고 하였는데 이것을 가장 가까운 값으로 해석해야 하는것인지 궁굼하다.

}

그럼 오른쪽 개념처럼 기준선이 움직인 셈이 된다.

그럼 C를 기준으로 최소  Y값은 우연히도 D이므로 D를 한단계 끌어올린다.

그럼 개념상 오른쪽 그림처럼 된다.

D에서 X 값으로 최소값은 H이므로 이것을 선택한다. 이때 H는 한단계 더 하위 계층이므로 이것을 끌러 올린다.

이때 I가 G보다 X축 값이 작으므로 왼쪽으로 붙는다.

1.6  장단점

kd-tree는 partial matching search에 유용하지만, empty space가 없고, 

point search와 region search가 다 가능하다. 하지만, 균형이 심~하게 안맞으면 performance가 안좋다. 

kd-tree는 메모리 기반 index이다. File 기반에서는... 안좋다

1.7 응용처

응용하는데 중에서 쉽게 찾을 수 있는 것은 폴리곤의 분류이다.

3차원 그래픽도 당연히 다차원이므로, 공간세어 객체를 뿌려놓고 찾아서, 렌더링을 해야 하는데 이럴때

kd-tree를 사용한다.

당연히 속도 문제가 이슈가 되기 때문에 여러가지 방법과 논문이 제안되고 있다.

삭은이 님의 블로그에서 보면

논문을 하나 추천하고 있다.

http://www.cgg.cvut.cz/members/havran/ARTICLES/ingo06rtKdtree.pdf

Rob Hess의 SIFT

앞서 두번에 걸쳐서 Rob의 코드를 컴파일해서 정상적으로 움직이는 것을 확인하였습니다.

이제 코드 내부가 어떻게 동작하는지 확인을 해보겠습니다.

SIFT자체는 나중에 따로 정리하기로 하고 전체 맥락을 한번 따라가는 형식으로 정리하였습니다.

이번에는 전체 코드를 한번 찬찬히 따라가면서 정리하였습니다.

그냥 코드를 읽는 수준이므로 큰 무리 없이 따라가면 됩니다.

OpenCV에 기반하므로, 그냥 이런 함수가 있다고 보고 읽어 가면 됩니다.

1. dspFeat의 분석

dspFeat를 먼저 코드를 보곘습니다.

이 프로그램은 그냥 SIFT를 대상 이미지에 올리는 그림입니다.

별다른 어려운 부분이 없읍니다.

시작 부분에서 두개의 파일을 먼저 설정하고 있습니다.

char* feat_file = "..\\beaver.sift";

char* img_file = "..\\beaver.png";

앞서의 것은 beaver.sift 의 결과물입니다. 텍스트 파일로 되어 있네요

두번째 것은 png format 으로 되어 있는 이미지 파일입니다.

이다. 큰 문제점은... 은 없네요~ 

draw_feature()함수를 나중에 따로 정리하여야 하겠습니다.

이것은 SIFT를 정리하면서 하면 되므로 여기서는  SKIP...

2. match의 코드 따라가기

그럼 이제 두번째로 match를 한번 따라가 보겠습니다.

여기서는 KDTree를 이용해서 공간상에서 dB를 구축하였음을 알수 있습니다.

다음에는 이것을 좀더 자세하게 따라가 보겠습니다.