MỤC LỤC
PHÂN CÔNG CÔNG VIỆC.................................................................................1
LỜI MỞ ĐẦU.......................................................................................................2
CHƯƠNG I. CƠ SỞ LÝ THUYẾT......................................................................3
1.1. Máy học là gì...............................................................................................3
1.2. Tiến trình máy học và phân loại các thuật tốn...........................................4
1.2.1. Tiến trình máy học................................................................................4
1.2.2. Phân loại các thuật tốn........................................................................5
CHƯƠNG II. THUẬT TỐN K-MEANS...........................................................9
2.1. Giới thiệu thuật toán và các định nghĩa cơ sở.............................................9
2.2. Thuật tốn K-means....................................................................................9
2.3. Ví dụ minh họa..........................................................................................10
2.4. Ưu và khuyết điềm của thuật toán.............................................................12
2.5. Cải tiến thuật toán K-means......................................................................12
CHƯƠNG III. ỨNG DỤNG THUẬT TOÁN K-MEANS TRONG PHÂN
ĐOẠN ẢNH........................................................................................................15
3.1. Giới thiệu về phân đoạn ảnh......................................................................15
3.1.1. Các phương pháp dựa trên không gian đặc trưng...............................16
3.1.2. Các phương pháp dựa trên không gian ảnh.........................................16
3.1.3. Các phương pháp dựa trên mơ hình vật lý..........................................17
3.2. Phát biểu ứng dụng....................................................................................18
KẾT LUẬN.........................................................................................................22
TÀI LIỆU THAM KHẢO...................................................................................23

1


PHÂN CƠNG CƠNG VIỆC
1. Ngụy Đình Thành - Trưởng nhóm
- Tìm hiểu nội dung liên quan và thiết kế khung của bài tiểu luận.
- Thực hiện cải tiến thuật toán.

- Thực hiện chương trình phân đoạn ảnh và demo.
2. Đồn Hữu Phước
- Tìm hiểu lý thuyết và thuyết trình.
- Tìm hiểu ứng dụng phân đoạn ảnh của thuật toán K-Means.
3. Nguyễn Hữu Khánh
- Tìm hiểu về tổng quan về thuật toán K-Means.
- Tổng hợp word và chỉnh sửa bài tiểu luận.
4. Đặng Văn Chung
- Tìm hiểu tổng quan cơ sở lý thuyết học máy.
- Tổng hợp word và làm slides.

1


LỜI MỞ ĐẦU
Trong thời đại hiện nay, sự phát triển như vũ bão của công nghệ thông tin
(CNTT) đã kéo theo sự phát triển của nhiều lĩnh vực khác. Có thể nói, CNTT
đang làm thay đổi hình hài của nền kinh tế thế giới, giúp nhân loại bước những
bước vững chắc đầu tiên trên con đường của kinh tế tri thức, thương mại điện
tử… Ngày nay, con người khơng cịn phải vất vả nhọc nhằn trong công việc thu
thập dư liệu vì đã có trợ thủ đắc lực là hệ thống máy tính và mạng truyền số liệu
triển khai ở quy mơ tồn cầu.
Tuy nhiên, sự phát triển vượt bậc của CNTT đã làm tăng số lượng giao
dịch thông tin trên mạng Internet một cách đáng kể, đặc biệt là thư điện tử, tin
tức điện tử... Một yêu cầu lớn đặt ra đối với chứng ta là làm sao tổ chức, tìm
kiếm thơng tin một cách hiệu quả nhất và phân loại thông tin là một trong những
giải pháp hợp lý cho yêu cầu này. Nhưng vối một khối lượng thơng tin q lớn
và địi hỏi phải xử lý nhanh thì việc phân loại thủ cơng là điều khơng tưởng.
Hướng giải quyết là xây dựng các giải pháp cho phép thuật tốn hóa và chương
trình hóa trên máy tính để có thể tự động phân loại các thơng tin trên.

Trong thập kỷ qua, việc ứng dụng máy học vào khoa học kỹ thuật đã giúp
cho chúng ta có thể tạo ra được những chiếc xe tự lái, nhận dạng giọng nói thực
tế, tìm kiếm web có hiệu quả, và sự hiểu ngày càng sâu sắc hơn về bộ gen của
con người, v.v... Ngày nay máy học phổ biến đến nỗi chúng ta có thể sử dụng nó
hàng chục lần một ngày mà khơng hề hay biết biết. Nhìn thấy khả năng và ứng
dụng của ML, đề tài nghiên cứu của chúng em là “Tìm hiểu thuật tốn KMeans và ứng dụng của thuật tốn K-means trong phân đoạn ảnh”. Ngồi
phần mở đầu, kết luận, bài tìm hiểu của nhóm gồm 3 chương:
Chương I: Cơ sở lý thuyết.
Chương II: Thuật toán K-Means.
Chương III: Ứng dụng thuật toán K-Means trong phân đoạn ảnh.
2


