프랙탈 압축

Fractal compression
2개의 삼각형, 프랙탈 압축의 작동 방식을 보여 주는 예제

프랙탈 압축프랙탈에 기반한 디지털 이미지의 손실 압축 방법입니다.이 방법은 텍스처 및 자연 이미지에 가장 적합하며, 이미지의 일부가 동일한 [1]이미지의 다른 부분과 비슷한 경우가 많습니다.프랙탈 알고리즘은 이 부분들을 "프랙탈 코드"라고 불리는 수학적 데이터로 변환하여 인코딩된 이미지를 재생성하는 데 사용됩니다.

기능 시스템 Iterated

프랙탈 이미지 표현 수학적으로 한iterated 기능 계통(모의 계기 비행)으로 기술할 수 있다.[2]

이진 이미지 들어

우리는 이치 영상의 이미지의 R2{\displaystyle \mathbb{R}^{2}의 부분 집합이라고 생각될지 모르는 표현 방법}. 수축 매핑 ƒ1의 모의 계기 비행 세트입니다,...,ƒN, 시작한다.

이러한 매핑 기능에 따르면 모의 계기 비행은 허친슨 연산자의 고정된 포인트로 2차원 집합 S에 대해 설명합니다.

, H는 세트에 대한 연산자 매핑 세트이고, S는 H(S) = S를 만족하는 고유한 세트입니다. 아이디어는 이 세트 S가 입력 이진 이미지가 되도록 IFS를 구성하는 것입니다.집합 S는 고정점 반복을 통해 IFS에서 복구할 수 있습니다. 비어 있지 않은 임의의 콤팩트 초기 집합0 A에 대해 반복k+1 A = H(Ak)는 S로 수렴됩니다.

집합 S는 자체 유사하다. 왜냐하면 H(S) = S는 S가 자신의 매핑 복사본의 결합임을 암시하기 때문이다.

즉, IFS는 S의 프랙탈 표현입니다.

그레이스케일로 확장

IFS 표현은 그래프를 R 3 집합으로 간주하여 그레이스케일 영상으로 확장할 수 있습니다. 그레이스케일 영상 u(x,y)의 경우 세트 S = {(x,y,u(x,y)})}.다음으로 바이너리 케이스와 마찬가지로 S는 일련의 수축 매핑 「,…」를1N 사용하여 IFS에 의해 기술되지만, R

부호화

프랙탈 화상 표현에 관한 현재 진행 중인 연구의 난제는 고정점이 입력 화상에 근접하도록 【…】를1N 어떻게 선택하고, 이것을 어떻게 효율적으로 할 것인가 하는 것이다.

이를 위한 간단한[2] 방법은 다음과 같은 Partitioned Repeated Function System(PIFS; 분할 반복 기능 시스템)입니다.

  1. 영상 도메인을 s×s 크기의 범위 블록i R로 분할합니다.
  2. i R에 대해 이미지를 검색하여 R과 매우i 유사한 2s×2si 크기의 블록 D를 찾습니다.
  3. i에 대해 H(Di) = Ri 되도록 매핑 함수를 선택합니다.

두 번째 단계에서는 IFS가 입력 화상을 정확하게 나타낼 수 있도록 유사한 블록을 찾는 것이 중요하므로 D 후보i 블록의 수를 충분히 고려할 필요가 있다.한편, 다수의 블록을 고려한 대규모 검색은 계산 비용이 많이 듭니다.이와 같은 블록 검색의 병목현상으로 인해 DCTwavelet 기반의 이미지 표현 등보다 PIFS 프랙탈 부호화가 매우 느려집니다.

Jacquin이 제시한 초기 사각 분할 및 브루트 포스 검색 알고리즘은 여러 가지 가능한 방향으로 더 많은 연구와 확장을 위한 출발점을 제공합니다. - 이미지를 다양한 크기와 모양의 범위 블록으로 분할하는 다양한 방법; 각 r에 대해 근접하게 일치하는 도메인 블록을 빠르게 찾기 위한 빠른 기술.빠른 움직임 추정 알고리즘과 같은 brute-force search가 아닌 ange block, 도메인 블록에서 범위 블록으로의 매핑을 부호화하는 다양한 방법 등.[3]

다른 연구자들은 임의의 이미지를 PIFS가 아닌 RIFS(Recurrent Repeated Function System) 또는 글로벌 IFS로 자동 부호화하는 알고리즘과 움직임 보상 및 3차원 반복 함수 [4][5]시스템을 포함한 프랙탈 비디오 압축 알고리즘을 찾으려고 합니다.

