Software Cinema

這兩天跟學妹一起在對 Java OpenCV Match Template (以下簡稱 Java OpenCV ) 這個 Tool 作一點修改.

Java OpenCV 其實是一個 Adapter, 把 OpenCV ( 著名的 Computer Vision Library ) 內的 cvMatchTemplate Function ( 用 C++ 寫的 ) 包上 Java 的外衣. 而 cvMatchTemplate 的主要能力就是比對基底影像 ( Source Image ) 與模板影像 ( Template Image ), 找出在基底影像中哪些地方存在著與模板影像相似的影像, 以及該處的位置 ( 在圖片或影像截圖上的 ).

為簡化敘述, 先不論 Java OpenCV 其實是 Adapter 而已, 假設把 Java OpenCV 跟 cvMatchTemplate 包在一起看成一個單一的 Component, 而這個 Component 提供一個 Interface 可以輸入基底影像以及模板影像, 而會回傳一個最佳的比對結果影像物件 ( Java Image Object ), 以及位置. 由於這是此 Component 唯一能夠提供的 Service, 因此就說這是 Java OpenCV 的 Functionality.

但是我們需要的是能夠提供多個比對結果的 Functionality. 例如下面的 Java OpenCV 測試圖, 在四個角落都有幾乎同樣的圓點, 但是 Java OpenCV 只會傳回最相似的一個結果而已. 而我們希望四個結果都可以傳回給我們作選擇.


由於短時間內沒有找到其他的 Tool 如此符合我們的需求, 加上 Java OpenCV 的程式碼其實不長, 因此我們去查看了一下原始碼. 在 Java OpenCV 與 cvMatchTemplate之間是使用 JNI 作連結, 而主要的 Image Matching 都是 cvMatchTemplate 進行的沒錯. cvMatchTemplate 是以逐一影像區塊進行比對的方式, 比完整張圖, 因此用了一個很大的 array 來存所有的比對結果.

<br />/* ...... 前面省略 */<br />float* match_result = (float*)malloc(RESULT_WIDTH*RESULT_HEIGHT*sizeof(float));<br />/* ...... 中間省略 */<br />jfloatArray return_result;<br />return_result = env->NewFloatArray(RESULT_WIDTH*RESULT_HEIGHT);<br />env->SetFloatArrayRegion(return_result, 0, RESULT_WIDTH*RESULT_HEIGHT, (jfloat*)match_result);<br />free(match_result);<br /><br />return return_result;<br />

而 cvMatchTemplate 回傳給 Java OpenCV 的內容其實包含了所有的比對結果, 而不是只有最佳的比對結果. 換句話說, 是在 Java OpenCV 內被做了過濾. 更嚴格來說是在 matchTemplate method 回傳之前, 在 findMaxPoint 裡面被過濾掉了, 只留下最佳的比對結果位置.

