CH8. 트리(Tree) 3 (이진 트리의 순회 (Traversal))

• 재귀를 사용하면 어렵지 않게 구현 가능

순회의 세 가지 방법

• 순회 기준은 루트 노드를 언제 방문하느냐에 있음
  • 루트 노드 방문하는 시점에 따라 중위, 후위, 전위 순회로 나뉨
• 각 하위 노드는 노드가 아니라 하나의 또다른 이진트리로 보면 됨
  • 각 이진 트리 접근 시 최 말단 이진트리의 접근이 끝나야 상위 트리의 접근이 가능함

순회의 재귀적 표현

• 중위 순회
  • 왼쪽 서브 트리의 순회 -> 루트 노드 방문 -> 오른쪽 서브 트리의 순회 순으로 참조

• 위 코드는 탈출 조건이 명시되지 않은 불완전한 코드

순회의 재귀적 표현의 완성

• 탈출 조건
  • 왼쪽/오른쪽에 하위 이진트리가 아닌 노드가 있는 경우 탈출

결과물

• 하위 트리 모두를 참조한 후 상위 트리가 순차적으로 참조됨

전위 순회와 후위 순회

• 동일한 코드에서 순서만 바꾸면 됨

노드의 참조를 자유롭게 구성하기

• 여태까지 코드는 노드의 참조를 print로만 한정시켜 동작
• 실제로는 포인터함수를 이용하여 다양한 연산이 가능함
  • 즉, 트리의 사용자가 노드 방문 목적을 직접 정의 할 수 있음
• 위 예제에선 void 형 함수를 사용했지만, int형 등 다양하게 구성하여 사용

CH8. 트리(Tree) 2 (이진 트리의 구현)

• 이진 트리를 구현할 수 있는 ‘도구’를 만드는 작업

이진 트리 구현의 두 가지 방법

• 배열 기반의 방법
  • 노드에 번호를 부여하고, 해당하는 값을 배열의 인덱스로 사용
    • 완전 이진트리 순서와 동일하게 인덱싱
    • 접근이 용이함
  • 편의상 배열의 첫 번째 요소는 사용하지 않음
  • 배열을 이용했을 때 쉬운 적용상황이 있으므로 쓸 데가 있음
  • 배열 기반의 이진 트리의 구조와 실제 리스트 구현에는 구조가 일지하지 않음
• 연결 리스트를 이용한 방법
  • 트리의 구조와 실제 구현된 구조가 일치
    • 양방향 연결리스트로 구현
  • 직관적인 이해가 좋은 편

헤더파일에 정의된 구조체의 이해

• 양방향 연결 리스트의 구현에는 두 구조체가 정의되어야 함
  • 구조체 1. 노드 구조체
  • 구조체 2. 양방향 연결리스트 구조체
• 이진트리는 노드 자체가 이진트리이므로 하나의 구조체로 정의됨
• 핵심

typedef struct _bTreeNode
{
  BTData data;
  struct _bTreeNode *left;
  struct _bTreeNode *right;
} BTreeNode;

• 위의 구조체가 노드 자체이자 이진 트리이며, 모든 노드는 직/간접적으로 연결되어 있음
  • 즉, 루트 노드의 주소값만 이용하여 트리 내 모든 노드에 접근 가능함

헤더파일에 선언된 함수들

• 함수 이름에 SubTree가 들어가는 이유?
  • 노드 자체도 하나의 하위 이진트리로 보기때문에 더 올바른 표현!

정의된 함수들의 이해를 돕는 main 함수

• 앞에서 정의된 함수들을 이용해 이진트리를 만드는 도구(노드/이진트리) 정의하고, main 함수에서 노드를 만들고 노드간에 연결을 하여 이진 트리를 완성

이진 트리의 구현

• 구현 자체에는 큰 어려움이 없으나, 기존에 연결된 노드를 삭제하는 과정에 대한 학습이 필요
  • 말단 노드의 경우 코드처럼 if문에서 free를 이용하여 간단하게 구현 가능
  • 하지만, 하위 노드가 존재하는 경우 해당 노드만 삭제하면 memory leakage가 발생!
    • 이진 트리의 순회로 해결
    • 나중에 memory leakage 없게 free 될 수 있도록 구현해보기

이진 트리 관련 main 함수

• 트리를 완전히 소멸시키는 방법으로는 이진 트리의 순회를 사용하며, 다음 세션에서 공부하고 적용해보기.