프랙탈 화상 압축은 벡터 양자화 화상 [6]압축과 많은 유사점을 가지고 있습니다.

특징들

프랙탈 압축에서는 자기유사성을 찾는 데 사용되는 검색 때문에 부호화가 계산적으로 매우 비쌉니다.그러나 디코딩은 매우 빠릅니다.이러한 비대칭성으로 인해 지금까지 실시간 애플리케이션에서는 실행이 불가능했지만, 디스크 스토리지에서 배포하기 위해 비디오를 아카이브하거나 파일을 다운로드하면 프랙탈 압축의 경쟁력이 [7][8]높아집니다.

약 50:1의 일반적인 압축비에서 프랙탈 압축은 [9]JPEG와 같은 DCT 기반 알고리즘과 유사한 결과를 제공합니다.압축비가 높을 경우 프랙탈 압축은 우수한 품질을 제공할 수 있습니다.위성 사진의 경우 170:1[10] 이상의 비율이 허용 가능한 결과로 달성되었습니다.25:1~244:1의 프랙탈비디오 압축비는 적절한 압축시간(2.4~66초/프레임)[11]으로 달성되었습니다.

단순한 그레이스케일 이미지에 비해 이미지의 복잡성과 색심도가 높을수록 압축 효율이 높아집니다.

해상도 독립성과 프랙탈 스케일링.

프랙탈 압축의 고유한 특징은 이미지가 프랙탈 코드로 변환된 후 해상도에 의존하지[12] 않는다는 것입니다.이는 압축 파일에서 반복된 기능 시스템이 무한히 확장되기 때문입니다.프랙탈의 이러한 무한 스케일링 속성을 "프랙탈 스케일링"이라고 합니다.

보간 프랙탈

프랙탈 인코딩 영상의 해상도 독립성을 사용하여 영상의 디스플레이 해상도를 높일 수 있습니다.이 과정은 "프랙탈 보간"이라고도 합니다.프랙탈 보간에서는, 화상을 프랙탈 압축을 개입시켜 프랙탈 코드로 부호화한 후, 보다 높은 해상도로 압축 해제한다.그 결과 반복된 기능 시스템이 보간물[13]사용된 업샘플링된 영상이 생성됩니다.프랙탈 보간법은 쌍선형 보간법쌍입방 [14][15][16]보간법과 같은 기존의 보간법에 비해 기하학적 세부사항을 매우 잘 유지한다.그러나 보간은 섀넌 엔트로피를 반전시킬 수 없기 때문에 의미 있는 디테일이 아닌 랜덤을 추가해 이미지를 선명하게 만든다.예를 들어, 한 사람의 얼굴이 한 두 개의 픽셀로 되어 있고 그들을 식별하기를 바라는 군중의 이미지를 확대시킬 수는 없다.

역사

마이클 반슬리는 1987년 프랙탈 압축 개발을 주도했으며,[17] 이 기술에 대한 여러 특허를 취득했습니다.가장 널리 알려진 실용적인 프랙탈 압축 알고리즘은 반슬리와 앨런 슬론이 발명했습니다.반슬리의 대학원생인 Arnsley Jacquin은 [18][19]1992년에 소프트웨어에 최초의 자동 알고리즘을 구현했습니다.모든 방법은 반복 함수 시스템을 사용하는 프랙탈 변환을 기반으로 합니다.마이클 반슬리와 앨런 슬론은 1987년에 프랙탈 압축과 관련된 20개 이상의 특허를 추가로 부여받은 반복 시스템 [20]주식회사를 설립했습니다.

Iterated Systems Inc.의 주요 돌파구는 프랙탈 압축 기술을 사용한 초기 실험에서와 같이 압축 중에 사람이 개입할 필요가 없어진 자동 프랙탈 변환 프로세스입니다.1992년, Iterated Systems Inc.는 프랙탈 변환 이미지 압축 기술을 이용한 디지털 이미지 스토리지 및 압축 해제 칩 프로토타입 개발을 위해 미화 210만 달러의 정부 보조금을[21] 받았습니다.

프랙탈 이미지 압축은 여러 상용 응용 프로그램에서 사용되었습니다. OnOne Software는 Iterated Systems Inc.의 라이센스 하에 개발되었으며 Genuine Frackals[22] 5는 압축 FIF(Fractal Image Format)로 파일을 저장할 수 있는 Photoshop 플러그인입니다.지금까지 프랙탈 이미지 압축을 가장 성공적으로 사용한 것은 Microsoft의 Encarta 멀티미디어 [23]백과사전이며 라이센스도 있습니다.

