아이돌의 사용으로 서비스 이용량이 급증한 상황에서, 제한된 저장소를 효율적으로 활용하기 위한 이미지 압축 알고리즘의 수학적 원리와 품질평가 지표를 통한 포토티켓 생성 서비스의 최적화 방안

[carter468]

서론

1. 주제 소개

• 이미지 압축은 디지털 이미지에 적용되는 데이터 압축 유형으로 저장 또는 전송비용을 절감하기 위해 사용됩니다. 시각적 인식과 통계적 속성을 사용한 알고리즘은 다른 디지털 데이터에 사용되는 일반적인 데이터 압축 방법에 비해 더 뛰어난 결과를 얻을 수 있습니다.

2. 목적과 필요성

• 포토 티켓 생성 서비스에서 사용자 경험을 극대화하기 위해 고해상도의 이미지를 다루는 것이 중요한 반면, 제한된 저장소를 효율적으로 활용해야 하는 문제에 직면하게 되었습니다. 이러한 맥락에서, 이미지 압축 알고리즘의 선택은 저장소 사용량과 이미지 품질 간의 균형을 유지하는 데 결정적인 역할을 합니다. 알고리즘에 대해 심도있게 알아보고 평가를 통해 최적화된 선택을 하고 서비스 경쟁력을 강화하고자 합니다.

3. 연구범위와 구조

이미지 압축 알고리즘 분석

• 무손실 압축 알고리즘의 수학적 원리와 적용 사례를 연구합니다.
• 손실 압축 알고리즘의 수학적 원리와 효율성을 분석합니다.

품질 평가 지표 연구

• PSNR, SSIM과 같은 전통적 이미지 품질 평가 지표를 중심으로, 이들의 계산 방법과 한계점을 연구합니다.
• VMAF와 같은 최신 품질 평가 지표를 포함하여, 이미지와 영상 품질 평가에 있어 지표들의 상대적 장단점과 적용 가능성을 분석합니다.

서비스 최적화

• 포토 티켓 생성 서비스에 적용 후 성과 분석

이미지 압축 알고리즘 연구

1. 무손실 압축 알고리즘

1. 런렝스 인코딩(RLE)

• 런렝스 인코딩의 기본 개념
  • 연속된 동일한 데이터 값을 줄여서 표현하는 방식입니다.
    예시) 원본 데이터: AAAABBBCCDAAA -> RLE 압축: 4A3B2C1D3A
• RLE를 이용한 이미지 압축
  • 이미지의 각 행(또는 열)에서 연속된 동일한 픽셀 값을 하나의 '런'으로 표현합니다.
    이와 같이 모든 행(또는 열)을 압축하여 새로운 데이터를 생성합니다.
• 장단점
  • 구현이 간단합니다. 연속적으로 동일한 픽셀이 많은 단순한 이미지는 높은 압축률을 기대할 수 있습니다. 압축과 복원이 빠릅니다.
  • 복잡한 이미지에서는 높은 압축률을 기대할 수 없습니다.
• 사용 사례
  • 단순한 그래픽 데이터: RLE는 단순한 2D 그래픽, 마스크, 아이콘 등의 압축에 사용됩니다. 이러한 데이터는 종종 연속적인 동일 픽셀이 많아 RLE의 효율성이 높습니다.
  • RLE는 BMP(Bitmap) 이미지 파일의 무손실 압축 방식 중 하나로 사용됩니다.

2. 허프만 코딩

• 원리 : 허프만 코딩은 빈도 기반 가변 길이 부호화를 사용하여 데이터를 압축합니다. 주어진 데이터에서 각 기호의 빈도수를 계산하고, 빈도수가 높은 기호는 짧은 이진 코드를, 빈도수가 낮은 기호는 긴 이진 코드를 할당합니다. 이렇게 할당된 코드를 사용하여 데이터를 압축합니다.
• 과정
  1. 빈도 계산: 데이터 내 각 기호의 발생 빈도를 계산합니다.
  2. 이진 트리 생성: 기호의 빈도수를 기준으로 허프만 트리를 생성합니다. 빈도수가 낮은 두 기호를 먼저 결합하여 새로운 노드를 만들고, 이를 반복하여 트리를 만듭니다.
  3. 이진 코드 할당: 허프만 트리에서 왼쪽 가지는 0, 오른쪽 가지는 1을 할당하여 각 기호에 대한 이진 코드를 생성합니다.
  4. 데이터 압축: 생성된 이진 코드를 사용하여 데이터를 압축합니다. 발생 빈도가 높은 기호는 짧은 코드로 표현되기 때문에 데이터의 크기가 줄어듭니다.
