이산 코사인 변환

이 기사는 많은 출처를 잘못 인용하거나 잘못 전달할 수 있습니다.자세한 내용은 정리 페이지를 참조하십시오. 편집자: 이 경고는 [Wikipedia talk: Wikipedia talk: Wikipedia: Wikipedia: Wikipedia:comment/Jagged 85/{{subpage}}여기에]에 대한 요청이 정확한지 확인되었습니다.(2022년 7월)

이산 코사인 변환(DCT)은 다른 주파수로 진동하는 코사인 함수의 합으로 데이터 포인트의 유한 시퀀스를 나타낸다.1972년 Nasir Ahmed가 처음 제안한 DCT는 신호 처리 및 데이터 압축에서 널리 사용되는 변환 기술입니다.디지털 이미지(JPEG나 HEIF 등, 작은 고주파 컴포넌트를 폐기할 수 있는), 디지털 비디오(MPEG나 H.26x 등), 디지털 오디오(Dolby Digital, MP3, AAC 등), 디지털 텔레비전(SDTV, HDTV, VOD 등), 디지털 라디오(DAB+AC 등) 등, 대부분의 디지털 미디어에 사용됩니다.C-LD, 사이렌 및 오퍼스).DCT는 또한 디지털 신호 처리, 통신 장치, 네트워크 대역폭 사용량 감소 및 편미분 방정식의 수치 해법을 위한 스펙트럼 방법 등 과학 및 공학 분야의 수많은 다른 응용 분야에도 중요합니다.

(아래 설명과 같이) 일반적인 신호를 근사하는 데 필요한 코사인 함수가 적은 반면 미분 방정식의 경우 코사인에서 경계 조건의 특정 선택을 나타내기 때문에 사인 함수가 아닌 코사인 함수의 사용은 압축에 중요합니다.특히 DCT는 이산 푸리에 변환(DFT)과 비슷하지만 실수만 사용하는 푸리에 관련 변환입니다.DCT는 일반적으로 주기적 및 대칭적으로 확장된 시퀀스의 푸리에 직렬 계수와 관련이 있는 반면, DFT는 주기적으로 확장된 시퀀스의 푸리에 직렬 계수와 관련이 있습니다.DCT는 (실제 및 짝수 함수의 푸리에 변환이 실제 및 짝수이므로) 대칭을 갖는 실제 데이터에서 작동하는 길이의 약 2배인 DFT와 동등하지만, 일부 변형에서는 입력 및/또는 출력 데이터가 샘플의 절반만큼 이동됩니다.표준 DCT에는 8가지 종류가 있으며, 그 중 4가지가 일반적입니다.

이산 코사인 변환의 가장 일반적인 변형은 Type-II DCT이며, 종종 간단히 "DCT"라고 불립니다.이것이 Ahmed가 처음 제안한 원래의 DCT였다.그것의 역, 타입 III DCT는 종종 단순히 단순히 "역 DCT" 또는 "IDCT"로 불린다.관련된 2가지 변환은 실제 및 홀수 함수의 DFT에 해당하는 이산 사인 변환(DST)과 중복 데이터의 DCT에 기반한 수정 이산 코사인 변환(MDCT)입니다.다차원 DCT(MD DCT)는 DCT의 개념을 MD 신호로 확장하기 위해 개발됩니다.MD DCT 계산에는 몇 가지 알고리즘이 있습니다.DCT 구현의 계산 복잡성을 줄이기 위해 다양한 고속 알고리즘이 개발되었습니다.그 중 하나가 표준 DCT의 ^{[2]: ix, xiii, 1, 141–304} 정수 근사치인 정수 DCT^[1](IntDCT)로, 여러 ISO/IEC 및 ITU-T 국제 ^[1][2]표준에서 사용됩니다.

블록 압축이라고도 하는 DCT 압축은 이산 DCT ^[3]블록 집합으로 데이터를 압축합니다.DCT 블록에는 표준 DCT의 경우 8x8 픽셀, 4x4 ~ 32x32 ^[1][4]픽셀의 다양한 정수 DCT 크기 등 다양한 크기를 사용할 수 있습니다.DCT는 높은 데이터 압축률로 ^[7][8]고품질을 달성할 수 있는 강력한 "에너지 압축"^[5][6] 특성을 가지고 있습니다.그러나 무거운 DCT 압축을 적용하면 블록 압축 아티팩트가 나타날 수 있습니다.

역사

이산 코사인 변환(DCT)은 캔자스 주립대학에서 근무하던 중 Nasir Ahmed에 의해 처음 고안되었으며, 1972년 National Science Foundation에 이 개념을 제안했습니다.그는 원래 이미지 ^[9][1]압축을 위해 DCT를 의도했습니다.아흐메드는 그의 박사과정 학생 T와 함께 실용적인 DCT 알고리즘을 개발했다.1973년 알링턴 텍사스 대학의 Raj Natarajan과 친구 K. Rao가 이미지 ^[9]압축에 가장 효과적인 알고리즘이라는 것을 발견했습니다.그들은 1974년 1월 이산 코사인 ^[5][6][10]변환이라는 제목의 논문에서 그 결과를 발표했다.현재는 타입 II DCT(DCT-II)^{[2]: 51} 및 타입 III 역DCT(IDCT)^[5]라고 불리는 것을 기술하고 있습니다.그것은 벤치마크 ^[11][12]출판물이었고,^[13] 출판 이후 수천 개의 작품에서 근본적인 발전으로 언급되어 왔다.DCT의 발전을 이끈 기초 연구 작업과 사건은 아흐메드의 후속 출판물인 "How I Come Up the Discrete Cosine Transform"^[9]에 요약되어 있다.

1974년에 도입된 이래, ^[10]DCT에 관한 중요한 연구가 행해져 왔다.1977년 천원슝은 C와 함께 논문을 발표했다.해리슨 스미스와 스탠리 C.고속 DCT 알고리즘을 ^[14][10]제공하는 프랄릭.M.J. Narasimha와 A.M. Peterson의 1978년 논문과 B.^[10]G. Lee의 1984년 논문 등이 추가로 개발되었습니다.이 연구 논문은 1974년 Ahmed 원본 논문 및 1977년 Chen 논문과 함께 1992년 JPEG의 손실 이미지 압축 알고리즘의 기초로 공동 사진 전문가 그룹에 의해 인용되었다.^[10][15]

1975년, 존 A.Roese와 Guner S. Robinson은 DCT를 프레임 간 움직임 보상 비디오 코딩에 적용했습니다.그들은 DCT와 고속 푸리에 변환(FFT)을 실험하여 양쪽 모두를 위한 프레임 간 하이브리드 코더를 개발하였고, DCT가 2비트를 필요로 하는 내부 코더에 버금가는 화질로 화상 데이터를 픽셀당 0.25비트로 압축할 수 있는 복잡성을 줄였기 때문에 가장 효율적이라는 것을 발견했다.1픽셀 ^[16][17]수 있습니다.1979년 아닐 K. 자인과 자스완트 R. 자인은 블록 모션 ^[19]보상이라고도 불리는 움직임 보상 DCT 비디오 압축을 ^[18][19]추가로 개발했습니다.이로 인해 Chen은 1981년에 ^[19]모션 보상 DCT 또는 적응 장면 부호화라고 불리는 실용적인 비디오 압축 알고리즘을 개발하게 되었습니다.모션 보상 DCT는 이후 1980년대 ^[20][21]후반부터 비디오 압축의 표준 부호화 기법이 되었습니다.

정수 DCT는 2003년에 도입된 Advanced Video Coding(AVC)^[22][1] 및 2013년에 도입된 High Efficiency Video Coding(HEVC)^[4][1]에서 사용됩니다.정수 DCT는 High Efficiency Image Format(HEIF; 고효율 이미지 포맷)에서도 사용됩니다.HEIF 에서는, 정지 ^[4]화상을 부호화하기 위해서 HEVC 비디오 부호화 포맷의 서브셋을 사용합니다.

DCT 변종인 수정 이산 코사인 변환(MDCT)은 John P. Princen, A.W. Johnson 및 Alan B에 의해 개발되었습니다.1986년 ^[24]프린센과 브래들리의 이전 연구에 이어 1987년 ^[23]서리 대학의 브래들리.MDCT는 Dolby Digital(AC-3),^[25][26] MP3(하이브리드 DCT-FFT ^[27]알고리즘을 사용), Advanced Audio Coding(AAC),^[28] Vorbis(Og)^[29] 등 대부분의 최신 오디오 압축 형식에서 사용됩니다.

이산 사인 변환(DST)은 x=0의 노이만 조건을 디리클레 ^{[2]: 35-36} 조건으로 대체하여 DCT에서 도출되었다.DST는 1974년 Ahmed, Natarajan 및 ^[5]Rao에 의해 DCT 논문에 기술되었다.타입 I DST(DST-I)는 1976년 아닐 K. 자인에 의해 기술되었으며 타입 II DST(DST-II)는 H.B에 의해 기술되었습니다.케크라와 J.K.1978년 ^[30]솔랑카.

