Nghiên cứu một số phương pháp phát hiện biên

5


DANH SÁCH CÁC HÌNH ẢNH

Hình 1.1: Quá trình xử lý ảnh

9
Hình 1.2: Các bước trong quá trình xử lý ảnh

10
Hình 1.3: Lân cận các điểm ảnh của tọa độ (x,y)

16
Hình 1.4: Đường biên lý tưởng

24
Hình 1.5: Đường biên dốc

25
Hình 1.6: Đường biên không trơn

26

Hình 2.1: Biên ảnh với Pixel Difference

31
Hình 2.2: Biên ảnh với Separated Pixel Difference

32
Hình 2.3: Biên ảnh với toán tử Robert

33

Hình 2.4: Biên ảnh với toán tử Prewitt

33
Hình 2.5: Biên ảnh với toán tử Sobel

34
Hình 2.6: Biên ảnh với toán tử Frie-Chen

34
Hình 2.7: Biên ảnh với toán tử Boxcar

35
Hình 2.8: Biên ảnh với toán tử Truncated Pyramid

36
Hình 2.9: Biên ảnh với toán tử Kirsh

38
Hình 2.10: Biên ảnh với toán tử la bàn Prewitt

39
Hình 2.11: Biên ảnh với toán tử Robinson 3 level

40
Hình 2.12: Biên ảnh với toán tử Robinson 5 level

41
Hình 2.13: Biên ảnh với kỹ thuật Laplace

42
Hình 2.14: Bộ lọc Laplace of Gauss

42
Hình 2.15: Biên ảnh với kỹ thuật Laplace of Gauss

44

Hình 3.1: Đạo hàm hàm Gauss theo hai hướng (x,y)

48
Hình 3.2: Hình mô tả các điểm biên lân cận

50

6
Hình 3.3: Biên ảnh theo phương pháp Canny

52
Hình 3.4: Biên ảnh theo phương pháp Shen-Castan

55
Hình 3.5: Dùng DWT cho biến đổi Neurite

56
Hình 3.6 Biên ảnh của một cái hộp đơn

57
Hình 3.7: Biên ảnh con chó nằm ở bậc thang

57
Hình 3.8: Sử dụng 3 tiêu chuẩn cho ảnh con cho nằm bậc thang

58
Hình 3.9: Sử dụng 3 tiêu chuẩn cho ảnh của Filopodia

59
Hình 3.10: Sử dụng liên kết tự động trong ảnh hộp đơn

59
Hình 3.11: Sử dụng liên kết tự động trong ảnh con cho nằm bậc thang

60
Hình 3.12: Sử dụng liên kết tự động trong ảnh của Filopodia

60

Hình 4.1: Hình mô phỏng kết quả tìm biên theo kỹ thuật Gradient

65
Hình 4.2: Biên ảnh theo đạo hàm bậc nhất và bậc hai

68
Hình 4.3: Phát hiện biên với Canny ngưỡng cố định

69
Hình 4.4: Phát hiện biên với Canny ngưỡng thay đổi σ =1

70
Hình 4.5: Biên ảnh theo Gradient, Laplace, Canny

71

Hình 4.6: Phát hiện biên theo phương pháp Wavelet

72



7




MỞ ĐẦU

