多数据源图象点变换的快速可视化算法

　　在常规的图象处理中，空间域点变换处理^［1，2］是一种最基本的图象处理操作.大多数的空间域点变换处理算法是以常规图象数据为处理对象，图象数据通常是8位的整数数据.还有一类专业图象数据，在本文中称为多源图象数据，包括遥感数据、航测数据、航空雷达数据、各种摄影的图象数据，以及通过数字化和网格化的地质图、地形图，各种地球物理、地球化学数据、高程数据和其他专业图象数据.它们的取值范围变化很大，需要用不同的数据类型来表示，如遥感数据通常用8位的整数表示，地球物理数据通常用32位的浮点数表示.为处理多源图象数据，常规图象处理系统通常采用的方法是对多源图象数据进行量化处理，将数据的取值范围归一到8位整数范围内，但是这种量化处理是以损失专业图象数据的精度为代价的，有时这种损失专业图象数据精度的方法是不可接受的.
　　为了保证精度不丢失和提高空间域点变换处理的速度，本文提出了多源图象点变换的快速可视化算法(FVAMSIPT).它能处理所有可能的数据类型，包括8位的常规灰度图象到64位的双精度浮点专业图象数据.

图1　多源图象点变换的快速可视化
Fig.1　Fast visualization of multisource image point transformation

1　FVAMSIPT流程图
　　
　　在FVAMSIPT中引入了二级查找表，分别称为重映射表(t_rmap)和彩色查找表(t_clut).利用重映射表(t_rmap)，可进行图象的快速点变换处理，并记录点变换的变换关系；利用彩色查找表(t_clut)，可进行显示器的伽码校正和彩色映射(如假彩色变换：灰度值映射为彩色RGB值).下面给出整个算法的流程图，流程图分两部分，如图1和图2所示.根据点变换的方式、输入范围和统计的图象直方图，点变换处理只需对重映射表进行处理.

图2　多源图象数据空间域快速点变换
Fig.2　Fast point transformation of multisource image

2　FVAMSIPT描述
　　
　　(1)求最大值、最小值.扫描图象文件，计算图象的最大值、最小值，并用双精度数据类型保存图象的最大值、最小值.若是灰度图象只需保存灰度通道的最大值、最小值，记为d_max，d_min；若是RGB图象则需分别保存R，G，B三通道的最大值、最小值，分别记为d_rmax，d_rmin，d_gmax，d_gmin，d_bmax，d_bmin.
　　(2)统计直方图.考虑到图象的最大可能尺寸，定义直方图为无符号4字节的数组.若是灰度图象，定义灰度通道的直方图为unsigned long d_hist［n_max］，若是RGB图象则分别定义R，G，B通道的直方图为unsigned long d_rhist［n_max］，unsigned long d_ghist［n_max］，unsigned long d_bhist［n_max］，n_max为直方图的最大表项，按以下方式确定.
　　对8位有符号数据和8位无符号数据，由于有256个灰度级，定义直方图的表项(n_max)为256项；对8位无符号数据n_max表示0至255灰度级的象元个数，对8位有符号数据表示－128至127灰度级的象元个数.对8位数据的直方图而言，统计结果无信息损失，所占内存空间较小.
　　对16位有符号数据和16位无符号数据，由于有65536个灰度级，定义直方图的表项(n_max)为65536项；对16位无符号数据n_max表示0至65535灰度级的象元个数，对16位有符号数据表示－32768至32767灰度级的象元个数.对16位数据的直方图而言，统计结果无信息损失，所占内存空间较大.
　　对32位有符号数据、32位无符号数据、32位浮点数据和64位浮点数据，由于灰度级太多，尤其32位浮点数据和64位浮点数据，灰度级可看作是连续量，所以对这4类数据类型无法按通常直方图意义来定义表项的数目.考虑到精度和空间的矛盾以及显示设备为256级，定义直方图的表项(n_max)为65536项；根据最大值和最小值，将各通道的数据按线性量化的方式量化为0至65535灰度级，并按量化的灰度级统计直方图.对灰度图象的象元，按下式统计直方图
　　w_i=［(d_raw-d_min)/(d_max-d_min)］×65536，
　　d_hist［w_i］=d_hist［w_i］+1.
其中：d_raw为象元的值，w_i为量化的灰度级.对32位和64位数据的的直方图而言，统计结果是原始数据量化后的结果，有信息损失，内存空间的开销较大.
　　(3)建重映射表.重映射表是一类查找表，利用重映射表(t_rmap)，可进行图象的快速点变换处理.在缺省时，重映射表记录的是原始的线性变换关系，即重映射表的映射值等于映射表的表项索引值(t_rmap［w_rmi］=w_rmi).这时，对原始图象未作任何处理，按显示流程图可知，最终显示的原始图象是按最大值和最小值线性拉伸的结果.
　　(4)计算重映射表.根据点变换的方式、输入范围和统计的直方图，点变换处理只需对重映射表进行处理.点变换包括有多源数据灰度线性拉伸、多源数据灰度分段线性拉伸、多源数据灰度直方图均衡化、多源数据灰度正规化、多源数据平方变换等.下面给出灰度线性拉伸变换和灰度直方图均衡化变换的算法.
　　①多源数据灰度线性拉伸.根据线性拉伸处理的累加直方图的范围(f_b开始范围，f_e结束范围)，如f_b=0.01，f_e＝0.99表示处理落入累加直方图范围在0.01～0.99的象元值，由直方图的统计表d_hist［］，计算需处理的重映射表的范围l_b，l_e.按以下公式对重映射表进行变换处理

