MỞ ĐẦU
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ền đề cho nhiều nghiên cứu thuộc 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.
Một hệ thống xử lý và nhận dạng ảnh được chia ra làm các thao tác khác
nhau. Trong đó, thao tác phân đoạn ảnh được xem là thao tác khó, quan trọng và
cần thiết [4]. Kết quả nhận dạng ảnh phụ thuộc rất nhiều vào công đoạn này. Độ
chính xác của quá trình phân đoạn ảnh có ý nghĩa quyết định tới các xử lý tính toán
sau đó. Phân đoạn có thể đóng vai trò trung tâm trong một số xử lý kĩ thuật như
phân tích chất lượng sản phẩm, kiểm tra quá trình lắp ráp các chi tiết điện, v.v. hoặc
là một khâu trung gian cần thiết cho các quá trình xử lý tiếp theo như các xử lý
trong y học.
Phân đoạn là các thao tác chia nhỏ bức ảnh đầu vào thành các miền hoặc các
vật thể con với mức độ tùy theo nhu cầu xử lý để biểu diễn, phân tích, nhận dạng
ảnh, v.v. Chung lại mục tiêu của phân đoạn ảnh là làm nổi bật hoặc tách hẳn vật thể
cần quan tâm ra từ ảnh ban đầu; làm đơn gián hóa và/ hoặc thay đổi cách biểu diễn
có ý nghĩa hơn và dễ dàng hơn để phân tích [1]. Phân đoạn thường được sử dụng để
xác định vị trí đối tượng và ranh giới (đường dây, đường cong, v.v.) trong hình ảnh.
Do đó đề tài có ý nghĩa và cần thiết thực hiện.
Cấu trúc của luận văn được chia làm 4 chương:
Chương 1: Trình bày tổng quan về xử lý ảnh; phân đoạn và vai trò của phân
đoạn ảnh; một số phương pháp cơ bản trong phân đoạn ảnh đa cấp xám.
Chương 2: Trình bày về các mô hình (không gian màu) cùng một vài kỹ
thuật phân đoạn ảnh màu đại diện.
Chương 3: Trên cơ sở lý thuyết và thuật toán về phân đoạn ảnh đa cấp xám
được trình bày ở chương I và phân đoạn ảnh màu ở chương II, chương này sẽ ứng
dụng cơ sở lý thuyết cùng với thuật toán vào cài đặt chương trình Demo gồm các
thuật toán Kmean, lý thuyết đồ thị và không gian màu CIE.
Chương 4: Phần kết luận nêu tóm tắt các kết quả đạt được và đưa ra hướng
giải quyết, nghiên cứu trong tương lai.

2


CHƯƠNG I:
TỔNG QUAN VỀ XỬ LÝ ẢNH VÀ PHÂN ĐOẠN
1.1 TỔNG QUAN VỀ XỬ LÝ ẢNH
Quá trình xử lý nhận dạng ả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 [3]. 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 vào

Xử lý ảnh

Ảnh ra (tốt hơn)

Kết luận
Hình 1.0 Quá trình xử lý ảnh
Ảnh trong xử lý ảnh có thể xem như ảnh n chiều. Bởi vì, ảnh có thể xem là tập
hợp các điểm ảnh. Trong đó, 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à do đó nó có thể xem như một hàm n biến P(c1,
c2,..., cn).
Sơ đồ tổng quát của một hệ thống xử lý ảnh:
Thu nhận
ảnh

Tiền xử lý
ảnh


Phân đoạn
ảnh

Biểu diễn
và mô tả ảnh

Nhận dạng
và nội suy

Hình 1.1. Các bước cơ bản trong một hệ thống xử lý ảnh
1.1.1.Tiền xử lý
Sau bộ thu nhận, ảnh có thể nhiễu độ tương phản thấp nên cần đưa vào bộ tiền
xử lý để nâng cao chất lượng. [1,2] Tiền xử lý là giai đoạn đầu tiên trong xử lý ảnh
số. Tuỳ thuộc vào quá trình xử lý tiếp theo trong giai đoạn này sẽ thực hiện các
công đoạn khác nhau như: nâng cấp, khôi phục ảnh, nắn chỉnh hình học, khử nhiễu
v.v..

1.1.2. Trích chọn đặc điểm

3


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 [3]. 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.
a. Phân đoạn
Phân đoạn (phân vùng ) một ảnh đầu vào thành các vùng thành phần để 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.
b) Biểu diễn và mô tả ảnh
Đầ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 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.
1.1.3. 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 họ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 loai ảnh 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ố và 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.v.v.
1.2 VAI TRÒ CỦA PHÂN ĐOẠN
Phân đoạn là các thao tác chia nhỏ bức ảnh đầu vào thành các miền hoặc các
vật thể con với mức độ tùy theo nhu cầu xử lý. Mục tiêu của phân đoạn ảnh là làm

4


nổi bật hoặc tách hẳn vật thể cần quan tâm ra từ ảnh ban đầu; làm đơn gián hóa và/
hoặc thay đổi cách biểu diễn có ý nghĩa hơn và dễ dàng hơn để phân tích [1].
Có rất nhiều kiểu phân đoạn như xác định biên của vật thể, xử lý các vùng

ảnh, tách bạch rõ ràng vật thể và nền bằng 1 ngưỡng, v.v. chung lại mục tiêu của
phân đoạn ảnh là làm nổi bật hoặc tách hẳn vật thể cần quan tâm ra từ ảnh ban đầu.
Trong các thao tác về xử lý và nhận dạng ảnh thì phân đoạn ảnh được xem là
thao tác khó, quan trọng và cần thiết [4]. Độ chính xác của quá trình phân đoạn ảnh
có ý nghĩa quyết định tới các xử lý tính toán sau đó.
1.3. PHÂN ĐOẠN ẢNH ĐA CẤP XÁM
Phân đoạn ảnh màu dựa trên cơ sở của phân đoạn ảnh đa cấp xám [4], vì vậy
mà trước khi đi tìm hiểu về phân đoạn ảnh màu, nội dung này sẽ đưa ra một vài kỹ
thuật phân đoạn ảnh đa cấp xám tiêu biểu. Kỹ thuật phân đoạn ảnh màu sẽ được
trình bày ở chương II.
1.3.1. Tách không liên tục
Phần này sẽ nói về ba kỹ thuật cơ bản để
tách mức xám không liên tục trong một ảnh số:
điểm, đường và biên. Cách phổ biến nhất để tìm
ra sự không liên tục này là sử dụng mặt nạ quét
qua hết bức ảnh. Ví dụ đối với mặt nạ 3x3 ở
hình 1.2, quá trình này bao gồm việc tính tổng
các tích của trọng số với mức xám trong vùng
Hình 1.2 Mặt nạ trọng số

