Görüntü sıkıştırma: JPEG ve JPEG2000. Biçimler - jpeg kod çözücü ayrıntıları

• öğretici

UPD. Tek aralıklı biçimlendirmeyi kaldırmak zorunda kaldım. Güzel bir gün, habraparser ön ve kod etiketlerinin içindeki biçimlendirmeyi algılamayı bıraktı. Tüm metinler bir karmaşaya dönüştü. Habr yönetimi bana yardım edemedi. Şimdi düzensiz, ama en azından okunabilir.

Hiç bir jpg dosyasının nasıl çalıştığını bilmek istediniz mi? Şimdi çözelim! Favori derleyicinizi ve altıgen düzenleyicinizi ısıtın, hadi şunu çözelim:

Özel olarak daha küçük bir çizim aldı. Bu, Google'ın tanıdık ama yoğun biçimde sıkıştırılmış favicon'udur:

Açıklamanın basitleştirilmiş olduğu ve sağlanan bilgilerin tam olmadığı konusunda sizi hemen uyarıyorum, ancak o zaman spesifikasyonu anlamak kolay olacaktır.

Kodlamanın nasıl gerçekleştiğini bilmeden bile dosyadan bir şeyler çıkartabiliriz.
- işaretleyiciyi başlat. Her zaman tüm jpg dosyalarının başındadır.
Bayt takip eder. . Bu, bir yorum bölümünün başlangıcını işaretleyen bir işaretçidir. Sonraki 2 bayt - bölüm uzunluğu (bu 2 bayt dahil). Yani sonraki iki - yorumun kendisi. Bunlar ":" ve ")" karakter kodlarıdır, yani. normal gülen Hex editörünün sağ tarafındaki ilk satırda görebilirsiniz.

biraz teori

Adım adım çok kısa:
Bu verilerin kodlanabileceği sırayı düşünelim. İlk başta Y kanalının tüm görüntü için kodlandığını, ardından Cb'nin ve ardından Cr'nin kodlandığını varsayalım. Herkes çevirmeli ağda resim yüklemeyi hatırlar. Bu şekilde kodlanmış olsalardı, ekranda görünmeden önce tüm görüntünün yüklenmesini beklememiz gerekirdi. Dosyanın sonunun kaybolması da rahatsız edici olacaktır. Muhtemelen başka iyi sebepler de vardır. Bu nedenle, kodlanmış veriler küçük parçalar halinde dönüşümlü olarak düzenlenir.

Her Y ij , Cb ij , Cr ij bloğunun Huffman kodlarıyla kodlanmış bir DCT katsayıları matrisi olduğunu hatırlatmama izin verin. Dosyada aşağıdaki sırayla bulunurlar: Y 00 Y 10 Y 01 Y 11 Cb 00 Cr 00 Y 20

Dosya okuma

Yorumu çıkardıktan sonra şunu anlamak kolay olacaktır:

• Dosya, önünde işaretleyiciler bulunan sektörlere bölünmüştür.
• Belirteçler, ilk bayt ile birlikte 2 bayt uzunluğundadır.
• Hemen hemen tüm sektörler, uzunluklarını işaretçiden sonraki 2 baytta saklar.

Kolaylık sağlamak için işaretleri vurgulayın:
FF D8 FF FE 00 04 3A 29 FF DB 00 43 00 A0 6E 78



FF FF FF FF FF FF FF FF FF FF FF FF FF FF DB 00
43 01 AA B4 B4 F0 D2 F0 FF FF FF FF FF FF FF FF
FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF
FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF
FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF
FF FF FF C0 00 11 08 00 10 00 10 03 01 22 00 02
11 01 03 11 01 FF C4 00 15 00 01 01 00 00 00 00
00 00 00 00 00 00 00 00 00 03 02 FF C4 00 1A
10 01 00 02 03 01 00 00 00 00 00 00 00 00 00 00
00 01 00 12 02 11 31 21 FF C4 00 15 01 01 01 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 01FF
C4 00 16 11 01 01 01 00 00 00 00 00 00 00 00 00
00 00 00 00 11 00 01 FF DA 00 0C 03 01 00 02 11
03 11 00 3F 00AE E7 61 F2 1B D5 22 85 5D 04 3C
82 C8 48 B1 DC BF FF D9

İşaretleyici: DQT - niceleme tablosu.

FF DB 00 43 00 A0 6E 78
8C 78 64 A0 8C 82 8C B4 AA A0 BE F0 FF FF F0 DC
DC F0 FF FF FF FF FF FF FF FF FF FF FF FF FF FF
FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF
FF FF FF FF FF FF FF FF FF FF FF FF FF

Bölüm başlığı her zaman 3 bayttır. Bizim durumumuzda, bu . Başlık şunlardan oluşur:
Uzunluk: 0x43 = 67 bayt
Tablodaki değerlerin uzunluğu: 0 (0 - 1 bayt, 1 - 2 bayt)
[_0] Tablo Kimliği: 0
Kalan 64 baytın 8x8 tabloyu doldurması gerekir.

Tablo değerlerinin doldurulduğu sıraya daha yakından bakın. Bu sıraya zikzak sıra denir:

İşaretleyici : SOF0 - Temel DCT

Bu işaretçiye SOF0 adı verilir; bu, görüntünün temel yöntemde kodlandığı anlamına gelir. Çok yaygın. Ancak internette, önce düşük çözünürlüklü bir görüntü, ardından normal bir resim yüklendiğinde, bildiğiniz aşamalı yöntem daha az popüler değildir. Bu, tam indirmeyi beklemeden orada gösterilenleri anlamanızı sağlar. Spesifikasyon birkaç tane daha tanımlıyor, bana öyle geliyor ki, çok yaygın yöntemler değil.

FF C0 00 11 08 00 10 00 10 03 01 22 00 02
11 01 03 11 01

Uzunluk: 17 bayt.
Hassasiyet: 8 bit Temel yöntemde her zaman 8. Anladığım kadarıyla kanal değerlerinin bit derinliği bu.
Resim Yüksekliği: 0x10 = 16
Desen Genişliği: 0x10 = 16
Bileşen sayısı: 3. Çoğu zaman Y, Cb, Cr'dir.

1. bileşen:
Kimlik: 1
Yatay incelme (H 1): 2
[_2] Dikey incelme (V 1): 2
Niceleme tablosu kimliği: 0

2. bileşen:
Kimlik: 2
Yatay incelme (H 2): 1
[_1] Dikey incelme (V 2): 1

3. bileşen:
Kimlik: 3
Yatay incelme (H 3): 1
[_1] Dikey incelme (V 3): 1
Niceleme tablosu tanımlayıcısı: 1

Şimdi bir görüntünün ne kadar inceltildiğini nasıl belirleyeceğinize bakın. H max \u003d 2 ve V max \u003d 2 buluyoruz. Kanal i, yatay olarak H max /H i kez ve dikey olarak V max /V i kez kırılacaktır.

İşaretleyici: DHT (Huffman şeması)

Bu bölüm, Huffman kodlaması ile elde edilen kodları ve değerleri saklar.

FF C4 00 15 00 01 01 00 00 00 00
00 00 00 00 00 00 00 00 00 00 03 02

uzunluk: 21 bayt.
sınıf: 0 (0 - DC katsayı tablosu, 1 - AC katsayı tablosu).
[_0] tablo kimliği: 0
Huffman kod uzunluğu: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Kod sayısı:
Kod sayısı, o uzunluktaki kod sayısı anlamına gelir. Bölümün, kodların kendilerini değil, yalnızca kodların uzunluklarını kaydettiğini unutmayın. Kodları kendimiz bulmalıyız. Yani 1 uzunluk ve 1 uzunluk 2 kodumuz var. Toplamda 2 kod var, bu tabloda başka kod yok.
Her kodun kendisiyle ilişkilendirilmiş bir değeri vardır ve bunlar dosyanın yanında listelenir. Değerler tek bayt olduğundan 2 bayt okuyoruz.
- 1. kodun değeri.
- 2. kodun değeri.

Huffman Kodlarından Bir Ağaç İnşa Etmek

DHT bölümünde aldığımız tablodan bir ikili ağaç oluşturmamız gerekiyor. Ve zaten bu ağaç tarafından her kodu tanıyacağız. Değerler tabloda listelendikleri sıraya göre eklenir. Algoritma basittir: Nerede olursak olalım, her zaman soldaki dala bir değer eklemeye çalışırız. Ve eğer meşgulse, o zaman sağa. Ve orada yer yoksa, o zaman yukarıdaki seviyeye döneriz ve oradan deneriz. Kodun uzunluğuna eşit bir seviyede durmanız gerekir. Sol dallar 0, sağ - 1 değerine karşılık gelir.
Yorum:
Her seferinde en baştan başlamaya gerek yok. Katma değer - yukarıdaki seviyeye geri dönün. Doğru şube var mı? Evet ise, tekrar yukarı çıkın. Değilse, doğru bir dal oluşturun ve oraya gidin. Ardından, oradan sonraki değeri eklemek için aramaya başlayın.

Bu örnekteki tüm tablolar için ağaçlar:


UPD (teşekkürler anarsoul): İlk ağacın düğümleri (DC, id =0) 0x03 ve 0x02 değerlerine sahip olmalıdır.

Dairelerde - kodların değerleri, dairelerin altında - kodların kendileri (bunları yukarıdan her düğüme giderek aldığımızı açıklayacağım). Bu tür kodlarla (bunun ve diğer tabloların) şeklin içeriği kodlanmıştır.

İşaretleyici : SOS (Taramanın Başlangıcı)

Belirteçteki bayt "EVET! Son olarak, doğrudan kodlanmış görüntünün bölümünü ayrıştırmaya gittik! Ancak bölüm sembolik olarak SOS olarak adlandırılır.

  FF DA 00 0C 03 01 00 02 11
03 11 00 3F 00

Başlığın uzunluğu (bölümün tamamı değil): 12 bayt.
Tarama bileşenlerinin sayısı. Y, Cb, Cr için birer tane olmak üzere 3 tane var.

1. bileşen:
Görüntü bileşen numarası: 1 (Y)
DC katsayıları için Huffman tablo kimliği: 0
[_0] AC katsayıları için Huffman tablo kimliği: 0

2. bileşen:
Görüntü bileşen numarası: 2 (Cb)

[_1]

3. bileşen:
Görüntü bileşen numarası: 3 (Cr)
DC katsayıları için Huffman tablo kimliği: 1
[_1] AC katsayıları için Huffman tablo kimliği: 1

Bu bileşenler döngüsel olarak değişir.

Başlık kısmının bittiği yer burasıdır, buradan sona (işaretleyici) kodlanmış veriler.

0

DC katsayısını bulma.
1. Bit dizisini okuma (2 bayt ile karşılaşırsak, bu bir işaretleyici değil, sadece bir bayttır). Her bitten sonra, okunan bit'e bağlı olarak 0 veya 1 dalı boyunca Huffman ağacı (karşılık gelen tanımlayıcı ile) boyunca hareket ederiz. Son düğümdeysek dururuz.
10 1011101110011101100001111100100

2. Düğümün değerini alıyoruz. 0'a eşitse, katsayı 0'dır, tabloya yazın ve diğer katsayıları okumaya devam edin. Bizim durumumuzda - 02. Bu değer, katsayının bit cinsinden uzunluğudur. Yani, sonraki 2 biti okuduk, bu katsayı olacak.
10 10 11101110011101100001111100100

3. İkili gösterimde değerin ilk basamağı 1 ise, olduğu gibi bırakın: DC_coef = value. Aksi takdirde, şunu dönüştürün: DC_coef = değer-2 değer uzunluğu +1 . Katsayıyı zikzak - sol üst köşenin başında tabloya yazıyoruz.

AC katsayılarını bulma.
1. Madde 1'e benzer şekilde, DC katsayısını bulma. Sıralamayı okumaya devam ediyoruz:
10 10 1110 1110011101100001111100100

2. Düğümün değerini alıyoruz. 0'a eşitse, matrisin kalan değerlerinin sıfırlarla doldurulması gerektiği anlamına gelir. Ardından bir sonraki matris kodlanır. Bu noktaya kadar okuyup bu konuda kişisel olarak bana yazan ilk birkaç kişi karmada bir artı alacak. Bizim durumumuzda, düğümün değeri 0x31'dir.
İlk kemirme: 0x3 - matrise kaç tane sıfır eklememiz gerekiyor. Bunlar 3 sıfır katsayı.
İkinci kemirme: 0x1 - bit cinsinden katsayı uzunluğu. Sonraki kısmı okuyun.
10 10 1110 1 110011101100001111100100

3. DC katsayısını bulmanın 3. noktasına benzer.

Zaten anladığınız gibi, kodun sıfır değerine rastlayana veya matris dolana kadar AC katsayılarını okumanız gerekir.
Bizim durumumuzda, şunları alacağız:
10 10 1110 1 1100 11 101 10 0 0 0 1 11110 0 100
ve matris:

Değerlerin aynı zikzak deseninde doldurulduğunu fark ettiniz mi?
Bu sırayı kullanmanın nedeni basittir - v ve u değerleri ne kadar büyük olursa, ayrık kosinüs dönüşümündeki S vu katsayısı o kadar az önemlidir. Bu nedenle, yüksek sıkıştırma oranlarında, önemsiz katsayılar sıfıra ayarlanır, böylece dosya boyutu küçülür.

[-4 1 1 1 0 0 0 0] [ 5 -1 1 0 0 0 0 0]
[ 0 0 1 0 0 0 0 0] [-1 -2 -1 0 0 0 0 0]
[ 0 -1 0 0 0 0 0 0] [ 0 -1 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0] [-1 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0] [ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0] [ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0] [ 0 0 0 0 0 0 0 0]

[-4 2 2 1 0 0 0 0]
[-1 0 -1 0 0 0 0 0]
[-1 -1 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]

Oh, kodlanmış DC katsayılarının DC katsayılarının kendileri değil, önceki tablonun (aynı kanalın) katsayıları arasındaki farkları olduğunu söylemeyi unuttum! Matrisleri düzeltmeniz gerekiyor:
2. için DC: 2 + (-4) = -2
3. için DC: -2 + 5 = 3
4. için DC: 3 + (-4) = -1

[-2 1 1 1 0 0 0 0] [ 3 -1 1 0 0 0 0 0] [-1 2 2 1 0 0 0 0]
………

Şimdi sipariş ver. Bu kural dosyanın sonuna kadar geçerlidir.

… ve Cb ve Cr için matrise göre:

[-1 0 0 0 0 0 0 0]
[ 1 1 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]

Her biri yalnızca bir matris olduğundan, DC katsayılarına dokunulmadan bırakılabilir.

Bilgi işlem

niceleme

Matrisin niceleme aşamasından geçtiğini hatırlıyor musunuz? Matrisin elemanları, niceleme matrisinin elemanları ile terim terim çarpılmalıdır. Doğru olanı seçmek için kalır. İlk olarak, ilk bileşeni taradık, görüntü bileşeni = 1. Bu kimliğe sahip görüntü bileşeni, 0'lık bir niceleme matrisi kullanır (ikiden ilkine sahibiz). Yani çarpma işleminden sonra:

[ 0 120 280 0 0 0 0 0]
[ 0 -130 -160 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]

Benzer şekilde, 3 tane daha Y-kanalı matrisi elde ederiz ...

[-320 110 100 160 0 0 0 0] [ 480 -110 100 0 0 0 0 0]
[ 0 0 140 0 0 0 0 0] [-120 -240 -140 0 0 0 0 0]
[ 0 -130 0 0 0 0 0 0] [ 0 -130 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0] [-140 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0] [ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0] [ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0] [ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0] [ 0 0 0 0 0 0 0 0]

[-160 220 200 160 0 0 0 0]
[-120 0 -140 0 0 0 0 0]
[-140 -130 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]

… ve Cb ve Cr için matrise göre.

[-170 0 0 0 0 0 0 0] [ 0 0 0 0 0 0 0 0]
[ 180 210 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0] [ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0] [ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0] [ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0] [ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0] [ 0 0 0 0 0 0 0 0]

Ters Ayrık Kosinüs Dönüşümü

Formül zor olmamalı*. S vu, sonuçtaki katsayı matrisimizdir. u - sütun, v - satır. s yx - doğrudan kanal değerleri.

* Genel olarak konuşursak, bu tamamen doğru değildir. 16x16'lık bir çizimi deşifre edip ekranda gösterebildiğimde 600x600'lük bir resim çektim (bu arada bu en sevdiğim albüm Mind.In.A.Box - Lost Alone'un kapağıydı). Hemen çalışmadı - çeşitli hatalar ortaya çıktı. Yakında doğru yüklenen resme hayran olabilirim. Tek hayal kırıklığı indirme hızıydı. 7 saniye sürdüğünü hala hatırlıyorum. Ancak bu şaşırtıcı değil, yukarıdaki formülü düşüncesizce kullanırsanız, o zaman bir pikselin bir kanalını hesaplamak için 128 kosinüs, 768 çarpma ve orada bazı eklemeler bulmanız gerekir. Bir düşünün - bir pikselin yalnızca bir kanalı için neredeyse bin zor işlem! Neyse ki, burada optimizasyon için yer var (birçok denemeden sonra, yükleme süresini 15ms'lik zamanlayıcı doğruluk sınırına indirdim ve bundan sonra resmi 25 kat daha büyük bir fotoğrafla değiştirdim. Belki bunu ayrı bir makalede yazarım. ).

Y kanalının sadece ilk matrisini hesaplamanın sonucunu yazacağım (değerler yuvarlanmıştır):


[ 87 72 50 36 37 55 79 95]
[-10 5 31 56 71 73 68 62]
[-87 -50 6 56 79 72 48 29]

Ve diğer 2:
Cb Cr
[ 60 52 38 20 0 -18 -32 -40] [ 19 27 41 60 80 99 113 120]
[ 48 41 29 13 -3 -19 -31 -37] [ 0 6 18 34 51 66 78 85]
[ 25 20 12 2 -9 -19 -27 -32] [-27 -22 -14 -4 7 17 25 30]
[ -4 -6 -9 -13 -17 -20 -23 -25] [-43 -41 -38 -34 -30 -27 -24 -22]
[ -37 -35 -33 -29 -25 -21 -18 -17] [-35 -36 -39 -43 -47 -51 -53 -55]
[ -67 -63 -55 -44 -33 -22 -14 -10] [ -5 -9 -17 -28 -39 -50 -58 -62]
[ -90 -84 -71 -56 -39 -23 -11 -4] [ 32 26 14 -1 -18 -34 -46 -53]
[-102 -95 -81 -62 -42 -23 -9 -1] [ 58 50 36 18 -2 -20 -34 -42]

