디인터레이싱을 위한 방향지향 보간법의 개선

Improvement of Direction-Oriented Interpolation for Deinterlacing

  • cc icon
  • ABSTRACT

    본 논문은 DOI방법을 개선한 디인터레이싱 방법을 제안한다. DOI방법은 강력한 인트라필드 기반의 디인터레이싱 기술이지만 긴 연산시간과 주기적인 패턴에서 방향을 잘못 찾는 문제를 가지고 있다. 이 문제를 해결하기 위해 기존의 전역검색 대신하여 2단계 검색을 하여 연산속도를 향상시키고 두 가지 과정을 추가하여 영상의 화질을 개선하는 방법을 제안한다. 첫 번째 단계로 잘못된 방향으로 찾은 공간벡터를 삭제하며 두 번째 단계로 찾지 못한 방향에 대한 공간 방향벡터를 삽입함으로써 제안된 방법에서 잘못 찾은 공간 방향벡터를 정확한 결과인지 재확인하여 픽셀의 보간에 사용할지 검사한다. ISO 실험 이미지를 이용하여 제안된 방법과 line evarage, edge-based line averaging, DOI, selective deinterlacing algorithm 등의 기존의 방법을 비교한 결과 제안된 방법이 객관적으로나 주관적으로 우 수하다는 것을 보였다.


    This paper presents, a deinterlacing method by improving the Direction-Oriented Interpolation (DOI) technique. The technique is considered to be a very strong tool for intrafield-based deinterlacing. However, DOI has some problems such as long processing time, wrong edge detection in periodic pattern. To remedy this problem, we replace the full search in DOI by a two-step search to reduce processing time and introduces two additional processes to improve image quality. In the proposed method, the spatial direction vectors (SDVs) misread data are reconsidered to prevent them utilizing in the next interpolation step, resulting in an accurate deinterlacing method. We conduct experiments with ISO experimental images to compare the proposed method with the existing methods including line evarage (LA), edge-based line averaging (ELA), DOI, selective deinterlacing algorithm (SDA). Experimental results show the proposed method gives better performance in objective and subjective quality than existing deinterlacing methods.

  • KEYWORD

    디인터레이싱 , 방향 기반 보간법 , 방향 벡터

  • Ⅰ. 서 론

    비월 주사(interace scanning)방식은 지금은 사라지고 있는 아날로그 TV 방송에서부터 중요한 역할을 한 기술이며, 디지털 TV의 시대인 오늘날에도 대역폭을 절감하기 위해 여전히 사용되는 기술이다[1-14].

    디인터레이싱은 비월 주사 필드에서 비어있는 영상 화소 데이터를 주변의 화소를 이용하여 온전한 하나의 프레임으로 만드는 것이다. 이를 위해서 일반적인 영상 보간법[15-18]을 기반으로 구현할 수 있으나 일반적으로 디인터레이싱 특징에 맞는 방향으로 접근한다. 디인터레이싱은 참조하는 필드 수에 따라 두 가지 방법으로 구분되는데 인트라필드(intra-field)방식과 인터필드 (inter-field)방식이다. 인트라필드 기반의 디인터레이싱은 단 한 장의 필드의 정보를 이용하여 순차 주사로 인해 사라진 라인을 보간하는 방법이다. 반면에 인터필드 방식은 2장 이상의 필드의 정보를 이용하여 없어진 라인을 보간하는 방법이다. 일반적으로 시간 영역 보간 방법은 공간 영역 보간 방법을 기반으로 이루어지기 때문에 공간 영역 보간 방식에 비해 더 복잡하다. 따라서 공간 영역 보간 방법은 여전히 개선할 필요가 있다.

    인트라필드 기반의 디인터레이싱 방법 중 가장 잘 알려진 방법은 복구할 라인의 두 인접한 라인을 이용해 방향을 추측하는 방법인 ELA(edge-based line averaging)[1]이다. 이 방법은 수직방향과 45⁰, 135⁰ 방향의 에지를 찾아내어 보간하는 방법으로, 에지의 방향을 정확히 찾아내었을 경우 화질의 개선 효과를 볼 수 있으나, 라인 샘플을 취하는 과정에서 에일리어싱 현상이 발생한다. 특히 이는 고주파 영역에서 에지의 방향을 제대로 찾아내지 못하여 영상의 화질을 저하 시킨다.이 문제를 해결하고 ELA를 개선하기 위하여 여러 가지 방법이 제안되었다[2-4,14]. 이 중 넓은 검색범위를 이용해 가장 수평에 가까운 에지를 복원하여 강력한 성능을 보이는 방법으로 DOI(direction-oriented interpolation)가 제안되었다[5]. DOI는 기존의 방법에 비해 화질은 크게 개선되었으나 기본적으로 블록 매칭 기반의 방법이기 때문에 연산속도가 상당히 느리다는 단점을 가지며, 넓은 검색 범위로 인하여 같은 패턴이 반복되는 영역에서 에지 방향을 잘 찾지 못하여 부분적인 화질의 저하를 확인할 수 있다. 그럼에도 불구하고 DOI는 현존하는 디인터레이싱 방법 중 가장 수평에 가까운 에지의 방향까지도 예측할 수 있다는 장점 때문에 이런 DOI의 장점을 유지하며 단점을 보완하는 방법이 지속적으로 제안되어 왔다. 여러 방법 중 효과적으로 DOI의 단점을 보완한 방법으로 MELA(modified edge-based line averaging)[3]와 DOI를 활용한 방법인 SDA(selective deinterlacing algorithm)가 제안되었으나, 기존의 DOI보다 연산량이 더 많아 연산속도의 개선이 이루어지지 않았다.

    Ⅱ. Direction-Oriented Interpolation

    DOI는 각 픽셀의 보간을 위해 픽셀간의 방향의 상관도를 계산한다. DOI는 기존의 방법보다 보간될 픽셀의 에지 방향을 예측하는 데 있어 더 정확히 방향을 예측할 수 있도록 공간 방향 벡터 SDVs(spatial direction vectors)를 도입한다. DOI는 방향을 예측하기 위해 위와 아래의 각각 2줄의 참조선을 이동하며 크기가 3×2인 블록을 사용하여 그림 1과 같이 블록 매칭을 한다. 보간될 픽셀의 방향은 보간될 픽셀의 블록과 위와 아래의 각각 참조선의 블록사이의 MSE(mean square error)값에 의해 결정된다. 이때 위 참조선의 공간 방향벡터 USDV(upper spatial direction vector)와 아래 참조선의 공간 방향벡터 LSDV(lower spatial direction vector)는 그림 1과 같이 위와 아래의 참조선에서 얻을 수 있다.

    DOI는 두 벡터를 이용하여 에지의 방향을 예측한다. 그림 1U0, U1, L0, L1은 각각 위와 아래의 참조선을 나타내고 X는 보간되는 라인을 나타낸다. SDVs를 찾기 위해 (1), (2)식을 사용한다.

    image
    image

    식 (1), (2)을 통해 검색 범위가 R일 때 위와 아래의 공간 방향벡터를 구하기 위해 각각 (3), (4)식을 사용한다.

    image
    image

    최종적으로 X(i)를 보간하는 식은 아래 식 (5)와 같다.

    image

    DOI는 보간할 때 위의 식을 사용하여 보간한다. 식 (5)에서 참조선 픽셀의 위치iU, iL이 정수가 아닐 경우 수평방향의 보간법을 이용하여 얻는다.

    DOI는 그림 2와 같이 위와 아래의 참조선 중에서 U0(i), L0(i)의 차이의 값을 임계값 T와 비교한다. 이 차이의 값이 임계값 T보다 작으면 X(i)는 LA를 하게 된다. 차이의 값이 T보다 클 경우 위와 아래의 각각 참조선에서 보간될 픽셀의 블록과의 블록 매칭을 통해 최소의 차이를 가지는 공간 방향벡터를 찾는다. 위와 아래의 두 공간 방향벡터의 인덱스 차이의 합이 1보다 크면 X(i)는 에지의 방향이 없다고 판단하여 LA를 하게 되며 차이의 합이 1보다 작거나 같으면 위 (5)식을 이용하여 X(i)를 보간한다. DOI는 에지의 방향을 기존의 방법들 보다 더 정확하게 찾아내며 수평에 가까운 에지도 찾아낼 수 있어 다른 방법들과 비교했을 때 주관적으로나 객관적으로 더 좋은 영상의 결과를 보여준다. 하지만 패턴이 반복되는 부분이나 여러 에지가 얽혀있는 부분에서 방향을 잘못 판단하는 경우가 생겨 보간 성능을 떨어뜨린다.

    Ⅲ. 제안하는 방법

    기존의 DOI는 수평에 가까운 에지의 방향까지도 찾아낼 수 있다. 하지만 연산시간이 오래 걸리며 특정 부분에서 방향을 잘못 보간하는 문제점을 가지고 있다. 이러한 문제점을 해결하기 위해, 본 논문에서는 기존의 DOI를 개선하여 각 픽셀의 에지 정보인 공간 방향벡터 (SDVs)를 찾는 방법을 기존의 전역 검색(full search)방법을 개선하여 그림 3과 같이 2단계 검색(two-step search)후 2가지 과정을 추가한 방법을 제안한다. 그림 2의 DOI 방법과는 달리 공간 방향벡터를 모든 픽셀을 이용해서 찾는 대신 3픽셀마다 계산하여 찾아낸다. 이 결과는 모든 픽셀을 볼 때보다 부정확하기 때문에 대략적인 에지의 방향만을 알 수 있다. 화질 개선을 위하여 주변의 방향과 전혀 다른 방향으로 찾은 공간 방향벡터는 잘못된 방향벡터임으로 삭제를 하고, 방향이 없어 수직 방향으로 보간을 해야 하는 픽셀의 주변이 모두 같은 방향의 공간 방향벡터라면 찾지 못한 공간 방향벡터이므로 삽입을 해준다.

       3.1. 2단계 검색

    기존의 DOI방법에서는 공간 방향벡터를 찾기 위해 블록 매칭을 한다. 기존의 DOI에서의 블록 매칭은 검색 범위가 R일 때 −R부터 R까지의 블록을 모두 매칭하는 방식이었으나 제안하는 방법의 블록 매칭은 첫 번째 단계로 3번째 블록마다 매칭을 한다. 첫 번째 단계의 식은 위의 식 (1) ,(2)과 같으며, 식 (1), (2)을 통해 검색 범위가 R일 때 위와 아래의 공간 방향벡터를 구하기 위해 각각 (6), (7)식을 사용한다. 여기서 찾은 공간 방향벡터는 전체를 검색하는 것이 아니기 때문에 대략적인 에지의 방향만을 알 수 있다.

    image
    image

    두 번째 단계는 첫 번째 검색에서 찾은 sdvUsdvL을 이용하여 검색된 공간 방향벡터 주변의 블록을 매칭하여 공간 방향벡터 값을 최종적으로 설정하는 단계이다. 첫 번째 검색에서 나온 블록과 양옆의 블록을 각각 현재 보간할 픽셀의 블록과 MSE값 비교를 통해 최종적으로 공간 방향벡터를 설정한다. i가 첫 번째 검색에서 나온 공간방향벡터의 인덱스일 때 두 번째 단계에서 공간 방향벡터 식은 아래 식 (8), (9)과 같다.

    image
    image

    2단계로 공간 방향벡터를 찾는 방법을 개선함으로서 기존의 전역 검색에 비하여 검색시간이 상당히 줄어든다. 기존의 DOI와 동일한 검색범위인 16을 사용하였을 때 이론적으로 기존의 DOI에 비하여 절반 이하의 검색시간이 소요된다.

       3.2. 잘못된 방향으로 찾은 공간 방향벡터 삭제

    위에서 찾은 2단계 검색 방법은 기존의 DOI에 비하여 연산속도는 상당히 향상되었으나 여전히 간혹 잘못된 방향 정보로 계산되는 경우가 발생한다. 이 경우는 보통 주변 픽셀은 에지의 방향이 잘 예측하였으나 잡음이 나타난 픽셀이 홀로 전혀 다른 방향으로 에지의 방향을 잘못 잡는 경우이다. 이로 인하여 주관적 화질을 저하된다. 따라서 이 단계에서는 홀로 잘못된 방향의 정보를 가지고 있는 픽셀의 방향 정보를 제거하여 영상의 화질을 향상시킨다. X(i)가 i번째 픽셀일 때 잘못된 방향정보를 제거하는 방법은 그림 4와 같다.

    현재위치 i에서 픽셀의 공간 방향벡터가 있고, 주변 픽셀인 i−1, i−2, i+1, i+2번째 픽셀은 공간 방향벡터가 없을 때 방향을 잘못 찾은 것이라고 가정하고 현재 위치의 공간 방향벡터를 지우고 에지의 방향이 없는 것으로 재설정한다. 즉, 현재의 위치를 중심으로 좌우의 방향벡터와의 상관성을 고려하여 현재 위치에서의 에지의 방향이 있을 때 주변의 에지의 방향이 없다면 현재 에지 방향정보는 주변의 정보와 다르다는 것을 추측할 수 있다. 이런 공간 방향벡터를 제거하고 수직 방향으로 보간한다. 이로 인해 드물게 생기는 부정확한 방향 예측으로 인한 잡음을 제거할 수 있다.

       3.3. 찾지 못한 방향에 대한 공간 방향벡터 삽입

    앞서 설명한 과정을 통해서 결과적으로 드물게 생기는 부정확한 예측으로 인한 잡음을 없애 주관적인 화질을 향상시킨다. 하지만 위의 경우와는 반대로 2단계 검색하기 때문에 영상의 에지에 대한 방향을 제대로 찾지 못하는 경우가 발생하여 에지가 중간에 끊어지는 경우가 생긴다. 이 문제를 해결하기 위해 에지 정보를 방향을 찾지 못한 부분 중 적당한 픽셀에 삽입하는 과정이 필요하다. 에지 정보를 삽입하는 방법은 그림 5와 같으며 그림 5를 만족하는 픽셀을 홀(hole)이라 한다.

    i가 현재 위치일 때, 주변 픽셀인 i−1, i−2, i+1, i+2번째 픽셀은 에지의 방향 정보인 공간 방향벡터를 가지고 있으며 왼쪽과 오른쪽의 각각의 픽셀의 에지의 방향 정보가 같다면 방향이 없는 현재의 위치에 주변의 에지 방향 정보를 삽입한다. 만약 주변 픽셀이 에지 정보를 가지고 있다고 하더라도 서로 다른 방향의 정보를 가지고 있다면 현재 상태를 유지한다. 즉, 현재의 위치에서 왼쪽과 오른쪽 각각 2픽셀 씩 상관성을 고려하여 이 4픽셀의 SDVs가 유사할 경우 현재위치의 픽셀도 같은 방향이 있다고 간주하여 현재위치의 방향정보를 주변 픽셀 정보로부터 받아올 수 있다. 이 과정을 통하여 2단계 검색으로 인하여 간혹 발생하는 방향이 충분히 있음에도 불구하고 에지의 방향을 찾지 못한 부분에 올바른 방향정보를 삽입하여 수직으로 영상이 보간되지 않고, 방향에 따라 보간되어 영상의 화질을 향상시킬 수 있다.

    Ⅳ. 실험 및 결과

    제안된 보간법의 성능 비교 평가를 위해서 그림 6에 명시한 ISO 9000 흑백영상 10장을 이용하여 실험하였다. 그리고 제안된 보간법의 성능 평가를 위해서 앞에서 소개한 여러 가지 방법과 비교 실험하였다. 여기서 제안된 방법의 임계값 T와 검색 범위 R은 기존의 DOI에서 사용한 값과 동일하게 각각 10과 16을 사용하였다. 각각의 방법으로 얻어진 결과영상과 원 영상을 비교하는 측정 방법으로 PSNR(peak signal to noise ratio) 을 사용하였으며 연산시간 10회 반복 수행한 결과에 대한 평균을 ms단위로 측정하였다.

    다음 표 1은 각각의 디인터레이싱 방법에 대한 PSNR 비교결과를 나타낸 것이다. 첫 번째 열은 실험을 위해 사용된 영상의 이름을 나타내고 두 번째 열부터 네 번째 열은 각각 ELA, DOI, SDA방법으로 영상을 실험한 결과를 나타낸다. 마지막 다섯 번째 열은 제안된 방법의 결과 값을 나타낸다. 표1의 실험결과가 보여주듯이 DOI나 SDA에 비해서도 평균적인 PSNR값이 다소 향상되었다. 또한 DOI방법보다 2단계 검색을 사용하여 평균적으로 200%이상의 연산속도 개선이 이루어졌다.

    그림 7은 finger 영상에 대한 기존의 보간법과 제안된 보간법을 적용한 결과를 보여주고 있다. 그림 7에서 DOI에 비하여 주관적인 화질 개선이 개선되었으며 2배 이상의 연산시간을 가지는 SDA와의 주관적인 화질 비교에서도 큰 차이가 없다. finger 영상에서도 따라서 제안된 방법의 결과는 기존의 방법과 주관적인 비교를 하여도 우수함을 알 수 있다.

    Ⅴ. 결 론

    본 논문에서는 DOI의 연산속도를 개선하기 위해 개선된 DOI방법을 제안하였다. 제안한 방법은 기존 DOI의 장점을 유지하며 느린 연산속도를 전역 검색하는 과정을 2단계 검색으로 변경하여 개선하고 드물게 잘못된 방향으로 보간하는 문제점을 개선하기 위하여 2가지 단계를 추가하였다. 제안된 방법에 대한 비교 평가 실험 결과는 기존의 방법에 비하여 주관적으로나 객관적으로 더 우수함을 보였다.

  • 1. Doyle T. 1998 "Interlaced to Sequential Conversion for EDTV Applications," [in Proc. 2nd Int. Workshop Signal Processing of HDTV] P.412-430 google
  • 2. Chen T., Wu H.R., Yu Z.H. 2000 "Efficient Deinterlacing Algorithm Using Edge-Based Line Average Interpolation," [Optical Engineering] Vol.39 P.2101-2105 google doi
  • 3. Shen Y., Zhang D., Zhang Y., Li J. 2006 "Motion Adaptive Deinterlacing of Video Data with Texture Detection [IEEE Trans. Consumer Electronics] Vol.52 P.1403-1408 google doi
  • 4. Kim W., Jin S., Jeong J.C. 2007 "Novel Intra Deinterlacing Algorithm Using Content Adaptive Interpolation," [IEEE Trans. Consumer Electronics] Vol.53 P.1036-1043 google doi
  • 5. Yoo H., Jeong J.C. 2002 "Directional-Oriented Interpolation and its Application to Deinterlacing," [IEEE Trans. Consumer Electronics] Vol.48 P.954-962 google
  • 6. Khvan D., Jeong J.C., Jeon G.G 2012 "Intra-Field Selective Deinterlacing Algorithm Considering the Fine Edge Direction," [IEEE SITIS 2012 8th Conference] P.884-890 google
  • 7. Kovacevic J., Safranek R.J., Yeh E.M. 1997 "Deinterlacing by Successive Approximation," [IEEE Transactions on Image Processing] Vol.6 P.339-344 google doi
  • 8. Lin S.F., Chang Y.L., Chen L.G. 2003 "Motion Adaptive Interpolation with Horizontal Motion Detection for Deinterlacing," [IEEE Transactions on Consumer Electronics] Vol.49 P.1256-1265 google doi
  • 9. Park M.K., kang M.G., Nam K.C., Oh S.G. 2003 "New Edge Deinterlacing Algorithm Based on Horizontal Edge Pattern," [IEEE Transactions on Consumer Electronics] Vol.49 P.1508-1512 google doi
  • 10. Ballester C., Betralmio M., Caselles V., Garrido L., Marques A., Ranchin F. 2007 "An Inpainting-based Deinterlacing Mehod," [IEEE Transactions on Image Processing] Vol.16 P.2476-2491 google doi
  • 11. Lee D.H. 2008 "A New Edge-based Intra-field Interpolation Method for Deinterlacing Using Locally Adaptive-thresholded Binary Image," [IEEE Transactions on Consumer Electronics] Vol.54 P.110-115 google doi
  • 12. Wang J., Jeon G.G, Jeong J.C. 2013 "Deinterlacing Using Taylor Series Expansion and Polynomial Regression," [IEEE Transactions on Circuits and Systems for Video Technology] Vol.23 P.912-917 google doi
  • 13. Park S.J., Jeon G.G, Jeong J.C. 2009 "Deinterlacing Algorithm Using Edge Direction from Analysis of the DCT Coefficient Distribution," [IEEE Transactions on Consumer Electronics] Vol.55 P.1674-1681 google doi
  • 14. Jin S.J, Kim W.K., Jeong J.C. 2008 "Fine Directional Deinterlacing Algorithm Using Modified Sobel Operation," [IEEE Consumer Electronics Society] Vol.54 P.587-862 google doi
  • 15. Park D.-Y., Yoo H. 2013 "Shifted Linear Interpolation with an Image-Dependent Parameter," [J. Korea Inst. Inf. Commun. Eng.] Vol.17 P.2425-2430 google doi
  • 16. Ha M.-R., Yoo H. 2014 "Determining of Weighting Factor for Two-Point Interpolation Filters," [J. Korea Inst. Inf. Commun. Eng.] Vol.18 P.706-712 google doi
  • 17. Yoo H., Yoon D., Kim D. 2010 "Decimation-interpolation structures for image communications and improvement using the lifting scheme," [IEEE Trans. Consumer Electronics] Vol.56 P.2669-2677 google doi
  • 18. Choi B.-D., Yoo H. 2009 "Design of piecewise weighted linear interpolation based on even-odd decomposition and its application to image resizing," [IEEE Trans. Consumer Electronics] Vol.55 P.2280-2286 google doi
  • [그림 1.] DOI 보간법의 공간 방향벡터
    DOI 보간법의 공간 방향벡터
  • [] 
  • [] 
  • [] 
  • [] 
  • [] 
  • [그림 2.] DOI의 흐름도
    DOI의 흐름도
  • [그림 3.] 제안한 방법의 흐름도
    제안한 방법의 흐름도
  • [] 
  • [] 
  • [] 
  • [] 
  • [그림 4.] 잘못된 방향을 제거하는 방법
    잘못된 방향을 제거하는 방법
  • [그림 5.] 공간 방향벡터를 채우는 방법
    공간 방향벡터를 채우는 방법
  • [그림 6.] 실험을 위한 ISO9000의 실험 영상
    실험을 위한 ISO9000의 실험 영상
  • [표 1.] 기존 방법과 제안된 방법의 PSNR(dB)과 CPU 시간(ms) 비교
    기존 방법과 제안된 방법의 PSNR(dB)과 CPU 시간(ms) 비교
  • [그림 7.] Finger 영상에 대한 주관적 화질 비교 : (a) 원 영상 (b) LA (c) ELA (d) DOI (e) SDA (f) 제안된 방법
    Finger 영상에 대한 주관적 화질 비교 : (a) 원 영상 (b) LA (c) ELA (d) DOI (e) SDA (f) 제안된 방법