[Computer Vision] Objectives - JPEG Algorithm (2)

🧑🏻‍💻용어 정리

Computer vision
Edge
Segmentation
huffman coding
run-length encoding
Transfer coding
DCT
Quantization
Thresholding
Zigzag scanning
DC
AC
Entropy coding
Decoding

 

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

 

해당 과정을 이어서 살펴보겠습니다.

 

 

Transfer coding

 

 

 

block은  m x n의 크기에 대해서 다루겠습니다.

 

DCT가지고 저번에는 4 x 4로 했었고,

 

8 x 8의 block으로 진행해보겠습니다.

 

 

지금, 0 ~ 255 사이의 값들이 들어가 있습니다.

 

다음의 과정을 봅시다.

 

 

 

1. 각 pixel의 값에 128을 빼줍니다. (전처리)

 

pixel의 중간값인 128을 빼주어 분포상의 중간값을 빼면 0기준 값으로 나누게 됩니다.

 

이것은 목적, 분야에 따라 조금씩 달라집니다.

 

 

2. DCT

 

 

128을 뺀 값에다가 DCT를 구해줍니다.

 

 

가장 왼쪽 위의 값이 DC 성분으로, 평균과 비례한 값이며 밝기에 비슷한 값입니다.

 

그래서 변화량을 나타내는 나머지 AC 성분에 비해 큰 값을 가지게 됩니다.

 

 

그래서 이러한 AC 값은 어떤 변화량들을 뽑아주는 역할을 한다고 볼 수 있습니다.

 

예를 들면, X 방향 변화량을 뽑아내는 filter로 filtering을 하는 것과 다를 게 없다고 보았습니다.

 

 



3. Quantization + Thresholding

 

 

 

이 Quantization은 값에 대해 나누기를 하고 소수에 대해 반올림을 하여 정수 혹은 자연수화 시키는 과정입니다.

 

8 x 8 크기의 Quantization table은 주어집니다.

 

내가 압축하고자 하는 Block의 크기와 같은 크기의 table이어야 하고, 이러한 table을 가지고 나누기를 해야합니다.

 

같은 크기이므로 정확히 동일한 위치에 대해 나누기를 진행할 수  있습니다.

 

 

우측에 보면 -415 / 16 이후 반올림을 하여 -26이 나오게 됩니다.

 

 

이것을 왜 할까요?

 

DCT 결과값 자체를 bit화 시켜도 됩니다.

 

아래 예시를 봅시다.

 

우리가 압축을 하는 목적은 최대한 적은 bit의 수로 앞의 숫자들을 압축을 하는 것이 목적이죠.

 

그래서 최대한 bit 수를 줄일 수 있는 방향이어야 합니다.

 

그 중 하나가 내가 표현하고자 하는 숫자의 범위를 줄이는 것입니다.

 

 

 

예를 들어,

 

8, 12, 100 가지의 값을 표현하려면 각각 3bit, 4bitm 7bit가 필요합니다.

 

그렇다면,

 

내가 표현하고자하는 값의 범위가 크면 클수록 더 많이 필요해집니다.

 

위 예처럼,

 

-415에서 16으로 나누고 반올림하여 -26을 만들었습니다.

 

415만큼의 범위에 대해 이렇게 나누기를 해줌으로써 -26으로 만들었습니다.

 

이렇게 나눠주는 것 자체가 표현의 범위를 줄여주므로 압축에 도움이 됩니다.

 

 

 

그렇다면 엄청 큰 수로 나누면 어떨까요?

 

이것은 당연히 문제가 있습니다.

 

 

압축률은 좋을 수 있지만, 원래 값으로 복원할 때를 생각하면 좋지 않습니다.

 

-415에서 16을 나누어 -26으로 나누었습니다. 그렇다면 아래와 같이 비트로 만들었습니다.

 

그런데 여기서 다시 돌아올 때, -26으로 돌아왔다고 보고, table에 가지고 있던 값을 통해 -26 x 16을 통해 -416으로 돌아왔습니다.

 

 

여기서 오차가 발생하게 됩니다. 이것이 손실이죠.

 

여기서 최악의 case는 15까지의 오차가 발생할 수 있습니다.

 

그래서 손실 압축이라고 부르게 되는 것입니다.

 

그럼에도 압축률을 높일 수 있기 때문에 해당 나누기를 해주고, 그로 인해 발생하는 오차도 감수하겠다는 것입니다.

 

 

이제 DC 이외의 나머지 AC 부분을 보겠습니다.

 

