728x90 Quality control (Univ. Study)197 Algorithm design - MST 신장 트리신장 트리(spanning tree)는 무향그래프 G=(V,E)에서 V는 그대로 두고 간선을 |V|-1개만 남겨 트리가 되도록 만든 것이다. DFS,BFS에사용된 간선 집합 T는 그래프 G의 신장 트리를 의미한다. 주어진 그래프 G에 대한 신장 트리는 유일하지 않다.MSTMST는 최소 비용 신장 트리(minimum cost spanning tree)의 준말이다. 신장트리가 되는 G의 부분그래프 중에서 가중치가 최소가 되는 부분그래프를 최소비용신장트리(MST, minimum spanning tree)라고 한다. 여기서 최소의 가중치를 가진 부분그래프는 반드시 트리가 되어야 한다. 왜냐하면, 만약 트리가 아니라면, 순환경로(cycle)가 있을 것이고, 그렇게 되면 순환경로 상의 하나의 이음선을 제거.. 2024. 5. 28. Algorithm design - BFS / DFS GraphGraph는 현상이나 사물을 정점(vertex)과 간선(edge)으로 표현한 것이다. Graph G = (V, E)으로 표현이 되고 이때 V는 정점 집합 E는 간선 집합이다. 두 정점이 간선으로 연결되어 있으면 인접하다고 한다. 인접은 adjacent라고 하고 간선은 두 정점의 관계를 나타낸다. 간단한 예시를 통해 다양한 그래프를 살펴보자.인간관계를 그래프로 표현한 그래프다.간선에 weight가 생겨 관계의 깊이를 표현한 그래프다.방향을 고려한 유향 그래프이다.두 요소가 결합된 가중치를 가진 유향 그래프이다. 이러한 그래프 구조를 traversal하는 대표적인 두가지 기법 BFS, DFS를 살펴보자.BFSBFS는 너비 우선 탐색(breadth first search)의 준말이다. 말그대로 한 정.. 2024. 5. 28. Digital Image Processing - SIFT SIFTSIFT는 Scale Invariant Feature Transform의 줄임말이고 SIFT알고리즘의 마지막 부분 구조가 체같이 생겨서 "체로 거르다"라는 뜻을 가진 sift라는 동사도 염두해두고 지은 센스있는 이름이다.David G. Lowe가 1999년 ICCV에서 소개하고 2004년 IJCV에서 확장하였다. SIFT 알고리즘은 feature detection 분야의 2000년대 초반을 섬렵한 기념비적인 알고리즘 이다. SIFT는 local feature를 추출하고 이를 normalized descriptor로 변환하여 Scale invariance를 갖춘 local feature extracting 알고리즘이다.Scale Space Detection아래와 같이 같은 부분인데 scale이 다르.. 2024. 5. 27. 알고리즘 설계 실습 - 최적 경로 찾기 문제n(2 ≤ n ≤ 100)개의 도시가 있습니다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 m(1 ≤ m ≤ 100,000)개의 버스가 있습니다. 각 버스는 한 번 사용할 때 필요한 비용이 있습니다. 모든 도시의 쌍 (A, B)에 대해서 도시 A에서 B로 가는데 필요한 비용의 최솟값을 구하는 프로그램을 작성하세요. 입력첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어집니다. 그리고 셋째 줄 부터 m+2줄까지 다음과 같은 버스의 정보가 주어집니다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어집니다. 버스의 정보는 버스의 시작 도시 a, 도착 도시 b, 한 번 타는데 필요한 비용 c로 이루어져 있습니다. 시작 도시와 도착 도시가 같은 경우는 없습니다. 비용은 100보다.. 2024. 5. 23. Digital Image Processing - Automatic Scale Selection Automatic Scale Selection이전에 다룬 Harris Detector의 문제점을 개선한 Automatic Scale Selection 기법에 대해 알아보자. 이름 그대로 Harris Detector가 Scale invariance가 부족하다는 점을 극복하여 자동으로 Scale에 대한 판단을 해내는 기법이다.위와 같이 이미지가 확대 되었음에도 유사한 feature로 판단해내는 기법이다.Scale에 따라 함수가 반응하는 것이 달라지고 normalization과정을 통해 scale이 조정되어 local feature를 비교하는 것이 쉬워지는 것을 볼 수 있다. 이때 사용하는 signature function으로 Laplacian-of-Gaussian(LoG)가 유용하게 사용된다.아래와 같이 L.. 2024. 5. 23. Algorithm design - TSP(Traveling Salesperson Problem) 오일러오일러(Leonhard Euler, 1707 - 1783)는 일생동안 800편에 육박하는 논문을 냈다고 하는데 그만큼 다양한 주제에 화두를 던진 학자이다. 그가 제시한 유명한 내용중 하나가 오일러 경로와 순회이다.오일러 경로(Euler tour(path)): 어떤 그래프의 모든 간선을 정확하게 한 번씩만 지나가는 경로오일러 순회(Euler cycle(circuit)): 어떤 그래프의 모든 간선을 정확하게 한 번씩만 지나 시작점으로 다시 돌아오는 경로다시 말해 오일러 순회는 시작점과 끝점이 똑같은 오일러 경로이다. 한붓그리기의 대표적인 예시인 쾨니히스베르크 다리 건너기 문제가 유명하다.TSP해밀턴 경로(Hamiltonian Circuit)는 모든 정점을 한 번씩만 방문하고 시작점으로 돌아오는 경로를 .. 2024. 5. 21. Digital Image Processing - Harris Detector Formulation Harris Detector Formulation이전 수업에 이어서 Harris corner detector의 수식에 대해서 자세히 알아보자. 이전 시간에 아래 식들의 첫줄 즉 벡터 변화에 따른 Intensity의 변화 차이의 제곱의 합을 통해 E값을 구하는 것을 살펴봤다. 그에 이어서 아래 식 변환 과정은 1차 테일러 급수를 이용하여 푸른색으로 밑줄친 부분의 식을 붉은 색으로 동그라미 친 식으로 변환하고 추가 계산하는 과정을 통해 최종적으로 사용될 Matrix A를 구하는 과정이다.참고로 테일러 급수는 아래와 같이 f(x)를 n차 미분의 합으로 표현하는 방법이다. 이때 1차 테일러 급수는 아래 식들중 첫번째 형태를 의미한다. 실제로 영상처리 분야에서 35년동안 연구하시면서 2차 이상의 테일러 급수 형태.. 2024. 5. 20. Digital Image Processing - Local Feature Local featureLocal feature와 Global feature를 비교하면 위와 같다. Global feature는 전체 Histogram을 비교하여 비슷한지 평가할때 쓰일 수 있다. 앞에서 texture에 대해서 배울때 나왔던 개념인 Gradient orientation의 Histogram을 뜻하는 HoG가 유용하게 쓰인다. 반면 위 사진에서 볼 수 있듯이 local feature는 부분 부분을 비교하고 평가하는 것이다.부분부분을 뽑아내서 비교하는 모습이다. 이렇게 뽑아낸 부분부분을 patch라고 부른다. 이때 첫번째 patch는 하늘의 어느곳을 잡아도 비슷하므로 local feature를 잡아냈다고 하기 어려울 것이다. 반면 세번째 patch는 조금만 이동해도 완전히 달라지는 부분이므로 .. 2024. 5. 19. Digital Image Processing - Texture TextureTexture(질감)은 "Regular or stochastic patterns caused by bumps, grooves, and/or markings"로 정의될 수 있다.Texture는 기본적으로 공간적으로 반복되는 pattern을 의미하는 것인데 위 그림들과 같이 자연의 texture는 좀더 stochastic하고 인간이 만들어낸 이미지나 물체는 비교적 regular하다. Stochastic하다는 것이 완전히 불규칙하다는 것이 아니라 확률적으로 pattern이 존재한다는 것이다. 예를들면 물은 불규칙하게 보이지만 그래픽 관련 프로그램에서 물리적인 water texture 패턴이 존재하듯이 이 부분이 물이구나를 알 수 있는 확률적 패턴이 존재한다. 반면 regular하다는 것은 좀더 명.. 2024. 5. 16. 이전 1 2 3 4 5 6 7 ··· 22 다음 728x90
