Algoritma, 1991 yılında, özellikle 24-bit ve gri tonlamalı görüntüleri sıkıştırmak için Joint Photographic Expert Group tarafından geliştirilmiştir. Bu algoritma iki seviyeli görüntüleri çok iyi sıkıştırmaz, ancak yakın piksellerin benzer renklere sahip olma eğiliminde olduğu sürekli tonlu görüntüleri çok iyi işler. Genellikle göz bu yöntemle 10 veya 20 kez sıkıştırıldığında herhangi bir fark görmez.

Algoritma, 8x8 piksel boyutunda, örtüşmeyen görüntü bloklarından oluşan bir matrise uygulanan DCT'ye dayanmaktadır. DCT, bu blokları belirli frekansların genliklerine göre ayrıştırır. Sonuç, pek çok katsayının sıfıra yakın olma eğiliminde olduğu ve kaba bir sayısal biçimde temsil edilebilen bir matristir, yani. restorasyon kalitesinde önemli bir kayıp olmadan nicelleştirilmiş bir biçimde.

Algoritmanın çalışmasını daha ayrıntılı olarak ele alalım. Tam renkli 24 bit bir görüntüyü sıkıştırdığınızı varsayalım. Bu durumda, aşağıdaki çalışma aşamalarını alıyoruz.

Aşama 1. Aşağıdaki ifadeyi kullanarak görüntüyü RGB uzayından YCbCr uzayına çeviriyoruz:

Ters dönüşümün, ters matrisi esasen bir YUV uzayı olan bir vektörle çarparak kolayca elde edilebileceğini hemen not edelim:

.

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, bir 8x8 blok 4:2:0 formatında YCbCr bileşenlerine ayrıştırılır, yani. Cb ve Cr bileşenleri satır ve sütunlardaki noktalardan alınır.

Aşama 3 8x8 piksel görüntü bloklarına DCT uygulanması. Resmi olarak, bir 8x8 blok için doğrudan DCT şu şekilde yazılabilir:

nerede . DCT, JPEG algoritmasının "kalbi" olduğundan, pratikte mümkün olduğu kadar çabuk hesaplanması arzu edilir. Hesapları hızlandırmak için basit bir yaklaşım, kosinüs fonksiyonlarını önceden hesaplamak ve hesaplamanın sonuçlarını tablo haline getirmektir. Ayrıca, farklı frekanslara sahip kosinüs fonksiyonlarının ortogonalliği göz önüne alındığında, yukarıdaki formül şu şekilde yazılabilir:

.

İşte bu uzaydaki blok sütunları temsil etmek için 8 boyutlu bir uzayı tanımlayan 8x8'lik bir matris. Matris, transpoze edilmiş bir matristir ve blok satırları dışında aynı şeyi yapar. Sonuç, matris formunda şu şekilde yazılan ayrılabilir bir dönüşümdür.

Burada, hesaplaması çarpma işlemlerini ve hemen hemen aynı sayıda eklemeyi gerektiren, yukarıdaki formülü kullanan doğrudan hesaplamalardan önemli ölçüde daha az olan DCT'nin sonucudur. Örneğin, 512x512 piksellik bir görüntüyü dönüştürmek için aritmetik işlemler gereklidir. 3 parlaklık bileşeni göz önüne alındığında, 12.582,912 aritmetik işlemin değerini elde ederiz. Çarpma ve toplama sayısı hızlı kullanılarak daha da azaltılabilir. Fourier dönüşümleri. Sonuç olarak, bir 8x8 bloğu dönüştürmek için 54 çarpma, 468 toplama ve bit kaydırma yapmanız gerekecek.

DCT'nin bir sonucu olarak, sol üst köşedeki katsayıların görüntünün düşük frekanslı bileşenine ve sağ altta yüksek frekanslı olana karşılık geldiği bir matris elde ederiz.

4. Adım niceleme. Bu adımda, bazı bilgiler atılır. Burada, matristeki her sayı "niceleme tablosundan" özel bir sayıya bölünür ve sonuç en yakın tam sayıya yuvarlanır:

.

Ayrıca, her Y, Cb ve Cr matrisi için kendi niceleme tablolarınızı ayarlayabilirsiniz. JPEG standardı, sıkıştırılmış verilerle birlikte kod çözücüye iletilmesi gerekecek olan kendi nicemleme tablolarının kullanılmasına bile izin verir, bu da artacaktır. toplam büyüklük dosya. Kullanıcının 64 katsayıyı bağımsız olarak seçmesinin zor olduğu açıktır, bu nedenle JPEG standardı niceleme matrisleri için iki yaklaşım kullanır. Birincisi, JPEG standardının önerilen iki niceleme tablosu içermesidir: biri luma için diğeri krominans için. Bu tablolar aşağıda gösterilmiştir. İkinci yaklaşım, kullanıcı tarafından belirtilen bir parametreye bağlı olarak bir nicemleme tablosunu sentezlemektir (anında hesaplamak). Tablonun kendisi formüle göre oluşturulmuştur.

Kuantizasyon adımında sıkıştırma oranı kontrol edilir ve en büyük kayıp meydana gelir. Büyük katsayılı nicemleme tabloları 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. Kuantizasyon adımının büyük değerlerinde kayıplar o kadar büyük olabilir ki görüntü düz 8x8 karelere bölünür. Buna karşılık, yüksek frekanslardaki kayıplar, keskin bir renk geçişi ile konturların etrafında dalgalı bir "nimbus" 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 çeviriyoruz (Şekil 2).

Pirinç. 2. Zigzag tarama

Sonuç olarak, vektörün başında kural olarak sıfır olmayan katsayılar yazılacak ve sonunda sıfır zincirleri oluşacaktır.

6. Adım Vektörü, çıktısında tür çiftlerini (atlama, sayı) aldığımız değiştirilmiş RLE algoritmasını kullanarak dönüştürüyoruz; burada "atlama", atlanan sıfırların sayacı ve "sayı", girilmesi gereken değerdir. sonraki hücre. Örneğin, 1118 3 0 0 0 -2 0 0 0 0 1 … vektörü (0, 1118) (0,3) (3,-2) (4.1) … .

Dönüştürülen bileşenin ilk sayısının esasen 8x8 bloğunun ortalama parlaklığına eşit olduğuna ve DC katsayısı olarak adlandırıldığına dikkat edilmelidir. Benzer şekilde tüm görüntü blokları için. Bu durum, DC katsayılarının, mutlak değerleri saklanmazsa, ancak geçerli bloğun DC katsayısı ile önceki bloğun DC katsayısı arasındaki fark şeklinde göreceli olanları ve ilk bloğun etkin bir şekilde sıkıştırılabileceğini göstermektedir. katsayısı olduğu gibi saklanır. Bu durumda DC katsayılarının sıralaması, örneğin aşağıdaki gibi yapılabilir (Şekil 3). AC katsayıları olarak adlandırılan kalan katsayılar değişmeden kalır.

7. Adım Elde edilen çiftleri sabit bir tablo ile tek tip olmayan Huffman kodları kullanarak daraltırız. Ayrıca DC ve AC katsayıları için farklı kodlar kullanılır, yani. farklı tablolar Huffman kodları ile.

Pirinç. 3. DC katsayılarını sıralama şeması

Pirinç. 4. JPEG algoritmasının blok şeması

Bu algoritmadaki görüntü yeniden oluşturma işlemi tamamen simetriktir. Yöntem, gözle görülür görsel kayıp olmadan görüntüleri 10-15 kat sıkıştırmanıza olanak tanır.

Bu standardı geliştirirken, bu algoritmanın görüntüleri oldukça hızlı bir şekilde sıkıştırması gerektiği gerçeği bize rehberlik etti - ortalama bir görüntüde bir dakikadan fazla değil. Bu 1991'de! Ve donanım uygulaması nispeten basit ve ucuz olmalıdır. Bu durumda algoritmanın çalışma süresi açısından simetrik olması gerekiyordu. İkinci şartın yerine getirilmesi, 24 bit görüntü alan dijital kameraların ortaya çıkmasını mümkün kıldı. Algoritma asimetrik olsaydı, cihaz "yeniden şarj olana" - görüntüyü sıkıştırana kadar uzun süre beklemek tatsız olurdu.

JPEG algoritması bir ISO standardı olmasına rağmen dosya formatı sabitlenmemiştir. Bunu kullanarak üreticiler kendi uyumsuz formatlarını oluştururlar ve bu nedenle algoritmayı değiştirebilirler. Böylece, ISO tarafından önerilen algoritmanın iç tabloları, kendileri tarafından değiştirilir. Belirli uygulamalar için JPEG çeşitleri de vardır.

Kayıplı arşivleme algoritmalarıyla ilgili sorunlar

Görüntüleri arşivlemek için kullanılan ilk algoritmalar geleneksel algoritmalardı. Yedekleme sistemlerinde, dağıtım oluştururken vb. kullanılanlar ve kullanılanlar. Bu algoritmalar bilgileri değişmeden arşivledi. Bununla birlikte, son zamanlarda ana eğilim, yeni görüntü sınıflarının kullanılması olmuştur. Eski algoritmalar artık arşivleme gereksinimlerini karşılamıyor. “Bir bakışta” bariz fazlalıkları olmasına rağmen, birçok görüntü pratik olarak sıkıştırılmadı. Bu, yeni bir tür algoritma oluşturulmasına yol açtı - bilgi kaybıyla sıkıştırma. Kural olarak, arşivleme oranı ve sonuç olarak bunlardaki kalite kaybı derecesi ayarlanabilir. Bu durumda, görüntülerin boyutu ve kalitesi arasında bir uzlaşmaya varılır.

Biri ciddi sorunlar bilgisayar grafikleri, görüntü kalitesi kaybını değerlendirmek için yeterli bir kriterin henüz bulunamaması gerçeğinde yatmaktadır. Ve sürekli olarak kaybolur - sayısallaştırma sırasında, sınırlı bir renk paletine dönüştürürken, baskı için başka bir renk temsil sistemine dönüştürürken ve özellikle bizim için önemli olan, kayıplarla arşivleme yaparken. Basit bir kritere örnek verebiliriz: piksel değerlerinin standart sapması (L 2 ölçü veya ortalama kare - RMS):

Buna göre, parlaklık yalnızca %5 oranında azaltıldığında görüntü büyük ölçüde zarar görecektir (göz bunu fark etmeyecektir - farklı monitörler için parlaklık ayarı çok daha fazla değişir). Aynı zamanda, "kar" içeren görüntüler - tek tek noktaların, soluk çizgilerin veya "harelerin" renginde keskin bir değişiklik "neredeyse değişmemiş" olarak kabul edilecektir (Nedenini açıklayın?). Diğer kriterlerin de dezavantajları vardır.

Örneğin, maksimum sapmayı düşünün:

Bu önlem, tahmin edebileceğiniz gibi, tek tek piksellerin atılmasına karşı son derece hassastır. Şunlar. görüntünün tamamında, yalnızca bir pikselin değeri önemli ölçüde değişebilir (ki bu gözle neredeyse algılanamaz), ancak bu ölçüye göre görüntü ciddi şekilde bozulacaktır.

Şu anda pratikte kullanılan ölçü, sinyal-gürültü oranının ölçüsü (tepe-tepe sinyal-gürültü oranı - PSNR) olarak adlandırılır.

Bu ölçü aslında standart sapmaya benzer, ancak ölçeğin logaritmik ölçeği nedeniyle kullanımı biraz daha uygundur. Standart sapma ile aynı dezavantajlara sahiptir.

Görüntü kalitesindeki kayıp en iyi şekilde gözlerimiz tarafından değerlendirilir. Arşivleme, orijinal ve sıkıştırılmamış görüntüleri gözle ayırt etmenin imkansız olduğu mükemmel olarak kabul edilir. İyi - hangi resimlerin arşivlendiğini anlayabildiğinizde, yalnızca iki bitişik resmi karşılaştırabilirsiniz. Sıkıştırma oranındaki bir artışla, kural olarak, bu algoritmanın karakteristik yan etkileri fark edilir hale gelir. Uygulamada, mükemmel kalite tutma ile bile, görüntüde düzenli olarak belirli değişiklikler yapılabilir. Bu nedenle, daha sonra yüksek kalitede basılacak veya görüntü tanıma programları tarafından işlenecek görüntülerin sıkıştırılması için kayıplı arşivleme algoritmaları önerilmez. Bu tür görüntülerde hoş olmayan etkiler, daha önce de söylediğimiz gibi, basit bir görüntü ölçekleme ile bile ortaya çıkabilir. JPEG algoritması

JPEG, en yeni ve oldukça güçlü algoritmalardan biridir. Tam renkli görüntüler için pratikte 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 matrisini kosinüs cinsinden bir çift seriye genişletirken (aşağıdaki formüllere bakın), yalnızca ilk katsayıların anlamlı olduğu ortaya çıkıyor. Böylece, görüntüdeki renk değişikliklerinin düzgünlüğü nedeniyle JPEG'de sıkıştırma gerçekleştirilir.

Algoritma, bir grup fotoğraf uzmanı tarafından özellikle 24 bit görüntüleri sıkıştırmak için geliştirildi. JPEG - Ortak Fotoğraf Uzman Grubu - ISO - Uluslararası Standardizasyon Örgütü içindeki bir bölüm. Algoritmanın adı ["jei" peg] olarak okunur. 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ü belirli frekansların genliklerine ayrıştırır. Böylece, dönüştürürken, birçok katsayının sıfıra yakın veya eşit olduğu bir matris elde ederiz. Ek olarak, insan görüşünün kusurlu olması nedeniyle, görüntü kalitesinde gözle görülür bir kayıp olmadan 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.

Algoritma nasıl çalışır?

Öyleyse, algoritmayı daha ayrıntılı olarak ele alalım. Diyelim ki 24 bitlik bir görüntüyü sıkıştırıyoruz.

Aşama 1.

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 yüksek kayıplarla ve buna bağlı olarak yüksek 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 geçiş matrisi kullanılarak temsil edilebilir:

Ters dönüşüm, YUV vektörünün ters matrisle çarpılmasıyla 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. Bu durumda, görülmesi kolay olduğu gibi, görüntünün renk bileşenleri hakkında faydalı bilgilerin 3 / 4'ünü kaybeder ve hemen iki kat sıkıştırma elde ederiz. Bunu YCrCb uzayında çalışarak yapabiliriz. Uygulamanın gösterdiği gibi, bu, elde edilen RGB görüntüsünü çok fazla etkilemez.

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

