KR100859073B1

KR100859073B1 - Motion estimation method

Info

Publication number: KR100859073B1
Application number: KR1020070015296A
Authority: KR
Inventors: 김지훈
Original assignee: 주식회사 대우일렉트로닉스
Priority date: 2007-02-14
Filing date: 2007-02-14
Publication date: 2008-09-17
Also published as: KR20080075987A

Abstract

본 발명은 움직임 추정 방법에 관한 것으로, 다른 크기를 가지는 영상으로 이루어진 여러 레벨의 평균 피라미드를 생성하는 단계와, 찾고자 하는 대상 블록의 주파수 신호 특성에 따라 평균 피라미드 중에서 어느 하나의 레벨을 탐색 레벨로 설정하는 단계와, 탐색 레벨에서 최소의 블록 정합 차이값을 가지는 후보 지점을 설정하는 단계와, 설정한 후보 지점에 대하여 평균 피라미드 중에서 최하위 레벨에서 움직임 벡터를 찾는 단계를 포함하며, 계층적 블록 정합 알고리즘에 블록의 주파수 특성에 따른 적응적인 개념을 도입해 불필요한 계층적 탐색을 제거하여 불필요한 계산을 최소화하면서도 움직임 벡터의 추출 정확도를 높이는 이점이 있다.The present invention relates to a motion estimation method, comprising: generating an average pyramid of various levels of images having different sizes, and setting any one level among the average pyramids as a search level according to a frequency signal characteristic of a target block to be searched for And setting a candidate point having the minimum block matching difference value at the search level, and finding a motion vector at the lowest level among the average pyramids for the set candidate point, wherein the hierarchical block matching algorithm includes: By adopting the adaptive concept according to the frequency characteristics of the block, the unnecessary hierarchical search is eliminated, thereby minimizing unnecessary computation and improving the accuracy of extracting the motion vector.

움직임 추정, 움직임 보상, 이미지 부호화, 움직임 벡터 Motion estimation, motion compensation, image coding, motion vector

Description

Motion estimation method {MOTION ESTIMATION METHOD}

도 1은 본 발명에 따른 움직임 추정 방법이 적용된 비디오 부호화기의 일 예를 보인 구성도,1 is a configuration diagram showing an example of a video encoder to which the motion estimation method according to the present invention is applied;

도 2는 움직임 추정 방법 중에서 TSS 방법에 의한 움직임 추정 과정을 보여주는 도면,2 is a view illustrating a motion estimation process by the TSS method among the motion estimation methods;

도 3은 움직임 추정 방법 중에서 BS 방법에 의한 움직임 추정 과정을 보여주는 도면,3 is a view illustrating a motion estimation process by the BS method among the motion estimation methods;

도 4는 움직임 추정 방법 중에서 계층적 블록 정합 방법에 의한 움직임 추정 과정을 보여주는 도면,4 is a diagram illustrating a motion estimation process by a hierarchical block matching method among motion estimation methods;

도 5는 본 발명에 따른 움직임 추정 방법에 의한 움직임 추정 과정을 보여주는 도면,5 is a view showing a motion estimation process by a motion estimation method according to the present invention;

도 6은 본 발명에 따른 움직임 추정 방법을 단계별로 설명하기 위한 흐름도.6 is a flowchart illustrating a step-by-step motion estimation method according to the present invention.

본 발명은 움직임 추정에 관한 것으로, 더욱 상세하게는 계층적 블록 정합 알고리즘에 블록의 주파수 특성에 따른 적응적인 개념을 도입한 움직임 추정 방법 에 관한 것이다.The present invention relates to motion estimation, and more particularly, to a motion estimation method in which an adaptive concept according to frequency characteristics of a block is introduced into a hierarchical block matching algorithm.

