Lời cảm ơn
Trước tiên, tôi muốn gửi lời cảm ơn sâu sắc t ới T.S Nguyễn Việt Hà, phó hi ệu trưởng
trường Đại học Công Nghệ - Đại học Quốc Gia Hà Nội, cùng Th.S Vũ Quang Dũng, giảng viên
bộ môn Công nghệ ph ần mềm, trường Đại học Công Ngh ệ. Các thầy đã hết lòng hướng dẫn tôi
trong suốt quá trình nghiên cứu k hoa học và thực hiện khó a luận tố t nghiệp này.
Tôi xin chân thành cảm ơn đội ngũ các thầy cô trường Đại học Công Nghệ đã cung cấp
cho tôi nền tảng kiến thức quý báu và giúp đỡ tận tình để tôi có thể hoàn thành khóa luận của
mình.
Tôi xin cảm ơn tới các thành viên phòng nghiên cứu Toshiba-Coltech đã giúp tôi có môi
trường nghiên cứu khoa học và luôn nhiệt tình trao đổi tài liệu cũng như kiến thức chuyên môn.
Cuối cùng, tôi xin gửi lời cảm ơn đến gia đình và những người thân của tôi, những người
đã luôn động viên tôi trong lúc khó khăn và giúp đỡ tôi trong s uốt quá trình học tập.
Hà Nội, 15 tháng 5 năm 201 0
Sinh viên,
Cao Bắc Tiến
i
Tóm tắt nội dun g của KLTN
Page layout là thuật toán được ứng dụng nhiều trong các bài toán hiển thị và tương tác với
người sử dụng. Ngày nay, cùng với sự phổ biến của thiết bị di động (TBDĐ) trong đờ i sống con
người thì vấn đề này càng mang ý nghĩa thiết thực. Vấn đề đặt ra là đưa các bài toán được hiển
thị t rên PC trước đây chuyển sang các TBDĐ với kích cỡ màn hì nh hạn chế và t hay đổi. Công
việc chuyển đổi này đòi hỏi yêu cầu tối ưu thuật toán để p hù hợp với các đặc tính về xử lý và
hiển thị của TBDĐ.
Nội dung khóa luận này sẽ hướng đến việc phát triển, tối ưu thu ật toán Adaptive Page
Layout về mặt tăng hiệu suất xử lý (tốc độ xử lý, bộ nhớ) cũng như các yêu cầu về giao diện
hiển thị. Để kiểm chứng các phương thức tối ưu, chúng tôi tiến hành cài đặt thuật toán và thực
hiện kiểm thử trên với môi trường Desktop PC và thiết bị nhúng (ARM). Đồng thời, các dữ liệu
được sử dụng đ ể kiểm thử ở đ ây chính là các dữ liệu về kiểm tra sức kh ỏe do bên phía Toshiba
cung cấp trong bài toán ứng dụng Health Examination Visualization.
Quá tr ình được thực hiện bởi n hóm nghiên cứu của p hòng thí nghiệm Tos hiba - Coltech.
Để giải quyết, chúng tôi sẽ lần lượt tiến hành cài đặt và tối ưu m ột phần với môi trường linux

(trên PC). Tiếp t heo là việc tối ưu về các phép xử lý từ Floating point sang Fixed point, m ột số
vấn đề hiển th ị khác t rên chip ARM n húng linux và hỗ trợ x ử lý đồ họa trên OpenGL|ES 2.0 .
Phần đầu sẽ được thực hiện b ởi tôi - Cao Bắc Tiến và phần thứ hai sẽ được đảm nhiệm bởi bạn
Nguyễn Tài Tuệ.
ii
Abstract
Page Layout is an algorithm which is used regularly in display and user interface in-
teraction problems. With the increasing popularity of mobile devices nowadays, the problems
become more necessary. T he question is how to por t that algorithm onto mobile devices which
have limited and various screen. The solving of its porting involes a need to optimize the algo-
ri thm to be in accord with features of processing and displaying.
Our thesis tends to improve, optimize algorithm Adaptive Page Layout in perfomance of
processing (speed of processing, memory consumptio n) as well as satisfyin g requirement of
user int erface. To verify effect of optimizing method, we p resent the methods to imp lement
algorithm and test it using a desktop Linux and an embedded (ARM) enviroment. For more
effectiveness of our verified method, the data using in test are given by Toshiba Corporation for
Health Examination Visualization application.
The process is done by research and d evelopment group of Toshiba-Coltech laboratory.
We also verify by optimizing in floating point calculation into fix point calculation which has
more effective to work with ARM embedded linux supporting OpenGL|ES 2.0 graphic environ-
ment. The part of testing and improving algorithm is done by me - Cao Bắc Tiến and the other
part will be done by Nguyễn Tài Tuệ.
iii
Mục lục
1 Mở đầu 1
2 Cơ sở lý thuyết 3
2.1 Ad aptive Page Layo ut . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.2 Thư vi ện ZUI Cippol o . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.2.1 Kiến trúc Cip polo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.2.2 Kịch bản hoạt động của Cippolo . . . . . . . . . . . . . . . . . . . . . 10

