[Computer Vision] Objectives - JPEG Algorithm

🧑🏻‍💻용어 정리

Computer vision
Edge
Segmentation
huffman coding
run-length encoding

 

이번에는 compression 중에서도 lossy compression, 즉 손실 압축에 대해 다루겠습니다.

 

 

JPEG Algorithm

 

 

이 방법은 data loss를 어느정도 수용하겠다는 것입니다.

 

그리고 높은 압축률을 취하는 것입니다.

 

그래서 아래와 같은 특성을 지닙니다.

 

• Some acceptable data loss
• Greater compression ratio

 

저장 공간이 충분하지 않은 환경에서는 높은 압축률이 매우 중요해집니다.

 

이것은 transform coding을 기반으로 합니다.

그 말은 위와 같이 주파수 도메인을 바꾸겠다는 의미이죠.

 

해당 frequency domain에서 압축을 수행하고, 해당 frequency에서 spatial domain으로 돌아오는 복원도 가능하다는 것입니다.

 

 

아래는 JPEG Algorithm의 흐름도입니다.

 

 

그래서, 영상 image가 들어왔을 때, 0 또는 1로 수치화 된 Compressed image를 말하는 것입니다.

 

그리고, 대부분의 case, width와 height가 다르기 때문에 M x N이라고 보겠습니다.

 

그리고 첫 단계를 보면, m x n의 subimage를 생성하는 것이라고 보겠습니다.

 

 

위와 같은 Image가 input으로 들어왔다고 가정해봅시다.

위와 같은 block 하나를 subimage라고 할 수 있습니다.

 

이 경우, 이 block 크기를 몇으로 하냐에 따라 발생할 수 있는 개수가 달라집니다.

 

그리고 block의 크기가 커질 수록 subimage의 숫자는 줄어듭니다.

 

이 block의 크기는 4 x 4, 8 x 8, 16 x 16, ... 가능합니다.

 

그런데 JPEG는 기본적으로 8 x 8을 사용합니다.

 

결국, 첫 단계에서는 동일한 크기의 정사각형을 여러 개를 만듭니다.

 

그리고 서로 겹치지 않게 쪼개서 만드는 것입니다.

 

 

그리고 이제, 이 하나의 block에 대해서 이후 과정을 수행할 것입니다.

 

그렇다면 compressed image인 코드화된 숫자가 나옵니다.

 

그렇게 block 단위로 계속해서 진행합니다.

 

 

이제 block을 어떻게 코드화할지에 대해 이야기해보겠습니다.

 

아래와 같은 4 x 4의 block이 있다고 합시다.

 

좌측은 image에서 쪼개서 온 것으로 x와 y의 domain을 가지므로 이것은 Spatial domain입니다.

 

여기서 Forward Transform을 합니다.

 

즉, Spatial domain을 frequency domain으로 바꾸는 작업이죠.

 

여기서 숫자값 자체가 달라지기 때문에 f(x,y)가 F(u,v)로 바뀌게 됩니다.

 

 

여기서 frequency domain으로 바꾸는 작업에서 사용되는 것이 Fourier transform, FT입니다.

 

그런데 여기서는 Cosine Transform을 사용합니다.

 

Discrete Cosine Transform

영상은 discrete한 case이기 때문에 Discrete Cosine Transform을 사용합니다.

 

어째튼

 

Spatial domain에서 Frequncy domain으로 바꾸기 위해서 신호처리 기술을 사용해야하는데,

 

이 JPEG에서는 어떤 수식을 사용하냐 하니, DCT를 사용한다는 것입니다.

 

위 수식과 같이 f(x,y) 값과 cos 계산 값을 통해서 F(u,v)의 값을 결정할 수 있습니다.

 

 

일단,

 

이 수식에서 F(0, 0)을 한 번 계산해보겠습니다.

 

 

 

위 시그마에 대한 수식은 f(x,y)에 대해서 pixel 값을 출력해내는 함수입니다.

 

위와 같이 나온 식을 더 전개해봅니다.

그리고, 위와 같이 w = 0일 때의 값을 따르며 이 경우 n = 4이므로, 아래와 같은 결과가 나옵니다.

그렇다면, 위 그림에서 n = 4이므로, 이것은 다음과 같은 식을 따르게 되죠.

그래서 이 것은 block의 총합을 띄게 되고,

 

이것에 1/4를 곱해주는 것은 평균에 가까운 연산을 의미합니다. (가깝다는 것은 1/16으로 나눠야 평균이 되기 때문에 사용한 말입니다.)

 

그래서 이 block이 밝다고 한다면, 총합이 크다는 의미가 됩니다.

 

그리고 이 block이 어둡다고 하면, 총합디 작다는 의미가 되겠죠.

 

결국 이 F(0, 0)이 의미하는 것은 이 압축하고자 하는 것의 밝기, 명도를 의미하게 됩니다.

 

 

 

