Tài liệu 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 interaction 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 algorithm 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 environment. 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 OpenCV . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.3 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.3 4.2.1 Phân hoạch node . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 4.2.2 Thay thế cây nhị phân . . . . . . . . . . . . . . . . . . . . . . . . . . 18 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 1 2 3 4 5 Từ hoặc cụm từ Từ viết tắt Adaptive Page Layout APL Personal Computer PC Health Examination Data Visu- HEDV alization Thiết bị di động TBDĐ Zoomable User Interface ZUI Bảng 1: Bảng từ viết tắt ix Chú thích Dàn trang mang tính thích ứng Máy tính cá nhân Hệ thống trực quan hóa dữ liệu kiểm tra sức khỏe Giao diện người dùng hỗ trợ "zoom" 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 , r1′ ), (a′2 , r2′ ), (a′3 , r3′ ), .... , (a′N , rN ). Tiếp theo, 4 khối hình chữ nhật có diện tích lớn nhất (a′1 , r1′ ), (a′2 , r2′ ), (a′3 , r3′ ) và (a′4 , r4′ ) 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 = PN 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). Ŝ = η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) X X 1 ηk = exp[ ∗ (α + mi ) ∗ Vi ] k i=1 i=1 k k (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