일반적으로 동영상 정보를 처리하는 시스템은 비디오 부호화기를 사용하며, 비디오 부호화기는 비디오 신호의 움직임을 추정하여 비디오 신호를 처리한다. 비디오 신호의 움직임 추정은 인접한 프레임간의 시간적 중복성을 제거하여 높은 압출율을 얻을 수 있는 방법이다.In general, a system for processing video information uses a video encoder, and the video encoder processes the video signal by estimating the motion of the video signal. Motion estimation of the video signal is a method of obtaining a high extrusion rate by eliminating temporal redundancy between adjacent frames.

움직임 보상기법은 움직임 추정기법을 통하여 입력 비디오 신호의 가장 유사한 영상신호를 시간적으로 이전 프레임으로부터 예측하고, 예측된 비디오 신호와 입력 비디오 신호와의 차를 변환 부호화하는 방법이다.The motion compensation technique is a method of predicting the most similar video signal of an input video signal from a previous frame in time using a motion estimation technique, and transform-coding the difference between the predicted video signal and the input video signal.

현재 MPEG-2, MPEG-4, H.263과 H.264를 포함하는 대부분의 비디오 코딩 표준은 움직임 보상 예측 코딩법에 기초하고 있는데, 시간적 중복은 움직임 보상에 의해 제거하고 공간적 중복은 변환 코딩에 의해 제거한다.Currently, most video coding standards, including MPEG-2, MPEG-4, H.263 and H.264, are based on motion compensated predictive coding, where temporal redundancy is eliminated by motion compensation and spatial redundancy is applied to transform coding. By removing.

시간적 중복을 제거하는 과정을 좀더 자세히 살펴보면, 프레임을 구성하는 구성단위, 예를 들면 각 매크로 블록(Macro Block)이 다음 시간의 프레임에서 해당 매크로 블록의 위치가 얼마만큼 이동했는지를 나타내는 움직임 추정치(Motion Vector)를 구하는 움직임 추정(Motion Estimation)을 한다. 움직임 추정이 끝나면 움직임 보상(Motion Compensation)을 하여 시간적 필터링(Filtering)을 통해 프레임간 시간적 중복성을 제거한다.Looking more closely at the process of eliminating temporal redundancy, the motion estimates indicate how much of the macroblocks that make up the frame, e.g., each macroblock, moved in the next frame of time. Motion Estimation is obtained. After motion estimation is completed, motion compensation is performed to remove temporal redundancy between frames through temporal filtering.

이러한 시간적 중복을 제거하는 과정은 매우 많은 연산을 필요로 하는데, 연산량을 줄이기 위한 여러 알고리즘들이 제안되고 있다. 크게 움직임 벡터 후보점의 갯수를 줄이는 방법을 통해서 계산을 줄이는 방법이 있고, 블록 정합 코스트 계산 을 통해서 줄이는 방법이 있으며, 움직임 벡터의 서브 샘플링 방법이 있다.The process of eliminating this temporal duplication requires a lot of operations, and various algorithms have been proposed to reduce the amount of computation. There is a method of reducing the calculation by greatly reducing the number of motion vector candidate points, a method of reducing the block matching cost by calculation, and a subsampling method of the motion vector.

움직임 추정을 위한 기법의 여러 가지 알고리즘들 중에서 블록 정합 알고리즘(Block Matching Algorithm: BMA)이 계산에 있어서 비교적 간단하기 때문에 가장 많이 사용된다. 블록 정합 알고리즘은 이전 프레임의 탐색 영역내에서 현재 블록의 가장 유사한 블록을 찾는 방법이다. 기본적인 방법인 전역 탐색 블록 정합 알고리즘(Full Search Block Matching Algorithm: FSBMA)은 성능면에서 최적이지만 계산량이 많고 하드웨어 부담이 커진다는 단점이 있으므로 계층적 블록 정합 알고리즘(Hierarchical Search Block Matching Algorithm: HSBMA)과 같은 고속 알고리즘을 사용하게 된다.Among the various algorithms of the technique for motion estimation, Block Matching Algorithm (BMA) is most frequently used because it is relatively simple in calculation. The block matching algorithm is a method of finding the most similar block of the current block in the search region of the previous frame. The basic method, the Full Search Block Matching Algorithm (FSBMA), is optimal in terms of performance but has a high computational cost and a high hardware burden. You will use a fast algorithm.

