this.code();

🏢 ETRI (2024.01.05)

📖 공부! (9:00-12:00)

먼저 읽을 논문 리스트부터 뽑아보았다.

∙ Unsupervised Domain Adaptation of Object Detectors: A Survey (IEEE 2023)
∙ Deep Domain Adaptive Object Detection: a Survey (IEEE 2020)

∙ Domain Adaptive Faster R-CNN for Object Detection in the Wild (CVPR 2018)
∙ Multi-Source Domain Adaptation for Object Detection (ICCV 2021)
∙ Multi-Granularity Alignment Domain Adaptation for Object Detection (CVPR 2022)
∙ Progressive Domain Adaptation for Object Detection (WACV 2020)
∙ SimROD: A Simple Adaptation Method for Robust Object Detection (ICCV 2021) 
∙ ConfMix: Unsupervised Domain Adaptation for Object Detection via Confidence-based Mixing (WACV 2023)
∙ Domain Contrast for Domain Adaptive Object Detection (IEEE 2021) 
∙ Unsupervised Domain Adaptive Object Detection using Forward-Backward Cyclic Adaptation (ACCV 2020)
∙ One-Shot Unsupervised Domain Adaptation for Object Detection (IEEE 2020)
∙ A Free Lunch for Unsupervised Domain Adaptive Object Detection without Source Data (AAAI 2021)
∙ Object detection based on semi-supervised domain adaptation for imbalanced domain resources (Machine Vision and Applications 31 2020)
∙ Cross-domain adaptive teacher for object detection (CVPR 2022)

🍚 밥이다 밥!

마찬가지로 동편제(한식)... ETRI표 떡갈비 진짜 맛있었다!!(사실 경양식 불고기? 느낌이었지만)

🛠️ 서버 작업! (14:00-18:00) 

GPU 넣고 새로 OS(Linux) 깔고 작업하는데 힘들어 죽는줄ㅠㅠ

GUI에 문제가 있는 서버, Linux 접속이 안되는 서버 등등 GPU도 장착하고 약간 밑바닥부터 시작하는 느낌이어서 새롭기도 했고, 그동안 이미 만들어진 서버로 🍯빨고 있었던 것 같아서 좀 반성(?)도 되었던 시간이었다ㅎㅎ

🍚 밥이다 밥!

ETRI동기분들이랑 간단한? 식사를 가졌다.

미소야라는 곳에서 먹었었는데 총 12명(나포함)이 식당에 들어서니 한 공간을 다 차지해 버렸다.

식사로는 우삼겸 덮밥을 골랐다. (이름만 보고 골랐던게 진짜진짜 실수였다.)

우삼겸 덮밥....이게...?

내가 아는 우삼겹 덮밥은 간장소스 베이스로 만들어져야하는데

분명히 사진속에서는 약간 갈색빛이 돌았던 것 같았는데... 시뻘건 무언가가 왔다.

진짜 처음에는 다른사람 메뉴가 나한테 잘못 배달온줄 알았다.

매워 죽는줄 알았는데 감사하게도 물을 따라주셔서 살았다.(사실 이 글을 적는 지금도 배 아픈 것 같다)

🚲 퇴근! (21:00 -)

2차로 카페에서 아이스크림까지 먹고(다이어트 실패ㅋㅋㅋ)

당연히 자전거 타슈타고 퇴근했다. 퇴근길에 찍은 신세계 백화점은 멋있구만...

🏋🏻 운동! (22:00 -)

열심히 벤치프레스만 했다ㅎㅎ (하체는 자전거로 이미 유산소겸 하체운동겸 끝이라...)

현대인은 운동부족이랬나... 당연히도 매일같이 헬스장에 가서 운동을 하니까 난 상관없겠지?

근데 헬스장 밖에서 이렇게 찍으니 감옥같....ㅋㅋㅋ

📌 TODO List:

1. Detection분야 Domain Adaptation 논문 List: 
  ∙ Abstract, Conclusion 정리 → ppt만들기

2. Deep Learning 2024(Bishop): Chapter 2 읽고 공부하기

🛏️ 2024.01.03

사이클 및 헬스의 여파로 9시에 잠을 청해버렸다.
대략 새벽 4시정도에 기상할 것으로 기대한 내 마음과는 달리 11시에 칼같이 기상해 버렸다...
진짜 망했다ㅠㅠ
출근준비시간이 8시간이나 남아버린것...
 
어찌할 방도 없이 바로 공부 시작!🔥
 
공부를 하다보니 어느덧 4시... 출근시간까지 2시간 남아 잠을 잘까 말까 고민했지만 바로 냅다 자버렸다.
 
 
 
 
 
 
 
 
 
 

🏢 ETRI (2024.01.04)

🚕 가는 길

🏃🏻 출발!

새벽 6시에 알람을 맞췄지만 귀신같이 일어난 시각은 8시 10분!!

물론 일어날 때도 귀신같이 "으악! 늦었다, 치코쿠 치코쿠(지각)~"하면서 일어나 버렸다.
(또 늦잠 자버렸다ㅠㅠ 데자뷴가...)

 
운이 좋게도(?) 타슈(🚲)가 날 반겨주고 있을 시간 따윈 없었다!
바로 카카오T 택시 잡고 출발했다!!!
 
 

🏢 ETRI 도착!

택시에서 내리니 8시 50분경... 9시까지인줄 알고 허겁지겁 달리니 정문에서 보안요원?들이 어디가시는거냐 물었고, 인턴하러 간다고 답했다.
다시 찾아보니 9시 30분까지였던건 안비밀ㅠㅠ 내 7500원💦

 
어찌저찌 통과한 뒤 아래 사진의 큰 건물로 들어가서 OT를 들었다.

가까이 가보니 1동 건물이라고 하는데 여기 회의실에서 간단한? OT를 가졌다.
OT에서 보안서약서 쓰고 출입증을 받았다ㅎㅎ

🏢 과연 내가 있을 건물은?

OT가 끝나고 12동에 배정받아 가는길에 연못도 보여서 구경하다보니

 
 
12동에 도착해버렸다!
12동 건물이 제일 멋진듯?

도착해서 간단하게 자리배정 및 프로젝트 주제배경설명만 듣고 질의응답을 진행했다.
프로젝트 주제도 비밀...
 
 

🍚 밥이다 밥!

도착해서 간단하게 자리배정 및 프로젝트 주제배경설명만 듣고 질의응답 후 밥을 먹으러 갔다.

서편제와 동편제(특식)가 있었는데, 동편제가 2500원 더 비쌌다.
신기했던 점은 모든 밥과 반찬을 양껏 담을 수 있다는 점이었다! 그래서 위 사진처럼 진짜 많이 받아서 먹었다.
 
 
 
 
 

📖 공부! (13:00-18:00)

식사 후 교수님께서 친절하게 ETRI 건물 안내해 주셨고, 간단하게 데이트?를 즐긴다음 공부에 돌입했다.
공부내용은 Domain Adaptation!
공부내용은 ETRI(공부 참조!)

🏃🏻 퇴근! (18:00 -)

아 진짜 힘들다ㅋㅋㄲ
퇴근길 한장  찰칵

빨리가서 벤치랑 스쿼트나 해야겠다ㅋㅋ
 
 
 
 

📌 TODO List:

1. Detection분야 Domain Adaptation 논문 읽기
  i) Deep Visual Domain Adaptation - VI.C. Object Detection part
 ii) Domain Adaptive Faster R-CNN for Object Detection in the Wild

2. PaperswithCode Search

3. 관련 GitHub Search

Part 1. Basic Concepts. &. Traditional Methods

📌 Basic Concepts

🤔 Domain과 DA란?

Domain: 데이터가 유래한 곳이나 특정 분포를 의미

DA 기본개념:
아래와 같이 source와 target 분포간의 Domain Shift가 발생하고,
그 정도가 심해지면 test성능은 떨어진다.

🤔 synthetic data란?

target domain과 유사한 source dataset을 synthetic data라 한다.

🤔  DA의 목적

인 target과 source dataset에 대해

를 만족하는
transformation T(.)함수를 찾는 것.

∙ Concept Shift [Ling et al; ICCV2013]

∙ Prior Shift [Kouw & Loog ; 2018]

등이 있었으나 본 내용은 Covariate Shift문제에 대해 다룬다.

📌 Traditional DA

Metric Learning

Metric Learning은 "거리기반"DA를 진행한다.
Src, Tgt의 label이 같다면 threshold보다 거리가 가깝도록 학습한다.

단점) Source, Target의 label이 모두 필요.

Subspace Representations

Src와 Tgt이 다른 subspace에 놓여있을 때,
이 둘의 subspace에 대해 subspace를 sampling하거나 Integration하는 등 alignment(조정)하여 해결.

Matching Distributions

Domain Shift로 인한 Distribution차이를 직접적으로 해결

📌 MMD방식 (Maximum Mean Discrepancy)

1. Src와 Tgt를 Hilbert Space(Completeness를 갖는 내적공간)로 mapping
2. Distribution의 차이를 계산
(Intra class간의 차이는 적어야하고)
(Inter class간의 차이는 커야함)

cf) MMD를 변형해 source sampling에 weight를 학습하거나 resampling하는 방법도 존재

---

📌 TCA방식 (Transfer Component Analysis)
TCA방식은 Feature space → Hilbert space → Latent space로 옮겨가며 mapping하는 W를 학습하는 방법이다.

---

📌 DIP방식 (Domain Invariant Projection)
TCA 역순, MMD minimize하도록 학습.

Part 2. Visual DA in Deep Learning

DNN을 통해 출력된 Deep features는 더 추상적이고 이미 Domain bias가 줄어들었기 때문에 Deep Learning의 도입은 빠른 성능발전을 야기시킬 수 있었다.

또한, 더 깊게 fine-tuning하는 것이 마지막 층에서만 하는 것보다 나은 효과를 보였다

MMD-based Network

📌 Deep Domain Confusion(2014)
[Src Domain]:
labeled data로 Lc를 최적화 + Tgt의 Unlabeled data로 feature vector추출
→ Src와 Tgt data간의 MMD 계산, minimize

DANN(🌟)

Domain-Adversarial Training of Neural Networks (2015)


[목적]:
∙ Src domain에서 classification성능이 높아야함. (Discriminativeness는 유지)
∙ Src domain과 Tgt domain을 구별하지 못해야함. (Domain-Invariance도 고려)

일종의 GAN에서 사용되던 Discriminator를 가져다 사용한 느낌!
다만, 이전 방법들은 Feature space Distribution을 match하기위해 Reweighting, transformation을 찾는 방법을 사용했으나
DANN은 ① Feature Representation자체를 바꾸는 방식 + ② DA와 Deep Feature Learning을 하나의 학습과정안에서 해결한다. 추가적으로 ③ 분포간 차이측정 시, Deep Discriminatively-Trained Classifier를 사용(GAN컨셉) 또한 사용한다.

Feature Extraction을 위한 Embedding model에 대해
Src Domain Classification Loss를 줄임
Domain Classifier는 Src인지 Tgt인지 구분
이때, Domain구분못하게 학습해야해서 Gradient를 바꿔서 backward한다.

Part 3. Beyond Classical DA

그림에 굉장히 많은 것들이 표시되어 있는데, 이중에서 대표적인 방식 4가지만 여기서 짚고 넘어가자.

i) Transfer Learning

가장 기본적인 방식, Pretrained model과 Tgt data만 필요.
Src data로 pretrain → Tgt data로 Fine-tuning

ii) Semi-supervised DA

labeled Src data와 labeled Tgt data 같이 활용.

Domain과 상관없이 Class가 동일하면(Intra-class) Loss가 작아지게 학습하고
Class가 다르면(Inter-class) Loss는 어느 정도까지 (보통 margin을 설정해) 커지게 학습

iii) Transductive Unsupervised DA

🤔 Truansductive...?
labeled Src data와 Unlabeld Tgt data를 사용해 학습하는 것

iv) Self-Supervised Learning

Label없이 학습가능한 self-learning task생성 후, 이를 이용해 Unlabeled Learning을 진행.

위의 Jigsaw퍼즐처럼 쪼개어 섞은 후, 원래의 순서를 학습하도록 하는 것이다.
이는 Src data와 Tgt data의 유무에 다라 다른 기법들과 같이 사용가능하다.

Ex)
Tgt > Src : Transfer Learning과 같이 사용
Labeled Src 가 존재 : Unsupervised DA방식 사용

Part 4. Perspectives. &. Outlook

📌 Multi-Domain Learning

