[go: up one dir, main page]

KR20070000702A - 탐색영역 재설정을 이용한 고속 움직임 예측 장치 및 방법 - Google Patents

탐색영역 재설정을 이용한 고속 움직임 예측 장치 및 방법 Download PDF

Info

Publication number
KR20070000702A
KR20070000702A KR1020050056265A KR20050056265A KR20070000702A KR 20070000702 A KR20070000702 A KR 20070000702A KR 1020050056265 A KR1020050056265 A KR 1020050056265A KR 20050056265 A KR20050056265 A KR 20050056265A KR 20070000702 A KR20070000702 A KR 20070000702A
Authority
KR
South Korea
Prior art keywords
search
block
search area
norm
previous frame
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.)
Ceased
Application number
KR1020050056265A
Other languages
English (en)
Inventor
최윤식
서동완
Original Assignee
연세대학교 산학협력단
Priority date (The priority date 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 date listed.)
Filing date
Publication date
Application filed by 연세대학교 산학협력단 filed Critical 연세대학교 산학협력단
Priority to KR1020050056265A priority Critical patent/KR20070000702A/ko
Publication of KR20070000702A publication Critical patent/KR20070000702A/ko
Ceased legal-status Critical Current

Links

Images

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/557—Motion estimation characterised by stopping computation or iteration based on certain criteria, e.g. error magnitude being too large or early exit
    • 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/56—Motion estimation with initialisation of the vector search, e.g. estimating a good candidate to initiate a search
    • 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/57—Motion estimation characterised by a search window with variable size or shape

Landscapes

  • Engineering & Computer Science (AREA)
  • Multimedia (AREA)
  • Signal Processing (AREA)
  • Computing Systems (AREA)
  • Theoretical Computer Science (AREA)
  • Compression Or Coding Systems Of Tv Signals (AREA)

Abstract

탐색영역 재설정을 이용한 고속 움직임 예측 장치 및 방법이 개시된다. 놈산출부는 이전 프레임내 모든 위치에서의 소정 크기의 블록을 구성하는 픽셀값들의 합 및 현재 블록을 구성하는 픽셀값들의 합으로 정의되는 각각의 블록의 놈을 산출한다. SAD산출부는 이전 프레임에서 (0,0)에 해당하는 위치에서 이전 프레임내의 블록과 현재 블록의 대응되는 위치의 픽셀의 차이값의 절대값을 합산하여 기준 SAD를 산출한다. 탐색영역설정부는 현재 블록을 소정 개수로 분할하여 후보탐색영역을 설정하고, 후보탐색영역들 내의 탐색위치마다 이전 프레임내의 블록의 놈과 현재 블록의 놈의 차이의 절대값이 기준 SAD보다 작아지는 탐색위치의 수가 가장 많은 후보탐색영역을 탐색영역으로 설정한다. 움직임벡터결정부는 설정된 탐색영역에 해당하는 탐색위치마다 산출한 SAD가 최소가 되는 위치에 해당하는 움직임 벡터를 최종적인 움직임 벡터로 결정한다. 본 발명에 따르면, 설정된 탐색영역내에서만 움직임 예측을 수행하도록 하여 계산량을 현저히 줄일 수 있고, 탐색영역을 줄이는 단계를 증가시키거나 감소시킴으로써 화질과 계산량을 조절할 수 있다.

Description

