[논문]매크로블록 간 움직임유사도를 이용한 고속 PDE 알고리즘

유태경; 정용재; 문광석; 김종남

매크로블록 간 움직임유사도를 이용한 고속 PDE 알고리즘
A Fast Partial Distortion Elimination Algorithm Using Motion Similarity of Macro-blocks 원문보기

유태경 (부경대학교) , 정용재 (부경대학교) , 문광석 (부경대학교) , 김종남 (부경대학교)

본 논문에서는 인접블록간의 움직임 유사도를 이용하여 불필요한 후보블록을 보다 빠르게 제거하는 PDE기반의 고속 블록매칭 알고리즘을 제안한다. 제안한 방법은 기존의 방법보다 불필요한 계수를 효율적으로 제거하기 위하여 인접 블록간의 영상의 유사성에 기초하여 네 개의 인접 매크로블록 가운데 최대 복잡도를 가지는 서브블록의 누적 분포 함수(cumulative distribution function-CDF)와 서브블록별 복잡도가 집중되지 않도록 하기위하여 normalized스캔 방법에 사용하여 효율적으로 계산량을 감소하였다. 제안한 알고리즘은 화질의 저하 없이 기존의 PDE 알고리즘에 비해 55% 이상의 계산량을 줄였으며, MPEG-2 및 MPEG-4 AVC를 이용하는 비디오 압축 응용분야에 유용하게 사용될 수 있을 것이다.

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

문제 정의

본 논문에서는 기존의 PDE기반의 블록매칭 알고리즘의 계산량을 줄이고 동시에 동일한 예측화질을 얻기 위해, 단일프레임 내에서 매크로 블록간의 움직임 유사도를 이용한 개선된 서브블록 매칭스캔 알고리즘을 제안하였다. 기존의 PDE 방법을 개선하기 위하여 인접 매크로블록의 각 서브블록별 CDF를 고려하여 최소 SAD값에 적용하여 후보블록을 서브 블록 단위로 효율적으로 제거하고 예측화질의 손실을 줄이기 위하여 서브블록당 복잡도를 줄이는 noramlaized 스캔 방법을 사용하여 전역 탐색방법과 거의 유사한 PSNR을 유지하면서 효율적으로 불필요한 계산량을 줄였다.
본 논문에서는 기존의 무손실 기반 움직임 추정방법인 PDE 알고리즘의 계산량을 보다 많이 줄이기 위하여 PDE기반으로 인접한 매크로블록과의 유사도를 고려하여 서브블록의 누적비율(cumulative distribution function- CDF)[7]을 고려하여 최소 SAD값에 적용하고 서브블록별로 보다 균일한 오차값을 적용하기 위하여 normalized 스캔방법의 초기 오차 보정을 통하여 보다 빠르게 후보블록을 제거하는 고속 PDE알고리즘을 제안한다. 제안한 방법을 고속 움직임 추정 방법에 적용하여 보다 빠른 움직임 추정이 가능하다.

제안 방법