🤔 Mutli-Domain Learning? 그게 뭐죠
여러 도메인에서 발생하는 데이터를 사용해 모델을 학습하거나 적용시켜 새로운 환경에서 강건하게 동작하게 하는 기술.
Domain: 데이터가 유래한 곳이나 특정 분포를 의미,

Multi-domain learning은 주로 다음과 같은 상황에서 활용된다:
∙ Domain Adaptation: 모델이 학습한 도메인과 테스트 도메인이 다를 때 발생하는 문제를 해결하기 위해 사용. 
∙ Domain Generalization: 여러 도메인에서의 데이터를 사용하여 일반적인 특성을 학습함으로써 새로운 도메인에 대한 성능을 향상시키는 것을 목표. 즉, 모델이 여러 도메인에서 얻은 지식을 더 일반적인 형태로 확장하는 것을 의미.

이점)
∙ 메모리 절약 및 multi-task효과,
∙ Incremental Learning (기존에 학습된 지식을 유지하면서 새로운 데이터 또는 클래스를 추가해 모델을 업데이트 하는 것.)

---

이에 대해 어떻게 sharing/seperation을 진행할 것인지에 대한 다양한 MDL방법론이 존재한다.
∙ Independent Networks
∙ Maximally Shared
∙ Residual Adapters

📌 Meta-Learning for DA & DG

Meta-Learning Brief

🤔 DA vs Meta-Learning

[DA]: 
∙ 목표) 학습된 모델을 다른 도메인으로 전이(transfer), 성능향상을 위해 모델을 조정.

∙ 방법) 주로 한 도메인에서 얻은 데이터를 사용하여 모델을 학습, 그 모델을 다른 도메인의 데이터에 적용합니다.
이를 위해 도메인 간의 차이를 최소화하거나 조정하는 방법을 적용합니다.

---

[Meta-Learning]:
∙ 목표) 작은 데이터에서 빠르게 학습하고 일반화할 수 있는 모델을 만드는 것이 목표로 학습하는 방식 자체의 개선으로 새 도메인에 빨리 적응,학습에 초점.
즉, "좋은 Inductive Bias"를 찾는 것이 중요!

∙ 방법) 작은 데이터셋에서 빠르게 학습하고 새로운 작업에 대해 일반화할 수 있는 학습 방법이나 알고리즘을 개발합니다.

---

[Summary]
DA: 하나의 도메인에서 학습된 모델을 다른 도메인으로 전이하는 방법에 중점
[Meta-Learning]: 모델 자체의 학습 방식을 개선하여 새로운 작업이나 도메인에 빠르게 적응하고 일반화하는 방법에 중점

Meta-Learning for DA 

많은 인기있는 DA알고리즘들은 좋은 시작점에 위치했는지에 의존적이다.
→ 이에 대해 Meta-Learn이 좋은 시작점이 될 수 있을까?

---

---

Meta-Learning for DG

DG Problem설정에 대해 생각해보자.

---

🤔 어떻게 Meta객체를 정의할 것인가?
Multi-Src에서, validation domain성능을 최적화해야한다.

어떤 하이퍼파라미터를 (meta)-learning에 사용해야할까?

∙ MetaReg (NeurIPS-18):
MetaReg는 도메인 일반화를 위해 메타-정규화를 사용, 일반화 성능향상을 위해 메타-정규화를 가정합니다.

∙ Feature-Critic (ICML-19):
Feature-Critic는 이질적인 도메인 일반화를 위한 기법 중 하나로 특징 품질을 평가하는 '비평가(critic)' 네트워크를 추가적인 손실 함수로 사용하여 도메인 간의 차이를 줄이고 일반화 성능을 향상시키려고 합니다.

---

🤔 어떻게 Meta-최적화를 할 것인가?
Meta-Learning에서 최적화는 일반적으로 비용이 많이 들고 불안정한 경우가 많은데, 이를 극복하기 위해 몇 가지 방법들이 제안된다.


∙ Bilevel Optimization:
meta-train 단계에서, 모델을 최적화하는 동안 다른 최적화 문제를 해결하는 방법으로
메타-트레이닝에서 더 나은 성능을 갖는 모델을 찾기 위해 메타-러닝을 수행한다.

실제 적용:

실제로는 전통적인 모델 업데이트와 함께 모델을 업데이트하고, 메타-러닝을 사용하여 도메인 간의 성능을 개선하는 방법을 번갈아가며 적용한다.
이러한 접근 방식들은 메타-러닝에서의 최적화를 개선하고, 비용과 안정성 문제를 극복하기 위한 것이다.

---

🤔 Conclusion
Meta-DA 및 Meta-DG가 기존의 DA & DG 연구를 보완할 수 있다는 점을 강조한다.

📌 Emerging Problem Areas & Applications

DG: Heterogeneous Case

∙ Homogeneous DG (동질적 도메인 일반화):
공유된(Src와 Tgt에서 동일한) Label space가 존재. 즉 label의 종류가 동일하거나 공유된다.


∙ Heterogeneous DG (이질적 도메인 일반화): 
Src와 Tgt 간 Label space가 안겹치거나 분리되어 있다.
이런 경우, 주로 특징 일반화(Feature Generalization)에 초점을 맞춥니다.
즉, Label space가 다른데도 특징(feature)을 일반화하려는 것이 중요합니다.

Ex) ImageNet pretrained CNN을 feature extractor로 다른 도메인의 이미지에 대한 특징을 추출하고 이를 통해 일반화를 시도

Cross-Domain FSL

∙ Traditional FSL(Few-Shot Learning):
meta-train에서 획득한 지식을 meta-test로 전이(transfer), 일반화하는 방식.


∙ CD-FSL (Cross-Domain Few-Shot Learning):
Domain-shift를 고려한 Few-Shot Learning.
Meta-Dataset과 같은 접근 방식은 어떻게 도메인 간의 변화를 전이하고 학습하는지에 초점 

∙ "Learned Feature-Wise Transforms" (ICLR-20)
특징별로 변형된(transformation) 학습.
stochastic layers는 DG를 향상시킬 수 있다는 것을 보여준다.
또한, Meta-Learning을 적용해 Noise Distribution 학습을 시도했다.

Sim2Real Meta-Learning

∙ 목표: Sim2Real for Object Detection & Segmentation:

∙ Meta Representation: Simulator/Dataset.
Idea: 시뮬레이터를 학습, 해당 시뮬레이터가 생성하는 데이터를 실제 환경에서 사용할 수 있는 형태로 만들어 모델을 학습시키면, 실제 환경에서 높은 정확도를 얻을 수 있을 것.

cf) RL/Evoluation Strategy 필요(시뮬레이터는  미분 불가능하기 때문.)

Simulator는 미분 불가능한(non-differentiable) 특성을 갖기에, 이를 다루기 위해 RL 또는 ES와 같은 기법들이 필요하며, 이런 접근 방식은 시뮬레이션 환경에서 생성된 데이터를 실제 환경에 적용할 수 있는 방식으로 학습하여, 객체 감지와 분할에서 시뮬레이션에서 실제로 사용될 때의 성능을 향상시킨다.

📌 InternImage [CVPR 2023]

InternImage: Exploring Large-Scale Vision Foundation Models with Deformable Convolutions

Paperswithcode 홈페이지에서 Detection, Segmentation 등 많은 Benchmark Dataset에서 최고의 성능(SOTA)를 달성한 (무친성능의) 모델이다.

🤔 Brief

Architecture

Basic block: transformer와 같이 Layer Norm, FFN으로 구성
Stem과 Downsampling layer: 기존 CNN의 설계(s2, p1은 각각 stride=2, padding=1)

목적

ViT, EfficientNet처럼 새로운 backbone모델로 Computer Vision분야에서도 GPT같은 foundation model을 만들겠다!!
(By. Deformable Convolutions)

1.  태생적인 CNN의 문제점과 극복

🤔 Why? Transformer > CNN

최근, ViT와 같은 Attention-base 모델들이 CNN보다 널리 사용되고 좋은 성능을 낸다.

Reason 1)

∙ CNN은 3x3처럼 고려 
∙ Transformer(MSA)는 모든 input을 고려.
→ CNN은 Receptive field가 너무 작아 상대적으로 멀리보지 못함(= Long-Range Dependency 차이)

Reason 2)

CNN은 layer가 쌓이면서 이런 단점을 극복되는 것이 철학.
항상 모든 input을 고려, 학습하는 ViT와 비교해 넓은 공간적 통합이 부족함

Ex) ERF의 경우
  ∙ ViT의 경우, layer는 항상 input에 적절한 영향을 받는다.
  ∙ CNN은 filter_size의 크기에 따라 커진다.
(ERF: 출력층의 하나의 뉴런에 영향을 미치는 input_pixel들의 공간 크기를 나타내는 것.)

Sol) DCN (Deformable Convolution)

1. ERF

• Convolution filter가 고정되지 않고 알아서 퍼지기에 넓은 범위를 볼 수 있다!!
• 이에 대한 증명으로 ERF를 사용 (ERF 확인 시, 넓게 퍼짐을 통해 증명)

2. ViT & Main Contribution

따라서 이 논문에서는 SOTA ViT에서 MSA 대신, 

"DCN(Deformable Convolution)을 잘 끼워 넣는다는 것"이 주요 내용이다.

→ 정확도∙연산량 등 transformer SOTA보다 더 좋다는 것이 main contribution

3. DCN v1 / DCN v2

[등장이유]

• 크기, 포즈, 시점 등의 이유로 SIFT, Affine transform 등의 전처리가 필요한 경우가 존재.
• CNN내에서, 알아서 conv연산이 필요한 경우, conv연산이 이루어지도록 학습해보자!라는 취지

[기존 CNN 연산]

3x3 filter의 경우, 하나의 output feature element를 만들기 위해 다음과 같은 연산을 진행한다.

• Feature vector의 3x3크기만큼 conv연산 진행, 그 값을 모두 더함 → 하나의 element로 만드는 작업을 반복

[DCN V1의 주장]

• 이때, p_n을 학습하게 하는 것이 DCN 이다!

📌 이때, p_n이 3x3상수가 아닌, learnable param인 ∆p_n이 된다면?

→ 이상적으로 알아서 학습이 필요한 위치에서 convolution이 진행될 것.

🚩 위치 학습 방법

1. 기존 convolution과 별개로 p_n을 학습할 수 있는 convolution(∆p_n)을 하나 더 붙임
2. p 를 weight처럼 학습
3. 그 p 를 feature x를 통해 convolution을 진행.
4. 이를 통해 위치정보가 반영된 convolution을 할 수 있게 됨.

[DCN V2의 주장]

위치 + 중요도∙영향력도 고려.

• filter의 위치에 따른 영향력, m_n(modulation변수)를 고려해보자! 

🚩 영향력 학습 방법

1. 앞과 같이 단순히 convolution을 하나 추가
2. 같은 방법으로 영향을 받는 정도까지 학습

4. DCN V3

<기존 DCN V1, V2의 문제점>

위의 DCN V2를 그대로 ViT에 넣으려고 하니 다음과 같은 문제가 발생

문제점

Prob 1) ViT SOTA에 끼워넣을 때, Convolution 개수에 따라 linear하게 parameter와 memory복잡성이 증가

Prob 2) DCN V2의 modulation이 불안정

ERF의 경우
  ∙ modulation filter의 sigmoid: 어떨 때는 평균이 1에 가깝고 어떨 때는 0에 가까움
  ∙ 이는 output에서 어느 것이 중요한지 판단이 안됨 (= 불안정)

<DCN V3의  3가지 Solution>

1. MobileNet에서 사용되는 "Depthwise Convolution"을 도입, weight를 합침
(= 경량화; 최종 결과를 토대로 볼 때, 성능보다는 연산량, 경량화를 우선)
weight를 합쳐 경량화를 하기 위해
   i) group을 나눠 group별로 하나의 weight만 학습하게 함
   ii) 그 group안에서 Depth-Wise Convolution을 진행, position과 modulation 학습
   iii) 이때, modulation factor는 softmax로 계산

2. Self-Attention처럼 MHA의 느낌이 나도록 "Group Convolution"을 도입


3. Sigmoid대신 Softmax를 사용 (→ 불안정성을 3x3 filter로 해결)

🤔 Appendix와 마무리...

ViT에서 benefit을 가져오고, EfficientNet처럼 쌓는다.(Scaling규칙)

Appendix

Appendix 내용을 볼 때, Stage별 ERF를 보면, 
∙ Stage 1,2에서는 작은 부분을 보고
∙ Stage 3,4에서는 ERF가 크게 커지는 것을 알 수 있다.

추가적으로, ResNet은 ERF가 학습이 되든 말든 Local하게 존재하지만
InternImage는 ERF가 Stage 3, 4가 넘어가게 되면, ERF가 많이 커짐을 알 수 있다. 

