JPEG의 DHT에는 실제 허프만 코드가 들어 있지 않습니다. 어떻게됩니까?

Question

DHT에는 1 비트에서 16 비트까지 각 길이의 허프만 코드로 인코딩 된 값의 개수가 포함 된 16 바이트가 포함되어 있습니다. 그런 다음 인코딩 된 실제 값을 포함하며이 값은 모두 8 비트 크기입니다.

Q : 왜 huffman 코드가 저장되어 있지 않은가, 디코더가 코드를 어떻게 파생 시키나요?

Q : 3 비트 길이의 허프만 코드가있는 4 개의 값이 있으면 4 바이트로 기록해야합니다. 그들이 어떤 순서로 존재하는지 또는 오름차순 또는 내림차순으로 있어야하는지가 중요합니까? 그 값들이 1 비트 허프만 코드를 갖는 값들에 2 비트 허프만 코드 e.t.c를 갖는 값들이 뒤따라 오도록 그 값들이 순서대로되어야한다는 것을 알 수있다.

Q : 저는 jpegsnoop을 사용하여 다른 파일의 huffman 테이블을 보았습니다. 일부는 MS 페인트로 만들어졌으며 일부는 다운로드되었습니다. 나는 그들이 모두 같은 테이블을 가지고있는 것을 발견했다. 여기

내가 JPEG의 스눕에서받은 DHT 항목은 다음과 같습니다

Destination ID = 1 
    Class = 1 (AC Table) 
    Codes of length 01 bits (000 total): 
    Codes of length 02 bits (002 total): 00 01 
    Codes of length 03 bits (001 total): 02 
    Codes of length 04 bits (002 total): 03 11 
    Codes of length 05 bits (004 total): 04 05 21 31 
    Codes of length 06 bits (004 total): 06 12 41 51 
    Codes of length 07 bits (003 total): 07 61 71 
    Codes of length 08 bits (004 total): 13 22 32 81 
    Codes of length 09 bits (007 total): 08 14 42 91 A1 B1 C1 
    Codes of length 10 bits (005 total): 09 23 33 52 F0 
    Codes of length 11 bits (004 total): 15 62 72 D1 
    Codes of length 12 bits (004 total): 0A 16 24 34 
    Codes of length 13 bits (000 total): 
    Codes of length 14 bits (001 total): E1 
    Codes of length 15 bits (002 total): 25 F1 
    Codes of length 16 bits (119 total): 17 18 19 1A 26 27 28 29 2A 35 36 37 38 39 3A 43 
             44 45 46 47 48 49 4A 53 54 55 56 57 58 59 5A 63 
             64 65 66 67 68 69 6A 73 74 75 76 77 78 79 7A 82 
             83 84 85 86 87 88 89 8A 92 93 94 95 96 97 98 99 
             9A A2 A3 A4 A5 A6 A7 A8 A9 AA B2 B3 B4 B5 B6 B7 
             B8 B9 BA C2 C3 C4 C5 C6 C7 C8 C9 CA D2 D3 D4 D5 
             D6 D7 D8 D9 DA E2 E3 E4 E5 E6 E7 E8 E9 EA F2 F3 
             F4 F5 F6 F7 F8 F9 FA 
    Total number of codes: 162 

그리고

Destination ID = 1 
    Class = 0 (DC/Lossless Table) 
    Codes of length 01 bits (000 total): 
    Codes of length 02 bits (003 total): 00 01 02 
    Codes of length 03 bits (001 total): 03 
    Codes of length 04 bits (001 total): 04 
    Codes of length 05 bits (001 total): 05 
    Codes of length 06 bits (001 total): 06 
    Codes of length 07 bits (001 total): 07 
    Codes of length 08 bits (001 total): 08 
    Codes of length 09 bits (001 total): 09 
    Codes of length 10 bits (001 total): 0A 
    Codes of length 11 bits (001 total): 0B 
    Codes of length 12 bits (000 total): 
    Codes of length 13 bits (000 total): 
    Codes of length 14 bits (000 total): 
    Codes of length 15 bits (000 total): 
    Codes of length 16 bits (000 total): 
    Total number of codes: 012 

교류 테이블이 제로 런 길이와 AC 계수의 크기를 포함 RRRRSSSS를 압축 직류 표를 압축하는 동안 SSSS. 따라서 AC 테이블에는 총 255 개의 항목 (exlcuded 0)이 있어야하며 DC 테이블은 15 개의 항목 (0은 제외)이어야합니다. 그러나 어느 테이블도이 많은 수의 코드를 포함하지 않습니다. 왜?

Answer 1

