基于模型驱动的图像处理算法实现及优化

王子豪 禹春竹 王 宝 韩翔宇

北京航天自动控制研究所，北京100854

随着航天领域的不断发展，航天嵌入式软件的规模、复杂度日益增长，安全性、可靠性等方面的需求也不断提高，这对传统嵌入式软件开发方法提出了很大的挑战。作为一种解决方案，基于模型驱动的软件开发方法得到了一定的应用与发展，相较于传统的软件开发方法，基于模型驱动的软件开发方法具有开发效率高、成本低等优点，同时形式化建模以及模型验证技术可以提升软件的安全性、可靠性，能更好地满足嵌入式软件开发的需求。

基于模型驱动的软件开发方法中的一项重要内容是代码自动生成技术。目前，SCADE，UML和Simulink等建模工具均支持代码自动生成，但相对于其他工具，SCADE自动生成的代码满足DO-178B标准，与模型具有一致性，可直接与项目其他部分代码进行集成[1]，具有很大优势，故本文选择SCADE作为建模工具。

SCADE建模工具对控制系统等逻辑控制软件的设计、实现方法较为完善，已有很多成功、完善的案例[2-3]。但对于图像处理算法这类具有数据量大、迭代计算次数多等特点的建模对象，SCADE是否能够建立出执行效率满足需求的算法模型，是值得关注的问题。本文对基于SCADE的图像处理算法的实现进行了探索，建立了图像处理经典算法Sobel算法的模型，对模型优化方法进行了总结，并针对算法模型的执行效率进行了优化，得到了具有较高执行效率的算法模型。

1 简介

1.1 建模工具简介

SCADE(全称为Safety Critical Application Development Environment)是由法国ESTEREL技术公司开发的高安全性应用开发环境，其针对高安全性系统及软件开发提出了一套完整的基于模型驱动的嵌入式开发解决方案[4]。利用该开发环境可有效地节约开发、测试时间，同时可更好地满足软件安全性需求。

SCADE模型设计工具SCADE Suite的核心是形式化同步语言Lustre语言，在用户建立图形化模型之后，系统将图形化模型转换为形式化语言，进而利用KCG代码生成器自动生成可执行的C代码。生成的C代码可保证与模型具有一致性，通过SCADE自身仿真工具进行模型仿真，结果符合预期，则生成的代码可集成至项目中。

1.2 实现算法简介

图像边缘检测是图像处理领域中的一个经典问题，其目的是检测出目标图像中的边缘信息，即检测出目标图像中局部变化最为明显的部分。目前已有很多成熟的边缘检测算法，如差分边缘检测、Reborts算法、Sobel算法等[5]，其中Sobel算法因其简单且高效等优点，在航天领域的图像信息处理等软件中有着极为重要的应用；而且Sobel算法具备图像处理算法的典型特点，所以本文选取Sobel算法作为研究对象。

Sobel算法的核心是2个Sobel算子，可记为x方向梯度算子和y方向梯度算子，分别用来检测目标图像的水平边缘和垂直边缘，具体表示如下：

将目标图像与Sx和Sy算子进行卷积运算，即可得到边缘信息图像。边缘信息图像位于边界行列的点均赋为0，其他点的计算公式为：

其中，S(x,y)为图像中一点灰度值；(x,y)为该点坐标，Sx(x,y)及Sy(x,y)分别为该点与x，y方向梯度算子卷积结果。

目前成熟的Sobel算法(由于水平边缘检测与垂直边缘检测算法实现上具有相似性， 所以本文后续对Sobel算法的讨论与建模均以水平边缘检测为例)程序的流程图如图1所示。

2 基于SCADE的Sobel算法

2.1 模型的建立

根据传统Sobel算法实现思路，利用SCADE工具进行建模，模型的实现共分为3层。

顶层模型如图2所示。

图1 Sobel算法流程图

图2 算法实现的顶层模型

本层模型利用全0数组作为FOLD迭代器中累加器的输入，对累加器进行初始化，将原始图像srcImage作为迭代器输入，经过(Height-1)次迭代计算输出结果图像，其中迭代器内部实现如图3所示。

图3 算法实现的中层模型

本层利用if-else块实现以下功能：当进行第一次迭代时，模型执行if节点中的操作，利用累加器中的全0数组对结果图像进行初始化；当进行第二次及以后的迭代时，模型将执行else节点中的操作，再次利用全0数组作为第二层中FOLD迭代器累加器的输入，并将原始图像srcImage以及当前迭代次数(行索引)作为迭代器输入，经过(Width-1)次迭代计算输出结果图像，该层迭代器内部实现如图4所示。

本层首先通过计算迭代次数，确定本次迭代的目标点索引，并将索引存储为局部变量icur，然后利用if-else块实现以下功能：当进行第1次迭代时，模型执行if节点中的操作，对结果图像全赋为0；当进行第2次及以后的迭代时，模型将执行else节点中的操作，根据水平边缘检测公式对目标点进行计算，并将结果赋予结果图像数组对应索引的元素。

通过进行模型仿真，模型计算结果符合预期，模型建立正确。但通过SCADE性能分析工具分析发现模型执行效率较低，迭代器部分的时间开销很大，故考虑对模型进行优化。