Nasir Ahmed는 또한 1995년 뉴멕시코 대학에서 Giridhar Mandyam 및 Neeraj Magotra와 함께 무손실 DCT 알고리즘을 개발했습니다.이를 통해 DCT 기술을 영상의 무손실 압축에 사용할 수 있습니다.원래 DCT 알고리즘을 수정한 것으로, 역DCT 및 델타 변조 요소를 포함합니다.이것은 엔트로피 ^[31]부호화보다 더 효과적인 무손실 압축 알고리즘입니다.무손실 ^[32]DCT는 LDCT라고도 합니다.

적용들

DCT는 신호 ^[33]처리에서 가장 널리 사용되는 변환 기술이며, 데이터 ^[34]압축에서 가장 널리 사용되는 선형 변환 기술입니다.비압축 디지털 미디어와 무손실 압축은 메모리 및 대역폭 요건이 비실용적으로 높았습니다.이는 매우 효율적인 DCT 손실 압축 기술로 ^[7][8]인해 크게 줄어들었습니다. 이는 거의 스튜디오 ^[7]품질의 경우 데이터 압축 비율을 8:1에서 14:1로, 허용 가능한 품질의 ^[8]컨텐츠의 경우 최대 100:1로 달성할 수 있습니다.DCT 압축 표준은 디지털 이미지, 디지털 사진,^[35][36] 디지털 비디오,^[20][37] 스트리밍 미디어,^[38] 디지털 TV, 스트리밍 TV, 주문형 비디오(VOD),^[8] 디지털 ^[25]시네마, HD 비디오(HD 비디오), HD TV(HD TV)^[7][39] 등의 디지털 미디어 테크놀로지에 사용됩니다.

DCT, 특히 DCT-II는 강력한 "에너지 압축"^[5][6] 특성을 가지고 있기 때문에 신호 및 이미지 처리, 특히 손실 압축에 자주 사용됩니다.일반적인 어플리케이션에서는 대부분의 신호 정보가 DCT의 몇 가지 저주파 컴포넌트에 집중되는 경향이 있습니다.강하게 상관된 마르코프 프로세스의 경우, DCT는 카르후넨-뢰브 변환의 압축 효율에 접근할 수 있다(장식적 의미에서 최적).아래에서 설명하듯이, 이것은 코사인 함수에 내포된 경계 조건으로부터 비롯된다.

또한 DCT는 스펙트럼 방법에 의한 편미분 방정식을 푸는 데 널리 사용된다. 여기서 DCT의 다른 변형은 어레이의 양단에서 약간 다른 짝수/홀수 경계 조건에 대응한다.

DCT는 또한 체비셰프 다항식과 밀접하게 관련되어 있으며, 체비셰프 다항식의 시리즈에 의한 임의 함수의 체비셰프 근사에는 예를 들어 클렌쇼-커티스 직교에서 빠른 DCT 알고리즘이 사용된다.

DCT는 멀티미디어 통신 장치의 부호화 표준입니다.이는 비트환율 감소 및 네트워크 대역폭 사용을 ^[1]줄이기 위해 널리 사용됩니다.DCT 압축은 디지털 ^[8]신호에 필요한 메모리와 대역폭을 대폭 줄입니다.

일반 응용 프로그램

DCT는 다음을 포함한 많은 애플리케이션에서 널리 사용됩니다.

DCT 비주얼 미디어 표준

간단히 DCT라고도 하는 DCT-II는 가장 중요한 이미지 압축 ^{[citation needed]}기술입니다.JPEG와 같은 이미지 압축 표준과 H.26x, MJPEG, MPEG, DV, Theora, Daala와 같은 비디오 압축 표준에서 사용됩니다.여기서 N${\displaystyle }$× $(\displaystyle$ N$\times$ N$)$ $블록$의 2차원 DCT-II를 계산하여 양자화하고 엔트로피를 부호화한다.이 경우 N$(\displaystyle$ N$)$은 일반적으로 8이며, DCT-II 공식은 블록의 각 행과 열에 적용됩니다.그 결과 (${\displaystyle 0}$, ${\displaystyle 0}$)$${$displaystyle (0,0)}$ 요소$$$({\displaystyle }$왼쪽 상단)가 DC(주파수 제로) 컴포넌트이며 수직 및 수평 인덱스 값이 증가하는 엔트리가 수직 및 수평 공간 주파수를 더 높게 나타냅니다.

Advanced Video Coding(AVC; 어드밴스드비디오 코딩)에서는 DCT의 ^[2][1]정수 근사치인 IntDCT^[22][1](IntDCT)가 사용됩니다.4x4 및 8x8 정수 DCT 블록을 사용합니다.High Efficiency Video Coding(HEVC; 고효율 비디오 코딩) 및 High Efficiency Image Format(HEIF; 고효율 이미지 포맷)은 4x4 ^[4][1]~32 픽셀의 다양한 정수 DCT 블록 크기를 사용합니다.2019년 현재^[update] AVC는 비디오 콘텐츠의 녹화, 압축 및 배포에 가장 일반적으로 사용되는 포맷으로 비디오 개발자의 91%가 사용하고 있으며,^[47] 다음으로 개발자의 43%가 HEVC를 사용하고 있습니다.

이미지 포맷

이미지 압축 표준	연도	일반적인 응용 프로그램
JPEG[1]	1992	가장 널리 사용되는 이미지 압축[56][57] 표준 및 디지털 이미지 [50]형식입니다.
JPEG XR	2009	오픈 XML 용지 사양
웹P	2010	디지털 이미지의 손실 압축을 지원하는 그래픽 형식입니다.Google이 개발했습니다.
고효율 이미지 포맷(HEIF)	2013	HEVC 압축에 근거한 이미지 파일 형식.JPEG보다 [58]압축을 개선하고 애니메이션 GIF [59]형식보다 훨씬 효율적인 압축을 지원합니다.
BPG	2014	HEVC 압축 기반
JPEG XL[60]	2020	로열티가 필요 없는 래스터 그래픽스 파일 형식.손실 압축과 무손실 압축을 모두 지원합니다.

비디오 형식

비디오 부호화 표준	연도	일반적인 응용 프로그램
H.261[61][62]	1988	비디오 코딩 표준 제품군 중 최초입니다.주로 구식 화상 회의 및 화상 전화 제품에서 사용됩니다.
모션 JPEG(MJPEG)[63]	1992	Quick Time, 비디오 편집, 비선형 편집, 디지털 카메라
MPEG-1 비디오[64]	1993	CD 또는 인터넷 비디오로 디지털 비디오 전송
MPEG-2 비디오(H.262)[64]	1995	방송 애플리케이션, 디지털 텔레비전, HDTV, 케이블, 위성, 고속 인터넷, DVD 비디오 전송에서의 디지털 이미지 저장 및 처리
DV	1995	캠코더, 디지털 카세트
H.263 (MPEG-4 파트 [61]2)	1996	공중전화교환망(PSTN), H.320, ISDN([65][66]Integrated Services Digital Network)을 통한 비디오 텔레포니
고도의 비디오 코딩 (AVC/H.264/MPEG-4)[1][22]	2003	가장 일반적인 HD 비디오 녹화/압축/배포 형식, 인터넷 비디오, YouTube, Blu-ray 디스크, HDTV 방송, 웹 브라우저, 스트리밍 TV, 모바일 디바이스, 소비자 디바이스, Netflix,[46] 비디오 텔레포니, Face[45] Time
테오라	2004	인터넷 비디오, 웹 브라우저
VC-1	2006	Windows 미디어, Blu-ray 디스크
Apple ProRes	2007	프로페셔널 비디오 제작.[54]
WebM 비디오	2010	HTML5에서 사용하기 위해 Google에서 개발한 멀티미디어 오픈 소스 형식입니다.
고효율 비디오 코딩(HEVC/H.265)[1][4]	2013	H.264/MPEG-4 AVC 표준의 새로운 후계 기종으로, 압축 기능이 대폭 향상되었습니다.
다알라	2013	비디오 포맷은 Xiph.org 에서 조사합니다.
AV1[67]	2018	VP10(VP9의 내부 후계자), Daala 및 Thor를 기반으로 하는 오픈 소스 형식으로 YouTube 및 [70][71]Netflix와 같은 콘텐츠[68][69] 공급자가 사용합니다.

MDCT 오디오 표준

일반 오디오