나누기로 나온 결과를 보면, 왼쪽 위에서 오른쪽 아래로 갈 수록 대부분 0의 값을 가지고 있습니다.

 

애초에 DCT를 통과한 값이 크지 않고, DC에서 멀어질 수록 값이 작아집니다.

 

그리고 Quantization table을 보면, 우측 하단으로 갈 수록, DC에서 멀어질 수록 이미지를 복원함에 있어 그렇게 중요한 값이 아니니, 나누기를 크게 하여 값의 범위를 낮추어 줍니다.

 

즉, 필요 없는 부분에 큰 값을 나누어 0으로 만들어 압축률을 높입니다.

 

이렇게 0이 많이 나오게 되면,

 

앞에서 배운 것처럼 run-length 때, 같은 숫자가 반복해서 많이 나오면 저장하기도 쉬워집니다.

 

그리고 0을 많이 발생 시키면 0의 개수만 세면 되기 때문에 적은 bit수로 표현이 가능해집니다.

 

해당 데이터를 더 이상 쓰지 않겠다는 것과 같은 것입니다.

 

이 0의 값에 어떤 값을 곱해도 0이 되기 때문에 사실상 쓰지 않겠다는 것입니다.

 

이것이 image 복원에 있어 크게 영향을 주지 않습니다.

 

그래서 그것을 감수하고 버려서 쓰지 않겠다는 것입니다.

 

그 낮은 값을 무시하겠다는 것이죠.

 

이 Quantization table은 JPEG를 연구하는 사람들이 오랜 연구로 실험적으로 만들어내어 정한 값이며 값이 바뀌었을 수도 있습니다.

 

연산 자체는 간단하죠.

 

이것은 범위를 낮춰주고 더 나아가 0으로 만들어 버려 표현 숫자 범위를 줄이는 효과를 가져옵니다.

 

이렇게 특정 부분에만 중요한 정보가 몰리게 할 수 있습니다.

 

거의 절반 부분은 거의 날리게 되는 구조입니다.

 

 

 

4. Zigzag scanning

 

 

 

이것을 결과적으로 bit화 시킵니다.

 

압축 과정 또한 2차원이 아닌 vector의 형태로 1차원으로 나열해야합니다.

 

 

우리는 image 접근에 있어 가로 scanning을 많이 해왔습니다.

 

그런데 단순하며 효과적인 zigzag scanning을 사욜하게 됩니다.

 

0이 여기서 예를 들어 40개가 있다고 봅시다.

 

그럼 EOB라는 것을 사용해 이 뒤는 다 0임을 나타내는 값을 나타냅니다.

 

우리가 scanning을 할 때, 끝 부분에 0이 많이 있을 수록 효과적이겠습니다.

 

 

그러한 것을 할 수 있는 것이 이 zigzag 입니다.

 

빨리 0들에 도달하기 위해선 zigzag가 가로 scanning보다 효과적입니다.

 

그리고 zigzag가 EOB 안에서 0의 개수가 훨씬 많아질 수 있습니다.

 

 

만약, EOB 안의 0의 개수가 40개 이고, 나머지는 24개라고 한다면,

 

24개만 bit화 시키면 끝인 것입니다.

 

 

이 위 24개가 훨씬 적으니 zigzag scanning이 훨씬 효율적임을 알 수 있게 됩니다.

 

0의 숫자는 동일하지만, 0의 연속한 개수를 늘릴 수 있겠다는 것입니다.

 

이렇게 압축률을 올릴 수가 있습니다.

 

 

 

 

 

DC

DC 값은 밝기 값에 비례해서 나옵니다.

 

둘 다 같은 배경의 이미지이면 값 차이가 거의 나지 않을 것입니다.

 

 

압축 하는 값의 범위를 줄이면 줄일 수록 압축률이 좋아집니다.

 

그래서 이웃 block 끼리 같은 경우 residual을 적용하여 수의 범위를 줄일 수 있으니, DC 만의 차이를 통해 residual을 사용하여 bit화 시키는 방법을 사용하여 압축률을 줄이는 데 기여합니다.

 

인접한 block 간의, DC 부분의 차이를 구하면 값을 낮은 값으로 많이 만들어줄 수 있습니다.

 

이 차이를 구하는 part가 있고, AC는 밝기를 계산하는 게 아니니 차이를 하진 않고,

 

밝기를 계산하는 Part인 DC 값만 인접한 block 간의 차이를 구해서 그 차이로 나온 값을 bit화 시킵니다.

 

 

