TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN
KHOA CÔNG NGHỆ THÔNG TIN PHẠM TRỌNG NGHĨA
KẾT HỢP ĐA ĐẶC TRƯNG TRONG MÔ HÌNH
CRFs CHO BÀI TOÁN PHÂN ĐOẠN ẢNH
THEO ĐỐI TƯỢNG NGÀNH: KHOA HỌC MÁY TÍNH
Mã số: 60.48.01
LUẬN VĂN THẠC SỸ NGƢỜI HƢỚNG DẪN KHOA HỌC
PGS. T.S LÊ HOÀI BẮC
Thành phố Hồ Chí Minh - 2010 II
Danh sách các bảng VIII
TÓM TẮT LUẬN VĂN IX
Danh mục chữ viết tắt: XI
Chƣơng 1: MỞ ĐẦU 1
1.1. Giới thiệu lĩnh vực và ý nghĩa của đề tài 1
1.1.1. Dẫn nhập 1
1.1.2. Lĩnh vực nghiên cứu của đề tài 3
1.1.3. Ý nghĩa lý luận và thực tiễn: 4
1.2. Các kết quả nghiên cứu liên quan 6
1.3. Phƣơng pháp giải quyết đề xuất. 8
1.4. Cấu trúc luận văn 10
Chƣơng 2: TRƢỜNG NGẪU NHIÊN CÓ ĐIỀU KIỆN VÀ CỰC TIỂU HOÁ
NĂNG LƢỢNG BẰNG GRAPH-CUT 13
2.1. Trƣờng ngẫu nhiên có điều kiện 13
2.2. Cực tiểu hoá năng lƣợng 15
2.2.1. Tổng quan về cực tiểu hoá năng lƣợng 15
2.2.2. Cực tiểu hoá năng lƣợng bằng phƣơng pháp graph cut. 16
Chƣơng 3: Mô hình CRFs cho bài toán phân đoạn ảnh theo đối tƣợng. 24
3.1. Thế năng vân-bố cục 26
3.1.1. Texton hoá ảnh 27 IV
3.1.2. Bộ lọc vân-bố cục 30
3.1.3. Thuật toán Joint Boosting 33
3.2. Thế năng màu sắc 36
3.3. Thế năng vị trí: 38
3.4. Mô hình CRF mức cao: 39
3.4.1. Phân đoạn ảnh không giám sát 39
Hình 1-2 – Ví dụ về bài toán nhận dạng đối tƣợng. Sử dụng thuật toán trong [28] 2
Hình 1-3. Ví dụ về bài toán phân đoạn ảnh theo đối tƣợng. Hàng trên là ảnh đầu
vào. Hàng dƣới là các ảnh kết quả với các màu sắc biểu diễn các đối tƣợng khác
nhau. 3
Hình 1-4. Chƣơng trình cắt dán ảnh tự động [4] 4
Hình 1-5. Chƣơng trình tổng hợp thông tin ngữ nghĩa. 5
Hình 1-6. Chƣơng trình biên tập ảnh. Bên trái: sau khi có kết quả phân đoạn ảnh,
ngƣời dùng chọn ngƣời, thực đơn ngữ cảnh xuất hiện, xác định đây là vùng ngƣời.
Bên phải: kết quả khi ngƣời dùng nhấn nút xoá. Vùng ảnh chứa ngƣời bị xoá [15] 5
Hình 1-7. Mô hình chung của hệ thống phân đoạn ảnh theo đối tƣợng dùng trong
luận văn 10
Hình 2-1: Ví dụ về mô hình CRF đôi định nghĩa trên các biến ngẫu nhiên
, Mô hình bao gồm các thế năng đơn phân cho từng biến
và các thế năng liên kết giữa các biến kề nhau trong đó
. Đồ thị factor thể hiện các biến liên quan trong từng
thành phần. 14
Hình 2-2. Ví dụ về đồ thị (a) và đƣờng cắt (b). Các cạnh nối giữa hai đỉnh đầu cuối
với các pixel (màu đỏ và xanh) thể hiện thế năng đơn phân. Các cạnh nối giữa các
pixel (màu vàng) thể hiện thế năng liên kết. Một đƣờng cắt sẽ chia tập các pixel ra
làm 2 phần, tƣơng ứng với việc gán nhãn nhị phân. 17
Hình 2-3. Ví dụ đơn giản về phân đoạn ảnh 2D cho ảnh 3x3. Trọng số của các cạnh
thể hiện bằng độ dày của cạnh đó trong hình. Đầu tiên ảnh (a) sẽ đƣợc chuyển thành
đồ thị tƣơng ứng (b), việc tìm ra đƣờng cắt tối thiểu (c) tƣơng ứng với sự phân đoạn
ảnh tốt nhất (d). [38] 18
Hình 2-4. Ví dụ về bƣớc di chuyển. (a) Nhãn ban đầu. (b) “bƣớc di chuyển đơn” sẽ
thay đổi nhãn của một pixel (đánh dấu tròn). (c) “hoán đổi alpha-beta” thay đổi một VI
VII
Hình 4-1. Bộ dữ liệu MSRC. Cột a-d là một số ảnh trong bộ dữ liệu. Cột e là ảnh đã
gán nhãn sẵn của các ảnh trong cột d. 44
Hình 4-2. Kết quả thí nghiệm hiệu năng của đặc trƣng vân – bố cục với các kích
thƣớc từ điển texton khác nhau. 45
Hình 4-3. Một số kết quả trên tập dữ liệu MSRC. Các cột lần lƣợt từ trái qua phải:
ảnh đầu vào, ảnh kết quả dùng đặc trƣng vân-bố cục, kết quả dùng thế năng đơn
phân, ảnh kết quả dùng mô hình CRF đôi, ảnh groundtruth. 47
Hình 4-4. Một số kết quả trên tập dữ liệu MSRC. Các cột lần lƣợt từ trái qua phải:
ảnh đầu vào, ảnh kết quả dùng mô hình CRFs đôi, kết quả mô hình CRFs mức cao
với tiền phân đoạn ảnh dùng thuật toán superpixel, kết quả dùng mô hình CRF mức
cao với tiền phân đoạn ảnh dùng thuật toán mean-shift, ảnh groundtruth. 48
Hình 4-5. Minh họa kết quả phân đoạn ảnh khi áp dụng hai thuật toán superpixel và
meanshift lên ảnh đầu vào và ảnh kết quả của mô hình CRFs mức cao. Lần lƣợt từ
trái qua phải: ảnh đầu vào, kết quả phân đoạn ảnh đầu vào dùng superpixel, kết quả
phân đoạn ảnh kết quả dùng superpixel, kết quả phân đoạn ảnh đầu vào dùng mean-
shift, kết quả phân đoạn ảnh kết quả dùng mean-shift. 49
Hình 4-6. Confusion matrix thể hiện kết quả của mô hình CRFs mức cao (mean-
shift) 51
Hình 4-7. Một số hình ảnh trong tập MSRC về đối tƣợng “bird”. 51
VIII
Danh sách các bảng
Bảng 2-1.Trọng số các cạnh trong đồ thị mở rộng alpha. 23
2
Các nghiên cứu thuần về nhận dạng đối tượng tập trung vào việc xác định xem
trong bức ảnh cho trƣớc có những đối tƣợng nào bằng cách đặt các ô hình chữ nhật
xung quanh đối tƣợng cần nhận dạng.
Hình 1-2 – Ví dụ về bài toán nhận dạng đối tƣợng. Sử dụng thuật toán trong [28]
Bài toán phân đoạn ảnh chỉ quan tâm đến việc phân chia ảnh thành các vùng khác
nhau mà không quan tâm đến ngữ nghĩa của từng vùng. Trong khi đó, bài toán nhận
dạng đối tƣợng chỉ ra đƣợc các đối tƣợng có trong hình, nhƣng lại không chính xác
đến từng pixel nhƣ trong bài toán phân đoạn ảnh mà chủ yếu xác định đối tƣợng
bằng một khung hình chữ nhật. Do đó, nhu cầu kết hợp hai bài toán này nhằm tận
dụng ƣu điểm của cả hai là rất cần thiết. Bài toán kết hợp hai vấn đề trên gọi là bài
toán phân đoạn ảnh theo đối tượng (object segmentation).
Cụ thể hơn, cho trƣớc một bức ảnh, thuật toán phân đoạn ảnh theo đối tƣợng sẽ tự
động phân tách nó ra thành các vùng khác nhau và xác định ngữ nghĩa của từng
vùng. Bài toán này còn đƣợc gọi là bài toán gán nhãn ảnh đa lớp (multi-class image
labeling) do việc phân đoạn ảnh tƣơng đƣơng với việc gán nhãn cho tất cả các pixel
trong ảnh. Giá trị nhãn của các pixel sẽ xác định lớp đối tƣợng mà pixel đó thuộc về
(xem hình 1-3). Sự phân đoạn ảnh đƣợc thể hiện bằng các đƣờng biên giữa các
vùng có nhãn khác nhau. Ví dụ, xem xét một bức ảnh chụp tại một thảo nguyên,
thuật toán sẽ gán cho các pixel một số nhãn nhƣ: cỏ, thú, nƣớc, bầu trời.
Lƣu ý rằng, khác với thuật toán phân đoạn ảnh thông thƣờng, các thuật toán phân
đoạn ảnh theo đối tƣợng đòi hỏi quá trình huấn luyện để rút ra mô hình cho các lớp
cần gán nhãn. Khái niệm “đối tƣợng” ở đây đƣợc hiểu nhƣ một tập hợp các pixel
Tự động cắt dán ảnh: nhận vào một tập hợp các ảnh, chƣơng trình sẽ tự động cắt
dán ảnh để tạo thành một bức ảnh tổng hợp lạ mắt [4].
Hình 1-4. Chƣơng trình cắt dán ảnh tự động [4]
Tổng hợp ảnh ngữ nghĩa: Trong [19] ngƣời dùng sẽ cung cấp một số nhãn (cây,
đƣờng, bầu trời) và vị trí của nó. Chƣơng trình sẽ tự động tìm trong cơ sở dữ liệu
các bức ảnh phù hợp với yêu cầu. Sau đó một bức ảnh mới sẽ đƣợc tạo thành từ các
ảnh này với thành phần ảnh đã cung cấp. 5 Hình 1-5. Chƣơng trình tổng hợp thông tin ngữ nghĩa.
Biên tập hình ảnh: kết quả của quá trình phân đoạn ảnh theo đối tƣợng cho phép
phần mềm biên tập ảnh xử lý tiếp [15]. Chẳng hạn nhƣ tăng độ sáng của bầu trời.
Hay xóa vùng chứa ngƣời nhƣ trong hình 1-6.
Hình 1-6. Chƣơng trình biên tập ảnh. Bên trái: sau khi có kết quả phân đoạn ảnh,
ngƣời dùng chọn ngƣời, thực đơn ngữ cảnh xuất hiện, xác định đây là vùng ngƣời.
Bên phải: kết quả khi ngƣời dùng nhấn nút xoá. Vùng ảnh chứa ngƣời bị xoá [15] 6
1.2. Các kết quả nghiên cứu liên quan
Nhƣ vậy, trong phần đầu của chƣơng, luận văn đã giới thiệu sơ lƣợc về bài toán
phân đoạn ảnh theo đối tƣợng. Phần tiếp theo của luận văn sẽ trình bày một số kế
quả nghiên cứu có liên quan đến bài toán mà luận văn đang giải quyết.
Cả hai bài toán nhận dạng đối tƣợng và phân đoạn ảnh đều là bài toán kinh điển
thƣờng để tăng độ chính xác.
Đặc trưng cục bộ là phần hầu nhƣ không thể thiếu đối với bất kỳ bài toán phân đoạn
ảnh nào. Đặc trƣng cục bộ sẽ mô tả các thông tin về màu sắc, độ sáng, hƣớng,… của
một pixel hay một vùng pixel. Hai loại đặc trƣng thƣờng đƣợc dùng phổ biến là
SIFT [7] và Texton [13]
Tuy nhiên nhƣ đã nói bên trên, trong bài toán phân đoạn ảnh theo đối tƣợng đặc
trƣng cục bộ không đủ để đƣa ra một kết quả tốt. Điều này là do nhiều đối tƣợng
đƣợc tạo thành từ những bộ phận có vẻ ngoài không giống nhau (chẳng hạn nhƣ đối
với đối tƣợng xe hơi thì kính và bánh xe sẽ có màu khác với màu sơn). Do đó, ngoài
đặc trƣng cục bộ, cần phải thêm thông tin ngữ cảnh để có thể phân đoạn theo đối
tƣợng đƣợc tốt.
Một trong những thông tin ngữ cảnh đáng lƣu ý là mối quan hệ không gian giữa các
đối tƣợng [10] [26] [34]. Ví dụ nhƣ khi một vùng đƣợc xác định là “tree”, thì nhiều
khả năng vùng đó sẽ nằm dƣới vùng “sky” và nằm trên vùng “grass”.
Thông tin về hình dạng đối tƣợng, hay thông tin về vị trí tƣơng đối giữa các thành
phần của một đối tƣợng cũng là một loại thông tin ngữ cảnh đáng quan tâm. Đã
đƣợc chứng minh tính hiệu quả trong [11][17]
Mô hình
Có nhiều cách để kết hợp các loại đặc trƣng với nhau. Trong số đó, một trong
những mô hình hiệu quả nhất cho bài toán này là mô hình trường ngẫu nhiên có
điều kiện (Conditonal Random Fields - CRFs) [18] đã đƣợc sử dụng trong rất nhiều
công trình nhƣ [10] [11] [26] [27][28]. Mô hình CRFs là hƣớng tiếp cận phổ biến vì
nó có nhiều ƣu điểm nhƣ: 8
Có khả năng mô hình hóa xác suất có điều kiện
Có khả năng kết hợp nhiều loại đặc trƣng khác nhau.
Đƣợc giải quyết bằng các phƣơng pháp dựa trên graph-cut vô cùng
trƣng này đƣợc tính bằng mô hình hỗn hợp Gaussian (Gaussian Mixture model
– GMM)
- Đặc trưng vị trí: mô hình hoá vị trí tƣơng đối của các đối tƣợng trong ảnh.
Tuy nhiên, phƣơng pháp trên chỉ tập trung vào rút trích đặc trƣng trên từng pixel mà
bỏ qua nguồn thông tin dồi dào từng các thuật toán phân đoạn ảnh không giám sát
vốn có thông tin về đƣờng biên giữa các đối tƣợng khá chính xác. Do đó, luận văn
sẽ đƣa thêm thông tin này vào mô hình theo cách tƣơng tự nhƣ trong [24].
Đóng góp của luận văn do đó gồm:
Xây dựng đặc trƣng vân – bố cục: đặc trƣng có khả năng nắm bắt thông tin
về vân ảnh, thông tin ngữ cảnh xung quanh đối tƣợng, thông tin bố cục của
các thành phần trong ảnh.
Áp dụng thông tin tiền phân đoạn ảnh vào mô hình CRFs truyền thống để
nâng cao hiệu năng phân đoạn.
Mô hình chung của hệ thống đƣợc tóm tắt qua hình 1-7. Các chƣơng còn lại, đặc
biệt là chƣơng 3, sẽ giải thích rõ hơn các thành phần trong mô hình này. 10 Hình 1-7. Mô hình chung của hệ thống phân đoạn ảnh theo đối tƣợng dùng trong
luận văn
1.4. Cấu trúc luận văn
Luận văn gồm 5 chƣơng:
Chƣơng 1 MỞ ĐẦU: Trong chƣơng mở đầu này, luận văn đã giới thiệu tổng
quan về bài toán phân đoạn ảnh theo đối tƣợng cùng với sự liên quan với hai bài
toán truyền thống: phân đoạn ảnh và nhận dạng đối tƣợng. Tiếp theo luận văn đã
trình bày những thách thức, khó khăn trong bài toán phân đoạn ảnh theo đối tƣợng,
những thách thức này chủ yếu là do sự đa dạng về màu sắc, hình dạng, và ngoại
cảnh của các đối tƣợng. Luận văn cũng giới thiệu đƣợc các hƣớng nguyên cứu có
phân đoạn ảnh không giám sát dù không xác định đƣợc ngữ nghĩa của từng vùng,
nhƣng lại cho ra các phân đoạn ảnh có đƣờng biên khá chính xác.
Chƣơng 4 KẾT QUẢ THỰC NGHIỆM: Trong chƣơng này, luận văn thử
nghiệm hai mô hình đã trình bày ở chƣơng 3 với các loại đặc trƣng khác nhau. Qua
các thử nghiệm, luận văn đã chứng tỏ rằng dù kết quả ban đầu chƣa bằng một thuật 12
toán kinh điển đƣợc chọn làm baseline, nhƣng với việc kết hợp các đặc trƣng một
các hợp lý trong mô hình CRFs đôi cho ra kết quả tốt hơn hẳn. Ngoài ra, các thử
nghiệm cũng chứng minh đƣợc ƣu điểm của mô hình CRFs mức cao với việc hiệu
năng và cảm nhận thị giác đƣợc cải thiện rõ rệt. Đặc biệt, mô hình CRFs mức cao
đã đạt đƣợc hiệu năng tƣơng đƣơng với kết quả “state of the art” hiện nay.
Chƣơng 5 KẾT LUẬN: Trong chƣơng cuối cùng này, luận văn sẽ tóm tắt lại
những luận điểm đã nêu ở các chƣơng trƣớc, các kết quả đã đạt đƣợc, cũng nhƣ
những đóng góp của luận văn. Mặt khác, những định hƣớng nhằm phát triển, hoàn
thiện mô hình trong luận văn cũng đƣợc thảo luận và đề xuất trong chƣơng này. 13
Chƣơng 2: TRƢỜNG NGẪU NHIÊN CÓ ĐIỀU KIỆN
VÀ CỰC TIỂU HOÁ NĂNG LƢỢNG BẰNG
GRAPH-CUT
2.1. Trƣờng ngẫu nhiên có điều kiện
Trường ngẫu nhiên có điều kiện (Conditional random fields - CRFs) là một mô hình
(2.1)
Trong đó, từng thành phần
(2.2)
Thành phần
là một hằng số dùng để chuẩn hoá kết quả, bảo đảm rằng tổng của
các phân bố xác suất là 1. Do đó:
. Đồ thị factor thể hiện các biến liên quan trong
từng thành phần.
Hàm năng lƣợng của ví dụ này là:
là tập các cạnh. 15
Để xác định cách gán nhãn tốt nhất, cần phải tìm ra xác suất hậu nghiệm tối đa
(maximum a posteriori - MAP) của việc gán biến ngẫu nhiên Y. Điều này tƣơng
đƣơng với tối thiểu hoá hàm năng lƣợng:
(3.1)
Trong đó, tập tƣơng ứng với tập các pixel,
là nhãn của pixel , là tập
hợp gồm tất cả các pixel láng giềng.
là hàm thế năng đơn phân (unary
potential) và
là hàm thế năng liên kết (pairwise potential). Hàm năng lƣợng
này thƣờng đƣợc rút ra trong ngữ cảnh của trƣờng ngẫu nhiên có điều kiện. Giá trị
cực tiểu của hàm năng lƣợng tƣơng ứng với xác suất hậu nghiệm tối đa của việc
gán nhãn x, tƣơng ứng với phân đoạn ảnh tốt nhất.
Hàm năng lƣợng thƣờng mô hình hoá tính chất toàn cục nào đó của bức ảnh mà tính
chất này không thể mô tả đƣợc bằng các tƣơng quan cục bộ. Vấn đề là trong trƣờng
hợp tổng quát việc cực tiểu hoá hàm năng lƣợng E có độ phức tạp ngoài đa thức
(NP-hard problem). Do sự phức tạp của việc tìm ra lời giải tối ƣu toàn cục, các nhà
nghiên cứu tập trung vào các thuật toán xấp xỉ để tìm ra một lời giải “gần tối ƣu”.
Hai hƣớng tiếp cận chính là graph-cut và message passing.
Một số công trình tiêu biểu theo hƣớng message passing có thể kể đến [14]
[20][31]. Hƣớng tiếp cận này có ƣu điểm là mang tính tổng quát cao, tuy nhiên nó 16
có một số khuyết điểm. Thứ nhất, nó thƣờng tìm ra lời giải có năng lƣợng cao hơn
Copyright: Tài liệu đại học ©