룩업테이블(Look Up Table) 연산

룩업 테이블(LookUpTable : LUT)은 산술연산을 고속으로 수행하기 위해서 사용된다. 예를 들어 입력된 원 영상에 일정한 값을 곱해서 영상의 대비를 증가시키는 연산을 행한다고 가정하자. 이러한 작업을 하는 프로그램은 다음과 같다.

for (i = 0; i < height; ++i)
{
  for (j = 0; j < width; ++j)
  {
    temp = (int)(InImg[i][j] * 1.4);
    OutImg[i][j] = temp > 255 ? 255 : temp;
  }
}

이 프로그램을 살펴보면 출력영상 ?OutImg[i][j]를 얻기 위해서 입력된 원 영상에 1.4라는 값을 곱하는 작업을 영상에 존재하는 단위픽셀의 수 만큼 반복해서 수행해 주고 있음을 알 수 있다. 곱셈 연산은 프로그램의 속도 저하에 많은 영향을 준다. 따라서, 고속동작을 위한 프로그램 작성을 위해서는 미리 필요한 곱셈 연산을 계산하여 임의의 테이블에 저장해 놓고 사용할 수 있다. 이러한 경우, 곱셈 산술 연산의 결과는 미리 생성된 테이블(?LookUp Table : LUT)에서 저장된 하나의 값을 가져오는 것만으로 해결도리 수 있게되므로 곱셈 연산의 수를 크게 줄일 수 있고 그만큼 계산 속도의 개선이 가능하다.

unsigned char LUT[256];

for (i = 0; i < 256; ++i)
{
  int temp = (int)(i * 1.4);
  LUT[i] = temp > 255 ? 255 : temp;
}

for (i = 0; i < height; ++i)
{
  for (j = 0; j < width; ++j)
  {
    OutImg[i][j] = LUT[InImg[i][j]];
  }
}

위의 두 리스트의 결과를 비교해 보면 곱셈횟수가 height * width 번에서 256번으로 줄었다는 것을 알 수 있다. 이것은 상당한 연산량의 감소이다.