Limitation

높은 속도를 요구하는 경우, 그렇게 좋지는 않다.
(MobileNet에서 사용되는 "Depthwise Convolution"을 도입해 weight를 합침을 통해 경량화를 진행했음에도 불구하고)
But, 자신들이 처음이어서 봐달라는 식으로 마무리되었다.

🛏️ 2024.01.02

연말동안 너무 놀았다는 생각과 후회로 급히 인턴십을 위한 배경지식을 조금이라도 쌓고자 다시 공부를 시작했다.

공부를 하다보니 잘 시간이 거의 다 되어 새벽 6시알람을 맞춘 후 인턴십 발대식에 갈 생각에 잠에 들었다.

🏢 ETRI (2024.01.03)

🚲 가는 길

🏃🏻 출발!

새벽 6시에 알람을 맞췄지만 귀신같이 일어난 시각은 11시!!

물론 일어날 때도 귀신같이 "으악! 늦었다, 치코쿠 치코쿠(지각)~"하면서 일어나 버렸다.

운이 좋게도(?) 새로운 모델의 타슈(🚲)가 날 반겨주고 있었다.

앞으로의 길이 얼마나 험난할 지는 모른 채, 행복하게 타슈에 탑승해 출발했다ㅎㅎ

🚴🏻 가는 길!!

그래도 평탄한 자전거 도로가 신세계 백화점까지는 이어져서 그나마 덜 힘들게? 21분동안 자전거를 탔다.

위의 사진을 뒤로 진짜 지고쿠(지옥)가 펼쳐졌는데, 오르막길 진짜 힘들어 죽는줄 알았다ㅠㅠ

(돌아올 때, 페달 밟지도 않고도 이곳까지 돌아올 수 있는 걸로 말 다했다 진짜...)

진짜 진짜 힘들게 페달을 밟고 낑낑대면서 가다보니 바닥에 부산 국제영화제 바닥마냥 연구소들 팻말? 같은게 쫙 깔려있었는데 신기했다.

어릴 적, 초등학교 때부터 가보고 싶었던 국방과학 연구소도 보였고,

이번 겨울방학 인턴을 하게 될 ETRI도 보였다.

또 조금 가다보니 아래처럼 사택이 있었는데 LG연구원들을 위해 제공되는? 집 같았는데 되게 깔끔하고 직장도 가깝고 

LG의 복지가 좋다고 새삼 느낄 수 있게 되었다.

🏢 ETRI...??

가다보니 드디어 ETRI가 보였다.

심지어 자녀가 있는 ETRI연구원분들을 위해 ETRI 어린이집까지 바로 옆에 있는 걸 봐선 대전에 있는 연구단지들의 연구소들은 거의 대부분 직원복지가 상당히(너무) 좋아보였다.

그런데 생각한 것 보다 아담한 규모에 조금 의아했었기에 카카오맵을 다시 보니 갈길이 멀리도 있었다.

(갈길도 멀었는데 심지어 모두 오르막길이라 진짜 힘들었..💦)

🏢 ETRI...!!

진짜 큰 규모에 이게 연구단지구나 싶게 여러 연구소들이 밀집한 지역에 들어섰고, 멀디 먼 갈길을 재촉해서 가니

드디어! ETRI를 영접?하게 되었다. 엄청난 규모에 놀랐고, 내일부터 인턴십할 생각에 설레버렸다🔥!

🏫 UST 연구인턴십 발대식

약 40분정도 걸쳐 1시 정각에 도착을 하게 되었다! (자전거 주행시간만 37분...)

연구인턴십 발대식을 시작했는데 ETRI쪽이 가장 사람이 많았던 것? 같았다.

무려 대강당의 2줄 반정도...

이후 4분정도가 발대식 발표를 해주셨는데, 무려 8.1 : 1의 경쟁률을 뚫었다는 말씀을 해주셨다.

(특히 ETRI의 경우, 인기가 많았던것 같은게 나는 면접에서만 10명 지원자들이 있었던 것을 생각하면 진짜 지원자들이 많았던 것 같았다.)

질문해주시면 소정의 상품을 드립니다라는 말씀에 귀신같이 질문을 드렸다.

질문 이후 아래와 같은 상품?을 받았는데 뭐...머그컵이나 수건이겠지...라고만 생각했었는데

강의 다 끝나고 ETRI인턴 지원하신 분들과 연락처 교환한 이후 포장을 뜯어보니 이게 웬걸?

1단 독서대가 톽! 

집에서 아주 유용하게 사용하고 있다ㅎㅎ

(집에 오니 자전거로만 소모한 칼로리가 무려 400kcal... 진짜 힘들었다💦)

내일부터는 인턴십에서 배운 내용들을 정리하는 좀 더 알찬 내용을 적고자 한다.

(한번도 이런 일상내용?을 적은 적이 없었기에...)

📌 목차

1. The Impact of Deep Learning
2. A Tutorial Example
3. A Brief History of Machine Learning

1. The Impact of Deep Learning

preview
Deep Learning은 상당히 강력하고 다목적을 위해 data로부터 학습된다.
또한, 요즘에는 AI와 Machine Learning이라는 용어가 서로 대체되어 사용된다.

꾸준한 발전으로 인해 AGI는 매우 급격한 발전을 이룩했는데, 특히 LLM은 매우 두드러진 능력을 보인다.
즉, LLM은 AGI로 가는 길의 효시라 할 수 있다.

본문 예제
주 내용: "기존 일상의 문제들" → 직접 algorithm을 짜서 풀기에는 문제가 난해하였음.
❗️Deep Learning을 사용함으로써 이를 해결.
(by. 많은 양의 training set 확보, 이를 training(=learning)시킴으로써 모델이 문제를 풀게함.)

2. A Tutorial Example

input(training set): x₁, . . . , x_N
target set: t₁, . . . , t_N

목표: 새로운 x에 대해 t값을 잘 예측하는 것 = generalization

Linear Models

Linear Model들은 선형적인 unknown parameter라는 중요한 특징이 있을 뿐만 아니라 "중요한 한계점"또한 존재.

Error Function

training data에 다항식을 fitting시켜 error function을 최소화 시킬 수 있다.

Model Complexity
이때, Model의 M(다항식 차수)를 고르는 것은 남아있는 중요한 과제이다.

M의 값에 따라 model이 overfitting이 될 수도, underfitting이 될 수도 있기 때문이다.
이때, Overfitting이 보통 주요한 문제이기 때문에 Regularization을 Loss항에 도입한다.

Regularization

위의 Loss function은 L2 Regularize항을 추가한 것으로
가 성립하며,  λ계수는 regularize항과 MSE항 간의 상대적 중요성을 결정하는 상관계수(coefficient)로 Loss function에 penalty를 줌으로써 overfitting의 정도를 결정할 수 있다.

Model Selection
λ는 w 결정을 위해 J(w)를 최소화하는 동안 고정되는 하이퍼파라미터이지만
단순히 w와 λ에 대해 에러 함수를 최소화해 λ → 0으로 수렴하게 되면, error값이 작은 과적합된 모델이 되어버릴 수 있다.
마찬가지로 단순히 M에 대한 trainingset의 오차를 최적화하면 M의 값이 커지고 과적합 될 수 있다.
따라서 하이퍼파라미터의 적절한 값을 찾기 위한 방법을 찾아야 한다.

위의 결과는 가능한 데이터를 가져와 train-valid-split방법을 제안한다.
trainset으로 w를 결정하고 validset에서 가장 낮은 오차를 갖는 모델을 선택한다.
그러나 제한된 크기의 dataset를 사용해 모델을 여러 번 설계하면, validset에 과적합될 수 있기에
마지막으로 선택된 모델의 성능을 평가하기 위해 세 번째 테스트 세트를 유지해야 할 수도 있다.

∙ Cross Validation
일부 응용 프로그램에서는 훈련 및 테스트용 데이터의 제공이 제한될 수 있다.
좋은 모델을 구축하려면 가능한 많은 데이터를 사용하여 훈련해야 하지만 validset이 너무 작으면 예측 성능의 상대적으로 노이즈가 많은 추정치를 제공할 수 있다.
이러한 딜레마의 해결책 중 하나는 아래 그림에서 설명된 교차 검증을 사용하는 것이다.
이를 통해 데이터의 (S - 1)/S의 비율로 훈련에 활용해 모든 데이터를 사용하여 성능을 평가할 수 있다.

∙ 'leave-one-out' 기법
특히나 데이터가 부족한 경우, datapoint의 총 수인 N과 같은 경우인 S = N을 고려하는 것. 


교차 검증의 주요 단점:
∙ S의 배수로 학습 실행 횟수가 증가되어, 자체적으로 계산 비용이 많이 드는 모델에서 문제가 될 수 있다는 것.
∙ 단일 모델에 여러 복잡성 하이퍼파라미터가 있을 수 있으며, 이런 하이퍼파라미터들의 설정을 조합하는 것은 지수적으로 많은 학습 실행 횟수를 요구.

3.  A Brief History of Machine Learning

Step 1. single neuron은 선형결합(Linear Combination)으로 생성됨
Step 2. 생성된 single neuron에 non-linear function으로 transform.

이를 수학적으로 표현하면 아래와 같다.

이때, a라는 값은 pre-activation이라 불리며, 
f(.)는 activation funtion이라 불리고 y는 activation이라 불린다.

Backpropagation 
MLP에서 중간 층의 노드는 hidden unit이라 하는데, 이는 trainset에 나타나지 않는 값이기 때문이다.
(trainset은 input과 output값만 제공하기 때문.)

여러 층의 가중치를 가진 신경망을 학습하는 능력은 1980년대 중반쯤부터 다시 관심이 증폭되는 계기가 되었는데, 특히, 확률 이론과 통계학에서의 아이디어가 신경망과 머신 러닝에서 중요한 역할을 한다는 것이 인식되었다.
학습에서의 배경 가정들, 사전 지식이나 귀납적 편향으로 불리기도 하는 것들이 포함될 수 있음을 한 가지 중요한 통찰은 말해준다.
이러한 가정들은 명시적으로 통합될 수 있는데, 예를 들어 피부 병변의 분류가 이미지 내 병변의 위치에 의존하지 않도록 신경망의 구조를 설계할 수 있다. 또는 모델의 수학적 형태나 훈련 방식으로부터 발생하는 암묵적인 가정 형태로 나타날 수 있습니다.



❗️Backpropagation 사용이유?
모델은 수천억개의 파라미터를 가지며, Loss function은 이런 parameter들의 높은 비선형함수일 것이기에
∙ Loss function을 닫힌 형태(e.g 선형 회귀)로 최소화하는 것이 아니라

∙ 파라미터에 대한 Loss function의 도함수(= ∂J(w) / ∂w)를 기반으로
반복적인 최적화 기술(= Backpropagation Algorithm)을 통해 최소화해야 한다.
이러한 모든 과정은 전문적인 컴퓨팅 하드웨어가 필요하며 상당한 계산 비용이 들 수 있다.

Deep Networks
많은 가중치를 가진 신경망을 '심층 신경망(deep neural networks)'이라고 하며, 이러한 신경망에 중점을 둔 기계 학습의 하위 분야를 '딥 러닝(deep learning)'이라 한다(LeCun, Bengio, and Hinton, 2015).

위 그림은 최첨단 신경망을 훈련하기 위해 필요한 연산 주기의 증가를 나타내며, 연산 주기의 두 가지 구분된 성장 단계를 보여준다.
수직 축은 지수적 스케일을 가지며 (petaflop/s-days) 단위로 표시된다.
∙petaflop: 1015(천 조)개의 부동 소수점 연산
∙petaflop/s-days: 초당 하나의 피타플롭을 의미.
petaflop/s-days은 24시간 동안 피타플롭/초의 속도로 계산되고, 대략 1020개의 부동 소수점 연산을 나타내며, 그래프의 최상단은 인상적인 1024개의 부동 소수점 연산을 나타낸다. 그래프의 직선은 지수적 성장을 나타낸다.

혁신적인 아키텍처 개선이나 더 정교한 형태의 귀납적 편향을 포함하는 경우
즉, 모델이 특정한 가정이나 선행 지식을 사용해 데이터를 해석 --> 성능 향상


∙ 표현 학습(representation learning)
심층 신경망의 숨겨진 레이어 역할
신경망이 입력 데이터를 의미 있는 새로운 표현으로 변환, 마지막층이 해결해야 할 훨씬 더 쉬운 문제를 만들어낸다(Bengio, Courville, and Vincent, 2012).
이러한 내부 표현은 전이 학습을 통해 관련된 문제의 해결을 가능하게 할 수 있다.

