作者：奚玲，高博，于陸，宋國民

1 引言

隨著人們物質(zhì)生活的極大豐富，旅行已經(jīng)成為了日常生活中重要的一部分。在戶外旅行中最重要的信息莫過于位置信息，于是地理信息系統(tǒng)（GIS）、衛(wèi)星定位系統(tǒng)（GPS）、導(dǎo)航系統(tǒng)逐漸開始走入人們的視線，GPS車輛導(dǎo)航系統(tǒng)，腕表式GIS系統(tǒng)等都為人們的出行提供了極大的方便。這些產(chǎn)品在外形上要滿足體積小、便于攜帶的要求；在性能上要滿足信息完備、實(shí)時性強(qiáng)、處理速度快的要求。綜合考慮以上因素，嵌入式應(yīng)用成為這些產(chǎn)品的首選。嵌入式芯片體積小，耗電低，適合開發(fā)功能單一的便攜式產(chǎn)品，但是和臺式機(jī)的CPU相比，嵌入式處理器的速度要慢得多。在嵌入式芯片上開發(fā)GIS系統(tǒng)時，信息完備性要求使得系統(tǒng)的數(shù)據(jù)處理量非常大，因此處理器速度的限制將使系統(tǒng)的性能受到嚴(yán)重的影響。例如，在嵌入式GIS系統(tǒng)的應(yīng)用中，地圖漫游速度是衡量系統(tǒng)性能優(yōu)劣的一項(xiàng)重要指標(biāo)，地圖漫游的速度在很大程度上受限于嵌入式CPU的處理速度，因此在嵌入式GIS設(shè)計中，如何提高地圖的瀏覽速度就成為一個重要課題。

提高地圖瀏覽速度應(yīng)該從以下幾個方面著手：

（1）提高芯片的處理速度 這是從選型時就應(yīng)該考慮的問題，一旦芯片選定，這種方法就失去了作用

（2）設(shè)計地圖數(shù)據(jù)結(jié)構(gòu)時對數(shù)據(jù)的有效性和冗余性進(jìn)行綜合考慮 這種方法是從減小地圖數(shù)據(jù)量從而減小處理器的工作負(fù)荷考慮的，但地圖信息完備性要求使這種改進(jìn)對于地圖漫游速度的提高有限

（3）提高對芯片的利用率 本文即從這個方面考慮，采用雙緩存技術(shù)，利用芯片的空閑時間進(jìn)行數(shù)據(jù)的預(yù)處理，達(dá)到提高芯片利用率的目的，從而加快地圖漫游速度

2 雙緩存技術(shù)實(shí)現(xiàn)地圖快速漫游的基礎(chǔ)

基于對圖像的開窗處理顯示矢量地圖是很多臺式機(jī)上的GIS系統(tǒng)采用的方法之一，這種算法的主要思想是：從數(shù)字地圖數(shù)據(jù)庫中提取出顯示范圍內(nèi)的地圖要素，將描述這些地理要素的坐標(biāo)轉(zhuǎn)換成屏幕坐標(biāo)，用顯示窗口對這些數(shù)據(jù)進(jìn)行剪裁，將剪裁后的地理要素直接繪制在屏幕窗口內(nèi)。這種算法的優(yōu)點(diǎn)是算法簡單，實(shí)現(xiàn)方便。同時，由于臺式機(jī)CPU處理速度能夠滿足實(shí)時剪裁圖像的要求，使得用該算法實(shí)現(xiàn)的GIS系統(tǒng)在臺式機(jī)上的實(shí)時性不受影響。但是對于嵌入式系統(tǒng)來說，速度限制是不容忽視的問題。如果仍然用同樣的方法實(shí)現(xiàn)地圖漫游，則會發(fā)現(xiàn)地圖的漫游成為難以忍受的過程，在屏幕上將地圖移動實(shí)際距離為兩公里的路程，需要的時間是在臺式機(jī)上實(shí)現(xiàn)同樣過程的十倍多。究其原因，可以發(fā)現(xiàn)速度的瓶頸在于兩點(diǎn)：1：嵌入式GIS產(chǎn)品從便攜式角度考慮，大多采用液晶顯示屏，液晶屏的顯示是由其自帶的緩存和顯示處理器存儲處理的，屏幕顯示數(shù)據(jù)通過異步方式和系統(tǒng)處理器間實(shí)現(xiàn)通信，導(dǎo)致液晶屏顯示緩存的讀寫慢，產(chǎn)生系統(tǒng)速度的瓶頸，這使得直接在顯示緩存上繪制地圖需要花費(fèi)很長的時間；2：預(yù)處理數(shù)據(jù)量大，預(yù)處理包括對地理要素的讀取、坐標(biāo)的轉(zhuǎn)換以及裁剪，因此預(yù)處理活動占用系統(tǒng)時間長。這兩點(diǎn)使得在單任務(wù)嵌入式操作系統(tǒng)中，地圖漫游的過程不僅很緩慢而且常常需要停頓下來等待數(shù)據(jù)的處理和顯示。因此，要實(shí)現(xiàn)嵌入式系統(tǒng)中地圖的平滑快速漫游，必須首先解決好這兩個問題。

