Đồ án tốt nghiệp: Tìm hiểu phương pháp làm mảnh ảnh (Thinning)

Tìm hiểu kỹ thuật làm mảnh ảnh, khám phá các phương pháp phổ biến và ứng dụng thực tế để tối ưu tốc độ tải trang và thiết kế web hiệu quả.

• Tác giả: Hà Đức Kiên
• Chuyên ngành: Xử lý ảnh
• Đề tài: Tìm hiểu phương pháp làm mảnh ảnh
• Loại tài liệu: Đồ án tốt nghiệp

Mục lục chi tiết

• LỜI NÓI ĐẦU
• 1. CHƯƠNG 1: TỔNG QUAN VỀ LÀM MẢNH ẢNH
• 1.1. Xử lý ảnh
• 1.2. Biểu diễn ảnh
• 1.3. Nhận dạng
• 1.4. Xương và các phương pháp tìm xương
• 1.4.1. Thế nào là xương và làm mảnh ảnh
• 1.4.2. Phương pháp thay đổi trục trung vị
• 1.4.3. Phương pháp tìm xương dựa trên làm mảnh
• 1.5. Các khái niệm cơ bản trong làm mảnh
• 1.6. Các tính chất và yêu cầu đối với làm mảnh
• 1.6.1. Yêu cầu về thời gian và số phép toán
• 1.6.2. Yêu cầu về khả năng tái tạo mẫu ban đầu
• 1.6.3. Yêu cầu về tính đẳng hướng và tính bất biến
• 1.6.4. Yêu cầu tính liên thông và tính Tô pô
• 1.6.5. Yêu cầu về tính hình học
• 2. CHƯƠNG 2 CÁC THUẬT TOÁN LÀM MẢNH TUẦN TỰ
• 2.1. Khi sử dụng các thuật toán làm mảnh tuần tự, các điểm biên được kiểm tra để xoá đi theo một thứ tự định trước, điều này có thể được hoàn thành bằng cách dò theo loạt hoặc theo biên. Làm mảnh theo các điểm biên
• 2.2. Thuật toán của Chu và Suen
• 2.3. Thuật toán của Arcelli
• 3. CHƯƠNG 3: CÁC THUẬT TOÁN LÀM MẢNH SONG SONG
• 4. CHƯƠNG 4: Cài đặt thực nghiệm

Tóm tắt

I. Tổng Quan Đồ Án Tìm Hiểu Phương Pháp Làm Mảnh Ảnh

Đồ án tốt nghiệp tập trung vào lĩnh vực xử lý ảnh, cụ thể là làm mảnh ảnh (thinning). Đây là một bước tiền xử lý quan trọng, hỗ trợ các bước tiếp theo trong quá trình nhận dạng ảnh. Mục tiêu chính là giới thiệu các khái niệm, phân loại và thuật toán liên quan đến phương pháp làm mảnh ảnh, đồng thời đưa ra đánh giá chi tiết cho từng loại thuật toán. Đồ án được cấu trúc thành bốn chương, bao gồm ba chương lý thuyết và một chương về cài đặt thực nghiệm. Làm mảnh ảnh giúp giảm thiểu dữ liệu, làm nổi bật các đặc trưng quan trọng, tạo tiền đề cho việc phân tích và nhận dạng hình ảnh hiệu quả hơn. Vai trò của làm mảnh ảnh ngày càng trở nên quan trọng trong bối cảnh khoa học nhận dạng phát triển mạnh mẽ, đặc biệt trong các ứng dụng đòi hỏi tốc độ và độ chính xác cao. Ứng dụng đa dạng, từ nhận dạng ký tự đến phân tích hình ảnh y tế. Thành công của đồ án này mở ra hướng nghiên cứu sâu hơn về các giải thuật tối ưu hóa cho làm mảnh ảnh.

1.1. Khái Niệm Cơ Bản về Xử Lý Ảnh và Biểu Diễn Ảnh

Xử lý ảnh số, tương tự như xử lý dữ liệu đồ họa, là một lĩnh vực ứng dụng của tin học. Nó bao gồm các phương pháp và kỹ thuật để biến đổi, truyền tải hoặc mã hóa các ảnh tự nhiên. Mục đích chính là biến đổi và làm đẹp ảnh, đồng thời tự động nhận dạng và đánh giá nội dung của ảnh. Trong xử lý ảnh bằng máy tính, ảnh được biểu diễn dưới dạng ma trận hai chiều. Mỗi phần tử của ma trận biểu diễn mức xám hoặc cường độ của điểm ảnh tương ứng (pixel). Tùy theo giá trị xám, ảnh được chia thành ảnh màu, ảnh xám hoặc ảnh nhị phân. Ảnh nhị phân chỉ có giá trị 0 hoặc 1, biểu diễn đen trắng. Ảnh xám sử dụng 1 byte (8 bit) để biểu diễn, cho phép 256 mức xám. Ảnh màu sử dụng 24 bit, chia thành 3 khoảng 8 bit cho các màu đỏ (red), lục (green) và lam (blue). Việc biểu diễn ảnh dưới dạng số cho phép áp dụng các thuật toán xử lý ảnh một cách hiệu quả.