계층적 블록 정합 알고리즘 기법은 입력영상과 이전영상을 몇 단계의 해상도 영상으로 나누어 움직임 추정을 하는 방법으로서 기본 아이디어는 우선 저해상도의 영상으로부터 큰 스케일의 움직임 벡터 후보를 얻은 후 고해상도 영상에서 최적의 움직임 벡터를 찾는 기법이다.The hierarchical block matching algorithm is a method of motion estimation by dividing an input image and a previous image into several resolution images. The basic idea is to first obtain a large-scale motion vector candidate from a low resolution image and then obtain an optimal motion vector from a high resolution image. Finding technique.

그런데, 기존의 계층적 블록 정합 알고리즘 기법 또한 비교적 계산량이 많아서 움직임 추정을 위한 동작시간이 많이 걸리고 전력소모가 많은 문제가 있었다. 움직임 추정은 동영상 압축의 성능에 매우 중요한 역할을 하지만 계산량이 많기 때문에 실시간 동영상 인코딩을 위해서는 움직임 추정의 연산량을 줄일 수 있는 알고리즘이 필요하다.However, the conventional hierarchical block matching algorithm also has a relatively large amount of computation, which requires a lot of operation time and power consumption for motion estimation. Motion estimation plays an important role in the performance of video compression, but because of the large amount of computation, an algorithm is needed to reduce the computation of motion estimation for real-time video encoding.

본 발명은 이와 같은 종래의 문제점을 해결하기 위하여 제안한 것으로, 계층 적 블록 정합 알고리즘에 블록의 주파수 특성에 따른 적응적인 개념을 도입, 즉 복잡한 택스쳐를 포함하는 영상 블록, 균일한 영역으로 이루어진 영상 블록 등의 블록 특성을 반영하여 계층의 레벨을 조정함으로써, 불필요한 계층적 탐색을 제거하여 불필요한 계산을 최소화하면서도 움직임 벡터의 추출 정확도를 높이는 데 그 목적이 있다.The present invention has been proposed to solve such a conventional problem, and introduces an adaptive concept according to the frequency characteristics of a block in a hierarchical block matching algorithm, that is, an image block including a complex texture, an image block including a uniform region, and the like. The purpose of this method is to increase the accuracy of extracting motion vectors while minimizing unnecessary computation by eliminating unnecessary hierarchical search by adjusting the level of the hierarchy to reflect the block characteristics of.

이와 같은 목적을 실현하기 위한 본 발명에 따른 움직임 추정 방법은, 다른 크기를 가지는 영상으로 이루어진 여러 레벨의 평균 피라미드를 생성하는 단계와, 찾고자 하는 대상 블록의 주파수 신호 특성에 따라 평균 피라미드 중에서 어느 하나의 레벨을 탐색 레벨로 설정하는 단계와, 탐색 레벨에서 최소의 블록 정합 차이값을 가지는 후보 지점을 설정하는 단계와, 설정한 후보 지점에 대하여 평균 피라미드 중에서 최하위 레벨에서 움직임 벡터를 찾는 단계를 포함한다.The motion estimation method according to the present invention for realizing the above object comprises the steps of generating an average pyramid of various levels of images having different sizes, and the average pyramid according to the frequency signal characteristics of the target block to be searched. Setting a level as a search level, setting a candidate point having a minimum block matching difference value at the search level, and finding a motion vector at the lowest level among the average pyramids for the set candidate point.

이하, 본 발명의 바람직한 실시 예를 첨부된 도면들을 참조하여 상세히 설명한다. 아울러 본 발명을 설명함에 있어, 관련된 공지 구성 또는 기능에 대한 구체적인 설명이 본 발명의 요지를 흐릴 수 있다고 판단되는 경우에는 그 상세한 설명을 생략한다.Hereinafter, exemplary embodiments of the present invention will be described in detail with reference to the accompanying drawings. In addition, in describing the present invention, when it is determined that the detailed description of the related known configuration or function may obscure the gist of the present invention, the detailed description thereof will be omitted.