mặt nạ đi qua để thu được đáp ứng của mặt nạ:
9

R = w1 z1 + w 2 z 2 + ... + w 9 z9 = ∑ w i zi

(1.1)

i =1

Trong đó,


zi

là mức xám của Pixel xác định bởi mặt nạ, w i là trọng số của

mặt nạ. Thông thường, đáp ứng mặt nạ được xác định chủ yếu dựa vào vị trí của
tâm mặt nạ.
1.3.1.1 Tách điểm ảnh
Về nguyên tắc, việc tách các điểm cô lập trong một bức ảnh khá đơn giản. Ví
dụ khi sử dụng mặt nạ như hình 1.3a, ta tách điểm có vị trí mà mặt nạ tập trung nếu:
|R| ≥T

5

(1.2)


Ở đây T là ngưỡng dương và R được xác định bởi (1.1). Về cơ bản, công thức
này đo độ chênh lệch giữa điểm trung tâm và các lân cận của nó. Ý tưởng chủ đạo ở
đây là một điểm cô lập (điểm có mức xám khác với nền của nó, và được định vị
trong vùng đồng nhất hoặc có thể nhận thấy) thì hơi khác so với những điểm xung
quanh, vì vậy nó dễ dàng bị tách bởi loại mặt nạ này. Lưu ý là các điểm cô lập phải
đủ lớn (xác định bởi T). Tổng hệ số của mặt nạ bằng 0, điều đó chứng tỏ rằng đáp
ứng của mặt nạ sẽ bằng 0 tại những vùng có mức xám không đổi.
Hình 1.3b là một minh họa cho việc tách các điểm cô lập trong một ảnh. Hình
1.3b biểu diễn ảnh chụp bằng tia X của bề mặt tua bin của 1 động cơ phản lực ở
trạng thái bị rỗ. Có 1 pixel màu đen đơn lẻ ở trong mỗi vùng bị rỗ. Hình 1.3c là kết
quả sau khi áp dụng tách điểm bằng cách sử dụng mặt nạ 1.3a cho ảnh 1.3b. Hình
1.3d là kết quả áp dụng công thức 1.2 với ngưỡng T bằng 90% giá trị của các pixel
cao nhất trong hình 1.3c. (Việc chọn ngưỡng – threshold sẽ được nói chi tiết trong

phần sau). Những pixel đơn hiện ra rõ ràng trong bức ảnh này.

Hình 1.3 Minh họa cho việc tách điểm
Đây là một cách xử tách khá đặc biệt bởi vì nó dựa trên cơ sở là những pixel
đơn không liên tục trên nền đồng nhất của mặt nạ tách. Khi điều kiện này không
thỏa mãn thì ta dùng phương pháp khác phù hợp hơn (sẽ được đề cập trong chương
này) để tách mức xám không liên tục.
1.3.1.2 Tách dòng
Phương pháp tiếp theo là tách dòng. Cho những mặt nạ như trong hình 1.4. Nếu
ma trận đầu tiên di chuyển qua bức ảnh, nó sẽ đáp ứng mạnh tại những đường có
hướng nằm ngang (độ dày một pixel). Với nền không đổi, kết quả trả về lớn nhất
khi đường đi qua hàng giữa của mặt nạ. Thực nghiệm cho thấy mặt nạ thứ 2 trong
hình 1.4 sẽ đáp ứng tốt nhất những đường có hướng là +45 o, mặt nạ thứ 3 thì đáp

6


ứng tốt với đường thẳng đứng, mặt nạ thứ tư thì đáp ứng tốt với những đường có
hướng là -45o. Chú ý rằng các hệ số trong 1 mặt nạ có tổng bằng 0, hệ số đáp ứng
của mặt nạ sẽ bằng 0 tại những vùng có mức xám không đổi.

Hình 1.4 Các mặt nạ dùng tách dòng
Đặt R1 , R2 , R3 và R4 là đáp ứng của những mặt nạ trong hình 1.4 từ trái qua
phải, trong đó Ri được xác định bởi (1.1). Cho 4 mặt nạ này lần lượt quét qua toàn
bộ ảnh. Nếu tại một điểm xác định trong hình, | Ri |>| R j | với mọi j≠i, ta nói rằng
điểm đó có hướng phù hợp với hướng của mặt nạ i hơn. Ví dụ nếu tại một điểm
trong bức ảnh mà | R1 |>| R j |, với j=2,3,4, thì điểm đó có hướng phù hợp hơn với
hướng của đường nằm ngang. Lần lượt chúng ta quan tâm đến việc tách những
đường có hướng xác định. Trong trường hợp này, chúng ta sẽ sử dụng mặt nạ phù
hợp với hướng và ngưỡng đó của đầu ra, theo biểu thức (1.2). Nói cách khác, nếu

như chúng ta quan tâm đến việc tách tất cả các đường trong ảnh với hướng xác định
bởi một mặt nạ cho trước, chúng ta chạy mặt nạ này qua ảnh và tạo ngưỡng cho giá
trị tuyệt đối của kết quả. Những điểm còn lại là những điểm có đáp ứng mạnh nhất,
đối với những đường có độ dày 1 pixel, phù hợp nhất với hướng được xác định bởi
mặt nạ. Ví dụ sau sẽ minh họa cho điều này.
Ví dụ:
Giả sử rằng chúng ta quan tâm đến việc tìm tất cả các đường có độ dày 1 pixel
và có hướng -45o. Với giả thuyết này, chúng ta sử dụng mặt nạ cuối cùng trong hình
1.4. Kết quả được thể hiện trong hình 1.5b. Chú ý rằng tất cả những phần ngang và
phần đứng trong bức ảnh thì bị loại bỏ và những phần của bức ảnh ban đầu mà có
hướng -45o thì được nổi rõ nhất trong hình 1.5b. Để xác định những đường nào phù
hợp nhất với mặt nạ chúng ta chọn ngưỡng cho hình này. Kết quả của việc sử dụng
ngưỡng bằng với giá trị lớn nhất của bức ảnh thể hiện trong hình 1.5c. Giá trị lớn
nhất này là một lựa chọn tốt cho 1 ngưỡng trong trường hợp này, bởi vì ảnh đầu vào

7


là ảnh nhị phân. Thực hiện xong việc này, chúng ta tìm những đáp ứng mạnh nhất.
Hình 1.5c biểu diễn tất cả những điểm vượt qua ngưỡng bằng màu trắng.

Hình 1.5 Ví dụ minh hoa về tách dòng
Trong trường hợp này, phương pháp trên chỉ tìm ra những đoạn có độ dày 1
pixel và hướng -45o. Những điểm cô lập nhìn thấy trong hình 1.5c là những điểm
đáp ứng mạnh đối với mặt nạ. Trong ảnh ban đầu, những điểm này và láng giềng
của chúng được định hướng theo hướng mặt nạ đáp ứng mạnh nhất. Những điểm cô
lập này có thể được tách bằng cách sử dụng mặt nạ trong hình 1.3a và sau đó được
xóa đi.
1.3.1.3 Tách biên ảnh
Phương pháp tách điểm và tách dòng là các kỹ thuật phân đoạn quan trọng,

