속도 왜곡 이론

정보 이론
엔트로피 미분 엔트로피 조건부 엔트로피 관절 엔트로피 상호 정보 조건부 상호 정보 상대 엔트로피 엔트로피율 이산점 밀도 제한
점근 등분할 특성 속도 왜곡 이론
섀넌의 소스 부호화 정리 채널 용량 노이즈 채널 부호화 정리 섀넌-하틀리 정리
v t

이 글은 검증을 위해 추가 인용문이 필요합니다. 신뢰할 수 있는 출처에 인용문을 추가하여 이 기사를 개선하는 데 도움을 주십시오. 조달되지 않은 자재는 제거될 수 있습니다.출처 : '등급 왜곡 이론'– 뉴스 · 신문 · 서적 · 학자 · JSTOR (2012년 3월) (이 템플릿 메시지 삭제 방법 및 삭제 시기 확인)

레이트 왜곡 이론은 손실 데이터 압축의 이론적 기초를 제공하는 정보 이론의 주요 분야입니다.이것은 채널을 통해 통신해야 하는 레이트 R로 측정되는 심볼당 최소 비트 수를 결정하는 문제에 대처하여 소스(입력 신호)를 대략 재구성할 수 있도록 합니다.수신측(출력 신호)에서 예상되는 왜곡 D를 넘지 않도록 합니다.

서론

속도-왜곡 이론은 손실 압축 방법을 사용하여 얼마나 많은 압축을 달성할 수 있는지에 대한 분석식을 제공합니다.기존의 오디오, 음성, 이미지 및 비디오 압축 기술의 대부분은 환율 왜곡 함수의 일반적인 형태를 이용하는 변환, 양자화 및 비트레이트 할당 절차를 가지고 있습니다.

속도-왜곡 이론은 클로드 섀넌이 정보 이론에 대한 그의 기초 연구에서 창조되었습니다.

레이트 왜곡 이론에서 레이트는 보통 저장 또는 전송되는 데이터 샘플당 비트 수로 이해됩니다.왜곡의 개념은 현재 ^[1]논의되고 있는 주제이다.가장 간단한 경우(대부분의 경우 실제로 사용됨)에서는 왜곡이 입력 신호와 출력 신호 간의 차이의 제곱 기대값(즉, 평균 제곱 오차)으로 정의됩니다.그러나 대부분의 손실 압축 기법이 인간 소비자가 인식할 수 있는 데이터(음악 듣기, 사진 및 비디오 보기)에 대해 작동한다는 것을 알고 있기 때문에 왜곡 척도는 가급적 인간의 지각 및 미학에 따라 모델링되어야 한다. 즉, 손실 없는 압축에서 확률을 사용하는 것과 마찬가지로 왜곡 척도가 발생할 수 있다.궁극적으로 베이지안 추정 및 결정 이론에서 사용되는 손실 함수로 식별된다.오디오 압축에서는 지각 모델(따라서 지각 왜곡 측정)이 비교적 잘 개발되어 MP3나 Vorbis와 같은 압축 기술에 일상적으로 사용되지만 종종 속도 왜곡 이론에 포함시키기가 쉽지 않습니다.이미지 및 비디오 압축에서 인간의 지각 모델은 덜 발달되어 있으며 포함은 대부분 JPEG 및 MPEG 가중치(양자화, 정규화) 매트릭스로 제한됩니다.

왜곡 함수