CHƯƠNG I. CƠ SỞ LÝ THUYẾT
1.1. Máy học là gì
Rất khó để có thể định nghĩa một cách chính xác về máy học. Một trong
những định nghĩa rộng nhất về thuật ngữ máy học là: “một cụm từ dùng để chỉ
khả năng một chương trình máy tính để tăng tính thực thi dựa trên những kinh
nghiêm đã trải qua” hoặc “là để chỉ khả năng một chương trình có thể phát sinh
ra một cấu trúc dữ liệu mới khác với các cấu trúc dữ liệu cũ”.
Lợi điểm của các phương pháp máy học là nó phát sinh ra các luật tường
minh, có thể được sửa đổi, hoặc được huấn luyện trong một giới hạn nhất
định.Các phương pháp này học trên các dữ liệu có đặc tả thơng tin. Cấu trúc
thơng tin gồm 4 mức được gọi là tri thức kim tự tháp.

Hình 1.1. Mơ hình tri thức kim tự tháp
Máy học là sự tự động của quy trình học và việc học thì tương đương với
việc xây dựng những luật dựa trên việc quan sát trạng thái trên cơ sở dữ liệu và
những sự chuyển hoá của chúng.
Máy học kiểm tra những ví dụ trước đó và kiểm tra ln cảnhững kết quả của

chúng khi xuất và học làm cách nào để tái tạo lại những kết quả này và tạo nên
những sự tổng quát hóa cho những trường hợp mới.

3


Nói chung, máy học sử dụng một tập hữu hạn dữ liệu được gọi là tập huấn
luyện. Tập này chứa những mẫu dữ liệu mà nó được viết bằng mã theo một cách
nào đó để máy có thể đọc và hiểu được.
Tuy nhiên, tập huấn luyện bao giờ cũng hữu hạn do đó khơng phải tồn bộ dữ
liệu sẽ được học một cách chính xác.
Lợi ích của máy học
Các thơng tin ngày càng nhiều, hàng ngày ta phải xử lý rất nhiều thông tin
đến từ nhiều nguồn khác nhau. Máy học có thể giúp xứ lý và dự báo các thơng
tin đó bằng cách tạo ra các luất sản xuất từdữ liệu thu thập. Ở những nơi khơng
có chun gia, máy học có thể giúp tạo ra được các quyết định từ các dữ liệu có
được. Các thuật tốn sử dụng trong máy học máy học có thể giúp xử lý khi dữ
liệu khơng đầy đử, khơng chính xác.
Máy học giúp thiết kế hệ thống huấn luyện tự động (mạng nơrôn nhân tạo) và
giải mã mối liên hệ giữa các tri thức được lưu trữtrong mạng từ dữ liệu. Công
nghệ Máy học là một trong những phương pháp chính trong khai phá dữ liệu.
Nó được sử dụng trong tiến trình khám phá tri thức.
1.2. Tiến trình máy học và phân loại các thuật tốn
1.2.1. Tiến trình máy học
Một tiến trình máy học bao gồm 2 giai đoạn:
 Giai đoạn học: hệ thống phân tích dữ liệu và nhận ra sự mối quan hệ (có
thể là phi tuyến hoặc tuyến tính) giữa các đối tượng dữ liệu. Kết quả của
việc học có thể là: nhóm các đối tượng vào trong các lớp, tạo ra các luật,
tiên đoán lớp cho các đối tượng mới.
 Giai đoạn thử nghiệm: Mối quan hệ (các luật, lớp...) được tạo ra phải

được kiểm nghiệm lại bằng một số hàm tính tốn thực thi trên một phần
của tập dữ liệu huấn luyện hoặc trên một tập dữ liệu lớn.
4


1.2.2. Phân loại các thuật toán
Các thuật toán máy học được chia làm 3 loại: học giám sát, học không giám
sát và học nửa giám sát.


Học có giám sát (Supervised Learning).

