KR101113862B1

KR101113862B1 - Methode for Optimisation of Motion Search Algorithm

Info

Publication number: KR101113862B1
Application number: KR1020050017782A
Authority: KR
Inventors: 일리아
Original assignee: 엘지전자 주식회사
Priority date: 2005-03-03
Filing date: 2005-03-03
Publication date: 2012-02-29
Anticipated expiration: 2025-03-03
Also published as: KR20060098599A

Abstract

본 발명은 모션 추정 알고리즘의 최적화 방법에 관한 것으로, 이전 프레임(frame F)의 서치영역을 찾는 단계; 최소 차분 절대치의 합(Sum of Absolute Difference; SAD)의 결과치를 산출하는 단계; 최소 차분 절대치의 합(SAD)과 임계치 값을 비교하는 단계 및 최소 차분 절대치의 합이 임계치 값보다 작은 경우 모션벡터를 결정하는 단계를 포함하여 이루어짐으로써 적은 계산량을 가지면서도 Full Search에 가까운 정밀도의 모션벡터를 얻을 수 있다.The present invention relates to a method of optimizing a motion estimation algorithm, the method comprising: finding a search region of a previous frame (F); Calculating a result of Sum of Absolute Difference (SAD); Comprising a step of comparing the minimum difference absolute value (SAD) and the threshold value and determining the motion vector when the sum of the minimum difference absolute value is less than the threshold value, the motion of the precision with a small amount of calculation close to Full Search You can get a vector.

모션벡터, SAD, 서치영역 Motion vector, SAD, search area

Description

Optimization method of motion estimation algorithm {Methode for Optimization of Motion Search Algorithm}

도 1은 본 발명의 실시예에 따른 변환 프레임의 움직임 예측도.1 is a motion prediction diagram of a transform frame according to an embodiment of the present invention.

도 2는 본 발명의 실시예에 따른 현재 프레임에 대한 이전 프레임의 서치영역을 나타낸 블럭도.2 is a block diagram illustrating a search area of a previous frame with respect to a current frame according to an embodiment of the present invention.

도 3은 본 발명의 실시예에 따른 모션 추정 알고리즘의 최적화 방법을 나타낸 흐름도.3 is a flowchart illustrating a method of optimizing a motion estimation algorithm according to an embodiment of the present invention.

※ 도면 부호의 설명※ Explanation of reference numerals

■ : 최상위 레벨(N)의 LL부대역■: LL subband of highest level (N)

□ : 움직임 예측에 이용되는 부대역□: sub-band used for motion prediction

→ : 변환방향→: Conversion direction

본 발명은 영상 압축 방법에 관한 것으로, 특히 모션 추정 알고리즘의 최적화 방법에 관한 것이다. The present invention relates to an image compression method, and more particularly, to an optimization method of a motion estimation algorithm.

동영상 코딩(압축)에 있어서 모션벡터(Motion Vector)는 화면에 표시되는 하 나의 점이 가지고 있는 프레임 사이의 방향성을 나타내는 정보이다. 이러한 모션벡터의 검출은 프레임간의 시간적 중복을 줄이는데 필수적 과정으로써, 영상의 화질 및 압축속도에 결정적인 영향을 끼친다. 모션벡터는 현재 프레임의 소정의 좌표에 있는 매크로 블록을 기준으로 하여 이전 프레임상의 가장 근사한 블럭의 위치를 찾음으로써 결정된다. 시간적으로 인접한 두장의 프레임간에 어긋난 부분 서치영역(Search Range)이라고 하며 이러한 서치영역은 이전 프레임 상에 위치해 있다. 이 서치영역에서 현재 프레임의 매크로블럭과 가장 근사한 블럭의 위치를 찾게 된다. 서치영역에서 가장 근사한 블럭의 위치를 찾아 모션벡터를 결정하는 방법은 이전 프레임의 서치영역내의 화소와 현재 프레임의 매크로 블럭을 이루는 화소간의 차이를 구해 그 차이의 절대값을 모두 더한후(이를 SAD라고 함)이 SAD(Sum of Absolute Difference) 중 가장 작은 값에 대응하는 위치를 찾아 모션벡터를 결정하는 것이다. 즉 현재 프레임의 매크로 블럭의 기준점이 [X,Y]이고, 이전 프레임의 서치영역에서의 매크로 블럭과 가장 근사한 블럭의 기준 점이 [X+i.Y+j]일때 모션벡터는 (i,j)으로 결정된다. 종래기술에 있어서, 모션벡터를 산출하기 위해서는 서치영역의 각 화소에 대하여 감산, 절대치 산출 및 합산을 하여야 하기 때문에 (Full Search) 계산량이 많아 실제적으로 적용하는데 많은 문제점이 있다. In video coding (compression), a motion vector is information indicating a direction between frames of one point displayed on a screen. The detection of such motion vectors is an essential step in reducing temporal overlap between frames, which has a decisive effect on the image quality and the compression speed. The motion vector is determined by finding the position of the closest block on the previous frame based on the macro block at the predetermined coordinate of the current frame. It is called a partial search range that is shifted between two adjacent frames in time, and the search range is located on the previous frame. In this search area, the location of the block that is closest to the macroblock of the current frame is found. The method of determining the motion vector by finding the position of the closest block in the search area is to calculate the difference between the pixels in the search area of the previous frame and the pixels that make up the macro block of the current frame, and then add the absolute values of the differences (this is called SAD). The motion vector is determined by finding a position corresponding to the smallest value of SAD (Sum of Absolute Difference). That is, when the reference point of the macro block of the current frame is [X, Y] and the reference point of the closest block to the macro block in the search area of the previous frame is [X + i.Y + j], the motion vector is (i, j). Is determined. In the prior art, in order to calculate a motion vector, subtraction, absolute value calculation, and summation should be performed for each pixel of the search area.