그래서 이 DCT라는 식을 가져온 것이 Spatial domain에서 Frequency domain으로 바꾸기 위함인데,

 

이 F(u,v)를 구하려면, 지금 4 x 4를 다 계산해야하는데, F(0,0)만 구했습니다.

 

그래서 이 F(0,0)의 값은 명도, 밝기를 나타내고, 이 값을 직류 성분 혹은 DC성분이라고 합니다.

 

 

그래서 이 밝기 성분인 DC에 대해서 나머지 15개 성분인 AC에 대해서 얼마나 변화하는지를 나타내는 것을 봅니다.

 

 

다시 식으로 돌아와서 F(1,0)을 구해봅시다.

 

 

위와 같은 로직으로 풀이하면 위와 같이 구할 수 있습니다.

 

결국 위 수식은 submask와 filter mask 사이의 filtering을 의미합니다.

 

filter mask는 아직 구하진 못한 식입니다.

 

아래 수식, 즉 위 cos 식에 의해서 filter mask의 값이 채워진다는 것입니다.

그리고 cos 함수를 한 번 봅시다.

 

그래서 위와 같이 양수와 음수 관계가 있습니다.

 

그래서 filter mask가 무엇으로 채워져있는지 위의 값을 통해 알 수 있습니다.

 

그렇게 색을 칠하면 위와 같은 결과를 얻을 수 있습니다.

 

그래서 왼쪽은 양수의 값, 우측은 음수의 값을 가집니다.

 

위 filter mask는 우리가 배운 sobel filter와 양상이 비슷합니다.

 

이 sobel filter가 수직선에서 높은 반응값을 나오게 하며, 좌측이 음수, 우측이 양수이지만 좌측이 양수, 우측이 음수입니다.

 

그래서 이 filter mask도 수직선에 해당하는 영역에서 높은 반응값이 나온다는 것입니다.

 

 

F(0,0)에 대한 값은 filter가 모두 1/4가 곱해져 있는 형태입니다.

 

이것은 이 block의 밝기 성분을 담고 있는 것과 동일한 형태입니다.

 

그런데, 이 값만으로는 우리가 원하는 원래의 값으로 복원하기에는 한계가 있습니다.

 

즉, 주변 pixel 값 사이의 차이도 저장을 해줘야합니다.

 

그리고 아래와 같이 나머지 위치에 대한 filter mask가 나와있습니다.

그래서 F(0,1)과 같은 경우에는 수평선에서 높은 반응값을 가지게 되는 것입니다.

 

그렇게 다른 것들도 주변간의 차이를 계산할 수 있는 형태로 계산됐다는 것입니다.

 

DCT를 사용하는 이유가 전반적인 밝기를 하나 저장한 뒤, 나머지는 차이를 구하기 위해서 다양한 mask를 사용했다는 것이죠.

 

그래서 가로, 세로, 대각선 등등의 차이를 볼 수가 있습니다.

 

위와 같이 특징을 가지는 block들을 추출하여 DCT로 16가지 종류의 filter mask를 취했을 때, 어떤 값의 결과를 갖는지 봅시다.

 

2번째 줄을 보면, 가장 높게 솟아있는 부분이 F(0,0)의 부분입니다.

 

이것이 전반적인 밝기 값을 나타내고 나머지는 변화량을 나타내는 것입니다.

 

전반적으로 변화가 없다면 전반적으로 낮은 값을 가집니다.

 

simple edge는 약간의 수직선을 가지는 부분에 대한 결과가 높게 나오는 것을 볼 수 있습니다.

 

그리고 highly detailed 부분을 보면, 해당 값은 서로 차이가 많기 때문에 다들 높은 값이 나옵니다.

 

 

 

그런데 smooth block의 경우에는,

 

영상에는 배경과 같은 부분에는 이렇게 8 x 8로 짤랐을 때,

 

같은 부분이 많이 나올 것입니다.

 

그리고, F(0,0)과 그 주변 가로 세로 부분을 제외하고 나머지 부분을 다 날려도, flat한 영역은 큰 차이 없이 복원이 가능합니다.

 

 

결국 이것은 무리가 없습니다. 그래서 중요한 값은 DC라는 곳에 저장되어 있고,

 

그렇기 때문에 DC 주변 값들만 저장해도 무리가 없다는 것입니다.

 

그렇게 저장 효율을 극대화 시키고 그것을 복원했을 때 상당히 좋은 효율을 낼 수 있다는 것이죠.

 

 

 

좌측은 조금 더 간소화된 형태입니다.

 

위 사진과 같이,

 

cosine에서 가장 좋은 효율을 내며,

 

8 x 8 일 때, 속도도 빠르고 복원도 많이 된다는 것입니다.

 

 

 

그래서 위와 같이 8을 대입하면 위와 같이 되고,

 

f(x,y)에 대한 convolution 연산과 filter mask 등의 연산들을 생각하며 봅시다.