본 논문에서는 CDS(Cross-Diamond Search algorithm) 및 CDHSs(Cross-Diamond-Hexagonal Search algorithms)의 성능을 향상시키기 위하여 탐색 영역의 위치에 따라 최적의 탐색 형태를 적용하는 CDTS(Cross-Diamond-Triangle Search algorithm)를 제안한다. CDTS에서 탐색 영역의 위치에 따라 최적의 탐색 형태를 적용하기 위하여 다양한 실험 영상들의 움직임 분포를 먼저 분석하였다. 분석된 움직임 분포에 근거하여 CDTS 구현 시 탐색 영역 중심부에서는 십자 탐색 형태와 다이아몬드 탐색 형태를 적용하고, 나머지 탐색 영역에서는 삼각 탐색 형태와 다이아몬드 탐색 형태를 적용한다. CDTS에서 제안하는 삼각 탐색 형태는 기존 탐색 알고리즘에서 사용하는 대칭형 구조와는 다르게 비대칭형 구조를 가지고 탐색점을 더욱 감소시키는 효과를 제공하면서도 화질을 유지할 수 있다. CDTS를 CDS 및 CDHSs와 비교하였을 때 화질 열화 없이 각각 평균 16.22$\%$ 및 3.09$\%$ 정도의 탐색점 감소 효과가 나타났다.
In this Paper, we propose a new motion search algorithm called CDTS (Cross-Diamond-Triangle Search algorithm) that uses optimal search pattern according to the position of a search area to improve the performance of CDS(Cross-Diamond Search algorithm) as well as CDHSs(Cross-Diamond-Hexagonal Searches algorithms). We analyze motion distributions in various test video sequences to apply optimal search pattern according to a position of search area. Based on the result of this analysis, we propose a new triangle-shaped search pattern whose structure is asymmetric while previous search patterns are generally symmetric in conventional algorithms. In CDTS, we apply cross- and diamond-shaped search patterns to central search areas, and triangle- and diamond-shaped patterns to the other areas. Applying CDTS to test video sequences, the proposed scheme can reduce search points more than CDS and CDHSs by 16.22$\%$ and 3.09$\%$, respectively, without any visual quality degradation.