∙ Foundation Models
여러 가지 downstream 작업에 적합하게 조정되거나 세부 조정될 수 있는 큰 신경망
넓은 적용 가능성을 갖도록 대규모이고 이질적인 데이터 세트를 활용할 수 있다(Bommasani et al., 2021).


∙ 규모 이외 방법을 이용한 발전.
규모 확장 외에도 딥 러닝의 성공에 도움이 된 다른 발전 사항들이 있었는데, 예를 들어, 단순한 신경망에서 깊은 신경망의 연속적인 층을 통해 역전파될수록 훈련 신호가 약해지는 현상을 해결하기 위해 잔차 연결(residual connections)을 도입(He et al., 2015a).

또 다른 주요 발전방법: by coding:
역전파를 수행하여 오류 함수의 그래디언트를 계산하는 코드 = loss.backward()
→ 순방향 전파를 지정하는 코드에서 자동으로 생성하는 자동 미분 방법의 도입. = autograd 내장.

🧐 정리

∙ LLM ← AGI로 가는 효시.

∙ Deep Learning의 목표:
Generalization이 잘 되도록 하는 Universal Approximation이 목표, 
이를 위해 적절한 model의 차수 M을 찾는것이 목표. (over/underfitting문제)

∙ 확률론과 통계학이 중요한 이유?
학습에서 prior, posterior, inductive bias 등의 포함가능성으로 인해 모델이 잘 작동하지 못할 수 있음.
물론, 정교한형태의 inductive bias를 포함하면 모델이 특정 가정이나 선행지식으로 데이터 해석을 하여 성능향상도 가능함.


∙ Representation Learning?
hidden layer의 역할, 문제해결을 더 쉽게 만드는 것.
input을 "유의미한 새로운 표현으로 변환하는 것."


❗️Backpropagation 사용이유?
Loss function=수천억개 parameter의 높은 비선형함수일 것이기에
∙ Loss function을 닫힌 형태(e.g 선형 회귀)로 최소화하는 것이 아니라
∙ 파라미터에 대한 Loss function의 도함수(= ∂J(w) / ∂w) 기반,
반복적인 최적화 기술(= Backpropagation Algorithm)을 통해 최소화 진행.

📌 목차

1. YOLO v3로 정지영상에서 Object Detection하기
2. YOLO v3로 비디오에서 Object Detection하기(랩탑 캠사용)

0.  파일준비 및 YOLO v3 공통코드

먼저 자신의 로컬 폴더에 다음 3개의 파일이 있어야한다.
∙ 'coco_names.txt' (이 파일은 1~80행까지 복사후 txt파일을 생성해 붙여넣는다.)
∙ 'yolov3.weights'
∙ 'yolov3.cfg'


이후 아래 코드에 대해 설명해보겠다.
- 5~13행: YOLO 모델 구성함수
- 15~38행: YOLO모델로 img영상에서 물체탐지 후 반환하는 함수

def construct_yolo_v3():
    f=open('coco_names.txt', 'r')
    class_names=[line.strip() for line in f.readlines()]

    model=cv.dnn.readNet('yolov3.weights','yolov3.cfg')
    layer_names=model.getLayerNames()
    out_layers=[layer_names[i-1] for i in model.getUnconnectedOutLayers()]
    
    return model,out_layers,class_names

def yolo_detect(img,yolo_model,out_layers):
    height,width=img.shape[0],img.shape[1]
    test_img=cv.dnn.blobFromImage(img,1.0/256,(448,448),(0,0,0),swapRB=True)
    
    yolo_model.setInput(test_img)
    output3=yolo_model.forward(out_layers)
    
    box,conf,id=[],[],[]		# 박스, 신뢰도, 클래스 번호
    for output in output3:
        for vec85 in output:
            scores=vec85[5:]
            class_id=np.argmax(scores)
            confidence=scores[class_id]
            if confidence>0.5:	# 신뢰도가 50% 이상인 경우만 취함
                centerx,centery=int(vec85[0]*width),int(vec85[1]*height)
                w,h=int(vec85[2]*width),int(vec85[3]*height)
                x,y=int(centerx-w/2),int(centery-h/2)
                box.append([x,y,x+w,y+h])
                conf.append(float(confidence))
                id.append(class_id)
            
    ind=cv.dnn.NMSBoxes(box,conf,0.5,0.4)
    objects=[box[i]+[conf[i]]+[id[i]] for i in range(len(box)) if i in ind]
    return objects

model,out_layers,class_names=construct_yolo_v3()		# YOLO 모델 생성
colors=np.random.uniform(0,255,size=(len(class_names),3))	# 클래스마다 색깔​

 

05~13행의 construct_yolo_v3 함수를 살펴보자.
∙ 06~07행은 COCO 데이터셋의 클래스이름을 담고 있는 coco_names. txt 파일에서 클래스 이름을 읽어 class_names에 저장한다.

∙ 09행은 YOLO v3 모델 정보를 파일에서 읽어 yolo_model 객체에 저장한다.

yolov3.weights 파일에서는 신경망의 가중치 정보를 읽어오고 yolov3.cfg 파일에서는 신경망의 구조 정보를 가져온다.

∙ 10~11행은 getUnconnectedOutLayers 함수를 이용하여 yolo 82, yolo 94, yolo_106 층을 알아내어 out_layers 객체에 저장한다.

∙ 13행은 모델, 층, 클래스 이름을 담은 객체를 반환한다.

---

15~38행의 yolo_detect 함수를 살펴보자.
∙ 16행은 원본 영상인 img의 높이와 너비 정보를 height와 width에 저장한다.

∙ 17행은 OpenCV의 blobFromImage 함수로 영상을 YOLO에 입력할 수 있는 형태로 변환해 test_img에 저장한다.
이 함수는 [0,255] 범위의 화솟값을 [0,1]로 변환하고 영상 크기를 448 X 448로 변환하며 BGR 순서를 RGB로 바꾼다.원본 영상은 img에 남아있다.

∙ 19행은 test_img에 저장되어 있는 영상을 신경망에 입력한다.

∙ 20행은 신경망의 전방 계산을 수행하는데, out layers가 출력한 텐서를 output3 객체에 저장한다.
이로 인해 Ouput3 객체는 아래 3가지 텐서를 갖는다.
14×14×85×3,
28×28×85×3,
56×56×85×3 

∙ 22~34행은 output3 객체로부터 물체 위치를 나타내는 박스 정보와 함께 물체 클래스와 신뢰도 정보를 추출한다.
22행은 박스와 신뢰도, 클래스정보를 저장할 리스트를 생성한다.
23행은 세 개의 텐서를 각각반복 처리하며
24행은 85차원 벡터를 반복 처리한다.
85 차원 벡터는 (x, y, w, h,o, p1. p2, … p80)으로 표현되며
앞의 네 요소는 박스, o는 신뢰도, 뒤의 80개 요소는 클래스확률이다.

∙ 25~27행은 뒤의 80개 요소 값에서 최고 확률에 해당하는 클래스를 알아내 클래스 번호는 class_id, 확률은 confidence에 저장한다.

∙ 28행은 confidence가 0.5보다 크지 않으면 버린다.
0.5보다 크면 29~31행에서 [0,1] 범위로 표현된 박스를 원래 영상 좌표 계로 변환해
왼쪽 위의 위치를 x와 y, 너비와 높이를 w와 h에 저장한다.

∙ 32~34행은 박스와 신뢰도, 클래스 정보를 리스트에 추가한다. 박스는 왼쪽 위와 오른쪽 아래 구석 좌표를 저장한다.

---

∙ 22~34행으로 검출한 박스들에는 상당한 중복성이 있다.
즉, 이전시간에 설명한 그림에서 빨간색 유니폼 선수를 검출한 박스가 검은색 칸에만 나타나지 않고 그 주위에 여럿 나타나는 현상이다.

∙ 36행의 NMSBoxes 함수는 박스를 대상으로 비최대 억제를 적용해 중복성을 제거한다.

∙ 37행 은 비최대 억제에서 살아남은 박스의 위치, 신뢰도, 클래스 이름을 모아 objects 객체에 저장한다.

∙ 38행은 objects를 반환한다.

∙ 40행은 contruct yolo_v3 함수로 YOLO 모델을 구성한다.

∙ 41 행은 물체 클래스를 고유한 색으로 표시하기 위해 컬러 목록을 만들어 colors 객체에 저장한다.

1. YOLO v3로 정지영상에서 Object Detection하기

메인 프로그램이 시작되는 
∙ 43행은 입력 영상을 읽어 img에 저장한다.
∙ 46행은 yolo_detect 함수로 원본 영상 img에서 물체를 검출해 res에 저장한다.
∙ 48~52행은 res에 있는 박스와 클래스 이름, 신뢰도를 영상에 표시한다.

프로그램 실행 결과를 보면, 왼쪽과 오른쪽 선수를 각각 100%와 94.1% 신뢰도의 person 클래스로 제대로 검출했다.
또한 축구공을 99.9% 신뢰도로 sports ball 클래스로 옳게 검출했다.

img=cv.imread('soccer.jpg')
if img is None: sys.exit('파일이 없습니다.')

res=yolo_detect(img,model,out_layers)	# YOLO 모델로 물체 검출

for i in range(len(res)):			# 검출된 물체를 영상에 표시
    x1,y1,x2,y2,confidence,id=res[i]
    text=str(class_names[id])+'%.3f'%confidence
    cv.rectangle(img,(x1,y1),(x2,y2),colors[id],2)
    cv.putText(img,text,(x1,y1+30),cv.FONT_HERSHEY_PLAIN,1.5,colors[id],2)

plt.imshow(img[...,::-1])

2. YOLO v3로 비디오에서 Object Detection하기 (랩탑 캠사용)

∙ 43~64행은 웹 캠에서 비디오를 읽어 디스플레이하는 코드에 YOLO를 적용한다.
∙ 50행은 비디오에서 획득한 현재 프레임을 yolo_detect 함수에 입력해 물체를 검출하고 결과를 res에 저장한다.
∙ 52~56행은 검출한 물체 정보를 영상에 표시한다. 

cap=cv.VideoCapture(0)
if not cap.isOpened(): sys.exit('카메라 연결 실패')

while True:
    ret,frame=cap.read()
    if not ret: sys.exit('프레임 획득에 실패하여 루프를 나갑니다.')
        
    res=yolo_detect(frame,model,out_layers)   
 
    for i in range(len(res)):
        x1,y1,x2,y2,confidence,id=res[i]
        text=str(class_names[id])+'%.3f'%confidence
        cv.rectangle(frame,(x1,y1),(x2,y2),colors[id],2)
        cv.putText(frame,text,(x1,y1+30),cv.FONT_HERSHEY_PLAIN,1.5,colors[id],2)
    
    cv.imshow("Object detection from video by YOLO v.3",frame)
    
    key=cv.waitKey(1) 
    if key==ord('q'): break

📌 목차

1. Metric (IoU(Jaccard Similarity) , mAP , PR-curve , ROC-curve)
2. Traditional Detection Method
3. CNN : RCNN 계열 (RCNN, fast RCNN, faster RCNN)
4. CNN : YOLO 계열
5. Transformer : DETR , SETR
6. Backbone Transformer : Swin Transformer

Object Detection기술 발전과정이 잘 정리된 추천 Survey논문

∙ [Liu 2018]

∙ [Jiao 2019]

∙ [Zaidi 2021]

1. Metric (IoU, mAP, PR-curve, ROC-curve)

preview

Detection모델은 영상의 물체(object)를 Bbox(Bounding_Box)라는 직사각형으로 지정한다.
이때, Box마다 class와 confidence를 출력한다.

PASCAL VOC대회, COCO 대회 등에서 성능을 주로 mAP로 측정한다.
IoU→AP→mAP 순으로 계산이 되기에 IoU부터 알아보고자 한다.
추천 Survey 논문: [Padilla 2020]

1.1 IoU (Intersection Over Union)

AP(Average Precision)는 IoU를 기반으로 계산되므로 IoU에 대해 알아보자.
아래 식은 IoU에 대한 식을 정의한다.
IoU는 Jaccard Similarity, Jaccard Index라고도 불리는데, 이는 기본적으로 prediction과 target간의 percent overlap을 정량화하는 방법이다.

실제로는 Object에 Bbox가 여럿 나타나 복잡한 상황이 된다.
∙ 참값 하나가 여러 예측과 겹치거나
∙ 예측이 여러 참값과 겹치고 겹침이 없거나.

1.2 AP. &  mAP

AP (Average Precision)

