다차원 이산 콘볼루션

신호 처리에서 다차원 이산형 콘볼루션은 n-차원에서도 제3의 함수를 생성하는 n차원 격자에서 f와 g의 두 함수 사이의 수학적 연산을 말한다.다차원 이산형 콘볼루션은 유클리드 공간의 함수 다차원 콘볼루션의 이산형 아날로그다.또한 집단이 정수의 n-tules 그룹일 때 집단에 대한 convolution의 특별한 경우다.

정의

문제성명 및 기본사항

1차원 사례와 유사하게, 별표는 콘볼루션 작동을 나타내기 위해 사용된다.주어진 작업에서 치수의 수는 별표 수에 반영된다.예를 들어, M-차원 콘볼루션은 M 별표를 사용하여 작성될 것이다.다음은 이산 신호의 M차원 경련을 나타낸다.

${\displaystyle y(n_{1},n_{2},...,n_{M}=x(n_{1},n_{2}, ...,n_{M})*{\overset {M}{{M}}}**h(n_{1},n_{2},n_{M})}$

이산값 신호의 경우, 이 콘볼루션은 다음을 통해 직접 계산할 수 있다.

${\displaystyle \sum \sum _{k_{1}=-\infit }^{\infit }^{k_{2}=-\infit }}...\sum _{k_{M}=-\infit }^{}^{\h(k_{1}{1}k_{2}, k_{M}x(n_{1}-k_{1}, n_{2}-k_{M}}}}}}}}$

이산 다차원 컨볼루션의 지원 결과 출력 영역은 두 입력 신호의 지원 크기와 영역에 기초하여 결정된다.

2차원 콘볼루션 운영자의 몇 가지 특성이 열거되어 있다.이러한 신호는 $N{\displaystyle }$ ${\displaystyle$ N} -dimension$$ 신호에도 확장될 수 있다는 점에 유의하십시오.

상호 교환 특성:

${\displaystyle x**h=h*x}$

속성 연결:

${\displaystyle (x**h)***g=x***(h*g)}$

분배 속성:

${\displaystyle x******(h+g)=(x*h)+(x**g)}$

이러한 특성은 아래 그림에서 사용 중인 것으로 보인다.Given some input ${\displaystyle x(n_{1},n_{2})}$ that goes into a filter with impulse response ${\displaystyle h(n_{1},n_{2})}$ and then another filter with impulse response ${\displaystyle g(n_{1},n_{2})}$, the output is given by ${\displaystyle y(n_1,n_2)}$${\displaystyle y(n_{1},n_{2$ $첫{\displaystyle }$ 번째 필터의 출력이 w${\displaystyle }$(${\displaystyle {n\mathrm{}}_{}}$ 1,${\displaystyle {}_{}}$n ${\displaystyle {2\mathrm{}}_{}}$) ${\displaystyle w(n_{1},n_{2}})$에 의해 주어진다고 가정하면 다음과 같다$.$

$w=x**h}$

또한, 그 중간 기능은 두 번째 필터의 임펄스 반응과 함께 해결되며, 따라서 출력은 다음과 같이 나타낼 수 있다.

${\displaystyle y=w**g=(x**h)*g}$

연관 특성을 이용하여 다음과 같이 다시 쓸 수 있다.

${\displaystyle y=x***(h*g)}$

계단식 시스템에 대한 등가 임펄스 응답은 다음과 같은 방법으로 제공된다.

${\displaystyle h_{eq}=h**g}$

유사한 분석을 아래 그림의 병렬 시스템 집합에서도 수행할 수 있다.

이 경우 다음과 같은 것이 분명하다.

${\displaystyle y=(x*h)+(x*g)}$

분배법을 사용하여 다음과 같은 것을 증명한다.

${\displaystyle y=x***(h+g)}$

즉, 병렬 시스템의 경우 등가 임펄스 반응이 다음과 같은 방법으로 제공됨을 의미한다.

${\displaystyle h_{eq}=h+g}$

계단식 시스템과 병렬 시스템 모두에서 등가 임펄스 반응은 $N{\displaystyle }$ ${\displaystyle N}$ - 필터 수가$$ 있는 시스템으로 일반화할 수 있다.^[1]

동기 부여 및 적용

한 차원에서의 콘볼루션은 필터 시스템의 임펄스 반응이 알려진 한 선형 시프트 인바리어트(LSI) 시스템의 입력과 출력을 쉽게 비교할 수 있게 해주는 강력한 발견이었다(LTI 시스템 이론 참조).이 개념은 다차원 필터의 충동 반응을 단순히 아는 것만으로도 시스템의 입력과 출력 사이에 직접적인 비교가 이루어질 수 있기 때문에 다차원적 경련에도 영향을 미친다.오늘날 디지털 세계에서 전송되는 여러 신호는 이미지와 비디오를 포함한 다차원이기 때문에 이것은 심오하다.1차원 콘볼루션과 유사하게, 다차원 콘볼루션은 주어진 입력 신호에 대한 LSI 시스템의 출력을 계산할 수 있다.

예를 들어 일부 무선 네트워크를 통해 전송되는 이미지를 전기 광학 노이즈의 영향을 받는다고 가정해 보십시오.가능한 소음원에는 채널 전송 오류, 아날로그-디지털 변환기 및 이미지 센서 등이 포함된다.보통 채널이나 센서에 의해 발생하는 노이즈는 공간적으로 독립된 고주파 신호 성분을 생성하여 실제 영상에 임의의 빛과 어두운 점으로 해석된다.고주파 스펙트럼 함량의 영상 데이터를 제거하기 위해서는 콘볼루션 정리에 근거한 저역-통과 필터의 주파수 응답에 곱하면 되는데, 저역-통과 필터의 임펄스 응답에 의해 시간/공간 영역의 신호를 경련하는 것과 동등하다.그렇게 하는 몇 가지 충동 반응이 아래에 나와 있다.^[2]

스펙트럼의 내용물을 걸러내는 것 외에도 다차원적 경련은 에지 검출과 평활화를 구현할 수 있다.이것은 다시 한번 입력 이미지와 함께 경련하는 데 사용되는 충동 반응의 값에 전적으로 의존한다.가장자리 감지를 위한 일반적인 충격 반응은 아래에 설명되어 있다.

이미지 처리 외에도, 다차원적 경련이 구현되어 다양한 다른 애플리케이션이 가능하게 할 수 있다.필터는 디지털 통신 시스템에 널리 보급되어 있기 때문에 다차원 데이터를 전송해야 하는 모든 시스템은 필터링 기법에 의해 보조된다. 실시간 비디오 처리, 신경 네트워크 분석, 디지털 지구 물리 데이터 분석 등에 사용된다.^[3]

이미지 및 비디오 캡처 또는 전송 응용 중에 발생하는 대표적인 왜곡은 저역 통과 필터링 프로세스에 의해 야기되는 흐릿하다.도입된 블러어는 가우스 로우패스 필터링을 사용하여 모델링할 수 있다.

분리 가능한 신호를 이용한 행-기둥 분해

분리 가능한 신호

신호는 복수의 1차원 신호의 산물로 쓸 수 있으면 분리가 가능하다고 한다.^[1]수학적으로 이것은 다음과 같이 표현된다.

${\displaystyle x(n_{1},n_{2},...,n_{M}=x(n_{1}x(n_{2})...x(n_{M}})}$

쉽게 알아볼 수 있는 분리 가능한 신호로는 단위 스텝 기능과 디락-델타 임펄스 기능이 있다.

${\displaystyle u}$( ${\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$,${\displaystyle {}_{}}$n ${\displaystyle {2\mathrm{}}_{}}$,${\displaystyle }$. .${\displaystyle }$. . . , ${\displaystyle {}_{}}$ ${\displaystyle M_{}}$ )${\displaystyle }$= ${\displaystyle u}$ ${\displaystyle (}$ ${\displaystyle {n\mathrm{}}_{}}$ ${\displaystyle {}_{}}$) ${\displaystyle u}$( ${\displaystyle {n\mathrm{}}_{}}$ ${\displaystyle 2_{}{}_{}}$)${\displaystyle }$. .${\displaystyle u}$ (n ${\displaystyle )}$ ${\displaystyle u(n_{1},n_{2}, n_{M}}}=u(n_{1})=u(n_{M})...u($단위 함수)

${\displaystyle \delta (n_{1},n_{2$$\delta (n_{M}})($dirac-delta 임펄스 함수)

콘볼루션은 선형 수술이다.그런 다음 분리 가능한 신호의 다차원적 경련은 많은 1차원 경련들의 산물로 표현될 수 있다는 것을 따른다.예를 들어 x와 h가 모두 분리 가능한 함수인 경우를 생각해 보십시오.

${\displaystyle x(n_{1},n_{2})**h(n_{1},n_{2})=\sum _{k_{1}=-\infty }^{\infty }\sum _{k_{2}=-\infty }^{\infty }h(k_{1},k_{2})x(n_{1}-k_{1},n_{2}-k_{2})}$

분리성의 속성을 적용하여 다음과 같이 다시 작성할 수 있다.

${\displaystyle x(n_{1},n_{2})**h(n_{1},n_{2})={\bigg (}\sum _{k_{1}=-\infty }^{\infty }h(k_{1})x(n_{1}-k_{1}){\bigg )}{\bigg (}\sum _{k_{2}=-\infty }^{\infty }h(k_{2})x(n_{2}-k_{2}){\bigg )}}$

이것은 1차원적 경련으로 감소한다는 것을 쉽게 알 수 있다.

${\displaystyle x(n_{1},n_{2})*h(n_{1}, n_{2}={\bigg [}x(n_{1})*h(n_{1}}{\bigg ]}{\bigg[}x({2})*h(n_{2}){\bigg ]}}}}}}}}}}}}}}}}}}}}}}}:$

