Wavelet 변환의 내장 제로 트리

Embedded Zerotrees of Wavelet transforms

Embedded Zerotree of Wavelet Transforms(EZW)는 손실 이미지 압축 알고리즘입니다.낮은 비트 전송률, 즉 높은 압축률에서는 서브밴드 변환(웨이브릿 변환 등)에 의해 생성되는 계수의 대부분은 0이거나 0에 매우 근접합니다.이는 "실제" 영상이 대부분 저주파수 정보(상관성이 높음)를 포함하는 경향이 있기 때문에 발생합니다.그러나 고주파수 정보(예: 영상의 가장자리)가 발생하는 경우 이는 특히 영상 품질에 대한 인간의 인식 측면에서 중요하므로 고품질 코딩 체계에서 정확하게 표현해야 합니다.

변환된 계수를 루트 노드에서 가장 낮은 주파수 계수를 갖는 트리(또는 트리)로 간주하고 각 트리 노드의 자녀가 다음 고주파 서브밴드에서 공간적으로 관련된 계수인 경우 하나 이상의 서브트리가 모두 0 또는 0인 계수로 구성될 가능성이 높다.거의 0에 가까운 서브트리를 제로트리라고 부릅니다.따라서 우리는 노드와 계수를 서로 바꿔서 사용하며, 계수의 하위 계수를 언급할 때는 해당 계수가 위치한 트리의 노드의 하위 계수를 의미합니다.트리의 하부에 직접 연결된 노드를 참조할 때 하위 노드를 참조할 때 하위 노드를 참조할 때 직접 연결되지 않더라도 트리의 특정 노드 아래에 있는 모든 노드를 참조할 때 사용합니다.

EZW 및 SPIHT와 같은 제로트리 기반 이미지 압축 방식에서는 중요한 계수의 위치를 효율적으로 코드화하기 위해 트리의 통계 특성을 사용하는 것이 목적입니다.대부분의 계수는 0이거나 0에 가깝기 때문에 유의한 계수의 공간적 위치는 일반적인 압축 영상의 전체 크기에서 큰 부분을 차지합니다.계수(나무와 마찬가지로)는 그 크기(또는 나무의 경우 노드 및 그 모든 하위의 크기)가 특정 임계값보다 높은 경우 유의한 것으로 간주됩니다.최대계수 크기에 가까운 문턱값부터 시작하여 문턱값을 반복 감소시킴으로써 점차 세밀함을 더하는 화상의 압축표현을 작성할 수 있다.트리의 구조상 특정 주파수 대역의 계수가 미미한 경우 그 모든 하위(공간적으로 관련된 고주파수 대역 계수)도 미미한 것이 될 가능성이 매우 높습니다.

EZW는 (a) 제로트리 루트, (b) 고립 제로(미미한, 그러나 유의한 후손을 갖는 계수), (c) 유의한 양의 계수 및 (d) 유의한 음의 계수를 나타내기 위해 4개의 기호를 사용한다.따라서 두 개의 이진 비트로 기호를 나타낼 수 있습니다.압축 알고리즘은 우위 패스와 하위 패스를 통한 여러 번의 반복으로 구성되며, 반복할 때마다 임계값이 업데이트됩니다(2배 감소).지배 패스는 트리를 스캔하고 네 가지 기호 중 하나를 방출함으로써 이전의 반복에서 아직 유의하게 발견되지 않은 계수의 중요성을 부호화한다.계수의 하위 항목은 계수가 유의한 것으로 확인되거나 계수가 고립된 0인 경우에만 스캔됩니다.하위 패스는 이전 유의 패스에서 유의한 것으로 확인된 각 계수에 대해 1비트(지금까지 방출되지 않은 각 계수의 가장 유의한 비트)를 방출합니다.따라서 하위 패스는 비트플레인 코딩과 비슷합니다.

주의해야 할 몇 가지 중요한 기능이 있습니다.우선, 압축 알고리즘을 언제라도 정지해, 원래의 화상의 근사치를 얻을 수 있기 때문에, 수신한 비트수가 많을수록 화상이 좋다.둘째, 압축 알고리즘이 일련의 결정으로 구조화되는 방식에 따라 동일한 알고리즘을 디코더에서 실행하여 계수를 재구성할 수 있지만, 그 결정은 착신 비트 스트림에 따라 이루어진다.실제 구현에서는 우세 패스의 성능을 더욱 향상시키기 위해 산술 코드와 같은 엔트로피 코드를 사용하는 것이 일반적입니다.하위 패스로부터의 비트는 일반적으로 엔트로피 부호화가 더 이상의 부호화 이득을 제공하지 않을 정도로 랜덤합니다.

이후 EZW의 코딩 성능은 SPIHT와 그 많은 파생 모델에 의해 능가되고 있습니다.