왼쪽 block의 DC 값을 -17로 가정한다면,

 

-9에 대해서 하려면 2개의 table 이 필요합니다.

 

 

여기서 -9이니 category가 4임을 알 수 있습니다.

 

이 category에 대해서 101의 Bit 값을 쓴다고 하였고,

 

이 범위 안에 있다고 암시하는 값이 101입니다.

 

그리고, -9 자체를 표기를 해야하니,

 

위 그림처럼,

 

9가 1001이니, 보수로 바꾸어

 

-9는 0110으로 표기합니다.

 

그래서 해당 residual이 1010110으로 표기됩니다.

 

그런데 이 category는 왜 붙일까요?

 

 

현재 bit화 시키고자 하는 것은 -9이긴 하지만,

 

우리가 현재 표현하고자하는 DC 값의 범위를 모릅니다.

 

 

0 ~ 255의 Pixel 값이 존재하는데, 이것은 8비트 안에 들어갑니다.

 

DC 값은 그것보다 범위가 더 커질 수 있습니다.

 

그래서 그 범위를 최대한 크게 잡아둬야 오류없이 진행될 수 있습니다.

 

최대한 에러가 나오지 않게 하기 위해서 나올 수 있는 모든 값의 범위를 다 포괄해야합니다.

 

 

그래서 8.17. table을 보면, 가장 아랫 범위는 꽤 큰 값이 됩니다.

 

이것은 3만대까지 가려면 16제곱까지도 갈 수 있습니다.

 

 

이것을 모두 16 비트로 잡아두면 너무 비효율적이니,

 

여기서 저번에 배운 huffman에서,

 

자주 나오는 case는 적은 Bit 수를 할당하는 것이었죠.

 

이 concept과 같은 것입니다.

 

우선, 범위를 최대로 잡아 오류가 나오지 않도록 합니다.

 

그리고, 그런데 이 최대 bit를 다 사용하면 너무 낭비이니,

 

자주 나오는 0 ~ 15 사이의 값에 대해서 비트가 다 작게 되어 있습니다.

 

그리고 이 범위에서 값이 커지면 커짐에 따라, 이 category를 표현하는 bit 수가 점점 늘어납니다.

 

이것이 huffman의 concept입니다.

 

이것은 huffman을 하긴 하지만, 값 자체에 대한 빈도보다는, 값이 어떤 category에 속하는지를 먼저 지정을 합니다.

 

이 빈도에 따라 category의 bit 수를 택합니다.

 

 

그래서 -9는 1010110으로 bit 총 7개로 표현한 것입니다.

 

 

AC

 

이제 AC를 봅시다.

 

-3에 대해서 따져봅시다.

 

AC도 마찬가지로, category를 찾아갑니다.

 

DC와 다르게 category가 '/'가 포함되어 있습니다.

 

/ 앞에 써지는 수는 지금 -3 앞에 0이 몇 개 있는지를 의미하는 것입니다.

 

 

그래서 -3 앞에 0이 없으므로, -9 밖에 없으므로, / 앞에는 0이 되고,

 

cateogry는 2이므로,

 

0/2가 됩니다.

0/2 group이 의미하는 것은 01입니다.

 

그래서 01을 가져오고,

 

이것은 group을 뜻하는 Bit이고,

 

-3의 값도 가져와야 합니다.

 

그래서 -3은 최종적으로 0100이 됩니다.

 

 

먼저 group에 대한 category가 먼저 할당 되고, 그 다음에 해당 숫자에 대한 Bit가 들어갑니다.

 

여기서 bit를 다시 숫자로 보는 복호화, 복원이 어렵고 복잡합니다.

 

여기서는 다루지 않겠습니다.

 

 

이것도 마찬가지로 자주 나오는 것에 대해서는 적은 bit, 많이 나오는 범위에서는 큰 bit로 표현하는 concept입니다.

 

DC와 다른 것은 앞에 0이 몇 번 나왔는지까지 체크합니다.

 

AC는 0이 중간중간에 존재합니다.

 

그래서 0을 하나하나 보는 것보다 0이 몇 번 발생하는지까지 같이 묶어서 보는 것이 조금 더 좋다고 판단됩니다.

 

 

0, 0, -1은 0을 무조건 묶어서 표현한다고 했었죠.

 

그리고 0이 안 나오는 숫자까지 기록을 합니다.

 

그래서 0, 0, -1이 한 set입니다.

 

이렇게 한 번에 bit화를 시킵니다.

 

 