2.2.3 Các thu ật toán xử lý chính . . . . . . . . . . . . . . . . . . . . . . . . 11
2.2.4 Phân loại hàm tron g Cippolo . . . . . . . . . . . . . . . . . . . . . . . 12
2.3 OpenCV . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
3 Bài toán đặt ra 13
3.1 Tốc đ ộ xử lý, giới hạn bộ nhớ . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
3.2 Các yêu cầu về giao di ện người dùng . . . . . . . . . . . . . . . . . . . . . . . 14
4 Giải pháp 15
4.1 Tri ển khai t huật toán trên linux . . . . . . . . . . . . . . . . . . . . . . . . . . 15
4.2 Tối ưu tốc độ xử lý và sử dụng bộ nh ớ . . . . . . . . . . . . . . . . . . . . . . 17
iv
MỤC LỤC
4.2.1 Phân hoạch node . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
4.2.2 Thay thế cây nhị phân . . . . . . . . . . . . . . . . . . . . . . . . . . 18
4.3 Tối ưu về mặt giao diện người dùng . . . . . . . . . . . . . . . . . . . . . . . 20
4.3.1 Sử dụng tỉ lệ tương đ ối . . . . . . . . . . . . . . . . . . . . . . . . . . 20
4.3.2 Kéo dãn khối hình . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
5 Thực nghiệm - Demo 22
5.1 Thực nghiệm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
5.2 Health Data Visualization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
5.2.1 Tóm tắt đặc tả yêu cầu phần mềm . . . . . . . . . . . . . . . . . . . . 25
5.2.2 Các bước phát triển hệ thống . . . . . . . . . . . . . . . . . . . . . . . 28
5.2.3 Kiến trúc chương trì nh . . . . . . . . . . . . . . . . . . . . . . . . . . 29
5.2.4 Demo chương trình . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
6 Kết luận và hướng phát triển 32
6.1 Kết luận . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
6.2 Một số hướng phát triển . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
A Phụ lục 34
A.1 Thuật toán chuyển đổi từ trung tố sang hậu tố (infix to postfix) . . . . . . . . . 34
A.2 Mẫu bản ghi dữ liệu sức kh ỏe do phía Toshiba cung cấp . . . . . . . . . . . . . 36
A.3 Demo chương trình hiển t h ị ảnh . . . . . . . . . . . . . . . . . . . . . . . . . 36

A.4 Phiên bản HEDV chúng tôi phát triển trên nền tảng Window . . . . . . . . . . 36
Tài liệu tham khảo 42
v
Danh sách hình vẽ
2.1 Biểu đồ khối thuật toán APL . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.2 Các mẫu có thể với số khối hình là 3 . . . . . . . . . . . . . . . . . . . . . . . 6
2.3 Biểu đồ khối Phân hoạch node s ử dụng trong APL . . . . . . . . . . . . . . . . 7
2.4 Ví dụ minh họa cách xếp 4 hình đầu tiên . . . . . . . . . . . . . . . . . . . . . 8
2.5 Ví dụ minh họa cây nhị phân sau khi chèn . . . . . . . . . . . . . . . . . . . . 8
2.6 Ví dụ minh họa cách sắp xếp mới . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.7 Tổng quan Cippolo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.8 Kịch bản hoạt động của Cippolo . . . . . . . . . . . . . . . . . . . . . . . . . 11
3.1 Yêu cầu cải thiện về mặt giao diện . . . . . . . . . . . . . . . . . . . . . . . . 14
4.1 Mô hình cài đặt APL không có xử lý về đồ họa . . . . . . . . . . . . . . . . . 16
4.2 Mô hình cài đặt APL với OpenCV . . . . . . . . . . . . . . . . . . . . . . . . 17
4.3 Mô hình xây dựng dàn trang . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
5.1 Đồ th ị thời gian thực thi của chương trình trước và sau khi tố i ưu . . . . . . . . 23
5.2 Đồ th ị diện tích bao phủ của các kh ối hình trước và sau khi tối ưu . . . . . . . . 24
5.3 Kiến trúc tổng quát của HEDV . . . . . . . . . . . . . . . . . . . . . . . . . . 25
vi
DANH SÁCH HÌNH VẼ
5.4 Mô hình ca sử dụng (usecase) của HEDV . . . . . . . . . . . . . . . . . . . . 26
5.5 Cách chia các mục trong mỗ i hình chữ nhật (sử dụng trong HE DV) . . . . . . . 28
5.6 Giao diện HEDV được yêu cầu (cung cấp bởi phía Toshiba) . . . . . . . . . . . 28
5.7 Biểu đồ thiết kế hệ thống HEDV . . . . . . . . . . . . . . . . . . . . . . . . . 30
5.8 Đồ th ị kết quả kiểm thử HEDV . . . . . . . . . . . . . . . . . . . . . . . . . . 30
5.9 Demo chương trình HEDV . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
A.1 Quá trình thực thi thuật toán "infix to postfix" . . . . . . . . . . . . . . . . . . 35
A.2 Giao diện demo chương trình hiển thị ảnh . . . . . . . . . . . . . . . . . . . . 37
A.3 Demo HEDV phiên bản trên Window với các mục được chia theo đường chéo . 38

