應用於複雜運動環境中以階梯函數為基礎之運動計算演算法

Abstract

根據以階梯函數為基礎的搜尋程序，我們提出一個以Wiener Filter為基 礎的演算法用以求取複雜運動環境中之物體運動參數。雖然用此方法可以 獲得良好的收斂速度與準確的計算結果，但是其需要龐大的運算量以至於 造成無法應用於及時運算。為此，我們另外提出一個區塊遞迴演算法( block recursive algorithm)配合有限字元長度的觀念用以降低運算的複 雜度。在此方法中，我們將階梯函數做量化處理。根據此簡化後的方法我 們可以用最少的損失來達成減少運算量的目的進而完成及時運算的目標。 在應用於實際影像的運動補償法中，所需傳送的字元長度是最重要的考量 因素。為了應用於更複雜的運動環境中，我們結合了區塊比對演算法( block matching algorithm)與區塊遞迴演算法二演算法之特色而提出一 個聯合運動參數計算演算法(combinative motion estimation algorithm) 。在此聯合運動參數計算演算法中，區塊比對演算法中之全 域搜尋程序(full searching procedure)與區塊遞迴演算法中之遞迴搜尋 程序(recursive searching procedure)被結合運用來計算複雜運動環境 中物體放大、縮小、旋轉、平移與不規則變形等各項運動參數而得到良好 的運算結果。為了更降低運算的複雜度，我們亦提出了相關於聯合運動參 數計算演算法之結構設計。根據此結構設計我們可以大量簡少運算量使得 此演算法更易於應用於達成及時運算的目標。 With the gradient based searching procedure, a wiener based estimation algorithm is proposed to estimate the motion parameters in complex motion model. In spite of with good performance on convergence speed and convergence accuracy, the wiener based algorithm needs large computational amount and this makes it hard to be real time implemented. For this, a block recursive algorithm with finite word length is proposed to reduce the computational complexity of the Wiener based algorithm. By using the quantized state on gradient estimation the simplified algorithm could get sufficient computational speed to meet the requirement of real time application with the least performance loss. For the motion compensation of real image sequence, the bit rate is the most important factor. Combining the features of block matching algorithm and block recursive algorithm a new motion estimation method is proposed for complex motion phenomenon. With the full searching procedure used in block matching algorithm and the recursive searching procedure used in block recursive algorithm, the proposed combinative algorithm can be used to estimate more complex motion parameters such as translation, zoom, rotatTo reduce the computational complexity, the corresponding architecture of the combinative algorithm is also proposed. With this architecture the computation amount can be largely reduced to make the proposed algorithm can be used for real time motion estimation.