오디오 압축 표준	연도	일반적인 응용 프로그램
돌비 디지털 (AC-3)[25][26]	1991	시네마, 디지털 시네마, DVD, Blu-ray, 스트리밍 미디어, 비디오 게임
적응 변환 음향 부호화(ATRAC)[25]	1992	미니 디스크
MPEG 레이어 III(MP3)[27][1]	1993	디지털 오디오 전송, MP3 플레이어, 휴대용 미디어 플레이어, 스트리밍 미디어
지각 오디오 코드(PAC)[25]	1996	디지털 오디오 라디오 서비스(DARS)
어드밴스드 오디오 코딩(AAC/MP4 오디오)[28][25]	1997	디지털 오디오 배포, 휴대용 미디어 플레이어, 스트리밍 미디어, 게임 콘솔, 모바일 장치, iOS, iTunes, Android, BlackBerry
고효율 어드밴스드 오디오 코딩(AAC+)[72][42]: 478]	1997	디지털 라디오, 디지털 오디오 방송(DAB+),[42] 디지털 라디오 몬다이얼(DRM)
코덱 조리	1998	리얼오디오
Windows Media Audio (WMA)[25]	1999	윈도 미디어
보비스[29][25]	2000	디지털 오디오 배포, 라디오 방송국, 스트리밍 미디어, 비디오 게임, Spotify, Wikipedia
HDC([43]고화질 부호화)	2002	디지털 라디오, HD 라디오
동적 해상도 적응(DRA)[25]	2008	중국 전국 오디오 표준, 중국 멀티미디어 모바일 방송, DVB-H
오퍼스[73]	2012	VoIP,[74] 모바일 텔레포니, WhatsApp,[75][76][77] PlayStation[78] 4
돌비 AC-4[79]	2017	ATSC 3.0, 초고화질 텔레비전(UHD TV)
MPEG-H 3D 오디오[80]

음성 부호화

음성 부호화 표준	연도	일반적인 응용 프로그램
AAC-LD(LD-MDCT)[81]	1999	모바일 텔레포니, VoIP(Voice-over-IP), iOS, Face[45] Time
사이렌[44]	1999	VoIP, 와이드밴드오디오, G.722.1
G.722.1[82]	1999	VoIP, 와이드밴드 오디오, G.722
G.729.1[83]	2006	G.729, VoIP, 광대역오디오,[83] 모바일텔레포니
EVRC-WB[42]: 31, 478]	2007	와이드밴드
G.718[84]	2008	VoIP, 광대역오디오, 모바일텔레포니
G.719[42]	2008	화상회의, 화상회의, 보이스 메일
셀트[85]	2011	VoIP,[86][87] 모바일텔레포니
Enhanced Voice Services(EVS;[88] 확장 음성 서비스)	2014	모바일 텔레포니, VoIP, 광대역 오디오

MD DCT

다차원 DCT(MD DCT)에는 주로 3D DCT-II와 같은 여러 응용 프로그램이 있으며, 여기에는 하이퍼 스펙트럼 이미징 코딩 시스템,^[89] 가변 시간 길이 3-DCT 코딩,^[90] 비디오 코딩 알고리즘,^[91] 적응형 비디오 코딩 및 3D ^[93]압축과 같은 몇 가지 새로운 응용 프로그램이 있습니다.하드웨어, 소프트웨어의 향상과 몇 가지 고속 알고리즘의 도입으로 M-D DCT의 필요성이 급속히 증가하고 있습니다.DCT-IV는 실가 다상 필터링 뱅크,^[94] 래핑 직교^[95][96] 변환 및 코사인 변조 웨이브릿 베이스의 ^[97]신속한 구현에 응용되어 인기를 얻고 있습니다.

디지털 신호 처리

DCT는 디지털 신호 처리에서 매우 중요한 역할을 합니다.DCT를 이용하여 신호를 압축할 수 있다.DCT는 심전도 신호의 압축을 위해 심전도 검사에서 사용할 수 있습니다.DCT2는 DCT보다 압축률이 우수합니다.

DCT는 Digital Signal Processor(DSP; 디지털 신호 프로세서) 및 디지털 신호 처리 소프트웨어에서 광범위하게 구현됩니다.많은 기업이 DCT 기술을 기반으로 DSP를 개발했습니다.DCT는 부호화, 디코딩, 비디오, 오디오, 멀티플렉싱, 제어신호, 시그널링, 아날로그-디지털 변환 등의 응용 프로그램에 널리 사용됩니다.DCT는 HDTV 인코더/디코더 ^[1]칩에도 일반적으로 사용됩니다.

압축 아티팩트

디지털 미디어에서의 DCT 압축의 일반적인 문제는 DCT ^[3]블록에 의한 블록 압축 ^[98]아티팩트입니다.DCT 알고리즘은 고압축이 적용될 때 블록 기반 아티팩트를 일으킬 수 있습니다.DCT는 대부분의 디지털 이미지 및 비디오 코딩 표준(JPEG, H.26x 및 MPEG 형식 등)에서 사용되고 있기 때문에 DCT 기반의 블록 압축 아티팩트는 디지털 미디어에 널리 퍼져 있습니다.DCT 알고리즘에서는, 화상(또는 화상 시퀀스내의 프레임)을, 서로 독립적으로 처리되는 정사각형 블록으로 분할해, 이러한 블록의 DCT를 취해, 그 결과 얻은 DCT 계수를 양자화한다.이 프로세스로 인해 주로 데이터 ^[98]압축률이 높을 때 블록 아티팩트가 발생할 수 있습니다.이것에 의해, 디지털 비디오(MPEG ^[99]형식등)에서 일반적으로 볼 수 있는 「모기 노이즈」효과도 발생할 가능성이 있습니다.

글리치 아트에서는 DCT ^[3]블록이 자주 사용됩니다.아티스트 Rosa Menkman은 글리치 아트,^[100] 특히 JPEG 디지털 이미지 및 MP3 디지털 ^[3]오디오와 같은 대부분의 디지털 미디어 형식에서 볼 수 있는 DCT 블록을 DCT 기반 압축 아티팩트를 사용합니다.또 다른 예는 독일 사진작가 토마스 러프의 JPEG로, 의도적인 JPEG 유물을 사진 스타일의 ^[101][102]기초로 사용한다.

비공식 개요

다른 푸리에 관련 변환과 마찬가지로 이산 코사인 변환(DCT)은 주파수 및 진폭이 다른 사인파 합계의 관점에서 함수 또는 신호를 나타냅니다.이산 푸리에 변환(DFT)과 마찬가지로 DCT는 한정된 수의 이산 데이터 포인트에서 함수에서 작동합니다.DCT와 DFT의 분명한 차이점은 코사인 함수만 사용하는 반면 코사인 함수와 사인(복잡한 지수 형식)은 모두 코사인 함수만 사용한다는 것입니다.그러나 이러한 가시적인 차이는 단지 더 깊은 구별의 결과일 뿐이며, DCT는 DFT 또는 다른 관련 변환과 다른 경계 조건을 암시한다.

DFT, DCT 또는 푸리에 시리즈와 같이 유한 도메인에 걸친 함수에서 작동하는 푸리에 관련 변환은 해당 함수의 확장을 도메인 외부에서 암묵적으로 정의하는 것으로 간주할 수 있습니다.즉, 함수 $x)$ {$displaystyle$ f$(x)}$를 사인파의 합으로 쓰면 $원래{\displaystyle }$ f$)$ {$displaystyle$ f$(x)}$가 지정되지 않은$$x$${$displaystyle$ x$}$에 $대해서도{\displaystyle }$ 그 합계를 $평가$할 수 있습니다.DFT는 푸리에 급수와 마찬가지로 원래 함수의 주기적 확장을 의미합니다.DCT는 코사인 변환과 마찬가지로 원래 함수의 짝수 확장을 의미합니다.

단, DCT는 유한 이산 시퀀스로 동작하기 때문에 연속 코사인 변환에는 적용되지 않는2가지 문제가 발생합니다.우선, 함수가 도메인의 왼쪽과 오른쪽 경계(즉, 아래 정의에서 각각 최소 n과 최대 n 경계)에서 짝수인지 홀수인지를 지정해야 한다.둘째, 함수가 짝수인지 홀수인지를 지정해야 한다.특히 간격이 동일한 4개의 데이터 점의 시퀀스 abcd를 고려하여 짝수 왼쪽 경계를 지정했다고 가정합니다.데이터가 샘플a에 관한 것이거나 짝수 내선번호가 dcbabcd인 경우 또는 짝수 내선번호가 dcbaabcd(a가 반복되는 경우)와 이전 포인트 사이의 중간쯤에 있는 경우입니다.

이러한 선택은 DCT의 모든 표준 변형과 이산 사인 변환(DST)으로 이어집니다.각 경계는 짝수 또는 홀수일 수 있으며(경계당 2개 선택) 데이터 지점 또는 두 데이터 지점 사이의 중간 지점(경계당 2개 선택)에 대해 대칭이 될 수 있으며, 총 2 × 2 × 2 = 16개의 가능성이 있다.이러한 가능성의 절반(왼쪽 경계가 짝수인 경우)은 8가지 유형의 DCT에 해당하고 나머지 절반은 8가지 유형의 DST에 해당합니다.

