基于模型驅動的圖像處理算法實現(xiàn)及優(yōu)化

王子豪 禹春竹 王 寶 韓翔宇

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

隨著航天領域的不斷發(fā)展，航天嵌入式軟件的規(guī)模、復雜度日益增長，安全性、可靠性等方面的需求也不斷提高，這對傳統(tǒng)嵌入式軟件開發(fā)方法提出了很大的挑戰(zhàn)。作為一種解決方案，基于模型驅動的軟件開發(fā)方法得到了一定的應用與發(fā)展，相較于傳統(tǒng)的軟件開發(fā)方法，基于模型驅動的軟件開發(fā)方法具有開發(fā)效率高、成本低等優(yōu)點，同時形式化建模以及模型驗證技術可以提升軟件的安全性、可靠性，能更好地滿足嵌入式軟件開發(fā)的需求。

基于模型驅動的軟件開發(fā)方法中的一項重要內(nèi)容是代碼自動生成技術。目前，SCADE，UML和Simulink等建模工具均支持代碼自動生成，但相對于其他工具，SCADE自動生成的代碼滿足DO-178B標準，與模型具有一致性，可直接與項目其他部分代碼進行集成[1]，具有很大優(yōu)勢，故本文選擇SCADE作為建模工具。

SCADE建模工具對控制系統(tǒng)等邏輯控制軟件的設計、實現(xiàn)方法較為完善，已有很多成功、完善的案例[2-3]。但對于圖像處理算法這類具有數(shù)據(jù)量大、迭代計算次數(shù)多等特點的建模對象，SCADE是否能夠建立出執(zhí)行效率滿足需求的算法模型，是值得關注的問題。本文對基于SCADE的圖像處理算法的實現(xiàn)進行了探索，建立了圖像處理經(jīng)典算法Sobel算法的模型，對模型優(yōu)化方法進行了總結，并針對算法模型的執(zhí)行效率進行了優(yōu)化，得到了具有較高執(zhí)行效率的算法模型。

1 簡介

1.1 建模工具簡介

SCADE(全稱為Safety Critical Application Development Environment)是由法國ESTEREL技術公司開發(fā)的高安全性應用開發(fā)環(huán)境，其針對高安全性系統(tǒng)及軟件開發(fā)提出了一套完整的基于模型驅動的嵌入式開發(fā)解決方案[4]。利用該開發(fā)環(huán)境可有效地節(jié)約開發(fā)、測試時間，同時可更好地滿足軟件安全性需求。

SCADE模型設計工具SCADE Suite的核心是形式化同步語言Lustre語言，在用戶建立圖形化模型之后，系統(tǒng)將圖形化模型轉換為形式化語言，進而利用KCG代碼生成器自動生成可執(zhí)行的C代碼。生成的C代碼可保證與模型具有一致性，通過SCADE自身仿真工具進行模型仿真，結果符合預期，則生成的代碼可集成至項目中。

1.2 實現(xiàn)算法簡介

圖像邊緣檢測是圖像處理領域中的一個經(jīng)典問題，其目的是檢測出目標圖像中的邊緣信息，即檢測出目標圖像中局部變化最為明顯的部分。目前已有很多成熟的邊緣檢測算法，如差分邊緣檢測、Reborts算法、Sobel算法等[5]，其中Sobel算法因其簡單且高效等優(yōu)點，在航天領域的圖像信息處理等軟件中有著極為重要的應用；而且Sobel算法具備圖像處理算法的典型特點，所以本文選取Sobel算法作為研究對象。

Sobel算法的核心是2個Sobel算子，可記為x方向梯度算子和y方向梯度算子，分別用來檢測目標圖像的水平邊緣和垂直邊緣，具體表示如下：

將目標圖像與Sx和Sy算子進行卷積運算，即可得到邊緣信息圖像。邊緣信息圖像位于邊界行列的點均賦為0，其他點的計算公式為：

其中，S(x,y)為圖像中一點灰度值；(x,y)為該點坐標，Sx(x,y)及Sy(x,y)分別為該點與x，y方向梯度算子卷積結果。

目前成熟的Sobel算法(由于水平邊緣檢測與垂直邊緣檢測算法實現(xiàn)上具有相似性， 所以本文后續(xù)對Sobel算法的討論與建模均以水平邊緣檢測為例)程序的流程圖如圖1所示。

2 基于SCADE的Sobel算法

2.1 模型的建立

