嵌入式系统中地图快速漫游算法的实现

1 引言  

随着人们物质生活的极大丰富，旅行已经成为了日常生活中重要的一部分。在户外旅行中最重要的信息莫过于位置信息，于是地理信息系统（GIS）、卫星定位系统(GPS)、导航系统逐渐开始走入人们的视线，GPS车辆导航系统，腕表式GIS系统等都为人们的出行提供了极大的方便。这些产品在外形上要满足体积小、便于携带的要求；在性能上要满足信息完备、实时性强、处理速度快的要求。综合考虑以上因素，嵌入式应用成为这些产品的首选。嵌入式芯片体积小，耗电低，适合开发功能单一的便携式产品，但是和台式机的CPU相比，嵌入式处理器的速度要慢得多。在嵌入式芯片上开发GIS系统时，信息完备性要求使得系统的数据处理量非常大，因此处理器速度的限制将使系统的性能受到严重的影响。例如，在嵌入式GIS系统的应用中，地图漫游速度是衡量系统性能优劣的一项重要指标，地图漫游的速度在很大程度上受限于嵌入式CPU的处理速度，因此在嵌入式GIS设计中，如何提高地图的浏览速度就成为一个重要课题。  

提高地图浏览速度应该从以下几个方面着手：  

（1）提高芯片的处理速度 这是从选型时就应该考虑的问题，一旦芯片选定，这种方法就失去了作用  

（2）设计地图数据结构时对数据的有效性和冗余性进行综合考虑 这种方法是从减小地图数据量从而减小处理器的工作负荷考虑的，但地图信息完备性要求使这种改进对于地图漫游速度的提高有限  

（3）提高对芯片的利用率 本文即从这个方面考虑，采用双缓存技术，利用芯片的空闲时间进行数据的预处理，达到提高芯片利用率的目的，从而加快地图漫游速度  

2 双缓存技术实现地图快速漫游的基础  

基于对图像的开窗处理显示矢量地图是很多台式机上的GIS系统采用的方法之一，这种算法的主要思想是：从数字地图数据库中提取出显示范围内的地图要素，将描述这些地理要素的坐标转换成屏幕坐标，用显示窗口对这些数据进行剪裁，将剪裁后的地理要素直接绘制在屏幕窗口内。这种算法的优点是算法简单，实现方便。同时，由于台式机CPU处理速度能够满足实时剪裁图像的要求，使得用该算法实现的GIS系统在台式机上的实时性不受影响。但是对于嵌入式系统来说，速度限制是不容忽视的问题。如果仍然用同样的方法实现地图漫游，则会发现地图的漫游成为难以忍受的过程，在屏幕上将地图移动实际距离为两公里的路程，需要的时间是在台式机上实现同样过程的十倍多。究其原因，可以发现速度的瓶颈在于两点：1：嵌入式GIS产品从便携式角度考虑，大多采用液晶显示屏，液晶屏的显示是由其自带的缓存和显示处理器存储处理的，屏幕显示数据通过异步方式和系统处理器间实现通信，导致液晶屏显示缓存的读写慢，产生系统速度的瓶颈，这使得直接在显示缓存上绘制地图需要花费很长的时间；2：预处理数据量大，预处理包括对地理要素的读取、坐标的转换以及裁剪，因此预处理活动占用系统时间长。这两点使得在单任务嵌入式操作系统中，地图漫游的过程不仅很缓慢而且常常需要停顿下来等待数据的处理和显示。因此，要实现嵌入式系统中地图的平滑快速漫游，必须首先解决好这两个问题。  

读写显示缓存的速度极大的影响了地图的绘图速度。在笔者开发的车载导航系统中，使用分辨率为640*480的液晶显示屏，在这样的屏幕上绘制一幅地图数据经测试平均需要400毫秒；而系统RAM的读写速度是几十Mbytes/s的速度，也就是说在系统RAM上绘制同样大小的区域仅需要几十毫秒甚至几毫秒。因此，我们采用这样的方法加快绘图过程的速度：首先在系统内存中开辟专门用于绘制地图图像的空间，称之为虚拟屏幕，虚拟屏幕的范围应远大于实际显示屏的显示范围，同时，我们在显示缓存中开辟和虚拟屏幕大小相同的空间用于缓存地图图像。这样，我们首先用开窗法在虚拟屏幕上绘制地图，绘制操作是对于系统RAM的读写，速度很快，然后从虚拟屏幕上将实际屏幕上应该显示的地图图像拷贝到缓存空间，图像拷贝要花费一定的时间，但是虚拟屏幕远大于实际屏幕范围，这样的拷贝工作不需要每移动一步都进行一次，而是积累一段时间以后才进行一次拷贝。显示屏幕上的图像实际上是显示缓存的一个窗口，也就是从显示缓存的某个地址开始的一块连续空间。因此，使用了显示缓存后，地图的移动过程就是在缓存空间上移动图像的起始指针的过程（见图1）。我们知道，指针移动是几乎没有时间消耗的，因此，这样的方法使得当虚拟屏幕上的一幅地图组织好并拷贝到显示缓存空间之后，地图的移动满足快速、实时的要求。此时速度的问题就转移到在虚拟屏幕上组织地图和将虚拟屏幕的图像拷贝到显示缓存空间的过程中，也就是说，此时地图的移动是快速但并不平滑的，因为虚拟屏幕的组织和图像拷贝将引起地图移动的停顿。虽然对于屏幕的显示缓存来说，图像拷贝的速度远大于单点读写的速度，但是，我们仍然无法满意它所造成的地图移动的不连续的后果。因此，我们仍然需要进一步采取措施解决组织虚拟屏幕和图像拷贝的时间消耗，这使得我们在缓存法的基础上研究了一种新的显示技术——双缓存法——来实现地图的快速漫游。