Luận văn Phát triển, tối ưu thuật toán Adaptive Pagelayout trên PC

ĐẠI HỌC QUỐC GIA HÀ NỘI

TRƯỜNG ĐẠI HỌC CÔNG NGHỆ

Cao Bắc Tiến

PHÁT TRIỂN, TỐI ƯU THUẬT TOÁN ADAPTIVE

PAGELAYOUT TRÊN PC

KHOÁ LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY

Ngành: Công nghệ phần mềm

HÀ NỘI – 2010

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 khoa 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 suốt quá trình học tập.

Hà Nội, 15 tháng 5 năm 2010

Sinh viên,

Cao Bắc Tiến

i

Tóm tắt nội dung 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ị trên PC trước đây chuyển sang các TBDĐ với kích cỡ màn hình hạn chế và thay đổi. Công

việc chuyển đổi này đòi hỏi yêu cầu tối ưu thuật toán để phù 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 nhóm nghiên cứu của phòng thí nghiệm Toshiba - 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 theo 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 trên chip ARM nhú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. The question is how to port that algorithm onto mobile devices which

have limited and various screen. The solving of its porting involes a need to optimize the algo-

rithm 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 consumption) as well as satisfying requirement of

user interface. To verify effect of optimizing method, we present the methods to implement

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 development 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

9

2.1 Adaptive Page Layout . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.2 Thư viện ZUI Cippolo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.2.1 Kiến trúc Cippolo . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

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 trong 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 thuậ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 thị ả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 . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.2 Các mẫu có thể với số khối hình là 3 . . . . . . . . . . . . . . . . . . . . . . .

2.3 Biểu đồ khối Phân hoạch node sử dụng trong APL . . . . . . . . . . . . . . . .

2.4 Ví dụ minh họa cách xếp 4 hình đầu tiên . . . . . . . . . . . . . . . . . . . . .

2.5 Ví dụ minh họa cây nhị phân sau khi chèn . . . . . . . . . . . . . . . . . . . .

2.6 Ví dụ minh họa cách sắp xếp mới . . . . . . . . . . . . . . . . . . . . . . . . .

5

6

7

8

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 HEDV) . . . . . . . 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 trong 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

2

3

Adaptive Page Layout

Personal Computer

APL

Dàn trang mang tính thích ứng

Máy tính cá nhân

PC

Health Examination Data Visu- HEDV

alization

Hệ thống trực quan hóa dữ liệu

kiểm tra sức khỏe

4

5

Thiết bị di động

Zoomable User Interface

TBDĐ

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, ... thì 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 trê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 video phải được chuyển đổi không

ngừng tương ứng 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ính thích ứng là hết sức cần thiế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 Segmentation 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 phá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ũng 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ính 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 Adaptive 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 phủ và các yếu tố khác như độ quan trọng, độ ưu tiên ...) cho các khối hình

chữ nhật có thứ tự.

Với N khối hình chữ nhật được sắp xếp theo thứ tự có diện tích (a) và cạnh (r) tương ứng

là (a₁, r₁), (a₂, r₂), (a₃, r₃), .... , (a_N, r_N) với 1, 2, 3, ... N là thứ tự ban đầu của các khối hình.

Khi đó, thuậ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ương 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 đó, ta có danh sách khối

′

hình chữ nhật mới (a₁, r₁), (a₂, r₂), (a₃, r₃), .... , (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₁, r₁), (a₂, r₂), (a₃, r₃) và (a₄, r₄) 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 giản, bằng cách tiề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 phủ được suy ra từ diệ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:

P_N

a_imin{r_pbb, r_page

}

i=1

S_N=

∗

(1)

a_pbb

max{r_pbb, r_page}

Với:

+ a_ilà diện tích tương đối của khối hình thứ i

+ r_pagelà cạnh của trang cho trước