이 결론은 다음과 같이 두 개의 분리 가능한 M-차원 신호의 경련으로 확장될 수 있다.

${\displaystyle x(n_{1},n_{2},...,n_{M})*{\overset {M}{\cdots }}*h(n_{1},n_{2},...,n_{M})={\bigg [}x(n_{1})*h(n_{1}){\bigg ]}{\bigg [}x(n_{2})*h(n_{2}){\bigg ]}...{\bigg [}x(n_{M})*h(n_{M}){\bigg ]}}$

따라서 두 신호가 분리될 수 있을 때 다차원적 경련은 ${\displaystyle n_{}}$ M ${\$ 1차원$$ 경련을 계산하여 계산할 수 있다.

행-기둥 분해

행-기둥 방법은 콘볼루션의 신호 중 하나가 분리될 수 있을 때 적용할 수 있다.이 방법은 각 표본의 직접 연산보다 계산적으로 더 효율적인 두 다차원 신호의 경련 계산 방법을 달성하기 위해 분리성의 특성을 이용한다(^[4]신호 중 하나가 분리 가능한 경우).다음은 행-기둥 분해 접근법(일반적으로 $h{\displaystyle }$(${\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$,${\displaystyle {}_{}}$n ${\displaystyle {2\mathrm{}}_{}}$) ${\displaystyle h(n_{1},n_{2})$의 수학적 추론을 보여준다.

${\displaystyle{\begin{정렬}(n_{1},n_{2})&, =\sum _{k_{1}=-\infty}^{\infty}\sum _{k_{2}=-\infty}^ᆳh(k_{1},k_{2})x(n_{1}-k_{1},n_{2}-k_{2})\\&, =\sum _{k_{1}=-\infty}^{\infty}\sum _{k_{2}=-\infty}^ᆷh_ᆸ(k_{1})h_ᆹ(k_{2})x(n_{1}-k_{1},n_{2}-k_{2})\\&, =\sum _{k_{1}=-\infty}^ᆻh_ᆼ(k_{1}){\Bigg는 경우}\sum _{k_{2}.=-\infty}^{\infit }h_{2}(k_{2})x(n_{1}-k_{1},n_{2}-k_{2}{\Bigg ]}\end{aigned}}}}}}}}}}$

The value of ${\displaystyle \sum _{k_{2}=-\infty }^{\infty }h_{2}(k_{2})x(n_{1}-k_{1},n_{2}-k_{2})}$ can now be re-used when evaluating other ${\displaystyle y}$ values with a shared value of ${\displaystyle n_{2}}$:

${\displaystyle{\begin{정렬}(n_{1}+\delta ,n_{2})&, =\sum _{k_{1}=-\infty}^ᆯh_ᆰ(k_{1}){\Bigg[}\sum_{k_{2}=-\infty}^{\infty}h_{2}({2})k_ x(n_{1}--LSB- k_{1}-\delta],n_{2}-k_{2}){\Bigg]}\\&, =\sum _{k_{1}=-\infty}^ᆵh_ᆶ(k_{1}+\delta){\Bigg[}\sum_{k_{2}=-\infty}^{\infty}h_{2}({2})k_ x({1}-k_{1},n_{2}-k_{2}){n_ \Bigg]}\.끝{alig네드}}$

$따라서$, 결과적인 콘볼루션은 먼저$$$n$ ${\displaystyle {1\mathrm{}}_{}}$,$n$ $)$의 모든 행에 대해$$콘볼루션 $작업$을 수행한 다음, 그 모든 열에 대해 효과적으로 계산할 수 있다$.$이 접근방식은 컴퓨터 프로세서 내에서 메모리에 접근하는 방법을 고려함으로써 더욱 최적화될 수 있다.

프로세서는 주어진 작업에 필요한 신호 데이터를 로딩한다.현대 프로세서의 경우 메모리보다 액세스 시간이 빠른 프로세서 캐시로 데이터가 로드된다.캐시 자체는 선으로 분할되어 있다.캐시 라인이 메모리에서 로드되면 여러 개의 데이터 피연산자가 한 번에 로드된다.일련의 신호 데이터가 프로세서의 캐시에 완전히 들어갈 수 있는 최적화된 경우를 생각해 보십시오.이 특정 프로세서는 데이터 행에 효율적으로 액세스할 수 있지만, 같은 열에 있는 서로 다른 데이터 피연산자가 서로 다른 캐시 라인에 있을 수 있기 때문에 열에는 액세스할 수 없다.^[5]메모리에 접근하는 방식을 활용하기 위해서는 데이터 세트를 열로 접근하려는 시도보다는 데이터 세트를 전치한 다음 행으로 축을 이루는 것이 더 효율적이다.알고리즘은 다음과 같이 된다.

