KR100335434B1 - Motion estimation method - Google Patents
Motion estimation method Download PDFInfo
- Publication number
- KR100335434B1 KR100335434B1 KR1019980061601A KR19980061601A KR100335434B1 KR 100335434 B1 KR100335434 B1 KR 100335434B1 KR 1019980061601 A KR1019980061601 A KR 1019980061601A KR 19980061601 A KR19980061601 A KR 19980061601A KR 100335434 B1 KR100335434 B1 KR 100335434B1
- Authority
- KR
- South Korea
- Prior art keywords
- motion vector
- layer
- matching condition
- determining
- block
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Expired - Fee Related
Links
Classifications
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04N—PICTORIAL COMMUNICATION, e.g. TELEVISION
- H04N19/00—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals
- H04N19/50—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals using predictive coding
- H04N19/503—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals using predictive coding involving temporal prediction
- H04N19/51—Motion estimation or motion compensation
- H04N19/513—Processing of motion vectors
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04N—PICTORIAL COMMUNICATION, e.g. TELEVISION
- H04N19/00—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals
- H04N19/10—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals using adaptive coding
- H04N19/169—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals using adaptive coding characterised by the coding unit, i.e. the structural portion or semantic portion of the video signal being the object or the subject of the adaptive coding
- H04N19/182—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals using adaptive coding characterised by the coding unit, i.e. the structural portion or semantic portion of the video signal being the object or the subject of the adaptive coding the unit being a pixel
Landscapes
- Engineering & Computer Science (AREA)
- Multimedia (AREA)
- Signal Processing (AREA)
- Compression Or Coding Systems Of Tv Signals (AREA)
Abstract
본 발명은 움직임 추정 방법에 관한 것으로, 현재 영상 및 이전 영상이 2:1로 부표본화된 영상들을 제1계층, 현재 영상 및 이전 영상을 제2계층이라 할 때, 상기 제1계층 및 제2계층을 차례로 탐색하여 현재 영상의 각 화소 블록의 움직임을 이전 영상과 비교하여 추정하는 방법에 있어서, 제2계층에서 현재 처리할 화소 블록과 동일한 블록에 해당하는 제1계층의 위치에서 소정 영역에 대해 탐색하여 소정 정합조건을 만족하는 제1움직임 벡터를 결정하는 제1단계; 제2계층에서 현재 처리할 화소 블록의 이웃 블록들중 이미 처리된 이웃 블록들의 움직임 벡터들의 중간값을 취하고, 중간값을 1/2하여 제1계층에 해당하는 초기 탐색점으로 설정하는 제2단계; 초기 탐색점 주변의 소정 영역을 탐색하여 정합조건을 만족하는 제2움직임 벡터를 결정하는 제3단계; 제1 및 제2움직임 벡터중 정합조건이 보다 작은 움직임 벡터를 제2계층에서 현재 블록에 대한 초기 움직임 벡터로 결정하는 제4단계; 및 제2계층에서 초기 움직임 벡터 주변의 소정 영역을 탐색하여 최종 움직임 벡터를 결정하는 제5단계를 포함함을특징으로한다.The present invention relates to a motion estimation method, wherein when a current image and a previous image are subsampled 2: 1, the first layer and the current image and the previous image are referred to as a second layer. In a method of estimating the motion of each pixel block of the current image by comparing the previous image with the previous image, searching for a predetermined region at a position of the first layer corresponding to the same block as the pixel block to be currently processed in the second layer Determining a first motion vector satisfying a predetermined matching condition; A second step of taking a median of motion vectors of neighboring blocks already processed among the neighboring blocks of the pixel block to be currently processed in the second layer, and setting the initial search point corresponding to the first layer by halving the median value; ; Determining a second motion vector satisfying a matching condition by searching a predetermined area around the initial search point; A fourth step of determining a motion vector having a smaller matching condition among the first and second motion vectors as an initial motion vector for the current block in the second layer; And a fifth step of determining a final motion vector by searching for a predetermined area around the initial motion vector in the second layer.
본 발명에 의하면, 원 영상을 2:1로 부표본화하고, 부표본화된 영역을 3단계로 감소하면서 탐색하여 초기 움직임 벡터를 결정하며, 원 영상에서는 초기 움직임 벡터 주변의 소정 영역에 대해서만 탐색하므로, 보다 빠른 탐색이 가능하다.According to the present invention, the original image is subsampled to 2: 1, the subsampled region is searched while reducing the subsampled area in three steps, and the initial motion vector is determined. In the original image, only the predetermined region around the initial motion vector is searched. Faster navigation is possible.
Description
본 발명은 움직임 추정 방법에 관한 것이다.The present invention relates to a motion estimation method.
더욱 더 치열해지는 현 사회에서 좀 더 정확한 정보의 전달과 공유를 위하여 점점 중요시되는 수단이 영상통신이다. 특히 엠펙(MPEG)-1/2/4 및 H.263 등의 동영상 부호화기들은 다양한 응용분야에서 사용되고 있다. 대표적으로 동영상 부호화기가 적용되는 분야는 디지털 텔레비젼, 동영상 스토리지 디바이스, 동영상 원격회의, 영상 전화기, 디지털 카메라, 브이.오.디.(VoD, Video on Demand) 등이다.In today's increasingly fierce society, video communications is an increasingly important means for the delivery and sharing of more accurate information. In particular, video encoders such as MPEG-1 / 2/4 and H.263 are used in various applications. Typical applications of video encoders include digital television, video storage devices, video teleconferencing, video telephony, digital cameras, and video on demand (VoD).
동영상 부호화 방법은 각 부호화 방식별로 목적과 특성이 다르기때문에 응용분야는 매우 다양하다. 그러나 이들 동영상 부호화 기법들은 공히 블록 움직임 벡터를 영상 압축 및 부호화시에 사용한다. 이 때 블록 움직임 벡터를 찾아내는 방법을 움직임 추정(Motion Estimation) 기법이라 한다. 모든 동영상 부호화기에서 가장 많은 복잡도를 요구하는 것이 움직임 추정이고, 따라서 작은 복잡도로 신뢰도가 높은 움직임 벡터를 얻는 것이 중요하다.The video coding method has a variety of applications because the purpose and characteristics of each video coding method are different. However, these video encoding techniques all use block motion vectors in image compression and encoding. At this time, a method of finding a block motion vector is called a motion estimation technique. It is motion estimation that requires the most complexity in all video encoders, so it is important to obtain a reliable motion vector with small complexity.
움직임 추정을 위해 지금까지 제안된 여러가지 알고리즘중 전역 탐색기법(Full Search Block Matching Algorithm)은 실시간 구현시 매우 큰 계산량으로 인해 칩 크기가 현저히 커지는 단점이 있다. 이런 단점을 보완하기위하여 여러 가지 고속 탐색 알고리즘이 제안되어 왔다. 하지만 이런 고속 탐색 알고리즘들은 계산량에는 큰 이득을 주었으나 전역 탐색기법에 비해 성능이 많이 떨어진다.Among the various algorithms proposed so far for motion estimation, the full search block matching algorithm has a drawback in that the chip size is significantly increased due to a large amount of computation in real time implementation. In order to make up for this drawback, several fast search algorithms have been proposed. However, these fast search algorithms have a large gain in computational performance, but are much worse than the global search method.
고속 탐색 알고리즘들중 계층적 탐색 알고리즘은 계산량이 현저히 줄어듦에도 불구하고 성능은 전역 탐색에 비해 크게 떨어지지 않는다. 계층적 탐색 알고리즘의 경우, 각 단계마다 처리하는 블록의 크기와 탐색 영역의 크기가 서로 다르다.Among the fast search algorithms, hierarchical search algorithms do not degrade much compared to global search even though the computational amount is significantly reduced. In the case of the hierarchical search algorithm, the size of the block to be processed and the size of the search area are different for each step.
일반적으로, 움직임 추정 알고리즘의 크기는 처리하는 블록과 탐색영역의 크기에 따라 결정된다. 예를 들어, 도 1에 도시된 3단 계층적 탐색 알고리즘의 경우를 고려하기로 한다. 도 1에 따르면, 3단 계층적 알고리즘은 현재 영상과 재생된 이전 영상을 4:1로 부표본화(subsampling)한 상위계층(100), 2:1로 부표본화한 중간계층(102) 및 원 영상인 하위계층(104)을 포함한다. 화소 블록의 크기가 16x16인 경우, 상위 계층(100)에서는 부표본화되어 가로, 세로가 각각 1/4씩 줄어든 영상을 이용하여 4x4블록 단위로 ±p0영역에 대해 탐색을 수행한다. 이전 영상의 탐색 영역의 후보 블록들 중 현재 영상에서 현재 처리중인 블록과 비교하여 각 화소값들의 절대값 차의 합(SAD, Summ of Absolute Difference)이 최소인 블록과 그 다음으로 최소인 블록을 찾는다. 그리고, 하위 계층(104)에서 현재 처리중인 블록과 인접한 블록들의 움직임 벡터들의 중간값(median)을 취한 벡터를 얻는다.In general, the size of the motion estimation algorithm is determined according to the size of a block to be processed and the search area. For example, consider the case of the three-stage hierarchical search algorithm shown in FIG. According to FIG. 1, the three-stage hierarchical algorithm includes an upper layer 100 subsampling a current image and a previous image reproduced 4: 1, a middle layer 102 subsampling 2: 1, and an original image. Phosphorus sub-layer 104. When the size of the pixel block is 16x16, the upper layer 100 searches for the ± p 0 region in units of 4x4 blocks by using an image that is subsampled and is reduced by 1/4 each in width and length. Among the candidate blocks of the search region of the previous image, a block having the smallest sum of absolute values (SAD) of each pixel value (SAD) and the next lowest block are compared with a block currently being processed in the current image. . In the lower layer 104, a vector obtained by taking the median of the motion vectors of blocks adjacent to the block currently being processed is obtained.
중간계층(102)에서는 이렇게 얻어진 세 개의 벡터들을 초기점으로하여, 부표본화되어 가로, 세로가 각각 1/2씩 줄어든 영상을 이용하여 8x8블록 단위로 ±p1영역에 대해서 탐색을 다시 수행한다. 각 탐색영역에 대해서 SAD가 최소인 벡터를 얻고, 얻어진 세 개의 벡터중 다시 SAD가 최소인 움직임 벡터를 하위계층(104)의 초기 벡터로 설정한다. 이 초기 벡터를 이용해서 하위계층에서 16x16 크기의 블록단위로 ±p2영역에 대해 탐색을 수행하여 SAD가 최소인 최종 움직임 벡터를 구하게된다.In the middle layer 102, the three vectors thus obtained are used as initial points, and the search is performed again on the ± p 1 region in 8x8 block units by using an image that is subsampled and reduced in width and length by 1/2. A minimum SAD vector is obtained for each search region, and a motion vector having the smallest SAD is again set as an initial vector of the lower layer 104 among the three vectors obtained. The initial vector is used to search a ± p 2 region in a 16x16 block unit in the lower layer to obtain a final motion vector having a minimum SAD.
그러나, 이러한 방법은 각 계층별로 부표본화를 수행해야하고, 입력 영상 및 움직임 벡터들의 특성에 따른 성능에 차이가 있다. 또한 각 계층간의 탐색점들이 중복되는 경우가 있으며. 상위 및 중간계층에서 수행하는 연산량이 많다는 문제점이 있다.However, this method requires subsampling for each layer, and there is a difference in performance according to characteristics of the input image and the motion vectors. In addition, search points between layers may overlap. There is a problem that a large amount of calculation performed in the upper and middle layers.
본 발명이 이루고자하는 기술적 과제는 원 영상을 2:1로 부표본화한 영상인 제1계층과 원 영상인 제2계층의 일부 영역을 탐색하여 현재 처리중인 블록의 움직임 벡터를 구하는 움직임 추정 방법을 제공하는데 있다.SUMMARY OF THE INVENTION The present invention provides a motion estimation method for finding a motion vector of a block currently being processed by searching a partial region of a first layer, which is an subsampled 2: 1 original image, and a second layer, which is an original image. It is.
도 1은 종래의 3단 계층적 탐색 알고리즘을 설명하는 도면이다.1 is a diagram illustrating a conventional three-stage hierarchical search algorithm.
도 2는 본 발명에 따른 움직임 추정 방법에 대한 흐름도이다.2 is a flowchart illustrating a motion estimation method according to the present invention.
도 3은 본 발명에 사용되는 현재 영상 및 재생된 이전 영상의 계층별 구성도를 도시한 것이다.3 is a block diagram of each layer of the current image and the previous image played back according to the present invention.
도 4는 3단계 탐색 알고리즘을 설명하는 도면이다.4 is a diagram illustrating a three-stage search algorithm.
도 5는 원 영상에서 현재 처리할 블록과 이웃 블록들을 도시한 것이다.5 illustrates blocks and neighboring blocks to be processed currently in the original image.
상기 기술적 과제를 이루기위한 본 발명은 현재 영상 및 이전 영상이 2:1로 부표본화된 영상들을 제1계층, 현재 영상 및 이전 영상을 제2계층이라 할 때, 상기 제1계층 및 제2계층을 차례로 탐색하여 현재 영상의 각 화소 블록의 움직임을 이전 영상과 비교하여 추정하는 방법에 있어서, 상기 제2계층에서 현재 처리할 화소 블록과 동일한 블록에 해당하는 제1계층의 위치에서 소정 영역에 대해 탐색하여 소정 정합조건을 만족하는 제1움직임 벡터를 결정하는 제1단계; 상기 제2계층에서 현재 처리할 화소 블록의 이웃 블록들중 이미 처리된 이웃 블록들의 움직임 벡터들의 중간값을 취하고, 상기 중간값을 1/2하여 상기 제1계층에 해당하는 초기 탐색점으로 설정하는 제2단계; 상기 초기 탐색점 주변의 소정 영역을 탐색하여 상기 정합조건을 만족하는 제2움직임 벡터를 결정하는 제3단계; 상기 제1 및 제2움직임 벡터중 상기 정합조건이 보다 작은 움직임 벡터를 제2계층에서 상기 현재 블록에 대한 초기 움직임 벡터로 결정하는 제4단계; 및 상기 제2계층에서 상기 초기 움직임 벡터 주변의 소정 영역을 탐색하여 최종 움직임 벡터를 결정하는 제5단계를 포함함을 특징으로한다.According to an embodiment of the present invention, when the current image and the previous image are sub-sampled 2: 1, the first layer and the current image and the previous image are referred to as a second layer. A method of estimating a motion of each pixel block of a current image by comparing the previous image with a previous image, wherein the second layer searches for a predetermined region at a position of a first layer corresponding to the same block as the pixel block to be currently processed. Determining a first motion vector satisfying a predetermined matching condition; Taking an intermediate value of motion vectors of neighboring blocks already processed among the neighboring blocks of the pixel block to be processed in the second layer, and setting the initial search point corresponding to the first layer by halving the intermediate value; Second step; Determining a second motion vector that satisfies the matching condition by searching a predetermined area around the initial search point; Determining a motion vector of which the matching condition is smaller among the first and second motion vectors as an initial motion vector for the current block in a second layer; And a fifth step of determining a final motion vector by searching for a predetermined area around the initial motion vector in the second layer.
상기 기술적 과제를 이루기위한, 본 발명은 현재 영상 및 이전 영상이 2:1로 부표본화된 영상들을 제1계층, 현재 영상 및 이전 영상을 제2계층이라 할 때, 상기 제1계층 및 제2계층을 차례로 탐색하여 현재 영상의 각 화소 블록의 움직임을 이전 영상과 비교하여 추정하는 방법에 있어서, 상기 제2계층에서 현재 처리할 화소 블록과 동일한 블록에 해당하는 제1계층의 위치에서 소정 영역에 대해 탐색하여 소정 정합조건을 만족하는 제1움직임 벡터를 결정하는 제1단계; 상기 제2계층에서 현재 처리할 화소 블록의 이전에 처리된 블록들중에서, 현재 처리할 블록과 인접하여 수평축에 위치한 블록을 B1, B1의 수직측 상단에 위치한 블록을 B2, 현재 처리할 블록의 수직축에 위치한 블록을 B3, B3의 우측 수평축에 위치한 블록을 B4라 할 때, B3와 B4간 움직임 벡터의 거리가 B1과 B2간 움직임 벡터의 거리보다 작다면, B3의 움직임 벡터와 B4의 움직임 벡터를 평균하고, 다시 1/2하여 상기 제1계층에 해당하는 초기 탐색점으로 설정하는 제2단계; 상기 초기 탐색점 주변의 소정 영역을 탐색하여 상기 정합조건을 만족하는 제2움직임 벡터를 결정하는 제3단계; 상기 제1 및 제2움직임 벡터중 상기 정합조건이 보다 작은 움직임 벡터를 제2계층에서의 초기 움직임 벡터로 결정하는 제4단계; 및 상기 제2계층에서 상기 초기 움직임 벡터 주변의 소정 영역을 탐색하여 상기 정합조건을 만족하는 최종 움직임 벡터를 결정하는 제5단계를 포함함을 특징으로한다.In order to achieve the above technical problem, the present invention provides the first layer and the second layer when the current image and the previous image are subsampled 2: 1, and the first layer and the current image and the previous image are the second layer. A method for estimating the motion of each pixel block of a current image by comparing the previous image with a previous image, the method comprising: comparing a predetermined region at a position of a first layer corresponding to the same block as a pixel block to be currently processed in the second layer; Searching and determining a first motion vector satisfying a predetermined matching condition; Among blocks previously processed of the pixel block to be currently processed in the second layer, the block located on the horizontal axis adjacent to the block to be currently processed is B 1 , the block located at the top of the vertical side of B 1 is currently processed to B 2 . When the block located on the vertical axis of the block is B 3 and the block located on the right horizontal axis of B 3 is B 4 , if the distance of the motion vector between B 3 and B 4 is smaller than the distance of the motion vector between B 1 and B 2 , A second step of averaging the motion vector of B 3 and the motion vector of B 4 and halving again to set an initial search point corresponding to the first layer; Determining a second motion vector that satisfies the matching condition by searching a predetermined area around the initial search point; A fourth step of determining a motion vector having a smaller matching condition among the first and second motion vectors as an initial motion vector in a second layer; And a fifth step of determining a final motion vector satisfying the matching condition by searching for a predetermined area around the initial motion vector in the second layer.
상기 기술적 과제를 이루기위한, 본 발명은 현재 영상 및 이전 영상이 2:1로 부표본화된 영상들을 제1계층, 현재 영상 및 이전 영상을 제2계층이라 할 때, 상기 제1계층 및 제2계층을 차례로 탐색하여 현재 영상의 각 화소 블록의 움직임을 이전 영상과 비교하여 추정하는 방법에 있어서, 상기 제2계층에서 현재 처리할 화소 블록과 동일한 블록에 해당하는 제1계층의 위치에서 소정 영역에 대해 탐색하여 소정의 정합조건을 만족하는 제1움직임 벡터를 결정하는 제1단계; 상기 제2계층에서 현재 처리할 화소 블록의 이웃 블록들중 이미 처리된 이웃 블록들의 각 움직임 벡터들과 동일한 위치에 해당하는 상기 제1계층의 움직임 벡터들 주변의 소정 영역에 대해 탐색하고, 그 중 상기 정합조건이 최소인 움직임 벡터를 초기 탐색점으로 설정하는 제2단계; 상기 초기 탐색점 주변의 소정 영역을 탐색하여 상기 정합조건을 만족하는 제2움직임 벡터를 결정하는 제3단계; 상기 제1 및 제2움직임 벡터중 상기 정합조건이 보다 작은 움직임 벡터를 제2계층에서의 초기 움직임 벡터로 결정하는 제4단계; 및 상기 제2계층에서 상기 초기움직임 벡터 주변의 소정 영역을 탐색하여 상기 정합조건을 만족하는 최종 움직임 벡터를 결정하는 제5단계를 포함함을 특징으로한다.In order to achieve the above technical problem, the present invention provides the first layer and the second layer when the current image and the previous image are subsampled 2: 1, and the first layer and the current image and the previous image are the second layer. A method for estimating the motion of each pixel block of a current image by comparing the previous image with a previous image, the method comprising: comparing a predetermined region at a position of a first layer corresponding to the same block as a pixel block to be currently processed in the second layer; A first step of searching and determining a first motion vector satisfying a predetermined matching condition; Search for a predetermined area around the motion vectors of the first layer corresponding to the same position as each of the motion vectors of the neighboring blocks that have already been processed among the neighboring blocks of the pixel block to be currently processed in the second layer; Setting a motion vector having the minimum matching condition as an initial search point; Determining a second motion vector that satisfies the matching condition by searching a predetermined area around the initial search point; A fourth step of determining a motion vector having a smaller matching condition among the first and second motion vectors as an initial motion vector in a second layer; And a fifth step of determining a final motion vector satisfying the matching condition by searching for a predetermined area around the initial motion vector in the second layer.
이하에서 첨부된 도면을 참조하여 본 발명의 실시예를 보다 상세히 설명하기로 한다. 도 2는 본 발명에 따른 움직임 추정 방법에 대한 흐름도이다. 먼저, 현재 영상 및 재생된 이전 영상을 2:1로 부표본화한다(200단계). 도 3은 부표본화된 영상들과 원 영상들을 계층화하여 도시한 것이다. 참조번호 300은 부표본화된 제1계층을 나타내고, 310은 원 영상의 제2계층을 나타낸다. 움직임 벡터를 추정하기위해 먼저, 제1계층(300)을 탐색한다. 원 영상(310)에서 현재 처리할 화소블록이 307로 나타내진 블록이라하면, 제1계층(300)에서 제2계층(310)의 307과 동일한 위치(302)에서 3단계 탐색 알고리즘에 따라 제1움직임 벡터를 탐색한다(202단계). 정합 기준(Matching Criterion)은 SAD이다.Hereinafter, exemplary embodiments of the present invention will be described in detail with reference to the accompanying drawings. 2 is a flowchart illustrating a motion estimation method according to the present invention. First, the current image and the previous image reproduced are subsampled at 2: 1 (step 200). 3 illustrates the subsampled images and the original images layered. Reference numeral 300 denotes a subsampled first layer, and 310 denotes a second layer of the original image. In order to estimate the motion vector, first, the first layer 300 is searched. If the pixel block to be processed currently in the original image 310 is a block indicated by 307, the first layer 300 according to the three-stage search algorithm is located at the same position 302 as that of 307 of the second layer 310. The motion vector is searched for (step 202). Matching Criterion is SAD.
3단계 탐색 알고리즘은 코가 등(T. Koga, et.al, "Motion compensated interframecoding for video-conferencing", in Proc. of NTC' 81)이 제안한 방법으로, 도 4에 도시된 바와 같이 16×16 크기의 블록으로 ±7 화소 범위의 탐색 영역에 대해 탐색하되, 전 영역에 대해 탐색하지 않고 일부 영역에 대해서만 탐색하는 방법이다. 제1단계에서는 ±7 탐색 영역중에서 (0,0)의 위치를 중심으로 ±4 화소 영역의 경계선에 있는 화소들중 가로축, 세로축 및 대각선에 위치한 화소들(○)에 대해서만 탐색한다. 제2단계에서는 탐색된 화소들중 SAD가 최소인 화소(400)를 중심으로 ±2 화소 영역의 경계선에 있는 화소들중 가로축, 세로축 및 대각선에 위치한 화소들(빗금친 원)에 대해서만 탐색한다. 제3단계에서는 제2단계에서 탐색된 화소들중 SAD가 최소인 화소(402)를 중심으로 ±1 화소 범위의 탐색 영역의 모든 화소를 탐색하고, SAD가 최소인 화소(404)를 찾아서 이 위치를 초기 움직임 벡터로 결정한다.The three-stage search algorithm is proposed by T. Koga, et.al, "Motion compensated interframecoding for video-conferencing", in Proc. Of NTC'81, as shown in FIG. A method of searching for a search region in a range of ± 7 pixels with a block of size, but searching for only a partial region without searching the whole region. In the first step, only pixels (○) located on the horizontal axis, vertical axis, and diagonal line among the pixels on the boundary line of the ± 4 pixel area around the position of (0,0) in the ± 7 search area are searched. In the second step, only the pixels (hatched circles) located on the horizontal axis, vertical axis, and diagonal line among the pixels on the boundary line of the ± 2 pixel area around the pixel 400 having the smallest SAD among the searched pixels are searched. In the third step, all pixels in the search area in the range of ± 1 pixel are searched for the pixel 402 having the smallest SAD among the pixels searched in the second step, and the pixel 404 having the smallest SAD is found and located at this position. Is determined as the initial motion vector.
본 발명에서는 제1단계에서 제1계층(300)의 (x0/2, y0/2) 위치를 ±7 탐색 영역의 (0,0) 위치로 하여 ±7 화소 영역에 대해 탐색하며, 나머지 제2 및 제3단계를 차례로 수행한다. 이 때, 영상의 크기에 대해 2를 밑수로하는 로그를 취해서 탐색영역을 보다 좁게할 수 있다.In the present invention, in the first step, the (x 0/2 , y 0/2) position of the first layer 300 is defined as the ( 0 , 0 ) position of the ± 7 search area, and the search is performed for the ± 7 pixel area. The second and third steps are performed in sequence. At this time, the search area can be narrowed by taking a logarithm to the base of the image 2 as the base.
202단계에서 탐색된 제1움직임 벡터외에 제2움직임벡터를 결정한다(204단계). 제2움직임 벡터는 제2계층(310)에서 현재 처리할 화소 블록인 307의 이웃 블록들의 움직임 벡터들로부터 여러 방법으로 구할 수 있다.In addition to the first motion vector found in step 202, a second motion vector is determined (step 204). The second motion vector may be obtained in various ways from the motion vectors of neighboring blocks of 307 which are pixel blocks to be processed in the second layer 310.
첫번째 방법은 이웃 블록들(306, 308, 309)의 움직임 벡터들의 중간값(median, 304)을 취하는 것이다. 즉, 이웃 블록들은 시간적으로 이미 처리되어있으므로 이들 이웃 블록들의 최종 움직임 벡터는 알고있는 상태이다. 이들 최종 움직임 벡터들을 각각 (MVx,1, MVy,1), (MVx,3, MVy,3), (MVx,4, MVy,4)라 하면, 이들의 움직임 벡터들의 x, y성분인 MVx, MVy를 다음과 같이 각각 중간값을 취해 하나의 움직임 벡터 후보로 결정한다.The first method is to take the median 304 of the motion vectors of the neighboring blocks 306, 308, 309. That is, since the neighboring blocks are already processed in time, the final motion vector of these neighboring blocks is known. Let these final motion vectors be (MV x, 1 , MV y, 1 ), (MV x, 3 , MV y, 3 ), (MV x, 4 , MV y, 4 ), respectively, x of their motion vectors , y components MV x and MV y are determined as one motion vector candidate by taking intermediate values as follows.
이렇게 얻어진 움직임 벡터 후보를 1/2로 크기를 줄여서 제1계층(300)에서의 초기 탐색점(301)으로 사용한다.The motion vector candidate thus obtained is reduced to 1/2 to be used as the initial search point 301 in the first layer 300.
두번째 방법은 이웃 움직임 벡터들의 중간값을 취하는 대신, 도 5에 도시된 바와 같이 제1계층에서 현재 블록(Bc)에 인접하는 블록들의 수직측 및 수평측 움직임 벡터간 절대값의 차가 작은 블록들의 평균을 취함으로써 결정하는 것이다. 인접 블록들인 B1, B2, B3, 그리고 B4중에서 수직측 블록들(B1, B2)의 움직임 벡터간 절대값 차를 D1이라 하고, 수평측 블록들(B3, B4)의 움직임 벡터간 절대값 차를 D2라 할 때, D1과 D2는 다음과 같이 표현될 수 있다.In the second method, instead of taking an intermediate value of neighboring motion vectors, as shown in FIG. 5, the blocks having a small difference in absolute value between vertical and horizontal motion vectors of blocks adjacent to the current block B c in the first layer are shown in FIG. 5. It is determined by taking the average. The absolute value difference between the motion vectors of the vertical blocks B 1 and B 2 among the adjacent blocks B 1 , B 2 , B 3 , and B 4 is called D 1 , and the horizontal blocks B 3 , B 4 When the absolute difference between the motion vectors of) is D 2 , D 1 and D 2 may be expressed as follows.
만일 D1<D2라면 상기 움직임 벡터 후보는 B3과 B4의 움직임 벡터의 평균으로 구해지고, 그 반대의 경우라면 B1과 B2의 움직임 벡터의 평균으로 구해질 수 있다. 이렇게 얻어진 움직임 벡터 후보를 1/2로 크기를 줄여서 제1계층(300)에서의 초기 탐색점(301)으로 사용한다.If D 1 <D 2, the motion vector candidate may be obtained as an average of motion vectors of B 3 and B 4 , and vice versa, as a mean of motion vectors of B 1 and B 2 . The motion vector candidate thus obtained is reduced to 1/2 to be used as the initial search point 301 in the first layer 300.
세번째 방법은 도 3에 도시된 이웃 블록들중 306, 308 그리고 309의 움직임 벡터에 해당하는 제1계층(300)의 화소 블록의 위치를 찾고, 각 화소 블록의 위치에서 ±1 화소 범위의 탐색영역에 대해 SAD를 구하고, 구해진 SAD중 최소 SAD를 갖는 화소의 위치를 초기 탐색점(301)으로 사용한다.The third method finds the position of the pixel block of the first layer 300 corresponding to the motion vectors of 306, 308, and 309 among the neighboring blocks shown in FIG. 3, and searches the region of ± 1 pixel at the position of each pixel block. For SAD, the position of the pixel having the smallest SAD among the obtained SADs is used as the initial search point 301.
상술한 방법중 하나로 구해진 초기 탐색점의 위치에서 ±2 화소 범위의 탐색영역을 탐색하여 SAD가 최소인 화소위치를 제2움직임 벡터로 결정한다.The search region in the range of ± 2 pixels is searched at the position of the initial search point obtained by one of the above methods, and the pixel position having the smallest SAD is determined as the second motion vector.
상기 단계들에서 구해진 제1 및 제2움직임 벡터중 SAD가 작은 벡터를 제2계층(310)에서현재 블록에 대한 초기 움직임 벡터로 결정한다(206단계).The SAD of the first and second motion vectors obtained in the above steps is determined as the initial motion vector for the current block in the second layer 310 (step 206).
제2계층(310)에서는 상기 단계에서 결정된 초기 움직임 벡터를 중심으로 ±2화소 범위에 대해 탐색하여 SAD가 최소인 화소의 위치를 최종 움직임 벡터로 결정한다(208단계).The second layer 310 searches for a ± 2 pixel range based on the initial motion vector determined in the above step, and determines the position of the pixel having the smallest SAD as the final motion vector (step 208).
한편, 상술한 본 발명의 움직임 추정 방법에 대한 실시예는 컴퓨터에서 실행될 수 있는 프로그램으로 작성가능하다. 그리고 컴퓨터에서 사용되는 매체로부터 상기 프로그램을 동작시키는 범용 디지털 컴퓨터에서 구현될 수 있다. 상기 매체는 마크네틱 저장매체(예: 롬, 플로피디스크, 하드디스크 등), 광학적 판독매체(예:CD-ROM 등) 및 캐리어 웨이브(예: 인터넷을 통해 전송)와 같은 저장매체를 포함한다.Meanwhile, the above-described embodiment of the motion estimation method of the present invention can be written as a program that can be executed in a computer. And it can be implemented in a general-purpose digital computer for operating the program from a medium used in the computer. The medium includes storage media such as a magnetic storage medium (e.g., ROM, floppy disk, hard disk, etc.), an optical reading medium (e.g., CD-ROM, etc.) and a carrier wave (e.g., transmitted over the Internet).
그리고 본 발명을 구현하기 위한 기능적인(functional) 프로그램, 코드 및 코드 세그먼트들은 본 발명이 속하는 기술분야의 프로그래머들에 의해 용이하게 추론될 수 있다.And functional programs, codes and code segments for implementing the present invention can be easily inferred by programmers in the art to which the present invention belongs.
본 발명에 의하면, 동영상 부호화시 가장 큰 복잡도를 요구하는 움직임 추정방법에 있어서 먼저, 원 영상을 2:1로 부표본화하고, 부표본화된 영역을 3단계로 감소하면서 탐색하여 초기 움직임 벡터를 결정하며, 원 영상에서는 초기 움직임 벡터 주변의 소정 영역에 대해서만 탐색하므로, 보다 빠른 탐색이 가능하다. 또한, 이 방법을 하드웨어로 구현하는 경우 처리될 블록과 탐색영역의 크기에 따라 결정되는 연산처리단위(Procassing Element)들의 크기도 감소하므로 비용이 절감될 수 있다.According to the present invention, in a motion estimation method that requires the largest complexity in video encoding, first, sub-sample the original image to 2: 1, and search for the sub-sampled area in three steps to determine the initial motion vector. In the original image, only a predetermined area around the initial motion vector is searched, thereby enabling faster searching. In addition, when the method is implemented in hardware, the size of the processing elements (procassing elements) determined according to the size of the block to be processed and the search area may be reduced, thereby reducing costs.
Claims (15)
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| KR1019980061601A KR100335434B1 (en) | 1998-12-30 | 1998-12-30 | Motion estimation method |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| KR1019980061601A KR100335434B1 (en) | 1998-12-30 | 1998-12-30 | Motion estimation method |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| KR20000045075A KR20000045075A (en) | 2000-07-15 |
| KR100335434B1 true KR100335434B1 (en) | 2002-06-20 |
Family
ID=19568330
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| KR1019980061601A Expired - Fee Related KR100335434B1 (en) | 1998-12-30 | 1998-12-30 | Motion estimation method |
Country Status (1)
| Country | Link |
|---|---|
| KR (1) | KR100335434B1 (en) |
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US12335516B2 (en) | 2021-05-21 | 2025-06-17 | Samsung Electronics Co., Ltd. | Video encoder and operating method of the video encoder |
Families Citing this family (7)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| KR100450746B1 (en) * | 2001-12-15 | 2004-10-01 | 한국전자통신연구원 | Apparatus and method for performing mixed motion estimation based on hierarchical Search |
| KR20040008359A (en) * | 2002-07-18 | 2004-01-31 | 삼성전자주식회사 | Method for estimating motion using hierarchical search and apparatus thereof and image encoding system using thereof |
| KR20040013325A (en) * | 2002-08-05 | 2004-02-14 | 엘지전자 주식회사 | Method for compression moving picture |
| KR100534207B1 (en) * | 2002-12-09 | 2005-12-08 | 삼성전자주식회사 | Device and method for motion estimating of video coder |
| KR100631777B1 (en) | 2004-03-31 | 2006-10-12 | 삼성전자주식회사 | Method and apparatus for effectively compressing motion vectors in multi-layer |
| KR100699835B1 (en) * | 2005-03-09 | 2007-03-27 | 삼성전자주식회사 | Hierarchical Motion Predictor and Motion Vector Prediction Method |
| KR100910209B1 (en) * | 2006-11-28 | 2009-07-30 | 한양대학교 산학협력단 | Apparatus and Method for the fast full search motion estimation using the partitioned search window |
-
1998
- 1998-12-30 KR KR1019980061601A patent/KR100335434B1/en not_active Expired - Fee Related
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US12335516B2 (en) | 2021-05-21 | 2025-06-17 | Samsung Electronics Co., Ltd. | Video encoder and operating method of the video encoder |
Also Published As
| Publication number | Publication date |
|---|---|
| KR20000045075A (en) | 2000-07-15 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US6628711B1 (en) | Method and apparatus for compensating for jitter in a digital video image | |
| EP1389016B1 (en) | Improved motion estimation and block matching pattern | |
| Liu et al. | Codingflow: Enable video coding for video stabilization | |
| JP4528441B2 (en) | Hierarchical motion estimation processing and apparatus using block matching method and integrated projection method | |
| JP5044568B2 (en) | Motion estimation using predictive guided decimation search | |
| US7590180B2 (en) | Device for and method of estimating motion in video encoder | |
| US7580456B2 (en) | Prediction-based directional fractional pixel motion estimation for video coding | |
| KR100752530B1 (en) | Motion estimation algorithm | |
| EP1430724B1 (en) | Motion estimation and/or compensation | |
| JP3538055B2 (en) | Motion vector detection device | |
| TWI382770B (en) | An efficient adaptive mode selection technique for h.264/avc-coded video delivery in burst-packet-loss networks | |
| US20050123039A1 (en) | Motion estimation method for motion picture encoding and recording medium having program recorded thereon to implement the motion estimation method | |
| US8121194B2 (en) | Fast macroblock encoding with the early qualification of skip prediction mode using its temporal coherence | |
| US20060098886A1 (en) | Efficient predictive image parameter estimation | |
| KR100335434B1 (en) | Motion estimation method | |
| KR100234264B1 (en) | Block matching method using moving target window | |
| KR100408294B1 (en) | Method adapted for low bit-rate moving picture coding | |
| US8379712B2 (en) | Image search methods for reducing computational complexity of motion estimation | |
| Li et al. | A Bayer motion estimation for motion-compensated frame interpolation | |
| Tsekeridou et al. | Vector rational interpolation schemes for erroneous motion field estimation applied to MPEG-2 error concealment | |
| KR100529331B1 (en) | Method of estimating motion vector in layered frame structure | |
| Chan et al. | A novel predictive global motion estimation for video coding | |
| JP2008072608A (en) | Apparatus and method for encoding image | |
| KR100413002B1 (en) | Apparatus and method for block matching by using dispersed accumulate array in video coder | |
| Song et al. | Fast motion estimation algorithm using spatial correlation of motion field and hierarchical search |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| PA0109 | Patent application |
Patent event code: PA01091R01D Comment text: Patent Application Patent event date: 19981230 |
|
| A201 | Request for examination | ||
| PA0201 | Request for examination |
Patent event code: PA02012R01D Patent event date: 20000327 Comment text: Request for Examination of Application Patent event code: PA02011R01I Patent event date: 19981230 Comment text: Patent Application |
|
| PG1501 | Laying open of application | ||
| E701 | Decision to grant or registration of patent right | ||
| PE0701 | Decision of registration |
Patent event code: PE07011S01D Comment text: Decision to Grant Registration Patent event date: 20020327 |
|
| GRNT | Written decision to grant | ||
| PR0701 | Registration of establishment |
Comment text: Registration of Establishment Patent event date: 20020423 Patent event code: PR07011E01D |
|
| PR1002 | Payment of registration fee |
Payment date: 20020424 End annual number: 3 Start annual number: 1 |
|
| PG1601 | Publication of registration | ||
| PR1001 | Payment of annual fee |
Payment date: 20050330 Start annual number: 4 End annual number: 4 |
|
| PR1001 | Payment of annual fee |
Payment date: 20060330 Start annual number: 5 End annual number: 5 |
|
| PR1001 | Payment of annual fee |
Payment date: 20070329 Start annual number: 6 End annual number: 6 |
|
| FPAY | Annual fee payment |
Payment date: 20080328 Year of fee payment: 7 |
|
| PR1001 | Payment of annual fee |
Payment date: 20080328 Start annual number: 7 End annual number: 7 |
|
| LAPS | Lapse due to unpaid annual fee | ||
| PC1903 | Unpaid annual fee |