nhưng việc tách biên lại hoàn toàn khác xa với các kỹ thuật trên, nó được sử dụng
phổ biến nhất cho việc tách độ trung bình không liên tục của mức xám. Trong phần
này chúng sẽ nói về công cụ đạo hàm bậc 1 và bậc 2 và nhấn mạnh về các thuộc
tính của chúng để tách biên cho bức ảnh.
*.Cơ sở tách biên:
Một cách trực quan, một biên là tập hợp những pixel ( nằm trên đường biên giới
giữa 2 vùng) liên kết với nhau. Tuy nhiên, biên và cạnh có sự khác nhau.Về cơ bản
ta sẽ xem xét một cách ngắn gọn, một cạnh là 1 khái niệm “cục bộ”, trong khi
đường biên của một miền mang tính toàn cục hơn nhiều. Một định nghĩa hợp lý của
“biên” đòi hỏi khả năng đo được sự chuyển tiếp mức xám.
Chúng ta bắt đầu bằng việc làm mô hình cho biên và việc đo đạc sự chuyển tiếp
trung bình của mức xám chỉ mang tính hình thức. Một cách trực quan, một biên lý
tưởng có các thuộc tính của mô hình ở hình 1.6a. Theo mô hình này thì một biên lý
tưởng là một tập hợp các pixel (ở đây là theo hướng thẳng đứng) liên kết với nhau,
mỗi thành phần của biên có vị trí tại 1 bước chuyển tiếp trực giao mức xám.

8


Hình 1.6 Biên lý tưởng và không lý tưởng
Trong thực tế, quang học, lấy mẫu,... và những cách thu nhận hình ảnh khác
không hoàn hảo dẫn đến biên bị nhòe với độ nhòe được xác định bởi những nhân tố
như là chất lượng của hệ thống thu nhận hình ảnh, tốc độ lấy mẫu và điều kiện
chiếu sáng của mỗi bức ảnh. Vì vậy kết quả là biên được mô hình gần giống với
một đoạn dốc hơn đoạn thẳng đứng, được thể hiện trong hình 1.6b. Độ nghiêng của
dốc tỉ lệ nghịch với độ nhòe của biên. Trong mô hình này, chúng ta không bao giờ
có một đường biên mảnh (có độ dày một pixel). Thay vào đó, một điểm biên bây
giờ là một điểm bất kì chứa trong đoạn dốc và biên là tập hợp những điểm liên
thông. Độ dày của đường biên được xác định bởi chiều dài của đoạn dốc, khi biên
biến đổi từ đầu đến cuối mức xám. Độ dài này được xác định bởi độ nhòe. Dễ dàng

nhận ra rằng: biên nhòe thì dày và biên sắc nét thì mảnh.

Hình 1.7 Đạo hàm bậc 1 và 2 của mức xám

9


Hình 1.7a hiển thị một phần trích ra từ hình 1.6b. Ảnh 1.7b thể hiện mặt
nghiêng của một mức xám theo hướng nằm ngang của biên nằm giữa hai vùng.
Hình này cũng cho thấy đạo hàm bậc 1, bậc 2 của mức xám. Đạo hàm bậc 1 dương
tại những điểm chuyển tiếp từ trong ra ngoài đoạn dốc theo hướng di chuyển từ trái
sang phải, và không đổi đối với những điểm nằm trên dốc, bằng 0 tại những vùng
có mức xám không đổi. Đạo hàm bậc hai dương tại những biến đổi tương ứng với
phía tối của biên, âm tại những biến đổi tương ứng với phía sáng của biên, và bằng
0 dọc theo dốc hoặc trong những vùng mức xám không đổi. Dấu của đạo hàm trong
1.7b sẽ bị đảo ngược đối với những biên biến đổi từ sáng sang tối.
Từ những quan sát trên ta kết luận rằng độ lớn của đạo hàm bậc 1 có thể được
sử dụng để phát hiện ra dấu hiệu của một biên tại một điểm trong hình (nghĩa là xác
định điểm đó có nằm trên dốc không). Tương tự như vậy dấu của đạo hàm bậc 2 có
thể được sử dụng để xác định một pixel cạnh nằm trên phía sáng hay phía tối của
biên. Chúng ta chú ý thêm hai thuộc tính của đạo hàm bậc hai xung quanh một biên:
(1) Nó tạo ra hai giá trị cho mỗi cạnh (điều không mong muốn)
(2) Một đường thẳng tưởng tượng nối từ điểm dương lớn nhất và điểm âm nhỏ
nhất của đạo hàm bậc hai sẽ đi qua 0 gần với điểm giữa của biên. Thuộc tính zerocrossing của đạo hàm bậc hai thì hữu dụng cho việc xác định trung tâm của biên
dày.

10


Hình 1.8 Độ nhậy của đạo hàm đối với nhiễu

Ví dụ:
Biên thể hiện trong Hình 1.6 và 1.7 thì không có nhiễu. Cột đầu tiên của Hình
1.8 thể hiện 4 biên (đoạn dốc) phân ra thành một vùng đen ở bên trái và một vùng
trắng ở bên phải. Lưu ý là toàn bộ biến đổi từ đen sang trắng này chỉ là biểu diễn
của một cạnh đơn. Vùng ảnh ở trên cùng bên trái là ảnh không có nhiễu. Ba ảnh còn
lại trong cột đầu tiên của Hình 1.8 bị sai lệch bởi nhiễu Gauss với “zero mean” và
độ lệch chuẩn mức xám lần lượt là 0.1 và 1.0 và 10. Đồ thị biểu diễn bên dưới mỗi
ảnh này là hình chiếu mức xám của đường quét theo hàng ngang qua toàn bộ ảnh.
Các ảnh trong cột 2 của hình 1.8 là đạo hàm bậc 1 của những ảnh ở cột 1. Xét
ảnh ở giữa trên cùng, đạo hàm bằng 0 tại những vùng đen và trắng không đổi. Đạo
hàm của một đoạn biên không đổi là hằng số biểu thị độ nghiêng của dốc. Đạo hàm
không đổi này được biểu diễn bằng màu xám. Hình tiếp theo của cột 2 thì các đạo
hàm càng tăng so với trường hợp không có nhiễu. Và trong hình cuối cùng của cột
2, rất khó để chỉ ra biên. Yếu tố gây ra sự sai lệch này chính là nhiễu. Ảnh cuối
cùng có nhiều hạt nhỏ nhưng sự sai lệch này hầu như không thể nhận thấy.
Ví dụ trên cho thấy độ nhạy của đạo hàm đối với nhiễu, đạo hàm bậc hai nhạy
hơn đối với nhiễu. Đạo hàm bậc hai của ảnh không nhiễu ở ảnh trên cùng bên phải