도 1은 본 발명에 따른 움직임 추정 방법을 적용한 비디오 인코더의 구성을 보여주는 블록도이다.1 is a block diagram showing the configuration of a video encoder to which the motion estimation method according to the present invention is applied.

비디오 인코더(100)는 비디오 프레임들간의 움직임을 추정하여 비디오 프레임들의 시간적 중복을 제거하고, 시간적 중복이 제거된 프레임들을 공간적 변환하 여 공간적 중복을 제거하며, 공간적 중복이 제거된 프레임들을 양자화하여 비트스트림을 생성한다. 이를 위하여 비디오 인코더(100)는 움직임 추정부(101), 움직임 보상부(103), 공간적 변환부(105), 양자화부(107), 움직임 정보 인코딩부(111) 및 비트스트림 생성부(109)를 포함한다.The video encoder 100 estimates the motion between video frames to remove temporal redundancy of the video frames, spatially transforms frames from which temporal redundancy is removed, removes spatial redundancy, and quantizes the frames from which spatial redundancy is removed. Create a stream. To this end, the video encoder 100 includes a motion estimator 101, a motion compensator 103, a spatial transformer 105, a quantizer 107, a motion information encoder 111, and a bitstream generator 109. It includes.

움직임 추정부(101)는 움직임 보상부(103)에서 현재 프레임(current frame)의 움직임을 보상하여 시간적 중복을 제거할 때 사용되는 움직임 벡터들을 찾는다. 움직임 벡터는 현재 프레임의 블록과 이에 매칭되는 참조 프레임의 블록간의 위치 차이로 정의할 수 있다. 참조 프레임으로 원래의 비디오 프레임이 이용될 수도 있으며, 코딩된 프레임을 디코딩하여 재구성한 프레임을 참조 프레임으로 이용할 수 있다.The motion estimator 101 finds motion vectors used when the motion compensator 103 compensates for the movement of the current frame to remove temporal overlap. The motion vector may be defined as a position difference between a block of a current frame and a block of a reference frame matched thereto. The original video frame may be used as the reference frame, and the frame reconstructed by decoding the coded frame may be used as the reference frame.

이와 같은 움직임 추정부(101)에 의해 움직임 벡터를 찾는 과정을 살펴보면, 평균 피라미드 구조의 레벨을 찾고자 하는 블록의 주파수 신호 특성에 따라 결정하는 단계, 탐색 지점을 선정하고 그 진행 과정을 설정하는 방법들을 필요에 따라 사용하여 이전 단계에서 결정된 레벨 상의 MAD(Maximum absolute difference)를 최소화시키는 지점을 찾는 단계, 이전 단계에서 찾은 지점에서 최하위 레벨에 대하여 전역 검색을 수행하여 움직임 벡터를 찾는 단계를 포함한다.Referring to the process of searching for a motion vector by the motion estimator 101, steps of determining according to the frequency signal characteristics of the block to find the level of the average pyramid structure, selecting a search point, and setting the process Finding a point to minimize the maximum absolute difference (MAD) on the level determined in the previous step by using as needed, and performing a global search for the lowest level at the point found in the previous step to find a motion vector.

움직임 보상부(103)는 움직임 추정부(101)에 의하여 구해진 움직임 벡터를 이용하여 현재 프레임의 시간적 중복을 제거한다. 이를 위하여 움직임 보상부(103)는 참조 프레임과 움직임 벡터를 이용하여 예측 프레임을 생성하고, 현재 프레임과 예측 프레임을 비교하여 잔여 프레임(residual frame)을 생성한다.The motion compensator 103 removes the temporal overlap of the current frame by using the motion vector obtained by the motion estimator 101. To this end, the motion compensator 103 generates a prediction frame by using the reference frame and the motion vector, and generates a residual frame by comparing the current frame and the prediction frame.

