星期三, 11月 28, 2007

全國校園軟體設計競賽入圍決賽

研究中的走失偵測系統與架構受到全國校園軟體設計競賽評審重視,目前入圍全國校園軟體設計競賽決賽。
公佈網址為:http://csc.pro.edu.tw/mod/resource/view.php?id=421

參加類別為:【教學應用及自由創意類】
名字:精障就輔 U 化小隊
學校:中原大學
題目:學齡兒童上學路徑偵測 U 化系統

星期三, 11月 21, 2007

Algorithms for Characterization and Trend Detection in Spatial Databases

論文篇名:Algorithms for Characterization and Trend Detection in Spatial Databases

摘要:

在空間特徵化(spatial characterization)中如何去決定每個類別所隸屬的資料庫物件是很重要的,因為非是只有不是空間的特性而且還要考慮鄰近點的資訊。在空間方位的分析上,一些在資料庫物件中的鄰近節點其非空間性的屬性的位元變化也會決定其資料。我們提出許多演算法在這個目的上。

緒論:

SDBS(Spatial Database System)式資料庫系統用來處理,控管空間資料的。是爲了找出隱含的規則,或是隱藏在大量資料中的法則或模式。在位置行銷,流量管制或是環境考察中,spatial data algorithm is very importment.
在這篇論文中,我們提出一個新的演算法在特徵化還有方位的偵測在空間資料庫中。一個簡單的方法在空間方位偵測,根據一般化群集演算法,在(Ester et al, 1996)中提出。
在1993年,以屬性為導向的歸納法被設計完成,使用空間和非空間的階層式去搜尋空間和非空間屬性之間的關係。這些資料根據階層式觀念來一般化。他們提出依個演算法去找尋空間資料的規則從X->Y(c%),X and Y are sets of spatial or non-spatial predicates and c is the confidence of the rule.

我們的演算法在空間特徵化和方位偵測上是以一個簡單方法來呈現。一般
得spatial data mining都是使用詳盡的或是固有的相鄰的關係。但是我們質疑這種方式,因為在一堆資料中要詳盡的去找尋不會有效率。因此,一個延伸至SDBS的資料架構和運算,在有效率的找尋鄰近點的關係上的研究被提出(Ester et al, 1997a)

Database Primitives for Spatial Data Mining:
我們的架構的概念是根據鄰近節點的圖像和相鄰的路徑是由鄰近物件的關係來決定。
這裡有三個空間關係的基本模型:位相幾何學(topological),距離,方向的相關性而這是由結合邏輯運算子去表達更複雜的鄰近節點的關係。我們只關心二度空間中方向的關係因為這在我們的濾波器中是被要求詳盡的以便於判斷。
文中提到,顯然地,兩個物件中的方位不會為唯一且輪廓分明的,再論文的例子中的圖一就顯示,兩個物件會有許多方位,就譬如兩個物件來作為說明,B在A南方,B也在A東方。爲了找到一個唯一的區域,作者說兩個物件一定有一個方位的相關性是最小的,稱為exact direction relation of A and B,是uniquely determined,在圖中則是B northeast A的區域最小,所以此區域即為exact direction relation of A and B。

定義一:
以下訂一幾項變數
neighbor :neighborhood relation
DB :Database of spatial objects
neighborhood graph :G(DB/neighbor) = (N,E)
graph with nodes :N=DB
edges :E包含於N*N
edge :e=(n1,n2)
a neighborhood path of length :k
k is defined as a sequence of nodes[n1,n2,...,nk]
neighbor(ni,ni+1) holds for all ni屬於N,1 小於等於 i 小於 k
我們假設在關係代數(relational algebra)標準的運算,就像是selection,union,intersection和difference是可獲得的在此物件的集合中和鄰近路徑的集合(e.g.運算選擇(set, predicate)returns the set of all elements of a set satisfying the predicate predicate)。只有接著的重要運算是明白的描述的。

  • neighbors: Graphs*Objects*Predicates-->

Sets_of_objects

  • paths: Sets_of_objects-->Sets_of_paths
  • extentions:Graphs*Sets_of_paths*Integer*Predicates*Sets_of_paths

運算子的鄰近點(graph,object,predicate)回傳全部物件的那個集合,連結到圖像的物件,滿足predicate predicate所要的條件。

運算的路徑(objects)產出長度1的所有路徑,是由一個單一的元素所形成,而且運算子副檔名(graph,paths,max,predicate)回傳此集合中的所有路徑並延伸其中一個路徑到圖上最長的節點。這延伸的路徑必須滿足宣稱的屬性。如此路徑不會保持到最後,即暗示沒有路徑可被延伸。

