![]()
P vs. NP vs. NP-hard vs. NP-complete P 다항시간 내에 풀 수 있는 문제 또는 다차시간 알고리즘을 찾은 문제 NP 다항시간 내에 답이 맞았는지 틀렸는지 확인해줄 수 있는 문제 (verification) 또는 다루기 힘들다고 증명되지 않았고, 다차시간 알고리즘도 찾지 못한 문제 NP-hard 아무리 답을 추측해도 그 답이 맞았는지 틀렸는지 확인이 어려운 문제 (예 : 최적화 문제) NP-complete NP-hard임과 동시에 NP인 문제, 즉 모든 NP 문제를 Polynomial-Time Reduction (다항식 시간 변환)시킨 문제가 다시 NP가 될 때, 그 문제를 'NP-complete 문제'라고 부른다. NP-hard NP-hard에 속하는 문제는? 모든 NP-comp..
![]()
이전 글 : [알고리즘] 시간복잡도와 Master Theorem [알고리즘] 시간복잡도와 Master Theorem Master Theorem $T(n) = a \cdot T(\frac{n}{b}) + f(n)$와 같은 모양을 가진 점화식은 마스터 정리에 의해 바로 분석할 수 있다 $T(n) = a \cdot T(\frac{n}{b}) + f(n)$ $h_n = n^{log_b a}$ $f(n)$과 $h(n)$ 비교 if $f(n) < h(n)$, then $ oneonlee.tistory.com 시간복잡도와 Master Theorem - 연습문제 출처: “Algorithms,” Sanjoy Dasgupta, Christos Papadimitriou, Umesh Vazirani, McGraw-Hill, ..
![]()
Master Theorem $T(n) = a \cdot T(\frac{n}{b}) + f(n)$와 같은 모양을 가진 점화식은 마스터 정리에 의해 바로 분석할 수 있다 $T(n) = a \cdot T(\frac{n}{b}) + f(n)$ $h_n = n^{log_b a}$ $f(n)$과 $h(n)$ 비교 if $f(n) h(n)$, then $O(T(n)) = f(n)$ 제약 조건 $f(n)$은 asymptotically positive function (양의 함수) 이어야 한다. $a \geq 1$ and $b > 1$이어야 한다. th..
Template Matching: 유사도 측정 (1) Correlation (2) Zero-mean correlation (3) SSD; Sum of square difference (4) NCC; Normalized cross correlation (1) Correlation 템플릿 자체를 필터로 사용하는 Correlation 방식은 문제가 있다. Correlation의 결과값은 필터와 영상의 곱으로 이뤄지는데, 영상 자체의 값이 크다면, 결과값도 함께 커지게 된다. (2) Zero-mean correlation Correlation 방식을 보완하기 위해, 원본 영상에서 원본 영상의 평균값을 뺀 영상을 사용한다. 여전히 False Detections가 나타날 수 있다. (3) SSD; Sum of sq..
더 많은 설명들과 실습 자료들은 GitHub을 방문해주세요. https://github.com/oneonlee/digital-image-processing/ GitHub - oneonlee/digital-image-processing: Digital Image Processing Digital Image Processing. Contribute to oneonlee/digital-image-processing development by creating an account on GitHub. github.com Filtering in Spatial Domain Linear Filters Gaussian Filter Non-Linear Filters Sobel Filter Median Filter Bilat..
![]()
더 많은 설명들과 실습 자료들은 GitHub을 방문해주세요. https://github.com/oneonlee/digital-image-processing/ GitHub - oneonlee/digital-image-processing: Digital Image Processing Digital Image Processing. Contribute to oneonlee/digital-image-processing development by creating an account on GitHub. github.com Filtering in Spatial Domain Linear Filters Gaussian Filter Non-Linear Filters Sobel Filter Median Filter Bilat..
![]()
DSLR (Digital Single Lens Reflex) Camera with Lenses 공식 : : 렌즈에서 물체까지 거리 : 상이 맺히는 거리 조리개 (Aperture) 공식 조리개의 지름 = (초점거리 f) / (조리개 값 F) 주의 ⚠️ 조리개 값 (대문자 F) ≠ 초점거리 (소문자 f) 조리개 값 (F) ≠ 조리개의 지름 조리개 값 (F) ↓ → 조리개의 지름 ↑ → 조리개의 크기 ↑ → 조리개를 통과하는 빛의 양 ↑ → 노출의 양 ↑ → 사진의 밝기 ↑ 조리개 값 (F) ↓ → 조리개의 크기 ↑ → 초점거리 (f) 짧아짐 ↓ → 심도가 얕아짐 → 화각이 넓어짐 셔터 스피드 (Shutter Speed) 셔터 스피드 ↓ → 빛의 양 ↑ → 역동적인 사진 (흔들림) 셔터 스피드 ↑ → 빛의 양..
![]()
참고 https://oneonlee.tistory.com/128 [영상처리] 인간의 눈의 구조, 원추세포와 간상세포 인간의 눈의 구조 각막 : 안구를 보호. 광선의 초기 초점 형성. 홍채 : 들어오는 빛의 양 조절. 수정체 (Flexible lens) : 상을 망막에 맺게 하는 볼록 렌즈 역할. 모양체 (Ciliary body) : 수정체 주위의 근 oneonlee.tistory.com Brightness Adaptation 사람의 눈은 밝기의 변화를 동시에 인지할 수 없고, 순차적으로 적응한다. 실제 실험에 의해 검증된 인간의 시각 시스템에 의해 인지된 밝기, 일명 주관적 밝기(subjective brightness)는 로그 함수로 나타낼 수 있다. 아래 그림은 이에 대한 결과 그래프이며 빛의 실제 세..
![]()
인간의 눈의 구조 각막 : 안구를 보호. 광선의 초기 초점 형성. 홍채 : 들어오는 빛의 양 조절. 수정체 (Flexible lens) : 상을 망막에 맺게 하는 볼록 렌즈 역할. 모양체 (Ciliary body) : 수정체 주위의 근육 조직이며, 수정체의 두께를 수정하는 역할. 모양체가 퇴화되면 근시와 원시가 발생할 수 있음. 망막 (Retina) : 영상을 감지하는 기관이며, 망막의 상이 맺히면 사물을 볼 수 있음. 원추세포(Cones)와 간상세포(Rods)라는 시세포가 분포. 원추세포 (Cone cell) : 세 종류의 시색소가 색에 따라 서로 다르게 반응. 간상세포 (Rod cell) : 빛의 밝기에 민감하지만 색을 잘 구분 못함. 중심와 (Fovea) : 0°, 원추세포(Cones)가 몰려있고,..
![]()
Image Digitization : Sampling & Quantization 샘플링(Sampling) Continuous한 데이터들 가운데 적당히 유한한 개수의 데이터를 뽑아내면서, 전체의 패턴을 추정하기 위한 데이터 수집 행위 해상도와 관련있는 개념이며, 연속적인 신호에서 일정한 간격으로 샘플을 추출하여 pixel 단위로 나누는 과정이다. 샘플링은 이미지의 해상도를 줄이거나, 이미지에서 필요한 정보를 추출하는 등의 용도로 사용된다. e.g., 영상에서 일정한 간격으로 픽셀을 추출 양자화(Quantization) 아날로그 형태로 Sampling한 데이터(신호)를 디지털화하는 작업 bit 수와 관련있는 개념이며, 연속적인 신호를 분할하여 이산적인 값을 가지도록하는 과정이다. e.g., 이미지에서 픽셀의..
![]()
Graph Traversal (그래프 순회) 대표적인 두 가지 방법 DFS (Depth-First Search) BFS (Breadth-First Search) 동일한 Tree를 각각 DFS/BFS로 방문하기 DFS : 깊이 먼저, 스택 (Stack) 자료구조 활용 BFS : 너비 먼저, 큐 (Queue) 자료구조 활용 깊이 우선 탐색 (Depth-First Search; DFS) (1) 정점 i를 방문한다. (2) 정점 i에 인접한 정점 중에서 아직 방문하지 않은 정점이 있으면, 이 정점들을 모두 스택에 저장한다. (3) 스택에서 정점을 삭제하여 새로운 i를 설정하고, 단계 (1)을 수행한다. (4) 스택이 공백이 되면 연산을 종료한다. DFS(s) { // s 는 시작 정점 for (i←0; i
![]()
Pipelined Protocols 앞서 서술하였듯이, RDT 2.1 모델부터는 송신자가 하나의 packet을 보내고나면 수신자의 응답을 기다리는 "Stop and Wait" 방식을 사용한다고 하였다. https://oneonlee.tistory.com/m/111 [네트워크] Reliable Data Transfer의 원리와 RDT 모델 알고리즘 Principles of RDT(Reliable Data Transfer) Reliable Data Transfer 신뢰성 있는 데이터 교환(이하 RDT)은 한마디로 "송/수신하는 데이터가 오류없이 온전히 전송되는 것" 이다. Transport Layer 에서는 신뢰성 있는 데이 oneonlee.tistory.com 하지만 이 방법은 ACK가 올 때까지 송신자가..
![]()
Principles of RDT(Reliable Data Transfer) Reliable Data Transfer 신뢰성 있는 데이터 교환(이하 RDT)은 한마디로 "송/수신하는 데이터가 오류없이 온전히 전송되는 것" 이다. Transport Layer 에서는 신뢰성 있는 데이터 교환을 하고 싶어하지만, 그 아래의 레이어에서는 신뢰성을 보장할 수 없기 때문에 신뢰성 있는 통신에 문제가 생길 수 있다. 이러한 상황 속에서 Transport Layer에서 적용 가능한 방식이 바로 "RDT 프로토콜"을 이용하는 것이다. 아래 그림을 살펴보자. 패킷 송신 (상위 계층 → Transport Layer → 하위 계층) 상위 계층 → Transport Layer : rdt_send() 시스템 콜을 호출하여 RDT ..
![]()
Transport Layer services Transport Layer의 역할 Source부터 Destination까지 패킷이 제대로 전송될 수 있도록 한다. Application Layer에서 만든 데이터를 일정한 크기로 자른다. Transport Layer 프로토콜의 종류 세부적으로 들어가면 Transport Layer에도 여러가지 프로토콜들이 존재하지만, 대표적으로 두가지 프로토콜이 있다. TCP (Transmission Control Protocol) for loss-sensitive application reliable transport 전송 프로세스와 수신 프로세스 간의 안정적인 전송이 가능하다. in-order delivery 데이터를 순서대로 전송한다. connection-oriented..
![]()
P2P applications Pure P2P architecture에 관한 내용은 이 곳을 참고해주세요. [네트워크 애플리케이션 구조] client-server, P2P Network Application architectures client-server peer-to-peer (P2P) Client-server architecture 유저의 시스템(client)이 내놓은 요구를 시스템(server)이 처리하도록 한 네트워크 구성 서버: 항상 켜져 있는 호스트이다. 영 oneonlee.tistory.com 이 글은 전편에 이어지는 글입니다. P2P application의 초창기 모델인 "Napster"와 "Gnutella"에 대한 설명은 여기를 참조해주세요. [네트워크] P2P applications ..