공간적 변환부(105)는 잔여 프레임을 변환시켜 변환 계수들을 얻는다. 공간적 변환 알고리즘은 정지 이산코사인변환(Discrete Cosine Transform) 또는 웨이브렛변환을 사용한다.The spatial transform unit 105 transforms the residual frame to obtain transform coefficients. Spatial transform algorithms use a discrete discrete cosine transform or wavelet transform.

양자화부(107)는 공간적 변환부(105)를 통해 얻은 변환 계수들을 양자화한다. 양자화의 세기는 비트레이트에 따라 결정된다.The quantization unit 107 quantizes the transform coefficients obtained through the spatial transform unit 105. The strength of quantization is determined by the bit rate.

움직임 정보 인코딩부(111)는 움직임 추정부(101)에 의해 구해진 움직임 벡터를 인코딩하여 정보량을 줄여 움직임 정보를 생성한다. 움직임 정보는 비트스트림에 포함된다.The motion information encoding unit 111 encodes the motion vector obtained by the motion estimation unit 101 to generate motion information by reducing the amount of information. The motion information is included in the bitstream.

비트스트림 생성부(109)는 양자화된 변환 계수들과 인코딩된 움직임 벡터를 포함한 비트스트림을 생성한다. 여기서, 양자화된 변환 계수들을 바로 비트스트림에 포함시키지 않고, 스캐닝과 스케일링 및 엔트로피 코딩 등을 거쳐 생성된 텍스쳐 정보를 비트스트림에 포함시킨다.The bitstream generator 109 generates a bitstream including the quantized transform coefficients and the encoded motion vector. Here, the quantized transform coefficients are not directly included in the bitstream, but texture information generated through scanning, scaling, and entropy coding is included in the bitstream.

이와 같이 구성된 비디오 인코더에 적용할 수 있는 본 발명에 따른 움직임 보상 방법에 대해 도 2 내지 도 6을 참조하여 보다 상세히 설명하기로 한다.A motion compensation method according to the present invention applicable to the video encoder configured as described above will be described in more detail with reference to FIGS. 2 to 6.

먼저, 본 발명에 따른 움직임 보상 방법을 설명하기에 앞서 본 발명의 이해를 돕기 위하여 움직임 추정을 위한 여러 가지 알고리즘들 중에서 본 발명의 기초가 되는 블록 정합 방법에 대해 살펴보기로 한다.First, before describing the motion compensation method according to the present invention, a block matching method, which is the basis of the present invention, will be described among various algorithms for motion estimation for better understanding of the present invention.

탐색 지점의 위치 선정 및 그 위치의 진행 과정을 설정하는 방법에 관련된 블록 정합 방법으로는 3단 탐색(Three Step Search, TSS), 2진 탐색(Binary Search, BS), 2차원 대수 탐색(Two Dimensional Logarithmic search, TDL), 4단 탐색(Four Step Search, FSS), 교차 탐색(Cross Search Algorithm, CSA) 등이 있고, 계산을 간단히 하기 위한 계층적 블록 정합 알고리즘(HSBMA)이 있다.The block matching method related to the positioning of the search point and the process of setting the location of the search point includes three-step search (TSS), binary search (BS), and two-dimensional algebraic search (Two Dimensional). Logarithmic search (TDL), Four Step Search (FSS), Cross Search Algorithm (CSA), etc. There is a hierarchical block matching algorithm (HSBMA) to simplify the calculation.

TSS, BS, TDL, FSS, CSA 등은 모두 중심 지점에서 일정 영역 안에서 최소의 블록 정합 차이값을 갖는 최적의 움직임 벡터를 찾는 것을 목표로 하며, 계산량을 줄이기 위하여 전체 영역을 모두 탐색하는 방법 대신에 여러 단계로 그 탐색 영역을 구분하여 최적 해에 근접한 해를 찾는다. 각 방법들은 각 단계에서 탐색 후보들을 기하학적으로 어떻게 설정하는지에 따라 구분된다.TSS, BS, TDL, FSS, CSA, etc. all aim to find the optimal motion vector with the smallest block matching difference in a certain area at the center point, instead of searching the whole area to reduce the computation The search area is divided into several steps to find a solution that is close to the optimal solution. Each method is distinguished by how the search candidates are geometrically set at each step.