AP는 위와 같은 상황(Bbox가 여럿 나타나는 상황)에서 계산한다.
AP계산을 위해 TP, FP, FN을 세야한다. cf) True = 맞춘것을 의미

AP 계산알고리즘:
① 신뢰도 임계값을 넘는 Bbox만 선택, 예측목록을 생성
② 예측목록에 있는 Bbox를 신뢰도로 정렬
③ Confidence값이 큰 순서대로 처리.
현재 Bbox가 IoU 임계값을 넘으면 TP로 판정, 아니면 FP로 판정


❗️이때, 2개 이상의 물체에 하나의 Bbox가 겹치게 된다면?
IoU가 최대인 쌍을 사용한다.
TP발생 시, 참값목록에서 TP_Bbox를 제거, 이중의 쌍을 맺는 것을 방지한다.
이때, 예측목록에 있는 Bbox를 모두처리후, 쌍을 맺지못한 채 남아있는 TP_Bbox는 FN으로 판정한다.

mAP (mean Average Precision)

AP를 각 물체 class에 대해 계산 → 이 AP를 모든 class에 대해 평균한 값이다.

아래 예시를 살펴보자.
먼저, Precision과 Recall은 아래수식처럼 구할 수 있다.

즉, True = 맞춘것을 의미하므로 Precision과 Recall은 아래처럼 설명할 수 있다.
∙ Precision = (맞춘것=TP) / (예측한 것 중 = ?P)
∙ Recall = (맞춘것=TP) / (실제 중)

먼저 mAP를 구하는 순서에 대해 설명해보겠다.

⓪ Confidence=0.6  &  IoU=0.5 로 설정

① Confidence임계값을 넘긴 Bbox로 예측목록 {a,b,d}를 생성

② 예측목록을 Confidence순으로 정렬 → {b,d,a}

③ 신뢰도가 가장 높은 b먼저 처리.
 ∙ b는 2,3과 겹침 → IoU가 더 큰 2와 쌍을 맺음
 ∙ b-2쌍을 TP로 판정 후, 2는 참값(Ground_Truth)목록에서 제외.

④ 2번째 신뢰도를 갖는 d를 처리
 ∙ d는 4와 IoU가 0.12(<임계IoU)이므로 FP로 판정

⑤ 마지막 Bbox예측목록원소 a를 처리
 ∙ a는 1과 IoU가 0.6(=임계IoU)이므로 TP로 판정 

⑥ Bbox로 생성한 예측목록을 모두 처리하였다.

⑦ 예측 Bbox 처리 후, 쌍을 못맺은 3과 4는 FN으로 판정.

⑧ 최종적인 Precision과 Recall은 다음과 같다.
 ∙ TP=2 , FP=1 , FN=2
 	∴ Precision = 2/3
 	∴ Recall = 2/4

⑨ Confidence임계값을 0.5로 낮추면, Precision과 Recall은 다음과 같다.
 ∙ TP=3 , FP=2 , FN=1
 	∴ Precision = 3/5
 	∴ Recall = 3/4

1.4  ROC / PR-Curve

PR-Curve

위의 PR-Curve에서 알 수 있는 사실은 Precision과 Recall은 서로 반비례 관계를 보인다는 점이다.
이때, PR곡선 아래부분면적이 의미하는 바가 바로 AP(Average Precision)이다.
AP는 [0,1]의 범위를 가지며, 1에 가까울수록 좋은 성능을 가짐을 의미한다.

추가적으로, class별로 AP를 구하고, 모든 class에 대한 평균(mean)을 계산한 것이 바로 mAP이다.

ROC-curve

ROC Curve는 양성 클래스와 음성 클래스의 비율이 균형적일 때 성능을 평가하는 데 유용하다.
즉, 클래스 불균형이 낮을 때, ROC Curve는 민감도와 특이도의 trade-off를 측정하여 모델의 성능을 평가한다.

좀 더 자세한 설명은 아래 필기로 대체한다.

2. Traditional Detection Method

Detection의 초기연구는 사람얼굴에 국한되어 진행되어왔다.
PASCAL VOC대회 시작 이후, 여러 class로 확장되어 연구가 진행되어왔다. [Everingham2010]

Object Detection은 물체의 위치와 class를 모두 알아내야 해결이 가능한데,
어떤 물체가 어디에 있는지 한번에 알아내기 어렵다.
따라서 가능성이 있는 후보영역을 많이 생성하고, 영역을 classification algorithm으로 걸러내는 two-stage 접근방법을 주로 사용해왔다.
여기서 주의할 점은, two-stage 접근방법을 제대로 구현하려면
"후보영역을 가급적 적게 생성"하고,
"실제 물체를 놓치지 않아야하며",
"후보영역을 높은 정확률로 분류"할 수 있어야 한다.

HOG

Viola Algorithm. with. HOG(Histogram Of Gradients)
2004년, 성공적인 얼굴검출방법으로 Viola Algorithm이 있다.
여기서, Dalal은 HOG Feature Extraction을 제안하였다.
아래는 Dalal은 HOG Feature Extraction을 간단히 설명한 그림이다.

좀 더 자세한 사례로 예시를 들어보자.

먼저 위처럼 후보크기를 128×64로 변환한다.
이후 이 영역을 8×8크기로 나누면, 16×8개의 타일이 생성된다.
이후 각 타일에서 특징을 추출한다.

타일에 있는 64개의 화소에 각 수평방향과 수직방향의 edge연산자를 적용해 gradient방향을 계산하고
9개의 구간을 양자화한다.
이후, 양자화된 gradient방향으로 histogram을 구하면 9차원 feature vector가 된다.
이때, 명암변화에 둔감히 하기 위해 feature vector를 정규화한다.
정규화과정에서 4개타일의 특징벡터를 이어붙여 36차원의 벡터를 생성하고, 36개요소의 제곱을 합하면 1이 되도록 한다.

이때, 4개타일=window라 하는데, 가로방향으로 7번, 세로방향으로 15번 이동한다. (sliding_window방식)
결국 7×15×36 = 3780차원의 특징벡터를 얻는데, 이를 HOG Feature라 한다.

이후 HOG Feature를 SVM에 입력해 사람일 확률을 출력한다.

DPM

DPM (Deformable Part Model)
이후 등장한 DPM은 파트를 이용해 물체를 모델링한다.
그렇기에 part-based model로 불리기도 한다.

Object는 자세와 모양이 심하게 변하기에, DPM은 이런 특성을 반영하기위해 물체를 몇개의 부품으로 모델링한다.

위의 그림은 5개 part로 모델링을 한다.
∙ 좌측은 물체전체
∙ 중앙은 5개의 part
∙ 우측은 part가 발생할 위치에 대한 확률분포
이때, Feature Extraction으로는 HOG를 사용한다.

또한, DNN도입 이전이기에

Detection Model은 위의 그림처럼 학습으로 알아낸다.

3.  R-CNN 계열 (RCNN, Fast R-CNN, Faster R-CNN)

3.1  R-CNN

R-CNN은 후보영역을 생성하는단계와 후보영역을 분류하는 단계로 구성된다 [Girshick 2014].
R-CNN은 후보영역을 영역제안[Region Proposal]이라한다.

2-stage를 순차적으로 처리하기에 RCNN계열방법들을 2-stage방법이라 부른다.
아래 그림은 영역제안과 영역분류의 2-stage를 거치는 RCNN처리과정이다.

∙ 영역제안과정

물체가 있을 가능성이 높은 영역을 찾는단계.
RCNN은 Selective Search Algorithm으로 image에서 2000여개의 후보영역을 생성한다.
Selective Search는 image를 super pixel로 분할 후, clustering과정으로 영역을 생성.

생성된 영역을 227×227크기로 정규화하고,
CNN에 입력해 4096차원의 특징벡터를 추출한다.

---

∙ 영역분류과정

추출된 특징벡터를 분류해 물체의 클래스를 알아내는일은 SVM이 담당하며,
SVM은 Binary-classifier이기에 물체마다 SVM을 학습해야한다.

Pascal VOC는 20개 class가 있으므로 21개 SVM이 각 클래스확률을 계산해
그림처럼 맨 오른쪽에 있는 클래스확률벡터를 출력한다.
cf) 21번째 SVM은 물체가 아닌 클래스를 의미.

최종적으로 2000여개 후보영역에 대해 위치와 클래스정보를 확보한 후,
21번 클래스를 버리고 나머지에대해 후처리를 거쳐 위치와 클래스를 최종적으로 출력한다.


즉, "Selective Search알고리즘 → RoI 생성 → CNN으로 특징벡터 추출 → SVM" 순이다.
다만, RCNN은 분류에 SVM을 사용하고 영역제안을 위해 고전방법을 사용하는 등 속도가 느리다는 결정적 단점이 있다.
이로인해 RCNN의 한계를 극복하는 fast RCNN과 faster RCNN이 등장했다.

3.2  Fast-RCNN

아래그림은 Fast-RCNN의 처리과정이다 [Girshick 2015].
∙ 영역제안단계: Selective Search Algorithm 사용.
∙ 영역분류단계: SVM을 Neural Net으로 대체.

∙ RoI  투영

input image를 Conv에 통과시켜 Conv특징맵을 얻는다.
Conv특징맵에서 후보영역에 해당하는곳을 RoI(Region Of Interest)로 지정하는, RoI투영을 진행한다.
그림에서 좌측선수에 해당하는 RoI가 노란색인데, RoI에 RoI풀링층을 적용해 고정크기맵(녹색 7×7맵)을 출력한다.

---

∙ RoI  특징벡터추출

이 특징맵을 2개의 FC층을 통과시켜 4096차원의 RoI특징벡터로 변환한다.
RoI특징벡터는 2갈래로 나뉜다.

---

∙ 분류 및 회귀과정을 모든 RoI에 적용

한곳은 분류를 담당하는 FC층을 통과, 클래스확률벡터를 출력하고
한곳은 회귀를 담당하는 FC층을 통과, 클래스별 박스정보(x,y,h,w)가 된다.

즉, "RoI투영 → RoI 특징벡터추출 → 분류 및 회귀과정을 모든 RoI에 적용" 한다.
물체없음으로 판정된 RoI는 버리고, 나머지는 후처리 후 박스정보와 클래스정보를 최종 Detection결과로 출력한다.

 

---

Fast-RCNN은 박스정보를 알아내는 회귀와 클래스를 알아내는 classification을 동시에 수행하기 때문에 하나의 Loss function으로 두 task를 달성해야한다.
∙ 손실함수: J = Jclassification + λ∙Jregression 형식
이런 손실함수를 다중과업손실함수(Multi-task Loss function)라 한다.
λ는 두 task의 비중을 결정하는 hyper-parameter로 논문에서는 1로 설정했다.

다만, 여전히 영역제안단계에서 고전알고리즘(Selective Search)을 사용하기에 한장의 이미지처리에 CPU로 2초가량 걸린다 알려져있다.

3.3   Faster-RCNN

아래그림은 Faster-RCNN의 처리과정으로 Fast-RCNN에 비해 정확도와 속도를 획기적으로 개선하였다 [Ren 2015].
오직 CNN신경망으로만 Object Detection을 수행하는 지평을 열어버렸기에 매우 기념비적이라 할 수 있다.

∙ 영역제안단계: 영역제안모듈, RPN(Region Proposal Network)신경망 사용.
∙ 영역분류단계: Fast R-CNN 사용.

∙ RPN

Pre-Trained VGG16을 앞에 배치해 특징맵을 추출(노란색 H×W맵)한다.
RPN은 이 특징맵의 각 pixel에서 3×3 filter로 512차원의 특징벡터를 추출한다.

이 특징맵에 서로 다른 2개의 1×1 convolution을 적용해 6개의 값들을 추출한다.
 ∙ 물체여부를 나타내는 2개의 값
 ∙ 박스정보를 나타내는 4개의 값.

위의 연산을 9번 적용해 크기와 가로세로비율이 다른 9개의 박스 (= Anchor)를 생성.
Anchor: 여러크기의 물체를 표현하는 Anchor를 생성함으로써 다중크기의 물체탐지능력을 갖춘다.

결과적으로 H×W의 pixel마다 9개의 Anchor가 생성되므로 H×W×9개의 Anchor가 생성된다.
여기서 NMS를 적용해 2,000여개의 Anchor만 남긴다.


즉, CNN으로 특징맵 추출 → 1×1 conv로 6개값 추출 9회 진행 → Anchor Box생성 순이다.

---

∙ Fast R-CNN

이 Anchor들을 RoI으로 간주해 위 그림의 신경망의 뒷부분에 있는 Fast-RCNN으로 입력한다.
Fast-RCNN은 후보영역 각각에 대해 RoI투영 → RoI 특징벡터추출 → 분류 및 회귀과정을 적용한다.