탐색영역 재설정을 이용한 고속 움직임 예측 장치 및 방법{Apparatus and method for fast motion estimation based on reduced search ranges}
도 1은 본 발명에 따른 탐색영역 재설정을 이용한 고속 움직임 예측 장치가 적용된 부호화기의 바람직한 실시예의 구성을 도시한 블록도,
도 2는 움직임 추정부(170)의 상세한 구성을 도시한 블록도,
도 3은 본 발명에 따른 탐색영역 재설정을 이용한 고속 움직임 예측 방법의 바람직한 수행과정을 도시한 흐름도,
도 4는 본 발명에 따른 탐색영역 재설정을 이용한 고속 움직임 예측 장치에서 제1탐색영역을 선택하는 과정을 도시한 도면, 그리고,
도 5는 본 발명에 따른 탐색영역 재설정을 이용한 고속 움직임 예측 장치에서 제1탐색영역 중에서 제2탐색영역을 선택하는 과정을 도시한 도면이다.
본 발명은 비디오 압축 부호화 표준을 위한 움직임 예측 장치 및 방법에 관한 것으로, 보다 상세하게는, 참조프레임에서 후보 매크로블록의 놈과 현재 매크로블록의 놈의 차이를 통해 최적의 움직임 벡터가 존재할 확률이 높은 탐색 영역을 설정하여 고속으로 움직임을 예측하는 장치 및 방법에 관한 것이다.
통신 기술의 급속한 발전으로 인해 이동통신상에서의 멀티미디어 서비스에 대한 수요가 증가하고 있다. 하지만 비교적 적은 양의 데이터만을 전송할 수 있는 이동통신 채널환경에서 깨끗한 화질의 영상을 안정적이면서도 빠르게 서비스하는 일은 매우 어렵다. 한편, 동영상 부호화에서는 높은 데이터 압축률을 얻기 위해 시간적 중복성을 제거하는 움직임 보상 부호화가 널리 쓰이고 있으며, 이는 MPEG, H.263 등과 같은 국제 영상 부호화 표준에서 중요한 부분을 차지하고 있다. 움직임 보상 부호화 기법은 움직임 예측을 통하여 현재의 매크로블록에 가장 유사한 매크로블록을 이전 프레임으로부터 취하고, 예측된 영상과 입력영상의 차를 변환 부호화하는 방법이다.
종래의 부호화기의 움직임 추정에 사용되는 움직임 예측 기법에는 블록정합 알고리즘(Block Matching Algorithm : BMA)이 있다. 블록정합 알고리즘은 블록내의 모든 화소가 같은 움직임 벡터를 갖는다는 가정 하에 이전 프레임으로부터 블록단위의 움직임을 추정하는 방법이다. 가장 널리 쓰이는 블록 정합 알고리즘으로는 전역 탐색 기법(Full Search BMA : FS-BMA)이 있다. 전역 탐색 기법은 이전 프레임의 탐색영역 내에서 가장 유사한 블록을 찾기 때문에 최적의 움직임 벡터를 찾을 수 있다. 그러나, 전역 탐색 기법은 각각의 탐색위치마다 MAD(Mean Absolute Difference), MSE(Mean Square Error) 등을 계산해야 하기 때문에 탐색영역과 탐색에 사용되는 블록의 크기가 증가함에 따라서 계산량이 지수 함수적으로 증가하는 문제점을 가지고 있다. 이러한 큰 계산량은 영상의 실시간 처리 및 전송을 어렵게 하기 때문에 그 동안 많은 고속 움직임 예측 기법들이 제안되어 왔다.
대표적인 고속 움직임 예측 알고리즘으로는 3 스텝 계층 탐색 기법(three-step hierarchical search: 3SHS), 2차원 대수 탐색 기법 (2-D logarithmic search: LOGS), MPEG-4 part 7에서 고속 움직임 예측기법으로 채택된 고속 움직임 예측 방법(MVFAST), 크로스-다이아몬드 헥사곤 탐색 방법(CDHS) 및 MPEG-4 Part 10 및 H.264에서 사용하는 언시매트릭컬-크로스 멀티 헥사곤 그리드 탐색 방법(UMHexagonS) 등이 널리 알려져 있다. 이 밖에도 이러한 고속 움직임 예측기법의 변형형태로서 여러 고속 움직임 예측기법들이 존재한다. 고전적인 방법의 3 스텝 계층 탐색 기법, 2차원 대수 탐색 기법과 그의 변형적인 방법은 탐색 영역 내에서 움직임 벡터의 분포가 단일 형태(unimodal)라는 가정 하에 시작된 알고리즘이다. 따라서, 실제 영상에서는 국소적인 최소치(local minimum)에 빠지기 쉬운 오류가 있고, 움직임이 큰 영상에서 전역 탐색 기법에 비해 현저하게 성능이 저하되는 문제점이 있었다.
비교적 최근에 알려진 MPEG-4 part 7에서 고속 움직임 예측기법으로 채택된 고속 움직임 예측 방법, 크로스-다이아몬드 헥사곤 탐색 방법, MPEG-4 Part 10 및 H.264에서 사용하는 언시매트릭컬-크로스 멀티 헥사곤 그리드 탐색 방법 등의 방법은 탐색을 수행하면서 최적의 움직임벡터가 존재하는 방향으로 탐색을 진행하는 방법을 취하고 있다. 비교적 전역 탐색 방법과 거의 동일한 결과를 나타낸다. 하지만 탐색을 진행하면서 계속 탐색 진행 방향을 평가해야 하므로 하드웨어 디자인을 고려할 때 적합하지 않다. 하드웨어적인 측면서는 계산의 일관성(Regularity)이 존재 해야만 SIMD(Single Instruction Multiple Data) 등을 활용한 고속 계산이 가능하기 때문이다.
본 발명이 이루고자하는 기술적 과제는 각각의 매크로 블록 놈의 차이값 및 SAD와의 관계를 통해서 최적의 움직임 벡터가 존재할 확률이 높은 탐색영역으로 탐색영역을 축소하여 재설정하여 움직임 예측의 계산적인 일관성을 유지하면서도 계산량을 줄임으로써 효율적인 움직임 예측이 가능한 탐색영역 재설정을 이용한 고속 움직임 예측 장치 및 방법을 제공하는 데 있다.
본 발명이 이루고자 하는 다른 기술적 과제는 각각의 매크로 블록 놈의 차이값 및 SAD와의 관계를 통해서 최적의 움직임 벡터가 존재할 확률이 높은 탐색영역으로 탐색영역을 축소하여 재설정하여 움직임 예측의 계산적인 일관성을 유지하면서도 계산량을 줄임으로써 효율적인 움직임 예측이 가능한 탐색영역 재설정을 이용한 고속 움직임 예측 방법을 컴퓨터에서 실행시키기 위한 프로그램을 기록한 컴퓨터로 읽을 수 있는 기록매체를 제공하는 데 있다.
상기의 기술적 과제를 달성하기 위한, 본 발명에 따른 탐색영역 재설정을 이용한 고속 움직임 예측 장치는, 이전 프레임내 모든 위치에서의 소정 크기의 블록을 구성하는 픽셀값들의 합 및 현재 블록을 구성하는 픽셀값들의 합으로 정의되는 각각의 블록의 놈을 산출하는 놈산출부; 상기 이전 프레임에서 (0,0)에 해당하는 위치에서 상기 이전 프레임내의 블록과 상기 현재 블록의 대응되는 위치의 픽셀의 차이값의 절대값을 합산하여 기준 SAD를 산출하는 SAD산출부; 상기 현재 블록을 소정 개수로 분할하여 후보탐색영역을 설정하고, 상기 후보탐색영역들 내의 탐색위치마다 상기 이전 프레임내의 블록의 놈과 상기 현재 블록의 놈의 차이의 절대값이 상기 기준 SAD보다 작아지는 탐색위치의 수가 가장 많은 후보탐색영역을 탐색영역으로 설정하는 탐색영역설정부; 및 상기 설정된 탐색영역에 해당하는 탐색위치마다 산출한 SAD가 최소가 되는 위치에 해당하는 움직임 벡터를 최종적인 움직임 벡터로 결정하는 움직임벡터결정부;를 구비한다.
상기의 다른 기술적 과제를 달성하기 위한, 본 발명에 따른 탐색영역 재설정을 이용한 고속 움직임 예측 방법은, 이전 프레임내 모든 위치에서의 소정 크기의 블록을 구성하는 픽셀값들의 합 및 현재 블록을 구성하는 픽셀값들의 합으로 정의되는 각각의 블록의 놈을 산출하는 단계; 상기 참조프레임에서 (0,0)에 해당하는 위치에서 상기 이전 프레임내의 블록과 상기 현재 블록의 대응되는 위치의 픽셀의 차이값의 절대값을 합산하여 기준 SAD를 산출하는 단계; 상기 현재 블록을 소정 개수로 분할하여 후보탐색영역을 설정하고, 상기 후보탐색영역들 내의 탐색위치마다 상기 이전 프레임내의 블록의 놈과 상기 현재 블록의 놈의 차이의 절대값이 상기 기준 SAD보다 작아지는 탐색위치의 수가 가장 많은 후보탐색영역을 탐색영역으로 설정하는 단계; 및 상기 설정된 탐색영역에 해당하는 탐색위치마다 산출한 SAD가 최소가 되는 위치에 해당하는 움직임 벡터를 최종적인 움직임 벡터로 결정하는 단계;를 갖는다.
이에 의해, 움직임 예측에 움직임 벡터의 분포가 단일 형태라는 가정에서 출 발하여 지역 최적화의 오류에 빠지거나 움직임 추정을 행하는 과정에서 최적 움직임 벡터가 존재할 방향으로 탐색을 진행하여 탐색 위치 수를 감소시키는 종래의 움직임 추정방법의 단점을 극복할 수 있다. 또한, 움직임 예측에 사용되는 SAD 계산을 수행하기 전에 탐색 영역 자체를 감소시킴으로써 계산적인 일관성을 유지하면서도 효율적으로 움직임 예측의 계산량을 감소시킬 수 있다.
이하에서 첨부된 도면들을 참조하여 본 발명에 따른 탐색영역 재설정을 이용한 고속 움직임 예측 장치 및 방법의 바람직한 실시예에 대해 상세하게 설명한다.
도 1은 본 발명에 따른 탐색영역 재설정을 이용한 고속 움직임 예측 장치가 적용된 부호화기의 상세한 구성을 도시한 블록도이다.
도 1을 참조하면, 본 발명에 따른 탐색영역 재설정을 이용한 고속 움직임 예측 장치가 적용된 부호화기(100)는, 이산코사인변환부(110), 양자화부(120), 가변장길이부호화부(130), 역양자화부(140), 역이산코사인변환부(150), 프레임 메모리부(160) 및 움직임추정부(170)를 구비한다.
먼저, 부호화기(100)에 입력되는 영상 데이터는 8×8 화소의 블록으로 분해된다. 이산코사인변환부(Discrete Cosine Transform : DCT)(110)는 영상 데이터의 공간적 상관성을 제거하기 위해 8×8 화소 블록 단위로 입력되는 영상 데이터에 대해 이산코사인변환연산을 수행한다. 양자화부(Quantization : Q)(120)는 이산코사인변환부(120)에서 얻어진 DCT 계수에 대해 양자화를 수행하여, 몇 개의 대표 값으로 표현함으로써, 고효율 손실 압축을 수행한다. 가변길이부호화부(Variable Length Coding : VLC)(130)는 양자화된 DCT 변환 계수들에 대해 엔트로피 부호화를 수행하여 엔트로피 부호화된 데이터 스트림을 출력한다.
역양자화부(Inverse Quantization : IQ)(140)는 양자화부(120)에 의해 양자화된 영상 데이터를 역양자화한다. 역이산코사인변환부(150)는 역양자화부(140)에 의해 역양자화된 영상 데이터에 대해 역이산코사인변환연산을 수행한다. 프레임 메모리부(160)는 역이산코사인변환부(150)에 의해 역이산코사인변변환된 영상 데이터를 프레임 단위로 저장한다.
움직임 추정부(Motion Estimation : ME)(170)는 입력되는 현재 프레임의 영상 데이터와 프레임 메모리부(160)에 저장되어 있는 이전 프레임의 영상 데이터의 매크로블록에 대해 얻어진 놈과 소정의 매크로블록에 대해 계산된 기준 SAD를 기초로 탐색영역을 분할하고, 분할된 탐색영역 중에서 기준 SAD에 비해 놈의 차이값의 절대값이 작은 탐색포인트를 가장 많이 가지는 탐색영역으로부터 최적의 움직임 벡터를 파악한다. 움직임 추정부(170)는 매크로블록 단위로 움직임 벡터를 추정하나 H.264(MPEG-4 Part 10)에서 사용하는 다양한 크기의 블록을 기초로 움직임 벡터의 추정이 가능하다. 도 2에는 움직임 추정부(170)의 상세한 구성이 도시되어 있다.
도 2를 참조하면, 움직임 추정부(170)는 놈산출부(210), SAD산출부(220), 탐색영역설정부(230) 및 움직임벡터결정부(240)를 구비한다.
놈산출부(210)는 참조프레임내 모든 위치에서의 16×16 단위의 매크로블록의 놈(Norm)을 구하고, 현재 매크로블록의 놈을 구한다. 참조프레임은 이전 프레임의 부호화가 종료된 후 프레임 메모리(160)에 저장된 프레임을 의미한다. 현재 매크로블록은 입력 영상신호에서 16×16에 해당하는 블록을 의미한다. 매크로블록의 놈은 해당 매크로블록에 포함되는 픽셀값들의 합이다.
SAD산출부(220)는 (0,0) 움직임 벡터에서의 SAD를 계산하여 기준 SAD로 설정한다. 기준 SAD는 참조프레임에서 (0,0)에 해당하는 위치에서 이전 매크로블록과 현재 매크로블록의 대응되는 위치의 픽셀끼리 차이의 절대값을 구하여 모두 더한 값이다.
탐색영역설정부(230)는 주어진 매크로블록을 9개의 사각형 탐색영역으로 동등하게 분할하여 제1탐색영역으로 설정될 수 있는 제1후보 탐색영역을 설정한다. 탐색영역설정부(230)는 제1후보 탐색영역들 내의 탐색위치마다 참조프레임 내의 매크로블록의 놈과 현재 매크로블록의 놈의 차이의 절대값을 구하여 기준 SAD보다 작아지는 탐색위치의 수가 가장 많은 영역을 제1탐색영역으로 설정한다. 다음으로, 탐색영역설정부(230)는 제1탐색영역을 9개의 사각형 탐색영역으로 동등하게 분할하여 제2탐색영역으로 설정될 수 있는 제2후보 탐색영역을 설정한다. 또한, 탐색영역설정부(230)는 제2후보 탐색영역들 내의 탐색위치마다 참조프레임 내의 매크로블록의 놈과 현재 매크로블록의 놈의 차이의 절대값을 구하여 기준 SAD보다 작아지는 탐색위치의 수가 가장 많은 영역을 제2탐색영역으로 설정한다. 만약 탐색영역이 추어진 임계넓이보다 크면 탐색영역설정부(230)는 제2탐색영역을 추가적으로 분할하여 제3탐색영역 및 제4탐색영역을 설정함으로써 탐색영역을 보다 줄일 수 있다.
움직임벡터결정부(240)는 전역탐색방법과 마찬가지로 제2탐색영역에 해당하는 탐색위치마다 SAD를 구하여 그 값이 최소가 되는 위치에 해당하는 움직임 벡터를 최적의 움직임 벡터로 설정하여 움직임 예측을 수행한다.
도 3은 본 발명에 따른 탐색영역 재설정을 이용한 고속 움직임 예측 방법의 바람직한 수행과정을 도시한 흐름도이다.
도 3을 참조하면, 놈산출부(210)는 참조프레임내 모든 위치에서의 16×16 단위의 블록 놈을 구하고, 현재 매크로블록의 놈을 구한다(S300). 다음으로, SAD산출부(220)는 (0,0) 움직임 벡터에서의 SAD를 계산하여 기준 SAD로 설정한다(S310). 기준 SAD는 참조프레임에서 (0,0)에 해당하는 위치에서 매크로블록과 현재 매크로블록을 같은 위치의 픽셀끼리 차이의 절대값을 구하여 모두 더한 값이다.
탐색영역설정부(230)는 초기 탐색영역을 9개의 사각형으로 동등하게 분할하여 후보탐색영역을 설정한다(S320). 다음으로, 탐색영역설정부(240)는 후보탐색영역들 내의 탐색위치마다 참조프레임 내의 매크로블록 놈과 현재 매크로블록 놈의 차이의 절대값을 구하여 기준 SAD보다 작아지는 탐색위치의 수가 가장 많은 영역을 탐색영역으로 설정한다(S330). 만약 설정된 탐색영역의 크기가 사전에 정해져 있는 임계값보다 크면, 탐색영역설정부(230)는 탐색영역의 크기가 사전에 정해져 있는 임계값보다 작아질 때까지 설정된 탐색영역에 대해 S320단계 및 S330단계를 반복적으로 수행한다(S340). 움직임벡터결정부(240)는 최종적으로 설정된 탐색영역에 해당하는 탐색위치마다 SAD를 구하여 그 값이 최소가 되는 위치에 해당하는 움직임 벡터를 최종적인 움직임 벡터로 설정한다(S350). 이상의 과정을 수행하여 SAD와 블록 놈의 관계에 따라서 탐색영역을 줄여 움직임 예측에 사용되는 연산을 감소시켜 고속의 움직임 예측이 가능하다.
SAD는 다음의 수학식 1에 의해 산출되며, 기준 SAD 값은 수학식 1에서 (mvx, mvy)를 (0,0)로 설정하여 산출된 값이다.
Figure 112005034582944-PAT00001
한편, 참조프레임에서 (mvx, mvy)에 정의되는 위치에서의 매크로블록 놈 MN과 현재 프레임에서 (i,j) 위치에 해당하는 매크로블록 놈 MM은 각각 수학식 2와 수학식 3에 의해 얻어진다.
Figure 112005034582944-PAT00002
Figure 112005034582944-PAT00003
수학식 2의 참조프레임의 블록 놈은 미리 전체 위치에서 구하기 때문에 반복적으로 겹쳐지는 위치에서의 계산은 생략할 수 있다. (mvx, mvy)에 해당하는 위치에서의 SAD 값은 참조프레임의 해당 위치에서의 매크로블록 놈과 현재 매크로블록 놈의 차이값보다 항상 크거나 같은 성질을 가지고 있으며, 이는 하기의 수학식 4에 의해 표현될 수 있다. 따라서, 기준 SAD보다 작은 SAD 값을 가질 수 있는 위치가 되기 위해서는 기준 SAD에 비해서 매크로블록 놈의 차이의 절대값이 작아야 한다.
Figure 112005034582944-PAT00004
수학식 1, 2, 3 및 4에서 N은 매크로블록의 한변의 길이(예를 들면, 16)이고, Fn은 현재 프레임을 의미하며, Fn-1은 참조프레임을 의미하고, (mvx, mvy)는 움직임 벡터를 의미한다.
도 4는 초기 탐색 영역에서 9개의 후보 탐색 영역을 구성하여 놈과 SAD 관계를 사용하여 제1탐색영역을 구하는 과정을 도시한 도면이고, 도 5는 제1탐색영역의 크기가 사전에 정해진 임계값보다 큰 경우 제1탐색영역내에서 9개의 후보 탐색영역을 구성하여 놈과 SAD 관계를 사용하여 제2탐색 영역을 구하는 과정을 도시한 도면이다.
도 4를 참조하면, 초기 탐색영역이 SRinit으로 주어졌을 경우, 탐색영역설정부(230)는 SRinit을 9개의 동등한 사각형의 후보 탐색 영역 A={A 1 , A 2 , …, A 9 }로 분할한다. 다음으로, SAD산출부(220)는 (0,0) 움직임 벡터를 나타내는 탐색 위치에서 기준 SAD를 계산한다. 기준 SAD SADbase는 하기의 수학식 5에 의해 구해진다.
Figure 112005034582944-PAT00005
다음으로, 탐색영역설정부(230)는 각각의 후보 탐색영역내에서 놈의 차이의 절대값과 기준 SAD를 비교하여 하기의 수학식 6을 만족하는 탐색위치의 수가 가장 많은 후보 탐색영역을 제1탐색영역으로 설정한다.
Figure 112005034582944-PAT00006
제1탐색영역을 설정하는 방법은 하기의 수학식 7에 의해 표현되며, 수학식 7에서
Figure 112005034582944-PAT00007
는 후보 탐색 영역 Ai 내의 탐색 위치들 중에서 수학식 6을 만족하는 탐색 위치 수를 의미한다. 도 4에 도시된 예에 따르면,
Figure 112005034582944-PAT00008
값이 가장 큰 후보탐색영역은 A5가 되며, 따라서, 제1탐색영역 SR1은 A5로 설정된다.
Figure 112005034582944-PAT00009
한편, 이상의 과정을 수행하여 설정된 제1탐색영역의 크기가 사전에 정해진 임계값보다 크면 추가적으로 제1탐색영역에 대한 분할과정이 수행된다. 제1탐색영역에 대한 추가적인 분할예는 도 5에 도시되어 있다.
도 5를 참조하면, 탐색영역설정부(230)는 제1탐색영역 SR1을 9개의 동등한 사각형의 후보 탐색영역 B={B 1 , B 2 , …, B 9 }로 분할한다. 다음으로 탐색영역설정부(230)는 도 5에 도시된 각 후보 탐색영역 내에서 놈의 차이의 절대값과 기준 SAD를 비교하여 수학식 6을 만족하는 탐색위치의 수가 가장 많은 후보 탐색영역을 제2탐색영역으로 설정한다. 제2탐색영역은 수학식 8에 의해 얻어지며, 수학식 8에서
Figure 112005034582944-PAT00010
는 후보 탐색영역 Bi 내의 탐색위치들 중에서 수학식 6을 만족하는 탐색위치 수를 의미한다. 도 5에 도시된 실시예에 따르면,
Figure 112005034582944-PAT00011
값이 가장 큰 후보 탐색영역은 B 6 가 되며, 따라서, 제2탐색영역 SR2는 B6으로 설정된다.
Figure 112005034582944-PAT00012
최종적으로 제2탐색영역이 설정되면, 움직임벡터결정부(240) 제2탐색영역 내에서 전역 탐색 방법으로 최종 움직임 벡터를 구한다. 최종 움직임 벡터는 수학식 9에 의해 얻어진다.
Figure 112005034582944-PAT00013
본 발명은 또한 컴퓨터로 읽을 수 있는 기록매체에 컴퓨터가 읽을 수 있는 코드로서 구현하는 것이 가능하며 칩으로 구현 가능하다. 특히, 칩으로 구현하였을 경우 다른 고속 움직임 추정 알고리즘에 비해 계산상의 일관성을 유지하고 있는 장점이 있다. 컴퓨터가 읽을 수 있는 기록매체는 컴퓨터 시스템에 의하여 읽혀질 수 있는 데이터가 저장되는 모든 종류의 기록장치를 포함한다. 컴퓨터가 읽을 수 있는 기록매체의 예로는 ROM, RAM, CD-ROM, 자기 테이프, 하드디스크, 플로피디스크, 플래쉬 메모리, 광데이터 저장장치 등이 있으며, 또한 캐리어 웨이브(예를 들어 인터넷을 통한 전송)의 형태로 구현되는 것도 포함한다. 또한 컴퓨터가 읽을 수 있는 기록매체는 네트워크로 연결된 컴퓨터 시스템에 분산되어, 분산방식으로 컴퓨터가 읽을 수 있는 코드로서 저장되고 실행될 수 있다.
이상에서 본 발명의 바람직한 실시예에 대해 도시하고 설명하였으나, 본 발명은 상술한 특정의 바람직한 실시예에 한정되지 아니하며, 청구범위에서 청구하는 본 발명의 요지를 벗어남이 없이 당해 발명이 속하는 기술분야에서 통상의 지식을 가진 자라면 누구든지 다양한 변형 실시가 가능한 것은 물론이고, 그와 같은 변경은 청구범위 기재의 범위 내에 있게 된다.
본 발명에 따른 탐색영역 재설정을 이용한 고속 움직임 예측 장치 및 방법에 의하면, 참조 프레임 내의 후보 매크로블록의 놈과 현재 매크로블록의 놈의 차이의 절대값과 SAD의 관계를 통해 설정한 탐색영역내에서만 움직임 예측을 수행하도록 하여 종래의 탐색 기법에 비해서 계산량을 현저히 줄일 수 있다. 또한 기존의 고속 움직임 예측 기법에 비해서 계산상의 일관성을 유지할 수 있으므로 하드웨어 설계에 있어서 계산상의 장점을 가지며, 탐색영역을 줄이는 단계를 증가시키거나 감소시킴으로써 화질과 계산량을 조절할 수 있다.