11


của hình. Đường mảnh màu trắng và đen là thành phần dương và âm được nhắc đến
trong hình 1.7. Màu xám trong những ảnh này biểu diễn cho số 0 tương ứng trong
thang chia tỷ lệ. Nhiễu đạo hàm bậc hai (tương tự với trường hợp không có nhiễu)
tương ứng với nhiễu có độ lệch chuẩn ở mức xám 0.1. Hai ảnh đạo hàm bậc hai và
biên cho thấy rất khó để các tách thành phần âm và dương.
Thực tế, nhiễu khá nhỏ vẫn có thể có sự tác động đáng kể trên 2 đạo hàm then
chốt được dùng cho việc tách ảnh. Vì vậy đối với những ứng dụng rất có khả năng
xuất hiện nhiễu với các mức độ chúng ta vừa đề cập, ta nên làm trơn ảnh trước khi
xử lý.

Dựa vào ví dụ này và nội dung đã trình bày, chúng ta đưa ra kết luận rằng tiêu
chuẩn để phân loại 1 điểm biên là sự chuyển tiếp mức xám tương ứng với điểm đó
phải mạnh hơn đáng kể so với nền của điểm đó. Vì chúng ta đang đề cập đến tính
toán cục bộ, do đó chúng ta kết luận 1 điểm trong ảnh là điểm biên nếu đạo hàm bậc
nhất của nó lớn hơn một ngưỡng lý thuyết. Biên là tập hợp những điểm thỏa điều
kiện đó liên kết với nhau theo một tiêu chuẩn xác định cho trước. Sự phân đoạn giới
hạn biên được sử dụng nếu biên ngắn so với các kích cỡ của ảnh. Vấn đề then chốt
trong việc phân đoạn là lắp ráp các phần biên thành những biên dài hơn. Nếu chúng
ta quyết định sử dụng đạo hàm bậc hai để dễ dàng xác định các điểm biên trong 1
ảnh khi đạo hàm bậc hai của nó là 0 thì có 1 định nghĩa thay thế. Trong trường hợp
này, định nghĩa của biên cũng giống như trên. Điều quan trọng cần chú ý là những
định nghĩa này không đảm bảo thành công trong việc tìm điểm biên của ảnh.
Chúng chỉ đơn giản là cho chúng ta một hình thức tìm kiếm các điểm biên đó.
1.3.2. Liên kết biên và tách đường giới hạn
Phương pháp mà ta đã thảo luận trước đây giúp định ra những pixel nằm trên
biên và sắp xếp các pixel đó vào các tập hợp riêng. Tuy nhiên trong thực tế thì hiếm
khi tập hợp các pixel này xác định 1 cạnh hoàn chỉnh vì có sự xuất hiện của nhiễu,
sự vỡ cạnh do chiếu sáng không đồng đều và các tác động khác tạo ra mật độ gián
đoạn sai lệch . Chính vì vậy mà các giải thuật xác định biên luôn đi kèm với việc
liên kết các thủ tục nhằm tập hợp các pixel thành các cạnh có ý nghĩa. Sau đây là
một vài phương pháp cơ bản:
1.3.2.1 Xử lý cụ bộ

12


Một trong số những phương pháp đơn giản nhất để liên kết cạnh là phân tích
tính chất của các pixel trong 1 láng giếng nhỏ (3 × 3 hay 5 × 5) của những pixel mà
đã được định là 1 điểm của 1 cạnh nào đó bằng 1 trong các phương pháp đã bàn
trong phần trước. Tất cả các điểm mà thỏa một số tính chất định trước nào đó thì

được liên kết lại. Sau cùng ta sẽ có 1 cạnh thỏa các tính chất đã định trước.
Hai tính chất chính được dùng trong phương pháp phân tích này là :(1) Độ dài
của kết quả của toán tử gradient được sử dụng để tạo ra các pixel cạnh; và (2)
Hướng của véctơ gradient. Tính chất đầu tiên sử dụng giá trị của

∇f = mag ( ∇f ) = Gx2 + Gy2 
Trong đó :

Gx =

x
∇f = G
G
 y

1/ 2

hoặc

∇f

:

∇f ≈| Gx | +G y |

∂f
∂f
, Gy =
,
∂y

∂x

 ∂f 
∂x
 = ∂
f  Là Gradient của 1 ảnh f(x,y) tại vị trí (x,y).

 ∂y 



Vì vậy một pixel cạnh ( nghĩa là pixel đã được định là 1 điểm của 1 cạnh nào
đó) có tọa độ ( x0 , y0 ) trong một lân cận được xác định trước của (x,y) thì tương
đương với pixel (x,y) về độ lớn nếu:

| ∇f ( x, y ) − ∇f ( x0 , y0 ) |≤ E ,trong đó E là 1 ngưỡng không âm.
Hướng (góc) của véctơ gradient được đưa ra trong phương trình sau :

 Gy 
α ( x, y ) = tan −1 
÷ Trong đó : α(x,y) biểu diễn hướng góc của vector ∆f
 Gx 
tại (x, y) và hướng của một biên tại (x,y) trực giao với hướng của vector Gradient
tại điểm đó.
Một pixel cạnh tại

( x0 , y0 ) trong một lân cận cho trước của (x,y) có góc

tương tự với pixel (x,y) nếu:
không âm.


13

| α( x, y ) − α( x0 , y0 ) |< A

, với A là ngưỡng góc


Một điểm trong lân cận cho trước của (x,y) được liên kết với pixel tại (x,y) nếu
cả tiêu chuẩn về độ lớn và hướng được đáp ứng. Quá trình này được lặp lại tại mọi
vị trí trong bức ảnh. Sẽ có một mẫu tin lưu lại những điểm liên kết với điểm trung
tâm của vùng lân cận lần lượt di chuyển từ pixel này sang pixel khác. Một thủ tục
đánh dấu đơn giản là đưa ra cho mỗi tập hợp các pixel biên liên kết một mức xám
khác nhau.
Để minh họa cho nội dung này được thể hiện qua hình 1.9. Trong hình 1.9(a) ảnh chụp phía sau chiếc xe. Mục đích là để tìm ra hình chữ nhật có kích thước phù
hợp với kích thước của biển số xe. Thông tin của những hình chữ nhật này có thể
được lấy được bằng cách xác định các cạnh dọc và ngang của chúng. Hình 1.9(b) và
(c) thể hiện những cạnh dọc và ngang nhận được bằng cách sử dụng toán tử Sobel
dọc và ngang. Hình 1.9(d) là kết quả nhận được sau khi liên kết tất cả những điểm
có giá trị gradient lớn hơn 25 và hướng của véctơ gradient không khác biệt quá 150 .
Các đường ngang được tạo ra
bằng cách sử dụng liên tiếp các
tiêu chuẩn trên cho từng dòng
của hình 1.9(c). Lần lượt quét
từng cột của hình 1.9(b) thì ta
có các cạnh dọc. Hơn nữa quá
trình xử lý trên còn bao hàm cả
thao tác liên kết các đoạn cạnh
nhỏ bị phân chia do các vết nứt
nhỏ và hủy bỏ các đoạn cạnh

