The main technical issue of low bit rate video communication is clearly the video coding method, which is required to achieve the necessary bit rate with sufficient image quality and reasonable hardware cost. Whereas most video coding standards uniquely define the bitstream syntax and the operation of the decoder, the exact nature of the encoder is generally left open to user specification. This implies that, given decoder configuration and bit rate, the quality of the encoded video depends on the strategy employed in the video encoder. Therefore, how to optimize the encoding algorithms effectively is the key factor deciding the value of the final product of the video codec system.
In this dissertation, we propose effective video encoding methods improving the overall quality of coded video in low bit rate coding. These include a motion estimation/compensation method and rate-distortion optimized video coding methods.
Overlapped block motion compensation(OBMC) has been proposed as a partial solution to the block artifact problems of conventional non-overlapped block motion compensation(BMC). OBMC has been shown to provide improved prediction efficiency as well as better subjective quality compared with BMC. Also, by using motion estimation techniques optimized for OBMC, called overlapped block motion estimation(OBME), we can obtain further substantial gains in compensation accuracy over conventional non-overlapped block motion estimation(BME).
In this dissertation, first, theoretical analysis on OBMC is presented. Previous studies have demonstrated that the performance of OBMC is better than that of BMC. However, most of them are extensively based on the exhaustive experiments using some test sequences. Due to this lack of theoretical study, the properties of OBMC have not yet been fully understood. In this work, we theoretically evaluate the performance of OBMC compared with BMC, based on the one-dimensional signal model characterized by the AR(1) process and first-order polynomial motion. We derived a condition under which the performance of OBMC is better than BMC, and an optimal window function for OBMC. The analysis explains various important properties of OBMC, some of which have been known experimentally.
Secondly, a novel motion estimation method for OBMC is proposed. Employing OBME with OBMC, we can get further substantial gains in compensation accuracy over BME. However, a lot of multiplication required for matching computation in OBME, prevent the practical realization of OBME. We propose a novel motion estimation method which significantly reduces the computational complexity of OBME. In order to eliminate computationally intensive multiplications of OBME, the proposed method uses a predetermined pattern in selecting matched pixels within a window support. By simulation, we show that our method achieves about the same prediction performance as the conventional approach with significant lower complexity.
Thirdly, we present an optimal approach for placement of resynchronization markers for video communication over noisy channels. In order to localize the spatially propagated bit errors, most of current video coding standards support the slice structure by which the flexible insertion of resynchronization markers into the coded video bitstream is possible. In the proposed method, we optimally decide the position of each marker, given the number of resynchronization markers assigned to the current frame. It takes into account the channel condition and the expected distortion at the decoder, and incorporates these informations into a rate-distortion framework. The Viterbi algorithm is employed to reduce the complexity of the rate-distortion optimization problem. Simulation results show that the proposed method outperforms the conventional ones for various bit error rates.
Finally, we propose a novel coding method that is based on adaptive truncation of zigzag scanned DCT coefficients in a rate-distortion sense. In the proposed method, high frequency coefficients ineffective in a rate-distortion sense are discarded and not coded to improve the overall performance of coded video. To reduce the complexity of the proposed method, we present a low-complexity rate-distortion computation method which recursively updates the rate-distortion cost of each coefficient. Tradeoff between the computational complexity and the coding performance is possible since the proposed rate-distortion computation method evaluate the cost function backward from high to low frequency coefficient. Simulation results show that the proposed coefficient truncation method consistently outperforms the conventional method, especially for very low bit rate cases.
저속 비트율 비디오 전송시 가장 중요한 것은 적당한 하드웨어 복잡도로 주어진 비트율에서 충분한 화질을 낼 수 있는 비디오 부호화 방법이다. 대부분의 비디오 부호화 표준이 부호화 시의 비트열 문법과 복호기의 기능을 정의하고 있지만, 부호기의 동작은 명확히 정의하고 있지 않다. 이것은 같은 비트율과 복호기에 대하여도 부호화 방법을 어떻게 사용하는 가에 따라 상당한 화질 차이가 나타날 수 있음을 의미한다. 그러므로, 어떻게 부호화 방법을 최적화하는 가는 최종적인 시스템의 가치를 결정하는 중요한 인자이다. 본 논문에서는 부호기의 성능을 향상시킬 수 있는 효과적인 부호화 방법들로, 움직임 추정/보상 방법 및 율-왜곡 기반의 최적화 기반 부호화 방법들을 제안한다.
중첩 블록 움직임 보상 방식은 기존의 비중첩 방식에서 나타나는 블록 경계 효과 현상을 감소시키기 위해 제안되어졌다. 이 방식이 주관적 및 객관적 화질면에서 비중첩 방식에 비해 우수함이 여러 실험들을 통하여 입증된 바 있다. 또한, 움직임 추정 시에 중첩 블록 움직임 추정 방법을 사용함으로써 비중첩 추정 방법을 사용하는 경우에 비하여 더욱 높은 예측 이득을 얻을 수 있음이 잘 알려져 있다.
본 논문에서는 우선, 중첩 블록 움직임 보상 방식의 이론적인 성능 분석을 시도한다. 기존의 많은 연구들이 중첩 블록 움직임 보상 방식의 우수성을 보여왔으나, 대부분의 결과들은 몇몇 영상들을 이용한 실험적인 결과에 바탕을 두고 있다. 이러한 이론적인 연구의 부족은 중첩 블록 움직임 보상 방식이 가진 여러 가지 특성들의 이해를 어렵게 하고 있다. 본 논문에서는 중첩 방식과 비중첩 방식의 성능을 이론적으로 비교 고찰한다. 분석을 통하여 객관적 및 주관적 화질면에서의 중첩 방식의 우수성을 보이며, 중첩 방식이 가지고 있는 여러 가지 특성들을 이론적으로 검증한다.
두번째로, 중첩 블록 움직임 보상 방식을 위한 새로운 움직임 추정 방법을 제안한다. 중첩 블록 움직임 보상 방식의 움직임 추정 방법으로 중첩 블록 움직임 추정 방법을 이용함으로써 상당한 추가적인 예측 이득을 얻을 수 있음이 잘 알려져 있다. 그러나, 이 방법은 탐색에서의 정합 계산 시에 많은 곱셈 연산을 필요로 하며, 이로 인해 실제 구현을 위해서는 상당히 높은 복잡도를 요구한다. 제안 방법은 곱셈 연산을 효과적으로 제거함으로써 복잡도를 현저히 줄인다. 곱셈 연산을 없애기 위하여 제안 방법은 윈도우 내의 정합 화소를 선택하는 데에 윈도우에 적응적으로 미리 구해진 패턴을 이용한다. 이 패턴은 선택된 화소의 밀도가 윈도우의 가중치값에 근사적으로 비례하게 함으로써 곱셈 연산의 효과를 반영한다. 실험을 통하여 제안 방법이 기존의 방법에 비하여 현저히 낮은 복잡도를 가지면서 사실상 동일한 예측 성능을 얻음을 보인다.
세번째로, 잡음이 있는 채널을 통하여 비디오를 전송할 때에 발생하는 비트 오류의 영향을 감소시키기 위한 재동기 마커의 최적 배치 방법을 제안한다. 제안 방법은 현재 화면에 할당된 재동기 마커들을 율-왜곡 관점에서 최적으로 영상 내에 배치한다. 율-왜곡 계산에는 채널의 오류율과 복호기에서 기대되는 재생 왜곡을 반영함으로써 주어진 환경에 최적인 위치가 결정된다. 계산시의 지수형 복잡도를 선형 복잡도로 만들기 위하여 Viterbi 알고리듬이 사용된다. 실험 결과, 제안 방법은 기존의 재동기 마커 배치 방법들에 비해 상당히 우수한 화질 개선 효과를 가져왔다.
마지막으로, 율-왜곡 관점에서 최적인 적응적 DCT 계수 제거 방법을 제안한다. 제안 방법은 율-왜곡 관점에서 효율적이지 못한 양자화된 고주파 계수들을 지그재그 주사 순서로 부호화하지 않음으로써 전체적인 화질의 향상을 얻는다. 율-왜곡 계산시의 복잡도를 감소시키기 위하여 DCT 영역에서의 재귀적인 율-왜곡 계산 방법을 제안한다. 고주파 계수에서 저주파 계수의 순으로 역방향으로 계산을 하며, 이전 계수의 율-왜곡 값을 이용하여 현재 계수의 값을 재귀적으로 계산함으로써 중복 계산을 최소화한다. 역방향 계산은 복잡도와 성능 향상의 교환 (tradeoff)을 가능하게 한다. 실험 결과, 제안 방법이 기존의 방법에 비하여 일관되게 우수한 성능을 보이며, 특히 초저속 비트율 부호화시에 뚜렷한 성능 개선을 보였다.