이 중에서 TSS는 도 2에 나타낸 바와 같이, 초기 단계크기가 정해진 후 탐색 영역의 중심점에서 단계크기만큼 떨어진 8개의 블록들을 비교 후보로 정하는 단계, 탐색중심점은 이전 단계의 후보들 중 최소 블록 정합 차이를 가지는 지점으로 바꾸고 단계크기는 반으로 줄이는 단계, 단계크기가 1보다 작아질 때까지 이전 단계들을 반복하는 단계로 이루어진다.Among these, as shown in FIG. 2, the TSS determines a comparison candidate for eight blocks that are separated by the step size from the center point of the search area after the initial step size is determined, and the search center point has a minimum block matching difference among the candidates of the previous step. Switching to a point and reducing the step size in half, repeating the previous steps until the step size is less than one.

BS는 도 3에 나타낸 바와 같이, 9개의 후보지점을 각각 탐색 영역의 중심점과 4모서리와 4변의 중심점에 설정하고, 각 점들을 중심으로 하여 탐색 영역들을 도 3과 같이 설정하는 단계, 9개의 후보지점에서 최소의 블록 정합 차이를 가지는 지점에 해당하는 탐색 영역에서 전역 검색을 수행하는 단계로 이루어진다.As shown in FIG. 3, the BS sets nine candidate points to the center point of the search area, four corners, and four sides, respectively, and sets the search areas as shown in FIG. A global search is performed in the search area corresponding to the point having the smallest block matching difference at the point.

계층적 블록 정합 알고리즘(HSBMA)은 다른 크기를 가지는 영상으로 이루어진 여러 레벨의 평균 피라미드를 생성한다. 그 다음으로는 서브 샘플링되어 작은 이미지 크기를 가지는 높은 레벨에서부터 블록 정합을 수행하여 작은 크기의 블록 정합 차이를 갖는 후보들에 대해여 추가적으로 낮은 레벨에서 블록 정합을 수행하는 식 으로 움직임 벡터를 탐색한다. The hierarchical block matching algorithm (HSBMA) generates several levels of average pyramids of different sized images. Next, the motion vectors are searched by performing block matching from a high level having a small image size by subsampling and performing block matching at additionally low levels for candidates having a small block matching difference.

이러한 계층적 블록 정합 알고리즘에 대해 도 4를 참조하여 단계별로 살펴보면, 먼저 L 레벨의 평균 피라미드를 생성한다. 레벨 0이 원 영상이라 하고, 레벨 L-1이 최상위 레벨의 영상이라 하고, l을 레벨이라 하며, x, y를 영상의 위치라고 할 때, 상위 레벨의 영상은 하위 레벨의 영상과 다음의 수학식 1과 같은 관계를 가진다.Referring to the hierarchical block matching algorithm step by step with reference to Figure 4, first generates an average pyramid of the L level. When level 0 is called the original image, level L-1 is the highest level image, l is called the level, and x and y are the position of the image, the upper level image is the lower level image and the following math. Equation 1 has the same relationship.

다음으로, 최소의 블록 정합 차이값을 가지는 N개의 후보를 최상위 레벨에서 설정한다. 예로서, 도 4의 왼쪽 그림과 같이 레벨 2에서 최소의 블록 정합 차이값을 가지는 2개의 후보를 설정, 그 중심 지점을 설정한다.Next, N candidates having a minimum block matching difference value are set at the highest level. For example, as shown in the left figure of FIG. 4, two candidates having a minimum block matching difference value at level 2 are set, and a center point thereof is set.