A.4 Demo HEDV phiên bản trên Window với các mục được chia theo treemap . . . 39
A.5 Chức năng hiển thị khối hình trong HEDV . . . . . . . . . . . . . . . . . . . . 39
A.6 Chức năng chọn mục dữ liệu trong HEDV . . . . . . . . . . . . . . . . . . . . 40
A.7 Chức năng tùy chọn hiển thị trong HEDV . . . . . . . . . . . . . . . . . . . . 40
A.8 Chức năng chọn lọc dữ liệu trong HEDV . . . . . . . . . . . . . . . . . . . . . 41
vii
Danh sách bảng
1 Bảng từ viết tắt . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ix
2.1 Phân loại hàm tron g Cippolo . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
5.1 Kết quả test thời gian thực thi (milli giây) . . . . . . . . . . . . . . . . . . . . 22
5.2 Kết quả test diện tích che phủ (%) . . . . . . . . . . . . . . . . . . . . . . . . 23
5.3 Kịch bản hoạt động . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
5.4 Kết quả kiểm thử demo chương trình . . . . . . . . . . . . . . . . . . . . . . . 31
A.1 Giá trị chuẩn của dữ liệu kiểm tra sức khỏe . . . . . . . . . . . . . . . . . . . 36
viii
Bảng từ viết tắt
STT Từ ho ặ c cụm từ Từ viết tắt Chú thích
1 Adaptive Page Layout APL Dàn trang mang tính thích ứng
2 Personal Computer PC Máy tính cá nhân
3 He alth Examination Data Visu-
alization
HEDV Hệ thống trực quan hóa dữ liệu
kiểm tra sức khỏe
4 Thiế t bị di động TBDĐ
5 Zoom ab le U se r Interface ZUI Giao diện người dùng hỗ trợ
"zoom"
Bảng 1: Bảng từ viết tắt
ix
CHƯƠNG 1
Mở đầu

Trong những năm gần đây, TBDĐ dần trở thành một trong những thiết bị thông tin phổ
biến nh ất hỗ trợ người sử dụng. Chúng có mặt khắp mọi nơi và có thể dễ dàng bắt gặp chúng mọi
lúc trong cuộ c sống của chúng ta. Cùng với điều này, việc hiển thị, tương tác người dùng dành
cho TBDĐ đã trở thành một vấn đề nghiên cứu rất được quan tâm. Khi mà dung lượ ng bộ nhớ
của các TBDĐ ngày càng lớn mang lại những lợi ích trong việc lưu trữ các tài liệu, hình ảnh,
video, t hì cũng tạo ra kh ó khăn trong việc tìm ki ếm và hiển thị chúng. Mặt khác, cùng với sự
phát triển, công nghệ ngày nay (điển hình là hệ thống Ambient Assisted Living [
2]) cho phép
người sử dụng hiển thị hay phát những dữ liệu (video, hình ảnh, ) giống nhau t rên nhiều thiết
bị khác nhau như iPod, Tivi, điện thoại, hay ngay cả màn hình định hướng GPS của xe h ơi
Mặc dù mỗi thiết bị này có kích cỡ hiển thị khác nhau, nội dung video, hình ảnh cần được hiển
thị với các layout thích ứng với từng màn hình đó. Giả sử rằng, đầu tiên, người dùng kiểm tra
một tập các video gia đình trên tivi 45-inch, kích thước 16:9 ở phòng khách, sau đó người này
chuyển vào phòng làm việc và tiếp tục công việc của mình trên máy tính xách tay với màn hình
12-inch, 4:3, cuối cùng là kết thúc công việc với một màn hình hiển thị nhỏ 3-inch, 3:4 của điện
thoại đi động ở ngoài ban công. Thumbnail hiển thị của các v ideo phải được chuyển đổi không
ngừng tương ứn g với từng màn hình hiển thị trong thời gian th ực nhằm cung cấp một giao diện
người dùng mang tính thí ch ứng một cách thông minh. Trong trường hợp này, việc dàn trang
nhanh chóng và mang tín h thích ứng là hết sức cần t hiết.
1
CHƯƠNG 1: MỞ ĐẦU
Có nhiều thuật toán về dàn trang (page layout) đã được nghiên cứu và phát triển như :
Layout Manga Algorithm [
3], VIPS (Vision-based Page Segmentatio n Algorithm) [4] hay Web
Page Layout [5], Adaptive Document Layout [6] Nhưng hầu hết các thuật toán n ày đều được
ứng dụng cho nền tảng PC, không thực sự đáp ứng được các yêu cầu khi chuyển đổi và cài trên
thiết bị nhúng (như giới hạn về khả năng xử lý, bộ nhớ và màn hình hiển thị ). Trong khóa luận
này, chúng tôi sẽ chọn thuật toán APL (for ordered block ) và tiến hành các bước tối ưu để giải
quyết bài toán về dàn trang trên TBDĐ. Chúng tôi hi vọng cách tiếp cận và giải quyết b ài toán
được đưa ra trong khóa luận này sẽ mang lại những ý nghĩa tích cực trong th ực tiễn.