根據(jù)傳統(tǒng)Sobel算法實現(xiàn)思路，利用SCADE工具進行建模，模型的實現(xiàn)共分為3層。

頂層模型如圖2所示。

圖1 Sobel算法流程圖

圖2 算法實現(xiàn)的頂層模型

本層模型利用全0數(shù)組作為FOLD迭代器中累加器的輸入，對累加器進行初始化，將原始圖像srcImage作為迭代器輸入，經(jīng)過(Height-1)次迭代計算輸出結果圖像，其中迭代器內(nèi)部實現(xiàn)如圖3所示。

圖3 算法實現(xiàn)的中層模型

本層利用if-else塊實現(xiàn)以下功能：當進行第一次迭代時，模型執(zhí)行if節(jié)點中的操作，利用累加器中的全0數(shù)組對結果圖像進行初始化；當進行第二次及以后的迭代時，模型將執(zhí)行else節(jié)點中的操作，再次利用全0數(shù)組作為第二層中FOLD迭代器累加器的輸入，并將原始圖像srcImage以及當前迭代次數(shù)(行索引)作為迭代器輸入，經(jīng)過(Width-1)次迭代計算輸出結果圖像，該層迭代器內(nèi)部實現(xiàn)如圖4所示。

本層首先通過計算迭代次數(shù)，確定本次迭代的目標點索引，并將索引存儲為局部變量icur，然后利用if-else塊實現(xiàn)以下功能：當進行第1次迭代時，模型執(zhí)行if節(jié)點中的操作，對結果圖像全賦為0；當進行第2次及以后的迭代時，模型將執(zhí)行else節(jié)點中的操作，根據(jù)水平邊緣檢測公式對目標點進行計算，并將結果賦予結果圖像數(shù)組對應索引的元素。

通過進行模型仿真，模型計算結果符合預期，模型建立正確。但通過SCADE性能分析工具分析發(fā)現(xiàn)模型執(zhí)行效率較低，迭代器部分的時間開銷很大，故考慮對模型進行優(yōu)化。

圖4 算法實現(xiàn)的底層模型

2.2 優(yōu)化方案

2.2.1 合理選擇迭代器

SCADE提供了2類迭代器，用來對數(shù)組進行迭代計算和處理，分別稱為FOLD迭代器和MAP迭代器。

FOLD迭代器：

圖5為一個迭代次數(shù)為N的FOLD迭代器，其中a和Output分別作為迭代器的輸入和輸出，Input1, Input2,……InputM均為長度為N的數(shù)組(元素數(shù)據(jù)類型與a和Output相同)，作為迭代器的輸入，Operator可看作迭代計算函數(shù)。該FOLD迭代器生成代碼的格式為：