이러한 서로 다른 경계 조건은 변환의 적용에 큰 영향을 미쳐 다양한 DCT 유형에 고유하게 유용한 속성으로 이어집니다.가장 직접적으로, 푸리에 관련 변환을 사용하여 스펙트럼 방법으로 편미분 방정식을 풀 때, 경계 조건은 해결 중인 문제의 일부로 직접 지정됩니다.또는 MDCT(type-IV DCT에 근거)의 경우 경계조건은 MDCT의 중요한 속성인 시간 도메인 에일리어스 취소와 밀접하게 관련되어 있습니다.보다 미묘한 방법으로 경계조건은 DCT를 이미지 및 오디오 압축에 유용하게 만드는 "에너지 콤팩트화" 속성을 담당합니다. 왜냐하면 경계조건은 푸리에 계열의 모든 수렴속도에 영향을 미치기 때문입니다.

특히 함수의 불연속성은 푸리에 급수의 수렴 속도를 감소시키기 때문에 주어진 정확도로 함수를 표현하기 위해 더 많은 사인파가 필요하다는 것은 잘 알려져 있다.같은 원리로 DFT 및 기타 변환의 신호 압축에 대한 유용성을 결정합니다. 함수가 부드러울수록 DFT 또는 DCT에서 정확하게 표현하기 위해 필요한 용어가 적어지고 압축할 수 있는 용어가 많아집니다.(여기서 DFT 또는 DCT는 그 '평활성'을 설명하기 위해 각각 함수의 푸리에 급수 또는 코사인 급수에 대한 근사치라고 생각한다.)단, DFT의 암묵적인 주기성은 보통 경계에서 불연속성이 발생한다는 것을 의미합니다.신호의 임의의 세그먼트는 왼쪽 경계와 오른쪽 경계 모두에서 같은 값을 가질 가능성이 거의 없습니다.(DST에서도 같은 문제가 발생합니다.여기서 홀수 왼쪽 경계 조건은 그 경계에서 제로가 되지 않는 함수의 중단을 의미합니다).반대로, 양쪽 경계가 짝수인 DCT는 (일반적으로 경사가 불연속적이긴 하지만) 경계에서 연속 확장을 산출합니다.따라서 DCT, 특히 타입 I, II, V 및 VI의 DCT(2개의 짝수 경계가 있는 타입)는 일반적으로 DFT 및 DST보다 신호 압축에 대해 뛰어난 성능을 발휘합니다.실제로, 타입 II DCT는 부분적으로 계산 편의상의 이유로 그러한 애플리케이션에 일반적으로 선호된다.

형식적 정의

형식적으로 이산 코사인 변환은 선형 $역함수{\displaystyle }$f : ${\displaystyle {}^{}}$ N$$ ${\displaystyle {}^{}}$ N {\$style$ f$:\mathbb {R} ^{N}\to$ \$mathbb {R} ^{N$}}($$$여기$서 R$\displaystyle$ \$mathbb {R}$은 실수의 집합을 나타내거나 등가역 N × N 행렬)이다.정의가 약간 변경된 DCT에는 몇 가지 종류가 있습니다.N개의 ${\displaystyle 실수{}_{}}$ ${\displaystyle {x\mathrm{}}_{}}$0 , ${\displaystyle \text{...}{x}_{}}$N -${\displaystyle {}_{}}{\displaystyle 1_{}}$ (\$displaystyle ~x_{0} ,\ldots \x_{N-1}$ ~ )은 다음 중 하나의 공식에 따라 N개의 ${\displaystyle {실수\mathrm{}}_{}}$X 0${\displaystyle }$, ${\displaystyle ...}$ ,${\displaystyle X_{}}$ ${\displaystyle {\mathrm{N}}_{}}$- 1 (\$displaystyle X_{$0} ,\$ldots$,$X_${N-1$$$}$ 로 변환됩니다.

DCT-I

${\displaystyle X_{k}=black {1}{2}}(x_{0}+(-1)^{k}x_{N-1}+\sum _{n=1}^{N-2}x_{n}\cos \left[,{\frac {pi }{,N-1,k},\right]\qquad {text{~k=0,\ldots\n-1~}.$

일부 작성자는 x$$(\$displaystyle$x_$${0}) 및 ${\displaystyle {\mathrm{x}}_{}}$ - 1(\displaystyle $x_{N-1$$$$$$})$ $항$에$$2를${\displaystyle \sqrt{}}$곱하고 X 0$(\$$displaystyle X_{0})$$및$ ${\displaystyle X_{}}$${\displaystyle {N\mathrm{}}_{}}$ - $(\$$displaystyle$ $X_{N-1})$ $항$에$2$를 곱합니다$.$$qrt$${2,}},},},},$ DCT-I 행렬을 직교하게 $만듭니다.$ 이때 2N${\displaystyle \sqrt{\frac{}{}}}$-${\displaystyle \sqrt{\frac{}{}}\sqrt{\frac{1}{}}}$의 $전체{\displaystyle \sqrt{\frac{\mathrm{}}{}}}$ 스케일 계수를 더 곱하면 {{$sqrt {\tfrac${2}{$N-1,}}}},$ 그러나$$ 실제 짝수 DFT와의 직접적인 대응은 깨집니다.

DCT-I는 대칭이 짝수인 DFT $2{\displaystyle \mathrm{}(N}$-${\displaystyle 1}$) {$displaystyle$ 2$(N-1)}$ 실수와$$ 정확히 동일합니다.예를 들어, $DCT-I$의 N $=$ ${\displaystyle 5}$({$displaystyle$ N$=5}$$실수$ a ${\displaystyle \text{b}}$ $displaystyle$ a$\b\d\e})$$$는 ${\displaystyle \text{8개}}$의 ${\displaystyle \text{실수}}$ a b c ${\displaystyle \text{d}}$ ${\displaystyle \text{c}}$ b \ $display a$\ $c \ d$ \ d $\$b \ d \ b \ d \ b )의 DFT와 정확하게 동등합니다(짝수 2개의 대칭으로 나눗셈).(반대로 DCT 타입 II-IV는 동등한 DFT에서 반표본 이동을 수반합니다.)

단, DCT-I는 2보다 작은N$(\displaystyle$ N$)$에 정의되어 있지 않습니다.다른 모든 DCT 타입은 임의의 $양$의 N$.\displaystyle$ N$.$에 정의되어 있습니다.