Claims (11)

  1. 이전 프레임내 모든 위치에서의 소정 크기의 블록을 구성하는 픽셀값들의 합 및 현재 블록을 구성하는 픽셀값들의 합으로 정의되는 각각의 블록의 놈을 산출하는 놈산출부;
    상기 이전 프레임에서 (0,0)에 해당하는 위치에서 상기 이전 프레임내의 블록과 상기 현재 블록의 대응되는 위치의 픽셀의 차이값의 절대값을 합산하여 기준 SAD를 산출하는 SAD산출부;
    상기 현재 블록을 소정 개수로 분할하여 후보탐색영역을 설정하고, 상기 후보탐색영역들 내의 탐색위치마다 상기 이전 프레임내의 블록의 놈과 상기 현재 블록의 놈의 차이의 절대값이 상기 기준 SAD보다 작아지는 탐색위치의 수가 가장 많은 후보탐색영역을 탐색영역으로 설정하는 탐색영역설정부; 및
    상기 설정된 탐색영역에 해당하는 탐색위치마다 산출한 SAD가 최소가 되는 위치에 해당하는 움직임 벡터를 최종적인 움직임 벡터로 결정하는 움직임벡터결정부;를 포함하는 것을 특징으로 하는 탐색영역 재설정을 이용한 고속 움직임 예측 장치.
  2. 제 1항에 있어서,
    상기 탐색영역설정부는 상기 설정된 탐색영역의 크기가 소정의 임계값보다 크면, 상기 설정된 탐색영역을 추가적으로 분할하여 하위후보탐색영역을 설정하고, 상기 하위후보탐색영역들 내의 탐색위치마다 상기 이전 프레임내의 블록의 놈과 상기 현재 블록의 놈의 차이의 절대값이 상기 기준 SAD보다 작아지는 탐색위치의 수가 가장 많은 하위후보탐색영역을 상기 탐색영역으로 설정하는 것을 특징으로 하는 탐색영역 재설정을 이용한 고속 움직임 예측 장치.
  3. 제 1항 또는 제 2항에 있어서,
    상기 블록은 입력 영상신호에서 16×16의 크기를 갖는 매크로블록인 것을 특징으로 하는 탐색영역 재설정을 이용한 고속 움직임 예측 장치.
  4. 제 1항 또는 제 2항에 있어서,
    상기 SAD 산출부는 다음의 수학식의 (mvx, mvy)를 (0,0)로 설정하여 산출된 값을 상기 기준 SAD로 설정하는 것을 특징으로 하는 탐색영역 재설정을 이용한 고속 움직임 예측 장치:
    Figure 112005034582944-PAT00014
    ,
    여기서, N은 상기 블록의 한변의 길이, Fn은 현재 프레임, Fn-1은 이전 프레임, 그리고, (mvx, mvy)는 움직임 벡터를 의미한다.
  5. 제 1항 또는 제 2항에 있어서,
    상기 놈산출부는 각각 다음의 수학식 1 및 2에 의해 상기 이전 프레임에서 (mvx, mvy)에 정의되는 위치에서의 매크로블록의 놈 및 상기 현재 프레임에서 (i,j) 위치에 해당하는 매크로블록의 놈을 산출하는 것을 특징으로 하는 탐색영역 재설정을 이용한 고속 움직임 예측 장치:
    [수학식 1]
    Figure 112005034582944-PAT00015
    ,
    [수학식 2]
    Figure 112005034582944-PAT00016
    ,
    여기서, N은 상기 블록의 한변의 길이, Fn은 현재 프레임, Fn-1은 이전 프레임, (mvx, mvy)는 움직임 벡터, 그리고, MN 및 MM은 각각 상기 이전 프레임에서 (mvx, mvy)에 정의되는 위치에서의 매크로블록의 놈 및 상기 현재 프레임에서 (i,j) 위치에 해당하는 매크로블록의 놈을 의미한다.
  6. 제 1항 또는 제 2항에 있어서,
    상기 탐색영역설정부는 상기 후보탐색영역중에서 다음의 수학식 1 및 2를 만족하는 후보탐색영역을 상기 탐색영역으로 설정하는 것을 특징으로 하는 탐색영역 재설정을 이용한 고속 움직임 예측 장치:
    [수학식 1]
    Figure 112005034582944-PAT00017
    ,
    [수학식 2]
    Figure 112005034582944-PAT00018
    ,
    여기서, N은 상기 블록의 한변의 길이, Fn은 현재 프레임, Fn-1은 이전 프레임, (mvx, mvy)는 움직임 벡터, MN 및 MM은 각각 상기 이전 프레임에서 (mvx, mvy)에 정의되는 위치에서의 매크로블록의 놈 및 상기 현재 프레임에서 (i,j) 위치에 해당하는 매크로블록의 놈, SADbase는 상기 기준 SAD,
    Figure 112005034582944-PAT00019
    는 후보 탐색 영역 Ai 내의 탐색 위치들 중에서 상기 수학식 1을 만족하는 탐색 위치 수, SRinit는 초기 탐색영역, 그리고, SR은 탐색영역을 의미한다.
  7. 제 1항 또는 제 2항에 있어서,
    상기 움직임벡터결정부는 다음의 수학식에 의해 상기 최종적인 움직임 벡터를 설정하는 것을 특징으로 하는 탐색영역 재설정을 이용한 고속 움직임 예측 장치:
    Figure 112005034582944-PAT00020
    ,
    여기서, (Omvx, Omvy)는 최적의 움직임 벡터, (mvx, mvy)는 움직임 벡터, 그리고, SR은 상기 탐색영역을 의미한다.
  8. 이전 프레임내 모든 위치에서의 소정 크기의 블록을 구성하는 픽셀값들의 합 및 현재 블록을 구성하는 픽셀값들의 합으로 정의되는 각각의 블록의 놈을 산출하는 단계;
    상기 이전 프레임에서 (0,0)에 해당하는 위치에서 상기 이전 프레임내의 블록과 상기 현재 블록의 대응되는 위치의 픽셀의 차이값의 절대값을 합산하여 기준 SAD를 산출하는 단계;
    상기 현재 블록을 소정 개수로 분할하여 후보탐색영역을 설정하고, 상기 후보탐색영역들 내의 탐색위치마다 상기 이전 프레임내의 블록의 놈과 상기 현재 블록의 놈의 차이의 절대값이 상기 기준 SAD보다 작아지는 탐색위치의 수가 가장 많은 후보탐색영역을 탐색영역으로 설정하는 단계; 및
    상기 설정된 탐색영역에 해당하는 탐색위치마다 산출한 SAD가 최소가 되는 위치에 해당하는 움직임 벡터를 최종적인 움직임 벡터로 결정하는 단계;를 포함하는 것을 특징으로 하는 탐색영역 재설정을 이용한 고속 움직임 예측 방법.
  9. 제 8항에 있어서,
    상기 탐색영역설정단계는 상기 설정된 탐색영역의 크기가 소정의 임계값보다 크면, 상기 설정된 탐색영역을 추가적으로 분할하여 하위후보탐색영역을 설정하고, 상기 하위후보탐색영역들 내의 탐색위치마다 상기 이전 프레임내의 블록의 놈과 상기 현재 블록의 놈의 차이의 절대값이 상기 기준 SAD보다 작아지는 탐색위치의 수 가 가장 많은 하위후보탐색영역을 상기 탐색영역으로 설정하는 것을 특징으로 하는 탐색영역 재설정을 이용한 고속 움직임 예측 방법.
  10. 제 8항 또는 제 9항에 있어서,
    상기 블록은 입력 영상신호에서 16×16의 크기를 갖는 매크로블록인 것을 특징으로 하는 탐색영역 재설정을 이용한 고속 움직임 예측 방법.
  11. 이전 프레임내 모든 위치에서의 소정 크기의 블록을 구성하는 픽셀값들의 합 및 현재 블록을 구성하는 픽셀값들의 합으로 정의되는 각각의 블록의 놈을 산출하는 단계;
    상기 이전 프레임에서 (0,0)에 해당하는 위치에서 상기 이전 프레임내의 블록과 상기 현재 블록의 대응되는 위치의 픽셀의 차이값의 절대값을 합산하여 기준 SAD를 산출하는 단계;
    상기 현재 블록을 소정 개수로 분할하여 후보탐색영역을 설정하고, 상기 후보탐색영역들 내의 탐색위치마다 상기 이전 프레임내의 블록의 놈과 상기 현재 블록의 놈의 차이의 절대값이 상기 기준 SAD보다 작아지는 탐색위치의 수가 가장 많은 후보탐색영역을 탐색영역으로 설정하는 단계; 및
    상기 설정된 탐색영역에 해당하는 탐색위치마다 산출한 SAD가 최소가 되는 위치에 해당하는 움직임 벡터를 최종적인 움직임 벡터로 결정하는 단계;를 포함하는 것을 특징으로 하는 탐색영역 재설정을 이용한 고속 움직임 예측 방법을 컴퓨터 에서 실행시키기 위한 프로그램을 기록한 컴퓨터로 읽을 수 있는 기록매체.
