|
3 - Codifica di sorgente |
97 |
- Passo 1 - Dato un vocabolario iniziale Co di dimensione N e con vettori di lunghezza k, una soglia di distorsione e > 0 piccola a piacere, una funzione di distribuzione statistica della sorgente (o alternativamente una sequenza di addestramento sufficientemente lunga), si inizializza l’algoritmo con m= 0 (indice delle iterazioni) e D-i = °° (distorsione media alla iterazione 1 ).
- Passo 2 - Dato il vocabolario corrente Cm = (Y(i); i = 1,2.N), si applica il primo criterio di ottimalità calcolando la partizione ottima Pm(Cm) = {pi; i= 1, 2,.... N}. Si calcola quindi la distorsione media D m = D(Pm(C m ), C m ) associata alla partizione ottima P m ed al vocabolario corrente Cm.
- Passo 3 - Qualora la distorsione media sia diminuita percentualmente di una quantità inferiore ad e nel passare dall'iterazione m -1 all'iterazione m e cioè in formule se
|
|
|
(3.52)
|
l’algoritmo termina con C m vocabolario finale, altrimenti l’algoritmo continua con il passo 4.
- Passo 4 - Data la partizione ottima P m calcolata al passo 2, si applica il secondo criterio di ottimalità calcolando il nuovo vocabolario Cm+l = { Y(sj); i = 1, 2,N} come collezione dei centroidi di ogni cluster pi. Si incrementa m e si ritorna al passo 2.
Il valore della distorsione media può essere calcolato come media di insieme, qualora si disponga della funzione di distribuzione statistica del segnale sorgente, o come media nel tempo qualora si disponga di una sequenza di addestramento sufficientemente lunga. Dalle due condizioni di ottimalità prima descritte, si evince che D m < D m -1 e quindi l’algoritmo converge ad un valore minimo seppur con un numero di iterazioni che può essere infinito.
Linde, Buzo e Gray hanno dimostrato [Lin80] che il loro algoritmo tende a produrre un quantizzatore ottimo, se questo esiste, attraverso un metodo di successive approssimazioni, pertanto se l’algoritmo termina con un valore di e = 0 in un numero finito di iterazioni, tale quantizzatore limite risulta determinato.