+ a_pbb, r_pbblà 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 trong 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 hoạ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 node (trong cây nhị 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 node lá của node "nội" vừa được chèn vào. Sau đó, sử dụng

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

X

1

η_k= exp[ ∗ (α +

m_i) ∗

V_i]

(3)

k

i=1

Với: V_ilà 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_klà 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 toá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ư trong 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 ứng 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 node 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 node 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 bao 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, APL tiêu tốn khá nhiều bộ nhớ khi tính

toán. Những hạn chế này gây khá nhiều bất lợi khi cài đặt APL lên thiết bị nhúng.

2.2 Thư việ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ò trong 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]. Cippolo đượ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 ma 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ương tác với người dùng thông

qua canvas, canvas nhận các sự kiện và sau đó, 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óng 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

Zoom

Miêu tả

- 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 OpenCV

OpenCV [12] sẽ đóng vai trò trong việc xử lý và xây dựng các đối tượng đồ 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 hiệ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ề giao diện thì có những yêu cầu đặt ra đặc trưng bởi nền tảng thiết

bị nhú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 ngườ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

độ thấ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ể giả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ững vấn

đề tối ưu về bộ nhớ đặt ra đó là, chỉ tải những dữ liệu cần hiển thị vào bộ nhớ và xóa chúng khi

13

CHƯƠNG 3: BÀI TOÁN ĐẶT RA

không có nhu cầu sử dụng.

3.2 Các yêu cầu về giao diện người dùng

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 ứng 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

Hình 3.1: Yêu cầu cải thiện về mặt giao diện

(b) APL mong muố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 thuậ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ẽ tiế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) thể 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 ; 261 ; 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à (316, 53) và có kích cỡ là (216, 292).

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 khối hình.

• BinaryTree chứa các hàm xử lý về template, và partions 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ình sẽ được bổ sung thành phần

về xử lý đồ họa, nhằm đánh giá chính xác hơn việc thỏ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

CHƯƠNG 4: GIẢI PHÁP

Hình 4.2: Mô hình cài đặt APL với OpenCV

4.2 Tối ưu tốc độ xử lý và sử dụng bộ nhớ

4.2.1 Phân hoạch node

Sau quá trình phân tích thuật toán ban đầu được đưa ra bởi Dr.Li, tôi nhận thấy rằng, phần

phân hoạch node (partions node) có thể được tối ưu hơn để giảm quá trình tính toán. Như đã nói

ở chương 2, phần phân hoạch node nhằm mục đích mở rộng cây nhị phân, và qua đó tác động

đến số phép duyệt để tìm ra cách sắp xếp tối ưu của thuật toán. Bởi vậy, nếu giảm được số cách

mở rộng cây nhị phân ở phần phân hoạch node cũng đồng nghĩa với việc giảm thời gian tính

toán của toàn bộ APL.

Thuật toán APL được đưa ra cho thấy rằng, số cách chèn một node vào một cây nhị phân

17

CHƯƠNG 4: GIẢI PHÁP

có n node "nội" (internal - các node phía trong) và n+1 nodes lá là (2*n + 1)*4. Nhưng, thực tế,

số cách chèn này nhỏ hơn, chỉ là 6*n + 4. Ta có thể thấy rõ điều này qua việc phân tích ví dụ

sau:

Ta xét cây nhị phân có 3 nodes "nội", và 4 nodes lá có dạng (1V2)H(3V4). Khi đó:

• Đối với các node lá. Với mỗi lá (1, 2, 3, 4) ta có 4 cách để chèn node 5 vào cây. Ví dụ: khi

chèn node 5 vào vị trí node lá số 1: (1V5)V2... , (5V1)V2..., (1H5)V2..., (5H1)V2....

• Nhưng công thức trên không đúng cho mỗi node "nội". Ví dụ, xét với vị trí node V trong

cây con (1V2). Nếu theo công thức trên ta sẽ có cách chèn như sau: ((1V2) H 5) H (3V4);

((1V2) V 5) H (3V4); (5 V (1V2)) H (3V4); (5 H (1V2)) H (3V4). Nhưng thực tế, ta