因為鄰近點數目可能會很多,這證明論述在鄰近作用和延展的動作過程,被當作濾波器去限制鄰近點的數目和路徑去找到他要的形式的鄰近點和路徑。
...

此篇論文是在找尋與某點有相關的特性與值,且鄰近點也會是拿來判斷的依據,並在找到之後不斷延伸直到找不到有相關性的點為止。

討論

此篇論文與走失偵測所需的要件不同:

(1)此篇論文主要在解釋概念性,閱讀之後無法了解該如何實用到我們的系統之上。

(2)如何判斷某個座標為此座標的鄰近點,此篇論文並無提及。

(3)此系統將所有點以一固定距離分配好,系統運行時開始往下去尋找,用線性迴歸下去運算。但是我們使用GPS訊號會有時間的這個參數,此系統並無考慮,因此我覺得還需要再多加尋找其他資料或是文章,才可讓思緒更加清楚。

星期一, 11月 19, 2007

無線通訊與識別技術應用於物件位置桿之系統建立之研究--之論文研究與探討

此研究出處為:MIST2007

摘要:
此系統利用GPS(室外)和RFID(室內)來作為感測的工具,傳輸的方式則是透過WI-FI無線網路來作為傳輸的方式,藉著無線網路連結到後端地理資訊系統進行明確位置之分析,系統自動判讀物件是否異常,例如不在監控區域內或與系統失去連結。並期望以低成本的方式發展物件感知的服務,例如失智老人所在位置。

此研究之動機:
此系統加入RFID之原因在於辨識物件的身分與資料,並利用RFID的事內能力彌補GPS在室內定位不足的限制,此系統研究人員更想擴大服務的範圍到物件監控服務,譬如在物件管理與資產追蹤上,他們認為可以有效提高資產管理的品質,也可減低傳統監控所需的成本與人力;另外,他們也有想到使用在人員監控上,譬如對師至病患的照護服務,可減少照護的成本和病患的走失率。

此篇論文使用的技術主要有三種,RFID,GPS,GIS(地理資訊系統,Geographic information System),是一套可以整合各項相關地理資料的資訊化作業系統,其架構於依完整豐富的地理資料庫上,並具有擷取,編修,更新,儲存,查詢,處理,分析即展示的不同功能,此篇論文所使用的GIS軟體工具為美國MapInfo公司所開發的MapXtreme Java,可於Internet上開發與部屬地圖應用程式的地圖應用伺服器,透過地圖實現資料視覺化,可顯示資料之間的關聯和發展趨勢。

系統架構:
(1)物件進出的監控:
在出入口設置主動式RFID Reader來監控物件進出的紀錄。

(2)室外物件感知模式:
作者想法為在物件端開發一個PDA應用程式,以此應用程式銜接RFID,藍芽GPS,再將讀取到的GPS座標資訊,透過WI-FI傳輸到後端的位置分析管理服務儲存。
位置分析管理服務以地理資訊系統為基礎,透過讀取資料庫中所記錄的物件座標資訊,再結合地理資料庫,達到在地圖上以圖形化的方式呈現。

監控模式:
(1)物件進出的監控:
主要做法分為兩部份,一為在出入口或是管制區域內設置主動式RFID,另一方面則是物件會黏貼存放識別資料的Tag。
當Reader無法偵測到Tag,則表示Reader異常,發出Reader故障的訊號。如可以正常讀取,則將讀取到的Tag資料傳送到資料庫比對,並判斷物件是否可離開此區域,如果查詢到物件不可離開此區域而且此物件已離開,則發出遺失通知。
(2)室外物件感知模式
此系統實作系統流程方面,將在隨身定位服務上設計一室外物件位置感知監控功能,當按下PDA 處理器上的啟動監控按鈕後,即可啟動活動區域偵測。當啟動室外監控物件模式時,PDA 處理器會先擷取所監控的物件是否為有效GPS 座標,如果所監測之座標無效則啟動判斷GPS 是否有效計時器T,若五分鐘內都無法偵測到有效的GPS 座標時(無效時間> 5 分鐘),系統將發出物件失蹤的警告。
反之,當偵測GPS 座標訊號有效時,PDA 處理器會先擷取有效的GPS 座標P,接著判斷P的位置是否有改變,若P 的位置沒有改變,則表示物件處於靜止狀態,資料庫無須更動,系統會繼續監控物件座標。若P 的位置有改變時,表示物件正在移動,系統將會立即將移動後的座標傳送到資料庫伺服器,然後繼續此監控流程。