CH8. 트리(Tree) 1-2 (트리의 개요)

서브 트리의 이해

• 서브 트리는 서브트리로 구성된 재귀적인 구조를 가짐
  • 서브트리는 자신을 부모노드로 하는 또다른 자식노드들을 가짐
• 기본적으로 트리는 자식노드의 갯수제한이 없음

이진 트리의 이해

• 이진트리는 자식 노드의 갯수가 2개로 제한됨
• 조건
  • 루트 노드를 중심으로 두 개의 서브 트리로 나뉜다
  • 나뉜 두 서브 트리 모두 이진 트리여야 한다.
• 즉, 이진트리는 서브트리를 어떻게 자르던 무조건 이진트리 구조를 갖는다.
  • 재귀적인 특징을 갖고 있음
• 마지막 단의 노드 하나도 모두 이진트리로 볼 수 있음

이진 트리와 공집합 노드

• 이진트리? -> 하나의 노드에 최대 두 개의 노드만 추가 가능
  • 규칙을 벗어나지 않기 위해 공집합 노드 개념이 추가됨
• 공집합 노드는 공간은 존재하지만 유효한 데이터가 들어있지 않은 꼴
• 공집합 노드 또한 하나의 노드로 보면, 아래 사진의 모든 구조는 이진트리가 됨

레벨과 높이, 그리고 포화, 완전 이진 트리

• 트리의 레벨은 최 상단 부모 노드 인덱스를 0으로 시작
• 트리의 높이는 하단으로 뻗어가는, 자식노드로 이어진 길의 길이를 생각하면 됨
  • 트리의 톺이와 레벨의 최대 값은 항상 같음
• 포화 이진 트리?
  • 모든 레벨에 노드가 꽉 차서 더 이상 레벨이 유지된 상태에서 노드 추가가 불가능한 형태
• 완전 이진 트리?
  • 위에서 아래로, 좌에서 우로 채워진 이진 트리를 의미
  • 완전 이진트리는 새로운 노드(공노드에 유효한 데이터)가 추가됨에 따라 포화 이진 트리가 될 수 있음
• 특, 포화 이진트리는 완전 이진 트리지만, 완전 이진 트리는 포화 이진 트리가 될 수 없음.

Vehicle detection in the UAV imagery related papers

Hand crafted methods

Car Detection in Low Resolution Aerial Image (2001)

• https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=937593&tag=1

• Top-view 방식의 저해상도 사진에서 vehicle을 detection하는 방법
• 차량의 외곽과 앞유리 등의 edge 정보와 그림자 정보를 이용하여 차량을 detection하는 traditional 한 방법
  • 차량의 전체적인 shape에 대한 특징을 학습하도록 함
  • 이러한 feature들의 학습에는 bayesian network를 이용
• 일반화성능이 매우 좋지 못하므로 제한된 상황에서만 적용 가능하며, 오탐률이 큼

Autonomous Real-time Vehicle Detection from a Medium-Level UAV (2009)

• https://pdfs.semanticscholar.org/277c/adfadc4550fc781be7df8cb4ec89e54b793e.pdf?_ga=2.254030475.2079888018.1563806469-1988452867.1561287261

• Bird-view 방식의 UAV imagery에서 vehicle detection하는 방법
• Cascaded Haar classifier를 학습시켜 vehicle detection을 수행
  • 일반화성능이 좋지 못하므로 정확도가 떨어짐
• 일반화성능이 매우 좋지 못하며 제한된 상황에서만 적용 가능하고 오탐률이 큼

Real-time people and vehicle detection from UAV imagery (2011)

• https://www.spiedigitallibrary.org/conference-proceedings-of-spie/7878/78780B/Real-time-people-and-vehicle-detection-from-UAV-imagery/10.1117/12.876663.short?SSO=1

• Vehicle detection을 위해 cascaded Haar classifier와 thermal image를 사용

  • 일반화 성능이 떨어지는 cascaded Haar classifier, multivariate Gaussian shape matching을 사용
  • Thermal image를 얻기 위한 별도의 고가의 장비가 필요

Car Detection from High-Resolution Aerial Imagery Using Multiple Features (2012)

• https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=6350403

