Nghiên cứu ứng dụng phân vùng ảnh trong xử lý ảnh

MỤC LỤC LỜI MỞ ĐẦU 1. Lý do chọn đề tài Trong những năm gần đây, cùng với sự phát triển vượt bậc của khoa học máy tính, thì xử lý ảnh là một là một lĩnh vực đang được quan tâm. Nó là một ngành khoa học còn tương đối mới mẻ so với nhiều ngành khoa học khác, nó cũng là đối tượng nghiên cứu lĩnh vực thị giác máy tính, là quá trình biến đổi ảnh từ một ảnh ban đầu sang một ảnh mới. Nhờ có công nghệ số hoá hiện đại, ngày nay con người đã có thể xử lý tín hiệu nhiều chiều thông qua nhiều hệ thống khác nhau, từ những mạch số đơn giản cho đến những mạch song song cao cấp. xử lý ảnh đã được nghiên cứu mạnh mẽ và đã có nhiều ứng dụng trong thực tế: như trong y học, xử lý ảnh để phát hiện và nhận dạng khối u, cải thiện ảnh X quang, nhận dạng đường biên mạch máu từ những ảnh chụp bằng tia X; Trong cuộc sống gia đình, xử lý ảnh được dùng để cải thiện ảnh tivi… Xử lý ảnh có liên quan đến nhiều ngành khác như: hệ thống thông tin, lý thuyết thông tin, lý thuyết thống kê, trí tuệ nhân tạo, nhận dạng… Xử lý ảnh cũng đã tạo ra được rất nhiều ứng dụng hữu ích trong thực tế như: bài toán nhận dạng vân tay, chữ viết, giọng nói… Để phân tích các đối tượng trong ảnh, chúng ta cần phải phân biệt được các đối tượng cần quan tâm với phần còn lại của ảnh. Những đối tượng này có thể tìm ra được nhờ các kỹ thuật phân đoạn ảnh, theo nghĩa tách phần tiền cảnh ra khỏi hậu cảnh trong ảnh. Chúng ta cần phải hiểu được là: - Không có kỹ thuật phân đoạn nào là vạn năng, theo nghĩa có thể áp dụng cho mọi loại ảnh. - Không có kỹ thuật phân đoạn nào là hoàn hảo. Có thể hiểu phân vùng là tiến trình chia ảnh thành nhiều vùng, mỗi vùng chứa một đối tượng hay nhóm đối tượng cùng kiểu. Chẳng hạn, một đối tượng có thể là một kí tự trên một trang văn bản hoặc một đoạn thẳng trong một bản vẽ kỹ thuật hoặc một nhóm các đối tượng có thể biểu diễn một từ hay hay đoạn thẳng tiếp xúc nhau. Phân vùng ảnh còn là một thao tác ở mức thấp trong toàn bộ quá trình xử lý ảnh. Quá trình này thực hiện việc phân vùng ảnh thành các vùng rời rạc và đồng nhất với nhau hay nói cách khác là xác định các biên của các vùng ảnh đó. Các vùng ảnh đồng nhất này thông thường sẽ tương ứng với tòan bộ hay từng phần của các đối tượng thật sự bên trong ảnh. Vì thế, trong hầu hết các ứng dụng của lĩnh vực xử lý ảnh (image processing), thị giác máy tính, phân vùng ảnh luôn đóng một vai trò cơ bản và thường là bước tiền xử lý đầu tiên trong toàn bộ quá trình trước khi thực hiện các thao tác khác ở mức cao hơn như nhận dạng đối tượng, biểu diễn đối tượng, nén ảnh dựa trên đối tượng, hay truy vấn ảnh dựa vào nội dung … Từ những lý do trên, tôi đã chọn đề tài “nghiên cứu ứng dụng phân vùng ảnh trong xử lý ảnh” cho bài nghiên cứu của mình. 2. Mục tiêu và nhiệm vụ 2.1. Mục tiêu Giúp người dùng công nghệ xử lý ảnh hiểu rỏ thêm về các phương pháp phân vùng ảnh. Đưa ra những ứng dụng thực tế của phân vùng ảnh trong khoa học và đời sống. 2.2. Nhiệm vụ Nghiên cứu phương pháp phân vùng ảnh theo ngưởng biên độ. Nghiên cứu phương pháp phân vùng ảnh theo miền đồng nhất. Nghiên cứu phương pháp phân vùng ảnh theo kết cấu bề mặt. Ngoài ra còn có nghiên cứu các phương pháp phân vùng dựa trên không gian đặt trưng, không gian ảnh và mô hình vật lý. 3. Đối tượng và phạm vi nghiên cứu Phân vùng ảnh dựa trên tính đồng đều ( độ tương tự của mức xám và các thuộc tính chung của các điểm ảnh trong mỗi vùng. Phân vùng ảnh dựa trên sự biến thiên của hàm độ xám hoặc mức xám ( phân vùng dựa trên tách biên). 4. Giả thiết nghiên cứu Hiểu được tổng quan về xử lý ảnh. Hiểu rỏ nguyên tắc phân vùng ảnh theo ngưởng biên độ. Nắm vững nguyên tắc phân vàn theo miền đồng chất gồm có ba phương pháp là: phương pháp tách cây tứ phân, phương pháp cục bộ và phương pháp tổng hợp. Trong phân vùng theo kết cấu bề mặt: chỉ ra hai phương pháp phân tích ảnh là thống kê và cấu trúc. 5. Phương pháp nghiên cứu Tìm hiểu rỏ các ứng dung của phân vùng ảnh. Xử dụng các thuật toán, hình ảnh để làm rỏ nội dung đề tài. 6. Ý nghĩa khoa học và thực tiển của đề tài Cùng với sự phát triển của phần cứng máng tính thì xử lý ảnh và đồ hoạ cũng đã phát triển mạnh mẻ và có nhiều ứng dụng trong cuộc sống. Nó đóng vai trò quan trọng trong việc tương tác giữa người và máy. Quá trình xử lý ảnh được xem như là quá trình thao tác ảnh đầu vào nhằm cho ra kết quả mong muốn. Kết quả đầu ra của quá trình xử lý ảnh có thể là một ảnh tốt hơn hoặc một kết luận. Nhưng trong đó, phân vùng ảnh là một trong những tính tất yếu quyết định đến chất lượng của hình ảnh. Vào những thời gian đầu, các phương pháp phân vùng ảnh được đưa ra chủ yếu làm việc trên các ảnh mức xám do các hạn chế về phương tiện thu thập và lưu trữ. Ngày nay, cùng với sự phát triển về các phương tiện thu nhận và biểu diễn ảnh , các ảnh màu đã hầu như thay thế hoàn toàn các ảnh mức xám trong việc biểu diễn và lưu trữ thông tin do các ưu thế vượt trội hơn hẳn so với ảnh mức xám. Do đó, các kỹ thuật, thuật giải mới thực hiện việc phân vùng ảnh trên các loại ảnh màu liên tục được phát triển để đáp ứng các nhu cầu mới. Các thuật giải, kỹ thuật này thường được phát triển dựa trên nền tảng các thuật giải phân vùng ảnh mức xám đã có sẵn. GIẢI QUYẾT VẤN ĐỀ Chương I: Tổng quan về xử lý ảnh 1.1. xử lý ảnh, các vấn đề cơ bản trong xử lý ảnh 1.1.1. xử lý ảnh là gì? Xử lý ảnh là một lĩnh vực mang tính khoa học và công nghệ. Nó là một ngành khoa học mới mẻ so với nhiều ngành khoa học khác nhưng tốc độ phát triển của nó rất nhanh, kích thích các trung tâm nghiên cứu, ứng dụng, đặc biệt là máy tính chuyên dụng riêng cho nó. Quá trình xử lý ảnh được xem như là quá trình thao tác ảnh đầu vào nhằm cho ra kết quả mong muốn. Kết quả đầu ra của một quá trình xử lý ảnh có thể là một ảnh “tốt hơn” hoặc một kết luận. Ảnh “tốt hơn” Kết luận Xử lý ảnh Ảnh Hình 1.1. Quá trình xử lý ảnh Hệ quyết định Ảnh có thể xem là tập hợp các điểm ảnh và mỗi điểm ảnh được xem như là đặc trưng cường độ sáng hay một dấu hiệu nào đó tại một vị trí nào đó của đối tượng trong không gian và nó có thể xem như một hàm n biến P(c1, c2,..., cn). Do đó, ảnh trong xử lý ảnh có thể xem như ảnh n chiều. Sơ đồ tổng quát của một hệ thống xử lý ảnh: Đối sánh rút ra kết luận Lưu trữ Hậu xử lý Trích chọn dặc điểm Tiền xử lý Thu nhận ảnh Hình 1.2. Các bước cơ bản trong một hệ thống xử lý ảnh 1.1.2. Các khái niệm cơ bản trong xử lý ảnh * Ảnh và điểm ảnh: Điểm ảnh được xem như là dấu hiệu hay cường độ sáng tại một toạ độ trong không gian của đối tượng và ảnh được xem như là một tập hợp các điểm ảnh. * Mức xám, màu: Là số các giá trị có thể có của các điểm ảnh của ảnh. 1.2. Thu nhận và biểu diển ảnh 1.2.1. Thu nhận, các thiết bị thu nhận ảnh Các thiết bị thu nhận ảnh bao gồm camera, scanner các thiết bị thu nhận này có thể cho ảnh đen trắng Các thiết bị thu nhận ảnh có 2 loại chính ứng với 2 loại ảnh thông dụng Raster, Vector. Nhìn chung các hệ thống thu nhận ảnh thực hiện 1 quá trình • Cảm biến: biến đổi năng lượng quang học thành năng lượng điện • Tổng hợp năng lượng điện thành ảnh. 1.2.2. Biểu diển ảnh Ảnh trên máy tính là kết quả thu nhận theo các phương pháp số hoá được nhúng trong các thiết bị kỹ thuật khác nhau. Quá trình lưu trữ ảnh nhằm 2 mục đích: • Tiết kiệm bộ nhớ • Giảm thời gian xử lý Việc lưu trữ thông tin trong bộ nhớ có ảnh hưởng rất lớn đến việc hiển thị, in ấn và xử lý ảnh được xem như là 1 tập hợp các điểm với cùng kích thước nếu sử dụng càng nhiều điểm ảnh thì bức ảnh càng đẹp, càng mịn và càng thể hiện rõ hơn chi tiết của ảnh người ta gọi đặc điểm này là độ phân giải. Việc lựa chọn độ phân giải thích hợp tuỳ thuộc vào nhu cầu sử dụng và đặc trưng của mỗi ảnh cụ thể, trên cơ sở đó các ảnh thường được biểu diễn theo 2 mô hình cơ bản: mô hình Raster và mô hình vector. 1.2.2.1. Mô hình Raster Đây là cách biểu diễn ảnh thông dụng nhất hiện nay, ảnh được biểu diễn dưới dạng ma trận các điểm (điểm ảnh). Thường thu nhận qua các thiết bị như camera, scanner. Tuỳ theo yêu cầu thực thế mà mỗi điểm ảnh được biểu diễn qua 1 hay nhiều bít. Mô hình Raster thuận lợi cho hiển thị và in ấn. Ngày nay công nghệ phần cứng cung cấp những thiết bị thu nhận ảnh Raster phù hợp với tốc độ nhanh và chất lượng cao cho cả đầu vào và đầu ra. Một thuận lợi cho việc hiển thị trong môi trường Windows là Microsoft đưa ra khuôn dạng ảnh DIB (Device Independent Bitmap) làm trung gian. Một trong những hướng nghiên cứu cơ bản trên mô hình biểu diễn này là kỹ thuật nén ảnh các kỹ thuật nén ảnh lại chia ra theo 2 khuynh hướng là nén bảo toàn và không bảo toàn thông tin nén bảo toàn có khả năng phục hồi hoàn toàn dữ liệu ban đầu còn nếu không bảo toàn chỉ có khả năng phục hồi độ sai số cho phép nào đó. Theo cách tiếp cận này người ta đã đề ra nhiều quy cách khác nhau như BMP, TIF, GIF, PCX… Hiện nay trên thế giới có trên 50 khuôn dạng ảnh thông dụng bao gồm cả trong đó các kỹ thuật nén có khả năng phục hồi dữ liệu 100% và nén có khả năng phục hồi với độ sai số nhận được. BMP PCC …… Cửa sổ DIB panit thay đổi Hình 1.4. Quá trình hiển thị và chỉnh sửa, lưu trữ ảnh thông qua DIB 1.2.2.2. Mô hình Vector Biểu diễn ảnh ngoài mục đích tiết kiệm không gian lưu trữ dễ dàng cho hiển thị và in ấn còn đảm bảo dễ dàng trong lựa chọn sao chép di chuyển tìm kiếm…Theo những yêu cầu này kỹ thuật biểu diễn vector tỏ ra ưu việt hơn. Trong mô hình vector người ta sử dụng hướng giữa các vector của điểm ảnh lân cận để mã hoá và tái tạo hình ảnh ban đầu ảnh vector được thu nhận trực tiếp từ các thiết bị số hoá như Digital hoặc được chuyển đổi từ ảnh Raster thông qua các chương trình số hoá Công nghệ phần cứng cung cấp những thiết bị xử lý với tốc độ nhanh và chất lượng cho cả đầu vào và ra nhưng lại chỉ hỗ trợ cho ảnh Raster. Do vậy, những nghiên cứu về biểu diễn vectơ đều tập trung từ chuyển đổi từ ảnh Raster. RASTER RASTER VECTOR Vecter r raster hoá hoá Hình 1.5. Sự chuyển đổi giữa các mô hình biểu diển ảnh Tổng kết chương I Hiểu được khái quát về xử lý ảnh, các cách biểu diển ảnh và các mô hình trong quan hệ xử lý ảnh. Chương II: Khái quát về phân vùng ảnh 2.1. Một số khái niệm Phân vùng ảnh là một bước then chốt trong xử lý ảnh. Giai đoạn này nhằm phân tích ảnh thành những thành phần có cùng tính chất dựa theo biên hay các vùng liên thông. Tiêu chuẩn để xác định các vùng liên thông có thể là mức xám, cùng màu hay độ nhám… Vùng ảnh (Region): là tập hợp các điểm ảnh có chung các thuộc tính thuộc về một đối tượng nào đó. Phân vùng ảnh (Image Segmentation): là quá trình phân hoạch tập các điểm ảnh của X thành các tập con R (hay một vùng ảnh) thỏa mãn các điều kiện sau: + R ≠ Æ + R Ç R = Æ (i ≠ j, " i,j) + È R = X, " i R : bao gồm các pixel có chung các thuộc tính nào đó. 2.2. Các hướng tiếp cận phân vùng ảnh Phân vùng ảnh là chia ảnh thành các vùng không trùng lắp. Mỗi vùng gồm một nhóm pixel liên thông và đồng nhất theo một tiêu chí nào đó. Tiêu chí này phụ thuộc vào mục tiêu của quá trình phân đoạn. Ví dụ như đồng nhất về màu sắc, mức xám, kết cấu, độ sâu của các layer… Sau khi phân đoạn mỗi pixel chỉ thuộc về một vùng duy nhất. Để đánh giá chất lượng của quá trình phân đoạn là rất khó. Vì vậy trước khi phân đoạn ảnh cần xác định rõ mục tiêu của quá trình phân đoạn là gì. Xét một cách tổng quát, ta có thể chia các hướng tiếp cận phân đoạn ảnh thành các nhóm chính như sau: - Dựa trên tính đồng đều ( độ tương tự của mức xám và các thuộc tính chung của các điểm ảnh trong mỗi vùng. - Phân vùng ảnh dựa trên sự biến thiên của hàm độ xám hoặc mức xám ( phân vùng dựa trên tách biên). 2.3. Các công đoạn chính của phân vùng ảnh - Gồm 3 công đoạn sau: + Tiền xử lý ảnh ( nếu có ) + Quá trình phân vùng ảnh ( thực hiện dựa trên các thuật toán ) + Đánh nhãn cho các vùng ảnh được phân tách và điều chỉnh nếu cần - Ngoài ra việc phân vùng ảnh còn dựa trên các phương pháp phân vùng chính là: + Phân vùng theo ngưỡng biên độ. + Phân vùng ảnh theo miền đồng nhất. + Phân vùng ảnh theo kết cấu bề mặt. 2.4. Một số thuộc tính của điểm ảnh và vùng ảnh 2.4.1. Một số thuộc tính của điểm ảnh - Giả sử có một điểm ảnh X = { P } , trong đó P là pixel thứ i ( i = 1,…, M*N) Có 2 loại ảnh sau: + Ảnh đơn màu : P được biểu diễn bằng giá trị mức xám ( độ xám ). Kí hiệu A(P) hoặc X(P). + Ảnh đa màu ( đa phổ ) : mỗi pixel được biểu diễn bởi một vecto màu mà ta gọi là vecto thuộc tính. P = - Độ tương phản giữa hai điểm ảnh ( S, S ) = | A(S) – A(S) | / ( L-1) Trong đó L : giá trị mức xám lớn nhất của ảnh 2.4.2. Một số thuộc tính của vùng ảnh - Độ đồng đều mức xám của một vùng ảnh R : E(R) = ( A(P) – m ) Trong đó : card(R) là số phần tử của vùng R ( lực lượng của vùng R ) A(P) là giá trị mức xám của một điểm ảnh m là giá trị trung bình được tính bằng công: m = A(P) - Hàm vị từ của R ( Pred (R) ) : để đo độ đồng đều của mức xám, được định nghĩa như sau: Pred(R) = Trong đó: q là ngưỡng tự chọn : nếu Pred(R) = 1 thì vùng R là vùng đồng đều Pred(R) = 0 thì vùng R là không đồng đều Thuộc tính tần số, thuộc tính thống kê, thuộc tính cấu trúc Tổng kết chương II Làm rỏ vấn đề phân vùng ảnh và các thuộc tính của nó trong xử lý ảnh. Chương III: Các phương pháp phân vùng ảnh 3.1. Phân vùng ảnh theo ngưởng biên độ Các đặc tính đơn giản, cần thiết nhất của ảnh là biên độ và các tính chất vật lý như: độ tương phản, độ truyền sáng, màu sắc hoặc đáp ứng phổ. Như vậy, có thể dùng ngưỡng biên độ để phân vùng khi biên độ đủ lớn đặc trưng cho ảnh. Thí dụ, biên độ trong bộ cảm biến ảnh hồng ngoại có thể phản ánh vùng có nhiệt độ thấp hay vùng có nhiệt độ cao. Kỹ thuật phân ngưỡng theo biên độ rất có lợi đối với ảnh nhị phân như văn bản in, đồ họa, ảnh màu hay ảnh X-quang. Việc chọn ngưỡng rất quan trọng. Nó bao gồm các bước : • Xem xét lược đồ xám của ảnh để xác định các đỉnh và các khe. Nếu ảnh có dạng rắn lượn (nhiều đỉnh và khe), các khe có thể dùng để chọn ngưỡng. • Chọn ngưỡng t sao cho một phần xác định trước η của toàn bộ số mẫu là thấp hơn t. • Điều chỉnh ngưỡng dựa trên lược đồ xám của các điểm lân cận. • Chọn ngưỡng theo lược đồ xám của những điểm thỏa mãn tiêu chuẩn chọn. Thí dụ, với ảnh có độ tương phản thấp, lược đồ của những điểm có biên độ Laplace g(m,n) lớn hơn giá trị t định trước (sao cho từ 5% đến 10% số điểm ảnh với Gradient lớn nhất sẽ coi như biên) sẽ cho phép xác định các đặc tính ảnh lưỡng cực tốt hơn ảnh gốc. • Khi có mô hình phân lớp xác suất, việc xác định ngưỡng dựa vào tiêu chuẩn xác suất nhằm cực tiểu xác suất sai số hoặc dựa vào một số tính chất khác của luật Bayes. 3.1.1. Kỹ thuật lấy ngưởng Kỹ thuật này dựa trên một ý tưởng hết sức đơn giản. Một tham số q, gọi là ngưỡng độ sáng, sẽ được chọn để áp dụng cho một ảnh a[m,n] theo cách sau: Nếu  thì  Ngược lại   Thuật toán trên giả định rằng chúng ta đang quan tâm đến các đối tượng sáng (object) hay nền ảnh (background) bằng các giá trị “1” hoặc “0”. 3.1.1.1. Ngưỡng cố định Phương pháp đầu tiên là chọn một ngưỡng độc lập với dữ liệu ảnh. Nếu chúng ta biết trước là chương trình ứng dụng sẽ làm việc với những ảnh có độ tương phản rất cao, trong đó các đối tuợng quan tâm rất tối còn nền gần như đồng nhất và rất sáng, thì giá trị ngưỡng không đổi 128 trên thang độ sáng từ 0 đến 255 sẽ là một giá trị chọn khá chính xác. Chính xác ở đây nên được hiểu theo nghĩa là số lượng các điểm ảnh bị phân lớp sai là cực tiểu. 3.1.1.2. Ngưỡng dựa trên lược đồ Trong hầu hết các trường hợp, ngưỡng được chọn từ lược đồ độ sáng của vùng hay ảnh cần được phân đoạn. Có rất nhiều kỹ thuật chọn ngưỡng tự động xuất phát từ lược đồ xám. Những kỹ thuật phổ biến nhất trong số đó sẽ được trình bày dưới đây. Những kỹ thuật này có thể tận dụng lợi thế do sự làm trơn dữ liệu lược đồ ban đầu mang lại, nhằm loại bỏ những dao động nhỏ về độ sáng. Tuy nhiên các thuật toán làm trơn cần phải cẩn trọng không được làm dịch chuyển các vị trí đỉnh của lược đồ.  3.2. Phương pháp phân vùng ảnh theo miền đồng nhất Kỹ thuật phân vùng ảnh thành các miền đồng nhất dựa vào các tính chất quan trọng nào đó của miền ảnh. Việc lựa chọn các tính chất của miền sẽ xác định tiêu chuẩn phân vùng. Tính đồng nhất của một miền ảnh là điểm chủ yếu xác định tính hiệu quả của việc phân vùng. Các tiêu chuẩn hay được dùng là sự thuần nhất về mức xám, màu sắc đối với ảnh màu, kết cấu sợi và chuyển động. Các phương pháp phân vùng ảnh theo miền đồng nhất thường áp dụng là : • Phương pháp tách cây tứ phân • Phương pháp cục bộ • Phương pháp tổng hợp 3.2.1. Phương pháp tách cây tứ phân Về nguyên tắc, phương pháp này kiểm tra tính hợp thức của tiêu chuẩn một cách tổng thể trên miền lớn của ảnh. Nếu tiêu chuẩn được thỏa mãn, việc phân đoạn coi như kết thúc. Trong trường hợp ngược lại, ta chia miền đang xét thành 4 miền nhỏ hơn. Với mỗi miền nhỏ, ta áp dụng một cách đệ quy phương pháp trên cho đến khi tất cả các miền đều thỏa. Một vùng thỏa chuẩn sẽ tạo nên một nút lá, nếu không nó sẽ tạo nên một nút trong và có 4 nút con tương ứng với việc chia làm 4 vùng. Ta cứ tiếp tục như vậy cho đến khi phân xong. Các nút của cây biểu diễn số vùng đã phân. Tiêu chuẩn phân vùng ở đây là màu sắc. Nếu mọi điểm của vùng đều là màu trắng thì sẽ tạo nên nút lá trắng và tương tự như vậy với nút lá đen. Nút màu ghi vùng không thuần nhất và phải tiếp tục chia. Với ngưỡng q cho trước, vùng thuần nhất phải thỏa điều kiện: · Độ lệch chuẩn s < q · Hoặc  với Max, Min lần lượt là giá trị lớn nhất và nhỏ nhất của mức xám trong vùng cần chia. 3.2.2. Phương pháp cục bộ Ý tưởng của phương pháp là xét ảnh từ các miền nhỏ nhất rồi nối chúng lại nếu thỏa mãn tiêu chuẩn để được một miền đồng nhất lớn hơn. Tiếp tục với các miền thu được cho đến khi không thể nối thêm được nữa. Số miền còn lại cho ta kết quả phân đoạn. Như vậy, miền nhỏ nhất của bước xuất phát là điểm ảnh. Phương pháp này hoàn toàn ngược với phương pháp tách. Song điều quan trọng ở đây là nguyên lý nối 2 vùng. Việc nối 2 vùng được thực hiện theo nguyên tắc sau : - Hai vùng phải đáp ứng tiêu chuẩn, thí dụ như cùng màu hay cùng mức xám. - Hai vùng phải kế cận nhau. Dựa theo nguyên lý của phương pháp nối, ta có 2 thuật toán : - Thuật toán tô màu (Blob Coloring) : sử dụng khái niệm 4 liên thông, dùng một cửa sổ di chuyển trên ảnh để so sánh với tiêu chuẩn nối. - Thuật toán đệ quy cực bộ: sử dụng phương pháp tìm kiếm trong một cây để làm tăng kích thước vùng. 3.2.3. Phương pháp tổng hợp Hai phương pháp nối (hợp) và tách đều có nhược điểm. Phương pháp tách sẽ tạo nên một cấu trúc phân cấp và thiết lập mối quan hệ giữa các vùng. Tuy nhiên, nó thực hiện việc chia quá chi tiết. Phương pháp hợp cho phép làm giảm số miền liên thông xuống tối thiểu, nhưng cấu trúc hàng ngang dàn trải, không cho ta thấy rõ mối liên hệ giữa các miền. Vì nhược điểm này, người ta nghĩ đến phối hợp cả hai phương pháp. Trước tiên, dùng phương pháp tách để tạo nên cây tứ phân, phân đoạn theo hướng từ gốc đến lá. Tiếp theo, tiến hành duyệt cây theo chiều ngược lại và hợp các vùng có cùng tiêu chuẩn. Với phương pháp này ta thu được một cấu trúc ảnh với các miền liên thông có kích thước tối đa. Giải thuật tách hợp gồm một số bước chính sau: Bước1: Kiểm tra tiêu chuẩn đồng nhất. Nếu không thỏa mãn tiêu chuẩn đồng nhất và số điểm trong một vùng nhiều hơn 1, tách vùng ảnh làm 4 miền (trên, dưới, phải, trái) bằng cách đệ quy. Nếu kết quả tách xong và không tách được nữa chuyển sang bước 2. Nếu tiêu chuẩn đồng nhất thỏa mãn thì tiến hành hợp vùng và cập nhật lại giá trị trung bình của vùng cho vùng này. Bước 2:Hợp vùng. Kiểm tra 4 lân cận như đã nêu trên. Có thể có nhiều vùng thỏa mãn. Khi đó, chọn vùng tối ưu nhất rồi tiến hành hợp. 3.3. Phân vùng ảnh theo kết cấu bề mặt Kết cấu thường được nhận biết trên bề mặt của các đối tượng như gỗ, cát, vải vóc…Kết cấu là thuật ngữ phản ánh sự lặp lại của các phần tử sợi (texel) cơ bản. Sự lặp lại này có thể ngẫu nhiên hay có tính chu kì hoặc gần chu kì. Một texel chứa rất nhiều điểm ảnh. Trong phân tích ảnh, kết cấu được chia làm hai loại chính là: loại thống kê và loại cấu trúc. 3.3.1. Tiếp cận thống kê Tính kết cấu ngẫu nhiên rất phù hợp với các đặc trưng thống kê. Vì vậy, người ta có thể dùng các đặc trưng ngẫu nhiên để đo nó như: Hàm tự tương quan(AutoCorrelation Function-ACF), các biến đổi mật độ gờ, ma trận tương tranh, v.v. Theo cách tiếp cận bằng hàm tự tương quan, độ thô của kết cấu sợi tỉ lệ với độ rộng của ACF, được biểu diễn bởi khoảng cách x , y : sao cho ( x , 0) = r(0, y ) = 1. Người ta cũng dùng cách đo nhánh của ACF nhờ hàm khởi tạo moment: M(k,l) = (m- m) (n- m)r(m,n) Với : m= mr(m,n) và m= nr(m,n) Các đặc trưng của kết cấu sợi như độ thô, độ mịn hay hướng có thể ước lượng nhờ các biến đổi ảnh bằng kỹ thuật lọc tuyến tính . Một mô hình đơn giản trong trường ngẫu nhiên cho việc phân tích tính kết cấu được mô tả trong hình 2.1. m(m,n) Trích chọn đặc tính Phân tích lược Lọc dài tương Đặc tính sợi Hình 2.1. Phân tích kết cấu sợi bằng dải tương quan. Trong mô hình này, trường kết cấu sợi trước tiên được giải chập bởi bộ lọc lấy từ đầu ra của ACF. Như vậy, nếu r(m, n) là ACF thì: U(m, n)Ä a(m, n) = e (m, n) là một trường ngẫu nhiên không tương quan. Ngoài các đặc trưng trên, có thể đưa thêm một số khái niệm và định nghĩa các đại lượng dựa trên đó như: lược đồ hiệu mức xám(Histogram grey level difference). Ma trận xuất hiện mức xám (grey level occurence matrices). Lược đồ hiệu mức xám dùng để mô tả các thông tin mang tính không gian và được định nghĩa như sau: Cho d = (d1, d2) là véctơ dịch chuyển giữa 2 điểm ảnh và g(d) là hiệu mức xám với khoảng cách d: g(d) = |f(k,l) – f(k+d,l+d ) Với f(k, l) hàm cho giá trị mức xám tại tọa độ (k, l). Gọi h(g, d) là lược đồ của hiệu mức xám với khoảng cách d. Như vậy, với mỗi khoảng cách d ta có 1 lược đồ riêng. Với mỗi điểm ảnh có kết cấu thô lược đồ h(g, d) có khuynh hướng tập trung xung quanh g= 0 với khoảng cách d nhỏ. Trái lại, với một miền ảnh có kết cấu mịn, h(g, d) sẽ phân nhánh dù với véctơ dịch chuyển d là khá nhỏ. Dựa trên lược đồ này, người ta định nghĩa lại một số đại lượng: Trung bình: m = g h (g , d) Phương sai: s = ( g k - m) h ( g , d) Độ tương phản: c = g h (g , d) Phương sai đo độ tản mát của hiệu mức xám tại một khoảng cách d nào đấy.Kết cấu tất định thường có khuynh hướng có phương sai s tương đối nhỏ. Độ tương phản cd chính là mômen của lược đồ hg(g, d) xung quanh g=0 và đo độ tương phản của hiệu mức xám. Người ta cũng sử dụng entropy để đo độ đồng nhất của lược đồ hg: H = - h (g , d)ln (h (g , d)) Ưu điểm cơ bản của lược đồ hiệu mức xám là tính toán đơn giản. Ngoài ra còn có khả năng cho ta tổ chức kết cấu không gian. Ma trận xuất hiện liên hiệp mức xám: gọi P(k, l , d) là xác suất liên hiệp của hai điểm ảnh fk và fl với các mức xám k, l tương ứng cách nhau một khoảng d. Xác suất này dễ dàng tính được nhờ việc tính số lần xuất hiện nk, l của điểm ảnh (fk, fl) có mức xám k và l với khoảng cách d. Gọi n là tổng số cặp liên hiệp mức xám cd được tính như sau: c = (c ) Và c= P(k,l,d) = Ma trận xuất hiện liên hiệp mức xám Cd là ma trận vuông N*N phần tử (N là số mức xám của ảnh). Ma trận này chứa đựng các thông tin rất hữu ích về tổ chức kết cấu không gian. Nếu cấu tương đối thô thì các phần tử của ma trận tập trung xung quanh đường chéo chính. Ngược lại nếu kết cấu bề mặt mịn giá trị các phần tử của cd sẽ phân rải tương đối rõ: Dựa trên khái niệm này người ta định nghĩa về một số độ đo: Xác xuất cực đại: P = max C Entropy: H d = - C ln(C) Dễ dàng thấy entropy cực đại khi xác suất liên hiệp P(k, l, d) có phân phối đều. Mô men hiệu bậc m: I = | k- 1| C Id cực tiểu khi các phần tử của ma trận C tập trung trên đường chéo chính vì khoảng cách | k- 1| là rất nhỏ. Id nhỏ có nghĩa là kết cấu khá thô. Người ta cũng còn đưa vào một số độ đo khác như hàm tự tương quan, phổ năng lượng. Kết cấu sợi có cấu trúc thuần nhất là những texels xác định, mà sự xuất hiện lập đi lặp lại tuân theo một luật tất định hay ngẫu nhiên nào đấy. Một texel về thực tế là một nhóm các pixel có cùng một số tính chất bất biến lặp trên ảnh. Một texel cũng có thể định nghĩa theo mức xám, theo bề mặt hay tính đồng nhất đối với một số các tính chất như kích thước, hướng, lược đồ bặc hai (ma trận tương tranh). Với các texel được phân bố ngẫu nhiên, tính kết cấu sợi tương ứng của nó được coi la yếu (weak) ngược lại với quy luật phân bố tất định gọi là khỏe (strong). Khi tính kết cấu sợi là yếu, luật phân bố có thể đo bởi: Mật độ gờ. Các loạt dài của các texel liên thông tối đa. Mật độ cực trị tương đối: số pixel trên một đơn vị diện tích có mức xám cực trị cục bộ địa phương so với các lân cận. Ngoài hai cách tiếp cận trên, người ta còn dùng cách tiếp cận khác bằng cách lấy tổ hợp 2 cách trên và gọi là kĩ thuật mosaic. Mô hình này biểu diễn các quá trình hình học ngẫu nhiên, thí dụ nhu khảm ngẫu nhiên hay đều của một mặt phẳng vào các đường cong nổi lên tính kết cấu tế bào. 3.3.3. Tiếp cận thao tính kết cấu Khi đối tượng xuất hiện trên một nền có tính kết cấu cao, việc phân đoạn dựa vào tính kết cấu trở nên quan trọng. Nguyên nhân là kết cấu sợi thường chứa mật độ cao các gờ (edge) làm cho phân đoạn theo biên kém hiệu quả, trừ khi ta loại tính kết cấu. Việc phân đoạn dựa vào miền đồng nhất cũng có thể áp dugnj cho các đặt trưng kết cấu và có thể dùng để phân đoạn các miền có tính kết cấu. Tồng kết chương III Dựa vào các công thức, các thuật toán để làm rỏ các phương pháp phân vùng ảnh, đồng thời khẳng định phân vùng ảnh là một yếu tố không thể thiếu trong xử lý ảnh. KẾT LUẬN Luận văn đã đưa ra được các lý thuyết tổng quan về xử lý ảnh và phân vùng ảnh, khẳng định được phân vùng ảnh là một bước then chốt trong xử lý ảnh. Vì vậy, việc nghiên cứu phát triển kỹ thuật phân vùng ảnh có ý nghĩa rất to lớn trong xử lý ảnh. Ngoài ra, nó còn cho thấy được các phương pháp phân vùng ảnh ứng vói từng thuật toán nhất định, từ đó chúng ta có thể vận dụng tốt hơn những ứng dụng phân vùng ảnh này vào thực tiển đồi sống. KẾ HOẠCH DỰ KIẾN TRIỂN KHAI ĐỀ TÀI STT Thời gian Nội dung thực hiện Kết quả dự kiến 1 10/2012 - 01/2013 Nghiên cứu lý thuyết về xử lý ảnh. Nắm vững kiến thức về xử lý ảnh. 2 01/2013 – 04/2013 Nghiên cứu ứng dụng phân vùng ảnh trong xử lý ảnh. Hiểu được ý nghĩa của phân vùng ảnh. 3 04/2013 – 06/2013 Nghiên cứu các phương pháp chính trong phân vùng ảnh. Hoàn thành đề tài nghiên cứu. HƯỚNG NGHIÊN CỨU TIẾP THEO Nghiên cứu kỹ thuật nâng cao các phương pháp phân vùng ảnh. TÀI LIỆU THAM KHẢO Tiếng việt [1] Th.S Nguyễn Duy Nhật Viển, giáo trình xử lý ảnh, 2006 [2] Lương Mạnh Bá và Nguyễn Thanh Thuỷ, nhập môn xử lý ảnh, nhà xuất bản khoa học và kỷ thuật, 2003 [3] Võ Đức khánh, Hoàng Văn Kiếm. Giáo trình xử lý ảnh số. Nhà xuất bản đại học quốc gia thành phố HCM Tiếng anh [4] Bhabatosh Chanda, Dwijesh Dutta Maumder. Digital image processing and analysis. Prentice hall of India, 2001 [5] Anil K. Jain Englewood Cliffs, Fundamentals of Digital Image Processing Trang web [6] Tailieu.vn./. [7] Ebook.com.vn./. Ý KIẾN CỦA CÁN BỘ HƯỚNG DẨN ……………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………… Quảng Nam, ngày tháng 11 năm 2012 Cán bộ hướng dẩn Ý KIẾN CỦA HỘI ĐỒNG CHẤM ĐỀ CƯƠNG ……………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………… Quảng Nam, ngày tháng 11 năm 2012