　　②灰度直方图均衡化变换的算法.定义累加直方图h_sum，由统计的直方图计算累加直方图，然后按以下公式对重映射表进行变换处理

t_rmap［l_i］=h_sum［l_i］×
(n_max-1)/h_sum［n_max-1］.
其中h_sum［n_max-1］记录的是图象的象元总数.

3　FVAMSIPT分析

3.1　时间复杂度分析
　　由上面的流程图和算法描述可知，本算法需要图象的最大值d_max和最小值d_min，并在需要时计算图象的直方图.这是本算法最费时的操作，因为求最大值d_max、最小值d_min必须对全图扫描一遍才能求出.通常对最大值d_max、最小值d_min可采用在生成原始图象文件时保留在图象文件头中，这样在显示和空间域点变换中就不考虑这一费时的操作.
　　当点变换需要图象的直方图信息时，通常也需对全图扫描一遍才能求出.考虑到图象的局部象元的空间

图3　多数据源图象空间域点变换交互式可视化控制界面
Fig.3　Interface of fast visual algorithm of multisource image point transformation

相关性，可采用规则采样或随机采样的方式来减少统计时间，具体的采样间隔可根据图象的大小和图象类型确定.采用这一方法后，统计直方图的时间大大减少.
　　本算法的显示速度与图象的大小无关，图象可能是数据量在几百兆到几千兆的大图象，而实际的显示屏幕是有限的；显示时只需将显示屏幕对应的原始图象数据取出(根据缩放比例，可进行动态重采样)，按显示流程图所示，经过线性拉伸、二级查找表变换后，就得到RGB显示数据.本显示过程可达到实时交互浏览的程度.
　　点变换处理的数据是重映射表和直方图表，这两个表的最大表项为65536项，与图象的大小无关，故点变换处理的时间是一很小的常数O(65536)，这个时间可忽略不计.
　　综上所述，本算法的时间复杂度在于计算一次最大值d_max和最小值d_min的时间.在计算后，就可达到实时交互点变换和交互浏览的程度.
3.2　空间复杂度分析
　　(1)本算法需要为各个通道直方图分配256K字节(每表项4字节，共65636表项)，对一个通道的灰度图象需要256K字节，对RGB三通道的彩色图象需要768K字节；(2)本算法需要为各个通道的重映射表分配128K字节(每表项2字节，共65636表项)，对一个通道的灰度图象需要128K字节，对RGB三通道的彩色图象需要384K字节；(3)本算法需要为RGB彩色查找表分配192K字节的空间(每表项1字节，每表65636表项，共3表).

4　FVAMSIPT实现
　　
　　MSIMAGES是一个32位专业图象处理分析软件，以多源图象数据为处理分析对象.在MSIMAGES中，作者实现了FVAMSIPT.
　　图3为多数据源图象空间域点变换交互式可视化控制界面，其中左侧的图象h301451.msi为高程矩阵数据，数据类型为4字节的浮点数据，d_max=198.151，d_min=12.7481；右侧的查找表编辑对话框为交互式控制界面，由两部分组成：直方图控制组和查找表控制组.在本查找表编辑对话框中，显示的是红色通道的所有直方图(包括变换前和变换后的直方图)，变换前的直方图以深灰色绘制，呈双峰状，变换后的直方图以红色绘制，呈水平状(这由均衡化点变换决定)，曲线表示重映射表曲线，对重映射表曲线可用鼠标绘制.
　　交互式查找表编辑体现在两方面：(1)通过选定变换通道、点变换方式和输入范围，然后按“应用变换方式和输入范围”按钮；(2)直接在查找表、直方图显示控制区修改重映射表曲线，用这两种方式修改重映射表曲线后，系统将实时更新显示图象.

5　结论
　　
　　多数据源图象点变换的快速可视化算法(FVAMSIPT)是对常规的图象查找表(LUT)变换算法的发展.利用本算法，可对多源图象数据的各类点变换进行实时的交互处理并实时显示.

1　周孝宽，曹晓光，陈建革等.实用微机图象处理.北京：北京航空航天大学出版社，1994. 191～204
2　毕厚杰，陈延标，郑树德等.图象通信工程.北京：人民邮电出版社，1993. 237～252

FAST VISUAL ALGORITHM OF
MULTISOURCE IMAGE POINT TRANSFORMATION

Li Jun　 Zhang Fayong　Xu Shiwu
(Faculty of Information Engineering, China University of Geosciences, Wuhan　430074)

　　
　　Abstract　As multisource images have very large data range, how to complete quickly point transformation is difficult in image processing system. By introducing concept of re_mapping table, color look_up_table and two_level color look_up_table, this paper puts forward an arithmetic called FVAMSIPT. By this algorithm, the image point transformation of multisource image data can be timely completed.
　　Key words　multisource image, look_up_table, histogram, gray transformation, image processing system, geographic information system.