Ngoài phần mở đầu, bố cục của khóa luận gồm bốn chương kế tiếp như sau:
• Chương 2: Trình bày các cơ sở lý thuyết mà chúng tôi sử dụng trong việc giải quyết bài
toán của mình.
• Chương 3: Trình bày cụ thể những yêu cầu mà bài toán đặt ra.
• Chương 4: Trình bày hướng giải quyết và những phương p háp được áp dụng.
• Chương 5: Đưa ra demo, kết quả thực nghiệm và đánh giá hiệu suất cũn g như ý nghĩa
thực tiễn.
• Chương 6: Kết lu ận và nêu một số hướng phát triển trong tương lai.
2
CHƯƠNG 2
Cơ sở lý thuyết
Trong khuôn khổ bài toán phải giải quyết và các vấn đề được nêu ra trong phần mở đầu,
chúng tôi cần quan tâm tìm hiểu tới các vấn đề về lý thuyết như: thuật toán Adaptive Page Layout
(dàn trang mang tín h thích ứng), thư viện ZUI (Zoomable User Interface) Cippolo , các cơ sở về
kiến trúc ARM, thuật toán về trực quan hóa dữ liệu Squarified Treemap và thư viện xử lý ảnh
OpenCV. Các vấn đề này sẽ được chúng tôi trì nh bày dưới dạng hiểu biết của m ình và kèm theo
các giải thích hướng vào sử dụng trong bài toán của chúng tôi.
2.1 Ad aptive Page Layout
Tóm lược thuật toán
Thuật toán Adaptive Page Layout [
7] được áp dụng để đưa ra cách dàn trang tối ưu (về
mặt không gian che p hủ và các yếu tố khác như độ quan trọng, độ ưu t iên ) cho các khối hình
chữ nhật có thứ tự.
Với N khối hình chữ n h ật được sắp xếp theo thứ tự có diện tích (a) và cạnh (r) tương ứng
là (a
1
, r
1
), (a
2

, r
2
), (a
3
, r
3
), . . , (a
N
, r
N
) với 1 , 2, 3, N là thứ tự ban đầu của các khối hình.
Khi đó, t huật toán sẽ đượ c xử lý theo hai bước:
3
CHƯƠNG 2: CƠ SỞ LÝ THUYẾT
• Nếu N ≤ 4 thì sẽ dùng các dàn trang với mẫu (template) cho sẵn.
• Nếu N > 4 thì phươn g pháp phân hoạch node sẽ được sử dụng. Đầu tiên, tất cả các khố i
hình chữ nhật sẽ đượ c liệt kê theo thứ tự diện tích giảm dần. Khi đó, t a có danh sách khối
hình ch ữ nhật mới (a
′
1
, r
′
1
), (a
′
2
, r
′
2
), (a

′
3
, r
′
3
), , (a
′
N
, r
′
N
). Tiếp theo, 4 khối hình chữ nhật
có diện tích lớn nhất (a
′
1
, r
′
1
), (a
′
2
, r
′
2
), (a
′
3
, r
′
3

) và (a
′
4
, r
′
4
) sẽ được sắp xếp vào trang hiển
thị theo phươ ng pháp sử dụng mẫu cho sẵn. Cuối cùng, các khối hình chữ nhật còn lại sẽ
được thêm vào cách dàn trang trước đó theo thứ tự diện tích của chúng từng cái một b ằng
việc sử dụng cách dàn trang với phân hoạch node. Biểu đồ khối mô tả thuật toán được thể
hiện trong h ình
2.1.
a. Dàn trang sử dụng mẫu.
Hình 2.2 thể hiện các mẫu (template) với số khối hình là 3 (tất cả có 8 mẫu). Với số
khối hình là 4 ta sẽ có số mẫu là 38.
Dàn trang sử dụng mẫu là phương pháp dàn trang đơn g iản, bằng cách t iền định
nghĩa các mẫu và chọn mẫu tốt nhất (mẫu có diện tích được che phủ lớn nhất) để sử dụ ng.
Thứ tự các khối hình được sắp xếp theo thứ tự trên cùng phía bên trái cho tới dưới cùng
phía bên phải. Với mỗi mẫu, diện tích che p hủ được suy ra từ d iện tích tương đối và các
cạnh của mỗi khối hình, theo công thức sau (1) sau:
S
N
=