1. Ah, hadi yemek yiyelim!
2. Evet hiç girmiyorum ne diyorsunuz.
3. YCbCr renk değerleri elde edildikten sonra geriye şu şekilde RGB'ye dönüştürmek kalır: YCbCrToRGB(Y ij , Cb ij , Cr ij) , Y ij , Cb ij , Cr ij - alınan matrislerimiz.
4. Kanalları incelttiğimiz için 4 Y matrisi ve her biri bir Cb ve Cr ve 4 Y pikselin her biri bir Cb ve Cr'ye karşılık gelir. Bu nedenle, şöyle hesaplayın: YCbCrToRGB(Y ij , Cb , Cr )

1 ve 4'ü seçerseniz, sizin için mutluyum. Ya doğru yaptın ya da yakında yemeğin tadını çıkaracaksın.

YCbCr'den RGB'ye dönüştürücü

R = Y + 1.402 * Kr
G = Y - 0.34414 * Cb - 0.71414 * Cr
B = Y + 1.772 * Cb
Her birine 128 eklemeyi unutmayın. Değerler aralığın dışına çıkıyorsa sınır değerleri atayın. Formül basittir, ancak aynı zamanda işlemci süresinin bir kısmını da tüketir.

Örneğimizin sol üst 8x8 karesi için R, G, B kanalları için sonuç tabloları:
255 248 194 148 169 215 255 255
255 238 172 115 130 178 255 255
255 208 127 59 64 112 208 255
255 223 143 74 77 120 211 255
237 192 133 83 85 118 184 222
177 161 146 132 145 162 201 217
56 73 101 126 144 147 147 141
0 17 76 126 153 146 127 108

231 185 117 72 67 113 171 217
229 175 95 39 28 76 139 189
254 192 100 31 15 63 131 185
255 207 115 46 28 71 134 185
255 241 175 125 112 145 193 230
226 210 187 173 172 189 209 225
149 166 191 216 229 232 225 220
72 110 166 216 238 231 206 186

255 255 249 203 178 224 255 255
255 255 226 170 140 187 224 255
255 255 192 123 91 138 184 238
255 255 208 139 103 146 188 239
255 255 202 152 128 161 194 232
255 244 215 200 188 205 210 227
108 125 148 172 182 184 172 167
31 69 122 172 191 183 153 134

Son

Genel olarak, bir JPEG uzmanı değilim, bu yüzden tüm soruları yanıtlayamıyorum. Tam kod çözücümü yazdığımda, çoğu zaman anlaşılmaz çeşitli sorunlarla uğraşmak zorunda kaldım. Ve görüntü yanlış görüntülendiğinde, nerede hata yaptığımı bilmiyordum. Belki bitleri yanlış yorumladı veya DCT'yi yanlış kullandı. Adım adım bir örneği gerçekten kaçırdım, bu yüzden bu makalenin kod çözücü yazarken yardımcı olacağını umuyorum. Sanırım temel yöntemin açıklamasını kapsıyor, ancak yine de bununla başa çıkamazsınız. İşte bana yardımcı olan bazı bağlantılar:

Eski güzel JPEG, birçok inkar edilemez avantajına rağmen, hala önemli sınırlamalara sahiptir. Bunları kaldırmak için, gelişimi uzun süredir devam eden yeni bir görüntü sıkıştırma yöntemi adı verildi. JPEG2000 artık resmi olarak tanınan bir format haline geldiğine göre, bu, çeşitli yazılım üreticileri tarafından aktif desteğinin başlangıcı olmalıdır.

Bir bilgisayarda grafiklerle çalışan pek çok kişi şu soruyla ilgileniyor: PC belleğinde çok etkileyici bir yer kaplayan bir görüntü, diskte çok daha küçük bir boyuta nasıl sıkıştırılabilir? Yayıncılık faaliyetimin başlangıcında, "sıkıştırma" kelimesinin benim için çok gizemli ve şaşırtıcı olduğunu hatırlıyorum... Gerçekten de, görüntü sıkıştırma nasıl çalışır - sonuçta, şimdi Web'i, dijital fotoğrafçılığı veya onsuz renkli baskı?

