嵌入式系统中地图快速漫游算法的实现
发布时间：2010-7-26 14:40
发布者：lavida
|
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）。我们知道，指针移动是几乎没有时间消耗的，因此，这样的方法使得当虚拟屏幕上的一幅地图组织好并拷贝到显示缓存空间之后，地图的移动满足快速、实时的要求。此时速度的问题就转移到在虚拟屏幕上组织地图和将虚拟屏幕的图像拷贝到显示缓存空间的过程中，也就是说，此时地图的移动是快速但并不平滑的，因为虚拟屏幕的组织和图像拷贝将引起地图移动的停顿。虽然对于屏幕的显示缓存来说，图像拷贝的速度远大于单点读写的速度，但是，我们仍然无法满意它所造成的地图移动的不连续的后果。因此，我们仍然需要进一步采取措施解决组织虚拟屏幕和图像拷贝的时间消耗，这使得我们在缓存法的基础上研究了一种新的显示技术——双缓存法——来实现地图的快速漫游。 3 利用双缓存技术实现地图快速漫游 3．1 双缓存技术实现地图平滑漫游的基本原理 双缓存技术实现地图平滑漫游是在缓存法的基础上提出的一种为解决嵌入式系统下，使用遥控器连续移动地图，地图漫游速度慢或不连续的问题的新方法。双缓存的方法解决了缓存法实现地图漫游中遗留下来的问题：移动过程中的停顿问题。它的实现基础在于：即使是连续发送移动命令，在遥控器的两个命令脉冲之间，仍然存在一定的时间间隔，根据地图移动的方向趋势，利用命令脉冲之间的时间间隔进行数据组织和图像拷贝工作是双缓存法的实现依据。图2是遥控器连续移动命令脉冲的时序和单缓存实现地图移动过程的对应。  图１ 移动命令时序 从上图我们可以看出： （1）两次连续的移动命令之间的时间至少为190ms, 实际显示图像在虚拟屏幕的范围之内时，图像的移动是显示缓存指针移动的过程，处理器在这段时间内空闲。 （2）实际显示图像达到虚拟屏幕的边界时，如果连续接收到移动的命令，则只能在以新的显示中心重新组织虚拟屏幕上的地图并将虚拟屏幕上的图像拷贝到显示缓存之后，才能继续移动显示缓存的指针，在此过程中，起码有三个移动命令没有及时处理。 从以上两点可以得出，在单缓存法实现地图移动的过程中，处理器的并不总处于忙状态，而是时忙时闲，因此如果将虚拟屏幕数据的组织和图像的拷贝工作平均分配到各个移动命令脉冲之间的处理器空闲时段，就能解决达到移动边界时，要长时间等待数据处理的问题。 3．2 双缓存实现地图平滑移动的方法及实现 利用双缓存技术实现地图平滑移动的内存空间分配图如下：  图２ 双缓存实现地图平滑移动 如上图所示，双缓存实现地图漫游的方法是：将显示缓存划分为两个和虚拟屏幕显示范围相同的缓存空间，我们称之为缓存A，和缓存B。定义预处理边界为范围小于虚拟屏幕范围的一个内边界。当显示屏幕的图像移动到预处理边界时，如果仍然接受到同一方向的连续移动命令，则开始在虚拟屏幕组织移动方向上的新图像，并拷贝该图像到缓存B；同时，在缓存A上，屏幕指针移动的过程仍在进行，当显示屏幕移动到缓存A的实际边界时，缓存B上已经准备好了显示方向上的新地图，此时将屏幕指针跳到缓存B相应位置的地址，就可以保证地图移动动作的连续性。 双缓存法实现地图平滑移动的过程流程图描述如图4所示。  图３双缓存法实现地图移动过程示意图 在采用双缓存法实现地图的平滑漫游的处理过程中，预处理边界的选取是一个决定其效果的重要因素，预处理边界如果和实际边界离得太近，则预留的时间不足以完成所有的预处理任务，无法满足平滑移动的要求，而如果预处理边界范围太小，则使得预测方向可信度降低，有可能使预处理过程无效。该边界的选取和系统读写屏幕的速度以及遥控器的灵敏度都是相关的，选取方法同时和预测方向的算法也有一定的联系，因此仁者见仁智者见智，可以根据各自系统设计的不同进行选择。 4 实验与结论 笔者在开发嵌入式环境下车载导航系统的软件中使用了双缓存法实现地图漫游，在使用该方法之前，对开窗法、缓存法和双缓存法实现的地图移动的速度的进行了比较试验，表1是试验结果。该试验是在同一幅地图数据，同样的数据量下，移动同样的距离得出的： 表1几种漫游方法显示速度试验 移动距离（地图距离） 2KM 5KM 开窗法 11.3S 25.5S 缓存法 4.6S 9.9S 双缓存法 1.2S 2.8S 在我们的地图漫游软件采用了这种双缓存法来实现地图的平滑移动后，人们从视觉上几乎感觉不到地图移动的停顿，因此系统的整体性能得以提高。 双缓存法是在嵌入式系统中实现地图平滑显示的一种实用方法，但用此法是以牺牲内存为代价提高地图的漫游速度，因此采用这种算法的系统必须有足够的内存（包括系统内存和显示缓存），预处理边界也需要根据系统要求科学选取。同时这个算法的实现代码也比前两种复杂，因此，大家可以根据自己系统的实际情况进行算法的选择。 |
网友评论