Nén dữ liệu Ảnh part 3

a lặp lại quá trình chia đôi đối với các dãy con, dãy con của dãy con và cứ tiếp tục chia như thế. Giống như biến đổi Fourier, mỗi bước lặp cũng được coi là một tầng phân chia. Với N = 2M thì số tầng phân chia là M. Để dễ hình dung, đầu ra của mỗi tầng được kí hiệu là Xm(n) với m là tầng hiện thời
Nội dung trích xuất từ tài liệu:
Nén dữ liệu Ảnh part 3 Ch¬ng T¸m: nÐn d÷ liÖu ¶nhnã sau ®ã ®em nh©n víi 2CNn. Ta lÆp l¹i qu¸ tr×nh chia ®«i ®èi víi c¸c d·y con, d·ycon cña d·y con vµ cø tiÕp tôc chia nh thÕ. Gièng nh biÕn ®æi Fourier, mçi bíc lÆpcòng ®îc coi lµ mét tÇng ph©n chia. Víi N = 2M th× sè tÇng ph©n chia lµ M. §Ó dÔ h×nh dung, ®Çu ra cña mçi tÇng ®îc kÝ hiÖu lµ Xm(n) víi m lµ tÇng hiÖnthêi. Ta xem x(n) lµ biÕn ®æi Cosin 0 tÇng cña x(n): X 0 ( n)  x ( n)XM(n) lµ biÕn ®æi Cosin tÇng M cña x(n), nã kh«ng ph¶i lµ X(k). Bëi v× cø sau mçitÇng, kh«ng chØ thø tù c¸c phÇn tö trong X(k) bÞ x¸o trén mµ c¸c X(2k+1) cßn ®îccéng víi X(2k-1). §Çu ra cña mét tÇng lµ ®Çu vµo cña tÇng tiÕp theo. N víi X 1 ( n)  g ( n) n  0,1,..., 1 2 N N víi X 1( n  )  h( n) n  0,1,..., 1 2 2 N X 1 (i )  X 0 (i )  X 0 (i  ) 2 N N i  X 1 (i  )   X 0 (i )  X 0(i  )  2C N 2 2 Tõ c«ng thøc tÝnh g(n) vµ h(n) ta cã: víi n  0,1,..., N  1Cø sau mçi tÇng, sè d·y con l¹i ®îc nh©n ®«i. XÐt phÐp biÕn ®æi t¹i tÇng thø m ,chóng ta ph¶i lÆp l¹i c«ng viÖc biÕn ®æi cho 2m-1 d·y con. Mçi d·y con ®ãng vai trßnh d·y x(n) Ntrong tÇng thø nhÊt. Sè phÇn tö trong mét d·y lµ: .C«ng ®o¹n biÕn ®æi trªn mét 2 m1d·y con gäi lµ mét khèi biÕn ®æi. Mçi d·y con sÏ tiÕp tôc ®îc ph©n lµm hai d·y nháh¬n. C«ng thøc tæng qu¸t t¹i mçi khèi lµ: N Xm (i )  Xm  1(i)  Xm  1(i  ) 2m (8.16) N N (8.17) )]2C i N / 2 m1 Xm(i  m )[ Xm  1(i )  Xm  1(i  M 2 2 N N N k = 0,1,...,2m-1 Víi i  k ,..., k m1  m , trong ®ã m 1 2 2 2 249NhËp m«n xö lý ¶nh sè - §HBK Hµ néi Ch¬ng T¸m: nÐn d÷ liÖu ¶nh PhÇn x©y dùng c«ng thøc tæng qu¸t trong phÐp biÕn ®æi nhanh Fourier ®îctr×nhbµy kh¸ chi tiÕt ë trªn chóng ta cã thÓ xem l¹i phÇn nµy ®Ó hiÓu h¬n vÒ c«ng thøctæng qu¸tcho mét khèi biÕn ®æi nhanh Cosin.ThuËt to¸n biÕn ®æi nhanh Cosin cã thÓ m« t¶ b»ng c¸c bíc sau:Bíc 1: TÝnh d·y hÖ sè Cji. X¸c ®Þnh sè tÇng M = log2N. TÇng hiÖn thêi m=1.Bíc 2: NÕu m  M thùc hiÖn bíc 3. NÕu kh«ng kÕt thóc. (Cha hÕt c¸c tÇng)Bíc 3: Khèi hiÖn thêi k = 0.Bíc 4: NÕu k < 2m-1 Thùc hiÖn bíc 5. NÕu kh«ng thùc hiÖn bíc 6. (Cha hÕt c¸c khèi trong mét tÇng)Bíc 5: TÝnh to¸n Xm(i) trong khèi theo c«ng thøc tæng qu¸t (8.16), (8.17). T¨ng k lªn 1. Quay vÒ bíc 4. (ChuyÓn ®Õn khèi tiÕp theo)Bíc 6: T¨ng m lªn 1. Quay vÒ bíc 2 (ChuyÓn ®Õn tÇng tiÕp theo) Mét sè vÊn ®Ò lu ý khi cµi ®Æt thuËt to¸n biÕn ®æi Cosin nhanh Kh¸c víi biÕn ®æi Fourier nhanh, trong biÕn ®æi Cosin, x(n) kh«ng ph¶i ®Çu vµotrùc tiÕp vµ X(k) kh«ng ph¶i lµ ®Çu ra trùc tiÕp. ë ®Çu vµo, x(n) chØ lµ c¸ch s¾p xÕpl¹i x(n). Chóng ta biÕt r»ng t¹i mçi tÇng, ®èi víi mçi khèi: X (2i  1)  X (2i  1)  X (2i  1)Nªn ë ®Çu ra, sau khi tÝnh ®îc XM(n) chóng ta ph¶i thùc hiÖn viÖc trõ truy håi tõ tÇngM vÒ tÇng 1 sau ®ã ho¸n vÞ l¹i theo thø tù ®¶o bit míi thu ®îc hÖ sè biÕn ®æi X(k)cÇn tÝnh. Bµi to¸n ...