N
i=1
a
i
a
pbb

∗
min{r
pbb
, r
page
}
max{r
pbb
, r
page
}
(1)
Với:
+ a
i
là diện tích tương đối của k hối hình thứ i
+ r
page
là cạnh của trang cho trước
+ a
pbb
, r
pbb
là diện tích tương đối và cạnh biên của node root được suy ra phép tìm
kiếm theo chiều sâu t rong cây nhị phân tương ứng
4
CHƯƠNG 2: CƠ SỞ LÝ THUYẾT
Hình 2.1: Biểu đồ khối thuật toán APL
b. Dàn trang sử dụng phân h oạch node
Việc dàn trang bằng phân hoạch node sử dụng cây nhị phân như là một cấu trú c

lưu trữ dữ liệu về cách dàn trang. Các node (tương ứng với mỗi khối hình) sẽ được chèn
5
CHƯƠNG 2: CƠ SỞ LÝ THUYẾT
Hình 2.2: Các mẫu có thể với số khối hình là 3
lần lượt vào cây nhị phân theo hai bước: (1) Chọn một n o de (trong cây n hị ph ân) và thay
thế cây con của nó bằng node "nội" (node nằm phía trong cây nhị phân) mới; (2) Thêm
khối hình mới và như l à một n ode lá của node "nội" vừa được chèn vào. Sau đó, sử dụn g
hàm đánh giá để tìm ra cách sắp xếp tốt nhất (xem biểu đồ hình 2.3).
c. Hàm đánh giá
Nhằm chọn ra cách dàn trang tốt nhất dựa theo tiêu chí về độ che phủ lẫn thứ tự, độ
ưu tiên của các khối hình, thuật toán APL sử dụng biểu thức đánh giá (2).
ˆ
S = η
k
∗ S
k
(2)
Trong đó:
– S
k
đã được tính thông qua công thức (1) đã được trình bày ở trên
– η
k
được tính thông qua công thức (3)
η
k
= exp[
1
k
∗ (α +

k

i=1
m
i
) ∗
k

i=1
V
i
] (3)
Với: V
i
là sự kéo dãn của 2 khối hình liên tiếp dựa vào thứ tự sắp xếp trong lượt thời
gian của chúng; m
k
là số hình khối giữa 2 hình khối liên tiếp (được chèn vào cây nhị
phân); α là hằng số để chỉnh độ ưu tiên của mỗi blocks.
6
CHƯƠNG 2: CƠ SỞ LÝ THUYẾT
Hình 2.3: Biểu đồ khối Phân hoạch node sử dụng trong APL
Ví dụ về hoạt động của thuật toán
Để hình dung rõ hơn thuật toán s ẽ hoạt động như thế nào, chúng ta xét ví dụ sau.
Giả sử s ố khối hình cần sắp xếp l à 5 bao gồm (1, 2, 3, 4, 5). Đầu tiên, dựa vào các mẫu
7
CHƯƠNG 2: CƠ SỞ LÝ THUYẾT
(template) cho trước, dành cho việc sắp xếp 4 khối hình, thuật toán sẽ tính t o án để chọn ra cách
sắp xếp phù hợp nhất. Giả sử, các hình được sắp xếp như tron g biểu đồ
2.4a. Khi đó, 2.4b s ẽ l à