Đây là cách học từ những mẫu dữ liệu mà ở đó các kỹ thuật máy học giúp
hệ thống xây dựng cách xác định những lớp dữ liệu. Hệ thống phải tìm một sự
mơ tả cho từng lớp (đặc tính của mẫu dữ liệu). Người ta có thể sử dụng các luật
phân loại hình thành trong quá trình học và phân lớp để có thể sử dụng dự báo
các lớp dữ liệu sau này.
Thuật tốn học có giám sát gồm tập dữ liệu huấn luyện M cặp:
S = {(xi, cj) i=1,…,M; j=1,…,C}
Các cặp huấn luyện này được gọi là mẫu, vớixi là vector n-chiều còn gọi
là vector đặc trưng, cj là lớp thứ j đã biết trước.
Thuật toán máy học giám sát tìm kiếm khơng gian của những giả thuyết
có thể, gọi là H. Đối với một hay nhiều giả thuyết, mà ước lượng tốt nhất hàm
khơng được biết chính xác f : x  c.Đối với công việc phân lớp có thể xem giả
thuyết như một tiêu chí phân lớp.
Thuật tốn máy học tìm ra những giả thuyết bằng cách khám phá ra
những đặc trưng chung của những ví dụ mẫu thể hiện cho mỗi lớp. Kết quả nhận
được thường ở dạng luật (Nếu ... thì).
Khi áp dụng cho những mẫu dữ liệu mới, cần dựa trên những giả thuyết đã
có để dự báo những phân lớp tương ứng của chúng. Nếu như khơng gian giả

thuyết lớn, thì cần một tập dữ liệu huấn luyện đủ lớn nhằm tìm kiếm một hàm
xấp xỉ tốt nhất f. Tùy thuộc vào mức độ của thuật toán học giám sát, người ta có
những mơ hình học giám sát như sau:

5


 Học vẹt (rote): hệ thống luôn luôn được “dạy” những luật đúng, rồi có học
hội tụ.
 Học bằng phép loại suy (analogy): hệ thống được dạy phản hồi đúng cho
một cơng việc tương tự, nhưng khơng xác định. Vì thế hệ thống phải hiệu
chỉnh phản hồi trước đó bằng cách tạo ra một luật mới có thể áp dụng cho
trường hợp mới.
 Học dựa trên trường hợp (case-based learning): trong trường hợp này hệ
thống học lưu trữ tất cả các trường hợp, cùng với kết quả đầu ra của
chúng. Khi bắt gặp một trường hợp mới, nó sẽ cố gắng hiệu chỉnh đến
trường hợp mới này cách xử lý trước đó của nó đã được lưu trữ.
 Học dựa trên sự giải thích (explanation-based learning), hệ thống sẽ phân
tích tập hợp những giải pháp nhằm chỉ ra tại sao mỗi phương pháp là
thành công hay không thành công. Sau khi những giải thích này được tạo
ra, chúng sẽ được dùng để giải quyết những vấn đề mới.
Một số thuật tốn học có giám sát.
-

Support Vector Machine – SVM.

-

K Nearest Neighbours – KNN.


-

Naïve Bayes – NB.

-

Decision Tree – DT.

-

Neural Network – Nnet.

-

Centroid–base vector.

-

Linear Least Square Fit – LLSF.

 Học Không giám sát (Unsupervised Learning).
Đây là việc học từ quan sát và khám phá. Hệ thống khai thác dữ liệu được
ứng dụng với những đối tượng nhưng khơng có lớp được định nghĩa trước, mà
6


để nó phải tự hệ thống quan sát những mẫu và nhận ra mẫu. Hệ thống này dẫn
đến một tập lớp, mỗi lớp có một tập mẫu được khám phá trong tập dữ liệu. Học
khơng giám sát cịn gọi là học từ quan sát và khám phá.
Trong trường hợp chỉ có ít, hay gần như khơng có tri thức về dữ liệu đầu

vào, khi đó một hệ thống học khơng giám sát sẽ khám phá ra những phân lớp
của dữ liệu, bằng cách tìm ra những thuộc tính, đặc trưng chung của những mẫu
hình thành nên tập dữ liệu.Một thuật tốn máy học giám sát ln có thể biến đổi
thành một thuật tốn máy học khơng giám sát (Langley 1996).Đối với một bài
tốn mà những mẫu dữ liệu được mơ tả bởi n đặc trưng, người ta có thể chạy
thuật toán học giám sát n-lần, mỗi lần với một đặc trưng khác nhau đóng vai trị
thuộc tính lớp, mà chúng ta đang tiên đốn.Kết quả sẽ là n tiêu chí phân lớp (n
bộ phân lớp), với hy vọng là ít nhất một trong n bộ phân lớp đó là đúng.
Một số thuật tốn học khơng giám sát:
-

Thuật tốn K-means

-

Mơ hình mạng Neural

-

