TỔNG QUAN VỀ XỬ LÝ ẢNH
Xử lý ảnh là gì?
Con người tiếp nhận thông tin chủ yếu qua các giác quan, trong đó thị giác là yếu tố quan trọng nhất Gần đây, sự phát triển mạnh mẽ của phần cứng máy tính đã thúc đẩy công nghệ xử lý ảnh và đồ họa, mở ra nhiều ứng dụng hữu ích trong đời sống Công nghệ này đóng vai trò thiết yếu trong việc cải thiện tương tác giữa con người và máy móc.
Quá trình xử lý ảnh là thao tác trên ảnh đầu vào để đạt được kết quả mong muốn, có thể là một bức ảnh "tốt hơn" hoặc một kết luận cụ thể.
Quá trình xử lý ảnh liên quan đến việc xem ảnh như một tập hợp các điểm ảnh, trong đó mỗi điểm ảnh thể hiện cường độ sáng hoặc một dấu hiệu tại một vị trí cụ thể trong không gian Điều này cho phép chúng ta coi ảnh như một hàm n biến P(c1, c2, …, cn), từ đó hình ảnh được hiểu là một đối tượng n chiều trong lĩnh vực xử lý ảnh.
Sơ đồ tổng quát của một hệ thống xử lý ảnh:
Hình 1 2 Các bước cơ bản trong một hệ thống xử lý ảnh
Các vấn đề cơ bản trong xử lý ảnh
1.2.1 Một số khái niệm cơ bản
Điểm ảnh là đơn vị cơ bản biểu thị cường độ sáng tại một tọa độ trong không gian của đối tượng, trong khi ảnh được coi là một tập hợp các điểm ảnh.
Là số các giá trị có thể có của các điểm ảnh của ảnh
1.2.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
Raster image acquisition devices, such as cameras, capture images in a pixel-based format, while vector image acquisition devices, including sensors and digitizers, convert or process images from raster format.
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.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
Giảm thời gian xử lý
Lưu trữ thông tin trong bộ nhớ ảnh hưởng lớn đến việc hiển thị, in ấn và xử lý ảnh Một bức ảnh được xem như một tập hợp các điểm với cùng kích thước, và khi sử dụng nhiều điểm ảnh hơn, bức ảnh sẽ trở nên đẹp hơn, mịn màng hơn và thể hiện rõ hơn các chi tiết Đặc điểm này được gọi là độ phân giải.
Việc chọn độ phân giải phù hợp phụ thuộc vào nhu cầu sử dụng và đặc điểm của từng bức ảnh, từ đó các ảnh thường được phân loại theo hai mô hình cơ bản.
Mô hình Raster là phương pháp phổ biến nhất để biểu diễn hình ảnh hiện nay, trong đó hình ảnh được thể hiện dưới dạng ma trận các điểm ảnh Các hình ảnh này thường được thu nhận từ các thiết bị như camera hoặc scanner Tùy thuộc vào yêu cầu thực tế, mỗi điểm ảnh có thể được biểu diễn bằng một hoặc nhiều bít.
Mô hình Raster rất hiệu quả cho việc hiển thị và in ấn nhờ vào công nghệ phần cứng hiện đại, cung cấp thiết bị thu nhận ảnh Raster với tốc độ nhanh và chất lượng cao Một điểm mạnh trong việc hiển thị trên hệ điều hành Windows là sự hỗ trợ của Microsoft với định dạng ảnh DIB (Device Independent Bitmap) như một trung gian Hình 1.4 minh họa quy trình chung để hiển thị ảnh Raster thông qua DIB.
Một trong những hướng nghiên cứu chính trong mô hình biểu diễn là kỹ thuật nén ảnh, được chia thành hai loại: nén bảo toàn và nén không bảo toàn Nén bảo toàn cho phép phục hồi hoàn toàn dữ liệu gốc, trong khi nén không bảo toàn chỉ có thể phục hồi với độ sai số nhất định Nhiều quy cách nén ảnh đã được đề xuất, bao gồm BMP, TIF, GIF và PCX.
Hiện nay, trên thế giới có hơn 50 định dạng ảnh phổ biến, bao gồm cả các kỹ thuật nén cho phép phục hồi dữ liệu hoàn toàn và nén với khả năng phục hồi có độ sai số nhất định.
Hình 1 3 Quá trình hiển thị và chỉnh sửa, lưu trữ ảnh thông qua DIB
Biểu diễn ảnh không chỉ giúp tiết kiệm không gian lưu trữ mà còn tối ưu cho việc hiển thị và in ấn Ngoài ra, kỹ thuật này còn hỗ trợ dễ dàng trong việc lựa chọn, sao chép, di chuyển và tìm kiếm Trong bối cảnh này, kỹ thuật biểu diễn vector nổi bật với nhiều ưu điểm vượt trội.
Trong mô hình vector, hướng giữa các vector của điểm ảnh lân cận được sử dụng để mã hóa và tái tạo hình ảnh ban đầu Ảnh vector có thể được thu nhận trực tiếp từ các thiết bị số hóa như Digital hoặc chuyển đổi từ ảnh Raster thông qua các chương trình số hóa.
Công nghệ phần cứng mang lại thiết bị xử lý nhanh chóng và chất lượng cao cho cả đầu vào và đầu ra, nhưng chỉ hỗ trợ định dạng ả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
Hình 1 4 Sự chuyển đổi giữa các mô hình biểu diễn ảnh
1.2.3 Nâng cao chất lƣợng ảnh
1.2.3.1 Nắn chỉnh biến dạng Ảnh thu nhận thường bị biến dạng do các thiết bị quang học và điện tử Ảnh thu nhận Ảnh mong muốn
Để cải thiện chất lượng hình ảnh, người ta sử dụng các phép chiếu được xây dựng dựa trên tập hợp các điểm điều khiển, nhằm khắc phục sự khác biệt giữa ảnh thu nhận và ảnh mong muốn.
Giả sử (P i , P i’ ) i = 1, n có n các tập điều khiển
Tìm hàm f: P i → f(Pi) sao cho: min
Giả sử ảnh bị biến đổi chỉ bao gồm: Tịnh tiến, quay, tỷ lệ, biến dạng bậc nhất tuyến tính Khi đó hàm f có dạng: f(x, y) = (a 1 x + b 1 y + c 1 , a 2 x + b 2 y + c 2 )
Giải hệ phương trình tuyến tính tìm được a 1 , b1, c1
Có 2 loại nhiễu cơ bản trong quá trình thu nhận ảnh:
Nhiều hệ thống: là nhiễu có quy luật có thể khử bằng các phép biến đổi
Nhiễu ngẫu nhiên: vết bẩn không rõ nguyên nhân→ khắc phục bằng các phép lọc
Nhằm khắc phục tính không đồng đều của hệ thống gây ra Thông thường có 2 hướng tiếp cận:
Giảm số mức xám bằng cách nhóm các mức xám gần nhau thành một bó Khi chỉ có hai mức xám, quá trình này tương đương với việc chuyển đổi ảnh sang đen trắng Ứng dụng thực tiễn của phương pháp này là in ảnh màu ra máy in đen trắng.
Tăng số mức xám: Thực hiện nội suy ra các mức xám trung gian bằng kỹ thuật nội suy Kỹ thuật này nhằm tăng cường độ mịn cho ảnh
Trong quá trình xử lý ảnh, việc trích chọn các đặc điểm của đối tượng phụ thuộc vào mục đích nhận dạng Một số đặc điểm quan trọng bao gồm đặc điểm không gian như phân bố mức xám, biên độ và điểm uốn Đặc điểm biến đổi được trích chọn thông qua lọc vùng, sử dụng các mặt nạ đặc điểm với hình dạng đa dạng như chữ nhật và tam giác Đặc điểm biên và đường biên cũng rất quan trọng, giúp nhận diện các thuộc tính bất biến của đối tượng Các đặc điểm này có thể được trích chọn bằng cách sử dụng các toán tử như gradient, la bàn, Laplace và zero crossing.
XƯƠNG VÀ CÁC KỸ THUẬT TÌM XƯƠNG
Giới thiệu
Xương được xem là cấu trúc cơ bản của một đối tượng, với số lượng điểm ảnh tối thiểu Thông qua xương, chúng ta có thể thu thập thông tin về hình dạng nguyên bản của đối tượng.
Xương có thể được định nghĩa một cách ngắn gọn dựa trên tính continuum, tương tự như hiện tượng cháy đồng cỏ, theo Blum (1976) Cụ thể, giả thiết rằng một đối tượng đồng nhất được bao phủ bởi cỏ khô và sau đó tạo ra một vòng biên lửa Trong bối cảnh này, xương được xem là nơi gặp gỡ của các vệt lửa, nơi mà chúng bị dập tắt.
Hình 2 1 Ví dụ về ảnh và xương
Kỹ thuật tìm xương đã trở thành một chủ đề nghiên cứu quan trọng trong lĩnh vực xử lý ảnh trong những năm gần đây Mặc dù đã có nhiều nỗ lực phát triển các thuật toán tìm xương, nhưng vẫn tồn tại vấn đề mất mát thông tin trong các phương pháp hiện tại Các thuật toán tìm xương có thể được chia thành hai loại cơ bản.
Các thuật toán tìm xương dựa trên làm mảnh
Các thuật toán tìm xương không dựa trên làm mảnh
Tìm xương dựa trên làm mảnh ảnh
2.2.1 Sơ lƣợc về thuật toán làm mảnh
Thuật toán làm mảnh ảnh số nhị phân đóng vai trò quan trọng trong xử lý ảnh và nhận dạng Xương của ảnh cung cấp thông tin bất biến về cấu trúc, hỗ trợ hiệu quả cho quá trình nhận dạng và vectơ hoá sau này.
Thuật toán làm mảnh là quá trình lặp lại để kiểm tra tất cả các điểm thuộc đối tượng Trong mỗi lần lặp, các điểm sẽ được xem xét và xóa nếu thỏa mãn điều kiện cụ thể của từng thuật toán Quá trình này tiếp tục cho đến khi không còn điểm biên nào bị xóa, và đối tượng sẽ được bóc dần lớp biên cho đến khi chỉ còn lại các điểm biên.
Các thuật toán làm mảnh được phân loại thành hai loại chính: thuật toán làm mảnh song song và thuật toán làm mảnh tuần tự, dựa trên phương pháp xử lý các điểm.
Thuật toán làm mảnh song song là phương pháp xử lý dữ liệu đồng thời, trong đó các điểm được xử lý cùng lúc Giá trị của mỗi điểm sau mỗi lần lặp chỉ phụ thuộc vào giá trị của các láng giềng xung quanh (thường là 8-láng giềng) đã được xác định trong lần lặp trước Trong hệ thống có nhiều bộ vi xử lý, mỗi bộ vi xử lý đảm nhiệm một khu vực của đối tượng, cho phép đọc dữ liệu từ các khu vực khác nhưng chỉ ghi dữ liệu trên khu vực mà nó đang xử lý.
Trong thuật toán làm mảnh tuần tự, các điểm thuộc đối tượng được kiểm tra theo một thứ tự nhất định, chẳng hạn từ trái sang phải hoặc từ trên xuống dưới Giá trị của mỗi điểm sau mỗi lần lặp không chỉ phụ thuộc vào các láng giềng bên cạnh mà còn dựa vào các điểm đã được xét trước đó trong cùng một lần lặp.
Chất lượng của thuật toán làm mảnh được đánh giá dựa trên các tiêu chuẩn dưới đây, mặc dù không cần phải đáp ứng tất cả các tiêu chí cùng một lúc.
Bảo toàn tính liên thông của đối tƣợng và phần bù của đối tƣợng
Sự tương hợp giữa xương và cấu trúc của ảnh đối tượng
Bảo toàn các thành phần liên thông
Bảo toàn các điểm cụt
Xương chỉ gồm các điểm biên, càng mảnh càng tốt
Bền vững đối với nhiễu
Xương cho phép khôi phục ảnh ban đầu của đối tượng
Xương thu được ở chính giữa đường nét của đối tượng được làm mảnh
Xương nhận được bất biến với phép quay
2.2.2 Một số thuật toán làm mảnh
Trong phần này điểm qua một số đặc điểm, ƣu và khuyết điểm của các thuật toán đã đƣợc nghiên cứu
Thuật toán làm mảnh cổ điển là một phương pháp song song, giúp tạo ra xương 8 liên thông Tuy nhiên, nhược điểm của nó là tốc độ chậm, dẫn đến hiện tượng đứt nét và có thể xóa hoàn toàn một số cấu hình nhỏ.
Thuật toán làm mảnh của Toumazet giữ nguyên tất cả các điểm cắt mà không làm đứt nét của đối tượng Tuy nhiên, nó có nhược điểm là tốc độ chậm, nhạy cảm với nhiễu, chỉ hỗ trợ xương 4-liên thông và không thể xử lý một số cấu hình phức tạp.
Thuật toán làm mảnh của Y Xia, dựa trên đường biên của đối tượng, có khả năng cài đặt theo cả phương pháp song song và tuần tự, cho tốc độ xử lý nhanh chóng Tuy nhiên, thuật toán này cũng có nhược điểm là gây ra hiện tượng đứt nét, dẫn đến việc tạo ra xương giả với độ dày lên tới 2 phần tử ảnh.
Thuật toán làm mảnh của N J Naccache và R Shinghal nổi bật với tốc độ nhanh và khả năng khôi phục hình ảnh gốc của đối tượng Tuy nhiên, nhược điểm chính của thuật toán là độ nhạy cao với nhiễu, dẫn đến việc xương nhận được phản ánh cấu trúc của đối tượng không rõ ràng.
Thuật toán làm mảnh của H E Lu P S P Wang có tốc độ nhanh và duy trì tính liên thông của ảnh, nhưng nó cũng có nhược điểm là tạo ra xương 4-liên thông và loại bỏ một số cấu hình nhỏ.
Thuật toán làm mảnh của P S P Wang và Y Y Zhang dựa trên đường biên của đối tượng, có thể triển khai theo phương pháp song song hoặc tuần tự Với xương 8-liên thông, thuật toán này ít bị ảnh hưởng bởi nhiễu, tuy nhiên, nhược điểm chính của nó là tốc độ xử lý chậm.
Thuật toán làm mảnh song song thuần tuý nhanh nhất trong số các thuật toán hiện có, giúp bảo toàn tính liên thông và ít bị ảnh hưởng bởi nhiễu Tuy nhiên, nhược điểm của nó là có thể xóa hoàn toàn một số cấu hình nhỏ, dẫn đến việc tạo ra xương 4-liên thông.
Tìm xương không dựa trên làm mảnh ảnh
Để tách xương của đối tượng, ta sử dụng đường biên bao quanh đối tượng Nếu một điểm p nằm trên trục trung vị, nó sẽ có nhiều điểm biên với khoảng cách ngắn nhất tới p Tập hợp tất cả các điểm này tạo thành trục trung vị hay xương của đối tượng Quy trình xác định xương diễn ra qua hai bước.
Để bắt đầu, cần tính khoảng cách từ mỗi điểm ảnh của đối tượng đến điểm biên gần nhất, bao gồm việc tính toán khoảng cách tới tất cả các điểm biên của ảnh.
Bước thứ hai,khoảng cách ảnh đã được tính toán và các điểm ảnh có giá trị lớn nhất được xem là nằm trên xương của đối tượng
2.3.1 Khái quát về lƣợc đồ Voronoi
Lƣợc đồ Voronoi là một công cụ quan trọng trong hình học tính toán, giúp xác định các khu vực trong mặt phẳng gần gũi với các điểm cụ thể Đối với hai điểm P i và P j trong tập Ω gồm n điểm, tập hợp các điểm gần P i hơn P j được xác định bởi nửa mặt phẳng H(Pi, P j), bao gồm điểm P i và bị giới hạn bởi đường trung trực của đoạn thẳng PiP j Từ đó, tập hợp các điểm gần P i hơn bất kỳ điểm P j nào có thể được xây dựng bằng cách giao n-1 nửa mặt phẳng H(P i, P j).
V(P i ) = ∩ H(P i , P j ) i≠j (i= 1, , n) (2 1) Định nghĩa 2 1 [Đa giác/Sơ đồ Voronoi]
Sơ đồ Voronoi của Ω là hợp của tất cả các V(P i )
Vor(Ω) = ∪V(Pi) Pi∈Ω (là một đa giác) (2 2) Định nghĩa 2 2 [Đa giác Voronoi tổng quát]
Cho tập các điểm Ω, đa giác Voronoi của tập con U của Ω đƣợc định nghĩa nhƣ sau:
2.3.2 Trục trung vị Voronoi rời rạc Định nghĩa 2 3 [Bản đồ khoảng cách - Distance Map]
Cho đối tƣợng S, đối với mỗi (x, y)∈S, ta tính giá trị khoảng cách map(x, y) với hàm khoảng cách d( , ) nhƣ sau:
∀(x, y)∈S: map(x, y) = min d[ (x, y), (xi, yi)] (2 4) trong đó (x i , yi)∈B(S) - tập các điểm biên của S
Tập tất cả các map(x, y), kí hiệu là DM(S), đƣợc gọi là bản đồ khoảng cách của S
Nếu hàm khoảng cách d(.,.) là khoảng cách Euclide, phương trình (2.4) thể hiện khoảng cách ngắn nhất từ một điểm bên trong đối tượng tới biên Do đó, bản đồ khoảng cách được gọi là bản đồ khoảng cách Euclide EDM(S) của S Định nghĩa này áp dụng cho cả hình rời rạc và liên tục.
Cho map(x, y) là khoảng cách ngắn nhất từ (x, y) đến biên (theo định nghĩa 2.3) Ta định nghĩa: map -1 (x, y)={p| p∈B(S), d(p, (x, y)):=map(x, y)}
Khi đó tập các điểm biên sinh ^B(S) đƣợc định nghĩa bởi:
Do S có thể chứa các đường biên rời nhau, nên ^B(S) bao gồm nhiều tập con, mỗi tập mô tả một đường biên phân biệt:
^B(S)={B1(S), Bn(S)} (2 6) Định nghĩa 2 5 [Trục trung vị Voronoi rời rạc (DVMA)]
Trục trung vị Voronoi rời rạc là kết quả của sơ đồ Voronoi bậc nhất rời rạc, được xác định từ tập hợp các điểm biên sinh giao với hình sinh S.
2.3.3 Xương Voronoi rời rạc Định nghĩa 2 6 [Xƣơng Voronoi rời rạc - DiscreteVoronoi Skeleton]
Xương Voronoi rời rạc theo ngưỡng T, kí hiệu là SkeDVMA(^B(S), T) (hoặc Ske(^B(S), T)) là một tập con của trục trung vị Voronoi:
SkeDVMA(^B(S), T)={ (x, y)| (x, y)∈DVMA(^B(S)), Ψ(x, y) > T} (2 8) Ψ: là hàm hiệu chỉnh
Dễ thấy nếu ngƣỡng T càng lớn thì càng thì số lƣợng điểm tham gia trong xương Vonoroi càng ít (Hình 2 2)
Hình 2 2 Xương Voronoi rời rạc
Xương Voronoi rời rạc ảnh hưởng của các hàm hiệu chỉnh khác nhau
(c) Hiệu chỉnh bởi hàm Potential, T=9 0
(d) Hiệu chỉnh bởi hàm Potential, T 0
Trong mục này sẽ trình bày ý tưởng cơ bản của thuật toán tìm xương và mô tả bằng ngôn ngữ tựa Pascal
Quá trình tính toán sơ đồ Voronoi bắt đầu từ một điểm sinh trong mặt phẳng, sau đó lần lượt thêm các điểm sinh mới và tiếp tục tính toán với các đa giác Voronoi đã có Quy trình này diễn ra cho đến khi không còn điểm sinh nào được thêm vào Tuy nhiên, nhược điểm của chiến lược này là mỗi khi có điểm mới được thêm vào, nó có thể làm thay đổi toàn bộ phân vùng của các đa giác Voronoi đã được tính toán trước đó.
Chia để trị là phương pháp chia tập điểm biên thành hai tập con có kích cỡ bằng nhau, sau đó tính toán sơ đồ Voronoi cho từng tập Quá trình này được lặp lại nhiều lần cho đến khi việc tính toán trở nên đơn giản hơn Mục tiêu cuối cùng là ghép hai sơ đồ Voronoi lại với nhau để đạt được kết quả mong muốn, biến việc tính sơ đồ Voronoi thành một bài toán về cách kết hợp các sơ đồ này.
Thuật toán sẽ trình bày ở đây là sự kết hợp của hai ý tưởng ở trên Tuy nhiên, nó sẽ mang nhiều dáng dấp của thuật toán chia để trị
Hình 2.3 minh họa ý tưởng của thuật toán, trong đó mười một điểm biên được chia thành hai phần bởi đường gấp khúc δ Hai sơ đồ Voronoi tương ứng là Vor(S L) và Vor(S R) Để tạo ra sơ đồ Voronoi tổng hợp Vor(S L ∪ S R), cần trộn hai sơ đồ và xác định lại một số đa giác bị ảnh hưởng bởi các điểm bên cạnh Mỗi phần tử của δ là một bộ phận của đường trung trực nối hai điểm, với một điểm thuộc Vor(S L) và một điểm thuộc Vor(S R) Trước khi xây dựng δ, ta xác định phần tử đầu và cuối của nó, trong đó cạnh δ1 và δ5 là các tia, giúp tìm ra cạnh vào tα và cạnh ra tω.
Sau khi xác định tα và tω, các điểm cuối của tα được sử dụng để xây dựng phần tử đầu tiên của δ (δ1) Tiếp theo, thuật toán tìm điểm giao giữa δ với Vor(SL) và Vor(SR) Trong ví dụ minh họa, δ đầu tiên giao với V(3).
Từ thời điểm này, các điểm trên phần kéo dài δ sẽ gần điểm 6 hơn điểm 3 Kết quả là, phần tử tiếp theo δ2 sẽ nằm trên đường trung trực của điểm 6 và điểm 7 Tiếp theo, điểm giao tiếp của δ sẽ thuộc vào Vor(S L); δ sẽ tiến vào V(9) và δ2 sẽ được thay thế bởi δ3 Quá trình này sẽ kết thúc khi δ gặp phần tử cuối δ5.
Bài viết này minh hoạ cho thuật trộn hai sơ đồ Voronoi trong chiến lược chia để trị, với một quy trình thực hiện khác biệt Thay vì đưa tập các điểm ảnh vào ngay từ đầu, chúng ta sẽ quét từng dòng một Ở bước thứ i, đã có sơ đồ Voronoi gồm i-1 hàng các điểm sinh Vor(S i-1 ) Tiếp theo, quét lấy hàng L i từ các điểm biên còn lại và tính sơ đồ Voronoi Vor(Li) cho hàng này Sau đó, tiến hành trộn Vor(S i-1 ) với Vor(L i ) để tạo ra một sơ đồ mới, tiếp tục quét hàng Li+1 cho đến khi không còn điểm biên nào để thêm vào Do Vor(L i ) có dạng răng lƣợc, việc trộn Vor(S i-1 ) với Vor(Li) trở nên đơn giản hơn.
Hình 2 4 Minh hoạ thuật toán thêm một điểm biên vào sơ đồ Voronoi
Giải thuật trên có thể đƣợc mô tả bằng ngôn ngữ tựa Pascal nhƣ sau:
(*S i : Tập các điểm của i dòng quét đầu tiên, 0