Số hóa bởi Trung tâm Học liệu

ĐẠI HỌC THÁI NGUYÊN
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG

Hà Minh Hải

MỘT SỐ KỸ THUẬT GÁN NHÃN ĐỐI TƢỢNG
TRONG ẢNH VÀ ỨNG DỤNG

LUẬN VĂN THẠC SỸ Thái Nguyên – 2014


Số hóa bởi Trung tâm Học liệu

LỜI CAM ĐOAN
Tôi xin cam đoan toàn bộ nội dung bản luận văn này là do tôi tự sƣu
tầm, tra cứu và sắp xếp cho phù hợp với nội dung yêu cầu của đề tài.
Nội dung luận văn này chƣa từng đƣợc công bố hay xuất bản dƣới bất
kỳ hình thức nào và cũng không sao chép từ bất kỳ một công trình nghiên cứu
nào.
Tất cả phần mã nguồn của chƣơng trình đều do tôi tự thiết kế và xây
dựng, trong đó có sử dụng một số thƣ viện chuẩn và các thuật toán đƣợc các
tác giả xuất bản công khai và miễn phí trên mạng Internet.
Nếu sai tôi xin hoàn toàn chịu trách nhiệm.

Thái Nguyên, ngày 20 tháng 05 năm 2014
Học viên thực hiện Hà Minh Hải

Số hóa bởi Trung tâm Học liệu LỜI CẢM ƠN
Trong suốt thời gian học tập và nghiên cứu tại lớp cao học K11C

1.1.1. Xử lý ảnh là gì? 6
1.1.2. Các giai đoạn chính trong xử lý ảnh 6
1.1.3. Một số vấn đề cơ bản trong xử lý ảnh 9
1.2. Tổng quan về bài toán gán nhãn 11
1.2.1. Giới thiệu bài toán 11
1.2.2. Mô tả bài toán gán nhãn cho đối tƣợng 12
Chƣơng 2 MỘT SỐ KỸ THUẬT TÍNH TOÁN VÀ HIỂN THỊ NHÃN
ĐỐI TƢỢNG 17
2.1. Kỹ thuật GFLP (Graphical Feature Label Placement) 18
2.1.1. Giới thiệu 18
2.1.2. Khái quát thuật toán 19
2.2. Kỹ thuật ELP (Edge Label Placement) 24
2.2.1. Giới thiệu 24
2.2.2. Thuật toán Fast ELP 25
2.3. Kỹ thuật NLP (Node Label Placement) 33
2.4. Kỹ thuật MLP (Multiple Label Placement) 34
2.4.1. Giới thiệu 34
ii

Số hóa bởi Trung tâm Học liệu

2.4.2. Thuật toán Iterative 39
2.4.3. Thuật toán Flow-based 42
2.5. Kỹ thuật gán nhãn dựa vào hiệu chỉnh đối tƣợng 46
Chƣơng 3 CÀI ĐẶT CHƢƠNG TRÌNH ỨNG DỤNG 48
3.1. Bài toán 48
3.2. Chƣơng trình 48
3.3. Kết quả thực nghiệm 49
KẾT LUẬN 51
TÀI LIỆU THAM KHẢO 53

Hình 1.4. (a) Gán nhãn đúng. (b) Gán nhãn gây hiểu nhầm. 15
Hình 2.1. Bản vẽ hƣớng nơi nhãn đƣợc định vị bằng các kỹ thuật phù hợp cho
kỹ thuật GFLP. Các nhãn đƣợc đặt song song với trục ngang. Hộp màu xám
là nút nhãn và hộp trắng cạnh nhãn. 20
Hình 2.2. Vị trí nhãn có thể cho một điểm. 21
Hình 2.3. Một đồ thị với vị trí nhãn đƣợc gán cho mỗi cạnh của bản vẽ. 22
Hình 2.4. Khả năng gán các nhãn của hình vẽ 26
Hình 2.5. (a) Một bản vẽ đơn giản với các vị trí nhãn cho mỗi cạnh. (b) Các
đồ thị phù hợp tƣơng ứng. 27
Hình 2.7. Kết quả gán nhãn cạnh cho một bản vẽ trực giao có nhiều cạnh
nằm ngang, áp dụng Fast ELP. Hình đƣợc lấy trong [11] 31
Hình 2.8. Bản vẽ hình tròn với các nhãn cạnh, nơi nhãn đƣợc phép chồng lên
các đối tƣợng hình khác, đƣợc sản xuất bằng kỹ thuật ELP 32
Hình 2.9. (a) Phân nhãn thích hợp hơn. (b) Đặt nhãn gây hiểu nhầm. (c) Xác
định ràng buộc khoảng cách chặt chẽ. (d) Xác định ràng buộc tự do 36
Hình 2.10. (a) Gán nhãn thích hợp hơn. (b) Việc gán nhãn chấp nhận đƣợc.
(c) Việc gán nhãn gây hiểu nhầm 38
v

