손실 압축 알고리즘 검토. 프랙탈 알고리즘의 실제 적용 프랙탈 방법을 이용한 영상 압축 평가
그러나 아마도 이 방향에 대한 작업의 상업적 구성 요소와 결과적으로 고려 중인 알고리즘에 대한 만족스러운 설명이 부족하기 때문에 제안된 수정 사항은 합리적이기보다는 직관적이고 자발적인 즉흥 연주의 결과로 인식됩니다. 특정 일련의 계산 실험의 결과. 동시에 이 분야를 시작하는 모든 연구자는 주요 알고리즘에 대한 철저한 비교 분석이 필요합니다.
목표와 목적
이 작업의 목적은 기본 알고리즘에 대한 비교 분석을 수행하고, 도메인 블록 선택 기능을 확립하고, 압축 효율성을 높이기 위한 근사치를 테스트하는 방법입니다. 이 목표는 도메인 블록을 선택하는 방법과 근사 방법의 변경을 통해 달성됩니다.
이 작업의 아이디어는 코딩 효율성을 높이기 위해 도메인 블록을 선택하는 방법과 이를 순위 블록으로 근사화하는 방법의 새로운 수정을 개발하는 것입니다.
이 목표를 달성하기 위해 석사 논문에서는 다음과 같은 과제를 설정하고 해결했습니다.
- 문헌 소스를 연구하고 손실이 있는 이미지 압축 알고리즘에 대한 이론적 분석을 수행합니다.
- 프랙탈 영상 압축 알고리즘의 동작 특성 확립, 이를 구현하는 소프트웨어 개발
- 이미지 세트 생성, 도메인 블록 및 근사 선택 기능 설정을 위한 계산 실험 수행, 결과 비교 분석, 결론 도출.
- 알고리즘의 개별 단계 수정, 새 버전 형성.
- 적절한 소프트웨어 구성 요소 개발, 실험 수행, 작업 비교 결과.
연구 주제는 손실 영상 압축 알고리즘이다.
연구 대상은 이미지 압축을 위한 프랙탈 알고리즘입니다.
연구 방법에는 계산 실험 수행, 결과 비교 분석, 수치 방법, 수학적 근사 방법, 객체 지향 프로그래밍이 포함됩니다.
과학적 참신성 주장
본 연구에서 이미 수행되고 계획된 연구의 과학적 신규성은 다음과 같이 가정된다.
- 기본적인 프랙탈 압축 알고리즘을 구현하고 비교 분석이 가능한 소프트웨어가 개발되었습니다.
- 전산실험을 수행하고 비교분석을 실시하여 기본 알고리즘에서 도메인 블록을 선택하는 특징을 확인하였다.
- 비선형 이미지 블록 매핑 모델의 적용 가능성 분석.
- 압축 효율성을 높이기 위한 새로운 알고리즘 수정이 제안되었습니다.
작업결과 설명
연구에 대한 설명
현재 단계에서는 프랙탈 이미지 압축을 위한 두 가지 알고리즘, 즉 문헌에 잘 설명되어 있는 기본 알고리즘과 FE 알고리즘에 대한 연구가 수행되었습니다. 그것들은 주요 것들 중에서 고려될 수 있습니다.
기본 알고리즘은 일반적으로 다음 단계를 포함합니다.
1단계. 이미지 f에서는 많은 도메인 블록이 식별됩니다. 겹칠 수 있으며, 겹침 정도는 특별히 제공된 매개변수에 의해 결정됩니다.
Step 2. 이미지를 겹치지 않는 순위 블록(R k)으로 나눕니다. 크기가 같지 않을 수도 있기 때문에... 가변 블록 크기를 갖는 쿼드 트리 방법을 사용하는 적응형 파티셔닝이 사용됩니다. 이를 통해 작은 크기의 랭크 블록으로 작은 세부 사항이 포함된 이미지 부분을 조밀하게 채울 수 있습니다.
Step 3. 각 순위 블록에 대해 도메인 블록을 정렬합니다. 이 경우 도메인 방향 변경이 제공됩니다(회전 옵션 3개, 반사가 있는 회전 옵션 2개, 반사 옵션 2개 및 8번째 옵션 - 변경되지 않은 원래 방향). 각 방향 옵션에 대해 도메인을 순위 블록의 크기로 압축하고 변환 계수 a ij 및 b ij의 최적 값을 계산합니다.
최소제곱법 및 공식
변환된 압축된 i번째 도메인 블록 wi ij(D" ij)의 j번째 방향에서 랭크 블록 R k에 대한 대응성을 특성화하는 매개변수 L(R k, D" ij)의 정규화된 값을 계산합니다. 여기서 r xy ∈ R k, d xy ∈ D" ij, D" ij는 j번째 방향의 i번째 도메인 블록으로, 순위 블록의 크기로 압축되었으며, N R k는 순위의 픽셀 수입니다. 차단하다. 이 단계에서 알고리즘은 사용자가 선택한 두 가지 모드(최상의 도메인 검색 포함 및 제외) 중 하나로 작동합니다. 최상의 도메인에 대한 검색 모드에서는 모든 도메인을 각 순위별로 정렬하고 i번째 도메인과 해당 j번째 방향을 선택하며, 그 중 L kij 값은 다른 모든 것 중에서 최소입니다. 최적의 도메인을 검색하지 않는 모드에서는 i번째 도메인과 j번째 방향이 발견되어 L kij 값이 지정된 허용 오차를 초과하지 않는 즉시 도메인 전체 검색이 중지됩니다(예: L kij ≤ 0.05). 두 모드 모두에서 모든 도메인 블록을 검색한 후 L kij 값이 지정된 허용 오류 값을 초과하지 않는 도메인 블록이 발견되지 않으면 문제의 순위 블록이 다음 위치에 있는지 확인합니다. 순위 분할의 최대 허용 수준. 그렇지 않은 경우 이 순위 블록은 더 작은 블록으로 나누어지고 알고리즘의 이 단계가 수행됩니다. 그렇다면 모든 도메인에서 L kij 값이 최소인 도메인과 해당 방향 변형 D ij를 선택하고 문제의 순위 블록이 이 도메인에 포함되는 것으로 간주합니다.
3단계에서는 가장 많은 계산이 필요합니다. 각 순위 블록 R k에 대해 알고리즘은 모든(또는 작동 모드에 따라 여러 개) 도메인 블록과 해당 방향 옵션을 반복하여 방향을 변경하는 데 컴퓨터 시간이 많이 걸리는 각각에 대해 픽셀 단위 작업을 수행하고 변환 계수를 찾으십시오. 좋은 압축은 순위 블록을 깊게 분할할 필요 없이 도메인과 순위 블록 간의 적절한 일치를 찾는 능력에 달려 있습니다. 지나치게 깊은 순위 분할은 순위가 너무 많아 압축률이 저하되는 반면, 순위 분할이 충분하지 않으면 인코딩된 이미지의 품질이 저하됩니다.
FE 알고리즘. 기본 알고리즘에서 순위를 도메인과 비교하려면 상당한 계산 리소스가 필요합니다. 이를 줄이기 위해 FE 알고리즘(English Feature Extraction - 특징 강조)은 도메인 및 순위 블록을 설명하는 5가지 특성을 식별합니다. 그리고 처음에는 비교가 수행되어 계산량이 크게 줄어 듭니다. 이러한 특성은 다음과 같습니다.
- 표준 편차;
- 어울리지 않음;
- 픽셀간 대비;
- 픽셀 값과 중앙 픽셀 값의 차이를 나타내는 베타 계수;
- 최대 기울기 - 수평 및 수직 기울기의 최대값입니다.
알고리즘 자체에는 다음 단계가 포함됩니다.
1단계. 기본 알고리즘의 1단계와 유사합니다.
Step 2. 기본 알고리즘의 Step 2를 보완하여 도메인 블록별로 특성 벡터의 값을 계산하여 저장한다.
3단계. 순위 블록을 처리할 때 먼저 특성 벡터를 계산한 다음 다음 공식을 사용하여 주어진 순위의 특성 벡터와 각 영역의 특성 벡터 사이의 거리를 계산합니다.
여기서 f j R 및 f j D는 각각 랭크 및 도메인 블록의 j번째 특성입니다. 후속 완전 비교를 위해 특성 벡터 사이의 거리 값이 최소인 도메인의 지정된 q 비율(예: q = 2%)만 선택됩니다. 후속 작업은 기본 알고리즘의 3단계에서 수행되는 작업과 유사하지만 도메인을 열거할 때 선택된 q%만 고려하고 그 중에서 가장 좋은 것을 선택한다는 차이점이 있습니다.
이 도메인 선택 절차는 선택할 도메인 수를 크게 제한하는 일종의 필터라는 점에 유의하세요.
개발된 소프트웨어 설명
연구를 수행하기 위해 Microsoft .NET Framework 2.0 기술과 Visual Studio 2005/2008 도구 셸을 사용하여 C# 언어로 특수 소프트웨어가 개발되었습니다. 래스터 이미지를 프랙탈 이미지로 인코딩하고 위에서 설명한 알고리즘을 사용하여 디코딩할 수 있습니다. 사용자는 인코딩된 이미지의 품질을 제어하는 인코딩 설정을 지정할 수 있습니다. 또한 소프트웨어에는 다음 분석 도구가 포함되어 있습니다.
- 속성 값이 포함된 테이블 형식과 시각적으로 이미지에 도메인 및 순위의 구조를 표시합니다.
- 원본 이미지와 인코딩된 이미지 사이의 평균 픽셀 오류를 계산하는 단계;
- 코딩에서 처리되고 사용되는 순위 및 도메인 수를 계산합니다.
- 인코딩 및 디코딩 시간 결정;
- 인코딩된 이미지에 순위 블록의 그리드를 표시하는 단계;
- 다양한 프랙탈 압축 알고리즘을 사용하여 이미지 인코딩 결과를 자동으로 분석합니다.
개발된 소프트웨어의 UML 다이어그램은 다음과 같습니다(그림 1).
그림 1 - 개발된 소프트웨어의 UML 다이어그램
그림 2 — 개발된 소프트웨어의 화면 형태
실험, 결과 및 결론
개발된 소프트웨어를 사용하여 무작위로 선택된 256×256 픽셀 크기의 이미지를 사용하여 그림 3에 제시된 일련의 실험을 수행했습니다. 초기 데이터, 설정 매개변수 및 실험 결과는 표 1에 표시됩니다. 그림 4는 디코딩된 이미지를 보여줍니다. 고려된 알고리즘에 의해 사전 인코딩된 이미지.
그림 3 - 원본 이미지
그림 4 - 기본 (a) 및 FE-(b) 프랙탈 이미지 압축 알고리즘으로 인코딩된 이미지 디코딩의 8회 반복 시각화. 애니메이션은 프레임 간 지연이 50ms인 9개의 프레임으로 구성됩니다. 재생 전 지연 시간은 400ms입니다. 재생 주기 수는 10으로 제한됩니다.
실험에서 두 알고리즘의 인코딩 시간은 제한되지 않았습니다. 각 후속 실험은 인코딩된 이미지의 품질을 결정하는 더 높은 매개변수 값이 이전 실험과 다릅니다. 알고리즘 설명에서 그 목적이 자세히 공개되지 않은 이러한 매개변수 중 일부를 설명하겠습니다. 도메인 분할의 초기 및 최대 수준과 도메인 슬라이딩 계수는 도메인 수, 크기 및 위치를 규제합니다. 슬라이딩 계수는 이웃 도메인이 얼마나 밀접하게 겹치는지를 결정합니다. 따라서 최소값이 0이면 전혀 겹치지 않고, 최대값이 1이면 정확히 1픽셀 너비의 영역이 폐색되지 않은 상태로 유지되도록 겹쳐집니다. 도메인 수는 전적으로 이러한 매개변수에 따라 달라집니다. 순위 분할의 초기 수준은 초기 최소 수와 가능한 최대 크기를 지정하고, 최대 분할 수준은 허용되는 최대 수와 가능한 최소 크기를 지정합니다. 이러한 수준은 본질적으로 쿼드 트리 방법을 사용하는 순위 분할 수준입니다. 코딩 종료 시 순위 수는 이러한 매개변수뿐만 아니라 허용되는 오류에 따라 달라집니다(알고리즘 설명 참조). 평균 픽셀 오류는 디코딩된 이미지가 원본 이미지와 얼마나 다른지 보여주며 공식에 의해 결정됩니다.
여기서 p x,y, p" x,y는 각각 원본 이미지와 디코딩된 이미지의 (x, y) 지점의 픽셀 값이고, I W, I H는 각각 이미지의 너비와 높이(픽셀 단위)이고, NI는 이미지의 픽셀 수.
도메인 수를 결정하는 매개변수는 인코딩 시간과 디코딩된 이미지의 품질에 직접적인 영향을 미치며 압축률에는 반영되지 않습니다. 순위의 수와 크기를 규제하는 매개변수는 인코딩 및 디코딩 시간과 디코딩된 이미지의 품질에 모두 영향을 미칩니다. 그리고 순위 수에 따라 압축 비율이 고유하게 결정됩니다.
표 1 - 실험 결과
| 옵션 | 실험번호 | |||
|---|---|---|---|---|
| FE 알고리즘 | ||||
도메인 수 |
||||
초급집 |
||||
최대 레벨 하우스. |
||||
계수. 도메인 슬라이딩 |
||||
순위 수 |
||||
시작 순위 분할 수준 |
||||
허용되는 침수 |
||||
최고의 도메인 검색 |
||||
수요일 픽스. 오류, % |
||||
압축비 |
||||
인코딩 시간(초) |
||||
디코딩 시간, (초) |
||||
| 기본 알고리즘 | ||||
도메인 수 |
||||
초급집 |
||||
최대 레벨 하우스. |
||||
집 전표 계수 |
||||
순위 수 |
||||
시작 순위 분할 수준 |
||||
최대. 순위 분할 수준 |
||||
허용되는 침수 |
||||
최고의 도메인 검색 |
||||
수요일 픽스. 오류, % |
||||
압축비 |
||||
인코딩 시간(초) |
||||
디코딩 시간, (초) |
||||
얻은 결과를 통해 다음과 같은 결론을 내릴 수 있습니다.
- FE 알고리즘은 기본 알고리즘에 비해 동일한 알고리즘 설정으로 수십 배 더 짧은 시간에 이미지를 압축할 수 있습니다.
- 알고리즘의 평균 픽셀 오류는 다릅니다. 설정에 따라 차이는 5~16% 범위입니다.
- 기본 알고리즘으로 인코딩한 결과, 모든 경우에 평균 30~40% 더 높은 압축률이 달성됩니다.
- FE 알고리즘을 사용하면 디코딩된 이미지의 시각적 품질이 눈에 띄게 향상됩니다.
- 모든 실험에서 기본 알고리즘을 사용할 때 다양한 인코딩 설정에서 인코딩된 이미지의 디코딩 시간이 더 짧습니다.
그 중 일부는 매우 분명합니다. 실제로 FE 알고리즘에서는 이미지 블록을 비교하는 대신 해당 특성 벡터를 비교하므로 당연히 성능에 영향을 미칩니다. 픽셀 오류와 압축 비율의 차이는 FE 알고리즘을 사용할 때 인코딩으로 인해 더 많은 수의 작은 크기 순위가 생성되고 더 높은 이미지 세부 정보, 즉 더 나은 시각적 품질을 제공한다는 사실로 설명될 가능성이 높습니다. 이러한 결론은 순위 그리드를 사용하여 두 알고리즘으로 인코딩된 이미지를 보여주는 그림 6에서 확인됩니다. 기본 알고리즘은 5~16% 더 나쁜 이미지 품질을 생성하지만 30~40% 더 높은 압축률을 달성한다는 점에 유의해야 합니다.
차이가 확인되는 이유는 FE 알고리즘에서 해당 특성 값으로 선택된 도메인을 검색할 때 순위 블록 준수에 대해 허용되는 허용 오류를 제공하는 사람이 없기 때문인 것으로 추측할 수 있습니다. 그 결과 순위 블록은 블록 크기에 따라 더 작은 블록으로 나뉩니다. 동시에 동일한 순위에 대한 기본 알고리즘으로 코딩할 때 이러한 도메인이 발견될 가능성이 높습니다.
이 가설을 테스트하기 위해 도메인을 선택할 때 두 알고리즘의 일치 수를 계산할 수 있는 추가 소프트웨어 모듈이 개발되었습니다. 두 알고리즘에서 동일한 순위에 대해 동일한 도메인이 선택된 경우. 이미지는 동일하게 유지되었습니다. 인코딩 설정은 표 1의 네 번째 실험에 사용된 설정과 일치하며 유일한 차이점은 기본 알고리즘이 최상의 도메인 검색 모드에서 작동한다는 것입니다. 즉, 각 랭크 블록을 처리할 때 허용 오차에 도달해도 멈추지 않고 모든 도메인 블록을 검색하여 가장 좋은 블록을 선택한다는 의미입니다. 이것이 우리의 의견으로는 정확한 비교를 가능하게 합니다.
실험 결과, 순위 블록의 99.73%에 대해 FE 알고리즘이 다른 도메인을 선택하는 것으로 나타났습니다. - 최고는 아닙니다. 따라서 적어도 이 이미지의 경우 FE 알고리즘에 채택된 도메인 선택 절차가 비교되는 블록의 근접성을 완전히 반영하지 못한다고 주장할 수 있습니다.
결론
수행된 연구와 실험의 결과, 다음과 같은 고려사항이 나타났다.
1. 압축 효율성은 원본 이미지의 초기 분할에 따라 크게 좌우되는 것이 타당해 보입니다. 실제로 성공적인 도메인을 포함하지 못하거나 잘못된 도메인 삭제는 압축 비율과 디코딩 품질 모두에 영향을 미칩니다. 선험적으로 인접한 가까운 픽셀 간의 차이는 일반적으로 무작위로 선택된 영역보다 덜 눈에 띄는 것이 타당해 보입니다. 이러한 이유로 초기에 형성된 세트에 프린징 도메인을 포함시키는 것이 유망해 보입니다.
2. 계산량을 획기적으로 줄이기 위해 단순화된 기준 세트를 도입한다는 아이디어는 매력적이지만, 도메인을 순위와 비교하는 경우 대부분의 경우 이 세트에서는 최적의 도메인을 식별할 수 없습니다. 즉, 이 세트는 주요 기준에 완전히 적합하지 않습니다. 따라서 이 세트 대신 기본 기준을 사용하는 것이 적절해 보이지만 문제의 도메인 순위 쌍의 축소된 복사본에 적용합니다.
3. 프랙탈 압축 방법의 이론적 기초에서 직접적으로 따르는 고려 사항도 발생합니다. 따라서 콜라주 정리에 따르면 압축 매핑 시스템의 어트랙터와 원본 이미지 간의 차이 정도는 생성된 매핑의 질적 특성에 따라 결정됩니다. 기본 알고리즘에 사용되는 가장 단순하고 대략적인 선형 모델에서 더 복잡한 비선형 모델로 이동할 때 증가를 예상하는 것은 당연합니다. 그런 점에서 그러한 모델을 사용하려는 시도는 타당해 보인다.
작업의 실질적인 중요성과 저자의 개인적인 기여는 두 가지 기본 알고리즘을 구현하고 모든 이미지에 대해 구현된 알고리즘의 작업을 자동으로 비교 분석할 수 있는 개발된 소프트웨어에 있습니다. 제시된 결과와 제안을 기반으로 알고리즘의 새로운 수정 사항을 소프트웨어로 구현하는 것은 개발 단계에 있습니다.
작업의 개별 단계에 대한 주요 조항은 젊은 과학자 및 학생을 위한 III 국제 과학 및 기술 컨퍼런스 "정보학 및 컴퓨터 기술"(Donetsk, DonNTU, 2007), 학생, 대학원생 및 젊은 학생을 위한 IV 국제 과학 컨퍼런스에서 발표되었습니다. 과학자 "컴퓨터 모니터링 및 정보 기술"(Donetsk, DonNTU, 2008).
* — 본 초록을 작성할 당시에는 아직 석사논문이 완성되지 않은 상태입니다. 최종 완성은 2008년 12월 1일에 이루어집니다. 논문의 텍스트와 자료는 이 날짜 이후 저자나 지도교수로부터 얻을 수 있습니다.
실제로 이 기사에서는 프랙탈 알고리즘의 실제 적용에 대해 논의할 것입니다. 프랙탈 아트에 대해서는 이전 기사에서 충분히 자세히 설명했습니다.
프랙탈 이미지 압축.
프랙탈 알고리즘의 최초이자 명백한 적용은 소위 말하는 것이었습니다. 프랙탈 이미지 압축. 프랙탈 이미지 압축- 애플리케이션 기반 손실 영상 압축 알고리즘 반복 가능한 함수 시스템이미지에. (반복 가능한 함수 시스템, 간단히 SIF는 하나의 다차원 집합을 다른 집합으로 매핑하는 특정 고정 클래스 함수의 함수 시스템입니다.) 이 알고리즘은 경우에 따라 매우 높은 압축률을 얻을 수 있다는 사실로 알려져 있습니다. 비율(가장 좋은 예는 원칙적으로 다른 이미지 압축 알고리즘에서는 접근할 수 없는 자연 물체의 실제 사진에 대해 최대 1000배(허용되는 시각적 품질 기준)입니다.
방법의 기초 프랙탈 코딩- 이미지에서 자기 유사 영역을 감지하는 것입니다. 반복 함수 시스템 이론을 이미지 압축 문제에 적용할 가능성은 Michael Barnsley와 Alan Sloan이 처음으로 탐구했습니다.
마이클 반슬리.
그들은 1990년과 1991년에 그들의 아이디어에 대해 특허를 받았습니다.프랙탈 아카이브는 반복 함수 시스템의 계수를 사용하여 이미지가 보다 컴팩트한 형태로 표시된다는 사실을 기반으로 합니다. 이 과정은 Barnsley 자신의 저서 Fractal Image Compression에서 가장 명확하게 입증되었습니다. 원본 사진이 표시되는 화면과 이미지를 다른 화면에 투사하는 렌즈 시스템으로 구성된 복사기 개념을 도입했습니다. 각 렌즈는 원본 이미지의 일부를 투사합니다. 렌즈를 배열하고 특성을 변경하여 결과 이미지를 제어할 수 있습니다. 렌즈에는 요구 사항이 적용됩니다. 즉, 이미지의 투사된 부분의 크기를 줄여야 합니다. 또한 조각의 밝기를 변경하고 원이 아닌 임의의 경계가 있는 영역을 투영할 수 있습니다.
기계의 한 단계는 원본 이미지를 투영하여 새로운 기계를 구성하는 것입니다. 어떤 단계에서는 이미지가 더 이상 변경되지 않을 것이라고 명시되어 있습니다. 이는 렌즈의 위치와 특성에만 의존하며 원본 이미지에는 의존하지 않습니다. 이 이미지를 이 SIF의 고정점 또는 어트랙터라고 합니다. 콜라주 정리(프랙탈 압축의 원리 중 하나)는 각 SIF에 대해 정확히 하나의 고정점이 존재함을 보장합니다. 렌즈 매핑은 압축적이므로 각 렌즈는 이미지의 자기 유사 영역을 명시적으로 정의합니다. 자기 유사성 덕분에 어떤 배율에서도 복잡한 이미지 구조를 얻을 수 있습니다.
SIF를 사용하여 얻은 가장 유명한 두 이미지는 Sierpinski 삼각형과 Barnsley 양치류입니다. 첫 번째는 3개에 의해 제공되고 두 번째는 5개의 아핀 변환(또는 우리 용어로는 렌즈)에 의해 제공됩니다. 각 변환은 문자 그대로 몇 바이트로 지정되는 반면, 도움을 받아 구성된 이미지는 몇 메가바이트를 차지할 수 있습니다.
반슬리 고사리(왼쪽)와 시에르핀스키 삼각형(오른쪽).
아카이버의 작동 방식과 시간이 많이 걸리는 이유가 분명해졌습니다. 실제로 프랙탈 압축은 이미지에서 자기 유사 영역을 검색하고 해당 영역에 대한 아핀 변환 매개변수를 결정하는 것입니다.
최악의 경우, 최적화 알고리즘을 사용하지 않으면 다양한 크기의 가능한 모든 이미지 조각을 열거하고 비교해야 합니다. 작은 이미지의 경우에도 불연속성을 고려하면 분류할 수 있는 옵션이 천문학적으로 많습니다. 예를 들어, 특정 횟수만 확장하여 변환 클래스를 크게 좁히더라도 허용 가능한 시간을 달성할 수 없습니다. 게다가 이미지 품질도 떨어집니다. 프랙탈 압축 분야의 대부분의 연구는 이제 고품질 이미지를 얻는 데 필요한 보관 시간을 줄이는 것을 목표로 합니다.
의학에서 프랙탈의 응용.
현재 프랙탈은 의학에 응용되고 있으며 아마도 그럴 것입니다. 인체 자체는 순환계, 근육, 기관지 등 많은 프랙탈과 유사한 구조로 구성됩니다.
인체의 프랙탈 구조의 예: 기관지, 혈관, 근육.
따라서 과학자들은 프랙탈 알고리즘을 사용하여 질병을 진단하거나 치료하는 것이 가능한지 궁금해했습니다. 가능하다는 것이 밝혀졌습니다. 예를 들어, 프랙탈 이론을 사용하여 심전도를 분석할 수 있습니다. 최근 몇 년 동안 선진국에서는 심혈관 질환 진단 및 치료를 위한 새로운 실험실 및 도구 방법 개발의 명백한 성공에도 불구하고 계속해서 성장하고 있습니다. 바이오리듬 기간, 특히 약 1시간, 하루 이상 지속되는 심박수는 히스토그램이나 스펙트럼 분석의 전통적인 방법을 사용하여 연구할 수 있습니다. 그러나 프랙탈 차원의 시간 구조와 리듬, 허스트 지수를 평가하면 항상성 장애와 특정 질병의 발병을 초기 단계에서 더 정확하고 정보 내용으로 판단할 수 있습니다.
심전도의 예.
프랙탈은 의료용 X선 이미지를 처리하는 데에도 사용할 수 있습니다(아직 성공적인 실험 단계에 있음).
엑스레이의 예.
프랙탈 알고리즘을 사용하여 처리된 X선 이미지는 더 나은 이미지를 제공하므로 더 나은 진단이 가능합니다!!
프랙탈을 적극적으로 사용할 수 있는 또 다른 의학 분야는 위장병학입니다. 지금까지, 그리고 오늘날에도 종종 프로브 방법을 사용하여 위장 질환을 진단하는데, 이는 다양한 두께의 프로브를 도입해야 하는 필요성과 관련되어 환자와 의료진 모두에게 불쾌감을 줍니다. 또한 이러한 연구 기술은 신체적으로 심각한 환자, 수술 후 초기 환자 등에서 사용할 수 없기 때문에 적용 범위가 크게 좁아집니다. 위와 장의 운동 대피 활동에 대한 연구뿐만 아니라 질적으로뿐만 아니라 위장관의 여러 부분의 운동 활동의 강도와 특성을 정량적으로 평가합니다. MEF를 연구하는 추가 방법으로는 장기의 전기적 활동을 측정하는 방법이 사용됩니다. 위장관 기관의 생체전기 활동에 대한 연구는 위장관검사(electrogastroenterography)라고 불리는 새로운 의학 연구 방법의 기초를 마련했습니다. 위장관검사(Electrogastroenterography)는 위, 십이지장 및 기타 위장관 부위의 생체전기 활동을 평가할 수 있는 연구 방법입니다.
심전도검사의 예.
이는 위장관의 전위 변화를 기록하는 것, 즉 전기위장검사(EGEG)를 기반으로 합니다. 장기로부터 수신된 생체전기 신호에 프랙탈 분석을 적용하면 장기 및 위장관의 운동 기능을 효과적으로 판단하고 다양한 질병을 성공적으로 진단할 수 있습니다.
또한 미국 과학자들의 최근 발견에 대해 언급할 필요가 있습니다. 즉, 물리학에서 접착 맵(물리학의 접착(라틴어 adhaesio - 접착) - 서로 다른 고체 및/또는 액체 표면의 접착)을 작성하면 정상 표면과 액체 표면의 접착이라는 것입니다. 암세포의 경우, 이 지도들은 서로 다른 프랙탈 차원을 가지고 있다는 것이 밝혀질 것입니다. 아마도 미래에 이 발견은 암을 진단하고 치료하기 위한 새롭고 효과적인 방법을 발견하는 데 도움이 될 것입니다.
암과 정상 세포 표면의 접착 지도
자연과학에서의 프랙탈의 응용.
자연 과학 분야에서 프랙탈의 적용은 매우 엄청납니다. 모든 것을 설명한다면 책 한 권으로는 충분하지 않을 것입니다. 따라서 우리는 가장 흥미로운 측면 중 일부에 중점을 둘 것입니다.
프랙탈은 지질학과 지구물리학에서 자주 사용됩니다. 섬과 대륙의 해안이 특정 프랙탈 차원을 가지고 있다는 것은 비밀이 아니며 어느 것이 해안의 길이를 매우 정확하게 계산할 수 있는지 알 수 있습니다.
프랙탈 분석은 또한 프랙탈 메커니즘에 따라 분포가 자주 발생하는 광물 매장지의 검색 및 개발에도 도움이 됩니다. 단층 구조론과 지진에 대한 연구는 때때로 프랙탈 알고리즘을 사용하여 연구되기도 합니다.
지구물리학은 프랙탈과 프랙탈 분석을 사용하여 자기장의 이상 현상을 연구하고, 파동의 전파와 탄성 매질의 진동을 연구하고, 기후와 기타 여러 가지를 연구합니다.
물리학에서는 프랙탈이 훨씬 더 널리 사용됩니다. 예를 들어, 고체 물리학에서 프랙탈 알고리즘을 사용하면 고체, 다공성, 해면체 및 다양한 에어로겔의 특성을 정확하게 설명하고 예측할 수 있습니다. 이는 독특하고 유용한 특성을 지닌 새로운 재료를 만드는 데 도움이 됩니다.
고체의 예로는 결정이 있습니다.
흐름의 난류에 대한 연구는 프랙탈에 매우 잘 적용됩니다. 난류 흐름은 혼란스럽기 때문에 정확하게 모델링하기가 어렵습니다. 그리고 여기에서 프랙탈 표현으로의 전환이 도움이 되며, 이는 엔지니어와 물리학자의 작업을 크게 촉진하여 복잡한 시스템의 역학을 더 잘 이해할 수 있게 해줍니다. 프랙탈을 사용하면 불꽃을 시뮬레이션할 수도 있습니다. 다공성 물질은 매우 복잡한 기하학적 구조를 가지고 있기 때문에 프랙탈 형태로 잘 표현됩니다. 그것은 석유 과학에 사용됩니다.
난기류.
통신에 프랙탈을 적용합니다.
통신에서 프랙탈은 프랙탈 안테나를 만드는 데 사용됩니다. 프랙탈 안테나는 상대적으로 새로운 종류의 전기 소형 안테나(EMA)로 알려진 솔루션과 구조가 근본적으로 다릅니다. 실제로 안테나의 전통적인 진화는 정수 차원의 객체(선, 원, 타원, 포물면 등)를 사용하여 작동하는 유클리드 기하학을 기반으로 했습니다. 놀랍도록 컴팩트한 디자인의 프랙탈 안테나는 소형 폼 팩터에서 뛰어난 광대역 성능을 제공합니다. 다양한 위치에 설치하거나 내장할 수 있을 만큼 컴팩트한 프랙탈 안테나는 해양, 항공기 또는 개인 장치에 사용됩니다.위 이미지는 프랙탈 안테나의 예입니다.
또한 네트워크 기술 분야에서도 다양한 유형의 네트워크를 통해 전송되는 트래픽의 자기 유사성을 보여주는 많은 연구가 진행되어 왔습니다. 이는 특히 음성, 오디오 및 비디오 서비스에 해당됩니다. 따라서 정보를 보다 효율적으로 전송하기 위해 네트워크를 통해 전송되는 트래픽의 프랙탈 압축 가능성에 대한 개발 및 연구가 현재 진행 중입니다.
시각화 및 특수 효과의 요소로서의 프랙탈.
프랙탈은 그 아름다움과 무한함으로 매력을 느끼고 매혹됩니다. 이것이 바로 프랙탈이 다양한 종류의 시각화, 비디오 설치, 컴퓨터 그래픽의 특수 효과 생성 등에 자주 사용되는 이유입니다.
게임부터 시작해 보겠습니다. 오늘날 다양한 종류의 자연 경관이 존재하는 많은 게임(아마도 Minecraft의 가장 놀라운 예)은 어떤 방식으로든 프랙탈 알고리즘을 사용합니다. 이 방법은 매우 효과적으로 입증되었습니다. 사실 실제 자연 물체는 근본적으로 프랙탈 구조를 가지고 있습니다. 이를 고려하여 프로그래머는 프랙탈 알고리즘을 기반으로 컴퓨터 환경을 만들려고 시도했습니다. 오늘날 아름다운 자연경관을 관찰할 수 있는 다양한 게임들을 관찰해보면, 성공적으로 성공했다는 결론을 내릴 수 있다. 또한 프랙탈 알고리즘을 기반으로 풍경과 풍경을 생성하기 위해 수많은 프로그램이 만들어졌습니다.
Fractal Landscapes 프로그램을 사용하여 프랙탈 알고리즘을 기반으로 한 풍경 모델링.
마인크래프트 게임 스크린샷.
영화는 프랙탈 없이는 할 수 없습니다. 실제로 영화에서도 게임처럼 다양한 환상적인 풍경을 연출하기 위해 동일한 원리가 사용됩니다. 실제로, 프랙탈 알고리즘으로 실행되는 컴퓨터 프로그램을 사용하면 이 모든 작업을 몇 배 더 빠르게 수행할 수 있는데 왜 매번 새로운 나무나 산을 만들고 이에 많은 시간을 소비합니까? 흥미로운 사실: 리들리 스콧(Ridley Scott)의 유명한 우주 공포 영화 에일리언(Alien)에서 팀이 행성 표면으로 하강하는 에피소드에서 우주선에 있는 모니터는 행성 표면의 이미지를 격자 형태로 전송합니다. 이것이 바로 프랙탈 기하학을 사용하여 만들어진 이미지입니다. 프랙탈 기하학을 사용하면 특수 효과 아티스트가 구름, 연기, 불꽃, 별이 빛나는 하늘 등과 같은 개체를 쉽게 만들 수 있습니다.
이제 프랙탈 애니메이션 주제를 조금 다루겠습니다. 다양한 생성기에서 생성된 프랙탈 이미지는 매우 아름답습니다. 그러면 프랙탈 애니메이션에 대해 뭐라고 말할 수 있겠습니까? 정말 놀라운 광경입니다. 우선, 전기양 자원을 언급할 가치가 있습니다. 전기양은 분산 컴퓨팅을 사용하여 프랙탈 불꽃 알고리즘(Scot Draves가 개발)을 기반으로 프랙탈 애니메이션을 생성하는 리소스입니다. 간단히 말해서, 컴퓨터를 사용하여 프랙탈 애니메이션을 계산하고 렌더링하는 동시에 소위 "라이브" 배경 화면 형식으로 완성된 프랙탈 애니메이션을 다운로드하여 표시하는 소프트웨어가 컴퓨터에 설치됩니다. 동시에, 이러한 동일한 배경화면은 컴퓨터의 특정 폴더에 저장되며 거기에서 꺼내어 비디오 편집과 같은 자신의 목적으로 사용할 수 있습니다(비디오 길이는 약간 짧습니다). - 5 초). 그러나 Apophysis 프로그램과 이를 위한 Apophymatator 스크립트를 마음대로 사용하면 원하는 만큼 자신만의 애니메이션을 쉽게 만들 수 있습니다(다행히도 인터넷에 이 주제에 대한 많은 강의가 있습니다). 가장 중요한 것은 귀하의 기계가 강력하다는 것입니다. 충분한.
전기양 애니메이션 스크린샷:
프랙탈 애니메이션의 광경은 VJ가 비디오 세트에서도 성공적으로 사용합니다. 이러한 비디오 설치는 특히 전자 음악 연주자의 콘서트에서 자주 사용됩니다. 이를 위해 소위 VJing 프로그램(예: Resolume)이 사용됩니다. Resolume 프로그램의 프랙탈 애니메이션 애니메이션 예:
프랙탈 애니메이션은 프랙탈 생성기와 직접 관련이 없는 프로그램 개발자가 시각화로 사용합니다. 예를 들어, 잘 알려진 Winamp 플레이어 세트에는 프랙탈 요소가 명확하게 표시되는(예: 애니메이션 Julia 세트) 시각화(밀크드롭 플러그인)가 많이 포함되어 있습니다. Winamp 플레이어용 Milkdrop 플러그인의 시각화 스크린샷:
따라서 이 짧은 검토를 수행한 후에도 오늘날 프랙탈과 프랙탈 알고리즘의 엄청난 실제 적용에 대해 자신있게 말할 수 있습니다. 프랙탈이 사용되는 영역은 매우 광범위합니다. 그리고 확실히 가까운 미래에 프랙탈이 사용될 영역 목록은 계속 확장될 것입니다!!!
기사 원문은 컴퓨아트(Compuart) 매거진 3월호에서 읽을 수 있습니다.
1. 프랙탈과 프랙탈 압축법의 역사
1992년 12월, 크리스마스 직전에 Microsoft는 새 CD인 Microsoft Encarta를 출시했습니다. 그 이후로 동물, 꽃, 나무, 그림 같은 장소에 대한 정보를 담은 이 멀티미디어 백과사전은 CD에 가장 인기 있는 백과사전 목록을 남기지 않았습니다. 최근 Microsoft 설문 조사에서 Encarta는 가장 가까운 경쟁자인 Compton Multimedia Encyclopedia를 제치고 다시 1위를 차지했습니다. 이러한 인기의 이유는 사용 용이성, 높은 품질의 제품, 그리고 가장 중요한 것은 많은 수의 재료에 있습니다. 디스크에는 7시간 분량의 사운드, 100개의 애니메이션 비디오, 약 800개의 확장 가능한 지도, 7000개의 고품질 사진이 포함되어 있습니다. 이 모든 것이 하나의 디스크에 담겨 있습니다! 압축되지 않은 일반 650MB CD에는 56분의 고품질 오디오, MPEG-1 형식의 320x200 해상도의 1시간 비디오 해상도 또는 640x480 크기의 풀 컬러 이미지 700개가 포함될 수 있습니다. 더 많은 정보를 수용하려면 상당히 효율적인 보관 알고리즘이 필요합니다. 비디오 및 오디오 보관 방법에 대해서는 다루지 않겠습니다. 새로운 유망 알고리즘인 그래픽 정보의 프랙탈 압축에 대해 이야기하겠습니다.
개념 "프랙탈"그리고 "프랙탈 기하학" (골절-조각으로 구성, 위도) 수학자에 의해 제안되었습니다. B. 만델브로트 1975년에 불규칙하지만 자기유사한 구조를 나타냄. 프랙탈 기하학의 탄생은 일반적으로 1977년 B. Mandelbrot의 저서 "자연의 프랙탈 기하학"의 출판과 관련이 있습니다. 이 책의 주요 아이디어 중 하나는 전통적인 기하학(즉, 선과 면을 사용하는)이 자연 물체를 표현하기가 극도로 어렵다는 것입니다. 프랙탈 기하학은 그것들을 매우 간단하게 정의합니다.
만델브로의 프랙탈 정의는 다음과 같습니다. "프랙탈은 어떤 의미에서 전체와 유사한 부분으로 구성된 구조입니다."
프랙탈의 주요 특성 중 하나는 자기 유사성입니다. 가장 간단한 경우, 프랙탈의 작은 부분에는 전체 프랙탈에 대한 정보가 포함되어 있습니다. 동적 시스템의 아름다운 이미지인 프랙탈은 이전에 컴퓨터 그래픽에서 주로 하늘, 나뭇잎, 산, 풀의 이미지를 구성하는 데 사용되었습니다. 아름답고 더 중요하게는 자연 물체를 확실하게 모방하는 이미지는 단지 몇 가지 계수로 지정될 수 있습니다.
프랙탈에는 다양한 종류가 있습니다. 잠재적으로 가장 유용한 유형의 프랙탈은 반복 함수 시스템을 기반으로 하는 프랙탈입니다. (반복 함수 시스템 - IFS). 방법 IFS위대한 전문가가 발명한 프랙탈 이미지 구성과 관련하여 마이클 반슬리그리고 주립 공과 대학의 그의 동료들. 그루지야 (조지아 공과대학)는 이미지 요소의 자기 유사성을 기반으로 하며 자체의 여러 작은 조각으로 그림을 모델링하는 것으로 구성됩니다. 특수 방정식을 사용하면 이미지 영역의 크기를 이동, 회전 및 변경할 수 있습니다. 따라서 이 영역은 나머지 그림의 구성 요소 역할을 합니다.
가장 놀랍고 유명한 것 중 하나 IFS-이미지는 검은색 양치류로, 각 잎은 실제로 양치류 자체의 축소판입니다(그림 참조). 그림이 아핀 변환 방법을 사용하여 컴퓨터로 생성되었다는 사실에도 불구하고 양치류는 실제 양치류와 똑같습니다. 자연은 식물과 나무의 유전적 구조를 암호화할 때 다음과 같은 방법을 사용한다고 제안되어 왔습니다. IFS-프랙탈.
IFS-프랙탈에는 매우 현실적이고 유용한 응용 프로그램이 있습니다. 큰 래스터 이미지를 일반 크기의 일부로 압축하는 데 사용할 수 있습니다. 이 진술은 정리에서 나온 것입니다. 바나흐수축 변환(또는 콜라주 정리) 이는 State Institute of Technology 연구원의 연구 결과입니다. 그루지야 마이클 반슬리지역에 IFS. 이 결론으로 무장한 그는 연구소를 떠나 자신의 발견에 대해 특허를 내고 회사를 설립했습니다. 반복 시스템 통합. 그는 잡지를 통해 자신의 업적을 세상에 알렸습니다. 바이트 1988년 1월. 그러나 역 문제, 즉 주어진 이미지에서 아핀 변환을 찾는 방법에 대한 정보는 없었습니다. 그 당시에는 이 문제에 대한 해결책의 힌트조차 없었습니다. 기사에서 반슬리여러 가지 사실적인 프랙탈 이미지가 표시되었지만 모두 손으로 만든 것입니다.
이상적으로는 모든 이미지에 대한 아핀 변환 시스템을 찾을 수 있기를 바랍니다. (IFSM), 주어진 정확도로 이미지를 재현합니다. 그러나 해결책은 조금 달랐습니다. 그걸 먼저 발견한 학생이었어 반슬리, 아르노 자캥. 제안된 방법은 다음과 같다. “분할된 반복 함수 시스템 - PIFS”. 이 체계에 따르면 이미지의 개별 부분은 전체 이미지와 유사하지 않고 일부만 유사합니다.
2. 프랙탈 압축의 수학적 기초
프랙탈 압축 방법을 사용하면 정보를 10,000배 압축할 수 있습니다. 알려진 모든 프랙탈 압축 프로그램은 1992년에 논문을 방어하면서 실용적인 프랙탈 압축 알고리즘을 설명한 Barnsley 직원인 Jackwin의 알고리즘을 기반으로 합니다. 이 작업의 확실한 장점은 압축 과정에서 인간의 개입이 완전히 제거되었다는 것입니다.
프랙탈 데이터 압축 메커니즘을 고려해 보겠습니다. 프랙탈 아카이브는 반복 함수 시스템의 계수를 사용하여 이미지가 보다 컴팩트한 형태로 표시된다는 사실을 기반으로 합니다. 보관 프로세스를 살펴보기 전에 IFS가 이미지를 구축하는 방법을 살펴보겠습니다. 엄밀히 말하면 IFS는 한 이미지를 다른 이미지로 변환하는 3D 아핀 변환 세트입니다. 3차원 공간(x좌표, y좌표, 밝기)의 점은 변환됩니다. 이 과정은 Barnsley 자신의 저서 Fractal Image Compression에서 가장 명확하게 입증되었습니다. 원본 사진이 표시되는 화면과 이미지를 다른 화면에 투사하는 렌즈 시스템으로 구성된 복사기 개념을 도입했습니다. 각 렌즈는 원본 이미지의 일부를 투사합니다. 렌즈를 배열하고 특성을 변경하여 결과 이미지를 제어할 수 있습니다. 렌즈에는 이미지의 투사된 부분의 크기를 줄여야 한다는 요구 사항이 적용됩니다. 또한 조각의 밝기를 변경하고 원이 아닌 임의의 경계가 있는 영역을 투영할 수 있습니다. 기계의 한 단계는 원본 이미지를 투영하여 새로운 기계를 구성하는 것입니다. 어떤 단계에서는 이미지가 더 이상 변경되지 않을 것이라고 명시되어 있습니다. 이는 렌즈의 위치와 특성에만 의존하며 원본 이미지에는 의존하지 않습니다. 이 이미지를 주어진 IFS의 고정점 또는 어트랙터라고 합니다. 콜라주 정리는 각 IFS에 대해 정확히 하나의 고정점이 있음을 보장합니다. 렌즈 매핑은 압축적이므로 각 렌즈는 이미지의 자기 유사 영역을 명시적으로 정의합니다. 자기 유사성 덕분에 어떤 배율에서도 복잡한 이미지 구조를 얻을 수 있습니다. IFS를 사용하여 얻은 가장 유명한 두 개의 이미지는 Sierpinski 삼각형과 Barnsley 고사리입니다. 첫 번째는 3개로 제공되고 두 번째는 마시는 아핀 변환(또는 용어로 렌즈)으로 제공됩니다. 각 변환은 문자 그대로 몇 바이트로 지정되는 반면, 도움을 받아 구성된 이미지는 몇 메가바이트를 차지할 수 있습니다. 아카이버의 작동 방식과 시간이 많이 걸리는 이유가 분명해졌습니다. 실제로 프랙탈 압축은 이미지에서 자기 유사 영역을 검색하고 해당 영역에 대한 아핀 변환 매개변수를 결정하는 것입니다. 최악의 경우, 최적화 알고리즘을 사용하지 않으면 다양한 크기의 가능한 모든 이미지 조각을 열거하고 비교해야 합니다. 작은 이미지의 경우에도 불연속성을 고려하면 분류할 수 있는 옵션이 천문학적으로 많습니다. 예를 들어, 특정 횟수만 확장하여 변환 클래스를 크게 좁히더라도 허용 가능한 시간을 달성할 수 없습니다. 게다가 이미지 품질도 떨어집니다. 프랙탈 압축 분야의 대부분의 연구는 이제 고품질 이미지를 얻는 데 필요한 보관 시간을 줄이는 것을 목표로 합니다.
따라서 프랙탈 압축 가능성에 대한 수학적 정당성을 고려해 보겠습니다.
가능한 모든 이미지 세트가 있는 매핑이 있습니다. 여매핑의 합집합입니다 승 나 :
이러한 매핑을 호출합니다. 압축, 다음 설명은 해당 항목에 해당됩니다.
어떤 이미지라면 에프 0 매핑을 반복적으로 적용하기 시작하겠습니다. 여~하도록 하다
이것이 최종 이미지입니다 에프~라고 불리는 유인자, 또는 매핑 W의 고정점. 변형된 경우에도 알려져 있습니다. 승 나압축되어 있고 그 결합은 여또한 압축적입니다.
3. 일반적인 프랙탈 압축 방식
위의 내용을 고려하면 압축 방식은 다음과 같습니다. 아르 자형조각조각 쪼개지다 아르 자형 나, 라고 불리는 순위 영역. 다음은 각 지역별로 아르 자형 나그 지역을 찾아라 디 나그리고 변신 승 나다음 조건이 충족되도록:
1. 디 나크기가 더 크다 아르 자형 나 .
2.w 나 (아르 자형 나 ) 모양, 크기, 위치가 동일합니다. 아르 자형 나 .
3. 계수 유변환 승 나 1보다 작아야 합니다.
4. 값은 가능한 한 작아야 합니다.
처음 세 가지 조건은 매핑을 의미합니다. 승 나압축됩니다. 그리고 네 번째 조건으로 인해 인코딩된 이미지는 아르 자형그리고 그의 이미지 승(R)서로 비슷할 것입니다. 이상적으로는 R = W(R). 이는 우리의 이미지를 의미합니다. 아르 자형고정된 지점이 될 것입니다 여. 여기에서 이미지의 여러 부분의 유사성이 사용됩니다(따라서 이름은 - "프랙탈 압축"). 결과적으로 거의 모든 실제 이미지에는 아핀 변환까지 서로 유사한 부분이 포함되어 있습니다.
따라서 이미지를 압축하려면 여필요하다:
1. 이미지를 순위 영역으로 나눕니다. 아르 자형 나(전체 이미지를 덮는 겹치지 않는 영역).
2. 각 순위 영역별 아르 자형 나지역 찾기 디 나(라고 불리는 도메인) 및 디스플레이 승 나, 위의 속성을 사용합니다.
3. 아핀 변환 계수를 기억하세요 여, 도메인 영역의 위치 디 나, 이미지를 도메인으로 나누는 것입니다.
따라서 이미지의 압축을 풀려면 다음이 필요합니다.
1. 초기 이미지를 만듭니다. 아르 자형 0 .
2. 매핑을 여러 번 적용합니다. 여(노동 조합 승 나).
3. 디스플레이 이후 여압축하면 결과적으로 충분한 반복 횟수 후에 이미지가 어트랙터에 도달하고 변경이 중지됩니다. 어트랙터는 우리의 원본 이미지입니다. 감압이 완료되었습니다.
이를 통해 배포 중에 여러 번 늘릴 수 있습니다. 특히 인상적인 것은 자연 물체의 이미지를 확대하면 이러한 물체에 고유한 새로운 세부 사항이 나타나는 예입니다(예를 들어 암석 사진을 확대하면 새롭고 작은 불규칙성이 획득됩니다).
4. 압축률 및 계산 비용 추정
순위 영역을 완전히 결정하기 위한 데이터 크기는 다음 공식을 사용하여 계산됩니다.
어디 NB그리고 Mb- 각 좌표를 저장하는 데 필요한 비트 수는 다음 공식을 사용하여 계산됩니다.
어디 V그리고 시간- 이미지의 수직 및 수평 크기, 크기- 도메인 블록 크기, 단계- 도메인 검색 단계.
변환을 저장하려면 티 3비트가 필요합니다.
보관용 유그리고 V각각 9비트와 7비트가 필요합니다.
예를 들어 256x256픽셀 크기의 이미지를 촬영하고 4픽셀 단위로 도메인 영역을 탐색해 보겠습니다.
Nd = Md = (256 - 8 + 1) / 4 = 62
Nb = Mb = CEIL(로그 2 62) = 6
Z = 12 + 3 + 6 + 6 = 27
압축비 에스금액
S = (8 * 8 * 8) / 27 = 19
압축 비율은 원하는 만큼 높지 않지만 압축 매개변수는 최적과는 거리가 멀고 비율이 크게 증가할 수 있습니다.
이제 이 알고리즘의 계산 복잡도를 추정해 보겠습니다. 압축 단계에서는 모든 도메인 영역(각각에 대해 1"024개 조각, 모든 순위 1개 조각, 58"081개 조각(1단계))을 열거하고 각 도메인 영역에 대해 차례로 8개의 변환을 모두 열거해야 합니다. 총계는 1"024 x 58"081 x 8 = 475"799"552개 작업입니다. 그러나 이러한 작업은 사소한 것이 아니며 부동 소수점 수의 곱셈 및 나눗셈 작업을 포함하는 여러 행렬 작업을 포함합니다.
불행하게도 최신 PC(그리고 이것이 바로 우리가 알고리즘을 구현하고자 했던 종류의 기계)에서도 크기가 256 x 256 픽셀에 불과한 이미지를 압축하는 데는 용납할 수 없을 정도로 오랜 시간이 걸립니다. 고려된 알고리즘에는 최적화가 필요하다는 것은 명백합니다.
키워드: 신경망; 이미지 압축; 기계 학습; 프랙탈.
주석
본 논문에서는 프랙탈 영상 압축을 위한 인코딩 시간을 줄이는 방법을 제시합니다. 이 접근 방식은 자체 구성 신경망을 사용하여 특징 추출과 도메인 분류를 결합합니다. 특징 추출을 통해 작업 크기가 줄어들고 신경망이 인코딩되는 이미지와 다른 이미지를 훈련할 수 있습니다. 분류를 위한 자체 구성 신경망은 클러스터 토폴로지 개념을 도입하고 또한 많은 적합한 이미지 클래스를 선험적으로 지정할 필요성을 제거합니다. 네트워크는 학습 과정에서 얻은 이미지 특성의 분포에 따라 자체적으로 구성됩니다. 이 논문은 분류 접근 방식이 비교 정확도와 압축 효율성을 유지하면서 인코딩 시간을 두 배로 줄일 수 있음을 보여주는 결과를 제시합니다.
1. 소개
프랙탈 이미지 인코딩은 인터넷 웹사이트와 같은 이미지 압축 애플리케이션에서 유망한 접근 방식입니다. 그러나 이 접근 방식의 코딩 단계에 필요한 시간은 실용적인 방법으로 채택하는 데 제한적인 장벽이었습니다. 인코딩 프로세스는 도메인 블록을 순위 이미지 블록으로 매핑하는 것입니다. 각 순위 블록에 대해 알고리즘은 순위 블록과 가장 잘 일치하는 도메인 블록 및 해당 변환을 검색합니다. 도메인 블록 분류는 검색해야 하는 도메인 수를 줄여 코딩 속도를 크게 높일 수 있습니다. 도메인 분류를 목적으로 자기 조직화 신경망을 사용하는 방법은 이미 연구되었습니다. 이러한 네트워크는 클래스 클러스터의 토폴로지를 식별하여 기본 분류 접근 방식보다 향상된 기능을 제공합니다. 이 작업의 기여는 자기 조직화 신경망을 사용한 도메인 분류와 특징 추출을 결합하여 더욱 빠른 이미지 인코딩을 가능하게 한다는 것입니다. 색조 및 질감 품질을 측정하는 작은 이미지 특징 세트가 각 도메인 및 순위 블록에 대해 계산됩니다. 따라서 각 블록에는 연관된 특성 벡터가 있으며, 그 크기는 블록 크기에 의존하지 않습니다. 특징 추출은 두 가지 이유로 유익합니다. 첫째, 문제 크기의 감소로 인해 도메인 검색 프로세스에 필요한 계산량이 줄어듭니다. 둘째, 특성은 특정 도메인의 구조와 독립적이기 때문에 하나의 이미지에서 자기 구성 네트워크를 훈련하고 결과 네트워크를 다른 이미지의 분류에 사용하는 것이 가능해집니다. 따라서 네트워크 훈련 시간은 총 인코딩 시간의 일부가 아닙니다. 프랙탈 이미지 인코딩 시간 측정은 일반적으로 Sun 또는 Silicon Graphics 워크스테이션에서의 실행 시간으로 표현됩니다. 여기에 제시된 접근 방식은 Pentium 120MHz PC에서 실행될 때 비슷한 측정값을 제공합니다.
2. 이미지의 프랙탈 코딩
이미지의 프랙탈 코딩은 반복 함수 시스템(이하 IFS로 약칭, 영어 반복 함수 시스템 - IFS) 이론을 기반으로 합니다. CIF 이론은 반복적인 방식으로 프랙탈 이미지를 구성하는 데 사용되는 고전적 분석의 수축 매핑 정리(이하 TOC, English Contraction Mapping Theorem - CMT에서 약칭)를 기반으로 합니다. 프랙탈 이미지는 TOS에서 보장하는 이미지 공간의 고정점이며, 이 이미지를 CIF 어트랙터라고 합니다. 프랙탈 이미지 코딩으로 해결되는 역 문제는 주어진 이미지를 고려하고 주어진 이미지에 가까운 이미지, 즉 어트랙터를 나타내는 SIF를 계산하는 것으로 시작됩니다. 프랙탈 이미지 코드는 일반적으로(항상은 아니지만) 원본 이미지보다 적은 저장 공간을 필요로 하므로 압축 기술이 됩니다. 경험적 결과에 따르면 프랙탈 방식은 오늘날 압축 표준으로 간주되는 JPEG만큼 우수한 경우가 많습니다.
프랙탈 이미지 압축은 분할 반복 함수 시스템(PIFS)이라는 특별한 유형의 PIF를 사용합니다. SICF는 완전한 메트릭 공간 X, 하위 도메인 세트 Di ⊂ X, i = 1,...,n 및 수축 변환 세트 wi ~: Di i → X, i = 1,...로 구성됩니다. ,N. 그레이스케일 이미지를 정사각형 영역 I 2 = I×I에 정의된 실제 값 f(x, y)의 함수로 간주합니다. w i ~ (x, y)를 다음과 같은 아핀 변환 I 2 → I 2로 둡니다.
단, w i ~는 가역적이고 (x,y) ∈ R i 입니다. 상수 s i는 함수 f의 값 범위를 확장하거나 좁히고 회색조 이미지에 대해 이야기하고 있으므로 대비를 제어합니다. 마찬가지로, 상수 oi는 회색조 값을 증가 또는 감소시키거나 밝기를 제어합니다. 변환 wi ~는 변환 wi 의 공간 구성요소라고 합니다.
기본 알고리즘은 다음과 같이 수행된다. 이미지를 겹치지 않는 직사각형 랭크 블록(Ri)으로 나눕니다. 블록 Ri는 동일한 크기일 수 있지만 가변 블록 크기를 사용하는 일종의 분할이 더 자주 사용되므로 작은 세부 정보가 포함된 이미지 부분을 작은 순위 블록으로 조밀하게 채울 수 있습니다. 여기에 제시된 결과는 에 설명된 쿼드트리 분할 방식을 사용하여 얻은 것입니다. 우리는 중첩될 수 있는 일련의 도메인 블록으로 이미지를 덮습니다. 도메인은 크기가 다양할 수 있으며 대개 수백, 수천 개에 이릅니다. 아핀 변환(2.1)은 |det A i |
 |