Hệ thống ART (adaptive resonance theory)

 Học nửa giám sát.
Học nửa giám sát là các thuật tốn học tích hợp từ học giám sát và học
không giám sát. Việc học nửa giám sát tận dụng những ưu điểm của việc học
giám sát và học không giám sát và loại bỏ những khuyết điểm thường gặp trên
hai kiểu học này.
Một số thuật toán học nửa giám sát.
-

EM - Expectation Maximization.


-

TSVM - Transductive Support Vector Machine.

-

Self-training.
7


-

Co-training.

-

Các phương pháp dựa trên đồ thị (graph-based).

8


CHƯƠNG II. THUẬT TỐN K-MEANS
2.1. Giới thiệu thuật tốn và các định nghĩa cơ sở
Thuật toán K-means thuộc vào loại thuật tốn khơng giám sát rất đơn giản
và được áp dụng rộng rãi vào các mẫu bài toán phân cụm do MacQueen giới
thiệu

trong tài


liệu “J.

Some

Methods

for Classification and Analysis

of Multivariate Observations” năm 1967.
Bài tốn phân cụm là q trình nhóm một nhóm các điềm dữ liệu vào
trong một số lượng nhỏ các cụm. Tổng quát về mặt biểu diễn toán học, chúng ta
có n điểm dữ liệu xi,i=1...n cần phải được phân vào trong k cụm. Mục tiêu của
bài toán là một điểm dữ liệu cho một cụm. Thuật toán K-means cung cấp cho
chúng ta một phương pháp để tìm ra được vị trí các điểm μi,i=1...k của các cụm
sao cho hàm khoảng cách từ các điểm đến các cụm là nhỏ nhất.

Trong đó ci là một tập các điểm bên trong cụm i. Thuật toán K-means sử
dụng khoảng cách Euclidean
2.2. Thuật toán K-means
Thuật toán K-means được dùng để giải bài toán về phân cụm hoạt động
qua từng bước như sau:
Đầu tiên chúng ta cần xác định số cụm k
1. Khởi tạo điểm trung
tâm của cụm

μi,i=1,...,k

2. Gán các điểm dữ liệu
vào các cụm gần nhất
3. Thiết lập lại điểm

trung tâm của mỗi
9


cụm
4. Lặp lại các bước 2-3
cho đến khi hội tụ
Ghi chú

|c|= số phần tử trong c

Thuật toán k-means trên được chứng minh là hội tụ và có độ phức tạp tính
tốn là:

Trong đó, n là số đối tượng dữ liệu, k là số cụm dữ liệu, d là số chiều, τ là
số vòng lặp, Tflop là thời gian để thực hiện một phép tính cơ sở như phép tính
nhân, chia... Như vậy, do K-means phân tích phân cụm đơn giản nên có thể áp
dụng đối với tập dữ liệu lớn. Tuy nhiên, nhược điểm của K-means là chỉ áp dụng
với dữ liệu có thuộc tính số và khám phá ra các cụm có dạng hình cầu, k-means
cịn rất nhạy cảm với nhiễu và các phần tử ngoại lai trong dữ liệu. Hơn nữa, chất
lượng phân cụm dữ liêuk của thuật toán k-means phụ thuộc nhiều vào các tham
số đầu vào như: số cụm k và k trọng tâm khởi tạo ban đầu. Trong trường hợp các
trọng tâm khởi tạo ban đầu mà quá lệch so với các trọng tâm cụm tự nhiên thì
kết quả phân cụm của k-means là rất thấp, nghĩa là các cụm dữ liệu được khám
phá rất lệch so với các cụm trong thực tế. Trên thực tế chưa có một giải pháp tối
ưu nào để chọn các tham số đầu vào, giải pháp thường được sử dụng nhất là thử
nghiệm với các giá trị đầu vào k khác nhau rồi sau đó chọn giải pháp tốt nhất.
2.3. Ví dụ minh họa
Trong phần này chúng ta sẽ xem qua các bước thực hiện của thuật toán Kmeans bằng đồ họa


10


Hình 2.1. Giá trị gốc ban đầu

Hình 2.2. Khởi tạo các cụm ban đầu

Hình 2.3. Gán các điểm dữ liệu vào Hình 2.4. Tính tốn lại vị trí các điểm
trung tâm của cụm
các cụm

Hình 2.5. Gán các điểm dữ liệu

Hình 2.6. Thuật tốn dừng lại vì

vào trong các cụm

khơng có điểm thay đổi

11