따라서 DCT-I는 경계 조건에 해당합니다. ${\displaystyle x_{}}$ $n{\displaystyle {}_{}}$ ${\$은 짝수 n ${\displaystyle =}$ $(\displaystyle$ n$=$${\displaystyle 0}$$},$ n ${\displaystyle {}_{}}$ 1$(\displaystyle$ n$=N-1$입니다.${\displaystyle X_{}}$ k$$. \ $displaystyle X_{k$} 에서도 마찬가지입니다.$}$

DCT-II

${\displaystyle X_{k}=\sum _{n=0}^{N-1}x_{n}\cos \left[, {\tfrac {1}{2}}\right}\qquad {{{\frac {1}{2}\right}\qquad {{{k=0,\1} n}\cos \left}.$

DCT-II는 아마도 가장 일반적으로 사용되는 형식이며, 종종 간단히 "DCT"^[5][6]라고 불립니다.

이 변환은 짝수 색인이 0인 대칭의 DFT $(\$style $4N)$과 정확히 동등합니다($전체$ 스케일 팩터 2까지).즉, $(\$$displaystyle$ $4N)$ $입력$ ${\displaystyle {yn}_{}}$ {${\displaystyle {displaystyle\mathrm{}}_{}}$ ${\displaystyle {\mathrm{y\_}}_{}}${$n$$})$의 절반입니다$.$ 여기서 y 2n $=$ 0$,$ {$displaystyle y_${2n} ${\displaystyle {=}_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle {}_{}}$ x$$(\$displaystyle y_{2n+$1} $= x_n$$})$은0, n$displaystyle$ 0, 0)에 대해 됩니다$.$$N}=0,}$ $및$ y ${\displaystyle 4_{}}$N - ${\displaystyle n_{}}$$=$ ${\displaystyle y_{}}$n < >0 의 . (\ $displaystyle$ $0$$< 2 N$. $n$. } DCT-II 변환은 2N 신호 뒤에 1/2 시프트 곱셈을 사용하여도 가능합니다$.$이것은 막홀에 의해 증명되었다.

일부 저자는 X $({$$style$ X_${$$0})$ $항$에${\displaystyle }$1/$2를$곱하고 결과 행렬에 2$({${{$2}/{N}}})$을 곱합니다(아래 DCT-II의 해당 변경 내용은 아래 참조).이것에 의해, DCT-II 행렬이 직교하게 됩니다만, 반시프트 입력의 리얼 짝수 DFT와의 직접적인 대응이 끊어집니다.이것은 Matlab에서 사용하는 정규화입니다. 예를 들어,^[103] 을 참조하십시오.JPEG와 같은 많은 애플리케이션에서 스케일 팩터는 후속 계산 단계(예를 들어 JPEG의 양자화^[104] 단계)와 결합될 수 있고 DCT를 더 적은 ^[105][106]곱셈으로 계산할 수 있는 스케일링을 선택할 수 있기 때문에 스케일링은 임의입니다.

DCT-II는 경계 조건을 의미합니다. ${\displaystyle x_{}}$n { $displaystyle$ x$_$ { $n$} 은$$ n = 1 $/$2${\displaystyle }$의 $짝수$이고 n ${\displaystyle =}$ ${\displaystyle N}$-${\displaystyle }1{\displaystyle }$ 의 짝수이고$,$ n$$=$N$- $2$의 짝수인 $x$${\displaystyle {}_{}}$ k $k$$= 0 style$ $X _$ { k$$} 는$$ $짝수$입니다$.$$}$

DCT-III

${\displaystyle X_{k}={1}/{2}x_{0}+\sum _{n=1}{N-1}x_{n}\cos \left[,\tfrac {,\pi }{N}}\left(k+{\frac {1}{2}}\right})\qad={n}\cos \left]$

이것은 DCT-II의 역수이기 때문에(최대 스케일 팩터, 아래 참조), 이 형태는 간단히 "역 DCT"("IDCT")^[6]라고 불립니다.

일부 저자는 x $표시$ 스타일 $~x_{0}~)$ ${\displaystyle 용어}$를 2가 아닌 2$($스타일 {$2,})$로 나누고($전체{\displaystyle {}_{}}$ ${\displaystyle {x\mathrm{}}_{}}$ 0${\displaystyle {}_{}}$/ $($ 스타일 $x_{0}/{\sqrt {2}})$ 결과$$ 매트릭스에 2$N$의 $전체\sqrt{\mathrm{}}$ 축척 배율을 곱합니다. {{qrt} {{n}) {{\sqrt} {{}}} {n} {{}}}}}$$ (DCT-II의 대응변화에 대해서는 상기 참조) DCT-II와 DCT-II가 서로 전치되도록 한다.이것에 의해, DCT-II 행렬이 직교하게 됩니다만, 반시프트 출력의 리얼 짝수 DFT와의 직접적인 대응이 끊어집니다.

DCT-III는 경계 조건을 의미합니다. ${\displaystyle x_{}}$n {\$displaystyle$$x_{$$n$}은$$ n ${\displaystyle =}$$0$$주변$이고 n $=$은 홀수입니다$.$ x $(\$k$$}는 k${\displaystyle =}$ ${\displaystyle 1\mathrm{}}$ / ${\displaystyle 2\mathrm{}}${\$displaystyle$ k= {$1/})$는 k ${\displaystyle =}$ ${\displaystyle 1}$ / 2 $근처$입니다.$=N-{1}/{$$2}.$$}$

DCT-IV

$\displaystyle X_{k}=\sum _{n=0}^{N-1}x_{n}\cos \left[, {\tfrac {,\pi }{N}},\left(n+{\frac {1}{2}}\right)\left(k+{\frac {2}}{{2}}}\right}\q},\q},\cos\left},\left({text},\q},\text},\cos\left},\text},\left$

DCT-IV 행렬은 2$\sqrt{/}\sqrt{N}$의 $전체\sqrt{\mathrm{}}$ 스케일 팩터를 더 곱하면 직교(명확히 대칭이며 자체 역)가 됩니다$.$ {\$textstyle {2/N,}.$$}$

다른 변환으로부터의 데이터가 중복되는 DCT-IV의 변형은 Modified Discrete Cosine Transform(MDCT;^[107] 수정 이산 코사인 변환)이라고 불립니다.

DCT-IV는 ${\displaystyle {경계}_{}}$ 조건을 의미합니다. ${\displaystyle x_{}}$n {\$displaystyle$ x_${$$n$$}$은(는) n ${\displaystyle =1\mathrm{}}$ /$$ $근처$이고 n $=$$/$${\displaystyle 2\mathrm{}}$ $근처$는 홀수입니다$.$ $X$$k$ .$${ $style x_k$$}$。$}$

DCT V-VII

타입 I-의 DCTIV는 대칭점에 대해 두 경계를 일관되게 처리합니다. 즉, 두 경계에 대한 데이터 점 주위에서 짝수/홀수이거나 두 경계에 대한 두 데이터 점 사이의 중간입니다.반면 V-VII 유형의 DCT는 한쪽 경계에 대해서는 데이터 점 주위에 짝수/홀수이고 다른 한쪽 경계에 대해서는 두 데이터 점 사이의 중간인 경계를 의미한다.

