以GPS和电子海图为技术核心，为航海用户提供安全航行所必需的海图、航路等信息的船舶导航系统目前正在全世界得到广泛应用，大大提高了船舶导航技术与船舶航行的安全性。
船舶导航系统目前主要有PC机系统、单片机系统和嵌入式系统等三种实现方式。常见的PC机船舶导航系统采用基于Windows的GIS软件(如 MapInfo、MapGIS)设计，具有系统功能丰富、响应速度快、人机交互界面友好等特点，但成本较高、系统集成度差，不适合作为专业系统使用。单片 机电子海图应用系统由于处理器运算能力较弱，资源有限，支持网络化困难，而且在图形用户界面实现较为困难，近年来已较少使用。随着嵌入式系统的发展，电子 海图应用系统有了更好的选择，使用嵌入式32位处理器和嵌入式操作系统的产品逐渐出现。由于系统集成度高、硬件成本较低等特点，在近几年获得较多应用。而 采用Windows CE、Vxworks、Palm OS等商用嵌入式操作系统，存在软件开发成本较高的缺点。
本文提出并设计了一种基于GPS和电子海图，使用嵌入式32位处理器和嵌入式Linux的船舶导航系统。该系统采用Motorola公司的MPC823E 嵌入式处理器，外接GPS接收仪和256色液晶显示器，基于嵌入式Linux操作系统，具有源码开放、易移植、模块化、资源丰富的优势。图形用户界面 (GUI)采用QT/Embedded图形开发库，电子海图使用海司航保部的符合国家军用标准的矢量海图，并预先对电子海图数据进行预处理，删除冗余数 据，进行二维几何数据压缩，建立网格索引。在此基础之上进行船舶导航系统软件设计，使得系统响应速度大大加快。
1 系统硬件结构和软件开发平台
系统整体结构如图1所示。本系统使用Motolora公司的MPC823E嵌入式处理器，该处理器采用嵌入式PowerPC处理核，采用RISC技术，主 频为75MHz，具有强大的处理能力，并针对通信进行优化，通过独立的通信处理模块(CPM)专门处理通信事务。系统通过通用串行总线控制器(USB)外 接键盘和鼠标；通过液晶显示(LCD)控制器外接一个256色的TFT LCD 640×480彩色液晶显示器，用于图形用户界面的显示；通过RS232外接GPS接收仪；系统外扩32MB Flash空间，用于存储Linux内核、应用程序和电子海图数据；系统外扩32MB SDRAM，用于操作系统内存空间，存放动态数据和运行程序。
系统软件基于嵌入式Linux操作系统，使用C++语言进行软件开发，并选择QT/Embedded作为图形用户界面(GUI)开发环境。QT是 Trolltech公司推出的跨平台C++图形用户开发库，QT/Embedded是QT面向嵌入式应用的版本，具有可移植性强，支持Linux、 Windows、Mac的优点，移植到新平台时，只需用该平台的编译器重新编译即可；面向对象，采用C++语言，加上特有的信号/槽(singal /slot)机制，使得面向对象的程序设计变得简单而有效；可裁剪，通过去掉无关模块可以调整库文件的大小，适合嵌入式系统使用；GUI界面支持大量标准 的窗口部件，并提供了界面设计工具designer；支持国际化，支持中文显示，并提供了多语言支持工具linguist。QT/Embedded强大的 图形绘制功能在电子海图的应用系统中得到了充分的应用。
系统从全球定位系统GPS实时获取船舶位置(包括经纬度与时间等)和航行信息(包括船速与航向等)，在电子海图上显示相关导航信息，用户通过精简的鼠标键盘操作，提供海图漫游、海图查询和航行信息管理等功能。
2 电子海图数据处理
2.1 电子海图数据组织结构
本系统使用海司航保部的军用矢量海图格式MVCF(Military Vector Chart Format)[1]海图。MVCF以图幅为单位组织，采用目录结构，目录名即为电子海图的编号。一个图幅目录由一个元数据文件和多个海图层次文件组成。 元数据文件记录每幅图的比例尺、基准纬度等控制信息，海图层次文件由40多种图层文件组成。例如海洋陆地层、港口设施层等。每一种图层文件由图形文件、索 引文件和属性文件组成。其中图形文件记录了海图要素的墨卡托投影坐标数据，索引文件记录了对应的图形文件中海图要素在图形文件中的偏移量，属性文件是 dbase表文件，记录了海图要素的属性，包括要素的名字、备注等。
这样一幅海图包括130多个文件，本系统使用的海图包括中国总图、沿海航行图、港湾图等共74幅海图，占用空间260多兆字节。由于嵌入式系统存储空间和处理器运算能力的限制，需要在PC机上对电子海图进行数据精简压缩和优化，以提高系统响应速度。
2.2 电子海图数据压缩
(1)删除冗余数据
MVCF海图数据量大，线状要素和多边形要素细节丰富，而嵌入式电子海图应用系统由于液晶显示器的大小和分辨率的限制，有相当一部分数据浪费。本系统使用 的液晶显示器分辨率为640×480，长和宽为21cm×15cm，可以计算出像素间距约为0.031cm。用各种比例尺的电子海图显示时，线状或面状实 体的某些点的间隔如果小于像素间距，显然无法显示，应删除这种冗余点。以像素间距作为阀值，删除海图冗余数据，算法如下：
选定一个线状或面状实体，顺序遍历其坐标点，除起点和终点外，对每个点计算该点与上一个点的距离，若小于阀值，则删除该点。
(2)二维几何压缩
使用合适的二维几何压缩算法能使电子海图在保持形状的前提下减少数据量。本系统使用Douglas-Poiker算法[2]进行线状和面状实体的压缩。该 算法的思想是，从一个近似的形状开始，逐步修正。该算法同样需要一个阀值，本系统可使用上文的同一阀值。以面状实体为例，算法过程如下：
选择多边形P的两个顶点V1和V2，考虑V1、V2，V1组成的多边形Q是P的一个近似，扫描P中其他顶点，选择距离Q的边最远的顶点W，把W加入到Q中 形成新的多边形，继续扫描P中的其他顶点，直到P中剩余的顶点距离Q边的最长距离小于阀值为止。多边形Q即为压缩结果。
2.3 建立网格索引
高效的索引结构是提高数据访问效率的关键。MVCF海图数据量大，电子海图应用系统实际使用过程中，显示的区域通常只是一个图幅的一部分，如果能快速搜索 到这部分的海图数据，系统的响应速度将大大提高。本系统使用网格索引，MVCF海图按比例尺分为从1：4000000到1：25000共10多级，对每一 种比例尺的海图，都建立一个网格索引，方法如下：
用一个矩形网格与海图要素逐个进行相交或包容判断，凡是在网格中的海图要素，就记录下该要素在图形文件内的偏移量，最后形成网格索引文件。其中，多边形要 素与矩形网格的相交判断方法是，若多边形的一部分端点落在矩形内，而另一部分却落在矩形的外部，则两者是相交的；多边形与矩形的包容判断是，若多边形所有 的端点落在矩形内则是包容于关系，若矩形所有的端点落在多边形内则是包容关系。线状要素也可用相似的方法判断。
3 系统软件的设计与实现
系统软件如图2所示，主要由以下模块组成：系统界面与管理模块、海图数据模块、海图算法模块、海图显示模块、航行信息管理模块、GPS接收模块等。
系统界面与管理模块：实现系统主界面和操作菜单，通过调用其它模块实现海图漫游、自动对中、海图查询、管理航线、保存航行记录等功能。
海图数据模块：负责读取电子海图文件，实现海图查询功能。通过dbase属性文件搜索地图要素，可以通过SQL语句在属性文件中找到该要素，从而得到该要素在索引文件中的位置。
海图算法模块：包括程序中用到的各种算法，如地理坐标、墨卡托投影坐标和屏幕坐标之间的相互转换[3]，点与点、点与线之间距离，线的长度，多边形的周长和面积等。
海图显示模块：海图显示是系统的核心模块。该模块根据管理模块给出的中心点位置及显示范围的参数，确定需要绘图的网格，根据网格索引，快速完成绘制海图的 功能。考虑到海图漫游通常是连续的，使用了位图缓存来提高响应速度，每次画图的时候，先在缓存中找，找不到则扩大范围画图，并保存到位图缓存，对缓存的管 理采用最近最少使用替换算法(LRU)。具体流程如图3所示。