블록 매칭 알고리즘

블록 매칭 알고리즘은 움직임 추정을 위해 일련의 디지털 비디오 프레임에서 일치하는 매크로 블록을 찾는 방법이다. 움직임 추정 뒤에 있는 기본적인 가정은 비디오 시퀀스 프레임에서 물체와 배경에 해당하는 패턴이 프레임 내에서 이동하여 후속 프레임에 해당하는 물체를 형성한다는 것이다. 이것은 비디오 시퀀스에서 시간적 중복성을 발견하는 데 사용할 수 있으며, 최소한으로 다른 알려진 매크로 블록의 내용을 참조하여 매크로 블록의 내용을 정의함으로써 프레임 간 비디오 압축의 효과를 높일 수 있다.

블록 매칭 알고리즘은 비디오의 현재 프레임을 매크로 블록으로 나누고, 각 매크로 블록을 해당 블록 및 그 인접 블록과 비디오의 인근 프레임(때로는 이전 블록만)에서 비교하는 것을 포함한다. 한 위치에서 다른 위치로 매크로 블록의 이동을 모형화하는 벡터가 생성된다. 프레임을 구성하는 모든 매크로 블록에 대해 계산된 이 운동은 프레임에서 추정된 운동을 구성한다.

좋은 매크로 블록 일치를 위한 검색 영역은 '검색 매개 변수', p에 의해 결정되는데, 여기서 p는 이전 프레임의 해당 매크로 블록의 4면 모두에 있는 픽셀 수입니다. 검색 매개 변수는 움직임의 척도다. p의 값이 클수록 잠재적인 움직임과 좋은 일치점을 찾을 가능성이 크다. 그러나 모든 잠재적 블록에 대한 완전한 검색은 계산적으로 비용이 많이 드는 작업이다. 대표적인 입력은 16픽셀 크기의 매크로 블록과 p = 7픽셀의 검색 영역이다.

블록 매칭과 3D 필터링은 이 접근방식을 이용해 정지 이미지와 디지털 비디오 모두에서 노이즈 감소와^[1] 디블러링과^[2] 같은 다양한 이미지 복원 역방향 문제를 해결한다.

동기

모션 추정은 일반적으로 비디오 시퀀스의 인접 프레임에서 2D 영상으로의 변환을 설명하는 모션 벡터를 결정하는 과정이다. 모션 벡터는 전체 이미지(글로벌 모션 추정) 또는 직사각형 블록, 임의 모양의 패치 또는 픽셀 당과 같은 특정 부품과 관련될 수 있다. 모션 벡터는 3차원 및 줌에서 회전 및 번역과 같이 실제 비디오 카메라의 움직임에 근사치를 줄 수 있는 변환 모델 또는 많은 다른 모델로 나타낼 수 있다.

이미지의 카메라나 물체를 이동하기 위해 다른 이미지로의 변환을 예측하기 위해 모션 벡터를 이미지에 적용하는 것을 모션 보정이라고 한다. 모션 추정과 모션 보상의 조합은 다른 많은 비디오 코덱뿐만 아니라 MPEG 1, 2, 4가 사용하는 비디오 압축의 핵심 부분이다.

모션 추정에 기반한 비디오 압축은 완전히 코드화된 프레임을 보내는 것과 반대로 본질적으로 엔트로피가 적은 인코딩된 차이 이미지를 전송함으로써 비트 저장에 도움이 된다. 그러나 전체 압축 프로세스에서 계산적으로 가장 비싸고 자원이 광범위한 작업은 모션 추정이다. 따라서 빠르고 계산적으로 저렴한 동작 추정 알고리즘은 비디오 압축이 필요하다.

평가 메트릭

매크로 블록을 다른 블록과 매칭하기 위한 메트릭은 비용 함수를 기반으로 한다. 계산 비용 측면에서 가장 인기 있는 것은 다음과 같다.

Mean difference or Mean Absolute Difference (MAD) = ${\frac {1}{N^{2}}}\sum _{i=0}^{n-1}\sum _{j=0}^{n-1} C_{ij}-R_{ij}$

Mean Squared Error (MSE) = ${\frac {1}{N^{2}}}\sum _{i=0}^{n-1}\sum _{j=0}^{n-1}(C_{ij}-R_{ij})^{2}$