• 장단점
  • 데이터의 빈도에 따른 효율적인 압축이 가능하고, 엔트로피 기반 압축의 핵심 요소로 작동하는 등의 응용이 가능합니다.
  • 실시간 처리가 느릴 수 있어 변화가 많은 데이터 같은 경우 불편할 수 있고, 빈도가 고르게 분포된 데이터에는 비효율적입니다.
• 응용분야로 다음에 나올 JPEG 이미지 압축에서 사용됩니다.

3. LZW 압축 알고리즘

• 소개
  • LZ78(Lempel-Ziv 1978) 알고리즘을 Terry Welch가 1984년 개선한 알고리즘입니다.
  • dictionary 기반의 압축 기법을 사용합니다.

def lzw_compress(uncompressed):
    dict_size = 256
    dictionary = {chr(i): i for i in range(dict_size)}
    
    w = ""
    compressed_data = []
    
    for c in uncompressed:
        wc = w + c
        if wc in dictionary:
            w = wc
        else:
            compressed_data.append(dictionary[w])
            dictionary[wc] = dict_size
            dict_size += 1
            w = c
    
    if w:
        compressed_data.append(dictionary[w])
    
    return compressed_data

def lzw_decompress(compressed):
    dict_size = 256
    dictionary = {i: chr(i) for i in range(dict_size)}
    
    w = chr(compressed.pop(0))
    decompressed_data = [w]
    
    for k in compressed:
        if k in dictionary:
            entry = dictionary[k]
        elif k == dict_size:
            entry = w + w[0]
        else:
            raise ValueError(f"잘못된 압축된 값입니다: {k}")
        
        decompressed_data.append(entry)
        
        dictionary[dict_size] = w + entry[0]
        dict_size += 1
        
        w = entry
    
    return ''.join(decompressed_data)

if __name__ == "__main__":
    input_string = "BABAABAAA"
    print(f"원본 문자열: {input_string}")
    
    compressed = lzw_compress(input_string)
    print(f"압축된 데이터: {compressed}")

    print(f"압축률 : {(len(input_string)-len(compressed))*100/len(input_string):.1f}%")
    
    decompressed = lzw_decompress(compressed)
    print(f"복원된 문자열: {decompressed}")

결과

원본 문자열: BABAABAAA
압축된 데이터: [66, 65, 256, 257, 65, 260]
압축률 : 33.3%
복원된 문자열: BABAABAAA

• 장단점
  • 반복되는 패턴이 많은 데이터에서 매우 높은 압축률을 보여줍니다. 패턴이 많을수록 사전이 더 큰 패턴을 빠르게 식별할 수 있기 때문에, 더욱 효과적입니다. 데이터를 처리하면서 실시간으로 사전을 구축하기 때문에, 미리 데이터의 구조를 알 필요가 없습니다. 이는 다양한 데이터 형식에 적용할 수 있음을 의미합니다.
  • 사전의 크기가 제한된 경우, 너무 많은 패턴이 추가되면 사전을 관리하는 데 어려움이 생길 수 있습니다. 고도의 랜덤 데이터에서는 LZW의 효율성이 떨어집니다.
• 응용분야 : GIF파일 포맷, TIFF파일 포맷

2. 손실 압축 알고리즘

1. JPEG 압축의 수학적 원리(DCT 변환)

• 주파수 영역에서 이미지 데이터를 표현하는 방식
  • 주파수는 이미지의 변화율을 나타내며, 저주파수 성분은 이미지 내에서 천천히 변화하는 정보(색상 또는 밝기 차이)를, 고주파수 성분은 빠르게 변화하는 정보(디테일, 경계선, 잡음 등)을 나타냅니다.
• DCT는 이미지를 공간 영역에서 주파수 영역으로 변환하여, 각 주파수 성분이 어떻게 변하는지를 분석하고, 이를 기반으로 데이터를 압축합니다.
• DCT의 수학적 기초

F(u,v) : 주파수 영역에서 변환된 값
f(x,y) : 원본 이미지의 픽셀 값
u,v : 주파수 좌표

• 저주파수와 고주파수 성분의 분리
  • 저주파수 성분 : F(0,0)는 DC성분으로 전체 이미지의 평균 밝기를 나타냅니다. u,v가 작을수록 코사인 함수의 주기가 길어지며, 느리게 변화하는 정보를 나타냅니다. 즉, 이미지의 . 큰구조나 천천히 변화하는 색상 또는 밝기를 설명하는 성분입니다.
  • 고주파수 성분 : F(u,v)에서 u와 v의 값이 클수록 주파수가 높아지며 빠르게 변화하는 정보를 나타냅니다. 주로 경계선, 텍스처, 세부 디테일과 같은 부분을 나타냅니다.