1. 분리 가능한 2차원 신호 $h{\displaystyle ({}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$,${\displaystyle {}_{}{n\mathrm{}}_{}}$ 2${\displaystyle {}_{}}$) ${\displaystyle h(n_{1},n_{2})$를 두 개의 1차원 신호 h ${\displaystyle {1\mathrm{}}_{}{n\mathrm{}}_{}}$ 1${\displaystyle {}_{}}$) ${\displaysty h_{1}(n_{1})$ 및$$ $h{\displaystyle {}_{}}$ ${\displaystyle {2\mathrm{}}_{}{}_{}}$ ${\displaystyle {2\mathrm{}}_{}}$ ${\displaysty h_{2}(n_{2})$로 구분하십시오.
2. $h{\displaystyle }$ ${\displaystyle {1\mathrm{}}_{}}$( ${\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$)${\displaystyle }$${\displaystyle h_{1}(n_$${1},{2})$을 사용하여$$$$ g${\displaystyle }$( ${\displaystyle {n\mathrm{}}_{}}$ 1${\displaystyle {}_{}}$) ${\displaystyle {}_{}}$$displaystyle h_{$1}(n_${1$}) ${\$$displaystyle g(n_{1},n_{2})$의 수평 구성 요소에 대해 행-현상 콘볼루션을 수행하십시오.
3. 2단계에서 발생한$$ 신호 $g{\displaystyle ({n\mathrm{}}_{}}$ 1,${\displaystyle {}_{}{}_{}}$ ${\displaystyle {2\mathrm{}}_{}}$) ${\displaystyle g(n_{1},n_{2}})$의 수직 구성 요소를 전치하십시오.
4. $g{\displaystyle ({}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$,${\displaystyle {}_{}{n\mathrm{}}_{}}$ ${\displaystyle {}_{}}$)의$$전치된 수직 구성 요소에 대해 행-현상 컨볼루션을 수행하여$$ 원하는 출력 $y{\displaystyle ({}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$, ${\displaystyle {}_{}}$ ${\displaystyle {2\mathrm{}}_{}}$) ${\displaystyle y(n_$$})$를 가져오십시오$.$

행-기둥 분해에 따른 계산 속도 향상

$X{\displaystyle }$ ${\displaystyle \times }$ ${\displaystyle Y}$ ${\displaystyle X\time Y}$ 크기의 이미지가 ${\displaystyle J}$ ${\displaystyle \times }$ K ${\displaystyle J\time K}$ 크기의 분리 가능한 필터를 통과하고 있는$$ 경우를 조사하십시오$.$ 이미지 자체는 분리할 수 없습니다.필터의 분리 가능성을 이용하지 않고 직접 콘볼루션 접근방식을 사용하여 결과를 계산하는 경우, 이 경우 약 $X{\displaystyle }$ Y ${\displaystyle J}$ ${\displaystyle K}$ ${\displaystyle XYJK}$의 승수와 추가가 필요할 것이다.필터의 분리성을 고려할 경우 필터링을 두 단계로 수행할 수 있다.The first step will have ${\displaystyle XYJ}$ multiplications and additions and the second step will have ${\displaystyle XYK}$, resulting in a total of ${\displaystyle XYJ+XYK}$ or ${\displaystyle XY(J+K)}$ multiplications and additions.^[6]직접 콘볼루션과 분리 가능한 콘볼루션 사이의 계산 복잡성의 비교는 다음 이미지에 제시되어 있다.

이산값 다차원 신호의 원형 콘볼루션

다차원 신호에 대한 원형 콘볼루션 접근법의 전제는 두 유한 확장 이산값 신호 사이의 콘볼루션을 계산하는 데 사용할 수 있는 콘볼루션 정리와 이산 푸리에 변환(DFT) 사이의 관계를 개발하는 것이다.^[7]

다차원에서의 콘볼루션 정리

1차원 신호에 대해, Convolution Organization은 두 신호 사이의 콘볼루션의 푸리에 변환은 그 두 신호의 푸리에 변환의 제품과 동일하다고 기술한다.따라서, 시간 영역의 콘볼루션은 주파수 영역의 곱셈과 같다.수학적으로 이 원리는 다음을 통해 표현된다.

이 원리는 다차원 신호 처리로 직접 확장 가능하다.이 속성은 다음과 같이 이산 푸리에 변환(DFT)을 사용한 용도에 쉽게 확장된다(N $크기 {\displaystyle$$\otimes }$을(를$)$ 사용하는 경우 선형 콘볼루션은 원형 콘볼루션으로 대체됨).$$

${\displaystyle y(n)=h(n)\otimes x(n)\long 왼쪽 오른쪽 화살표 Y(k)=H(k)X(k)}$

다차원 신호 처리 시:

여기서 순환 경련은 N ${\displaystyle {1\mathrm{}}_{}}$,${\displaystyle {}_{}{N\mathrm{}}_{}}$ 2,${\displaystyle }$.${\displaystyle }$. .${\displaystyle {}_{}}$ ${\displaystyle M_{}}$ ${\$}, $...,N_{M}$의 크기가 될 것이다$.$

순환 콘볼루션 접근법

원형 콘볼루션 접근법을 사용하는 동기는 그것이 DFT를 기반으로 하기 때문이다.원형 경련 뒤의 전제는 입력 신호의 DFT를 취하여 함께 곱한 다음 역 DFT를 취하는 것이다.앨리어싱이 발생하지 않도록 충분히 큰 DFT를 사용할 수 있도록 주의해야 한다.DFT는 유한한 범위의 신호를 처리할 때 숫자로 계산할 수 있다.이 접근방식이 갖는 한 가지 장점은 DFT와 역DFT를 취해야 하기 때문에 FFT(Fast Fourier Transform)와 같은 효율적인 알고리즘을 활용할 수 있다는 점이다.원형 콘볼루션은 주파수 영역뿐만 아니라 시간/공간 영역에서도 계산할 수 있다.

앨리어싱을 방지하기 위해 DFT 크기 선택

두 개의 유한 연장 신호 x와 h를 취하는 경우를 생각해 보십시오.두 신호에 대해 다음과 같은 DFT가 있다.

${\displaystyle x(n_{1},n_{2})\longleftrightarrow X(k_{1},k_{2})}$ and ${\displaystyle h(n_{1},n_{2})\longleftrightarrow H(k_{1},k_{2})}$

The region of support of ${\displaystyle x(n_{1},n_{2})}$ is ${\displaystyle 0\leq n_{1}\leq P_{1}-1}$ and ${\displaystyle 0\leq n_{2}\leq P_{2}-1}$ and the region of support of ${\displaystyle h(n_{1},n_{2})}$ is ${\displaystyle 0\le n_{}}$${\displaystyle 1_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle {Q\mathrm{}}_{}}$ ${\displaystyle 1{}_{}}$- 1 ${\displaystyle 0\leq n_{1}-1}$및$$ $0{\displaystyle \mathrm{}}$ ${\displaystyle \le }$$n$ ${\displaystyle {2\mathrm{}}_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle {Q\mathrm{}}_{}}$ $2$${\displaystyle {}_{}}$- ${\displaystyle 1}$ ${\displaystyle 0\leq n_{2}\leq Q_{2}-1}$.

이 두 신호의 선형 경련은 다음과 같이 주어질 것이다.

Given the regions of support of ${\displaystyle x(n_{1},n_{2})}$ and ${\displaystyle h(n_{1},n_{2})}$, the region of support of ${\displaystyle y_{linear}(n_{1},n_{2})}$ will then be given as the following:

Based on the regions of support of the two signals, a DFT of size ${\displaystyle N_{1}\times N_{2}}$ must be used where ${\displaystyle N_{1}\geq \max(P_{1},Q_{1})}$ and ${\displaystyle N_{2}\geq \max(P_{2},Q_{2})}$ since the same size DFT m두 신호에 모두 사용된다.신호의 범위보다 큰 DFT 크기가 필요한 경우, 신호는 필요한 길이에 도달할 때까지 무패딩 처리된다.DFT를 곱하고 그 결과에 대해 역 DFT를 취한 후, 그 결과로 나타나는 원형 경련은 다음에 의해 주어진다.

${\displaystyle y_{circular}(n_{1},n_{2})=\sum _{r_{1}}\sum _{r_{2}}{\Bigg [}\sum _{m_{1}=0$$}^{Q_{1}-1}\sum _{m_{2}=0}^{Q_{2}-1}h(m_{1},m_{2})x(n_{1}-m_{1}-r_{1}N_{1},n_{2}-m_{2}-r_{2}N_{2}){\Bigg ]}}$ for ${\displaystyle (n_{1},n_{2})\in R_{N_{1}N_{2}}}$

${\displaystyle R_{N_{1}{1}N_{2}}\triangleq \{{1}{1}{1}\leq N_{1}{1}-1,0\leq n_{2}\leq N_{2}-1}:0\leq N_{2}-1}:00}$

결과는 $y{\displaystyle {}_{}}$ ${\displaystyle c_{}}$ i ${\displaystyle c_{}}$ ${\displaystyle u_{}}$ ${\displaystyle a_{}}$ r${\displaystyle {}_{}}$(${\displaystyle {n\mathrm{}}_{}}$ 1,${\displaystyle {}_{}{}_{}}$ ${\displaystyle {2\mathrm{}}_{}}$ )${\displaystyle y_{circular}(n_{1},n_{2})$이 선형 컨볼루션 결과 $y{\displaystyle {}_{}}$ l ${\displaystyle i_{}}$ ${\displaystyle e_{}}$ ${\displaystyle a_{}}$ ${\displaystyle {}_{}{n\mathrm{}}_{}}$ 1,${\displaystyle {}_{}{n\mathrm{}}_{}}$ 2$){\displaystyle y_{lineine}(n_{1},n_{2$})의 공간 별칭 버전이 될 것이다$.$이는 다음과 같이 표현할 수 있다.

${\displaystyle y_{circular}(n_{1},n_{2})=\sum _{r_{1}}\sum _{r_{2}}y_{linear}(n_{1}-r_{1}N_{1},n_{2}-r_{2}N_{2}){\mathrm {\,\,\,for\,\,\,} }(n_{1},n_{2})\in R_{N_{1}N_{2}}}$

그런 다음 공간 별칭 복제본 사이의 앨리어싱을 방지하려면 ${\displaystyle {N\mathrm{}}_{}}$ 1 ${\$및$$ N ${\displaystyle {2\mathrm{}}_{}}$ ${\$ 다음 조건을 충족하도록 선택해야$$ 한다.

${\displaystyle N_{1}\geq P_{1}+Q_{1}-1}$

${\displaystyle N_{2}\geq P_{2}+Q_{2}-1}$

이러한 조건들이 충족되면, 순환 결합의 결과는 선형 결합의 결과와 같을 것이다(순환 결합의 주요 기간을 지원 영역으로 삼음).즉,

${\displaystyle y_{circular}(n_{1},n_{2})=y_{linear}(n_{1},n_{2})}$ for ${\displaystyle (n_{1},n_{2})\in R_{N_{1}N_{2}}}$

DFT를 사용한 절차 요약

따라서 콘볼루션 정리 및 순환 콘볼루션은 선형 콘볼루션을 수행하는 것과 동등한 결과를 얻기 위해 다음과 같은 방법으로 사용할 수 있다.^[8]

1. Choose ${\displaystyle N_{1}}$ and ${\displaystyle N_{2}}$ to satisfy ${\displaystyle N_{1}\geq P_{1}+Q_{1}-1}$ and ${\displaystyle N_{2}\geq P_{2}+Q_{2}-1}$
2. ${\displaystyle {신호\mathrm{}}_{}}$ $h{\displaystyle ({n\mathrm{}}_{}}$ 1,${\displaystyle {}_{}{n\mathrm{}}_{}}$ ${\displaystyle {}_{}}$) ${\displaystyle h(n_{1},n_{2}}$ 및 $x$(n 1,${\displaystyle {}_{}{n\mathrm{}}_{}}$ ${\displaystyle {}_{}}$) ${\displaystyle x(n_{1},n_{2}})$를 모두 N $1{\displaystyle {}_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle {2\mathrm{}}_{}}$ ${\$} 크기로 0 패딩하십시오.
3. $h{\displaystyle ({n\mathrm{}}_{}}$ 1,${\displaystyle {}_{}{n\mathrm{}}_{}}$ ${\displaystyle {}_{}}$) ${\displaystyle h(n_{1},$$n\_{\displaystyle }$${2}}$ 및$$ x${\displaystyle ({n\mathrm{}}_{}}$ 1,${\displaystyle {}_{}}$n ${\displaystyle {2\mathrm{}}_{}}$) ${\displaystyle$ x$(n_{1},n_{2})$의 DFT 계산
4. $Y{\displaystyle ({}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$,${\displaystyle {}_{}{k\mathrm{}}_{}}$ 2${\displaystyle {}_{}}$)${\displaystyle }$= ${\displaystyle H({}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$,${\displaystyle {}_{}}$k ${\displaystyle {2\mathrm{}}_{}}$) X${\displaystyle ({}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$,${\displaystyle {}_{}{k\mathrm{}}_{}}$ 2 $){\displaystyle Y(k_{1},k_{2}=$를 얻기 위한 DFT의 여러 결과$H(k_{1},k_{2})X(k_{1},k_{2})}$
5. 그런 $다음{\displaystyle }$ Y${\displaystyle ({k\mathrm{}}_{}}$ 1,${\displaystyle {}_{}{k\mathrm{}}_{}}$2 )$${\$displaystyle Y(k_{1},k_{2})$의 IDFT 결과가 두 신호에 대해 선형 콘볼루션을 수행한 결과와 동일할$$ 것이다.

오버랩 및 추가

다차원적 경련을 수행하는 또 다른 방법은 중복과 추가 접근법이다.이 방법은 현대 디지털 시스템에 내재된 방대한 양의 데이터로 인해 다차원적 경련과 관련된 계산 복잡성을 줄이는 데 도움이 된다.^[9]간결성을 위해 2차원 사례를 예로 들지만, 동일한 개념을 다차원까지 확대할 수 있다.

직접 연산을 사용한 2차원 경련을 고려하십시오.

${\displaystyle y(n_{1},n_{2})=\sum _{k_{1}-\nft }^{k_{1}=-\nft }^{k_{1}-\nfty }^{x(n_{1}-k_{1},k_{2})h(k_{1},k_}}}).$

출력 신호 $y{\displaystyle ({n\mathrm{}}_{}}$ 1,${\displaystyle {}_{}{n\mathrm{}}_{}}$ 2${\displaystyle {}_{}}$) ${\displaystyle y(n_{1},n_{2})$가 0이 아닌 계수가 N이고 임펄스 응답에 0이 아닌 샘플이 있다고 가정하면, 이 직접 계산에는 MN 곱과 MN - 1이 추가되어야 계산이 가능하다.대신 FFT를 사용하면 필터의 주파수 응답과 입력의 푸리에 변환을 메모리에 저장해야 할 것이다.^[10]방대한 양의 계산과 메모리 저장 공간의 과도한 사용은 더 많은 차원이 추가되면서 문제가 되고 있다.여기서 중첩과 덧셈 콘볼루션 방법이 나온다.

더 작은 콘볼루션 블록으로 분해

정보 블록 전체에 대해 경련을 수행하는 대신, 정보는 ${\displaystyle {L\mathrm{}}_{}}$ $1{\displaystyle {}_{}}$ ${\$ 스타일 $L_{$$}$ x ${\displaystyle {}_{}}$ ${\displaystyle {2\mathrm{}}_{}}${\$디스플레이$ 스타일 $L_{2$}}개의 작은 치수 블록으로 분할되어$$ FFT가 작아지고 계산 복잡성이 줄어들며 저장 필요성이 줄어들 수 있다.이는 다음과 같이 수학적으로 표현할 수 있다.

${\displaystyle x(n_{1},n_{2}}=\sum _{i=1}^{P_{1}:{1}\sum _{j=1}^{p_{2}}x_{ij}(n_{1},n_{2})}}$

where ${\displaystyle x(n_{1},n_{2})}$ represents the ${\displaystyle N_{1}}$x${\displaystyle N_{2}}$ input signal, which is a summation of ${\displaystyle P_{1}P_{2}}$ block segments, with ${\displaystyle P_{1}=N_{1}/L_{1}}$ and ${\displaystyle }$${\displaystyle P_{}}$ ${\displaystyle {2\mathrm{}}_{}}$= ${\displaystyle {}_{}}$ ${\displaystyle {2\mathrm{}}_{}}$/ ${\displaystyle L{}_{}}$ ${\displaystyle {2\mathrm{}}_{}}$ ${\$

출력 신호를 생성하기 위해 2차원 콘볼루션을 수행한다.

${\displaystyle y(n_{1},n_{2})=x(n_{1},n_{2})*h(n_{1},n_{2}}$

$x{\displaystyle ({n\mathrm{}}_{}}$ 1,${\displaystyle {}_{}{}_{}}$ ${\displaystyle {2\mathrm{}}_{}}$) ${\displaystyle x(n_{1},n_{2})$에 대체하면 다음과 같은 결과가$$ 발생한다.

${\displaystyle y(n_{1},n_{2})=\sum _{i=1}^{P_{1}:{1}\sum _{j=1}^{{{p_{2}}x}(n_{1},n_{2})*h(n_{1},n_{2})}}}$

이 콘볼루션은 직접 콘볼루션을 수행하는 것보다 복잡성을 더하지만, FFT 고속 콘볼루션과 통합되기 때문에 오버랩 애드는 더 빨리 수행되며 메모리 효율이 더 높은 방법이기 때문에 다차원 데이터의 대규모 집합에 실용적이다.

절차고장

$h{\displaystyle }$( ${\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$,${\displaystyle {}_{}}$n ${\displaystyle {2\mathrm{}}_{}}$) ${\displaystyle h(n_{1},n_{2}}$을(를) $M{\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle {2\mathrm{}}_{}}$ ${\$

1. 입력 $x{\displaystyle ({}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$,${\displaystyle {}_{}{}_{}}$ ${\displaystyle {2\mathrm{}}_{}}$) ${\displaystyle x(n_{1},n_{2}}}$을(를) 치수 L ${\displaystyle {1\mathrm{}}_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle {2\mathrm{}}_{}}$ {\$displaystyle L_{1$}\$time L_{2$}의 겹치지 않는 블록으로$$ 분할하십시오$.$
2. Zero pad ${\displaystyle h(n_{1},n_{2})}$ such that it has dimensions (${\displaystyle L_{1}+M_{1}-1}$) ${\displaystyle \times }$ (${\displaystyle L_{2}+M_{2}-1}$).
3. DFT를 사용하여 $H{\displaystyle ({k\mathrm{}}_{}}$ 1,${\displaystyle {}_{}{k\mathrm{}}_{}}$ 2${\displaystyle {}_{}}$) ${\displaystyle H(k_{1},k_{2}}$을(를) 가져오십시오$.$
4. 각 입력 블록에 대해:
   1. Zero pad ${\displaystyle x_{ij}(n_{1},n_{2})}$ to be of dimensions (${\displaystyle L_{1}+M_{1}-1}$) ${\displaystyle \times }$ (${\displaystyle L_{2}+M_{2}-1}$).
   2. $각{\displaystyle {}_{}}$ 블록의 이산 푸리에 변환을 사용하여 X i ${\displaystyle j_{}{}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$,${\displaystyle {}_{}}$k ${\displaystyle {2\mathrm{}}_{}}$) ${\displaystyle X_{ij}(k_{1},k_{2})$를 지정하십시오$.$
   3. 곱하여 ${\displaystyle {Yi}_{}}$ ${\displaystyle j_{}{k\mathrm{}}_{}}$ 1,${\displaystyle {}_{}{k\mathrm{}}_{}}$ 2${\displaystyle {}_{}}$)${\displaystyle }$= ${\displaystyle {}_{}}$ ${\displaystyle i_{}}$ ${\displaystyle j_{}{k\mathrm{}}_{}}$ 1,${\displaystyle {}_{}}$k ${\displaystyle {2\mathrm{}}_{}{}_{}}$) ${\displaystyle H({}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$,${\displaystyle {}_{}}$k ${\displaystyle {}_{}}$ )${\displaystyle Y_{ij}(k_{1},k_{2})=X_{ij}(k_{1},k_{2$})를 얻으십시오$.$$H(k_{1},k_{2}})}$.
   4. ${\displaystyle {Yi}_{}}$ ${\displaystyle j_{}{k\mathrm{}}_{}}$ 1,${\displaystyle {}_{}{k\mathrm{}}_{}}$ 2${\displaystyle {}_{}}$) ${\displaystyle Y_{ij}(k_{1},k_{2})$의 역 이산 푸리에 변환을 사용하여$$ $yi{\displaystyle {}_{}}$ ${\displaystyle j_{}{n\mathrm{}}_{}}$ 1,${\displaystyle {}_{}{n\mathrm{}}_{}}$ 2${\displaystyle {}_{}}$) ${\displaystyle y_{ij}(n_{1},n_{2})$를 얻으십시오$.$
5. Find ${\displaystyle y(n_{1},n_{2})}$ by overlap and adding the last ${\displaystyle (M_{1}-1)}$${\displaystyle \times }$ ${\displaystyle (M_{2}-1)}$ samples of ${\displaystyle y_{ij}(n_{1},n_{2})}$ with the first ${\displaystyle (M_1-}$${\displaystyle 1}$$$${\displaystyle }$) ${\displaystyle (M_{1}-1)$${\displaystyle }$ ${\displaystyle \times }$ $($${\displaystyle {M\mathrm{}}_{}}$- ${\displaystyle 1}$) ${\displaystyle (M_{2}-1)$ 샘플$$ ${\displaystyle {yi}_{}}$+ ${\displaystyle 1_{}}$,${\displaystyle j_{}}$+ ${\displaystyle 1_{}}$(${\displaystyle {}_{}}$ 1,${\displaystyle {}_{}{}_{}}$ ${\displaystyle {2\mathrm{}}_{}}$) ${\displaysty y_{i+$^[11]1$,j+1}(n_{$1},$n_{2})}).$

그림 작동 방법

중복 추가 방법을 보다 명확하게 시각화하기 위해 다음 그림은 그 방법을 그래픽으로 조사한다.입력 $x{\displaystyle ({n\mathrm{}}_{}}$ 1,${\displaystyle {}_{}{n\mathrm{}}_{}}$ 2${\displaystyle {}_{}}$) ${\displaystyle x(n_{1},n_{2})$가 아래 그림과 같이 세로 방향과 가로 방향 모두에서 길이 N의 사각 영역 지원을 가지고 있다고$$ 가정하십시오.그리고 나서 그것은 네 개의 작은 사각형으로 구성될 수 있는 방식으로 네 개의 작은 부분으로 분할된다.집계 신호의 각 블록에는 치수$({\displaystyle N\mathrm{}}$/ 2${\displaystyle }$) ${\displaystyle (N/2)}$ $\times$${\displaystyle }$ ${\displaystyle \times$}(N$$${\displaystyle }$/${\displaystyle 2\mathrm{}}$) ${\displaystyle (N/2)}$이 있다$.$

그런 다음 필터의 임펄스 반응과 함께 각 구성 요소가 융화된다.컴퓨터가 동시에 저장하고 계산하기에 충분한 메모리와 자원을 가지고 있는 한, 이러한 각 경련은 컴퓨터에서 병렬로 사용될 수 있기 때문에 이와 같은 구현을 위한 이점은 여기서 가시화할 수 있다.

아래 그림에서 왼쪽의 첫 번째 그래프는 해당 임펄스 응답 $h{\displaystyle ({}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$,${\displaystyle {}_{}{n\mathrm{}}_{}}$ 2${\displaystyle {}_{}}$) ${\displaystyle h(n_{1},n_{2}})$와 함께 $입력{\displaystyle {}_{}}$ ${\displaystyle {x\mathrm{}}_{}}$ ${\displaystyle {0,}_{}}$ 0, ${\$$displaystyle$ $x_$${0,$$0}$의 구성요소에 해당하는 콘볼루션을 나타내며$,$ 그 오른쪽에 입력 $x{\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$, $,$ {\displaystystylex $x_x_x_${1,0$}$이 있다$$.n 임펄스 응답 h ${\displaystyle ({}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$, n${\displaystyle {}_{}{}_{}}$)${\displaystyle {}_{}}${\$displaystyle h(n_{1$},$n_{2}})$와 함께 convolved$.$

다른 두 입력에 대해서도 각각 동일한 과정이 수행되며, 그것들은 함께 축적되어 경합을 형성한다.이것은 왼쪽에 묘사되어 있다.

필터 임펄스 응답 h${\displaystyle ({}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$,${\displaystyle {}_{}{n\mathrm{}}_{}}$ 2${\displaystyle {}_{}}$) ${\displaystyle h(n_{1},n_{2})$의 지원 영역이 두 차원 모두에서${\displaystyle }$(${\displaystyle N\mathrm{}}$/ 8${\displaystyle }$) ${\displaystyle(N/8$)이라고 가정하십시오.이는 각 콘볼루션이 n ${\displaystyle {1\mathrm{}}_{}}$ ${\$및$$ n ${\displaystyle {2\mathrm{}}_{}}$ ${\$}} 방향$$ 모두에서$$ 치수$({\displaystyle N}$/ $2$) ${\displaystyle \time$ $\}($${\displaystyle N\mathrm{}}$/ 8$){\displaystystyle$ ($N$$/$$8$)를 가진 신호를 경합하므로(파란색으로 강조 표시됨) 길이).각각의 개별적인 콘볼루션의 경우는 다음과 같다.

${\displaystyle (N}$/ ${\displaystyle 2\mathrm{}}$) ${\$$displaystyle$($N/2)}$${\displaystyle }$+ ${\displaystyle +}$${\displaystyle }$(${\displaystyle N\mathrm{}}$/ 8${\displaystyle }$) ${\displaystyle (N/8$)$$${\displaystyle }$- ${\$$displaystyle$ -$}$ $1$${\displaystyle \mathrm{}}$=${\displaystyle }$( 5${\displaystyle }$/ ${\displaystyle 8\mathrm{}}$) ${\displaystyle N}$- ${\displaystyle 1}$ - 1$$($5/8)N-1}$

양방향으로밝은 파란색 부분은 인접한 두 개의 경련 사이의 중첩과 상관관계가 있는 반면, 진한 파란색 부분은 네 개의 경련 모두 중첩이 된다.이 모든 겹치는 부분은 결합 경련 y${\displaystyle }$($n{\displaystyle }$ ${\displaystyle {1\mathrm{}}_{}}$,${\displaystyle {}_{}{n\mathrm{}}_{}}$ 2 $){\displaystyle y(n_{1},n_{2})$를 형성하기 위해 경련 외에 함께 추가된다$.$^[12]

겹쳐서 저장

오버랩 및 추가 방법과 마찬가지로 중복 및 저장 방법도 이산 시간 경련과 관련된 계산 복잡성을 줄이는 데 사용된다.FFT와 결합한 이 방법은 방대한 데이터 배열의 연산에 필요한 메모리 공간을 최소화하면서 디지털 시스템을 통해 대량의 데이터를 필터링할 수 있게 한다.

중복 및 추가 비교

중복 및 저장 방법은 몇 가지 주목할 만한 예외가 있는 중복 및 추가 방법과 매우 유사하다.중복 추가 방법에는 이산 시간 신호의 선형 결합이 수반되는 반면, 중복 저장 방법은 순환 결합 원리를 수반한다.또한 오버랩과 세이브 방식은 임펄스 반응의 일회성 제로 패딩만을 사용하는 반면, 오버랩 애드 방식은 각 입력 구성요소의 모든 콘볼루션에 대해 제로 패딩을 포함한다.오버랩 추가 상대와 같은 시간 영역 별칭을 방지하기 위해 제로 패딩을 사용하는 대신, 오버랩 저장 기능은 모든 별칭 지점을 무시하고 이전 데이터를 다음 블록의 콘볼루션에 복사하기 위해 한 블록에 저장한다.

한 차원에서는 두 방법 간의 성능 및 스토리지 메트릭 차이가 최소화된다.단, 다차원적 콘볼루션의 경우, 속도나 저장 능력 면에서 오버랩 애드 방식보다 오버랩-세이브 방식을 선호한다.^[13]오버랩과 추가 케이스에서와 마찬가지로 2차원 케이스를 불러오지만 모든 다차원 프로세스로 쉽게 확장할 수 있다.

절차고장

$h{\displaystyle }$( ${\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$,${\displaystyle {}_{}}$n ${\displaystyle {2\mathrm{}}_{}}$) ${\displaystyle h(n_{1},n_{2}}$을(를) $M{\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle {2\mathrm{}}_{}}$ ${\$

1. 입력 신호 x${\displaystyle ({}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$,${\displaystyle {}_{}{}_{}}$ ${\displaystyle {2\mathrm{}}_{}}$) $시작$ 부분에${\displaystyle }$($M$ 1${\displaystyle }$- ${\displaystyle 1}$) ${\$$displaystyle$$(M_$${1}-1)$열과$$($M_{2$$}-1)$0 행을$$ 양 치수에$$ 삽입한다$.$
2. Split the corresponding signal into overlapping segments of dimensions (${\displaystyle L_{1}+M_{1}-1}$)${\displaystyle \times }$(${\displaystyle L_{2}+M_{2}-1}$) in which each two-dimensional block will overlap by ${\displaystyle (M_{1}-1)}$ ${\displaystyl$$e \times$ $\}($${\displaystyle {}_{}}$ ${\displaystyle {2\mathrm{}}_{}}$- ${\displaystyle 1}$) ${\displaystyle(M_{2}-1)}$.
3. Zero pad ${\displaystyle h(n_{1},n_{2})}$ such that it has dimensions (${\displaystyle L_{1}+M_{1}-1}$)${\displaystyle \times }$(${\displaystyle L_{2}+M_{2}-1}$).
4. DFT를 사용하여 $H{\displaystyle ({k\mathrm{}}_{}}$ 1,${\displaystyle {}_{}{k\mathrm{}}_{}}$ 2${\displaystyle {}_{}}$) ${\displaystyle H(k_{1},k_{2}}$을(를) 가져오십시오$.$
5. 각 입력 블록에 대해:
   1. $각{\displaystyle {}_{}}$ 블록의 이산 푸리에 변환을 사용하여 X i ${\displaystyle j_{}{}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$,${\displaystyle {}_{}}$k ${\displaystyle {2\mathrm{}}_{}}$) ${\displaystyle X_{ij}(k_{1},k_{2})$를 지정하십시오$.$
   2. 곱하여 ${\displaystyle {Yi}_{}}$ ${\displaystyle j_{}{k\mathrm{}}_{}}$ 1,${\displaystyle {}_{}{k\mathrm{}}_{}}$ 2${\displaystyle {}_{}}$)${\displaystyle }$= ${\displaystyle {}_{}}$ ${\displaystyle i_{}}$ ${\displaystyle j_{}{k\mathrm{}}_{}}$ 1,${\displaystyle {}_{}}$k ${\displaystyle {2\mathrm{}}_{}{}_{}}$) ${\displaystyle H({}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$,${\displaystyle {}_{}}$k ${\displaystyle {}_{}}$ )${\displaystyle Y_{ij}(k_{1},k_{2})=X_{ij}(k_{1},k_{2$})를 얻으십시오$.$$H(k_{1},k_{2}})}$.
   3. ${\displaystyle {Yi}_{}}$ ${\displaystyle j_{}{k\mathrm{}}_{}}$ 1,${\displaystyle {}_{}{k\mathrm{}}_{}}$ 2${\displaystyle {}_{}}$) ${\displaystyle Y_{ij}(k_{1},k_{2})$의 역 이산 푸리에 변환을 사용하여$$ $yi{\displaystyle {}_{}}$ ${\displaystyle j_{}{n\mathrm{}}_{}}$ 1,${\displaystyle {}_{}{n\mathrm{}}_{}}$ 2${\displaystyle {}_{}}$) ${\displaystyle y_{ij}(n_{1},n_{2})$를 얻으십시오$.$
   4. 각 출력 블록 ${\displaystyle {\mathrm{yi}}_{}}$ j${\displaystyle {}_{}}$(${\displaystyle }$${\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$,${\displaystyle {}_{}{n\mathrm{}}_{}}$ 2${\displaystyle {}_{}}$) ${\displaystyle$$$(${\displaystyle {}_{}}$$1}-1)$$×$ $\{\backslash {\displaystyle }$$displaystyle \times$ $}{{$2} {\$displaystyle$$y_{ij}(n_{1$},$n_{2$})를$$ 제거하십시오$.$
6. 각 출력 블록 ${\displaystyle {yi}_{}}$ ${\displaystyle j_{}{}_{}{n\mathrm{}}_{}}$ 1,${\displaystyle {}_{}{n\mathrm{}}_{}}$ 2${\displaystyle {}_{}}$)에 대한 마지막$({\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle {L\mathrm{}}_{}}$ ${\displaystyle {}_{}}$) ${\displaystyle(L_{1}\times L_{2$} 샘플$$$)$을 첨부하여$$ $y{\displaystyle ({}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$,${\displaystyle {}_{}}$n ${\displaystyle {2\mathrm{}}_{}}$ )$$${\displaystyle y_{ij}(n_{1$},$n_{2})$를 찾으십시오$.$^[11]

나선 변환

행-기둥 분해와 유사하게, 나선 변환은 1차원 콘볼루션 특성 및 연산자를 통합하여 다차원 콘볼루션을 계산한다.그러나 신호의 분리성을 사용하는 대신 카르트 좌표 공간을 나선 좌표 공간에 매핑하여 다차원 공간에서 1차원 공간으로의 매핑을 허용한다.

1차원 콘볼루션 방법을 이용한 다차원 콘볼루션

나선의 변형을 이해하기 위해서는 먼저 다차원적 경련이 어떻게 1차원 경련으로 분해될 수 있는지를 이해하는 것이 유용하다.Assume that the two signals to be convolved are ${\displaystyle X_{M\times N}}$ and ${\displaystyle Y_{K\times L}}$, which results in an output ${\displaystyle Z_{(M-K+1)\times (N-L+1)}}$. This is expressed as follows:

${\displaystyle Z(i,j)=\sum _{m=0}^{M-1}\sum _{n=0}^{N-1}X(m,n)Y(i-m,j-n)}}$

다음으로, 두 개의 행렬이 만들어지며, 각 입력은 동일한 치수를 가지도록 양 차원에서 각각 0 패드를 만든다.

=[ ${\$ = ${\begin{bmatrix}X&0\0&0\\\\end{bmatrix}}$ 및 Y =[ ${\$ = ${\be{bmatrix}$$Y&0\\0&0\\\end{bmatrix}}$

여기서 각 입력 행렬은 현재 치수$({\displaystyle M}$+ ${\displaystyle \mathrm{K}}$- 1${\displaystyle }$) ${\displaystyle (M+K-1)$${\displaystyle }$ ${\displaystyle \time$ $\}($${\displaystyle N}$+ ${\displaystyle L}$- ${\displaystyle 1}$) ${\displaystyle (N+$L-1)이$$된다$.$그런 다음 수정된 행렬을 $벡터{\displaystyle {}^{}}$, X ${\displaystyle {″}^{}}$ ${\$ X$'}$ $및{\displaystyle {}^{}}$ Y$$ ${\displaystyle {″}^{}}$ ${\$ $Y$$'}$로 변환하기 위해 열별 사전 편찬 순서를 구현할 수 있다$.$ 각 벡터의 중요하지 않은 샘플 수를 최소화하기 위해 각 벡터는 원래 행렬 $X{\displaystyle }${의 마지막 샘플 이후에 잘린다.$\displaystyle X}$ $및$ Y ${\displaystyle Y}$ 각각$$.이에 따라 벡터 $X{\displaystyle {}^{}}$″ ${\$ X$'}$ 및$$ Y ${\displaystyle {″}^{}}$ ${\$의 길이는 다음과 같이 지정된다$$.

${\displaystyle l_{}}$ ${\displaystyle {X{}^{}}_{}}$ ${\displaystyle {{″}^{}}_{}}$= ${\displaystyle l_{X$${\displaystyle M}$+ ${\displaystyle \mathrm{K}}$- 1${\displaystyle }$) ${\displaystyle (M+K-1)$${\displaystyle }$ ${\displaystyle \time$ $\}($${\displaystyle \mathrm{N}}$- 1${\displaystyle }$) ${\$$displaystyle$$$($N-1$)$$+ $}$

${\displaystyle {l{}^{}}_{}}$ ${\displaystyle {{″}^{}}_{}}$= ${\displaystyle l_{Y$${\displaystyle M}$+ ${\displaystyle \mathrm{K}}$- 1${\displaystyle }$) ${\displaystyle (M+K-1)$${\displaystyle }$ ${\displaystyle \time$ $\}($${\displaystyle L}$- ${\displaystyle 1}$) ${\displaystyle (L-1)}$ $$+ K ${\displaystystystystyle K}$

이 두 벡터, $Z{\displaystyle {}^{}}$ ${\displaystyle {″}^{}}$ ${\$의 콘볼루션 길이를 도출하여 다음과 같이 나타낼 수 있다.

${\displaystyle l_{Z'}=}$ ${\displaystyle l_{Y'}+}$${\displaystyle l_{X"}}}$ ${\displaystyle =(M+K-1)}$$\displaystyle \reason }$${\displaystyle(N+L-1)}$

이 벡터 길이는 원래의 매트릭스 출력 $Z{\displaystyle }$ ${\displaystyle Z}$의 치수와 동일하며$,$ 매트릭스로의 변환을 직접 변환으로 만든다.따라서 벡터인 $Z{\displaystyle {}^{}}$ ${\displaystyle {″}^{}}$ ${\$ Z$'}$은$$2차원 이산형 콘볼루션의 출력을 생성하는 매트릭스 형태로 다시 변환된다.^[14]

나선형에서의 필터링

2차원 데카르트 메시에서 작업할 때 양쪽 축을 따라 푸리에 변환하면 각 기둥이나 행의 끝이 실린더를 형성하는 각각의 상면에 부착되면서 2차원 평면이 실린더가 된다.나선형의 필터링은 이와 유사한 방식으로 동작하지만, 이 경우를 제외하고 각 기둥의 하단이 다음 기둥의 상부에 부착되어 헬리컬 메쉬가 발생한다.이것은 아래에 설명되어 있다.어두워진 타일은 필터 계수를 나타낸다.

그런 다음 이 나선 구조를 얇게 썰어 1차원 스트립으로 분해하면 2-d 카르테시안 평면의 동일한 필터 계수가 동일한 입력 데이터와 일치하게 되어 동등한 필터링 체계를 얻게 된다.이를 통해 필터 계수를 분리하는 영점 간격이 있는 1D 필터에 2D 필터가 풀렸기 때문에 1차원 콘볼루션 운영자가 2차원 콘볼루션을 수행할 수 있게 된다.

다음과 같은 일부 로우패스 2차원 필터를 사용했다고 가정한다.

0	-1	0
-1	4	-1
0	-1	0

그러면 일단 2차원 공간이 나선형으로 변환되면 1차원 필터는 다음과 같이 보일 것이다.

${\displaystyle h(n)=-1,1,0,...,0,-1,4,1,0,...,0,1,0,...}$

1차원 필터에서 풀린 후 1차원 필터링 스트립에 표시된 것처럼 선행 0이 없다는 것을 주의하십시오.전체 1차원 스트립은 합심할 수 있었지만, 선행 영점을 단순히 무시하는 것은 계산적으로 덜 비싸다.또한 이러한 백그라운드 제로 값 중 어떤 것도 메모리에 저장하지 않아도 되어 소중한 메모리 자원을 보존할 수 있다.^[15]

적용들

콘볼루션을 통한 재귀 필터를 구현하기 위한 나선 변환은 신호 처리의 다양한 영역에서 사용된다.주파수 영역 푸리에 분석은 시스템이 정지해 있을 때 계수가 일정하고 주기적으로 샘플링되는 데이터가 있을 때 효과적이지만 불안정한 시스템에서는 더욱 어려워진다.나선 변환은 3차원 속도 변화를 위한 데이터를 처리할 수 있는 3차원 스택 후 마이그레이션 프로세스를 가능하게 한다.^[15]또한 암묵적인 3차원 파장 외삽 문제를 보조하기 위해 적용할 수 있다.^[16]다른 애플리케이션에는 지진 데이터 정규화, 예측 오류 필터 및 지구물리학적 디지털 시스템의 소음 감쇠에 유용한 알고리즘이 포함된다.^[14]

가우스 콘볼루션

신호와 영상 처리 내에서 사용되는 다차원적 경련법의 한 가지 적용은 가우스 경련이다.이는 입력 신호를 가우스 분포 함수로 경련하는 것을 말한다.

한 차원 이산형 값에서 샘플링된 가우스 분포는 다음과 같은 방법으로 제시된다($\mu {\displaystyle }$ ${\displaystyle =}$ ${\displaystyle 0}${\$displaystyle \mu =0}).$

이는 M 치수 신호까지 쉽게 확장된다$({\displaystyle \sigma$ }}은$($는) 모든 치수에 대해 일정하게 유지되고$$ ${\displaystyle {\mu \mathrm{}}_{}}$ 1${\displaystyle {}_{}}$= ${\displaystyle {}_{}}$ ${\displaystyle {2\mathrm{}}_{}}$=${\displaystyle }$.${\displaystyle }$. =${\displaystyle {}_{}}$ ${\displaystyle M_{}}$= ${\displaystyle 0}$ ${\displaystyle \mu _{1}=\2}=...).$$=\mu _{M}=0}$ }:$$인식해야 할 한 가지 중요한 특성은 M 치수 신호가 다음과 같이 분리가 가능하다는 것이다.그러면 이산값 신호를 가진 가우스 콘볼루션은 다음과 같이 표현할 수 있다.

${\displaystyle y(n)=x(n)*G(n)}$

${\displaystyle y(n_{1},n_{2},...,n_{M}=x(n_{1},n_{2}, ...,n_{M}*...*G(n_{1},n_{2}, ...,n_{M}})}$

FIR 필터별 근사치

가우스 콘볼루션은 유한 임펄스 응답(FIR) 필터의 구현을 통해 효과적으로 근사치를 계산할 수 있다.필터는 가우스 버전의 잘린 버전으로 설계된다.2차원 필터의 경우 그러한 필터의 전송 기능은 다음과 같이 정의된다.^[17]

${\displaystyle H(z_{1},z_{2})={\frac {1}{s(r_{1},r_{2})}}\sum _{n_{1}=-r_{1}}^{r_{1}}\sum _{n_{2}=-r_{2}}^{r_{2}}G(n_{1},n_{2}){z_{1}}^{-n_{1}}{z_{2}}^{-n_{2}}}$

어디에

${\displaystyle s(r_{1},r_{2})=\sum _{n_{1}=-r_{1}:{1}^{n_{1}:{n_{1}}\sum _{n_{2}=-r_{2}}:G(n_{1},n_{2})}}}}$

$r{\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$ ${\$및$$ ${\displaystyle {r\mathrm{}}_{}}$ $2{\displaystyle {}_{}}$ ${\$}}개의 낮은 값을 선택하면 연산은 덜 수행되지만$$, 높은 값을 선택하는 동안 정확도가 낮은 근사치를 산출하지만, 더 많은 수의 연산이 필요하다.

상자 필터별 근사치

가우스 콘볼루션의 근사치를 위한 또 다른 방법은 박스 필터를 통한 재귀 통과를 통한 것이다.약 1차원 경련에 대해 이 필터는 다음과 같이 정의된다.^[17]

${\displaystyle H(z)={\frac {1}{2r+1}:{2r+1}{\frac {z^{r}-z^{-r-1}{1-z^{-1}1}}}$

일반적으로 정확한 근사치를 얻기 위해 재귀 패스 3, 4, 5회를 수행한다.^[17]그 다음에 제안된 r 계산 방법은 다음과 같이 제시된다.^[18]

${\displaystyle {\sigma }^{}}$ ${\displaystyle {2\mathrm{}}^{}}$= 1 ${\displaystyle {12\mathrm{}}^{}}$ ${\displaystyle K}$(${\displaystyle }$( ( 2 ${\displaystyle \mathrm{r}}$+ 1${\displaystyle {}^{}}$) 2${\displaystyle {}^{}}$-${\displaystyle 1}$ ) ${\displaystyle \sigma$^{2$}={\frac${1$}{12}$K($2r+1$){2}$K({2}-1)}$ 여기서$$ K는 필터를 통과하는 재귀 통과 수입니다.

그렇다면 가우스 분포는 다른 차원에 걸쳐 분리가 가능하기 때문에 1차원 필터(각 차원을 별도로 분리)를 통한 재귀 통과는 다차원 가우스 콘볼루션의 근사치를 산출할 것이다.즉, M-차원 가우스 콘볼루션은 다음과 같은 1차원 필터를 통한 재귀적 패스를 통해 근사치를 구할 수 있다.

${\displaystyle H(z_{1}}={\frac {1}{1}{1}+1}:{2r_{1}+1}{\frac {{z_{1}:{1}-{1}-{1}^{1}-r_{1}-1}:{1-1}:{1-1}:{1-1}:{1-{1}:{1}}}}}}}}}}}}}}}}}}}$

${\displaystyle H(z_{2})={\frac {1}{2r_{2}+1}:{\frac {{z_{2}}-{{2}}-{z_{2}}-{2}^{-r_{{2}}-1}:{1-{1-{z_}-2}}:}}}}$

$\displaystyle \vdots }$

${\displaystyle H(z_{M}}={\frac {1}{2r_{M}+1}{\frac {{z_{M}}^{{M}}-{M}^{-r}-{M}-1}{1-{M}-1}}}}}}}}{{-1}:{-}1}:{-1}:{-1}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}$

적용들

가우스 경련은 신호 처리와 이미지 처리에서 광범위하게 사용된다.예를 들어 이미지 블러링은 가우스 콘볼루션으로 수행할 수 있으며 여기서 $where{\displaystyle }$ ${\displaystyle \sigma }$ 매개$$ 변수가 흐림의 강도를 제어한다.따라서 값이 높을수록 더 흐릿한 최종 결과에 해당된다.^[19]또한 SIFT(Scale-invariant feature transform) 피쳐 검출과 같은 컴퓨터 비전 애플리케이션에서도 흔히 사용된다.^[20]

참고 항목

• 콘볼루션
• 커널(이미지 처리)
• 신호처리

참조