Thuật tốn kết thúc vì khơng có sự thay đổi của các đối tượng trong từng cụm.
2.4. Ưu và khuyết điềm của thuật toán
Ưu điểm:
 Với số lượng biến lớn thì thuật tốn K-means có thể tính tốn nhanh hơn
so với các thuật tốn phân nhóm phân cấp khác (nếu K là nhỏ).
 K-means có thể gom các cụm chặt chẽ hơn so với phân cụmtheo cấp bậc,
đặc biệt là nếu các cụm hình cầu.
Khuyết điểm: Giống như các thuật tốn khác, k- means cũng có một số

khuyết điềm nhất định:
 Việc khởi tạo phần tử trung tâm của các cụm ban đầu ảnh hưởng đến sự
phân chia đối tượng vào cụm trong trường hợp dữ liệu không lớn.
 Số cụm k luôn phải được xác định trước.
 Không xác định được rõ ràng vùng của các cụm, cùng 1 đối tượng, nó có
thể được đưa vào cụm này hoặc cụm khác khi dung lượng dữ liệu thay
đổi.
 Điều kiện khởi tạo có ảnh hưởng lớn đến kết quả. Điều kiện khởi tạo khác
nhau có thể cho ra kết quả phân cụm khác nhau.
 Không xác định được mức độ ảnh hưởng của thuộc tính đến q trình tạo
các cụm.
2.5. Cải tiến thuật tốn K-means
Như phần trên, nhóm em đã giới thiệu thuật tốn K-Means, tuy nhiên
thuật tốn có những hạn chế nhất định. Do đó, nhóm em cải tiến thuật toán này
nhằm khắc phục những hạn chế của thuật toán K-means.

12


Nội dung: thay vì chọn số điểm (k) làm trọng tâm, chúng ta không chọn
số điểm (k) làm trọng tâm cho số cụm mà sẽ tăng số cụm từ 1 lên k cụm bằng
cách đưa trung tâm cụm mới vào cụm có mức độ biến dạng lớn nhất và tính lại
trọng tâm các cụm.
Với thuật toán K-means bắt đầu bằng cách chọn k cụm và chọn ngẫu
nhiên k điểm làm trung tâm cụm, hoặc chọn phân hoạch ngẫu nhiên k cụm và
tính trọng tâm của từng cụm này. Việc chọn ngẫu nhiên k điểm làm trung tâm
cụm như đã nói ở trên có thể cho ra các kết quả khác nhau tùy vào chọn k điểm
này.
Thuật toán K-means cải tiến:
Bước 1: Khởi tạo giá trị ban đầu cho K: K=1

Bước 2:
Bước 2.1: Kiểm tra điều kiện K
Nếu K=1: chọn bất kỳ một điểm làm trung tâm của cụm.
Nếu K>1: thêm trung tâm của cụm mới vào cụm có biến dạng max.
Bước 2.2: Gán từng điểm vào cụm có trung tâm gần nhất với điểm đang
xét và cập nhật lại trung tâm cụm.
Bước 2.3: Nếu trung tâm cụm không thay đổi, chuyển sang bước 3.
Ngược lại, quay trở lại bước 2.2 (bước 2).
Bước 3: (Tăng số cụm)
Nếu K≤ giá trị ấn định số cụm thì K:=K+1, quay trở lại bước 2.1 (bước 2).
Ngược lại, thuật toán dừng.
13


Với thuật toán K-means cải tiến: đưa ra sự khác biệt, đó là mức độ biến
dạng của các cụm (dựa trên biến dạng để phân cụm). Mức độ biến dạng
của các cụm được tính như sau:
I=S-N(d(w, x))
Trong đó: w: trung tâm của cụm; N: Số các thành phần trong cụm; S:
Tổng bình phương khoảng cách giữa các thành phần trong cụm và trung
tâm của không gian Euclidean; I: Mức độ biến dạng của cụm; d(w, x): là
khoảng cách giữa trung tâm w của cụm và trung tâm của không gian
Euclidean x.
Nhận xét:
+ Một cụm có mức độ biến dạng lớn thì trung tâm cụm đó có vị trí khơng thích
hợp.
+ Việc xác định các cụm cũng như xác định trung tâm của cụm, như vậy thuật
tốn chủ yếu tìm trung tâm cụm chính xác và xác định lại các thành phần trong
cụm.
Với thuật toán K-means cải tiến:

+ Bước 2: như K-means nhưng khác là: không xác định trước k điểm mà tăng k
lên dần từ 1. Và chọn cụm có mức độ biến dạng lớn để phân ra 2 cụm (khi đó 2
cụm này có mức độ biến dạng giảm, nhỏ hơn).
+ Thuật tốn cải tiến K-means có độ phức tạp là O(k^2*nt), như vậy so với thuật
tốn K-means có độ phức tạp O(tkn) thì: O(k^2*nt)>O(tkn), nhưng vẫn chấp
nhận được, do k<Tuy nhiên ưu điểm của thuật toán là giảm sự phụ thuộc vào việc khởi tạo
các cụm ban đầu nên ta sẽ khơng phải lặp lại thuật tốn với việc chọn các cụm
ban đầu khác nhau để tìm ra kết quả tối ưu như ở K-Means.
14


15


CHƯƠNG III. ỨNG DỤNG THUẬT TOÁN K-MEANS TRONG
PHÂN ĐOẠN ẢNH

3.1. Giới thiệu về phân đoạn ảnh
Phân đoạn ảnh là một thao tác ở mức thấp trong tồn bộ q trình xử lý
ảnh. Quá trình này thực hiện việc phân vùng ảnh thành các vùng rời rạc và đồng
nhất với nhau hay nói cách khác là xác định các biên của các vùng ảnh đó. Các
vùng ảnh đồng nhất này thơng thường sẽ tương ứng với tòan bộ hay từng phần
của các đối tượng thật sự bên trong ảnh. Vì thế, trong hầu hết các ứng dụng của
lĩnh vực xử lý ảnh (image processing), thị giác máy tính, phân đoạn ảnh ln
đóng một vai trị cơ bản và thường là bước tiền xử lý đầu tiên trong tồn bộ q
trình trước khi thực hiện các thao tác khác ở mức cao hơn như nhận dạng đối
tượng, biểu diễn đối tượng, nén ảnh dựa trên đối tượng, hay truy vấn ảnh dựa
vào nội dung …
Vào những thời gian đầu, các phương pháp phân vùng ảnh được đưa ra

chủ yếu làm việc trên các ảnh mức xám do các hạn chế về phương tiện thu thập
và lưu trữ. Ngày nay, cùng với sự phát triển về các phương tiện thu nhận và biểu
diễn ảnh, các ảnh màu đã hầu như thay thế hoàn toàn các ảnh mức xám trong
việc biểu diễn và lưu trữ thông tin do các ưu thế vượt trội hơn hẳn so với ảnh
mức xám. Do đó, các kỹ thuật, thuật giải mới thực hiện việc phân vùng ảnh trên
các loại ảnh màu liên tục được phát triển để đáp ứng các nhu cầu mới. Các thuật
giải, kỹ thuật này thường được phát triển dựa trên nền tảng các thuật giải phân
vùng ảnh mức xám đã có sẵn.
Các hướng tiếp cận phân đoạn ảnh
Phân đoạn ảnh là chia ảnh thành các vùng khơng trùng lắp. Mỗi vùng gồm
một nhóm pixel liên thơng và đồng nhất theo một tiêu chí nào đó. Tiêu chí này
phụ thuộc vào mục tiêu của q trình phân đoạn. Ví dụ như đồng nhất về màu
sắc, mức xám, kết cấu, độ sâu của các layer… Sau khi phân đoạn mỗi pixel chỉ
16


thuộc về một vùng duy nhất. Để đánh giá chất lượng của q trình phân đoạn là
rất khó. Vì vậy trước khi phân đoạn ảnh cần xác định rõ mục tiêu của quá trình
phân đoạn là gì. Xét một cách tổng quát, ta có thể chia các hướng tiếp cận phân
đoạn ảnh thành ba nhóm chính như sau:
 Các kỹ thuật phân đoạn ảnh dựa trên không gian đặc trưng.
 Các kỹ thuật dựa trên không gian ảnh.
 Các kỹ thuật dựa trên các mơ hình vật lý.
3.1.1. Các phương pháp dựa trên không gian đặc trưng
Nếu chúng ta giả định màu sắc bề mặt của các đối tượng trong ảnh là một
thuộc tính bất biến và các màu sắc đó được ánh xạ vào một khơng gian màu nào
đó, vậy thì chúng ta sẽ có một cái nhìn đối với mỗi đối tượng trong ảnh như là
một cụm (cluster) các điểm trong khơng gian màu đó. Mức độ phân tán của các
điểm trong trong một cụm được xác định chủ yếu bởi sự khác biệt về màu sắc.
Một cách khác, thay vì ánh xạ các pixel trong ảnh vào một không gian màu cụ

