Cosa devo fare quando uso il codice Golomb / Rice per valori elevati?

Question

Cosa devo fare quando uso il codice Golomb / Rice per valori elevati?

#1 da (2 voti)
#2 da (0 voti)

2

Quando usi il codice Golomb / Rice nella compressione dell'immagine, è inevitabile per noi soddisfare grandi valori. La codifica di Golomb utilizza un parametro sintonizzabile M per dividere un valore di input N in due parti: q, il risultato di una divisione per M e r, il resto. Il quoziente viene inviato in codice unario, seguito dal resto in binario.

Ad esempio, se N è 120, e M è 4, allora q è 30 (in unario 111 ..... 1111110, 31bits), r è 0. Quindi il risultato è 33 bit. Non è pratico nell'uso della compressione dell'immagine.

Quindi cosa dovrei fare quando uso il codice Golomb / Rice per grandi valori? O ha qualche regola per grandi valori?

compression

posta dongbao wu 11.01.2015 - 09:52

fonte

2 risposte

Leggi altre domande sui tag compression

Costruttore punto di ingresso vs init (), run () ecc Al volo, partizione casuale di un intervallo di numeri [0, N] in gruppi di dimensione M massima

score 2 · Answer 1

Non capisco perché "33 bit non è pratico". Ci sono due risposte a questo a seconda di cosa intendi:

L'intero punto di questo tipo di codifica è ottimizzare rappresentazione dei piccoli valori a scapito di valori elevati. Supponendo un'adeguata distribuzione di numeri con cui essere compressi molti più piccoli valori rispetto ai valori più grandi, ci dovrebbe essere meno bit necessari per la rappresentazione codificata complessiva. Si noti che per l'immagine compressione, questo tipo di schema viene generalmente utilizzato per codificare gli errori da un valore di pixel previsto , non i valori dei pixel stessi.
Se ti riferisci ad alcuni problemi dovuti a una dimensione intera di 32 bit nella lingua che stai utilizzando, trovo che sia abbastanza importante / utile avere una classe bitvector di lunghezza arbitraria per questo tipo di cose ( boost's dynamic_bitset per esempio).

score 0 · Answer 2

Golomb-Codes e Rice-Codes sono efficienti solo se i simboli che vuoi codificare hanno una distribuzione geometrica o una distribuzione quasi geometrica. (d (n) = (1-p) p ⁿ). Questo è un codice che può codificare anche valori infiniti, ma il simbolo codificato cresce di dimensioni quando è più lontano da 0, poiché sono meno probabili dei valori vicini a 0. Questo è il motivo per cui si spendono più bit su simboli meno probabili e pochi bit su molto simboli probabili.

Un codice Golomb è un codice di lunghezza variabile. Dove ogni simbolo può essere codificato su una base diversa. Meno è probabile, più lunga è la codifica. Ogni simbolo è codificato da più bit e si scrive la codifica bit per bit, indipendentemente dal fatto che si sia verificato un vincolo magico a 8, 16, 32 o 64 bit. Il codice non è inteso per essere letto / scritto byte, word, int o long, questo è quello che fai, quando scrivi i dati codificati sul disco. Se devi spendere 33 bit per un dato simbolo, devi spenderlo, altrimenti il codice non è reversibile. Ma devi leggere o scrivere bit per bit.

Nel tuo esempio il valore 120 creerebbe un prefisso a 31 bit e alcuni extra 2 per il codice. Ma d'altra parte 120 è 2 ^-30 volte meno probabile di 0. Quindi è completamente perfetto per spendere questo "molto" bit per esso.

La selezione della M ottimale dipende dalla distribuzione data. Golomb-Coding e Rice-Coding (che è un caso speciale della codifica di Golomb) sono usati nella compressione delle immagini e nella compressione video, perché è facile da implementare e veloce nell'elaborazione.