Thời đại công nghệ thông tin phát triển như vũ bão đã đi vào từng ngõ ngách
của cuộc sống. Hiện nay, bất cứ sự phát triển của ngành công nghiệp nào đều có sự
hiện diện và đóng góp rất to lớn của công nghệ thông tin. Xử lý ảnh là một trong
những chuyên ngành quan trọng và lâu đời của Công nghệ thông tin. Xử lý ảnh
được áp dụng trong nhiều lĩnh khác nhau như y học, vật lý, hoá học, tìm kiếm tội
phạm, trong quân sự và trong một số lĩnh vực khác
Phần lớn con người thu nhận thông tin bằng thị giác, cụ thể đó là các hình ảnh.
Vì vậy xử lý ảnh là vấn đề không thể thiếu và hết sức quan trọng để thu được hình
ảnh tốt hơn, đẹp hơn, nhằm đáp ứng yêu cầu thông tin khác nhau của người nhận.
Trong xử lý ảnh, việc nhận dạng và phân lớp đối tượng cần trải qua các quá
trình và các thao tác khác nhau. Phát hiện biên là một giai đoạn rất quan trọng vì các
kỹ thuật phân đoạn ảnh chủ yếu dựa vào giai đoạn này. Mục đích của việc dò biên
sẽ đánh dấu những điểm trong một ảnh số mà có sự thay đổi đột ngột về độ xám,
tập hợp nhiều điểm biên tạo nên một đường bao quanh ảnh (đường biên). Nhờ có
đường biên mà chúng ta có thể phân biệt giữa đối tượng và nền, phân biệt giữa các
vùng khác nhau và định vị được đối tượng từ đó mà nhận dạng đối tượng. Đây là cơ
sở quan trọng trong việc ứng dụng phương pháp này vào thực tiễn của cuộc sống,
đặc biệt là trong điều kiện đất nước ta đang từng bước phát triển và đi lên nên việc
nghiên cứu các ứng dụng vấn đề này cần được quan tâm và phát triển.
Xuất phát từ thực tế đó, luận văn lựa chọn đề tài " Nghiên cứu một số phương
pháp phát hiện biên". Mục đích chính của đề tài là hệ thống hóa kiến thức về các
phương pháp phát hiện biên, từ các kỹ thuật dò biên cài đặt chương trình để đưa ra
các nhận xét, so sánh, đánh giá về các phương pháp phát hiện biên. Qua đó có cái
nhìn tổng quát về các phương pháp phát hiện biên.

8
Ngoài phần mở đầu và kết luận luận văn được chia làm 4 chương, nội dung cụ
thể của các chương như sau:
Chương I: Tổng quan về xử lý ảnh và biên
Trong chương này trình bày sơ lược về xử lý ảnh, giới thiệu các bước xử lý
trong một hệ thống xử lý ảnh. Một số thành phần cốt tử trong xử lý ảnh, như điểm
ảnh, mức xám, biên,…được trình bày như là các khái niệm.
Chương II: Các phương pháp phát hiện biên cổ điển
Nội dung của chương này sẽ đề cập đến một số phương pháp phát hiện biên
trong phương pháp đạo hàm bậc nhất và phương pháp đạo hàm bậc hai.
Chương III: Các phương pháp phát hiện biên nâng cao
Trong chương này đề cập đến phương pháp phát hiện biên Canny, phương
pháp Shen-Castan và phương pháp Wavelet.
Chương IV: Một số nhận xét đánh giá các phương pháp phát hiện biên
Qua việc cài đặt thử nghiệm các phương pháp phát hiện biên đã trình bày trong
các chương trước, từ các kết quả mô phỏng thực nghiệm khi chạy chương trình,
trong chương này đưa ra các nhận xét đánh giá, so sánh các phương pháp phát hiện
biên. Chỉ ra phương pháp phát hiện biên phù hợp với loại ảnh cần xử lý.

Tuy nhiên, việc nghiên cứu một vấn đề khoa học đi đến kết quả là một khó khăn
và nhiều thách thức do vậy luận văn chắc còn nhiều thiếu sót. Rất mong nhận được
ý kiến đóng gópquý báu của các thầy cô và đồng nghiệp.

Học viên




Nguyễn Quang Sơn

9




CHƯƠNG I
TỔNG QUAN VỀ XỬ LÝ ẢNH VÀ BIÊN

1.1. Tổng quan về xử lý ảnh
1.1.1. Xử lý ảnh
Con người thu nhận thông tin qua các giác quan trong đó thị giác đóng vai trò
quan trọng nhất. Sự phát triển nhanh của phần cứng máy tính, xử lý ảnh và đồ hoạ
đã phát triển mạnh mẽ và ngày càng có nhiều ứng dụng trong cuộc sống. Xử lý ảnh
đóng một vai trò quan trọng trong tương tác người máy.
Quá trình xử lý nhận dạng ảnh là một quá trình thao tác nhằm biến đổi một
ảnh đầu vào để cho ra một 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.





Hình 1.1: Quá trình xử lý ảnh