Số hóa bởi Trung tâm Học liệu

Hình 2.12. Một bản vẽ phân cấp với vị trí hai nhãn mỗi cạnh sự dụng thuật
toán Iterative 41
Hình 2.13. Đồ thị Flowbased 42
Hình 2.14. Bản vẽ với vị trí hai nhãn mỗi cạnh bởi thuật toán Flow-based 44
Hình 2.15. Một bản vẽ vòng tròn với ba nhãn cho mỗi cạnh và nút đƣợc định
vị bằng thuật toán Flow-based trên. Các ô màu trắng là các nhãn cạnh và các
hộp đen là nút nhãn 45
Hình 3.1. Hình ảnh sau khi gán nhãn cho bản đồ trƣờng Cao đẳng Công
nghiệp và Xây dựng ở chể độ phóng to ảnh 49

những ứng dụng của bài toán này, học viên đã quyết định lựa chọn đề tài:

1
“Label placement is a source of many geometric optimization problems. Even when labels are to be placed
in fixed positions relative to point features these are typically NP-hard. Since maps do need labels, heuristics
and efficient algorithms for identifying constraints and possible positions are needed.” – Application
Challenges to Computational Geometry, CG Impact Task Force Report, pp. 18.
2

Số hóa bởi Trung tâm Học liệu

“MỘT SỐ KỸ THUẬT GÁN NHÃN ĐỐI TƢỢNG TRONG ẢNH VÀ
ỨNG DỤNG”, bởi đây là một đề tài có mang tính thực tiễn cao và đồng thời
mở ra nhiều hƣớng phát triển nghiên cứu.
2. Lịch sử nghiên cứu
Tài liệu đầu tiên có liên quan tới bài toán gán nhãn có thể là một bản đồ
địa lí, do bản đồ luôn bao gồm hai yếu tố hình vẽ và chữ viết. Bằng chứng đầu
tiên là một tấm bản đồ ƣớc chừng khoảng 2300 năm trƣớc, với tỉ lệ xích
1
500

của vùng ngày nay là miền nam thị trấn Heibei ở Trung Quốc. Bài báo đầu
tiên về bài toán gán nhãn đƣợc công bố năm 1962 bởi Eduard Imhof [4],
ngƣời đã đặt ra các nguyên tắc cho chất lƣợng của bản đồ. Trƣớc đó, những
ngƣời vẽ bản đồ đánh giá chất lƣợng một tấm bản đồ đƣợc gán nhãn tốt hay
không tốt hoàn toàn chỉ dựa vào kinh nghiệm. Mƣời năm sau, Pinhas Yoeli
lần đầu tiên thử xây dựng một hệ thống gán nhãn tự động [11]. Trong khoảng
gần hai thập kỉ sau đó, có rất ít nghiên cứu về bài toán gán nhãn tự động.
Tuy nhiên vào đầu những thập niên 80, lƣợng nghiên cứu về lĩnh vực
gán nhãn tự động tăng đáng kể, thể hiện qua số lƣợng các bài báo đã đƣợc

Feature Label Placement), một tập hợp các điểm (NLP: Node Label
Placement), gán nhãn cho một tập hợp các đƣờng hoặc cạnh (ELP: Edge
Label Placement), nhiều nhãn trên mỗi đối tƣợng (MLP: Multiple Label
Placement) và kỹ thuật gán nhãn dựa vào hiệu chỉnh đối tƣợng.
Chƣơng 3: Chƣơng trình
4

Số hóa bởi Trung tâm Học liệu

