Xem mẫu
- for(i=0;i10.0) delta=2.0;
else delta=0.1;
di=ri_1+delta;
i=0;
/* Using Newton-Raphson's method for root
finding. */
while(fabs(delta)>=EPS)
{
i++;
if(i>=1000)
{
381
- printf("\n no convergence.\n");
return di;
}
area1=Romberg(di-1,di,f1);
area2=Romberg(di-1,di,f2);
ff=area1/area2;
fun=(ri_1)-ff;
if(fabs(area2)
- /* -----------------------------
Numerical integration using
Romberg method.
---------------------------- */
double Romberg(double di_1,double di,double
(*f)(double))
{
double T[10][10],h,x,Area;
int N,k,kk,i,j;
N=9;
k=1 ;
h=di- di_1;
T[0][0]=h*((*f)(di_1)+(*f)(di))/2.0;
for(i=1;i
- 2. Víi mçi lùa chän sè bit ta chän:
Gauss.
§ång ®Òu.
Laplace.
3. C¸c møc lîng tö cã thÓ dïng cho thiÕt kÕ cã trªn ®Üa, vÝ dô dïng
Q3G.DAT cho lîng tö 3 bit dïng lîng tö Gauss, Q4L.DAT cho 4 bit
lîng tö Laplace.
Ph¬ng ph¸p Lloyd Lloyd còng ®a ra mét ph¬ng ph¸p thø hai cho
phÐp x¸c ®Þnh c¸c møc lîng tö mµ «ng gäi lµ ph¬ng ph¸p Lloyd I.
Ph¬ng ph¸p nµy cã nhiÒu u ®iÓm h¬n ph¬ng ph¸p II (gi¶i thuËt Lloyd-
Max), v× nã dÔ dµng cho tÝnh to¸n vµ c¸c vector lîng tö ho¸ cã thÓ më
réng. Chó ý lµ vÊn ®Ò mµ chóng ta quan t©m ë ®©y lµ kho¶ng c¸ch lîng
tö ho¸, lîng tö ho¸ cña hµm mét biÕn ®· biÕt ®îc ph©n t¸n. Vector
lîng tö ho¸ lµ mét vector cña nhiÒu biÕn mµ víi c¸c biÕn nµy ta ®· biÕt
®îc ph©n t¸n.
ThuËt to¸n Lloyd theo c¸c bíc sau:
1. Rót ra íc lîng cho ph¹m vi cña c¸c biÕn
di {i = 0, 1, 2, ..., N}
(Mét íc lîng cã thÓ rót ra b»ng c¸ch dïng c¸c gi¸ trÞ tõ lîng tö ho¸
®ång ®Òu hoÆc tõ c¸c møc lîng tö tríc mµ ta cÇn mét kÕt qu¶ tèt h¬n).
2. §Æt mét biÕn D1= 0. D1 dïng ®Ó lu l¹i t×nh tr¹ng kh«ng chÝnh x¸c
lóc tríc.
3. TÝnh
d i1
yp ( y )dy
di
r
i d i 1
p ( y)dy
di
i = 0, 1, ..., N - 1.
4. TÝnh
ri ri 1
di
2
i = 0, 1, ..., N - 1
5. TÝnh t×nh tr¹ng kh«ng chÝnh x¸c
N 1d k 1
( y rk ) 2 p( y )dy
D2
k 0 d k
Cã thÓ dÔ dµng më réng biÓu thøc tr¹ng th¸i kh«ng chÝnh x¸c theo
384
- N 1 d k 1 d k 1 d k 1
d p ( y )dy
y 2 p ( y) 2rk yp ( y ) dy rk2 (13.58)
D
dk dk
k
k 0
6. NÕu
D2 D1
D1
th× mét gi¶i ph¸p ®· ®îc t×m ra. Lu l¹i kÕt qu¶ vµ tho¸t khái ch¬ng
tr×nh.
7. §Æt D1 = D2
8. Quay l¹i bíc 3.
Mét ch¬ng tr×nh C cho gi¶i thuËt trªn ®îc ®Ò cËp ®Õn ë díi ®©y.
Ch¬ng tr×nh 13.10 LLOYDQ.C ThuËt to¸n Lloyd cho viÖc
thiÕt kÕ c¸c møc lîng tö.
/*Program13.10 "LLOYDO.C".Lloyd algorithm for
quantizer design.*/
/* Program for designing the Lloyd-quantizer
for a Gauss, uniform or Laplace
distribution.*/
#include
#include
#include
#include
#include
double decision_level(double, double);
double f1(double);
double f2(double);
double f3(double);
double p(double);
double Romberg(double, double, double
(*)(double));
char ch;
void main( )
{
double *r,*d,step,sum,I1,I2,I3,D1,D2;
385
- int i,j,m,N,xt,yt,niter,ind;
char file_name[16],ch1;
FILE *fptr;
clrscr( ) ;
printf("Enter number of bits--->");
scanf("%d",&m);
printf("Enter number of iterations-->");
scanf("%d",&niter);
N=1
- fscanf(fptr,"%f %f ",&d[i],&r[i]);
d[N]=20.0;
fclose(fptr);
break;
}
case 'n':
d[N]=20.0;
d[0]=-20.0;
if(ch=='2')
{d[N]=1.0; d[0]=-1.0;}
step=(d[N]-d[0])/(float)N;
for(i=1;i
- switch(ch)
{
case '1':
case '3':
printf("\n\n -%c %9.6f ",(char)236,r[0]);
break;
case '2':
printf("\n\n %9.6f %9.6f ", d[0], r[0]);
}
for(i=1; i
- break;
}
return prob;
}
/* -------------------------
functions used by numerical integration routine.
-------------------------------- */
double f1(double y)
{
return (y*(p(y)));
}
double f2(double y)
{
return p(y);
}
double f3(double y)
{
return y*y*p(y);
}
Bµi tËp 13.10
1. Lµm l¹i bµi tËp 13.8 nhng lÇn nµy dïng ch¬ng tr×nh 13.10 cho
gi¶i thuËt Lloyd.
2. So s¸nh thêi gian tÝnh to¸n khi dïng gi¶i thuËt Lloyd-Max vµ khi
dïng gi¶i thuËt Lloyd.
Tõ biÓu thøc (13.52) vµ (13.58) chóng ta cã thÓ ph¸t triÓn mét ch¬ng
tr×nh cho t×nh tr¹ng mÐo tèi thiÓu:
N 1 d k 1 d k 1
d p ( y) dy
y 2 p ( y ) dy rk2 (13.59)
Dmin
dk
k
k 0
13.6 Lîng tö ho¸ c¸c hÖ sè cña FCT
Trong phÇn 13.4 chóng ta ®· b¾t ®Çu vÊn ®Ò cña biÕn ®æi cho m· ho¸.
Ph¬ng ph¸p chóng ta ¸p dông lµ chia ¶nh thµnh c¸c khèi h×nh vu«ng;
mçi khèi cã kÝch thíc 8 8 vµ 16 16. BiÕn ®æi cosin nhanh cho mçi
khèi nµy ®· ®îc rót ra. Chóng ta nhËn thÊy r»ng hÇu hÕt c¸c hÖ sè nµy
cã biªn ®é rÊt nhá so víi c¸c gi¸ trÞ xung quanh khèi (mét chiÒu) DC.
389
- C©u hái ®Æt ra lóc nµy lµ c¸c hÖ sè nµo chóng ta cÇn lu gi÷ vµ b»ng
ph¬ng ph¸p nµo chóng ta cã thÓ lu gi÷ tèt nhÊt c¸c gi¸ trÞ nµy? C©u tr¶
lêi cho vÊn ®Ò nµy cã thÓ t×m thÊy trong phÇn lîng tö ho¸ mµ chóng ta
®· nghiªn cøu ë trªn.
Chó ý lµ c¸c hÖ sè cña FCT x¸c ®Þnh mét d¹ng biÕn d¹ng. Cho vÝ dô,
mét ¶nh cã 256 256 ®iÓm vµ kÝch thíc cña c¸c khèi lµ 8 8 ®iÓm, cã
tÊt c¶ 64 hÖ sè cho mçi khèi vµ 32 32 khèi. Mçi hÖ sè cã 1024 gi¸ trÞ
khi chóng ta xem xÐt tÊt c¶ c¸c khèi, vµ t¹o nªn mét biÕn d¹ng riªng.
§¸nh gi¸ biÕn d¹ng cho hÖ sè thø j cã thÓ cho bëi
d
N J 1 k 1 j
(y r (13.60)
Dj ) p j ( y)dy
k, j
k 0 d k
j
j = 0, 1, 2, ..., L - 1.
ë ®©y L lµ sè c¸c hÖ sè cho mét khèi vµ Nj sè c¸c møc lîng tö cho hÖ sè
j. Tæng sè c¸c biÕn d¹ng sÏ lµ
L 1
D Dj (13.61)
j 0
Lµm theo c¸c bíc trong phÇn 13.5 chóng ta ®îc
d k 1 j
yp j ( y)dy
dk j
(13.62)
rk , j d k 1, j
p j ( y ) dy
d kj
rk , j rk 1, j
vµ (13.63)
d k, j
2
NÕu chóng ta coi r»ng bÊt kú hÖ sè nµo cã thÓ x¸c ®Þnh b»ng cïng mét
hµm kh¶ n¨ng xuÊt hiÖn ®é s¸ng, th× thay thÕ gi¸ trÞ c¸c hÖ sè nµy (mµ
®îc biÓu diÔn trong biÓu thøc trªn lµ y) b»ng
y j
(13.64)
j
Chóng ta sÏ cho tÊt c¶ c¸c hÖ sè víi c¸c ph©n bè xuÊt hiÖn gièng nhau,
víi gi¸ trÞ trung b×nh vµ chuÈn cña ®é lÖch cho bëi = 0 vµ = 1. KÕt
qu¶ sau khi tÝnh to¸n cho ta c¸c møc chia vµ c¸c møc kh«i phôc cho tÊt
c¶ hÖ sè “chia”. §iÒu nµy tÊt nhiªn chØ ¸p dông víi ®iÒu kiÖn lµ c¸c hÖ sè
cã cïng mét sè c¸c bit. Tríc khi ®a ra c¸c møc lîng tö chóng ta cã
thÓ bá bít mét sè hÖ sè. NÕu hÖ sè (0, 0) hay cßn gäi lµ thµnh phÇn mét
390
- chiÒu DC biÓu diÔn cho gi¸ trÞ trung b×nh cña ®é s¸ng cña mét khèi,
chóng ta kh«ng thÓ bá ®iÓm nµy ®i ®îc. C¸c hÖ sè kh¸c trong mét khèi
(cßn gäi lµ c¸c hÖ sè xoay chiÒu AC) mang c¸c th«ng tin vÒ c¸c chi tiÕt
cña ¶nh. Cã thÓ nhËn thÊy lµ c¸c chi tiÕt cã ®é lÖch lín h¬n ®é lÖch chuÈn
th× mang nhiÒu tin tøc h¬n c¸c chi tiÕt cã ®é lÖch Ýt h¬n ®é lÖch chuÈn. V×
vËy mµ chóng ta b¾t ®Çu lîc bá c¸c hÖ sè b¾t ®Çu tõ vïng cã tr¶i réng Ýt
nhÊt. VËy bao nhiªu hÖ sè sÏ ®îc chóng ta gi÷ l¹i? §iÒu nµy phô thuéc
vµo møc ®é mµ chóng ta muèn nÐn ¶nh vµ phô thuéc vµo bao nhiªu c¸c
chi tiÕt bÞ mÊt trªn ¶nh mµ chóng ta cã thÓ chÊp nhËn ®îc.
Dùa trªn c¸c gi¶ thiÕt trªn chóng ta cã thÓ ph¸t triÓn mét thuËt to¸n
cho nÐn ¶nh vµ lîng tö ho¸. C¸c bíc sau m« t¶ cho c¶ viÖc lîng tö
ho¸ c¸c hÖ sè FCT.
1. TÝnh vµ cho tÊt c¶ c¸c hÖ sè FCT. (Chó ý lµ ®é lÖch chuÈn vµ
trung b×nh cã thÓ tÝnh trong mét d¶i th«ng cña ¶nh dïng biÓu thøc sau
cho :
n xi2 xi
2
2
n(n 1)
ë ®©y xi biÓu diÔn c¸c gi¸ trÞ cho mét trong c¸c hÖ sè). ®îc tÝnh tõ
tæng cña xi.
2. ¸p dông c¸c hÖ sè cho c¸c chi tiÕt ®îc gi÷ l¹i cô thÓ lµ 0.25 , 0.5.
3. Gi÷ l¹i c¸c hÖ sè ®· nh©n thªm ph©n sè chia cã sai lÖch cao h¬n sai
lÖch chuÈn.
4. §Þnh d¹ng mét ma trËn T cã d¹ng
nÕu hÖ sè (i, j) kh«ng mÊt
1
Tij
0 c¸c trêng hîp cßn l¹i
5. Chia kho¶ng c¸ch c¸c hÖ sè cij (cô thÓ mét cho c¸c gi¸ trÞ mµ Tij = 1)
trong tÊt c¶ c¸c khèi, ngo¹i trõ c¸c gi¸ trÞ mét chiÒu cho mçi khèi, nh
sau:
cij ij
(13.65)
ij
6. TÝnh ph©n bè cña c¸c gi¸ trÞ AC “chia” cho m¶ng FCT.
7. TÝnh s cña ph©n bè rót ra tõ c¸c bíc tríc.
391
- 8. Dïng lîng tö ho¸ Lloyd-Max møc N, vµ söa l¹i c¸c møc chia vµ
kh«i phôc c¸c møc theo:
(13.66)
di di s
i = 0, 1, 2, ..., N - 1.
chó ý dN = -d0
Hµm ph©n bè Laplace cung cÊp mét xÊp xØ tèt h¬n cho ph©n bè cña
c¸c hÖ sè chia nh chóng ta thÊy ë phÇn díi ®©y. Sù lùa chän cña N
còng nh c¸c hÖ sè chia cña c¸c hÖ sè phô thuéc møc ®é nÐn.
9. Lîng tö c¸c hÖ sè AC “ chia” dïng lîng tö ho¸ cña bíc 8.
10. Chia mçi gi¸ trÞ mét chiÒu víi 2. §iÒu nµy ®¶m b¶o r»ng c¸c gi¸ trÞ
mét chiÒu kh«ng vît qu¸ 255 (mét biÓu diÔn 8 bit).
11. §Þnh d¹ng mét phÇn ®Çu file chøa ®Çy ®ñ th«ng tin ®Ó kh«i phôc
l¹i ¶nh bÞ nÐn. PhÇn nµy chøa th«ng tin vÒ c¸c møc chia vµ c¸c møc
mét chiÒu bÞ c¾t bít vµ tËp hîp c¸c gi¸ trÞ AC cho c¸c hÖ sè gi÷ l¹i.
12. ¸p dông mµ m· ho¸ Huffman cho file chøa c¸c gi¸ trÞ AC.
Ma trËn T thêng gäi lµ ma trËn khu vùc, vµ cÇn cung cÊp c¸c hÖ sè
cho chøc n¨ng kh«i phôc. PhÇn ®Çu file dïng bèn th«ng tin theo thø tù
sau.
ChiÒu réng cña khèi (ta coi khèi lµ mét h×nh vu«ng): 1byte.
Sè c¸c møc lîng tö: 1 byte.
ChiÒu réng cña ¶nh: 2 byte.
Ma trËn T: 1 bit cho mét phÇn tö.
§é lÖch chuÈn, trung b×nh: 4 byte trong biÓu diÔn sè thùc sè c¸c hÖ
sè.
C¸c møc kh«i phôc: 4 byte trong biÓu diÔn sè thùc/ møc.
392
nguon tai.lieu . vn