Iterated Systems Inc.는 Windows에서 사용하기 위한 쉐어웨어 인코더(Fractal Imager), 독립형 디코더, Netscape 플러그인 디코더 및 개발 패키지를 제공했습니다.Wavelet 기반의 이미지 압축 방법이 개선되고 상용 소프트웨어 벤더가 보다 쉽게 라이센스를 부여함에 따라 프랙탈 이미지 포맷의 채택은 [citation needed]발전하지 못했습니다.ColorBox III SDK가 제공하는 "압축 해제기 DLL"의 재배포는 독점 소프트웨어 벤더의 디스크 단위 또는 연도별 라이센스 제도 및 특정 등급의 다른 [24]사용자에 대한 반복 시스템 제품의 프로모션을 수반하는 재량권 제도에 의해 관리되었습니다.

1990년대에 Iterated Systems Inc.와 그 파트너들은 프랙탈 압축을 비디오에 도입하기 위해 상당한 자원을 소비했습니다.압축 결과는 유망했지만, 그 당시 컴퓨터 하드웨어에는 프랙탈 비디오 압축이 몇 가지 선택된 사용법을 넘어 실용화되기 위한 처리 능력이 부족했습니다.1분간의 비디오를 압축하는 데 최대 15시간이 소요되었습니다.

ClearVideo – RealVideo (Fractal)라고도 불리는 ClearVideo 와 SoftVideo 는 초기 프랙탈 비디오 압축 제품입니다.ClearFusion은 웹 브라우저용 스트리밍 비디오 플러그인입니다.1994년 SoftVideo는 Falcon Gold와 Star Trek을 포함CD-ROM 게임에 사용할 수 있도록 Spectrum Holobyte에 라이센스를 받았습니다. 차세대 최종 [25]통합

1996년, 주식회사 Iterated Systems Inc.는[26] 클리어 비디오를 일본 고객에게 판매하기 위해 미쓰비시 주식회사와 제휴를 발표했다.원래의 ClearVideo 1.2 디코더 드라이버는, 인코더는 서포트되고 있지 않지만, Microsoft[27] 에서는 Windows Media Player 로 서포트되고 있습니다.

Total Multimedia Inc.와 Dimension이라는 두 회사는 모두 Iterated의 비디오 기술을 소유하거나 독점 라이선스를 가지고 있다고 주장하지만, 둘 다 아직 작동하는 제품을 출시하지 않았습니다.기술 기반은 상당 부분 [28]분석된 디멘션의 미국 특허 8639053과 8351509로 보인다.요약하면 이는 기존의 DCT 기반 코덱의 대역폭 효율도 PSNR 품질도 없는 단순한 쿼드트리 블록 복사 시스템입니다.2016년 1월 TMMI는 프랙탈 기반 기술을 완전히 포기한다고 발표했습니다.

1997년부터 2007년까지의 연구 논문에서는 프랙탈 알고리즘과 부호화 하드웨어를 [29][30][31][32][33][34][35][36][37]개선하기 위한 가능한 솔루션에 대해 논의했습니다.

구현

Fiasco라고 불리는 도서관은 Ullrich Hafner에 의해 만들어졌다.2001년, Fiasco리눅스 저널에 실렸다.[38] 2000-04 Fiasco 매뉴얼에 따르면 Fiasco는 동영상 압축에 사용할 수 있습니다.[39] Netpbm 라이브러리에는 Fiasco 라이브러리가 포함되어 있습니다.[40][41]

펨토소프트는 오브젝트 파스칼자바에서 프랙탈 이미지 압축의 구현을 개발했습니다.[42]

「 」를 참조해 주세요.