ngắn cô lập.
Hình 1.9 Minh họa phương pháp xử lý cục bộ

Cuối cùng, như ta thấy ở
hình 1.9(d), hình chữ nhật

tương ứng với biển số xe là 1 trong số các hình chữ nhật được xác định trong ảnh.
Và bây giờ thì thật dễ dàng để định vị biển số xe dựa vào các hình chữ nhật này
(phía dưới bên trái của hình 1.9d)
1.3.2.2 Liên kết cạnh và tách biên
Trong nội dung này, các điểm được liên kết với nhau đầu tiên nếu chúng nằm
trên một đường cong có hình dạng được định trước. Không giống như phương pháp

14


phân tích cục bộ đã được thảo luận trong phần trước, bây giờ chúng ta lại quan tâm
tới mối quan hệ toàn cục giữa các pixel.
Cho n điểm trên 1 bức ảnh. Giả sử rằng ta muốn tìm ra những tập con của các
điểm thuộc cùng một đường thẳng. Một lời giải khả dĩ là trước tiên tìm ra tất cả các
đường thẳng được xác định bởi mỗi cặp điểm, rồi sau đó tìm các tập con của những
điểm gần với các đường đặc biệt. Vấn đề nảy sinh trong cách làm này là nó bao

n(n − 1) n 2
gồm việc xác định ra
∼
2
2

đường thẳng và sau đó là khoảng


n.n( n −1) n 3
phép so sánh từng điểm có thuộc ngần ấy đường đó hay không.
∼
2
2
Cách tiếp cận này làm cho việc tính toán trở nên rất phức tạp ngay cả trong các ứng
dụng bình thường nhất.
Hough [1962] đã đề xuất 1 cách tiếp cận khác, đó là biến đổi Hough (Hough
transform). Xét điểm ( xi , yi ) và phương trình tổng quát của đường thẳng có dạng:

yi = axi + b . Có vô số đường thẳng cùng đi qua ( xi , yi ) , nhưng tất cả chúng đều
có dạng

yi = axi + b với các giá trị khác nhau của a và b. Tuy nhiên, khi viết lại

phương trình này dưới dạng

b=-ax i + yi và xét mặt phẳng ab (còn gọi là không

gian tham số) ta đưa ra được phương trình của một đường đơn cho một cặp

( xi , yi ) tương ứng. Hơn nữa, một điểm thứ hai ( x j , y j ) cũng có một đường trong
không gian tham số tương ứng với nó, và đường này giao với đường thẳng ứng với

( xi , yi ) tại (a', b'), với (a',b') là giao điểm của đường thẳng chứa cả hai điểm
( xi , yi ) và ( x j , y j ) trong mặt phẳng xy. Thực tế, tất cả mọi điểm trên đường này
đều có các đường trong không gian tham số giao nhau tại (a’,b’). Hình 1.10 minh
họa cho những khái niệm này.


15


Hình 1.10 Minh họa điểm trong mặt phẳng
Điểm đặc biệt trong tính toán của biến đổi Hough bắt nguồn từ việc chia nhỏ
không gian tham số thành những cái gọi là ô tích lũy (accumulator cells) như minh
họa trong hình 1.11, trong đó

(amax , amin ) và (bmax , bmin ) là những khoảng mong

đợi của các giá trị độ dốc (slope) và intercept. Ô ở tọa độ (i,j) (có giá trị tích lũy
A(i,j)) tương ứng với hình vuông trong không gian tham số có tọa độ

(ai , b j ) .

Quá trình xác định các giá trị
tích lũy được làm như sau :
B1: Cho mọi giá trị tích lũy
A(i,j) = 0.
B2: Với mỗi điểm ( xk , yk )
trong mặt phẳng ảnh.Ta đặt tham
số a = giá trị chia nhỏ trên trục x.
Sau đó giải

Hình 1.11 Chia không gian tham số

b = − xk a + yk rồi

làm tròn b tới giá trị gần nhất trên
trục b. Nếu một lựa chọn của ap


tìm được bq, chúng ta gán A(p,q) = A(p,q)+1.
B3: Cuối cùng ta thay giá trị Q trong A(i,j) tương ứng với Q điểm trong mặt
phẳng xy nằm trên đường thẳng

y = ai x + b j . Số lượng các điểm chia trong mặt

phẳng ab quyết định sự chính xác của sự cộng tuyến của các điểm này.

16


Cần chú ý rằng nếu số khoảng chia nhỏ của trục a là K thì ứng với mỗi điểm ảnh

( xk , yk ) , giá trị K của b tương ứng với các giá trị K có thể có của a. Do đó với n
điểm ảnh thì ta chỉ tốn nK phép tính. Vì vậy mà quá trình xử lý này là tuyến tính
theo n, và tích nK không đạt đến số phép tính đã được thảo luận ở đầu phần này trừ
khi K xấp xỉ hoặc lớn hơn n.
Tuy nhiên có vấn đề nảy sinh khi sử dụng phương trình y = ax + b để biểu diễn
1 đường thẳng là hệ số góc sẽ tiến tới vô cùng khi đường thẳng “xấp xỉ” trục đứng.
Một cách để khắc phục khó khăn này là sử dụng biểu diễn thông thường của đường
thẳng :

x cosθ + y sin θ = ρ

(1-3)

Hình 1.12 Minh họa chia nhỏ không gian hình học và tham số
Hình 1.12a minh họa sự giải thích bằng hình học của những tham số được sử
dụng trong phương trình (1.3). Việc sử dụng biểu diễn này trong việc xây dựng một

bảng của những bộ đếm thì giống với phương pháp đã thảo luận cho cách biểu diễn
Slope-intercept. Tuy nhiên, thay vì là những đường thẳng, quỹ tích các điểm đó lại
là các đường hình sin trong mặt phẳng

ρθ . Như trên, Q điểm cùng nằm trên đường

thẳng x cos θ j + y sin θ j = ρ tạo ra Q đường hình sin giao nhau tại (ρi , θ j ) trong
không gian tham số. Hình 1.12b biểu diễn việc chia không gian tham số. Tăng θ và
giải ρ tương ứng sẽ thu được Q dữ liệu trong giá trị tích lũy A(i,j) tương ứng với ô