1.2. Ứng Dụng Của Làm Mảnh Ảnh Trong Nhận Dạng

Nhận dạng là một ứng dụng quan trọng của làm mảnh. Việc nhận biết và đánh giá nội dung của ảnh (nhận dạng) là sự phân tích một hình ảnh thành những phần có nghĩa để phân biệt đối tượng này với đối tượng khác. Dựa vào đó, có thể mô tả cấu trúc của hình ảnh ban đầu. Một số phương pháp nhận dạng cơ bản bao gồm nhận dạng biên, tách cạnh và phân đoạn ảnh. Kỹ thuật này được sử dụng nhiều trong y học (xử lý tế bào, nhiễm sắc thể) và nhận dạng chữ trong văn bản. Quá trình nhận dạng liên quan đến mô tả đối tượng mà người ta muốn đặc tả nó, thường đi sau quá trình trích chọn các đặc tính. Có hai kiểu mô tả đối tượng: mô tả theo tham số và mô tả theo cấu trúc. Ứng dụng thực tế bao gồm nhận dạng chữ in, chữ viết tay, tăng tốc độ và chất lượng thu nhận thông tin.

II. Khám Phá Xương Ảnh và Các Phương Pháp Tìm Xương Ảnh

Xương ảnh là kết quả của việc làm mảnh ảnh, thể hiện hình dạng cơ bản của đối tượng với số lượng điểm ảnh tối thiểu. Việc tìm xương ảnh giúp trích xuất thông tin về hình dạng nguyên bản, vị trí, hướng và độ dài của đối tượng. Các kỹ thuật tìm xương ảnh là một chủ đề nghiên cứu phức tạp trong xử lý ảnh, và các thuật toán hiện tại thường bị mất mát thông tin do tính phức tạp của nó. Làm mảnh ảnh hữu dụng với các đối tượng là đường (thẳng hoặc cong) và không có tác dụng với các đối tượng có hình dạng đóng trong một vùng. Thông thường, làm mảnh là bước chuẩn bị cho các bước tiếp theo, làm việc trên các thuộc tính cần thiết của xương. Nghiên cứu về làm mảnh cần chú ý các vấn đề trên để đạt được hiệu quả cao nhất trong quá trình xử lý ảnh.

2.1. Phân Loại Các Thuật Toán Tìm Xương Cơ Bản

Có hai phương pháp tìm xương cơ bản: phương pháp biến đổi trục trung vị (MFA) và phương pháp làm mảnh (thinning). Phương pháp MFA xác định trục trung vị bằng cách nối các điểm trung tâm của khối bao bọc đối tượng, thường sử dụng hàm khoảng cách cực đại. Đây là phương pháp tìm xương không dựa trên làm mảnh. Phương pháp làm mảnh bao gồm các thuật toán loại bỏ các điểm cực trị (điểm biên) mà không làm thay đổi tính liên thông và cấu trúc tôpô của ảnh cho đến khi độ rộng của các đường bằng 1 pixel. Phương pháp thay đổi trục trung vị thường không mang lại một xương chuẩn và tốn thời gian tính toán.

2.2. Phương Pháp Làm Mảnh Dựa Trên Thay Đổi Trục Trung Vị

Blum (1976) định nghĩa xương thông qua hàm trục trung vị (MFA). MFA xử lý tất cả các điểm ảnh trên đường biên như các điểm nguồn của một mặt sóng trước. Sóng truyền qua mỗi điểm chỉ một lần và khi hai sóng gặp nhau, chúng sẽ triệt tiêu nhau, sinh ra một góc. Trục trung vị (MA) là quĩ tích của các góc này, và là mẫu xương của một đối tượng. MAF sử dụng cả thông tin về không gian lẫn thời gian, và có thể đảo ngược lại một ảnh gốc. Để tìm ra trục trung vị, có thể sử dụng đường biên của đối tượng. Đối với bất cứ một điểm p nào đó trên đối tượng, đều có thể bao nó bởi một đường biên. Nếu như có nhiều hơn một điểm biên có khoảng cách ngắn nhất thì p nằm trên trục trung vị. Bộ tất cả các điểm như vậy lập thành trục trung vị của đối tượng. MAF thường không mang lại một xương chuẩn, và thời gian tính toán quá dài.

2.3. Phân Loại Thuật Toán Dựa Trên Làm Mảnh Ảnh