nhận thấy các cách chèn như trên sẽ lặp lại cách chèn mà ta đã xét với các nodes lá. Ví

dụ: ((1V2) V 5)... sẽ trùng với 1V(2V5)... (cách chèn với đối với node lá số 2); và 5 V

(1V2)... sẽ trùng với (5V1)V2... (cách chèn với node lá số 1). Vì thực chất, khi biểu diễn

dàn trang, thì (1V2) V 5 và 1 V (2V5) là như nhau. Vậy với mỗi nodes "nội" , số cách

chọn để chèn giảm xuống chỉ còn 2 cách chứ không phải là 4 so với các node lá.

Vậy, số cách để chèn 1 node vào cây nhị phân n nodes và (n+1) lá thực sự chỉ còn lại là:

n*2 + (n+1)*4 = 6*n+4.

4.2.2 Thay thế cây nhị phân

Một trong những thành phần cơ bản của APL chính là xây dựng cây nhị phân thể hiện các

khối hình. Khi cài đặt thuật toán, mỗi node của cây nhị phân sẽ cần tới hai con trỏ. Mặt khác,

trong khi số các phép duyệt, hay chèn thêm node mới vào cây nhị phân cũng chiếm khá nhiều

thời gian và bộ nhớ (do tăng theo hàm số mũ). Bởi vậy, khi triển khai APL trên các thiết bị có

tốc độ xử lý và bộ nhớ hạn chế như TBDĐ cũng gây ra những ảnh hưởng đáng kể tới hiệu suất.

Nhận thấy rằng, việc sử dụng cây nhị phân trong thuật toán APL thực chất chỉ nhằm lưu

trữ và thể hiện cách sắp xếp các khối hình theo dạng (1V2)H(3H4)... mà trong đó, có thể coi H,

V như là hai phép toán số học được định nghĩa riêng. Điều này gợi ý cho tôi đề xuất hướng tiếp

18

CHƯƠNG 4: GIẢI PHÁP

cận mới. Thay vì sử dụng cây nhị phân, ta có thể sử dụng các xâu để biểu diễn các khối hình

theo dạng (1V2)H(3V4)... như trên. Các node 1, 2, 3, 4 đơn thuần chỉ là các định danh giúp ta

ánh xạ tới các khối hình có kích cỡ thực, chứ không chứa các thông tin của khối hình như trong

cây nhị phân (điều này cũng giúp giảm đáng kể việc sử dụng bộ nhớ khi cài đặt). Các tiến trình

chèn một khối hình (node) vào trang (layout) sẽ được thực hiện bằng cách duyệt xâu. Cụ thể,

xem xét ví dụ sau:

