Biến đổi fourier rời rạc trong xử lý ảnh

Trong toán học , phép biến đổi Fourier rời rạc ( DFT ) chuyển đổi một chuỗi hữu hạn các mẫu cách đều nhau của một hàm thành một chuỗi có cùng độ dài các mẫu cách đều nhau của phép biến đổi Fourier thời gian rời rạc (DTFT), là một phép phức có giá trị hàm của tần số. Khoảng thời gian mà DTFT được lấy mẫu là nghịch đảo của khoảng thời gian của chuỗi đầu vào. DFT nghịch đảo là một chuỗi Fourier , sử dụng các mẫu DTFT làm hệ số của hình sin phức tạp ở các tần số DTFT tương ứng. Nó có các giá trị mẫu giống như chuỗi đầu vào ban đầu. Do đó, DFT được cho là một biểu diễn miền tần số của chuỗi đầu vào ban đầu. Nếu dãy ban đầu kéo dài tất cả các giá trị khác 0 của một hàm, thì DTFT của nó là liên tục (và tuần hoàn) và DFT cung cấp các mẫu rời rạc của một chu kỳ. Nếu dãy ban đầu là một chu kỳ của một hàm tuần hoàn, thì DFT cung cấp tất cả các giá trị khác không của một chu kỳ DTFT.

DFT là phép biến đổi rời rạc quan trọng nhất , được sử dụng để thực hiện phân tích Fourier trong nhiều ứng dụng thực tế. [1] Trong xử lý tín hiệu kỹ thuật số , hàm là bất kỳ đại lượng hoặc tín hiệu nào thay đổi theo thời gian, chẳng hạn như áp suất của sóng âm thanh , tín hiệu vô tuyến hoặc số đọc nhiệt độ hàng ngày , được lấy mẫu trong một khoảng thời gian hữu hạn (thường được xác định bởi một cửa sổ hàm [2] ). Trong xử lý hình ảnh , các mẫu có thể là giá trị của các pixel dọc theo một hàng hoặc cột của hình ảnh raster . DFT cũng được sử dụng để giải quyết hiệu quảphương trình vi phân riêng và để thực hiện các phép toán khác như tích chập hoặc nhân các số nguyên lớn.

Vì nó xử lý một lượng dữ liệu hữu hạn, nó có thể được thực hiện trong máy tính bằng các thuật toán số hoặc thậm chí là phần cứng chuyên dụng . Các triển khai này thường sử dụng các thuật toán biến đổi Fourier nhanh (FFT) hiệu quả ; [3] đến nỗi thuật ngữ "FFT" và "DFT" thường được sử dụng thay thế cho nhau. Trước khi được sử dụng hiện tại, chủ nghĩa khởi tạo "FFT" cũng có thể được sử dụng cho thuật ngữ mơ hồ " biến đổi Fourier hữu hạn ".

Các đổi Fourier rời rạc biến đổi một chuỗi của N số phức vào một chuỗi các số phức, được định nghĩa bởi {NSn}: =NS0,NS1,…,NSn-1{\ displaystyle \ left \ {\ mathbf {x_ {n}} \ right \}: = x_ {0}, x_ {1}, \ ldots, x_ {N-1}}{NSk}: =NS0,NS1,…,NSn-1,{\ displaystyle \ left \ {\ mathbf {X_ {k}} \ right \}: = X_ {0}, X_ {1}, \ ldots, X_ {N-1},}

Mối quan hệ giữa phép biến đổi Fourier (liên tục) và phép biến đổi Fourier rời rạc. Cột bên trái: Một hàm liên tục (trên cùng) và biến đổi Fourier của nó (dưới cùng). Cột giữa bên trái: Tổng kết định kỳ của hàm gốc (trên cùng). Biến đổi Fourier (đáy) bằng không ngoại trừ tại các điểm rời rạc. Biến đổi nghịch đảo là một tổng của các hình sin được gọi là chuỗi Fourier . Cột ở giữa bên phải: Chức năng ban đầu được tùy chỉnh (nhân với lược Dirac ) (trên cùng). Biến đổi Fourier của nó (dưới cùng) là một tổng tuần hoàn ( DTFT ) của biến đổi ban đầu. Cột bên phải:DFT (dưới cùng) tính toán các mẫu riêng biệt của DTFT liên tục. DFT nghịch đảo (trên cùng) là tổng định kỳ của các mẫu ban đầu. Các FFT thuật toán tính toán một chu kỳ của DFT và nghịch đảo của nó là một chu kỳ nghịch đảo DFT.