Các phương pháp tìm xương dựa trên làm mảnh là trọng tâm của đồ án này. Chúng là các dạng thuật toán xóa các điểm biên của mẫu một cách có chọn lọc cho đến khi thu được xương. Việc xóa đi hay giữ lại một điểm ảnh (điểm đen) p dựa trên vùng lân cận của p. Các thuật toán có thể được phân loại thành thuật toán tuần tự hoặc song song. Trong thuật toán tuần tự, các điểm ảnh được xóa theo một trật tự nhất định trong mỗi vòng lặp, và giá trị của điểm ảnh p sau mỗi vòng lặp phụ thuộc vào giá trị của các láng giềng và các điểm ảnh đã được xét trước đó. Trong thuật toán làm mảnh song song, các điểm ảnh có thể được xử lý cùng một lúc, và giá trị của điểm ảnh chỉ phụ thuộc vào giá trị của các láng giềng. Thuật toán song song được sử dụng trên các bộ vi xử lý song song để tăng khả năng tính toán, chia thành các kiểu 1, 2 hoặc 4 chu trình con.

III. Phân Tích Các Khái Niệm Cơ Bản Trong Làm Mảnh Ảnh

Các khái niệm cơ bản trong làm mảnh bao gồm láng giềng, đường đi, điểm biên, điểm trong, điểm cuối và số giao. Láng giềng là các điểm ảnh xung quanh điểm ảnh đang xét. Đường đi là một trật tự của các điểm ảnh liên tiếp nhau. Điểm biên là các điểm ảnh có ít nhất một láng giềng là trắng. Điểm trong là các điểm đen mà không phải là điểm biên. Điểm cuối là một điểm đen thỏa mãn điều kiện b(p)=1 (chỉ có một láng giềng đen). Số giao là số lần biến đổi từ 1 điểm trắng sang 1 điểm đen và ngược lại khi các điểm ảnh láng giềng được đặt theo thứ tự ngược chiều kim đồng hồ. Các khái niệm này giúp định nghĩa các thuật toán làm mảnh một cách chính xác và hiệu quả, đồng thời đảm bảo tính liên thông và chất lượng của xương ảnh.

3.1. Định Nghĩa Láng Giềng và Đường Đi Trong Ảnh

Xét điểm ảnh p(i,j) và các điểm lân cận của nó. Các điểm ảnh x1, x2,..., x8 là 8_láng giềng của p và được biểu thị bởi N(p). Các điểm ảnh x1, x3, x5, x7 được gọi là 4_láng giềng hay kề 4 của p. Một trật tự của các điểm ảnh y1, y2,..., yn được gọi là một 8_đường đi (hoặc 4_đường đi) nếu yi+1 là một trong 8_láng giềng (hoặc 4_láng giềng) của yi (i=1, 2,...). Hai điểm được gọi là liên thông với nhau nếu tồn tại đường đi giữa chúng. Một bộ con Q của ảnh P được gọi 8_liên thông (hay 4_liên thông) nếu mọi cặp điểm x, y trong Q đều tồn tại 8_đường đi (hoặc 4_đường đi) từ x đến y phù hợp với các điểm của Q.

3.2. Điểm Biên Điểm Trong và Điểm Cuối Vai Trò và Ứng Dụng

Các điểm ảnh được xét để xóa là các điểm biên, thường được định nghĩa là có ít nhất 1 trong các láng giềng là trắng. Có 2 loại biên: 4 liên kết và 8 liên kết. Các điểm đen mà không phải là điểm biên được gọi là điểm trong của ảnh. Một điểm đen thỏa mãn điều kiện b(p)=1 (chỉ có một láng giềng đen) thì được coi là điểm cuối. Điều kiện điểm cuối này có thể được đưa ra với các dạng khác nhau, và có thể bị bỏ qua để tránh các nhánh giả. Phần lớn sự khác nhau giữa các thuật toán là ở điều kiện đảm bảo tính liên thông.

3.3. Số Giao Định Nghĩa và Ứng Dụng trong Làm Mảnh

Có hai định nghĩa về số giao của một điểm ảnh. Rutovitz đưa ra định nghĩa: số giao là số các lần biến đổi từ 1 điểm trắng sang 1 điểm đen và ngược lại khi các điểm ảnh láng giềng của điểm đang xét được đặt theo thứ tự ngược chiều kim đồng hồ. Việc xóa đi điểm đang xét sẽ không ảnh hưởng đến 4_liên thông nếu số giao bằng 2. Hilditch định nghĩa số giao như số lần nhảy từ điểm trắng sang điểm đen khi các điểm này đang được đặt trong thứ tự, cắt góc giữa kề 4 đen và 4_láng giềng. Nếu số giao bằng 1 thì việc xóa đi điểm đang xét không làm thay đổi tính 8_liên thông của mẫu.