KR1020050056265A 2005-06-28 2005-06-28 탐색영역 재설정을 이용한 고속 움직임 예측 장치 및 방법 Ceased KR20070000702A (ko)

Priority Applications (1)

Application Number Priority Date Filing Date Title
KR1020050056265A KR20070000702A (ko) 2005-06-28 2005-06-28 탐색영역 재설정을 이용한 고속 움직임 예측 장치 및 방법

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
KR1020050056265A KR20070000702A (ko) 2005-06-28 2005-06-28 탐색영역 재설정을 이용한 고속 움직임 예측 장치 및 방법

Publications (1)

Publication Number Publication Date
KR20070000702A true KR20070000702A (ko) 2007-01-03

Family

ID=37868457

Family Applications (1)

Application Number Title Priority Date Filing Date
KR1020050056265A Ceased KR20070000702A (ko) 2005-06-28 2005-06-28 탐색영역 재설정을 이용한 고속 움직임 예측 장치 및 방법

Country Status (1)

Country Link
KR (1) KR20070000702A (ko)

Cited By (5)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
KR100891768B1 (ko) * 2007-05-02 2009-04-07 삼성전자주식회사 모션 벡터 탐색 방법
KR101036552B1 (ko) * 2009-11-02 2011-05-24 중앙대학교 산학협력단 적응적 탐색 영역 및 부분 정합 오차 기반의 고속 움직임 추정 장치 및 방법
CN102263947A (zh) * 2010-05-27 2011-11-30 香港科技大学 图像运动估计的方法及系统
US9398249B2 (en) 2012-06-28 2016-07-19 Samsung Electronics Co., Ltd. Motion estimation system and method, display controller, and electronic device
CN116074533A (zh) * 2023-04-06 2023-05-05 湖南国科微电子股份有限公司 运动矢量预测方法、系统、电子设备及存储介质