즉, DCT 타입 I~IV는 대응하는 DFT의 $길이$가 2$N$ - 1$)($DCT-I의 경우$$) $또는{\displaystyle \mathrm{}}$ $(Display$ $style$ $4N($DCT-I의 $경우{\displaystyle \mathrm{}}$) 또는 8N(DCT-II의 경우)이므로 짝수 순서(N\displaystyle$$N\ $display style$ 2$(N-1).$4가지 유형의^[108] 이산 코사인 변환은 기본적으로 논리적으로 홀수 차수의 실제 짝수 DFT에 대응하며, 코사인 인수의 분모는 N${\displaystyle }$± ${\displaystyle 1\mathrm{}}$/$(\$ N$\pm {1}/{2})$입니다.

그러나 이러한 변형은 실제로 거의 사용되지 않는 것으로 보인다.한 가지 이유는 홀수 길이 DFT의 FFT 알고리즘이 일반적으로 짝수 길이 DFT의 FFT 알고리즘보다 더 복잡하기 때문일 수 있으며(예를 들어 가장 단순한 기수-2 알고리즘은 짝수 길이에만 해당), 이러한 복잡성이 증가하여 다음과 같이 DCT로 전달됩니다.

(단일 번호 a의 길이 1의 DFT(홀수 길이)인 일반 짝수 배열은 $길이{\displaystyle }$ N ${\displaystyle =}$ 1${\displaystyle \mathrm{.}}${$displaystyle$ N$=1$의 DCT-V에 해당합니다).

역변환

위의 정규화 규칙을 사용하면 DCT-I의 역수는 DCT-I에 2/(N - 1)를 곱한 것입니다.DCT-IV의 역수는 DCT-IV에 2/N을 곱한 값입니다.DCT-II의 역수는 DCT-III에 2/N을 곱한 값이며,^[6] 그 반대도 마찬가지입니다.

DFT와 마찬가지로, 이러한 변환 정의 앞에 있는 정규화 계수는 단지 관례일 뿐이며 처리마다 다릅니다.예를 들어 일부 저자는 변환에 2$(\$을 곱하여 역수가 추가 곱셈 인수가 필요하지 않도록 합니다.δ2(위 참조)의 적절한 인자와 결합하면 변환 행렬을 직교하는 데 사용할 수 있습니다.

다차원 DCT

다양한 DCT 유형의 다차원 변형은 1차원 정의에서 쉽게 따라갑니다. 즉, 각 차원을 따라 DCT의 분리 가능한 산물(등가적으로 구성)입니다.

M-D DCT-II

예를 들어 화상 또는 매트릭스의 2차원 DCT-II는 단순히 위에서 행에 따라 행에 따라 수행된 1차원 DCT-II이다(또는 그 반대).즉, 2D DCT-II는 다음과 같은 공식으로 표시됩니다(위의 정규화 및 기타 스케일 계수는 제외).

${\displaystyle {begin {1}X_{1},k_{2}}=0}{N_{1}-1}\left(\sum _ {n_{2}=0}{N_{2}-1}x_{n_{1},n_{2}}\cos[\fr}\&=\sum _{n_{1}=0}^{N_{1}-1}\sum _{n_{2}=0}^{N_{2}-1}x_{n_{1}x_{n_{1}\cos \left[{\frac {pi}{N_1}\left(n_{1}){{{1}}\frc}{{frc}{1}{fr1}\end { aligned}}$

다차원 DCT의 역수는 해당하는 1차원 DCT의 역수(위 참조)의 분리 가능한 산물일 뿐이다. 예를 들어 행-열 알고리즘에서 한 번에 한 차원을 따라 적용되는 1차원 역수이다.

3-D DCT-II는 3차원 공간에서 2-D DCT-II의 확장일 뿐이며 수학적으로 다음 공식으로 계산할 수 있습니다.

$({displaystyle X_{1},k_{2},k_{3}}=\sum _{n_{1}=0}^{N_{1}=0}^{N_{2}-1}\sum _{n_{3}=0}^{n_{1}_{n}_{n}_{1}\sumt)k_{3}\right],\text{for}k_{i}=0,1,2,\text,N_{i}-1.}$

3-D DCT-II의 역수는 3-D DCT-II이며, 다음 공식에서 계산될 수 있다.

$({displaystyle x_{1},n_{2},n_{3}}=\sum _{k_{1}=0}^{N_{1}-1}\sum _{k_{2}=0}^{N_{2}-1}\sum _{k_{3}=0}^{K_{1}_{1},{k_{1}_{k_{1}_{1}_{k_{1}})t)k_{3}\right],\text{for}n_{i}=0,1,2,\text,N_{i}-1.}$

기술적으로 각 차원을 따라 1차원 DCT의 시퀀스에 의해 2, 3차원(또는 -다중) 차원 DCT를 계산하는 것을 행-열 알고리즘이라고 한다.그러나 다차원 FFT 알고리즘과 마찬가지로 다른 순서로 계산을 수행하면서 동일한 것을 계산하는 다른 방법이 있습니다(즉, 다른 차원에 대한 알고리즘의 인터리빙/결합).3-D DCT를 기반으로 한 애플리케이션의 빠른 성장으로 인해, 3-D DCT-II의 연산을 위해 몇 가지 빠른 알고리즘이 개발되었습니다.벡터 기수 알고리즘은 M-D DCT 계산에 적용되어 계산 복잡성을 줄이고 계산 속도를 높인다.3D DCT-II를 효율적으로 계산하기 위해 고속 알고리즘인 Vector-Radix Decimation in Frequency(VR DIF) 알고리즘이 개발되었습니다.

3D DCT-II VR DIF

VR DIF 알고리즘을 적용하기 위해 입력 데이터를 다음과 ^[109][110]같이 공식화 및 재배치한다.변환 크기 N × N × N은 2로 가정한다.

${\displaystyle {\tilde {x}(n_{1}, n_{2}, n_{3})=x(2n_{1}, 2n_{2}, 2n_{3}\{\tilde {x}(n_1}, n_{2})=x_{1}, n_{2}, n_{2}, n_{2}, n_{n}, n_{1}, n_{n}, n_{1},\tilde {x}(N-n_{1}-1,n_{2},N-n_{3}-1)=x(2n_{1}+1,2n_{2}+1)\{\tilde {x}(N-n_{1}-1,N-{2}={n})$

$여기$서 0${\displaystyle {}_{}}$ n${\displaystyle {}_{}{1\mathrm{}}_{}}$, ${\displaystyle {}_{}{}_{}}$2, n ${\displaystyle {3\mathrm{}}_{}n\frac{}{}}$ ${\displaystyle \frac{\mathrm{N}}{}}$2 -$$ (\$displaystyle$0\$leq n_{1}, n_{2}, n_{3}\leq {Frac {N}$ {$2}}-1)$

옆의 그림은 VR DIF 알고리즘을 사용한3D DCT-II 계산에 관여하는4가지 단계를 나타내고 있습니다.첫 번째 단계는 위의 공식에서 설명한 인덱스 매핑을 사용한 3-D 순서 변경입니다.두 번째 단계는 나비 계산입니다.각 나비는 아래 그림과 같이 8개의 점을 함께 계산합니다.$여기$서 c${\displaystyle }$( ${\displaystyle i_{}}$i ) ${\displaystyle =}$ ${\displaystyle \cos }$ ${\displaystyle (}$ ( ${\displaystyle {\phi }_{}}$i$$) \ $displaystyle$ c ( \ $varphi$_ { i } = \ $cos$( \ $varphi$_ { $i$} )$$。

원래의 3D DCT-II는 다음과 같이 기술할 수 있습니다.

$({displaystyle X(k_{1},k_{2},k_{3})=\sum _{n_{1}^{N-1}\sum _{n_{2}=1}^{N-1}{\tilde {x}}{{n}_{3}=\sum _{n})$

$여기$서, } i ${\displaystyle {}_{}}$ ${\displaystyle \frac{n}{}}$2 ${\displaystyle \mathrm{N}}$ ( ${\displaystyle 4_{}\mathrm{N}}$ i + 1)${\displaystyle 및}$ i ${\displaystyle =1}$,${\displaystyle \mathrm{2,}}$3.$$({ $displaystyle$\$varphi$_ { i } =$spi$ frac { 2$$N$}$（ 4 $N$_ { $i$} + $1$） 、 \$text$ { }$= 1, 2$, 3$$} 。

${\displaystyle {k1\mathrm{}}_{}}$ $({$ 및$$ $({$의 짝수 부분과 홀수 부분을 고려하면 3-D DCT-II의 계산 공식은 다음과 같이 나타낼 수 있다.

$({displaystyle X(k_{1},k_{2},k_{3})=\sum _{n_{1}^{{\tfrac {N}{2}=1}^{{{\tfrac {N}-1}\sum {n_{1}{{{nfrac {1}){{{{1}}{{nFR}{{{{{{{}}}}}}{{{{{{}}}}}}{{{{{{{{}}}}}}}}}}}{{{{{{{{}}}}$

어디에

${{displaystyle {x}_{ijl}(n_{1},n_{2},n_{3})=sqtilde {x}(n_{1},n_{2},n_{3})+(-1)^{l}{x}\left(n_{1},n_{2},n_{3}) {right} {x}}$

$\ displaystyle +(-1)^{j}{\tilde {x}\left(n_1},n_{2}+{\frac {2}+{3}\right)+(-1)^{j+l}{\tilde {x}\left(n_{1}+{2}},n_{\frac {2}}{\frac}{n}{\frac}{2}+}$

${{displaystyle +(-1)^{i}{\tilde {x}}\left(n_{1}+{\frac {2}+{\frac {3}\right)+(-1)^{i+j}{x}\left(n_{1}+{2}}+{frac}{n}, {frac}{frac}{2}\frac}{n}, {2}\frac}, {frac}, {frac}$

${{displaystyle +(-1)^{i+l}{\tilde {x}}\left(n_{1}+{\frac {n}{2}},n_{3}+{\frac {n}{3}}}\right}}}$

$\displaystyle +(-1)^{i+j+l}{\tilde {x}\left(n_{1}+{\frac {n}{2}},n_{3}+{2}}\right}{\text},ij,l={text}}}},{\text}}}},{\text}}}},{\text}}}}}}},{n_{{{\text}}}}}}}}}}}}}}}}}}}}}}}},{i}},{}$

산술 복잡도

전체 3-D DCT 계산에는 [${\displaystyle {log\mathrm{}}_{}}$ 2${\displaystyle {}_{}n}$ N$]$ {$displaystyle ~[\log$ _${2}N]~}$개의$$ 단계가 필요하며${\displaystyle ,}$ 각 단계에는 ${\displaystyle \frac{18}{}}$ $displaystyle ~{\tfrac {1}{8}}\N^{3}~})$의 나비가 ${\displaystyle 포함}$됩니다.3D DCT 전체를 계산하려면 [${\displaystyle \frac{1}{}}$ ${\displaystyle 8{}^{}}$ N ${\displaystyle 3_{}}$ ${\displaystyle {log\mathrm{}}_{}}$ 2${\displaystyle {}_{}n}$ N${\displaystyle }$] { $displaystyle ~\left$[ { \ $tfrac {1}$ {$8}$ \ $N^{3}$ \ $log$_ {2$}$ N \ $right$]~}의$$ 나비가 필요합니다${\displaystyle .}$각 나비에는 7개의 실수 곱셈(소수 곱셈 포함)과 24개의 실수 덧셈(소수 덧셈 포함)이 필요하다.따라서 이 단계에서 필요한 실제 곱셈의 총수는 [${\displaystyle \frac{7}{}}$ ${\displaystyle 8{}^{}}$ ${\displaystyle {N\mathrm{}}^{}}$ ${\displaystyle 3_{}{}^{}{}_{}}$ ${\displaystyle {log\mathrm{}}_{}}$ 2${\displaystyle {}_{}n}$ N$],$ {\$displaystyle ~\left[{\tfrac {7}}\N^{3}\log$ _${2}N\right]~,}$이며${\displaystyle ,}$ 덧셈 후 직접 계산할 수 있는 실제 덧셈의 총수는 다음과 같다.단계 또는bit-reverse 무대 후 ⏟ 레알+[32N3통나무 2⁡ N− 3N3+3N2]⏟ Recursive)[92N3통나무 2⁡ N− 3N3+3N2].{\displaystyle ~\underbrace{\left[{\frac{3}{2}}N^{3}\log_{2}N\right]}_{\text{R.by[110][32N3통나무 2⁡ N] 주어진다eal}$}+\underbrace {\frac {3}{3}\log _{2}N-3N^{3}+3N^{2}\right]}_{\text {Recursive}=\left[{\frac {9}{2}}N^{3}\log_3-N}{3-}{\right]$$}$