Như vậy mục tiêu của xử lý ảnh có thể chia làm ba hướng như sau:
- Xử lý ảnh ban đầu để cho ra một ảnh mới tốt hơn theo một mong muốn của
người dùng (ví dụ: ảnh mờ cần xử lý để được rõ hơn).
- Phân tích ảnh để thu được thông tin nào đó giúp cho việc phân loại và nhận
biết ảnh (ví dụ: phân tích ảnh vân tay để trích chọn các đặc trưng vân tay).
- Từ ảnh đầu vào mà có những nhận xét, kết luận ở mức cao hơn, sâu hơn (ví
dụ: ảnh một tai nạn giao thông phác hoạ hiện trường tai nạn).
Ảnh đầu vào
Xử lý ảnh
Ảnh tốt hơn
Kết luận

10
1.1.2. Các bước cơ bản trong xử lý ảnh
Quá trình xử lý một ảnh đầu vào nhằm thu được một ảnh đầu ra mong muốn
thường phải trải qua rất nhiều bước khác nhau. Các bước cơ bản của một quá trình
xử lý ảnh được thể hiện thông qua hình sau:














Hình 1.2: Các bước cơ bản trong quá trình xử lý ảnh

1.1.2.1 Thu nhận ảnh
Đây là bước đầu tiên trong quá trình xử lý ảnh. Để thực hiện điều này, ta cần
có bộ thu ảnh và khả năng số hoá những tín hiệu liên tục được sinh ra bởi bộ thu
ảnh đó. Bộ thu ảnh ở đây có thể là máy chụp ảnh đơn sắc hay màu, máy quét ảnh,
máy quay Trong trường hợp bộ thu ảnh cung cấp chưa phải là dạng số hoá ta còn
phải chuyển đổi hay số hoá ảnh. Quá trình chuyển đổi ADC (Analog to Digital
Converter) để thu nhận dạng số hoá của ảnh. Mặc dù đây chỉ là công đoạn đầu tiên
song kết quả của nó có ảnh hưởng rất nhiều đến công đoạn kế tiếp.


Phân đoạn
ảnh
Biểu diễn và
mô tả
Tiền xử
lý ảnh
Thu nhận ảnh
(Scaner, sensor,
camera)

Nhận dạng và
nội suy
CƠ SỞ
TRI THỨC

11
1.1.2.2 Tiền xử lý
Ở bước này, ảnh sẽ được cải thiện về độ tương phản, khử nhiễu, khôi phục
ảnh, nắn chỉnh hỉnh học Với mục đích làm cho chất lượng ảnh trở lên tốt hơn nữa,
chuẩn bị cho các bước xử lý phức tạp kế tiếp sau đó.
* Khử nhiễu: Nhiễu được chia thành hai loại: nhiễu hệ thống và nhiễu ngẫu
nhiên. Đặc trưng của nhiễu hệ thống là tính tuần hoàn. Do vậy, có thể khử nhiễu này
bằng việc sử dụng phép biến đổi Fourier và loại bỏ các đỉnh điểm. Đối với nhiễu
ngẫu nhiên, trường hợp đơn giản là các vết bẩn tương ứng với các điểm sáng hay
tối, có thể khử bằng phương pháp nội suy, lọc trung vị và trung bình.
* Chỉnh mức xám: Đây là kỹ thuật nhằm chỉnh sửa tính không đồng đều của
thiết bị thu nhận hoặc độ tương phản giữa các vùng ảnh.
* Chỉnh tán xạ: Ảnh thu nhận được từ các thiết bị quang học hay điện tử có
thể bị mờ, nhoè. Phương pháp biến đổi Fourier dựa trên tích chập của ảnh với hàm
tán xạ cho phép giải quyết việc hiệu chỉnh này.
* Nắn chỉnh hình học: Những biến dạng hình học thường do các thiết bị điện
tử và quang học gây ra. Do đó, phương pháp hiệu chỉnh ảnh dựa trên mô hình được
mô tả dưới dạng phương trình biến đổi ảnh biến dạng f(x,y) thành ảnh lý tưởng
f(x',y') như sau:



=
=
),('
),('
yxhy
yxhx
y
x

Trong đó h
x
, h
y
là các phương trình tuyến tính (biến dạng do phối cảnh) hay
bậc hai (biến dạng do ống kính camara).

1.1.2.3 Phân đoạn ảnh
Phân đoạn ảnh có nghĩa là chia một ảnh đầu vào thành nhiều phần khác nhau
hay còn gọi là các đối tượng để biểu diễn phân tích, nhận dạng ảnh. Ví dụ: để nhận
dạng chữ (hoặc mã vạch) trên phong bì thư cho mục đích phân loại bưu phẩm, cần
chia các câu, chữ về địa chỉ hoặc tên người thành các từ, các chữ, các số (hoặc các
vạch) riêng biệt để nhận dạng. Đây là phần phức tạp khó khăn nhất trong xử lý ảnh
và cũng dễ gây lỗi, làm mất độ chính xác của ảnh. Kết quả nhận dạng ảnh phụ

12
thuộc rất nhiều vào công đoạn này.
Kết quả của bước phân đoạn ảnh thường được cho dưới dạng dữ liệu điểm ảnh
thô, trong đó hàm chứa biên của một vùng ảnh hoặc tập hợp tất cả các điểm ảnh
thuộc về chính vùng ảnh đó. Trong cả hai trường hợp, sự chuyển đổi dữ liệu thô này
thành một dạng thích hợp hơn cho việc xử lý trong máy tính là hết sức cần thiết,
nghĩa là nên biểu diễn một vùng ảnh dưới dạng biên hay dưới dạng một vùng hoàn
chỉnh gồm tất cả những điểm ảnh thuộc về nó.
- Biểu diễn dạng biên cho một vùng phù hợp với những ứng dụng chỉ quan
tâm đến các đặc trưng hình dạng bên ngoài của đối tượng, ví dụ như các góc cạnh
và điểm uốn trên biên.
- Biểu diễn dạng vùng lại thích hợp cho những ứng dụng khai thác các tính
chất bên trong của đối tượng. Ví dụ như vân ảnh hoặc cấu trúc xương của nó. Và
trong một số ứng dụng thì cả hai cách biểu diễn trên đều cần thiết.

1.1.2.4 Biểu diễn và mô tả
a) Biểu diễn
Đầu ra ảnh sau phân đoạn chứa các điểm ảnh của vùng ảnh (ảnh đã phân
đoạn) cộng với mã liên kết với các vùng lận cận. Việc biến đổi các số liệu này thành
dạng thích hợp là cần thiết cho xử lý tiếp theo bằng máy tính. Việc chọn các tính
chất để thể hiện ảnh gọi là trích chọn đặc trưng (Feature Selection) gắn với việc
tách các đặc tính của ảnh dưới dạng các thông tin định lượng hoặc làm cơ sở để
phân biệt lớp đối tượng này với đối tượng khác trong phạm vi ảnh nhận được. Ví
dụ: trong nhận dạng ký tự trên phong bì thư, chúng ta miêu tả các đặc trưng của
từng ký tự giúp phân biệt ký tự này với ký tự khác.

b) Mô tả
Ảnh sau khi số hoá sẽ được lưu vào bộ nhớ, hoặc chuyển sang các khâu tiếp
theo để phân tích. Nếu lưu trữ ảnh trực tiếp từ các ảnh thô, đòi hỏi dung lượng bộ
nhớ cực lớn và không hiệu quả theo quan điểm ứng dụng và công nghệ. Thông
thường, các ảnh thô đó được đặc tả (biểu diễn) lại (hay đơn giản là mã hoá) theo các

13
đặc điểm của ảnh được gọi là các đặc trưng ảnh như: biên ảnh, vùng ảnh. Một số
phương pháp biểu diễn thường dùng:
• Biểu diễn bằng mã chạy: Phương pháp này thường biểu diễn cho vùng ảnh
và áp dụng cho ảnh nhị phân.
• Biểu diễn bằng mã xích: Phương pháp này thường dùng để biểu diễn đường
biên ảnh.
• Biểu diễn bằng mã tứ phân: Phương pháp này được dùng để mã hoá cho
vùng ảnh.

