Khóa luậ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 2.1 Adaptive Page Layout . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 2.2 Thư viện ZUI Cippolo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.2.1 Kiến trúc Cippolo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 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 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 . . . . . . . . . . . . . . . . . . . . . . . . . . . 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 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 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 Health 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 Zoomable User 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, ... 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à (a1, r1), (a2, r2), (a3, r3), .... , (aN , rN ) 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′ 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 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: SN = ∑N i=1 ai apbb ∗ min{rpbb, rpage} max{rpbb, rpage} (1) Với: + ai là diện tích tương đối của khối hình thứ i + rpage là cạnh của trang cho trước + apbb , rpbb 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 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 ∗ Sk (2) Trong đó: – Sk đã đượ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 mi) ∗ k∑ i=1 Vi] (3) Với: Vi 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; mk 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 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 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 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 (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 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 này, chúng ta sẽ cần sử dụng thuật toán "infix to postfix" 1 để chuyển các xâu ở trên về dạng 1Thuậ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 V2 trong biểu đồ bên phải, tương tự với V1, H1, H2, V0. Để ý 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 CHƯƠNG 4: GIẢI PHÁP Hình 4.3: Mô hình xây dựng dàn trang khi thực hiện APL (cũ), dựa vào cách sắp xếp, tọa độ cũng như kích cỡ cụ thể của các khối hình, quá trình "hậu xử lý" sẽ tiến hành kiểm tra "không gian chết" và kéo dãn (vẫn giữ nguyên tỉ lệ) các khối hình so với các khối hình xung quanh. Qua kiểm thử, quá trình "hậu xử lý" cho thấy giảm đáng kể không gian chết. 21 CHƯƠNG 5 Thực nghiệm - Demo 5.1 Thực nghiệm Sau khi đưa ra các giải pháp tối ưu, chúng tôi sẽ tiến hành cài đặt APL và tiến hành kiểm thử. Với các kết quả thực nghiệm này sẽ đánh giá hiệu quả của các giải pháp này. Môi trường tiến hành kiểm thử: PC: Celeron 2.8 GHz, RAM 512 MB Hệ điều hành: Ubuntu 8.10 Trình dịch: GCC/G++ Bảng 5.1: Kết quả test thời gian thực thi (milli giây) STT Số block Trước khi tối ưu Sau khi tối ưu 1 5 0 0 2 8 10 10 3 10 10 10 4 20 40 40 5 40 320 310 6 60 1140 1020 7 80 2750 2390 8 100 5490 4820 Nhìn vào kết quả kiểm thử về thời gian được thể hiện qua đồ thị ??, ta có thể thấy rằng với số khối hình (block) nhỏ thì việc tối ưu không thực sự mang lại sự khác biệt. Tuy vậy, khi số block tăng lên (với số khối hình từ 40 trở lên) thì thời gian của thuật toán có 22 CHƯƠNG 5: THỰC NGHIỆM - DEMO Hình 5.1: Đồ thị thời gian thực thi của chương trình trước và sau khi tối ưu sự giảm xuống đáng kể. Bảng 5.2: Kết quả test diện tích che phủ (%) STT Số block Trước khi tối ưu Sau khi tối ưu 1 4 63.6 70.59 2 5 41.54 56.39 3 6 74.82 82.97 4 7 74.13 85.12 5 8 71.04 76.05 6 9 77.59 82.43 7 10 83.69 87.98 8 15 84.39 90.66 9 20 85.67 90.41 10 25 83.48 89.34 11 30 83.72 90.23 12 35 85.48 91.06 13 40 84.5 91.76 14 45 83.23 88.06 15 50 88.04 92.75 16 55 86.77 92.3 17 60 84.12 90.44 18 65 84.22 90.16 19 70 85.28 91.24 Qua đồ thị 5.2 thể hiện tỉ lệ phần trăm diện tích che phủ của chương trình trước và sau 23 CHƯƠNG 5: THỰC NGHIỆM - DEMO Hình 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 khi tối ưu, đã cho thấy rằng, tính "thẩm mỹ", giao diện người dùng của chương trình đã được cải thiện đáng kể. Tuy với các dữ liệu khác nhau thì có sự thay đổi trong hiệu quả mang lại, nhưng nhìn chung, các giải pháp tối ưu về mặt giao diện đã mang lại kết quả khả quan. Ngoài ra, các giải pháp và kết quả thực nghiệm này cũng đã được kiểm chứng và có sự đồng thuận từ phía Toshiba. Những kết quả này đã được phát triển thành bài báo mang tên "Implementing adaptive page layout algorithm on embedded devices" [14] tại hội nghị KSE 2009. 5.2 Health Data Visualization Ngoài việc tối ưu, phát triển APL, trong khóa luận này, chúng tôi sẽ tiến hành phát triển một số ứng dụng có sử dụng thuật toán này như là minh chứng ý nghĩa thực tiễn của nó. Một trong những ứng dụng đó là chương trình: Trực quan hóa dữ liệu kiểm tra sức khỏe (Health Examination Data Visualization - HEDV). HEDV là một trong những dự án của phòng thí nghiệm Toshiba - Coltech. Mục đích của HEDV là nhằm đưa ra mô hình trực quan nhất cho các số liệu kiểm tra sức 24 CHƯƠNG 5: THỰC NGHIỆM - DEMO khỏe, qua đó cho thấy cái nhìn tổng thể về tình hình sức khỏe của người sử dụng. Mục tiêu của dự án là có thể triển khai HEDV trên cả PC và TBDĐ. 5.2.1 Tóm tắt đặc tả yêu cầu phần mềm HEDV sử dụng Adaptive Page Layout như một module (biểu đồ 5.3) . Hình 5.3: Kiến trúc tổng quát của HEDV Biểu đồ ca sử dụng Người dùng có thể xem các thông tin trong các dữ liệu kiểm tra sức khỏe. Người dùng cũng có thể tùy biến dữ liệu theo mục đích tìm kiếm thông tin của mình (có thể lọc, thay đổi tính tương quan của dữ liệu, . . . ). Hơn nữa, hệ thống cũng cho phép người dùng thực hiện các chức năng về trực quan hóa dữ liệu (phóng to, thu nhỏ, thay đổi kiểu mô hình, . . . ) (biểu đồ 5.4). 25 CHƯƠNG 5: THỰC NGHIỆM - DEMO Hình 5.4: Mô hình ca sử dụng (usecase) của HEDV Kịch bản hoạt động Kịch bản hoạt động được mô tả cụ thể qua bảng 5.3. Các yêu cầu chức năng • Dữ liệu đầu vào: Là các dữ liệu về kiểm tra sức khỏe do phía Toshiba cung cấp. (Cụ thể, xem phụ lục) • Xử lý: - Đọc dữ liệu từ tệp CSV, tiến hành chuẩn hóa dữ liệu - Định nghĩa các hình chữ nhật ban đầu (các mô hình dùng để trực quan hóa dữ liệu) theo đường chéo và theo Treemap. - Tiến hành tô màu các mục trong các hình chữ nhật. • Đầu ra: Giao diện chương trình bao gồm phần hiển thị chính bên trái thể hiện kết quả của việc trực quan hóa. Phần trên cùng bên phải là các tùy chọn để người dùng tùy biến dữ liệu (hình 5.6). Các giới hạn, ràng buộc • Hệ điều hành: nền tảng Window và Linux. Trong khóa luận này, tôi sẽ đề cập chi tiết đến việc phát triển hệ thống trên nền Linux. 26 CHƯƠNG 5: THỰC NGHIỆM - DEMO Bảng 5.3: Kịch bản hoạt động Tác nhân Hành động Mô tả Đầu tiên, người dùng chỉ định cơ sở dữ liệu hoặc tệp dữ liệu chứa dữ liệu kiểm tra sức khỏe và hệ thống sẽ đọc những dữ liệu này. Thứ hai, người dùng sẽ chọn mục và tỉ lệ của chúng, hệ thống sẽ lọc dữ liệu dựa theo những phần này. Tiếp theo, khi người dùng nhấn vào chức năng trực quan hóa, mỗi bản ghi dữ liệu được mô hình hóa thành một hình chữ nhật ban đầu, cỡ và tọa độ vị trí của những hình chữ nhật ban đầu này đươc tính toán bởi thuật toán Adaptive Page Layout. Cuối cùng, các hình chữ nhật này sẽ được tô màu và hiển thị lên màn hình. Điều kiện tiên quyết Phải tồn tại dữ liệu kiểm tra sức khỏe và có thể đọc được. Điều kiện kết thúc Tất cả các dữ liệu phải được trực quan hóa lên màn hình hiển thị Kịch bản chính Các bước Tác nhân Hành động Đọc dữ liệu Người dùng Chọn tệp dữ liệu để đọc Hệ thống Đọc các bản ghi từ tệp dữ liệu Hệ thống Chuẩn hóa dữ liệu Tùy biến dữ liệu Người dùng Chỉ định mục và tỉ lệ để trực quan hóa Hệ thống Lọc dữ liệu Trực quan hóa Người dùng Chọn chức năng trực quan hóa Hệ thống Định nghĩa các hình chữ nhật ban đầu và chuyển chúng đến module Adap- tive Page Layout để tính toán vị trí và cỡ của mỗi hình trên màn hình hiển thị Hệ thống Tô màu các hình chữ nhật với các mục trong bản ghi Hệ thống Hiển thị các hình chữ nhật ra màn hình • Phần cứng: Hỗ trợ chạy trên PC với CPU 1.0GHz và bộ nhớ 512MB. • Ngôn ngữ lập trình: C++ (với nền Linux), C# (với nền Window) 27 CHƯƠNG 5: THỰC NGHIỆM - DEMO (a) Theo đường chéo (b) Theo treemap Hình 5.5: Cách chia các mục trong mỗi hình chữ nhật (sử dụng trong HEDV) Hình 5.6: Giao diện HEDV được yêu cầu (cung cấp bởi phía Toshiba) 5.2.2 Các bước phát triển hệ thống Hệ thống được phát triển qua các bước sau: 28 CHƯƠNG 5: THỰC NGHIỆM - DEMO - Phân tích cơ sở dữ liệu về sức khỏe - Cài đặt thuật toán APL vào ứng dụng trực quan hóa dữ liệu sức khỏe trên môi trường Linux - Sử dụng môi trường đồ họa WideStudio để xây dựng giao diện đồ họa trên Linux. - Kiểm thử với các dữ liệu thực và xem xét thời gian chạy, bộ nhớ sử dụng với số bản ghi dữ liệu tăng lên. 5.2.3 Kiến trúc chương trình Thuật toán APL được cài đặt như một module và được sử dụng bởi hệ thống. Khi phát triển hệ thống HEDV, chúng tôi có cài đặt sử dụng thêm thư viện ZUI đó là Cippolo nhằm hỗ trợ người dùng trong việc "zoom" các dữ liệu. Và, cài đặt thuật toán Treemap để sinh ra cấu trúc treemap cho các mục trong mỗi hình chữ nhật. Giao diện đồ họa của chương trình được xây dựng bởi WideStudio. Cũng cần nhấn mạnh rằng, thời gian để nhóm nghiên cứu làm quen với môi trường đồ họa này là khá ngắn, bởi vậy cũng nảy sinh khá nhiều khó khăn để xây dựng, phát triển hệ thống ứng dụng này. Thiết kế của hệ thống được thể hiện qua biểu đồ gói trong hình 5.7. 5.2.4 Demo chương trình Kết quả kiểm thử Với môi trường tiến hành kiểm thử: PC: Celeron 2.8 GHz, RAM 512 MB Hệ điều hành: Debian 2.6 Kết quả kiểm thử được thống kê trong bảng 5.4. Qua đồ thị 5.8, ta có thể nhận thấy, khi tăng số lượng bản ghi dữ liệu thì kéo theo thời gian xử lý tăng nhưng không ảnh hưởng đáng kể tới dung lượng bộ nhớ sử dụng. Điều này cho thấy, sự tiêu tốn bộ nhớ sinh ra khi có sự tải các bản ghi cần thiết vào bộ 29 CHƯƠNG 5: THỰC NGHIỆM - DEMO Hình 5.7: Biểu đồ thiết kế hệ thống HEDV Hình 5.8: Đồ thị kết quả kiểm thử HEDV nhớ còn các bản ghi chưa (hoặc không) sử dụng sẽ không được cấp phát bộ nhớ. Qua các số liệu kiểm thử cho thấy, các giải pháp tối ưu về bộ nhớ trong trường hợp này tỏ ra 30 CHƯƠNG 5: THỰC NGHIỆM - DEMO Bảng 5.4: Kết quả kiểm thử demo chương trình STT Số bản ghi Thời gian (mili giây) Bộ nhớ (MB) 1 5 0 1.2 2 10 0 1.2 3 20 20 1.2 4 50 230 1.2 5 100 1540 1.3 6 150 5360 1.3 7 200 12470 1.3 8 250 26270 1.4 9 300 46230 1.4 10 350 76090 1.4 11 400 111230 1.4 12 450 162870 1.4 13 500 223160 1.4 thực sự hiệu quả. Ngoài ra, cũng cần để ý rằng, khi số bản ghi tăng nhưng không vượt quá 350 thì thời gian thực thi có tăng nhưng không đáng kể. Đây là cũng là kết quả khá khả quan về việc tối ưu tốc độ xử lý. Một số hình ảnh về giao diện của chương trình Hình 5.9 thể hiện giao diện chính của chương trình. Chi tiết, có thể xem phần Phụ lục để hiểu rõ các tính năng cũng như cách sử dụng. (a) Theo đường chéo (b) Theo treemap Hình 5.9: Demo chương trình HEDV 31 CHƯƠNG 6 Kết luận và hướng phát triển 6.1 Kết luận Trong khóa luận này, chúng tôi đã trình bày các phương pháp tối ưu thuật toán Adaptive Page Layout trên hệ thống PC: Giảm số phân hoạch node, Thay thế cây nhị phân, Kéo giãn khối hình hay Sử dụng tỉ lệ tương đối. Qua các demo và kết quả thực nghiệm đã chứng tỏ tiềm năng của những phương pháp này. Đây chính là tiền đề cho việc triển khai và tối ưu tiếp trên hệ thống nhúng (ARM). Mặt khác, chúng tôi cũng hi vọng các phương pháp tối ưu APL mà chúng tôi đề xuất cùng với những kết quả thực nghiệm có được sẽ tạo điều kiện cho những nhóm nghiên cứu quan tâm tới vấn đề này có cơ sở tiến hành so sánh, đánh giá và hoàn thiện phương pháp của mình. 6.2 Một số hướng phát triển Qua khóa luận này, cũng cho thấy việc tối ưu thuật toán Adaptive Page Layout không những mang lại ý nghĩa quan trọng trong các bài toán về dàn trang trên thiết bị di động mà còn có ý nghĩa đối với các bài toán sẽ được xây dựng tại phòng thí nghiệm trong giai đoạn tới. Trong tương lai, khi kết quả tối ưu được cải thiện, chúng tôi sẽ tiếp tục nghiên cứu phát triển đối với 32 CHƯƠNG 6: KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN các bài toán mô hình hóa dữ liệu trên nền tảng 3D và một số bài toán liên quan khác. 33 PHỤ LỤC A Phụ lục A.1 Thuật toán chuyển đổi từ trung tố sang hậu tố (infix to postfix) Trong đại số thông thường, chúng ta sử dụng các kí hiệu ở dạng trung tố như a+b*c. Biểu thức với các kí hiệu được biểu diễn ở dạng hậu tố tương ứng sẽ là abc*+. Thuật toán chuyển từ trung tố sang hậu tố được tiến hành như sau: • Quét xâu trung tố từ trái qua phải • Khởi tạo một ngăn xếp rỗng • Nếu kí tự được quét là một toán hạng, thêm nó vào trong xâu hậu tố. Nếu kí tự được quét là một toán tử và ngăn xếp rỗng thì sẽ đẩy kí tự đó vào ngăn xếp. – Nếu kí tự được quét là một toán hạng và ngăn xếp không rỗng thì so sánh quyền ưu tiên (ví dụ, phép nhân có quyền cao hơn phép cộng) của kí tự với phần tử ở đỉnh ngăn xếp (topStack). Nếu topStack có quyền ưu tiên cao hơn kí tự đã được quét thì đẩy nó ra khỏi ngăn xếp, ngược lại, đẩy kí tự đã quét vào ngăn xếp. Lặp lại bước này trong khi ngăn xếp không rỗng và topStack có quyền ưu tiên cao hơn kí tự được 34 PHỤ LỤC A: PHỤ LỤC quét. Lặp lại bước này cho đến khi tất cả các kí tự được quét. • Sau khi tất cả các kí tự đã được quét, chúng ta phải thêm mọi kí tự có thể có tới xâu hậu tố. Nếu ngăn xếp không rỗng, thêm topStack vào xâu hậu tố và đẩy ra khỏi ngăn xếp. Lặp lại bước này trong khi ngăn xếp chưa rỗng. • Trả về xâu hậu tố. Để hình dung rõ hơn thuật toán thực hiện thế nào, chúng ta xét ví dụ với xâu trung tố: a+b*c-d. Quá trình thuật toán được mô tả qua hình A.1 Hình A.1: Quá trình thực thi thuật toán "infix to postfix" 35 PHỤ LỤC A: PHỤ LỤC A.2 Mẫu bản ghi dữ liệu sức khỏe do phía Toshiba cung cấp Bảng A.1: Giá trị chuẩn của dữ liệu kiểm tra sức khỏe Item Standard value UnitLower limit Upper limit BMI 18.5 25 . . . BPT (Blood pressure top number) . . . 140 mmHG BPB (Blood pressure bottom number) . . . 80 mmHG WBC (white blood cell) 3000 10000 /ul GOT (AST) . . . 40 IU/I GPT (ALT) . . . 40 IU/I r-GTP . . . 80 IU/I T.CH 100 220 Mg/dl NF (Neutral fat) 20 150 Mg/dl HDL-C (HDL-Cholesterol) 40 . . . Mg/dl LDL-C (LDL-Cholesterol) . . . 140 Mg/dl UC (Uric acid) . . . 7.0 Mg/dl BS (Blood sugar) 60 110 Mg/dl HbA1c . . . 5.8 % A.3 Demo chương trình hiển thị ảnh Đây là một demo ứng dụng đơn giản cho phép người dùng hiện các tập ảnh được lưu trữ ra màn hình hiển thị theo cách dàn trang tốt nhất. Chương trình đơn thuần sử dụng APL và thư viện xử lý ảnh OpenCV. A.4 Phiên bảnHEDV chúng tôi phát triển trên nền tảngWin- dow Cửa sổ chính hiển thị danh sách các menu, các thành phần quản lý để tùy biến hiển thị của dữ liệu. Để nhập dữ liệu khám sức khỏe, người dùng sử dụng File menu. Người dùng cũng có thể hiển thị dữ liệu của mỗi khối hình (sau khi đã được trực quan hóa) khi sử dụng Tool menu, 36 PHỤ LỤC A: PHỤ LỤC Hình A.2: Giao diện demo chương trình hiển thị ảnh rồi chọn View selected block hoặc đúp chuột trực tiếp lên khối hình trong màn hình hiển thị. Dữ liệu của mỗi khối hình sẽ được hiển thị dưới dạng sau (hình A.5) Người dùng có thể hiển thị danh sách màu tương ứng với các mục dữ liệu sức khỏe bằng cách chọn Show Items Colors form. Để phóng to hay thu nhỏ các khối hình, người dùng có thể chọn kiểu "zoom" trên thanh menu. Tương ứng, Zoom In - dể phóng to, Zoom Out - để thu nhỏ. Người dùng cũng có thể lựa chọn các mục dữ liệu được liệt kê trong combo box, khi đó, dữ liệu hiển thị sẽ được tổ chức lại để tương quan với giá trị chuẩn hóa dựa vào mục đã được chọn (hình A.6). Để thay đổi cách hiển thị các mục dữ liệu trong mỗi khối hình, người dùng cần chọn kiểu hiển thị trong combo box ở mục Display types. "Diagonal" để hiển thị theo đường chéo, "Squarified" để hiển thị theo Squarified treemap. Kích cỡ của mỗi khối hình con này sẽ tương 37 PHỤ LỤC A: PHỤ LỤC Hình A.3: Demo HEDV phiên bản trên Window với các mục được chia theo đường chéo ứng với độ lớn của các số liệu thuộc các mục này. Mặt khác, trong phần Show sub items cho phép người dùng tùy chọn để hiển thị những mục cần thiết trong mỗi khối hình (hình A.7) Sau khi chọn một khối hình, người dùng có thể tùy biến diện tích hiển thị bằng việc lọc các dữ liệu dựa trên giá trị của khối hình đã chọn. Đồng thời, người dùng có thể thay đổi, việc lọc các mục dữ liệu bằng cách chọn mục để lọc trong combo box (hình A.8), 38 PHỤ LỤC A: PHỤ LỤC Hình A.4: Demo HEDV phiên bản trên Window với các mục được chia theo treemap Hình A.5: Chức năng hiển thị khối hình trong HEDV 39 PHỤ LỤC A: PHỤ LỤC Hình A.6: Chức năng chọn mục dữ liệu trong HEDV Hình A.7: Chức năng tùy chọn hiển thị trong HEDV 40 PHỤ LỤC A: PHỤ LỤC Hình A.8: Chức năng chọn lọc dữ liệu trong HEDV 41 Tài liệu tham khảo [1] Cliff Brake. Power management in portable arm based systems. [2] Michael Huch. Ambient assisted living preparation of new european initiative for it sup- ported solutions. Technical report. [3] A. Girgensohn S. Uchihashi, J. Foote and J. Boreczky. Video manga: Generating seman- tically meaningful video summaries. ACM Press, 1999. [4] Ji-RongWenWei-YingMaDeng Cai, Shipeng Yu. Vips: a vision-based page segmentation algorithm. Technical report, Microsoft Research - Microsoft Corporation, 2003. [5] Amit Madaan Srinivasan H Sengamedu, Rupesh R Mehta. Web page layout optimization using section importance. 2009. [6] David H. Salesin Charles Jacobs, Wilmot Li. Adaptive document layout via manifold content. [7] Takashi MORIMOTO Xinxiao LI*, Yoshifumi TAKAYAMA. Adaptive page layout for ordered blocks. 2008. [8] OpenGL ES Common Profile Specification Version 2.0.24 (Full Specification). 2009. [9] ARM System Developers Guide-Designing and Optimizing System Software. Morgan Kaufmann, 2004. [10] URL 42 TÀI LIỆU THAM KHẢO [11] Kees Huizing Mark Bruls and Jarke J. van Wijk. Squarified treemaps. 1999. [12] Intel Corporation. Open Source Computer Vision Library. Intel Corporation. [13] Đinh Mạnh Tường. Cấu trúc dữ liệu và giải thuật. Đại học Quốc Gia Hà Nội, 2008. [14] Viet-Ha Nguyen Vu Quang Dung, Xinxiao Li. Implementing adaptive page layout algo- rithm on embedded devices. In KSE2009. 43