系統運作流程:
此系統開始時,監控人員透過本系統設計之網頁輸入欲查詢物件的Tag ID,系統會利用此Tag ID 到物件資料與座標資料庫去抓取物件最新的座標資料,並將此座標資料進行GIS 資訊轉換,這個程序是利用該物件的座標資料到地理資訊資料庫抓取相對應的圖層。
然後繼續該物件的監控服務,並隨時判斷是否有異常狀況的發生,異常狀況如物件離開限制的室內監控區域、物件在室外失去GPS 位置的訊號等狀況,則位置分析管理服務將最新的物件經緯度的資訊轉換成GIS的資訊,例如物件移動軌跡的描繪等。再整合與物件相關的資訊,如遺失物件最後的所在地理位置等資訊,以警告監控人員,直到此服務完成為止。
GIS 資訊的轉換是利用本研究所設計的地理資訊系統進行轉換,是以GIS 技術為基礎,將建築物、街道、地理區塊等物件附近相關的位置資訊以圖層影像的方式加以呈現。

解決方案的探討與選擇:
本研究在物件端的定位方案所選擇的是RFID+ PDA或3G/GSM Cell Phone with Wi-Fi and GPS Cards。

系統環境的假設:
1.考慮到攜帶性與方便性,在室外監控的模式下,物件必須是無生命的物體。
2. 室外所偵測的區域是在Wi-Fi 無線網路的涵蓋區域下,例如大台北都會區已經廣佈無線網路的節點,隨時隨地都可連接網際網路。
3. PDA 處理器必須支援RFID reader CF 介面的模組,還須配備RFID Reader CF Card。
4. GPS 接收器可以透過PDA 的任何介面來裝備,例如Secure Digital(SD)介面、CF 介面以及藍芽介面。本研究是採藍芽介面來銜接GPS 接收器。

物件定位服務的設計:

物件定位服務包含三個部份。
第一是GPS 接收器:
可提供物件目前的經緯度座標、時間、速度與方向等衛星定位資訊,透過藍芽傳輸的方式將這些與位置有關的資訊傳送給PDA處理器。
第二是RFID Tag 卡片:
可提供物件識別或相關的物件資訊,透過RFID 頻率433MHz 傳送到PDA處理器。
第三是PDA 處理器:
PDA 處理器的CF 介面安裝有主動式RFID Reader 卡,使其具備RFID Reader的功能,同時也支援藍芽介面傳輸功能。
再透過本系統開發的程式,將接收到的GPS 與RFID 訊號進行解析、指令執行和邏輯判斷,並且透過Wi-Fi 無線技術將整合的訊息傳送到資料庫伺服器記錄。
位置分析管理服務的運作原理與轉換流程:
地理資訊系統的地圖圖像(Map Image)呈現主要是由許多圖層堆疊而成,圖層的種類可分為點、線、面三類型,例如景點的呈現可以是點類型圖層,街道的呈現可以是線類型的圖層,公園的呈現可以是面類型的圖層。在本系統中位置分析服務會以此堆疊方式先建置一個基礎的地圖,再將資料庫中所儲存的GPS 經緯度資訊以點類型圖層的方式呼叫Insert()這個方法,將圖層插入到這個基礎地圖,以此達到即時監控的功能。
位置分析管理服務在使用者協尋介面端是以HTML 瀏覽器來讀取位置分析管理服務所提供的ServletContainer 所產生的Map Image。
Servlet Container 主要由MapXtreme Servlet、User Defined Servlet 所組成,MapXtreme Servlet 提供User Defined Servlet 所需的Map Image,Map Image 是透過MapXtreme Servlet 呼叫MapJ 物件讀取Map Defined File(MDF)格式的檔案所產生,而其中MDF 檔案中定義了基本地圖呈現方式、圖層數量、圖層大小、圖層顯現等,也包含了各圖層的資料(路名、編號等,以TAB 的檔名呈現)。
在建置一個地圖時,步驟如下所述。
1. 在伺服器上建置一個MDF 檔存取本地端的地圖資源。
2. 使用者每次連線將使用MDF 的定義檔來重新初始化MapJ 的物件。
3. User Defined Servlet 利用MapXtreme Servlet 來製造Map image。
4. Map image 傳回User Defined Servlet。
5. User Defined Servlet 將地圖併入HTML 傳到使用者端。
實驗分析:
針對遮蔽物的影響因素進行實際測試後,分別針對發現GPS 在室內監測並無法偵測到有效的資料,在走廊上雖然可以偵測到有效的GPS 資料,但是靜止狀態下每秒的誤差卻達到將近100 公尺,最後在空曠處進行實驗,結果驗證在空曠處GPS 的準確度很高,誤差近乎於0,因此我們可知多路徑效應誤差對GPS 訊號接收的準確度影響是相當大的。
此系統遭遇的限制:
1.地理資訊資料庫侷限於新莊到泰山地區,無法提供此地區以外詳細的物件相關資訊服務。
2.無線技術受到遮蔽物遮蔽的影響。
3.行動裝置的電力問題
4.物件在高速狀態下無法使用wifi。
對於此篇論文之研究與討論:

1.論文優點:
(1)有分析GPS接收度好壞的數據。
(2)內容詳盡,將此系統的概念描述的非常清楚。
2.系統缺點:
(1)網頁所選用的地圖:
介面不夠人性化,且只可顯示一個點在地圖上。
(2)系統的圖資有限,因此有使用上的範圍
(3)從論文中看來,此篇論文作者還無法寫出在PDA上所需撰寫的程式。
(4)論文中提到RFID Tag限制在無生命的物品上使用,有非常大的使用限制。
(5)RFID Tag難免有標籤化的問題,此系統作者並無考慮此一點。
(6)判別GPS所偵測的座標是否有效為5分鐘,此數據如何選用並無根據。

走失偵測系統與此系統之比較(針對室外監控部份):
(1)此系統有辦法完成之判別,走失偵測系統已經早就可以做到。
(2)走失偵測系統給精障者使用,除去無線通訊與識別技術應用於物件位置桿之系統中只給無生命使用的限制。
(3)使用Google maps當作地圖介面,引入Web2.0的概念,讓使用者操作方便,並以一路徑方式顯示出使用者的位置,更可達到監控與照護的目的。
(4)未來朝向自動化監測目的更可減輕監控者的負擔。
(5)無時間倒數機制,雖然物品停在原地,但有可能內容物被拿走或是人員已經受傷之類的狀況發生,此系統研發人員欠缺此一層考慮。

星期四, 11月 08, 2007

learning and inferring transportation routines

learning and inferring transportation routines與走失偵測系統的差異

1.此套系統使用非監控式的方式,而且依照論文中的敘述,此系統只有模擬狀況,並無真正地接收GPS訊號來運作,並且與我們的系統差異最大的地方在於他們的系統雖然也有一路徑,但是偵測時並非全按照所記錄的路徑來作為偵測,在此系統設定某個終點之後,使用者可以隨便按照自己的意思來走,偵測是否錯誤是將數據計算過後由kalman filter來決定。

2.又譬如此系統中的變數(vertice transition),決定在交叉路該往哪個點走,但是我們的系統可以按照之前所記錄的點,直接以一路徑判斷,因此該如何行走到目的地已經早就規劃好了,因此不需要系統再去預測使用者往哪邊走,就可分辨此使者是否已經出錯。

3.是否該搭車或是該搭什麼車。

在此方面,我們的系統在紀錄使用者的位置時,當a使用者選擇起始點與終點之後,路徑中如有搭公車或是開車,就會看到某段速度特別快,因此要判斷此使用者是否搭車則可以有以下方式來偵錯。


(1)如果我們的系統偵測到a使用者的速度與原本所記錄的速度有太大的差異,即可知道此使用者出現錯誤。

(2)另外,也可從經緯度座標的差異來判斷使用者使否有出現錯誤,因為本系統會間隔一段時間才紀錄,因此,如果交通模式有差異,則下個出現的位置必定會因為速度的關係而有差異。

(3)如果使用者是搭乘公車,則會在固定站牌停下,所以在站牌的位置的速度為零,而如果是汽車,則不會發生這類事件,當然如果路上交通擁塞,則可以知道此使用者所送出的gps訊號是走走停停。

所以可以根據這些條件來判斷使用者是搭乘何種交通工具,在未來更可以透過這些判斷式提供使用者該搭乘何種交通工具。

可學習處:
如果要簡化資料,在判斷時以一簡化過的路徑來作為判斷,此篇論文中是使用kalman filter來計算和取得平均速度和位置,並使用MATLAB來做演算,如果無法找到更好的工具,可運用用kalman filter來作為計算的工具。

星期四, 11月 01, 2007

走失偵測系統待完成工作事項

網站:
1.架設網站資料庫
2.區別登入網站者的身分
3.將資料儲存成兩個不同的xml檔,一為即時資訊,一為歷史資訊,方便使用者觀看。
4.顯示偵測出錯誤時的訊息。

人工智慧部份:
1.規劃如何存取資料與比對資料(程式的撰寫)
2.顯示的方法(該以何種方式顯示)