Kuantizasyon yapıyoruz. Prensipte, bu basitçe çalışma matrisinin niceleme matrisi elemanına elemana bölünmesidir. Her bileşen için (Y, U ve V), genel durumda, kendi niceleme matrisi q (bundan sonra 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. Gama katsayısının yüksek değerlerinde, düşük frekanslardaki kayıplar 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 matrisi “zikzak” tarama kullanarak 64 elemanlı bir vektöre çeviriyoruz, yani. (0,0), (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, "atlama"nın atlanan sıfırların sayacı olduğu ve "sayı"nın bir sonraki hücreye konulması gereken değer olduğu türde (atlama, sayı) çiftler elde ederiz. Böylece, 42 3 0 0 0 -2 0 0 0 0 1 ... vektörü (0.42) (0.3) (3,-2) (4.1) ... çiftleri halinde katlanır.

7. Adım

Ortaya çıkan çiftleri sabit bir tablo ile Huffman kodlaması ile katlı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ı ayarlar.
2. izin günü renkli görüntü nokta başına 24 bit olabilir.

Algoritmanın dezavantajları şunlardır:

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

Daha önce de belirtildiği gibi, JPEG nispeten yakın zamanda standart hale getirildi - 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 zamanı yaklaşık olarak arşivleme zamanına eşittir).

İkinci gereklilik, bu tür oyuncakların ortaya çıkmasını mümkün kıldı: dijital kameralar- PCMCIA arayüzlü 10-20 MB flash kartta 24 bit fotoğraf çeken, küçük bir video kamera boyutunda cihazlar. Daha sonra bu kart dizüstü bilgisayarınızdaki yuvaya takılır ve ilgili program görüntüleri okumanızı sağlar. Algoritma asimetrik olsaydı, cihaz “yeniden şarj olana” - görüntüyü sıkıştırana kadar uzun süre beklemenin hoş olmayacağı doğru değil mi?

JPEG'in pek hoş olmayan bir başka özelliği de, ekrandaki yatay ve dikey şeritlerin genellikle kesinlikle görünmez olması ve yalnızca hareli desen şeklinde 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, insan görüntülemeye yönelik görüntüleri arşivlerken, şu anda vazgeçilmezdir.

JPEG'in uzun bir süre yaygın kullanımı, 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üreye ihtiyaç duyulmuştur. 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 çok 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. Bunu kullanarak üreticiler kendi uyumsuz formatlarını oluştururlar ve bu nedenle algoritmayı değiştirebilirler. Böylece, ISO tarafından önerilen algoritmanın iç tabloları, kendileri tarafından değiştirilir. Ek olarak, 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. Aynı zamanda “%100” kalite kayıpsız sıkıştırma anlamına gelmez. Belirli uygulamalar için JPEG çeşitleri de vardır.

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

Algoritma Özellikleri JPEG:

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

Ö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.

Fraktal Algoritma

Yöntem fikri

Fraktal arşivleme, görüntüyü daha kompakt bir biçimde - yinelenen işlevler sisteminin (Yinelenen İşlev Sistemi - bundan sonra IFS olarak anılacaktır) katsayılarını kullanarak temsil etmemize dayanır. Arşivleme sürecinin kendisini düşünmeden önce, IFS'nin bir görüntüyü nasıl oluşturduğuna bakalım, yani. dekompresyon süreci.

Kesin olarak konuşursak, IFS, bizim durumumuzda bir görüntüyü diğerine dönüştüren bir dizi üç boyutlu afin dönüşümdür. Üç boyutlu uzaydaki noktalar (x_koordinatı, y_koordinatı, parlaklık) dönüşüme tabi tutulur.

Bu süreç en açık şekilde Barnsley tarafından “Fractal Image Compression” kitabında gösterilmiştir. Orada, orijinal görüntünün görüntülendiği bir ekrandan ve görüntüyü başka bir ekrana yansıtan bir mercek sisteminden oluşan bir Fotokopi makinesi konsepti tanıtıldı:

• Lensler görüntünün bir bölümünü yansıtabilir serbest çalışma yeni görüntüdeki başka herhangi bir yere.
• alanlar, hangisinde görüntüler yansıtılır kesişme.
• lens olabilir parlaklığı değiştir ve kontrastı azalt.
• lens olabilir çevir ve döndür görüntü parçanız.
• Lens zorunlu derecelendirmek(azalt) görüntü parçanızı.

Lensleri yerleştirerek ve özelliklerini değiştirerek ortaya çıkan görüntüyü kontrol edebiliriz. Makinenin çalışmasının bir yinelemesi, projeksiyon yardımıyla orijinal görüntüden yenisinin oluşturulması ve ardından yenisinin ilk görüntü olarak alınması gerçeğinden oluşur. Yinelemeler sürecinde değişmeyi bırakacak bir görüntü alacağımız iddia ediliyor. Yalnızca lenslerin konumuna ve özelliklerine bağlı olacaktır ve orijinal görüntüye bağlı olmayacaktır. Bu görüntünün adı " sabit nokta" veya cazibe merkezi bu IFS. Karşılık gelen teori, her IFS için tam olarak bir sabit nokta olduğunu garanti eder.

Mercek eşleme daraltıcı olduğundan, her mercek açıkça tanımlar kendine benzer imajımızdaki alanlar. Kendi kendine benzerlik sayesinde, herhangi bir büyütmede karmaşık bir görüntü yapısı elde ederiz. Bu nedenle, yinelenen işlevler sisteminin tanımladığı sezgisel olarak açıktır. fraktal(kesinlikle - kendine benzer matematiksel nesne).

En ünlüsü, IFS'nin yardımıyla elde edilen iki görüntüdür: “Sierpinski üçgeni” ve “Barnsley eğreltiotu”. "Sierpinski üçgeni" üç tarafından ve "Barnsley eğreltiotu" dört afin dönüşümle (veya bizim terminolojimizde "mercekler") verilir. Her dönüşüm sadece birkaç bayta kodlanırken, onların yardımıyla oluşturulan görüntü birkaç megabayt alabilir.

Alıştırma: Görüntüde, tüm görüntüyü kaplayacak şekilde birleştirilecek ve her biri görüntünün tamamına benzer olacak 4 alanı belirtin (eğrelti otu sapını unutmayın).

Yukarıdan, arşivleyicinin nasıl çalıştığı ve neden bu kadar zaman aldığı açıkça ortaya çıkıyor. Aslında fraktal sıkıştırma, bir görüntüde kendine benzer alanların aranması ve bunlar için afin dönüşümlerin parametrelerinin belirlenmesidir.

=>
En kötü durumda, bir optimizasyon algoritması uygulanmazsa, farklı boyutlardaki tüm olası görüntü parçalarını numaralandırmak ve karşılaştırmak gerekecektir. Küçük görüntüler için bile, ayrılığı hesaba katarak, sıralanacak astronomik sayıda seçenek elde edeceğiz. Ayrıca, örneğin yalnızca belirli sayıda ölçekleme yoluyla dönüşüm sınıflarının keskin bir şekilde daraltılması bile, zaman açısından gözle görülür bir kazanç sağlamaz. Ayrıca, görüntünün kalitesi kaybolur. Fraktal sıkıştırma alanındaki araştırmaların büyük çoğunluğu artık yüksek kaliteli bir görüntü elde etmek için gereken arşivleme süresini azaltmayı hedefliyor.

Tanım.

nerede a,b,c,d,e,f gerçek sayılar ve denir iki boyutlu afin dönüşüm.

Tanım. Dönüşüm, formda gösterilebilir

a, b, c, d, e, f, p, q, r, s, t, u reel sayılardır ve üç boyutlu afin dönüşüm olarak adlandırılır.

Tanım. X uzayında bir dönüşüm olsun. sabit nokta(çekici) dönüşümün.

Tanım. Bir metrik uzayda (X, d) bir dönüşümün, eğer bir sayı varsa, daraltıcı olduğu söylenir. s: öyle ki

Yorum: Biçimsel olarak, fraktal sıkıştırma için herhangi bir daralma eşlemesi kullanabiliriz, ancak gerçekte katsayılar üzerinde oldukça güçlü kısıtlamalarla birlikte yalnızca üç boyutlu afin dönüşümler kullanılır.

Teorem. (Sıkıştırma dönüşümü hakkında)

Tam bir metrik uzayda olsun (X, d). O zaman bu dönüşümün tam olarak bir sabit noktası vardır ve herhangi bir nokta için dizi için yakınsar.

Bu teoremin daha genel bir formülasyonu yakınsamayı garanti eder.

Tanım. resim birim karede tanımlanan ve 0'dan 1'e kadar değerler alan bir S fonksiyonudur veya

Üç boyutlu afin dönüşüm şu şekilde yazılabilir:

ve Kartezyen kare x'in kompakt bir alt kümesinde tanımlanır. Sonra yüzeyin bir kısmını çevirecek S bir vardiya ile bulunan alana (e,f) ve matris tarafından verilen döndürme

Ancak değeri yorumlarsak S karşılık gelen noktaların parlaklığı olarak azalacaktır. p kez (dönüşüm büzülmeli olmalıdır) ve bir vardiyaya dönüşecek q.

Tanım. sınırlı nüfus W etki alanlarında tanımlanan üç boyutlu afin dönüşümleri daraltmak ve , denir yinelenen işlevler sistemi ( IFS).

Yinelenen işlevler sistemi, benzersiz bir şekilde sabit bir noktayla - bir görüntüyle - ilişkilendirilir. Bu nedenle, sıkıştırma işlemi sistemin katsayılarının aranmasından oluşur ve açma işlemi, elde edilen görüntü sabitlenene kadar (sabit nokta IFS) sistemin yinelenmesinden oluşur. Pratikte 7-16 yineleme yeterlidir. Bölgeler olarak anılacaktır sıralama, ve alanlar alan adı.

Algoritma oluşturma

Yukarıdan da anlaşılacağı gibi, fraktal algoritma tarafından sıkıştırmada ana görev, karşılık gelen afin dönüşümleri bulmaktır. En genel durumda, herhangi bir boyut ve şekildeki görüntü alanlarını çevirebiliriz, ancak bu durumda, şu anda bir süper bilgisayarda bile işlenemeyen farklı parçaların ayıklanması için astronomik sayıda seçenek elde ederiz.

AT algoritmanın eğitim versiyonu , aşağıda belirtilen alan üzerinde aşağıdaki kısıtlamalar yapılmıştır:

1. Tüm bölgeler kenarları görüntünün kenarlarına paralel olan karelerdir. Bu sınırlama oldukça şiddetlidir. Aslında, tüm geometrik şekil çeşitlerine sadece karelerle yaklaşacağız.
2. Bir alan alanını bir sıralama alanına dönüştürürken, boyut küçülür tam olarak iki kez. Bu, hem kompresörü hem de dekompresörü büyük ölçüde basitleştirir. küçük alanları ölçekleme görevi önemsiz değildir.
3. Tüm alan blokları karelerdir ve sabit boyut. Görüntü, tek tip bir ızgara ile bir dizi etki alanı bloğuna bölünür.
4. Domain alanları alınır hem X hem de Y'de "bir noktadan", bu da aramayı hemen 4 kat azaltır.
5. Bir etki alanı etki alanını birinci sıraya dönüştürürken, küp döndürülebilir sadece 0 0 , 90 0 , 180 0 veya 270 0'da. Aynalamaya da izin verilir. Toplam olası dönüşüm sayısı (boş sayılır) 8'dir.
6. Dikey olarak ölçekleme (sıkıştırma) (parlaklık) gerçekleştirilir sabit sayıda kez- 0.75'te.

Bu kısıtlamalar şunları sağlar:

1. Yeterince büyük görüntülerde bile nispeten az sayıda işlem gerektiren bir algoritma oluşturun.
2. Bir dosyaya yazılacak verileri temsil etmek çok kompakttır. IFS'deki her afin dönüşüm için ihtiyacımız var:

• etki alanı bloğunun ofsetini ayarlamak için iki sayı. Giriş görüntülerini 512x512 ile sınırlarsak, sayı başına 8 bit yeterli olacaktır.
• Bir etki alanı bloğunu bir sıra bloğuna dönüştürürken simetri dönüşümünü belirtmek için üç bit.
• Çeviri sırasında parlaklık kaymasını ayarlamak için 7-9 bit.

Blok boyutu bilgileri dosya başlığında saklanabilir. Böylece, afin dönüşümü başına 4 bayttan daha az harcadık. Blok boyutunun ne olduğuna bağlı olarak, görüntüde kaç blok olacağını hesaplayabilirsiniz. Böylece, sıkıştırma derecesinin bir tahminini alabiliriz.

Örneğin, blok boyutu 8 piksel olan 512x512 piksellik 256 renkli bir gri tonlamalı dosya için afin dönüşümler 4096 (512/8x512/8) olacaktır. Her biri 3.5 bayt gerektirir. Bu nedenle, orijinal dosya 262144 (512x512) bayt (başlık hariç) işgal ederse, katsayılı dosya 14336 bayt alır. Arşivleme katsayısı - 18 kez. Aynı zamanda, katsayıları olan bir dosyanın da fazlalık olabileceğini ve LZW gibi kayıpsız bir arşivleme yöntemi kullanılarak arşivlenebileceğini hesaba katmıyoruz.

Önerilen kısıtlamaların olumsuz yönleri:

1. Tüm alanlar kare olduğundan, şekil olarak karelerden uzak nesnelerin (gerçek görüntülerde oldukça yaygın olan) benzerliğini kullanmak imkansızdır.
2. Benzer şekilde, benzerlik katsayısı 2'den çok farklı olan görüntüdeki nesnelerin benzerliğini kullanamayacağız.
3. Algoritma, aralarındaki açı 90 0'ın katı olmayan görüntüdeki nesnelerin benzerliğini kullanamaz.

Bu ücret sıkıştırma hızı ve katsayıları bir dosyaya paketleme kolaylığı için.

Paketleme algoritmasının kendisi, tüm etki alanı bloklarının numaralandırılmasına ve karşılık gelen her bir sıra bloğunun seçimine indirgenir. Aşağıda bu algoritmanın bir diyagramı bulunmaktadır.

for (tüm aralık blokları) (
min_mesafe = MaksimumMesafe;
R ij= image->CopyBlock(i,j);
for (tüm etki alanı blokları) ( // Döndürmeler ve neg.
akım=Mevcut koordinatlar dönüşümler;
D=image->CopyBlock(mevcut);
akım_mesafe = R ij.L2mesafe(D);
if(geçerli_mesafe< min_distance) {
// En iyi oranlar daha kötüyse:
min_mesafe = akım_mesafe;
en iyi=mevcut;
}
) //Sonraki aralık
Save_Coectives_to_file(en iyi);
) //Sonraki alan

Yukarıdaki algoritmadan da görülebileceği gibi, her bir rank bloğu için onu tüm olası alan bloklarıyla (simetri dönüşümü geçirmiş olanlar dahil) kontrol ederiz, en küçük L ölçüsüne sahip varyantı buluruz. 2 (en az standart sapma) ve bu dönüşümün katsayılarını bir dosyaya kaydedin. Katsayılar (1) bulunan bloğun koordinatları, (2) simetri dönüşümünü (dönüş, bloğun yansıması) karakterize eden 0 ila 7 arasında bir sayı ve (3) bu blok çifti için parlaklıktaki kaymadır. Parlaklık kayması şu şekilde hesaplanır:

,

nerede r ij- sıralama bloğunun piksel değerleri ( R), a d ij- alan bloğunun piksel değerleri ( D). Bu durumda, önlem şu şekilde kabul edilir:

.

L'nin karekökünü hesaplamıyoruz 2 ölçün ve bölmeyin n, dönüştürme verileri monoton olduğundan ve ekstremumu bulmamıza engel olmayacağından, ancak her blok için iki işlem daha az gerçekleştirebileceğiz.

Gri tonlamalı 256 renk 512x512 piksel ve blok boyutu 8 piksel olan bir görüntüyü sıkıştırmak için ihtiyacımız olan işlem sayısını hesaplayalım:

Böylece sıkıştırma algoritmasının işlem sayısını oldukça hesaplanabilir (birkaç saat içinde de olsa) değerlere indirmeyi başardık.

Görüntü sıkıştırma algoritmasının şeması

Fraktal sıkıştırma algoritmasının dekompresyonu son derece basittir. Katsayıları sıkıştırma aşamasında elde edilen üç boyutlu afin dönüşümlerinin birkaç yinelemesini gerçekleştirmek gerekir.

Kesinlikle herhangi bir görüntü (örneğin, kesinlikle siyah) ilk görüntü olarak alınabilir, çünkü karşılık gelen matematiksel aparat bize IFS yinelemeleri sırasında elde edilen görüntü dizisinin hareketsiz bir görüntüye (orijinal olana yakın) yakınsamasını garanti eder. Bunun için genellikle 16 iterasyon yeterlidir.

Dosyadan tüm blokların katsayılarını okuyun;
İstenilen boyutta siyah bir görüntü oluşturun;
Kadar(görüntü sabit olmayacak)(
İçin(her aralık (R))(
D=image->CopyBlock(D_coord_for_R);
için(her piksel( ben, j) blokta(
R ij = 0.75 D ben + Ö R;
) //Sonraki piksel
) //Sonraki blok
)//Sonuna kadar

Blokların katsayılarını kaydettiğimizden beri R ij(belirttiğimiz gibi, bizim özel durumumuzda aynı büyüklükteki karelerdir) art arda, bir afin dönüşüm kullanarak görüntüyü art arda bölme ızgarasının kareleriyle doldurduğumuz ortaya çıktı.

Hesaplanabileceği gibi, geri yükleme sırasında gri tonlamalı görüntünün piksel başına işlem sayısı alışılmadık derecede küçüktür (N işlem “+”, 1 işlem “*”, burada N yineleme sayısıdır, yani 7-16). Bu nedenle, fraktal algoritma için görüntü açma, örneğin 64 "+" ve 64 "? ” (RLE adımları ve Huffman kodlaması hariç!). Aynı zamanda, fraktal algoritma için çarpma, her blok için bir rasyonel sayı ile gerçekleşir. Bu, ilk olarak, kayan nokta aritmetiğinden önemli ölçüde daha hızlı olan tamsayılı rasyonel aritmetiği kullanabileceğimiz anlamına gelir. İkinci olarak, bir vektörü bir sayı ile çarpmak, genellikle işlemci mimarisinde (SGI işlemciler, Intel MMX...) yerleşik olarak bulunan, JPEG durumunda gerekli olan iki vektörün skaler ürününden daha basit ve daha hızlı bir işlemdir. Tam renkli bir görüntü için durum niteliksel olarak değişmez, çünkü her iki algoritma da dönüştürmeyi başka bir renk uzayına kullanır.

Kayıpların tahmini ve düzenleme yolları

saat özet Algoritmanın basitleştirilmiş versiyonu birçok önemli konuyu gözden kaçırdı. Örneğin, algoritma görüntünün herhangi bir parçası için benzer bir görüntü bulamazsa ne olur? Yeterince açık olan çözüm, bu parçayı daha küçük parçalara bölmek ve onları aramaya çalışmaktır. Aynı zamanda, bu prosedürün süresiz olarak tekrarlanamayacağı açıktır, aksi takdirde gerekli dönüşümlerin sayısı o kadar çok olur ki, algoritma bir sıkıştırma algoritması olmaktan çıkar. Bu nedenle, görüntünün bir kısmında kaybolmaya izin veriyoruz.

Fraktal sıkıştırma algoritması ve diğer kayıplı sıkıştırma algoritmaları için, sıkıştırma derecesini ve kayıp derecesini kontrol etmenin mümkün olacağı mekanizmalar çok önemlidir. Bugüne kadar, yeterince büyük bir bu tür yöntemler seti geliştirilmiştir. İlk olarak, sıkıştırma oranının sabit bir değerden düşük olmamasını sağlayarak afin dönüşümlerin sayısını sınırlamak mümkündür. İkinci olarak, işlenmekte olan parça ile en iyi yaklaşımı arasındaki farkın belirli bir eşik değerinin üzerinde olduğu bir durumda, bu parçanın zorunlu olarak bölünmesi gerekebilir (bunun için mutlaka birkaç “mercek” oluşturulur). Üçüncüsü, örneğin dört noktadan daha küçük parçaların parçalanmasını yasaklamak mümkündür. Bu koşulların eşik değerlerini ve önceliğini değiştirerek, bit-bit eşleştirmeden herhangi bir sıkıştırma derecesine kadar olan aralıkta görüntü sıkıştırma oranı üzerinde çok esnek bir kontrole sahip olacağız. Bu esnekliğin en yakın "rakip" olan JPEG algoritmasından çok daha yüksek olacağını unutmayın.

Fraktal algoritmanın özellikleri :

Sıkıştırma Oranları: 2-2000 (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). Daha büyük öneme sahip alanların (algı için) daha zıt ve keskin olması ve daha az öneme sahip alanların - düşük kontrastlı ve bulanık olması arzu edilir.

Simetri: 100-100000

Özellikler: Sıkıştırmayı açarken görüntüyü serbestçe ölçeklendirebilir, "merdiven efekti" görünümü olmadan 2-4 kat artırabilir. Sıkıştırma seviyesi arttıkça görüntüdeki blokların kenarlarında “bloklu” bir efekt belirir.

Özyinelemeli (dalga) algoritma

Özyinelemeli sıkıştırmanın İngilizce adı dalgacıktır. Rusça'ya dalga sıkıştırması ve patlamaları kullanan sıkıştırma olarak çevrilir. Bu tür arşivleme uzun zamandır bilinmektedir ve doğrudan bölgelerin uyumunu kullanma fikrinden kaynaklanmaktadır. Algoritma, renkli ve siyah beyaz görüntülere odaklanmıştır. yumuşak geçişler. Röntgen gibi resimler için idealdir. Sıkıştırma oranı ayarlanır ve 5-100 arasında değişir. Keskin kenarlıklar, özellikle çapraz olarak geçenler için daha yüksek bir katsayı ayarlamaya çalıştığınızda, bir "merdiven efekti" belirir - birkaç piksel boyutunda farklı parlaklıktaki adımlar.

Algoritmanın fikri, farkı dosyaya kaydetmemizdir - görüntüdeki komşu blokların ortalama değerleri arasındaki sayı, genellikle 0'a yakın değerler alır.

yani iki sayı a 2i ve a 2i +1 her zaman olarak temsil edilebilir b 1 ben=(a 2i +a 2i +1 )/2 ve b 2 ben=(a 2i -a 2i +1 )/2. Benzer şekilde sıra a içiftler halinde bir diziye çevrilebilir b 1.2 ben.

Belirli bir örneğe bakalım: 8 piksel parlaklık değerinden oluşan bir diziyi sıkıştıralım ( a i): (220, 211, 212, 218, 217, 214, 210, 202). Aşağıdaki dizileri alacağız b 1 ben, ve b 2 ben: (215.5, 215, 215.5, 206) ve (4.5, -3, 1.5, 4). değerlere dikkat edin b 2 ben0'a yeterince yakın. b 1 ben nasıl a i. Bu eylem, özyinelemeli olarak gerçekleştirilir, bu nedenle algoritmanın adı. (215.5, 215, 215.5, 206): (215.25, 210.75) (0.25, 4.75). Elde edilen katsayıları, tam sayılara yuvarlanmış ve sıkıştırılmış, örneğin, sabit tablolarla Huffman algoritmasını kullanarak bir dosyaya koyabiliriz.

Dönüşümümüzü zincire yalnızca iki kez uyguladığımızı unutmayın. Gerçekte, dalgacık dönüşümünü 4-6 kez uygulayabiliriz. Ayrıca, düzgün olmayan adım Huffman tabloları kullanılarak ek sıkıştırma elde edilebilir (yani tablodaki en yakın değer için Huffman kodunu saklamamız gerekir). Bu teknikler, fark edilir sıkıştırma oranları elde etmenizi sağlar.

Bir egzersiz:(215, 211) (0, 5) (5, -3, 2, 4) zincirini dosyadan geri yükledik (örneğe bakın). Dalga sıkıştırma algoritmasının yeniden oluşturacağı sekiz piksel parlaklık değerinden oluşan bir dizi oluşturun.

İki boyutlu veriler için algoritma benzer şekilde uygulanır. Parlaklıkları olan 4 noktalı bir karemiz varsa a 2i, 2j,a 2 ben +1 , 2j,a 2i, 2j+1, ve a 2 ben +1 , 2 j +1, sonra

İlk		B1	B2
resim		B3	B4

Bu formülleri kullanarak, 512x512 piksellik bir görüntü için, ilk dönüşümden sonra, 256x256 eleman boyutunda 4 matris elde edeceğiz:

-- İlki, tahmin edebileceğiniz gibi, görüntünün küçültülmüş bir kopyasını saklayacaktır. İkincisi - yatay boyunca piksel değerleri çiftlerinin ortalama farklılıkları. Üçüncüsü - dikey boyunca piksel değerleri çiftlerinin ortalama farklılıkları. Dördüncüsü - köşegen boyunca piksel değerlerindeki ortalama fark. İki boyutlu duruma benzeterek, dönüşümümüzü tekrarlayabilir ve ilk matris yerine 128x128 boyutunda 4 matris elde edebiliriz. Dönüşümümüzü üçüncü kez tekrarlayarak, 4 matris 64x64, 3 matris 128x128 ve 3 matris 256x256 elde edeceğiz. Uygulamada, bir dosyaya yazarken, son satırda () elde edilen değerler genellikle ihmal edilir (hemen dosya boyutunun yaklaşık üçte biri kadar bir kazanç elde edilir - 1- 1/4 - 1/16 - 1/64 ...).

Bu algoritmanın avantajları arasında, görüntüyü ağ üzerinden iletirken görüntünün kademeli olarak "gelişme" olasılığını kolayca gerçekleştirmenize izin vermesi gerçeği yer alır. Ek olarak, aslında görüntünün başında küçük bir kopyasını sakladığımız için, “kaba” görüntüyü başlığa göre göstermek daha kolaydır.

JPEG ve fraktal algoritmadan farklı olarak bu yöntem, örneğin 8x8 piksel gibi bloklarla çalışmaz. Daha doğrusu 2x2, 4x4, 8x8 vb. bloklarla çalışıyoruz. Ancak, bu blokların katsayılarını bağımsız olarak saklamamız nedeniyle, görüntüyü “mozaik” karelere bölmekten oldukça kolay kurtulabiliriz.

Dalga algoritmasının özellikleri:

Sıkıştırma Oranları: 2-200 (Kullanıcı Tanımlı)

Görüntü sınıfı: Fraktal ve JPEG gibi.

Simetri: ~1.5

Özellikler: Ek olarak, yüksek derecede sıkıştırma ile görüntü ayrı bloklara bölünür.

Çözüm

Sonuç olarak, yukarıda tartışılan çeşitli görüntü sıkıştırma algoritmalarının parametrelerini özetleyen tablolara bakalım.

algoritma	Sıkıştırmanın meydana geldiği görüntünün özellikleri
RLE	Ardışık özdeş renkler: 2 2 2 2 2 2 15 15 15
LZW	Aynı alt dizeler: 2 3 15 40 2 3 15 40
huffman	Farklı renk frekansı: 2 2 3 2 2 4 3 2 2 2 4
CCITT-3	Görüntüde beyaz rengin baskınlığı, tek renkle dolu geniş alanlar
özyinelemeli	Pürüzsüz renk geçişleri ve keskin kenarlar yok
JPEG	Keskin sınırlar yok
fraktal	Görüntü Öğeleri Arasındaki Benzerlik

algoritma	K-sen sıkıştırma	zaman içinde simetri	Ne için odaklı	kayıplar	Boyut
RLE	32, 2, 0.5	1	3.4 bit	Değil	1B
LZW	1000, 4, 5/7	1.2-3	1-8 bit	Değil	1B
huffman	8, 1.5, 1	1-1.5	8 bit	Değil	1B
CCITT-3	213(3), 5, 0.25	~1	1 bit	Değil	1B
JBIG	2-30 kez	~1	1 bit	Değil	2B
Kayıpsız JPEG	2 kez	~1	24 bit gri	Değil	2B
JPEG	2-20 kez	~1	24 bit gri	Evet	2B
özyinelemeli sıkıştırma	2-200 kez	1.5	24 bit gri	Evet	2B
fraktal	2-2000 kez	1000-10000	24 bit gri	Evet	2.5D

Uygulama alanı

JPEG algoritması, parlaklık ve renkte yumuşak geçişlerle gerçekçi sahneler içeren fotoğrafları ve resimleri sıkıştırmak için en uygundur. JPEG en yaygın olarak dijital fotoğrafçılıkta ve interneti kullanarak görüntüleri depolamak ve iletmek için kullanılır.

Öte yandan, JPEG, komşu pikseller arasındaki keskin kontrastın gözle görülür yapaylıklara yol açtığı çizimleri, metinleri ve işaret grafiklerini sıkıştırmak için çok az kullanışlıdır. Bu tür görüntüler TIFF, GIF veya PNG gibi kayıpsız biçimlerde kaydedilmelidir.

JPEG (diğer sıkıştırma yöntemlerinin yanı sıra), çok aşamalı işleme sırasında görüntüleri sıkıştırmak için uygun değildir, çünkü ara işleme sonuçları her kaydedildiğinde görüntülerde bozulmalar ortaya çıkacaktır.

JPEG, astronomik veya tıbbi görüntülerin sıkıştırılması gibi minimum kaybın bile kabul edilemez olduğu durumlarda kullanılmamalıdır. Bu gibi durumlarda, JPEG standardı tarafından sağlanan Kayıpsız JPEG sıkıştırma modu (ancak çoğu popüler codec bileşeni tarafından desteklenmez) veya JPEG-LS sıkıştırma standardı önerilebilir.

Sıkıştırma

Sıkıştırıldığında, görüntü RGB renk alanından YCbCr'ye (YUV) dönüştürülür. JPEG standardının (ISO / IEC 10918-1), YCbCr seçimini hiçbir şekilde düzenlemediği, diğer dönüşüm türlerine (örneğin, üçten farklı birkaç bileşenle) ve dönüştürme olmadan sıkıştırmaya izin verdiği belirtilmelidir. (doğrudan RGB'ye), ancak JFIF (JPEG Dosya Değişim Biçimi, 1991'de C-Cube Microsystems tarafından önerilen ve şimdi fiili standart) belirtimi RGB-> YCbCr dönüşümünün kullanımını içerir.

RGB->YCbCr dönüşümünden sonra, renkten sorumlu Cb ve Cr görüntü kanalları için, parlaklık kanalı Y'nin her 4 piksel (2x2) bloğunun atanması gerçeğinden oluşan “desimasyon” (alt örnekleme) gerçekleştirilebilir. Cb ve Cr'nin ortalama değerleri ("4:2:0"). Aynı zamanda, her 2x2 blok için 12 değer (4 Y, 4 Cb ve 4 Cr) yerine sadece 6 kullanılır (her biri 4 Y ve bir ortalama Cb ve Cr). Sıkıştırmadan sonra geri yüklenen görüntünün kalitesi artan gereksinimler, inceltme sadece bir yönde gerçekleştirilebilir - dikey (şema "4:4:0") veya yatay ("4:2:2") veya hiç yapılmaz ("4:4:4") .

Standart ayrıca 2x2 blok için değil, ardışık dört (dikey veya yatay) piksel için, yani 1x4, 4x1 bloklar (4:1:1 şema) ve 2x4 ve 4x2 için ortalama Cb ve Cr ile inceltmeye izin verir. (şema "4:1:0"). Ayrıca kullanılmasına izin verilir çeşitli tipler Cb ve Cr için kırım, ancak pratikte bu tür şemalar çok nadiren kullanılmaktadır.

Ayrıca parlaklık bileşeni Y ile Cb ve Cr renginden sorumlu bileşenler 8x8 piksellik bloklara bölünmüştür. Bu tür blokların her biri ayrı bir kosinüs dönüşümüne (DCT) tabi tutulur. Elde edilen DCT katsayıları nicelenir (genellikle Y, Cb ve Cr için farklı niceleme matrisleri kullanılır) ve run ve Huffman kodları kullanılarak paketlenir. JPEG standardı ayrıca çok daha verimli aritmetik kodlamanın kullanılmasına izin verir, ancak patent kısıtlamaları nedeniyle (JPEG standardında açıklanan aritmetik QM kodlayıcının patenti IBM'e aittir), pratikte nadiren kullanılır. Popüler libjpeg kitaplığına en son sürümler aritmetik kodlama desteği dahildir, ancak bu yöntem kullanılarak sıkıştırılmış görüntülerin görüntülenmesi sorunlu olabilir çünkü birçok izleyici bunları çözmeyi desteklemez.

DCT katsayılarını nicelemek için kullanılan matrisler, JPEG dosyasının başlığında saklanır. Genellikle, yüksek frekans katsayıları, düşük frekans katsayılarından daha güçlü nicemlemeye tabi tutulacak şekilde inşa edilirler. Bu, görüntüdeki ince ayrıntıların kabalaşmasına yol açar. Sıkıştırma oranı ne kadar yüksek olursa, tüm katsayıların nicelenmesi o kadar güçlü olur.

Bir görüntüyü JPEG dosyası olarak kaydettiğinizde, 1 ila 100 veya 1 ila 10 gibi bazı rastgele birimlerde bir kalite ayarı belirtirsiniz. Daha büyük bir sayı genellikle daha iyi kalite (ve daha büyük bir sıkıştırılmış dosya) anlamına gelir. Bununla birlikte, en yüksek kaliteyi kullanırken bile (yalnızca bunlardan oluşan bir niceleme matrisine karşılık gelir), geri yüklenen görüntü, hem DCT uygulamasının sonlu doğruluğu hem de yuvarlama ihtiyacı ile ilişkili olan orijinal görüntüyle tam olarak eşleşmeyecektir. Y, Cb, Cr değerleri ve en yakın tam sayıya DCT katsayıları. DCT kullanmayan Kayıpsız JPEG sıkıştırma modu, geri yüklenen ve orijinal görüntüler arasında tam bir eşleşme sağlar, ancak düşük verimliliği (sıkıştırma oranı nadiren 2'yi geçer) ve yazılım geliştiricilerin desteğinin olmaması, Kayıpsız'ın popülaritesine katkıda bulunmadı. JPEG.

Çeşitli JPEG sıkıştırma şemaları

JPEG standardı, kodlanmış verileri temsil etmenin iki ana yolunu sunar.

Mevcut codec bileşenlerinin çoğu tarafından desteklenen en yaygın olanı, kodlanmış görüntü bloğunun soldan sağa, yukarıdan aşağıya sıralı geçişini varsayan sıralı (sıralı JPEG) veri gösterimidir. Yukarıda açıklanan işlemler, her bir kodlanmış görüntü bloğu üzerinde gerçekleştirilir ve kodlama sonuçları, tek bir "tarama" biçiminde çıktı akışına yerleştirilir, yani sıralı olarak geçirilen ("taranmış") bir kodlanmış veri dizisidir. görüntü. Ana veya "temel" (temel) kodlama modu yalnızca böyle bir gösterime izin verir. Genişletilmiş (genişletilmiş) mod, sıralı ile birlikte aşamalı (aşamalı JPEG) veri gösterimine de izin verir.

Aşamalı JPEG durumunda, sıkıştırılmış veriler çıktı akışına, her biri tüm görüntüyü artan ayrıntılarla tanımlayan bir dizi tarama olarak yazılır. Bu, her taramada tam bir DCT katsayıları seti değil, sadece bazılarını kaydederek elde edilir: ilk - düşük frekans, sonraki taramalarda - yüksek frekans ("spektral seçim" yöntemi, yani spektral örnekler ) veya ardışık olarak, taramadan taramaya, DCT katsayılarının iyileştirilmesi (“ardışık yaklaşım” yöntemi, yani ardışık yaklaşımlar). Verilerin bu aşamalı gösterimi, JPEG dosyasının küçük bir bölümünü aktardıktan sonra görüntünün tamamını görmenizi sağladığından, düşük hızlı iletişim kanalları kullanılarak sıkıştırılmış görüntülerin iletilmesi sırasında özellikle yararlıdır.

Açıklanan her iki şema (hem sıralı hem de aşamalı JPEG) DCT'ye dayanmaktadır ve temelde orijinaliyle tamamen aynı olan restore edilmiş bir görüntü elde edilmesine izin vermez. Bununla birlikte, standart, DCT kullanmayan, ancak doğrusal bir tahmin edici (kayıpsız, yani "kayıpsız", JPEG) temelinde oluşturulan sıkıştırmaya da izin verir; bu, tam, bit-bit eşleşmesini garanti eder. orijinal ve restore edilmiş görüntüler. Aynı zamanda, fotoğraf görüntüleri için sıkıştırma oranı nadiren 2'ye ulaşır, ancak bazı durumlarda garantili bozulma olmaması talep edilir. Adlarındaki benzerliğe rağmen, doğrudan JPEG ISO/IEC 10918-1 ile ilgili olmayan, ISO/IEC 14495-1 tarafından açıklanan JPEG-LS sıkıştırma yöntemi kullanılarak belirgin şekilde daha yüksek sıkıştırma oranları elde edilebilir (ITU T.81 Tavsiyesi). ) standart (ITU T.87 Tavsiyesi).

Sözdizimi ve yapı

JPEG dosyası diziyi içerir işaretçiler, her biri 0xFF baytı ile başlayan, işaretçinin başlangıcını ve bir tanımlayıcı baytı gösterir. Bazı işaretleyiciler yalnızca bu bayt çiftinden oluşurken, diğerleri, işaretçinin bilgi bölümünün uzunluğuyla (bu alanın uzunluğu dahil, ancak başlangıç ​​noktasının iki baytı hariç) iki baytlık bir alandan oluşan ek veriler içerir. işaretleyici, yani 0xFF ve tanımlayıcı) ​​ve verilerin kendisi. Bu dosya yapısı, gerekli verileri (örneğin, satırın uzunluğu, satır sayısı ve sıkıştırılmış görüntünün renk bileşenlerinin sayısı) içeren bir işaretçiyi hızlı bir şekilde bulmanızı sağlar.

Temel JPEG işaretçileri

İşaretleyici	bayt	Uzunluk	Amaç	Yorumlar
YANİ BEN	0xFFD8	Numara	Görüntü başlangıcı
SOF0	0xFFC0	değişken boyut	Çerçeve başlangıcı (temel, DCT)	Görüntünün, DCT ve Huffman kodu kullanılarak temel modda kodlandığını gösterir. İşaretçi, satır sayısını ve görüntü satırının uzunluğunu (işaretçinin başlangıcından itibaren sırasıyla 5 ve 7 ofset değerine sahip iki baytlık alanlar), bileşenlerin sayısını (noktadan 8'lik bir ofsetteki bayt alanı) içerir. işaretçinin başlangıcı), bileşen başına bit sayısı (işaretleyicinin başlangıcından itibaren 4'lük bir ofsetli bayt alanı) ve bileşenlerin oranı (örneğin, 4:2:0).
SOF1	0xFFC1	değişken boyut	Çerçevenin başlangıcı (genişletilmiş, DCT, Huffman kodu)	Görüntünün DCT ve Huffman kodu kullanılarak genişletilmiş modda kodlandığını gösterir. İşaretçi, görüntünün satır sayısını ve satır uzunluğunu, bileşenlerin sayısını, bileşen başına bit sayısını ve bileşenlerin oranını (örneğin 4:2:0) içerir.
SOF2	0xFFC2	değişken boyut	Çerçevenin başlangıcı (aşamalı, DCT, Huffman kodu)	Görüntünün, DCT ve Huffman kodu kullanılarak aşamalı modda kodlandığını gösterir. İşaretçi, görüntünün satır sayısını ve satır uzunluğunu, bileşenlerin sayısını, bileşen başına bit sayısını ve bileşenlerin oranını (örneğin 4:2:0) içerir.
DHT	0xFFC4	değişken boyut	Huffman tabloları içerir	Bir veya daha fazla Huffman tablosu belirtir.
DQT	0xFFDB	değişken boyut	Kuantizasyon tablolarını içerir	Bir veya daha fazla niceleme tablosu belirtir.
DRI	0xFFDD	4 bayt	Tekrar aralığını belirtir	RST işaretleri arasındaki aralığı belirtir n makro bloklarda.
s.o.s.	0xFFDA	değişken boyut	Taramayı Başlat	Soldan sağa yukarıdan aşağıya baypas yönü ile görüntünün ilk veya sonraki taramasının başlangıcı. Temel kodlama modu kullanılmışsa, bir tarama kullanılır. Aşamalı modları kullanırken, çoklu taramalar kullanılır. SOS işaretçisi, görüntünün bilgilendirici (başlık) ve kodlanmış (aslında sıkıştırılmış veri) bölümleri arasında ayrılır.
RST n	0xFFD n	Numara	tekrar başlat	Her birine eklendi r makroblok, nerede r- DRI işaretçisi yeniden başlatma aralığı. DRI işaretçisinin yokluğunda kullanılmaz. n, düşük 3 bit kod işaretçisi, 0'dan 7'ye döngü.
UYGULAMA n	0xFFE n	değişken boyut	Uygulamaya göre ayarla	Örneğin, bir JPEG dosyasının EXIF'i, meta verileri TIFF tabanlı bir yapıda depolamak için APP1 işaretçisini kullanır.
COM	0xFFFE	değişken boyut	Yorum	Yorum metnini içerir.
EOI	0xFFD9	Numara	Resmin kodlanmış bölümünün sonu.

Avantajlar ve dezavantajlar

JPEG sıkıştırmanın dezavantajları arasında, yüksek sıkıştırma oranlarında geri yüklenen görüntülerde karakteristik bozulmaların ortaya çıkması yer alır: görüntü, yüksek sıkıştırma oranlarında 8x8 piksel boyutunda bloklara dağılır (bu etki, özellikle parlaklıkta yumuşak değişiklikler olan görüntü alanlarında fark edilir), yüksek uzamsal frekans (örneğin, görüntünün kontrast konturları ve sınırları üzerinde) artefaktlar gürültü haleleri şeklinde görünür. JPEG standardının (ISO/IEC 10918-1, Ek K, madde K.8) blok artefaktlarını bastırmak için özel filtrelerin kullanılmasını sağladığına dikkat edilmelidir, ancak pratikte bu tür filtreler, yüksek verimliliklerine rağmen pratikte değildir. Kullanılmış. Bununla birlikte, eksikliklere rağmen, JPEG, oldukça yüksek (göründüğü sırada var olan alternatiflere kıyasla) sıkıştırma oranı, tam renkli görüntü sıkıştırma desteği ve nispeten düşük hesaplama karmaşıklığı nedeniyle çok yaygınlaştı.

JPEG sıkıştırma performansı

JPEG standardına göre sıkıştırma işlemini hızlandırmak için, özellikle DCT hesaplanırken geleneksel olarak hesaplamaların paralelleştirilmesi kullanılır. Tarihsel olarak, bu yaklaşımı kullanarak sıkıştırma sürecini hızlandırmaya yönelik ilk girişimlerden biri, 32 bitlik genel amaçlı yazmaçları kullanarak hesaplamaları etkili bir şekilde paralelleştirmeyi mümkün kılan orijinal bir DCT yaklaşımı öneren Kasperovich ve Babkin tarafından 1993 tarihli bir makalede anlatılmıştır. Intel 80386 işlemciler. daha üretken hesaplama şemaları, x86 mimarisi işlemci komut setinin SIMD uzantılarını kullandı. Paralel hesaplamayı yalnızca DCT için değil, aynı zamanda JPEG sıkıştırmanın diğer aşamaları (renk alanı dönüştürme, çalışma düzeyi, istatistiksel kodlama, vb.) ) ve 8x8 kodlanmış veya kodu çözülmüş görüntünün her bloğu için. Makale ilk kez [ kaynak?] JPEG standardına göre sıkıştırma ve kod çözme performansını önemli ölçüde hızlandıran CUDA teknolojisi kullanılarak JPEG algoritmasının tüm aşamalarının paralelleştirilmesinin uygulanması sunulmaktadır.

2010 yılında PLANETS projesinden bilim adamları, İsviçre Alpleri'ndeki özel bir sığınağa yerleştirilen özel bir kapsüle JPEG formatını okumak için talimatlar yerleştirdiler. Bu, 21. yüzyılın başında popüler olan dijital formatlar hakkında gelecek nesiller için bilgileri korumak için yapıldı.

Ayrıca bakınız

Notlar

Bağlantılar

• JFIF 1.02 spesifikasyonu (metin dosyası)
• JPEG optimizasyonu. Bölüm 1 , Bölüm 2 , Bölüm 3 .

Oy: 22, 4

giriiş

Günümüzde yüksek kaliteli, yüksek performanslı bilgisayar grafikleri, yazılım geliştiriciler için en önemli görevlerden biridir. Çeşitli grafik ve multimedya sistemleri için verimli ekipmanların geliştirilmesine büyük fonlar yatırılıyor. Son yıllarda bilgisayarlar, televizyonu veya görüntüleri kaliteli olarak basmayı çoktan geride bırakan en karmaşık görsel görüntüleri gerçek zamanlı olarak yeniden üretebilecek kapasitede göründüler. Bu ortaya çıkmasına katkıda bulundu büyük miktar Bu özellikleri kullanan programlar: bilgisayar oyunları, video uygulamaları, 3d animasyon vb. Ancak tüm bu programların bir ayırt edici özelliği vardır: grafik veri, birlikte çalıştıkları çok yer kaplar.

O zamanlar, BMP, PCX, GIF gibi grafik formatları, kişisel bilgisayar kullanıcıları arasında oldukça yaygındı. Ancak grafik bilgi miktarındaki iki kat azalma bile modern grafik sistemleri için yetersiz kaldı. Bu bağlamda, 80'lerin sonlarından beri dünyanın en büyük iki standart kuruluşu olan CCITT ve ISO, tek bir format standardı geliştirmek için güçlerini birleştirdi. grafik dosyası kayıplı sıkıştırılmış Yeni standart, Joint Photographic Experts Group'tan sonra JPEG olarak adlandırıldı.

Küçük bir hatırlatma yapalım: JPEG, öncelikle bir sıkıştırma yöntemidir. Tam teşekküllü bir görüntü temsil standardı olarak kabul edilemez. Bu nedenle, geometrik piksel boyutu, renk uzayı veya bit dizisi serpiştirme gibi belirli görüntü parametrelerini belirtmez. Aynısı JPEG2000 ve JPEG-LS için de söylenebilir - bunlar tam teşekküllü standartlar değil, sıkıştırma yöntemleridir.

1.JPEG

En basit kayıplı JPEG kodlayıcının çalışma algoritmasını düşünün. Tüm süreç aşağıdaki ana adımlardan oluşur:

Pirinç. bir.

• Ön işleme, görüntünün önceden işlendiği ve onu sonraki kodlama için uygun bir forma götürdüğü aşamadır.
• Ayrık Kosinüs Dönüşümü (DCT), bir görüntüyü uzamsal temsilinden spektral temsiline dönüştürmek için JPEG kodlayıcı tarafından kullanılır.
• Yuvarlama (niceleme), önemsiz, yüksek frekanslı DCT katsayılarının yuvarlanması nedeniyle ana bilgi kaybının meydana geldiği aşamadır.
• Sıkıştırma - alınan verilerin standart yöntemler (tekrar kodlama, aritmetik kodlama vb.)

Görüntü birden fazla bileşen içeriyorsa, bunlar ayrı ayrı kodlanır. Bu konuda, üzerinde bu aşama grafik görüntü, bileşen gösteriminden bir renk farkı, parlaklık gösterimine (ICT - Tersinir Renk Dönüşümü) çevrilir. İnsan gözünün parlaklığa renkten daha duyarlı olması nedeniyle, bu dönüşüm daha az görsel kayıpla daha iyi sıkıştırma sonuçları elde edecektir. Daha sonra, tek bir bileşenin kodlaması ele alınacaktır.

Pirinç. 2.

Pirinç. 3.

BİT dönüşümüne ek olarak, bu aşamada orijinal görüntü küçük kare bloklara bölünür ve görüntünün doğru uzamsal temsili için renk değerlerinin tabanı sıfıra göre kaydırılır: -> [-2 p-1 , 2 s-1 - 1] . Bu adımlar önemli etkili çalışma Bir sonraki adımda kodlayıcı.

1.2. HAZIRLIK

Sıkıştırma algoritmasının önemli bir adımı olan ayrık kosinüs dönüşümü (bundan sonra DCT olarak anılacaktır) bir tür Fourier dönüşümüdür ve ikincisi gibi bir ters dönüşüme (ODCT) sahiptir. Bir görüntüyü, X ve Y eksenlerinin görüntünün genişliğine ve yüksekliğine karşılık geldiği ve Z ekseninin karşılık gelen piksellerin renk değerlerini temsil ettiği bir dizi uzamsal dalga olarak düşünürsek, uzamsaldan geçiş yapabiliriz. görüntünün temsilinden spektral temsiline ve tam tersi. DCT, bir N x N piksel matrisini uygun boyutta bir frekans katsayı matrisine dönüştürür.

Pirinç. dört.

Ortaya çıkan matriste, düşük frekanslı bileşenler sol üst köşeye daha yakın yerleştirilir ve yüksek frekanslı bileşenler sağa doğru kaydırılır. Ekrandaki grafik görüntülerin ana bölümünün düşük frekanslı bilgilerden oluşması nedeniyle, elde edilen matrisi kullanarak, en azını diferansiyel olarak atmak mümkündür. önemli bilgi Minimum görsel kayıp ile. Böylece DCT, resme ciddi bozulmalar getirmeden ağrısız bir şekilde atılabilecek bilgileri seçmenize izin verir. Bu görevin orijinal görüntü üzerinde nasıl gerçekleştirilebileceğini hayal etmek zor.

Formüllerden (Şekil 4), elde edilen matrisin bir elemanının hesaplanmasının O(N 2) zaman gerektirdiği görülebilir, bu nedenle tüm matrisi dönüştürmek neredeyse imkansızdır. JPEG Geliştirme Grubu önerdi en iyi seçenek bu sorunun çözümleri: orijinal matrisi standart 8x8 boyutundaki karelere bölün ve her biri üzerinde bir dönüşüm gerçekleştirin. Daha büyük blokların kullanılması, sıkıştırma kalitesini artıracaktır, ancak çok uzak noktaların birbirine benzer olma olasılığı çok küçük olduğundan, sonsuza kadar değil.

Hesaplamalar sırasında, dönüştürme hızını önemli ölçüde artırabilecek yalnızca 32 önceden hesaplanmış kosinüs değeri kullanıldığına dikkat edilmelidir. Bu, kuşkusuz, kısmi bir bilgi kaybına yol açar, ancak hacimleri nispeten önemsizdir.

Hesaplamalarda yalnızca tamsayı aritmetiği kullanılırsa performansta hafif bir artış elde edilebilir, ancak bu yalnızca eski bilgisayarlar için geçerlidir, çünkü modern bilgisayarlarda kayan nokta sayıları üzerindeki işlemlerin maliyeti tamsayılar üzerindeki işlemlerden farklı değildir. Ayrıca, tamsayı aritmetiğinin kullanılması, sıkıştırılmış görüntünün kalitesini olumsuz yönde etkiler ve bu da bu yöntemi kabul edilemez hale getirir. modern bilgisayarlar. DCT, Fourier dönüşümünün bir varyasyonu olduğundan, Fourier dönüşümünün performansını artırmaya yönelik tüm yöntemler burada da kullanılabilir.

1.3. yuvarlama

Ana bilgi kaybının meydana geldiği bir sonraki aşama, yuvarlama veya nicelemedir. Gördüğünüz gibi, DCT herhangi bir sıkıştırma veya kodlama yapmıyor. Ana görevi, orijinal görüntüyü, üzerinde sonraki işlemler için uygun bir forma dönüştürmektir.

Yuvarlama, DCT matrisini depolamak için gereken bilgi miktarını kısmi bir doğruluk kaybıyla azaltma işlemidir. Bunun için JPEG standardına göre bir yuvarlama matrisi (MO) kullanılır. Orijinal DCT matrisinin her elemanı bir MO elemanına karşılık gelir. Ortaya çıkan matris, orijinal matrisin MO'ya bölünmesiyle elde edilir. Aynı zamanda, DCT matrisindeki düşük frekans değerleri daha düşük MO katsayılarına karşılık gelir, bu da daha önemli, düşük frekanslı bilgiler bırakmayı ve daha az önemli yüksek frekans bilgilerini atmayı mümkün kılar. Düşük frekanslı bileşenlerin DCT matrisinin sol üst köşesinde yoğunlaşmasından dolayı MO değerleri soldan sağa ve yukarıdan aşağıya doğru artmaktadır.

3	5	7	9	11	13	15	17
5	7	9	11	13	15	17	19
7	9	11	13	15	17	19	21
9	11	13	15	17	19	21	23
11	13	15	17	19	21	23	25
13	15	17	19	21	23	25	27
15	17	19	21	23	25	27	29
17	19	21	23	25	27	29	31

Kalite faktörü 2 olan bir yuvarlama matrisi örneği.

Yuvarlamanın sonuçları ve yeniden oluşturulan görüntünün kalitesi doğrudan seçilen yuvarlama matrisine bağlıdır. JPEG standardı herhangi bir MO'nun kullanılmasına izin verir, ancak ISO, kapsamlı deneysel testler yoluyla en uygun sonuçları elde etmek için bir dizi matris geliştirmiştir.

1.4. Sıkıştırma

Algoritmanın son aşaması jpeg kodlaması sıkıştırmadır. DCT matrisi MO yardımıyla işlendikten sonra, ortaya çıkan matriste özellikle yüksek frekans bölgesinde (sağ alt köşede) çok sayıda sıfır belirir.

İlk adım, elde edilen matrisin sol üst köşesindeki değeri göreceli bir değerle değiştirmektir. Komşu görüntü blokları birbirine benzer olduğu için bir sonraki elemanı (0,0) bir öncekinden farklı olarak kodlamak daha verimli olacaktır. İkinci adım, çok sayıda ardışık sıfırı işlemek için tekrar kodlama algoritmasını (LZW) doğrudan uygulamaktır. Deneysel testler, aşağıdaki şekilde gösterildiği gibi matrisin zikzak olması durumunda en iyi sonuçların elde edilebileceğini göstermiştir.

Pirinç. 5.

Son olarak, üçüncü ve son adımda, sonuç, uygulamaya bağlı olarak Huffman algoritması veya aritmetik kodlama kullanılarak normal veriler gibi sıkıştırılır. Bu adıma "entropi kodlaması" denir (JPEG terminolojisinde).

1.5. kod çözme

DCT bir Fourier dönüşümü olduğundan, buna ters bir ayrık kosinüs dönüşümü (IDCT) vardır. Kod çözme algoritması, kodlama algoritmasını ters sırada tekrarlar.

2. JPEG2000

Başlangıçta, yeni standart, gelecekteki bir sıkıştırma standardı için bir temel olarak geliştirildi. JPEG-LS kaybı, ancak daha verimli algoritmaların ortaya çıkması nedeniyle daha sonra terk edildi. Teknolojinin gelişmesiyle bağlantılı olarak, JPEG standardı giderek alaka düzeyini kaybetti. JPEG2000'in tasarımcıları, mevcut standartların birçok hatasını düzeltecek bir standart yaratmayı umuyorlardı. Görevleri arasında şunlar vardı:

• Verimsiz düşük frekanslı sıkıştırmayı ortadan kaldırın. Mevcut algoritmalar, orta frekans ve yüksek frekans bölgelerini sıkıştırmada iyi bir iş çıkardı, ancak düşük frekans bölgesinde kötü sonuçlar gösterdiler.
• Kayıplı ve Kayıpsız Sıkıştırma. Geliştirme sırasında, tek bir sıkıştırma akışında kayıplı ve kayıpsız sıkıştırmaya izin veren bir standart yoktu.
• Büyük Görüntü İşleme. Mevcut algoritmalar, 64Kx64K'dan büyük görüntülerin döşeme yapılmadan verimli bir şekilde sıkıştırılmasına izin vermiyordu.
• Sıkıştırma algoritmasının birleşik yapısı. Mevcut JPEG uygulaması, çoğu uygulamaya özel olan ve desteklenmeyen 44 değişikliği destekledi. çoğu kısım için kod çözücüler.
• Gürültü bağışıklığı. JPEG geliştirme sırasında ağ teknolojileri henüz yeterince geliştirilmemiştir ve JPEG tasarımcıları, görüntüleri güvenli olmayan kanallar üzerinden iletirken gürültü bağışıklığını ve iletim sonucu hasar görmüşse bir görüntüyü kurtarma olasılığını düşünmediler.
• Bilgisayar tarafından oluşturulan görüntüler. Orijinal algoritmalar, dijital fotoğraf makinesi veya tarayıcı ile çekilen dijital fotoğraflar ve görüntüler üzerinde iyi çalıştı, ancak örneğin grafik düzenleyiciler kullanılarak bir bilgisayarda oluşturulan görüntüler verimsiz bir şekilde işlendi.
• Karmaşık Belgeler. JPEG, karmaşık iki boyutlu görüntüleri (özellikle metin görüntüleri) işlerken çok kötü sonuçlar gösterdi.

Aşağıdaki şema, bir JPEG2000 kodlayıcının temel işlem adımlarını göstermektedir.

Pirinç. 6.

Pirinç. 7.

JPEG'den farklı olarak, JPEG2000 kodlayıcı, algoritmada kullanılan DWT (ayrık dalgacık dönüşümü) herhangi bir boyuttaki parçalar üzerinde çalıştığından, görüntüyü küçük kare bloklara bölmeyi gerektirmez. Öte yandan, bazen, kodlayıcının çalışması için kullanılabilir bellek miktarı, görüntünün tamamını kodlamak için gereken bellek miktarından daha azsa, görüntü, birbirinden bağımsız olarak kodlanmış kare karolara bölünür. Ardından, bir döşemenin kodlaması dikkate alınacaktır. Adımların geri kalanı JPEG'e benzer.

Pirinç. sekiz.

2.2. sunta

JPEG2000, bir görüntüyü yüksek frekanslı ve düşük frekanslı bölgelere bölmek için Ayrık Dalgacık Dönüşümü kullanır. DWT, bir frekans filtresi kullanarak orijinal görüntünün her satırını ve sütununu işler.

Pirinç. 9.

Çıkışta bir frekans filtresi kullanılarak her geçişin bilgi miktarını iki katına çıkardığı gerçeğinden dolayı, işlemden sonra görüntü boyutu yarıya iner. DWT'nin bir aşamasından sonra, işlenen parça dört bölüme ayrılır:

• LL - satırlarda ve sütunlarda düşük frekanslar
• HL- yüksek frekanslar satırlara göre ve sütunlara göre düşük
• LH - satırlarda düşük frekanslar ve sütunlarda yüksek frekanslar
• HH - satırlarda ve sütunlarda yüksek frekanslar

Standarda göre kademe sayısı 0 ila 32 arasında olabilir. Normal bir görüntü için 4 ila 8 kademe kullanılır. Takip eden her aşamada, yüksek frekans bölgeleri genellikle önemli bilgiler içermediğinden yalnızca düşük frekans bölgesi (LL) işlenir.

Pirinç. on.

Pirinç. on bir.

2.3. yuvarlama

DWT katsayılarını yuvarlamak için ölü bölgeli sabit bir niceleyici kullanılır. (Şekil 14) Her parça için, bu parçanın tüm katsayıları için yuvarlama adımının sabit bir değeri kullanılır. Yuvarlatılmış değerleri hesaplama formülü Şekil 12'de gösterilmiştir. Burada y, katsayının başlangıç ​​değeridir, sgn(y) katsayının işaretini belirler ve Δb, yuvarlama adımının değeridir. Ölü bölge niceleyici, sıfır civarında 2Δb aralığına sahip bir aralıktır, çıktıda daha fazla sıfır verir.

2.4. kodlama

Elde edilen yuvarlatılmış katsayıların kodlanması blok blok yapılır. JPEG2000 standardına göre, kodlamadan hemen önce parçalar, bir parçanın tüm blokları aynı boyutta olacak şekilde yeterince küçük bloklara (örneğin, 32x32 veya 64x64 boyutunda) bölünür. Engelleme, gürültü bağışıklığını iyileştirmek için sıkıştırılmış bilgilerin daha esnek bir organizasyonunu uygulamak için gerçekleştirilir, vb.

Pirinç. 16.

JPEG2000'de her blok ayrı ayrı kodlanmıştır. Kodlama algoritması, Şekil 17'de gösterildiği gibi her bloğun yuvarlama katsayısı matrisini şeritler halinde çaprazlar. Bloklar, nominal yüksekliği 4 olan bloklara bölünür. Daha sonra, şeritler yukarıdan aşağıya taranır ve her şeritteki sütunlar taranır. soldan sağa atlanır.

Pirinç. 17.

Kodlama işlemi sırasında, bloktaki katsayılar sanal olarak bit düzlemleri olarak temsil edilir. Bu düzlemlerden biri katsayıların işaretleridir; kalan düzlemler, katsayı değerlerinin farklı basamaklarına karşılık gelir (düzlemdeki bir bitin konumu, katsayının bloktaki konumuna karşılık gelir). Kodlama düzlemler tarafından gerçekleştirilir: ilk önce katsayıların en yüksek sırasına karşılık gelen düzlem kodlanır, ardından bir sonraki azalan düzende vb. N adet en öncelikli bit düzleminin (LPB düzlemleri) bir tane içermemesi olabilir. Bu durumda, NPB düzlemi, en az bir birim içeren, sırayla ilk düzlem olur. Kodlama sırasında önündeki boş düzlemler atlanır ve blok başlığına sayıları hakkında bilgi girilir.

Aritmetik kodlama, bağlama bağlı bir modele dayanır. Bağlam, kodlanmış biti çevreleyen bit değerlerinin bir fonksiyonu olarak oluşturulur. NBP hariç her bit düzlemi genellikle üç geçişte kodlanır. İlk kod geçişi sırasında katsayıların önemi hakkında bilgi dağıtımı yapılır. Kodlama sırasında, kodlanmış bloktaki her katsayıya bir anlamlılık parametresi atanır. Geçerli anda kodlanmış bit düzlemlerinde, bu katsayının sıfır olmayan en az bir biti varsa, bir katsayı anlamlı olarak adlandırılır.

Düzlemin her bir biti için, karşılık gelen katsayı henüz anlamlı değilse ve en az bir komşu katsayı zaten önemliyse, mevcut katsayı için anlamlılık gerçeği, yani kodlanmış akımın bu bitinin değeri kodlanır. uçak aslında kodlanmıştır. Kodlanan bit sıfır değilse, işlendikten hemen sonra katsayı işareti bit düzleminin karşılık gelen biti kodlanır (işaret kodlaması).

İkinci geçiş sırasında, ilk geçişte bozulmamış olan ve o anda önemli olan katsayıların bitleri kodlanır. Önceki geçişten farklı olarak, kodlama kararı bitişik katsayıların önemi hakkındaki bilgilere dayalı olarak verildiğinde, bu geçiş sırasında bitler hatasız olarak kodlanır.

Üçüncü ve son geçiş sırasında, birinci ve ikinci geçişlerde işlenmeyen bitlerin işlenmesi gerçekleştirilir. Bu son adımda, grup kodlaması ile birlikte aritmetik kodlama uygulanır.

Standart tarafından sağlanan önemli bir ayrıntı, bilgi kaybından kaynaklanan başka bir verimlilik kazancı kaynağı olan kod geçişlerini atlama yeteneğidir (ilk, en belirgin kaynak nicelemedir). Bu özellik, kod oluşturma hızını kontrol etmek için aktif olarak kullanılmaktadır.

2.5. Veri organizasyonu

Söz konusu standardın önemli bir avantajı, bir görüntünün tek tek öğelerine, temsilinin kodunu tamamen çözmeden erişme yeteneğidir. Bu olanak, ilk olarak orijinal görüntünün birbiriyle kesişmeyen alanlara (döşemeler) bölünmesiyle sağlanır. bireysel görüntüler ve ikincisi, ayrı bir döşemenin kodunun, her biri (karo) alanının bir kısmına karşılık gelen katsayıların toplam kodu olan parçalar (katmanlar) biçiminde temsili. Katmanlar, sırayla, farklı ayrışma seviyelerinde katsayıların kod bloklarını içeren sözde paketlere bölünür. Görüntünün herhangi bir alanını çözmek için, hangi karoya ait olduğunu ve bu karolarla ilgili hangi katmanların gerekli alanı geri yüklemek için gerekli katsayı bloklarının kodunu içerdiğini belirlemek yeterlidir.

Pirinç. yirmi.

Elbette, bir görüntünün "uygun" bir temsili sıkıştırma verimliliği açısından avantajlı olamaz. Gerçekten de, yapısal elemanların (fayanslar, fayansların katman oluşturan alanları vb.) boyutunda bir azalma ile sıkıştırma verimi bir miktar azalır. Bu durumda standart bize bir seçenek bırakıyor: bir yandan, görüntünün parçalarını hızlı bir şekilde çıkarmamıza ve düzenlememize izin veren bilgi temsillerini elde etme yeteneğine sahibiz, diğer yandan standart, oluşturulmasını engellemez. hacim açısından verimli bilgi temsilleri.

Gürültü bağışıklığını ve bilgiye erişim kolaylığını sağlamak için JPEG2000 standardı, bir işaretleyici ve işaretleyici segmentleri sistemi sağlar. İşaretleyici segmentler, işaretleyiciler tarafından sınırlandırılan bilgi parçalarının parametrelerini içerir. Bir işaretleyici ile başlayan veriler, herhangi bir ek bilgi olmadan doğru bir şekilde yorumlanabilir (bu, bütünün parçalardan geri yüklenebileceği anlamına gelmez), bu, temsili bozulmuş bir görüntünün kısmen geri yüklenmesini mümkün kılar. Gürültü bağışıklığı elemanlarının tanıtılması, standardın her türlü telekomünikasyon uygulamasında kullanımına yeşil ışık yakmaktadır.

Yüksek kaliteli sıkıştırma elde etmek, elbette, standardı oluştururken ana görevlerden biriydi ve burada geliştiriciler açık bir ilerleme kaydettiler. JPEG2000 standardı, kayıplı sıkıştırmada yaklaşık 2 kat ve kayıpsız sıkıştırmada %5-20 oranında JPEG standardından daha iyi performans gösterir. Tabii ki, bu durumda kayıpsız sıkıştırma verimliliği, örneğin JPEG-LS standardı kadar yüksek değil, ancak oldukça kabul edilebilir. Kayıplı sıkıştırmanın verimliliğine gelince, burada standart, bu tür yöntemler için bugüne kadarki en iyi sonuçlara yakın sonuçların elde edilmesini sağlar.

3.JPEG-LS

Biçim JPEG-LS formata dayanıyordu LOCO-I(Görüntüler için Düşük Karmaşıklık Kayıpsız Sıkıştırma). JPEG-LS standardının geliştirilmesi için temel olarak benimsenen LOCO-I kayıpsız sıkıştırma algoritması, ilk kez yalnızca kayıpsız değil, aynı zamanda neredeyse kayıpsız modu da (sınırlı, kullanıcı tanımlı kayıplarla sıkıştırma) sağladı. JPEG2000 kayıpsız modunun aksine, JPEG-LS'nin gerçekten başarılı olduğu ortaya çıktı: daha yüksek sıkıştırma verimliliği ile yeni standart, yüksek sıkıştırma / açma hızı sağlar ve bilgisayar kaynakları için fazla talepkar değildir.

JPEG-LS formatının şu anlama geldiğini anlamak önemlidir:

• JPEG yönteminin bir uzantısı veya değişikliği değildir;
• ne DCT (DCT) ne de aritmetik kodlama kullanmaz;
• zayıf nicelemeyi yalnızca "neredeyse kayıpsız" biçimde kullanır

3.1. Temel kavram ve çalışma prensiplerinin tanıtılması

Kayıpsız veri sıkıştırma, iki ayrı bağımsız bölümden oluşur: modelleme (modelleme) ve kodlama (kodlama). Aşağıda aktif olarak kullanacağımız bazı terimleri tanımlayalım:

Kodlayıcı (Kodlayıcı), kodlama işleminden "sorumludur", yani: kaynak görüntüyü girdi olarak alır. dijital format ve standart tarafından tanımlanan tüm gerekli parametreler ve kullanılarak özel set prosedürler oluşturur veri seti sıkıştırılmış bir görüntü içeren Kod Çözücü, kod çözme işlemi ve parçaların dönüştürülmesinden "sorumludur", yani: sıkıştırılmış bir görüntü ile verileri ve girdi olarak gerekli tüm parametreleri almak, yeniden yapılandırılmış görüntüyü çıktı olarak verir

JPEG-LS kod çözücü, kodlayıcıdan çok az farklıdır, bu nedenle bu sıkıştırma algoritması neredeyse simetrik olarak adlandırılabilir. İşte kodlama ilkelerini gösteren basitleştirilmiş bir diyagram:

Pirinç. 21.

hakkında bazı bilgiler orijinal fotoğraf: aşağıdaki şemada gösterildiği gibi (Şekil 22), orijinal görüntü Nf bileşenlerinden oluşabilir. Her Ci bileşeni, x i sütunları ve y i satırları olan iki boyutlu bir piksel dizisi (örnekler) içerir. Bileşenlerin boyutları iki parametreye bağlıdır: X ve Y, burada X, x i değerleri arasında maksimum ve Y tüm bileşenlerin y i değerleri arasında maksimumdur. (JPEG-LS standardında, tek bileşenli görüntülere kıyasla çok bileşenli görüntülerle çalışmanın farklılıklarına tam bir bölüm ayrılmıştır, ancak bu makalede yalnızca tek bileşenli görüntülerle çalışmaya odaklanacağız).

Pirinç. 22.

Şekil, her bileşenin yönünü göstermektedir: üst (üst), alt (alt), sol (sol) ve sağ (sağ). Piksellerin kodlama prosedürlerine işlenmek üzere gönderilme sırası şu şekilde tanımlanır: bileşene göre soldan sağa (soldan sağa) ve yukarıdan aşağıya (yukarıdan aşağıya).

Bağlam pikselleri a, b, c, d, mevcut piksel x'i tahmin etmek için kullanılır. Bağlama bağlı olarak kodlayıcı bir mod seçer: seri (çalışma modu) veya normal (normal mod). seri moda y ve z'nin eşleşme olasılığı varsa seçilir, düzenli- aksi halde. Seçeneğin varlığı ile ilgili olarak buraya bir not düşelim. "neredeyse kayıpsız": Bu seçenek etkinleştirildiğinde, Y ve z YAKIN tolerans ayarına göre neredeyse eşitse seri mod seçilecektir.

Seri modunun kullanılması durumunda, x pikselinden geçerli satırı görüntülemeye başlarız ve bağlam pikseli a ile eşleşen en uzun piksel serisini buluruz. Böylece, geçerli satır içinde, değeri bilinen piksel a ile eşleşen bir dizi özdeş piksel elde ederiz. Sadece dizinin uzunluğunu kodlamak için kalır. (Bu, 32 elemanlı bir J dizisi ile yapılır). "Neredeyse kayıpsız" seçeneği etkinleştirildiğinde, NEAR parametresi kullanılarak a'ya yakın bir dizi pikselin seçildiğini tahmin etmiş olabilirsiniz.

Şimdi normal bir mod kullanılması durumunda eylemlerimizi düşünün. Piksel değerleri a, b ve c piksel x (Px) tahminini hesaplamak için kullanılır. Daha sonra sözde tahmin hatası (Errval) hesaplanır. Değeri x ve Px arasındaki farka eşittir. Errval, içeriğe bağlı bazı üyeler tarafından ayarlanır ve ardından Golomb kodları ile kodlanır. Golomb kodu, A ve N özel dizilerinde depolanan aynı piksellerin a, b, c, d ve Errval değerlerine bağlıdır. "Neredeyse kayıpsız" seçeneği etkinleştirildiğinde, kodlamadan önce tahmin hatası ek olarak nicelenir.

Pirinç. 23.

3.2. kodlayıcı

Temel olarak, JPEG-LS kayıpsız bir bilgi sıkıştırma yöntemi olarak kullanılır, bu nedenle geri yüklenen görüntü dosyası genellikle orijinal dosyayla aynıdır. Neredeyse kayıpsız bir şekilde, orijinal ve yeniden oluşturulmuş görüntü farklılık gösterebilir. Yeniden oluşturulan pikseli Rp ve orijinal pikseli p olarak göstereceğiz.

Başlatma aşaması sırasında kodlayıcı aşağıdaki işlemleri gerçekleştirir:

• Parametreler hesaplanır ARALIK = kat((MAKSVAL + 2 * YAKIN) / (2 * YAKIN + 1)) + 1, qbpp = tavan(log ARALIĞI), bpp = max(2, tavan(log(MAXVAL + 1)) ), LIMIT = 2 * (bpp + maks(8, bpp)) . (Kayıpsız kodlama durumunda, YAKIN = 0, ARALIK = MAKSVAL + 1. Kayıpsıza yakın modu etkinleştirilirse, YAKIN > 0). MAXVAL ve NEAR, algoritmayı uygulayan uygulama tarafından ayarlanan parametrelerdir.
• N , A , B ve C dizin dizileri başlatılır. Amaçlarını açıklayalım: N her bağlamın oluşma sıklığını depolamak için kullanılır, A tahmin hatası değerini toplamak için kullanılır, B sistematik sapmayı hesaplamak için kullanılır, C tahmin hatası düzeltme değerlerini depolamak için kullanılır.
• Çalışma modu değişkenleri RUNindex=0 ve J = (0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 9,10,11,12,13,14,15) .
• İki yardımcı değişken Nn, Nn=0, çoğuşma pikselini kodlamak için başlatılır.

Aşağıda kullanılacak bazı fonksiyonları ve değişkenleri tanıtalım:

GetNextSample() Fonksiyonu: Kaynak görüntüdeki bir sonraki piksel hakkında bilgi alır ve x, a, b, c, d, Ix, Ra, Rb, Rc, Rd değişkenlerinin karşılık gelen değerlerini ayarlar. Okunan piksel satırın sonundaysa GetNextSample(), EOLine = 1 değerini ayarlar. Diğer tüm durumlarda EOLine = 0 . Ra, Rb, Rc, Rd değerleri, değerlerini daha önce hesaplanan Rx değerinden devralır. EOLine Global değişkeni: GetNextSample() işlevi tarafından ayarlanır: geçerli piksel satırdaki sonuncuysa 1'e, aksi takdirde 0'a eşittir. AppendToBitStream(a,b) İşlev: B bitlerini kullanarak kodlanmış bit akışına negatif olmayan bir ikili sayı ekler. En önemli bitler önce eklenir. Quantize(a) Fonksiyonu: Neredeyse kayıpsız modda tahmin hatasını nicelemek için kullanılır. ComputeRx() İşlevi: geçerli piksel için yeniden yapılandırılmış Rx değerini döndürür (nicelenmiş "tahmin hatası" kullanır).

Yukarıdaki görüntüden (Şekil 23) a, b, c ve d piksellerinin x pikselini kodlamada önemli bir rol oynadığı açıktır. Bu pikseller kaybolduğunda ne olduğunu anlamaya çalışalım. Yani kodlama yaparken üst çizgi Bağlam pikselleri c, b ve d eksiktir, bu nedenle değerlerinin sıfır olduğu varsayılır. Geçerli piksel satırın başında veya sonundaysa, a, c veya d pikselleri tanımsızdır. Bu durumda, a ve d için, piksel b'nin yeniden yapılandırılmış Rb değeri (veya üst sıra için sıfır) kullanılır ve c için, önceki satırın ilk karakteri kodlanırken a'nın yeniden yapılandırılmış değeri kullanılır. Bu nedenle kodlayıcı, bazı pikselleri yeniden yapılandırarak kod çözücünün işinin bir kısmını yapmalıdır.

Kodlayıcı aşağıdaki üç adımla başlar:

Q bağlamı oluşturulduktan sonra kodlayıcı x pikselini tahmin eder. İlk olarak, Px tahmini, sözde "kenar kuralı" (kenar tespit eden tahmin edici) kullanılarak hesaplanır:

if (Rc >= maks(Ra, Rb)) Px = min(Ra, Rb);
başka(
eğer (Rc<= min(Ra, Rb))
Px=maks(Ra, Rb);
başka
Px = Ra + Rb - Rc;
}

“Kenarın kuralı”nın özünü açıklayalım. Bunu yapmak için, b durumunu düşünün< а. При этом условии «правило края» выбирает b в качестве прогноза х во многих случаях, когда вертикальный край изображения находится непосредственно слева от х. Аналогично, пиксель а выбирается в качестве прогноза х во многих случаях, когда горизонтальный край находится непосредственно над х. Если край не обнаруживается, то «правило края» вычисляет прогноз в виде а + b - с, что имеет простую геометрическую интерпретацию. Если каждый пиксель является точкой трехмерного пространства, то прогноз а + b - с помещает Рх на ту же плоскость, что и точки а, b и с.

Bir sonraki adım, SIGN numarası (üç bölge numarası Qi'ye bağlı olarak), düzeltme değerleri C(Q) (sistematik sapmalardan türetilmiştir ve burada ele alınmamıştır) ve MAXVAL parametresi kullanılarak sapmadan tahmin düzeltmesidir.

eğer (İŞARET == +1)
Px = Px + C(Q);
başka
Px = Px - C(Q);

(Px > MAXVAL) ise
Px=MAKSVAL;
başka ise (Px< 0)
piksel=0;

Tahmini Px bulunduktan sonra, kodlayıcı x - Px farkı olarak Errval tahmin hatasını hesaplar, ancak SIGN negatifse işareti tersine çevirir.

Neredeyse kayıpsız bir tarzda, hata nicelenir ve kodlayıcı, piksel x'in bu yeniden yapılandırılmış Rx değerini bir kod çözücünün yaptığı gibi kullanır. Temel niceleme adımı aşağıdaki gibidir:

if (hata > 0)
Errval = (Errval + YAKIN) / (2 * YAKIN + 1);
başka
Errval = - (Errval - YAKIN) / (2 * YAKIN + 1);

Bu, YAKIN seçeneğini kullanır, ancak burada gösterilmeyen bazı ayrıntılar vardır. Ana yeniden yapılandırma adımı, Rx = Px + SIGN * Errval * (2 * NEAR + 1) bulmaktır.

Tahmin hatası (olası nicelemeden sonra) modülo indirgemeye maruz kalır. (Bundan sonra ana kodlama adımına hazırdır).

eğer (Errval< 0)
Errval = Errval + ARALIK;
if (Hata >= ((RANGE + 1) / 2))
Errval = Errval - ARALIK;

Golomb kodları (ana parametre b ile gösterilmiştir). JPEG-LS'de bu parametre m ile gösterilir. m sayısı zaten seçilmişse, o zaman negatif olmayan bir n tamsayının Golomb kodu iki kısımdan oluşur: n/m sayısının tamsayı kısmının tekli kodu ve ikili gösterim n mod m . Bu kod için idealdir tam sayılar, geometrik bir dağılıma sahip (yani, n sayısının olasılığı (1 - r) olduğunda) * r n , 0< r < 1) . Для каждого геометрического распределения найдется такое число m, что код Голомба, построенный по m, имеет наименьшую возможную среднюю длину. Простейший случай, когда m равно степени 2 (m = 2 k), приводит к простым операциям кодирования/декодирования. Код числа n состоит в этом случае из k младших разрядов числа n, перед которыми стоит унарный код числа, составленного из остальных старших разрядов числа n. Этот специальный код Голомба обозначается через G(k) .

Örneğin, n = 19 = 10011 2 sayısının G(2) kodunu hesaplayalım. k = 2 olduğundan, m = 4. n'nin en az anlamlı iki basamağı olan 11 2 ile başlayalım. Bunlar, n mod m (3 = 19 mod 4) ile aynı olan 3'tür. Kalan yüksek rakamlar, 100 2, n/m'nin (19/4 = 4.75) tamsayı kısmına eşit olan 4 sayısını verecektir. Tekli kod 4 00001'dir, dolayısıyla n = 19'un G(2) kodu 00001|11'dir.

Pratikte, her zaman sonlu sayıda negatif olmayan tam sayı vardır. En büyük sayıyı I ile belirtin. G(0)'ın en büyük uzunluğu I + 1'dir ve I büyük olabileceğinden Golomb kodunun boyutunu sınırlamak istenir. Bu, k ve glimit olmak üzere iki parametreye bağlı olan özel Golomb kodu LG(k, glimit) kullanılarak yapılır. İlk olarak, n sayısının en anlamlı rakamlarından q sayısını oluşturmalısınız. eğer q< glimit- - 1 , то код LG(k, glimit) совпадает с кодом LG(k]. В противном случае, приготавливается унарный код числа glimit - ceil(log I) - 1 (то есть, glimit - ceil(log I) - 1 нулей, за которыми стоит единственная 1). Это действует как код esc, после которого стоит двоичный код n - 1 из ceil(log I) бит.

Tahmin hataları mutlaka pozitif sayılar değildir. Sıfır veya negatif olabilen bazı farklılıklara eşittirler. Ancak, Golomb kodları pozitif sayılar için oluşturulmuştur. Bu nedenle, kodlamadan önce, negatif hata değerleri, negatif olmayan bir dizi sayıya yansıtılmalıdır. Bunu yapmak için ekranı kullanın:
MERrval=
2 * Errval >= 0 ise Errval,
2*|hata| eğer Errval< 0.

Bu eşleme, negatif ve pozitif değerleri 0, -1, +1, -2, +2, -3,... dizisi olarak değiştirir.

Aşağıdaki tablo, alfabenin boyutu 256 (yani, I = 255 ve ceil(log I) = 8) olduğunu varsayarak, bazı tahmin hatalarını, görüntülenen değerleri ve bunların LG(2, 32) kodlarını listeler.

Tablo: tahmin hataları, eşlemeler ve kodlar LG(2, 32)

Tahmin hatası	Görüntülenen değer	kod
0	0	1 00
-1	1	1 01
1	2	1 10
-2	3	1 11
2	4	01 00
-3	5	01 01
3	6	01 10
-4	7	01 11
4	8	001 00
-5	9	001 01
5	10	001 10
-6	11	001 11
6	12	0001 00
...
50	100	000000000000 000000000001 01100011

Şimdi Golomb kodları için k parametresinin seçimini tartışmamız gerekiyor. Bu uyarlamalı olarak yapılır. k parametresi bağlama bağlıdır ve değeri, bu bağlama sahip bir piksel bulunduğunda her zaman güncellenir. k'nin hesaplanması basit bir satırda ifade edilebilir:
için (k=0; (N[Q]<burada A ve N, 0 ile 364 arasındaki dizin dizileridir. Bu formül, iki dizinin dizini olarak bağlam Q'yu kullanır. Başlangıçta k sıfıra başlatılır ve ardından döngü yürütülür. Döngünün her yinelemesinde, N[Q] dizi elemanı k bit sola kaydırılır ve A[Q] ile karşılaştırılır. Kaydırılan N[Q] değeri A[Q]'ya eşit veya daha büyükse, mevcut k değeri seçilir. Aksi takdirde, k 1 artırılır ve test tekrarlanır.

k sayısını bulduktan sonra, Errval tahmin hatası, LG(k, LIMIT) kodu kullanılarak kodlanan MErrval sayısına dönüştürülür. LIMIT numarası bir parametredir. A ve N dizilerinin güncellenmesi (bir yardımcı dizi B ile birlikte) aşağıdaki kod parçacığını gösterir (RESET parametresi uygulama tarafından ayarlanır):

B[Q] = B[Q] + Errval * (2 * YAKIN + 1);
A[Q] = A[Q] + abs(Errval);
if (N[Q] == SIFIRLA) (
A[Q] = A[Q]>>1;
B[Q] = B[Q]>>1;
N[Q] = N[Q]>>1;
}
N[Q] = N[Q] + 1;

Şimdi tahminin sistematik sapmasını hesaplamaktan bahsedelim. Tahmin düzeltme değeri C[Q], kodlama pikseli x'in sonunda güncellenmelidir. Bunun için iki değişken gerekir - B[Q] ve N[Q]. N[Q], başlatmadan bu yana Q bağlamının oluşum sayısıdır. B[Q], C[Q] değerini yineleme başına en fazla bir kez güncellemenize izin veren sistematik bir sapmadır. Böylece, C[Q] tahmin edici değeri aşağıdaki koda göre hesaplanır:

eğer (B[Q]<= -N[Q]) {
B[Q] = B[Q] + N[Q];
eğer (C[Q] > MIN_C)
C[Q] = C[Q] - 1;
eğer (B[Q]<= -N[Q])
B[Q] = -N[Q] + 1;
}
başka ise (B[Q] > 0) (
B[Q] = B[Q] - N[Q];
eğer (C[Q]< MAX_C)
C[Q] = C[Q] + 1;
eğer (B[Q] > 0)
B[Q] = 0;
}

MIN_C ve MAX_C sabitleri, sırasıyla -128 ve 127 dizin dizisi C'nin minimum ve maksimum olası değerleridir.

Seri modda kodlama farklı yapılır. Kodlayıcının, Ix değerleri eşleşen ve bağlam pikseli a'nın yeniden yapılandırılmış Ra değerine eşit olan ardışık x piksellerini algıladığında bu modu seçtiğini hatırlayın. "Neredeyse kayıpsız" seçeneği için serideki piksellerin |Ix - Ra| eşitsizliğini sağlayan Ix değerlerine sahip olması gerekir.<= NEAR . Серия не должна выходить за пределы текущей строки. Длина серии кодируется (сам пиксель кодировать не нужно, поскольку он равен Ra), и если конец серии находится раньше конца строки, то после ее закодированной длины будет сразу записан код следующего пикселя (который прерывает серию). Две основные задачи кодера в этой моде состоят

1. serinin izlenmesinde ve uzunluğunun kodlanmasında;
2. seriyi kesintiye uğratan pikselin kodlamasında.

Seri takibi şu şekilde yapılabilir:

ÇALIŞMA değeri = Ra;
ÇALIŞTIR = 0;
while (abs(Ix - RUNval)<= NEAR) {
RUNcnt = RUNcnt + 1;
Rx=ÇALIŞMA değeri;
if (EOLine == 1)
kırmak;
başka
GetNextSample();
}

Girilen değerlerden bazılarını açıklayalım: RUNcnt, tekrar eden piksellerin sayacıdır (seri mod için) ve RUNval, yeniden oluşturulan yinelenen pikselin geçerli değeridir.

Seri kodlama sürecini anlatalım. İlk kod parçacığı, rm uzunluğundaki seri segmentlerinin kodlamasını açıklar:

while (RUNcnt >= (1<AppendToBitStream(1, 1);
RUNcnt = RUNcnt - (1<if (RUNindex< 31))
RUNindex = RUNindex + 1;
}

Aşağıdaki kod, rm'den daha kısa uzunluktaki çalıştırma bölümleri için kodlamayı gösterir:

if (EOLine == 0) (
AppendToBitStream(0, 1);
AppendToBitStream(RUNcnt, J);
if (RUNindex > 0)) (
RUNindex = RUNindex - 1;
}
else if (ÇALIŞTIR > 0)
AppendToBitStream(1, 1);

Burada kodlayıcı, rk ile gösterilen 32 girişten oluşan J tablosunu kullanır. J değerlerle başlatılır
0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 9, 10, 11, 12, 13, 14, 15 .

Her rk değeri için rm = 2 rk olarak gösteriliriz. rm sayılarına (toplamda 32 tane vardır) kod sırası denir. İlk 4 rk değeri rm = 2 0 = 1'dir. İkinci dörtlü için rm = 2 1 = 2 ve sonraki dörtlü için rm = 2 2 = 4. Son sayı için rm = 2 15 = 32768. Kodlayıcı, RUNlen değişkeninde saklanan serinin uzunluğunu bulmak için açıklanan prosedürü gerçekleştirir. Daha sonra bu değişken, değerleri ardışık sayılar rm'ye eşit olan terimlere bölünerek kodlanır. Örneğin, RUNlen=6 ise, ilk beş rm sayısı kullanılarak 6 = 1 + 1 + 1 + 1 + 2 olarak temsil edilir. 5 bit ile kodlanmıştır. Kayıt, AppendToBitStream(l,l) komutuyla yapılır. Her 1 yazıldığında, karşılık gelen rm değeri RUNlen'den çıkarılır. RUNlen başlangıçta 6'ya eşitse, sırayla 5, 4, 3, 2 ve 0'a düşer.

RUNlen serisinin uzunluğu, rm sayılarının tamsayı toplamına eşit olmayabilir. Örneğin, RUNlen = 7 . Bu durumda, 1'in beş biti bir kod olarak yazılır, ardından bir önek biti ve dosyaya bir dizi rk biti olarak yazılacak olan RUNlen'in geri kalanı (örneğimizde bu 1'dir) yazılır. Örneğimizdeki rk değeri 2)'dir. Bu son işlem AppendToBitStream (RUNcnt, J) yordamı çağrılarak gerçekleştirilir. Seri, satırda başka bir piksel tarafından kesilirse önek biti 0'dır. Dizi, dizenin sonuna giderse, önek biti 1'dir.

Kodlayıcının ikinci ana görevi olan çoğuşma pikselini kodlamak, mevcut pikseli kodlamaya benzer şekilde yapılır. Uygulamasının ayrıntılarını tartışalım.

Bir piksel satırının sonunda kodlama işleminin kesintiye uğradığı durumu düşünün: kesintiye neden olan yeni piksel nasıl kodlanacak? Bu sorun, mevcut x konumundaki Ix değeri ile a veya b piksellerinin yeniden oluşturulmuş değeri arasındaki farkın kodlanmasıyla çözülür (bunların x'e göre komşu pikseller olduğunu hatırlayın - bkz. Şekil 23). Bu durumda iki farklı durum göz önünde bulundurulur: birincisi, abs(Ra - Rb) olduğunda<= NEAR , вторая - в противном случае. По сути кодирование пикселя прерывания серии происходит теми же методами, что и кодирование нового пикселя в регулярной моде с тем лишь дополнением, что Ix должно отличаться от Ra на величину большую NEAR, иначе ход кодирования будет продолжен. Опишем операции, которые должны быть выполнены:

if (mutlak(Ra - Rb)<= NEAR)
Rtipi = 1;
başka
Rtipi = 0;
if (RItype == 1)
P = Ra;
başka
P=Rb;
Errval = Ix - Rb;

Yukarıdaki kod parçacığı, x pikseli için RItype indeksini ve tahmin hatasını belirler. Ardından, gerekirse Errval işaretini değiştirin ve “neredeyse kayıpsız” seçeneği için tahmin hatasını da niceleyin:

if ((RItype == 0) && (Ra > Rb)) (
hata = -errval;
İŞARET=-1;
başka
İŞARET = 1;
eğer (YAKIN > 0) (
Errval = Quantize(Errval);
Rx = ComputeRx();
}
başka
Rx=Ix;
Errval = ModRange(Errval, RANGE);

Şimdi Golomb kodlarında k parametresini hesaplamak için kullanılacak olan yardımcı değişken TEMP'yi hesaplayalım.

if (RItype == 0)
SICAKLIK=A;
başka
TEMP = A + (N>>1);

Q = RItype + 365 olarak ayarlayın. Golomb kodları için k parametresi aşağıdaki gibi hesaplanacaktır: for (k=0; (N[Q]<

eğer (Errval< 0) {
Nn[Q] = Nn[Q] + 1;
A[Q] = A[Q] + ((EMERrval + 1 -RItype)>>1);
if (N[Q] == SIFIRLA) (
A[Q] = A[Q]>>1;
N[Q] = N[Q]>>1;
Nn[Q] = Nn[Q]>>1;
}
N[Q] = N[Q] + 1;

Bu, JPEG-LS kodlayıcısının açıklamasını tamamlar. Kesinlikle eksik olduğuna dikkat edin, ancak kendimize bu yöntemin standardını kopyalama hedefini koymadık. Atlanan tüm parçalar standartta bulunabilir. Şimdi dekoderin ilkelerinin kısa bir açıklamasına geçelim.

3.3. kod çözücü

Daha önce belirtildiği gibi, JPEG-LS yöntemi neredeyse simetriktir, bu nedenle kodlayıcının açıklamasını küçük değişikliklerle kopyalamayacağız - bu bilgi standartta da okunabilir. Sadece seri modda kod çözmenin nasıl gerçekleştiği üzerinde duralım. Geçerli piksel için tüm değerler hesaplandıktan sonra okur yeni vuruş Bit akışından R. 1'e eşitse, o zaman:

1. Görüntü 2 J|RUNindex| ile tamamlanmaktadır. Ra değerine sahip pikseller.
2. Önceki adımda görüntü zaten 2 J|RUNindex| ile tamamlanmışsa piksel ve RUNindex< 31, то RUNindex увеличивается на 1. Если последний пиксель в строке ещё не декодирован, то мы снова считываем биты, в противном случае переходим к вычислению всех требуемых величин.

Bit 0 ise, o zaman:

1. J|RUNindex|'i okuyun bit akışından bit ve bir sayıya dönüştürülür ve görüntü, hesaplanan sayıya karşılık gelen miktarda Ra değerlerine sahip piksellerle doldurulur.
2. RUNindex > 0 ise, RUNindex 1 azalır.
3. Patlama kesici pikselin kodu çözülür ve gerekli tüm değerlerin hesaplanması yeniden başlar.

3.4. Dosya formatı

sıkıştırılmış dosya oluşur:

• Golomb kodlarını ve çalışma uzunluklarını içeren veri bölümlerinden;
• işaretleyici segmentlerinden (kod çözücünün ihtiyaç duyduğu bilgiler);
• "kalan" işaretleyiciler bölümünden (bazı ayrılmış JPEG işaretçileri).

Burada bir işaretçiyi bir bayt olarak adlandırırız ve ardından yeni bir segmentin başlangıcını bildiren özel bir kod gelir. Bir işaretleyiciyi, en anlamlı biti 1 olan bir bayt izliyorsa, o bayt, işaretleyici segmentinin başlangıcıdır. Aksi takdirde, veri segmenti başlar.

3.5. Golomb kodları

Golomb kodlarından bir kereden fazla bahsetmiştik. Bu ne? Negatif olmayan bir tamsayının Golomb kodu "etkili bir Huffman kodu olabilir". Bazı b parametresinin seçimine bağlıdır. Kodlama prensibi:

• iki miktar hesaplanır
  q = kat((n - 1) / b) ve
  r = n - qb - 1;
• kod iki kısımdan oluşturulmuştur: ilk kısım tekli bir kodda q, ikinci kısım r için küçük artıklar için floor(log 2 b) bitleri ve büyük için ceil(log 2 b) bitlerinden oluşan ikili bir ifadedir. olanlar.

JPEG-LS'de Golomb kodlarının kullanımı için matematiksel bir gerekçe sağlamıyoruz, sadece şunu not ediyoruz: giriş akışı veriler tamsayılardan oluşur ve n sayısının olasılığı P(n) = (1 - p) n - 1 p (0<= p <= 1) , то коды Голомба будут оптимальными кодами для этого потока данных, если выбрать параметр b следующим образом:
(1 - p)b + (1 - p)b + 1<= 1 <= (1 - p) b - 1 + (1 - p) b .

3.6. Çözüm

JPEG-LS formatı öncelikle tıbbi amaçlarla, yani en ufak bir kalite kaybı olmadan büyük bir görüntünün önemli olduğu durumlarda görüntüleri depolamak için geliştirilmiştir. Daha önce de belirtildiği gibi, HP Labs duvarları içinde geliştirilen LOCO-I formatı esas alınmıştır. Ardından "HP" ve "Mitsubishi"nin ortak çabalarıyla sonuçlandırıldı. Her iki şirket de bu formattaki patentlerinin lisans ödemeden kullanılmasına izin verdi, bu nedenle JPEG-LS normal PC programlarında da bulunabilir.

Kendi örneğimle açıklayayım. Belki bazı şeyleri anlamama yardım edebilirsin. Önüme kendim koyduğum görev şudur. Bir çerçeveyi (komutla) WEB kameradan bir cep telefonunun belleğine aktarın ve ardından başka bir cep telefonuna aktarın. Makalenizden hangi formatın temel alınması gerektiği, algoritmanın kullanılabilirliği net değil. Ayrıca - sosine dönüşümü yalnızca yüzeysel bir yorumdur, ancak belirli bir örnekle ayrıntılı bir algoritmayı nerede görebilirim (örneğin, matematiksel analiz öğrenin, ancak neredeyse hiç belirli örnek yok ve varsa, tüm hesaplama parçaları eksik) .Belki özel bir kılavuz vardır, bu yüzden bakın.Dosya organizasyonunun yapısı tamamen atıldı ve hatta bağlantılar belirtilmedi. "Sonuçtaki matriste, düşük frekanslı bileşenler sol üst köşeye daha yakın ve daha yükseğe yerleştirildi. frekans bileşenleri sağa kaydırılır", bana öyle geliyor ki, bu şekilde yapılıyor, ancak işe yaramıyor (belki yanılıyorum!).

Soru: örneğin, bir PC kullanmadan, bir MK kullanarak telefonun ekran çözünürlüğünde daha fazla kod çözme için bir JPG çerçevesinden yalnızca gerekli bilgileri nasıl yakalayabilirim. Çerçevenin yeterli siyah beyaz versiyonu. Hangi FFxx'e dikkat etmeniz ve sadece o bilgiyi yazmanız gerekiyor. WEB kamera çerçeve yapısını nereden alabilirim. Sorunun karmaşık ve çok yönlü olduğunu anlıyorum. Örneğin, MK'de çerçevenin kodunu çözemez ve ardından istenen çözünürlükte sıkıştıramazsınız, ancak muhtemelen en azından üst köşeyi istenen formatta kesmek mümkündür.

Bilgi için minnettar olacağım.

Ne yapabilirim = VB, MK'de programlayın. Cep telefonu aracılığıyla çoklu röle kontrolünün kendi kendine hareket eden etkileşimli gelişimi, cep telefonu kullanarak ses kontrolü.

>> İkinci adım, >> tekrar kodlama algoritmasını (LZW) doğrudan uygulamaktır.

belki RLE?

Tabii ki, bu adımda JPEG (bağlama bakın) RLE'dir. Hatayı tespit ettiğiniz için teşekkürler.

fil 17 Aralık 2013 02:09

JPEG'i icat etmek

• algoritmalar,
• Görüntü işleme

• öğretici

Bunun JPEG algoritmasının sıradan bir açıklaması olmadığını başlıktan doğru anladınız (dosya formatını yazıda detaylı 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 ne kadar 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 animasyonlar 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 üst üste bindikleri ve dahası, yarı saydam oldukları için, ş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 bir p = (x, y) noktasının yeni sistem bir nokta olarak temsil edilecektir (a 0 , a 1). Yeni katsayıları bilerek, 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 hayal edin: 0 veya 1 (yani, 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". Zaten oldukça ince olan bu üç boyutlu tabaka 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). AT son sürüm Hiçbir şeyi atmadık, bu yüzden orijinalini aldık.

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 görsel olarak dört boyutlu uzayda tabanı 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.
Yani, 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 matrisi dönüşüm matrisi olarak adlandırılır 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 bir ifade elde edebiliriz. Bu kadar kısa bir fonksiyona sahip olmamızın bir önemi yok, çünkü aynı mantık N-boyutlu bir vektör için işe yarar, bu N değerleri ile ayrık bir fonksiyon olarak gösterilebilir. 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. Ayrıca, 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 temel 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 hesaplaması, orijinal vektörün mesafe olarak bir diğerine minimum yakınsamasını verir. Mesafenin Pisagor teoremi kullanılarak hesaplandığını akılda tutarak, fonksiyonlar şeklinde benzer bir temsil, bir fonksiyonun diğerine en iyi kök-ortalama-kare 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, sadece iki nokta ile bir fonksiyona 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.
Bir dizi elde edilen 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 buldu. "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ğunu nasıl anlayabilirim? Ama son işlevi dinlemeyi düşünseydim, o zaman 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 ayrıştırmadığı anlaşılmıştır. 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. Ancak ş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. DCT-dönüşüm formülünün nasıl elde edildiğini yukarıdaki grafiklerden açıkça gördüğünü düşünüyorum:

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. Bu, ters dönüşüm sırasında 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 yoktur. Gerçekten de, sesten farklı olarak, bir görüntüyü periyodik fonksiyonlara ayırmanın yararı çok daha az açıktır. Ancak, 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 edilir:

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 tekdüze arka planı görürsek, ona yaklaştıkça genlik büyümeye başlar, sonunda Minimum değer, 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 konusunda yanlış bir izlenim edinebilirsiniz. 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 son katsayılar bile büyük olacaktır. Bu nedenle, DCT'nin enerji tasarrufu özelliğini duyduğunuzda, bunun karşılaştığınız birçok sinyal türü için geçerli olduğu, ancak hepsi için geçerli olmadığı gerçeğini hesaba katı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 incelediğimde, 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 sürü farklı resimle, bilinen çeşitli temellerle donatıyoruz ve gerçek görüntüden standart sapmayı hesaplamaya başlıyoruz. farklı miktar katsayılar. Bu teknikle ilgili makalede (kullanılan görüntüler) 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. Çizelgelere 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 dönüşüm Fourier. 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ırmasında herhangi bir saf harmonik sinyalin (bir tamsayı frekansı ile) bu harmoniğe karşılık gelen yalnızca bir sıfır olmayan 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 kaydırılmış 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 diğer frekanslardan oluştuğu gerçeğine yol açar. İkinci yarının bu yanlış harmonikleri aynadaki görüntüönce ve ek bilgi taşımayın. 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 farkedilir olacaktır. 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ına yakın, 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 var hızlı algoritmalar karmaşıklık ile O(N*logN), alındaki hesaplamanın aksine: 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 resim 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ışması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 önemli genişleme katsayılarıdır.
Sağ alt köşe, en önemsiz katsayıların en önemsiz genişleme katsayılarıdır.
Soldan çapraz olarak hareket edersek katsayıların öneminin azaldığı açıktır. üst köşe sağ altta. 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 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.
Ancak, 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 sadece periyodik fonksiyonlarda 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ünür 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özle görülü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 blokları: 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şi içeren bir örneği kontrol edelim:


16x16 blok distorsiyonu 8x8'den daha fazla uzansa da, yazı 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, 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ının 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 fazla 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 - nicelleştirilmiş 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 getiremeyeceğ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 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. Ama 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 etmek 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: bir hayvanat bahçesindeki alfabenin bir harfi, bir kelime veya 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 gösteriminin 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.
3m farklı semboller(A, B, C) olası 2 bit değerini (0 ve 1) eşleştirmenin bir yolu yoktur. 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. Ancak B ve C iki olsa bile A'yı bir bit ile kodlamaya kararlıyız. Bu dilekten yola çıkarak A'ya 0 kodunu veriyoruz. O zaman B ve C kodları 0 ile başlayamaz. Ancak 1 ile başlayabilirler:

• B:10
• C:11

Sıra şu şekilde kodlanacaktır: 0000001011. Zihinsel olarak deşifre etmeye ç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ığı, oluşum payını yansıtan göreli bir değer veya sembol sayısına eşit mutlak bir değer olabilir. Ana şey, ağırlıkların karakterlerin oluşumuyla orantılı olmasıdır.

Örnek 3
Düşünmek Genel dava herhangi bir ağırlığa sahip 4 karakter için.

• 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 bir 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, 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 karakterin diğerinden iki kat daha seyrek olarak ortaya çıkması durumunda, kodunun uzunluğunun bir bit daha uzun olacağı anlamına gelir. Ancak, 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. Dahası, 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ı kodlanmış olmaları ş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 tüm orijinal değerlerden 128 çıkarır, bu da DC'den 1024'ün çıkarılmasına karşılık gelir) 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ı az çok 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 kapladığından (baştaki sıfırlar kaldırılırsa), sıkıştırma kurallarından biri iyi karşılanmıştır: büyük ağırlıklı semboller atayın kısa kodlar(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 onların tarafından kodlanır. ikili gösterim, ve negatif olanlar aynıdı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 uzunluğunda 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, "0" ın yanında "9" u daha yüksek bir seviyeye güvenle yükseltebilirsiniz? 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ı ile elde edilen kodlar, uzunlukları aynı olmasına rağmen bitlerle 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ş verin. DC'lerin nasıl depolandığını anladık:
[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 2 - bir sonraki frekans. Bu anlaşılabilir bir durumdur - herkes kuantizasyondan 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öşeye yakın olduğundan ve sağ alt köşeye ne kadar yakınsa o kadar fazla sıfır 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 resimde - alternatif yol baypas, JPEG ile ilgili değil, ilginç bir adla (kanıt). Geçmeli videoyu sıkıştırırken MPEG'de kullanılabilir. Bypass algoritmasının seçimi görüntü kalitesini etkilemez, ancak sonuçta dosya boyutunu etkileyebilecek şekilde kodlanmış sıfır gruplarının sayısını artırabilir.
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üzende yazılmışsa). Bu sıfırlar, nicelemeden kurtulamayan 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.

Miktarın bu çiftlere ve bir Huffman ağacına 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 kullanılan daha fazla çift. Ö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 iş. 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 değil ayrı kanal parlaklık. Her kanalın değerlerinin toplamına bağlıdır. Bu nedenle, RGB küpü (bu, tüm olası değerlerin bir temsilidir) diyagonal üzerine basitçe “koyulur” - ne kadar yüksekse, o kadar parlaktır. Ancak bu bunlarla sınırlı değildir - küp kenarlardan 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 ikiye ayrılırlar küçük bloklar, örneğin 2x2, 4x2, 1x2 ve bir bloğun tüm değerlerinin ortalamasını alın. 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 şekilde destekler ve düzenli programlar Windows, paint.net tüm bilgileri doğru bir şekilde çıkartıyor ama daha sonra 4. siyah kanalı atıyor, yani (bunu atmadıklarını söyledi, yorumlarını okuyun) daha açık bir görüntü veriyor. 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 (zaten öğrendiğimiz gibi: Huffman ve zikzak baypas), ardından ikinci terimleri vb. kodlarız. Bu numara, aşağıdaki durumlarda yararlıdır. yavaş internet, ilk başta sadece DC katsayıları yüklendiğinden, buna göre 8x8 “piksel” ile kaba bir resim oluşturulur. Ardından, deseni iyileştirmek için yuvarlatılmış AC katsayıları. Sonra onlara kaba düzeltmeler, sonra daha doğru olanları. Peki, vb. Oranlar şu şekilde yuvarlanır: erken aşamalar yükleme doğruluğu o kadar önemli değil, ancak her aşama kendi Huffman tablosunu kullandığından yuvarlama, kodların uzunluğu üzerinde olumlu bir etkiye sahiptir.

kayıpsız mod

Kayıpsız sıkıştırma. DCT değildir. 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 birden çok katman oluşturulur. farklı izinler. İ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ı sanki kesirli sayı biraz. 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
kullanılan yazılımı belirtmek için sunulmuştur. 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. Şovlar detaylı bilgi jpeg dosyası hakkında.
• 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ü. için bakıyordum görsel düzenleyici formüller, çünkü Lateks ile pek arkadaş canlısı değilim. 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üzellik.

Etiketler:

• jpeg
• dct
• dft
• Fourier
• huffman

Etiket ekle