Ở đây, tôi sẽ cài đặt theo thuật toán đƣợc trình bày trong chƣơng 2 tìm
vị trí thích hợp nhất khi phóng to và thu nhỏ ảnh để hiển thị nhãn tối đa cho
các đối tƣợng trong một bức ảnh.
5

Số hóa bởi Trung tâm Học liệu

Chƣơng 1
KHÁI QUÁT VỀ XỬ LÝ ẢNH VÀ BÀI TOÁN GÁN NHÃN ĐỐI TƢỢNG
Trong ngành khoa học máy tính, xử lý ảnh là một dạng của xử lý tín
hiệu cho đầu vào là một ảnh hoặc các frame của phim ảnh. Đầu ra có thể là
một hình ảnh, hoặc tập hợp các ký tự hoặc các tham số liên quan tới hình ảnh.
Thƣờng thì kỹ thuật xử lý ảnh có liên quan tới xử lý tín hiệu hai chiều và
đƣợc áp dụng bằng một chuẩn riêng về kỹ thuật xử lý ảnh cho nó. Các khái
niệm cơ bản để xử lý tín hiệu nhƣ, khái niệm về tích chập, các biến đổi
Fourier, biến đổi Laplace, các bộ lọc hữu hạn,… Ngoài ra còn cần tới các
công cụ toán học nhƣ đại số tuyến tính, thống kê. Và một số kiến thức cần
thiết nhƣ trí tuệ nhân tao, mạng nơron nhân tạo cũng đƣợc đề cập trong quá
trình phân tích và xử lý ảnh.
1.1. Khái quát về xử lý ảnh
Cũng nhƣ xử lý dữ liệu bằng đồ hoạ, xử lý ảnh là một lĩnh vực của tin

vai trò quan trọng nhất. Những năm trở lại đây với sự phát triển của phần
cứng máy tính, xử lý ảnh và đồ hoạ đó phát triển một cách mạnh mẽ và có
nhiều ứng dụng trong cuộc sống. Xử lý ảnh và đồ hoạ đóng một vai trò quan
trọng trong tƣơng tác ngƣời máy.
Xử lý ả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. 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
1.1.2. Các giai đoạn chính trong xử lý ảnh
Giai đoạn xử lý ảnh đƣợc mô tả bằng sơ đồ sau:
Ảnh đầu vào

XỬ LÝ ẢNH

Ảnh “Tốt hơn”

Kết luận

7

Số hóa bởi Trung tâm Học liệu Hình 1.2. Quá trình xử lý ảnh
 Thu nhận ảnh: Đây là công đoạn đầu tiên mang tính quyết định đối với
quá trình xử lý ảnh. Ảnh đầu vào sẽ đƣợc thu nhận qua các thiết bị nhƣ
camera, sensor, máy quét, vv… và sau đó các tín hiệu này sẽ đƣợc số
hóa. Các thông số quan trọng ở bƣớc này là độ phân giải, chất lƣợng
màu, dung lƣợng bộ nhớ và tốc độ thu nhận ảnh của các thiết bị.

thích hợp hơn cho việc xử lý trong máy tính là rất cần thiết. Để chuyển
đổi chúng, câu hỏi đầu tiên cần phải trả lời 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 chủ yếu đế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 hay cấu trúc
xƣơng của nó. Sự chọn lựa cách biểu diễn thích hợp cho một vùng ảnh
chỉ mới là một phần trong việc chuyển đổi dữ liệu ảnh thô sang một
dạng thích hợp hơn cho những xử lý về sau. Chúng ta còn phải đƣa ra
một phƣơng pháp mô tả dữ liệu đã đƣợc chuyển đổi đó sao cho những
tính chất cần quan tâm đến sẽ đƣợc làm nổi bật lên, thuận tiện cho việc
xử lý chúng.
 Nhận dạng và giải thích: Đây là bƣớc cuối cùng trong quá trình xử lý
ảnh. Nhận dạng ảnh có thể đƣợc nhìn nhận một cách đơn giản là việc
gán nhãn cho các đối tƣợng trong ảnh. Giải thích là công đoạn gán
nghĩa cho một tập các đối tƣợng đã đƣợc nhận biết.
Chúng ta có thể thấy rằng, không phải bất kỳ một ứng dụng xử lý ảnh
nào cũng bắt buộc phải tuân theo các bƣớc xử lý đã nêu ở trên, ví dụ nhƣ các
ứng dụng chỉnh sửa ảnh nghệ thuật chỉ dừng lại ở bƣớc tiền xử lý. Một cách
tổng quát thì những chức năng xử lý bao gồm cả nhận dạng và giải thích
9