본 논문에서는 기존의 PDE기반의 블록매칭 알고리즘의 계산량을 줄이고 동시에 동일한 예측화질을 얻기 위해, 단일프레임 내에서 매크로 블록간의 움직임 유사도를 이용한 개선된 서브블록 매칭스캔 알고리즘을 제안하였다. 기존의 PDE 방법을 개선하기 위하여 인접 매크로블록의 각 서브블록별 CDF를 고려하여 최소 SAD값에 적용하여 후보블록을 서브 블록 단위로 효율적으로 제거하고 예측화질의 손실을 줄이기 위하여 서브블록당 복잡도를 줄이는 noramlaized 스캔 방법을 사용하여 전역 탐색방법과 거의 유사한 PSNR을 유지하면서 효율적으로 불필요한 계산량을 줄였다. 제안한 알고리즘은 화질의 저하 없이 기존의 PDE 알고리즘에 비해 55% 이상의 계산량을 줄였으며, MPEG-2 및 MPEG-4 AVC를 이용하는 비디오 압축 응용분야에 유용하게 사용될 수 있을 것이다.
제안한 방법은 단일 프레임 내에서 인접한 매크로 블록간에는 움직임의 유사성이 존재한다는 것을 고려하였다. 따라서 그림 1과 같이 하나의 프레임 영상에서 인접한 4개의 매크로블록간의 유사성을 고려하여 참조 매크로블록을 위치에 따라4가지 종류의 참조 블록형태(UpperLeft,UpperRight, Upper, Left)로 구성하고 각 참조블록의 복잡도를 참조하여 현재 후보블록을 적응적으로 제거한다. 우선 참조블록으로 사용되는 매크로블록의 움직임 추정의 경우 기존의 복잡도 기반 움직임 추정방법으로 최소SAD값을 가지는 후보점의 서브블록별 복잡도를 기준으로 서브블록 매칭순서를 구하여 무손실 움직임 추정방법을 수행한다.
서브블록의 크기는 4×4 크기를 갖는 형태로 서브블록에서 각각 하나의 픽셀을 가져오는 normalized 방법을 개선한 방법을 사용하였다.
정적인 영상의 경우는 거의 움직임이 없는 경우도 있다. 이러한 비디오영상의 특성을 제대로 고려하기 위하여 매칭 스캔 순서를 정하는 방법으로 나선형 스캔(spiral scan)을 적용하여 최소 SAD값이 우선적으로 나올 수 있도록 고려하였다. 기존의 PDE방법의 계산량 감소를 위해서는 NPDS 방법에서 사용하였던 서브 블록과 SADmin값의 서브블록별 부분 값을 비교하여 계산량 감소를 이룰 수 있었다.
제안한 방법은 단일 프레임 내에서 인접한 매크로 블록간에는 움직임의 유사성이 존재한다는 것을 고려하였다. 따라서 그림 1과 같이 하나의 프레임 영상에서 인접한 4개의 매크로블록간의 유사성을 고려하여 참조 매크로블록을 위치에 따라4가지 종류의 참조 블록형태(UpperLeft,UpperRight, Upper, Left)로 구성하고 각 참조블록의 복잡도를 참조하여 현재 후보블록을 적응적으로 제거한다.
이러한 복잡도의 집중은 NPDS 기반 방법에서의 예측화질 손실의 원인이 된다. 제안한 방법은 이러한 서브블록별 복잡도를 각 서브블록별로 고르게 분포하도록 하기 위하여 normalized 스캔방법을 적용하여 서브블록 매칭시 CDF값이 하나의 서브블록에 모여 원하지 않는 후보블록이 제거되지 않도록 normalized 방법에 디더링 방법을 적용하고 최초 서브블록의 복잡도를 기반하여 서브블록의 매칭순서를 정하였다. 초기 매칭 블록의 오차를 고려하여 제안한 방법은 초기 매칭 시 발생하는 오차를 보정할 수 있는 계수 값(α=1/32)을 더하였다.
본 논문에서는 기존의 무손실 기반 움직임 추정방법인 PDE 알고리즘의 계산량을 보다 많이 줄이기 위하여 PDE기반으로 인접한 매크로블록과의 유사도를 고려하여 서브블록의 누적비율(cumulative distribution function- CDF)[7]을 고려하여 최소 SAD값에 적용하고 서브블록별로 보다 균일한 오차값을 적용하기 위하여 normalized 스캔방법의 초기 오차 보정을 통하여 보다 빠르게 후보블록을 제거하는 고속 PDE알고리즘을 제안한다. 제안한 방법을 고속 움직임 추정 방법에 적용하여 보다 빠른 움직임 추정이 가능하다.
제안한 알고리즘과 기존의 알고리즘의 성능을 비교하기 위해, "foreman", "car phone", "trevor","claire", "grandmother"의 비디오 시퀀스를 실험하였다.
초기 매칭 블록의 오차를 고려하여 제안한 방법은 초기 매칭 시 발생하는 오차를 보정할 수 있는 계수 값(α=1/32)을 더하였다.

데이터처리

프레임의 크기는QCIF(176×144)이다. 실험 결과는 계산된 평균 행의 수와 PSNR로 나타내었다. 계산된 평균 행의 수는 하나의 스캔 블록에서 계산 되는 평균 행의 수치이다.

성능/효과