cây nhị phân tương ứng của cách sắp xếp này.
(a) Cách xếp (b) Cây nhị phân tương ứn g với
4 hình
Hình 2.4: Ví dụ minh họa cách xếp 4 hình đầu tiên
Tiếp theo, khối hình thứ 5 , APL sẽ tiến hành chèn vào cây nhị phân để sinh ra cách sắp
xếp mới. Nếu như chèn 5 vào các nod e l á (ví dụ chèn vào node 1) ta được 1 trường hợp cây nhị
phân mới (hình 2.5a). Hoặc với trường hợp chèn vào node nội (ví dụ, chèn vào node V bên trái)
ta được 1 trường hợp cây nhị phân mới khác (hình
2.5b).
(a) Chèn vào node lá (b) Chèn vào node "nội"
Hình 2.5: Ví dụ minh họa cây nhị phân sau khi chèn
Khi đó, xét với trường hợp cây nhị phân mới khi chèn node số 5 vào no de lá (hình
2.5a) ở
trên, ta có cách sắp xếp mới tương ứng như được thể hiện trong hình
2.6. Tương tự như thế, các
khối hình còn lại sẽ được chèn lần lượt vào trang hiển thị.
8
CHƯƠNG 2: CƠ SỞ LÝ THUYẾT
Hình 2.6: Ví dụ minh họa cách sắp xếp mới
Một số nhược điểm tồn tại
APL còn tồn tại một số nhược điểm về hiển thị và hiệu suất. Cách dàn trang được đưa
ra bởi APL vẫn có nhiều không gian "chết" - diện tích không được b ao phủ bởi các khối hình.
Mặt khác, độ phức tạp của APL là khá cao (tính theo hàm số mũ), bởi vậy, đòi hỏi nhi ều thời
gian tính toán khi số lượng khối hình tăng lên. Hơn nữa, A PL tiêu tốn khá nhiều bộ nhớ khi t ính
toán. Những hạn chế này gây khá nh iều bất lợi khi cài đặt APL lên thiết b ị nhúng.
2.2 Thư v i ện ZUI Cippolo
Cippolo là một thư viện ZUI (Zoomable User Interface) cung cấp các khả năng tương
tác đồ họa sử dụng trên thiết bị nhúng được phát triển bởi nhóm phát triển Toshiba-Coltech.
Cippolo không có vai trò t rong quá trình tối ưu thuật toán APL, tuy vậy, là một thành phần quan
trọng trong việc xây dựng demo của chúng t ôi trong phần Thực nghiệm - Demo.

2.2.1 Kiến trúc Cippolo
Cippolo sử dụng OpenGL|ES và kết hợp thư viện Xlib để xử lý đồ họa. Cippolo được
hình thành và phát triển dựa trên thư viện Piccolo - là thư viện ZUI trên PC [
10]. Cippo lo được
9
CHƯƠNG 2: CƠ SỞ LÝ THUYẾT
viết hoàn toàn bằng ngôn ngữ lập trình C và được tối ưu cho kiến trúc thiết bị nhúng ARM.
Xlib được dùng nhằm xây dựng giao diện đồ họa người dùng và giao tiếp với thiết bị nhúng.
OpenGL|ES có vai trò trong xử lý các đối tượng đồ họa phức tạp, các đối tượ ng đồ họa chuyển
động. Cippolo sử dụng đồng thời Xlib và OpenGL|ES để xây dựng thư vi ện hàm về "zoom". Vai
trò của các thành phần được mô hình một cách trực quan thông qua biểu đồ 2.7.
Trong ứng dụng demo của chúng tôi, Cippolo sẽ đóng vai trò trong việc cung cấp các hàm
API và nền tảng để xây dựng khả năng tương tác với người dùng, cho phép người dùng phóng
to hoặc thu nhỏ các đối tượng đồ họa trên màn hình hiển thị.
Hình 2.7: Tổng quan Cippolo
2.2.2 Kịch bản hoạt động của Cippolo
Kịch bản hoạt động của Cipplo được mô hình hóa qua biểu đồ
2.8.Cippolo tạo ra
kiến trúc đa tầng giữa các đối tượng Các node con sẽ được đặt trong hệ tọa độ của "mẹ"
chúng. Mỗi node sẽ có một m a trận, ma trận này được sử dụng để tính tọa độ của nó trong
hệ tọa độ của "mẹ" nó. Điều này giúp cho các node có thể đ ượ c kéo giãn, tịnh tiến, hoặc
xoay. Khi tọa độ của node mẹ bị thay đổi, thì tọa độ của node con cũng bị thay đổi bởi
vì node con nằm trong node "mẹ". Node root điều khiển t ất cả các chuyển động của các
node con bằng AnimationScheduler. Cây chứa các node tươn g tác với người dùng thông
qua canvas, canvas nhận các sự ki ện và s au đó, sẽ tính toán xem những node nào sẽ bị ảnh
10
CHƯƠNG 2: CƠ SỞ LÝ THUYẾT
hưởng bởi những sự kiện này. Canvas cũng chịu trách nhiệm vẽ cây chứa các node và hiện
thực hóa khi nó được vẽ lại vùng diện tích bị thay đổi.
Hình 2.8: Kịch bản hoạt động của Cippolo