thể, ta xây dựng một histogram dựa trên các đặc trưng màu dạng ad-hoc cho ảnh
đó (ví dụ như Hue), và thơng thường, các đối tượng trong ảnh sẽ xuất hiện như
các giá trị đỉnh trong histogram đó. Do đó, việc phân vùng các đối tượng trong
ảnh tương ứng với việc xác định các cụm – đối với cách biểu diễn thứ nhất –
hoặc xác định các vùng cực trị của histogram – đối với cách biểu diễn thứ hai.
Các phương pháp tiếp cận này chỉ làm việc trên một không gian màu xác
định chẳng hạn phương pháp của Park áp dụng trên không gian màu RGB, cịn
phương pháp của Weeks và Hague thì áp dụng trên không gian màu HIS. Dựa
trên không gian đặc trưng, ta có các phương pháp phân đoạn: phương pháp phân
nhóm đối tượng không giám sát, phương pháp phân lớp trung bình-k thích nghi,
phương pháp lấy ngưỡng histogram.

17


3.1.2. Các phương pháp dựa trên không gian ảnh
Hầu hết những phương pháp được đề cập trong phần trên đều hoạt động
dựa trên các không gian đặc trưng của ảnh (thơng thường là màu sắc). Do đó,
các vùng ảnh kết quả là đồng nhất tương ứng với các đặc trưng đã chọn cho từng
khơng gian. Tuy nhiên, khơng có gì đảm bảo rằng tất cả các vùng này thể hiển
một sự cô đọng (compactness) về nội dung xét theo ý nghĩa không gian ảnh (ý
nghĩa các vùng theo sự cảm nhận của hệ thần kinh con người). Mà đặc tính này
là quan trọng thứ hai sau đặc tính về sự thuần nhất của các vùng ảnh. Do các
phương pháp gom cụm cũng như xác định ngưỡng histogram đã nêu đều bỏ qua
thơng tin về vị trí của các pixel trong ảnh.
Trong các báo cáo khoa học về phân vùng ảnh mức xám, có khá nhiều kỹ
thuật cố thực hiện việc thoả mãn cùng lúc cả hai tiêu chí về tính đồng nhất trong
khơng gian đặc trưng của ảnh và tính cô đọng về nội dung ảnh. Tuỳ theo các kỹ
thuật mà các thuật giải này áp dụng, chúng được phân thành các nhóm sau:
 Các thuật giải áp dụng kỹ thuật chia và trộn vùng.

 Các thuật giải áp dụng kỹ thuật tăng trưởng vùng.
 Các thuật giải áp dụng lý thuyết đồ thị.
 Các giải thuật áp dụng mạng neural.
 Các giải thuật dựa trên cạnh.
3.1.3. Các phương pháp dựa trên mơ hình vật lý
Tất cả các giải thuật được xem xét qua, khơng ít thì nhiều ở mặt nào đó
đều có khả năng phát sinh việc phân vùng lỗi trong các trường hợp cụ thể nếu
như các đối tượng trong ảnh màu bị ảnh hưởng quá nhiều bởi các vùng sáng
hoặc bóng mờ, các hiện tượng này làm cho các màu đồng nhất trong ảnh thay
18


đổi nhiều hoặc ít một cách đột ngột. Và kết quả là các thuật giải này tạo ra các
kết quả phân vùng quá mức mong muốn so với sự cảm nhận các đối tượng trong
ảnh bằng mắt thường. Để giải quyết vấn đề này, các giải thuật phân vùng ảnh áp
dụng các mơ hình tương tác vật lý giữa bề mặt các đối tượng với ánh sáng đã
được đề xuất. Các cơng cụ tốn học mà các phương pháp này sử dụng thì khơng
khác mấy so với các phương pháp đã trình bày ở trên, điểm khác biệt chính là
việc áp dụng các mơ hình vật lý để minh hoạ các thuộc tính phản chiếu ánh sáng
trên bề mặt màu sắc của các đối tượng.
Cột mốc quan trọng trong lĩnh vực phân vùng ảnh màu dựa trên mơ hình
vật lý được Shafer đặt ra. Ơng giới thiệu mơ hình phản xạ lưỡng sắc cho các vật
chất điện môi không đồng nhất. Dựa trên mơ hình này, Klinker đã đặt ra một
giải thuật đặt ra một số giả thiết quang học liên quan đến màu sắc, bóng sáng,
bóng mờ của các đối tượng và cố gắng làm phù hợp chúng với hình dạng của
các cụm. Hạn chế chính của giải thuật này là nó chỉ làm việc trên các vật chất
điện môi không đồng nhất. Hai ông cùng tên Tsang đã áp dụng mơ hình phản xạ
lưỡng sắc trong khơng gian HSV để xác định các đường biên trong ảnh màu.
Healey đề xuất một mơ hình phản xạ đơn sắccho các vật chất kim loại.
Các phương pháp đề cập trong phần này chỉ áp dụng cho hai loại vật chất là kim