IV. Đánh Giá Tính Chất và Yêu Cầu Đối Với Thuật Toán Làm Mảnh

Một thuật toán làm mảnh hiệu quả cần đáp ứng nhiều yêu cầu và tính chất quan trọng. Chúng bao gồm duy trì các thuộc tính tô pô và hình học, tính đẳng hướng, tính bất biến, khả năng tái tạo, không mất tính liên thông, không tạo ra lỗ hổng, không mất điểm cuối và tốc độ xử lý cao. Các yêu cầu về thời gian và số phép toán cần được tối ưu hóa, và khả năng tái tạo mẫu ban đầu từ xương là một thước đo khách quan về độ chính xác. Tính đẳng hướng và tính bất biến dưới phép quay cũng là những yếu tố quan trọng. Việc duy trì tính liên thông và tính chất tô pô khi làm mảnh cần được đảm bảo, và việc đáp ứng các thuộc tính hình học là một thách thức lớn. Việc cân bằng giữa tính đơn giản của thuật toán và khả năng giữ lại thông tin cấu trúc là rất quan trọng.

4.1. Yêu Cầu Về Thời Gian Số Phép Toán và Khả Năng Tái Tạo

Các phương thức làm mảnh không lặp, không phụ thuộc vào điểm ảnh có hiệu quả trong việc giảm số các phép toán cần thiết, chúng giữ lại được tốt hơn những nét đặc trưng chi tiết của mẫu. Nhìn chung, các thuật toán làm mảnh song song đã làm tăng tốc độ xử lý, đặc biệt khi mà các cấu trúc xử lý ảnh song song đang ngày càng tăng. Khả năng tái tạo, hay còn gọi là khả năng phục hồi lại mẫu ban đầu từ một xương, là một thước đo khách quan về độ chính xác đối với mỗi một mẫu xương. Những điều kiện này, nhìn chung, phù hợp với những thuật toán dựa trên trục trung vị.

4.2. Yêu Cầu Về Tính Đẳng Hướng Bất Biến và Liên Thông

Đa số các thuật toán lặp đều đảm bảo tính đẳng hướng hoặc tính bất biến dưới một phép quay. Trong các thuật toán tuần tự, kết quả thu được dựa trên thứ tự của các điểm ảnh được kiểm tra, còn trên các thuật toán song song xóa đi một hay hai kiểu điểm biên trên mỗi vòng lặp con, thì xương thu được phụ thuộc vào thứ tự của các vòng lặp con này. Trong khi đó thì việc thay đổi trục trung vị không bất biến dưới một phép quay bởi vì tính không đầy đủ của các thuật toán. Việc duy trì tính liên thông và tính chất Tô pô khi làm mảnh cũng đã được giải quyết bằng những cách khác nhau. Trong các thuật toán tuần tự, kiểm tra một vùng 3 × 3 láng giềng dưới dạng số giao.

4.3. Yêu Cầu Về Tính Hình Học và Duy Trì Cấu Trúc

Đảm bảo những thuộc tính hình học, là vấn đề gặp nhiều khó khăn nhất. Khó khăn chính là việc đạt được tính đơn giản của thuật toán, nó cho phép giữ lại một vùng nhỏ các láng giềng, nhưng các láng giềng này lại không thể đáp ứng được cho tổng thể, các thông tin có cấu trúc loại này lại cần thiết để phân biệt giữa điểm cuối giả và các điểm cuối thực. Để tránh sự xói mòn quá mức và việc tạo ra các điểm cuối giả tạo cùng một lúc, chúng ta phải có những cách khác nhau nhằm loại trừ điều kiện điểm cuối, tạo ra những điều kiện tổng quát và thích hợp hơn, hoặc chỉ áp dụng điều kiện trên các giai đoạn trước làm mảnh.

V. Hướng Dẫn Các Thuật Toán Làm Mảnh Tuần Tự Chi Tiết

Các thuật toán làm mảnh tuần tự kiểm tra và xóa các điểm biên theo một thứ tự định trước. Điều này có thể được thực hiện bằng cách dò theo loạt hoặc theo biên. Trong quá trình dò biên, tất cả các điểm ảnh biên của một đối tượng đơn liên thông (hoặc đa liên thông) được xét đến. Khi một điểm ảnh p được kiểm tra, nó sẽ được xóa đi hay giữ lại tùy theo cấu trúc của vùng lân cận N(p). Để ngăn chặn việc xóa một nhánh trên một vòng lặp, thuật toán thường đánh dấu các điểm ảnh sẽ được xóa đi, và tất cả các điểm ảnh đánh dấu được xóa ở cuối vòng lặp. Điều này đảm bảo rằng chỉ có một lớp các điểm ảnh sẽ được xóa đi trên mỗi chu trình. Một điểm p được xóa đi nếu nó là điểm ảnh đen, không phải điểm cô lập hoặc điểm cuối, và là điểm ảnh đường biên.

