Đồ án Kỹ thuật nhận dạng vật thể dựa trên thuật toán kth-Law ECP-SCF

không gian, biên ảnh,… 2.1.3.Nhận dạng và phân loại ảnh (recognition and classification of image partterns) * Nhận dạng ảnh (recognition of image partterns): Khi một bức ảnh đã được phân đoạn, nhiệm vụ tiếp theo là nhận dạng vật thể hoặc vùng đã được phân đoạn. Mỗi một vật thể là một thành phần ở trong ảnh và các giá trị đo được là các đặc tính của thành phần đó. Một tập các vật thể cùng có các đặc tính giống nhau được gọi là một ‘lớp vật thể’(pattern class). Theo đó có thể định nghĩa, nhận dạng là quá trình phân loại các đối tượng được biểu diễn theo một mô hình nào đó và gán cho chúng vào một lớp (gán cho đối tượng một tên gọi) dựa theo những quy luật và các mẫu chuẩn. Sự nhận dạng ảnh thường dựa trên nhiều tính chất của vật và với mỗi tính chất đều có các kỹ thuật nhận dạng khác nhau. VD: Mỗi chữ cáI trong tiếng Anh đều là một tập các đường thẳng đứng, ngang, chéo hoặc cong. Trong khi chữ ‘A’ được mô tả bởi 2 đường chéo và một đường nằm ngang thì chữ ‘B’ được mô tả bởi một đường thẳng đứng với 2 đoạn cong. Một số tính chất của các vật thể 2 hoặc 3 chiều là diện tích, thể tích, chu vi, bề mặt,… có thể đo được thông qua việc tính toán số ‘pixel’. Tương tự như vậy, bang của một vật được đặc trưng bởi đường biên của nó. Một số tham số để xác định bang của một vật là cac mô-ment bất biến (invariant moment), đường trung bình (medial axis) của vật thể … Mầu của một vật cũng là đặc điểm hết sức quan trọng được dùng trong nhận dạng. Kỹ thuật dùng để phát hiện các đặc tính của vật thể gọi là kỹ thuật trích chọn đặc tính (feature extraction). Khi đó vật thể được miêu tả như một tập các đặc tính. Sự lựa chọn và tách lấy các tính chất thích hợp được coi như là vấn đề cơ bản đầu tiên trong nhận dạng ảnh. * Phân loại thành phần ảnh (classification of image patterns) Phân loại là một công đoạn quan trọng trong quá trình nhận dạng vật. Đã có nhiều kỹ thuật phân loại được sử dụng trong việc nhận dạng thành phần. Một số kỹ thuật phân loại được biết như là những kỹ thuật lý thuyết chính xác. Với những kỹ thuật lý thuyết chính xác này, phân loại một thành phần chưa biết được quyết định dựa trên một số nguyên tắc hoặc đã xác định hoặc có ý nghĩa thống kê hoặc thậm chí đôI khi còn chưa được xác định rõ. Hình 1. thể hiện quá trính phân loại Vật cần Kết quả kiểm tra đã phân loại Vật mẫu Trích chọn đặc tính Trích chọn đặc tính Thu nhận thông tin Bộ phân loại Các kỹ thuật nhận dạng vật có mẫu chuẩn được chia làm 2 loại chính: 1.Phương pháp phân loại dựa trên việc thu nhận có giám sát(supervised learning). 2.Phương pháp phân loại sử dụng các kỹ thuật không cần giám sát(nonsupervised learning). Các giải thuật phân loại có giám sát có thể được phân thành các loại nhỏ hơn: * Phân loại dựa vào tham số (Parametric classifiers) * Phân loại không cần tham số (Nonparametric classifiers) Đối với phân loại có giám sát dựa trên tham số, thiết bị phân loại lấy mẫu với một tập gồm nhiều mẫu thành phần xác định nhằm tính toán các thông số thống kê của mỗi loại thành phần như: trung bình số học, công sai… Các vector đặc tính đầu vào đạt được trong thời gian lấy mẫu của phân loại có giám sát được coi như các biến Guass. Các giải thuật không cần giám sát thường được sử dụng trong các bộ phân loại theo khoảng cách nhỏ nhất (minimum distance classifer) và bộ phân loại tương đồng lớn nhất (maximum likelihood classifier). Ngược lại, một số thông số không được quan tâm trong phương pháp phân loại co giám sát không cần tham số. Một số kỹ thuật của loại này là: K điểm lân cận gần nhất (K-nearest neighbors), cửa sổ Parzen (Parzen window)… Đối với các phương pháp phân loại không cần giám sát, bộ phân loại sẽ chia toàn bộ tập thông tin dựa trên một số tiêu chuẩn tương đồng. Điều này cho kết quả là một tập các thành phần trong đó mỗi thành phần thuộc về một lớp cụ thể nào đó. CHƯƠNG 3 NHẬN DẠNG VẬT BẰNG XỬ LÝ ẢNH 3.1.Tương quan tuyến tính và tương quan phi tuyến Một đại lượng tương quan cho phép tính tóa mức độ giống nhau giữa 2 vật. Biểu thức toán học thể hiện sự tương quan giữa 2 hàm số s(x,y) và r(x,y) được định nghĩa bởi: (3.1.1) Trong biểu thức thỡ dấu hoa thị biểu diễn cho tớnh liờn hợp phức và Ä thể hiện tương quan chéo. Nếu như các hàm số s(x,y) và r(x,y) thể hiện một bức ảnh được phân tích và một mẫu tham chiếu thỡ tương quan giữa chúng chính là phét đo sự trùng khớp giữa các vật trong bức ảnh đối với mẫu tham chiếu. Theo đó, sự tương quan có thể được coi như một sự tính toán cấp độ giống nhau giữa chúng. Sự tương quan cũng có thể được biểu diễn bởi các biến đổi Fourier. Nếu như ký hiệu ^ biểu diễn cho biến đổi Fourier, hàm tương quan được biểu diễn bởi (3.1.1) có thể được biểu diễn bởi phương trình: (3.1.2) Trong đó TF-1 là biến đổi Fourier. Phương trình (3.1.2) cho thấy tỉ lệ tương quan giữa 2 hàm số có thể tính toán được bằng cách nhân các biến đổi fourier trong miền tần số và sau đó nghịch đỏa tích số này. Các hệ thể hiện sự tương quan được gọi là các hàm tương quan. Mỗi hàm tương quan cho phép xử lý theo thời gian thực một dữ lượng thông tin lớn. Các hàm tương quan được mô tả bởi phương trình(3.1.1) cú rất nhiều hạn chế khi cú thờm cỏc thành phần nhiễu nền. Thêm vào đó, các hàm tương quan này không còn chính xác khi bức ảnh bị ‘méo’ do tỉ lệ thay đổi, vật bị di chuyển hay điều kiện ánh sáng không ổn định. Áp dụng các kỹ thuật lọc trong không gian khác nhau trước khi thực hiện biến hổi Fourier trong miền tần số cho phép khắc phục những vấn đề này. Ví dụ: việc nhận dạng các vật bị ảnh hưởng bởi các biến đổi tỉ lệ cũng như góc quay là hoàn toàn có thể thực hiện. Một toán tử phi tuyến tác động đến các biến đổi Fourier của bức ánh và mẫu tham chiếu được gọi là một hàm tương quan phi tuyến. Hàm tương quan phi tuyến thường được sử dụng do các đặc tính ưu việt của nó so với hàm tương quan tuyến tính trên nhiều khía cạnh như khử nhiễu, khả năng phân biệt... Với các bộ xử lý bậc k, toán tử phi tuyến được áp dụng một cách đối xứng với bức ảnh cũng nhuew với biến đổi Fourier tham chiếu: , k£1 (4.1.3) Tham số k kiểm soát khả năng của hàm phi tuyến được áp dụng. VD: với k=1 tương ứng với một kỹ thuật lọc tuyến tính; với k=0 tương ứng với một kỹ thuật phi tuyến nhị phân; các giá trị khác của k cho phép thay đổi đặc tính của toán tử phi tuyến cũng như thay đổi tính chất của hàm tương quan (VD khả năng phân biệt hoặc bất biến đối với cường độ sang). Chỉ số k chính xác chỉ đạt được khi có một sự biểu diễn chính xác của hàm tương quan. Biến đổi Fourier Các kỹ thuật lọc phi tuyến Biến đổi Fourier Các kỹ thuật lọc phi tuyến Biến đổi Fourier ngược X Biểu đồ của một bộ xử lý tương quan phi tuyến 3.2 Các kỹ thuật lọc phi tuyến trong nhận dạng theo tỉ lệ Để xây dựng các hệ thống nhận dạng vật theo tỉ lệ thỡ có nhiều cách tiếp cận khỏc nhau. Điểm chung nhất giữa các hường tiếp cận là yêu cầu của việc lưu trữ thong tin dựa trên các điều kiện ‘méo’ khác nhau ảnh hưởng tới đối tượng. Cách thông dụng nhất để lưu giữ thông tin của sự ‘méo’ của đối tượng là thiết kế một bộ lọc đơn giản cho mỗi loại ‘méo’. Khi đó ta nhắc tới việc thiết lập một bộ lọc thông dải. Để xác định liệu đối tượng có bị méo hay không trong bức ảnh cần xử lý cần phải tương quan bức ảnh với nhiều bộ lọc với các dải thông khác nhau. Do đó, kỹ thuật này thường tốn nhiều thời gian. Các bộ lọc tổng hợp được đưa ra như là một đáp án cho vấn đề này. Thông tin trong bộ lọc tổng hợp thường chứa các cách nhỡn khỏc nhau đối với đối tượng ở trong các điều kiện khác nhau (điều kiện về góc nhỡn, tỉ lệ tương quan, độ chói…) Việc tổng hợp tất cả những thông tin này trong một bộ lọc tổng hợp được thực hiện trong một điều kiện với các giới hạn nhất định. Ưu điểm lớn nhất của việc dung các bộ lọc tổng hợp so với các bộ lọc thông dải là việc tiết kiệm được thời gian trong quá trỡnh xử lý. Chỉ với một phép tương quan đơn giản có thể so sánh bức ảnh của đối tượng với tất cả các bức ảnh trong tập ảnh tham chiếu. Mặc dù vậy, các bộ lọc tổng hợp thường thiếu tính chính xác và khả năng phân biệt trong nhận dạng. Số lượng bức ảnh mẫu được dung để tham chiếu trong bộ lọc tổng hợp được giới hạn nhằm đưa lại kết quả xử lý tốt nhất. Trong khuôn khổ luận văn này, các bộ lọc phi tuyến sử dụng mặt phẳng Fourier được sử dụng như các bộ lọc phi tuyến tổng hợp. Các kết quả thí nghiệm đó cho thấy cỏc bộ lọc phi tuyến trên mặt phẳng Fourier có thể thực thi tốt công việc ngay cả trong trường hợp có nhiều loại nhiễu khác nhau. Hàm ECP-SDF bậc k đó được sử dụng và phát triển trong nhiều ứng dụng thực tế và đó đưa lại những kết quả đáng tin cậy. Vì vậy, tụi xin phộp được sử dụng kết quả của thuật toán này đưa vào chương trình xử lý ảnh của mạch nhằm đưa ra một giải pháp cho công việc xử lý ảnh. 3.3 Thuật toán Kth_law ECP-SDF (equal-correlation-peak synthetic discriminant function) tạm dịch là hàm phân biệt và tổng hợp ảnh tuân theo tỉ lệ tương quan. Đặt s1(x,y),s2(x,y),...,sN(x,y) để biểu diễn cho N bức ảnh được chọn. Đặt P là tổng số pixel của mỗi bức ảnh. Thay cho một ma trận biểu diễn một bức ảnh ta sử dụng một khái niệm vector cú trật tự lexico*. Mỗi vector cột gồm p phần tử đại diện cho mỗi bức ảnh bằng cách tái sắp xếp các hàng trong ma trận. Các phần tử của vector được sắp xếp từ trái qua phải và từ trên xuống dưới. Tiếp đến chúng ta sẽ xây dựng một bức ảnh dữ liệu mẫu S có vector si là cột thứ i của nó. Khi đó S sẽ là một ma trận kích thước PxN. Khi đó, một bộ lọc tổng hợp có trật tự lexico h(x,y) được biểu diễn bởi công thức: (3.3.1) Trong đó: S+ là ma trận chuyển vị phức liờn hợp của S ()- biểu diễn sự nghịch đảo của ma trận Vector c chứa giá trị tương quan chéo mong muốn lớn nhất cho mỗi bức ảnh C* là vector phức liên hợp của c Trong miền tần số, (1) trở thành: (3.3.2) ký hiệu ^ biểu diễn cho biến đổi Fourier. Khi đó bộ lọc phi tuyến tổng hợp h đạt được bằng cách thay ở (3.3.2) bởi . Với là một ma trận phi tuyến đối với mỗi phần tử. Toán tử tuyến tính biểu diễn cho phần tử của hàng thứ r và cột thứ l của ma trận được định nghĩa bởi: |Srl|kexp(jfSrl) Đồng thời, bộ lọc bậc k tuân theo hàm ECP-SDF được xác định bởi công thức: (3.3.3) 3.4 BIẾN ĐỔI FOURIER RỜI RẠC Việc phân tích tín hiệu rời rạc theo thời gian trong miền tần số thường được thực hiện rất hiệu quả và tiện lợi bằng bộ vi xử lý tín hiệu số. Bộ vi xử lý này có thể là máy tính được sử dụng cho các mục đích chung hoặc là một thiết bị số chuyên dụng. Để thực hiện việc phân tích này, tín hiệu rời rạc theo thời gian {x(n} cần được chuyển từ miền thời gian sang miền tần số tương ứng thông qua biến đổi Fourier X (w) của dãy. Tuy vậy, do X (w) là hàm liên tục của biến tần số nên có thể thấy việc xử lý bằng máy tính của cách biểu diễn này là không thuận tiện. Để tránh nhược điểm nêu trên có thể đưa ra một cách biểu diễn khác của {x(n} – biểu diễn thông qua việc lấy mẫu phổ X (w) của tín hiệu. Như vậy, từ biểu diễn của tín hiệu trong miền tần số liên tục ta đã đưa đến biến đổi Fourier rời rạc (DFT). Biến đổi này là một công cụ rất hiệu quả trong việc phân tích các tín hiệu rời rạc theo thời gian. 3.4.1. Lấy mẫu trong miền tần số và biến đổi Fourier rời rạc Trước khi nghiên cứu DFT, ta hãy xét việc lấy mẫu của biến đổi Fourier đổi với dãy tín hiệu rời rạc theo thời gian không tuần hoàn và qua đây có thể thiết lập được quan hệ giữa biến đổi Fourier đã được lấy mẫu và DFT. * Lấy mẫu trong miền tần số và khôi phục lại tín hiệu rời rạc theo thời gian Chúng ta đã biết rằng mọi tín hiệu không tuần hoàn có năng lượng hữu hạn đều có phổ liên tục. Hãy xét một tín hiệu không tuần hoàn rời rạc theo thời gian x (n) với biến đổi Fourier: X (w) = (3.4.1) Giả sử tín hiệu X (w) được lấy mẫu tuần hoàn và khoảng cách giữa hai lần lấy mẫu liên tiếp là bằng nhau và bằng dw radian. Bởi vì X (w) là tuần hoàn với chu kỳ 2p do vậy chỉ cần xét đến các mẫu được lấy trong miền tần số cơ bản. Nếu chọn khoảng tần số cơ bản là 0 £ w £ 2p và số lượng mẫu được lấy trong khoảng này là N thì khoảng cách giữa các lần lấy mẫu sẽ là dw = 2p/N – xem hình 4.1. Nếu đánh giá (3.4.1) tại w = 2pk / N, ta nhận được: , k = 0, 1, …, N-1 (3.4.2) và đây chính là n mẫu được lấy của X (w) Ta hãy chia tổng trong (3.4.2) thành một số lượng vô hạn các tổng, trong đó mỗi tổng có chứa N phần tử. Như vậy công thức (3.4.2) có thể được viết thành: Nếu chỉ số n của tổng bên trong được thay đổi thành n – lN và vị trí của hai tổng được thay đổi cho nhau ta sẽ nhận được kết quả sau: (3.4.3) với k = 0, 1, 2, …, N-1. Tín hiệu: (3.4.4) là tín hiệu nhận được do sự xếp chồng của vô tín hiệu x (n) đặt lệch nhau một chu kỳ là N. Rõ ràng rằng xp (n) là tín hiệu tuần hoàn với chu kỳ cơ bản là N và do vậy nó có thể được khai triển qua chuỗi Fourier bằng công thức sau: , n = 0, 1, …, N-1 (3.4.5) với các hệ số: , k = 0, 1, …, N-1 (3.4.6) Bằng cách so sánh (3.4.3) với (3.4.6) ta sẽ có: , k = 0, 1, …, N-1 (3.4.7) Từ đâu suy ra: , n = 0, 1, …, N-1 (3.4.8) Quan hệ được đưa ra bởi (3.4.8) chính là công thức cho phép khôi phục lại tín hiệu tuần hoàn xp (n) từ các mẫu của phổ X (w). Quan hệ này, tuy vậy vẫn không đảm bảo được rằng x (n) hoặc X (w) có thể được khôi phục từ các mẫu hay không. Để đảm bảo được điều này cần phải xem xét thêm quan hệ giữa x (n) và xp (n). Bởi vì theo công thức (3.4.4) xp (n) là sự mở rộng một cách tuần hoàn của x (n) do vậy x (n) có thể được khôi phục lại từ xp (n) nếu không có sự “trùm thời gian” giữa các thành phần của xp (n). Điều này đòi hỏi x (n) phải có độ dài hữu hạn và độ dài L phải nhỏ hơn chu kỳ N của xp (n), Trên hình 4.2 mô tả hai trường hợp của tín hiệu xp (n) ứng với các trường hợp N > L và N < L. Ở đây không làm mất tính tổng quát ta có thể xem x (n) là một dãy có độ dài hữu hạn với các giá trị khác không trong khoảng 0 £ n £ L-1. Có thể đưa ra nhận xét rằng khi N ³ L thì: x (n) = xp (n), 0 £ n £ N-1 vì vậy x (n) có thể được khôi phục từ xp (n) mà không có sự sai lệch. Mặt khác nếu N < L thì sẽ không có khả năng khôi phục x (n) từ xp (n) do có sự tùm tín hiệu trong miền thời gian. Từ kết quả thu được ở trên ta suy ra phổ của tín hiệu không tuần hoàn rời rạc theo thời gian không tuần hoàn với độ dài hữu hạn L có thể được khôi phục một cách chính xác thông qua các mẫu của nó tại các tần số wk = 2pk/N nếu N ³ L. Quá trình này được thực hiện trước hết bằng việc xác định xp (n), n = 0, 1, 2, …, N-1 thông qua công thức (3.4.8). Khi N ³ L thì x(n) được xác định thông qua xp(n): 0 £ n £ N-1 (3.4.9) với các giá trị khác của n và do vậy: , 0 £ n £ N-1 (4.1.10) Nếu sử dụng công thức (3.4.1) và thay thế x(n) bằng (3.4.10) ta nhận được: (4.1.11) Tổng của các phần tử nằm trong dấu ngoặc vuông của (4.1.11) biểu diễn công thức nội suy được dịch bởi 2pk/N theo tần số. Thật vậy, ta định nghĩa: (3.4.12) Thì (3.4.11) sẽ trở thành: (3.4.13) Như vậy, có thể thấy cũng giống như trường hợp tín hiệu liên tục theo thời gian, X(v) có thể được xác định thông qua các mẫu X(2pk/N) của nó thông qua công thức nội suy (3.4.12), với k = 0, 1, 2, … , N-1. Điểm khác biệt ở đây là ở chỗ P(v) không có dạng của (sinq)/q mà thay vào đó nó sẽ phụ thuộc vào tính chất tự nhiên của X(v). Độ lệch pha trong (3.4.12) phản ánh tính chất của tín hiệu x(n) – nhân quả và là dãy có độ dài hữu hạn N. Đồ thị sin(wN/2)/(Nsin(w/2) được thể hiện trên hình 4.3. với N = 5. Có thể thấy rằng hàm P(w) có đặc tính: (3.4.14) Và do vậy theo công thức nội suy (3.4.13) thì các giá trị của X(w) sẽ được xác định chính xác bằng các giá trị mẫu X(2pkn/N) với w = 2pk/N. Ở tại các tần số khác, công thức nội suy sẽ cho phép xác định X(w) thông qua tổ hợp tuyến tính có trọng số của các mẫu phổ. * Biến đổi Fourier rời rạc (DFT) Phần 4.1.1 đã xem xét việc lấy mẫu trong miền tần số của tín hiệu không tuần hoàn x(n) với năng lượng hữu hạn. Trong trường hợp tổng quát, các mẫu được lấy cách đều nhau theo tần số X(2pk/N), k = 0, 1, 2, … , N-1 sẽ không cho phép khôi phục tín hiệu gốc x(n) có độ dài vô hạn. Thay vào đó các mẫu này sẽ tương ứng với dãy tuần hoàn xp(n) với chu kỳ N. Ở đây xp(n) là tín hiệu xấp xỉ của x(n) và quan hệ của chúng được biểu diễn qua công thức: xp(n) = (3.4.15) Khi dãy x(n) có độ dài hữu hạn L £ N thì xp(n) đơn giản chỉ là sự lặp lại có chu kỳ của x(n) và trong một chu kỳ đơn thì xp(n) sẽ được xác định bởi: (3.4.16) Bởi vì x(n) = xp(n) trên một chu kỳ đơn (tín hiệu x(n) được đưa thêm N-L điểm mẫu không) do vậy tín hiệu gốc x(n) với độ dài hữu hạn sẽ có thể nhận được từ các mẫu tần số {X(2pk/N} thông qua công thức (3.4.8). Điều này chứng tỏ các mẫu tần số, X(2pk/N), k = 0, 1, 2, … , N-1 sẽ cho phép xác định tín hiệu với độ dài hữu hạn x(n) một cách duy nhất. Một điều quan trọng cần lưu ý là các giá trị không được đưa thêm vào sẽ không cung cấp thêm bất kỳ một thông tin nào về phổ X(w) của dãy x(n) và để có thể khôi phục lại X(w) có thể sử dụng công thức (3.4.13) với L mẫu được lấy cách đều nhau của X(w). Tuy vậy việc đưa thêm N-L không vào x(n) và tính N điểm DFT sẽ làm cho đồ thị của biến đổi Fourier trở nên tốt hơn. Nói tóm lại, dãy số x(n) với độ dài hữu hạn L (nghĩa là x(n) = 0 với n < 0 và n ³ L) có biến đổi Fourier: (3.4.17) Khi việc lấy mẫu của X(w) được thực hiện ở các tần số cách đều nhau wk = 2pk/N, k = 0, 1, 2, … , N-1 với N ³ L thì các mẫu nhận được sẽ là: Để cho thuận tiện thì trong công thức này chỉ số trên của tổng được tăng từ L - 1 lên N - 1 bởi vì x(n) = 0 khi n ³ L. Quan hệ (3.4.18) chính là công thức dùng để biến đổi dãy {x(n)} với độ dài L £ N thành dãy của các mẫu tần số {X(k)} với độ dài N. Bởi vì các mẫu tần số nhận được bằng cách đánh giá giá trị của biến đổi Fourier X(w) tại N tần số rời rạc cách đều nhau do vậy quan hệ (3.4.18) được gọi là biến đổi Fourier rời rạc (DFT) của x(n). Ngược lại quan hệ (3.4.18) sẽ cho phép khôi phục dãy x(n) từ các mẫu tần số. Biểu thức: được gọi là biến đổi ngược DFT (IDFT). Rõ ràng, khi x(n) có độ dài L < N thì IDFT với N điểm sẽ có x(n) = 0 với L £ n £ N – 1. Như vậy các công thức của DFT và IDFT sẽ là: DFT: (3.4.18) IDFT: (3.4.19) 3.4.2. Biến đổi Fourier nhanh FFT: Do vai trò quan trọng của DFT trong nhiều lĩnh vực khác nhau nên việc tính toán hiệu quả của DFT là một bài toán được rất nhiều nhà toán học, kỹ sư v.v… dành nhiều thời gian để nghiên cứu. Phần này sẽ trình bày một số phương pháp khác nhau để thực hiện việc tính toán DFT một cách hiệu quả hơn. Như ta đã biết, DFT của dãy x(n) với độ dài hữu hạn N được xác định thông qua công thức sau: (5.1.1) với: (5.1.2) Trong trường hợp tổng quát thì dữ liệu của dãy {x(n)}sẽ có giá trị phức. Phép biến đổi Fourier rời rạc ngược (IDFT) của X(k) là: (5.1.3) Do các biểu thức (5.1.1) và (5.1.3) chỉ khác nhau ở dấu của số mũ W và ở hệ số tỷ lệ 1/N nên mọi lý luận về cách tính của IDFT đều giống với cách tính DFT. Có thể thấy trong công thức tính DFT, đối với mỗi giá trị của k thì việc tính trực tiếp X(k) sẽ đòi hỏi N phép nhân số phức (4N phép nhân số thực) và N-1 phép cộng số phức (4N-2 phép cộng số thực). Như vậy để tính N giá trị của DFT thì cần phải sử dụng 4N2 phép nhân thực và N(4N-2) phép cộng thực hay N2 phép nhân phức và N2 - N phép cộng số phức. Việc tính toán DFT sẽ hiệu quả hơn nếu ta sử dụng một số tính chất quan trọng của hệ số pha WN. Các tính chất này bao gồm: Tính đối xứng: (5.1.4) Tính tuần hoàn: (5.1.5) Hầu hết các thuật toán tính nhanh Fourier đều khai thác các tính chất quan trọng này của hệ số pha. CHƯƠNG 4 XỬ LÝ ẢNH VỚI MATLAB 4.1 Giới thiệu về MATLAB MATLAB là ngôn ngữ lập trình bậc cao dùng cho kỹ thuật. Đồng thời nó là môI trường tương tác có thể thực hiện nhiều nhiệm vụ: phát triển giảI thuật, phân tích dữ liệu, tính toán các phép tính số học và hình ảnh hóa dữ liệu. So với các ngôn ngữ lập trình truyền thống như C, C++ hay Fortran thì MATLAB có nhiều ưu điểm hơn do được tích hợp các hỗ trợ rất mạnh. MATLAB được sử dụng trong nhiều lĩnh vực ứng dụng bao gồm: sử lý tín hiệu và hình ảnh, truyền thông, thiết kế điều khiển, kiểm tra và đo lường, phân tích và mô hình hóa các thông tin tài chính, tính toán trong hóa sinh… Ngoài ra, MATLAB còn được tích hợp các hộp công cụ (mỗi hộp gồm hệ thống các hàm có những chức năng đặc biệt của MATLAB) nhằm giảI quyết các lớp vấn đề cụ thể trong các lĩnh vực ứng dụng khác nhau. MATLAB cung cấp nhiều đặc tính tiện lợi đối với việc xử lý và chia sẻ công việc. Trong quá trình làm việc với MATLAB, các đoạn mã của nó có thể được tích hợp với các ngôn ngữ và ứng dụng khác. 4.1.1 Các đặc điểm cơ bản của MATLAB: * Là ngôn ngữ bậc cao dùng cho các tính toán kỹ thuật. * Là môi trường phát triển để quản lý dữ liệu. * Gồm nhiều công cụ tương tác cho việc khai thác và xử lý dữ liệu, thiết kế và giảI quyết vấn đề. * Các hàm đồ thị đối với ảnh 2 hoặc 3 chiều cho phép hình ảnh hóa dữ liệu. * Chứa các công cụ để xây dựng các giao diện đồ thị của người sử dụng. * Gồm nhiều hàm chức năng dựa trên các giảI thuật cơ sở nhằm tích hợp MATAB với các ứng dụng và ngôn ngữ lập trình khác như: C,C++, Fortran, Java, Microsoft excel… 4.1.2 Phát triển giải thuật và ứng dụng MATLAB là một ngôn ngữ bậc cao được tích hợp các công cụ phát triển giúp người sử dụng phát triển và phân tích các giảI thuật và ứng dụng một cách nhanh chóng. Ngôn ngữ lập trình MATLAB: Ngôn ngữ lập trình MATLAB hỗ trợ các phép toán đối với ma trận và vec-tơ cơ sở cho các vấn đề kỹ thuật và khoa học. Việc lập trình và phát triển giảI thuật trong MATLAB có tốc độ nhanh hơn so với các ngôn ngữ lập trình truyền thống do MATLAB bỏ qua các công việc điều khiển bậc thấp như khai báo biến, khai báo mẫu dữ liệu và xác định vùng nhớ. Trong nhiều trường hợp, MATLAB còn bỏ qua cả sự cần thiếp của các vòng lặp ‘for’. Kết quả là, một dòng lệnh được viết trong MATLAB có thể tương đương với nhiều dòng lệnh trong C hay C++. Là một công cụ lập trình mạnh, MATLAB vẫn hỗ trợ những đặc tính của một ngôn ngữ lập trình truyền thống như: toán tử số học, cấu trúc vòng, các cấu trúc và dạng dữ liệu cùng đặc tính gỡ rối. VD: Chương trình biểu diễn thuật toán điều chế tín hiệu truyền thông tạo ra 1024 điểm, thực hiện điều chế, thêm nhiễu phức Gauss và vẽ lại kết quả. % tạo một vector N bit N = 1024; bits = rand(N,1)>0.5; % chuyen sang ky tu Tx=1-2*bits; %them vao nhieu Gauss trang P=0.4 Nz=P*(randn(N,1)+i*randn(N,1)); Rx= Tx + Nz; %hien thi ket qua plot(Rx,'.'); axix([-2 2 -2 2]); axis square, grid; Hình 4.1 Trong khi đối với phần lớn các ngôn ngữ lập trình truyền thống phảI trảI qua giai đoạn dịch (compilation) và liên kết (linking) thì MATLAB cho phép người sử dụng có thể thực thi ngay các lệnh hoặc nhóm lệnh cùng lúc. Điều này làm cho tốc độ xử lý trên MATLAB nhanh hơn đáng kể so với trên các ngôn ngữ truyền thống. 4.1.3 Phân tích và tiếp cận dữ liệu: Trong quá trình phân tích dữ liệu, MATLAB hỗ trợ hầu hết các công đoạn như: thu nhận dữ liệu từ thiết bị ngoại vi, các phân tích số học, tiền xử lý, hình ảnh hóa… Phân tích dữ liệu: Chương trình MATLAB cung cấp các công cụ tương tác cũng như các hàm điều khiển theo dòng cho việc tính toán trong phân tích dữ liệu bao gồm: * Các phép nội suy * Trích chọn tính chất * Chọn ngưỡng và lọc nhiễu * Tương quan, phân tích Fourier và lọc * Phát hiện các điểm đỉnh, đáy và điểm không * Thống kê cơ bản và chuẩn hóa các đường cong * Phân tích ma trận 4.1.4 Tiếp cận dữ liệu Việc tiếp cận dữ liệu từ các thư mục, ứng dụng, cơ sở dữ liệu và thiết bị ngoại vi bởi MATLAB là hết sức dễ dàng. MATLAB hỗ trợ nhiều loại định dạng file: ASCII, nhị phân, các file hình ảnh và âm thanh hay thậm chí các file định dạng HDF. Trong MATLAB có nhiều hộp công cụ (toolbox) hỗ trợ cho việc tiếp cận dữ liệu như: hộp công cụ cơ sở dữ liệu (Database Toolbox), hộp công cụ thu nhận dữ liệu (Data Acquisition Toolbox) hay hộp công cụ điều khiển thiết bị (Instrument Control Toolbox). 4.1.5 Hình ảnh hóa dữ liệu Tất cả các đặc tính về hình ảnh cần thiết cho hình ảnh hóa các dữ liệu khoa học kỹ thuật đều được tích hợp trong MATLAB. Những đặc tính này bao gồm: các hàm vẽ ảnh 2 và 3 chiều, các hàm vẽ thể tích 3 chiều, các công cụ tương tác tạo ảnh, khả năng xuất kết quả dưới các dạng file ảnh thông thường. VD: vẽ hàm y= sin(x) với -pi < x < pi Mã chương trình: >>x = -pi:.1:pi; >>y = sin(x); >> plot (x, y) Hình 4. đồ thị hàm y = sin(x) 4.1.6 Xuất kết quả và triển khai ứng dụng MATLAB đưa ra nhiều đặc tính giúp báo cáo và chia sẻ công việc. Các đoạn code viết trên MATLAB có thể được tích hợp với các ngôn ngữ và ứng dụng khác. Đồng thời cũng có thể triển khai các thuật toán cũng như ứng dụng của nó như một chương trình hoặc các khối phần mềm riêng biệt. Xuất kết quả: Sau khi hoàn thành công việc, người sử dụng cần xuất kết quả ra thường là dưới dạng hình ảnh hoặc báo cáo. MATLAB có hỗ trợ file hình ảnh với nhiều định dạng khác do đó việc xuất kết quả dưới dạng đồ thị hay file ảnh là hết sức dễ dàng. Ngoài ra, nếu muốn thì cũng có thể chuyển code từ MATLAB ra các dạng khác: HTML, Word, Latex… Kết hợp mã MATLAB với các loại ngôn ngữ và ứng dụng khác: MATLAB cung cấp sẵn các hàm cho việc kết hợp mã của các ngôn ngữ lập trìn