(2.3) |
작았습니다. 디지털화된 이미지의 경우 적분(2.3)은 픽셀에 대한 합산으로 대체됩니다. 최선의 wi를 찾은 후에도 값(2.3)이 미리 결정된 일부 오류보다 여전히 큰 경우 쿼드 트리 분할 방식은 순위를 4개의 작은 직사각형으로 분할하고 이러한 작은 블록에 대해 최적의 변환을 찾는 프로세스가 반복됩니다. 이 프로세스는 값(2.3)이 허용 가능한 오류보다 작아지거나 미리 결정된 최대 쿼드 트리 깊이에 도달할 때까지 계속됩니다. 이미지 f에 변환 W를 반복적으로 적용하여 이미지가 디코딩됩니다.
W(f)(x,y) = w i (f)(x,y) for (x,y) ∈ R i
변환(wi)이 올바르게 선택되면 반복 W0n(f)은 n의 충분한 값에 대해 원본 이미지에 가깝습니다. 인코딩 단계는 각 순위 블록에 대해 검색해야 하는 도메인의 수가 많고 도메인을 순위와 비교할 때마다 필요한 계산으로 인해 계산 집약적입니다. 이 작업에서는 인코딩 단계의 계산 요구 사항을 줄이는 것이 두 가지 방법으로 해결됩니다. 먼저 각 도메인과 랭크 블록별로 정의된 이미지 특성의 개념을 소개한다. 그런 다음 픽셀 자체의 값보다 더 적은 수의 이러한 특성 값을 기반으로 잠재적으로 적합한 도메인을 선택할 수 있습니다. 둘째, 자기 조직화 신경망을 이용하여 도메인 블록을 클러스터 토폴로지로 정리하는 것을 제안한다. 이는 네트워크가 순위 블록과 유사한 도메인 블록을 기능 공간에서 빠르게 찾을 수 있도록 하여 인코딩 시간을 더욱 단축합니다.
3. 특징 추출
이미지의 프랙탈 코딩 프로세스 속도를 높이는 한 가지 방법은 도메인 및 순위 블록을 설명하는 소수의 특성을 분리하는 것입니다. 그런 다음 도메인과 랭크 블록의 비교가 개별 픽셀이 아닌 이러한 특성을 기반으로 수행되므로 작업량이 줄어듭니다. 이 작업에서는 이미지의 질감 분포와 대비를 설명하는 6가지 특성이 사용됩니다. 특징 추출 자체는 인코딩 프로세스에 상당한 속도 향상을 제공합니다.
여기에는 다음 6가지 특성이 사용됩니다. 1) 표준 편차, σ; 2) 픽셀 값과 블록의 평균값 사이의 차이의 세제곱의 합인 비대칭성(왜곡도)은 세제곱 σ로 정규화됩니다. 3) 이웃 픽셀 값 간의 차이를 측정하는 픽셀 간 대비(이웃 대비); 4) 베타(beta)는 픽셀 값이 블록 중앙의 값과 얼마나 다른지 보여줍니다. 5) 블록 픽셀 값의 수평 변화를 특징으로 하는 수평 그라데이션; 6) 블록 픽셀 값이 위에서 아래로 변화하는 것을 특징으로 하는 수직 그라데이션. 도메인과 랭크 블록 간의 매칭 과정에서 대비와 밝기가 변하므로 평균 픽셀 값은 특징으로 사용하지 않습니다. 특징 공간에서 거리를 비교할 때 특징 벡터는 큰 특징 값이 비교를 지배하지 않도록 정규화됩니다.
4. 자기 조직화 신경망
다음으로 개선할 수 있는 점은 이러한 특성을 바탕으로 도메인과 순위를 분류하고 유사한 클래스의 도메인끼리만 순위를 비교하는 것입니다. 여기에 사용된 도메인 분류 체계는 자체 구성 코호넨 신경망을 기반으로 합니다. 이 유형의 네트워크는 노드 위치의 격자로 구성됩니다. 각 격자 노드는 특성 벡터의 차원과 동일한 차원을 갖는 가중치 벡터와 연관됩니다. 여기에 사용된 특징 벡터의 차원은 6입니다. 그리고 여기에 사용된 노드 격자는 10개의 행과 10개의 열로 구성됩니다. 각 노드는 이미지 도메인 블록 클래스를 나타내므로 총 노드 수를 아주 작게 유지하는 것이 목표입니다. 고차원 행렬과 같은 노드를 구성하는 다른 방법을 고려할 수 있습니다.
학습 과정은 사람의 통제 없이 독립적으로 진행됩니다. 가중치 벡터 네트워크는 임의의 값으로 초기화됩니다. 그런 다음 네트워크는 입력 특징 벡터를 수신하고 입력 벡터에 가장 가까운 가중치 벡터를 찾습니다. 즉, 우리는 i'j'를 다음과 같이 찾습니다.
||v – w i'j' || ≤ ||v – w ij || 나, j 모두를 위해
여기서 v는 입력 특징 벡터이고 w는 노드 ij의 가중치 벡터입니다. 선택한 가중치 w i'j'에 대해 격자에서 인접한 가중치는 입력 벡터와 더 유사하도록 조정됩니다. 이 적응은 공식으로 표현됩니다
w ij new = w ij old + ε·exp(α·||v–w ij old || 2)·(v– w ij old)
여기서 ij는 노드 i'j' 근처에 있는 노드의 인덱스입니다. 이 이웃의 크기는 학습 과정이 새로 반복될 때마다 감소합니다. 매개변수 ε는 반복 단계이고 α는 이 단계에 반비례합니다. 제시된 결과의 소프트웨어 구현이 제공됩니다.
네트워크가 훈련되면 주어진 이미지에 대한 도메인 블록은 특징 공간에서 가장 가까운 가중치 벡터를 각각에 할당하여 분류됩니다. 랭킹 블록의 특성 벡터가 네트워크에 들어오면 이는 네트워크의 가중치 벡터와도 연관됩니다. 그런 다음 순위 블록은 이 가중치 벡터와 관련된 도메인뿐만 아니라 네트워크 격자의 인접한 가중치 벡터와 관련된 도메인과도 비교됩니다. 자기 구성 신경망을 기반으로 한 분류의 장점은 이미지 클래스를 인접한 클래스로 구성한다는 아이디어에 있으며 이는 네트워크 격자에 의해 보장됩니다. 또 다른 장점은 이미지 클래스를 미리 정의할 필요 없이 이미지 유형의 클러스터링이 발생한다는 것입니다.
5. 결과
표 1은 그림 1과 2에 표시된 이미지에 적용된 세 가지 다른 방법을 사용하여 프랙탈 이미지 압축을 비교한 결과를 나타냅니다. "기본" 방법은 도메인 분류 없이 에서 설명한 표준 쿼드 트리 분할 방법입니다. "쿼드트리 레벨" 값은 쿼드트리의 최대 허용 깊이를 나타냅니다. 여기서 숫자가 크면 랭크 블록이 작아지고, 이는 디코딩된 이미지의 품질이 좋아지지만 동시에 압축률이 나빠집니다. "오류 임계값"은 순위 블록을 쿼드 트리의 다음 상위 레벨의 더 작은 블록으로 분할하는 조건을 제어하는 매개변수입니다. 오류 값은 원본 비트맵을 6번의 반복을 사용하여 디코딩된 이미지와 비교하여 계산됩니다(반복 횟수가 많을수록 오류가 약간 작아집니다). "평균 오류"는 픽셀당 평균 오류이고, "PSNR"은 에서와 같이 계산된 피크 신호 대 잡음비입니다. "FO"(features-only) 방법은 섹션 3에서 설명한 6가지 특성을 기반으로 도메인과 순위 블록을 비교합니다. 마지막 방법("SO")은 위에서 설명한 대로 자체 구성 기능 추출 신경망을 사용하여 도메인을 분류합니다. 각 경우에 총 320개의 도메인 블록이 사용되었습니다. 도메인이 많을수록 인코딩 시간이 길어지고 압축률이 어느 정도 향상됩니다.
압축률은 원본 비트맵의 66614바이트에 대한 각 순위 블록의 평균 4바이트 비율로 추정됩니다. SO 방법은 FO 방법보다 약 2배 빠르며 기본 방법보다 100배 빠릅니다("블록당 시간"은 최종 이미지 정밀도와 무관한 실행 시간 측정을 나타냅니다. 여기에 제공된 시간은 Pentium에 대한 것입니다). 120MHz PC). 자기 조직화 네트워크는 여기에 제시된 두 이미지와는 다른 이미지에 대해 별도로 훈련되었으므로 훈련 시간은 이 방법의 총 시간에 포함되지 않습니다. 가속 방법과 기본 방법 모두에서 디코딩된 이미지의 압축 정도와 품질은 비슷합니다.
표 1 - 자체 구성 도메인 분류("SO" 방법), 특성만을 기반으로 한 도메인 비교("FO") 및 기본 방법("Base")을 사용한 프랙탈 이미지 압축 결과
영상 |
오류 임계값 |
쿼드 트리 수준 |
블록 수 |
시간, (들) |
블록당 시간(초) |
평균 오류, % |
계수. 압축 |
||
|---|---|---|---|---|---|---|---|---|---|
 |
