Motion estimation via a block-matching algorithm (BMA) has been used in almost all the video coding standards, including ITU-T H.263/H.264 and ISO/IEC MPEG-1/2/4, because it efficiently removes temporal redundancy between frames. The BMA divides frames into non-overlapped blocks and finds the displacement of the best-matched block from the reference frame within a search window, which is considered to be the motion vector (MV) of the block in the current frame. The measures that are widely used for determination of the best-matched block are the sum of the absolute differences (SAD) and the sum of the squared errors (SSE). The SAD is preferred due to the simplicity of its implementation.
Although the full-search (FS) algorithm is the optimal BMA with regard to motion estimation accuracy, its computational complexity limits practical usage. Hence, many BMAs have been developed to reduce the complexity. The methods used in BMAs can be divided into two categories: 1) reducing the number of search points and 2) reducing the load for the matching-criterion.
One approach in the second category uses lower bounds (also called boundary values) for the complete matching error, SAD. Before calculating the SAD of the current candidate, lower bound values (BVs) are obtained, and the necessity of calculating the SAD is determined by comparing lower bound values with the minimum SAD obtained from the previous candidates. The famous set of lower bound values of the SAD is derived from the well-known triangular inequality. With a set of lower bound values, the temporal minimum SAD is compared with BVs from the smallest BV to the largest BV to reject non-best candidates. In this thesis, a new scheme to obtain a BVs set is proposed. It is derived from a concept of block division gain (BDG), which is defined as the difference between the adjacent boundary values. The proposed scheme successively reduces the number of computations needed to compute the next BV from the previous BV. This scheme can be applied to any algorithms that use lower bounds derived from the triangular inequality.
Fast motion estimation algorithms utilizing lower bounds are called fast full-search algorithm (FFSA), since it guarantees the same output with that of FS with smaller computations. However, FFSAs requires results of the previous searched candidates, which make it difficult to implement FFSAs on the hardware with parallel processors. One method to resolve the difficulty is to compute a BV of the SAD for all candidates and choose a final winner among some candidates with the minimum lower bound value. For each candidate, a BV is computed without any previous results, which makes it easy to implement a method on the hardware for parallel processing, i.e. to divide all candidates into groups with the number of parallel processors. For further speed up gain, computational loads of calculating a BV are reduced. Since a BV is obtained from summations of absolute difference values, a scheme of partial summation is introduced, based on the expecting value of absolute difference values.
FFSA can be combined with any algorithms in the second category preserving performance in accuracy, since FFSA finds the optimal MV among a given set of candidates like FS. Algorithms in the second category are divided into two groups: 1) algorithms focusing more on speed and 2) algorithms focusing more on accuracy. Major difference of two groups is the number of search points. Candidate position subsampling technique (CPST) belongs to the second group. The CPST is used to search candidates that correspond to the subsampling pattern in a search window. Hence, the CPST usually follows coarse-to-fine search strategy. In order for CPST to have accuracy in finding a MV with the minimum SAD like FS, winner-selection condition (WSC) plays an important role, which decides positions where fine search is conducted. A novel WSC is proposed, which is very efficient when FFSA is used together. The proposed WSC reduces computational loads and improves algorithm accuracy of CPSTs with various sampling rates.
Recently, subpixel motion estimation (SPME) enhances the coding efficiency of hybrid video coders. A two-step search approach is usually preferred for estimating MVs with subpixel accuracy. In this approach, the best matching block at integer locations of the search area is found in a preliminary step of the search procedure. Then, in a second step, the sub-sample locations surrounding the selected integer candidate block is searched. This is exactly matched with CPST, hence the proposed WSC can be applied to SPME instead of a conventional WSC of choosing a candidate with the minimum cost. Results of SPME with the proposed WSC show that the proposed WSC gives improvement in PSNR performance of algorithm.
블록 정합 기법은 최신 동영상 압축 표준들에서 공통적 사용되는 방법으로 이웃한 화면간에 존재하는 정보의 시간적 중복성을 활용하여 동영상을 압축한다. 가장 정확성이 높은 블록 정합 기법은 전역 검색 기법이지만 (Full Search: FS) 이 기법은 매우 많은 연산량을 요구하기 때문에 여러 실시간 동영상 응용 분야들에서 사용되기에 부적합하다. 그래서, 연산량을 줄이기 위해서 많은 고속 블록 정합 기법들이 제안되어 왔고, 이들은 기준 영상에서 최적 정합 블록을 찾기 위해 사용되는 후보 블록들의 개수를 제한하거나, 정합 척도의 하계값들을 이용하여 정합 척도를 계산할 때의 연산량을 줄임으로써 해결책을 찾아내었다.
블록 정합 기법은 주어진 후보 위치들 중에서 정합 척도가 최소가 되는 위치를 찾는 것이 목적이다. 이를 위해, FS는 매 후보 위치마다 정합 척도를 계산하여 이전까지의 최소 정합 척도값보다 계산된 정합 척도가 더 작으면 최소 정합 척도값과 그 위치를 현재 후보 위치의 정합 척도값과 위치로 갱신한다. 그런데, 현재 후보의 정합 척도를 계산하기 전에 하계값들을 먼저 계산하면, 모든 하계값들이 이전까지의 최소 정합 척도값보다 큰 경우에만 현재 후보의 정합 척도를 계산하면 된다. 본 논문에서는 이전 하계값에서 다음 하계값을 계산할 때 효과적으로 다음 하계값을 계산할 수 있는 방법을 이전 하계값과 다음 하계값 간의 관계식을 통해 얻었다.
그런데, 정합 척도의 하계값들을 이용하는 방법은 한 후보 위치가 최적 위치인지 아닌 지를 판단할 때 이전까지 검색했던 후보 위치들의 결과인 이전까지의 최소 정합 척도값이 필요하다. 이로 인해, 하계값들을 이용하는 방법은 병렬처리로 구현하는 데에 어려움이 있다. 그래서, 이전 후보 위치들의 결과를 이용하지 않고, 병렬처리를 위해 하나의 하계값을 모든 후보 위치에서 효율적으로 계산하는 방법을 제안하였다.
FS의 연산량을 줄이기 위한 또 다른 접근 방식은 사용되는 후보 위치들의 개수를 줄이는 것이다. 이러한 방식들 중 블록 정합 기법의 정확도를 최대한 살려주기 위한 방법 중의 하나는 후보 위치들을 일정한 간격을 두고 선택하는 방식 (Candidate Position Subsampling Technique: CPST) 이다. CPST는 세 단계로 구성되며, 먼저는 후보 위치들을 일정한 간격을 두고 고르기, 둘째는 선택된 후보 위치들 중에서 정밀 검색을 위한 승자 고르기, 마지막으로 승자 주변에 있는 후보들을 검색하기이다.
승자 선택에 있어서 기존의 접근 방식은 이웃한 위치들간의 정합 척도값은 서로 비슷할 것이라는 가정 하에, 첫 번째 단계에서 선택된 후보 위치들 중에서 최소 정합 척도값을 갖는 후보 M개를 선택하는 방식이 대부분이다. 하지만, 이 같은 조건식들은 하계값들을 이용한 블록 정합 기법과 함께 사용할 경우, 연산량을 크게 줄일 수가 없었다. 그래서, 블록 정합 기법과 함께 사용할 경우에도 부가적인 연산량이 없으며, 최소 정합 척도값을 갖는 후보 M개를 선택하는 방식보다 정확도와 속도 측면에서 더 성능이 더 좋은 새로운 승자 선택 조건이 제안되었다. 뿐만 아니라, 2:1 CPST의 수행 속도와 정확도를 보다 높이기 위해 빠른 움직임 추정 단계와 PSNR 보상 단계를 추가했다.
2:1의 선택비뿐만 아니라 제안하는 승자 선택 조건을 다양한 선택비의 CPST에 적용하기 위하여, 정밀 검색 방법에 대한 지침을 알려주면서 승자 선택 조건 간의 성능을 비교할 수 있는 척도를 제안하였다. 이 척도를 통해 2:1과 144:1 사이의 여러 선택비 중 25:1이 가장 좋은 방법임을 알아내었다. 또한, 기존의 부화소 단위 움직임 추정 방법이 CPST 관점에서 해석될 수 있어서, 제안된 승자 선택 조건을 그대로 부화소 단위 움직임 추정에 적용할 수 있었다. 그 결과, 승자 선택 조건을 사용한 부화소 단위 움직임 추정 방법은 기존 방법보다 약간 증가된 연산량을 필요로 하였지만, 검색 영역 내 비슷한 블록이 많으며 고주파 성분이 많은 영상에 대해서는 어느 정도 화질을 향상 시켰다.