• Top-view 방식의 고해상도 사진에서 vehicle을 detection하는 방법
• Histogram of Oriented Gradients (HOG), Local Binary Pattern (LBP), Opponent Histogram, Intersection kernel support vector machine (IKSVM) 등을 이용하여 학습한 후, exhaustive search를 이용하여 vehicle detection을 수행 후, non-maximum suppression(NMS)를 이용하여 겹치는 결과들을 제거
• 일반화 성능이 떨어지므로 사용에 제한이 있으며 정확도가 떨어짐

Vehicle detection methods from an unmanned aerial vehicle platform (2012)

• https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=6294294

• Top-view 방식의 UAV imagery에서 vehicle detection하는 방법
• 움직이는 객체는 scale invariant feature transform (SIFT)와 Kanada-Lucas-Tomasi (KLT) matching algorithm을 조합하여 feature point tracking을 이용하여 찾으며, 움직이지 않는 객체는 도로를 찾은 뒤 blob information을 이용하여 탐지함
• 일반화성능이 떨어지므로 사용에 제한이 있고 정확도가 떨어짐

Detecting Cars in UAV Images With a Catalog-Based Approach (2014)

• https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=6719494

• Top-view UAV imagery에서 vehicle detection 수행
• 아스팔트 위의 차량만 찾도록 고안됨
• 아스팔트를 일단 찾은 후 해당 영역에서 수직/수평 방향의 필터링 연산을 수행하여 생성된 HOG feature를 이용하여 catalog에 등록된 reference car feature와의 유사도를 계산하여 vehicle detection을 수행
• 일반화성능이 떨어지고 사용에 제한이 있으며 정확도가 낮음

An Enhanced Viola–Jones Vehicle Detection Method From Unmanned Aerial Vehicles Imagery (2017)

• https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=7726065

• 원래의 Viola-Jones obejct detection method를 개선시켜 저 고도에서의 UAV imagery vehicle detection이 잘되도록 함
  • 다양한 방향을 갖는 영상에 대비되도록 도로를 수평방향으로 정렬시키는 과정이 필요함
  • Detection 후 tracker를 이용하여 tracking
• 일반화 성능이 떨어지는 hand crafted method

Deep learning methods

Fast Vehicle Detection in UAV Images (2017)

• https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=7958795

• 기존의 YOLO V2 구조를 그대로 이용하여 UAV imagery에서의 vehicle detection을 수행
  • YOLO V2의 구조적 단점을 거론해야 함 (작은 객체를 찾도록 최적화되어있지 않음)
• Image annotation과 data augmentation을 적용하였으며, 영상에서 vehicle을 annotate하기위해 CSK tracking을 적용함.
• 입력으로 416x416 크기 영상을 사용하며, GeForce GTX 1060에서 48ms의 속도로 동작함
  • 제안하는 방법은 33ms의 속도로 동작

Object Recognition in Aerial Images Using Convolutional Neural Networks (2017)

• https://webcache.googleusercontent.com/search?q=cache:Fic0MXgNDy0J:https://www.mdpi.com/2313-433X/3/2/21/pdf+&cd=4&hl=en&ct=clnk&gl=kr

• YOLO를 이용하여 UAV imagery dataset을 제안하고 모델을 학습시킴.
• 다만, YOLO의 hyper parameter들을 이용하여 최적화함
  • YOLO가 갖는 작은 객체를 잘 찾지 못하는 단점등에 대해 논해야 함
  • 또한 YOLO를 이용할 경우 저 고도에서 큰 객체밖에 찾지 못함
• Top-view 방식이며, 150FPS로 동작하지만 그 한계가 명확함

Vehicle Detection Under UAV Based on Optimal Dense YOLO Method (2018)

• https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=8599403

• YOLO v2의 구조를 활용하여 작은 객체를 잘 찾도록 최적화 된 네트워크를 제안하고, 이를 DOLO라고 명명
• Top-view 방식의 vehicle detection에서 정확도가 비교적 뛰어나지만, 단순히 YOLO의 네트워크를 깊게 하여 표현력을 증대시키고 Dense YOLO라고 하며 DOLO로 명명
• 또한 네트워크 전체의 깊이가 깊어짐에 따라 연산량의 증가폭이 큼
  • 실시간 동작이 가능하지만, 정확도가 좋은 모델은 연산량이 매우 큼

Real-time Vehicle Detection from UAV Imagery (2018)

• https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=8499466&tag=1

• 네트워크 구조가 복잡하고 느리지만 성능이 좋은 RefineDet을 최적화하여 UAV Imagery object detection을 수행

  • 구조를 그대로 사용한것이 아니라 default box의 크기를 작게 해 작은 객체 탐지에 최적화시킴