MD-DCT-II를 계산하는 기존 방법은 RCF(Row-Column-Frame) 방식을 사용하는 것으로, 계산은 복잡하고 최신 최신 하드웨어 플랫폼에서는 생산성이 떨어집니다.VR DIF 알고리즘을 계산하는 데 필요한 곱셈 수는 RCF 알고리즘에 비해 상당히 많습니다.RCF 접근법에 관련된 증배 및 추가 수는 [${\displaystyle \frac{3}{}}$ ${\displaystyle 2{}^{}}$ N ${\displaystyle 3_{}}$ ${\displaystyle {log\mathrm{}}_{}}$ $2$N$$]({\$displaystyle {3}\log$ _${2}N\right]~)$ 및$$${\displaystyle }$[${\displaystyle \frac{9}{}}$ ${\displaystyle {2\mathrm{}}^{}}$ N ${\displaystyle 3_{}}$ -${\displaystyle {}^{}}$ ${\displaystyle {}^{}{}_{}}$3${\displaystyle {}^{}}$+ $DISPLAY$2$]($왼쪽$)$로 표시됩니다$.$각각 다음과 같다.표 1에서 총 숫자는 다음과 같습니다.

1 계산을 DIF 과 RCF 3D-DCT-II 1개

" " "	VR 3D VR »	RCF " "	에 3D VR 추가 ★	가 RCF를 추가하다
× 8 × 8 × 8	2.625	4.5	10.875	10.875
× × 16 × 16	3.5	6	15.188	15.188
× × 32 × 32	4.375	7.5	19.594	19.594
× × 64 × 64	5.25	9	24.047	24.047

3D DCT VR 알고리즘과 관련된 곱셈이 RCF 접근법에 관련된 곱셈보다 40% 이상 적다.또한 RCF 접근 방식에는 매트릭스 전치 및 새로운 VR 알고리즘보다 더 많은 인덱싱 및 데이터 스와핑이 포함됩니다.따라서 3D DCT VR 알고리즘은 비디오 압축 및 기타 3D 이미지 처리 응용 프로그램 등 3D DCT-II를 사용하는 3D 응용 프로그램에 보다 효율적이고 적합합니다.

빠른 알고리즘을 선택할 때 고려해야 할 주요 사항은 계산 및 구조적 복잡성을 피하는 것이다.컴퓨터와 DSP의 기술이 발전함에 따라 산술 연산의 실행 시간(곱셈과 덧셈)이 매우 빨라지고 있으며, 정기적인 연산 구조가 가장 중요한 ^[111]요소가 되고 있다.따라서 위에서 제안한 3D VR 알고리즘은 곱셈 수에 ^[112]대한 이론적 하한을 달성하지는 못하지만 다른 3D DCT 알고리즘에 비해 계산 구조가 단순합니다.단일 접영을 사용하여 제 위치에 구현할 수 있으며, 쿨리의 특성을 보유한다.터키 FFT 알고리즘(3D).따라서 3-D VR은 나비 스타일의 쿨리 특성을 갖는 단순한 구조를 유지하면서 3-D DCT-II 계산 시 산술 연산을 줄이는 데 좋은 선택입니다.터키 FFT 알고리즘.

오른쪽 이미지는 8 × ${\displaystyle }$8 (${\displaystyle {N\mathrm{}}_{}}$ 1 $=$ ${\displaystyle {N\mathrm{}}_{}}$ 2 $=$ $){style$ (~$N_{1$}=$N_{2$}=$8~})$ 2차원$$ DCT의 수평 및 수직 주파수 조합을 보여줍니다.왼쪽에서 오른쪽으로, 위에서 아래로 각 단계는 주파수가 1/2 사이클씩 증가합니다.예를 들어 왼쪽 위 사각형에서 오른쪽 사각형으로 이동하면 수평 주파수가 반주기 증가합니다.오른쪽으로 한 번 더 이동하면 두 번의 반주기가 생성됩니다.아래로 이동하면 수평으로 두 개의 하프 사이클과 수직으로 두 개의 하프 사이클이 생성됩니다.소스 데이터(8×8)는 이러한 64개 주파수 사각형의 선형 조합으로 변환됩니다.

MD-DCT-IV

M-D DCT-IV는 M차원 도메인에 대한 1-D DCT-IV의 확장일 뿐입니다.매트릭스 또는 이미지의 2-D DCT-IV는 다음과 같습니다.

$}= _ _,m \left=,{4displaystylex_{k_{n,\ell}_{n,\ell}N}}\cos \left(\frac {,(2n+1)(2\ell +1)\pi \,}{4M}\right)~,}$

${\displaystyle k}$ ${\displaystyle =}$ ${\displaystyle 0,\text{1}\mathrm{}}$,${\displaystyle \text{2}\mathrm{}}$ …${\displaystyle \text{N}}$ -${\displaystyle }{\displaystyle 1}$ { $displaystyle$~ ~k$$=$0$, \ 1$,$ $\ 2 \ldots$\ $N-1$ ~$$} 및$$ } ${\displaystyle =0}$ ,${\displaystyle \text{1}\mathrm{}}$ ,${\displaystyle }$2 . ${\displaystyle \text{M}}$-${\displaystyle 1}$ .$$\ $displaystyle$ ~ ~ ~\$ell$=$0$, \ 1, \ 2$,$ $\ldots$\$M-1$ ~$$} 。

MD DCT-IV를 정규 행-열 방법을 사용하여 계산하거나 다항식 변환^[113] 방법을 사용하여 빠르고 효율적인 계산을 수행할 수 있습니다.이 알고리즘의 주요 아이디어는 다차원 DCT를 일련의 1-D DCT로 직접 변환하기 위해 다항식 변환을 사용하는 것입니다.MD DCT-IV에는, 다양한 분야의 애플리케이션도 몇개인가?

계산

이들 식을 직접 적용하기 위해서는 O${\displaystyle }$( ${\displaystyle {N\mathrm{}}^{}}$ ${\displaystyle {}^{}}$) { $displaystyle$ ~ {\$mathcal {O}}(N^{2})~}$개의$$ 연산이 ${\displaystyle 필요}$하지만, 마찬가지로 빠르게 변환함으로써 O${\displaystyle }$(${\displaystyle N}$ log${\displaystyle n}$ N$)$ {$displaystyle ~{\mathcal {O}(N\log$ N$)~$의 복잡도만으로 동일한 연산을 할 수 있다.rm(FFT)또한 O${\displaystyle }$(${\displaystyle N}$ )$${$displaystyle ~{\mathcal {O}}(N)~}$개의$$ 전/후 처리 단계와 ${\displaystyle 결합}$된 FFT를 통해 DCT를 계산할 수도 있습니다.일반적으로 DCT를 계산하는 O (${\displaystyle }$N ${\displaystyle \log n}$ $)\$ N$)~}$ ${\displaystyle 메서드}$는 Fast Cosine Transform(FCT; 고속 코사인 변환) 알고리즘이라고 불립니다.

가장 효율적인 알고리즘은 통상적인 FFT + $)$ (\$displaystyle ~{\mathcal {O}}(N)~}$개의$$ 추가 연산을 사용하는 것과 달리 일반적으로 DCT에 직접 특화된 알고리즘입니다(예외 사항은 아래 참조).단, "특화된" DCT 알고리즘(적어도 최소 2의 제곱에 대해 알려진 가장 낮은 산술 카운트를 달성하는 모든 알고리즘 포함)은 일반적으로 FFT 알고리즘과 밀접하게 관련되어 있습니다. DCT는 기본적으로 실제 짝수 데이터의 DFT이기 때문에 FFT를 사용하여 중복 연산을 제거함으로써 고속 DCT 알고리즘을 설계할 수 있습니다.o 이 대칭.이것은 자동적으로 실시할 수도 있습니다(Frigo & Johnson 2005).Cooly에 기반한 알고리즘-Tukey FFT 알고리즘이 가장 일반적이지만 다른 FFT 알고리즘도 적용할 수 있습니다.예를 들어, Winograd FFT 알고리즘은 일반적으로 추가 비용이 많이 들지만 DFT를 위한 최소 곱셈 알고리즘으로 이어지며, 유사한 알고리즘이 (Feig, Winograd & June 1992) harv 오류에 의해 제안되었다: 대상 없음: CITREFFeigWinograd1992년 7월(도움말).DFT, DCT 및 유사한 트랜스폼의 알고리즘은 모두 밀접하게 관련되어 있기 때문에 한 트랜스폼의 알고리즘이 개선되면 이론적으로는 다른 트랜스폼에도 즉시 이익이 됩니다(Duhamel & Vetterli 1990).