이러한 비디오영상의 특성을 제대로 고려하기 위하여 매칭 스캔 순서를 정하는 방법으로 나선형 스캔(spiral scan)을 적용하여 최소 SAD값이 우선적으로 나올 수 있도록 고려하였다. 기존의 PDE방법의 계산량 감소를 위해서는 NPDS 방법에서 사용하였던 서브 블록과 SADmin값의 서브블록별 부분 값을 비교하여 계산량 감소를 이룰 수 있었다. 하지만 NPDS방법의 경우 서브블록의 오차값이 SADmin값의 부분 값 보다 커지는 상황이 발생하여 예측 화질의 손실이 발생한다.
제안한 방법은 전역탐색 방법과 비교하여 영상의품질의 차이가 거의 없었다. 따라서 본 논문에서는 계산의 복잡도를 제거하기위하여 참조 서브블록과 현재 서브블록간의 SAD_min값과의 CDF를 이용하여 블록별로 적응적 임계치를 구하여 화질의 감소 없이 우수한 계산량의 감소를 얻을 수 있었다.
이 차이는 제안한 방법을 적용하였을 경우 발생하는 오차의 정도이다. 제안한 방법은 전역탐색 방법과 비교하여 영상의품질의 차이가 거의 없었다. 따라서 본 논문에서는 계산의 복잡도를 제거하기위하여 참조 서브블록과 현재 서브블록간의 SAD_min값과의 CDF를 이용하여 블록별로 적응적 임계치를 구하여 화질의 감소 없이 우수한 계산량의 감소를 얻을 수 있었다.
그림2는 10fps "foreman"영상에서 각 방법별 영상 시퀀스에서 서브 블록에 대해 다양한 방법으로 실험된 순차적 매칭 스캔과 제안한 방법을 사용하여 계산된 평균 행의 수를 보여 준다. 제안한 방법을 적용하면 각 후보 블록별로 종래의 순차적인 방법에 비해 매칭 에러를 계산하는데 있어 서브 블록 당 매칭에러 비교를 적용했을 때 불필요한 계산을 현저히 줄였다.
기존의 PDE 방법을 개선하기 위하여 인접 매크로블록의 각 서브블록별 CDF를 고려하여 최소 SAD값에 적용하여 후보블록을 서브 블록 단위로 효율적으로 제거하고 예측화질의 손실을 줄이기 위하여 서브블록당 복잡도를 줄이는 noramlaized 스캔 방법을 사용하여 전역 탐색방법과 거의 유사한 PSNR을 유지하면서 효율적으로 불필요한 계산량을 줄였다. 제안한 알고리즘은 화질의 저하 없이 기존의 PDE 알고리즘에 비해 55% 이상의 계산량을 줄였으며, MPEG-2 및 MPEG-4 AVC를 이용하는 비디오 압축 응용분야에 유용하게 사용될 수 있을 것이다.
표 1에서 30fps의 경우 제안한 알고리즘은 기존의 PDE알고리즘보다 50∼63%의 계산량 감소를 보였다.
표 1에서 30fps의 경우 제안한 알고리즘은 기존의 PDE알고리즘보다 50∼63%의 계산량 감소를 보였다. 표 2의 경우 제안한 알고리즘을 10fps의 영상에 적용하면 53～65%의 계산량 감소를 나타냄을 알수 있었다.

핵심어

질문

논문에서 추출한 답변

PDE알고리즘은 무엇인가?

PDE알고리즘은 후보 블록의 부분 매칭 에러를 가지고 최소 에러와 비교함으로써 불필요한 계산을 줄이는 것이다. 즉, 매칭 에러의 중간 합이 그때까지의 최소 에러보다 크다면 나머지 계산을 할 필요가 없다는 것이다. 식 (1)은 일반적인 PDE에서 사용되는 SAD값의 행별 부분비교를 나타낸 것이다.

NPDS 방법에서 예측 화질의 손실이 발생한 이유는 무엇인가?

기존의 PDE방법의 계산량 감소를 위해서는 NPDS 방법에서 사용하였던 서브 블록과 SADmin값의 서브블록별 부분 값을 비교하여 계산량 감소를 이룰 수 있었다. 하지만 NPDS방법의 경우 서브블록의 오차값이 SADmin값의 부분 값 보다 커지는 상황이 발생하여 예측 화질의 손실이 발생한다. 이러한 예측화질의 손실을 막고 계산량 감소를 이루기 위해서는 새로운 매칭 스캔 방법이 필요하다.

무손실 움직임 추정 방법의 단점은 무엇인가?

무손실 움직임 추정 방법의 경우 손실 방법에 비해 계산량의 감소가 적은 단점을 가지고 있다. 이런 계산량 감소의 단점을 해결하기 위하여 예측화질의 손실을 일부 감수하더라도 계산량 감소를 이루려는 연구들이 진행되었다.

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증

매크로블록 간 움직임유사도를 이용한 고속 PDE 알고리즘
A Fast Partial Distortion Elimination Algorithm Using Motion Similarity of Macro-blocks 원문보기

초록
AI-Helper

AI 본문요약
AI-Helper

문제 정의

제안 방법

데이터처리

성능/효과

질의응답

이 논문을 인용한 문헌

관련 콘텐츠

원문 보기

이 논문과 함께 이용한 콘텐츠

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

선택된 텍스트

연합인증

매크로블록 간 움직임유사도를 이용한 고속 PDE 알고리즘 A Fast Partial Distortion Elimination Algorithm Using Motion Similarity of Macro-blocks 원문보기

초록 용어보기논문에서 용어와 풀이말을 자동 추출한 결과로, 시범 서비스 중입니다. AI-Helper

AI 본문요약 엑셀 다운로드 AI-Helper

문제 정의

제안 방법

데이터처리

성능/효과

질의응답

이 논문을 인용한 문헌

관련 콘텐츠

원문 보기

이 논문과 함께 이용한 콘텐츠

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

선택된 텍스트

매크로블록 간 움직임유사도를 이용한 고속 PDE 알고리즘
A Fast Partial Distortion Elimination Algorithm Using Motion Similarity of Macro-blocks 원문보기

초록
AI-Helper

AI 본문요약
AI-Helper