물체없음으로 판정된 후보영역은 버리고, 나머지 후처리 후, 박스정보와 클래스정보를 최종 Detection결과로 출력한다.

4. YOLO 계열

YOLO는 RCNN계열에 비해 정확도는 떨어지나 속도가 월등히 빠른 장점이 있다. (물론, 이도 옛날얘기로 최근에는 YOLOv8, YOLOX계열 등으로 충분히 RCNN을 뛰어넘는 성능을 보이고 있으며, 정확도가 높은 모델을 필요로 하는 경우, InternImage나 DETR계열을 사용한다.)

2016년 최초 발표된 YOLO v1은 Titan X GPU에서 45FPS를 처리한다.[Redmon2016]
YOLO는 물체의 위치와 클래스정보를 Regression으로 한번에 알아내는, End-to-End방식을 고수한다.

YOLO v1의 특징

image를 s×s격자로 나눈다.
(실제 구현은 아래그림의 노란격자처럼 s=7로 설정해  총 49개의 칸이 존재한다; 빨간박스는 dataset에 라벨링된 참값이다.)

아래그림에서 검은칸을 예로들어 90차원의 벡터로 표현해보자.
빨간색의 좌측선수를 표시한 빨간박스의 중심은 검은칸에 놓이기에 검은칸이 이 박스를 책임진다.
벡터는 90차원인데 앞의 5개요소(x1, y1, w1, h1, o1)는 이 박스의 위치와 크기, 신뢰도를 의미한다.

박스의 위치와 크기는 영상좌표계를 [0,1]사이로 정규화하고 정규화좌표를 중심으로 표현한다.
x2,y2,w2,h2,o2는 또다른 박스를 표현할 수 있기에 한칸은 박스를 2개까지 책임질 수 있다.

p0~p80은 해당박스가 어떤객체클래스에 속하는지 나타내는 one-hot코드이다.

YOLO는 RCNN계열에 비해 상당히 단순한데, 아래 그림은 YOLO가 사용하는 CNN의 구조이다.
∙ Conv층: 24개 / MaxPool층: 4개 / FC층: 2개 로 구성되며
  - input은 448×448크기로 변환되어 입력되고
  - output은 7×7×90의 출력텐서를 갖는다.

위 그림에서 신경망은 image를 입력으로 받아 7×7×90의 출력텐서를 참값으로 주어 통째로 학습한다.

참값텐서에 [float으로 표시되는 Bbox정보], [OneHot코드로 표현되는 클래스정보]가 섞여있기에
classification과 regression이 동시에 일어난다. 

YOLO의 Loss function

YOLO의 Loss function은 5개의 항으로 구성된 조금 복잡한 식을 갖는다.

∙ 1, 2항은 각 박스의 위치오류와 크기오류를 측정하는 Regression Loss이다.
∙ 3항은 물체가 있지만 없다고한 FN오류를 측정하는 Confidence Loss이고,
∙ 4항은 물체가 없지만 있다고한 FP오류를 측정하는 Confidence Loss이다.
∙ 5항은 class를 나타내는 OneHot코드의 오류를 측정하는 Classification Loss이다.

YOLO v3

YOLO v3는 여러 scale을 표현해 다양한 크기의 물체를 탐지하는 능력이 향상되었다 [Redmon 2018]. 
YOLO v3은 (object, class)의 85차원 벡터를 추출하는 층을 신경망 3곳에 배치한다.

∙ yolo_82층에서는 14×14격자로 나눠 14×14×85×3텐서를 출력한다. 따라서 14×14의 각 요소는 박스를 3개까지 출력한다.
∙ yolo_94층에서는 28×28격자로 나눠 28×28×85×3텐서를 출력한다. 
∙ yolo_106층에서는 56×56격자로 나눠 56×56×85×3텐서를 출력한다.

이 층들이 출력한 텐서를 객체정보로 변환하면, 다양한 크기의 객체를 탐지할 수 있다.

5. Transformer : DETR , SETR

고안 배경)

Image에서 객체를 탐지하는 신경망은 여러 Bbox를 예측해야해서 집합예측모델이라 할 수 있다.
모델의 예측과 정답에 해당하는 라벨이 모두 Box집합이기에 Hungarian Algorithm으로 최적의 매칭쌍을 알아내 손실함수를 계산한다.
고전방법과 딥러닝 모두 후보영역을 충분히 많이 생성한 후, 후보영역 각각에 대해 어떤 물체인지 분류하는 접근방법을 사용한다.
이후, 여러 Bbox가 중복검출되는 현상이 발생하면, 중복해소를 위해 비최대억제(NMS)로 후처리를 적용한다.

---

고안 배경)Transformer를 사용하면,
∙ 후보영역(RoI)을 생성하는 중간단계없이 Box집합을 직접예측할 수 있을까?
∙ 중복현상이 아예 일어나지 않게 할 수 있을까?
∙ Convolution기반의 Faster-RCNN이나 YOLO보다 좋은 성능을 얻을 수 없을까?

---

CNN은 유연하기에 Faster-RCNN과 YOLO v3의 구조를 자유자재로 설계가능하였다.

하지만 Transformer는 다소 고정적인데, 이유는 아래와 같다.
∙ T × d_model 크기의 tensor가 여러 encoder블록과 decoder블록을 흐르며 연산이 진행

---

Encoder만 사용되는 ViT와 달리(https://chan4im.tistory.com/163)
DETR는 영상을 입력으로 박스집합을 출력해야하기에 Encoder와 Decoder 모두 사용한다.
Decoder에 붙은 출력층은 T × d_model tensor를 Box집합으로 변환해야한다.

손실함수는 Transformer가 예측한 Box집합과 label박스집합이 일치하는 정도를 측정하는 능력을 가져야한다.
Box는 직사각형을 표현하는 4개의 좌표(coordinate)와 물체 클래스를 나타내는 Class확률벡터(softmax)로 표현된다.

5.1 DETR (DEtection TRansformer)

Faster-RCNN같은 CNN기반 신경망은 Box집합을 바로 예측하기 어렵기에
RoI를 생성 후, 영역을 분류하는 일종의 우회하는 방식을 사용한다.
즉, 기존문제를 대리문제로 바꾸고 대리문제를 푸는 셈이라 볼 수 있다.
[Carion 2020]은 transformer를 이용해 집합예측을 하는 DETR모델을 제안한다.


DETR은 RoI생성단계가 없고, NMS라는 후처리단계가 없다.
즉, End-to-End 학습이 가능하다.

위의 그림은 DETR모델구조로 DETR은 ①~③로 표시한 3가지 모듈로 구성된다.

∙ 모듈 ①

CNN을 통해 Feature Extraction을 진행.
또한, 1×1 convolution을 적용해 channel을 C에서 d_model로 줄여 h×w×d_model의 tensor로 변환한다.
이후 Flatten으로 pixel을 이어붙여 행에 배치한 hw×d_model 행렬을 얻는다.
위 그림에서는 hw를 T로 표기하는데, 이는 최종적으로 transformer의 input으로 입력할 T×d_model행렬을 얻음을 의미한다.

이 행렬의 각 행은 축소된 image의 pixel에 해당하며, Self-Attention계산 시 행이 Query로 참여하기에
축소된 pixel(= patch)간의 attention정보를 추출하는 셈이다.
즉, DETR은 Self-Attention을 반영한다 볼 수 있다.

---

 

∙ 모듈 ②

Encoder-Decoder로 구성된 Transformer로
모듈 ①에서 입력된 T×d_model 행렬에 Position Encoding을 적용해 Encoder블록1에 입력한다.

Encoder블록1, ... , Encoder블록M을 통해 변환된 행렬은

Decoder의 MHA에 입력되어 Key와 Value의 역할을 한다.


Decoder를 좀 더 살펴보자.

기존 Transformer에서는 Decoder가 Auto-Regressive방식으로 작동한다.
즉, NLP에서 <SOS>토큰을 주면 첫번째 단어가 생성되고 
<SOS>토큰과 첫번째 단어를 주면 두번째 단어가 생성된다.
이런 AR방식을 객체탐지에 적용할 수 있을까?? → ❌ 
(Bbox는 순서없이 집합으로만 표현하기 때문.)

Decoder 입력을 보면 object queries라 표시된 K개 벡터가 있다.
K×d_model크기의 행렬이 입력된다는 의미로 K는 탐지가능한 물체의 최대개수이다.
출력층은 물체가 아닌경우, ∅를 출력할 수 있기에 가변개수의 객체탐지가 가능하다.

그림의 예시에서는 2개의 박스와 3개의 ∅를 출력했다.
Decoder의 최초 입력인 object queries는 Box에 대한 아무런 정보❌ 
Position Encoding, P를 갖고 출발해야하는데, DETR은 학습을 통해 알아낸 P를 사용한다.

---

∙ 모듈 ③

Decoder블록이 출력한 K×d_model행렬의 각 행을 Feed-Foward에 통과시켜 박스정보로 변환한다.
이렇게 모델이 예측한 박스집합을 ŷ라 하고
정답에 해당하는 Ground_Truth Box집합을 y라 하자.

y에 ∅박스를 추가해 ŷ처럼 K개 박스를 갖게 한다. 
ŷ과 y에 Hungarian Algorithm을 사용해 최적매칭쌍을 구한다.



📌 Loss Function
매칭된 참값박스 i와 예측박스 j쌍을 이용해 아래 처럼 손실함수를 정의한다.

첫번째 항은 class를 맞췄는지 측정한다. (p̂j(ci)는 class확률벡터에서 참값class에 해당하는 확률.)
두번째, 세번째 항은 물체위치를 얼마나 정확히 맞혔는지 측정한다. (2번째항: IoU ; 3번째항: L1 Distance)

---

Self-Attention Matrix식 = softmax(QK^T / √d_key).
이 행렬은 image를 구성하는 여러 Q벡터가 상호주목하는 정도를 표현.

전술했듯, DETR에서 모듈 ①이 m×n크기의 기존image를 h×w로 축소하고
축소된 특징맵에서 화소각각을 Q벡터로 취하기에
Self-Attention Matrix는 축소된 pixel (= patch)가 상호주목하는 정도를 측정한다.

위의 그림에서 주황색 표시된 코끼리의 경우, 코와 발, 등, 꼬리에 주목하고 있는데,
이는 Bbox의 경계에 주목하고 있다는 사실을 확인할 수 있다.

이 사실을 바탕으로 Decoder의 역할을 추론해보면,
Decoder는 Bbox를 제대로 알아내기위해 Self-Attention Matrix를 통해 물체의 상하좌우 경계에 주목한다고 할 수 있다.

5.2 SETR (SEgmentation TRansformer)

DETR는 Object Detection의 목적으로 고안되었다.
이때, Transformer의 특성으로인해 분할을 할 수 있도록 쉽게 확장할 수 있다.

위의 DETR모델의 모듈 ③은 출력행렬을 해석해 Box정보로 변환하는, Detection용도의 Head이다.
따라서, Segmentation용도의 Head를 붙이면, 분할용도의 Transformer모델인, SETR이 된다.
즉, 요약하면 SETR은 Encoder(Transformer) - Decoder(CNN)의 구조를 띈다.

---

---

Segmentation Head는 축소된 해상도를 원래 해상도로 복구하기위해 UpSampling을 위한 Convolution층이 포함된다.

(a). 먼저 image(m×n×3)를 고정된 크기의 patch로 나누고
각 patch를 선형 임베딩한 다음 Position Embedding을 추가한 후,
결과 벡터 시퀀스를 표준 트랜스포머 인코더에 공급한다.
(이때, 픽셀 단위 분할을 수행하기 위해 다양한 디코더를 도입한다)

(b) Decoder는 점진적 UpSampling(resulting in a variant called SETRPUP)으로
여러 단계의 Convolution층을 쌓아 피라미드 형태로 쌓은 Decoder를 제안한다.

(c) multi-level feature aggregation (a variant called SETR-MLA).

6. Backbone Transformer : Swin Transformer

6.1 Backbone Transformer

CNN transfer learning은 DNN의 큰 이점이다.
보통 전이학습(transfer learning)에 널리 사용되는 Backbone model로는 VGG, GoogLeNet, ResNet, DenseNet121 등이 있었으며, 최근에는 EfficientNet 등이 있다.

Backbone model은 주로 input data에서 feature map을 추출하는 역할을 한다. 
주로 pretrained model을 사용하며, 다양한구조(CNNs, Transformers, ResNets)를 사용할 수 있다.

기존 NLP에서 Transformer가 사용이 되었기에(GPT, BERT), 초반에는 transformer도 transfer learning을 위한 Backbone model로 쓸 수 있을까? 라는 의문에서 출발했다.

지역정보를 추출하는 Convolution연산에 의존하는 CNN에 비해 Self-Attention에 의존하는 Transformer가 Transfer Learning에 훨씬 유리하다는 실험적 입증이 많이 발표되었는데,
Backbone으로 쓸 수 있는 Vision Transformer를 제작할 수 없을까? 라는 의문에서 Swin Transformer로 답을 해준다.

---

Backbone이 되려면 image의 feature를 충분히 반영한 구조를 설계해야한다.
기존 transformer는 문장처리목적으로 설계되었기에, 조금의 변형이 필요하다.
Backbone모델이 되려면 아래의 특성들을 잘 반영해 처리할 수 있어야 한다.
(문장을 구성하는 단어는 scale변화가 없으나 image를 구성하는 Object는 아주 다양한 크기로 나타나기에 scale변화가 심한편.)
(또한, 한 문장을 구성하는 단어는 수십∙수백개에 불과하지만, image를 구성하는 pixel은 수만~수백만 개이다.)
(문장의 단어는 띄어쓰기로 잘 분할되어있지만, image는 Object끼리 혹은 배경이 심하게 섞여있다.)

6.2 Hierarchical Feature map. &. Shifted Window

Swin Transformer는 image특성을 반영하기위한 핵심아이디어를 2가지로 설명한다.

∙ Hierarchical  ViT

아래 그림(a)은 Hierarchical ViT(= Hierarchical Featuremap)을 사용해 객체의 scale변환에 대응하는 방법을 설명한다.
모든 window는 M×M개의 patch로 구성된다. (여기서 M=4)
맨 아래층은 작은 patch_size로 window가 4×4개가 있다.
가운데 층은 patch_size가 2배로 커져 2×2개의 window가 있고, 맨 윗층은 1개의 window가 있다.
이렇게 작은 patch부터 큰 patch로 구분해 처리하면, 여러 크기의 객체를 분류하거나 탐지할 수 있다.

그림 (b)의 ViT의 경우, 영상을 분류하는데 사용할 수는 있지만 객체탐지 및 분할에는 한계가 있다.

계층적 특징맵은 계산효율상에도 큰 이점이 존재한다.

단일해상도를 사용하는 ViT의 경우)
224×224 image를 16×16 patch(= 14×14개)로 나눈다 가정하자.
이 경우, T = 196인 행렬이 입력되는데, MHA는 T개 patch끼리 Self-Attention을 계산하기에 T²번 연산을 수행한다.
이때, 연산은 QK^T의 행렬곱으로 이뤄진다.
Q와 K가 T×d_key행렬이므로 T²×d_key만큼 곱셈이 수행된다. 