허프만 인코딩은 거의 모든 256 심볼의 상대 빈도에 의해 결정됩니다 (타이 브레이커 규칙 제외). 즉, 상대 주파수를 인코딩 할 수있는 많은 형식을 선택할 수 있습니다. 가장 단순한 것은이 모든 주파수를 저장하는 것입니다. 그러면 수신기는 해당 순서에서 인코딩을 다시 작성할 수 있습니다.

배경 : 허프만 인코딩의 두 가지 최소 문자는 동일한 (긴) 접두사를 공유하며 마지막 비트 만 다릅니다. 그런 다음이 조합에 공동 주파수 (두 조합의 합)가 할당되며이 주파수는 접두사를 결정하기 위해 재귀 적으로 사용됩니다. 마지막으로 X 문자를 포함하고 다른 문자는 256-X 문자를 포함하는 두 세트로 끝납니다. 첫 번째 집합은 접두사 0이고 두 번째 집합은 접두사 1입니다.

네, 그건 0과 1을 바꿀 수 있고 비슷한 테이블과 압축률을 가질 수 있습니다 - 0은 하나. 그래서 규칙을 자세히 세우는 것입니다 (예 : 가장 일반적인 세트는 0, 타이 브레이커는 세트의 첫 번째 바이트 임).

인코딩으로 돌아 가기. 우리는 여기서 압축을 사용하기 때문에 이러한 상대적 주파수를 효율적으로 저장하려고합니다. 이제 제가 지적했듯이, 코드 접미사 -0과 접미어 -1이있을 때, 둘 다 똑같이 길어집니다 (즉, 접미사 길이 + 1). 그래서 우리는 119 개의 고유 16 비트 코드가 있다는 것을 알고 있습니다. 길이가 15 인 60 개의 고유 한 접두어가 있습니다. 역방향을 계산하면 길이가 15이고 총합이 62 인 두 개의 고유 한 기호가 있다는 것을 알 수 있습니다. 따라서 31 개의 접두사가 있어야합니다 길이 14의 접두어로 다시 되돌릴 수 있습니다.

다시 말하면, 접두어의 정확한 값과 일치하는 기호는 여기에서 알 수 없다는 것을 지적해야합니다. 이는 타이 브레이커 규칙에 따라 다르지만 이러한 규칙은 JPEG로 고정되어 있습니다.

JPEG에는 매우 드문 기호 인 호프만 코드 이 있어야합니다.은 16 비트보다 길어야합니다.그렇게하는 것이 불편합니다. 따라서 테이블을 만들 때 둘 중 가장 긴 결합 수를 가진 두 세트를 선택하지 마십시오.이 두 세트를 결합하면 접미사가 더 길어집니다. 예제에서 모든 16 비트 코드와 함께 이것을 볼 수 있습니다. 대부분은 순수한 허프만 인코딩에서 더 긴 코드를 가져야합니다.

가장 자주 발생하는 문자가 50 %, 다음 25 % 등으로 나타나는 경우 최악의 경우라고 생각합니다. 코드 0, 10, 110, 1110 등이 표시됩니다. 이것은 단항 계산이며, 실제로는이 경우에 가장 적합하지만, 가장 긴 코드는 이제 256 비트입니다. 2^-256의 빈도를 가지려면 2^256 바이트의 문서가 필요합니다.

Answer 2

Q : 왜 huffman 코드가 저장되어 있지 않은지, 디코더가 코드를 어떻게 파생 시키나요?

허프만 테이블이 실제 코드가 아닌 정의 된 이유는 인코딩 방식이 훨씬 작고 간단하다는 것입니다. PNG는 비슷하지만 다른 방법을 사용합니다.

허프 먼 코드를 JPEG 스트림에 저장하려면 길이와 코드 자체를 모두 포함해야합니다. 결과는 길이의 수를 인코딩하는 것보다 훨씬 더 커집니다.

Q : 3 비트 길이의 허프만 코드를 갖는 4 개의 값이있는 경우, 4 바이트로 기록해야합니다. 그들이 어떤 순서로 존재하는지 또는 오름차순 또는 내림차순으로 있어야하는지가 중요합니까?

허프만 코드가 3 비트 인 경우 JPEG 스트림에 3 비트로 기록됩니다. 코드는 오름차순으로 생성됩니다.

Q : jpegsnoop을 사용하여 다른 파일의 huffman 테이블을 보았습니다. 일부는 MS 페인트로 만들어졌으며 일부는 다운로드되었습니다. 나는 그들이 모두 같은 테이블을 가지고있는 것을 발견했다.

인코더가 게으르고 고정 된 허프만 테이블을 사용 중입니다. 그들이 자주 사용하는 JPEG 표준 샘플 허프만 테이블이 있습니다. 최적의 허프만 코드를 생성하려면 인코더가 데이터를 두 번 통과해야합니다. 프리셋 테이블을 사용하면 엔코더가 한 번만 통과하면됩니다.