Đề tài ỨNG DỤNG CÁC NGUYÊN TẮC SÁNG TẠO TRONG XÂY DỰNG THUẬT TOÁN TÍNH SỐ BƢỚC CHÂN TRÊN iPHONE

ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH TRƢỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN ------------------------------------ PHƢƠNG PHÁP NGHIÊN CỨU KHOA HỌC TRONG TIN HỌC ỨNG DỤNG CÁC NGUYÊN TẮC SÁNG TẠO TRONG XÂY DỰNG THUẬT TOÁN TÍNH SỐ BƢỚC CHÂN TRÊN iPHONE. GVHD : GS. TSKH. HOÀNG KIẾM Học viên: Lê Anh Tú (1211078 – Cao học KHMT K22) LỜI CÁM ƠN Em xin gửi lời cám ơn chân thành đến thầy GS.TSKH Hoàng Kiếm đã tận tình giảng dạy và hướng dẫn em trong suốt thời gian học chuyên đề này. Em đã không thể hoàn thành đề tài nếu như không có sự giúp đỡ, các lời góp ý của các bạn bè cũng như sự động viên tinh thần của gia đình và người thân. Mặc dù nhóm đã có nhiều cố gắng trong quá trình thực hiện đề tài, nhưng do kinh nghiệm và thời gian còn hạn chế nên đề tài không thể tránh được thiếu sót. Vì vậy em rất mong nhận được sự chỉ bảo của thầy cô và sự đóng góp ý kiến của các bạn để đề tài được hoàn thiện hơn. Em xin chân thành cám ơn. Học viên thực hiện Lê Anh Tú MỤC LỤC LỜI CÁM ƠN .................................................................................................................... 2 MỞ ĐẦU ............................................................................................................................. 5 TỔNG QUAN ..................................................................................................................... 6 Chƣơng I: LÝ THUYẾT VÀ THỰC NGHIỆM ............................................................. 7 1. Cảm biến .................................................................................................................... 7 1.1 Khái niệm về cảm biến ....................................................................................... 7 1.2 Đặc điểm của cảm biến ....................................................................................... 7 1.3 Một số loại cảm biến trên smartphone ............................................................... 7 1.4 Ứng dụng phổ biến của cảm biến ....................................................................... 8 2. Xử lý tín hiệu cảm biến ............................................................................................. 9 2.1 Giới thiệu bộ lọc Kalman ................................................................................... 9 2.2 Xử lý tín hiệu từ gia tốc kế ............................................................................... 12 2.3 Phương pháp tính số bước chân từ tín hiệu của gia tốc kế ............................... 14 2.4 Kết quả đạt được ............................................................................................... 17 Chƣơng II: ỨNG DỤNG NGUYÊN TẮC SÁNG TẠO TRÊN SỰ PHÁT TRIỂN CẢM BIẾN VÀ TRONG QUÁ TRÌNH THỰC HIỆN ................................................ 19 1. Ứng dụng nguyên tắc sáng tạo trên sự phát triển của cảm biến: ............................. 19 1.1 Nguyên tắc phân nhỏ: ....................................................................................... 19 1.2 Nguyên tắc phẩm chất cục bộ: .......................................................................... 19 1.3 Nguyên tắc kết hợp: .......................................................................................... 20 1.4 Nguyên tắc vạn năng: ....................................................................................... 20 1.5 Nguyên tắc năng động: ..................................................................................... 20 1.6 Nguyên tắc rẽ thay cho đắt: .............................................................................. 21 1.7 Nguyên tắc thay thế sơ đồ cơ học: .................................................................... 21 1.8 Nguyên tắc sử dụng vật liệu tổng hợp: ............................................................. 22 2. Ứng dụng nguyên tắc sáng tạo trong quá trình thực hiện: ...................................... 22 2.1 Nguyên tắc phân nhỏ: ....................................................................................... 22 2.2 Nguyên tắc “tách khỏi”: ................................................................................... 22 2.3 Nguyên tắc phẩm chất cục bộ: .......................................................................... 23 2.4 Nguyên tắc kết hợp: .......................................................................................... 23 2.5 Nguyên tắc vạn năng: ....................................................................................... 23 2.6 Nguyên tắc gây ứng xuất sơ bộ: ....................................................................... 24 2.7 Nguyên tắc thực hiện sơ bộ: ............................................................................. 24 2.8 Nguyên tắc năng động: ..................................................................................... 24 2.9 Nguyên tắc sử dụng trung gian: ........................................................................ 25 2.10 Nguyên tắc đổi màu: ......................................................................................... 25 Chƣơng III: ỨNG DỤNG NGUYÊN TẮC SÁNG TẠO ĐƢA RA NHỮNG HƢỚNG PHÁT TRIỂN CHO ĐỀ TÀI .......................................................................................... 26 KẾT LUẬN ...................................................................................................................... 27 TÀI LIỆU THAM KHẢO ............................................................................................... 28 MỞ ĐẦU Lý do chọn đề tài Hiện nay, điện thoại di động ngày càng trở nên phổ biến và được sử dụng rất rộng rãi. Trong những năm gần đây, smartphone ngày càng được các hãng sản xuất điện thoại di động chú trọng phát triển, với cấu hình phần cứng ngày càng mạnh mẽ và được tích hợp các công nghệ cảm biến tiên tiến. Cảm biến trên smartphone được ứng dụng rộng rãi và chủ yếu được dùng để điều khiển các ứng dụng trò chơi. Tuy nhiên, các cảm biến trên smartphone còn có rất nhiều ứng dụng chưa được khai thác hết. Do đó, em quyết định chọn đề tài mình đã thực hiện “Xây dựng thuật toán tính số bước chân trên iPhone” nhằm tìm hiểu và phân tích các nguyên tắc sáng tạo được sử dụng trong quá trình thực hiện. (Bài báo "A high-accuracy step counting algorithm for iPhones using Accelerometer " của nhóm đã được chấp nhận ở ISSPIT 2012 vừa qua ) Đối tƣợng và phạm vi nghiên cứu Đối tượng nghiên cứu chính của em là loại cảm biến phổ biến trên iPhone là: gia tốc kế. Phương pháp phân tích và nhận biết hành động bằng tín hiệu gia tốc kế; và cách ứng dụng của cảm biến trên điện thoại. Trong đó, phạm vi nghiên cứu của nhóm tập trung vào cách sử dụng và ứng dụng cảm biến trên iPhone. TỔNG QUAN Việc khai thác ứng dụng của cảm biến đã được đề cập từ rất lâu. Trong bài báo "Activity Recognition from User-Annotated Acceleration Data" (1), 2 tác giả Ling Bao và Stephen S. Intille đã ứng dụng gia tốc kế vào việc nhận dạng hành động của người sử dụng. Hai tác giả trên đã dùng 5 gia tốc kế gắn tại 5 vị trí khác nhau trên người sử dụng để ghi nhận được nhiều loại hành động của người dùng như đứng, đi bộ, chạy, ngồi,... Kết hợp với việc so sánh với các dữ liệu gia tốc của 20 người tình nguyện trong phòng thí nghiệm, từ đó phân loại hành động của người sử dụng. Và độ chính xác với cách làm của họ là 84%. Tuy nhiên, việc gắn 5 gia tốc kế lên người sử dụng là không tiện dụng, đồng thời gia tốc kế mà họ sử dụng là gia tốc kế riêng biệt. Trong bài báo "A simple method for reliable footstep detection on embedded sensor platforms” của tác giả Ryan Libby (2), gia tốc kế được ứng dụng để nhận biết bước đi của người dùng. Trong cách thức tiến hành, Ryan sử dụng một thiết bị tích hợp gia tốc kế và đặt nó ở hông người sử dụng. Kết quả tốt nhất trong phần nhận biết bước đi khi người dùng đi bộ là 99,5%. Ở đề tài “Xây dựng thuật toán tính số bước chân trên iPhone”, em thực hiện xây dựng thuật toán tính số bước chân dựa vào bộ lọc Kalman. Và em xin được áp dụng để làm đề tài cho chuyên đề này, nhằm phân tích phân tích các nguyên tắc sáng tạo được áp dụng trong quá phát triển cảm biến trên iPhone cũng như trong quá trình thực hiện đề tài Chƣơng I: LÝ THUYẾT VÀ THỰC NGHIỆM 1. Cảm biến 1.1 Khái niệm về cảm biến Cảm biến là một thiết bị đo một đại lượng vật lý và chuyển đổi nó thành tín hiệu để người hoặc thiết bị khác có thể đọc được. Ví dụ: nhiệt kế thủy ngân chuyển đổi sự thay đổi nhiệt độ thành sự độ cao của cột thủy ngân trong ống thủy tinh để có thể đọc được. Hầu hết các cảm biến đều được canh chỉnh độ chính xác dựa vào các chuẩn đã biết. Ví dụ: nhiệt độ của nước đá là 0oC và nhiệt dộ của nước đang sôi là 100oC thì ta sẽ đánh dấu được bảng chia nhiệt độ cho nhiệt kế. Bản thân cảm biến cũng ảnh hưởng đến kết quả đo đạc. Ví dụ: nếu dung nhiệt kế thủy ngân vào ly nước để đo nhiệt độ nước thì bản thân cảm biến cũng ảnh hưởng đến nhiệt độ đo được của nước trong ly. Do đó, cảm biến phải được thiết kế sao cho mức ảnh hưởng của nó đến giá trị mà cảm biến đo được là nhỏ nhất. 1.2 Đặc điểm của cảm biến Độ nhạy của cảm biến được định nghĩa là độ thay đổi giá trị của cảm biến tương ứng với một lượng thay đổi của đại lượng cần đo. Ví dụ: nếu như cột thủy ngân của nhiệt kế dâng lên 1cm khi nhiệt độ tăng 1oC thì độ nhạy của cảm biến là 1cm/oC. Cảm biến có khả năng ghi nhận được những thay đổi càng nhỏ thì càng nhạy. Độ phân giải của cảm biến là sự thay đổi nhỏ nhất của giá trị cần đo mà cảm biến có thể ghi nhận được. 1.3 Một số loại cảm biến trên smartphone - Ambient Light Sensor (ALS): cảm biến ánh sáng. - Proximity Sensor: cảm biến gần. - Accelerometer: gia tốc kế. - Magnetometer: cảm biến từ trường. - Gyroscope : cảm biến con quay hồi chuyển. 1.4 Ứng dụng phổ biến của cảm biến - Ứng dụng của Ambient Light sensor (cảm biến ánh sáng): dựa vào khả năng đo lượng ánh sáng (độ sáng) của môi trường xung quanh. Giảm điện năng tiêu thụ bằng cách điều chỉnh độ sáng màn hình phù hợp với môi trường sử dụng. Điều chỉnh độ sáng của không gian xung quanh nhờ vào việc nhận biết mức ánh sáng tương ứng. - Ứng dụng của Proximity Sensor (cảm biến gần): cảm biến gần được dùng để đo độ gần của một vật thể bằng cách phát ra tia hồng ngoại và đo độ mạnh của tín hiệu phản hồi. Cảm biến gần được dùng chủ yếu để nhận biết khi nào người dùng đặt điện thoại gần tai nhằm tắt màn hình để tiết kiệm điện năng và tắt cảm ứng màn hình để tránh việc vô tình phát sinh sự kiện chạm màn hình. - Ứng dụng của Accelerometer (gia tốc kế): Với khả năng nhận biết trạng thái chuyển động, rung lắc, và trạng thái, gia tốc kế được dùng trong nhiều loại ứng dụng như tiện ích, game, đo sức khỏe, v.v... - Ứng dụng của cảm biến từ trường: Cảm biến từ trường được tích hợp khá nhiều trên các loại smartphone. Với khả năng xác định hướng, cảm biến từ trường được kết hợp với định vị GPS để xác định tuyến đường mà người dùng đã đi. - Ứng dung của Gyroscope (cảm biến con quay hồi chuyển): Tương tự như gia tốc kế, cảm biến con quay hồi chuyển cũng được ứng dụng chủ yếu vào các trò chơi, các tiện ích mà trong đó điện thoại được điều khiển bằng cách nghiêng điện thoại qua lại. 2. Xử lý tín hiệu cảm biến 2.1 Giới thiệu bộ lọc Kalman 2.1.1 Khái niệm về bộ lọc Bộ lọc là phương pháp loại bỏ những giá trị không quan tâm và giữ lại những giá trị cần thiết. Thông thường, bộ lọc được sử dụng để lọc tín hiệu nhiễu ra khỏi tín hiệu cần đo. Trên thực tế, không thể lọc được toàn bộ tín hiệu nhiễu ra khỏi tín hiệu thực tế, vì vậy bộ lọc chỉ có thể lọc ra tín hiệu ước lượng gần đúng so với tín hiệu thực. Hình 1. Mô hình bộ lọc 2.1.2 Giới thiệu về bộ lọc Kalman Năm 1960, R.E Kalman đã công bố bài báo nổi tiếng về một giải pháp truy hồi để giải quyết bài toán lọc thông tin rời rạc tuyến tính (discrete data linear filtering) mang tên "A New Approach to Linear Filtering and Prediction Problems". Bộ lọc Kalman là tập hợp các phương trình toàn học mô tả phép tính hồi quy để ước lượng trạng thái một quá trình sao cho phương sai giữa giá trị ước đoán và giá trị thật là nhỏ nhất. Mô hình hệ thống Kalman Filter Tín hiệu đo được Tín hiệu cảm biến Hình 2. Mô hình bộ lọc Kalman 2.1.3 Giới thiệu về bộ lọc Kalman rời rạc Bộ lọc Kalman rời rạc sử dụng cho bài toán ước lượng trạng thái một quá trình được mô hình hóa một cách rời rạc theo thời gian. Trạng thái của quá trình được mô tả theo phương trình ngẫu nhiên tuyến tính: xk = A*xk-1 + B*uk-1 + wk-1 , w ~ (0, Q) (1) Kết quả đo được z được mô tả theo phương trình: zk = H*xk + vk ,v ~ (0,R) (2) Nếu x có kích thước n, u có kích thướng l, z có kích thước m thì khi đó: - A: ma trận kích thước n x n. Thể hiện mối quan hệ giữa x và trạng thái trước nó. - B: ma trận kích thướng n x l. Thể hiện mối quan hệ giữa u và x. - u : tín hiệu điều khiển. - w : tín hiệu nhiễu của hệ thống. - H: ma trận kích thước n x m. - v : tín hiệu nhiễu đo đạc. - Qua mô hình hệ thống, ta thấy bộ lọc Kalman rời rạc là đi tìm giá trị ước lượng x khi biết được mô hình trạng thái của x và giá trị đo được z phụ thuộc vào x. Để tìm được giá x gần đúng với giá trị thật nhất, Kalman đã đưa ra mô hình bộ lọc Kalman dưới đây: Hình 2. Mô hình xử lí của bộ lọc Kalman rời rạc Trong đó: - P: ma trận sai số của hệ thống. - x- :giá trị ước đoán từ mô hình hệ thống. - x: giá trị tính toán được. Bộ lọc Kalman rời rạc gồm 2 phần: - Time Update: dựa vào mô hình trạng thái đã thiết lập và giá trị x tiền nghiệm tính được tính toán giá trị ước đoán x. Và điều chỉnh giá trị sai số P. - Measurement Update: tính toán giá trị thật x dựa vào giá trị ước đoán, giá trị đo được và sai số ước lượng. Ta có thể mô hình Kalman rời rạc một cách tổng quát như sau: Ước đoán giá trị x Mô hình hệ thống Ước đoán sai số Giá trị đo được Tính toán giá trị x Tính toán sai số 1 2 2 2 3 4 4 Hình 4. Mô hình tổng quát bộ lọc Kalman rời rạc Thứ tự thực hiện từ 1 đến 4 và lặp lại. 2.2 Xử lý tín hiệu từ gia tốc kế 2.2.1 Phƣơng pháp lọc nhiễu ứng dụng bộ lọc Kalman rời rạc Như đã nêu trên, để sử dụng bộ lọc Kalman rời rạc, ta cần mô hình hóa hệ thống theo hai phương trình ngẫu nhiên tuyến tính của bộ lọc Kalman rời rạc: (1) với A=1, u=0  xk = xk-1 + wk-1 , w ~ (0, Q) Kết quả đo được chỉ bao gồm giá trị tín hiệu thật và thêm vào lượng nhiễu nên H =1 và được mô tả theo phương trình: (2) với H=1  zk = xk + vk ,v ~ (0,R) Hình 53. Mô hình bộ lọc Kalman rời rạc cho tín hiệu cảm biến Trước Sau Hình 6. Tín hiệu 3 trục x, y, z của accelerometer trƣớc và sau khi qua bộ lọc Kalman rời rạc Qua hình 6, ta thấy bộ lọc Kalman rất hiệu quả trong việc lọc nhiễu tín hiệu của cảm biến đặc biệt là tín hiệu gia tốc kế. 2.3 Phƣơng pháp tính số bƣớc chân từ tín hiệu của gia tốc kế Bộ lọc Kalman Lọc cực trị cục bộ Tín hiệu từ gia tốc kế Số bước chân n Hình 74. Sơ đồ phƣơng pháp tính số bƣớc chân Với tín hiệu từ gia tốc kế, xác định kiểu đặt điện thoại để xác định giá trị trục của gia tốc kế có biến đổi nhiều và có thể tính được bước chân từ đó. Kiểu đặt máy và giá trị trục tương ứng như sau: o Với kiểu cầm tay: lấy tín hiệu trục z. o Với kiểu bỏ túi áo: lấy tín hiệu trục y. o Với kiểu bỏ túi quần: lấy tín hiệu trục z. Thông số nhiễu em sử dụng R= 0.02, Q:0.5, và thông số nhiễu thay đổi tùy vào kiểu đặt điện thoại và được xác định dựa vào bộ dữ liệu thu được để có kết quả tốt nhất. Hình 8. Tín hiệu từ gia tốc kế Hình 9. Tín hiệu từ gia tốc kế qua 1 lần lọc Kalman với thông số nhiễu thấp Hình 105. Tín hiệu từ gia tốc kế qua 1 lần lọc Kalman với thông số nhiễu cao Hình 11. Tín hiệu từ gia tốc kế qua 3 lần lọc Kalman với thông số nhiễu thấp Với tín hiệu sau 3 lần lọc Kalman (tín hiệu K), em sử dụng bộ lọc bước đi em đề xuất. Mục đích bộ lọc bước đi là lọc giữ lại những cực trị cục bộ: bao gồm dãy tín hiệu tăng và dãy tín hiệu giảm. Cách thức lọc bước đi như sau:  Nếu (K i - K i-1> d):  Ti := Ti-1 + k.  Nếu (K i-1 - K i > d):  Nếu Ti-1 = 0 : Ti := T lớn nhất cục bộ kề trước.  Nếu Ti-1 > 0 : Ti := Ti-1 - k .  Nếu Ti < 0: Ti := 0.  Nếu (| Ki-1 - Ki | <= d): Ti = 0. Trong đó:  K: tín hiệu sau khi qua bộ lọc Kalman.  T: tín hiệu sau khi lọc cực trị.  d: tham số sai lệch.  k: hằng số bất kì. Hình 12. Kết quả sau khi lọc bƣớc đi - Tín hiệu thứ 1: tín hiệu sau bộ lọc Kalman K. - Tín hiệu thứ 2: tín hiệu T.  Kết quả lọc bƣớc đi Sau khi qua lọc bước đi, ta có thể dễ dàng tính bước đi S từ dãy tín hiệu T. Với mỗi cặp tăng giảm có cực trị kề và bằng nhau thì giá trị S =1 và đó là một bước chân. Hình 13. Bƣớc đi S từ dãy tín hiệu T - Tín hiệu thứ 1: tín hiệu T. - Tín hiệu thứ 2: tín hiệu S.  Kết quả tín hiệu S Từ tín hiệu S, số giá trị S = 1 chính là là số bước chân nhận diện được. 2.4 Kết quả đạt đƣợc Nhóm tiến hành thu thập dữ liệu số bước đi với 2 kiểu cầm tay và bỏ túi áo. Dữ liệu tính được thu thập từ việc cho người sử dụng ứng dụng PathTracker và 5 ứng dụng đếm số bước chân có lượng Rating cao trên Appstore bao gồm: Pedometer 2.2.2 with GPS+, Stepmetr, Pedometer Pro, Pedometer 2.2.2 và Footstep. Với kiểu cầm tay, chúng em thu thập trên 21 người thử nghiệm và thu thập 61 bộ dữ liệu với 20640 bước bao gồm 5 mức: 20, 40, 60, 80, 100 bước. Với kiểu bỏ túi chúng em thu thập trên 6 người thử nghiệm và thu thập 22 bộ dữ liệu với 7560 bước bao gồm 5 mức: 20, 40, 60, 80, 100 bước. Độ chính xác trung bình của chúng em ở kiểu cầm tay là 96.3%, và ở kiểu bỏ túi là 96.7%. Ở 2 kiểu ứng dụng của chúng em đều đạt được độ chính xác cao nhất trong số các ứng dụng được thử nghiệm. Tên người thực hiện Số bước chân Applications Path Tracker Pedometer 2.2.2 with GPS+ Stepmetr Pedometer Pro Pedometer 2.2.2 Footstep Trân 20 19 19 14 19 18 18 Truc Anh 20 20 18 16 17 11 18 Phuc 40 38 31 27 27 36 27 Khoi 40 39 34 31 25 27 37 Thao 60 55 52 40 52 57 54 Truc Anh 60 57 43 58 55 26 66 Thao 80 77 77 57 45 76 72 Ngon 80 72 61 40 75 59 58 Bảng 1. Một số bộ dữ liệu tính bƣớc đi thu thập trên các ứng dụng Hình 6. Biểu đồ độ chính xác trung bình của các ứng dụng ở kiểu cầm tay Hình 7. Biểu đồ độ chính xác trung bình của các ứng dụng ở kiểu bỏ túi 95.6% 84.6% 67.8% 79.2% 78.8% 84.7% 0.0% 10.0% 20.0% 30.0% 40.0% 50.0% 60.0% 70.0% 80.0% 90.0% 100.0% PathTracker Pedometer 2.2.2 with GPS+ Stepmetr Pedometer Pro Pedometer 2.2.2 Footstep 96.7% 92.4% 78.9% 88.8% 92.0% 89.8% 0.0% 10.0% 20.0% 30.0% 40.0% 50.0% 60.0% 70.0% 80.0% 90.0% 100.0% PathTracker Pedometer 2.2.2 with GPS+ Stepmetr Pedometer Pro Pedometer 2.2.2 Footstep Chƣơng II: ỨNG DỤNG NGUYÊN TẮC SÁNG TẠO TRÊN SỰ PHÁT TRIỂN CẢM BIẾN VÀ TRONG QUÁ TRÌNH THỰC HIỆN 1. Ứng dụng nguyên tắc sáng tạo trên sự phát triển của cảm biến: 1.1 Nguyên tắc phân nhỏ:  Nội dung: - Chia các đối tượng thành các phần độc lập. - Làm đối tượng trở nên tháo lắp được. - Tăng mức độ phân nhỏ của đối tượng.  Ứng dụng: - Các loại chuyển động, biến khác nhau được phân ra và xây dựng các cảm biến khác nhau. Ví dụ: cảm biến ánh sáng, cảm biến gia tốc, cảm biến gốc quay. - Bên trong mỗi cảm biến: các biến đổi được chia ra làm các đại lượng đặc trưng khác nhau: Ví dụ: trên cảm biến gia tốc có 3 đại lượng: x, y và z. Đặc trưng cho gia tốc ở 3 chiều của điện thoại. 1.2 Nguyên tắc phẩm chất cục bộ:  Nội dung: - Chuyển đối tượng (hay môi trường bên ngoài, tác động bên ngoài) có cấu trúc đồng nhất thành không đồng nhất. - Các phần khác nhau của đối tượng phải có những chức năng khác nhau. - Mỗi phần của đối tượng phải ở trong những điều kiện thích hợp nhất đối với công việc.  Ứng dụng: - Các cảm biến được quản lí một cách độc lập và được bố trí ở những vị trí khác nhau, nhằm tạo ra