基于模型驅動的圖像處理算法實現及優化

王子豪 禹春竹 王 寶 韓翔宇

北京航天自動控制研究所，北京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對數據量大、迭代計算次數多的算法進行建模，在迭代過程中不可避免會造成一定的開銷，使得程序執行效率低于人工編寫的成熟代碼。所以在設計模型時，要結合工具能力而不是完全依靠傳統編碼思想進行設計，盡可能地提高程序執行效率。