원형 합성곱

원형 합성곱 또는 원형 컨벌루션(circular convolution) 또는 순환 합성곱(cyclic convolution)은 주기가 같은 두 주기 함수의 합성곱인 주기 합성곱(periodic convolution)의 특수한 경우이다. 주기 합성곱은 예를 들어 이산시간 푸리에 변환(DTFT)의 맥락에서 발생한다. 특히, 두 이산 수열의 곱에 대한 DTFT는 개별 수열의 DTFT들의 주기 합성곱이다. 그리고 각 DTFT는 연속 푸리에 변환 함수의 주기적 합산이다 ( 참조). DTFT는 대개 주파수에 대한 연속 함수이지만, 주기 및 원형 합성곱의 개념은 이산 데이터 수열에도 직접 적용 가능하다. 이러한 맥락에서 원형 합성곱은 특정 종류의 일반적인 필터링 연산의 효율성을 극대화하는 데 중요한 역할을 한다.

 정의 

두 T-주기 함수 와 의 주기 합성곱은 다음과 같이 정의될 수 있다:



여기서 는 임의의 매개변수이다.  일반적인 선형 또는 비주기적 합성곱의 표기법을 사용한 대안적 정의는 와 를 비주기적 성분 와 의 주기적 합산으로 표현함으로써 도출된다:

그러면 다음과 같다:

두 형태 모두 주기 합성곱이라 부를 수 있다. 원형 합성곱이라는 용어는 와 의 0이 아닌 부분을 모두 구간 로 제한하는 중요한 특수 사례에서 유래한다. 이 경우 주기적 합산은 주기적 확장이 되며, 다음과 같이 원형 함수로 표현될 수 있다:

 (모든 실수)

그리고 적분 범위는 함수 의 길이로 줄어든다:

 이산 수열 
마찬가지로 이산 수열과 매개변수 N에 대해, 비주기 함수 와 의 원형 합성곱을 다음과 같이 쓸 수 있다:

이 함수는 N-주기적이다. 이는 최대 N개의 고유한 값을 갖는다. x와 h의 0이 아닌 범위가 모두 ≤ N인 특수한 경우, 이는 적분 변환의 커널이 순환 행렬인 행렬 곱셈으로 축소될 수 있다.

 예시 
섬네일|400px|원형 합성곱은 FFT 알고리즘을 통해 빠르게 수행될 수 있으므로, 선형 합성곱을 효율적으로 계산하기 위해 FIR 필터와 함께 자주 사용된다. 이 그래프들은 그것이 어떻게 가능한지 보여준다. FFT 크기(N)가 더 크면 그래프 #6이 #3과 완전히 일치하지 않게 만드는 중첩 현상을 방지할 수 있다.
실무적으로 매우 흥미로운 사례가 그림에 설명되어 있다. 수열 x의 길이는 N(또는 그 이하)이고, 수열 h의 길이는 그보다 현저히 짧다. 그러면 원형 합성곱의 많은 값들이 x∗h의 값과 동일해지는데, 이는 수열 h가 유한 임펄스 응답(FIR) 필터일 때 실제로 원하는 결과이다. 또한 원형 합성곱은 고속 푸리에 변환(FFT) 알고리즘과 원형 합성곱 정리를 사용하여 매우 효율적으로 계산할 수 있다.

실용적인 N 값보다 더 긴 수열 x를 처리하는 방법도 있다. 수열을 세그먼트(블록)로 나누어 부분적으로 처리한다. 그런 다음 필터링된 세그먼트들을 주의 깊게 다시 이어 붙인다. 입력 블록이나 출력 블록을 중첩시킴으로써 경계 효과를 제거한다. 이러한 방법을 설명하고 비교하기 위해, 길이 201의 수열 h와 FFT 크기 N = 1024를 예로 들어 논의한다.

 입력 블록 중첩 

이 방법은 FFT 크기(1024)와 동일한 블록 크기를 사용한다. 먼저 일반적인 선형 합성곱의 관점에서 설명한다. 각 블록에 대해 일반적인 합성곱이 수행될 때, 필터 지연(200개 샘플)으로 인해 블록 경계에서 시작 및 소멸 과도 현상이 발생한다. 합성곱 출력 중 824개만이 경계 효과의 영향을 받지 않는다. 나머지는 버려지거나 아예 계산되지 않는다. 입력 블록이 연속적이라면 이로 인해 출력에 간격이 생길 것이다. 입력 블록을 200개 샘플만큼 중첩시킴으로써 이러한 간격을 피한다. 어떤 의미에서는 각 입력 블록의 200개 요소를 "저장"하여 다음 블록으로 넘기는 것이다. 이 방법을 중첩 저장법(overlap-save)이라고 한다. 비록 다음에 설명할 방법도 출력 샘플에 대해 유사한 "저장"이 필요하지만 말이다.

FFT를 사용하여 영향을 받지 않는 824개의 DFT 샘플을 계산할 때, 영향을 받는 샘플을 계산하지 않을 선택권은 없지만, 원형 합성곱 때문에 앞부분과 뒷부분의 경계 효과가 중첩되어 더해진다. 결과적으로 1024포인트 역 FFT(IFFT) 출력은 200개의 경계 효과 샘플(버려짐)과 824개의 영향받지 않은 샘플(유지됨)만을 포함하게 된다. 이를 설명하기 위해 오른쪽 그림의 네 번째 프레임은 주기적으로(또는 "원형으로") 확장된 블록을 묘사하며, 다섯 번째 프레임은 전체 수열에 대해 수행된 선형 합성곱의 개별 성분을 묘사한다. 경계 효과는 확장된 블록의 기여분이 원래 블록의 기여분과 겹치는 부분이다. 마지막 프레임은 합성된 출력이며, 녹색으로 칠해진 부분이 영향을 받지 않은 부분을 나타낸다.

 출력 블록 중첩 

이 방법은 중첩 가산법 (overlap-add)으로 알려져 있다. 이 예시에서는 824 크기의 연속된 입력 블록을 사용하고 각 블록에 200개의 0 값을 갖는 샘플을 패딩한다. 그런 다음 1024개 요소의 출력 블록들을 중첩하여 더한다. 아무것도 버려지지 않지만, 다음 블록과의 덧셈을 위해 각 출력 블록의 200개 값을 "저장"해야 한다. 두 방법 모두 1024포인트 IFFT당 824개 샘플만큼만 진행되지만, 중첩 저장법은 초기 제로 패딩과 최종 덧셈 과정을 피할 수 있다.

 같이 보기 
 합성곱 정리
 순환 행렬
 이산 힐베르트 변환

 내용주 

 각주 

 더 읽어보기 

분류:영상 처리
분류:함수해석학
분류:이항연산