그리고, 그 하위 레벨에서는 설정된 후보들의 주위에 대하여만 다시 최소의 블록 정합 차이값을 가지는 일정 수의 후보들을 선정한다. 이때 최소 블록 정합 차이값을 가지는 블록을 찾기 위하여 TSS를 사용한다. 이 과정을 최하위 레벨에 이를 때까지 반복한다. 예로서, 도 4의 가운데 그림과 같이 레벨 1에서 기 설정된 중심 지점으로 주위 일정 크기의 창 내에서 다시 최소 블록 정합 차이값을 가지는 지점을 탐색한다.At a lower level, a predetermined number of candidates having a minimum block matching difference value are selected again only around the set candidates. In this case, TSS is used to find a block having a minimum block matching difference value. Repeat this process until you reach the lowest level. For example, as shown in the center of FIG. 4, a point having a minimum block matching difference value is searched again in a window of a predetermined size to a predetermined center point at level 1.

그리고, 최하위 레벨의 후보에 대해서는 전역 검색을 수행하여 최종 해를 구한다. 예로서, 도 4의 오른쪽 그림과 같이 이전 단계에서 결정된 지점을 중심으로 전력 검색을 수행한다.The final solution is then searched for the lowest level candidates. For example, as shown in the right figure of FIG. 4, the power search is performed around the point determined in the previous step.

한편, 본 발명에 따른 움직임 보상 방법은 전술한 바와 같은 움직임 보상 기법 중에서 계층적 블록 정합 알고리즘에 블록의 주파수 특성에 따른 적응적인 개념을 도입하여 움직임 보상의 계산량을 줄이고 성능을 개선하는 것을 목표로 한다.Meanwhile, the motion compensation method according to the present invention aims to reduce the amount of motion compensation and improve performance by introducing an adaptive concept according to the frequency characteristics of a block in the hierarchical block matching algorithm among the motion compensation techniques described above. .

도 5 및 도 6을 참조하면, 계층적 블록 정합 알고리즘과 같이 다른 크기를 가지는 영상으로 이루어진 여러 레벨(L 레벨)의 평균 피라미드를 생성한다. 즉 부호화할 현재 블록과 이전 프레임이 원래 해상도를 가지는 하위 레벨(lower level), 하위 레벨의 원래 영상을 수평 및 수직으로 각각 2:1로 데시메이팅(decimation)하여 해상도를 낮춘 중간 레벨(Middle level) 및 중간 레벨의 영상을 다시 한번 수평 및 수직으로 각각 2:1로 데시메이팅하여 해상도를 낮춘 상위 레벨(Upper level)을 생성한다.5 and 6, an average pyramid of several levels (L levels) consisting of images having different sizes, such as a hierarchical block matching algorithm, is generated. That is, the lower level where the current block and the previous frame to be encoded have the original resolution, and the middle level where the resolution is lowered by decimating the original image of the lower level horizontally and vertically 2: 1 respectively. And decimating the intermediate level image 2: 2 horizontally and vertically, respectively, to generate an upper level having a lower resolution.

다음으로, 찾고자 하는 대상 블록이 위의 평균 피라미드 구조를 적용했을 때 상위 레벨로 올라감에 따라 평균되고 서브샘플링되는 과정에서 그 이미지 블록의 주파수 정보가 A%(예로서, 80%)이상 손실되지 않는 최상위 레벨을 탐색 레벨로 설정한다(S210).Next, the frequency information of the image block is not lost by more than A% (e.g., 80%) in the process of being averaged and subsampled as the target block to be found is raised to the upper level when the above average pyramid structure is applied. The highest level is set as the search level (S210).

이를 결정하기 위하여 도 5에 나타낸 바와 같이 대상 블록을 FFT(Fast Fourier Transform) 분석하여 에너지의 A% 손실을 가져오는 저주파 블록의 크기를 구한다. 위 블록 크기가 변의 길이 기준으로 원 대상 블록의 1/N일 때 레벨은

이 된다. 이때

는 버림을 의미한다.In order to determine this, as shown in FIG. 5, the target block is analyzed by fast Fourier transform (FFT) to obtain a size of a low frequency block resulting in A% loss of energy. When the above block size is 1 / N of the original target block based on the length of the side, the level is

Becomes At this time

Means abandonment.