• DCT 계수 배열의 해석

저주파수 성분은 주로 시각적으로 중요한 정보가 포함되어 JPEG 압축에서는 저주파수 성분을 상대적으로 보존합니다.
고주파수 성분은 시각적으로 덜 중요한 정보로 간주되어 압축의 핵심 역할을 합니다.
JPEG 압축의 핵심은 양자화로, 양자화 과정에서 고주파수 성분은 더 많이 압축되거나 버려지게 되며, 저주파수 성분은 더정확하게 유지됩니다. 이 과정에서 파일 크기가 대폭 줄어들지만 사람이 인지하는 부분은 손실이 최소화되어 시각적으로는 크게 품질 손실이 없습니다.

• 기본 양자화 테이블을 이용한 양자화

저주파수 성분은 작은 값으로 나누어 손실을 최소화하고, 고주파수 성분은 큰 값으로 나누어 값이 줄어들거나 0으로 처리되어 데이터를 손실합니다.
JPEG 표준에서는 Quality Factor를 사용하여 양자화 테이블의 값을 조절합니다. 품질 인수가 높으면 양자화 테이블 값이 작아져 고주파수 성분까지 세밀하게 유지되고, 품질 인수가 낮으면 양자화 테이블 값이 커져 고주파수 성분을 많이 제거하여 파일 크기가 작아집니다.
자연이미지는 고주파수 성분을 많이 압축해도 품질 저하가 적지만, 텍스트나 그래픽은 경계선이 선명해야 하므로 고주파수 성분을 덜 압축해야 합니다.

JPEG 압축의 전체 과정

1. 색상 공간 변환(RGB -> YCbCr) : Y(밝기 성분) , Cb, Cr(색차 성분)
2. 크로마 서브샘플링 : CbCr은 인간의 시각에 . 덜중요하기 때문에 크로마 서브샘플링을 통해 색상 데이터를 압축할 수 있습니다. 4:2:0 서브샘플링 방식이 흔히 사용되며, 2X2 픽셀 블록에서 Cb,Cr 성분을 1개만 남기믄 방식입니다.
3. 이미지 블록 분할 : 변환된 YCbCr 이미지 데이터를 8X8 픽셀 블록으로 분할합니다. 블록단위로 변환을 수행하는 이유는 계산 효율성을 높이기 위해서입니다.
4. 이산 코사인 변환 : 픽셀 값을 저주파수 성분과 고주파수 성분으로 분리하는 과정입니다.
5. 양자화 : 손실 압축이 발생하는 과정입니다.
6. 지그재그 스캔 : DCT 계수 배열에서 지그재그로 스캔을 하면 저주파->고주파 순서대로 처리할 수 있기 때문에 이 방식을 사용합니다.
7. 엔트로피 코딩 : 주로 Huffman Coding 방식으로 더 압축됩니다.

JPEG 압축의 장점

1. 파일 크기를 크게 줄일 수 있으며, 압축률을 조정할 수 있습니다.
2. 저주파 성분을 잘 보존하면서, 고주파 성분을 효율적으로 압축하여 시각적으로 품질을 유지합니다.
3. JPEG는 디지털 사진과 같은 복잡한 이미지에 특히 적합하며, 웹에서의 이미지 전송, 저장 등에 널리 사용됩니다.

JPEG 압축의 단점

1. 고주파수 성분의 일부 정보를 버리기 때문에, 압축률을 높이면 이미지 품질이 저하될 수 있습니다.
2. 고압축률에서 '8x8 블록 경계 인공물(blocking artifacts)'이 나타날 수 있습니다. 이는 특히 저해상도 이미지에서 눈에 띄게 보일 수 있습니다.
3. 동일 이미지를 반복해서 JPEG로 저장하면, 손실이 누적되어 품질 저하가 일어납니다.

2. Wavelet 변환을 이용한 이미지 압축

Wavelet 변환의 개념

웨이블릿 변환은 시간-주파수 분석을 동시에 할 수 있는 기법으로, '다중 해상도 분석(Multiresolution Analysis)'을 제공합니다. DCT과 같은 기존 변환 방법은 주파수 정보만 제공하지만, 웨이블릿 변환은 주파수 정보와 동시에 시간적(공간적) 정보를 보존하는 특징이 있습니다. 이미지의 다양한 세부 정보를 다른 해상도로 분석하는 데 효과적입니다.

[startupcodekr]

"아이돌의 사용으로 서비스 이용량이 급증한 상황에서, 제한된 저장소를 효율적으로 활용하기 위한 이미지 압축 알고리즘의 수학적 원리와 품질평가 지표를 통한 포토티켓 생성 서비스의 최적화 방안"