5.1. Thuật Toán Làm Mảnh Của Chu và Suen Ưu điểm và Hạn Chế

Trong thuật toán này, việc làm trơn được thực hiện trước mỗi vòng lặp. Trên mỗi vòng lặp, các điểm biên thỏa mãn các điều kiện của thuật toán được đánh dấu xóa với điều kiện điểm cuối. Khi không còn điểm ảnh nào có thể xóa được nữa, một giai đoạn chỉnh lý cuối cùng được đưa ra mà trên đó các điểm ảnh xương sẽ được chuyển cho một trong 4_láng giềng của nó nếu điểm ảnh sau cùng có khoảng cách lớn hơn 8 kể từ nền. Trong quá trình xử lý, tính liên thông của xương được đảm bảo trong khi các điểm xương được di chuyển dần tới đường trung vị của mẫu gốc.

5.2. Thuật Toán Arcelli Sử Dụng Số Giao Rutovitz

Số giao Rutovitz XR(p) được sử dụng để xác định việc xóa các điểm ảnh. Trên các thuật toán này, một định nghĩa khác của điểm biên được sử dụng: ở đây, một điểm biên đen có ít nhất một 8_láng giềng là trắng. Điều kiện này cùng với việc sử dụng XR(p) đòi hỏi một điều kiện bổ sung để đảm bảo rằng không tạo ra các lỗ hổng khi các điểm đường biên được xóa đi. Bổ sung các điều kiện cho khả năng xóa điểm nhưng vẫn đảm bảo tính liên thông được đưa ra trong thuật toán này. Khi thu được một bộ với một lõi rỗng, mỗi điểm ảnh p được giữ lại trên bộ đó được gán cho một nhãn, và các điểm ảnh không lớn nhất dưới nhãn này được xóa đi, kết quả thu được là xương có độ dày 2 điểm ảnh.

5.3. Thuật Toán Pavlidis Kết Hợp Tuần Tự và Song Song

Trong thuật toán này, đặc điểm của các điểm bội được định nghĩa lại trên giới hạn của các vùng láng giềng, và do đó có thể xác định được trên tuần tự hay song song thông qua việc so sánh các bộ mặt nạ với nhau. Thuật toán này chủ yếu đảm bảo tính liên thông của xương bằng cách phát hiện và gán các điểm bội cho xương rồi tìm và gán cho xương các điểm ảnh thích hợp để liên kết điểm bội với bên trong của mẫu. Sự phối hợp giữa tuần tự và song song rất có thể có hiệu quả hơn đối với những ảnh mà trên đó đa số các điểm ảnh không đòi hỏi phải được xử lý. Đối với những ảnh như vậy, mẫu có thể được chia ra thành các phần và ấn định cho từng bộ điều khiển.

VI. So Sánh Các Thuật Toán Làm Mảnh Song Song Hiện Đại

Trong làm mảnh song song, các điểm ảnh được kiểm tra để xóa dựa trên kết quả của vòng lặp trước đó, phù hợp để cài đặt trên các bộ xử lý song song. Tuy nhiên, các thuật toán hoàn toàn song song khó có thể giữ được sự liên thông nếu chỉ cho phép tác động lên khối 3 x 3 các điểm ảnh lân cận. Do đó, cách thông thường là sử dụng các láng giềng 3 x 3 nhưng phải chia mỗi vòng lặp ra thành các vòng lặp con, trên đó chỉ có một tập con các điểm biên được xét để xóa. Tùy theo số chu trình con, các thuật toán được chia thành các kiểu 4 chu trình con, 2 chu trình con hoặc 1 chu trình con. Các thuật toán song song đòi hỏi sự cân bằng giữa tốc độ và khả năng duy trì tính liên thông của xương ảnh.

6.1. Thuật Toán Rutovitz Ứng Dụng Thực Tế và Cải Tiến

Đây là một thuật toán song song cơ bản, một điểm ảnh p được xóa đi nếu tất cả các điều kiện nhất định đều được thỏa mãn. Thuật toán này còn có thêm một điều kiện phụ đảm bảo p có 4_láng giềng là trắng, do đó việc xóa p không tạo ra lỗ hổng. Đây là một thuật toán 1_vòng lặp con sử dụng các thông tin từ một cửa sổ 4 x 4, và nó cho ta các xương liên thông mà không nhạy cảm đối với nhiễu biên, nhưng lại có tạo ra xói mòn quá mức. Từ 4_thành phần rời nhau có thể là 8_liên thông, việc xóa đi các điểm p thỏa mãn các điều kiện trên không giảm độ rộng đơn vị điểm ảnh của các đường chéo.