<br />public Point matchTemplate(int x, int y, int w, int h, int method )<br /> {<br /> float[] sourceImgData = getFloatPixels(sourceImgBI, x, y, w, h);<br /> <br /> //Print sourceImgData<br /> //displayBufferedImage(getImageGrayFromFloat(sourceImgData, w, h), "sourceImgData");<br /> <br /> this.cvMatchTemplateFloat = cvMatchTemplate(sourceImgData, w, h, this.templateImgData, this.TEMPLATE_W, this.TEMPLATE_H, method);<br /> RESULT_W = w-this.TEMPLATE_W+1;<br /> RESULT_H = h-this.TEMPLATE_H+1;<br /> //System.out.println("result: <"+RESULT_W+","+RESULT_H+">");<br /> //System.out.println("result.length =" + this.cvMatchTemplateFloat.length);<br /> <br /> Point resultPoint = null;<br /> if ((method==MatchTemplate.CV_TM_SQDIFF) || (method==MatchTemplate.CV_TM_SQDIFF_NORMED))<br /> {<br /> resultPoint = findMinPoint(x, y);<br /> }<br /> else<br /> {<br /> resultPoint = findMaxPoint(x, y);<br /> }<br /> //getMatchImage();<br /> //displayImages(x, y);<br /> <br /> return resultPoint;<br /> }<br /> <br /> private Point findMaxPoint(int x, int y)<br /> {<br /> int maxIndex = 0;<br /> float maxValue= Float.MIN_VALUE;<br /> for(int i = 0 ; i< this.cvMatchTemplateFloat.length; i++)<br /> {<br /> if (this.cvMatchTemplateFloat[i]>=maxValue)<br /> {<br /> maxValue = this.cvMatchTemplateFloat[i];<br /> maxIndex = i;<br /> }<br /> }<br /> int max_h = maxIndex / RESULT_W;<br /> int max_w = maxIndex - max_h*RESULT_W;<br /> //System.out.println("max point: <"+(max_w+x)+","+(max_h+y)+">");<br /> return new Point(max_w+x, max_h+y); <br /> }<br />

這樣一來事情就很簡單了, 我們另外加上了一個 matchTemplateMultiple method, 使用動態決定 Threshold 的方式來過濾出最好的幾個比對結果, 因此可以獲得多個比對結果.

但我覺得有趣的是, 很顯然地 Java OpenCV Component 本身就具有偵測到所有可能比對結果的 Capability, 只是由於他只提供了 matchTemplate 的 Interface, 因此形成了 Functionality 與 Capability 不相稱的情況. 基於 Encapsulation 的原則, 我們不可能從 Interface 就得知 Java OpenCV Component 的真實 Capability, 但是透過知道 Java OpenCV 原本的 Capability, 卻使得我可以評估花較少的 Effort 去增加 Java OpenCV 的 Functionality, 變相地增加了 Java OpenCV 的 Re-usability.

之前會說希望把 Java OpenCV 看成單一 Component 而不要管 Adapter 身份是因為此 Case 有點特殊, Adapter 本身本來就可能對於原本的 Component Functionality 有遮蔽的作用. 但我認為對於一般 Component 來說也可能會有此現象發生, 如果可以有辦法偵測或是表達 Component 本身的 Capability 與 Functionality 之間的差異, 或許會是一件很有用的資訊.

UNITED_BOTTLE 是在 2007 德國紅點設計獎 (International Red Dot Design Award) 的得獎作品之一. 其基本概念是認為產品設計應該考量到預設用途之後的其他用途 ( future design should think beyond the product ), 因此在塑膠水瓶的例子中, 對於水瓶的外部設計, 除了考量到容易拿取不滑落的需求外, 其實水瓶的形狀跟是否能夠裝水的主要功能 (functionality) 是關係不大的.

但是用過的水瓶事實上可以變成是一種一般的容器, 就向有的家庭會把好看的玻璃瓶拿來裝別的東西, 當作花瓶, 或是作為裝飾. 在這裡是考量到可以把用過的水瓶拿來裝沙土, 就有了類似沙磚的效果, 可以用來快速建造臨時性的房屋, 避難所, 甚至可以建造永久性建築, 過可能需要搭配其他的黏性固定材料.


在這樣的應用中, 關鍵在於怎樣的外型設計可以方便裝沙土的水瓶作為磚塊使用, 可以快速地堆疊, 以及搬運. 創作者是以固定數量的水瓶可以組成一個單位的角度來進行設計.

嚴格來說, 雖然水瓶的形狀跟功能性關係不大, 但是卻會跟 marketing 有關係, 因此這樣的想法是否會獲得廠商支持倒是很難說.

在進行 software design 時, 我們也往往需要考量 design for reuse, 然而, 在 software component 身上, 是否也找的到類似水瓶的形狀的特徵 (attributes), 是跟主要的功能關係不大, 但是可以直接被用來橫量此 component 的 reusability 的呢 ? 是否我們可以就此列出一張清單 (checklist), 當我們面對什麼樣的 software components 時, 只要檢查此清單上的項目, 就可以撰寫出一份此 component 的 design for reuse 文件呢 ?

之前在對於某個 software measurement 想法進行 prototyping 時, 因為短時間內需要建立數個不同 programming languages 的 parsers, 同時還要能容易取得 parsing results, 因此很傷腦筋. 雖然已經有類似 ANTLR 的 parser generator, 但是寫 grammar file 還是很麻煩的一件事, 而別人已經寫好的 grammar file 能支援的 programming languages 也有限, 有些是尚沒有最新版本的 grammar files, 有些則是要自己寫. 而就算寫出來, 通常 parser generator 也不會特別幫你設計 parsing information 存取的 interface, 還是需要手動去 parser 裡面作一些修改, 一整個麻煩.

因為想偷懶, 結果就把腦筋動到支援較多 programming language 的 source code document generator 上, 例如 Doxygen.

Source code document generator 本身就一定會有 parsing 的功能, 但是要把這塊 component 挖出來也不容易, 畢竟人家本來就不是 design for reuse. 所以就採取折衷的辦法, 利用 document generator 能夠產生 HTML 或是 XML 等 formatted document 的特性, 再寫一個 XML parser 去讀取需要的 parsing information 就好. 寫 XML parsing 就簡單多了, 基本上就是在樹上繞來繞去而已. 整個流程像這樣 :


這樣在 Fact Collection 的 phase 幾乎不用作什麼事情了, 而同時 Doxygen 對於不同 programming language 的 parsing results, 用 XML 存的話, naming 都還蠻一致的, 所以所建立的 Doxygen XML Extractor 幾乎不用作太多的修改就可以不斷地 adapt 到不同的 programming languages 身上.

剩下的是在 Metrics Measurement phase, 把從 Doxygen 得到的 parsing information 塞到自訂的 program model 上, 然後利用特定的 software metrics 進行 measurement 就得到 program quality report 了.

在 development effort 上大大地省下許多功夫, 也能滿足 prototyping 的目的. 不過相對來說, 付出的 performance 代價是十分地恐怖, 恐怖到我一點也不想去比較真正的 parser 跟這個作法的 performance, 至少差了幾千倍吧. Performance 的 bottleneck 在於兩個地方, 一個是 Doxygen 要建立 document, 因此需要不斷地 cross-reference code entities, 另外一個則是 Doxygen 與 Doxygen XML Extractor 對於 document file 的 I/O. 對於程式碼很大且複雜的 software 來說, 例如 GCC, 可能要跑個幾天才會出來結果 (我用還蠻不錯的 PC machine 是跑了兩天多才出來).

所以基本上呢, 這種做法就只適合 prototyping 用吧, 另外就是需要不計較執行時花的時間, 唯一省下的好處是要寫 parser 或是 grammar file 的時間 :p

在 wikipedia 上有其他 source code document generator 的比較列表, 其他 document generator 應該也是可以取代 Doxygen 位置, 只要輸出的格式是 formatted document 就沒問題.

Recently, I am working on a small Lab. project about a novel approach for component storage and retrieval to assist component reuse in CBSD. In the domain analysis phase, some component modeling approaches were surveyed and compared. They were organized (ordered by publication year) in following table for anyone interested.

It amazed me that the graph-based approach had been applied since 1992, although the approach in [Ostertag1992] was far from similar with recent researches.Most of them are functionality-based classification, only very few associated with non-funcitionall qualities. The knowledge-based approach seems to be an interesting direction based on these previous influential functionality-based approaches.

References

1. [Seacord1998] R. C. Seacord, S. A. Hissam, and K. C. Wallnau, "Agora : A Search Engine for Software Components," IEEE Internet Computing, vol.6, no.2, pp.62-70, 1998
2. [Chatzigeorgiou2003] A. Chatzigeorgiou, "Mathematical Assessment of Object-Oriented Design Quality," IEEE Transactions on Software Engineering, vol.29, No.11, pp.1050-1053, Nov. 2003
3. [Plasil2002] F. Plasil and S. Visnovsky, "Behavior Protocols for Software Components," IEEE Transactions on Software Engineering, vol.28, No.11, pp.1056-1076, Nov. 2002
4. [Inverardi2000] P. Inverardi, A. L. Wolf, and D. Yankelevich, "Static Checking of System Behaviors Using Derived Component Assumptions," ACM Transactions on Software Engineering and Methodology, vol.9, no.3, pp.239-272, July 2000
5. [Zaremski1997] A. M. Zaremski and J. M. Wing, "Specification Matching of Software Components," ACM Transactions on Software Engineering and Methodology, vol.6, no.4, pp.333-369, Oct. 1997
6. [Zaremski1995] A. M. Zaremski and J. M. Wing, "Signature Matching: A Tool for Using Software Libraries," ACM Transactions on Software Engineering and Methodology, vol.4, no.2, pp.146-170, April 1995
7. [Mili1997] R. Mili, A. Mili, and R. T. Mittermeir, "Storing and Retrieving Software Components: A Refinement Based System," IEEE Transactions on Software Engineering, vol.23, No.7, pp.445-460, July 1997
8. [Inoue2005] K. Inoue, R. Yokomori, T. Yamamoto, M. Matsushita, and S. Kusumoto, "Ranking Significance of Software Components based on Use Relations," IEEE Transactions on Software Engineering, vol.31, No.3, pp.213-225, March 2005
9. [Damiani1999] E. Damiani, M. G. Fugini, and C. Bellettini, "Corrigenda: A Hierarchy-Aware Approach to Faceted Classification of Object-Oriented Components," ACM Transactions on Software Engineering and Methodology, vol.8, no.4, pp.425-472, Oct. 1999
10. [Ostertag1992] E. Ostertag, J. Hendler, R. P. Díaz, and C. Braun, "Computing Similarity in a Reuse Library System: An AI-Based Approach," ACM Transactions on Software Engineering and Methodology, vol.1, no.3, pp.205-228, July 1992
11. [Henninger1997] S. Henninger, "An Evolutionary Approach to Constructing Effective Software Reuse Repository," ACM Transactions on Software Engineering and Methodology, vol.6, no.2, pp.111-140, April 1997
12. [Frakes1994] W. B. Frakes and T. P. Pole, "An Empirical Study of Representation Models for Reusable Software Components," IEEE Transactions on Software Engineering, vol.20, no.8, pp.617-630, August 1994
13. [Vitharana2003] P. Vitharana, F. M. Zahedi, and H. Jain, "Knowledge-Based Repository Scheme for Storing and Retrieving Business Components: A Theoretical Design and Empirical Analysis," IEEE Transactions on Software Engineering, vol.29, no.7, pp.649-664, July 2003
    
    
    

SPARS-J 是日本井上研究室(Software Engineering Labratory, Osaka University) 的 SPARS project 所建立的 web-based software component search engine. 目前在 source code 部分還僅支援 java source, 另外支援部份的 document search (根據 paper [1]). 從 search engine 實際上的使用可以發現還提供 XML 以及 JSP search.


SPARS-J 的基本原理是利用 authors 所提的 component rank model 對於 component 做 weighting. 搭配上基於 text-based token analysis 對於 component 所建立的 keyword index 作為搜尋的支持. 整個運作分為兩個 phase.

Phase 1 為 source input phase, source provider 所提供的 source 會自動被分析, 做 compoennt ranking, 然後存起來. Phase 2 為 search phase. 使用者基於 keyword 進行 search, 結果會分為數個 component groups 以 component rank 做排序. 細節請參考 [1].

一個 component group 由數個 similar components 所組成, 大部份情況下一個 component group 內的 components 會是同一個 software source package 的不同版本, 例如搜尋 "qsort" "string" 就會看到有 Eclipse 內部不同版本的 Util.java 被歸納在同一個 group. 下圖可以看到搜尋結果共有 13 個 groups (綠色), 第一個 group 的 rank ordering 是 1 (藍色), 同一個 file 事實上是不同版本 (紅色).

至於怎樣決定 component similarity 則依據 SPARS-J 內定的 similarity comparison algorithm, 這是可以被調整的. 目前來說應該是使用 [2] 內所提到的 classification 方法.

[1] 文內也針對效能與 Google, Nazama 做比較, 不過可惜的是沒有跟 Google Code 做比較.


References

1. K. Inoue, R. Yokomori, T. Yamamoto, M. Matsushita, and S. Kusumoto, "Ranking Significance of Software Components based on Use Relations," IEEE Transactions on Software Engineering, vol.31, No.3, pp.213-225, March 2005 ( available pdf)
   


2. K. Kobori, T. Yamamoto, M. Matsusita, and K. Inoue, "Classification of Java Programs in SPARS-J," Proceedings of International Workshop on Community-Driven Evolution of Knowledge Artifacts, 2003