수정되지 않은 FFT를 사용하는 DCT 알고리즘은 최상의 특수 DCT 알고리즘과 비교하여 이론적인 오버헤드가 있는 경우가 많지만, 전자는 다음과 같은 뚜렷한 이점을 가지고 있습니다.고도로 최적화된 FFT 프로그램을 널리 사용할 수 있습니다.따라서 실제로는 FFT 기반 ^[a]알고리즘을 사용하여 일반 길이 N에 대해 고성능을 얻는 것이 더 쉽습니다.한편, 특수 DCT 알고리즘에서는 JPEG 압축에 사용되는8 × 8 DCT-II나 오디오 압축에 일반적으로 사용되는 소형 DCT(또는 MDCT) 등, 작은 고정 사이즈의 변환에 폭넓게 사용되고 있습니다(코드 사이즈가 작아진 것도, 임베디드 디바이스의 애플리케이션에 특수 DCT 를 사용하는 이유일 수 있습니다).

실제로 일반 FFT를 사용하는 DCT 알고리즘도 때로는 실제 대칭 데이터의 더 큰 FFT에서 중복 연산을 제거하는 것과 같으며, 산술 카운트의 관점에서 최적일 수도 있습니다.예를 들어 Type-II DCT는 ${\displaystyle \mathrm{사이즈}}$가$4N$인 DFT에 해당하며 짝수 색인이 0인 실짝수$$ 대칭입니다$.$FFT를 통해 이를 계산하는 가장 일반적인 방법 중 하나(예: FFTPACK 및 FFTW에서 사용되는 방법)는 Narasimha & Peterson(1978년)와 Makhoul(1980년)에 의해 설명되었으며, 나중에 보면 이 방법은 기수-4 소멸 시간 쿨리의 한 단계로 볼 수 있다.DCT-II에 ^[b]대응하는 '논리적인' 리얼 짝수 DFT에 적용되는 Tukey 알고리즘.짝수 인덱스의 요소는 0이므로 이 기수-4 스텝은 스플릿 기수 스텝과 동일합니다.후속 ${\displaystyle 크기}$ N$(\$displaystyle $~N~)$의 실제 데이터 FFT가 실제 데이터 분할 기수 알고리즘(Sorensen 등(1987년))에 의해서도 실행되는 경우, 결과 알고리즘은 실제로 2의 DCT-II(2 ${\displaystyle N_{}}$ ${\displaystyle \log }$ ${\displaystyle {2\mathrm{}}_{}}$N -${\displaystyle \mathrm{display}}$2 )에 대해 $공개$된 가장 낮은 연산 카운트와 일치합니다.$-N+2~}$의 실수 연산^[c]).

최근 ${\displaystyle 179}$ ${\displaystyle N_{}}$ ${\displaystyle {로그\mathrm{}}_{}}$ 2${\displaystyle {}_{}n}$N +${\displaystyle O}$ (${\displaystyle }$N$$) { $displaystyle$ ~ {\$tfrac {17}$ {$9} N$ \$log$ _${2}$ N + {\$mathcal {O}}$ {$N$}$$} 로의 조작 카운트의 감소도 실데이터 ^[114]FFT 를 사용합니다.따라서 산술적 관점에서 FFT를 통해 DCT를 계산하는 데 본질적으로 나쁜 점은 없습니다. 때로는 해당 FFT 알고리즘이 최적인지에 대한 질문일 뿐입니다.(실제로 개별 FFT 루틴을 호출할 때의 함수 호출 오버헤드는 ${\displaystyle 작은}$N$(\displaystyle ~N~,)$에 대해 유의할 수 있지만 이는 언롤링 또는 인라이닝으로 해결할 수 있기 때문에 알고리즘적인 질문이 아니라 구현입니다).

IDCT의 예

대문자 A의 이 8x8 그레이스케일 이미지를 생각해 보십시오.

각 기본 함수에 계수를 곱한 후 이 곱을 최종 화상에 추가한다.

「 」를 참조해 주세요.

• 이산 웨이브릿 변환
• JPEG - 이산 코사인 변환 - 잠재적으로 이해하기 쉬운 DCT 변환 예를 포함합니다.
• 푸리에 관련 변환 목록
• 수정된 이산 코사인 변환

메모들

레퍼런스

추가 정보

• Narasimha, M.; Peterson, A. (June 1978). "On the Computation of the Discrete Cosine Transform". IEEE Transactions on Communications. 26 (6): 934–936. doi:10.1109/TCOM.1978.1094144.
• Makhoul, J. (February 1980). "A fast cosine transform in one and two dimensions". IEEE Transactions on Acoustics, Speech, and Signal Processing. 28 (1): 27–34. doi:10.1109/TASSP.1980.1163351.
• Sorensen, H.; Jones, D.; Heideman, M.; Burrus, C. (June 1987). "Real-valued fast Fourier transform algorithms". IEEE Transactions on Acoustics, Speech, and Signal Processing. 35 (6): 849–863. CiteSeerX 10.1.1.205.4523. doi:10.1109/TASSP.1987.1165220.
• Plonka, G.; Tasche, M. (January 2005). "Fast and numerically stable algorithms for discrete cosine transforms". Linear Algebra and Its Applications. 394 (1): 309–345. doi:10.1016/j.laa.2004.07.015.
• Duhamel, P.; Vetterli, M. (April 1990). "Fast fourier transforms: A tutorial review and a state of the art". Signal Processing (Submitted manuscript). 19 (4): 259–299. doi:10.1016/0165-1684(90)90158-U.
• Ahmed, N. (January 1991). "How I came up with the discrete cosine transform". Digital Signal Processing. 1 (1): 4–9. doi:10.1016/1051-2004(91)90086-Z.
• Feig, E.; Winograd, S. (September 1992). "Fast algorithms for the discrete cosine transform". IEEE Transactions on Signal Processing. 40 (9): 2174–2193. Bibcode:1992ITSP...40.2174F. doi:10.1109/78.157218.
• Malvar, Henrique (1992), Signal Processing with Lapped Transforms, Boston: Artech House, ISBN 978-0-89006-467-2
• Martucci, S. A. (May 1994). "Symmetric convolution and the discrete sine and cosine transforms". IEEE Transactions on Signal Processing. 42 (5): 1038–1051. Bibcode:1994ITSP...42.1038M. doi:10.1109/78.295213.
• Oppenheim, Alan; Schafer, Ronald; Buck, John (1999), Discrete-Time Signal Processing (2nd ed.), Upper Saddle River, N.J: Prentice Hall, ISBN 978-0-13-754920-7
• Frigo, M.; Johnson, S. G. (February 2005). "The Design and Implementation of FFTW3" (PDF). Proceedings of the IEEE. 93 (2): 216–231. CiteSeerX 10.1.1.66.3097. doi:10.1109/JPROC.2004.840301. S2CID 6644892.
• Boussakta, Said.; Alshibami, Hamoud O. (April 2004). "Fast Algorithm for the 3-D DCT-II" (PDF). IEEE Transactions on Signal Processing. 52 (4): 992–1000. Bibcode:2004ITSP...52..992B. doi:10.1109/TSP.2004.823472. S2CID 3385296.
• Cheng, L. Z.; Zeng, Y. H. (2003). "New fast algorithm for multidimensional type-IV DCT". IEEE Transactions on Signal Processing. 51 (1): 213–220. doi:10.1109/TSP.2002.806558.
• Wen-Hsiung Chen; Smith, C.; Fralick, S. (September 1977). "A Fast Computational Algorithm for the Discrete Cosine Transform". IEEE Transactions on Communications. 25 (9): 1004–1009. doi:10.1109/TCOM.1977.1093941.
• Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007), "Section 12.4.2. Cosine Transform", Numerical Recipes: The Art of Scientific Computing (3rd ed.), New York: Cambridge University Press, ISBN 978-0-521-88068-8

외부 링크

• Syd Ali Khayam:이산 코사인 변환(DCT): 이론과 응용
• 8x8 IDCT의 MPEG 정수 근사 구현(ISO/IEC 23002-2)
• 마테오 프리고와 스티븐 G. 존슨: FFTW, http://www.fftw.org/.임의의 크기의 1개 이상의 차원으로 고속 DCT(타입 I-IV)를 계산할 수 있는 프리(GPL) C 라이브러리.
• 오우라 타쿠야: 범용 FFT 패키지, http://www.kurims.kyoto-u.ac.jp/~ooura/1902.208.고속 DCT를 계산하기 위한 무료 C & FORTRAN 라이브러리 (타입 II ~ )III) 1차원, 2차원 또는 3차원에서 2사이즈의 전력.
• 팀 키엔츨:8 포인트 DCT 및 IDCT를 계산하는 고속 알고리즘, http://drdobbs.com/parallel/184410889.
• LTFAT는 타입 I-IV의 DCT 및 DST의 FFTW 구현 인터페이스를 갖춘 무료 Matlab/Octave 도구 상자입니다.