테트리스 (Tetris)

개발한 것들 2020. 10. 18. 21:25

아이들에게 주려고 만든 프로그램입니다. 아빠가 만들었다고 하면 조금 느낌이 다르지 않을까 해서.. ^^

 

색상이랑 화면 구성 등 아이들에게 의견을 물어가면서 재미있게 만들었습니다.

세로줄을 넣는 것은 아내의 아이디어입니다.

 

윈도우(windows) 프로그램이고 실행파일 하나로 동작합니다.

 

WuKaTetris

실행파일 다운로드: Tetris.zip

 

컨트롤

  Left/Right/A/D: 좌우 이동

  Up/W/X: 시계방향 회전 (CW)

  Z/Ctrl: 반시계방향 회전 (CCW)

  Space: 아래로 떨어뜨리기 (hard drop)

  Down/S: 한칸 아래로 이동 (soft drop)

 

 'n': 새로운 게임(new game)

 'p': 게임 일시멈춤(pause)

 'm': 효과음 온/오프

 

by 다크 프로그래머

벡터 외적을 이용한 직선의 교점 구하기

수학 이야기 2020. 9. 10. 09:31

이미지 평면위의 네 점(픽셀) p1, p2, p3, p4가 주어졌을 때, 두 직선 p1p2, p3p4의 교점을 벡터의 외적(cross product)를 이용하여 구하는 방법입니다.

 

[두 직선의 교점 구하기]

먼저, 네 점의 픽셀 좌표를 homogeneous 좌표로 변환하고 3D 벡터로 해석한다 (카메라 원점과 이미지 평면위의 점을 잊는 벡터).

직선1: $p_1 = (x_1, y_1, 1)$, $p_2 = (x_2, y_2, 1)$

직선2: $p_3 = (x_3, y_3, 1)$, $p_4 = (x_4, y_4, 1)$

 

벡터의 외적을 이용하여 $v$를 계산

$v = (p_1 \times p_2) \times (p_3 \times p_4)$

 

계산된 결과가 $v = (x, y, w)$라면 두 직선의 교점의 좌표는 $(x/w, y/w)$로 주어진다.

 

[원리]

네 점 p1, p2, p3, p4를 3D 좌표계(카메라 좌표계)에서 이미지 평면 위에 있는 점으로 생각하자. 그리고 이 점들은 3차원 공간에서 카메라 원점(C)으로부터의 3D 벡터들로 해석할 수 있다. 이 때, 카메라 원점 C와 점 p1, p2를 지나는 평면을 생각하면 두 벡터 $p_1$, $p_2$의 외적 $n_1 = p_1 \times p_2$는 이 평면의 normal 벡터이다. 마찬가지로, $n_2 = p_3 \times p_4$은 C와 p3, p4를 지나는 평면에 수직인 벡터이다. 이 때, 두 평면의 교선을 $v$라 하면 $v$는 카메라 원점 C를 지나면서 두 직선 p1p2, p3p4의 교점을 지난다. 교선 $v$는 두 평면 위에 있으므로 $n_1$과도 수직이고 $n_2$와도 수직이다 (평면 위에 모든 벡터는 그 평면의 normal 벡터와 수직이다). 즉, $v = n_1 \times n_2$ (homogeneous 좌표에서 scale은 무시).

 

[여러 직선의 교점 구하기]

이미지 평면에 존재하는 여러 line segment들의 최소자승(least squares) 교점을 구하는 문제를 생각해 보자. Line segment l1, l2, ...로부터 구한 normal 벡터(line segment의 양 끝점과 카메라 원점을 지나는 평면의 normal 벡터)들을 n1, n2, ...라 하자. 최소좌승 교점을 v라 하면, v는 모든 normal 벡터들과 수직인 벡터이다.

$$v = \arg \min_v \sum_{i=1}^{n}{( n_i^T v)^2 }$$

그리고, 이러한 v는 ni들을 행벡터로 갖는 행렬 A에 대해 Av = 0의 해를 구함으로써 구할 수 있다.

 

