728x90 전체 글423 Algorithm design - Knapsack Knapsack Problem냅색 문제는 해당 문제를 풀기 위한 알고리즘인 냅색 알고리즘과 함께 굉장히 유명하다. 아래 그림과 같이 가방에 넣을 수 있는 무게가 정해져 있고, 각각 무게와 가치가 정해져있는 물건을 가장 최대 가치로 가방에 조합해서 넣는 최상의 조합을 찾는 알고리즘이다.Knapsack Problem은 물건을 쪼갤 수 있는 Fraction Knaspack Problem과 물건을 쪼갤 수 없는 0-1 KnapSack Problem으로 나뉜다. 이중 0-1 KnapSack Problem을 살펴보려한다.0-1 Knapsack Problem가장 기본적으로 생각해볼 수 있는 것은 모든 조합을 고려해보는 것이다. 그러나 크기가 n인 부분집합의 수는 2^n이다.이번엔 greedy한 기법을 생각해보면 가장.. 2024. 5. 24. 알고리즘 설계 실습 - 최적 경로 찾기 문제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. 프로그래머스 - 연속된 부분 수열의 합 문제비내림차순으로 정렬된 수열이 주어질 때, 다음 조건을 만족하는 부분 수열을 찾으려고 합니다.기존 수열에서 임의의 두 인덱스의 원소와 그 사이의 원소를 모두 포함하는 부분 수열이어야 합니다.부분 수열의 합은 k입니다.합이 k인 부분 수열이 여러 개인 경우 길이가 짧은 수열을 찾습니다.길이가 짧은 수열이 여러 개인 경우 앞쪽(시작 인덱스가 작은)에 나오는 수열을 찾습니다.수열을 나타내는 정수 배열 sequence와 부분 수열의 합을 나타내는 정수 k가 매개변수로 주어질 때, 위 조건을 만족하는 부분 수열의 시작 인덱스와 마지막 인덱스를 배열에 담아 return 하는 solution 함수를 완성해주세요. 이때 수열의 인덱스는 0부터 시작합니다. 입출력 예시입출력 예 #1[1, 2, 3, 4, 5]에서 합이.. 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. [논문 리뷰] Adding Conditional Control to Text-to-Image Diffusion Models(ControlNet) Introduction이 논문은 흔히 ControlNet이라고 불리고 제목 그대로 추가적인 input condition을 지원하여 large diffusion model를 제어하기 위한 모델이다. ControlNet은 end-to-end 방식으로 학습하며, 학습 데이터 세트가 적은(저자는 기존 large text-to-image 모델의 prompt에 대한 의존성과 특정 task에서 활용함에 있어서 발생할 수 있는 현실적인 문제를 언급했다. 이와 관련해서 세 가지 측면에서 검토하고 제안했다. 1. task-specific domain의 경우 일반적인 text-to-image 데이터 스케일만큼 크지 않으므로 large model을 특정 문제에 대해 학습시킬 때는 과적합을 방지하고 일반화 능력을 보존할 수 .. 2024. 5. 17. 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. DIP 실습 - Mean-shift / GrabCut 풀이 코드#include#include#include "opencv2/core/core.hpp"#include "opencv2/highgui/highgui.hpp"#include "opencv2/imgproc/imgproc.hpp"#include using namespace cv;using namespace std;#include void exCvMeanShift() { Mat img = imread("fruits.png"); if (img.empty()) exit(-1); cout img_split; // 채널별로 분할되는 Mat MeanShift(float, float, float, float, int); // Bandwidth 설정을 위한 생성자 void doFilter.. 2024. 5. 16. 알고리즘 설계 실습 - 연쇄 행렬 곱셈 문제i × j 행렬과 j × k행렬을 곱하기 위해서는 i × j × k번 만큼의 곱셈이 필요합니다. 연쇄적으로 행렬 을 곱할 때, 어떤 행렬 곱셈을 먼저 수행하는지에 따라서 필요한 곱셈의 횟수는 달라지게 됩니다.예를 들어, 크기가 1×9인 행렬 A, 크기가 9×9인 행렬 B, 크기가 9×3인 행렬 C가 주어졌을 때 행 렬의 곱 ABC를 구하는 경우, 다음과 같이 여러 방법이 존재합니다. AB를 먼저 곱하고 C를 곱하는 경우 (AB)C에 필요한 곱셈 연산의 수는 1×9×9 + 1×9×3 = 81 + 27 = 108번입니다.BC를 먼저 곱하고 A를 곱하는 경우 A(BC)에 필요한 곱셈 연산의 수는 9×9×3 + 1×9×3 = 243 + 27 = 270번입니다. 행렬 N개의 크기가 주어졌을 때, 모든 행렬을 .. 2024. 5. 16. Digital Image Processing - MRF / Graph Cuts Spatial similarity검은 배경에 흰색 디스크가 있는 이미지를 각 픽셀의 색을 확률에 따라 독립적으로 칠하면 아래와 같이 noise가 굉장히 많이 나타난다. 이러한 결과는 이미지는 공간적인 관점에서 연속적이라는 사실을 반영하지 않았기 때문이다.이러한 문제를 해결하기 위해 인접한 픽셀과의 관계를 반영한 아래의 식을 이용하면 픽셀의 label을 더욱 잘 예상할 수 있다.Individual predictions 부분을 보면 말 그대로 각 픽셀 단위의 연산이다. yi는 0(background) 또는 1(foreground)로 labeling되는 픽셀 값이고 theta는 알고리즘의 매개변수, data는 raw image 자체이다.Pairwise predictions 부분은 yi(해당 픽셀), yj(인접.. 2024. 5. 15. 이전 1 2 3 4 5 6 7 8 ··· 36 다음 728x90
