6. LUT를 이용한 속도 비교(ColorReduction / ColorReductionLUT)

lookUpTable(LUT) -> In computer science, a lookup table is an array that replaces runtime computation with a simpler array indexing operation. The savings in terms of processing time can be significant, since retrieving a value from memory is often faster than undergoing an "expensive" computation or input/output operation.^[1] The tables may be precalculated and stored in static program storage, calculated (or "pre-fetched") as part of a program's initialization phase (memoization), or even stored in hardware in application-specific platforms. Lookup tables are also used extensively to validate input values by matching against a list of valid (or invalid) items in an array and, in some programming languages, may include pointer functions (or offsets to labels) to process the matching input. FPGAs also make extensive use of reconfigurable, hardware-implemented, lookup tables to provide programmable hardware functionality.

간단하게 말해서 배열 인덱싱 작업과 런타임 계산을 대체하는 방법 입니다. 

메모리로부터 값을 검색하는 것은 비싼 계산 이므로 미리 정적프로그램 저장부에 계산을 해놓구 처리하는 부분을 따로 해놓은 방법입니다.

변환 속도를 단순화 하기 위해서라고 이해해 주시면 좋겠습니다. 사용목적은 간단한 프로그램 작성할때는 요즘 컴퓨터 성능이 좋아져서 차이점을 못 느끼지만 큰 작업을 해야될 경우에는 속도차이가 있어, 그 규모가 커지면 커질수록 차이가 많이 짐니다.

-출처 : https://en.wikipedia.org/wiki/Lookup_table 

앞서 나온 Reduction함수와 차이점을 비교해보자.

cv::Mat myColorReductionLUT(Mat &srcImg, int cw)//lookuptable

{

Mat_<Vec3b> destImg = Mat_<Vec3b>(srcImg.clone());

uchar lut[256];

for (int i = 0; i < 256; i++)

{

lut[i] = int(i / cw) *cw;

}

for (int r = 0; r < srcImg.rows; r++)

{

for (int c = 0; c < srcImg.cols; c++)

{

Vec3b rgb = destImg(r, c);

for (int k = 0; k < 3; k++)

{

rgb[k] = lut[rgb[k]];

}

destImg(r, c) = rgb;

}

}

return destImg;

}

---------------------------------

rgb[k] = int(rgb[k] / cw) * cw; 앞에 나온 차이점은 여기서 나온다. 미리 for문을 이용하여 값을 만들어 놓은후 그 값을 대입시켜준다.

그래서 for문을 이용하여 두 함수가 호출되는 시점을 시간을 비교해 보겠습니다

setup함수에서 비교를 해보겠습니다.

for (int i = 0; i < 1000; i++)

{

Mat colorReduced = myColorReduction(srcImg, 64);  

}

for (int i = 0; i < 1000; i++)

{

Mat colorReducedLUT = myColorReductionLUT(srcImg, 64);

}

이 두개의 차이를 비교해보겠습니다 각 천번씩 루프를 돌며 비교해 봤습니다.

비교방식은 간단합니다.

double t = (double)getTickCount();

//함수호출

t = ((double)getTickCount() - t) / getTickFrequency();

cout << "Times passed in seconds: " << t << endl;

를 이용하여 비교를 해봤습니다.

getTickCount함수는 시스템이 시작된 이후 경과한 시간을 밀리초 단위로 반환합니다

Lookup Table를 이용하지 않은 방식입니다. 대략 32.3085초가 걸렸네요

 LookUp Table를 이용한 방식에서는 30.6334초가 걸렸네요

여기서 대략 2초정도가 차이가 나는데 이미지 한장 할때 차이인데 수백 수천 수만장 이상이 넘어가게 되면, 차이가 더 어마어마 해지겠죠?