여기서 N은 매크로 블록의 크기, $C_{ij}$ $C_{ij}$ ${\$ 와 $R_{ij}$ j ${\$ 은 각각 현재 매크로 블록과 참조 매크로 블록에서 비교되고 있는 픽셀이다 $R_{ij}$ .

기준 프레임에서 모션 벡터와 매크로 블록을 사용하여 생성된 모션 보정 영상은 피크 신호 대 잡음 비(PSNR)로 특징지어진다.

${\text{PSNR}}=10\log _{10}{\frac {({\text{peak to peak of original data}}})^{2}}{\text{MSE}}$

알고리즘

블록 매칭 알고리즘은 1980년대 중반부터 연구되어 왔다. 많은 알고리즘이 개발되었지만, 가장 기본적이거나 일반적으로 사용되는 몇몇 알고리즘만이 아래에 설명되어 있다.

철저한 검색

이 알고리즘은 검색창의 가능한 각 위치에서 비용 함수를 계산한다. 이를 통해 참조 프레임의 매크로 블록과 다른 프레임의 블록이 가장 잘 일치하게 된다. 결과적으로 동작 보정된 영상은 다른 블록 일치 알고리즘과 비교하여 피크 신호 대 잡음 비율이 가장 높다. 그러나 이것은 가장 계산적으로 광범위한 블록 매칭 알고리즘이다. 검색 창이 크면 더 많은 수의 계산이 필요하다.

최적화된 계층 블록 일치(OHBM)

최적화된 계층 블록 매칭(OHBM) 알고리즘은 최적화된 이미지 피라미드를 기반으로 철저한 검색 속도를 높인다.^[3]

3단계 검색

이것은 가장 초기 빠른 블록 매칭 알고리즘 중 하나이다. 다음과 같이 운영된다.

중앙의 검색 위치부터 시작
스텝 크기 S = 4 및 검색 매개 변수 p = 7 설정
위치(0,0) 및 위치(0,0) 주변의 8개 위치 +/- S 픽셀 검색
검색된 9개소 중 최소 비용 기능이 있는 곳을 선택하십시오.
새 검색 원점을 위에서 선택한 위치로 설정
새 스텝 크기를 S = S/2로 설정
S = 1까지 검색 절차를 반복하십시오.

S=1의 결과 위치는 최소 비용 함수가 있고 이 위치의 매크로 블록이 가장 잘 일치한다.

이 알고리즘에서는 9배수의 계산이 감소한다. p=7의 경우 ES가 225개의 매크로 블록에 대한 비용을 평가하는 반면 TSS는 25개의 매크로 블록에 대해서만 평가한다.

2차원 로그 검색

TDLS는 TSS와 밀접한 관련이 있지만 큰 검색 창 크기에 대한 모션 벡터 추정에 더 정확하다. 알고리즘은 다음과 같이 설명할 수 있다.

중앙의 검색 위치부터 시작
초기 단계 크기 선택(예: S = 8)
X 축과 Y 축의 중심에서 S의 거리에서 4개 위치 검색
최소 비용 함수로 포인트 위치 찾기
중앙 이외의 점이 가장 적합한 일치점이라면,
1. 이 점을 새 중앙으로 선택하십시오.
2. 2~3단계를 반복하십시오.
가장 적합한 일치점이 중심에 있는 경우 S = S/2를 설정하십시오.
S = 1일 경우, 거리 S에서 중앙 주변의 8개 위치를 모두 검색한다.
모션 벡터를 최소 비용 함수를 가진 점으로 설정

새로운 3단계 검색

TSS는 균일하게 할당된 점검 패턴을 사용하며 작은 움직임을 놓치기 쉽다. NTSS는 센터 편향 검색 체계를 제공하고 계산 비용을 줄이기 위해 중도에 중단해야 하는 조항이 있기 때문에 TSS보다 개선된 것이다. 이 알고리즘은 최초로 널리 인정된 고속 알고리즘 중 하나였으며 MPEG 1과 H.261과 같은 초기 표준을 구현하는 데 자주 사용되었다.

알고리즘은 다음과 같이 실행된다.

중앙의 검색 위치부터 시작
S = 4 및 8 위치 +/- S 픽셀 8개 위치 +/- S = 1 주변 위치(0,0) 검색
검색된 16개소 중 최소 비용 기능이 있는 곳을 선택하십시오.
최소 비용 함수가 원점에서 발생하는 경우 검색을 중지하고 모션 벡터를 (0,0)으로 설정하십시오.
최소 비용 함수가 S = 1의 8개 위치 중 하나에서 발생하는 경우 새 검색 원점을 이 위치로 설정하십시오.
1. 이 위치에 대한 인접 가중치를 점검하십시오. 위치에 따라 3점 또는 5점을 확인할 수 있음
가장 낮은 중량을 주는 것이 가장 가까운 일치점이며, 모션 벡터를 그 위치로 설정한다.
첫 번째 단계 이후 최저 중량이 S = 4의 8개 위치 중 하나일 경우, 일반적인 TSS 절차는 다음과 같다.
1. 검색된 9개소 중 최소 비용 기능이 있는 곳을 선택하십시오.
2. 새 검색 원점을 위에서 선택한 위치로 설정
3. 새 스텝 크기를 S = S/2로 설정
4. S = 1까지 검색 절차를 반복하십시오.

따라서 이 알고리즘은 매크로 블록마다 17개의 지점을 확인하고 최악의 경우 33개의 위치를 확인하는 것을 포함하는데, 이는 여전히 TSS보다 훨씬 빠르다.

간편하고 효율적인 검색

TSS의 이면에 있는 아이디어는 모든 매크로 블록에서 동작으로 인한 오류 표면이 단일하다는 것이다. 단일 표면은 비용 함수에 의해 생성되는 무게가 전지구적 최소치에서 단조롭게 증가하도록 그릇 모양의 표면을 말한다. 그러나 단일한 표면은 반대 방향으로 최소 두 개를 가질 수 없으므로 TSS의 8점 고정 패턴 검색은 이것을 통합하고 연산을 절약하도록 추가로 수정할 수 있다. SES는 이 가정을 통합한 TSS의 확장이다.

SES 알고리즘은 SES의 각 검색 단계가 두 단계로 나뉠 때 TSS 알고리즘을 기반으로 개선된다.

• 1단계 :

     • Divide the area of search in four quadrants      • Start search with three locations, one at center (A) and others (B and C), S=4 locations away from A in orthogonal directions      • Find points in search quadrant for second phase using the weight distribution for A, B, C:             • If (MAD(A)>=MAD(B) and MAD(A)>=MAD(C)), select points in second phase quadrant IV             • If (MAD(A)>=MAD(B) and MAD(A)<=MAD(C)), select points in second phase quadrant I             • If (MAD(A)<MAD(B) and MAD(A)<MAD(C)), select points in second phase quadrant II             • If (MAD(A)<MAD(B) and MAD(A)>=MAD(C)), select points in second phase quadrant III

• 2단계:

     • 무게가 가장 낮은 위치 찾기 • 위에서 찾은 지점으로 새 검색 원점 설정

• 새 단계 크기를 S = S/2로 설정

• S=1까지 SES 검색 절차를 반복한다.

• 동작 벡터 SES가 TSS에 비해 계산적으로 매우 효율적이기 때문에 무게가 가장 낮은 위치를 선택한다. 그러나 실제 오차 표면이 엄격히 비변형적이지 않기 때문에 TSS에 비해 최대 신호 대 잡음 비율은 낮다.

4단계 검색

Four Step Search는 낮은 계산 비용과 더 나은 최대 신호 대 잡음 비율 측면에서 TSS보다 개선된 것이다. 금감원은 NTS와 마찬가지로 센터 편향 검색도 채용하고 절반 정도 중단 조항이 있다.

알고리즘은 다음과 같이 실행된다.

중앙의 검색 위치부터 시작
스텝 사이즈 S = 2, (검색 파라미터 p와 관계 없이) 설정
위치(0,0) 주변의 8개 위치 +/- S 픽셀 검색
검색된 9개소 중 최소 비용 기능이 있는 곳을 선택하십시오.
검색 창 중앙에 최소 무게가 있는 경우:
1. 새 스텝 크기를 S = S/2(S = 1)로 설정하십시오.
2. 3단계부터 4단계까지 검색 절차를 반복하십시오.
3. 운동 벡터로 무게가 가장 적은 위치 선택
센터 이외의 8개 위치 중 하나에서 최소 중량이 발견되는 경우:
1. 새 원점을 이 위치로 설정
2. 스텝 크기를 S = 2로 고정
3. 3단계부터 4단계까지 검색 절차를 반복하십시오. 신규 출처 위치에 따라 5개소 또는 3개소를 검색하십시오.
4. 무게가 가장 적은 위치 선택
5. 최소 무게 위치가 새 창의 중앙에 있는 경우 5단계로 이동하거나 6단계로 이동하십시오.

다이아몬드 서치

다이아몬드 검색(DS)^[7] 알고리즘은 다이아몬드 검색 포인트 패턴을 사용하며 알고리즘은 4SS와 정확히 동일하게 실행된다. 다만 알고리즘이 취할 수 있는 단계 수에는 제한이 없다.

두 종류의 고정된 패턴이 검색에 사용된다.

LDSP(Large Diamond Search Pattern)
소형 다이아몬드 검색 패턴(SDSP)

알고리즘은 다음과 같이 실행된다.

LDSP:

1. 중앙의 검색 위치부터 시작
2. 스텝 크기 S = 2 설정
3. 다이아몬드 검색 지점 패턴을 사용하여 (X + Y =S) 위치(0,0) 주위에 8개 위치 픽셀(X,Y) 검색
4. 검색된 9개소 중 최소 비용 기능이 있는 곳을 선택하십시오.
5. 검색 창의 중앙에 최소 무게가 있는 경우 SDSP 단계로 이동하십시오.
6. 센터가 아닌 8개 위치 중 하나에서 최소 중량이 발견되면 새 원점을 이 위치로 설정하십시오.
7. LDSP 반복

SDSP:

1. 새 검색 원점 설정
2. 새 스텝 크기를 S = S/2(S = 1)로 설정하십시오.
3. 검색 절차를 반복하여 무게가 가장 적은 위치를 찾으십시오.
4. 운동 벡터로 무게가 가장 적은 위치 선택

이 알고리즘은 검색 패턴이 너무 크지도 작지도 않기 때문에 글로벌 최소값을 매우 정확하게 찾아낸다. Diamond Search 알고리즘은 Fervive Search에 근접한 피크 신호 대 잡음 비를 가지고 있으며 계산 비용이 현저히 적다.

적응형 루드 패턴 검색

적응형 rood 패턴 검색(ARPS) 알고리즘은 프레임의 일반적인 움직임이 대개 일관성이 있다는 사실을 활용한다. 즉, 현재 매크로 블록 주위의 매크로 블록이 특정 방향으로 이동했다면 현재 매크로 블록도 유사한 동작 벡터를 가질 가능성이 높다. 이 알고리즘은 매크로 블록의 동작 벡터를 그것의 바로 왼쪽에 사용하여 그 자체의 동작 벡터를 예측한다.

적응형 루드 패턴 검색은 다음과 같이 실행된다.

중앙의 검색 위치부터 시작(원본)
블럭에 대한 예측 모션 벡터 찾기
스텝 크기 S = 최대(X , Y ) 설정, 여기서 (X,Y)는 예측 동작 벡터의 좌표임
단계 크기 S에서 원점 주위에 루드 패턴 분산점 검색
최소 중량으로 점을 원점으로 설정
새 원점에서 작은 다이아몬드 검색 패턴(SDSP)을 사용하여 검색
SDSP 중심에 최소 가중치가 부여될 때까지 SDSP 검색을 반복하십시오.

루드 패턴 검색은 검색이 잘 맞는 블록을 찾을 가능성이 높은 영역에 직접 배치한다. DS 대비 ARPS의 주요 장점은 예측 동작 벡터가 (0, 0)일 경우 LDSP를 할 때 계산 시간을 낭비하지 않고 직접 SDSP를 사용하기 시작한다는 것이다. 더욱이, 예측된 동작 벡터가 중심에서 멀리 떨어져 있다면, 다시 말하지만, ARPS는 그 근처로 직접 뛰어들어 SDSP를 사용함으로써 연산을 절약하는 반면, DS는 LDSP를 하는 데 시간이 걸린다.

참조

^ Dabov, Kostadin; Foi, Alessandro; Katkovnik, Vladimir; Egiazarian, Karen (16 July 2007). "Image denoising by sparse 3D transform-domain collaborative filtering". IEEE Transactions on Image Processing. 16 (8): 2080–2095. Bibcode:2007ITIP...16.2080D. CiteSeerX 10.1.1.219.5398. doi:10.1109/TIP.2007.901238. PMID 17688213. S2CID 1475121.
^ Danielyan, Aram; Katkovnik, Vladimir; Egiazarian, Karen (30 June 2011). "BM3D Frames and Variational Image Deblurring". IEEE Transactions on Image Processing. 21 (4): 1715–28. arXiv:1106.6180. Bibcode:2012ITIP...21.1715D. doi:10.1109/TIP.2011.2176954. PMID 22128008. S2CID 11204616.
^ Je, Changsoo; Park, Hyung-Min (2013). "Optimized hierarchical block matching for fast and accurate image registration". Signal Processing: Image Communication. 28 (7): 779–791. doi:10.1016/j.image.2013.04.002.
^ Li, Renxiang; Zeng, Bing; Liou, Ming (August 1994). "A New Three-Step Search Algorithm for Block Motion Estimation". IEEE Trans. Circuits and Systems for Video Technology. 4 (4): 438–442. doi:10.1109/76.313138.
^ Lu, Jianhua; Liou, Ming (April 1997). "A Simple and Efficient Search Algorithm for Block-Matching Motion Estimation". IEEE Trans. Circuits and Systems for Video Technology. 7 (2): 429–433. doi:10.1109/76.564122.
^ Po, Lai-Man; Ma, Wing-Chung (June 1996). "A Novel Four-Step Search Algorithm for Fast Block Motion Estimation". IEEE Trans. Circuits and Systems for Video Technology. 6 (3): 313–317. doi:10.1109/76.499840.
^ Zhu, Shan; Ma, Kai-Kuang (February 2000). "A New Diamond Search Algorithm for Fast Block-Matching Motion Estimation". EEE Trans. Image Processing. 9 (12): 287–290. doi:10.1109/83.821744. PMID 18255398.
^ Nie, Yao; Ma, Kai-Kuang (December 2002). "Adaptive Rood Pattern Search for Fast Block-Matching Motion Estimation" (PDF). IEEE Trans. Image Processing. 11 (12): 1442–1448. doi:10.1109/TIP.2002.806251. PMID 18249712.

외부 링크

1. http://www.mathworks.com/matlabcentral/fileexchange/8761-block-matching-algorithms-for-motion-estimation

2. https://www.ece.cmu.edu/~ee899/프로젝트/deepak_mid.htm

[1] Dabov, Kostadin; Foi, Alessandro; Katkovnik, Vladimir; Egiazarian, Karen (16 July 2007). "Image denoising by sparse 3D transform-domain collaborative filtering". IEEE Transactions on Image Processing. 16 (8): 2080–2095. Bibcode:2007ITIP...16.2080D. CiteSeerX 10.1.1.219.5398. doi:10.1109/TIP.2007.901238. PMID 17688213. S2CID 1475121.

[2] Danielyan, Aram; Katkovnik, Vladimir; Egiazarian, Karen (30 June 2011). "BM3D Frames and Variational Image Deblurring". IEEE Transactions on Image Processing. 21 (4): 1715–28. arXiv:1106.6180. Bibcode:2012ITIP...21.1715D. doi:10.1109/TIP.2011.2176954. PMID 22128008. S2CID 11204616.

[Je_spic13_ohbm-3] Je, Changsoo; Park, Hyung-Min (2013). "Optimized hierarchical block matching for fast and accurate image registration". Signal Processing: Image Communication. 28 (7): 779–791. doi:10.1016/j.image.2013.04.002.

[tss-4] Li, Renxiang; Zeng, Bing; Liou, Ming (August 1994). "A New Three-Step Search Algorithm for Block Motion Estimation". IEEE Trans. Circuits and Systems for Video Technology. 4 (4): 438–442. doi:10.1109/76.313138.

[5] Lu, Jianhua; Liou, Ming (April 1997). "A Simple and Efficient Search Algorithm for Block-Matching Motion Estimation". IEEE Trans. Circuits and Systems for Video Technology. 7 (2): 429–433. doi:10.1109/76.564122.

[6] Po, Lai-Man; Ma, Wing-Chung (June 1996). "A Novel Four-Step Search Algorithm for Fast Block Motion Estimation". IEEE Trans. Circuits and Systems for Video Technology. 6 (3): 313–317. doi:10.1109/76.499840.

[7] Zhu, Shan; Ma, Kai-Kuang (February 2000). "A New Diamond Search Algorithm for Fast Block-Matching Motion Estimation". EEE Trans. Image Processing. 9 (12): 287–290. doi:10.1109/83.821744. PMID 18255398.

[8] Nie, Yao; Ma, Kai-Kuang (December 2002). "Adaptive Rood Pattern Search for Fast Block-Matching Motion Estimation" (PDF). IEEE Trans. Image Processing. 11 (12): 1442–1448. doi:10.1109/TIP.2002.806251. PMID 18249712.

[1]

[2]

[3]

[7]

Search

블록 매칭 알고리즘

네임스페이스

더

목차

동기

평가 메트릭

알고리즘

철저한 검색

최적화된 계층 블록 일치(OHBM)

3단계 검색

2차원 로그 검색

새로운 3단계 검색

간편하고 효율적인 검색

4단계 검색

다이아몬드 서치

적응형 루드 패턴 검색

참조

외부 링크