2.2.3 Các thuật toán xử lý chính
Cippolo chứa các thuật toán xử lý cơ bản:
••••••- Zooming
Thuật toán xử lý việc hiển thị mặt ph ẳng vô hạn, và hỗ trợ mọi độ phân giải, nhằm cho
phép người d ùng có thể phón g to, thu nhỏ các đối tượng đồ h ọ a.
- Quản lý đối tượng (camera, layer, node, canvas)
Thuật toán xử lý quan hệ phân cấp giữa các đối tượng đồ họa.
- Quản lý miền đồ h ọa
Thuật toán xử lý giới hạn của các miền đồ họa
- Render ảnh
Các thuật toán render hình ảnh ra màn hình hiển thị, có sử dụng các API của OpenGLES.
11
CHƯƠNG 2: CƠ SỞ LÝ THUYẾT
Phân loại Miêu tả
Zoom - Hiển thị một mặt phẳng vô hạn có thể được
hiển thị với bất kì độ phân giải nào.
- Việc tương tác zoom và mở rộng cho phép
người dùng chỉ định những đối tượng được
hiển thị.
- Phóng to hoặc thu nhỏ ở mức độ chi tiết
được yêu cầu.
Animation Các đối tượng đồ họa chuyển động sử dụng
các đặc tả OpenGL|ES.
Bảng 2.1: Phân loại hàm trong Cippolo
2.2.4 Phân loại hàm trong Cippolo
2.3 OpenC V
OpenCV [
12] sẽ đóng vai trò trong việc xử lý và xây dựng các đối tượn g đồ họa trong
demo mà chúng tôi sẽ đề cập sau trong phần Thực nghiệm - Demo.
OpenCV là một thư viện xử lý ảnh mã nguồn mở, ban đầu được phát triển bởi Intel.

OpenCV là thư một viện "đa nền tảng" (cross-platform) và tập trung vào việc xử lý ảnh thời
gian thực. Thư viện này chủ yếu được viết bằng ngôn ngữ lập trình C bởi vậy giúp nó có tính
tương thích, khả chuyển trên một số nền tảng. Bởi những ưu điểm đó, chúng tôi đã chọn OpenCV
để thực h iện các demo có sử dụng đồ h ọa trên môi trường linux của mình.
Ngoài ra, trong quá trình thực hiện khóa luận này, em sẽ tham khảo thêm một số kiến
thức về ARM và thuật toán Squarified Treemap được trình bày trong khóa luận tốt nghiệp của
bạn Nguyễn Tài Tuệ.
12
CHƯƠNG 3
Bài toán đặt ra
Mục tiêu bài toán là giải quyết vấn đề hiển thị và tương tác ngườ i dùng trên TBDĐ, bởi
vậy, ngoài những yêu cầu về gi ao diện thì có những yêu cầu đặt ra đặc trưng bởi nền tảng thiết
bị n húng. Có thể nói, bài toán bao gồm hai vấn đề lớn : (1) Tốc độ xử lý, giới hạn bộ nhớ và (2)
Các yêu cầu về giao diện n gười dùng. Những yêu cầu này có sự khác biệt khi tiến hành triển
khai trên PC và chuyển sang ARM.
Tuy mục đích hướng đến là các TBDĐ, nhưng chúng em sẽ thực hiện theo hai bước: thứ
nhất, tối ưu ban đầu trên PC với môi trường Linux và th ứ hai, tiến h ành chuyển sang ARM. Vì
vậy, có một số yêu cầu khác nhau giữa chúng.
3.1 Tốc độ xử lý, giớ i hạn bộ nhớ
Đầu tiên, cần cài đặt thuật toán APL trên PC vớ i môi trường Linux và tiến hành kiểm thử
hiệu suất. Thứ hai, nhằm mục đích cuối cùng l à triển khai trên TBDĐ với b ộ vi xử lý có tốc
độ t hấp và bộ nhớ giới hạn rất nhiều so với PC, nên trong giai đoạn triển khai ban đầu trên PC,
thuật toán APL cần tối ưu tối đa về các phép tính toán xử lý làm sao có thể g iảm thiểu thời gian
tính toán và yêu cầu về bộ nhớ trước khi chuyển sang cài đặt trên ARM. Một trong nh ữn g vấn
đề tối ưu về bộ nhớ đặt ra đó là, chỉ tải nhữn g dữ liệu cần hiển thị vào bộ nhớ và xó a chúng kh i
13
CHƯƠNG 3: BÀI TOÁN ĐẶT RA
không có nhu cầu sử dụn g.
3.2 Các yêu cầu về giao d iện người dùn g
Một trong những nhiệm vụ chính của việc xây dựng giao diện người dù ng là mang tới sự