Yani sıkıştırma. Kalite kaybına neden olabilir veya olmayabilir. Son durum, RLE (Çalışma Uzunluğu Kodlaması, çalışma uzunluklarının kodlanması, sonuç olarak hangi tür çiftlerinin ( atlamak, değer, nerede atlamak ardışık sıfırların sayısıdır ve değer- onları takip eden değer) ve LZW (Lempel-Ziff-Welch yöntemiyle sıkıştırma), PSD, GIF ve TIFF formatlarında uygulanır. RAR ve ZIP gibi arşivleyiciler tarafından yaygın olarak kullanılırlar. Ortalama kayıpsız sıkıştırma oranı 2-3 katıdır.

Görüntüyü daha güçlü bir şekilde sıkıştırmanız gerekiyorsa, kalite kaybı olmadan yapamazsınız. İlkeler nelerdir? İlk olarak, herhangi bir görüntü, kaldırılması resmin kalitesinde gözle görülür bir değişikliğe yol açmayacak belirli bir fazlalık içerir. İkincisi, insan gözü parlaklıktaki değişikliklere renkten daha duyarlıdır. Bu nedenle, görüntünün farklı kanalları için farklı sıkıştırma oranları kullanılır - bilgi kaybolur, ancak bu görsel olarak fark edilmez. Ek olarak, gözün küçük görüntü öğelerine duyarlılığı düşüktür, bu da kaliteden ödün vermeden bunların çıkarılmasını mümkün kılar. Bu şekilde görüntüyü (kalite bozulması zaten fark edilebilir olsa bile) kabul edilebilir bir eşiğe kadar sıkıştırabilirsiniz. Her özel durum için kalite bozulma derecesi belirlenir. Yazdırma için, yalnızca minimum bozulmalar kabul edilebilir ve İnternet'te yayınlamak için (amaca bağlı olarak) - çok daha fazlası.

Kayıplı sıkıştırma yöntemleri arasında en popüler olanı, otuz kat sıkıştırmada bile yeterli görüntü kalitesini koruyan JPEG'dir. Bu arada, çoğu modern veri sıkıştırma yönteminde (örneğin, mp3 olarak bilinen Layer-4 ve MPEG), JPEG'e benzer mekanizmalar uygulanmaktadır. Bu formata daha yakından bir göz atalım, özellikle de çok uzun zaman önce olmayan en son uygulaması olan JPEG2000, nihayet on yıl boyunca JPEG / MPEG'e yapılan tüm eklemeleri içeren onaylandığından beri.

JPEG

Sıkıştırma algoritmasının adı, ITU (Uluslararası Telekomünikasyon Birliği) ve ISO (Uluslararası Standardizasyon Örgütü) uzmanları tarafından oluşturulan bir girişim grubu olan Joint Photographic Expert Group'un kısaltmasıdır. Adında Joint önekinin bulunmasının nedeni budur. 1992'de JPEG, grafikler için uluslararası standart olarak ilan edildi.

JPEG sıkıştırması her zaman kaliteyi kaybeder. Bu durumda, her zaman bir seçenek vardır: hacim pahasına kaliteyi tercih etmek (dosya boyutu yaklaşık üç kez sıkıştırılacaktır) veya tam tersi, hala tanınabilir kalacağı minimum görüntü boyutunu elde etmek için ( sıkıştırma oranı 100'e ulaşabilir). Ortaya çıkan görüntü ile orijinal arasındaki kalite farkının hala fark edilmediği sıkıştırma, dosya boyutunda 10-20 kat küçülme sağlar.

Uygulama alanı

JPEG, fotoğraf kalitesinde tam renkli ve tek renkli görüntüleri en iyi şekilde sıkıştırır. Bir görüntüyü indeks paleti ile kaydetmek istiyorsanız, önce tam renge dönüştürülür. JPEG yöntemini kullanarak sıkıştırırken, her şeyin görüntülerin doğasına bağlı olduğunu unutmamalısınız: renk değişikliklerinin önemsiz olduğu ve keskin renk geçişlerinin olmadığı yerler çok daha küçük bir hacim kaplayacaktır. JPEG, fotoğraf görüntülerinin depolanması gereken her yerde kullanılır: dijital kameralarda, baskıda (EPS DCS 2.0), İnternet onsuz düşünülemez.

Birkaç çeşit JPEG sıkıştırması vardır, ancak standart pakette Adobe Photoshop raster görüntüleri ile çalışmak için kullanılan bunlardan yalnızca ikisini ele alacağız - temel ve ilerici. Diğer iki yöntem - aritmetik ve kayıpsız - birçok nedenden dolayı yaygın olarak kullanılmayan egzotiktir.

Sıkıştırma Nasıl Olur?

1. İlk aşama şunlardan oluşur: renk modeli dönüştürme görüntüyü (genellikle RGB) parlaklık ve renk bileşenlerinin ayrıldığı (örneğin, YCbCr veya YUV) bir modele dönüştürür, bu da her kanal için (göz algısını dikkate alarak) sıkıştırma seviyeleri seçimine en uygun şekilde yaklaşmanıza olanak tanır. Dönüşüm şu şekilde olur:

Y = 0.299xR+0.587*G+0.114xB Cb = (B-Y)/0.866/2+128 Cr = (R-Y)/0.701/2+128

2. Bir sonraki aşamada, sözde. ön filtreleme Cb ve Cr kanallarının her birinde ayrı ayrı komşu piksellerin yatay ve dikey yönlerde çiftler halinde gruplandırıldığı ve parlaklık kanalı Y'nin değişmeden bırakıldığı . Bundan sonra, dört piksellik grubun tamamı, ilgili Cb ve Cr bileşenlerinin ortalama değerini alır. Kısa olması için, böyle bir şema 4:1:1 olarak belirtilebilir (aynı temsil biçimi DRAW - jpeg dışa aktarma penceresi için de benimsenmiştir). Her pikselin 3 bayt (üç kanalın her biri için 256 seviye) olarak kodlandığı gerçeği göz önüne alındığında, sonuç olarak, veri miktarı otomatik olarak 2 kat azaltılır (4 pikseli aktarmak için 12 bayt yerine, sadece 4+1+1 = 6 bayt aktarmak için yeterli) . Matematik açısından bakıldığında, böyle bir dönüşüm önemli bir bilgi kaybına yol açar, ancak sıradan fotoğraf görüntülerinde önemli bir fazlalık olduğu için insan gözü kaybı algılamaz.

3. Birincil “temizlik” aşamasını geçen alınan bilgiler, yine her kanalda ayrı ayrı bloklar halinde gruplandırılır, ancak zaten 8x8 boyutundadır, bundan sonra onlara ana sıkıştırma uygulanır - sözde. ayrık kosinüs dönüşümü, kısaca - DCT (ayrık kosinüs dönüşümü). Sonuç olarak, bilgi dağıtım hakkında piksel parlaklığı, aşağıdakilere dayalı bir dağılımla tanımlandığı başka bir forma dönüştürülür. oluşma sıklığı bir veya başka piksel parlaklığı. DCT'nin diğer dönüşümlere (örneğin, Fourier dönüşümü) göre bir takım avantajları vardır ve daha iyi bilgi kurtarma sağlar.

Görüntüyü oluşturan her blok için 64 değerlik bir dizi (8x8 piksel) yerine 64 frekanslık bir dizi elde ediyoruz. DCT'nin çalışmasını bir örnek üzerinde düşünün. Diyelim ki görüntümüzün bir bloğundaki piksellerin parlaklığı Şekil 1'de gösterilen forma sahip. 1 solda, ardından dönüşüm sonucu sağda gösterildiği gibi olacaktır.

1

Önemli doğruluğa rağmen, bu aşamada bir miktar bilgi kaybı meydana gelir - bu nedenle JPEG her zaman kalite kaybına yol açar. Dönüşümün temel amacı, daha sonra önemsiz bilgileri ortadan kaldırırken kullanışlı olacak olan büyük (şekilde sol üstte) ve küçük (sağ altta) nesnelerin dağılımının genel resmini bulmaktır.

4. Bir sonraki adım, gözle neredeyse hiç fark edilmeyen bilgileri bloktan çıkarmak veya nicemleme(kuantizasyon). Tüm bileşenler, orijinal görüntünün kalitatif restorasyonu için her birinin önemini belirleyen çeşitli katsayılara bölünür ve sonuç yuvarlanmış bir tamsayı değerine Görüntünün son hacmini azaltarak en büyük kalite kaybını sağlayan bu prosedürdür. Yüksek frekanslı bileşenler kabaca nicelenir ve düşük frekanslı bileşenler en belirgin olduklarından daha kesin olarak nicelenir. Kalitedeki düşüşü biraz yumuşatmak için parlaklık kanalında renk kanallarından daha küçük bölme faktörleri kullanılır. Ancak daha sık (bu, hesaplamaları hızlandırmak için yapılır), özel olarak seçilen değerler yerine, yalnızca bir tane alınır - kullanıcının sıkıştırma derecesini seçerken girdiği.

Örneğin, Kalite parametresinin (veya daha doğrusu türevinin) aynı olduğu Web için kaydet işlemini kullanarak bir görüntüyü kaydederken Photoshop penceresinin nasıl göründüğü aşağıda açıklanmıştır. yuvarlama faktörü(İncir. 2).

Kuantizasyon sonucunda, orijinal görüntünün belirli bir doğrulukla geri yüklendiği bir dizi bileşen elde edilir (Şekil 3).

4

Şek. Şekil 4, sırasıyla bir, dört ve on beş bileşenli siyah beyaz bir kareyi geri yüklemenin sonucunu gösterir.

5. Görüntü sıkıştırma üzerinde ana çalışmayı gerçekleştirdikten sonra, diğer dönüşümler ikincil görevlere indirgenir: kalan bileşenler sırayla gidiyoröyle bir şekilde ki, önce büyük detaylardan sorumlu olanlar, sonra da daha küçük olanlar için. Şekle bakarsanız, kodlayıcının hareketi zikzak bir çizgi gibi görünüyor. Aşama ZigZag olarak adlandırılır (Şekil 5).

5

Daha sonra elde edilen dizi sıkıştırılır: önce normal RLE, ardından Huffman yöntemi.

6. Ve sonunda temiz teknik aşama- veriler, görüntünün geri yüklenebilmesi için tüm sıkıştırma parametrelerini gösteren bir başlık ile sağlanan bir kabuk içine alınır. Ancak bazen bu bilgiler başlıklarda yer almaz, bu da sıkıştırmada ek bir kazanç sağlar, ancak bu durumda dosyayı okuyacak uygulamanın bunları bildiğinden emin olmanız gerekir.

Burada, genel olarak ve tüm dönüşümler. Şimdi örneğimizde ne kadar sıkıştırma yapıldığını hesaplayalım. Orijinal 8x8 görüntüyü geri yükleyecek 7 değerimiz var. Böylece, her iki renk kanalında DCT-dönüştürme uygulamasından kaynaklanan sıkıştırma 8x8/7 9 kez olmuştur. Parlaklık kanalına 8x8/11 6 verecek olan yedi değil 11 katsayı atayalım. Her üç kanal için de (9+9+6)/3=8 kez elde ederiz. İkinci aşamada meydana gelen görüntünün “kırılması” sırasında kalitedeki düşüş, nihai sonucu verecek olan ek bir çift artış (şema 4-1-1, parlaklık bileşenini kodlamanın özelliklerini dikkate alarak) verir - 16 kez. Bu, bazı yönleri dikkate almayan, ancak gerçek resmi yansıtan kaba bir tahmindir. Dosya boyutunda otuz kat azalma elde etmek için yalnızca 3-4 bileşen bırakmanız gerekir.

Görüntü yeniden oluşturma işlemi ters sırada ilerler: ilk olarak, bileşenler niceleme tablosundaki değerlerle çarpılır ve ters kosinüs dönüşümü için yaklaşık katsayılar elde edilir. Sıkıştırma sırasında ne kadar iyi kalite seçilirse, orijinal katsayılara yakınlık derecesi o kadar yüksek olur, bu da görüntünün daha doğru şekilde geri yükleneceği anlamına gelir. Geriye sadece bir eylem eklemek kalıyor: Bitmeden önce, aralarındaki keskin farkları ortadan kaldırmak için komşu bloklardan sınır piksellerinde bazı ayarlamalar (gürültü) yapın.

JPEG'in dezavantajları

1. Blok boyutu sınırlaması (sadece 8x8) nedeniyle yüksek sıkıştırma oranları elde etmenin imkansızlığı.
2. Yüksek sıkıştırma oranlarında bloklu yapı.
3. Bir görüntüdeki keskin köşeleri yuvarlayın ve ince öğeleri bulanıklaştırın.
4. Yalnızca RGB görüntüleri desteklenir (DCS aracılığıyla EPS formatındaki CMYK görüntüleri için yalnızca JPEG kullanabilirsiniz).
5. Resim tamamen yüklenene kadar görüntülenemez.

JPEG'in standart olarak onaylanmasından bu yana on yıl geçti. Bu süre zarfında, araştırma grupları orijinal versiyona bir dizi önemli eklemeler önerdiler ve bu da geçen yılın sonunda yeni bir standardın ortaya çıkmasıyla sonuçlandı.

JPEG2000

1997'den beri, JPEG tarafından getirilen tüm kısıtlamaları ortadan kaldıracak ve içerikten bağımsız olarak (siyah beyaz, gri tonlamalı, tam renkli ve çok bileşenli) her tür görüntüyle etkin bir şekilde çalışabilecek evrensel bir kodlama sistemi oluşturmaya yönelik çalışmalar başlamıştır. fotoğraflar, oldukça küçük metinler ve hatta çizimler olabilir). Uluslararası standardizasyon kuruluşlarının yanı sıra Agfa, Canon, Fujifilm, Hewlett-Packard, Kodak, LuraTech, Motorola, Ricoh, Sony ve diğerleri gibi endüstri devleri de geliştirmesinde yer aldı.

Yeni algoritmanın evrensel olduğu iddia edildiğinden, özellikle multimedya uygulamalarında, örneğin İnternet üzerinden gerçek yayınlarda kritik olan çeşitli veri iletimi yöntemlerini (gerçek zamanlı ve dar bir bant genişliğiyle) kullanmakla görevlendirildi.

JPEG2000 formatı için temel gereksinimler:

1. JPEG'e kıyasla daha yüksek bir sıkıştırma derecesi elde etmek.
2. Görüntüleri metinle sıkıştırmak için kullanılmasına izin verecek tek renkli görüntüler için destek.
3. Kayıpsız sıkıştırma imkanı.
4. Ayrıntılı olarak kademeli iyileştirme ile çıktı görüntüleri (aşamalı GIF'de olduğu gibi).
5. Görüntüde kalitenin görüntünün geri kalanından daha yüksek ayarlanabileceği öncelikli alanların kullanımı.
6. Gerçek zamanlı kod çözme (gecikme yok).

sıkıştırma prensibi

JPEG2000'deki ana sıkıştırma mekanizması olarak, JPEG'den farklı olarak, tüm görüntüye uygulanan bir filtre sistemi olan dalga (dalgacık) dönüşümü kullanılır. Sıkıştırmanın ayrıntılarına girmeden sadece ana noktaları not ediyoruz.

6

İlk olarak, tıpkı JPEG'de olduğu gibi, görüntü YCrCb sistemine dönüştürülür, ardından gereksiz bilgilerin birincil olarak kaldırılması (zaten bilinen bitişik piksellerin 2x2 bloklara kombinasyonu ile). Ardından, görüntünün tamamı aynı boyuttaki parçalara bölünür (karo), her birinin üzerinde diğerlerinden bağımsız olarak daha fazla dönüşüm gerçekleşir (bu, bellek ve bilgi işlem kaynakları için gereksinimleri azaltır). Ayrıca her kanal, alçak geçiren ve yüksek geçiren filtrelerle sıralar ve sıralar halinde ayrı ayrı filtrelenir, bunun sonucunda ilk geçişten sonra her bölümde dört küçük görüntü (alt bant) oluşur. Hepsi orijinal görüntü hakkında bilgi taşır, ancak bilgi içerikleri çok farklıdır (Şekil 6).

Örneğin, satırlar ve satırlar (sol üst) tarafından alçak geçiren filtrelemeden sonra elde edilen görüntü en büyük miktarda bilgiyi taşırken, yüksek geçiren filtrelemeden sonra elde edilen görüntü minimuma sahiptir. Satırların düşük geçişli filtrelemesinden ve sütunlar için yüksek frekanslı filtrelemeden (ve tersi) sonra elde edilen görüntülerin bilgi içeriği ortalamadır. En bilgilendirici görüntü yeniden filtrelenir ve elde edilen bileşenler, jpeg sıkıştırmasında olduğu gibi nicelenir. Bu birkaç kez olur: kayıpsız sıkıştırma için, döngü genellikle kayıplarla 3 kez tekrarlanır - 10 yineleme boyut, kalite ve dekompresyon hızı arasında makul bir uzlaşma olarak kabul edilir. Sonuç, küçük bir resim ve küçük ayrıntılara sahip bir dizi resim, art arda ve belirli bir doğrulukla normal boyuta geri yüklenir. Açıkçası, daha fazla döngü ayarlanabildiğinden, en büyük sıkıştırma derecesi büyük görüntülerde elde edilir.

Pratik uygulama

JPEG2000 sıkıştırmasının temelleri atıldığından beri, bir dizi şirket, uygulanması için oldukça verimli algoritmalar geliştirdi.

Büyük yazılım geliştiricileri arasında Corel'in not edilebilir (bu arada, dalga dönüşümlerine dayalı wi formatı için destek ve onur ve övgü olduğu paketlerine ilk destek verenlerden biriydi) - tüm görüntüler CD'lerde sağlandı CorelDRAW paketi ile dokuzuncu sürüme kadar bu şekilde sıkıştırılmıştır.

Daha sonra, Adobe de ona yetişti. JPEG2000'in arkasındaki fikirlerden bazıları, Photoshop 6 geliştiricileri tarafından bir görüntüyü JPEG olarak kaydederken (düzenli, kosinüs dönüşümüne dayalı) gelişmiş seçenekler biçiminde uygulanmıştır. Bunların arasında aşamalı JPEG (Web için Kaydet penceresindeki Aşamalı seçeneği) bulunur. Bu algoritma öncelikle gerçek zamanlı sistemler için tasarlanmıştır ve aşamalı GIF ile tamamen aynı şekilde çalışır. İlk olarak, yalnızca birkaç büyük bloktan oluşan görüntünün kaba bir kopyası belirir ve zamanla, verilerin geri kalanı yüklendiğinde, yapı giderek daha net bir şekilde görüntülenmeye başlar, sonunda nihai görüntü olana kadar. tamamen restore edildi. GIF'den farklı olarak, bu algoritma, iletilen her sürüm için tüm dönüştürme döngüsünü tamamlaması gerekeceğinden görüntüleyici üzerinde büyük bir yük oluşturur.

Diğer eklemelerin yanı sıra, değişen derecelerde sıkıştırma, çözünürlük ve hatta renk modellerine sahip birkaç JPEG sıkıştırılmış görüntünün dosyasına dahil edildiğini not ediyoruz. Buna göre, Photoshop 6'da görüntüdeki tek tek alanları seçmek ve bunlara farklı sıkıştırma ayarları uygulamak mümkün hale geldi ( İlgi Alanı, ilk kez böyle bir mekanizma 1995'te önerildi), niceleme tablosunda daha düşük değerler kullanılarak. Bunu yapmak için gerekli alan ayarlanır (örneğin, görüntüde yeni bir kanal şeklinde) ve Kalite öğesinin yanında maske simgesine basılır. Görünen pencerede, kaydırıcıları hareket ettirerek görüntü ile deney yapabilirsiniz - bitmiş sonuç ekranda görüntülenerek kalite ve boyut arasında gerekli uzlaşmayı hızlı bir şekilde bulmanızı sağlar.

Özel dönüştürücüler ve görüntüleyiciler

Standart, sıkıştırma / açma yöntemlerinin belirli uygulamalarını belirtmediğinden, bu, üçüncü taraf sıkıştırma algoritması geliştiricilerine yer bırakır. Aslında, basitleştirilmiş bir dalga biçimi algoritması kullanabilir ve böylece sıkıştırma işlemini hızlandırabilir veya tam tersine daha karmaşık bir algoritma kullanabilir ve buna bağlı olarak büyük sistem kaynakları gerektirebilirsiniz.

Diğer şirketlerden özel çözümler, ticari gelişmeler olarak mevcuttur. Bazıları ayrı programlar (Aware tarafından geliştirilen JPEG 2000), diğerleri en yaygın tarama düzenleyicileri için eklenti modülleri olarak uygulanır (Pegasus Imaging tarafından geliştirilen ImagePress JPEG2000 ve LEAD Technologies'den LEAD JPEG2000 modülü). Arka planlarına karşı, uzun süredir bu konuyla ilgilenen LuraTech şirketi öne çıkıyor. LuraWave teknolojisini bağımsız ürün LuraWave SmartCompress'te teşvik eder (3. sürüm şimdi mevcuttur) ve Photoshop, Paintshop, Photopaint için modüller sunar. Ayırt edici bir özellik, birkaç megabayt boyutundaki resimlerde bile daha yüksek bir çalışma hızıdır (neredeyse anında dönüştürme). Buna göre, bu modülün fiyatı en yüksek - 79 dolar.

JPEG2000 görüntülerini tarayıcılarda görüntülemek için özel bir görüntüleme modülü yüklemeniz gerekir (tüm geliştiriciler bunu ücretsiz olarak sunar). Herhangi bir eklenti gibi bir html belgesine bir resim eklemek, EMBED yapısını (ek parametrelerle) kullanmaya gelir. Örneğin, aşamalı görüntü aktarım yönteminin kullanılacağı anlamına gelir. Yani, örneğimizde (139 KB dosya), önce kaba bir görüntünün oluşturulacağı yalnızca 250 bayt aktarılır, ardından 500 bayt yüklendikten sonra görüntü güncellenir (bu, LIMIT değeri olana kadar devam eder). ulaşmış).

Daha iyi bir görüntü elde etmek istiyorsanız, sağ tuşta açılan menüden İyileştir öğesini seçmeniz gerekir (Şekil 9). Dört özgeçmiş için, görüntünün tamamı tamamen indirilecektir.

9

sonuçlar

Bu nedenle, JPEG2000, yalnızca yüksek sıkıştırma oranlarında nesnel olarak JPEG'den daha iyi sonuçlar verir. 10-20 kat sıkıştırma ile çok fazla fark yoktur. Yaygın formatın yerini alabilecek mi yoksa basitçe rekabet edebilecek mi? Yakın gelecekte - pek çok durumda, JPEG tarafından sağlanan kalite / boyut oranı oldukça kabul edilebilir. Ve JPEG2000'in görsel olarak aynı kalitede sağladığı %10-20'lik ek sıkıştırmanın popülaritesinde bir artışa yol açması pek olası değildir.

Öte yandan, ışığa duyarlı matrislerin boyutu her yıl istikrarlı bir şekilde arttığından ve görüntüleri belleğe yerleştirmek giderek daha zor hale geldiğinden, dijital kamera şirketleri yeni formata yakın ilgi gösteriyor. Ve sonra yeni format daha yaygın hale gelecek ve kim bilir, belki bir süre sonra JPEG2000, JPEG'i yakalayacaktır. Her durumda, Analog Micro Devices yakın zamanda donanım düzeyinde yeni bir teknoloji kullanılarak sıkıştırma / açma işleminin uygulandığı özel bir çip yayınladı ve ABD Savunma Bakanlığı, casus uydulardan alınan fotoğrafları kaydetmek için aktif olarak yeni bir format kullanıyor.

gerçekler ve varsayımlar

1. Dosyayı açarken ve yeniden kaydederken JPEG kalitesini kaybediyor.

Doğru değil. Kalite yalnızca görüntünün kaydedildiği sıkıştırma oranından daha düşük bir sıkıştırma oranı seçildiğinde kaybolur.

2. Bir dosyayı düzenlerken JPEG kalitesini kaybeder.

Gerçek. Değiştirilmiş bir dosyayı kaydettiğinizde, tüm dönüştürmeler yeniden gerçekleştirilir - bu nedenle sık sık resim düzenleme yapmaktan kaçının. Bu yalnızca dosya kapatıldığında geçerlidir; dosya açık kalırsa endişelenmenize gerek yok.

3. Farklı programlarda aynı parametrelerle sıkıştırmanın sonucu aynı olacaktır.

Doğru değil. Farklı programlar, kullanıcı tarafından girilen değerleri farklı şekillerde yorumlar. Örneğin, bir programda, kaydedilen görüntünün kalitesi (örneğin Photoshop'ta olduğu gibi), diğerinde sıkıştırma derecesi (karşılıklı) belirtilir.

4. Maksimum kaliteye ayarlandığında, görüntü herhangi bir kalite kaybı olmadan kaydedilir.

Doğru değil. JPEG her zaman kayıplarla sıkıştırır. Ancak örneğin %100 yerine %90 kaliteyi ayarlamak, gözle algılanan kalite kaybından daha fazla dosya boyutunda bir azalmaya neden olur.

5. Herhangi bir JPEG dosyası, JPEG formatını anlayan herhangi bir düzenleyicide açılabilir.

Doğru değil. Aşamalı JPEG, bazı düzenleyicilerin anlamadığı bir JPEG çeşididir.

6. JPEG şeffaflığı desteklemez.

Gerçek. Bazen görüntünün bir kısmı saydam gibi görünebilir, ancak aslında rengi html sayfasındaki arka plan rengiyle eşleşecek şekilde seçilir.

7. JPEG, GIF'den daha iyi sıkıştırır.

Doğru değil. Farklı uygulama alanlarına sahiptirler. Genel olarak, JPEG'e dönüştürüldükten sonra tipik bir "gif" resmi daha büyük bir hacme sahip olacaktır.

JPEG2000 ve JPEG

7

1. 20-30x sıkıştırmada, JPEG2000 ve JPEG yaklaşık olarak aynı kaliteyi verir (bu arada Photoshop normal bir fotoğrafı bu sınırın ötesinde sıkıştıramaz).

2. Daha yüksek sıkıştırma ile, JPEG2000'in kalitesi, JPEG'den önemli ölçüde daha yüksektir; bu, 50 kata kadar fazla kayıp olmadan ve bazı kayıplarla (İnternet için resimlerden bahsediyoruz) - 100'e kadar ve hatta daha fazla sıkıştırmanıza izin verir. 200'e kadar.

3. Pürüzsüz bir renk değişiminin olduğu alanlarda yüksek sıkıştırma oranları ile görüntü, basit bir JPEG'in blok yapısı özelliğini kazanmaz. JPEG2000 ayrıca keskin kenarları lekeliyor ve yuvarlatıyor - fotoğraflara bakın (Şek. 7 ve 8).

Farklı sıkıştırma oranlarına sahip test dosyası sıkıştırmasının sonuçlarını gösterir (solda - Photoshop'ta JPG formatında kaydedilmiş, sağda - JPEG2000 formatında). Şek. 7 sıkıştırma seviyesi 20, 40, 70 ve 145 seçildi (bunlar JPEG2000'e kaydedilirken açıkça belirtilebilirler), JPG sıkıştırma oranı seçildi, böylece dosya boyutu JPEG2000 tarafından sıkıştırıldıktan sonra aynı olacaktı. Dedikleri gibi, sonuçlar geldi. Netlik için, daha keskin ayrıntılara sahip bir görüntü üzerinde (10, 20, 40 ve 80 sıkıştırma seviyeleriyle) ikinci bir deney yapıldı. Avantaj yine JPEG2000 tarafındadır (Şekil 8).

8

4. Aslında, farklı çözünürlükteki kopyalar tek bir JPEG2000 dosyasında saklandığından

Böylece internette resim galerisi yapanlar için küçük resim oluşturmaya gerek kalmıyor.

5. Özellikle ilgi çekici olan, bozulma olmadan sıkıştırmadır (kayıpsız mod). Böylece, Photoshop'tan LZW sıkıştırmalı test dosyası 827 KB ve sıkıştırılmış JPEG2000 - 473 KB aldı.

6. JPEG ile karşılaştırıldığında, daha gelişmiş adaşı, önemli ölçüde daha fazla sistem kaynağı tüketir. Ancak bilgisayarların son birkaç yılda önemli ölçüde artan gücü, görüntü sıkıştırma problemlerini yeni bir yöntemle başarılı bir şekilde çözmeyi mümkün kılıyor.

7. Tarayıcılarda JPEG2000 desteğinin olmaması. Bu tür görüntüleri görüntülemek için oldukça büyük bir eklenti (1.2 MB) indirmeniz gerekir.

8. Görüntüleri yeni biçimde kaydetmek için ücretsiz yazılım eksikliği.

Kamuya açık dergiler.

Aynı konuda:

• öğretici

Bunun JPEG algoritmasının pek de olağan bir açıklaması olmadığını başlıktan doğru anladınız (“Aptallar için JPEG Kod Çözme” makalesinde dosya formatını ayrıntılı olarak anlattım). Her şeyden önce, materyali sunmanın seçilen yolu, yalnızca JPEG hakkında değil, aynı zamanda Fourier dönüşümü ve Huffman kodlaması hakkında da hiçbir şey bilmediğimizi varsayar. Genel olarak, derslerden çok az şey hatırlıyoruz. Sadece bir fotoğraf çektiler ve nasıl sıkıştırılabileceğini düşünmeye başladılar. Bu nedenle, yalnızca özü erişilebilir bir şekilde ifade etmeye çalıştım, ancak okuyucunun algoritma hakkında yeterince derin ve en önemlisi sezgisel bir anlayış geliştireceği. Formüller ve matematiksel hesaplamalar - en azından, sadece neler olduğunu anlamak için önemli olanlar.

JPEG algoritmasını bilmek, görüntü sıkıştırmadan daha fazlası için çok yararlıdır. Dijital sinyal işleme, matematiksel analiz, lineer cebir, bilgi teorisi, özellikle Fourier dönüşümü, kayıpsız kodlama vb. teorileri kullanır. Bu nedenle, kazanılan bilgi her yerde faydalı olabilir.

Bir arzu varsa, makaleye paralel olarak aynı adımları kendi başınıza izlemenizi öneririm. Verilen mantığın farklı görüntüler için nasıl uygun olduğunu kontrol edin, algoritmada kendi değişikliklerinizi yapmaya çalışın. Çok ilginç. Araç olarak harika bir Python + NumPy + Matplotlib + PIL(Pillow) paketini önerebilirim. Neredeyse tüm çalışmalarım (grafikler ve animasyon dahil) onlarla yapıldı.

Dikkat trafik! Çok sayıda illüstrasyon, grafik ve animasyon (~ 10Mb). İronik olarak, JPEG ile ilgili makalede elliden bu formatta sadece 2 resim var.

Bilgi sıkıştırma algoritması ne olursa olsun, prensibi her zaman aynı olacaktır - kalıpları bulma ve tanımlama. Daha fazla desen, daha fazla fazlalık, daha az bilgi. Arşivciler ve kodlayıcılar genellikle belirli bir bilgi türü için "keskinleştirilir" ve bunları nerede bulacaklarını bilirler. Bazı durumlarda, desen, örneğin mavi bir gökyüzünün resmi gibi hemen görülebilir. Dijital temsilinin her satırı, düz bir çizgi ile oldukça doğru bir şekilde tanımlanabilir.

Rakun kedileri üzerinde eğitim vereceğiz. Yukarıdaki gri resim örnek olarak alınmıştır. Hem homojen alanları hem de zıt alanları iyi bir şekilde birleştirir. Ve griyi sıkıştırmayı öğrenirsek, renkle ilgili herhangi bir sorun olmayacaktır.

vektör gösterimi

İlk olarak, komşu iki pikselin ne kadar bağımlı olduğunu kontrol edelim. Büyük olasılıkla çok benzer olacaklarını varsaymak mantıklıdır. Bunu görüntünün tüm çiftleri için kontrol edelim. Onları koordinat düzleminde noktalarla işaretleriz, böylece X ekseni boyunca noktanın değeri, Y ekseni boyunca ilk pikselin değeri - ikincisi. 256 x 256 resmimiz için 256*256/2 piksel elde ederiz:

Tahmin edilebileceği gibi, noktaların çoğu y=x doğrusu üzerinde veya yakınındadır (ve birçok kez birbirleriyle örtüştüğünden ve ayrıca yarı saydam olduklarından, şekilde görebileceğinizden çok daha fazlası vardır). Ve eğer öyleyse, onları 45 ° döndürerek çalışmak daha kolay olurdu. Bunu yapmak için onları farklı bir koordinat sisteminde ifade etmeniz gerekir.

Yeni sistemin temel vektörleri açıkça aşağıdaki gibidir: . Bir ortonormal sistem elde etmek için ikinin köküne bölmeye zorlanır (temel vektörlerin uzunlukları bire eşittir). Burada, yeni sistemdeki bir p = (x, y) noktasının bir nokta (a 0 , a 1) olarak temsil edileceği gösterilmiştir. Yeni katsayıları bildiğimiz için eskileri ters döndürme ile kolayca elde edebiliriz. Açıkçası, ilk (yeni) koordinat ortalamadır ve ikincisi x ve y arasındaki farktır (ancak 2'nin köküne bölünür). Değerlerden yalnızca birini bırakmanızın istendiğini düşünün: 0 veya 1 (diğerini sıfıra ayarlayın). 1 ve dolayısıyla değeri muhtemelen sıfır civarında olacağından 0 seçmek daha iyidir. Görüntüyü yalnızca 0'dan geri yüklersek şunlar olur:

4 kat büyütme:

Dürüst olmak gerekirse, bu tür bir sıkıştırma çok etkileyici değil. Resmi benzer şekilde piksellerin üçlülerine bölmek ve onları üç boyutlu uzayda sunmak daha iyidir.

Aynı tablo ama farklı açılardan. Kırmızı çizgiler kendilerini öneren eksenlerdir. Vektörlere karşılık gelirler: . Vektörlerin uzunluklarının bire eşit olması için bazı sabitlere bölmeniz gerektiğini hatırlatırım. Böylece, böyle bir temelde genişleyerek, a 0 , a 1 , a 2 ve 0, 1'den daha önemlidir ve 1, 2'den daha önemlidir 3 değeri elde ederiz. 2 atarsak, grafik e 2 vektörü yönünde "düzleşir". Bu zaten oldukça ince olan üç boyutlu levha düz hale gelecektir. Çok bir şey kaybetmeyecek ama değerlerimizin üçte birinden kurtulacağız. Üçüzler tarafından geri yüklenen görüntüleri karşılaştıralım: (a 0 , 0, 0), (a 1 , a 2 , 0) ve (a 0 , a 1 , a 2). Son versiyonda hiçbir şeyi atmadık, bu yüzden orijinalini alıyoruz.

4 kat büyütme:

İkinci çizim zaten iyi. Keskin alanlar hafifçe düzeltilir, ancak genel olarak resim çok iyi korunur. Şimdi aynı şekilde dörde bölelim ve tabanı dört boyutlu uzayda görsel olarak belirleyelim... Ah, peki, evet. Ancak temel vektörlerden birinin ne olacağını tahmin edebilirsiniz, bu: (1,1,1,1)/2. Bu nedenle, diğerlerini tanımlamak için dört boyutlu uzayın vektöre (1,1,1,1) dik uzaya izdüşümüne bakılabilir. Ama bu en iyi yol değil.
Amacımız (x 0 , x 1 , ..., x n-1)'i (a 0 , a 1 , ..., a n-1)'e nasıl dönüştüreceğimizi öğrenmektir, böylece a i'nin her değeri daha küçük olur ve öncekilerden daha az önemlidir. Bunu yapabilirsek, belki de dizinin son değerleri tamamen atılabilir. Yukarıdaki deneyler bunun mümkün olduğunu ima ediyor. Ancak matematiksel aparat olmadan yapılamaz.
Bu yüzden puanları yeni bir temele dönüştürmeniz gerekiyor. Ama önce uygun bir temel bulmanız gerekiyor. İlk eşleştirme deneyine dönelim. Genel hatlarıyla ele alalım. Temel vektörleri tanımladık:

Onlar aracılığıyla ifade edilen vektör p:

veya koordinatlarda:

0 ve 1 bulmak için yansıtmanız gerekir püzerinde e 0 ve e 1 sırasıyla. Ve bunun için skaler ürünü bulmanız gerekiyor.

benzer şekilde:

koordinatlarda:

Dönüşümü matris biçiminde gerçekleştirmek genellikle daha uygundur.

O zaman A = EX ve X = E T A. Bu güzel ve kullanışlı bir form. E matrisine dönüşüm matrisi denir ve ortogonaldir, onunla daha sonra buluşacağız.

Vektörlerden fonksiyonlara geçiş.

Küçük boyutlu vektörlerle çalışmak uygundur. Bununla birlikte, daha büyük bloklarda desenler bulmak istiyoruz, bu nedenle N boyutlu vektörler yerine bir görüntüyü temsil eden dizilerle çalışmak daha uygundur. Aşağıdaki akıl yürütme sürekli işlevler için de geçerli olduğundan, bu tür dizileri ayrık işlevler olarak adlandıracağım.
Örneğimize dönersek, sadece iki noktada tanımlanmış bir f(i) fonksiyonu hayal edin: f(0)=x ve f(1)=y. Benzer şekilde, e 0 (i) ve e 1 (i) temel fonksiyonlarını da bazlara göre tanımlarız. e 0 ve e bir . Alırız:

Bu çok önemli bir sonuçtur. Şimdi "bir vektörün ortonormal vektörler cinsinden genişlemesi" ifadesinde "vektör" kelimesini "fonksiyon" ile değiştirebilir ve "bir fonksiyonun ortonormal fonksiyonlar cinsinden genişlemesi" tamamen doğru ifadesini elde edebiliriz. Bu kadar kısa bir fonksiyona sahip olmamızın bir önemi yok, çünkü aynı akıl yürütme, N değerleriyle ayrık bir fonksiyon olarak temsil edilebilen N-boyutlu bir vektör için işe yarıyor. Ve fonksiyonlarla çalışmak, N-boyutlu vektörlerden daha açıktır. Vektör gibi bir işlevi temsil edebilir ve bunun tersi de yapabilirsiniz. Üstelik, sıradan bir sürekli fonksiyon, Öklid'de olmasa da Hilbert uzayında sonsuz boyutlu bir vektörle temsil edilebilir. Ama oraya gitmeyeceğiz, sadece ayrık fonksiyonlarla ilgileneceğiz.
Ve bir taban bulma sorunumuz, uygun bir ortonormal fonksiyonlar sistemi bulma sorununa dönüşüyor. Aşağıdaki akıl yürütmede, bir şekilde genişleteceğimiz bir dizi temel işlevi tanımladığımız varsayılmaktadır.
Diyelim ki, diğerlerinin toplamı olarak temsil etmek istediğimiz (örneğin değerlerle temsil edilen) bir fonksiyonumuz var. Bu işlemi vektör formunda gösterebilirsiniz. Bir işlevi genişletmek için, onu temel işlevlere tek tek "yansıtmanız" gerekir. Vektör anlamında, izdüşümün hesaplanması, orijinal vektörün mesafe olarak bir diğerine minimum yakınsamasını verir. Mesafenin Pisagor teoremi kullanılarak hesaplandığı akılda tutularak, fonksiyonlar biçimindeki benzer bir temsil, bir fonksiyonun diğerine en iyi ortalama karekök kök yaklaşımını verir. Böylece, her katsayı (k), fonksiyonun "yakınlığını" belirler. Daha resmi olarak, k*e(x), l*e(x) arasında f(x)'e en iyi rms yaklaşımıdır.
Aşağıdaki örnek, bir fonksiyona sadece iki nokta ile yaklaşma sürecini göstermektedir. Sağda vektör temsilidir.

Eşleştirme denememizle ilgili olarak, bu iki noktanın (apsis üzerinde 0 ve 1) bir çift bitişik piksel (x, y) olduğunu söyleyebiliriz.
Aynı ama animasyonlu:

3 puan alırsak, üç boyutlu vektörleri dikkate almamız gerekir, ancak yaklaşıklık daha doğru olacaktır. Ve N değerleri olan ayrık bir fonksiyon için N boyutlu vektörleri göz önünde bulundurmanız gerekir.
Elde edilen bir dizi katsayıya sahip olarak, alınan temel fonksiyonları karşılık gelen katsayılarla toplayarak orijinal fonksiyon kolayca elde edilebilir. Bu katsayıların analizi birçok yararlı bilgi sağlayabilir (tebana bağlı olarak). Bu düşüncelerin özel bir durumu, bir Fourier serisindeki genişleme ilkesidir. Ne de olsa, akıl yürütmemiz herhangi bir temele uygulanabilir ve bir Fourier serisine genişletilirken tamamen özel bir tane alınır.

Ayrık Fourier Dönüşümleri (DFT)

Bir önceki bölümde, işlevi bileşenlere ayırmanın güzel olacağı sonucuna vardık. 19. yüzyılın başında Fourier de bunu düşündü. Doğru, rakunlu bir resmi yoktu, bu yüzden metal bir halka üzerindeki ısı dağılımını araştırmak zorunda kaldı. Daha sonra, halkanın her noktasındaki sıcaklığı (ve değişimini) farklı periyotlara sahip sinüzoidlerin toplamı olarak ifade etmenin çok uygun olduğunu keşfetti. "Fourier, ikinci harmoniğin birinciden 4 kat daha hızlı bozulduğunu ve daha yüksek dereceli harmoniklerin daha da hızlı bozulduğunu tespit etti (okumanızı tavsiye ederim, ilginç).
Genel olarak, kısa süre sonra periyodik fonksiyonların dikkate değer bir şekilde bir sinüzoid toplamına ayrıştırılabileceği ortaya çıktı. Ve doğada periyodik fonksiyonlarla tanımlanan birçok nesne ve süreç olduğundan, bunların analizi için güçlü bir araç ortaya çıkmıştır.
Belki de en belirgin periyodik süreçlerden biri sestir.

• 1. grafik - 2500 hertz frekanslı saf bir ton.
• 2. - beyaz gürültü. Yani, tüm aralıkta eşit olarak dağıtılmış frekanslara sahip gürültü.
• 3 - ilk ikisinin toplamı.

Fourier serilerini bilmediğim bir zamanda son fonksiyonun değerleri bana verilse ve bunları analiz etmem istense, o zaman kesinlikle zarara girer ve değerli bir şey söyleyemezdim. Evet, bir tür işlev, ama orada sipariş edilen bir şey olduğu nasıl anlaşılır? Ama son işlevi dinlemeyi düşünseydim, kulak gürültünün arasında saf bir ses yakalardı. Çok iyi olmasa da, üretim sırasında bu tür parametreleri özellikle seçtim, böylece sinyal toplam grafikte gürültüde görsel olarak çözülür. Anladığım kadarıyla, işitme cihazının bunu nasıl yaptığı hala tam olarak ayarlanmadı. Ancak son zamanlarda sesi sinüzoidlere ayırmadığı anlaşıldı. Belki bir gün bunun nasıl olduğunu anlayacağız ve daha gelişmiş algoritmalar ortaya çıkacak. Hâlâ eski modayız.
Neden sinüzoidleri temel almayı denemiyorsunuz? Aslında, aslında zaten yaptık. 3 temel vektöre ayrıştırmamızı hatırlayın ve bunları bir grafik üzerinde gösterin:

Evet, evet, uygun göründüğünü biliyorum ama üç vektörle daha fazlasını beklemek zor. Ama şimdi örneğin 8 temel vektörün nasıl elde edileceği açık:


Çok zor olmayan bir kontrol, bu vektörlerin ikili olarak dik, yani ortogonal olduğunu gösterir. Bu, temel olarak kullanılabilecekleri anlamına gelir. Böyle bir temel üzerinde bir dönüşüm iyi bilinmektedir ve Ayrık Kosinüs Dönüşümü (DCT) olarak adlandırılır. Sanırım yukarıdaki grafiklerden DCT-dönüşüm formülünün nasıl elde edildiği açıkça görülüyor:

Hâlâ aynı formül: A = EX, ikame esaslı. Belirtilen DCT'nin temel vektörleri (bunlar E matrisinin satır vektörleridir) ortogonaldir, ancak ortonormal değildir. Ters dönüşüm sırasında bu hatırlanmalıdır (bunun üzerinde durmayacağım, ancak ilgilenenler için, tabanın sıfır vektörü diğerlerinden daha büyük olduğundan, ters DCT'nin 0,5*a 0 terimi vardır).
Aşağıdaki örnek, alt toplamları orijinal değerlere yaklaştırma sürecini göstermektedir. Her yinelemede, bir sonraki temel, bir sonraki katsayı ile çarpılır ve ara toplama eklenir (yani, rakun üzerindeki erken deneylerde olduğu gibi - değerlerin üçte biri, üçte ikisi).

Ancak, yine de, böyle bir temeli seçmenin uygunluğu hakkında bazı tartışmalara rağmen, henüz gerçek bir argüman yok. Gerçekten de, sesten farklı olarak, bir görüntüyü periyodik fonksiyonlara ayırmanın yararı çok daha az açıktır. Bununla birlikte, görüntü küçük bir alanda bile gerçekten çok tahmin edilemez olabilir. Bu nedenle, resim yeterince küçük parçalara bölünür, ancak ayrıştırmanın bir anlam ifade etmesi için çok da küçük değildir. JPEG'de görüntü 8x8 karelere "dilimlenir". Böyle bir parça içinde, fotoğraflar genellikle çok tekdüzedir: arka plan artı hafif dalgalanmalar. Bu tür alanlara sinüzoidler tarafından zarif bir şekilde yaklaşılır.
Bu gerçeğin az çok sezgisel olduğunu varsayalım. Ancak keskin renk geçişleri konusunda kötü bir his var çünkü yavaş değişen işlevler bizi kurtarmaz. İşlerini yapan, ancak homojen bir arka plana karşı yanlarda görünen çeşitli yüksek frekanslı işlevler eklemeliyiz. İki kontrast alanı olan bir 256x256 görüntü alalım:

Her satırı DCT kullanarak ayrıştırırız, böylece satır başına 256 katsayı elde ederiz.
Sonra sadece ilk n katsayıları bırakırız ve gerisini sıfıra eşitleriz ve bu nedenle görüntü yalnızca ilk harmoniklerin toplamı olarak temsil edilecektir:

Resimdeki sayı kalan bahis sayısıdır. İlk resimde sadece ortalama değer kalıyor. İkinciye bir düşük frekanslı sinüzoid zaten eklendi, vb. Bu arada, sınıra dikkat edin - tüm en iyi yaklaşımlara rağmen, diyagonalin yakınında 2 şerit açıkça görülebilir, biri daha açık, diğeri daha koyu . 4 kez büyütülmüş son resmin bir kısmı:

Ve genel olarak, sınırdan uzakta ilk düzgün arka planı görürsek, o zaman ona yaklaşırken genlik büyümeye başlar, sonunda minimum bir değere ulaşır ve sonra keskin bir şekilde maksimum olur. Bu fenomen Gibbs etkisi olarak bilinir.

Fonksiyonun süreksizliklerinin yakınında ortaya çıkan bu tümseklerin yüksekliği, fonksiyonların terim sayısındaki artışla azalmayacaktır. Kesikli bir dönüşümde, yalnızca hemen hemen tüm katsayılar korunduğunda kaybolur. Daha doğrusu görünmez olur.
Aşağıdaki örnek, yukarıdaki üçgen ayrıştırmasına tamamen benzer, ancak gerçek bir rakun üzerinde:


DCT çalışırken, yalnızca ilk birkaç (düşük frekans) katsayıların her zaman yeterli olduğu yolunda yanlış bir izlenim edinilebilir. Bu, değerleri büyük ölçüde değişmeyen birçok fotoğraf için geçerlidir. Bununla birlikte, zıt alanların sınırında, değerler hızlı bir şekilde "atlayacak" ve hatta son katsayılar büyük olacaktır. Bu nedenle, DCT'nin enerji tasarrufu özelliğini duyduğunuzda, karşılaştığınız birçok sinyal türü için geçerli olduğunu, ancak hepsi için geçerli olmadığını dikkate alın. Örnek olarak, sonuncusu dışında genişleme katsayıları sıfırsa ayrık bir fonksiyonun nasıl görüneceğini düşünün. İpucu: ayrıştırmayı vektör biçiminde temsil edin.
Eksikliklere rağmen, seçilen temel, gerçek fotoğrafların en iyilerinden biridir. Biraz sonra diğerleriyle küçük bir karşılaştırma göreceğiz.

DCT vs her şey

Ortogonal dönüşümler konusunu çalıştığımda, açıkçası, etraftaki her şeyin harmonik salınımların toplamı olduğu argümanlarına pek ikna olmadım, bu yüzden resimleri sinüzoidlere ayırmanız gerekiyor. Ya da belki bazı adım işlevleri daha uygun olur? Bu nedenle, gerçek görüntüler üzerinde DCT'nin optimalliği üzerine araştırma sonuçları arıyordum. “Enerji yoğunluğu” özelliğinden dolayı pratik uygulamalarda en sık rastlanan DCT olduğu gerçeği her yerde yazılıdır. Bu özellik, maksimum bilgi miktarının ilk katsayılarda yer aldığı anlamına gelir. Ve neden? Bir araştırma yapmak zor değil: Kendimizi bir dizi farklı resim, bilinen çeşitli temellerle donatıyoruz ve farklı sayıda katsayı için gerçek görüntüden standart sapmayı hesaplamaya başlıyoruz. Bu teknikle ilgili makalede (kullanılan resimler) küçük bir çalışma buldum. Depolanan enerjinin farklı bazlardaki ilk genişleme katsayılarının sayısına bağımlılığının grafiklerini içerir. Grafiklere baktıysanız, DCT'nin sürekli olarak onurlu bir… ee… 3. sırada olduğunu göreceksiniz. Nasıl yani? KLT dönüşümü başka nedir? DCT'yi övdüm ve sonra...

KLT

KLT dışındaki tüm dönüşümler sabit tabanlı dönüşümlerdir. Ve KLT'de (Karhunen-Loeve dönüşümü) birkaç vektör için en uygun temel hesaplanır. İlk katsayılar tüm vektörler için toplamda en küçük ortalama karekök hatasını verecek şekilde hesaplanır. Benzer çalışmaları daha önce manuel olarak gerçekleştirerek temeli görsel olarak belirledik. İlk başta bu sağlam bir fikir gibi görünüyor. Örneğin, görüntüyü küçük bölümlere ayırabilir ve her biri için farklı bir temel hesaplayabiliriz. Ancak, yalnızca bu temeli saklamanın özeni ortaya çıkmakla kalmaz, aynı zamanda hesaplanmasının işleyişi de oldukça zahmetlidir. Ve DCT sadece biraz kaybeder ve ayrıca DCT'nin hızlı dönüştürme algoritmaları vardır.

DFT

DFT (Ayrık Fourier Dönüşümü) - ayrık Fourier dönüşümü. Bu ad bazen yalnızca belirli bir dönüşüme değil, aynı zamanda tüm ayrık dönüşümler sınıfına da atıfta bulunur (DCT, DST...). DFT formülüne bakalım:

Tahmin edebileceğiniz gibi, bu bir tür karmaşık temele sahip ortogonal bir dönüşümdür. Böyle karmaşık bir form normalden biraz daha sık meydana geldiğinden, türevini incelemek mantıklıdır.
DCT ayrıştırmadaki herhangi bir saf harmonik sinyalin (bir tamsayı frekansı ile) bu harmoniğe karşılık gelen yalnızca sıfır olmayan bir katsayı vereceği izlenimi edinilebilir. Bu böyle değildir, çünkü frekansın yanı sıra bu sinyalin fazı da önemlidir. Örneğin, sinüsün kosinüs cinsinden genişlemesi (aynı şekilde ayrık genişlemede) aşağıdaki gibi olacaktır:

İşte size saf bir armonika. Bir sürü başkalarını doğurdu. Animasyon, sinüzoidin DCT katsayılarını farklı fazlarda gösterir.


Sütunların bir eksen etrafında döndüğü size göründüyse, o zaman size görünmüyordu.
Şimdi fonksiyonu, sadece farklı frekanslarda değil, aynı zamanda bazı fazlarda kaymış sinüzoidlerin toplamına ayrıştıracağız. Bir kosinüs örneğini kullanarak faz kaymasını düşünmek daha uygun olacaktır:

Basit bir trigonometrik özdeşlik önemli bir sonuç verir: faz kayması, cos(b) ve sin(b) katsayılarıyla alınan sinüs ve kosinüsün toplamı ile değiştirilir. Bu, fonksiyonların sinüs ve kosinüs toplamına (fazsız) ayrıştırılabileceği anlamına gelir. Bu yaygın bir trigonometrik formdur. Bununla birlikte, karmaşık çok daha sık kullanılır. Bunu elde etmek için Euler formülünü kullanmanız gerekir. Sinüs ve kosinüs için türev formüllerini yerine koyarsak şunu elde ederiz:


Şimdi küçük bir değişiklik. Alt çizgi eşlenik sayıdır.

Son eşitliği elde ederiz:

c, gerçek kısmı kosinüs katsayısına ve sanal kısmı sinüs katsayısına eşit olan karmaşık bir katsayıdır. Ve (cos(b), sin(b)) noktaları kümesi bir dairedir. Böyle bir gösterimde, her harmonik genişlemeye hem pozitif hem de negatif frekanslarla girer. Bu nedenle, Fourier analizinin çeşitli formüllerinde, genellikle eksiden artı sonsuza toplama veya entegrasyon gerçekleşir. Hesaplamaları böyle karmaşık bir biçimde yapmak genellikle daha uygundur.
Dönüştürme, sinyali, sinyal alanına bir ile N osilasyonları arasındaki frekanslarla harmoniklere ayrıştırır. Ancak örnekleme hızı, sinyal alanı başına N'dir. Ve Kotelnikov teoremine göre (diğer adıyla Nyquist-Shannon teoremi), örnekleme frekansı, sinyal frekansının en az iki katı olmalıdır. Durum böyle değilse, yanlış frekanslı bir sinyalin görünümünün etkisi elde edilir:

Noktalı çizgi, yanlış yeniden oluşturulmuş sinyali gösterir. Hayatınızda bu fenomenle sık sık karşılaştınız. Örneğin, bir videoda bir arabanın tekerleklerinin komik bir hareketi veya hare efekti.
Bu, N karmaşık genliklerinin ikinci yarısının başka frekanslardan oluştuğu gerçeğine yol açar. İkinci yarının bu yanlış harmonikleri, birinci yarının ayna görüntüsüdür ve ek bilgi içermez. Böylece elimizde N/2 kosinüs ve N/2 sinüs (dik bir temel oluşturan) kalır.
Tamam, bir temeli var. Bileşenleri, sinyal alanında tam sayıda salınımlara sahip harmoniklerdir, bu, harmoniklerin aşırı değerlerinin eşit olduğu anlamına gelir. Daha doğrusu, son değer tam olarak kenardan alınmadığından neredeyse eşittirler. Ayrıca her harmonik, merkezine göre neredeyse ayna simetriktir. Tüm bu fenomenler, kodlama yaparken bizim için önemli olan düşük frekanslarda özellikle güçlüdür. Bu da kötüdür çünkü blok sınırları sıkıştırılmış görüntüde fark edilir. DFT tabanını N=8 ile göstereceğim. İlk 2 satır kosinüs bileşenleri, sonuncusu sinüs:

Frekans arttıkça yinelenen bileşenlerin görünümüne dikkat edin.

Değerleri başlangıçtaki maksimum değerden sonunda minimum değere yumuşak bir şekilde düşen bir sinyalin nasıl ayrıştırılabileceğini zihinsel olarak düşünebilirsiniz. Aşağı yukarı yeterli bir yaklaşım ancak sonlara doğru harmonikler tarafından yapılabilir, ki bu bizim için pek hoş değil. Soldaki şekil, tek uçlu bir sinyalin bir tahminidir. Sağ - simetrik:


İlki son derece kötü.
Yani DCT'de olduğu gibi yapılabilir - frekansları 2 veya daha fazla kez azaltmak, böylece bazı salınımların sayısı kesirli ve sınırlar farklı fazlarda mı? O zaman bileşenler ortogonal olmayacak. Ve yapacak bir şey yok.

DST

DCT'de kosinüs yerine sinüs kullanırsak ne olur? Ayrık Sinüs Dönüşümü (DST) alacağız. Ancak bizim görevimiz için, sinüslerin hem tamsayıları hem de yarım periyotları sınırlarda sıfıra yakın olduğundan, hepsi ilgi çekici değildir. Yani, DFT ile yaklaşık olarak aynı uygunsuz ayrıştırmayı elde edeceğiz.

DCT'ye dönüş

Sınırlarda durumu nasıl? İyi. Antifazlar var ve sıfır yok.

Tüm kalan

Fourier olmayan dönüşümler. tarif etmeyeceğim.
WHT - matris yalnızca -1 ve 1 değerlerine sahip adım bileşenlerinden oluşur.
Haar - yarı zamanlı dikey dalgacık dönüşümü.
DCT'den daha düşüktürler, ancak hesaplanması daha kolaydır.

Böylece, kendi dönüşümünüzü yaratma fikri size geldi. Hatırla bunu:

1. Temel ortogonal olmalıdır.
2. Sabit bir temelde, sıkıştırma kalitesi açısından KLT'yi geçemezsiniz. Bu arada, gerçek fotoğraflarda DCT neredeyse iyi.
3. DFT ve DST örneğinde, sınırları hatırlamanız gerekir.
4. Ve DCT'lerin başka bir iyi avantajı olduğunu unutmayın - bileşenlerinin sınırları yakınında, türevler sıfıra eşittir, bu da komşu bloklar arasındaki geçişin oldukça düzgün olacağı anlamına gelir.
5. Fourier dönüşümleri, alındaki hesaplamanın aksine O(N*logN) karmaşıklığına sahip hızlı algoritmalara sahiptir: O(N 2).

Kolay olmayacak, değil mi? Ancak bazı görüntü türleri için DCT'den daha iyi bir temel seçebilirsiniz.

2B dönüşümler

Şimdi böyle bir deney yapmaya çalışalım. Örneğin, bir görüntü parçası alın.

3D şeması:

Her satır için DCT(N=32) üzerinden gidelim:

Şimdi, elde edilen katsayıların her bir sütunu üzerinde gözlerinizi gezdirmenizi istiyorum, yani yukarıdan aşağıya. Amacımızın, önemli olmayanları dışarıda bırakarak mümkün olduğunca az değer tutmak olduğunu hatırlayın. Muhtemelen elde edilen katsayıların her bir sütununun değerlerinin, orijinal görüntünün değerleriyle tamamen aynı şekilde ayrıştırılabileceğini tahmin etmişsinizdir. Ortogonal bir dönüşüm matrisi seçmemizde kimse bizi kısıtlamaz, ancak bunu DCT(N=8) kullanarak tekrar yapacağız:

Katsayının (0.0) çok büyük olduğu ortaya çıktı, bu nedenle grafikte 4 kat azaldı.
Peki ne oldu?
Sol üst köşe, en önemli katsayıların ayrıştırılmasının en önemli katsayılarıdır.
Sol alt köşe, en önemli katsayıların en önemsiz genişleme katsayılarıdır.
Sağ üst köşe, en önemsiz katsayıların en anlamlı genişleme katsayılarıdır.
Sağ alt köşe, en önemsiz katsayıların en önemsiz genişleme katsayılarıdır.
Sol üst köşeden sağ alt köşeye çapraz hareket edersek katsayıların öneminin azaldığı açıktır. Hangisi daha önemli: (0, 7) veya (7, 0)? Ne anlama geliyorlar?
Önce satırlarla: A 0 = (EX T) T = XE T (sütunlar için A=EX formülünden dolayı yer değiştirir), ardından sütunlarla: A=EA 0 = EXE T . Dikkatlice hesaplarsanız, formülü elde edersiniz:

Bu nedenle, vektör sinüzoidlere ayrıştırılırsa, matris cos(ax)*cos(by) biçimindeki fonksiyonlara ayrılır. JPEG'deki her 8x8 blok, formun 64 fonksiyonunun toplamı olarak temsil edilir:


Wikipedia'da ve diğer kaynaklarda, bu tür işlevler daha uygun bir biçimde sunulur:

Bu nedenle, (0, 7) veya (7, 0) katsayıları eşit derecede faydalıdır.
Bununla birlikte, aslında, bu 64 64 boyutlu tabana olağan tek boyutlu genişlemedir. Yukarıdakilerin tümü yalnızca DCT için değil, aynı zamanda herhangi bir ortogonal ayrıştırma için de geçerlidir. Analojiyle hareket ederek, genel durumda N boyutlu bir ortogonal dönüşüm elde ederiz.
Ve işte 2D rakun dönüşümü (DCT 256x256). Yine sıfır değerlerle. Sayılar - hepsinden sıfır olmayan katsayıların sayısı (sol üst köşedeki üçgen alanda bulunan en önemli değerler bırakıldı).

(0, 0) katsayısının DC, diğer 63'ün AC olduğunu unutmayın.

Blok boyutu seçimi

Yoldaş soruyor: JPEG'de neden 8x8 bölme kullanılıyor. Oylanan cevaptan:

DCT, bloğa periyodikmiş gibi davranır ve sınırlarda ortaya çıkan sıçramayı yeniden yapılandırması gerekir. 64x64 blok alırsanız, büyük olasılıkla sınırlarda büyük bir sıçrama yapacaksınız ve bunu tatmin edici bir hassasiyetle yeniden yapılandırmak için çok sayıda yüksek frekanslı bileşene ihtiyacınız olacak.

Örneğin, DCT yalnızca periyodik işlevlerde iyi çalışır ve büyük bir boyut alırsanız, büyük olasılıkla blok sınırlarında dev bir sıçrama yapacaksınız ve bunu kapatmak için çok sayıda yüksek frekanslı bileşene ihtiyacınız olacak. Bu doğru değil! Böyle bir açıklama DFT'ye çok benzer, ancak DCT'ye değil, çünkü bu tür atlamaları zaten ilk bileşenlerle mükemmel bir şekilde kapsıyor.
Aynı sayfada, büyük bloklara karşı ana argümanlarla birlikte MPEG SSS'den bir cevap var:

• Büyük bloklara ayrılırken az kar.
• Artan hesaplama karmaşıklığı.
• Bir blokta Gibbs etkisine neden olacak çok sayıda keskin kenarın yüksek olasılığı.

Bunu kendi başına araştırmanı öneririm. İle başlayalım ilk.


Yatay eksende - ilk sıfır olmayan katsayıların oranı. Dikey - piksellerin orijinalden standart sapması. Mümkün olan maksimum sapma bir olarak alınır. Tabii ki, bir karar için bir fotoğraf açıkça yeterli değil. Ayrıca, doğru yapmıyorum, sadece sıfırlıyorum. Gerçek bir JPEG'de, niceleme matrisine bağlı olarak, yüksek frekans bileşenlerinin yalnızca küçük değerleri sıfırlanır. Bu nedenle, aşağıdaki deneyler ve sonuçlar, ilke ve kalıpları yüzeysel olarak ortaya koymayı amaçlamaktadır.
Bölmeyi, katsayıların kalan yüzde 25'iyle (soldan sağa, sonra sağdan sola) farklı bloklara karşılaştırabilirsiniz:

Görsel olarak 32x32'den neredeyse ayırt edilemez oldukları için büyük bloklar gösterilmemiştir. Şimdi orijinal görüntüyle arasındaki mutlak farka bakalım (2 kat artırılmış, aksi takdirde hiçbir şey gerçekten görünmez):

8x8, 4x4'ten daha iyi sonuçlar verir. Boyutta daha fazla artış, artık açıkça görülebilir bir avantaj sağlamaz. 8x8 yerine 16x16'yı ciddi olarak düşünecek olsam da: zorlukta %33'lük bir artış (bir sonraki paragrafta zorluk hakkında daha fazla bilgi) aynı sayıda katsayı ile küçük ama yine de görünür bir gelişme sağlar. Ancak, 8x8 seçimi oldukça makul görünüyor ve belki de altın ortalamadır. JPEG 1991'de yayınlandı. O zamanın işlemcileri için böyle bir sıkıştırmanın çok zor olduğunu düşünüyorum.

İkinci argüman. Unutulmamalıdır ki blok boyutu arttıkça daha fazla hesaplama yapılması gerekecektir. Nasıl olduğunu değerlendirelim. Alına dönüştürmenin karmaşıklığı, zaten nasıl yapılacağını bildiğimiz gibi: O (N 2), çünkü her katsayı N terimden oluşur. Ancak pratikte verimli bir Hızlı Fourier Dönüşümü (FFT) algoritması kullanılır. Açıklaması makalenin kapsamı dışındadır. Karmaşıklığı: O(N*logN). İki boyutlu bir genişleme için iki kez N kez kullanmanız gerekir. Dolayısıyla 2B DCT'nin karmaşıklığı O(N 2 logN)'dir. Şimdi bir görüntü hesaplamanın karmaşıklığını bir blok ve birkaç küçük blokla karşılaştıralım:

• Bir blokta (kN)x(kN): O((kN) 2 log(kN)) = O(k 2 N 2 log(kN))
• k*k N*N blok: O(k 2 N 2 logN)

Bu, örneğin 64x64'te bölme yaparken hesaplamanın 8x8'de olduğundan iki kat daha zor olduğu anlamına gelir.

Üçüncü argüman. Görüntüde keskin bir renk sınırımız varsa, bu tüm bloğu etkiler. Belki de bu bloğun yeterince küçük olması daha iyidir, çünkü birçok komşu blokta böyle bir sınır muhtemelen artık mevcut olmayacaktır. Ancak, sınırlardan uzakta, zayıflama oldukça hızlı gerçekleşir. Ayrıca, sınırın kendisi daha iyi görünecek. Katsayıların yalnızca dörtte biri ile yine çok sayıda kontrast geçişli bir örnek üzerinde kontrol edelim:


16x16 blok distorsiyonu 8x8'den daha fazla uzansa da, harfler daha pürüzsüz. Bu nedenle, yalnızca ilk iki argüman beni ikna etti. Ama 16x16 bölümünü daha çok seviyorum.

niceleme

Bu aşamada, kosinüs dönüşüm katsayılarına sahip bir grup 8x8 matrisimiz var. Önemsiz katsayılardan kurtulmanın zamanı geldi. Yukarıda yaptığımız gibi, sadece son katsayıları sıfıra sıfırlamaktan daha zarif bir çözüm var. Sıfır olmayan değerler aşırı hassasiyetle saklandığı için bu yöntemden memnun değiliz ve şanssız olanlar arasında oldukça önemli olanlar olabilir. Çıkış yolu bir niceleme matrisi kullanmaktır. Bu aşamada kayıplar meydana gelir. Her Fourier katsayısı, niceleme matrisindeki karşılık gelen sayıya bölünür. Bir örneğe bakalım. Rakunumuzdan ilk bloğu alıp nicelleştirelim. JPEG özelliği standart bir matris sağlar:


Standart matris, FastStone ve IrfanView'da %50 kaliteye karşılık gelir. Kalite ve sıkıştırma oranı dengesi açısından böyle bir tablo seçilmiştir. DCT'nin normalize edilmemesi ve ilk değerin olması gerekenden daha büyük olması nedeniyle DC katsayısı değerinin komşu olanlardan daha büyük olduğunu düşünüyorum. Yüksek frekans katsayıları daha az önem taşıdıkları için daha çok kabalaştırılır. Kalitedeki bozulma açıkça fark edildiğinden, artık bu tür matrislerin nadiren kullanıldığını düşünüyorum. Hiç kimse masasını kullanmayı yasaklamaz (1'den 255'e kadar değerlerle)
Kod çözme sırasında, ters işlem gerçekleşir - nicelenmiş katsayılar, niceleme matrisinin değerleri ile terim terimle çarpılır. Ancak değerleri yuvarladığımız için orijinal Fourier katsayılarını doğru bir şekilde geri yükleyemeyeceğiz. Kuantizasyon sayısı ne kadar büyük olursa, hata o kadar büyük olur. Bu nedenle, geri kazanılan katsayı yalnızca en yakın kattır.
Başka bir örnek:

Tatlı olarak da %5 kaliteyi göz önünde bulundurun (Fast Stone'da kodlama yaparken).


Bu bloğu geri yüklediğimizde, yalnızca ortalama değeri artı dikey gradyanı elde edeceğiz (korunmuş -1 değeri nedeniyle). Ancak bunun için yalnızca iki değer saklanır: 7 ve -1. Diğer bloklarda durum daha iyi değil, işte geri yüklenen resim:

Bu arada, yaklaşık% 100 kalite. Tahmin edebileceğiniz gibi, bu durumda nicemleme matrisi tamamen birlerden oluşur, yani nicemleme gerçekleşmez. Ancak katsayıların en yakın tam sayıya yuvarlanmasından dolayı orijinal görüntüyü tam olarak geri yükleyemiyoruz. Örneğin, rakun piksellerin %96'sını tam olarak korudu ve %4'ü 1/256 oranında farklılık gösterdi. Tabii ki, bu tür "bozulmalar" görsel olarak görülemez.
Ve çeşitli kameraların niceleme matrislerine bakabilirsiniz.

kodlama

Devam etmeden önce, daha basit örnekler kullanarak, alınan değerleri nasıl sıkıştırabileceğimizi anlamamız gerekiyor.

Örnek 0(ısınma için)
Arkadaşınızın evinizde bir listenin olduğu bir kağıt parçasını unuttuğu ve şimdi sizden bunu telefonda dikte etmenizi istediği bir durum düşünün (başka bir iletişim yolu yoktur).
Liste:

• d9rg3
• wfr43gt
• wfr43gt
• d9rg3
• d9rg3
• d9rg3
• wfr43gt
• d9rg3

Görevinizi nasıl kolaylaştırırsınız? Tüm bu kelimeleri acı verici bir şekilde dikte etmek için özel bir arzunuz yok. Ancak bunlardan sadece ikisi var ve bunlar tekrarlanıyor. Bu nedenle, sadece bir şekilde ilk iki kelimeyi dikte edersiniz ve daha sonra ilk kelimeyi “d9rg3” ve ikinci kelimeyi “wfr43gt” olarak adlandıracağınızı kabul edersiniz. O zaman şunu dikte etmeniz yeterli olacaktır: 1, 2, 2, 1, 1, 1, 2, 1.

A, B, C gibi kelimeleri belirleyeceğiz ve onlara semboller diyeceğiz. Ayrıca, sembolün altına her şey gizlenebilir: alfabenin bir harfi, bir kelime veya hayvanat bahçesindeki bir su aygırı. Ana şey, aynı sembollerin aynı kavramlara karşılık gelmesi ve farklı - farklı olmasıdır. Görevimiz verimli kodlama (sıkıştırma) olduğundan, bunlar bilgi temsilinin en küçük birimleri olduğundan bitlerle çalışacağız. Bu nedenle listeyi ABBAAAABA olarak yazıyoruz. "Birinci kelime" ve "ikinci kelime" yerine 0 ve 1 bitleri kullanılabilir.Daha sonra ABBAAAABA 01100010 (8 bit = 1 bayt) olarak kodlanır.

örnek 1
ABC'yi kodlayın.
3 farklı karakter (A, B, C) 2 olası bit değerine (0 ve 1) eşlenemez. Ve eğer öyleyse, karakter başına 2 bit kullanabilirsiniz. Örneğin:

• bir:00
• b:01
• C:10

Bir sembolle ilişkili bit dizisine kod adı verilir. ABC şu şekilde kodlanacaktır: 000110.

Örnek 2
AAAAAABC'yi kodlayın.
A karakteri başına 2 bit kullanmak biraz savurgan görünüyor. Şöyle denerseniz ne olur:

• C:00

Kodlanmış sıra: 000000100.
Açıkçası, bu seçenek uygun değildir, çünkü bu dizinin ilk iki bitinin nasıl çözüleceği açık değildir: AA olarak mı yoksa C olarak mı? Kodlar arasında bir çeşit ayırıcı kullanmak çok israftır, bu engeli farklı bir şekilde nasıl aşacağımızı düşüneceğiz. Bu yüzden başarısızlık, C kodunun A koduyla başlamasıdır. Ama B ve C iki olsa bile A'yı bir bitle kodlamaya kararlıyız. Bu dilekten yola çıkarak A'ya 0 kodunu veriyoruz. O zaman B ve C kodları 0 ile başlayamaz. Ama 1 ile başlayabilirler:

• B:10
• C:11

Sıra şu şekilde kodlanacaktır: 0000001011. Zihinsel olarak kodunu çözmeye çalışın. Bunu sadece bir şekilde yapabilirsiniz.
İki kodlama gereksinimi geliştirdik:

1. Bir karakterin ağırlığı ne kadar büyükse, kodu o kadar kısa olmalıdır. Ve tam tersi.
2. Belirsiz kod çözme için, bir karakter kodu başka bir karakter koduyla başlayamaz.

Açıkçası, karakterlerin sırası önemli değil, sadece ortaya çıkma sıklığıyla ilgileniyoruz. Bu nedenle, her karakter, ağırlık adı verilen belirli bir sayı ile ilişkilendirilir. Bir sembolün ağırlığı ya onun oluşum payını yansıtan göreli bir değer ya da sembollerin sayısına eşit bir mutlak değer olabilir. Ana şey, ağırlıkların karakterlerin oluşumuyla orantılı olmasıdır.

Örnek 3
Herhangi bir ağırlığa sahip 4 karakter için genel durumu düşünün.

• bir: baba
• B:pb
• C: bilgisayar
• D:pd

Genelliği kaybetmeden pa ≥ pb ≥ pc ≥ pd koyduk. Uzunluk kodlarında temelde farklı olan yalnızca iki seçenek vardır:


Hangisi tercih edilir? Bunu yapmak için, alınan kodlanmış mesajların uzunluklarını hesaplamanız gerekir:
W1 = 2*pa + 2*pb + 2*pc + 2*pd
W2 = pa + 2*pb + 3*pc + 3*pd
W1, W2'den küçükse (W1-W2<0), то лучше использовать первый вариант:
W1-W2 = pa - (pc+pd)< 0 =>baba< pc+pd.
C ve D diğerlerinden daha sık birlikte meydana gelirse, ortak tepe noktaları en kısa tek bitlik kodu alır. Aksi takdirde, bir bit A karakterine gider. Dolayısıyla, karakterlerin birleşimi bağımsız bir karakter gibi davranır ve gelen karakterlerin toplamına eşit bir ağırlığa sahiptir.
Genel olarak, p, oluşumunun bir kesriyle (0 ile 1 arasında) temsil edilen bir karakterin ağırlığıysa, o zaman en iyi kod uzunluğu s=-log 2 p'dir.
Bunu basit bir durum üzerinde düşünelim (bir ağaç şeklinde temsil etmek kolaydır). Bu yüzden 2 s karakteri eşit ağırlıkta (1/2 s) kodlamamız gerekiyor. Ağırlıkların eşitliğinden dolayı kodların uzunlukları da aynı olacaktır. Her karakterin s bitine ihtiyacı olacaktır. Yani, bir karakterin ağırlığı 1/2 s ise, uzunluğu s'dir. Ağırlık p ile değiştirilirse, s=-log 2 p kod uzunluğunu alırız. Bu, bir karakter diğerinden iki kat daha seyrek olarak ortaya çıkarsa, kodunun uzunluğunun bir bit daha uzun olacağı anlamına gelir. Bununla birlikte, bir bit eklemenin olası seçeneklerin sayısını iki katına çıkarmanıza izin verdiğini hatırlarsanız, böyle bir sonuç çıkarmak kolaydır.
Ve bir gözlem daha - en küçük ağırlığa sahip iki sembol her zaman en büyük fakat eşit kod uzunluklarına sahiptir. Ayrıca, sonuncusu hariç bitleri aynıdır. Bu doğru değilse, öneki ihlal etmeden en az bir kod 1 bit kısaltılabilir. Bu, kod ağacındaki en küçük ağırlığa sahip iki karakterin bir seviye daha yüksek ortak bir ebeveyne sahip olduğu anlamına gelir. Bunu yukarıdaki C ve D'de görebilirsiniz.

Örnek 4
Aşağıdaki örneği, önceki örnekte elde edilen sonuçlara göre çözmeye çalışalım.

1. Tüm karakterler azalan ağırlık sırasına göre sıralanır.
2. Son iki karakter bir grup halinde birleştirilir. Bu gruba, bu elemanların ağırlıklarının toplamına eşit bir ağırlık atanır. Bu grup, semboller ve diğer gruplarla birlikte algoritmaya katılır.

Adımlar sadece bir grup kalana kadar tekrarlanır. Her grupta bir karaktere (veya alt gruba) bit 0 ve diğer bit 1 atanır.
Bu algoritmaya Huffman kodlaması denir.
Resimde 5 karakterli bir örnek gösterilmektedir (A: 8, B: 6, C: 5, D: 4, E: 3). Sağda sembolün (veya grubun) ağırlığı bulunur.

katsayıları kodlama

Geri döndük. Şimdi, bir şekilde kaydedilmesi gereken, her biri 64 katsayılı birçok bloğumuz var. En basit çözüm, faktör başına sabit sayıda bit kullanmaktır - açıkçası talihsizlik. Elde edilen tüm değerlerin bir histogramını oluşturalım (yani, katsayı sayısının değerlerine bağımlılığı):

Lütfen dikkat - ölçek logaritmiktir! 200'ü aşan değerlerin birikmesinin nedenini açıklayabilir misiniz? Bunlar DC katsayılarıdır. Diğerlerinden çok farklı oldukları için ayrı ayrı kodlanmaları şaşırtıcı değildir. İşte sadece DC:

Grafiğin şeklinin, çok erken piksel eşleştirme ve üçlü deneme deneylerinden elde edilen grafiklerin şekline benzediğini unutmayın.
Genel olarak, DC katsayılarının değerleri 0 ila 2047 arasında değişebilir (daha kesin olarak -1024 ila 1023 arasında, çünkü JPEG, DC'den 1024'ün çıkarılmasına karşılık gelen tüm orijinal değerlerden 128 çıkarır) ve küçük değerlerle oldukça eşit olarak dağıtılır. zirveler. Yani Huffman kodlaması burada pek yardımcı olmaz. Ayrıca kodlama ağacının ne kadar büyük olacağını da hayal edin! Ve kod çözme sırasında, içindeki değerleri aramanız gerekecek. Bu çok maliyetli. Devamını düşünüyoruz.
DC katsayısı - 8x8 bloğunun ortalama değeri. Fotoğraflarda sıklıkla bulunan bir degrade geçişi (ideal olmasa da) hayal edelim. DC değerlerinin kendileri farklı olacak, ancak aritmetik bir ilerlemeyi temsil edecekler. Bu nedenle, farkları aşağı yukarı sabit olacaktır. Bir farklılıklar histogramı oluşturalım:

Şimdi bu daha iyi, çünkü değerler genellikle sıfır civarında yoğunlaşıyor (ancak yine Huffman algoritması aşırı büyük bir ağaç verecektir). Küçük değerler (mutlak değerde) yaygındır, büyük olanlar nadirdir. Ve küçük değerler birkaç bit aldığından (baştaki sıfırlar kaldırılırsa), sıkıştırma kurallarından biri iyi çalışır: büyük ağırlıklı karakterlere kısa kodlar atayın (ve tersi). Hala başka bir kuralın yerine getirilmemesiyle sınırlıyız: açık kod çözmenin imkansızlığı. Genel olarak, bu sorun şu şekillerde çözülür: sınırlayıcı kodla karıştırmayın, kodun uzunluğunu belirtin, önek kodlarını kullanın (bunları zaten biliyorsunuz - bu, hiçbir kod diğeriyle başlamadığında geçerlidir). Basit ikinci seçenekle gidelim, yani her katsayı (daha doğrusu komşu olanlar arasındaki fark) aşağıdaki gibi yazılacaktır: (uzunluk) (değer), böyle bir plakaya göre:

Yani, pozitif değerler doğrudan ikili gösterimleriyle kodlanır ve negatif değerler aynı şekilde kodlanır, ancak baştaki 1 yerine 0 gelir. Geriye uzunlukların nasıl kodlanacağına karar vermek kalır. 12 olası değer olduğundan, uzunluğu saklamak için 4 bit kullanılabilir. Ancak burada Huffman kodlamasını kullanmak daha iyidir.

4 ve 6 uzunluklarında en fazla değer vardır, bu nedenle en kısa kodları (00 ve 01) aldılar.

Soru ortaya çıkabilir: örnekte neden 9 değeri 111111 değil de 111111 koduna sahip? Sonuçta, "9" u güvenli bir şekilde "0" ın yanında daha yüksek bir seviyeye yükseltebilir misiniz? Gerçek şu ki, JPEG'de yalnızca birimlerden oluşan bir kod kullanamazsınız - böyle bir kod saklıdır.
Bir özellik daha var. Tanımlanan Huffman algoritması tarafından elde edilen kodlar, uzunlukları aynı olmasına rağmen bitleri JPEG'deki kodlarla eşleşmeyebilir. Huffman algoritmasını kullanarak, kodların uzunlukları elde edilir ve kodların kendileri oluşturulur (algoritma basittir - kısa kodlarla başlarlar ve öneki koruyarak bunları mümkün olduğunca sola tek tek ağaca eklerler. Emlak). Örneğin, yukarıdaki ağaç için bir liste saklanır: 0,2,3,1,1,1,1,1,1. Ve elbette, bir değerler listesi saklanır: 4,6,3,5,7,2,8,1,0,9. Kod çözme sırasında kodlar aynı şekilde üretilir.

Şimdi sipariş ver. DC'lerin nasıl saklandığını bulduk:
[DC fark uzunluğu için Huffman kodu (bit olarak)]
DC farkı = DC akımı - DC önceki

AC'yi izleyin:

Çizim, DC farklılıkları grafiğine çok benzer olduğundan, ilke aynıdır: [AC uzunluğu için Huffman kodu (bit olarak)]. Ama gerçekten değil! Grafikteki ölçek logaritmik olduğundan, değerlerden yaklaşık 10 kat daha fazla sıfır değeri olduğu hemen fark edilmez - bir sonraki frekans. Bu anlaşılabilir bir durumdur - herkes nicelemeden sağ çıkmamıştır. Niceleme adımında elde edilen değerlerin matrisine geri dönelim (FastStone niceleme matrisini kullanarak, %90).

Birçok ardışık sıfır grubu olduğundan, fikir ortaya çıkar - gruptaki yalnızca sıfır sayısını yazmak. Bu sıkıştırma algoritmasına RLE (Çalışma uzunluğu kodlaması, tekrar kodlaması) adı verilir. "Arka arkaya gitme" baypasının yönünü bulmak için kalır - kim kimin arkasında? Sıfırdan farklı katsayılar sol üst köşede yoğunlaştığından ve sağ alt köşeye ne kadar yakınsa sıfır o kadar fazla olduğundan, soldan sağa ve yukarıdan aşağıya yazmak çok verimli değildir.

Bu nedenle JPEG, soldaki şekilde gösterildiği gibi "Zig-zag" adlı bir düzen kullanır. Bu yöntem, sıfır gruplarını iyi seçer. Sağdaki şekilde - JPEG ile ilgili olmayan, ancak ilginç bir adla (kanıt) alternatif bir atlama yolu. Geçmeli videoyu sıkıştırırken MPEG'de kullanılabilir. Bypass algoritmasının seçimi görüntü kalitesini etkilemez, ancak kodlanmış sıfır gruplarının sayısını artırabilir, bu da sonuçta dosya boyutunu etkileyebilir.
Girişimizi değiştirelim. Her sıfır olmayan AC - katsayısı için:
[AC'den önceki sıfır sayısı][AC uzunluğu için Huffman kodu (bit olarak)]
Bence hemen diyeceksiniz - sıfır sayısı da Huffman tarafından mükemmel bir şekilde kodlanmış! Bu çok yakın ve fena olmayan bir cevap. Ama biraz optimize edebilirsiniz. Önünde 7 sıfır bulunan bir AC katsayısına sahip olduğumuzu hayal edin (tabii ki, zikzak düzeninde yazılmışsa). Bu sıfırlar, kuantizasyondan sağ çıkamayan değerlerin ruhudur. Büyük olasılıkla, katsayımız da kötü bir şekilde hırpalandı ve küçüldü, bu da uzunluğunun kısa olduğu anlamına geliyor. Bu nedenle, AC'den önceki sıfırların sayısı ve AC'nin uzunluğu bağımlı niceliklerdir. Bu nedenle, şöyle yazılmıştır:
[Huffman kodu (AC'den önceki sıfır sayısı, AC uzunluğu (bit olarak)]
Kodlama algoritması aynı kalır: sıklıkla meydana gelen bu çiftler (AC'den önceki sıfır sayısı, AC uzunluğu) kısa kodları alır ve bunun tersi de geçerlidir.

Bu çiftlere ve bir Huffman ağacına miktarın bağımlılığının bir histogramını oluşturuyoruz.


Uzun "dağ silsilesi" varsayımımızı doğrular.

JPEG'deki uygulama özellikleri:
Böyle bir çift 1 bayt kaplar: sıfır sayısı için 4 bit ve AC'nin uzunluğu için 4 bit. 4 bit 0'dan 15'e kadar olan değerlerdir. AC uzunluk için fazlasıyla yeterlidir ama 15'ten fazla sıfır olabilir değil mi? Daha sonra daha fazla çift kullanılır. Örneğin, 20 sıfır için: (15, 0)(5, AC). Yani 16. sıfır sıfır olmayan bir katsayı olarak kodlanmıştır. Bloğun sonu her zaman sıfırlarla dolu olduğundan, (0,0) çifti, sıfır olmayan son katsayıdan sonra kullanılır. Kod çözme sırasında meydana gelirse, kalan değerler 0'a eşittir.

Kodlanan her bloğun dosyada şu şekilde saklandığını öğrendim:
[DC fark uzunluğu için Huffman kodu]
[huffman kodu (AC 1'den önceki sıfır sayısı, uzunluk AC 1 ]
…
[huffman kodu (AC n'den önceki sıfırların sayısı, AC n'nin uzunluğu]
AC i sıfır olmayan AC katsayılarıdır.

renkli görüntü

Renkli bir görüntünün temsil edilme şekli, seçilen renk modeline bağlıdır. Basit çözüm, RGB kullanmak ve görüntünün her bir renk kanalını ayrı ayrı kodlamaktır. O zaman kodlama, gri görüntünün kodlamasından farklı olmayacak, sadece 3 kat daha fazla çalışacak. Ancak gözün parlaklıktaki değişikliklere renkten daha duyarlı olduğunu hatırlarsak görüntü sıkıştırması arttırılabilir. Bu, rengin parlaklıktan daha fazla kayıpla saklanabileceği anlamına gelir. RGB'nin ayrı bir parlaklık kanalı yoktur. Her kanalın değerlerinin toplamına bağlıdır. Bu nedenle, RGB küpü (bu, tüm olası değerlerin bir temsilidir) köşegen üzerine basitçe “koyulur” - ne kadar yüksekse, o kadar parlaktır. Ancak bununla sınırlı değiller - küp yanlardan hafifçe bastırılır ve daha çok paralel yüzlü gibi görünür, ancak bu sadece gözün özelliklerini dikkate almak içindir. Örneğin, yeşile maviden daha açıktır. YCbCr modeli böyle doğdu.

(Intel.com'dan görüntü)
Y parlaklık bileşeni, Cb ve Cr mavi ve kırmızı renk farkı bileşenleridir. Bu nedenle, görüntüyü daha güçlü bir şekilde sıkıştırmak istiyorlarsa, RGB YCbCr'ye dönüştürülür ve Cb ve Cr kanalları inceltilir. Yani 2x2, 4x2, 1x2 gibi küçük bloklara bölünürler ve bir bloğun tüm değerlerinin ortalaması alınır. Veya başka bir deyişle, bu kanal için görüntü boyutunu dikey ve/veya yatay olarak 2 veya 4 kat küçültün.

Her 8x8 blok kodlanır (DCT + Huffman) ve kodlanan diziler şu sırayla yazılır:

JPEG spesifikasyonunun model seçimini sınırlamaması ilginçtir, yani kodlayıcı uygulaması görüntüyü keyfi olarak renk bileşenlerine (kanallara) bölebilir ve her biri ayrı ayrı kaydedilecektir. Gri Tonlamalı (1 kanal), YCbCr (3), RGB (3), YCbCrK (4), CMYK (4) kullandığımın farkındayım. İlk üçü hemen hemen herkes tarafından destekleniyor ancak son 4 kanallı olanlarda sorunlar var. FastStone, GIMP bunları doğru destekler ve standart Windows programları, paint.net tüm bilgileri doğru bir şekilde çıkarır, ancak daha sonra 4. siyah kanalı atar, yani (Antelle onu atmadıklarını söyledi, yorumlarını okuyun) daha hafif bir görüntü gösterir. Sol - klasik YCbCr JPEG, sağ CMYK JPEG:



Renkleri farklıysa veya yalnızca bir resim görünüyorsa, büyük olasılıkla IE'niz (herhangi bir sürüm) var (UPD. Yorumlarda “veya Safari” diyorlar). Makaleyi farklı tarayıcılarda açmayı deneyebilirsiniz.

Ve bir şey daha

Ek özellikler hakkında kısaca.

aşamalı mod

Elde edilen DCT katsayı tablolarını tabloların toplamına ayıralım (bunun gibi (DC, -19, -22, 2, 1) = (DC, 0, 0, 0, 0) + (0, -20, -20 , 0, 0) + (0, 1, -2, 2, 1)). İlk olarak, tüm ilk terimleri kodluyoruz (zaten öğrendiğimiz gibi: Huffman ve zikzak baypas), ardından ikinci terimler vb. Bu hile, yavaş İnternet için kullanışlıdır, çünkü ilk önce yalnızca DC katsayıları yüklenir, bu da kaba bir yapı oluşturmak için kullanılır. 8x8 “piksel” ile resim. Ardından, deseni iyileştirmek için yuvarlatılmış AC katsayıları. Sonra onlara kaba düzeltmeler, sonra daha doğru olanları. Peki, vb. Yüklemenin ilk aşamalarında doğruluk o kadar önemli olmadığı için katsayılar yuvarlanır, ancak yuvarlama, kodların uzunluğu üzerinde olumlu bir etkiye sahiptir, çünkü her aşama kendi Huffman tablosunu kullanır.

kayıpsız mod

Kayıpsız sıkıştırma. DCT değil. 4. noktanın üç komşu tarafından tahmini kullanılır. Tahmin hataları Huffman tarafından kodlanmıştır. Benim düşünceme göre, hiç olmamasından biraz daha sık kullanılıyor.

hiyerarşik mod

Görüntüden farklı çözünürlüklere sahip birkaç katman oluşturulur. İlk kaba katman her zamanki gibi kodlanır ve ardından yalnızca katmanlar arasındaki fark (görüntü iyileştirme) (Haar dalgacığı gibi görünür). Kodlama için DCT veya Kayıpsız kullanılır. Bana göre hiç olmadığı kadar az kullanılıyor.

aritmetik kodlama

Huffman algoritması, karakter ağırlığına göre en uygun kodları oluşturur, ancak bu yalnızca karakterlerin kodlara sabit bir yazışması için geçerlidir. Aritmetik, kodların olduğu gibi, kesirli sayıda bit ile kullanılmasına izin veren böyle katı bir bağlamaya sahip değildir. Huffman'a kıyasla dosya boyutunu ortalama %10 oranında küçülttüğü iddia ediliyor. Patent sorunları nedeniyle yaygın değil, herkes tarafından desteklenmiyor.

Umarım şimdi JPEG algoritmasını sezgisel olarak anlamışsınızdır. Okuduğunuz için teşekkürler!

UPD
vanwin, kullanılan yazılımı belirtmeyi teklif etti. Hepsinin mevcut ve ücretsiz olduğunu duyurmaktan memnuniyet duyuyorum:

• Python + NumPy + Matplotlib + PIL(Yastık). Ana araç. "Matlab ücretsiz alternatif" yayınında bulundu. Ben tavsiye ediyorum! Python'a aşina olmasanız bile, birkaç saat içinde hesaplama yapmayı ve güzel grafikler oluşturmayı öğreneceksiniz.
• jpeg gözetleme. jpeg dosyası hakkında ayrıntılı bilgi gösterir.
• yEd. Grafik düzenleyici.
• inkscape. İçinde Huffman algoritmasının bir örneği gibi illüstrasyonlar yaptım. Birkaç öğretici okudum ve harika oldu.
• Daum Denklem Editörü. Lateks ile pek arkadaş canlısı olmadığım için görsel bir formül düzenleyici arıyordum. Daum Equation, Chrome için bir eklenti, çok uygun buldum. Fare dürtmesine ek olarak Latex'i düzenleyebilirsiniz.
• hızlı taş. Tanıtılmasına gerek olduğunu düşünmüyorum.
• PicPick. SnagIt'e ücretsiz bir alternatif. Tepsiye oturur, ne dediklerini nerede söylerlerse ekran görüntüsü alır. Ayrıca cetvel, pipet, açı ölçer vb. gibi her türlü güzellikler.

Etiketler: Etiketler ekle

• öğretici

UPD. Tek aralıklı biçimlendirmeyi kaldırmak zorunda kaldım. Güzel bir gün, habraparser ön ve kod etiketlerinin içindeki biçimlendirmeyi algılamayı bıraktı. Tüm metinler bir karmaşaya dönüştü. Habr yönetimi bana yardım edemedi. Şimdi düzensiz, ama en azından okunabilir.

Hiç bir jpg dosyasının nasıl çalıştığını bilmek istediniz mi? Şimdi çözelim! Favori derleyicinizi ve altıgen düzenleyicinizi ısıtın, hadi şunu çözelim:

Özel olarak daha küçük bir çizim aldı. Bu, Google'ın tanıdık ama yoğun biçimde sıkıştırılmış favicon'udur:

Açıklamanın basitleştirilmiş olduğu ve sağlanan bilgilerin tam olmadığı konusunda sizi hemen uyarıyorum, ancak o zaman spesifikasyonu anlamak kolay olacaktır.

Kodlamanın nasıl gerçekleştiğini bilmeden bile dosyadan bir şeyler çıkartabiliriz.
- işaretleyiciyi başlat. Her zaman tüm jpg dosyalarının başındadır.
Bayt takip eder. . Bu, bir yorum bölümünün başlangıcını işaretleyen bir işaretçidir. Sonraki 2 bayt - bölüm uzunluğu (bu 2 bayt dahil). Yani sonraki iki - yorumun kendisi. Bunlar ":" ve ")" karakter kodlarıdır, yani. normal gülen Hex editörünün sağ tarafındaki ilk satırda görebilirsiniz.

biraz teori

Adım adım çok kısa:
Bu verilerin kodlanabileceği sırayı düşünelim. İlk başta Y kanalının tüm görüntü için kodlandığını, ardından Cb'nin ve ardından Cr'nin kodlandığını varsayalım. Herkes çevirmeli ağda resim yüklemeyi hatırlar. Bu şekilde kodlanmış olsalardı, ekranda görünmeden önce tüm görüntünün yüklenmesini beklememiz gerekirdi. Dosyanın sonunun kaybolması da rahatsız edici olacaktır. Muhtemelen başka iyi sebepler de vardır. Bu nedenle, kodlanmış veriler küçük parçalar halinde dönüşümlü olarak düzenlenir.

Her Y ij , Cb ij , Cr ij bloğunun Huffman kodlarıyla kodlanmış bir DCT katsayıları matrisi olduğunu hatırlatmama izin verin. Dosyada aşağıdaki sırayla bulunurlar: Y 00 Y 10 Y 01 Y 11 Cb 00 Cr 00 Y 20

Dosya okuma

Yorumu çıkardıktan sonra şunu anlamak kolay olacaktır:

• Dosya, önünde işaretleyiciler bulunan sektörlere bölünmüştür.
• Belirteçler, ilk bayt ile birlikte 2 bayt uzunluğundadır.
• Hemen hemen tüm sektörler, uzunluklarını işaretçiden sonraki 2 baytta saklar.

Kolaylık sağlamak için işaretleri vurgulayın:
FF D8 FF FE 00 04 3A 29 FF DB 00 43 00 A0 6E 78



FF FF FF FF FF FF FF FF FF FF FF FF FF FF DB 00
43 01 AA B4 B4 F0 D2 F0 FF FF FF FF FF FF FF FF
FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF
FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF
FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF
FF FF FF C0 00 11 08 00 10 00 10 03 01 22 00 02
11 01 03 11 01 FF C4 00 15 00 01 01 00 00 00 00
00 00 00 00 00 00 00 00 00 03 02 FF C4 00 1A
10 01 00 02 03 01 00 00 00 00 00 00 00 00 00 00
00 01 00 12 02 11 31 21 FF C4 00 15 01 01 01 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 01FF
C4 00 16 11 01 01 01 00 00 00 00 00 00 00 00 00
00 00 00 00 11 00 01 FF DA 00 0C 03 01 00 02 11
03 11 00 3F 00AE E7 61 F2 1B D5 22 85 5D 04 3C
82 C8 48 B1 DC BF FF D9

İşaretleyici: DQT - niceleme tablosu.

FF DB 00 43 00 A0 6E 78
8C 78 64 A0 8C 82 8C B4 AA A0 BE F0 FF FF F0 DC
DC F0 FF FF FF FF FF FF FF FF FF FF FF FF FF FF
FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF
FF FF FF FF FF FF FF FF FF FF FF FF FF

Bölüm başlığı her zaman 3 bayttır. Bizim durumumuzda, bu . Başlık şunlardan oluşur:
Uzunluk: 0x43 = 67 bayt
Tablodaki değerlerin uzunluğu: 0 (0 - 1 bayt, 1 - 2 bayt)
[_0] Tablo Kimliği: 0
Kalan 64 baytın 8x8 tabloyu doldurması gerekir.

Tablo değerlerinin doldurulduğu sıraya daha yakından bakın. Bu sıraya zikzak sıra denir:

İşaretleyici : SOF0 - Temel DCT

Bu işaretçiye SOF0 adı verilir; bu, görüntünün temel yöntemde kodlandığı anlamına gelir. Çok yaygın. Ancak internette, önce düşük çözünürlüklü bir görüntü, ardından normal bir resim yüklendiğinde, bildiğiniz aşamalı yöntem daha az popüler değildir. Bu, tam indirmeyi beklemeden orada gösterilenleri anlamanızı sağlar. Spesifikasyon birkaç tane daha tanımlıyor, bana öyle geliyor ki, çok yaygın yöntemler değil.

FF C0 00 11 08 00 10 00 10 03 01 22 00 02
11 01 03 11 01

Uzunluk: 17 bayt.
Hassasiyet: 8 bit Temel yöntemde her zaman 8. Anladığım kadarıyla kanal değerlerinin bit derinliği bu.
Resim Yüksekliği: 0x10 = 16
Desen Genişliği: 0x10 = 16
Bileşen sayısı: 3. Çoğu zaman Y, Cb, Cr'dir.

1. bileşen:
Kimlik: 1
Yatay incelme (H 1): 2
[_2] Dikey incelme (V 1): 2
Niceleme tablosu kimliği: 0

2. bileşen:
Kimlik: 2
Yatay incelme (H 2): 1
[_1] Dikey incelme (V 2): 1

3. bileşen:
Kimlik: 3
Yatay incelme (H 3): 1
[_1] Dikey incelme (V 3): 1
Niceleme tablosu tanımlayıcısı: 1

Şimdi bir görüntünün ne kadar inceltildiğini nasıl belirleyeceğinize bakın. H max \u003d 2 ve V max \u003d 2 buluyoruz. Kanal i, yatay olarak H max /H i kez ve dikey olarak V max /V i kez kırılacaktır.

İşaretleyici: DHT (Huffman şeması)

Bu bölüm, Huffman kodlaması ile elde edilen kodları ve değerleri saklar.

FF C4 00 15 00 01 01 00 00 00 00
00 00 00 00 00 00 00 00 00 00 03 02

uzunluk: 21 bayt.
sınıf: 0 (0 - DC katsayı tablosu, 1 - AC katsayı tablosu).
[_0] tablo kimliği: 0
Huffman kod uzunluğu: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Kod sayısı:
Kod sayısı, o uzunluktaki kod sayısı anlamına gelir. Bölümün, kodların kendilerini değil, yalnızca kodların uzunluklarını kaydettiğini unutmayın. Kodları kendimiz bulmalıyız. Yani 1 uzunluk ve 1 uzunluk 2 kodumuz var. Toplamda 2 kod var, bu tabloda başka kod yok.
Her kodun kendisiyle ilişkilendirilmiş bir değeri vardır ve bunlar dosyanın yanında listelenir. Değerler tek bayt olduğundan 2 bayt okuyoruz.
- 1. kodun değeri.
- 2. kodun değeri.

Huffman Kodlarından Bir Ağaç İnşa Etmek

DHT bölümünde aldığımız tablodan bir ikili ağaç oluşturmamız gerekiyor. Ve zaten bu ağaç tarafından her kodu tanıyacağız. Değerler tabloda listelendikleri sıraya göre eklenir. Algoritma basittir: Nerede olursak olalım, her zaman soldaki dala bir değer eklemeye çalışırız. Ve eğer meşgulse, o zaman sağa. Ve orada yer yoksa, o zaman yukarıdaki seviyeye döneriz ve oradan deneriz. Kodun uzunluğuna eşit bir seviyede durmanız gerekir. Sol dallar 0, sağ - 1 değerine karşılık gelir.
Yorum:
Her seferinde en baştan başlamaya gerek yok. Katma değer - yukarıdaki seviyeye geri dönün. Doğru şube var mı? Evet ise, tekrar yukarı çıkın. Değilse, doğru bir dal oluşturun ve oraya gidin. Ardından, oradan sonraki değeri eklemek için aramaya başlayın.

Bu örnekteki tüm tablolar için ağaçlar:


UPD (teşekkür ederim): İlk ağacın düğümleri (DC, id =0) 0x03 ve 0x02 değerlerine sahip olmalıdır.

Dairelerde - kodların değerleri, dairelerin altında - kodların kendileri (bunları yukarıdan her düğüme giderek aldığımızı açıklayacağım). Bu tür kodlarla (bunun ve diğer tabloların) şeklin içeriği kodlanmıştır.

İşaretleyici : SOS (Taramanın Başlangıcı)

Belirteçteki bayt "EVET! Son olarak, doğrudan kodlanmış görüntünün bölümünü ayrıştırmaya gittik! Ancak bölüm sembolik olarak SOS olarak adlandırılır.

  FF DA 00 0C 03 01 00 02 11
03 11 00 3F 00

Başlığın uzunluğu (bölümün tamamı değil): 12 bayt.
Tarama bileşenlerinin sayısı. Y, Cb, Cr için birer tane olmak üzere 3 tane var.

1. bileşen:
Görüntü bileşen numarası: 1 (Y)
DC katsayıları için Huffman tablo kimliği: 0
[_0] AC katsayıları için Huffman tablo kimliği: 0

2. bileşen:
Görüntü bileşen numarası: 2 (Cb)

[_1]

3. bileşen:
Görüntü bileşen numarası: 3 (Cr)
DC katsayıları için Huffman tablo kimliği: 1
[_1] AC katsayıları için Huffman tablo kimliği: 1

Bu bileşenler döngüsel olarak değişir.

Başlık kısmının bittiği yer burasıdır, buradan sona (işaretleyici) kodlanmış veriler.

0

DC katsayısını bulma.
1. Bit dizisini okuma (2 bayt ile karşılaşırsak, bu bir işaretleyici değil, sadece bir bayttır). Her bitten sonra, okunan bit'e bağlı olarak 0 veya 1 dalı boyunca Huffman ağacı (karşılık gelen tanımlayıcı ile) boyunca hareket ederiz. Son düğümdeysek dururuz.
10 1011101110011101100001111100100

2. Düğümün değerini alıyoruz. 0'a eşitse, katsayı 0'dır, tabloya yazın ve diğer katsayıları okumaya devam edin. Bizim durumumuzda - 02. Bu değer, katsayının bit cinsinden uzunluğudur. Yani, sonraki 2 biti okuduk, bu katsayı olacak.
10 10 11101110011101100001111100100

3. İkili gösterimde değerin ilk basamağı 1 ise, olduğu gibi bırakın: DC_coef = value. Aksi takdirde, şunu dönüştürün: DC_coef = değer-2 değer uzunluğu +1 . Katsayıyı zikzak - sol üst köşenin başında tabloya yazıyoruz.

AC katsayılarını bulma.
1. Madde 1'e benzer şekilde, DC katsayısını bulma. Sıralamayı okumaya devam ediyoruz:
10 10 1110 1110011101100001111100100

2. Düğümün değerini alıyoruz. 0'a eşitse, matrisin kalan değerlerinin sıfırlarla doldurulması gerektiği anlamına gelir. Ardından bir sonraki matris kodlanır. Bu noktaya kadar okuyup bu konuda kişisel olarak bana yazan ilk birkaç kişi karmada bir artı alacak. Bizim durumumuzda, düğümün değeri 0x31'dir.
İlk kemirme: 0x3 - matrise kaç tane sıfır eklememiz gerekiyor. Bunlar 3 sıfır katsayı.
İkinci kemirme: 0x1 - bit cinsinden katsayı uzunluğu. Sonraki kısmı okuyun.
10 10 1110 1 110011101100001111100100

3. DC katsayısını bulmanın 3. noktasına benzer.

Zaten anladığınız gibi, kodun sıfır değerine rastlayana veya matris dolana kadar AC katsayılarını okumanız gerekir.
Bizim durumumuzda, şunları alacağız:
10 10 1110 1 1100 11 101 10 0 0 0 1 11110 0 100
ve matris:

Değerlerin aynı zikzak deseninde doldurulduğunu fark ettiniz mi?
Bu sırayı kullanmanın nedeni basittir - v ve u değerleri ne kadar büyük olursa, ayrık kosinüs dönüşümündeki S vu katsayısı o kadar az önemlidir. Bu nedenle, yüksek sıkıştırma oranlarında, önemsiz katsayılar sıfıra ayarlanır, böylece dosya boyutu küçülür.

[-4 1 1 1 0 0 0 0] [ 5 -1 1 0 0 0 0 0]
[ 0 0 1 0 0 0 0 0] [-1 -2 -1 0 0 0 0 0]
[ 0 -1 0 0 0 0 0 0] [ 0 -1 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0] [-1 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0] [ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0] [ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0] [ 0 0 0 0 0 0 0 0]

[-4 2 2 1 0 0 0 0]
[-1 0 -1 0 0 0 0 0]
[-1 -1 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]

Oh, kodlanmış DC katsayılarının DC katsayılarının kendileri değil, önceki tablonun (aynı kanalın) katsayıları arasındaki farkları olduğunu söylemeyi unuttum! Matrisleri düzeltmeniz gerekiyor:
2. için DC: 2 + (-4) = -2
3. için DC: -2 + 5 = 3
4. için DC: 3 + (-4) = -1

[-2 1 1 1 0 0 0 0] [ 3 -1 1 0 0 0 0 0] [-1 2 2 1 0 0 0 0]
………

Şimdi sipariş ver. Bu kural dosyanın sonuna kadar geçerlidir.

… ve Cb ve Cr için matrise göre:

[-1 0 0 0 0 0 0 0]
[ 1 1 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]

Her biri yalnızca bir matris olduğundan, DC katsayılarına dokunulmadan bırakılabilir.

Bilgi işlem

niceleme

Matrisin niceleme aşamasından geçtiğini hatırlıyor musunuz? Matrisin elemanları, niceleme matrisinin elemanları ile terim terim çarpılmalıdır. Doğru olanı seçmek için kalır. İlk olarak, ilk bileşeni taradık, görüntü bileşeni = 1. Bu kimliğe sahip görüntü bileşeni, 0'lık bir niceleme matrisi kullanır (ikiden ilkine sahibiz). Yani çarpma işleminden sonra:

[ 0 120 280 0 0 0 0 0]
[ 0 -130 -160 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]

Benzer şekilde, 3 tane daha Y-kanalı matrisi elde ederiz ...

[-320 110 100 160 0 0 0 0] [ 480 -110 100 0 0 0 0 0]
[ 0 0 140 0 0 0 0 0] [-120 -240 -140 0 0 0 0 0]
[ 0 -130 0 0 0 0 0 0] [ 0 -130 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0] [-140 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0] [ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0] [ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0] [ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0] [ 0 0 0 0 0 0 0 0]

[-160 220 200 160 0 0 0 0]
[-120 0 -140 0 0 0 0 0]
[-140 -130 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]

… ve Cb ve Cr için matrise göre.

[-170 0 0 0 0 0 0 0] [ 0 0 0 0 0 0 0 0]
[ 180 210 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0] [ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0] [ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0] [ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0] [ 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0] [ 0 0 0 0 0 0 0 0]

Ters Ayrık Kosinüs Dönüşümü

Formül zor olmamalı*. S vu, sonuçtaki katsayı matrisimizdir. u - sütun, v - satır. s yx - doğrudan kanal değerleri.

* Genel olarak konuşursak, bu tamamen doğru değildir. 16x16'lık bir çizimi deşifre edip ekranda gösterebildiğimde 600x600'lük bir resim çektim (bu arada bu en sevdiğim albüm Mind.In.A.Box - Lost Alone'un kapağıydı). Hemen çalışmadı - çeşitli hatalar ortaya çıktı. Yakında doğru yüklenen resme hayran olabilirim. Tek hayal kırıklığı indirme hızıydı. 7 saniye sürdüğünü hala hatırlıyorum. Ancak bu şaşırtıcı değil, yukarıdaki formülü düşüncesizce kullanırsanız, o zaman bir pikselin bir kanalını hesaplamak için 128 kosinüs, 768 çarpma ve orada bazı eklemeler bulmanız gerekir. Bir düşünün - bir pikselin yalnızca bir kanalı için neredeyse bin zor işlem! Neyse ki, burada optimizasyon için yer var (birçok denemeden sonra, yükleme süresini 15ms'lik zamanlayıcı doğruluk sınırına indirdim ve bundan sonra resmi 25 kat daha büyük bir fotoğrafla değiştirdim. Belki bunu ayrı bir makalede yazarım. ).

Y kanalının sadece ilk matrisini hesaplamanın sonucunu yazacağım (değerler yuvarlanmıştır):


[ 87 72 50 36 37 55 79 95]
[-10 5 31 56 71 73 68 62]
[-87 -50 6 56 79 72 48 29]

Ve diğer 2:
Cb Cr
[ 60 52 38 20 0 -18 -32 -40] [ 19 27 41 60 80 99 113 120]
[ 48 41 29 13 -3 -19 -31 -37] [ 0 6 18 34 51 66 78 85]
[ 25 20 12 2 -9 -19 -27 -32] [-27 -22 -14 -4 7 17 25 30]
[ -4 -6 -9 -13 -17 -20 -23 -25] [-43 -41 -38 -34 -30 -27 -24 -22]
[ -37 -35 -33 -29 -25 -21 -18 -17] [-35 -36 -39 -43 -47 -51 -53 -55]
[ -67 -63 -55 -44 -33 -22 -14 -10] [ -5 -9 -17 -28 -39 -50 -58 -62]
[ -90 -84 -71 -56 -39 -23 -11 -4] [ 32 26 14 -1 -18 -34 -46 -53]
[-102 -95 -81 -62 -42 -23 -9 -1] [ 58 50 36 18 -2 -20 -34 -42]

1. Ah, hadi yemek yiyelim!
2. Evet hiç girmiyorum ne diyorsunuz.
3. YCbCr renk değerleri elde edildikten sonra geriye şu şekilde RGB'ye dönüştürmek kalır: YCbCrToRGB(Y ij , Cb ij , Cr ij) , Y ij , Cb ij , Cr ij - alınan matrislerimiz.
4. Kanalları incelttiğimiz için 4 Y matrisi ve her biri bir Cb ve Cr ve 4 Y pikselin her biri bir Cb ve Cr'ye karşılık gelir. Bu nedenle, şöyle hesaplayın: YCbCrToRGB(Y ij , Cb , Cr )

1 ve 4'ü seçerseniz, sizin için mutluyum. Ya doğru yaptın ya da yakında yemeğin tadını çıkaracaksın.

YCbCr'den RGB'ye dönüştürücü

R = Y + 1.402 * Kr
G = Y - 0.34414 * Cb - 0.71414 * Cr
B = Y + 1.772 * Cb
Her birine 128 eklemeyi unutmayın. Değerler aralığın dışına çıkıyorsa sınır değerleri atayın. Formül basittir, ancak aynı zamanda işlemci süresinin bir kısmını da tüketir.

Örneğimizin sol üst 8x8 karesi için R, G, B kanalları için sonuç tabloları:
255 248 194 148 169 215 255 255
255 238 172 115 130 178 255 255
255 208 127 59 64 112 208 255
255 223 143 74 77 120 211 255
237 192 133 83 85 118 184 222
177 161 146 132 145 162 201 217
56 73 101 126 144 147 147 141
0 17 76 126 153 146 127 108

231 185 117 72 67 113 171 217
229 175 95 39 28 76 139 189
254 192 100 31 15 63 131 185
255 207 115 46 28 71 134 185
255 241 175 125 112 145 193 230
226 210 187 173 172 189 209 225
149 166 191 216 229 232 225 220
72 110 166 216 238 231 206 186

255 255 249 203 178 224 255 255
255 255 226 170 140 187 224 255
255 255 192 123 91 138 184 238
255 255 208 139 103 146 188 239
255 255 202 152 128 161 194 232
255 244 215 200 188 205 210 227
108 125 148 172 182 184 172 167
31 69 122 172 191 183 153 134

Son

Genel olarak, bir JPEG uzmanı değilim, bu yüzden tüm soruları yanıtlayamıyorum. Tam kod çözücümü yazdığımda, çoğu zaman anlaşılmaz çeşitli sorunlarla uğraşmak zorunda kaldım. Ve görüntü yanlış görüntülendiğinde, nerede hata yaptığımı bilmiyordum. Belki bitleri yanlış yorumladı veya DCT'yi yanlış kullandı. Adım adım bir örneği gerçekten kaçırdım, bu yüzden bu makalenin kod çözücü yazarken yardımcı olacağını umuyorum. Sanırım temel yöntemin açıklamasını kapsıyor, ancak yine de bununla başa çıkamazsınız. İşte bana yardımcı olan bazı bağlantılar:

JPEG, en yeni ve oldukça güçlü algoritmalardan biridir. Uygulamada, tam renkli görüntüler için fiili standarttır. Algoritma, parlaklığın ve rengin nispeten düzgün bir şekilde değiştiği 8x8 alanlarla çalışır. Sonuç olarak, böyle bir bölgenin matrisi kosinüs cinsinden bir çift seriye ayrıştırıldığında (aşağıdaki formüller), yalnızca ilk katsayıların anlamlı olduğu ortaya çıkar. Böylece, görüntüdeki renk değişikliklerinin düzgünlüğü nedeniyle JPFG'de sıkıştırma gerçekleştirilir.

Algoritma, bir grup fotoğraf uzmanı tarafından, özellikle 24-bit JPEG görüntülerini sıkıştırmak için geliştirildi - Ortak Fotoğraf Uzman Grubu - ISO'nun bir bölümü - Uluslararası Standardizasyon Örgütü. Genel olarak, algoritma, bazı yeni katsayılar matrisi elde etmek için görüntü matrisine uygulanan ayrı bir kosinüs dönüşümüne (bundan sonra DCT olarak anılacaktır) dayanmaktadır. Orijinal görüntüyü elde etmek için ters bir dönüşüm uygulanır.

DCT, görüntüyü bazı frekansların genlikleri açısından ayrıştırır, böylece dönüşüm sırasında birçok katsayının sıfıra yakın veya eşit olduğu bir matris elde ederiz. Ayrıca, insanın renk algılama sistemi belirli frekansları tanımada zayıftır. Bu nedenle, görüntü kalitesinde gözle görülür bir kayıp olmadan bazı katsayıları daha kabaca tahmin etmek mümkündür.

Bunun için katsayıların nicelenmesi kullanılır. En basit durumda, bu sağa doğru aritmetik bir bit düzeyinde kaymadır. Bu dönüşüm bazı bilgileri kaybeder, ancak büyük sıkıştırma oranları elde edilebilir.

Algoritmanın çalışması.

24 bitlik bir görüntüyü sıkıştıralım.

Adım I

Görüntüyü, noktanın renginin kırmızı (Kırmızı), yeşil (Yeşil) ve mavi (Mavi) bileşenlerinden sorumlu bileşenlerle birlikte RGB renk uzayından YCrCb renk uzayına (bazen YUV olarak adlandırılır) çeviriyoruz.

İçinde Y parlaklık bileşenidir ve Cr, Cb renkten sorumlu bileşenlerdir (kromatik kırmızı ve kromatik mavi). İnsan gözünün renge karşı parlaklıktan daha az duyarlı olması nedeniyle, Cr ve Cb bileşenleri için dizileri büyük kayıplarla ve buna bağlı olarak büyük sıkıştırma oranlarıyla arşivlemek mümkün hale gelir. Benzer bir dönüşüm televizyonda uzun süredir kullanılmaktadır. Renkten sorumlu sinyallere daha dar bir frekans bandı atanır.

Basitleştirilmiş, RGB renk alanından YCrCb renk alanına çeviri aşağıdaki gibi gösterilebilir:

Ters dönüşüm, YUV vektörünü ters matrisle çarparak yapılır:

Adım 2

Orijinal görüntüyü 8x8 matrislere böldük. Her bileşen için ayrı ayrı - 8 bitten üç DCT çalışma matrisi oluşturuyoruz. Yüksek sıkıştırma oranlarında bu adım biraz daha zor olabilir. Görüntü Y bileşenine bölünür - ilk durumda olduğu gibi ve Cr ve Cb bileşenleri için matrisler çizgi ve sütun boyunca yazılır. Şunlar. orijinal 16x16 matrisinden yalnızca bir çalışan DCT matrisi elde edilir. Ayrıca, kolayca görülebileceği gibi, görüntünün renk bileşenleri hakkında faydalı bilgilerin 3/4'ünü kaybediyoruz ve hemen iki kat sıkıştırma elde ediyoruz. Bunu YCrCb uzayında çalışarak yapabiliriz. Elde edilen RGB görüntüsünde, uygulamanın gösterdiği gibi, bu çok fazla etkilenmiyor.

Aşama 3

Her çalışma matrisine DCT uygularız. Bu durumda, sol üst köşedeki katsayıların görüntünün düşük frekans bileşenine ve sağ altta yüksek frekans bileşenine karşılık geldiği bir matris elde ederiz.

Basitleştirilmiş bir biçimde, bu dönüşüm aşağıdaki gibi temsil edilebilir:

4. Adım

nicelleştirelim. Prensipte, bu basitçe çalışma matrisinin niceleme matrisi elemanına elemana bölünmesidir. Genel durumda her bileşen (Y, U ve V) için kendi niceleme matrisi (bundan böyle MC olarak anılacaktır) belirtilir.

Bu adımda sıkıştırma oranı kontrol edilir ve en büyük kayıp meydana gelir. MC'yi büyük katsayılarla ayarlayarak daha fazla sıfır ve sonuç olarak daha büyük bir sıkıştırma oranı elde edeceğimiz açıktır.

Algoritmanın spesifik etkileri de niceleme ile ilişkilidir. Katsayının büyük değerleri için gama , - düşük frekanslardaki kayıp o kadar büyük olabilir ki görüntü 8x8 karelere bölünür. Yüksek frekanslardaki kayıplar, keskin bir renk geçişi ile konturların etrafında bir tür "halo" oluştuğunda, "Gibbs etkisi" olarak adlandırılan şekilde kendini gösterebilir.

Adım 5

8x8 matrisini zikzak tarama kullanarak 64 elemanlı bir vektöre dönüştürme, ör. (0.0) indeksli elemanları seçin. (0.1). (1.0). (2.0)...

Böylece, vektörün başlangıcında, düşük frekanslara ve sonunda - yüksek frekanslara karşılık gelen matrisin katsayılarını alırız.

6. Adım

Grup kodlama algoritmasını kullanarak vektörü sararız. Bu durumda, "atla"nın atlanan sıfırların sayacı olduğu ve "sayı"nın bir sonraki hücreye yazılması gereken değer olduğu türde (atlama, sayı) çiftler elde ederiz.

Böylece vektör (0, 42) (0, 3) (3, -2) (4, 1) çiftlerine bölünecektir.

7. Adım

Huffman kodlayarak öğrenilen çiftleri sabit bir tablo ile daraltıyoruz.

Bu algoritmadaki görüntü yeniden oluşturma işlemi tamamen simetriktir. Yöntem, bazı görüntüleri ciddi kayıplar olmadan 10-15 kat sıkıştırmanıza izin verir.

JPEG algoritmasında kullanılan işlem ardışık düzeni.

Algoritmanın önemli olumlu yönleri şunlardır:

• 1) Sıkıştırma oranını ayarlayın
• 2) Çıktı renkli görüntüde nokta başına 24 bit olabilir.

Algoritmanın dezavantajları şunlardır:

• 1) Sıkıştırma oranı artırıldığında, görüntü ayrı karelere (8x8) bölünür. Bunun nedeni, kuantizasyon sırasında düşük frekanslarda büyük kayıpların meydana gelmesi ve orijinal verilerin geri yüklenmesinin imkansız hale gelmesidir.
• 2) Gibbs efekti belirir - keskin renk geçişlerinin sınırları boyunca haleler.

Nispeten yakın zamanda standartlaştırılmış JPEG - 1991'de. Ancak o zaman bile daha az kalite kaybıyla daha güçlü sıkıştıran algoritmalar vardı. Gerçek şu ki, standart geliştiricilerin eylemleri, o sırada var olan teknolojinin gücü ile sınırlıydı. Yani, kişisel bir bilgisayarda bile, algoritma ortalama bir görüntü üzerinde bir dakikadan daha az çalışmak zorundaydı ve donanım uygulaması nispeten basit ve ucuz olmalıdır. Algoritmanın simetrik olması gerekiyordu (açma süresi yaklaşık olarak arşivleme süresine eşittir).

İkinci gereklilik, dijital kameraların ortaya çıkmasını mümkün kıldı - PCMCIA arayüzlü 10-20 MB flash kartta 24 bit fotoğraflar çeken küçük bir video kamera boyutundaki cihazlar. Ardından kart dizüstü bilgisayardaki yuvaya takılır ve ilgili program görüntüleri okumanıza olanak tanır. Algoritma asimetrik olsaydı, cihaz "yeniden şarj olana" - görüntüyü sıkıştırana kadar uzun süre beklemek tatsız olurdu.

JPEG'in pek hoş olmayan bir başka özelliği de, ekrandaki yatay ve dikey şeritlerin genellikle kesinlikle görünmemesi ve yalnızca hareli desen biçiminde yazdırıldığında görünebilmesidir. Görüntünün yatay ve dikey şeritlerine eğik bir baskı deseni uygulandığında oluşur. Bu sürprizler nedeniyle JPEG, yüksek katsayılar ayarlayarak baskıda aktif kullanım için önerilmez. Ancak, arşivleme ve insan görüntülemeye yönelik görseller şu anda vazgeçilmezdir.

JPEG'in uzun süredir yaygın olarak kullanılması, belki de yalnızca 24 bit görüntülerle çalışması gerçeğiyle engellendi. Bu nedenle geleneksel bir monitörde kabul edilebilir kalitede bir resmin 256 renk paletinde görüntülenebilmesi için uygun algoritmaların kullanılması ve dolayısıyla belirli bir süre gerekliydi. Oyunlar gibi seçici bir kullanıcıyı hedefleyen uygulamalarda bu tür gecikmeler kabul edilemez. Ek olarak, örneğin 8 bit GIF biçiminde, 24 bit JPEG'e dönüştürülmüş ve ardından görüntülemek için GIF'e dönüştürülmüş resimleriniz varsa, her iki dönüştürmede de iki kez kalite kaybı olur. Ancak, arşiv boyutlarındaki kazanç genellikle o kadar büyüktür (3-20 kat!) ve kalitedeki kayıp o kadar küçüktür ki, görüntüleri JPEG formatında depolamak çok verimlidir.

Bu algoritmanın modifikasyonları hakkında birkaç söz söylenmelidir. JPEG bir ISO standardı olmasına rağmen, dosya formatı sabitlenmemiştir. Üreticiler bundan yararlanarak kendi uyumsuz formatlarını kullanırlar ve bu nedenle algoritmayı değiştirebilirler. Yani, ISO tarafından önerilen algoritmanın iç tabloları. kendileriyle değiştirilirler.Ayrıca, kayıp derecesi belirlenirken hafif bir karışıklık vardır. Örneğin, test ederken, "mükemmel" kalite, "%100" ve "10 puan"ın önemli ölçüde farklı resimler verdiği ortaya çıkıyor. Ayrıca, bu arada "%100" kalite kayıpsız sıkıştırma anlamına gelmez. Belirli uygulamalar için JPEG çeşitleri de vardır.

ISO Standardı JPEG, bilgisayar ağlarında görüntü alışverişinde giderek daha yaygın olarak nasıl kullanılmaya başlandı. JPEG algoritması Quick Time, PostScript Level 2, Tiff 6.0 formatlarında desteklenmektedir ve şu anda multimedya sistemlerinde önemli bir yer tutmaktadır.

JPFG algoritmasının özellikleri:

Sıkıştırma oranları: 2-200 (Kullanıcı tanımlı).

Görüntü sınıfı: Keskin renk geçişleri olmayan tam renkli 24 bit veya gri tonlamalı görüntüler (fotoğraflar).

Simetri: 1.

Özel özellikler: Bazı durumlarda, algoritma görüntüdeki keskin yatay ve dikey kenarların etrafında bir "halo" oluşturur (Gibbs etkisi). Ek olarak, yüksek derecede sıkıştırma ile görüntü 8x8 piksellik bloklara bölünür.