6.2. Thuật Toán Zang Suen Thuật Toán Làm Mảnh Hiệu Quả

Đây là phép cài đặt dựa trên tập các điều kiện trong thuật toán Rutovitz theo 2 vòng lặp con. Vòng thứ nhất, p được xóa đi nếu nó thỏa mãn các điều kiện nhất định. Trong vòng lặp thứ hai, các điều kiện được thay bởi phép xoay chúng. Vì vậy, chu trình con thứ nhất xóa đi các điểm ảnh đơn trên biên phía Đông-Nam cũng như các điểm ảnh góc Tây-Bắc, ngược lại chu trình thứ hai xóa các điểm biên theo hướng ngược lại. Đây là một thuật toán đơn giản và hiệu quả mà nó loại được nhiễu biên. Tuy nhiên, các đường chéo có độ rộng 2 điểm ảnh có thể bị xóa hẳn, và các hình vuông 2 × 2 cũng có thể bị xóa hoàn toàn.

6.3. Thuật Toán Stentiford Đảm Bảo Tính Đối Xứng

Thuật toán được phát biểu như sau: Tìm các điểm ảnh thích hợp với các mẫu trong hình. Nếu điểm trung tâm không phải là điểm cuối và có số kết nối =1, đánh dấu để thực hiện xóa. Lặp lại bước trên cho tất cả các điểm ảnh so khớp với mẫu. Lặp lại các bước trên đối vơí các mẫu khác. Nếu điểm ảnh bào đó được đánh dấu thì xóa. Lặp lại từ bước trên cho đến khi không còn điểm ảnh nào bị xóa ở bước trước. Mục đích của các mẫu là tìm các điểm ảnh để xóa là các điểm rìa trên, bên trái, bên dưới và bên phải của đối tượng. Kiểu lý thuyết và hướng áp dụng đảm bảo các điểm ảnh sẽ bị xóa một cách đối xứng.

Trích đoạn nội dung tài liệu

CHƯƠNG 1 TỔNG QUAN VỀ LÀM MẢNH ẢNH 1.1 Xử lý ảnh Cũng như xử lý dữ liệu bằng đồ họa, xử lý ảnh số là một lĩnh vực của tin học ứng dụng. Xử lý ảnh số bao gồm các phương pháp và kỹ thuật để biến đổi, để truyền tải hoặc mã hoá các ảnh tự nhiên. Mục đích của xử lý ảnh gồm: ¾ Thứ nhất, biến đổi ảnh và làm đẹp ảnh. ¾ Thứ hai, tự động nhận dạng ảnh hay đoán nhận ảnh và đánh giá các nội dung của ảnh.

Hình 1: các giai đoạn chính trong xử lý ảnh 1.1 Biểu diễn ảnh Trong xử lý ảnh bằng máy tính , ảnh phải được đưa về dạng biểu diễn số. Một ảnh được biểu diễn dưới dạng một ma trận hai chiều. Mỗi phần tử của ma trận biểu diễn cho mức xám hay cường độ của điểm ảnh tương ứng. Mỗi phần tử trong ma trận được gọi là phần tử ảnh (pixel).

Tuỳ theo vùng các giá trị xám của điểm ảnh, mà các ảnh được phân chia ra thành ảnh màu, ảnh xám, hay ảnh nhị phân. Khi trên một ảnh chỉ tồn tại các Sinh viên Hà Đức Kiên - CT702 Trang 2 LUAN VAN CHAT LUONG download : add [e-mail] Đồ án tôt nghiệp Tìm hiểu phương pháp làm mảnh ảnh giá trị 0 hoặc 1 thì ta nói đó là một ảnh nhị phân hoặc ảnh đen trắng và các điểm ảnh của nó gọi là điểm ảnh nhị phân. Mỗi điểm ảnh nhị phân chỉ cần dùng 1 bit để biểu diễn. Với ảnh xám nếu dùng 1 Byte để biểu diễn thì số mức xám có thể biểu diễn là 28 hay 256 màu.

Mỗi mức xám được biểu diễn dưới dạng số nguyên nằm trong khoảng từ 0 đến 255. Với ảnh màu , việc biểu diễn tương tự ảnh xám chỉ khác các phần tử của ma trận biểu diễn cho ba màu riêng rẽ gồm đỏ (red) , lục (green) , lam (blue). Để biểu diễn cho một điểm ảnh cần 24 bit , chia làm 3 khoảng 8 bit , mỗi khoảng biểu diễn cho cường độ sáng của một trong các màu chính.2 Nhận dạng Nhận dạng là một ứng dụng quan trọng của làm mảnh. Nhận biết và đánh giá nội dung của ảnh(nhận dạng) là sự phân tích một hình ảnh thành những phần có nghĩa để phân biệt đối tượng này với đối tượng khác.