서론

1993년 J. Shapiro에 의해 개발된 임베디드 제로트리 웨이브릿 알고리즘(EZW)은 확장 가능한 이미지 전송 및 디코딩을 가능하게 합니다.그것은 네 가지 핵심 개념에 기초한다. 첫째, 이산 웨이브릿 변환 또는 계층적 서브밴드 분해여야 한다. 둘째, 이미지에 내재된 자기 유사성을 탐색할 때 중요한 정보의 부재를 예측해야 한다. 셋째, 엔트로피 코딩된 연속 근사 양자화를 가지고 있으며 넷째, 미완료화를 달성할 수 있다.적응형 산술 부호화를 통한 iversal 무손실 데이터 압축.

또한 EZW 알고리즘에는 다음 기능도 포함되어 있습니다.

(1) 화상 중의 콤팩트한 다해상도 표현을 사용할 수 있는 이산 웨이브릿 변환.

(2) 중요도 맵의 콤팩트한 다중 해상도 표현을 제공하는 제로트리 부호화.

(3) 유의한 계수의 콤팩트한 다중 정밀도 표현을 위한 순차적 근사치.

(4) 웨이브릿 계수의 정밀도, 규모, 규모 및 공간적 위치에 따라 중요도가 결정되는 우선순위 부여 프로토콜.

(5) 심볼의 엔트로피 문자열을 빠르고 효율적으로 부호화하는 적응형 다단계 연산 부호화.

임베디드 제로트리 웨이브릿 코딩

A. 중요도 맵의 계수 부호화

유의성 지도에서 계수는 다음과 같은 네 가지 다른 기호로 나타낼 수 있습니다.이러한 기호를 사용하여 이미지 정보를 표시하면 코딩이 덜 복잡해집니다.

1. 제로트리 뿌리

계수의 크기가 임계값 T보다 작고 모든 하위 계수가 T보다 작으면 이 계수를 제로트리 루트라고 합니다.또한 계수에 제로트리 루트로 라벨이 붙여진 경우 그 모든 하위 계수가 중요하지 않으므로 하위 계수에 라벨을 붙일 필요가 없습니다.

2. 고립 영점

분계점 T보다 작지만 유의한 후손이 있는 계수의 크기가 여전히 있으면 이 계수를 고립된 0이라고 합니다.

3. 양의 유의계수

계수의 크기가 수준 T에서 임계값 T보다 크고 양수이면 양의 유의 계수입니다.

4. 음의 유의계수

계수의 크기가 수준 T에서 임계값 T보다 크고 음수이면 음의 유의 계수입니다.

B. 임계값의 정의

위의 문턱값을 사용하는 문턱값은 다음과 같이 정의할 수 있습니다.

1. 초기 임계값0 T: (C가max 가장 큰 계수라고 가정합니다.)

Threshold-0119.png

2. 임계값i T는 이전 임계값의 절반으로 감소합니다.

Threshold-01192.png

다. 계수의 스캔 순서

래스터 스캔은 이미지 캡처 및 재구성의 직사각형 패턴입니다.EZW 트랜스폼에서 이 스캔을 사용하는 것은 부모 노드보다 먼저 자식 노드가 스캔되지 않도록 계수를 스캔하는 것입니다.또, 소정의 서브밴드내의 모든 위치가 스캔 되어 다음 서브밴드로 이행합니다.

D. 2패스 비트플레인 부호화

(1) 정제 패스(또는 하위 패스)

이를 통해 계수가 [Ti, 2Ti] 구간 내에 있는지 여부가 결정됩니다.그리고 각 유의한 계수에 대해 정제 비트가 부호화됩니다.

이 방법에서는 서브밴드 내의 크기 및 래스터 순서에 따라 유의한 계수를 방문합니다.

(2) 유의 패스(또는 우세 패스)

이 방법은 아직 유의하지 않은 각 계수에 대해 비트를 코드화합니다.일단 중요성의 결정이 이루어지면, 유의한 계수는 정제 통과의 추가적인 개선을 위해 목록에 포함된다.그리고 이미 0으로 알려진 계수는 다시 코드화되지 않습니다.

「 」를 참조해 주세요.

  • 계층 트리로 파티션 설정(SPIHT)

레퍼런스

  • J.M. Shapiro (1993). "Embedded image coding using zerotrees of wavelet coefficients". IEEE Transactions on Signal Processing. 41 (12): 3445–3462. CiteSeerX 10.1.1.131.5757. doi:10.1109/78.258085. ISSN 1053-587X. S2CID 18047405. Zbl 0841.94020. Wikidata Q56883112.

외부 링크

Wikimedia Commons에는 EZW 관련 미디어가 있습니다.