☞ 관련 원리는 벡터의 외적 및 homogeneous 좌표에 대한 이해가 필요하며, [영상처리] - [영상 Geometry #2] Homogeneous Coordinates 글 참조하기 바랍니다.

 

by 다크 프로그래머

'수학 이야기' 카테고리의 다른 글

상관계수와 cross correlation  (6) 2021.09.12
구구단 암산법  (4) 2018.10.08
아이와 수학 공부하기  (5) 2017.11.15

YOLO와 성능지표(mAP, AP50)

기계학습 2020. 9. 7. 12:23

최근에 YOLO 논문들을 보다 보니 저자가 2018년 YOLOv3를 마지막으로 YOLO 연구를 중단한 것을 알게 되었다.

 

☞ 그리고 올해 2020년 2월 자신의 twitter를 통해 컴퓨터비전 연구를 중단한다고 선언한다.

 

YOLOv3 논문에 보면 자신도 Google이나 군에서 fund를 지원받아서 이런 연구를 하고 있는데.. 이게 어디에 쓰일지(프라이버시 정보 수집, 군사목적 등) 뻔하기 때문에 더 이상 그런 곳에 기여할 수는 없다는 게 이유이다.

 

그리고 논문 말미 Rebuttal을 통해 현재 비전계의 mAP 평가방식(MS COCO)에 대해 강도 높은 비판을 하면서 이 연구계를 떠난다.

 

Detector의 성능을 COCO 데이터셋에 대해 평가했을 때,

  • MS COCO mAP 기준으로 YOLOv3는 33.0 ≪ RetinaNet은 40.8
  • Pascal VOC mAP (AP50) 기준으로 YOLOv3는 57.0 ≒ RetinaNet 61.1 (속도는 YOLOv3가 4배 빠름)

 

똑같은 mAP 인데 왜 이렇게 차이가 나는 걸까?

 

 과거 Pascal VOC 기준으로는 YOLO가 단연 최고의 detector인데, 최근 논문들이 사용하는 COCO 챌린지 기준으로는 속도만 빠른 detector로 전락해 버린다.

 

도대체 뭐가 다른지.. 이번 기회에 mAP 계산 방식에 대해 살펴봤는데 이게 여간 복잡하지 않다.

- Evaluation metrics for object detection and segmentation: mAP

 

Pretty soon you will be pulling your hair out and ask yourself what the **** is all this. “I have an algorithm, and I have my dataset. All I want to do is to evaluate it. Why is it so hard?” 라면서 욕을 바가지로 한 사람도 있다. (공감..)

 

Pascal VOC는 IoU(Intersection over Union) > 0.5 인 detection은 true, 그 이하는 false로 평가하는 방식이고 COCO는 IoU>0.5, IoU>0.55, IoU>0.6, …, IoU>0.95 각각을 기준으로 AP를 계산한 후 이들의 평균을 취하는 방식이다.

 

COCO 방식은 기존 Pascal VOC 방식이 정확도가 높은 (ground truth와 일치하는 box를 검출하는) detector들을 구분하지 못하는 단점을 보완하기 위해서 도입한 것이라고 한다. 나름 일리가 있다.

 

그런데, yolo 저자는 이에 대해 다음과 같이 반박한다.

  1. ground truth는 사람이 만든 것으로서 오차가 있을 수 있으며 그러한 오차를 감안하여 Pascal VOC에서는 IoU 0.5라는 기준을 적용하였다. (사실, 무엇이 정답인지에 대한 기준 자체도 모호하다. 예를 들어 팔을 벌리고 있는 사람의 가장 이상적인 bounding box는 어디인가? 저자는 box를 사용하면서 정확도를 평가한다는 것 자체가 멍청한 짓이라고 말한다)
  2. IoU 기준을 높이다 보면 상대적으로 classification 정확도는 무시되게 된다. box의 위치 정확도가 물체의 클래스 인식율보다 중요한 것인가? (예를 들어 IoU>0.7 기준을 사용하면, 그 이하의 검출은 물체를 사람으로 인식했는지 자동차로 인식했는지 여부와 무관하게 모두 false로 간주된다)
  3. 물체 class별로 각각 AP를 계산하는 방식도 문제이다. 사람 class의 경우, 현재의 평가방식은 detector의 출력들 중 사람에 대한 출력값만 가지고 precision, recall을 계산한다. 그래서, detector가 실제 사람을 치타라고 분류하거나 강아지라고 분류하더라도 이것들은 성능 평가에 아무런 영향을 미치지 않는다. 지금처럼 개별 class별로 AP를 계산한 후 평균하는 방식이 아니라 모든 class를 한꺼번에 놓고 평가하는 방식으로 바꿔야 한다. (이건 조금 이해하기 힘들 수 있는데, multi-class classification 문제에서는 class 개수만큼 ouput 노드를 만들고 그중 가장 출력이 큰 값을 해당 객체의 class로 분류한다. 그런데, 해당 classifier로 사람만 평가한다고 하면 사람 노드의 출력값만 이용해서 출력값>threshold인 경우에 대해 precision-recall 그래프를 그리게 되고, 다른 class 노드에서 사람 노드보다 더 높은 출력값이 나오더라도 이 값은 무시되게 된다)

 

개인적으로는 yolo 저자의 주장에 대부분 공감이 간다. IoU>0.5라는 기준이 사실 그렇게 낮은 기준이 아니다. 크기가 동일한 box라 하더라도 ground truth와 66.7% 이상 overlap이 되어야 IoU = 0.5가 나오고 사람의 눈으로 봤을 땐 대부분 잘 찾았네 하고 느껴지는 수준이다.

 

COCO 기준이 IoU>0.5 AP와 IoU>0.75 AP의 평균을 사용한다면 어느정도 수긍할 수 있다. 그런데, IoU>0.95까지 동일한 weight로 평균한 것은 수긍이 어렵다. 

 

기준이 어찌되었든 모든 detector들에게 동일하게 적용되는 것이니 공평한 것 아니냐 할 수도 있다. 하지만, COCO 방식이 찾은 물체의 사람/자동차/물건 구분은 종종 틀리더라도 COCO가 정한 ground truth 박스와 최대한 일치하게 물체의 bounding box를 찾아주는 detector들에게 유리한 방식임은 틀림없다.

 

그런데, Joseph Redmon이 yolo를 중단한 후, 그동안 yolo에 대한 다양한 플랫폼 빌드(github.com/AlexeyAB/darknet)를 제공하던 Alexey Bochkovskiy이 대대적인 optimization을 통해 올해 2020년 4월에 YOLOv4를 release한다. 그리고 YOLOv4는 MS COCO 지표로 mAP 43.5% (Pascal VOC mAP로는 65.7%), 속도 65 fps를 발표한다.

 

by 다크 프로그래머

'기계학습' 카테고리의 다른 글

딥러닝과 Loss 함수의 이해  (9) 2021.09.15
YOLO 윈도우즈(windows) 버전  (64) 2017.09.01
최적화 기법의 직관적 이해  (122) 2015.06.02