Số hóa bởi Trung tâm Học liệu

thƣờng chỉ có mặt trong hệ thống phân tích ảnh tự động hoặc bán tự động,
đƣợc dùng để rút trích ra những thông tin quan trọng từ ảnh, ví dụ nhƣ các
ứng dụng nhận dạng kí tự quang học, nhận dạng chữ viết tay vv…
1.1.3. Một số vấn đề cơ bản trong xử lý ảnh

8 láng giềng của (x,y) là một tập cha của 4 láng giềng và bao gồm láng giềng
ngang, dọc và chéo:
N
8
((x,y)) = N
4
((x,y)) {(x+1,y+1), (x-1,y-1), (x+1,y-1), (x-1,y+1)} (1.2)

1.1.3.5. Vùng liên thông
Một vùng R đƣợc gọi là liên thông nếu bất kỳ hai điểm (x
A
,y
A
) và
(x
B
,y
B
) thuộc vào R có thể đƣợc nối bởi một đƣờng (x
A
,y
B
) (x
i-1
,y
i-1
), (x
i
,y
i

k
) đƣợc gọi là kề với điểm (x
l
,y
l
) nếu (x
l
,y
l
) thuộc vào láng
giềng trực tiếp của (x
k
,y
k
).
1.1.3.6. Biểu diễn ảnh
Trong biểu diễn ảnh, ngƣời ta dùng các phần tử đặc trƣng của ảnh là
pixel. Có thể xem một hàm hai biến chứa các thông tin nhƣ biểu diễn của ảnh,
việc xử lý ảnh số yêu cầu ảnh phải đƣợc mã hóa và lƣợng tử hóa. Việc lƣợng
tử hóa ảnh là chuyển đổi tín hiệu tƣơng tự sang tín hiệu số của một ảnh đã lấy
mẫu sang một số hữu hạn mức xám.
Một số mô hình thƣờng đƣợc dùng trong xử lý ảnh, mô hình toán, mô hình
thống kê.
1.1.3.7. Tăng cường và khôi phục ảnh
Tăng cƣờng ảnh là bƣớc quan trọng tạo tiền đề cho xử lý ảnh, gồm một
loạt các kỹ thuật nhƣ: lọc độ tƣơng phản, khử nhiễu, nổi màu…
11

Số hóa bởi Trung tâm Học liệu


một vị trí tốt để gán nhãn do những vị trí này còn phụ thuộc vào cảm nhận của
con ngƣời nhƣ trực giác và kinh nghiệm , đặc biệt là khi những cảm giác,
kinh nghiệm này đƣợc hoàn thiện qua nhiều thế kỷ bởi những nhà vẽ bản đồ
và đƣợc họ nâng lên thành một nghệ thuật. Vì vậy các vị trí nhãn do các hệ
thống máy tính cung cấp khó có thể có chất lƣợng tƣơng đƣơng so với làm
thủ công bởi những ngƣời làm bản đồ có kinh nghiệm. Tuy vậy vẫn có nhiều
lĩnh vực không có nhiều đòi hỏi cao, nghiêm ngặt về tính thẩm mĩ, các kỹ
thuật tự động gán nhãn có thể đƣợc áp dụng trong những trƣờng hợp này. Ví
dụ có thể áp dụng để gán nhãn tức thời cho những hệ thống thông tin địa lý
trực tuyến, tìm kiếm bản đồ trên internet hay một số bản đồ với mục đích đặc
biệt khác nhƣ hiển thị điều tra dân số, thăm dò dầu khí, điều tra đất. Hiện tại,
các hệ thống tƣơng tác bán tự động có thể là hƣớng tiếp cận phổ biến nhất cho
nghiên cứu gán nhãn tự động. Các hệ thống có thể cung cấp các vị trí nhãn,
những vị trí này sau đó đƣợc chỉnh sửa thủ công để đạt đƣợc kết quả nhƣ
mong muốn. Hơn nữa toàn bộ khái niệm của gán nhãn bản đồ tự động có thể
thay đổi phụ thuộc vào khả năng của máy tính. Bản đồ có thể đƣợc thể hiện
dƣới dạng điện tử, cho phép tƣơng tác với ngƣời dùng để hiển thị những
thông tin theo yêu cầu thay vì hiển thị toàn bộ mọi thông tin.
1.2.2. Mô tả bài toán gán nhãn cho đối tượng
Cho Γ là một bản vẽ và F là tập hợp các đối tƣợng đồ họa của Γ đƣợc
gán nhãn. Một giải pháp cho bài toán gán nhãn cho bản vẽ Γ bằng văn bản
hoặc ký tự cho mỗi thành phần f của F sao cho các thông tin có liên quan
đƣợc truyền đạt một cách tốt nhất có thể. Điều này có thể đạt đƣợc bằng cách
định vị các nhãn ở các vị trí thích hợp nhất.
13