여기서는 -1이 어떤 category에 들어가야하는지를 봐야합니다.

 

이 경우 category 1이고,

 

0이 두 번 발생했으므로, 2/1로 이 group을 구성할 수 있습니다.

 

그래서 표에서 찾아서 보면 11011이고, -1을 표현하면 0이 되므로,

 

0, 0, -1은 110110이 됩니다.

 

 

 

그리고 마지막 EOB부터 마지막까지 다 0임을 나타냅니다.

 

즉, "여기서부터 64까지 다 0입니다."이라,

 

EOB는 1010으로 Bit를 나타냅니다.

 

 

그리고 -26을 residual에 대해서 -9로 계산이 된 형태입니다.

 

결과적으로 93 Bits로 표현하였습니다.

 

 

기본적으로, 64개의 pixels 값에 대해서 8 bits개가 있으므로,

 

512 bits가 존재합니다.

 

그런데 이것을 JPEG 방법을 통해서 92 bits로 줄였습니다.

 

이렇게 많이 줄이다보니, 손실이 나서 값이 그대로 돌아오기는 어렵습니다.

 

 

그래서 이러한 부분에서 자주 나오는 것은 적은 bits 수로, 적게 나오는 것은 많은 bits 수로 표현하는 huffman이 사용되었고,

 

AC 부분에서 0이 몇 번 발생했는지 중간 중간 체크하는 run-length까지 개념이 들어가 있습니다.

 

그러나 Huffman과 run-length는 손실이 일어나지는 않습니다.

 

 

 

 

그래서 bit화 시키고 원래의 값으로 돌아오는 부분에서는 loss가 발생하지 않습니다.

 

그런데, 10진수로 바뀐 다음에 다시 곱하기를 통해서 원래 값으로 돌아가는 부분에서 loss가 발생합니다.

 

즉, quantization에서 나누기 할 때 발생하는 것입니다.

 

실제로 곱하기로 돌아왔을 때 다를 수 있습니다.

 

 

DCT를 해줬으니, 다시 inverse DCT를 해주며,

 

여기서도 당연히 Loss는 일어나지 않습니다.

 

마지막으로 128을 더해주는 것으로 끝납니다.

 

 

그래서 위와 같은 before, after table을 볼 수 있습니다.

 

 

압축 후 복원한 사진입니다.

 

위와 같이 육안으로 봤을 때는 크게 차이는 안 보입니다.

 

 

그런데 이렇게 빼기를 했을 때, noise가 나오게 됩니다.

 

실제로 이러한 값의 변화는 있다고 볼 수 있습니다.

 

 

그래서 Quantization에서 loss가 발생한다고 했습니다.

 

여기서 나누는 값을 더 크게 한다면 어떻게 될까요?

 

 

 

위와 같이 오차가 더 많이 발생하는 것을 볼 수 있습니다.

 

 

더 큰 수로 나눌 수록 더 많은 오차가 발생하는 것을 위와 같이 볼 수 있습니다.

 

 

여기서 Block 별로 맞춰서 진행하고 다시 복원하니, 매끄럽게 진행돼야 block 들이 image에서 안 보이는데,

 

더 큰 값으로 나눈 것들은 block 들이 나타나 있습니다.

 

당연하게도,

 

더 큰 값으로 나눠줄 수록 더 많이 달라질 수가 있고,

 

16으로 나눠주면 0 ~ 15의 오차이지만 32로 나눠주면 0 ~ 31의 오차가 있을 것입니다.

 

만약 10배라면 160으로 나누어 0 ~ 159의 오차가 있을 수 있습니다.

 

 

그리고 0으로 되는 숫자가 더 많아집니다.

 

0이 되면 데이터가 아예 날라가는 것입니다.

 

아무리 AC 부분에서 중요하지 않은 부분이 많다곤 하지만,

 

남겨뒀어야 할 AC 값도 같이 0이 되어버리므로 복원이 안 됩니다.

 

큰 값으로 나누어줄 수록 복원했을 때 왜곡이 커집니다.

 

그럼에도 압축률은 좋아집니다.

 

0의 개수가 많아지고 값 자체의 범위가 작아지기 때문이죠.

 

그렇게 값의 범위를 좁히고 0의 반복들을 늘려서 압축률이 줄어듭니다.

 

그럼에도 복원률은 떨어지게 됩니다.

 

압축률과 복원률의 최적의 point를 잡아야합니다.

 

그것이 아까 적용된 Quantization table인 것이죠.