|||||||||
| (ㅏ) | (비) |
그림 2 - (a): 원본 래스터 이미지 “Leaves”(256×256, 256 회색조); (b): 디코딩된 이미지(6회 반복, 쿼드 트리 레벨 7, 평균 픽셀 오류 3.05%, 압축 1.6:1). 이 이미지의 세부 수준이 높을수록 성능이 저하됩니다.
6. 결론
특징 추출과 자기 조직화 신경망을 통한 도메인 분류를 결합하면 코딩 속도가 크게 향상됩니다. 적은 수의 특징을 기반으로 이미지를 분류하면 관련된 계산량이 줄어들 뿐만 아니라 네트워크가 인코딩되는 이미지가 아닌 다른 이미지에 대해 훈련할 수 있으므로 전체 인코딩 시간에서 훈련 시간이 제거됩니다. 자체 구성 네트워크는 고유한 대표 도메인 클래스 집합을 설정하고 도메인 클래스의 클러스터 토폴로지도 정의합니다.
문학
- E. DeJesus, “걷고, 말하는 웹”, 바이트, 1997년 1월, 81-84.
- Y. Fisher, ed., Fractal Image Compression, (뉴욕: Springer-Verlag, 1995).
- A. Jacquin, "반복 수축 이미지 변환의 프랙탈 이론을 기반으로 한 이미지 코딩", IEEE Trans. 이미지 처리 1, 1992, 18-30.
- A. Bogdan 및 H. Meadows, "반복 변환 이론을 기반으로 한 이미지 코딩을 위한 Kohonen 신경망", Proc. SPIE 1766, 1992, 425-436.
- R. Hamzaoui, "프랙탈 이미지 압축을 위한 자체 구성 맵을 통한 코드북 클러스터링", NATO ASI Conf. 프랙탈 이미지 인코딩 및 분석, 1995년 7월.
- M. Barnsley, 도처에 있는 프랙탈, 2판. (보스턴: 학술 출판부, 1993).
- T. Kohonen, 자기 조직화 및 연관 기억, (Springer-Verlag, 1989).
- S. Welstead, C/C++의 신경망 및 퍼지 논리 응용 프로그램(뉴욕: John Wiley and Sons, 1994).
벡터 양자화를 사용하면 디지털 신호의 N 샘플 그룹이 동시에 인코딩됩니다( N-차원 벡터). 1차원 신호의 경우 벡터는 다음의 그룹이 될 수 있습니다. N연속 카운트. 이미지의 경우 벡터는 수평 및 수직으로 인접한 여러 이미지 요소의 블록일 수 있습니다. 그림에서. 그림 5.54는 벡터 양자화를 사용하는 정보 전송 시스템의 블록 다이어그램을 보여줍니다.
벡터 양자화의 의미는 다음과 같습니다. 신호에서 발생하는 모든 것의 집합 N-차원 벡터는 다음과 같이 나뉩니다. 엘각 부분집합에 포함된 벡터가 서로 거의 다르지 않도록 부분집합을 만듭니다. 각 하위 집합에서 해당 하위 집합의 모든 벡터를 나타내기 위해 하나의 참조 벡터가 선택됩니다. 모든 참조 벡터는 코드북에 기록되고 각각에는 특정 코드워드가 할당됩니다.
디지털 입력 x(n)인코더 입력으로 옵니다. 인코딩 절차는 코드북의 각 N차원 벡터에 대해 가장 가까운 참조 벡터가 있고 그 코드가 인코더의 출력으로 전송된다는 것입니다. 따라서 각 그룹에 대해 N- 입력 신호 샘플 x(n)하나의 코드워드가 전송된다 너(케이).
수신된 코드워드에 따른 디코더에서 너(케이)(막대는 신호가 통신 채널에 도착했음을 나타냅니다.) 참조 벡터는 코드북에서 판독되어 다음 그룹으로 변환됩니다. N출력 신호 샘플 와이(엔). 코드북은 인코딩되는 신호의 속성에 따라 달라질 수 있습니다.
벡터 양자화는 손실이 있는 압축 방법이며, 실제 그룹은 N입력 신호 샘플 엑스(엔)출력 신호에서 와이(엔)참조 자료로 대체됩니다. N- 차원 벡터. 벡터 양자화의 장점 중 하나는 코드북에서 참조 벡터를 읽는 작업만 수행하는 디코더의 단순성입니다.
동시에, 인코딩되는 참조 벡터에 가장 가까운 참조 벡터를 인코더에서 검색하려면 많은 양의 계산이 필요합니다. 양자화 오차 제곱의 최소값에 도달하면 코드북에서 가장 가까운 참조 벡터를 읽습니다. 이자형 :
이자=에스 (a j -b j) 2 ,
어디 에이 j- 입력 벡터의 요소; 비제이– 참조 벡터의 요소.
벡터 양자화에 가까운 것은 프랙탈 이미지 코딩으로, 원본 이미지 자체에서 잘라낸 블록을 코드북 요소로 사용합니다.
프랙탈 압축 방법은 원본 이미지 자체에서 다양한 방식으로 잘라낸 블록을 코드북 요소로 사용하는 벡터 양자화의 변형으로 간주할 수 있습니다. 인코딩된 이미지의 블록을 변환하여 이러한 블록을 참조 블록과 유사하게 만들 수 있습니다(회전, 거울 반사). 벡터 양자화 및 프랙탈 코딩은 텔레비전에 사용되어 상당한 정보 압축을 제공합니다.
그러나 인코딩에 관련된 많은 양의 계산으로 인해 디지털 텔레비전 시스템에서 이러한 방법을 사용하는 것이 불가능합니다.
통제 질문
1. JPEG 표준에 따라 컬러 이미지 블록은 어떤 순서로 인코딩됩니까?
2. DCT 계수의 양자화가 이미지 자체의 양자화보다 눈에 띄는 왜곡을 덜 일으키는 이유는 무엇입니까?
3. JPEG 표준은 압축 정도를 어떻게 제어합니까?
4. 가변 길이 코드워드를 사용한 코딩의 본질은 무엇입니까?
5. MPEG-1, MPEG-2 표준과 관련하여 "하이브리드 코딩"이라는 용어는 무엇을 의미합니까?
6. MPEG-1, MPEG-2를 인코딩하기 전에 GOP에서 프레임을 재배열하는 이유는 무엇입니까?
7. MPEG-1, MPEG-2의 프레임 인코딩 모드와 필드 인코딩 모드의 차이점은 무엇입니까?
8. 왜? 비-프레임이 최고 수준의 압축을 달성했습니까?
9. MPEG-2 인코더에서 버퍼 메모리의 목적은 무엇입니까?
10. 확장성이란 무엇입니까?
11. MPEG-2 레벨과 프로필이란 무엇입니까?
12. MPEG-2 전송 스트림에서 다양한 TV 프로그램의 데이터는 어떻게 추출됩니까?
