룩업 테이블, Lookup table

출처: https://blog.naver.com/sapeyes/70112636840

영상처리 기법에서 주로 사용되는 알고리즘인 룩업테이블을 알아본다.


1. 룩업테이블이란?


  룩업테이블은 주어진 연산에 대해 미리 계산된 결과들의 집합(배열)을 가리킨다. 이 집합(배열)은 주어진 연산에 대한 결과를 계산하는 시간보다 더 빠르게 값을 취득해 갈 수 있도록 사용되는 레퍼런스로 사용된다. 


 LUT는 주로 실시간 데이터 취득, 실시간 프로세싱 시스템 (embedded system)에서 사용된다. 이러한 시스템에서는 시간내에 연산 결과 취득에 대한 요구사항이 매우 높기 때문이다. 한가지 고려해야 할 점은 LUT는 배열을 최초 초기화 할때에는 연산량이 매우 많다는 점이다. 실시간 시스템에서는 이러한 초기화에서 딜레이가 일어나는 것 정도는 어느정도 감수해 주기 때문에 LUT가 사용되는 빈도가 높다. 


2. LUT 예제


 LUT에 대해 예를 들어본다. 심플하게, 실시간 데이터 취득을 고려해본다. 8비터 숫자로 데이터가 취득되고 있다고 가정해보자. 그리고 이 데이터들은 양수 (0~255)이다. 실시간 시스템은 데이터의 근(root)를 얻는 연산을 필요로 한다. C에서는 해당 연산에 대한 LUT를 다음과 같이 계산할 수 있다.


double LUT_sqrt[256];   /* 미리 전역변수로 선언해야 다른데서 쓰겠죠? */


/* 초기화 코드 부분을 이정도에 넣어야 겠죠? */
for (i=0; i<256; i++)
LUT_sqrt[i] = sqrt(i);   // math.h의 sqrt함수를 사용합시다.


/* 이부분은 실시간 시스템에서 데이터 변환 하는 곳이라고 봅시다. */


result = LUT_sqrt[sample];  /* sqrt(sample) 대신에 사용함으로써 시간 절약됩니다 */


3. 요약


 - 룩업테이블은 결과값을 가진 배열이다.
 - 룩업테이블 배열의 인덱스는 입력값이다. 배열의 값은 출력값이다.
 - 실시간 시스템에서 사전 초기화 모듈이 있는 경우 사용하면 좋다. 


4. 추가적으로 공부해야 할 부분


 - 인덱스에 들어가는 데이터 값이 소수라면 LUT를 사용할 수 있는가? 답은 YES. 


#참조 
http://www.mochima.com/articles/LUT/LUT.html#what_is_a_LUT


written by chim

[출처] LUT (Lookup Table) 룩업테이블|작성자 침스

 

 

순람표

출처: 위키백과, 우리 모두의 백과사전.

순람표(順覽表) 또는 룩업 테이블(lookup table)은 컴퓨터 과학에서 일반적으로 배열이나 연관 배열로 된 데이터 구조로, 런타임 계산을 더 단순한 배열 색인화 과정으로 대체하는 데 자주 쓰인다. 처리 시간의 절약은 중요할 수 있는데, 이는 메모리로부터 값을 받아오는 것이 더 일이 많이 드는 계산이나 입출력 기능을 거치는 것보다 더 빠르기 때문이다.[1] 테이블들은 정적인 프로그램 저장소에 미리 계산되어 저장하거나, 프로그램 초기화 단계(메모이제이션)의 일부로 계산(프리페치)할 수도 있다. 룩업 테이블은 배열에 위치한 일련의 (올바르거나 올바르지 않은) 값 항목들을 일치시키면서 입력값이 유효한지 확인하는 데 널리 쓰이기도 하며, 프로그래밍 언어에서는 포인터 함수를 포함(또는 레이블로 오프셋)하여 일치하는 입력을 처리할 수 있다.

역사[편집]

순람표는 컴퓨터 스프레드시트에 구현된 최초의 기능들 가운데 하나였으며 초기 20개 함수 가운데 LOOKUP 함수를 포함하여 VisiCalc(1979년)의 초기 버전에서 비롯되었다.[2] 이것이 마이크로소프트 엑셀과 같은 차기 스프레드시트에 도입되었으며 수직 또는 수평 방향으로 표 순람을 단순케 하기 위한 특수한 VLOOKUP 및 HLOOKUP 함수로 보충되었다. 마이크로소프트 엑셀에서 XLOOKUP 함수는 2019년 8월 28일을 기점으로 출시되었다.

같이 보기[편집]

·        메모이제이션

각주[편집]

1.      ↑ “보관된 사본”. 2012년 8월 31일에 원본 문서에서 보존된 문서. 2012년 1월 27일에 확인함.

2.      ↑ Bill Jelen: "From 1979 – VisiCalc and LOOKUP"!, by MrExcel East, March 31, 2012

외부 링크[편집]

·        (영어) Art of Assembly: Calculation via Table Lookups