17


được xác định bởi (ρi , θ j ) . Hình 1.12b minh họa việc chia nhỏ cho không gian tham
số.
Khoảng giá trị của

θ là ±900 , tương ứng với trục x. Do đó với biểu diễn trong

hình 19a, một đường thẳng nằm ngang sẽ có

θ = 00 và ρ bằng x-intercept dương.

Tương tự với trường hợp đường thẳng dọc ta có
dương , hoặc θ

θ = 900 còn ρ

bằng y-intercept


= −900 , với ρ bằng giá trị y-intercept âm.

Hình 1.13 minh họa biến đổi Hough dựa vào phương trình (1.3). Hình 1.13a
biểu diễn ảnh với 5 điểm được đánh số. Mỗi điểm được ánh xạ qua mặt phẳng ρθ
như biểu diễn ở hình 1.13b. Khoảng giá trị của giá trị

θ

là

±900 , và khoảng của

trục ρ là ± 2D , với D là khoảng cách giữa hai góc trong ảnh. Không giống như
biến đổi dựa trên việc sử dụng slope-intercept, mỗi đường cong có dạng hình sin
khác nhau. Đường nằm ngang là kết quả của việc ánh xạ điểm 1, đó là trường hợp
đặc biệt của một hàm sin với biên độ 0.

Hình 1.13 Minh họa biến đổi Hough

18


Thuộc tính nhận dạng sự cộng tuyến của biến đổi Hough được minh họa trong
hình 1.13c. Điểm A là giao điểm của những đường cong tương ứng với các điểm
1,3 và 5 trong mặt phẳng ảnh xy. Vị trí của điểm A cho thấy 3 điểm này nằm trên
một đường thẳng đi qua gốc tọa độ (ρ = 0) và có hướng là −450 . Tương tự, giao
điểm của những đường cong tại điểm B trong không gian tham số cho thấy các
điểm 2, 3, 4 nằm trên một đường thẳng có hướng 450 và khoảng cách của các điểm
đó đến gốc tọa độ bằng nửa khoảng cách đường chéo từ gốc đến góc đối diện của
ảnh.

Cuối cùng, hình 1.13d cho thấy rằng biến đổi Hough biểu diễn mối quan hệ đối
xứng tại những biên bên trái và bên phải của khoảng cách tham số. Thuộc tính này
được biểu diễn bởi những điểm A, B, C trong hình 1.13d, là kết quả của phương
pháp với ρ và θ thay đổi dấu tại các đường bao ±900 .
Mặc dù biến đổi Hough chủ yếu dành cho đường thẳng nhưng ta vẫn có thể áp
dụng nó cho bất cứ hàm nào có dạng g(v,c) = 0, trong đó v là vector tọa độ và c là
vector hệ số. Ví dụ các điểm nằm trên đường tròn

( x − c1 ) 2 + ( y − c2 ) 2 = c32

(1-4)

có thể được xác định bằng cách sử dụng phương pháp trên. Sự khác nhau cơ bản là
sự hiện diện của 3 tham số (c 1, c2 và c3), mà kết quả nằm trong không gian tham số
3-D với những khối lập phương và tích lũy có dạng A(i, j, k). Thủ tục này là để tăng
c1, c2, tìm c3 theo phương trình (1-4) và cập nhật giá trị tích lũy cho các ô tương
ứng với bộ ba (c1, c2 và c3). Rõ ràng, độ phức tạp của biến đổi Hough tỉ lệ với số
lượng tọa độ và những hệ số được cho trong phương trình biểu diễn. Hơn nữa, ta có
thể suy rộng biến đổi Hough nhằm nhận diện các đường cong có biểu diễn không
đơn giản, như là ứng dụng của biến đổi ảnh xám.
Tóm lại, một phương pháp dựa trên biến đổi Hough được trình bày như sau:
+ Tính gradient của một ảnh và ngưỡng để thu được ảnh nhị phân.
+ Chia nhỏ mặt phẳng ρθ .
+ Kiểm tra việc đếm các ô tích lũy (accumulator cell) cho những vùng tập trung
pixel cao.
+ Kiểm tra các quan hệ ( chủ yếu là về sự liên tục) giữa các pixel trong ô được
chọn.

19



Khái niệm liên tục trong trường hợp này dựa trên tính toán khoảng cách giữa
những pixel không liên kết được xác định trong suốt quá trình quét tập hợp những
pixel tương ứng với những ô tích lũy (accumulator cell) được đưa vào. Độ lệch tại
một điểm bất kì là đáng kể nếu khoảng cách giữa điểm đó và lân cận gần nhất của
nó vượt quá một ngưỡng xác định.
1.3.2.3 Xử lý toàn cục bằng phương pháp lý thuyết đồ thị
Trước hết ta cần quan tâm đến một số định nghĩa cơ bản: Một đồ thì G= (N, U)
là một tập hợp các nốt N khác rỗng hữu hạn, với một tập hợp U không có thứ tự các
cặp thành phần nhất định của tập N. Mỗi cặp (ni, nj) của U được gọi là một cung.
Một đồ thị mà các cạnh có hướng được
gọi là đồ thị có hướng. Nếu một cung có
hướng từ ni đến nj, thì nj là con của nốt ni.
Quá trình nhận biết một successor của 1
nốt được gọi là khai triển của một nốt.

Hình 1.14 Minh họa láng giềng-4

Trong mỗi đồ thị chúng ta xác định các
mức của nó, chẳng hạn mức 0 gồm một nốt

đơn, gọi là nốt bắt đầu hay nốt gốc, và những nốt ở mức cuối cùng được gọi là nốt
lá. c(ni, nj) có thể kết nối được với mọi cung (n i, nj). Một dãy các nốt n 1, n2,…, nk
( trong đó mỗi nốt ni là một nốt con của n i-1) được gọi là một đường đi từ n 1 đến nk.
Trọng số của toàn bộ đường đi là:
k

c = ∑ c ( ni −1 , ni )

(1-5)


i =2

Một thành phần cạnh như là đường bao giữa 2 pixel p và q, với p và q là láng
giềng-4 như minh họa ở hình 1.14. Những thành phần cạnh được định nghĩa bởi
những tọa độ (x,y) của điểm p và q. Nói cách khác, thành phần cạnh trong hình 1.14
được định nghĩa bởi cặp (x p, yp)(xq, yq). Giống với định nghĩa trong 1.3.1.3, một
cạnh là một dãy các thành phần cạnh liên kết với nhau.
Chúng ta có thể minh họa cách áp dụng tư tưởng trên để tách biên sử dụng ảnh
3x3 trong hình 1.15a. Các số bên ngoài là các tọa độ pixel và số bên trong ngoặc
vuông biểu diễn giá trị mức xám.