for (idx = 0; idx

kcg_copy(&acc,Output);

Operator(

idx,

&acc,

Input1,

…

InputM,

output);

MAP迭代器：

圖5 fold迭代器示意圖

圖6為一個迭代次數(shù)為N的MAP迭代器，其中Input1, Input2, …… ，InputM均為長度為N的數(shù)組，作為迭代器的輸入，Output同樣為長度為N的數(shù)組，作為迭代器的輸出，Operator可看作迭代計算函數(shù)。該MAP迭代器生成代碼的格式為：

for (idx = 0; idx

(*output)[idx] = Operator(

idx,

Input1[idx],

…

InputM[idx]);

}

圖6 MAP迭代器示意圖

對比2種迭代器生成的代碼可以看出，F(xiàn)OLD迭代器在每次循環(huán)的開始，都會利用拷貝函數(shù)，將上次循環(huán)計算出的結果拷貝到累加器中，如果進行迭代計算的數(shù)據(jù)量很大，則拷貝的過程會對程序的執(zhí)行造成很大的開銷。所以，在數(shù)據(jù)量較大且迭代計算次數(shù)多的情況下，除非無法利用MAP迭代器建立滿足需求的模型，否則在模型設計中應當盡量規(guī)避FOLD迭代器的使用，即盡可能通過重新設計算法流程，使用MAP迭代器對FOLD迭代器進行替換，達到減少迭代處理的時間開銷的目的。

2.2.2 工具方面的優(yōu)化

除了模型設計上的優(yōu)化，還可以利用KCG代碼生成器內(nèi)置的一些程序執(zhí)行效率的優(yōu)化功能來對模型進行小幅優(yōu)化，此處列舉2項對本次算法優(yōu)化有效的優(yōu)化功能:

在KCG設置中可以將某一模塊設置為“Expand”，即內(nèi)聯(lián)模塊，這樣在代碼生成過程中該模塊將以內(nèi)聯(lián)函數(shù)的方式生成，從而在代碼執(zhí)行時，可以有效地節(jié)省調用函數(shù)帶來的額外時間開銷。與選取函數(shù)作為內(nèi)聯(lián)函數(shù)的標準相同，建模時應當選取調用次數(shù)多，且內(nèi)部實現(xiàn)簡單的模塊作為內(nèi)聯(lián)模塊。

另外，在KCG設置中可以將局部變量設置為static形式，即將其定義在靜態(tài)存儲區(qū)，這樣所有局部變量會在程序初始化時被分配定義，從而在程序執(zhí)行時能夠節(jié)省變量分配時間，達到執(zhí)行時間優(yōu)化的目的。

2.3 優(yōu)化后的算法模型

根據(jù)上文分析、總結的優(yōu)化方法，利用map迭代器實現(xiàn)Sobel算法，頂層模型如圖7所示。

圖7 優(yōu)化后的頂層模型

根據(jù)map迭代器的實現(xiàn)特性，將算法拆分為兩部分實現(xiàn)，即先迭代處理每一行元素，實現(xiàn)初始矩陣列與列之間的計算；隨后對處理后的矩陣進行轉置，再對每一列元素進行迭代處理，實現(xiàn)初始矩陣行與行之間的計算，最后經(jīng)過轉置得到最終輸出圖像矩陣。2部分內(nèi)容的實現(xiàn)邏輯相似，故本文只介紹第一部分內(nèi)容。圖8為該層迭代器(Row_Deliver)內(nèi)部模型。

圖8 優(yōu)化后的中層模型

將上層模型傳入的原始圖像矩陣的行作為map迭代器的輸入，對其進行迭代計算，迭代器內(nèi)部具體計算邏輯、方法如圖9所示。

圖9 優(yōu)化后的底層模型

本層利用if-else塊實現(xiàn)以下功能：如果是行內(nèi)首尾元素，則輸出為0；否則計算當前索引對應元素的前一位元素和后一位元素之差，將差值賦給結果數(shù)組的該索引元素。

通過進行模型仿真，模型計算結果符合預期，模型建立正確。

3 實驗

將優(yōu)化前后的模型分別生成代碼，導入現(xiàn)有工程，配置接口，與手寫成熟代碼進行執(zhí)行時間對比實驗。實驗平臺為聯(lián)想ThinkCentre M4500t，配置Intel(R) Core(TM) i7-4790 CPU,主頻3.60GHz，內(nèi)存3.41GB。搭載操作系統(tǒng)為Windows XP Professional，使用集成開發(fā)環(huán)境Visual Studio 2010。

2種模型生成代碼執(zhí)行結果與手寫成熟代碼均相同，代碼執(zhí)行時間的對比如表1所示。

表1 代碼執(zhí)行時間對比

通過表1可以看出，對模型進行優(yōu)化之后，代碼的執(zhí)行時間提升了2個數(shù)量級，有效縮短了與手寫成熟代碼之間的差距。也說明SCADE針對Sobel此類運算數(shù)據(jù)多、迭代計算次數(shù)多的算法，可以建立出正確、具有可靠性的模型，并且可以通過模型設計思路的優(yōu)化，建立執(zhí)行效率較高的模型。

4 結論

根據(jù)傳統(tǒng)Sobel算法的實現(xiàn)流程設計了基于SCADE的Sobel算法模型，針對模型時間開銷過大的問題，對模型進行了分析，總結了優(yōu)化方法；通過重新設計模型(使用MAP迭代器以減少迭代計算開銷)以及使用KCG代碼生成器內(nèi)置優(yōu)化功能對模型進行了優(yōu)化，使其生成代碼執(zhí)行效率提升了2個數(shù)量級，具備了進行工程化的基礎。

受到工具本身的制約，利用SCADE對數(shù)據(jù)量大、迭代計算次數(shù)多的算法進行建模，在迭代過程中不可避免會造成一定的開銷，使得程序執(zhí)行效率低于人工編寫的成熟代碼。所以在設計模型時，要結合工具能力而不是完全依靠傳統(tǒng)編碼思想進行設計，盡可能地提高程序執(zhí)行效率。