다중해상도를 사용하는 Swin의 경우)
window별로 self-attention을 적용한다.
window는 M×M개의 patch로 구성되기에 한 window는 M²×d_key만큼 곱셈을 수행한다.

즉, ViT에비해 (T×T) / (M×M×window개수)배 빠르게 계산된다.
예를 들면 그림(a)의 맨 아래층에서는 window가 16개이므로 49배 빠르다.

---

∙ Shifted Window

Swin Transformer의 이름이 Shifted WINdow에서 유래되었을 정도로 핵심아이디어이다.
ℓ번째 layer에서 이전처럼 window를 나누는데,
그 다음 ℓ+1층에서는 window를 절반크기만큼 수평과 수직방향으로 이동해 나눈다.

shifted window를 사용하면 window간의 연결성강화 및 다양한 크기의 객체를 처리할 수 있고,
객체의 상대적인 위치정보를 저장하는 등 이를 통한 성능향상이 가능하다.

6.3 Swin Transformer Architecture

아래그림은 Swin Transformer의 구조이다.

좌측에서 우측으로 흐르는 단계 1~4는
좌측그림의 (a)의 아래에서 위로 진행하며 patch는 커지고
window개수는 작아지는 방향에 해당한다.




예를들어, C=96으로 하고, m×n = 448×448 image가 입력될 때,
단계1) input tensor: 112×112×48 // output tensor: 112×112×96
단계2) input tensor: 112×112×96 // output tensor: 56×56×192
단계3) input tensor: 56×56×192 // output tensor: 28×28×384
단계4) input tensor: 28×28×384 // output tensor: 14×14×768

위 그림의 (a)는 이런 tensor변환을 어떻게 수행하는지 설명한다.

단계 2에서 patch합치기 적용시, 맨 아래층에서 맨 위층으로 진행하는 과정에 해당하는 것으로 단순히 이웃한 4개 patch를 하나의 patch로 합치는 과정을 의미한다.

모든 단계를 거쳐 얻은 특징맵에 classification을 위한 head를 붙이면 classifier가 되고,
Detection을 위한 head를 붙이면 detector가,
Segmentation을 위한 head를 붙이면 segmentor가 된다.
이런 방식으로 Swin Transformer는 Backbone 모델로 작용한다.

이제 단계 1~4에 노랜색 표시된 Swin Transformer Block의 동작을 그림 (b)를 통해 살펴보자.
(b)는 Encoder Block을 2개 쌓은 상황으로 현재 Block ℓ은 ℓ-1번째 Block에서 x^ℓ-1 tensor를 받아 Layer Normalization을 거쳐 W-MHSA층으로 Self-Attention을 적용한다.
이후, Add와 Norm, FF, Add를 적용해 x^ℓ을 출력한다.

ℓ+1번째 Block은 x^ℓ을 입력으로 받아 같은 과정을 거쳐 x^ℓ+1 tensor를 출력한다.
ℓ Block과 ℓ+1 Block의 Self-Attention을 W-MHA, SW-MHA로 표기했다.
W-MHA는 window를 분할하고 SW-MHA는 Shifted Window로 분할한다.

Swin Transformer는 Backbone으로 쓰이는 CNN인 ResNet등과 호환되도록 tensor모양을 설정했기에
기존 딥러닝모델에서 CNN-Backbone을 들어내고 Swin-Transformer로 쉽게 대치할 수 있다.

이미 일전 글들에서 classification관련해 많이 다루었기에 아래 링크를 남긴다.

https://chan4im.tistory.com/category/Deep%20Learning%20%3A%20Vision%20System/%EB%85%BC%EB%AC%B8%20review

좀 더 자세한 CNN의 원리를 알고싶다면, 아래 링크를 추천한다.

https://poloclub.github.io/cnn-explainer/

📌 CNN 및 Vision 기본:
∙ CNN 원리:
https://chan4im.tistory.com/160
https://chan4im.tistory.com/133
∙ Auto-Encoder: https://chan4im.tistory.com/156

📌 AlexNet: https://chan4im.tistory.com/145

📌 VGGNet: https://chan4im.tistory.com/146

📌 Batch Normalization: https://chan4im.tistory.com/147

📌 GoogLeNet: https://chan4im.tistory.com/149

📌 ReLU에 관한 고찰: https://chan4im.tistory.com/150

📌 ResNet: https://chan4im.tistory.com/151

📌 ResNet-V2: https://chan4im.tistory.com/152

📌 DropBlock: https://chan4im.tistory.com/153

📌 Vision Transformer: https://chan4im.tistory.com/163
∙ Attention: https://chan4im.tistory.com/161
∙ Transformer: https://chan4im.tistory.com/162
∙ ViT: https://chan4im.tistory.com/164

---

📌 Semantic Segmentation:
∙ Intro: https://chan4im.tistory.com/158
∙ Model: https://chan4im.tistory.com/159

📌 목차

1. Intro. 코딩의 중요성을 간과하지 말라!!!
2. 좋은 코드작성을 위한 원칙
3. 자주하는 실수
4. Debugging.  &.  Testing
5. 변수범위의 이해

1. Intro. 코딩의 중요성을 간과하지 말라!!!

코딩테스트 및 대회에서 코드를 빨리 작성하는 것보다 더욱 중요한 것은 뭘까?
바로 "읽기 쉬운 코드"를 작성하는 것이다.
복잡하고 가독성이 떨어지는 코드는 디버깅도 어렵고 한번에 정확히 작성하기도 어렵기 때문이다.
많은 전문가들은 반복적 연습으로 자신의 코드 스타일을 간결하고 일관되고 다듬기 위해 노력한다.

본 글에서는 코딩과 디버깅에 관한 노하우와 코딩테스트에서 자주하는 실수에 대해 다룬다.

2. 좋은 코드작성을 위한 원칙

간결한 코드 작성
짧고 간결한 코드는 오타나 단순버그가 생길 확률을 줄이고 쉬운 디버깅을 가능케한다.

C/C++의 경우, #define을 이용한 매크로 방법으로 반복문처럼 우리가 자주 타이핑 하는 코드를 빠르게 표현하는 경우를 예로 들 수 있다.

#define FOR(i,n) for(int i=0; i < (n); i++)
bool hasDuplicate(const vector<int>& array){
	FOR(i, array.size())
        FOR(j, i)
            if (array[i] == array[j])
                return true;
   	return false;
}​

 

물론, 위와 같은 방법은 속된말로 "에바"라고 생각할 수도 있다.
하지만, 위와 같은 방법은 아래와 같은 실수를 예방할 수 있다.

for (int i=0; i < array.size(); i++)
	for (int j=0; j < i; i++) // j++이어야함​

다만, 이런 방법은 가끔 사용하면 아주 유용하지만 
일종의 "대치동의 어둠의 스킬"같은 느낌이기에 신중히 사용할 것이 권장된다.

적극적인 코드 재사용
간결한 코드를 작성하기 위한 가장 직접적인 방법은 코드를 "모듈화"하는 것이다.
같은 코드 반복시(약 3번이상), 이들을 함수나 클래스로 분리해 재사용하는 것이다.

시간이 없다해서 코드를 더 알기 쉽게 고치는 것을 주저하는 것은 아니된다.
계속 눈이 코드의 간결성에 익숙하게 하여 다음 코딩에 좀 더 간결한 코딩을 가능케한다.

표준 라이브러리 공부
C++의 표준라이브러리, STL의 경우 문자열, 동적배열, 스택, 큐, 리스트, 딕셔너리 등의 자료구조와 정렬 등의 표준 알고리즘 구현을 직접하는 것이 아닌, 구현 사용법에 익숙해진다면 이를 활용해 더욱 빠른 코드작성이 가능하다.

항상 같은형태로 작성
while문을 쓰던자리에 do-while문을 사용해본다던지 하는 등을 말한다.
이는 시간이 지나면서 점점 실수의 원인이 될 수 있는만큼 지양하는 편이 좋다.

일관∙명료한 명명법 사용

int a[30][30], i, j, k=0;​

 

위와같은 코드는 모호하지 않은 변수명과 함수명의 예시이다.
보통, 사용언어에 맞는 naming convention을 익히는 것을 추천한다.(예를 들어 CamelCase)

모든 자료를 정규화
같은 자료를 2가지 형태로 저장하지 않는 것이다.
예를 들어 유리수 표현클래스 Fraction의 경우, 기약분수로 표현하는 것이 좋다.
(9/6과 3/2로 표현하는 방법이 달라지면 표현하는 변수가 달라질 수 있기 때문.)

코드와 데이터를 분리
날짜를 다루는 프로그램을 작성한다 가정하자.

string getMonthName(int month){
	if (month == 1) return "Jan";
    if (month == 1) return "Feb";
    ...
    if (month == 12) return "Dec";
}​

처음 코딩하는 사람들의 경우, 위와 같이 작성할 것이다.

하지만, 이는 연차가 쌓일수록 기피하는 코드가 되는데, 코드의 논리와 상관없는 데이터는 분리하는 쪽이 낫다.
예를들어, 아래처럼 월의 영어이름을 아래처럼 table로 생성할 수 있다.

const string monthName[] = {"Jan", "Feb", ... , "Dec"};​

이 기법의 또 다른 좋은 예시로 체스와 같은 보드게임이 존재한다.

const int KnightDx[8] = {2,2,-2,-2,1,1,-1,-1};
const int KnightDy[8] = {1,-1,1,-1,2,2,2,-2};​

3.  자주하는 실수

산술 Overflow
계산과정에서 변수의 표현범위를 벗어나는 값을 사용하는 것으로 Section 5에서 좀 더 상세히 다룬다.

배열범위 밖 원소에 접근
C/C++은 배열원소 접근 시, 별도로 확인하지 않기에 범위를 벗어난 위치값에 접근하는 버그는 아주 찾기 힘들다.
다만, 이때 Run-time stack등을 건드려 프로그램이 Run-Time-Error를 내고 종료될 때, 이를 알아챌 수 있다.
하지만, 오류가 나지 않으면서 틀린 답만 내놓는 경우도 종종 있기에 이런 실수를 예방하기 위해서는 배열크기를 정할 때, 계산을 신중하게 하는 것이 가장 중요하다.