Dựa vào đó ta có thể mô tả cấu trúc của hình ảnh ban đầu. Có thể liệt kê một số phương pháp nhận dạng cơ bản như nhận dạng biên của một đối tượng trên ảnh , tách cạnh , phân đoạn ảnh. Kỹ thuật này được dùng nhiều trong y học ( xử lý tế bào , nhiễm sắc thể ) , nhận dạng chữ trong văn bản. Nhận dạng là quá trình liên quan đến mô tả đối tượng mà người ta muốn đặc tả nó.

Quá trình nhận dạng thường đi sau quá trình trích chọn các đặc tính của đối tượng. Có hai kiểu mô tả đối tượng : • Mô tả theo tham số ( nhận dạng theo tham số) • Mô tả theo cấu trúc ( nhận dạng theo cấu trúc) Trên thực tế người ta đã áp dụng nhận dạng chữ ( chữ cái , chữ số , chữ có dấu) Hiện nay có các phương pháp nhận dạng chữ bằng phương pháp cấu trúc , véctơ hoá đường nét các ảnh bản đồ , nhận dạng theo cấu trúc topo. Sinh viên Hà Đức Kiên - CT702 Trang 3 LUAN VAN CHAT LUONG download : add [e-mail] Đồ án tôt nghiệp Tìm hiểu phương pháp làm mảnh ảnh Nhận dạng chữ in hoặc đánh máy phục vụ cho quá trình tự động đọc tài liệu , tăng tốc độ và chất lượng thu nhận thông tin. Nhận dạng chữ viết tay (với mức độ ràng buộc về cách viết , kiểu chữ.

) phục vụ cho nhiều lĩnh vực. Ngoài hai kỹ thuật nhận dạng trên còn kỹ thuật nhận dạng mới dựa vào kỹ thuật mạng nơron đang được áp dụng và cho kết quả khả quan.2 Xương và các phương pháp tìm xương 1. Thế nào là xương và làm mảnh ảnh Kết quả của việc làm mảnh là đưa ra xương của đối tượng ảnh , vậy “xương ảnh là gì?”. Thuật ngữ “xương” dùng để chỉ kết quả mà không quan tâm đến hình dạng chuẩn của mẫu hoặc các phương thức được sử dụng.

Cho đến nay, vẫn chưa có một định nghĩa đáng thuyết phục nào về xương ảnh. Vì vậy việc tìm xương ảnh, tức là tìm ra những nét đặc trưng cho một đối tượng ảnh, là một điều hết sức khó khăn. Xương được coi như hình dạng cơ bản của một đối tượng, với số ít các điểm ảnh cơ bản. Ta có thể lấy được các thông tin về hình dạng nguyên bản của một đối tượng thông qua xương.

Vị trí, sự định hướng, độ dài của một đoạn xương đặc trưng cho đoạn ảnh đó. Nhiệm vụ đặt ra là phải định rõ đặc điểm thành phần của đoạn ảnh. Các kỹ thuật tìm xương luôn là chủ đề nghiên cứu trong xử lý ảnh. Do tính phức tạp của nó , mặc dù có những nỗ lực cho việc phát triển các thuật toán tìm xương nhưng các phương pháp đưa ra đều bị mất mát thông tin.

Nghiên cứu về làm mảnh ta cần chú ý các vấn đề sau : ¾ Không phải tất cả các đối tượng đều có thể làm mảnh. Làm mảnh chỉ hữu dụng với các đối tượng là đường, nghĩa là chúng chỉ Sinh viên Hà Đức Kiên - CT702 Trang 4 LUAN VAN CHAT LUONG download : add [e-mail] Đồ án tôt nghiệp Tìm hiểu phương pháp làm mảnh ảnh thẳng hoặc cong và nó không có tác dụng với các đối tượng có hình dạng đóng trong một vùng. ¾ Làm mảnh thông thường là bước chuẩn bị cho các bước tiếp theo xử lý một đối tượng ảnh. Các bước tiếp theo làm việc trên các thuộc tính cần thiết của xương.

Phân loại các thuật toán tìm xương Có hai phương pháp tìm xương cơ bản : ¾ Phương pháp thứ nhất xử dụng phép biến đổi trục trung vị , trục trung vị được xác định bằng cách nối các điểm trung tâm của khối bao bọc đối tượng , các điểm trung tâm thường được tính bằng hàm khoảng cách cực đại. Phương pháp này là phương pháp tìm xương không dựa trên làm mảnh. ¾ Phương pháp thứ hai bao gồm các thuật toán làm mảnh(thinning) bằng các loại bỏ các điểm cực trị ( điểm biên) mà không làm thay đổi tính liên thông và cấu trúc tôpô của ảnh cho đến khi độ rộng của các đường bằng 1 đơn vị (1 pixel). Phương pháp thay đổi trục trung vị Có thể người đầu tiên định nghĩa xương là Blum (1976), thông qua việc định nghĩa hàm trục trung vị (MFA).