20


Mỗi thành phần biên xác định bởi pixel p và q có trọng số tương ứng được định
nghĩa bởi:

c ( p, q ) = H − [ f ( p ) − f ( q ) ]

(1-6)

Với H là giá trị mức xám cao nhất trong bức ảnh (trong trường hợp này là 7), và
f ( p) và f ( q) là giá trị mức xám của p và q. Qui ước điểm p nằm bên tay phải của

hướng di chuyển dọc theo thành phần biên.

Hình 1.15 Minh họa tách biên trong phưong pháp lý thuyết đồ thị

Hình 1.16 Biểu diễn đồ thị trong phương pháp lỹ thuyết đồ thị


21


Ví dụ: đoạn biên (1, 2) (2, 2) nằm giữa điểm (1, 2) và (2, 2) trong hình 1.15b. Nếu
hướng di chuyển sang bên phải thì p là điểm có tọa độ (2, 2) và q là điểm có tọa độ
(1, 2); khi đó c(p, q) = 7 - [ 7 - 6] = 6. Trọng số này được biểu diễn trong hình
vuông bên dưới thành phần biên. Nếu chúng ta di chuyển sang trái giữa hai điểm
như trên thì p là điểm (1, 2) và q là điểm (2, 2). Trong trường hợp này c(p, q) = 8,
được thể hiện bên trên của thành phần biên trong hình 1.15b. Để đơn giản chúng ta
giả sử rằng các cạnh bắt đầu ở hàng trên cùng và kết thúc ở hàng cuối, vì vậy thành
phần đầu tiên của biên chỉ có thể nằm giữa những điểm (1, 1), (1, 2) hoặc (1, 2), (1,
3). Tương tự thành phần biên cuối cùng chỉ nằm giữa những điểm (3, 1), (3, 2) hoặc
(3, 2), (3, 3). Dựa theo ý tưởng này thì p và q là liên láng giềng 4 như chú ý trên.
Hình 1.16 biểu diễn đồ thị cho vấn đề này. Mỗi nốt trong đồ thị tương ứng với
thành phần biên từ hình 1.15. Giữa 2 nốt có một cung nếu 2 thành phần biên tương
ứng là một thành phần của một cạnh. Như hình 1.15(b), trọng số của mỗi thành
phần biên được tính toán bằng công thức 1-6, được biểu diễn trong hình vuông nằm
bên cạnh cung nối với nốt tương ứng. Các nốt lá được tô đậm. Đường đi có trọng số
nhỏ nhất được biểu diễn bằng đường đứt nét và cạnh tương ứng với đường đi này
được biểu diễn trong hình 1.15(c).
Thường thì vấn đề tìm đường đi có trọng số nhỏ nhất không đơn giản trong tính
toán. Phương pháp này sẽ làm mất đi sự tối ưu tốc độ. Thuật toán sau đây biểu diễn
lớp các thủ tục sử dụng heuristic để giảm đi việc tìm kiếm. Đặt r(n) là ước lượng
của trọng số của đường đi có trọng số nhỏ nhất từ điểm bắt đầu s cho đến nốt lá,
trong đó đường đi phải đi qua n. Trọng số này có thể biểu diễn như là một trọng số
ước lượng của đường đi có trọng số nhỏ nhất từ s đến n cộng với trọng số của
đường đi đó từ n đến nốt lá, tức là,
r(n) = g(n) + h(n)


(1-7)

trong đó g(n) có thể chọn như là đường đi có trọng số nhỏ nhất từ s tới n đã được
tìm thấy, và h(n) có được bằng cách sử dụng bất kỳ thông tin heruristic nào có giá
trị. Một thuật toán sử dụng r(n) như là nền tảng cho biểu diễn tìm kiếm trong đồ thị
gồm các bước sau:
Bước 1 : Đánh dấu nốt bắt đầu là OPEN và đặt g(s) =0.
Bước 2 : Nếu không có nốt nào OPEN thì thoát và báo lỗi, ngược lại đến bước 3.

22


Bước 3 : Đánh dấu CLOSED cho nốt OPEN n mà ước lượng r(n) được tính từ
phương trình (1-7) là nhỏ nhất.
Bước 4 : Nếu n là nốt lá thì kết thúc, ta nhận được đường đi kết quả bằng việc dò
ngược con trỏ. Ngược lại, qua bước 5.
Bước 5 : Mở rộng nốt n, khởi tạo tất cả các phần tử tiếp theo của nó (nếu không có
phần tử tiếp theo thì đến bước 2).
Bước 6 : Nếu một phần tử tiếp theo ni không được đánh dấu. Đặt
r(ni)= g(n) + c(n, ni) ,
đánh dấu OPEN, và hướng con trỏ quay ngược lại n.
Bước 7 : Nếu phần tử kế tiếp ni được đánh dấu CLOSED hoặc OPEN, cập nhật giá
trị của nó bằng cách đặt
g’(ni) = min[ g(ni), g(n) + c(n,ni)] .
Đánh dấu OPEN cho những nốt CLOSED kế tiếp có giá trị g’ nhỏ và định
hướng lại các con trỏ đến n từ tất cả những nốt mà giá trị g’ nhỏ, trở về bước 2.
Thuật toán này không chắc chắn đưa ra đường đi ngắn nhất, ưu điểm của nó là
tốc độ nhờ sử dụng heuristic. Tuy nhiên, nếu h(n)
là giới hạn nhỏ hơn của trọng số của đường đi
ngắn nhất từ n đến một nốt lá thì thuật toán này sẽ

tìm được một đường đi tối ưu. Nếu không có
Hình 1.17 Minh họa
kết quả phân đoạn phương
pháp lý thuyết đồ thị

thông tin Heuristic nào có giá trị (nghĩa là h ≡ 0)
thì phải dùng thuật toán Dijkstra [1959].

Ví dụ :
Hình 1.17 biểu diễn bức ảnh của một ảnh của bóng nhiễm sắc thể bị nhiễu và một
biên được tìm thấy bằng cách sử dụng tìm kiếm đồ thị heuristic dựa trên thuật toán
được phát triển trong mục này. Biên biểu diễn bằng màu trắng chồng lên trên ảnh
gốc. Chú ý rằng, trong trường hợp này biên và giới hạn của đối tượng là xấp xỉ như
nhau. Trọng số tính theo phương trình 1-6 và heuristic sử dụng ở một điểm bất kỳ
trên đồ thị là để xác định và sử dụng đường đi tối ưu cho 5 mức từ điểm đó. Xem
xét số lượng nhiễu biểu diễn trong hình này, ta thấy phương pháp tìm kiếm đồ thị đã
đưa ra một kết quả chính xác hợp lý.
1.3.3. Phân đoạn dựa vào ngưỡng biên độ

23