일관되지 않은 범위표현방식의 사용
배열의 잘못된 인덱스를 참조하는 오류가 발생하는 큰 원인 중 하나.
2~12를 프로그램내에서 표현해보자.
2 ≤ i ≤ 12도 되고 1 < i < 13도 되며,이 두가지 방법에는 모두 나름의 장단점이 존재한다.

닫힌구간의 문제는 공집합을 우아하게 직관적으로 표현할 수 없다는 점이고
열린구간의 문제는 배열의 첫원소부터 시작하는 법위를 표현시, 첫원소 이전의 가상원소를 사용해야한다.

따라서 프로그래밍언어는 대부분 이 둘 사이의 절충인 반열린구간(half-open-interval)을 사용한다.
0 ≤ i < n
ex)
[C++]: begin()은 첫원소를 가리키지만, end()는 마지막원소 다음의 가상의 원소를 가리킨다.
[Python]: a[4:8]은 a[4]~a[7]의 원소를 의미.

Off-by-One 오류
계산의 큰 줄기는 맞지만, 하나가 모자라거나 하나가 많아서 틀리는 코드로 발생하는 모든 오류들을 가리킨다.
예를들어 <, > 연산자와 ≤, ≥연산자를 혼동해 원소를 하나 더 적게나 많이 순회하는 경우도 이 예시에 포함된다.

ex) 100미터에 10미터 간격으로 기둥을 세운다 가정하자.
이때, 필요한 기둥은 10개가 아닌, 11개이다.

Compiler가 못잡는 상수오타
변수명이나 함수명에서 낸 오타는 컴파일러에서 잡는다.
하지만 각종 상수에 대한 오타로 오답처리될 수 있다.

Stack Overflow
프로그램 실행 중, call stack이 overflow해 프로그램이 강제종료 되는 것.
stackoverflow는 대개 재귀호출의 깊이가 너무 깊어지게될 때 발생한다.

C++의 경우, 지역변수로 선언한 배열이나 클래스인스턴스가 기본적으로 stack memory를 사용하기에 특히나 stackoverflow를 조심해야한다.
따라서, 대부분 heap에 메모리를 할당하는 STL container를 사용하거나 전역변수를 사용한다.

다차원 배열인덱스 순서바꿔쓰기
심심찮게 4, 5차원 이상의 고차원 배열 사용 시, 한두군데 인덱스의 순서를 헷갈려 잘못쓰는 일이 있다.
특히, 이후 다루는 동적 계획법(DP; Dynamic Programming)를 위한 memoization 패턴을 사용 시 이런 일이 잦은데, 가능한 한 특정 배열에 접근하는 위치를 하나로 통일하는 것이 좋다.

잘못된 비교함수의 작성

// a가 b의 진부부분집합이면 true
bool isProperSubset(const IntegerSet& a, const IntegerSet& b);

// a가 b의 진부분집합일 때, a가 항상 앞에 오도록 집합을 정렬
bool operator < (const IntegerSet& a, const IntegerSet& b){
	if (isProperSubset(a,b)) return true;
    if (isProperSubset(b,a)) return false;
    return false;
]​

위의 함수의 경우, 정수의 집합을 저장하는 IntegerSet클래스에 대해 vector<IntegerSet>에 담긴 집합들을 순서대로 처리하기 위한 함수로 operator overloading을 이용해 < 연산자를 오버로딩한다.

위 함수의 경우, 어떤 문제가 있을까?
대부분 사람들은 isProperSubset()의 구현을 찬찬히 살피고 테스트 해볼 것이다.
하지만 아무런 문제가 없다는 것을 알게되면, 어떻게 해결해야할 지 막막해진다.

operator < 의 경우, a<b와 b<a가 모두 거짓이라면, a와 b를 같은 값으로 간주한다.
즉, a,b와 b,c가 같다면 a와 c도 같아야 한다. (상등관계의 전이성)
이 성질을 만족시키지 못하는 것을 알 수 있다.

이를 해결하기 위해 코드를 수정하면 아래와 같다.

bool operator < (const IntegerSet& a, const IntegerSet& b) {
	if (isProperSubset(a,b)) return true;
    if (isProperSubset(b,a)) return false;
    if (a.size() != b.size()) return a.size() < b.size();
    return lexicographical_compare(a.begin(), a.end(),
    							b.begin(), b.end());
}​

위의 코드처럼, 애초에 크기비교 및 사전순 비교만으로 충분한 문제에 복잡한 비교함수사용은 실수를 유발하니 유의하는 것이 좋다.

최대∙최소 예외 잘못 다루기
예외란, 우리가 예상한 입력규칙에 들어맞지 않는 모든 입력이다.
이때, 가능한 입력 중 최소값과 최대값이 예외가 되는 문제들은 생각외로 많다.

ex) 자연수를 입력받아 소수(prime number)인지 판정하는 함수로 예를 들어보자면, 

bool isPrime(int n) {
	if (n%2==0) return false;	// 짝수는 소수가 아님
    for (int i = 2; i < n; i++)
    	if (n%i==0)	return false;	// 2이상, n미만의 약수가 있으면 소수가 아님
    return true;	// 통과 시 소수
}​

오류 1) 모든 짝수를 소수가 아니라고 판단한 것. (반례: 2)

따라서 2를 별도로 처리해야한다.

bool isPrime(int n) {
	if (n == 2) return true;	// 2는 소수임
	if (n%2==0) return false;	// 짝수는 소수가 아님
    for (int i = 2; i < n; i++)
    	if (n%i==0)	return false;	// 2이상, n미만의 약수가 있으면 소수가 아님
    return true;	// 통과 시 소수
}​

아직 오류가 있는 곳이 있을까?
소수인 가장 작은 입력에 대해 확인했으니, 소수가 아닌 가장 작은 입력도 생각해봐야한다.
소수가 아닌 가장 작은 자연수는 1로, for문도 실행되지 않고 건너뛰어 true를 반환해버린다.

따라서 1에 대해서도 별도로 예외처리가 필요하다.
이처럼, 예외는 꼼꼼히 처리하기 쉽지  않다는 것을 알 수 있다.

연산자 우선순위의 오사용
사칙연산은 혼동하는 일이 적다.
하지만, 시프트연산자나 비트단위연산자들의 우선순위는 종종 헷갈리게 된다.

예를 들어보자.

if(b & 1 == 0)​

이 if문은 얼핏 b의 최하 비트가 0일 때 참으로 보인다.
하지만 bit단위 연산자 &의 우선순위는 비교연산자 ==보다 낮다.
따라서 아래처럼 해석된다.

if (b & (1 == 0))​

결과적으로 위의 조건문은 항상 거짓이 된다.
(1 == 0)은 항상 False(즉, 0의 값)를 갖는다.
따라서 헷갈리는 경우, 괄호를 적절히 감싸는 것이 중요하다.

너무 느린 입출력방식
cin 의 사용은 고수준 입력방식을 사용할 수 있어 코드가 간단해진다.
하지만 이에 따른 속도저하 또한 클 수 있다.

따라서 아래와 같은 방법으로 입력을 받기 전에 수행하는 것이 좋다.

cin.sync_with_stdio(false);​

변수 초기화 문제
대부분의 코딩테스트에서 한번에 여러개의 입력에 대해 답을 처리하라 요구한다.
이때, 이전 입력에서 사용한 전역변수값을 초기화하지 않고 그대로 사용하는 것은 문제가 된다.

4. Debugging. &. Testing

Debugging
프로그램을 작성하고 예제입력에 대해 원하는 결과와 다르게 나왔을 때, 보통 Debugger를 활용한다.
Debugger는 물론 유용한 도구지만, 프로그래밍 대회나 테스트에서는 이런 유용성이 제한된다.

따라서 Debugger없이 프로그램의 버그를 찾아내는 연습이 필요하다.
보통 Debugger사용 대신, 아래 단계가 추천된다.

1. 작은 입력에 대해 제대로 실행되나 확인
2. 단정문(assertion) 사용
3. 프로그램의 계산 중간결과를 출력​

Testing
많은 경우, 예제입출력 외에도 몇가지 간단한 입력을 직접 만들어 넣어보면 오답률을 줄일 수 있다.
프로그램 테스트 시, 유용한 기법은 스캐폴딩(scaffolding)이 있다.

스캐폴딩이란, 다른 코드 개발 시, 뼈대를 잡기위해 임시로 사용하는 코드이다.
아래는 정렬함수를 테스트하는 스캐폴딩 코드이다.

void mySort(vector<int>& array);

// 주어진 배열을 문자열로 바꾼다.
string toString(const vector<int>& array);

int main(){
	while(true) {
    	// 임의의 입력 생성
        int n = rand()%100 + 1;
        vector<int> input(n);
        for (int i=0; i<n; i++)
        	input[i] = rand();
            
        // 2개의 복제를 생성
        // 하나는 우리의 정렬함수로, 하나는 STL로 정렬
        vector<int> mySorted = input;
        mySort(mySorted);
        vector<int> ref = input;
        sort(ref.begin(), ref.end());
        
        // 만약 다르면 오류를 내고 종료
        if (mySorted != ref) {
        	cout << "MisMatch!" << endl;
            cout << "Input: " << toString(input) << endl;
            cout << "Expected: " << toString(ref) << endl;
            cout << "Got: " << toString(mySorted) << endl;
            break;
        }
    }
}​

 

작은 입력을 여러개 수행하며 더 빠른 코드의 문제를 찾아내는데 유용하다.

5. 변수범위의 이해

Arithmetic Overflow
컴퓨터의 가장 대표적 제한은 유한성이다. 컴퓨터의 모든 변수에는 답을 담을 수 있는 크기가 제한되어 있다.
이때, 수학적/논리적으로 완전히 정당한 알고리즘도 예상과 다르게 동작가능한데, 이 문제를 일으키는 흔한 원인이 바로 산술 오버플로(arithmetic overflow)다.
산술오버플로는 어떤 식의 계산값이 반환되는 자료형의 표현가능범위를 벗어나는 경우이다.
상당히 많이 저지르는 실수 중 하나인데, 여기에는 크게 2가지 이유가 있다.

1. 대부분의 프로그래밍언어들은 사칙연산과정 중 overflow가 발생해도 별다른 경고가 없다.
(연산이 일어날 때마다 overflow를 확인하는 것은 너무 비효율적이기 때문)

2. 프로그램의 정당성을 검증할 때, 프로그램 논리의 정확성에만 집중하면 산술오버플로 등장사실을 잊기 쉽다.

다만, STL 등의 제공으로 산술오버플로를 신경 쓸 일이 크게 줄어들었지만 이런 클래스들은 훨씬 많은 Cost를 차지한다.

너무 큰 결과
당연하게도 32bits자료형의 범위를 넘어가면 64bits정수나 더 큰 정수구현을 이용해야한다.
이때, 큰 정수를 다룰 때는 항상 변수의 형태에 주의하는 습관을 들여야한다.

너무 큰 중간값
산술오버플로가 문제가 되는 또다른 경우는 무엇일까?
프로그램의 출력값의 범위는 작지만 중간과정에서 큰 값을 일시적으로 계산해야하는 경우이다.

ex)

int gcd(int a, int b);	// 두 수의 최대공약수 반환

int lcm(int a, int b) {
	return (a*b) / gcd(a,b);	
}​

위의 코드로 lcm(50000, 100000)을 계산해보자.
사실 반환값은 간단하게도 100000이며 이는 32bits보다 작은 수이기에 잘 계산될 것 같다.
하지만 위의 코드는 14100을 출력한다.

위의 경우, a×b의 값은 5×10⁹가 된다. 이 값은 signed_int_32bit의 최대치를 가뿐히 넘긴다.
이때, C++은 아무 경고를 하지도 않기에 이런 버그를 찾기는 힘들다.

너무 큰 '무한대'값
프로그램을 작성시, 무한대에 해당하는 큰 값을 이용하는 것이 편리할 때가 존재한다. (최단경로 문제.)

무한대 값을 선택 시, 무한대값들이 서로 더해지거나 곱해지는 경우가 없는지 잘 살펴보고 이럴 때도 overflow가 나지 않을 크기의 값을 선택하는 것이 좋다.

Overflow 심화
그렇다면 overflow발생사실을 알았을 때, 어떻게 코드를 고쳐야할까?
가장 간단한 방법은 "더 큰 자료형"을 사용하는 것이다.

int lcm(int a, int b) {
	return (a * (long long)b) / gcd(a,b);
}​