Hàm MFA xử lý tất cả các điểm ảnh trên đường biên như các điểm nguồn của một mặt sóng trước. Mỗi một điểm ảnh lại tác động lên các láng giềng của nó với một thời gian trễ tương ứng với khoảng cách, do vậy chúng cũng trở thành một phần của sóng trước. Sóng truyền qua mỗi điểm chỉ một lần và khi hai sóng gặp nhau, chúng sẽ triệt tiêu nhau, sinh ra một góc. Trục trung vị (MA) là quĩ tích của các góc này, và là Sinh viên Hà Đức Kiên - CT702 Trang 5 LUAN VAN CHAT LUONG download : add [e-mail] Đồ án tôt nghiệp Tìm hiểu phương pháp làm mảnh ảnh mẫu xương của một đối tượng.

MAF sử dụng hai thông tin cả về không gian lẫn thời gian, và có thể đảo ngược lại một ảnh gốc. Có một cách để tìm ra trục trung vị là sử dụng đường biên của đối tượng. Đối với bất cứ một điểm p nào đó trên đối tượng, đều có thể bao nó bởi một đường biên. Nếu như có nhiều hơn một điểm biên có khoảng cách ngắn nhất thì p nằm trên trục trung vị.

Bộ tất cả các điểm như vậy lập thành trục trung vị của đối tượng. Điều đó phải được thực hiện với độ phân giải cao, hoặc khoảng cách Ơcơlit là không bằng nhau, và như thế các điểm ảnh xương sẽ mất đi. Ta dễ dàng thu được một xấp xỉ của trục trung vị trên một lưới đơn giản sau hai bước: ¾ Bước thứ nhất, tính toán khoảng cách từ mỗi điểm ảnh của đối tượng đến điểm biên gần nhất. Việc này yêu cầu phải tính toán khoảng cách tới tất cả các điểm ảnh đường biên.

¾ Bước thứ hai, khoảng cách ảnh đã được tính toán, và các điểm ảnh có giá trị rộng nhất được xem là nằm trên trục trung vị. Hình2: Trục trung vị Hầu hết các nhà nghiên cứu đều cho rằng thay đổi trục trung vị thường không mang lại một xương chuẩn, và thời gian tính toán quá dài, tuy nhiên, nó là mẫu cơ bản của phần lớn các phương pháp làm mảnh. Sinh viên Hà Đức Kiên - CT702 Trang 6 LUAN VAN CHAT LUONG download : add [e-mail] Đồ án tôt nghiệp Tìm hiểu phương pháp làm mảnh ảnh Phương pháp thay đổi trục trung vị được coi là một phương pháp làm mảnh không lặp , ngoài ra còn có một vài thuật toán duyệt các điểm biên 2 bên mẫu , tính điểm trung tâm của các đường nối giữa các điểm biên đó và xương thu được là tập hợp các điểm trung tâm đó ( line following) hoặc các phương thức sử dụng chuỗi Fourier (Fourier transform) cũng được coi là làm mảnh không lặp. Phương pháp tìm xương dựa trên làm mảnh Các phương pháp tìm xương dựa trên làm mảnh chính là vấn đề mà đồ án này nghiên cứu.

Đó chính là các dạng thuật toán xoá các điểm biên của mẫu một cách có chọn lọc cho đến khi thu được xương. Việc xoá đi hay giữ lại một điểm ảnh (điểm đen) p dựa trên vùng lân cận của p. Như vậy chúng ta xét các điểm ảnh, các thuật toán có thể được phân lớp thành các thuật toán tuần tự hay song song. Đối với thuật toán tuần tự các điểm ảnh được xoá đi theo một trật tự nhất định trong mỗi vòng lặp và giá trị của điểm ảnh p sau mỗi vòng lặp không chỉ phụ thuộc vào giá trị của các láng giềng mà còn phụ thuộc vào các điểm ảnh đã được xét trước đó trong chính vòng lặp đó.

Đối với thuật toán làm mảnh song song , các điểm ảnh có thể được xử lý cùng một lúc , giá trị của điểm ảnh chỉ phụ thuộc vào giá trị của các láng giềng. Chính vì thế mà các thuật toán dạng này được xử dụng trên các bộ vi xử lý song song để tăng khả năng tính toán. Tuỳ theo số chu trình con được xử Sinh viên Hà Đức Kiên - CT702 Trang 7 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.