图4 算法实现的底层模型

2.2 优化方案

2.2.1 合理选择迭代器

SCADE提供了2类迭代器，用来对数组进行迭代计算和处理，分别称为FOLD迭代器和MAP迭代器。

FOLD迭代器：

图5为一个迭代次数为N的FOLD迭代器，其中a和Output分别作为迭代器的输入和输出，Input1, Input2,……InputM均为长度为N的数组(元素数据类型与a和Output相同)，作为迭代器的输入，Operator可看作迭代计算函数。该FOLD迭代器生成代码的格式为：

for (idx = 0; idx

kcg_copy(&acc,Output);

Operator(

idx,

&acc,

Input1,

…

InputM,

output);

MAP迭代器：

图5 fold迭代器示意图

图6为一个迭代次数为N的MAP迭代器，其中Input1, Input2, …… ，InputM均为长度为N的数组，作为迭代器的输入，Output同样为长度为N的数组，作为迭代器的输出，Operator可看作迭代计算函数。该MAP迭代器生成代码的格式为：

for (idx = 0; idx

(*output)[idx] = Operator(

idx,

Input1[idx],

…

InputM[idx]);

}

图6 MAP迭代器示意图

对比2种迭代器生成的代码可以看出，FOLD迭代器在每次循环的开始，都会利用拷贝函数，将上次循环计算出的结果拷贝到累加器中，如果进行迭代计算的数据量很大，则拷贝的过程会对程序的执行造成很大的开销。所以，在数据量较大且迭代计算次数多的情况下，除非无法利用MAP迭代器建立满足需求的模型，否则在模型设计中应当尽量规避FOLD迭代器的使用，即尽可能通过重新设计算法流程，使用MAP迭代器对FOLD迭代器进行替换，达到减少迭代处理的时间开销的目的。

2.2.2 工具方面的优化

除了模型设计上的优化，还可以利用KCG代码生成器内置的一些程序执行效率的优化功能来对模型进行小幅优化，此处列举2项对本次算法优化有效的优化功能:

在KCG设置中可以将某一模块设置为“Expand”，即内联模块，这样在代码生成过程中该模块将以内联函数的方式生成，从而在代码执行时，可以有效地节省调用函数带来的额外时间开销。与选取函数作为内联函数的标准相同，建模时应当选取调用次数多，且内部实现简单的模块作为内联模块。

另外，在KCG设置中可以将局部变量设置为static形式，即将其定义在静态存储区，这样所有局部变量会在程序初始化时被分配定义，从而在程序执行时能够节省变量分配时间，达到执行时间优化的目的。

2.3 优化后的算法模型

根据上文分析、总结的优化方法，利用map迭代器实现Sobel算法，顶层模型如图7所示。

图7 优化后的顶层模型

根据map迭代器的实现特性，将算法拆分为两部分实现，即先迭代处理每一行元素，实现初始矩阵列与列之间的计算；随后对处理后的矩阵进行转置，再对每一列元素进行迭代处理，实现初始矩阵行与行之间的计算，最后经过转置得到最终输出图像矩阵。2部分内容的实现逻辑相似，故本文只介绍第一部分内容。图8为该层迭代器(Row_Deliver)内部模型。

图8 优化后的中层模型

将上层模型传入的原始图像矩阵的行作为map迭代器的输入，对其进行迭代计算，迭代器内部具体计算逻辑、方法如图9所示。

图9 优化后的底层模型

本层利用if-else块实现以下功能：如果是行内首尾元素，则输出为0；否则计算当前索引对应元素的前一位元素和后一位元素之差，将差值赋给结果数组的该索引元素。

通过进行模型仿真，模型计算结果符合预期，模型建立正确。

3 实验

将优化前后的模型分别生成代码，导入现有工程，配置接口，与手写成熟代码进行执行时间对比实验。实验平台为联想ThinkCentre M4500t，配置Intel(R) Core(TM) i7-4790 CPU,主频3.60GHz，内存3.41GB。搭载操作系统为Windows XP Professional，使用集成开发环境Visual Studio 2010。

2种模型生成代码执行结果与手写成熟代码均相同，代码执行时间的对比如表1所示。

表1 代码执行时间对比

通过表1可以看出，对模型进行优化之后，代码的执行时间提升了2个数量级，有效缩短了与手写成熟代码之间的差距。也说明SCADE针对Sobel此类运算数据多、迭代计算次数多的算法，可以建立出正确、具有可靠性的模型，并且可以通过模型设计思路的优化，建立执行效率较高的模型。

4 结论

根据传统Sobel算法的实现流程设计了基于SCADE的Sobel算法模型，针对模型时间开销过大的问题，对模型进行了分析，总结了优化方法；通过重新设计模型(使用MAP迭代器以减少迭代计算开销)以及使用KCG代码生成器内置优化功能对模型进行了优化，使其生成代码执行效率提升了2个数量级，具备了进行工程化的基础。

受到工具本身的制约，利用SCADE对数据量大、迭代计算次数多的算法进行建模，在迭代过程中不可避免会造成一定的开销，使得程序执行效率低于人工编写的成熟代码。所以在设计模型时，要结合工具能力而不是完全依靠传统编码思想进行设计，尽可能地提高程序执行效率。