1.1.2.5 Nhận dạng và nội suy ảnh
Nhận dạng ảnh là quá trình xác định ảnh. Quá trình này thường thu được bằng
cách so sánh với mẫu chuẩn đã được lọc (hoặc lưu) từ trước.
Nội suy là phán đoán theo ý nghĩa trên cơ sở nhận dạng. Ví dụ: một loạt chữ
số và nét gạch ngang trên phong bì thư có thể được nội suy thành mã điện thoại. Có
nhiều cách phân loại khác nhau về ảnh. Theo lý thuyết về nhận dạng, các mô hình
toán học về ảnh được phân theo hai loại nhận dạng ảnh cơ bản:
- Nhận dạng theo tham số.
- Nhận dạng theo cấu trúc.
Một số đối tượng nhận dạng khá phổ biến hiện nay đang được áp dụng trong
khoa học và công nghệ là: nhận dạng ký tự (chữ in, chữ viết tay, chữ ký điện tử),
nhận dạng văn bản (Text), nhận dạng vân tay, nhận dạng mã vạch, nhận dạng mặt
người…

1.1.2.6 Cơ sở tri thức
Ảnh là một đối tượng khá phức tạp về đường nét, độ sáng tối, dung lượng
điểm ảnh, môi trường để thu ảnh phong phú kéo theo nhiễu. Trong nhiều khâu xử lý
và phân tích ảnh ngoài việc đơn giản hóa các phương pháp toán học đảm bảo tiện
lợi cho xử lý, người ta mong muốn bắt chước quy trình tiếp nhận và xử lý ảnh theo
cách của con người. Trong các bước xử lý đó, nhiều khâu hiện nay đã xử lý theo
các phương pháp trí tuệ con người. Vì vậy, ở đây các cơ sở tri thức được phát huy.

14
1.1.2.7 Trích chọn đặc điểm
Việc giải quyết bài toán nhận dạng trong những ứng dụng mới, nảy sinh trong
cuộc sống không chỉ tạo ra những thách thức về giải thuật, mà còn đặt ra những yêu
cầu về tốc độ tính toán. Đặc điểm chung của tất cả những ứng dụng đó là những đặc
điểm đặc trưng cần thiết thường là nhiều, không thể do chuyên gia đề xuất, mà phải
được trích chọn dựa trên các thủ tục phân tích dữ liệu.
Việc trích chọn hiệu quả các đặc điểm giúp cho việc nhận dạng các đối tượng
ảnh chính xác, với tốc độ tính toán cao và dung lượng nhớ lưu trữ giảm xuống.
Các đặc điểm của đối tượng được trích chọn tuỳ theo mục đích nhận dạng
trong quá trình xử lý ảnh. Có thể nêu ra một số đặc điểm của ảnh sau đây:
- Đặc điểm không gian: Phân bố mức xám, phân bố xác suất, biên độ, điểm
uốn v.v
- Đặc điểm biến đổi: Các đặc điểm loại này được trích chọn bằng việc thực
hiện lọc vùng (zonal filtering). Các bộ vùng được gọi là “mặt nạ đặc điểm” (feature
mask) thường là các khe hẹp với hình dạng khác nhau (chữ nhật, tam giác, cung
tròn v.v )
- Đặc điểm biên và đường biên: Đặc trưng cho đường biên của đối tượng và
do vậy rất hữu ích trong việc trích trọn các thuộc tính bất biến được dùng khi nhận
dạng đối tượng. Các đặc điểm này có thể được trích chọn nhờ toán tử Gradient, toán
tử la bàn, toán tử Laplace, toán tử “chéo không” (zero crossing)

1.1.3. Một số vấn đề cơ bản trong xử lý ảnh
1.1.3.1 Điểm ảnh (Picture Element)
Gốc của ảnh là ảnh liên tục về không gian và độ sáng. Để xử lý bằng máy tính,
ảnh cần phải được số hoá. Số hoá ảnh là sự biến đổi gần đúng một ảnh liên tục
thành một tập điểm phù hợp với ảnh thật về vị trí (không gian) và độ sáng (mức
xám). Khoảng cách giữa các điểm ảnh đó được thiết lập sao cho mắt người không
phân biệt được ranh giới giữa chúng. Mỗi một điểm như vậy gọi là điểm ảnh (PEL:
Picture Element) hay gọi tắt là Pixel. Trong khuôn khổ ảnh hai chiều, mỗi pixel ứng
với cặp tọa độ (x, y).

Xem chi tiết: Nghiên cứu một số phương pháp phát hiện biên