Các phương pháp phát hiện và tách biên ảnh trong xử lý ảnh số

Mục lục LỜI MỞ ĐẦU Hiện nay, trong các trường đại học và cao đẳng, xử lý ảnh đã trở thành một môn học chuyên ngành của sinh viên các ngành công nghệ thông tin, Viễn thông. Nhằm giúp cho sinh viên những kiến thức cơ bản về các kỹ thuật xử lý ảnh, trong đó Nghiên cứu các vấn đề về phát triển và tách biên ảnh là một trong nhưng mục tiêu quan trọng trong lĩnh vực xử lý ảnh số. Sau giai đoạn tiền xử lí ảnh, ảnh đã được tăng cường hay khôi phục để làm nổi các đặc trưng chủ yếu, tiếp theo là quá trình phân tích ảnh. Quá trình phân tích ảnh gồm các giai đoạn trích trọn các đặc tính, sau đó là phân đoạn ảnh thành các phần tử, thí dụ như phân đoạn theo biên. Phát hiện biên là một phần trong quá trình phân tích ảnh sau khi đã lọc ảnh hay tiền xử lí ảnh. Để tìm hiểu việc phát hiện và dò biên ảnh trước hết chúng ta tìm hiểu các khái niệm ban đầu Biên ảnh: biên ảnh là những điểm mà tại đó hàm độ sáng của ảnh liên tục có bước nhảy hoặc biến thiên nhanh. Cơ sở toán học của việc phát hiện và tách biên là phép toán đạo hàm, phương pháp này còn được gọi là phương pháp phát hiện biên trực tiếp. Tập hợp các điểm biên tạo thành đường biên(edge) hay đường bao (boundary) của ảnh. Ví dụ trong một ảnh nhị phân một điểm có thể được gọi là biên nếu đó là điểm đen và có ít nhất một điểm trắng lân cận. Vùng ảnh (region): là tập tất cả những điểm ảnh thuộc về một đối tượng trong ảnh. Ranh rới giữa các vùng ảnh gọi là biên ảnh và các đường biên khép kín cho phép xác định vùng ảnh. Ý nghĩa của đường biên trong xử lí: đường biên là một loại đặc trưng cục bộ tiêu biểu trong việc phân tích và nhận dạng ảnh. Ngoài ra người ta còn sử dụng đường biên để phân vùng ảnh và ngược lại dùng các vùng ảnh để xác định biên. Đây chính là phương pháp xác định biên gián tiếp. Đường biên của ảnh Như vậy, phát hiện biên một cách lí tưởng là phát hiện được tất cả các đường biên trong đối tượng. Định nghĩa toán học trên là cơ sở cho các kỹ thuật phát hiện biên mà chúng ta sẽ tìm hiểu trong tiểu luận. Chương I. GIỚI THIỆU PHÁT BIỂU ĐỀ TÀI Phát biểu về đề tài Xử lý ảnh là một trong những mảng quan trọng nhất trong kỹ thuật thị giác máy tính, là tiêu đề cho nhiều nghiên cứu trong lĩnh vực này. Hai nhiệm vụ cơ bản của quá trình xử lý ảnh là nâng cao chất lượng thông tin hình ảnh và xử lý số liệu cung cấp cho các quá trình khác trong đó có việc ứng dụng thị giác vào điều khiển. Đã có rất nhiều các công trình nghiên cứu tại nhiều quốc gia từ năm 1920 đến nay về xử lý ảnh đã góp phần thúc đẩy tiế bộ trong lĩnh vực này lớn mạnh không ngừng. Qúa trình bắt đầu từ việc thu nhận ảnh nguồn (từ các thiết bị thu nhận ảnh dạng số hoặc tương tự) gửi đến máy tính. Dữ liệu ảnh được lưu trữ ở dạng phù hợp với quá trình xử lý. Người lập trình sẽ tác động các thuật toán tương ứng lên dữ liệu ảnh nhằm thay đổi cấu trúc ảnh phù hợp với các ứng dụng khác nhau. Một trong những vấn đề trọng tâm nghiên cứu của lĩnh vực thị giác máy là biên và các thao tác trên nó vì các kĩ thuật phân đoạn ảnh chủ yếu dựa vào biên. Nhìn chung về mặt toán học, người ta coi điểm biên của ảnh là điểm có sự thay đổi nhanh hoặc đột ngột về độ xám (hoặc màu). Ví dụ, trong một ảnh nhị phân, một điểm có thể gọi là biên nếu đó là điểm đen và có ít nhất một điểm trắng ở bên cạnh. Tập hợp các điểm biên liên tiếp tạo thành biên hay đường bao quanh của ảnh. Ý nghĩa của đường biên trong xử lý: _ Thứ 1 : đường biên là một loại đặc trưng cục bộ tiêu biểu trong phân tích, nhận dạng ảnh. _ Thứ 2 : người ta sử dụng biên làm phân cách cá vùng xám (màu) cách biệt. Ngược lại người ta cũng sử dụng các vùng ảnh để tìm đường phân cách.Tầm quan trọng của biên. Việc nhận dạng đối tượng phụ thuộc nhiều vào các đặc trưng trích chọn và các đặc trưng này chủ yếu được trích chọn từ biên. Đây là một đề tài vẫn đang được quan tâm và phát triển. Nhất là, ở Việt Nam hiện nay, chưa có nhiều nghiên cứu về vấn đề nhận dạng các đối tượng ảnh. Mặc dù, những ứng dụng thực tế đòi hỏi có những cách giải quyết cụ thể, chẳng hạn như phần mềm nhận dạng các đối tượng địa lý, các biểu tượng trên bản đồ, phần mềm phát hiện và đếm các đối tượng chuyển động. Phạm vi đề tài Nghiên cứu về các vấn đề phát hiện và tách biên ảnh trong xử lý ảnh số. Phát hiện biên và tách biên là một phần trong phân tích ảnh, sau khi lọc ảnh (hay tiền xử lý ảnh). Việc dò và tìm biên ảnh là một trong các đặc trưng thuộc khối trích chọn đặc trưng. Đối tượng Các đối tượng trong ảnh cần được xử lý. 4. Mục đích nghiên cứu Việc nghiên cứu biên và các phương pháp xử lý trên nó đã được nhiều tác giả nghiên cứu và tiếp tục được nghiên cứu cả về mặt lý thuyết lẫn ứng dụng thực tế. Các sản phẩm kết hợp giữa biên và trung vị hiện nay là các sản phẩm nhập liệu tự động như MapScan for Windows (phần mềm nhập dữ liệu bản đồ), MarkRead 1.0 (phần mềm nhập phiếu điều tra dạng đánh dấu) dùng biên để tách các đối tượng chứa dấu, WinGIS, VectMap véc tơ hoá bản đồ dựa trên việc trích chọn xương ảnh. Biên và xương đã và đang tạo ra các kết quả thực tế phong phú và đa dạng. Mục tiêu của tiểu luận : Tìm hiểu các kỹ thuật xử lý biên trong xử lý ảnh và đồ hoạ nhằm kế thừa và cái tiến các kỹ thuật trước đó. Nghiên cứu kỹ thuật phát hiện biên trực tiếp và gián tiếp và một số phương pháp phát hiện biên mới cho một số lớp bài toán. Dò biên và kết nối đường biên (nguyên tắc dò biên – phương pháp dò biên theo quy hoạch động). Đưa ra một số bài toán ứng dụng thực tế có sử dụng cá phương pháp trên và cài đặt. 5.Nội dung chính của tiểu luận Các lý thuyết liên quan đến đề tài, có ví dụ minh hoạ Cài đặt thử nghiệm chương trình (gồm cấu trúc dữ liệu và giải thuật nếu có). Đánh giá kết quả nghiên cứu và kết luận. Chương II. CÁC PHƯƠNG PHÁP PHÁT HIỆN VÀ TÁCH BIÊN ẢNH TRONG XỬ LÝ ẢNH SỐ I. Các phương pháp phát hiện biên trong xử lý ảnh số 1. Một số khái niệm 1.1 Định nghĩa và khái niệm Điểm Biên: Một điểm ảnh được coi là điểm biên nếu có sự thay đổi nhanh hoặc đột ngột về mức xám (hoặc màu). Ví dụ trong ảnh nhị phân, điểm đen gọi là điểm biên nếu lân cận nó có ít nhất một điểm trắng. Đường biên (đường bao: boundary): tập hợp các điểm biên liên tiếp tạo thành một đường biên hay đường bao. Ý nghĩa của đường biên trong xử lý: ý nghĩa đầu tiên: đường biên là một loại đặc trưng cục bộ tiêu biểu trong phân tích, nhận dạng ảnh. Thứ hai, người ta sử dụng biên làm phân cách các vùng xám (màu) cách biệt. Ngược lại, người ta cũng sử dụng các vùng ảnh để tìm đường phân cách. Tầm quan trọng của biên: để thấy rõ tầm quan trọng của biên, xét ví dụ sau: khi người họa sỹ muốn vẽ một danh nhân, họa sỹ chỉ cần vẽ vài đường nứt tốc họa mà không cần vẽ một cách đầy đủ. Mô hình biểu diễn đường biên, theo toán học: điểm ảnh có sự biến đổi mức xám u(x) một cách đột ngột theo hình dưới. Hình 4.1 Đường bao của ảnh Các khái niệm và định nghĩa tóm tắt trên là cơ sở giúp ta hiểu và dùng để hiểu cách xây dựng, thiết kế các kỹ thuật phát hiện biên ảnh. Các bước của phân tích ảnh có thể mô tả theo sơ đồ dưới đây. Việc dò và tìm biên ảnh là một trong các đặc trưng thuộc khối trích chọn đặc trưng. Hình 4.2 Các bước xử lý và phân tích ảnh 1.2 Phân loại các kỹ thuật phát hiện biên Từ định nghĩa toán học của biên người ta sử dụng hai phương pháp phát hiện biên như sau (phương pháp chính) a, Phương pháp phát hiện biên trực tiếp: phương pháp này chủ yếu dựa vào sự biến thiên độ sáng của điểm ảnh để làm nổi biên bằng kỹ thuật đạo hàm. • Nếu lấy đạo hàm bậc nhất của ảnh: ta có phương pháp Gradient • Nếu lấy đạo hàm bậc hai của ảnh: ta có phương pháp Laplace. Hai phương pháp này được gọi chung là phương pháp dò biên cục bộ. Ngoài ra, người ta còn sử dụng phương pháp “đi theo đường bao” dựa vào công cụ toán học là nguyên lý quy hoạch động và đượng gọi là phương pháp dò biên tổng thể. Phương pháp dò biên trực tiếp có hiệu quả và ít bị tác động của nhiễu. b, Phương pháp phát hiện biên gián tiếp: Nếu bằng cách nào đấy, chúng ta thu đượng các vùng ảnh khác nhau thì đường phân cách giữa các vùng đó chính là biên. Nói cách khác, việc xác định đường bao của ảnh được thực hiện từ ảnh đã được phân vùng. Phương pháp dò biên gián tiếp khó cài đặt nhưng áp dụng tốt khi sự biến thiên độ sáng nhỏ. Chú ý: Kỹ thuật dò biên và phân vùng ảnh là hai bài toán đối ngẫu của nhau. 1.3 Quy trình phát hiện biên. B1: Do ảnh ghi được thường có nhiễu, bước một là phải lọc nhiễu theo các phương phápdã tìm hiểu ở các phần trước. B2: Làm nổi biên sử dụng các toán tử phát hiện biên. B3: Định vị biên. Chú ý rằng kỹ thuật nổi biên gây tác dụng phụ là gây nhiễu làm một số biên giả xuất hiện do vậy cần loại bỏ biên giả. B4: Liên kết và trích chọn biên. 2. Các phương pháp phát hiện biên 2. 1 Phương pháp phát hiện biên cục bộ( phát hiện biên trực tiếp) a. Phương pháp phát hiện biên dựa trên Gradient của ảnh Định nghĩa: Gradient là một vec tơ f(x, y) có các thành phần biểu thị tốc độ thay đổi mức xám của điểm ảnh (theo hai hướng x, y trong bối cảnh xử lý ảnh hai chiều) tức: Trong đó dx, dy là khoảng cách giữa 2 điểm kế cận theo hướng x, y tương ứng (thực tế chọn dx= dy=1). Đây là phương pháp dựa theo đạo hàm riêng bậc nhất theo hướng x, y. Gradient trong tọa độ góc (r,θ), với r là véc tơ, θ: góc f(.) đạt cực đại khi tức: hay: (4-4) Kỹ thuật Gradient: Theo định nghĩa về Gradient, nếu áp dụng nó vào xử lý ảnh, việc tính toán sẽ rất phức tạp. Để đơn giản mà không mất tính chất của phương pháp Gradient, người ta sử dụng kỹ thuật Gradient dùng cặp mặt nạ H1, H2 trực giao (theo 2 hướng vuông góc). Nếu định nghĩa g1, g2 là Gradient theo hai hướng x, y tướng ứng thì biên độ g(m,n) tại điểm (m,n) được tính: Để giảm độ phức tạp tính toán, A0 được tính gần đúng như sau: Xét một số toán tử Gradient tiêu biểu như toán tử Robert, Sobel, Prewitt, đẳng hướng (Isometric), 4-lân cận như dưới đây. • Toán tử Robert (1965). Robert áp dụng công thức tính Gradient tại điểm (x, y) như hình bên Với mỗi điểm ảnh I(x,y) đạo hàm theo x, y được ký hiệu tương ứng: gx, gy: Các công thức kể trên được cụ thể hóa bằng các mặt nạ theo chiều x và y tương ứng như sau: • Toán tử (mặt nạ) Sobel. Toán tử Sobel được Duda và Hart [5] đặt ra năm 1973 với các mặt nạ tương tự như của Robert nhưng cấu hình khác như sau: • Mặt nạ đẳng hướng: Một mặt nạn khác cũng được nêu như dưới đây gọi là mặt nạ đẳng hướng (Isometric). • Toán tử 4-lân cận (4-Neighbour Operator). Toán tử 4-lân cận được Chaudhuri và Chandor (1984) nêu ra, trong đó mặt nạ có kích thước 3x3 được thay cho mạt nạ 2x2 của toán tử Robert. Các mặt nạy này được cho: b. Toán tử La bàn Kirsh đã đề xuất các mặt nạ theo 8 hướng như 8 hướng của la bàn (Compass). Hình 4.8 là mô hình 8 hướng và được đặt tên theo hướng địa lý và theo chiều kim đồng hồ: Đông, Đông-Nam, Nam, Nam-Tây, Tây, Tây-Nam, Tây-Bắc, Bắc, Đông-Bắc; mỗi hướng lệch nhau 450. • Toán tử la bàn Kirsh: Có nhiều toán tử la bàn khác nhau. Trong phạm vi tài liệu này, ta xem xét toán tử la bàn Kirsh đặc trưng bởi tám mặt nạ với kích thước 3x3 như sau: Ký hiệu Ai; i= 1, 2, …, 8 là Gradient theo 8 hướng như 8 mặt nạ kể trên, khi đó biên độ Gradient tại điểm ảnh (x,y) được tính theo A(x, y) = Max (|gi(x,y)|) i=1, 2, …, 8. (4-11) • Toán tử la bàn khác: Ngoài toán tử la bàn Kirsh, một số toán tử la bàn khác sử dụng bộ mặt nạ 8 hướng khác như: Trường hợp tổng quát, người ta có thể mở rộng các mặt nạ với n hướng cách đều tương ứng với các mặt Wi; i=1, 2, …, n. Khi đó, biên độ tại hướng thứ i với mặt nạ Wi được xác định: A(x, y) Max( WT I (x, y) ) i = với i=1, 2, …, n. (4-12) c. Phát hiện biên dựa trên laplace của ảnh Để khắc phục hạn chế và nhược điểm của phương pháp Gradient, trong đó sử dụng đạo hàm riêng bậc nhất người ta nghĩ đến việc sử dụng đạo hàm riêng bậc hai hay toán tử Laplace. Phương pháp dò biên theo toán tử Laplace hiệu quả hơn phương pháp toán tử Gradient trong trường hợp mức xám biến đổi chậm, miền chuyển đổi mức xám có độ trải rộng. Toán tử Laplace được đĩnh nghĩa như sau: Toán tử Laplace dùng một số kiểu mặt nạ khác nhau nhằm tính gần đúng đạo h àm riêng bậc hai. Các dạng mặt na theo toán tử Laplace bậc 3x3 có thể: Ghi chú: Mặt nạ H1 còn cải biên bằng việc lấy giá trị ở tâm bằng 8 thay vì giá trị 4. Để thấy rõ việc xấp xỉ đạo hàm riêng bậc hai trong không gian hai chiều với mặt nạ H1 làm ví dụ, ta có thể tính gần đúng như sau: do đó: Kỹ thuật theo toán tử Laplace tạo đường biên mảnh (có độ rộng 1 pixel). Nhược điểm của kỹ thuật này rất nhạy với nhiễu, do vậy đường biên thu được thường kém ổn định. d. Tách biên ảnh theo phương pháp canny Bộ tác sườn ảnh theo Canny (1986) dựa trên cặp đạo hàm riêng bậc nhất với việc làm sạch nhiễu. Mục này được để riêng vì đây là phương pháp tách đường biên khá phổ biến được dùng theo toán tử đạo hàm. Như đã nói, phương pháp đạo hàm chịu ảnh hưởng lớn của nhiễu. Phương pháp đạt hiệu quả cao khi xấp xỉ đạo hàm bậc nhất của Gauss. với fx, fy là đạo hàm riêng theo x và y của f. do vậy: Lấy đạo hàm riêng theo x và y của G ta được: Do bộ lọc Gauss là tách được, ta có thể thực hiện riêng biệt các tích chập theo x và y: Từ đó ta có: Với biên độ và hướng tính theo công thức trên, thuật toán được minh họa trên Hình 4.9. 2.2 Dò biên theo quy hoạch động Dò biên theo phương pháp Gradient là xác định cực trị cục bộ của Gradient theo các hướng; còn phương pháp Laplace dựa vào cắt điểm không của đạo hàm bậc hai. Phương pháp dò biên theo quy hoạch động là phương pháp tìm cực trị tổng thể theo nhiều bước. Nó dựa vào nguyên lý tối ưu của Bellman. Nguyên lý này phát biểu như sau: “Con đường tối ưu giữa 2 điểm cho trước cũng là tối ưu giữa 2 điểm bất kỳ nằm trên đường tối ưu đó”. Thí dụ, nếu C là một điểm trên con đường tối ưu giữa A và B thì đoạn CB cũng là còn đường tối ưu từ C đến B không kể đến ta đến C bằng cách nào (Hình 4.10). Trong kỹ thuật này, giả sử bản đồ biên đã được xác định và được biểu diễn dưới dạng đồ thị liên thông N chặng. Giả sử hàm đánh giá được tính theo công thức: • xk, k=1, …, N: biểu diễn các đỉnh của đồ thị trong chặng thứ k; • d(x ,y): khoảng cách giữa 2 đỉnh x và y tính theo các định nghĩa tương ứng về khoảng cách; • |g(xk)| và θ(xk) là Gradient biên độ và Gradient hướng ở đỉnh xk. • α và β là các hằng số không âm. Đường bao tói ưu sẽ nhận được bằng cách nối các đỉnh k x , k =1, …, N nào đó sao cho S(x1,…, xN, N ) đạt cực đại. Định nghĩa hàm φ như sau: Viết lại công thức (4-21) một cách đệ quy ta có: Đặt f(xN-1, xN)=|g(xN)| - α| θ(xk) - θ(xk-1) | - βd(xN,xN-1) và thay vào ( 4-23) ta có: Lấy N = k theo (4-22) và (4-24) thực hiện suy diễn ta có: Như vậy, Với cách này, thay vì tìm tối ưu toàn cục phức tạp của S(x1, … ,xN, N), ta tìm tối ư của N chặng theo tối ưu 2 biến. Trong mỗi chặng, với mỗi xk tìm tối ưu ( x , k ) k φ . Để dễ hình dung, xét ví dụ sau: Giả sử có bản đồ biểu diễn bởi đồ thị liên thông (Hình 4.11a). Theo phương pháp trên có φ ( A,1) = 5 , với k =2 có φ (D ,2 ) = max(11,12) = 12 . Điều đó có nghĩa là đường từ A đến D đi qua C và ACD là biên được chọn với k=2. Tương tự, với k=4, có hai đường được chọn là ACDEF và AGHJ. Tuy nhiên, với k=5 thì đoạn JB bị loại và chỉ tồn tại đường duy nhất với cực đại là 28. Như vậy, biên được xác định là ADEFB. Trên hình 4.11b, những đường nét đứt đoạn biểu thị cung bị loại; đường nét liền có mũi tên biểu thị đường đi hay biên của ảnh. 2.3 Một số phương pháp khác Ngoài các phương pháp trên, người ta cũng áp dụng một số phương pháp khác cải tiến như tiếp cận bởi mô hình mặt, cách tiếp cận tối ưu hóa. Cách tiếp cận theo mô hình mặt dựa vào việc thực hiện xấp xỉ đa thức trên ảnh gốc hay ảnh đã thực hiện phép lọc Laplace. Cách tiếp cận tối ưu nhằm xác định một hàm (một bộ lọc), làm giảm phương sai σ2 hoặc giảm một số điểm cực trị cục bộ. Dưới đây sẽ trình bày một cách tóm tắt các phương pháp đó. a. Tiếp cận theo mô hình mặt Tư tưởng của phương pháp này là tại lân cận điểm cắt không (điểm biên), ảnh sau khi lọc Laplace có thể được xấp xỉ bởi một đa thức bậc 3 theo hàng và cột. Đa thức thường được dùng là đa thức Trebưchép với kích thước 3x3. Các đa thức này được định nghĩa như sau: P0(x,y)=1; P1(x,y)=x; P2(x,y)=y; ; P4(x,y)=xy; P6(x,y)=xP5(x,y); P7 (x,y)=yP3(x,y); P8(x,y)= P5(x,y)P3(x,y) Với mỗi điểm cắt không phát hiện tại P(x, y) trong ảnh đã được lọc bởi toán tử Laplace – Gauss, Huertas và Medioni đã cho được tính theo công thức tính xấp xỉ: Vấn đề là xác định các hệ số ai, i=1, 2, …, N-1. Nếu W là cửa số lọc tại điểm cắt không và x, y, i, j trong cửa số; các hệ số ai có thể được tính toán như một tổ hợp tuyến tính: ở đây, IL-G(x, y) là ký hiệu ảnh đã được lọc bởi toán tử Laplace–Gauss. Các hệ số này có thể nhận được bởi chập ảnh IL-G(x, y) với các nhân chập như trung bình có trọng số hay một số nhân chập khác. Các bước cài đặt phương pháp nhày có thể mô tả như sau: _ Chập ảnh gốc kích thước NxM với toán tử Laplac –Gauss kích thước M2, ảnh thu được gọi là IL-G. _ Trích chọn các điẻm cắt không của ảnh IL-G, ảnh kết quả ký hiệu là IZCR. _ Với mỗi điểm cắt không trong IZCR, thực hiện một xấp xỉ với kích thước 3x3 để suy ra các điểm cắt không theo cách gải tích. _ Tạo một ảnh mới của các điểm cắt không kích thước nXxnY mà các đường bao được xác định với độ phân giải n nào đó. b. Tiếp cận tối ưu hóa Ý tưởng của cách tiếp cận này là định vị đúng vị trí bằng cách cực tiểu hóa phương sai σ2 vị trí các điểm cắt không hoặc hạn chế số điểm cực trị cục bộ để chỉ tạo ra một đường bao. Canny đã đề xuất 3 ràng buộc ứng với 3 điều kiện: Ràng buộc đầu tiên (Σ) nhằm tìm hàm h(x) phản đối xứng sao cho tỉ số giữa tín hiệu và nhiễu là cực đại. Ràng buộc thứ hai ( Λ ) nhằm cực tiểu hóa phương sai. Ràng buộc thứ ba nhằm hạn chế điểm cực trị cục bộ với mục đích cung cấp chỉ một đường bao. II.Các phương pháp tách biên ảnh trong xử lý ảnh số Cơ sở lý thuyết tách biên Tách biên là phương pháp thông dụng nhất để tách theo nghĩa gián đoạn trong các giá trị cường độ. Sự gián đoạn được tách sử dụng đạo hàm bậc nhất và bậc hai.Đạo hàm bậc nhất lựa chọn trong xử lý ảnh là gradient (độ dốc). Gradient của hàm 2- D được định nghĩa dưới dạng vectơ Biên độ của vectơ này : Để tính toán đơn giản, con số này được xấp xỉ bằng cách sử dụng giá trị tuyệt đối Xấp xỉ này vẫn còn dưới dạng đạo hàm đó là : chúng bằng 0 trong các vùng có cường độ không đổi và giá trị của chúng tỷ lệ với bậc của sự thay đổi cường độ trong vùng có các giá trị pixel biến thiên. Nó được xem là biên độ của gradient hoặc xấp xỉ đơn giản của nó dưới dạng “ gradient”. Đặc tính cơ bản của vectơ gradient là các điểm của nó hướng tỷ lệ thay đổi hàm tại tọa độ lớn nhất. Góc xảy ra tỷ lệ thay đổi lớn nhất là : Một trong những phương pháp then chốt đưa ra là ước đoán đạo hàm và theo phương pháp số. Đạo hàm bậc hai trong xử lý ảnh được sử dụng toán tử Laplace. Toán tử Laplace của hàm 2-D được cho dưới dạng vi phân như sau : Toán tử Laplace ít khi được dùng để tách biên vì vi phân bậc hai dễ bị hạnh hưởng bởi nhiễu, biên độ của nó sinh ra các biên kép và không thể tách hướng biên. Tuy nhiên, toán tử Laplace có thể là phần bổ sung mạnh khi sử dụng kết hợp với kĩ thuật tách biên khác. Ví dụ: mặc dù các biên kép không thích hợp để tách biên trực tiếp, đặc tính này có thể dùng để định vị biên. Ý tưởng cơ bản đằng sau tách biên là tìm các nơi trong ảnh có cường độ thay đổi nhanh, sử dụng một trong 2 tiêu chuẩn tổng quát sau: _ Tìm các nơi đạo hàm bậc nhất của cường độ sáng có biên độ hơn 1 ngưỡng _ Tìm các nơi đạo hàm bậc 2 của cường độ sáng có chỗ chéo 0. Các hàm biên của IPT ( Image Processing Toolbox) cung cấp một số ước lượng đạo hàm dựa trên các tiêu chuẩn. Đối với 1 số trong ước lượng này, có thể xác định bộ tách biên có nhạy với các biên ngang, biên dọc hay không hoặc cả 2. Cấu trúc tổng quát của hàm này là: [g, t] = edge (f, ‘method’, parameters) Trong đó f là ảnh đầu vào, method là 1 trong các phương pháp và parameters là các tham số thêm vào. Trong ngõ ra, g là mảng logic với các giá trị 1 tại các vị trí các điểm biên được tách và với giá trị 0 khi không được tách. Tham số t là tùy chọn, nó cho ngưỡng được dùng bởi biên để xác định các giá trị gradient đủ mạnh để được gọi là các điểm biên. Bảng 1. ĐẶC TÍNH CƠ BẢN CỦA CÁC BỘ TÁCH BIÊN Bộ tách biên Các đặc tính cơ bản Sobel Tìm biên dùng xấp xỉ Sobel với đạo hàm cho trong hình 1(b) Prewitt Tìm biên dùng xấp xỉ Prewitt với đạo hàm cho trong hình 1(c) Roberts Tìm biên dùng xấp xỉ Roberts với đạo hàm cho trong hình 1(d) Laplacian of a Gaussian (LoG) Tìm biên bằng cách tìm điểm chéo 0 sau khi lọc qua bộ lọc Gauss Zero crossings Tìm biên bằng cách tìm điểm chéo 0 sau khi lọc qua bộ lọc của người sử dụng. Canny Tìm biên bằng cách tìm các cực đại địa phương của gradient f(x,y). Gradient được tính toán dùng đạo hàm cảu bộ lọc Gauss. Phương pháp dùng hai ngưỡng để tách các biên mạnh và yếu và gộp các biên yếu ở ngõ ra chỉ khi chúng được kết nối với các biên mạnh. Do đó, phương pháp này chỉ thích hợp hơn để tách các biên yếu thật sự. 2. Các bộ tách biên 2.1 Bộ lọc Sobel Bộ tách biên Sobel sử dụng các mặt nạ trong hình 1(b) để xấp xỉ đạo hàm bậc nhất và. Nói cách khác, gradient tại điểm tâm trong 1 lân cận được tính theo bộ tách Sobel: Khi đó, ta nói rằng vị trí (x,y) là pixel biene nếu tại vị trí đó, trong đó T là một ngưỡng được chỉ định. (a) (b) ( c ) (d) Hình 1: Một số mặt nạ tách biên và đạo hàm bậc nhất chúng thực hiện. Bộ tách biên Sobel có thể được thực hiện bằng cách lọc 1 ảnh, f, (dùng imfilter) với mặt nạ bên trái hình 1(b), lọc lại f với mặt nạ khác bình phương các giá trị pixel với mỗi ảnh được lọc, cộng hai kết quả và tính căn bậc hai. Hàm edge đơn giản các gói toán tử trước thành một hàm gọi và thêm vào các đặc tính khác chẳng hạn như chấp nhận một giá trị ảnh ngưỡng hoặc xác định ngưỡng một cách tự động. Thêm vào đó, edge chứa các kỹ thuật tách biên không thực hiện trực tiếp được bằng imfilter. Cú pháp gọi bộ tách biên Sobel tổng quát là: [g , t ] = edge(f, ‘sobel’, T, dir) Trong đó f là ảnh đầu vào, T là ngưỡng được chỉ định và dir xác định hướng cần tách biên : ‘ngang’, ‘dọc’ hoặc cả hai. Như trên g là ảnh logic chứa giá trị tại những nơi biên được tách và giá trị không tại những nơi biên không được tách. Tham số t trong ngõ ra là tùy chọn, nó là giá trị ngưỡng được dùng bởi edge. Nếu T được chỉ định thì t = T. Mặt khác, nếu T không được chỉ định ( hoặc để rỗng []), f sẽ đặt t bằng với ngưỡng do nó tự động xác định và sau đó sử dụng cho việc tách biên, 1 trong lý do cơ bản cho việc gộp t trong tham số ngõ ra là để nhận giá trị khởi tạo cho ngưỡng. Hàm edge sử dụng bộ tách Sobel mặc đính nếu cú pháp g= edge(f) hoặc là [g,t] = edge(f). 2.2 Bộ tách biện Prewitt Bộ tách biên Prewitt sử dụng mặt nạ trong hình 1 (c) để xấp xỉ theo phương pháp số đạo hàm bậc nhất và . Cú pháp tổng quát là: [g , t ] = edge(f, ‘prewitt’, T, dir) Tham số hàm này đồng nhất với tham số Sobel. Bộ tách biên Prewitt đơn giản hơn để thực hiện bằng máy tính so với bộ tách Sobel, nhưng nó có khuynh hướng sinh ra một chút nhiễu. Nó có thể được thể hiện qua hệ số 2 trong bộ tách biên hàm trơn. 2.3 Bộ tách biên Roberts Bộ tách biên Robert sử dụng mặt nạ trong hình 1(d) để xấp xỉ theo phương pháp số đạo hàm bậc nhất và . Cú pháp tổng quát là: [g , t ] = edge(f, ‘roberts’, T, dir) Tham số hàm này đồng nhất với tham số Sobel. Bộ tách biên Roberts là một trong những bộ tách biên xưa nhất trong xử lý ảnh số và theo hình 1(d) nó cũng đơn giản nhất. Bộ tách biên này được dùng ít hơn đáng kể các bộ tách khác do chức năng giới hạn của nó ( ví dụ như: nó ko đối xứng và không thể được tổng quát hóa để tách biên là thừa số của 450). Tuy nhiên, nó vẫn được dùng thường xuyên trong thực hiện phần cứng khi tính đơn giản và tốc độ là các yếu tố chi phối. 2.4 Bộ tách biên Laplace của hàm Gauss (LoG) Xét hàm Gauss Trong đó và độ lệch chuẩn. Đây là hàm trơn, nếu nó chập với một ảnh nó sẽ làm mờ ảnh. Độ mờ được xác định bởi giá trị . Toán tử Laplace của hàm này ( đạo hàm bậc 2 theo r): Với những lý do rõ ràng, hàm này gọi là toán tử Laplace của hàm Gauss (LoG). Vì đạo hàm bậc 2 là toán tử tuyến tính, chập( lọc) với 1 ảnh bằng giống như đầu tiên chập ảnh với hàm trơn và sau dó tính kết quả của toán tử Laplace. Đây là chìa khóa khái niệm cơ bản của bộ tách LoG. Chúng ta chập ảnh bằng biết nó có 2 tác động: nó làm mịn ảnh ( do đó giảm nhiễu ) và nó tính toán tử Laplace, làm cong 1 ảnh biên kép. Định vị các biên sau đó tìm các điểm giao zero giữa các biên kép. Cú pháp gọi tổng quát là: [g , t ] = edge(f, ‘log’, T, sigma) Trong đó sigma là độ lệch chuẩn và các tham số còn lại tương tự như các bộ tách biên ở trên. Giá trị mặc định của sigma là 2. Như đã nói, bỏ qua bất cứ biên nào không lớn hơn T. Nếu T không được cho hoặc rỗng [ ], edge chọn giá trị một cách tự động. Đặt T từ 0 tạo các biên là các đường viền kín, 1 đặc tính quen thuộc của phương pháp LoG. 2.5 Bộ tách biên điểm giao Zero Bộ tách biên này dựa trên khái niệm giống phương pháp LoG, nhưng phép chập được thực hiện sử dụng hàm lọc được chỉ định hàm H. Cú pháp gọi hàm : [g , t ] = edge(f, ‘zerocross’, T, H) Các tham số được