따라서 본 발명은 상기와 같은 문제점을 감안하여 창안한 것으로, 적은 계산량을 가지면서도 Full Search에 가까운 정밀도의 모션벡터를 얻을 수 있는 모션 추정 알고리즘의 최적화 방법을 제공함에 그 목적이 있다. Accordingly, the present invention has been made in view of the above problems, and an object thereof is to provide an optimization method of a motion estimation algorithm capable of obtaining a motion vector with a precision close to Full Search while having a small amount of calculation.

상기와 같은 목적을 달성하기 위해 본 발명은 이전 프레임(frame F)의 서치영역을 찾는 단계; 최소 차분 절대치의 합(Sum of Absolute Difference; SAD)의 결과치를 산출하는 단계; 최소 차분 절대치의 합(SAD)과 임계치 값을 비교하는 단계 및 최소 차분 절대치의 합이 임계치 값보다 작은 경우 모션벡터를 결정하는 단계를 포함하여 이루어진다.In order to achieve the above object, the present invention is to find a search region of the previous frame (frame F); Calculating a result of Sum of Absolute Difference (SAD); Comparing the minimum difference absolute value (SAD) and the threshold value and determining the motion vector when the minimum difference absolute value is less than the threshold value.

도 1은 본 발명의 실시예에 따른 변환 프레임의 움직임 예측도이다.1 is a motion prediction diagram of a transform frame according to an embodiment of the present invention.

F(t)는 변환된 현재 프레임을 의미하고 F(t-1)은 이전 프레임을 나타낸다. 변환된 이미지는 주파수 영역이 다른 다해상도의 부대역으로 분활되는 특징이 있다. 즉, 레벨에 따라 부대역의 크기가 다르며, 픽셀당 계수의 크기도 다르다. 또한 상위레벨과 하위레벨의 부대역간의 유사성도 존재한다. 예를 들어 LH3은 LH2의 1/4 크기이며 형태는 LH2를 축소한 형태로 나타나며 계수당 크기는 K배 높은 것으로 나타난다. K는 소스이미지, 필터에 따라 다르게 나타난다. 도 1에서 보듯이 상위레벨의 부대역이 하위 부대역을 참조하여 움직임 예측을 수행한다. 따라서, 최하위 레벨의 부대역은 LH1, HL1, HH1은 움직임 보상이 수행되지 않는다. 이 부대역은 양자화와 엔트로피 코딩에만 이용된다. [식 1]은 최상위 레벨 N의 (X,Y)번째 블럭에 대한 모션벡터를 찾는 과정을 기술한 것이다. 최소 차분 절대치의 합(SAD)은 현재 블럭내의 각 픽셀과 이전 영역의 필셀간 차이값의 절대치의 합을 구하는 함수이다. 계산된 함수 값 중에서 가장 작은 함수의 위치(i,j)가 모션벡터가 된다. F (t) means the converted current frame and F (t-1) indicates the previous frame. The transformed image is characterized by being divided into multi-resolution subbands of different frequency domains. That is, the size of the subbands varies depending on the level, and the size of the coefficients per pixel also varies. There is also a similarity between the upper and lower levels of subbands. For example, LH3 is 1/4 the size of LH2, and the shape is reduced to LH2, and the size per coefficient is K times higher. K depends on the source image and the filter. As shown in FIG. 1, the upper level subband refers to the lower subband to perform motion prediction. Therefore, the LH1, HL1, and HH1 of the lowest level subbands are not subjected to motion compensation. This subband is used only for quantization and entropy coding. Equation 1 describes a process of finding a motion vector for the (X, Y) th block of the highest level N. The sum of the minimum difference absolute values (SAD) is a function for calculating the sum of the absolute values of the difference values between the pixels in the current block and the pixels of the previous region. The position (i, j) of the smallest function among the calculated function values becomes a motion vector.

모션벡터는 최소 차분 절대치의 합(SAD)의 결과치과 임계치(Threshold)보다 작은 경우에 성공적으로 구할 수 있다. The motion vector can be found successfully if the result of the minimum difference absolute value (SAD) is less than the threshold.