loại và điện mơi khơng đồng nhất. Một thuật tốn tổng quát và phức tạp hơn
cũng được Maxwell và Shafer đề xuất.
3.2. Phát biểu ứng dụng
Thuật toán K-means phân cụm thường được sử dụng trong thị giác máy
tính là một hình thức phân đoạn ảnh thuộc nhóm phương pháp dựa trên không
gian đặc trưng. Các kết quả của các phân đoạn thường được sử dụng để hỗ trợ
phát hiện các đường biên biên và xác định đối tượng. Ứng dụng mẫu sau đây
thực hiện phân đoạn ảnh bằng cách sử dụng các tiêu chuẩn bình phương khoảng

19


cách Euclide trên không gian màu RGB. Các phương thức xác định khoảng cách
tốt hơn để phân đoạn ảnh sẽ khơng được thể hiện trong ví dụ này.
Trong chương trình này có sử dụng thư viện SciPy để đọc hình ảnh. Đây
là một bộ thư viện chuyên dùng trong lĩnh vực thị giác máy tính, trí tuê nhân tạo
– xử lý ảnh, mạng neural, các thuật toán di truyền, máy học, robotics, v.v...
Thuật toán K-means được thực hiện trong thư viện sklearn-cluster. Chương trình
được chạy trên Python 3.7.

Hình 3.1. Ảnh gốc chưa phân đoạn
Dữ liệu cần đưa vào là một tập tin hình ảnh và chọn số cụm cần được
phân chia. Kết quả sau khi xử lý sẽ được hiển thị sau khi chạy chương trình. Kết
quả thực hiện với số cụm lần lượt là 3, 7 và 12 như sau:

20


Hình 3.2. Thực hiện chương trình với số cụm bằng 3 (k = 3)

Hình 3.3. Thực hiện chương trình với số cụm bằng 7 (k=7)

21


Hình 3.4. Thực hiện chương trình với số cụm bằng 12 (k=12)
Kết luận của chương trình
 Phân đoạn ảnh được thực hiện bằng việc sử dụng thuật tốn K-means
trong khơng gian màu RGB hoạt động rất tốt với tất cả các hình ảnh.
 Sự rõ nét trong hình ảnh đã phân đoạn bằng K-means là rất tốt.
 Sự rõ nét của hình ảnh cũng phụ thuộc vào số lượng các cụm (số k)
được sử dụng.
 Một bất lợi của thuật toán này là số lượng cụm là phải được xác định
trong mỗi lần lặp.

22


KẾT LUẬN
Trong tiểu luận này, nhóm đã trình bày tổng quát những kiến thức về học
máy cũng như thuật toán K-Means trong học máy. Từ đó giải quyết được bài
tốn phân đoạn ảnh. Qua đó có thể rút ra kết luậ dù thuật toán K-Means đơn
giản, dễ sử dụng hơn nhưng độ chính xác của thuật tốn K-Means khơng vì thế
mà thấp hơn các thuật toán phức tạp khác mà còn cao hơn, kết quả thực nhiệm
đã cho thấy điều đó. Kết quả chúng ta vừa xem trên đây chưa phải là kết quả tối
ưu, nhưng hy vọng rằng đây sẽ là một bước khởi đầu thuận lợi làm tiền đề
nghiên cứu để thực hiện những chương trình phân loại mã độc tốt hơn nữa trong
tương lai.
Việc nghiên cứu đề tài phân đoạn ảnh không chỉ dừng ở mức độ trong một
tiểu luận, nhóm em sẽ tìm hiểu và tiếp tục nghiên cứu sâu hơn các thuật toán

khác để kết hợp cải tiến thuật toán K-Means nhằm đem lại hiệu suất cao nhất có
thể và mở rộng nghiên cứu để tối ưu được kết quả.

23


TÀI LIỆU THAM KHẢO
[1] Bài giảng môn học “Máy học” (2014) Giảng viên: PGS.TS Vũ Thanh
Nguyên.
[2] Kiri Wagsta, Claire Cardie, Seth Rogers, Stefan Schroedl (2001)
“Constrained K-means Clustering with Background Knowledge”.
[3] “K-means clustering” From Wikipedia.
[4] R. Rojas: Neural Networks, Springer-Verlag, Berlin (1996), “Unsupervised
Learning and ClusteringAlgorithms” pp 101 – 120.
[5] “K-means clustering” from
[6]
[7] a

24