Mô tả biến đổi Fourier (phía trên bên trái) và tổng định kỳ của nó (DTFT) ở góc dưới bên trái. Các dãy quang phổ ở (a) phía trên bên phải và (b) phía dưới bên phải lần lượt được tính từ (a) một chu kỳ của tổng tuần hoàn của s (t) và (b) một chu kỳ của tổng tuần hoàn của dãy s (nT) . Các công thức tương ứng là (a) tích phân chuỗi Fourier và (b) tổng DFT . Những điểm tương đồng của nó với phép biến đổi ban đầu, S (f), và tính dễ tính toán tương đối của nó thường là động lực để tính toán một chuỗi DFT.

Mô tả ma trận của DFT cho N = 8. Mỗi phần tử được biểu diễn bằng một hình ảnh về vị trí của nó trong mặt phẳng phức liên quan đến đường tròn đơn vị.

Biến đổi fourier rời rạc sử dụng trong Xử lý ảnh số Chơng 6 Biến đổi Fourier rời rạc 6.1 Chỉ dẫn Trong chơng 2,chúng ta đã chứng minh rằng đáp ứng tần số của hệ thống của hệ thốngtuyến tính bất biến (LSI ) 2-D đợc cho bởi: ==+=1 22211)(2121),(),(k kkkjekkhH (6.1)Nếu h(k1,k2) chỉ có chỉ tồn tại với k1 0, k 2 0 và tổng quát đợc xác định trong miềnhữu hạn có kích thớc N ì N thì ==+=1010)(21211 22211),(),(NkNkkkjekkhH (6.2)Công thức này chứng tỏ rằngH( , ) 1 2là tuần hoàn, chu kỳ tuần hoàn là 2. Nếuchúng ta lấy mẫu dới dạng 1, 2, và miền xác định là (0 1 2) và (0 2 2), Nì N mẫu, chúng ta có thể viết: 1 12=Nn và 2 22=Nn(6.3) vì thế ( ) =+==102102121122112),(),(NkknknNjNkekkhnnH (6.4) Biểu thức (6.4) đợc gọi là biến đổi Fourier rời rạc 2-D hay còn gọi là DFT. Công thứcnày đợc áp dụng vào nhiều ứng dụng nh lọc, nén ảnh, phóng đại ảnh. Trong chơng nàychúng ta sẽ nghiên cứu 2-D DFT và các kỹ thuật tính toán. Đầu tiên, chúng ta sẽ xem xét1-D DFT, sau đó mở rộng ra cho 2-D.6.2 Biến đổi Fourier 1-D Biến đổi Fourier 1-D cho tín hiệu thời gian rời rạc f(kT) tính theo công thức : ==102)()(NknkNjekTfnF (6.5)Công thức này có thể viết lại dới dạng ==10Ư)()(NnnkNWkfnF (6.6)75ở đây f(k) = f(kT) và WN = e- j2 /N . WN đợc gọi là hạt nhân của phép biến đổi. Tổngquát, F(n) có dạng )()()(njenAnF= (6.7)Ký hiệu A(n), (n) gọi là phổ khuyếch đại và phổ pha của F(n).6.2.1 Biến đổi ngợc DFTHàm f(k) là biến đổi ngợc DFT của F(n) cho bởi theo biểu thức ==102)(1)(NnnkNjenFNkf (6.8)Chứng minh: Từ định nghĩa của DFT =======1010)(101010)(1)(1)(1NmNnmknNknNNnNmnmNNnnkNWmfNWWmfNWnFN(6.9) Đặt ==10)(NnmknNWS Nếu (k = m) thì S = N. Nếu (k m), chúng ta có thể viết: S = 1 + WN (k -m ) + WN 2(k -m ) + + WN (N-1)(k -m ) hoặc )(2))(2(m)-(kNm)-N(kN11W-1W-1mkNjmkjeeS== Khi e j2(k-m) = 1 và e j2/N. (k-m) 1 với (k m), vì vậy S = 0 với (k m ). Vì vậy, biểu thức (6. 9) có thể rút gọn thành f(k).N1)(110NWnFNNnnkN===Kết quả này giống nh biểu thức (6.8). Khi f(k) có thể rút ra từ F(n) và ngợc lại, chúng gọi là cặp biến đổi. Cặp biến đổi nàycó dạng )()( nFkf 76Chú ý từ biểu thức (6.8) ta có thể dễ dàng chứng minh: )()(1)(110.210)(2kfenFNenFNNnnkNjNnNknNj=====+ (6.10)Mặc dù f(k) đợc xác định trên miền k [0,N], nó vẫn là tín hiệu tuần hoàn với chu kỳNT. (T đợc bao hàm và rút ra từ biểu thức 6.5). 6.2.2 Một vài tính chất của DFT Tuyến tính. Nếu ta có hai dãy tuần hoàn cùng f1(n) và f2(n), và cả hai dãy này tuầnhoàn với chu kỳ N, đợc dùng để tính f3(k) = af1(k) + bf2(k) (6.11)là kết quả của biến đổi DFT f3(n) cho bởi F3(n) = aF1(n) + bF2(n) (6.12) ở đây a, b là hằng số và F1(n) = DFT của f1(k) F2(n) = DFT của f2(k)Tính đối xứng. Tính đối xứng của DFT rất hay đợc dùng. nkNjNknkNjNkNNjNknNkNeekfeekfWkfnNF======210210210)()()()()( Nếu f(k) là thực thì ===)()()(10.2nFekfnNFNknkNj(6.13)Dấu * có nghĩa là liên hợp phức. Tích chập tuần hoàn. Coi f1(k) và f2(k) là hai dãy tuần hoàn có chu kỳ N, với biếnđổi Fourier rời rạc là F1(n) và F2(n). Xem xét tích F(n1).F(n2)77)( Nkf +khi )()(101111111==NkknNWkfnF )()(102222222==NkknNWkfnF và tại các vị trí n1 = n2 = n Đặt f3(k) = IDFT của F1(n).F2(n) hay ( )nkNnWnFnFNkf==10213)().(1)(vì vậy == =+=====+10)(10221011101010)(221121211 2211)()()()(1NnkkknNNkNknkNNnNkNkkknN3WNkfkfWWkfkfN(k)f Chú ý là ==+01110)(21NnkkknWNở đây l là số nguyên. Vì vậy mà)()()(12101113lNkkfkfkfNk== (6.14)ở đây k = 0 đến 2N - 1. Biểu thức trên biểu diễn tích chập của hai tín hiệu tuần hoàn. Chú ý rằng biêủ thức nàychỉ áp dụng cho hai dãy có chung một chu kỳ, và chiều dài của dãy tính theo biểu thứctrên là 2N - 1. Kết quả này chứng minh rằng trong DFT, tín hiệu có số mẫu lớn hơn N sẽđợc biến đổi thành dãy tuần hoàn có chu kỳ N. Khi dùng DFT cho một tín hiệu không cóchu kỳ, mà kết quả thu đợc từ tích hai dãy, ta sẽ phạm một sai lầm gọi là lỗi wraparound.Đó là lý do ta phải làm cho cả hai dãy có chu kỳ bằng nhau. Để sửa lỗi này, một số số 0cần phải thêm vào cả hai dãy để chiều dài hai dãy bằng nhau. Ví dụ, nếu một dãy cóchiều dài A, một dãy có chiều dài B, kết quả ta phải thêm các số 0 cho cả hai dãy cóchiều dài ít nhất là A + B - 1.78cho k = k1 + k2 + lNcác trờng hợp còn lại. W =.= 2n-N2111122211110221110101210111111)()()()()().(kNkknNNnNkknNNkknNWkfkfWkfWkfnFnF====Bài tập 6.1 Cho hai dãy sau =01)(1kf =01)(2kf1. Tính bằng tay tích chập của hai dãy trên. Vẽ một lu đồ biểu diễn thuật toán.2. Làm lại phần 1, nhng lần này sử dụng tích chập tuần hoàn.3. Lập một chơng trình C rút ra f3(k) từ biểu thức f3(k) = IDFT{DFT[f1(k)].DFT[f1(k)]}. So sánh kết quả của phần 1 và phần hai.4. Bây giờ thêm các số không vào f1(k) và f2(k) để chu kỳ của chúng = 5 + 6 - 1. Làmlại phần 3 và so sánh kết quả.6.3 Thuật toán biến đổi nhanh FourierTính trực tiếp giá trị của DFT bao gồm N phép nhân phức và N - 1 phép cộng phứccho mỗi giá trị của F(n). Khi N giá trị đợc tính toán thì N2 phép nhân và N(N - 1) phépcộng đợc tính toán. Cũng nh vậy, cho N có giá trị rất lớn, tính trực tiếp giá trị của DFT sẽđòi hỏi một số phép tính lớn đến mức không thể chấp nhận đợc. Để ví dụ, cho N = 1024= 210 ta sẽ phải tính 220 = 1,048,576 phép nhân số phức và một số gần bằng nh vậy cácphép cộng.Hoàn thiện có nghĩa là phải giảm số phép tính trong biến đổi Fourier xuống. Dới đâychúng ta sẽ giới thiệu hai thuật toán hay dùng là thuật toán phân chia thời gian và thuậttoán phân chia tần số. DFT dùng các thuật toán trên gọi là Fast Fourier transform (FFT).6.3.1 Thuật toán phân chia thời gian Xem xét tính toán của DFT cho bởi (5.6) với N= 2r (r là một số nguyên bất kỳ). Cơ sởcủa thuật toán phân chia thời gian thì rõ ràng. Tuy nhiên, việc thiết kế phần mềm cũngđòi hỏi một số phân tích chi tiết. Để làm rõ các bớc của thuật toán này chúng ta sẽ bắtđầu phân tích với N = 16 và sau đó mở rộng ra áp dụng cho N bất kỳ. Cơ sở của thuật toán phân chia thời gian dựa trên cơ sở chiến lợc chia và chiếm. Cácbớc sau sẽ làm sáng tỏ thuật toán. Vì trong trờng hợp này N =16; nên, ==15016)()(knkWkfnF Chia dãy f(k) thành hai dãy, một dãy đợc rút ra từ phần tử chẵn và một dãy từ nhữngphần tử lẻ. Đó là, ==+=1501615016)()()(knkknkWkfWkfnF k chẵn k lẻ Chúng có thể viết thành 790 k1 4các trờng hợp còn lại.0 k1 5các trờng hợp còn lại.=+=++=70)12(1670)2(16)12()2()(kknkknWkfWkfnF(6.15)Chú ý là nknkjknjknWeeW===8.82)2(.162)2(16 vì thế==++=70816708)12()2()(knknknkWkfWWkfnFđặt f(2k)(k)f 10= 1)f(2k(k)f11+= Ta đợc==+=708111670810)()()(knknknkWkfWWkfnF(6. 16) Đặt ==7081010)()(knkWkfnF (6.17)==7081111)()(knkWkfnF(6.18)Viết lại biểu thức (6.16) chúng ta đợc (n)FW (n)F F(n)11-n1610+=(6.19)Cũng nh vậy, phát triển cho một biểu thức (n)FW -(n)F 8)F(n11-n1610=+(6.20)Biểu thức (6.19) và (6.20) định dạng những đơn vị tính toán gọi là bớm. Hình 6.1 làbiểu đồ của phần tử bớm. Ký hiệu W16-n thờng gọi là trọng lợng hay hệ số xoay. Hai biểuthức này biểu diễn bớc cuối cùng trong lu đồ tính toán của hình 6.2.Bây giờ xem xét biểu thức ==7081010)()(knkWkfnFXử lý nh trên chúng ta có 80 ∑∑=−−=−++=7041083041010)12()2()(knknknkWkfWWkfnFDÔ thÊy -2n16-n8 WW =®Æt 1)(2kf(k)f(2k)f(k)f10211020+== H×nh 6.1 (a) Bím; (b) BiÓu diÔn rót gän.81 F10(n) F(n) F11(n) F(n+8)F10(n) F(n) F11(n) F(n+8)1W16-n nHình 6.2 Bớc cuối cùng của thuật toán biến đổi FFT phân chia miền thời gian.X(k) ký hiệu vector chứa giá trị đợc tính qua phép biến đổi FFT. Vì vậy, ==+=304213021642010)()()(knkknnkWkfWWkfnF (n)FW (n)F (n)F21-2n162010+=(6.21) (n)FW - (n)F 4)(nF21-2n162010=+(6.22)ở đây ==3042020)()(knkWkfnF (6.23)==3042121)()(knkWkfnF(6.24)Tơng tự (n)FW (n)F (n)F23-2n162211+= (6.25)(n)FW - (n)F 4)(nF 23-2n162211=+ (6.26) ở đây ==3042222)()(knkWkfnF (6.27)82012!4567012!4567012!4567891011121!1415F10(n)F(n)F11(n)X(k)X(k)==3042323)()(knkWkfnF(6.28) và (2k)f (k)f1122= 1)(2kf (k)f1123+=Biểu thức (6.21), (6.22), (6.25) và (6.26) có thể biểu diễn bằng sơ đồ hình 6.3. Biểuthức (6.23), (6.24), (6.27) và (6.28) có thể tiếp tục chia nhỏ ra nh các bớc đã làm ở trênnh sau: (n)FW (n)F (n)F31-4n163020+= (6.29)(n)FW - (n)F 2)(nF31-4n163020=+(6.30) (n)FW (n)F (n)F33-4n163221+=(6.31)(n)FW - (n)F 2)(nF33-4n163221=+ (6.32)(n)FW (n)F (n)F35-4n163422+= (6.33)(n)FW - (n)F 2)(nF35-4n163422=+ (6.34) (n)FW (n)F (n)F37-4n163623+= (6.35)(n)FW - (n)F 2)(nF37-4n163623=+(6.36)ở đây F n f k Wnkk30 30 201( ) ( )== (6.37)F n f k Wnkk31 31 203( ) ( )==(6.38) , vv.Các biểu thức từ (6.29) đến (6.36) cho kết quả trong bớc thứ ba của thuật toán và biểudiễn trong lu đồ hình 6.4.Mỗi phần tử từ F30(n) đến F37(n) có thể chia tiếp thành hai phầntử nữa và bớc này tạo thành sơ đồ cuối cùng (bớc đầu tiên) trong lu đồ.8!012!012!012!012!012!4567012!45670F20(n)2F21(n)46F22(n)0F2!(n)426F10(n)F11(n)X(k)X(k)W-2nHệ số xoayn=0 đến !H×nh 6.3 Bíc thø hai sau bíc cuèi cïng trong thuËt to¸n FFT.84[...]... trận có kích thớc 23 ì 23 Trong tất cả các lần lặp lại bạn cần phải giữ lại trong bộ nhớ kích hoạt tại hai hàng cuối cùng, cho phép lặp, tất cả là yêu cầu yêu cầu N lần truy nhập đĩa cho xử lý một ảnh có kích thớc N ì N Nếu N = 2r thì r ì N số lần truy nhập đĩa để dịch chuyển một ảnh, ít hơn nhiều so với N ì N lần truy nhập trong cách xử lý đọc một ảnh cơ bản từng khối một Số lần truy nhập đĩa có thể... thì pha của ảnh cũng bị biến dạng Lý do của sự biến dạng này là tất cả các điểm đều phải chịu một sự dịch chuyển vị trí khác nhau tuỳ theo vị trí của ảnh Tổng quát, ảnh đã đợc lọc có thể cho bởi i f (n1 - f (n1 , n2 ), n2 - f( n1 , n 2 )) ở đây f là hàm dịch chuyển vị trí Chú ý rằng một ảnh biến dạng pha sẽ xuất hiện trên màn hình nh một ảnh mờ Tính đối xứng liên hợp và tuần hoàn Biến đổi2 -D DFT và... bốn bớc trong lu đồ Trong mỗi bớc cần phải có tám bớm Trong mỗi bớm chỉ có một phép nhân phức, hai phép cộng hoặc trừ phức Tổng số phép nhân phức là 8/2 4 Tổng quát cho N = 2r số phép nhân phức là (N/2) r = (N/2 ) log2 N và số phép cộng là Nlog2N Chú ý, thực tế số phép nhân sẽ giảm xuống một ít, vì trong bớc đầu tiên hệ số xoay W 0 = 1 và trong các bớc còn lại chúng ta cũng có các bớm với hệ số xoay... incr . chúng ta sẽ xem xét 1-D DFT, sau đó mở rộng ra cho 2-D. 6.2 Biến đổi Fourier 1-D Biến đổi Fourier 1-D cho tín hiệu thời gian rời rạc f(kT) tính theo công thức : = = 1 0 2 )()( N k nk N j ekTfnF . = + = = 1 0 2 1 0 2121 1 2211 2 ),(),( N k knkn N j N k ekkhnnH (6.4) Biểu thức (6.4) đợc gọi là biến đổi Fourier rời rạc 2-D hay còn gọi là DFT. Công thức này đợc áp dụng vào nhiều ứng dụng nh lọc, nén ảnh,. Chơng 6 Biến đổi Fourier rời rạc 6.1 Chỉ dẫn Trong chơng 2,chúng ta đã chứng minh rằng đáp ứng tần số của hệ thống

Xem thêm: Biến đổi fourier rời rạc sử dụng trong Xử lý ảnh số, Biến đổi fourier rời rạc sử dụng trong Xử lý ảnh số, , 2 Biến đổi Fourier 1-D, 3 Thuật toán biến đổi nhanh Fourier, 7 Bộ lọc hai chiều dùng FFT