왜곡 함수는 $기호{\displaystyle }$x(\$displaystyle$ x$)$를 근사 $기호{\displaystyle \stackrel{}{}}$x$(\$로 나타내는 비용을 측정합니다.일반적인 왜곡 함수는 해밍 왜곡과 제곱 오차 왜곡입니다.

해밍 왜곡

$\displaystyle d(x, {\hat {x})=param {case}0&{\text{if}}x=param {x}\1&{\text{if}}x\neq {x}\end{cases}}$

제곱 오차 왜곡

${\displaystyle d(x, {\hat {x}})=\left(x-{\hat {x}}\right)^{2}}$

환율 왜곡 함수

환율과 왜곡에 관련된 함수는 다음과 같은 최소화 문제의 해결책으로 볼 수 있습니다.

${\displaystyle\inf_{Y\mid X}(y\mid x)}I_{Q}(Y;X){\text{}D_{Q}\leq D^{*}의 대상입니다.}$

Here ${\displaystyle Q_{Y\mid X}(y\mid x)}$, sometimes called a test channel, is the conditional probability density function (PDF) of the communication channel output (compressed signal) ${\displaystyle Y}$ for a given input (original signal) ${\displaystyle X}$, and ${\displaystyl$$e$ I_${Q}(Y;X)$는 다음과 같이 정의된 Y$(\displaystyle$ Y$)$와 X$(\displaystyle$ X$)$ $사이$의 상호 정보입니다.

$({displaystyle I(Y;X)=H(Y)-H(Y\mid X)}$

$여기$서 H$)$ {$displaystyle$ H$(Y)}$ $및$ H${\displaystyle (Yx}$X$)$ {$displaystyle$ H$(Y\mid$ X$)}$는 각각 출력 신호 Y의 엔트로피 및 입력 신호가 주어진 출력 신호의 조건부 엔트로피입니다.

${\displaystyle H(Y)=-\int _{-\inty }^{\infty }P_{Y}(y)\log _{2}(P_{Y}(y),dy}$

${\displaystyle H(Y\mid X)=-\int _{-\infty }^{\infty }^{\infty }Q_{Y\mid X}(y\mid x)P_{X}(x)\log _{2}(Q_{Y\mid X\mid X}, XY)}$

이 문제는 왜곡 속도 함수로 공식화할 수도 있으며, 여기서 주어진 속도 제약에 대해 달성 가능한 최소 왜곡을 찾을 수 있습니다.관련된 표현은 다음과 같습니다.

${\displaystyle\inf_{Y\mid X}(y\mid x)}E[D_{Q}[X,Y] {\text{}I_{Q}(Y;X)\leq R.}$

두 공식은 서로 반대되는 함수로 이어집니다.

상호 정보는 수신기가 송신자의 신호(H(Y))에 대해 갖는 '전' 불확실성에 대한 척도로 이해할 수 있으며, 이는 송신자의 신호(${\displaystyle (Yx}$X$)\displaystyle$ H$(Y\mid$ X$))$에 대한 정보를 수신한 후 남은 불확실성에 의해 감소됩니다.물론 불확실성의 감소는 I${\displaystyle }$(${\displaystyle Y}$ ;${\displaystyle X}$) \ $displaystyle I$ \$left$( $Y$; X$$\ right )$정보$의 통신량에 의한 것입니다$.$

$예$를 들어 통신이 전혀 없는 경우 H${\displaystyle (Yx}$X ) ${\displaystyle =}$ $Y)$ {$displaystyle$ H$(Y\mid$ X)=$H(Y)}$ 및$$ $I{\displaystyle (Y;}$ ${\displaystyle \mathrm{X}}$)$$= 0(Y) = 0 {$displaystyle$ I$(Y;X$ $= 0$ 또는 신호가 $수신$되고 완벽한 채널일 경우입니다.$그{\displaystyle }$ 다음 ${\displaystyle H}$( Y${\displaystyle }$$x$${\displaystyle }$X ) ${\displaystyle =}$ ( \ $displaystyle H$( Y \ $mid$${\displaystyle }$X$$ ) ${\displaystyle =}$ ${\displaystyle 0}$ } 、$$( ${\displaystyle Y}$ ) ${\displaystyle =}$ ${\displaystyle H}$ (${\displaystyle }$X ) ${\displaystyle =}$ H ($Y$ ) =$$H ( X )$$= H ( X ) =$H$( X ) （ Y ) = H ( X$$)$$） 。

레이트 왜곡 함수의 정의에서 D $(\$${Q$$})$ 및$$ $D{\displaystyle {}^{}}${\(\$displaystyle$ D$^{*})$는 $특정{\displaystyle {}_{}}$ ${\displaystyle Q_{}}$ Y${\displaystyle x_{}}$X$(\$X$)$에 대해$$X$(\$$displaystyle$ Y$)$와 Y(\$displaystyle Y)$ 사이의$$ 왜곡입니다.평균 제곱 오차를 왜곡 측정으로 사용하는 경우, (진폭 연속 신호의 경우) 다음과 같이 됩니다.

${\displaystyle D_{Q}=\int _{-\infty }^{\infty}{\infty}P_{X,Y}(x,y)^{2},dx,dy=\int _{-\infty}^{\interfy}_{-int}_{-infty}_in}}$

위의 공식에서 알 수 있듯이 레이트 왜곡 함수를 계산하려면 $PDF{\displaystyle {}_{}}$ $P{\displaystyle }$ X${\displaystyle {}_{}x})$의 $관점$에서 입력$$X(\$displaystyle$ $X)$를 확률적으로 기술한 다음 조건부 $PDF{\displaystyle {}_{}}$ Q ${\displaystyle {Yx}_{}}$X ( $y$ $display style$ Q _$mid$ X $}$를 찾는 것이 목적입니다.$주어진$ 왜곡 $D{\displaystyle {}^{}}$ ${\$ {\$displaystyle$D$^\{*\}\}.$ 이러한 정의는 이산 및 혼합 랜덤 변수도 고려하도록 이론적으로 공식화할 수 있습니다.

이 최소화 문제에 대한 분석적 해결 방법은 가장 잘 알려진 두 가지 예를 다음에 제시하는 경우를 제외하고는 얻기 어려운 경우가 많습니다.모든 선원의 속도 왜곡 함수는 몇 가지 기본 특성을 따르는 것으로 알려져 있으며, 가장 중요한 것은 연속적이고 단조롭게 감소하는 볼록(U) 함수이기 때문에 예제의 함수의 모양이 전형적이라는 것이다(실생활에서 측정된 속도 왜곡 함수도 매우 유사한 형태를 갖는 경향이 있다).

이 문제에 대한 해석적 해법은 드물지만, 유명한 Shannon Lower Bound(SLB; 섀넌 하한)를 포함한 이러한 함수에는 상한과 하한이 있습니다.이 함수는 오차 제곱과 메모리리스 소스의 경우 유한한 미분 엔트로피를 가진 임의의 소스에 대해 다음과 같이 기술합니다.

${\displaystyle R(D)\geq h(X)-h(D)}$

여기서 h(D)는 분산이 D인 가우스 랜덤 변수의 미분 엔트로피입니다.이 하한은 메모리 및 기타 왜곡 측정이 있는 소스로 확장할 수 있습니다.SLB의 중요한 특징 중 하나는 다양한 종류의 소스에 대해 낮은 왜곡 상태에서 점근적으로 조여진다는 것이며 경우에 따라서는 실제로 속도 왜곡 함수와 일치한다는 것입니다.섀넌 하한은 일반적으로 두 숫자 사이의 왜곡이 이 두 숫자 값의 차이에 대한 함수로 표현될 수 있는 경우 찾을 수 있습니다.

Richard Blahut이 공동 개발한 Blahut-Arimoto 알고리즘은 임의의 유한 입력/출력 알파벳 소스의 속도 왜곡 함수를 수치적으로 얻기 위한 우아한 반복 기법이며, 이를 보다 일반적인 문제 사례로 확장하기 위해 많은 작업이 수행되었습니다.

메모리를 탑재한 정지 소스로 작업할 때는 레이트 왜곡 함수의 정의를 수정해야 하며, 길이가 증가하는 시퀀스에 대한 제한의 의미로 이해해야 합니다.

${\displaystyle R(D)=\lim _{n\rightarrow \infty }R_{n}(D)}$

어디에

${\displaystyle R_{n}(D)=black {1}{n}}\inf _{Q_{Y^{n}\mid X^{n}\in {mathcal {Q}}I(Y^{n},X^{n})}$

그리고.

${\displaystyle {Q}}=\{Q_{Y^{n}\mid X^{n}(Y^{n}\mid X^{n},X_{0}):E[d(X^{n})]Y^{n}>\leq D\}$

여기서 superscripts는 그 시점까지의 완전한 시퀀스를 나타내고, 첨자0은 초기 상태를 나타냅니다.

메모리리스(독립형) 가우스 소스(오류 제곱 왜곡 포함

X$(\displaystyle$ X$)$가 분산이 $(\$^{$2$인 가우스 랜덤 변수라고 가정하고 $신호{\displaystyle }$ X$(\displaystyle$ X$)$의 연속 샘플이 확률적으로 독립적이라고 가정하면(또는 동등하게 소스가 메모리리스이거나 신호가 상관 없음) 다음 ana를 찾을 수 있습니다.속도 왜곡 함수의 용리식:

${\displaystyle R(D)=begin{1}{2}}\log _{2}(\frac_{x}^{2}/D),& {\text{leq D\leq\f}{2}\sigma_{x}^{2}/D}.\end {case}}$ ^{[2]: 310}

다음 그림은 이 함수의 모양을 보여줍니다.

속도-왜곡 이론은 '회색 영역 밖에서 작동하는 압축 시스템이 존재하지 않는다'고 말합니다.실용적인 압축 시스템이 빨간색(하위) 경계에 가까울수록 성능이 향상됩니다.일반적으로 이 경계는 부호화 블록 길이 파라미터를 증가시키는 경우에만 얻을 수 있습니다.그럼에도 불구하고, 단위 블록 길이에서도 실질적으로 관련이 ^[2]있는 속도 왜곡 함수와의 거리에서 작동하는 좋은 (스칼라) 정량자를 찾을 수 있다.

이 속도 왜곡 함수는 가우스 메모리리스 소스에 대해서만 유지됩니다.가우스 소스는 인코딩이 가장 "어려운" 소스인 것으로 알려져 있습니다. 즉, 주어진 평균 제곱 오차의 경우 가장 많은 수의 비트가 필요합니다.예를 들어 이미지에서 작동하는 실용적인 압축 시스템의 성능은 표시된 R$)\$ R$\left(D\right)$ 하한$$ $이하일{\displaystyle }$ 수 있습니다.

Hamming 왜곡이 있는 메모리리스(독립형) 베르누이 소스

해밍 왜곡이 있는 베르누이 랜덤 변수의 속도 왜곡 함수는 다음과 같습니다.

${\displaystyle R(D)=\left\{\begin{행렬}H_{b}(p)-H_{b}(D),&0\leq D\leq \min {(p,1-p)}\\0,&D>\min {(p,1-p)}\end {matrix}\right.}$

${\displaystyle {여기}_{}}$서 H b$(\$는 이진 엔트로피 함수를 나타냅니다.

p ${\displaystyle =0}$.5 {$displaystyle$ p$=0.$5$\}$에 $대한{\displaystyle }$ 속도 왜곡 함수 그림:

채널 용량에 대한 환율 왜곡 이론 연결

D를 넘지 않는 왜곡으로 소스에 관한 정보를 사용자에게 송신한다고 가정합니다.Rate–distortion theory tells us that at least ${\displaystyle R(D)}$ bits/symbol of information from the source must reach the user.또한 Shannon의 채널 코딩 정리를 통해 소스 엔트로피가 H비트/심볼이고 채널 용량이 C서 C< $H$ \ $displaystyle$C <$H$ \ H ） )인 경우 이 정보를 지정된 채널로 전송할${\displaystyle }$때 ${\displaystyle H}$ -$$C \ $displaystyle H-C$}비트/심볼이 손실된다는 것을 알 수 있습니다.사용자가 최대 왜곡 D로 재구성을 희망하려면 전송 중에 손실된 정보가${\displaystyle }$H -${\displaystyle R}$ (${\displaystyle D}$) \ $displaystyle$H - R ( $D$) } bits$$ / symbol의 $최대{\displaystyle }$ 허용 손실을 초과하지 않도록 해야 합니다.즉, 채널 용량은 ${\displaystyle \mathrm{적어도}}$R (${\displaystyle }$D $)\displaystyle$ R$(D$$만큼{\displaystyle }$ 커야 합니다.

「 」를 참조해 주세요.

• 장식 관계
• 환율 왜곡 최적화
• 소스 코딩
• 구면 패킹
• 화이트닝
• 블라후트-아리모토 알고리즘

레퍼런스

외부 링크

• PyRated: 속도 왜곡 이론의 기본 계산을 위한 Python 코드.
• VcDemo 이미지 및 비디오 압축 학습 도구