A Closer Look at Faster R-CNN for Vehicle Detection (2016)

• https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=7535375

• Faster RCNN을 사용하여 vehicle detection을 수행.(UAV 아님)

  • Faster RCNN 기반의 새로운 detector를 제안함

Inception-v4, Inception-ResNet and the Impact of Residual Connections on Learning

Original paper: https://arxiv.org/pdf/1602.07261.pdf

Authors: Christian Szegedy, Sergey Ioffe, Vincent Vanhoucke, Alex Alemi

• 참고 글
  • https://norman3.github.io/papers/docs/google_inception.html
• 2015년 ResNet을 Inception에 붙여보려는 시도를 보인 논문
  • 하지만 해당 모델은 Inception v4가 아니라 Inception-resnet 이라는 별도의 모델로 생성시킴
  • Inception v4는 기존의 v3모델에 몇 가지 기능을 추가시켜 업그레이드한 모델
  • 따라서 이 논문은 Inception v4와 Inception-resnet 둘 다 다루고 있음
    • 특히 resnet을 도입한 모델을 Inception-resnet이라 명명
    • 마찬가지로 Inception-resnet v1, Inception-resnet v2와 같이 별도의 버전들이 존재함
  • 실제로는 ad-hoc한 모델로 이 모델의 한계점을 시사
• Residual connections
  • 깊은 망의 학습시에는(classification) residual connection이 꼭 필요한것인지 구글 내에선 논의중이라고 함
  • 하지만 residual connection이 존재하는 구조의 경우 확실히 학습속도가 빨라지게됨(장점)

• 위 그림은 residual connection의 예시를 보여줌
  • 첫 번째 그림은 가장 간단한 형태의 residual connection 구조
  • 두 번째는 1x1 conv를 추가하여 연산량을 줄인 residual connection 구조
  • 즉, residual의 개념은 이전 몇 단계 전 레이어의 결과를 현재 레이어의 결과와 합쳐서 내보내는것을 의미

Inception v4, Inception-resnet v2

• Inception v4의 전체 망 구조는 아래와같음

• Inception v3와 마찬가지로 거의 유사한 형태의 네트워크 구성을 갖지만 세부적인 inception 모듈의 구성이 다름

Versioning

• Inception에 resnet이 추가되면서 버저닝이 생김
• Inception v3를 확장한게 Inception v4
• 여기에 Inception v3와 v4에 각각 residual connection을 적용한 버전이 Inception-resnet v1, Inception-resnet v2다.
  • Inception v3를 적용한 resnet은 Inception-resnet v1
  • Inception v4를 적용한 resnet은 Inception-resnet v2

Stem Layer

• Inception v3에서 앞단의 conv 레이어를 stem영역이라고 부름
• Inception v4에서는 이 부분을 약간 변경함
  • Inception-resnet v2 (Inception v4)에서도 stem영역은 동일하게 아래의 구조를 사용
• Stem 영역의 구조는 아래와 같음

• 이런 구조가 나오게 된 배경지식은 Inception v3에서 다루었고, Inception v4에서는 앞단의 영역에도 이런 모델이 추가로 적용되어있음
  • 아마도 이것저것 테스트해보다가 결과가 더 좋게 나오기에 이를 채용한듯 하다..

4 x Inception-A

7 x Inception-B

3 x Inception-C

• 위에서 설명된 Inception 모듈은 모두 입출력 크기의 변화가 없음
  • Inception 모듈의 input, output 사이즈를 의미
• 실제 크기 변화가 발생되는 부분은 아래처럼 reduction이라는 이름을 사용함

Reduction-A

Reduction-B

• Inception v4 모듈엔 새로운 컨셉이 등장하지 않고 기존의 Inception v3 모델을 이것저것 실험해보며 좋은 성능을 보인 case들을 조합해놓은것임

Resnet

• 논문에선 버전을 Inception-resnet v1과 v2로 구분하여 그림으로 설명함

• 특별한 내용 없이 residual connection만 추가된 구조

결과

• Resnet 도입으로 학습 속도가 빨라짐

• 위 그림은 Inception v3와 Inception-resnet v1의 error rate 수렴 속도를 나타냄
  • Resnet이 적용된 모델의 수렴속도가 훨씬 빠른것을 볼 수 있음
• 성능지표는 아래와같음