Xét với cách dàn trang cho trước là (1V2)H(3H(4V5). Công việc của chúng ta là chèn

node 6 vào cách dàn trang này. Nên chú ý rằng, các node 1, 2, 3, 4, 5 tương ứng với các node lá

trong cây nhị phân và các node V, H tương ứng với các node "nội" trong cây nhị phân. Khi đó:

• Tương ứng với việc chèn node 6 vào một node "nội" đối với cây nhị phân, chúng ta sẽ tiến

hành chèn node 6 và thêm hai kí hiệu mở ngoặc "(" và đóng ngoặc ")". Ví dụ, tương ứng

với việc chèn node 6 vào node "nội" V thứ nhất (node V bên trái), ta sẽ có ba cách chèn

vào xâu ở trên như sau: ((1 V 2) H 6) H (3 H (4 V 5)); ((1 V 2) V 6) H (3 H (4 V 5)) hoặc

(6 H (1 V 2)) H (3 H (4 V5)). (Các kí tự in đậm là các kí tự được chèn thêm vào). Chú ý

rằng, như ở phần nói về Phân hoạch node đã nói ở trên, thì cách sắp xếp (6 V (1 V2)) H

(3 H (4 V5)) sẽ trùng với ((1 V 2) V 6) H (3 H (4 V 5)).

• Tương ứng với việc chèn node 6 vào một node node lá đối với cây nhị phân, chúng ta sẽ

tiến hành thay thế các node lá trong xâu bởi chính node đó kết hợp thêm node 6. Ví dụ,

tương ứng với việc chèn node 6 vào node lá 2, ta sẽ thay node 2 bằng (2H6), (6H2) hoặc

(2V6). Khi đó ta có các cách chèn vào xâu ở trên như sau: (1 V (2 H 6)) H (3 H (4 V 5));

(1 V (2 V 6)) H (3 H (4 V 5)) hoặc (1 V (6 H 2)) H (3 H (4 V 5)). (Các kí tự in đậm là

các kí tự được chèn thêm vào).

Tiếp theo là tiến trình về duyệt các cách dàn trang, tính toán đánh giá để tìm ra cách dàn

trang tốt nhất. Chúng ta coi các xâu trên như các biểu thức số học với hai phép tính H, V và tiến

hành tính "score" như là tính giá trị của một biểu thức số học bình thường. Để thực hiện điều

1

này, chúng ta sẽ cần sử dụng thuật toán "infix to postfix" để chuyển các xâu ở trên về dạng

¹Thuật toán nhằm chuyển cách biểu diễn từ trung tố sang hậu tố, sẽ được trình bày cụ thể ở phần phụ lục A.1

19

CHƯƠNG 4: GIẢI PHÁP

biểu thức "postfix" (hậu tố). Ví dụ, xâu (1V2)H(3H(4V5) sẽ tương ứng với xâu 12V345VHH ở

dạng "postfix". Tuy việc chuyển đổi "infix to postfix" cũng như tính toán biểu thức đòi hỏi phải

cài đặt các ngăn xếp (stack) nhưng độ phức tạp và sử dụng bộ nhớ sẽ giảm đi đáng kể so với

việc sử dụng cây nhị phân.

4.3 Tối ưu về mặt giao diện người dùng

4.3.1 Sử dụng tỉ lệ tương đối

APL là phương pháp xây dựng layout mà không thay đổi tỉ lệ (chiều dài : chiều rộng) của

các khối hình. Tuy có thể giữ được hình ảnh thực của các khối hình, nhưng nó cũng tạo ra nhiều

"không gian chết" - khoảng diện tích không được che phủ bởi các khối hình. Để cân bằng vấn

đề về yêu cầu giao diện và tính tôn trọng kích cỡ thực của các khối hình, trong khóa luận này,

tôi đề xuất thay đổi APL theo hướng cho phép thay đổi tỉ lệ của các khối hình (chiều dài : chiều

rộng) trong một khoảng chấp nhận được.

4.3.2 Kéo dãn khối hình

APL xây dựng dàn trang (layout) dựa vào quan hệ phân cấp và tỉ lệ kích cỡ giữa các node.

Bởi thế, xảy ra hiện tượng "không gian chết". Để hiểu rõ, chúng ta xem xét với trường hợp mô

tả cách sắp xếp trong biểu đồ 4.3 (với 6 khối hình 1, 2, 3, 4, 5, 6).

Hình trái mô tả cách sắp xếp dàn trang các khối hình. Hình phải mô tả cách tổ chức các

node theo quan hệ phân cấp. Trong hình trái, hình bao của khối hình 5 và 6 chính là thể hiện

tương ứng với node V₂trong biểu đồ bên phải, tương tự với V₁, H₁, H₂, V₀. Để ý thấy rằng, do

diện tích của khối hình 3và khối hình 4 bằng nhau, dẫn đến kích thước của node 3 và node 4

trong dàn trang là như nhau. Tuy vậy, kích cỡ (chiều dài, chiều rộng) của hai khối hình này lại

có sự sai khác, điều này dẫn đến việc có "không gian chết".

Để giải quyết vấn đề này, tôi sẽ bổ sung quá trình "hậu xử lý" vào thuật toán APL. Sau

20