Cited By (7)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
KR100891768B1 (ko) * 2007-05-02 2009-04-07 삼성전자주식회사 모션 벡터 탐색 방법
KR101036552B1 (ko) * 2009-11-02 2011-05-24 중앙대학교 산학협력단 적응적 탐색 영역 및 부분 정합 오차 기반의 고속 움직임 추정 장치 및 방법
CN102263947A (zh) * 2010-05-27 2011-11-30 香港科技大学 图像运动估计的方法及系统
CN102263947B (zh) * 2010-05-27 2016-07-06 香港科技大学 图像运动估计的方法及系统
US9398249B2 (en) 2012-06-28 2016-07-19 Samsung Electronics Co., Ltd. Motion estimation system and method, display controller, and electronic device
CN116074533A (zh) * 2023-04-06 2023-05-05 湖南国科微电子股份有限公司 运动矢量预测方法、系统、电子设备及存储介质
CN116074533B (zh) * 2023-04-06 2023-08-22 湖南国科微电子股份有限公司 运动矢量预测方法、系统、电子设备及存储介质

Similar Documents

Publication Publication Date Title
US8761254B2 (en) Image prediction encoding device, image prediction decoding device, image prediction encoding method, image prediction decoding method, image prediction encoding program, and image prediction decoding program
US8625916B2 (en) Method and apparatus for image encoding and image decoding
US8315309B2 (en) Method and apparatus for encoding and decoding an image by using consecutive motion estimation
CN101573984B (zh) 用于使用多个运动矢量预测因子来估计运动矢量的方法和设备，编码器、解码器和解码方法
US8693546B2 (en) Video encoding method and video decoding method
US20120076207A1 (en) Multiple-candidate motion estimation with advanced spatial filtering of differential motion vectors
JP2013502140A (ja) 動きベクトルの正確度の調節を利用した映像符号化、復号化方法及び装置
KR20050119422A (ko) 움직임 보상에 기반한 입력 영상의 노이즈 예측 및 그장치와, 이를 사용한 노이즈 제거 및 동영상 부호화 방법,이를 수행하기 위한 프로그램이 기록된 기록 매체
CN101978698A (zh) 用于对图像进行编码和解码的方法及设备
JP4417054B2 (ja) 離散コサイン変換係数を参照する動き推定方法及び装置
KR20110050480A (ko) 움직임 보상 비디오 코딩에 있어서, 이미지 블록들을 비교하기 위한 메트릭을 결정하는 방법 및 시스템
JP4494803B2 (ja) 動き補償に基づいた改善されたノイズ予測方法及びその装置とそれを使用した動画符号化方法及びその装置
US20090028241A1 (en) Device and method of coding moving image and device and method of decoding moving image
JP5613319B2 (ja) 映像符号化装置、映像符号化方法および映像符号化プログラム
KR100910209B1 (ko) 세분화된 탐색 영역을 기반으로 하는 고속 전영역 움직임예측 방법 및 그 장치
US8792549B2 (en) Decoder-derived geometric transformations for motion compensated inter prediction
KR20070000702A (ko) 탐색영역 재설정을 이용한 고속 움직임 예측 장치 및 방법
KR100508975B1 (ko) 다층 레벨 연속 제거 알고리즘을 이용한 동영상 움직임추정 방법
JP2009049969A (ja) 動画像符号化装置及び方法並びに動画像復号化装置及び方法
US8050324B2 (en) Method and apparatus for selecting a reference frame for motion estimation in video encoding
JP5832263B2 (ja) 画像符号化装置及び画像符号化方法
KR100859073B1 (ko) 움직임 추정 방법
JP5358485B2 (ja) 画像符号化装置
JP5913911B2 (ja) 画像符号化装置
JP2006074520A (ja) 動きベクトル検出装置

Legal Events

Date Code Title Description
A201 Request for examination
PA0109 Patent application

Patent event code: PA01091R01D

Comment text: Patent Application

Patent event date: 20050628

PA0201 Request for examination
E902 Notification of reason for refusal
PE0902 Notice of grounds for rejection

Comment text: Notification of reason for refusal

Patent event date: 20061013

Patent event code: PE09021S01D

PG1501 Laying open of application
E601 Decision to refuse application
PE0601 Decision on rejection of patent

Patent event date: 20070315

Comment text: Decision to Refuse Application

Patent event code: PE06012S01D

Patent event date: 20061013

Comment text: Notification of reason for refusal

Patent event code: PE06011S01I