thân thiện và tiện lợi. Điều đó đòi hỏi thuật toán dàn trang phải đưa ra cách sắp xếp hiệu quả
đảm bảo tận dụng tối đa không gian hiển thị, tốc độ cũng như có khả năng đáp ứng nhanh các
yêu cầu về tìm kiếm và các xử lý khác (như phóng to, thu nhỏ, ). Và đặc biệt, khi bài toán
chuyển sang thiết bị di động với màn hình hiển thị rất giới hạn thì các yêu cầu trên cần phải
được đáp ứn g một cách hoàn thiện và đầy đủ hơn.
Thuật toán APL còn tồn tại nhiều không gian "chết" giữa các blocks - phần diện tích
không được bao phủ bởi các blocks (hình
3.1). Giảm thiểu các khoảng trống này cũng là một
vấn đề về tối ưu cần th ực hiện. Điều thứ hai trong yêu cầu về giao diện người dùng đó là vấn đề
"Zoomable" - cho phép người d ùng có thể dễ dàng hiển thị những nội dung quan trọng. Ngoài
ra, vấn đề tối ưu bộ nhớ được giải quyết cũng góp phần tăng tốc độ hiển thị của chương trình.
(a) APL chứa nhiều không gian chết (b) APL mong muốn
Hình 3.1: Yêu cầu cải thiện về mặt giao diện
14
CHƯƠNG 4
Giải pháp
Về phần giải pháp, trong khóa luận này, tôi sẽ tập trung trình bày việc cài đặt và tố i ưu
thuật toán APL trên PC với môi trường linux. Về bước tối ưu và triển khai trên ARM sẽ được
tr ình bày cụ thể trong khóa luận của bạn Nguyễn Tài Tuệ.
4.1 Triển khai th uật toán trên linux
Để nhằm đánh giá chính xác hiệu suất tính toán của thuật toán, tôi sẽ t iến hành cài đặt
thuật toán với hai lần và có đánh giá cho mỗi lần, đó là: lần một, cài đặt thuật toán như một ứng
dụng console và lần hai, cài đặt thuật toán có xử lý đồ họa.
Với lần một, thuật toán sẽ được cài đặt đơn thuần không có xử lý về đồ họa nhằm mục
đích kiểm tra tính tối ưu trong các phép tính toán của APL. Cấu trúc cài đặt được thể hiện trong
hình
4.1. Dữ liệu đầu vào của chương trình sẽ l à các tệp văn bản đơn giản (.txt) chứa các th ông
số về các khối hình: số hình, kí ch cỡ của mỗi khối hình. Dữ liệu đầu ra của chương trình sẽ là
tệp văn bản chứa cách sắp xếp các khối hình, chi tiết cách sắp xếp và thời gian tiêu tốn.
• Cách sắp xếp các khối hình sẽ được thể hiện theo định dạng sau: (((1H0)V(2H4))V3)

Trong đó, H (horizontal) t hể hiện việc sắp xếp nằm ngang, V (vertical) thể hiện sự sắp
15
CHƯƠNG 4: GIẢI PHÁP
xếp thẳng đứng. 0, 1, 2, là các định danh của các khối hình.
• Chi tiết cách sắp xếp sẽ bao gồm một tập hợp gồm tọa độ và kích cỡ của mỗi khối hình
sau khi sắp xếp. Ví dụ: 3: 316 ; 53 ; 2 61 ; 292 nghĩa là khối hình có định danh là 3 có tọa
độ đỉnh trên cùng bên trái là (31 6, 53) và có kích cỡ là (216, 29 2).
Hình 4.1: Mô hình cài đặt APL không có xử lý về đồ họa
• Rect sẽ lưu các dữ liệu về mỗi k hối hình.
• BinaryTree chứa các hàm xử lý về template, và partion s node, để chèn các khối hình
vào cây nhị phân.
• PageLayout nhận xử lý các dữ liệu đầu vào, sử dụng BinaryTree để đưa ra cách sắp xếp
tối ưu và ghi vào dữ liệu đầu ra.
• List, Node là các cấu trúc dữ liệu sử dụng để cài đặt thuật toán.
Lần hai, cũng cài đặt tương tự như lần một nhưng chương trìn h sẽ được bổ sung thành p hần
về xử lý đồ họa, nhằm đánh giá chính xác hơn việc t hỏa mãn yêu cầu về giao diện của APL và
tốc độ xử lý ảnh (hình
4.2) . Thư viện xử lý ảnh đượ c sử dụng đó là OpenCV.
16