Digital Image Processing 8. Image Compression Compter Engineering Sejong Uniersit 영상압축 Image Compression 일반적으로영상은대용량의저장공간소요 영상압축 : 영상을표현하는데에필요한데이터량을줄임 영상압축의기본원리 영상내에존재하는중복적인데이터 redndant data 를제거 application 디지털 TV 방송 Digital TV broadcasting 화상회의 Teleideo-conferencing 의학용영상 Medical imaging FAX 전송 Facsimile transmission 다양한 Mlti-media 환경 > 주로영상의전송과저장을위해사용 /58
기본이론 Fndamentals 압축및복원 무손실압축 Lossless compression : 압축후복원시원래의정보를정확히재생 손실압축 Loss compression : 압축후복원시원래의정보에서손실이발생 data compression 주어진양의정보를표현하는데필요한데이터의양을줄이는과정 데이터간의중복성을없앰으로써가능 영상데이터의중복특성 coding redndanc interpiel i redndanc d pschoisal redndanc /58 기본이론 Fndamentals Coding Redndanc의제거 발생빈도가높은값에짧은코드를부여 발생빈도가낮은값에긴코드를부여 코드의길이가변화됨 : 가변길이부호화 ariable length coding 전체데이터양을줄이는것이관건 영상데이터의경우히스토그램을관찰하여히스토그램이높은값에대해서는낮은비트를할당 /58
기본이론 Fndamentals 필요데이터양 화소값을 [] 범위의확률변수 r k 로표시 r k 의발생확률을p r r k 라고하면 pr rk nk n 총화소수를 L r k 를표현하는비트수를 lr k 라고하면한화소를나타내는평균비트수는 L ag L l r p k k r r k Coding Redndanc 의제거 : L ag 를최소화 5/58 기본이론 Fndamentals Coding Redndanc 의제거 L code code 7 7 ag l rk pr rk k k /58 Lag l rk pr rk.9 +.5 +. +..9 +.5 +. +. +.8 +. +. +. +.8 + 5. +. +.. bits.7 bits
기본이론 Fndamentals Coding Redndanc 의제거 발생확률과비트할당관계 7/58 기본이론 Fndamentals Interpiel Redndanc의제거 인접된화소간의유사성을이용 인접된필드간의유사성을이용 이웃하는화소간의차이값을이용하여데이터표현 Rn-length encoding DPCM ADPCM 기법 interpiel e redndanc da 를나타내는용어들 - spatial redndanc - geometric redndanc - interframe redndanc 8/58
기본이론 Fndamentals Interpiel Redndanc 의제거 9/58 기본이론 Fndamentals Pschoisal Redndanc의제거 인간의시각특성이영상정보에정확히반응하지않는사실이용 특정영상정보는인간의눈이무시하는경향 이러한정보들을제거함으로써인간의지각에차이를주지않고데이터의제거가가능 > 복원시정확한복구가안되는경우가많음 보통표본화 sampling 양자화 qantization 와관련 /58
기본이론 Fndamentals Pschoisal Redndanc 의제거 /58 기본이론 Fndamentals 충실도 fidelit 의기준 손실된시각정보의특성과양을규정짓는평가수단 objectie fidelit criteria i 객관적충실도기준 sbjectie fidelit criteria 주관적충실도기준 두평가기준이항상일치하지는않음 /58
기본이론 Fndamentals 객관적충실도기준의예 입력영상과출력영상의 root-mean-sqare error f fˆ 가각각입력영상 출력영상이라고하면 M 크기의두영상과의총오차는 M [ f ˆ f ] 두영상간의 root-mean-sqare e rms 는 e rms M M [ fˆ f ] / /58 기본이론 Fndamentals 객관적충실도기준의예 출력영상의평균제곱신호대잡음비 mean-sqare signal-to-noise ratio SR ms 는 SR ms M f M ˆ [ fˆ f ] /58
Image Compression Model Image Compression Sstem Encoder부와 Decoder부로구성 Sorce encoder : inpt 데이터의중복성제거 Channel encoder : noise에대한면역성 immnit 보강 영상의저장등채널잡음이없는경우에는 channel encoder/decoder는불필요 f Sorce Channel Channel Sorce Channel encoder encoder decoder decoder f ˆ Encoder Decoder 5/58 Image Compression Model Sorce Encoder 입력영상에서 coding interpiel pschoisal redndanc 를줄이거나제거하는역할 Sorce Encoding 단계 Mapper : 가역과정 reersible Qantizer : 비가역과정 irreersible Smbol encoder : 가역과정 reersible f Mapper Qantizer Smbol encoder Channel Sorce Encoder /58
Image Compression Model Mapper 입력영상에서 interpiel redndanc를줄이도록데이터형태를변환 데이터변환과정에서데이터양이줄어들수도있고같을수도있다. 예 : rn-length coding 변환결과 : 계수의배열로구성 Qantizer Mapper 출력의정밀도를줄임 pschoisal redndanc 를줄임 무손실압축시에는이과정을생략해야함 Qantizer coding redndanc를줄임 고정길이나가변길이코드를출력 7/58 Image Compression Model Sorce Decoder Sorce encoding의역과정으로원래의영상을복구 Encoding 시 qantization 과정이없을경우완전한복구가능 Sorce Decoding 단계 Smbol decoder : Smbol encoding 의역과정 Inerse mapper : Mapper 의역과정 Channel Smbol Inerse f Decoder Mapper ˆ Sorce Decoder 8/58
무손실압축 Error-free compression 무손실압축 손실을허용하지않는경우에사용되는압축방법 interpiel coding redndanc 를제거 Application 의학적인문서혹은비즈니스문서 인공위성영상 : 영상의취득이나관리가매우중요 방사선사진 digital radiograph : 정확한진단을위해필요 압축율은 ~ 정도 압축기법 가변길이부호법 ariable-length coding 산술부호법 Arithmetic ih i coding Bit-plane coding : 런길이부호법 Rn-length coding 무손실예측부호법 Lossless predictie coding 9/58 무손실압축 Error-free compression 가변길이부호법 ariable-length coding 가장단순한압축방법 coding redndanc만을제거 가장많이등장하는값에가장짧은부호를지정 입력으로서영상의화소값 화소값의차이 rn-length encoding 결과등이될수있다. 종류 허프만부호법 Hffman coding Trncated Hffman coding Shift coding Hffman shift coding /58
무손실압축 Error-free compression 허프만부호법 Hffman coding 가장일반적인기술 각 sorce smbol 당가장작은 code smbol 생성 자주사용되는 code에적은비트를할당허프만부호화과정. smbol 의확률을정렬. 가장낮은확률을갖는 smbol들을단일 smbol로조합하여 smbol 수를계속적으로줄여나감. 가장작은 smbol 수에서각각코드할당. smbol이줄어든역과정으로코드를추가로할당해나감 /58 허프만부호법 Hffman coding smbol 수를줄이는과정 코드할당과정 /58
허프만부호법 Hffman coding 장점 한번에하나의코드를생성할때최적의코드를생성 이론적인한계치에거의근접 일단코드테이블이구해지면룩업테이블방식으로유일하게부호 / 복호화가가능 block code 특성 : 각 sorce smbol이일정한길이의 code smbol로 mapping 인접하는코드를참조할필요없이개별적인코드만을이용 단점 smbol 수가많을경우코드테이블의구성이어렵다 5 계조의영상의경우 5 단계의 sorce smbol redction과 5단계의 code 할당과정필요 /58 기타가변길이부호법의성능 /58
무손실압축 Error-free compression 산술부호법 Arithmetic coding nonblock code 발생 : 여러 sorce smbol이모여서하나의산술코드를생성 code word는 에서 사이의실수값을가짐 sorce smbol 의길이가길어질수록나타내는실수간격이조밀해지면서산술코드가길어짐 5/58 무손실압축 Error-free compression LZW 부호법 Lempel-Zi-Welch coding 가변길이의 sorce smbol에고정길이의 code word를할당 초기에기본 codebook 생성 : 영상의경우 ~ 55 할당 부호화과정에서연속하는 sorce smbol 들의 code를 codebook 에추가 5 57 등에 Sorce smbol들이 codebook에있으면 codebook내의 code word로대체 LZW 부호법의특징 부호화과정에서 Hffman 과같은사전지식은요구하지않음 부호화를진행하면서 codebook 을계속적으로 pdate gif tiff pdf 등의파일형식에서사용 /58
무손실압축 Error-free compression LZW 부호법의예 7/58 무손실압축 Error-free compression Bit-plane coding 계조영상을이진영상의연속으로분해한후이진영상의압축방법을이용하여영상데이터를압축 각 bit-plane 당압축률을높이는기술이관건 8/58
Bit-Plane Coding Bit-plane 의재구성 일반적인이진영상의경우 low bit에서데이터의변화가매우큼 m-bit gra code 를이용 > bit 의변화를줄임 서로이웃하는화소의경우비슷한값을갖는특성이용 비슷한농도에서비트변화가적어지도록비트를할당 진수 BCD 코드 그레이코드 5 7 8 9 9/58 무손실압축 Error-free compression original image original gra coded original gra coded /58
무손실압축 Error-free compression 런길이부호법 rn-length coding interpiel redndanc를제거하는기법 이진영상의압축방법으로흔히사용 계조영상의각 bit-plane에적용 black white 값의연속적인길이로영상을표현 FAX 전송에사용 bit 의계조영상에적용가능 입력 : 출력 : 5bwb bmp file 의압축용으로사용 /58 무손실압축 Error-free compression 무손실예측부호법 Lossless predictie coding interpiel redndanc를제거하는기법 이전화소로부터얻은정보를이용하여인접화소에서얻은새로운정보만을추출하고이를부호화 새로운정보 : 이전화소로부터예측된값의차이 /58
무손실압축 Error-free compression 무손실예측부호법 Lossless predictie coding 원영상 예측차이영상 히스토그램 차이영상의히스토그램 /58 손실압축 Loss compression 손실압축 압축율을높이기위해손실을허용하며압축하는방법 interpiel coding redndanc pschoisal redndanc 를제거 양자화단계존재 : 무손실압축과차이 Application 디지털 TV : MPEG- 영상회의 영상전화 : H. 정지영상부호와 : JPEG 압축율은 ~ 정도 압축기법 손실예측부호법 Loss predictie coding 변환부호법 Transform coding 계층부호법 Hierarchical coding Hbrid coding waelet coding /58
예측부호법 Predictie Coding 손실예측부호법 Lossl predictie coding 무손실예측부호기에양자화기추가 부호화와복호화기에서같은예측기 predictor 사용 가장잘알려진부호법 - DMDelta Modlation - 가장단순 그외 - ADMAdaptie Delta Modlation - DPCMDifferential Plse Code Modlation - ADPCMAdaptie Differential Plse Code Modlation 최적예측부호법 : DPCM - encoder 의 mean-sqare prediction error 를최소화하는기법 5/58 예측부호법 Predictie Coding 손실예측부호법 Lossl predictie coding 손실예측부호화모델 /58
예측부호법 Predictie Coding DMDelta Modlation 한화소의표현을위해 비트를할당 부호할당방법 - 화상입력신호값과현재값비교 - 입력값이현재값보다높거나같으면부호 할당 - 그외에는 을할당 구현 - 일정한진폭 델타 를정해두고 오차가축적되지않도록지금까지의부호화에의해서얻어진화상값과입력되어오는화상신호와의차인잔차신호에대한부호화를수행 - 부호 에 + delta - 부호 에 delta 값적용 Granlar noise 발생 - 입력영상의변화가없는부분에서발생 Slope oerload 발생 - 입력영상의변화가큰부분에서발생 7/58 예측부호법 Predictie Coding DMDelta Modlation 8/58
예측부호법 Predictie Coding Delta Modlation 의문제점 : 진폭을키울경우 : granlar noise 가커짐 진폭을줄일경우 : slope oerload 가커짐 ADMAdaptie Delta Modlation 진폭 delta 을가변으로처리 입력영상의변화가없는부분 - 진폭 delta 을줄임 - 작은신호를충실하게부호화 - granlar noise 를줄임 입력영상의변화가큰부분 - 진폭 delta 을키움 - 입력신호를빠르게추종 - slope oerload를줄임 9/58 예측부호법 Predictie Coding DPCMDifferential Plse Code Modlation 부호화부의예측에러를최소화하는기법 E{ e n } E{[ f n ˆ f ] } n 최적예측부호법 화상입력과예측신호값의차이를직접이용 /58
DPCMDifferential Plse Code Modlation 예 f ˆ.5 f f ˆ.97 +.5 f Δh f f Δ f f fˆ ˆ.75 f +.75 f.5 f /58.97 f fˆ.97 f if Δ h Δ otherwise 예측부호법 Predictie Coding 양자화예 /58
DPCM 에의한손실압축예 bits/piel bits/piel.5 bits/piel.5 bits/piel bits/piel.5 bits/piel /58 DPCM 에러예 bits/piel bits/piel.5 bits/piel.5 bits/piel bits/piel.5 bits/piel /58
변환부호법 Transform Coding 변환부호화를통한압축 화상정보는대부분직류성분이나저주파성분에집중 영상을주파수성분으로변환 영상의고주파성분에는비트수를적게할당 결과적으로화질에영향을작게미치면서영상을압축 변환부호화기법 영상을정방영역 88 : 블록 으로분할 각블록별로직교변환수행 변환계수생성 각변환기법에따라다른결과 변환계수의영역별로적절한양자화수행 그림 7. 참고 5/58 변환부호법 Transform Coding 전형적인변환부호화시스템 /58
변환부호법 Transform Coding 변환부호법 Transform coding 변환부호법 Transform Coding 변환부호법 Transform coding 변환된계수에양자화를적용하여압축 대부분양자화후부호화를적용하여추가압축 transform kernelbasis fnction 에의해서변환방식결정 g f F h F f 변환부호법의종류 - KLTKarhnen-Loee Transform - DFTDiscrete Forier Transform - DCTDiscrete Cosine Transform WHTW l h H d d T f 7/58 - WHTWalsh-Hadamard Transform 변환부호법 Transform Coding 주요변환부호법 Transform coding 변환부호법 Transform Coding 주요변환부호법 Transform coding Discrete Forier TransformDFT j j e h e g / / + + π π Walsh-Hadamard TransformWHT e h e g + m i i i i i p b p b h g Discrete Cosine TransformDCT π π + + ] ]cos[ cos[ h g π π α α + + for α α 8/58... for
변환부호법 Transform Coding Transform Kernel 의예 Walsh-Hadamard basis fnction for Discrete-cosine basis fnction for 9/58 a difference Approimations sing a Forier b Hadamard d c Cosine b c 88 block 압축율 : rms error: a:.8 b:.8 c:.8 5/58
변환부호법 Transform Coding 변환부호법의 RMS error 비교 Reconstrction error erss sbimage size comparison 5/58 변환부호법 Transform Coding 변환부호법의양자화 변환계수의양자화 F Fˆ rond Z Tpical normalization matri : Z 5/58
변환부호법 Transform Coding 변환부호법 Transform Coding 변환부호법의양자화 5 8 5 5 8 변환부호법의양자화 DCT 예 5 7 8 7 5 7 57 5 5 7 5 8 5 5 8 5 5 57 7 57 57 5 7 5 7 8 7 9 DC component 8 5 57 5 5 57 8 5 57 5 5 5 8 5 9 8 5 5 5 8 5 57 5 7 8 9 5 5 9 5 5 5 8 Original image DCT 5/58 AC component 양자화예 9 양자화예 5 8 5 9 8 5 5 5 7 8 9 5 5 9 5 5 5 8 Qantisation 9 55 58 9 5 77 9 8 5 7 8 8 87 5 9 7 5 9 57 W 87 78 9 9 8 55 5 77 9 8 5 7 8 5/58 99 98 95 9 7 Qantisation Matri
Video 압축기법 Video 압축기법 DPCM 과 DCT VLC 를이용한일반적인영상압축기법 DPCM 과 DCT VLC 를이용한일반적인영상압축기법 55/58 Video 압축기법 Scan Video 압축기법 Scan 양자화이후수행하여 coding redndanc 제거하기위한전처리과정 Zig-Zag scan Alternate scan Zig-Zag scan 5/58 - - -
Video 압축기법 Rn-Length Coding zig-zag 시퀀스를 앞에있는 의개수 이아닌상수 의형태로표현 [ ] 5 Hffman Coding 출현빈도가높은값에적은비트할당 무손실부호화 A Smbol Probabilit Code A.5 B B. C C. 57/58 Video 압축전체과정 9 9 5 5 5 5 5 DCT 7 5 55 9 59 7 Original image or difference between original & predicted images [ 79 ] Rn-Length Code 79 Hffman Code 58/58 Zig-Zag scan... Qantisation / 79