Số hóa bởi Trung tâm Học liệu

Vị trí nhãn tốt sẽ hỗ trợ trong việc truyền đạt thông tin và tăng cƣờng
tính thẩm mỹ của bản vẽ. Rất khó để xác định đƣợc tất cả các đặc tính của

(c)
Hình 1.3. (a) Gán nhãn của một điểm. (b) Gán nhãn của một đường thẳng.
(c) Gán nhãn của một khu vực.
Trong việc sản xuất các bản đồ địa lý, việc sắp xếp thứ tự vị trí nhãn
theo nguyên tắc xây dựng qua nhiều năm kinh nghiệm, mà thƣờng nắm bắt
đƣợc chất lƣợng thẩm mỹ của vị trí nhãn. Một nguyên tắc đặc trƣng khi gán
nhãn điểm nút là nhãn phải đƣợc đặt ở bên phải và bên trên điểm. Ví dụ, trong
hình 1.3 (a) số thứ tự của từng vị trí nhãn cho thấy thứ hạng ƣu tiên của nhãn
cho nút này. Ngoài ra, nhãn của một điểm đƣợc phép chạm vào nhƣng không
chồng chéo lên điểm liên quan hoặc bất kỳ đối tƣợng đồ họa khác trong bản
vẽ. Trong trƣờng hợp gán nhãn cho đƣờng thẳng (cạnh), một nhãn đƣợc chấp
nhận khi chạm vào đƣờng đó, nhƣng nó không nên chồng chéo bất kỳ đối
tƣợng đồ họa khác trong một bản vẽ. Trong hình 1.3 (b), nơi mà đối tƣợng đồ
họa đƣợc gán nhãn là một đoạn thẳng, nhãn nhƣ A, B và D có vị trí thích hợp
hơn nhãn C, nhãn đƣợc đặt chồng lên cạnh liên quan, nó có thể chấp nhận
đƣợc với một số thời gian thích hợp để gán nhãn cho nó. Thực tế đƣợc chấp
nhận cho việc đặt một nhãn gắn liền với một khu vực là phải có nhãn trải dài
toàn bộ khu vực và phù hợp với hình dạng của nó, nhƣ thể hiện trong hình 1.3
(c).
Khi các đối tƣợng đồ họa đƣợc gán nhãn thuộc về một bản đồ kỹ thuật
hoặc bản vẽ, sau đó là một bộ quy tắc khác nhau của quy định quản lý các vị
15

Số hóa bởi Trung tâm Học liệu

trí nhãn thích hợp. Những quy định này phụ thuộc vào các ứng dụng cụ thể,
và phải tuân theo thông số kỹ thuật ngƣời dùng.

(a)


OS ( ( )) ( , )
i
i F j
C T i P i j

Với
1,nÕu (i)=j
P ( i, j)
0,trêng hîp kh¸c

Và
( , )
i
i F j
P i j F

Trong đó
( , ) 1, .
i
j
P i j i F

Bài toán gán nhãn có thể đƣợc xem nhƣ là một vấn đề tối ƣu hóa mà
mục tiêu là để tìm cách gán nhãn với thời gian tối thiểu mà mỗi đối tƣợng đồ
họa có một vị trí nhãn đƣợc gán. Mỗi vị trí nhãn λ
f
là một phần nhiệm vụ để
gán nhãn cuối cùng với thời gian thực. COST: Λ → N là hàm cung cấp cho vị
trí nhãn λ
f