讀寫顯示緩存的速度極大的影響了地圖的繪圖速度。在筆者開發(fā)的車載導(dǎo)航系統(tǒng)中，使用分辨率為640*480的液晶顯示屏，在這樣的屏幕上繪制一幅地圖數(shù)據(jù)經(jīng)測試平均需要400毫秒；而系統(tǒng)RAM的讀寫速度是幾十Mbytes/s的速度，也就是說在系統(tǒng)RAM上繪制同樣大小的區(qū)域僅需要幾十毫秒甚至幾毫秒。因此，我們采用這樣的方法加快繪圖過程的速度：首先在系統(tǒng)內(nèi)存中開辟專門用于繪制地圖圖像的空間，稱之為虛擬屏幕，虛擬屏幕的范圍應(yīng)遠(yuǎn)大于實(shí)際顯示屏的顯示范圍，同時，我們在顯示緩存中開辟和虛擬屏幕大小相同的空間用于緩存地圖圖像。這樣，我們首先用開窗法在虛擬屏幕上繪制地圖，繪制操作是對于系統(tǒng)RAM的讀寫，速度很快，然后從虛擬屏幕上將實(shí)際屏幕上應(yīng)該顯示的地圖圖像拷貝到緩存空間，圖像拷貝要花費(fèi)一定的時間，但是虛擬屏幕遠(yuǎn)大于實(shí)際屏幕范圍，這樣的拷貝工作不需要每移動一步都進(jìn)行一次，而是積累一段時間以后才進(jìn)行一次拷貝。顯示屏幕上的圖像實(shí)際上是顯示緩存的一個窗口，也就是從顯示緩存的某個地址開始的一塊連續(xù)空間。因此，使用了顯示緩存后，地圖的移動過程就是在緩存空間上移動圖像的起始指針的過程（見圖1）。我們知道，指針移動是幾乎沒有時間消耗的，因此，這樣的方法使得當(dāng)虛擬屏幕上的一幅地圖組織好并拷貝到顯示緩存空間之后，地圖的移動滿足快速、實(shí)時的要求。此時速度的問題就轉(zhuǎn)移到在虛擬屏幕上組織地圖和將虛擬屏幕的圖像拷貝到顯示緩存空間的過程中，也就是說，此時地圖的移動是快速但并不平滑的，因?yàn)樘摂M屏幕的組織和圖像拷貝將引起地圖移動的停頓。雖然對于屏幕的顯示緩存來說，圖像拷貝的速度遠(yuǎn)大于單點(diǎn)讀寫的速度，但是，我們?nèi)匀粺o法滿意它所造成的地圖移動的不連續(xù)的后果。因此，我們?nèi)匀恍枰M(jìn)一步采取措施解決組織虛擬屏幕和圖像拷貝的時間消耗，這使得我們在緩存法的基礎(chǔ)上研究了一種新的顯示技術(shù)——雙緩存法——來實(shí)現(xiàn)地圖的快速漫游。

3 利用雙緩存技術(shù)實(shí)現(xiàn)地圖快速漫游

3．1 雙緩存技術(shù)實(shí)現(xiàn)地圖平滑漫游的基本原理

雙緩存技術(shù)實(shí)現(xiàn)地圖平滑漫游是在緩存法的基礎(chǔ)上提出的一種為解決嵌入式系統(tǒng)下，使用遙控器連續(xù)移動地圖，地圖漫游速度慢或不連續(xù)的問題的新方法。雙緩存的方法解決了緩存法實(shí)現(xiàn)地圖漫游中遺留下來的問題：移動過程中的停頓問題。它的實(shí)現(xiàn)基礎(chǔ)在于：即使是連續(xù)發(fā)送移動命令，在遙控器的兩個命令脈沖之間，仍然存在一定的時間間隔，根據(jù)地圖移動的方向趨勢，利用命令脈沖之間的時間間隔進(jìn)行數(shù)據(jù)組織和圖像拷貝工作是雙緩存法的實(shí)現(xiàn)依據(jù)。圖2是遙控器連續(xù)移動命令脈沖的時序和單緩存實(shí)現(xiàn)地圖移動過程的對應(yīng)。

圖１ 移動命令時序

從上圖我們可以看出：

（1）兩次連續(xù)的移動命令之間的時間至少為190ms， 實(shí)際顯示圖像在虛擬屏幕的范圍之內(nèi)時，圖像的移動是顯示緩存指針移動的過程，處理器在這段時間內(nèi)空閑。