메모들

  1. ^ May, Mike (1996). "Fractal Image Compression". American Scientist. 84 (5): 442–451. Bibcode:1996AmSci..84..442M. JSTOR 29775747. ProQuest 215266230.
  2. ^ a b Fischer, Yuval (1992-08-12). Przemyslaw Prusinkiewicz (ed.). SIGGRAPH'92 course notes - Fractal Image Compression (PDF). SIGGRAPH. Vol. Fractals - From Folk Art to Hyperreality. ACM SIGGRAPH.
  3. ^ Saupe, Dietmar; Hamzaoui, Raouf (November 1994). "A review of the fractal image compression literature". ACM SIGGRAPH Computer Graphics. 28 (4): 268–276. doi:10.1145/193234.193246. S2CID 10489445.
  4. ^ Lacroix, Bruno (1999). Fractal image compression (Thesis). doi:10.22215/etd/1999-04159. OCLC 1103597126. ProQuest 304520711.
  5. ^ Fisher, Yuval (2012). Fractal Image Compression: Theory and Application. Springer Science & Business Media. p. 300. ISBN 978-1-4612-2472-3.
  6. ^ 헨리 샤오"프랙셔널 압축"2004.
  7. ^ John R. Jensen, "Remote Sensing Textbooks", Image Compression Alternatives and Media Storage Considerations (reference to compression/decompression time), University of South Carolina, archived from the original on 2008-03-03
  8. ^ Steve Heath (23 August 1999). Multimedia and communications technology. Focal Press. pp. 120–123. ISBN 978-0-240-51529-8. Focial Press
  9. ^ Sayood, Khalid (2006). Introduction to Data Compression. Elsevier. pp. 560–569. ISBN 978-0-12-620862-7.
  10. ^ Wee Meng Woon; Anthony Tung Shuen Ho; Tao Yu; Siu Chung Tam; Siong Chai Tan; Lian Teck Yap (2000). "Achieving high data compression of self-similar satellite images using fractal". IGARSS 2000. IEEE 2000 International Geoscience and Remote Sensing Symposium. Taking the Pulse of the Planet: The Role of Remote Sensing in Managing the Environment. Proceedings (Cat. No.00CH37120). Vol. 2. pp. 609–611. doi:10.1109/IGARSS.2000.861646. ISBN 0-7803-6359-0. S2CID 14516581.
  11. ^ Fisher, Y. (July 1995). Fractal encoding of video sequences. Fractal image encoding and analysis. Trondheim. INIST:1572685.
  12. ^ Wayback Machine Byte Magazine의 Walking, Talking Web Archived 2008-01-06 프랙탈 압축/해상도 독립성 기사
  13. ^ He, Chuan-jiang; Li, Gao-ping; Shen, Xiao-na (May 2007). "Interpolation decoding method with variable parameters for fractal image compression". Chaos, Solitons & Fractals. 32 (4): 1429–1439. Bibcode:2007CSF....32.1429H. doi:10.1016/j.chaos.2005.11.058.
  14. ^ Navascués, M. A.; Sebastián, M. V. (2006). "Smooth fractal interpolation". Journal of Inequalities and Applications. 2006: 1–20. doi:10.1155/JIA/2006/78734. S2CID 20352406.
  15. ^ Uemura, Satoshi; Haseyama, Miki; Kitajima, Hideo (28 January 2003). "EFIFを用いた自己アフィンフラクタル図形の拡大処理に関する考察" [A Note on Expansion Technique for Self-Affine Fractal Objects Using Extended Fractal Interpolation Functions]. IEICE Technical Report (in Japanese). 102 (630): 95–100. doi:10.11485/itetr.27.9.0_95. NAID 110003171506.
  16. ^ Kuroda, Hideo; Hu, Xiaotong; Fujimura, Makoto (1 February 2003). "フラクタル画像符号化におけるスケーリングファクタに関する考察" [Studies on Scaling Factor for Fractal Image Coding]. The Transactions of the Institute of Electronics, Information and Communication Engineers (in Japanese). 86 (2): 359–363. NAID 110003170896.
  17. ^ 미국 특허 4,941,193 – 1987년 10월에 출원된 반슬리와 슬론의 첫 반복 기능 시스템 특허
  18. ^ 디지털 라이브러리 테크니컬리포트의 이미지 콘텐츠 인덱스에 프랙탈 코딩 사용
  19. ^ Jacquin, A.E. (1992). "Image coding based on a fractal theory of iterated contractive image transformations". IEEE Transactions on Image Processing. 1 (1): 18–30. Bibcode:1992ITIP....1...18J. CiteSeerX 10.1.1.456.1530. doi:10.1109/83.128028. PMID 18296137.
  20. ^ Iterated Systems Inc.가 MediaBin Inc.로 사명을 변경. 2001년에 Inc.를 인수한 후, 2003년에 Interwoven, Inc.)
  21. ^ NIST SP950-3, "접근성 향상을 위한 환자 의료 정보 캡처통합", 36페이지의 "디지털 이미지 파일을 압축하는 MediaBin 프랙탈 기반 기술" 2015-09-23 웨이백 머신에서 아카이브됨
  22. ^ 정규 프랙탈 제품 리뷰
  23. ^ "MAW 1998: Theme Essay". www.mathaware.org. Archived from the original on 31 August 2016. Retrieved 18 April 2018.
  24. ^ Aitken, William (May 1994). "The big squeeze". Personal Computer World.
  25. ^ 1994 Spectrum Holobyte 라이선스 하에 SoftVideo (11페이지)를 지정하는 매뉴얼
  26. ^ "Mitsubishi Corporation Inks Agreement With Iterated Systems" (Press release). Iterated Systems. 29 October 1996. Archived from the original on 8 July 2012.
  27. ^ "Windows Media Player for Windows XP Supported Codecs". 31 October 2003. Archived from the original on 28 October 2004.
  28. ^ "April - 2014 - Due Diligence Study of Fractal Video Technology". paulschlessinger.wordpress.com. Retrieved 18 April 2018.
  29. ^ Kominek, John (1 June 1997). "Advances in fractal compression for multimedia applications". Multimedia Systems. 5 (4): 255–270. CiteSeerX 10.1.1.47.3709. doi:10.1007/s005300050059. S2CID 6016583.
  30. ^ Harada, Masaki; Kimoto, Tadahiko; Fujii, Toshiaki; Tanimoto, Masayuki (2000). "Fast calculation of IFS parameters for fractal image coding". In Ngan, King N; Sikora, Thomas; Sun, Ming-Ting (eds.). Visual Communications and Image Processing 2000. Vol. 4067. p. 457–464. Bibcode:2000SPIE.4067..457H. doi:10.1117/12.386580. S2CID 30148845. INIST:1380599.
  31. ^ Rajkumar, Wathap Sapankumar; Kulkarni, M.V.; Dhore, M.L.; Mali, S.N. (2006). "Fractal image compression performance synthesis through HV partitioning". 2006 International Conference on Advanced Computing and Communications. pp. 636–637. doi:10.1109/ADCOM.2006.4289976. ISBN 978-1-4244-0715-6. S2CID 15370862.
  32. ^ 단순하고 고속 프랙탈이미지 압축회로, 신호 및 시스템 - 2003
  33. ^ Wu, Ming-Sheng; Jeng, Jyh-Horng; Hsieh, Jer-Guang (June 2007). "Schema genetic algorithm for fractal image compression". Engineering Applications of Artificial Intelligence. 20 (4): 531–538. doi:10.1016/j.engappai.2006.08.005.
  34. ^ Wu, Xianwei; Jackson, David Jeff; Chen, Hui-Chuan (September 2005). "A fast fractal image encoding method based on intelligent search of standard deviation". Computers & Electrical Engineering. 31 (6): 402–421. doi:10.1016/j.compeleceng.2005.02.003.
  35. ^ Wu, Xianwei; Jackson, David Jeff; Chen, Hui-Chuan (2005). "Novel fractal image-encoding algorithm based on a full-binary-tree searchless iterated function system". Optical Engineering. 44 (10): 107002. Bibcode:2005OptEn..44j7002W. doi:10.1117/1.2076828.
  36. ^ Truong, Trieu-Kien; Jeng, Jyh H. (2000). "Fast classification method for fractal image compression". In Schmalz, Mark S (ed.). Mathematics and Applications of Data/Image Coding, Compression, and Encryption III. Mathematics and Applications of Data/Image Coding. Vol. 4122. pp. 190–193. Bibcode:2000SPIE.4122..190T. doi:10.1117/12.409247. S2CID 120032052.
  37. ^ Erra, Ugo (2005). "Toward Real Time Fractal Image Compression Using Graphics Hardware". Advances in Visual Computing. Lecture Notes in Computer Science. Vol. 3804. pp. 723–728. doi:10.1007/11595755_92. ISBN 978-3-540-30750-1.
  38. ^ Hafner, Ullrich (2001). "FIASCO - An Open-Source Fractal Image and Sequence Codec". Linux Journal (81). Retrieved February 19, 2013.
  39. ^ "Manpage of fiasco". castor.am.gdynia.pl. Archived from the original on 9 March 2012. Retrieved 18 April 2018.
  40. ^ "Pnmtofiasco User Manual". netpbm.sourceforge.net. Retrieved 18 April 2018.
  41. ^ "Fiascotopnm User Manual". netpbm.sourceforge.net. Retrieved 18 April 2018.
  42. ^ "Archived copy". Archived from the original on 2010-10-23. Retrieved 2010-07-10.{{cite web}}: CS1 maint: 제목으로 아카이브된 복사(링크)

외부 링크