도 2는 본 발명의 실시예에 따른 현재 프레임에 대한 이전 프레임의 서치영역을 나타낸 블럭도이다. 모든 서치블럭에 대한 SAD 값의 산출은 많은 수학적 연산 작용을 필요로 하기때문에 최적화된 합의 최소 절대치 차분(Absolute Difference of Sums; ADS)값을 도입한다. 2 is a block diagram illustrating a search area of a previous frame with respect to a current frame according to an embodiment of the present invention. Since the calculation of SAD values for all search blocks requires a lot of mathematical operations, we introduce an optimized absolute difference of sums (ADS).

[식 2]에 의해서 모든 서치블럭의 ADS 값 중 임계치(TH)보다 큰경우는 자연 소거된다. 따라서,According to [Equation 2], if it is larger than the threshold value TH among the ADS values of all the search blocks, it is naturally erased. therefore,

SAD >= ADSSAD> = ADS

최소 차분 절대치의 합(SAD)은 최소값 ADS로 나타난 서치블럭에 의해 산출된다. 이전 프레임에서 서치영역의 합산출은 단 한번의 계산과정으로 아래와 같이 수행한다.The sum of the minimum difference absolute values (SAD) is calculated by the search block indicated by the minimum value ADS. In the previous frame, the sum of search areas is performed as follows in a single calculation process.

서치블럭의 합 =

Sum of search blocks =

도 3은 본 발명의 실시예에 따른 모션 추정 알고리즘의 최적화 방법을 나타낸 흐름도이다.3 is a flowchart illustrating a method of optimizing a motion estimation algorithm according to an embodiment of the present invention.

S300 단계에서 현재 프레임(frame F1)에 대응하는 이전프래임(frame F)의 서치영역을 찾는다. 이전 프레임(F)에서 서치영역은 [수학식 3]에 의한 연산으로 산출한다.(S301) F1의 현재블럭 내의 각 픽셀과 frame F 의 서치블럭내의 픽셀간 차이값의 절대치의 합을 구한다. 이때 최소 차분 절대치의 합(SAD)을 산출한다(S302). S307 단계에서 최소 차분 절대치의 합(SAD)과 임계치(Threshold)를 비교하여 작을 경우 S304 단계로 진행한다. 이때 최소 차분 절대치의 합(SAD)은 최소 절대치 차분(Absolute Difference of Sums; ADS)값과 같거나 크다(S304). 산출된 함수값 중 가장 작은 함수의 위치가 모션벡터가 된다(S305). 최소 차분 절대치의 합(SAD)이 임계치(TH)보다 클 경우 이전 프래임(F)의 서치블럭의 합을 산출하는 과정을 반복한다(S301).In operation S300, the search area of the previous frame F corresponding to the current frame F1 is found. In the previous frame F, the search area is calculated by the equation (3). (S301) The sum of the absolute values of the difference values between the pixels in the current block of F1 and the pixels in the search block of frame F is obtained. At this time, the sum SAD of the minimum difference absolute values is calculated (S302). In operation S307, when the sum of the minimum difference absolute value SAD and the threshold is smaller, the process proceeds to operation S304. In this case, the sum of the minimum difference absolute value (SAD) is equal to or greater than the minimum absolute difference of sum (ADS) value (S304). The position of the smallest function among the calculated function values becomes a motion vector (S305). When the sum SAD of the minimum difference absolute value is greater than the threshold TH, the process of calculating the sum of the search blocks of the previous frame F is repeated (S301).

상술한 바와 같이 본 발명은 적은 계산량을 가지면서도 Full Search에 가까운 정밀도의 모션벡터를 얻을 수 있는 모션 추정 알고리즘의 최적화 방법을 제공함으로써, As described above, the present invention provides a method of optimizing a motion estimation algorithm capable of obtaining a motion vector with a precision close to Full Search while having a small amount of calculation.

1. 서치블럭의 합을 한번에 산출하는 장점이 있다.1. It has the advantage of calculating the sum of search blocks at once.

2. 현재 플레임의 현재블럭 합 산출이 쉽게 최적화되는 장점이 있다.2. The advantage of calculating the current block sum of the current frame is that it is easily optimized.

3. 같은 합산출이 다른 원래 프래임의 서치영역으로 사용되어질 수 있는 장점이 있다. 3. The same summation has the advantage that it can be used as a search area for different original frames.

Claims

delete

Finding a search region of a previous frame F;

Calculating a result of Sum of Absolute Difference (SAD);

Comparing the sum of minimum difference absolute values (SAD) and the threshold value; And

Determining a motion vector when the sum of the minimum difference absolute values is less than a threshold value,

And the search region of the previous frame performs an iterative operation for finding the highest level.

3. The method of claim 2,

The iterative operation is performed at the coordinate points [X, Y] of the previous frame and the estimated position vector [C, D] of the highest level (N). A method of optimizing a motion estimation algorithm, characterized in that the expression.

delete