（2）實(shí)際顯示圖像達(dá)到虛擬屏幕的邊界時，如果連續(xù)接收到移動的命令，則只能在以新的顯示中心重新組織虛擬屏幕上的地圖并將虛擬屏幕上的圖像拷貝到顯示緩存之后，才能繼續(xù)移動顯示緩存的指針，在此過程中，起碼有三個移動命令沒有及時處理。

從以上兩點(diǎn)可以得出，在單緩存法實(shí)現(xiàn)地圖移動的過程中，處理器的并不總處于忙狀態(tài)，而是時忙時閑，因此如果將虛擬屏幕數(shù)據(jù)的組織和圖像的拷貝工作平均分配到各個移動命令脈沖之間的處理器空閑時段，就能解決達(dá)到移動邊界時，要長時間等待數(shù)據(jù)處理的問題。

3．2 雙緩存實(shí)現(xiàn)地圖平滑移動的方法及實(shí)現(xiàn)

利用雙緩存技術(shù)實(shí)現(xiàn)地圖平滑移動的內(nèi)存空間分配圖如下：

圖２ 雙緩存實(shí)現(xiàn)地圖平滑移動

如上圖所示，雙緩存實(shí)現(xiàn)地圖漫游的方法是：將顯示緩存劃分為兩個和虛擬屏幕顯示范圍相同的緩存空間，我們稱之為緩存A，和緩存B。定義預(yù)處理邊界為范圍小于虛擬屏幕范圍的一個內(nèi)邊界。當(dāng)顯示屏幕的圖像移動到預(yù)處理邊界時，如果仍然接受到同一方向的連續(xù)移動命令，則開始在虛擬屏幕組織移動方向上的新圖像，并拷貝該圖像到緩存B；同時，在緩存A上，屏幕指針移動的過程仍在進(jìn)行，當(dāng)顯示屏幕移動到緩存A的實(shí)際邊界時，緩存B上已經(jīng)準(zhǔn)備好了顯示方向上的新地圖，此時將屏幕指針跳到緩存B相應(yīng)位置的地址，就可以保證地圖移動動作的連續(xù)性。

雙緩存法實(shí)現(xiàn)地圖平滑移動的過程流程圖描述如圖4所示。

圖３雙緩存法實(shí)現(xiàn)地圖移動過程示意圖

在采用雙緩存法實(shí)現(xiàn)地圖的平滑漫游的處理過程中，預(yù)處理邊界的選取是一個決定其效果的重要因素，預(yù)處理邊界如果和實(shí)際邊界離得太近，則預(yù)留的時間不足以完成所有的預(yù)處理任務(wù)，無法滿足平滑移動的要求，而如果預(yù)處理邊界范圍太小，則使得預(yù)測方向可信度降低，有可能使預(yù)處理過程無效。該邊界的選取和系統(tǒng)讀寫屏幕的速度以及遙控器的靈敏度都是相關(guān)的，選取方法同時和預(yù)測方向的算法也有一定的聯(lián)系，因此仁者見仁智者見智，可以根據(jù)各自系統(tǒng)設(shè)計的不同進(jìn)行選擇。

4 實(shí)驗(yàn)與結(jié)論

筆者在開發(fā)嵌入式環(huán)境下車載導(dǎo)航系統(tǒng)的軟件中使用了雙緩存法實(shí)現(xiàn)地圖漫游，在使用該方法之前，對開窗法、緩存法和雙緩存法實(shí)現(xiàn)的地圖移動的速度的進(jìn)行了比較試驗(yàn)，表1是試驗(yàn)結(jié)果。該試驗(yàn)是在同一幅地圖數(shù)據(jù)，同樣的數(shù)據(jù)量下，移動同樣的距離得出的：

表1幾種漫游方法顯示速度試驗(yàn)

在我們的地圖漫游軟件采用了這種雙緩存法來實(shí)現(xiàn)地圖的平滑移動后，人們從視覺上幾乎感覺不到地圖移動的停頓，因此系統(tǒng)的整體性能得以提高。

雙緩存法是在嵌入式系統(tǒng)中實(shí)現(xiàn)地圖平滑顯示的一種實(shí)用方法，但用此法是以犧牲內(nèi)存為代價提高地圖的漫游速度，因此采用這種算法的系統(tǒng)必須有足夠的內(nèi)存（包括系統(tǒng)內(nèi)存和顯示緩存），預(yù)處理邊界也需要根據(jù)系統(tǒng)要求科學(xué)選取。同時這個算法的實(shí)現(xiàn)代碼也比前兩種復(fù)雜，因此，大家可以根據(jù)自己系統(tǒng)的實(shí)際情況進(jìn)行算法的選擇。

責(zé)任編輯：gt