그리고, 단계 S210에서 설정한 레벨에서 최소의 블록 정합 차이값을 가지는 1개의 후보를 설정한다. 이때 최소 블록 정합 차이값을 가지는 블록을 찾기 위하여 TSS, TDL, FSS, BS, CSA 등 여러 가지의 탐색 방법을 이용한다. 예로서, 도 5에 나타낸 바와 같이 대상 블록이 상위 레벨로 평균되고 서브샘플링되는 과정에서 A%이하의 주파수 정보 손실을 갖는 최상위 레벨 X에서 최소 블록 정합 차이값을 갖는 지점, 즉 MAD를 최소화시키는 지점을 찾는다(S220).Then, one candidate having a minimum block matching difference value is set at the level set in step S210. In this case, various search methods such as TSS, TDL, FSS, BS, and CSA are used to find a block having a minimum block matching difference value. For example, as shown in FIG. 5, a point having a minimum block matching difference value at the highest level X having a frequency information loss of less than or equal to A% in a process in which a target block is averaged to a high level and subsampled, that is, a point that minimizes MAD Find (S220).

이후, 단계 S220에서 설정된 후보에 대하여 최하위 레벨에서 전역 검색을 수행하여 최종 해를 구한다. 예로서, 도 5에 나타낸 바와 같이 해당 지점에서 레벨 0으로 내려와 전역 검색을 수행하여 움직임 벡터를 찾는다(S230).Thereafter, a global search is performed at the lowest level with respect to the candidate set in step S220 to obtain a final solution. For example, as shown in FIG. 5, the motion vector is found by descending to the level 0 at the corresponding point and performing a global search (S230).

지금까지는 본 발명의 일 실시 예에 국한하여 설명하였으나 본 발명의 기술이 당업자에 의하여 용이하게 변형 실시될 가능성이 자명하다. 이러한 변형된 실시 예들은 본 발명의 특허청구범위에 기재된 기술사상에 당연히 포함되는 것으로 해석되어야 할 것이다.It has been described so far limited to one embodiment of the present invention, it is obvious that the technology of the present invention can be easily modified by those skilled in the art. Such modified embodiments should be construed as naturally included in the technical spirit described in the claims of the present invention.

전술한 바와 같이 본 발명은 계층적 블록 정합 알고리즘에 블록의 주파수 특성에 따른 적응적인 개념을 도입, 즉 복잡한 택스쳐를 포함하는 영상 블록, 균일한 영역으로 이루어진 영상 블록 등의 블록 특성을 반영하여 계층의 레벨을 조정함으로써, 불필요한 계층적 탐색을 제거하여 불필요한 계산을 최소화하면서도 움직임 벡터의 추출 정확도를 높이는 효과가 있다.As described above, the present invention introduces an adaptive concept according to the frequency characteristics of a block in a hierarchical block matching algorithm, that is, reflects block characteristics such as an image block including a complex texture and an image block composed of uniform regions. By adjusting the level, the unnecessary hierarchical search is eliminated, thereby minimizing unnecessary calculations and improving the accuracy of extracting motion vectors.

Claims

(a) generating an average pyramid of several levels of images having different sizes,

(b) setting any one of the average pyramids as a search level according to a frequency signal characteristic of a target block to be searched for;

(c) setting a candidate point having a minimum block matching difference value at the search level;

(d) finding a motion vector at the lowest level among the average pyramids for the set candidate points

Motion estimation method comprising a.

The method of claim 1,

In the step (b), the search level is the highest level in which the frequency information of the image block is not lost more than a predetermined value in the process of being averaged and subsampled as the target block is raised to a higher level when the average pyramid is applied. Set to

Motion estimation method.

The method of claim 1,

Step (c) includes three-step search (TSS), binary search (BS), two-dimensional logarithmic search (TDL), four-step search (Four Step Search, FSS). ), Or one of the cross search algorithms (CSA)

Motion estimation method.

The method of claim 1,

In step (d), a global search is performed at the lowest level to find the motion vector.

Motion estimation method.