Bởi vì những tính chất trực giác và sự thực hiện đơn giản nên phân ngưỡng
được sử dụng nhiều trong phân đoạn ảnh [4]. Trong các các nội dung trước đó,
chúng ta đã đề cập sơ về ngưỡng cùng một số ứng dụng đơn giản của nó, trong nội
dung này sẽ trình bày về ngưỡng một cách chi tiết hơn.
1.3.3.1 Ngưỡng biên độ

Hình 1.18 Minh họa histogram của một ảnh
Ta giả sử rằng histogram mức xám trong hình 1.18a là histogram của 1 tấm ảnh

(gọi là f(x,y)) gồm có các vật thể sáng trên 1 nền tối. Các pixel của các vật thể lẫn
cái nền có mức xám được chia vào 2 dạng chính ( dominant modes). Một cách tự
nhiên để trích các vật thể ra là chọn 1 ngưỡng T mà có thể phân chia các dạng này.
Khi đó với điểm (x,y) thì (x,y) sẽ được gọi là điểm vật thể nếu f(x,y) > T, ngoài ra
gọi (x,y) là điểm nền.
Hình 1.18b thể hiện 1 trường hợp tổng quát hơn 1 chút về cách tiếp cận này.
Trong đó 3 dạng chính biểu thị tính chất của histogram ảnh ( trong ví dụ ta thấy có
2 vật thể sáng trên 1 nền tối). Ở đây, ngưỡng nhiều mức (mutilevel thresholding)
chia 1 điểm (x,y) hoặc thuộc về 1 lớp vật thể nếu
lớp vật thể khác nếu f(x,y) >

T1 < f ( x, y ) ≤ T2 hoặc thuộc 1

T2 , và hoặc thuộc về nền nếu f ( x, y ) ≤ T1 . Trong

trường hợp tổng quát, bài toán phân đoạn yêu cầu nhiều ngưỡng được giải quyết tốt
nhất bằng cách dùng phương pháp tăng vùng (sẽ giới thiệu trong phần 1.3.4.2).
Dựa trên những gì đã nói trên , việc chọn ngưỡng có thể xem như 1 thao tác
kiểm tra hàm T :
T = T[x, y, p(x,y), f(x,y)]

24

(1-8)


với f(x,y) là mức xám của điểm (x,y) còn p(x,y) là 1 số tính chất địa phương của
điểm này (ví dụ như mức xám trung bình của 1 láng giềng tâm (x,y)). Một bức ảnh
đã được phân ngưỡng g(x,y) được định nghĩa như sau:


1
g(x,y)= 
0

khi f(x,y) > T
khi f(x,y) ≤ T

trong đó ta hiểu f(x,y) là mức xám tại (x,y). Do đó tất cảc các pixel nào được
gán giá trị 1 (hoặc bất kỳ 1 mức xám thuận lợi nào) thì tương ứng với các vật thể,
còn các pixel được gán giá trị 0 (hoặc 1 giá trị nào khác mức xám đã gán cho các
vật thể) tương ứng với nền.
Khi T chỉ phụ thuộc vào f(x,y) (tức là chỉ phụ thuộc vào giá trị mức xám) thì
ngưỡng được gọi là ngưỡng toàn cục. Nếu T phụ thuộc vào f(x,y) và p(x,y) thì
ngưỡng được gọi là ngưỡng cục bộ. Ngoài ra nếu T phụ thuộc vào các tọa đô không
gian x và y thì ngưỡng được gọi là động (adaptive).
1.3.3.2 Ảnh hưởng của sự chiếu sáng trong việc chọn ngưỡng.
Chúng ta đã biết f(x,y) có thể được định dạng như tích của thành phần năng suất
phản xạ (reflectance component) r(x,y) và thành phần chiếu sáng (illumination
component) i(x,y). Do đó trong mục này sẽ sử dụng dạng này nhằm giới thiệu ngắn
gọn về ảnh hưởng của sự chiếu sáng lên trên việc chọn ngưỡng, đặc biệt với ngưỡng
toàn cục.
Lưu ý tới hàm phản xạ được xác định bởi máy tính biểu diễn trong hình 1.19a.
Histogram của hàm này ( được thể hiện trong hình 1.19b) phân làm đôi một cách rõ
ràng và có thể dễ dàng chia ra bằng cách dùng một ngưỡng toàn cục đơn (single
global threshold) T tại rãnh của histogram. Nhân hàm phản xạ trong hình 1.19a với
hàm chiếu sáng (biểu diễn bằng hình 1.19c) thì tạo ra bức ảnh như trong hình 1.19d.
Và hình 1.19e là histogram của bức ảnh này. Chú ý là rãnh gốc ban đầu hầu như đã
bị loại bỏ, do đó việc phân đoạn ảnh bằng 1 ngưỡng đơn trở nên không thể. Mặc dù
chúng ta hiếm khi làm việc với hàm phản xạ nhưng minh họa này cho thấy chúng ta
có thể dễ dàng phân chia tính chất phản xạ tự nhiên của các vật thể và nền. Ngược

lại, bức ảnh kết quả trong ví dụ lại rất khó để phân đoạn.
Vậy tại sao histogram trong hình 1.19e bị biến dạng rất nhiều so với histogram
của hàm phản xạ ? ta có thể được giải thích như sau:

25


f ( x, y ) = i ( x, y ) r ( x, y )
Lấy ln hai vế ta có :

(1-9)

z ( x, y ) = ln f ( x, y )
= lni(x,y) + lnr(x,y)

(1-10)

= i’(x,y) + r’(x,y)
Theo định lý xác suất (Papoulis – 1991), nếu i’(x,y) và r’(x,y) là 2 biến ngẫu
nhiên độc lập thì histogram của z(x,y) là tích chập (convolution) của histogram của
i’(x,y) và histogram của r’(x,y). Nếu i(x,y) là hằng số thì i’(x,y) cũng là hằng số và
histogram của i’(x,y) có dạng xung đơn (nghĩa là 1 đoạn thẳng) giống như một xung
lực. Tích chập của hàm số dạng xung lực này với histogram của r’(x,y) không làm
thay đổi hình dạng cơ bản của histogram của r’(x,y) (tích chập của một hàm số với
một xung lực sẽ sao chép lại hàm số ở vị trí xung lực). Tuy nhiên nếu i’(x,y) có một
histogram rộng hơn (nguyên nhân là do sự chiếu sáng không đồng đều) thì tích chấp
sẽ làm thay đổi nhiều hình dạng của histogram của r’(x,y). Do đó histogram của
z(x,y) có thể có hình dạng hoàn toàn khác histogram của r’(x,y). Độ sai lệch phụ
thuộc vào độ rộng của histogram của i’(x,y), mà độ rộng này thì lại phụ thuộc vào
mức độ không đồng đều của sự chiếu sáng.


26