JPEG algoritması

JPEG oldukça güçlü bir algoritmadır. Uygulamada, tam renkli görüntüler için fiili standarttır. Algoritma, parlaklığın ve rengin nispeten yumuşak bir şekilde değiştiği 8x8 alanlarla çalışır. Sonuç olarak, böyle bir bölgenin matrisi kosinüslerde çift seri halinde genişletildiğinde, sadece ilk katsayılar anlamlıdır. Böylece, JPEG formatında sıkıştırma, görüntüdeki renklerde yumuşak değişiklikler pahasına gerçekleştirilir.

Bir grup fotoğraf uzmanı tarafından özellikle 24 bitlik görüntüleri sıkıştırmak için geliştirilen bir algoritma. JPEG - Joint Photographic Expert Group - ISO - Uluslararası Standardizasyon Örgütü içinde bir bölüm. Algoritmanın adı ["jei" peg] okur. Genel olarak, algoritma, bazı yeni katsayılar matrisi elde etmek için görüntü matrisine uygulanan Ayrık Kosinüs Dönüşümüne (DCT) dayanmaktadır. Orijinal görüntüyü elde etmek için ters dönüşüm uygulanır.

Görüntüyü bazı 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 sıfıra eşit olduğu bir matris elde ederiz. Ek olarak, insan görüşünün kusurlu olmasından dolayı, görüntü kalitesinde gözle görülür bir kayıp olmadan katsayıları daha kabaca tahmin etmek mümkündür.

Algoritma nasıl çalışır?

Algoritmayı daha ayrıntılı olarak ele alalım. 24 bitlik bir görüntüyü sıkıştırdığımızı varsayalım.

Aşama 1.
Nokta renginin kırmızı (Kırmızı), yeşil (Yeşil) ve mavi (Mavi) bileşenlerinden sorumlu bileşenlerle RGB renk uzayından görüntüyü YCrCb renk uzayına (bazen YUV olarak adlandırılır) çeviririz. İçinde Y parlaklık bileşenidir ve Cr, Cb renkten (kromatik kırmızı ve kromatik mavi) sorumlu bileşenlerdir. İnsan gözünün renge karşı parlaklığa göre daha az hassas 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. Bu dönüşüm uzun süredir televizyonda kullanılıyor. Renkten sorumlu sinyallere daha dar bir frekans bandı tahsis edilir.

RGB renk uzayından YCrCb renk uzayına basitleştirilmiş çeviri, bir geçiş matrisi kullanılarak temsil edilebilir:

Adım 2.
Orijinal görüntüyü 8x8 matrislere bölün. Her bir bileşen için ayrı ayrı 8 bit olmak üzere üç çalışma matrisi oluşturuyoruz. Daha yüksek sıkıştırma oranlarında bu adım biraz daha zor olabilir. Görüntü, ilk durumda olduğu gibi Y bileşenine bölünür ve Cr ve Cb bileşenleri için matrisler bir satır ve bir sütun boyunca yazılır. Şunlar. orijinal 16x16 matristen sadece bir çalışan DCT matrisi elde edilir. Aynı zamanda görülmesi kolay olduğu için görüntünün renk bileşenleri ile ilgili faydalı bilgilerin 3 / 4'ünü kaybediyoruz ve hemen iki katlı bir sıkıştırma elde ediyoruz. Bunu YCrCb uzayında çalışarak yapabiliriz. Pratikte gösterildiği gibi, bunun ortaya çıkan RGB görüntüsü üzerinde çok az etkisi vardır.

Aşama 3.
Basitleştirilmiş bir biçimde, n \u003d 8 için DCT aşağıdaki gibi temsil edilebilir:

Her çalışma matrisine DCT uygularız. Bu durumda, 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. Frekans kavramı, görüntüyü iki boyutlu bir sinyal olarak düşünmekten kaynaklanır (sesi bir sinyal olarak düşünmeye benzer). Düzgün bir renk değişimi, düşük frekanslı bir bileşene karşılık gelir ve yüksek frekanslı bir bileşene keskin atlar.

4. adım.
Nicelleştiriyoruz. Temel olarak, bu sadece çalışma matrisini kuantizasyon matrisiyle öğeye böler. Her bileşen (Y, U ve V) için, genel durumda, kendi niceleme matrisi q (bundan sonra MC) belirtilir.

Bu adımda sıkıştırma oranı kontrol edilir ve en büyük kayıp meydana gelir. MK'yi büyük katsayılarla belirterek, daha fazla sıfır ve dolayısıyla daha büyük bir sıkıştırma oranı elde edeceğimiz açıktır. JPEG standardı, ampirik olarak oluşturulmuş önerilen MK'yi içerir. Daha fazla veya daha az sıkıştırma derecesi için matrisler, orijinal matrisin bir sayı gama ile çarpılmasıyla elde edilir.

Niceleme, algoritmanın belirli etkileriyle ilişkilidir. Yüksek gama değerlerinde, düşük frekanslardaki kayıp o kadar büyük olabilir ki, görüntü 8x8 karelere bölünür. Yüksek frekanslardaki kayıplar, keskin bir renk geçişi ile konturların etrafında bir tür "hale" oluştuğunda, "Gibbs etkisi" olarak adlandırılan şekilde kendini gösterebilir.

Adım 5.
8x8 matrisi bir "zikzak" taraması kullanarak 64 elemanlı bir vektöre çeviririz, örn. indisli elemanlar alıyoruz (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 matris katsayılarını elde ederiz.

6. adım.
Vektörü grup kodlama algoritmasını kullanarak birleştiriyoruz. Bu durumda, "atla" nın atlanan sıfırların sayacı olduğu ve "sayı" nın bir sonraki hücreye koyulması gereken değer olduğu türden çiftler (atlama, sayı) elde ederiz. Böylece, vektör 42 3000-2 00001 ... çiftler halinde katlanacaktır (0.42) (0.3) (3, -2) (4.1) ...

7. Adım.
Elde edilen çiftleri Huffman kodlamasıyla sabit bir tabloyla birleştirin.

Bu algoritmadaki görüntü restorasyon süreci tamamen simetriktir. Yöntem, bazı görüntüleri ciddi bir kayıp olmadan 10-15 kez 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. Çıktı renkli görüntüsü nokta başına 24 bit olabilir.

Algoritmanın dezavantajları şunlardır:

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

JPEG'in pek hoş olmayan bir özelliği de, ekrandaki yatay ve dikey şeritlerin tamamen görünmez olması ve yalnızca hareli desen şeklinde basıldığında görünebilmesidir. Bir görüntünün yatay ve dikey şeritleri üzerine eğik bir baskı taraması yapıldığında oluşur. Bu sürprizler nedeniyle, JPEG'nin baskıda aktif olarak kullanılması ve niceleme matrisinin yüksek katsayıları ayarlanması önerilmez. Ancak, görüntüleri insan görüntüleme için arşivlerken, şu anda yeri doldurulamaz.

JPEG’nin yaygın kullanımı, belki de yalnızca 24-bit görüntülerle çalıştığı gerçeğiyle uzun süredir kısıtlanmıştır. Bu nedenle, bir monitörde 256 renkli bir palette kabul edilebilir kalitede bir resim görüntülemek için, uygun algoritmaları ve dolayısıyla belirli bir süre kullanmak gerekiyordu. Oyunlar gibi seçici bir kullanıcıyı hedefleyen uygulamalarda bu tür gecikmeler kabul edilemez. Ek olarak, örneğin 8 bit GIF formatındaki mevcut görüntüler 24 bit JPEG'e dönüştürülür ve ardından görüntüleme için tekrar GIF'e dönüştürülürse, her iki dönüştürmede de kalite kaybı iki kez meydana gelir. Bununla birlikte, arşiv boyutundaki kazanç genellikle o kadar büyüktür (3-20 kat) ve kalite kaybı o kadar küçüktür ki, görüntüleri JPEG formatında depolamak çok etkilidir.

1991'de standartlaştırılmış JPEG. Ancak o zaman bile, daha az kalite kaybıyla daha güçlü sıkıştıran algoritmalar vardı. Gerçek şu ki, standardın geliştiricilerinin eylemleri, o sırada var olan teknolojinin gücü ile sınırlıydı.

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şturur ve bu nedenle algoritmayı değiştirebilirler. Böylelikle ISO tarafından önerilen algoritmanın dahili tabloları kendi tabloları ile değiştirilir. Ek olarak, bir kayıp oranı belirlenirken biraz karışıklık vardır. Örneğin, test ederken, "mükemmel" kalite, "% 100" ve "10 puan" önemli ölçüde farklı resimler verir. Aynı zamanda, "% 100" kalite kayıpsız sıkıştırma anlamına gelmez. Belirli uygulamalar için JPEG seçenekleri de vardır.

JPEG algoritması özellikleri:
Sıkıştırma oranı 2-200 (Kullanıcı tanımlı).
Görüntü sınıfı: Keskin renk geçişleri olmayan tam renkli 24 bit veya gri tonlamalı görüntüler (fotoğraflar).
Simetri: 1
Özellikler: Bazı durumlarda, algoritma görüntüdeki keskin yatay ve dikey kenarların etrafında bir "hale" oluşturur (Gibbs etkisi). Ek olarak, sıkıştırma oranı yüksek olduğunda, görüntü 8x8 piksellik bloklara bölünür.

Geri dön

İçeriğe

İleri

JPEG benzeri şemalarda uyarlanabilir niceleme matrisleri üretimi

Luzhkov Yuri Valerievich,

st.Petersburg Devlet Bilgi Teknolojileri, Mekanik ve Optik Üniversitesi'nde yüksek lisans öğrencisi.

Bilimsel danışman - Teknik Bilimler Doktoru, Profesör

Tropchenko Alexander Yuvenalievich.

Giriş

Son yıllarda, dalgacık dönüşümlerine dayalı kayıplı görüntü sıkıştırma şemalarının popülerleştirilmesinde belirgin bir eğilim var. Bununla birlikte, ayrık kosinüs dönüşümü (DCT) görüntü sıkıştırma formatları hala en yaygın kullanılanıdır.

Formatın yaygın kullanımıJPEG (Birleşik Fotoğraf Uzmanları Grubu) [ Wallace G.K.] araştırmacılara şu soruyu soruyor: Mevcut sıkıştırma şemasını, açma algoritmasını değiştirmeden sıkıştırma kalitesini artıracak şekilde değiştirmek mümkün müdür? Bu sorunun çözülmesi, kullanıcılar tarafından görüntü açma için özel (değiştirilmiş) yazılımların kullanılabilirliği konusunda endişelenmeden mevcut kompresörlerde değişiklik yapılmasına izin verecektir.

JPEG benzeri bir şema ile, bir görüntüyü dikdörtgen parçalara ayıran bir sıkıştırma şemasının bir versiyonunu kastediyoruz, bunların zorunlu öğeleri şunlardır: ortogonal dönüşüm, dönüştürülen verilerin nicelleştirilmesi ve sonraki entropi kodlaması.

Çoğu sıkıştırma algoritması bir dizi varsayılan parametre kullanır. JPEG'de bunlar, niceleme matrislerini ve Huffman tablolarını içerir. Sıkıştırılmış dosyanın başlığına kaydedilirler ve kullanıcı tarafından bağımsız olarak tanımlanabilirler, bu da sıkıştırma kalitesini artırır.

Bu nedenle, bugüne kadar, JPEG niceleme matrislerini (örneğin ve) oluşturmak için evrensel olmayan birkaç yaklaşım önerilmiştir. Çalışmamızda, uygulaması basit olan ve JPEG benzeri şemalarda uygulanabilen, spektral katsayıların uyarlanabilir skaler nicemlemesine genelleştirilmiş bir yaklaşım ele alacağız.

Uyarlanabilir sinyal niceleme

Niceleme, içine distorsiyon eklemeyi içeren bir sinyal işleme yöntemidir. Öz skaler nicemleme aşağı gelir bir fonksiyonun değer aralığını sonlu sayıda aralığa bölmek ve bu aralıktaki herhangi bir değeri temsil etmek için bir değerin müteakip seçimi.

Öyleyse, bir dizi aralık ve bir dizi nokta verilsin, o zaman niceleme işlevi için tanımlanmıştır. Ne zaman düzgün skaler nicemleme aralıklar şu şekilde temsil edilebilir:

nerede - parametre veya niceleme adımı, - aralıkların temel kayması, , - kodlanmış nesne olan aralığın numarası. Daha sonra niceleme işlemi yuvarlama ile basit bölmeye indirgenebilir:

.(1)

Skaler nicemlemede uyarlanabilirlik, nicemlenmiş her değer için niceleme adımını ayrı ayrı seçerek elde edilir.

Ağırlıklı Uyarlanabilir Skaler Niceleme

Önerdiğimiz yaklaşım temel alır spektral katsayıların istatistiksel analizi... Sıkıştırma şemalarında kullanılabilir (ör.Jpeg ), sinyal tarama penceresinin sabit bir boyuta sahip olması şartıyla.

Öyleyse, bir miktarlar dizisi verilsin, bölünmüşM aynı bloklarN her birindeki değerler ve - bu bloktaki öğenin indeksi, yani her öğenin başka herhangi bir blokta kendi analogu vardır. Önerilen yaklaşımın özü aşağıdaki gibidir: her biri içinnÜçüncü elemandan, özel bir ağırlık kriterinin değeri hesaplanır ve bu spektrum elemanının niceleme adımı, ne kadar büyük olursa, karşılık gelen ağırlık kriteri değeri o kadar düşük ayarlanır.

Bu nedenle, niceleme prosedürü, aşağıdaki şekilde verilen sinyal hakkındaki bazı istatistiksel bilgiler dikkate alınarak gerçekleştirilir.M bloklar ve her dizinin öğeleri için benzersiz n... Bu durumda niceleme işlevi (1), olarak belirtilecektir ve niceleme parametre işlevi – .

Bir kriter getiriyoruz, buna spektrum katsayısı ağırlığı... Değer, ilgili spektral konumun önem derecesini yansıtacaktır.n katsayılar .

Hesaplama yöntemlerinden biri ortalama genliklere dayanmaktadır:

.(2)

Deneyler, DCT katsayıları için (2) 'ye göre hesaplamanın, yüksek ve düşük frekans spektral katsayıları için kriter değerlerinin orantısız bir dağılımına yol açtığını göstermiştir. Kullanarak durumu düzeltebilirsiniz düzeltici işlev (aşağıya bakın) veya maksimum genliklere göre değerleri hesaplayarak:

.(3)

Bir fonksiyon tanımlama sorusuna dönelim. Değerleri aralıkla sınırlı olsun ... Doğrusal bir işlevi tanıtalım:

,

nerede ve sırasıyla minimum ve maksimum değerler (durum ayrı olarak değerlendirilir).

Uygulamada, bir düzeltme işlevi kullanılarak elde edilen doğrusal olmayan bir işlevi kullanmak avantajlıdır:

.(4)

Genel durumda herhangi biri orijinal spektral vektörün tüm elemanlarına bağlı olduğundan, fonksiyonE ayrıca bağlıdır. Aslında bu, sinyal niceleme adımının bir fonksiyonudur. Gösterimi tanıtalım ... Daha sonra formül (4) nihayet şu biçimi alır:

.(5)

Bu nedenle, niceleme adımının işlevi aşağıdaki aralıkta yerelleştirilir:a 1 ila a 2 Şekli değiştirilerek, belirli katsayı grupları az ya da çok bastırılabilir.

Şimdi, şemadaki uyarlanabilir niceleme matrisleri üretimi için önerilen yaklaşımı uygulayalım.Jpeg ... (5) 'te, doğrusal bir düzeltme fonksiyonu ve maksimum genlikler için kriter (3) kullanacağız.

Niceleme adımının varsayılan fonksiyon grafikleriJpeg Şek.1 kaldı. Δ görüntü için uyarlamalı olarak oluşturulan grafikler "Yaşlı adam"Şek.1, doğru. Her iki durumda da değerler artan sırada sıralanır. Gördüğünüz gibi, argümanın değerlerinin ilk üçte biri için, özellikle üretilen fonksiyonların karakteristiği olan Δ'da keskin bir artış var. Bu bölgede oluşturulmuş Δ bazı yerlerde standardı önemli ölçüde aşar, bu da karşılık gelen frekansların daha fazla bastırılmasına yol açar.

Şekil: 1. Sıralı nicemleme parametresinin standart ve oluşturulmuş fonksiyonları

değerlere göre artan.

Görüntü grafiği "Yaşlı adam»Şekil 2'de gösterilmiştir.2 sol. Sağ tarafta, sıkıştırma sonuçları deney tarafından oluşturulan varsayılan matrisler ve matrisler kullanılarak gösterilmektedir. Sonuçlardan da görülebileceği gibi, sıkıştırma oranındaki fark, aynı değerlere sahip uyarlamalı yaklaşım lehine% 20'ye kadar çıkmaktadır.PSNR.

Şekil: 2. Devre için uyarlanabilir nicemleme matrislerinin oluşturulması Jpeg.

Sonuç

Spektral bileşenlerin önemi için kriterin hesaplanmasına dayanarak, spektral katsayıların uyarlamalı skaler nicemlemesi için bir yöntem önerdik. Deneyler, şemada dikkate alınan yaklaşımın kullanımınınJpeg standart niceleme matrislerini kullanmaya kıyasla sıkıştırma oranında% 20'ye varan bir kazanç elde etmenizi sağlar.

Göz önünde bulundurulan modifikasyonun pratik kullanımı sadece bir kompresörün uygulanmasını içerir ve görüntüleri görüntülemek için kullanmak yeterlidir.Jpeg -decompressor, önerilen çözümün önemli bir avantajıdır.

Edebiyat

1. Fung H.T., Parker K. J. JPEG // Journal of Electronic Imaging için görüntüye uyarlanabilir niceleme tablolarının tasarımı. - 1996. - Cilt. 4, N. 2. - S. 144 - 150.

2. Gray R.M., Neuhoff D.L. Bilgi Teorisi Üzerine Niceleme // IEEE İşlemleri. - 1998. - Cilt. 44, N. 6. - S. 2325 - 2383.

3. Ratnakar V., Livny M. RD'yi Genişletme JPEG optimizasyonu için global eşikli OPT // Veri Sıkıştırma Konferansı.– 1996.

4. Wallace G. K. JPEG sabit resim sıkıştırma standardı // IEEE Trans. Tüketici Elektroniği. - 1992. - Cilt. 38, N. 1. - S. 18 - 34.

JPEG dijital sıkıştırma

En eksiksiz ve popüler görüntü sıkıştırma standartlarından biri JPEG standardıdır.

Sıkıştırma işleminin kendisi üç ardışık adımdan oluşur:

a) DI matrisinin standart bölümlemesinden sonra elde edilen 8 * 8 bloklu matrisler için ayrık kosinüs dönüşümünün (DCT) hesaplanması;

b) DCT katsayılarının nicelleştirilmesi;

c) eşit olmayan kodla kodlama.

İlk olarak, DI, soldan sağa ve yukarıdan aşağıya sırayla işlenen 8 * 8 elemanlı ayrı bloklara bölünmüştür. Her bloğun işlenmesi, 64 öğesinin tamamının değerlerinin bir parlaklık kaymasıyla başlar, bu değerin çıkarılmasıyla elde edilir, burada maksimum parlaklık seviyesi sayısıdır. Daha sonra blok elemanlarının iki boyutlu DCT'si hesaplanır. Katsayıların elde edilen değerleri aşağıdaki formüle göre nicelendirilir:

,

dCT katsayı değerinin nicelemesinin sonucu ve niceleme katsayıları matrisinin karşılık gelen öğesidir:

.

(Nicelleştirilmiş DCT katsayılarının bir görüntü bloğunu yeniden oluşturmak için ters DCT'ye dönüştürülmeden önce aşağıdakilerle çarpılması gerektiği unutulmamalıdır:

. (2.5)

Açıktır ki, elde edilen değerlerin ters dönüşümü, geri yüklenen görüntü bloğunun bir yaklaşımı ile sonuçlanacaktır.)

Katsayıların nicelleştirilmiş değerleri, aşağıdakilere göre zikzak dönüşümü ile yeniden sıralanır:

katsayıların seçildiği sıra gösterilir. Sonuç, tek boyutlu nicelleştirilmiş katsayılar dizisidir.

Zikzak dönüşümünden sonra elde edilen tek boyutlu dizi, artan uzaysal frekansta sıralanır ve bir kural olarak, JPEG kodlama prosedürü tarafından etkin bir şekilde kullanılan uzun sıfır dizileri görünür. Önerilen JPEG niceleme matrisi aşağıdaki gibidir:

Misal. Sıralı JPEG kodlama ve kod çözme... JPEG sıralı kodlama standardına göre aşağıdaki 8 * 8 öğe bloğunun sıkıştırılmasını ve geri yüklenmesini düşünün:

Orijinal pikseller 256 veya 28 parlaklık seviyesine sahip olabilir, bu nedenle kodlama işlemi değer aralığını kaydırarak başlar - piksel değerlerinden 27 veya 128 çıkarılır. Sonuç bir dizidir:

doğrudan DCT'den sonra şöyle görünecektir:

Elde edilen verileri nicelemek için yukarıdaki niceleme matrisi kullanılıyorsa, nicelemeden sonra katsayılar şu şekilde olacaktır:

Niceleme prosedürü, önemli sayıda sıfır eleman verir. Katsayılar zikzak dönüşüme göre yeniden düzenlendikten sonra aşağıdaki dizi elde edilecektir:

(-26-31-3-2-6 2-4 1-4 1 1 5 0 2 0 0-1 2 0 0 0 0 0-1-1 KB)

KB kod sözcüğü bloğun sonu anlamına gelir ve yeniden sıralanan dizide kalan tüm katsayıların 0'a eşit olduğunu belirtir. Elde edilen diziyi kodlamak için, diziyi sürekli bir bit akışına dönüştüren standart Huffman kodları kullanılır.

Sıkıştırılmış bir JPEG bloğu kurtarılırken, kod çözücü ilk önce nicelleştirilmiş DCT katsayılarını sürekli bit akışından yeniden oluşturmalıdır. Bir ikili Huffman kod dizisi benzersiz bir şekilde çözüldüğünden, bu adım bir tablo dönüşümü kullanılarak kolayca gerçekleştirilebilir. (2.5) 'e göre niceleme katsayılarıyla çarpıldıktan sonra, diziyi elde ederiz:

Ortaya çıkan dizinin ters DCT'sini gerçekleştirdikten sonra tamamen kurtarılmış bir blok elde edilir:

ve değerler aralığının +2 7 \u003d + 128 ile ters kaydırılması. Sonuç olarak, şunları elde ederiz:

Orijinal ve kurtarılan blokların öğelerinin değerlerindeki tüm farklılıklar, JPEG sıkıştırma ve kurtarma prosedürlerinin özü olan kayıplı sıkıştırmanın doğasından kaynaklanmaktadır. Bu örnekte, kurtarma hataları -14 ile 11 arasındadır ve aşağıdaki gibi dağıtılır:

JPEG sıkıştırmada dijital görüntü matrisinin bloklarının tekil sayılarının karakteristik özellikleri . Orijinal DRO'nun bazı kayıpsız formatlarda, örneğin matrisi boyutlara sahip TIF formatında saklanmasına izin verin, standart bir şekilde bloklara bölünsün. Her DI bloğu için tüm ELF'lerin kümesini (tekil spektrum) belirlersek, toplam blok sayısının (OFB) ortalama olarak yalnızca% 2.40'ının sıfır ELF'ye sahip olduğu ortaya çıkar.

Bu gerçek tesadüfi değildir. Herhangi bir matrisin sıralaması, sıfır olmayan ELF sayısıyla belirlenir; bu, tekil spektrumda sıfırların varlığının, doğrusal olarak bağımsız satırlarının (sütunlarının) sayısının boyuttan daha küçük olduğunu göstereceği anlamına gelir. Bununla birlikte, rastgele bir gerçek DI için, piksel parlaklık değerlerinin korelasyonu hesaba katılsa bile, sonraki bloğun satırlarının (sütunlarının) doğrusal olarak bağımlı hale gelme olasılığı küçüktür.

DI'leri JPEG formatında (kayıpla) kaydetme sürecinde ortaya çıkan DCT katsayılarının nicelendirilmesi, geri döndürülemez bir prosedürdür ve ELF bloklarının bazı tuhaflıklarına yol açar.

Orijinal DI'nin JPEG sıkıştırmasına maruz kalmasına izin verin. Bunun için, aşağıdakileri içeren kısmi kurtarma (PC) işlemini gerçekleştirelim: 1) entropi kod çözme; 2) elde edilen katsayıların, normalleştirme dizisinin karşılık gelen elemanlarıyla çarpılması (niceleme matrisi); 3) ters DCT'nin uygulanması, ancak daha sonra yuvarlama olmadan.

Ortaya çıkan matriste, hemen hemen tüm bloklar sıfır ELF içerir ve bloklarda bu tür birçok değer olacaktır (Tablo 2.1). Bu durum doğaldır. Blokların DCT katsayılarının nicelleştirilmesi ve yuvarlanmasından sonra, yüksek ve orta frekanslara karşılık gelen birçoğu sıfır olacak, CW'den sonra sıfır kalacaktır; sırasıyla VLF ve karşılık gelen sol ve sağ BAŞLANGIÇLAR olan görüntü matrisi, blokların en küçük (ve muhtemelen boyut olarak ortalama) ELF matrislerinin sıfırlanmasına yol açacaktır.

Tablo 2.1. Kısmen yeniden yapılandırılmış görüntülerin bloklarının tekil değer ayrıştırmasının sonuçları

	OChB		TBN'ye göre blok sayısı, ELF'si 2'den fazla olan kediler (% olarak)
m \u003d 8	m \u003d 7	m \u003d 6	m \u003d 5	m \u003d 4	m \u003d 3	m \u003d 2	m \u003d 1	m \u003d 0
POUT
KAMERAMAN
TEKERLEK
AY											99.8
HÜCRE

Söz konusu blokta ne kadar az sıfır ELF varsa, o kadar fazla kontur çizgisi içerdiğine dikkat edin. Gerçekte, bir bloktaki konturların varlığı, bu bloğa karşılık gelen sinyalde önemli bir yüksek frekanslı bileşeni gösterir. Daha sonra, yüksek ve orta frekanslara karşılık gelen DCT katsayıları nispeten büyük olacaktır ve niceleme ve FW'den sonra sıfırdan farklı kalabilir ve bu nedenle sadece maksimum ELF'ye katkıda bulunmayacaktır.

Yukarıdakilerin geçerliliğinin görsel bir temsili için, СELL.TIF görüntüsünü düşünün (Şekil 2.5 (a)). Şekil 2.5 (b), her bir elemanı karşılık gelen bloktaki sıfır VLF bloklarının sayısına eşit olan bir CW görüntüsünün boyutlarına sahip sıfır VLF bloklarından (MNFB) oluşan bir matris gösterir. Şekilde, en küçük değerlere sahip elemanlar vurgulanmıştır; bu, orijinal DI'nın konturları ile en az miktarda sıfır VLF içeren bloklar arasındaki uygunluğu net bir şekilde görmenize olanak tanır.

JPEG sıkıştırması geçirmiş orijinal görüntünün tamamen geri yüklenmesine izin verin. Bu, CW'den sonra tüm piksel parlaklık değerlerinin tam sayılara yuvarlanıp aralığa girildiği anlamına gelir. Bu işlem CW'den sonra elde edilen görüntü matrisini bozacak, bloklardaki sıfır VLF sayısı belirli bir şekilde değişecektir (Tablo 2.2). FW'den sonra önemli ölçüde 0'dan küçük veya 255'ten büyük herhangi bir öğenin olmadığı durumlarda, matris pertürbasyonu küçük olacaktır. Orana göre

, (2.6)

sırasıyla orijinal matrisin ELF'si ve düzensiz matrislerin ELF'si bloğun pertürbasyon matrisidir, spektral matris normu, ELF rahatsız edici etkilere karşı duyarsızdır. CW görüntü matrisinin bazı sıfır VLF blokları, tam geri kazanımdan (RR) sonra sıfırdan farklı hale gelirse, değerleri orijinal DI blokları için tipik olmayan yuvarlama hatasıyla karşılaştırılabilir olacaktır.

Şekil 2.5. Orijinal resim СELL.TIF (a); PV (b) 'den sonra MNSCHB; Tam iyileşmeden sonra MNSCHB (c)

Kümülatif orijinal görüntü ile JPEG sıkıştırmasından sonra tamamen kurtarılan görüntü arasındaki en göze çarpan fark, MNSS'leri karşılaştırılırken olacaktır. Tipik bir resim Şekil 2.5 (c) 'de gösterilmektedir, CELL.TIF için MNSS ise sadece sıfır değerlere sahiptir.

Tablo 2.2. Tamamen yeniden oluşturulmuş görüntü bloklarının tekil değer ayrıştırması

Kayıpsız Görüntü (TIF)	OChB	Sıfır VLF'ye sahip blok sayısı	TBN'ye göre ikiden fazla sıfır SP'ye sahip blok sayısı (%)
m \u003d 8	m \u003d 7	m \u003d 6	m \u003d 5	m \u003d 4	m \u003d 3	m \u003d 2	m \u003d 1	m \u003d 0
POUT
KAMERAMAN
TEKERLEK
AY
HÜCRE

Sorular

1. Veri sıkıştırması ne anlama geliyor? Veri Yedekliliği nedir?
2. Ana veri yedekliliği türleri.
3. Nicelleştirilmiş sıkıştırma nasıl uygulanır?
4. Düşük sıralı görüntü yaklaşımı nedir? Düşük sıralı görüntü yaklaşımları kullanılarak sıkıştırma nasıl uygulanır?
5. Bir matrisin tekil değer ayrışımı nedir?
6. Spektral matris ayrışımı nedir?
7. Uzamsal ve frekans alanlarındaki dijital bir görüntünün parametreleri arasındaki yazışma.
8. Dijital bir görüntünün JPEG sıkıştırmasının temel adımları. Niceleme matrisleri.
9. JPEG sıkıştırmada dijital görüntü matrisinin bloklarının tekil sayılarının karakteristik özellikleri.
10. Sıkıştırmadan sonra dijital görüntünün kısmi ve tam restorasyonu.

Edebiyat

1. Kobozeva A.A. Bilgi güvenliği analizi / A.A. Kobozeva, V.A.Khoroshko. - K .: Ed. GUIKT, 2009. - 251 s.
2. J. Demmel Hesaplamalı doğrusal cebir / J. Demmel; lane in English. Kh.D. Ikramova. - M .: Mir, 2001. - 430 s.
3. Bakhvalov N.S. Sayısal yöntemler / N.S. Bakhvalov, N.P. Zhidkov, G.M. Kobelkov. - M: BINOM. Bilgi Laboratuvarı, 2006. - 636 s.
4. Gonzalez R. Dijital görüntü işleme / R. Gonzalez, R. Woods; başına. İngilizceden. ed. P.A. Chochia. - M .: Technosphere, 2005. - 1072 s.
5. Kahaner D. Sayısal yöntemler ve yazılım / D. Kahaner, K. Mowler, S. Nash; başına. İngilizceden. Kh.D. Ikramova. - M .: Mir, 2001. - 575 s.
6. Gantmakher F.R. Matris teorisi / F.R. Gantmakher. - Moskova: Nauka, 1988. - 552 s.
7. V.V. Voevodin Doğrusal cebirin hesaplama temelleri / V.V. Voevodin. - M .: Bilim. Fizik ve Matematik Edebiyatı'nın baş editörü, 1977. - 304 s.

Uygulama alanı

Biçim, kayıplı bir sıkıştırma biçimidir, bu nedenle JPEG'nin verileri kanal başına 8 bit (piksel başına 24 bit) olarak sakladığını varsaymak yanlıştır. Öte yandan, JPEG sıkıştırılmış veriler ve sıkıştırılmış veriler genellikle kanal başına 8 bit olarak temsil edildiğinden, bu terminoloji bazen kullanılır. Gri tonlamalı görüntülerin sıkıştırılması da desteklenmektedir.

Bir JPEG dosyasını kaydederken, kalite derecesini ve dolayısıyla genellikle bazı rasgele birimlerde, örneğin 1'den 100'e veya 1'den 10'a ayarlanan sıkıştırma derecesini belirleyebilirsiniz. Daha yüksek sayı, daha iyi kaliteye karşılık gelir, ancak dosya boyutu artar. Genellikle 90 ile 100 arasındaki kalite farkı pratik olarak göz tarafından algılanmaz. Lütfen JPEG formatında kurtarılan görüntünün orijinalin tam bir kopyası olmadığını unutmayın. Yaygın bir yanılgı, JPEG kalitesinin depolanan bilgi miktarı ile aynı olmasıdır.

JPEG formatı için çeşitli yazılımlar tarafından yaygın destek, genellikle bunun için tasarlanmamış görüntülerin JPEG kodlamasına neden olur - doğru yapılmış PNG veya GIF ile karşılaştırıldığında sıkıştırma oranında herhangi bir kazanç olmaksızın, ancak acınacak kalitede sonuçları vardır. Örneğin, küçük kontrast ayrıntıları (özellikle renk) içeren bir görüntüyü JPEG formatında kaydetme girişimi, yüksek bir "kalite seviyesinde" bile karakteristik açıkça görülebilen yapay nesnelerin ortaya çıkmasına yol açacaktır.

Sıkıştırma

Görüntü sıkıştırıldığında RGB'den YCbCr'ye (YUV) dönüştürülür. JPEG standardının (ISO / IEC 10918-1) herhangi bir şekilde YCbCr seçimini düzenlemediği, diğer dönüştürme türlerine (örneğin, üçten farklı birkaç bileşenle) ve dönüştürme olmadan sıkıştırmaya izin verdiği unutulmamalıdır. (doğrudan RGB'ye), ancak JFIF (C-Cube Microsystems tarafından 1991'de önerilen JPEG Dosya Değişim Formatı ve şimdi fiili standart), RGB-\u003e YCbCr dönüşümünün kullanıldığını varsayar.

Renkten sorumlu Cb ve Cr görüntü kanalları için RGB-\u003e YCbCr dönüşümünden sonra, "decimation" (alt örnekleme) gerçekleştirilebilir, bu da Y parlaklık kanalının 4 piksellik (2x2) her bloğunun ortalamalı Cb ve Cr'ye atandığı anlamına gelir. değerleri (onsimasyon şeması "4: 2: 0". Bu durumda, her 2x2 blok için, 12 değer (4 Y, 4 Cb ve 4 Cr) yerine, yalnızca 6 değer (4 Y ve bir ortalama Cb ve Cr) kullanılır. Görüntü sıkıştırmaya artan gereksinimler uygulanır, ondalık ayırma yalnızca tek yönde yapılabilir - dikey ("4: 4: 0") veya yatay ("4: 2: 2") veya hiç gerçekleştirilmez ("4: 4: 4").

Standart ayrıca Cb ve Cr ortalamalı 2x2 blok için değil, dört ardışık (dikey veya yatay) piksel için, yani 1x4 veya 4x1 bloklar ("4: 1: 1" düzeni) için dekimasyona izin verir. Cb ve Cr için farklı türlerde dekimasyona da izin verilir, ancak pratikte bu tür şemalar oldukça nadirdir.

Daha sonra, luma Y bileşeni ve renkten sorumlu Cb ve Cr bileşenleri 8x8 piksel bloklarına bölünür. Bu tür blokların her biri ayrı bir kosinüs dönüşümüne (DCT) uğrar. Elde edilen DCT katsayıları nicelleştirilir (genel durumda Y, Cb ve Cr için, farklı niceleme matrisleri kullanılır) ve Huffman kodları kullanılarak paketlenir. JPEG standardı ayrıca çok daha verimli aritmetik kodlamanın kullanımına da izin verir, ancak patent kısıtlamaları nedeniyle (JPEG standardında açıklanan aritmetik QM kodlayıcı için patent IBM'e aittir), pratikte kullanılmaz.

DCT katsayılarını nicelemek için kullanılan matrisler, JPEG dosyasının başlık kısmında saklanır. Genellikle, yüksek frekans katsayılarının düşük frekanslı olanlardan daha güçlü nicelleştirileceği şekilde yapılandırılırlar. Bu, görüntüdeki ince ayrıntıların kabalaşmasına yol açar. Sıkıştırma oranı ne kadar yüksekse, tüm katsayılar o kadar güçlü bir şekilde nicelendirilir.

JPEG sıkıştırma şemalarının çeşitleri

JPEG standardı, kodlanmış verileri temsil etmek için iki ana yol sağlar.

Mevcut kodeklerin çoğu tarafından desteklenen en yaygın olanı, şifreli görüntünün blok halinde soldan sağa, yukarıdan aşağıya sıralı geçişini içeren verilerin sıralı JPEG 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" (bir kodlanmış veri dizisi) biçiminde çıkış akışına sıralı olarak yerleştirilir. Temel veya "temel" kodlama modu yalnızca bu gösterime izin verir. Sıralı mod ile birlikte genişletilmiş (genişletilmiş) mod, aşamalı (aşamalı JPEG) veri sunumuna da izin verir.

Aşamalı JPEG durumunda, sıkıştırılmış veriler çıktı akışına her biri görüntüyü artan ayrıntı derecesiyle tam olarak tanımlayan bir dizi tarama olarak yazılır. Bu, ya her taramada tam bir DCT katsayıları setini değil, yalnızca bazılarını kaydederek elde edilir: birincisi - sonraki taramalarda düşük frekans - yüksek frekans ("spektral seçim" yöntemi, yani spektral örnekleme) veya taramadan taramaya sıralı olarak DCT katsayılarının iyileştirilmesi (yöntem "ardışık yaklaşım", yani ardışık yaklaşımlar). Verilerin bu aşamalı temsili, düşük hızlı iletişim kanalları kullanılarak sıkıştırılmış görüntüleri aktarırken özellikle yararlıdır, çünkü JPEG dosyasının yalnızca küçük bir kısmı aktarıldıktan sonra görüntünün tamamı hakkında bir fikir edinmenize olanak tanır.

Açıklanan şemaların her ikisi de (hem sıralı hem de aşamalı JPEG) DCT'ye dayalıdır ve temelde orijinal olanla tamamen aynı olan geri yüklenen görüntünün elde edilmesine izin vermez. Bununla birlikte, standart aynı zamanda DCT kullanmayan, ancak orijinal ve yeniden yapılandırılmış olanın tam, bit bit, çakışmasını garanti eden doğrusal bir öngörücü (kayıpsız, yani "kayıpsız", JPEG) temelinde oluşturulan sıkıştırmaya da izin verir. Görüntüler. Aynı zamanda, fotoğrafik görüntüler için sıkıştırma oranı nadiren 2'ye ulaşır, ancak bazı durumlarda garantili bozulma yokluğu talep edilmektedir. ISO / IEC 14495-1 tarafından açıklanan JPEG-LS sıkıştırma yöntemi kullanılarak fark edilir derecede daha yüksek sıkıştırma oranları elde edilebilir; bu, isimlerdeki benzerliğe rağmen, doğrudan JPEG standardı ISO / IEC 10918-1 (ITU T.81 Öneri) (ITU T.87 Tavsiye).

Sözdizimi ve yapı

Bir JPEG dosyası, her biri işaretleyicinin başlangıcını belirten bir 0xFF baytı ve bir bayt tanımlayıcısı ile başlayan bir dizi işaretleyici içerir. Bazı işaretçiler yalnızca bu bayt çiftinden oluşurken, diğerleri, işaretleyicinin bilgi kısmının uzunluğuna sahip iki baytlık bir alandan oluşan ek verileri içerir (bu alanın uzunluğu dahil, ancak eksi başlangıcının iki baytı dahil) işaret, yani 0xFF ve tanımlayıcı) ve verinin kendisi.

Temel JPEG işaretçileri

İşaretleyici	Bayt	Uzunluk	Randevu

Fil 17 Aralık 2013, 02:09

JPEG icat etmek

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

• Öğretici

Başlığından, bunun JPEG algoritmasının tamamen sıradan bir açıklaması olmadığını doğru bir şekilde anladınız (dosya formatını makalede ayrıntılı olarak anlattım). Her şeyden önce, materyali sunmanın seçilen yolu, sadece JPEG hakkında değil, aynı zamanda Fourier dönüşümü ve Huffman kodlaması hakkında da hiçbir şey bilmediğimizi varsayar. Ve genel olarak, derslerden pek bir şey hatırlamı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 algoritmanın yeterince derin ve en önemlisi sezgisel bir anlayışını geliştireceği. Formüller ve matematiksel hesaplamalar - en azından, sadece neler olup bittiğini anlamak için önemli olanlar.

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

Dilerseniz makaleye paralel olarak aynı adımları kendi başınıza da atmanızı öneririm. Yukarıdaki 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 (Yastık) kombinasyonu önerebilirim. Çalışmalarımın neredeyse tamamı (grafikler ve animasyon dahil) bunlar kullanılarak yapıldı.

Dikkat, trafik! Çok sayıda illüstrasyon, grafik ve animasyon (~ 10Mb). İronik bir şekilde, JPEG ile ilgili makalede bu formatta elliden yalnızca 2'si var.

Bilgi sıkıştırma algoritması ne olursa olsun, ilkesi her zaman aynı olacaktır - kalıpları bulmak ve açıklamak. Daha fazla desen, daha fazla artıklık, daha az bilgi. Arşivleyiciler ve kodlayıcılar genellikle belirli bir bilgi türü için "keskinleştirilir" ve bunları nerede bulacaklarını bilirler. Bazı durumlarda, mavi gökyüzü deseni gibi desen hemen görünür. Dijital temsilinin her satırı, düz bir çizgiyle 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, o zaman renkle ilgili herhangi bir sorun olmayacaktır.

Vektör gösterimi

İlk olarak, iki komşu 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. Bunları koordinat düzleminde noktalarla işaretleyelim, böylece X ekseni boyunca noktanın değeri, Y ekseni boyunca - ikincisi - ilk pikselin değeri olur. 256x256 görselimiz için 256 * 256/2 puan alıyoruz:

Noktaların çoğunun y \u003d x doğrusu üzerinde veya yakınında olduğu tahmin edilebilir (ve şekilden görebileceğinizden daha fazlası vardır, çünkü bunlar tekrar tekrar üst üste bindirilmiştir ve dahası, yarı- şeffaf). Öyleyse, 45 ° döndürerek çalışmak daha kolay olacaktır. Bunu yapmak için, onları farklı bir koordinat sisteminde ifade etmeniz gerekir.

Yeni sistemin temel vektörleri açıkça aşağıdaki gibidir: Ortonormal bir sistem elde etmek için ikiye bölünmek zorunda kalıyoruz (temel vektörlerin uzunlukları bire eşittir). Burada, yeni sistemdeki bazı p \u003d (x, y) noktalarının bir nokta (a 0, a 1) olarak temsil edileceği gösterilmiştir. Yeni katsayıları bilerek, eski olanları tersine döndürerek kolayca elde edebiliriz. Açıkçası, ilk (yeni) koordinat ortalamadır ve ikincisi, x ve y arasındaki farktır (ancak 2'nin köküne bölünür). Değerlerden yalnızca birini bırakmanızın istendiğini düşünün: 0 veya 1 (yani, diğerini sıfıra eşitleyin). 0 seçmek daha iyidir, çünkü 1'in değeri muhtemelen sıfıra yakın olacaktır. Görüntüyü yalnızca 0 ile geri yüklersek ne olur:

4x büyütme:

Dürüst olmak gerekirse, bu tür bir sıkıştırma pek etkileyici değil. Resmi üç piksele aynı şekilde bölmek ve bunları üç boyutlu uzayda temsil etmek daha iyidir.

Aynı grafiktir, ancak farklı bakış açılarından. 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ırlatmama izin verin. Böylece, böyle bir temelde genişlediğimizde, 3 değer elde ederiz a 0, a 1, a 2 ve a 0, 1'den daha önemlidir ve a 1, 2'den daha önemlidir. Bir 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 fazla kaybetmeyecek ama değerlerin üçte birinden kurtulacağız. Üçüzlerle yeniden oluşturulmuş görüntüleri karşılaştıralım: (a 0, 0, 0), (a 1, a 2, 0) ve (a 0, a 1, a 2). Son versiyonda, hiçbir şeyi atmadık, bu yüzden orijinalini alıyoruz.

4x büyütme:

İkinci çizim zaten iyi. Keskin alanlar biraz düzleştirilir, ancak genel olarak resim çok iyi korunur. Ve şimdi, aynı şekilde, dörde ayıralım ve dört boyutlu uzayda temeli görsel olarak tanımlayalım ... Ah, peki, evet. Ancak temel vektörlerden birinin ne olacağını tahmin edebilirsiniz: (1,1,1,1) / 2. Bu nedenle, diğerlerini ortaya çıkarmak için dört boyutlu uzayın vektöre (1,1,1,1) dik olan uzay üzerindeki izdüşümüne bakabilirsiniz. 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ürebileceğimizi öğrenmektir, böylece her ai değeri daha az önemlidir öncekilerden. ... Bunu yapabilirsek, o zaman belki de dizinin son değerleri hep birlikte atılabilir. Yukarıdaki deneyimler bunun mümkün olduğunu ima ediyor. Ancak matematiksel bir aygıt olmadan kimse yapamaz.
Yani, puanları yeni bir temele dönüştürmeniz gerekiyor. Ama önce uygun bir temel bulmalısın. İlk eşleştirme deneyine geri dönelim. Genel anlamda ele alacağız. Temel vektörleri tanımladık:

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

veya koordinatlarda:

0 ve 1 bulmak için projelendirmeniz gerekir p açık e 0 ve e Sırasıyla 1. Bunun için iç çarpımı bulmanız gerekir

benzer şekilde:

Koordinatlarda:

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

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

Vektörlerden fonksiyonlara geçiş.

Küçük boyutlu vektörlerle çalışmak uygundur. Bununla birlikte, desenleri büyük bloklarda bulmak istiyoruz, bu nedenle N boyutlu vektörler yerine, görüntüyü temsil eden dizilerle çalışmak daha uygundur. Bu tür dizileri ayrık işlevler olarak adlandıracağım, çünkü aşağıdaki mantık sürekli işlevlere uygulanabilir.
Örneğimize dönersek, sadece iki noktada tanımlanan böyle bir f (i) fonksiyonunu hayal edin: f (0) \u003d x ve f (1) \u003d y. Benzer şekilde, e 0 (i) ve e 1 (i) temel fonksiyonlarını tabanlara göre tanımlarız. e 0 ve e bir . Biz alırız:

Bu çok önemli bir sonuç. Şimdi "bir vektörün birimdik vektörlere genişletilmesi" ifadesinde, "vektör" sözcüğünü "işlev" ile değiştirebilir ve "bir işlevin birimdik işlevlere genişlemesi" tamamen doğru bir ifade elde edebiliriz. Bu kadar yetersiz bir fonksiyona sahip olmamız önemli değil, çünkü aynı mantık, N değerleriyle ayrık bir fonksiyon olarak temsil edilebilen N boyutlu bir vektör için de geçerli. Ve fonksiyonlarla çalışmak, N boyutlu vektörlerden daha nettir. Alternatif olarak, böyle bir işlevi bir vektör olarak temsil edebilirsiniz. Dahası, sıradan bir sürekli fonksiyon sonsuz boyutlu bir vektörle temsil edilebilir, ancak artık Öklid'de değil, Hilbert uzayında. Ama oraya gitmeyeceğiz, sadece ayrık fonksiyonlarla ilgileneceğiz.
Ve bir temel bulma görevimiz, uygun bir birimdik fonksiyonlar sistemi bulma görevine dönüşüyor. Aşağıdaki muhakemede, ona göre genişleyeceğimiz bir dizi temel işlevi zaten 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 süreci vektör formunda temsil edebilirsiniz. Bir işlevi ayrıştırmak için, onu sırayla temel işlevlere "yansıtmanız" gerekir. Vektör anlamında, izdüşümün hesaplanması, orijinal vektörün diğerine minimum yaklaşımını mesafe olarak verir. Mesafenin Pisagor teoremi kullanılarak hesaplandığı akılda tutulduğunda, fonksiyonlar biçiminde benzer bir gösterim, bir fonksiyonun en iyi ortalama kare yaklaşımını diğerine verir. Böylece, her katsayı (k) fonksiyonun "yakınlığını" belirler. Daha biçimsel olarak, k * e (x), l * e (x) arasında f (x) 'e en iyi rms yaklaşımıdır.
Aşağıdaki örnek, bir fonksiyona yalnızca iki nokta yaklaştırma sürecini gösterir. Sağda vektör gösterimi var.

Çiftlere ayırma deneyimizle ilgili olarak, bu iki noktanın (apsis üzerinde 0 ve 1) bir çift bitişik piksel (x, y) olduğunu söyleyebiliriz.
Aynı, ancak animasyonla:

3 nokta alırsak, o zaman üç boyutlu vektörleri düşünmemiz gerekir, ancak yaklaşım daha doğru olacaktır. Ve N değerli ayrık bir fonksiyon için, N boyutlu vektörleri dikkate almak gerekir.
Elde edilen bir dizi katsayıya sahip olmak, karşılık gelen katsayılarla alınan temel işlevleri toplayarak orijinal işlevi kolayca elde edebilir. Bu katsayıların analizi birçok yararlı bilgi sağlayabilir (temele bağlı olarak). Bu hususların özel bir durumu, Fourier serisi genişletme ilkesidir. Sonuçta, akıl yürütmemiz herhangi bir temele uygulanabilir ve bir Fourier serisinde genişlerken, tamamen spesifik olanı alınır.

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

Önceki bölümde, işlevi bileşik olanlara ayırmanın güzel olacağı sonucuna vardık. 19. yüzyılın başlarında Fourier de bunu düşündü. Doğru, rakunlu bir resmi yoktu, bu yüzden metal halka boyunca ısının dağılımını araştırması gerekiyordu. Daha sonra halkanın her noktasındaki sıcaklığı (ve değişimini) farklı dönemlere sahip sinüzoidlerin toplamı olarak ifade etmenin çok uygun olduğunu keşfetti. "Fourier, ikinci harmoniğin birinciden 4 kat daha hızlı bozunduğunu ve daha yüksek mertebelerin harmoniklerinin daha da büyük bir hızla bozunduğunu buldu (okumanızı tavsiye ederim, ilginçtir)."
Genel olarak, kısa süre sonra periyodik işlevlerin dikkat çekici bir şekilde sinüzoidlerin toplamına ayrıştırıldığı ortaya çıktı. Doğada periyodik fonksiyonlarla tanımlanan birçok nesne ve süreç olduğundan, analizleri için güçlü bir araç ortaya çıktı.
Belki de en görünür periyodik süreçlerden biri sestir.

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

Fourier serisini bilmediğim anda bana son fonksiyonun değerlerini verseler ve onları analiz etmek isteselerdi, o zaman kesinlikle bir yitirmiş olurdum ve kayda değer bir şey söyleyemeyecektim. Evet, bir tür işlev, ama orada sipariş edilen bir şey olduğunu nasıl anlayabilirim? Ama son işlevi dinleyeceğimi tahmin etseydim, o zaman kulak gürültünün arasında net bir ton yakalardı. Çok iyi olmasa da, üretim sırasında bu tür parametreleri özel olarak seçtiğim için özet grafiğinde sinyal görsel olarak gürültüye dönüşür. Anladığım kadarıyla, işitme cihazının bunu nasıl yaptığı hala net değil. Ancak son zamanlarda sesi sinüzoidlere ayı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 moda yoldayız.
Neden sinüzoidleri temel almayı denemiyorsunuz? Aslında bunu zaten yaptık. 3 temel vektöre ayrıştırmamızı hatırlayalım ve bunları grafikte gösterelim:

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


Basit bir kontrol, bu vektörlerin çiftler halinde dik, yani dik olduğunu gösterir. Bu, temel olarak kullanılabilecekleri anlamına gelir. Böyle bir temelde dönüşüm yaygın olarak bilinmektedir ve ayrık kosinüs dönüşümü (DCT) olarak adlandırılır. Verilen grafiklerden DCT dönüşüm formülünün nasıl elde edildiğinin açık olduğunu düşünüyorum:

Hala aynı formül: A \u003d EX ikameli bir temele sahip. Belirtilen DCT'nin temel vektörleri (bunlar aynı zamanda E matrisinin satır vektörleridir) ortogonaldir, ancak ortonormal değildir. Ters dönüşüm sırasında bu hatırlanmalıdır (bunun üzerinde durmayacağım, ancak kimin ilgilendiği - sıfır temel vektörü diğerlerinden daha büyük olduğu için 0,5 * a 0 terimi ters DCT'de görünür).
Aşağıdaki örnek, değişen toplamları orijinal değerlere yaklaştırma sürecini gösterir. Her yinelemede, bir sonraki temel bir sonraki katsayı ile çarpılır ve ara toplama eklenir (yani rakun üzerindeki ilk deneylerde olduğu gibi - değerlerin üçte biri, üçte ikisi).

Ancak yine de, böyle bir temeli seçmenin tavsiye edilebilirliğine ilişkin bazı argümanlara rağmen, hala gerçek argümanlar yoktur. Aslında, sesten farklı olarak, bir görüntüyü periyodik işlevlere ayırmanın uygunluğu çok daha az açıktır. Bununla birlikte, görüntü küçük bir alanda bile gerçekten çok tahmin edilemez olabilir. Bu nedenle, resim, ayrıştırmanın anlamlı olması için yeterince küçük parçalara bölünmüştür, ancak çok da küçük değildir. JPEG'de, görüntü 8x8 kareler halinde "dilimlenir". Böyle bir parçanın içinde fotoğraflar genellikle oldukça tekdüzedir: arka plan artı hafif dalgalanmalar. Bu tür alanlara şık bir şekilde sinüzoidler yaklaşmaktadır.
Pekala, diyelim ki bu gerçek aşağı yukarı sezgiseldir. Ancak keskin renk geçişleri hakkında kötü bir his var çünkü yavaş değişen işlevler bizi kurtarmayacaktır. İşlerini yapan çeşitli yüksek frekanslı işlevler eklemeliyiz, ancak yanlarda tek tip bir arka planda görünür. İki zıt alan içeren 256x256 bir resim çekin:

Her satırı DCT kullanarak ayrıştıralım, böylece satır başına 256 katsayı elde edelim.
Sonra sadece ilk n katsayıları bırakıyoruz ve geri kalanını sıfıra eşitliyoruz ve bu nedenle, görüntü yalnızca ilk harmoniklerin bir toplamı olarak sunulacak:

Resimdeki sayı, kalan oranların sayısıdır. İlk görüntüde sadece ortalama kaldı. Bir düşük frekanslı sinüzoid zaten ikinciye eklendi ve bu böyle devam ediyor. Bu arada, sınıra dikkat edin - tüm daha iyi yaklaşımlara rağmen, köşegenin yanında 2 şerit açıkça görülebilir, biri daha hafif, diğeri daha koyu. 4 kez yakınlaştırılan son görüntünün bir kısmı:

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

Fonksiyon süreksizliklerinin yanında görünen bu tümseklerin yüksekliği, fonksiyon terimlerinin sayısındaki artışla azalmayacaktır. Ayrık bir dönüşümde, yalnızca neredeyse tüm katsayılar korunursa kaybolur. Daha doğrusu görünmez hale gelir.
Aşağıdaki örnek, yukarıdaki üçgenlerin ayrışmasına tamamen benzer, ancak gerçek bir rakun üzerinde:


DCT'yi incelerken, yalnızca birkaç ilk (düşük frekanslı) katsayı her zaman yeterli olduğu gibi yanlış bir izlenim edinebilirsiniz. Bu, değerleri önemli ölçüde değişmeyen birçok fotoğraf parçası için geçerlidir. Bununla birlikte, zıt alanların sınırında, değerler hızlı bir şekilde "sıçrayacak" ve hatta son katsayılar büyük olacaktır. Bu nedenle, DCT'nin enerji tasarrufu özelliğini duyduğunuzda, karşılaşılan birçok sinyal türü için geçerli olduğunu, ancak hepsi için geçerli olmadığını göz önünde bulundurun. Örneğin, genişleme katsayıları sonuncusu hariç sıfıra eşit olan ayrık bir fonksiyonun nasıl görüneceğini düşünün. İpucu: Ayrıştırmayı vektör biçiminde düşünün.
Eksikliklere rağmen, seçilen temel gerçek fotoğrafların en iyilerinden biridir. Daha sonra başkalarıyla küçük bir karşılaştırma göreceğiz.

DCT ve diğer her şey

Dürüst olmak gerekirse, dik dönüşümler konusunu incelerken, etraftaki her şeyin harmonik salınımların toplamı olduğu argümanlarına pek ikna olmadım, bu nedenle resimleri sinüzoidlere ayırmak gerekiyor. Ya da belki bazı adım işlevleri daha iyidir? Bu nedenle, DCT'nin gerçek görüntüler üzerindeki optimalliği üzerine yapılan çalışmaların sonuçlarını arıyordum. "Enerji yoğunlaştırması" özelliğinden dolayı pratik uygulamalarda en sık bulunan DCT'dir "gerçeği her yerde yazılır. Bu özellik, maksimum bilgi miktarının ilk katsayılarda bulunduğu anlamına gelir. Ve neden? Bir araştırma yapmak zor değil: kendimizi bir grup farklı resimle, farklı bilinen temellerle donatıyoruz ve farklı sayıda katsayı için gerçek görüntüden standart sapmayı hesaplamaya başlıyoruz. Bu teknikle ilgili makalede (kullanılmış resimler) küçük bir araştırma buldum. Depolanan enerjinin farklı bazlardaki ilk genleşme katsayılarının sayısına bağımlılığının grafiklerini gösterir. Grafiklere bakarsanız, DCT'nin sürekli olarak onurlu ... um ... 3. sırayı aldığına ikna oldunuz. Nasıl yani? KLT dönüşümü nedir? DCT'yi övüyordum ama burada ...

KLT

KLT dışındaki tüm dönüşümler sabit esaslı dönüşümlerdir. Ve KLT'de (Karunen-Loeve dönüşümü) birkaç vektör için en uygun temel hesaplanır. İlk katsayıların tüm vektörler için toplamda en küçük ortalama kare hatasını verecek şekilde hesaplanır. Benzer bir çalışmayı daha önce manuel olarak gerçekleştirdik, temeli görsel olarak belirledik. İlk başta mantıklı bir fikir gibi görünüyor. Örneğin, resmi küçük bölümlere ayırabilir ve her biri için farklı bir temel hesaplayabiliriz. Ancak sadece bu temeli saklama endişesi ortaya çıkmıyor, aynı zamanda onu hesaplama işlemi de oldukça zahmetli. Ve DCT çok az kaybediyor ve ayrıca DCT'nin hızlı dönüştürme algoritmaları var.

DFT

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

Tahmin edebileceğiniz gibi, bu bir tür karmaşık temeli olan ortogonal bir dönüşümdür. Böyle karmaşık bir form her zaman olduğundan biraz daha sık meydana geldiğinden, sonucunu incelemek mantıklıdır.
DCT ayrıştırıldığında herhangi bir saf harmonik sinyalin (tamsayı frekansı ile) bu harmoniğe karşılık gelen yalnızca sıfır olmayan bir katsayı vereceği görünebilir. Durum böyle değildir çünkü frekansa ek olarak bu sinyalin fazı da önemlidir. Örneğin, kosinüslerdeki sinüs genişlemesi (ayrık genişlemeye benzer şekilde) aşağıdaki gibi olacaktır:

Saf bir armonika için çok fazla. Bir sürü başkasını doğurdu. Animasyon, bir sinüzoidin DCT katsayılarını farklı fazlarda gösterir.


Sütunların bir eksen etrafında döndüğü size görünüyorsa, o zaman size görünmüyordu.
Şimdi, işlevi sadece farklı frekansların değil, aynı zamanda bir aşamada kaymış olan sinüzoidlerin toplamına da ayrıştıracağız. Bir kosinüs örneğini kullanarak faz kaymasını dikkate almak daha uygun olacaktır:

Basit bir trigonometrik kimlik önemli bir sonuç verir: faz kayması, cos (b) ve sin (b) katsayıları ile alınan sinüs ve kosinüs toplamı ile değiştirilir. Bu, fonksiyonları sinüslerin ve kosinüslerin toplamına (herhangi bir faz olmadan) ayrıştırabileceğiniz 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. Formülün türevlerini sinüs ve kosinüs yerine koyun, şunu elde ederiz:


Şimdi küçük bir yedek. Alt çizgi, eşlenik bir sayıdır.

Nihai 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 noktalar kümesi (cos (b), sin (b)) bir çemberdir. Böyle bir kayıtta, her bir harmonik hem pozitif hem de negatif frekanslarla ayrışmaya girer. Bu nedenle, Fourier analizinin çeşitli formüllerinde, toplama veya entegrasyon genellikle eksi ile artı sonsuz arasında gerçekleşir. Bu karmaşık formda hesaplamalar yapmak genellikle daha uygundur.
Dönüşüm, sinyali, sinyal alanında bir ila N salınımları olan harmoniklere ayırır. Ancak sinyal alanında örnekleme oranı N'dir. Ve Kotelnikov teoremine göre (Nyquist - Shannon teoremi olarak da bilinir), örnekleme hızı sinyal frekansının en az iki katı olmalıdır. Durum bu değilse, yanlış frekanslı bir sinyalin ortaya çıkmasının etkisi elde edilir:

Kesikli çizgi, yanlış bir şekilde yeniden yapılandırılmış bir sinyali gösterir. Hayatınızda sık sık böyle bir fenomenle karşılaştınız. Örneğin, bir videoda bir arabanın tekerleklerinin komik bir hareketi veya hareli efekt.
Bu, N karmaşık genliklerinin ikinci yarısının başka frekanslardan oluşuyormuş gibi görünmesini sağlar. İkinci yarının bu yanlış armonikleri, birinci yarının ayna görüntüsüdür ve ek bilgi taşımaz. Böylece, N / 2 kosinüs ve N / 2 sinüs (ortogonal bir temel oluşturan) kalır.
Tamam, bir dayanak var. Bileşenleri, sinyal bölgesinde tam sayı salınımları olan harmoniklerdir, bu, harmoniklerin uç değerlerinin eşit olduğu anlamına gelir. Daha doğrusu, son değer tam olarak kenardan alınmadığı için neredeyse eşittirler. Dahası, her harmonik merkezi etrafında neredeyse ayna simetriktir. Tüm bu fenomenler, özellikle kodlama sırasında bizim için önemli olan düşük frekanslarda güçlüdür. Bu da kötüdür çünkü sıkıştırılmış görüntüde blok sınırları fark edilebilir olacaktır. DFT temelini N \u003d 8 ile göstereceğim. İlk 2 sıra kosinüs bileşenleridir, sonuncusu sinüs bileşenleridir:

Bileşenlerin kopyalarının artan sıklıkta görünmesine dikkat edin.

Zihinsel olarak, değerleri başlangıçtaki maksimum değerden sonunda minimuma sorunsuz bir şekilde düşen bir sinyalin nasıl ayrıştırılabileceğini düşünebilirsiniz. Az ya da çok yeterli bir yaklaşım, yalnızca sona yaklaşan harmonikler tarafından yapılabilir ki bu bizim için çok da büyük değildir. Soldaki şekil, tek uçlu bir sinyalin yaklaşık bir değeridir. Sağda - simetrik:


İlkinde işler son derece kötü.
Öyleyse, DCT'deki gibi yapılabilir - frekansları 2 veya daha fazla kez azaltmak, böylece bazı salınımların miktarı kesirli ve sınırlar farklı aşamalarda mı? Daha sonra bileşenler ortogonal olmayacaktır. Ve bu konuda yapabileceğiniz hiçbir şey yok.

DST

DCT'de kosinüsler yerine sinüsler kullanılırsa ne olur? Ayrık Sinüs Dönüşümü (DST) alacağız. Ama bizim sorunumuz için, bunların hepsi ilgi çekicidir, çünkü sinüslerin periyotlarının tamamı ve yarısı sınırlarda sıfıra yakındır. Yani, DFT'deki ile aynı uygunsuz ayrışmayı elde ederiz.

DCT'ye geri dönülüyor

Sınırlarda ne durumda? Tamam. Zıt fazlar 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 kademeli bileşenlerden oluşur.
Haar aynı zamanda ortogonal bir dalgacık dönüşümüdür.
DCT'den daha düşüktür, ancak hesaplanması daha kolaydır.

Yani, kendi dönüşümünüzü ortaya çıkarmak için bir fikriniz var. Hatırla bunu:

1. Temel, ortogonal olmalıdır.
2. Sabit bir temel ile, KLT'yi sıkıştırma kalitesinde yenemezsiniz. Bu arada, gerçek fotoğraflarda, DCT neredeyse olabileceği kadar iyidir.
3. DFT ve DST örneğiyle, sınırları hatırlamanız gerekir.
4. Ve DCT'nin başka bir iyi avantajı olduğunu unutmayın - bileşenlerinin sınırlarının yakınında, türevleri sıfıra eşittir, bu da bitişik bloklar arasındaki geçişin oldukça pürüzsüz olacağı anlamına gelir.
5. Fourier dönüşümleri, kafa kafaya hesaplamanın aksine O (N * logN) karmaşıklığı olan hızlı algoritmalara sahiptir: O (N 2).

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

İki boyutlu dönüşümler

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

3D grafiği:

Her satır için DCT'yi (N \u003d 32) inceleyelim:

Şimdi, gözlerinizi, elde edilen katsayıların her bir sütununda, yani yukarıdan aşağıya doğru gezdirmenizi istiyorum. Amacımızın önemsiz değerleri ortadan kaldırırken değerleri olabildiğince küçük tutmak olduğunu unutmayın. Muhtemelen, elde edilen katsayıların her bir sütununun değerlerinin, orijinal görüntünün değerleri ile aynı şekilde ayrıştırılabileceğini tahmin etmişsinizdir. Ortogonal dönüşüm matrisini seçmede kimse bizi sınırlamaz, ancak bunu tekrar DCT kullanarak yapacağız (N \u003d 8):

(0,0) katsayısı çok büyük olduğu için grafikte 4 kat azalmıştır.
Peki ne oldu?
Sol üst köşe, en önemli katsayıların en önemli açılma 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 az önemli 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.
Sol üst köşeden çapraz olarak sağ alt köşeye geçerseniz katsayıların öneminin azaldığı açıktır. Hangisi daha önemli: (0, 7) veya (7, 0)? Ne anlama geliyorlar ki?
İlk olarak, satırlara göre: A 0 \u003d (EX T) T \u003d XE T (A \u003d EX formülü sütunlar için olduğundan transpoze edilir), sonra sütunlarla: A \u003d EA 0 \u003d EXE T. Dikkatlice hesaplarsanız, formülü alırsınız:

Böylece, vektör sinüzoidlere ayrışırsa, matris cos (ax) * cos (by) formunun işlevlerine dönüşür. JPEG'deki her 8x8 blok, formun 64 işlevinin toplamı olarak temsil edilir:


Wikipedia ve diğer kaynaklar, bu tür işlevleri daha uygun bir biçimde sağlar:

Bu nedenle, (0, 7) veya (7, 0) katsayıları eşit derecede faydalıdır.
Ancak, aslında bu, 64 64 boyutlu tabana tek boyutlu sıradan bir ayrıştırmadır. Yukarıdakilerin tümü yalnızca DCT için değil, aynı zamanda herhangi bir ortogonal ayrıştırma için de geçerlidir. Benzetme yoluyla, genel durumda, N-boyutlu bir ortogonal dönüşüm elde ederiz.
Ve işte rakunun 2 boyutlu dönüşümü (DCT 256x256). Yine sıfırlanmış değerlerle. Sayılar - hepsinin sıfırlanmamış katsayılarının sayısı (sol üst köşedeki üçgen alanda bulunan en önemli değerler kaldı).

Katsayının (0, 0) DC, diğer 63'ün AC olarak adlandırıldığını unutmayın.

Bir blok boyutu seçme

Bir arkadaş soruyor: JPEG'de neden 8x8 bölümleme kullanılıyor? Gönderilen cevaptan:

DCT, bloğa periyodikmiş gibi davranır ve sonuçta ortaya çıkan sıçramayı sınırlarda yeniden yapılandırması gerekir. 64x64 bloklar alırsanız, sınırlarda büyük bir olasılıkla büyük bir sıçrama yaşarsı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 olacaktır.

Gibi, DCT yalnızca periyodik işlevlerde iyi çalışır ve büyük bir boyut alırsanız, büyük olasılıkla bloğun sınırlarında dev bir sıçrama elde edersiniz ve onu örtmek için çok sayıda yüksek frekanslı bileşene ihtiyacınız olacaktır. Bu doğru değil! Bu açıklama DFT'ye çok benziyor, ancak DCT'ye çok benzemiyor, çünkü zaten ilk bileşenlerle bu tür sıçramaları mükemmel şekilde kapsıyor.
Aynı sayfa, büyük bloklara karşı ana argümanlarla birlikte MPEG SSS'den bir cevap sağlar:

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

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


Yatay eksen, ilk sıfırlanmamış katsayıların oranıdır. Dikey - piksellerin orijinalden standart sapması. Olası maksimum sapma, birim olarak alınır. Elbette bir karara varmak için tek bir resim yeterli değildir. Ayrıca, pek doğru davranmıyorum, sadece sıfırlıyorum. Gerçek JPEG'de, niceleme matrisine bağlı olarak, yüksek frekanslı bileşenlerin yalnızca küçük değerleri sıfırlanır. Bu nedenle, aşağıdaki deneyler ve sonuçlar, ilkeleri ve kalıpları yüzeysel olarak ortaya çıkarmayı amaçlamaktadır.
Katsayıların kalan yüzde 25'i ile farklı bloklara bölünmeyi karşılaştırabilirsiniz (soldan sağa, sonra sağdan sola):

Görsel olarak 32x32'den neredeyse ayırt edilemedikleri için büyük bloklar gösterilmemiştir. Şimdi orijinal görüntü ile mutlak farka bakalım (2 kat büyütülür, aksi takdirde hiçbir şey görünmez):

8x8, 4x4'ten daha iyi sonuçlar verir. Boyuttaki daha fazla artış artık açıkça görülebilir bir avantaj sağlamaz. Her ne kadar 8x8 yerine 16x16'yı ciddi olarak düşünsem de: Zorluğu% 33 arttırmak (bir sonraki paragrafta yaklaşık olarak), aynı sayıda katsayı ile küçük ama yine de görünür bir iyileşme sağlar. Bununla birlikte, 8x8 seçimi yeterince makul görünüyor ve belki de altın ortalamadır. JPEG 1991'de yayınlandı. Bu tür bir sıkıştırmanın o zamanki işlemciler için çok zor olduğunu düşünüyorum.

İkinci argüman. Blok boyutunu artırmanın daha fazla hesaplama gerektireceğini unutmayın. Ne kadar olduğunu tahmin edelim. Alnına dönüşümün karmaşıklığı, zaten nasıl olduğunu bildiğimiz gibi: O (N 2), çünkü her katsayı N terimden oluşuyor. Ancak pratikte, verimli bir Hızlı Fourier Dönüşümü (FFT) algoritması kullanılır. Açıklaması bu makalenin kapsamı dışındadır. Karmaşıklığı O (N * logN). İki boyutlu bir ayrıştırma için, onu iki kez N defa kullanmanız gerekir. Dolayısıyla, 2D DCT'nin karmaşıklığı O (N 2 logN) 'dir. Şimdi bir görüntüyü hesaplamanın karmaşıklığını bir blok ve birkaç küçük blokla karşılaştıralım:

• Bir blok (kN) x (kN): O ((kN) 2 log (kN)) \u003d O (k 2 N 2 log (kN))
• k * k blokları N * N: O (k 2 N 2 logN)

Bu, örneğin 64x64 bölümünün 8x8 bölümünün iki katı karmaşık 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 etkileyecektir. 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 uzaklaşmak yeterince hızlı. Artı, sınırın kendisi daha iyi görünecek. Katsayıların sadece dörtte birini içeren çok sayıda kontrast geçişine sahip bir örnekle kontrol edelim:


16x16 blokların distorsiyonu 8x8'den daha fazla genişlese de yazı daha yumuşaktır. Bu nedenle, sadece 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 oranları sıfırlamaktan daha zarif bir çözüm var. Sıfırlanmamış değerler aşırı hassasiyetle saklandığı ve şanssız olanlar arasında oldukça önemli olanlar olabileceği için bu yöntemden memnun değiliz. Çıkış yolu bir kuantizasyon matrisi kullanmaktır. Kayıplar tam da bu aşamada gerçekleşir. 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 alalım ve nicelendirelim. JPEG belirtimi standart bir matris sağlar:


Standart matris, FastStone ve IrfanView'de% 50 kalitelidir. Bu tablo kalite dengesi ve sıkıştırma oranı açısından seçilmiştir. DCT'nin normalize edilmemesi ve ilk değerin olması gerekenden 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 önemli oldukları için daha kabadır. Sanırım şimdi bu tür matrisler nadiren kullanılıyor, çünkü kalitedeki bozulma açıkça fark ediliyor. Hiç kimse tablosunu 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ğerleriyle terime göre çarpılır. Fakat değerleri yuvarladığımız için, orijinal Fourier katsayılarını doğru bir şekilde yeniden oluşturamayacağız. Niceleme sayısı ne kadar büyükse, hata o kadar büyük olur. Bu nedenle, yeniden yapılandırılmış katsayı yalnızca en yakın katsayıdır.
Başka bir örnek:

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


Bu bloğu geri yüklerken, yalnızca ortalama değer artı dikey gradyanı elde ederiz (korunan değer -1 nedeniyle). Ancak bunun için yalnızca iki değer saklanır: 7 ve -1. Durum diğer bloklarla daha iyi değil, işte yeniden yapılandırılmış resim:

Bu arada, yaklaşık% 100 kalite. Tahmin edebileceğiniz gibi, bu durumda niceleme matrisi tamamen birlerden oluşur, yani niceleme gerçekleşmez. Bununla birlikte, katsayıların tam sayıya yuvarlanması nedeniyle orijinal görüntüyü tam olarak geri yükleyemiyoruz. Örneğin, bir rakun piksellerin% 96'sını doğru tuttu ve% 4'ü 1/256 oranında farklılık gösterdi. Elbette bu tür "çarpıklıklar" görsel olarak görülemez.
Ve çeşitli kameraların kuantizasyon matrislerini görebilirsiniz.

Kodlama

Devam etmeden önce, daha basit örnekler kullanarak, elde edilen değerlerin nasıl sıkıştırılabileceğini anlamamız gerekiyor.

Örnek 0 (ısınma için)
Arkadaşınızın evinizde bir liste olan bir kağıt parçasını unuttuğunu ve şimdi sizden bunu telefonda dikte etmenizi istediği bir durumu hayal edin (başka 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ı bir şekilde dikte etmek için özel bir arzunuz yok. Ama sadece iki tane var ve tekrarlanıyorlar. Bu nedenle, bir şekilde ilk iki kelimeyi dikte ediyor ve daha fazla "d9rg3" ün ilk kelime ve "wfr43gt" - ikincisi olarak adlandırılacağını kabul ediyorsunuz. O zaman dikte etmek yeterli olacaktır: 1, 2, 2, 1, 1, 1, 2, 1.

A, B, C ... gibi kelimeleri belirleyip onlara sembol diyeceğiz. Dahası, sembolün altında her şey gizlenebilir: alfabenin bir harfi, bir kelime veya hayvanat bahçesindeki bir su aygırı. Önemli olan, aynı kavramların aynı simgelere karşılık gelmesi ve farklı olanların farklı olanlara karşılık gelmesidir. Görevimiz etkili kodlama (sıkıştırma) olduğundan, bunlar en küçük bilgi temsil birimleri oldukları için bitlerle çalışacağız. Bu nedenle listeyi ABBAAABA olarak yazacağız. "İlk kelime" ve "ikinci kelime" yerine 0 ve 1 bitleri kullanılabilir.Daha sonra ABBAAABA 01100010 (8 bit \u003d 1 bayt) olarak kodlanır.

örnek 1
ABC'yi kodlayın.
3 farklı karakter (A, B, C) 2 olası bit değeriyle (0 ve 1) hiçbir şekilde eşleşemez. 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ı verilecektir. ABC şu şekilde kodlanacaktır: 000110.

Örnek 2
AAAAAABC'yi kodlayın.
Karakter A başına 2 bit kullanmak biraz savurgan görünüyor. Ya böyle denediyseniz:

• C: 00

Kodlu sıra: 000000100.
Açıktır ki, bu dizinin ilk iki bitinin nasıl çözüleceği açık olmadığından bu seçenek uygun değildir: AA olarak mı yoksa C olarak mı? Kodlar arasında bir çeşit ayırıcı kullanmak çok savurgan, bu engeli nasıl aşacağımızı farklı bir şekilde düşüneceğiz. Yani başarısızlık, C kodunun A koduyla başlamasından kaynaklanıyordu, ancak B ve C iki olsa bile A'yı bir bit ile kodlamaya kararlıyız. Bu isteğimizden yola çıkarak A'ya 0 kodunu veriyoruz. Sonra B ve C kodları 0 ile başlayamaz ama 1 ile başlayabilirler:

• B: 10
• C: 11

Dizi şu şekilde kodlanmıştır: 0000001011. Bunu zihinsel olarak çözmeye çalışın. Bunu yapmanın tek bir yolu var.
İ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. Kesin kod çözme için, bir karakter kodu başka herhangi bir karakter koduyla başlayamaz.

Açıkçası, sembollerin sırası önemli değil, biz sadece bunların ortaya çıkma sıklığıyla ilgileniyoruz. Bu nedenle, ağırlık olarak adlandırılan belirli bir sayı, her sembolle ilişkilendirilir. Bir sembolün ağırlığı, meydana gelme oranını yansıtan göreceli bir değer veya sembollerin sayısına eşit mutlak bir değer olabilir. Önemli olan, ağırlıkların sembollerin oluşumuyla orantılı olmasıdır.

Örnek 3
Herhangi bir ağırlığa sahip 4 sembol için genel durumu ele alalım.

• A: pa
• B: pb
• C: bilgisayar
• D: pd

Genellik kaybı olmadan, pa ≥ pb ≥ pc ≥ pd koyun. Uzunluk olarak temelde farklı olan yalnızca iki varyant kodu vardır:


Hangisi tercih edilir? Bunu yapmak için, kodlanmış mesajların alınan uzunluklarını hesaplamanız gerekir:
W1 \u003d 2 * pa + 2 * pb + 2 * bilgisayar + 2 * pd
W2 \u003d pa + 2 * pb + 3 * bilgisayar + 3 * pd
W1, W2'den küçükse (W1-W2<0), то лучше использовать первый вариант:
W1-W2 \u003d pa - (pc + pd)< 0 => pa< pc+pd.
C ve D diğerlerinden daha sık birlikte ortaya çıkarsa, ortak tepe noktaları bir bitlik en kısa kodu alır. Aksi takdirde, bir bit A sembolüne gider. Bu, sembollerin birleşiminin bağımsız bir sembol olarak davrandığı ve gelen sembollerin toplamına eşit bir ağırlığa sahip olduğu anlamına gelir.
Genel olarak, p, oluşumunun kesriyle temsil edilen bir karakterin ağırlığı ise (0'dan 1'e), o zaman en iyi kod uzunluğu s \u003d -log 2 p'dir.
Bunu basit bir durum için ele alalım (onu bir ağaç olarak göstermek kolaydır). Bu nedenle, 2 s karakterini eşit ağırlıklarla (1/2 s) kodlamanız gerekir. Ağırlıkların eşitliğinden dolayı kodların uzunlukları aynı olacaktır. Her karakterin bitlerine ihtiyacı vardır. Dolayısıyla, bir sembolün ağırlığı 1/2 s ise uzunluğu s'dir. Ağırlığı p ile değiştirirsek, s \u003d -log 2 p kodunun uzunluğunu elde ederiz. Bu, bir karakterin diğerinden iki kat daha az sıklıkta ortaya çıkması durumunda, kodunun uzunluğunun bir bit daha uzun olacağı anlamına gelir. Ancak, bir bit eklemenin olası seçeneklerin sayısını ikiye katlamanıza izin verdiğini hatırlarsanız, bu sonuca ulaşmak kolaydır.
Ve bir gözlem daha - en küçük ağırlıklara sahip iki sembol her zaman en büyük ancak eşit kod uzunluklarına sahiptir. Üstelik sonuncusu hariç bitleri aynıdır. Bu doğru değilse, o zaman en az bir kod, öneki kırmadan 1 bit kısaltılabilirdi. Bu, kod ağacındaki en düşük ağırlığa sahip iki karakterin daha yüksek bir seviyede ortak bir ebeveyne sahip olduğu anlamına gelir. Bunu yukarıdaki C ve D örneğinde görebilirsiniz.

Örnek 4
Bir önceki örnekte elde edilen sonuçlara dayanarak aşağıdaki örneği çözmeye çalışalım.

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

Adımlar, yalnızca bir grup kalana kadar tekrar edilir. Her grupta, bir sembole (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). Sembolün (veya grubun) ağırlığı sağda belirtilmiştir.

Katsayıları kodluyoruz

Geri dönüyoruz. Şimdi, her birinde bir şekilde kaydedilmesi gereken 64 katsayılı birçok bloğumuz var. En basit çözüm, faktör başına sabit sayıda bit kullanmaktır - tabii ki talihsiz bir durum. Elde edilen tüm değerlerin bir histogramını oluşturalım (yani, katsayı sayısının değerine bağımlılığı):

Dikkat edin - ölçek logaritmiktir! 200'ü aşan değerlerin birikmesinin nedenini açıklar mısınız? Bunlar DC katsayılarıdır. Diğerlerinden çok farklı oldukları için ayrı ayrı kodlanmaları şaşırtıcı değildir. İşte sadece DC:

Grafiğin şeklinin, piksel çiftlerine ve üçe bölünmesine ilişkin çok erken deneylerden elde edilen grafiklerin şekline benzediğine dikkat edin.
Genel olarak, DC katsayılarının değerleri 0 ila 2047 arasında değişebilir (daha kesin olarak -1024 ila 1023, çünkü JPEG'de 128, DC'den 1024'ün çıkarılmasına karşılık gelen tüm orijinal değerlerden çıkarılır) ve oldukça eşit olarak dağıtılır küçük zirveler ile. Yani Huffman kodlamasının burada pek bir faydası olmayacak. 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 pahalıdır. Daha fazlasını düşünüyoruz.
DC faktörü, bir 8x8 bloğunun ortalama değeridir. Fotoğraflarda sıklıkla bulunan bir gradyan geçişini (mükemmel olmasa da) hayal edin. DC değerlerinin kendileri farklı olacaktır, ancak aritmetik bir ilerlemeyi temsil edeceklerdir. Bu, farklarının aşağı yukarı sabit olacağı anlamına gelir. Bir farklılık histogramı oluşturalım:

Bu daha iyidir, çünkü değerler genellikle sıfır civarında yoğunlaşmıştır (ancak Huffman algoritması yine çok büyük bir ağaç verecektir). Küçük değerler (mutlak değerde) yaygındır, büyük değerler nadirdir. Ve küçük değerler birkaç bit kapladığından (baştaki sıfırları kaldırırsanız), sıkıştırma kurallarından biri iyi takip eder: büyük ağırlıklı karakterlere kısa kodlar atayın (veya tersi). Hala başka bir kurala uymamakla sınırlıyız: kesin kod çözmenin imkansızlığı. Genel olarak, böyle bir sorun şu şekillerde çözülebilir: ayırıcı kodla uğraşın, kodun uzunluğunu belirtin, önek kodlarını kullanın (bunları zaten biliyorsunuz - bu, hiçbir kodun başka bir kodla başlamadığı durumdur). Basit ikinci seçeneğe göre gidelim, yani her katsayı (daha doğrusu komşu olanlar arasındaki fark) şu şekilde yazılacaktır: (uzunluk) (değer), bu plakaya göre:

Yani, pozitif değerler doğrudan ikili gösterimlerinde kodlanır ve negatif değerler aynı şekilde kodlanır, ancak baştaki 1 0 ile değiştirilir. Uzunlukların nasıl kodlanacağına karar verir. 12 olası değer olduğundan, uzunluğu saklamak için 4 bit kullanılabilir. Ancak Huffman kodlamasının daha iyi olduğu yer burasıdır.

Uzunlukları 4 ve 6 olan değerler en çok, bu nedenle en kısa kodları (00 ve 01) aldılar.

Soru ortaya çıkabilir: örneğin neden 9 değeri 1111111 değil de 1111110 koduna sahiptir? Sonuçta, "9" u güvenli bir şekilde daha yüksek bir seviyeye, "0" ın yanında yükseltebilirsiniz. Gerçek şu ki, JPEG'de yalnızca kodlardan oluşan bir kodu kullanamazsınız - bu kod saklıdır.
Bir özellik daha var. Açıklanan Huffman algoritması ile elde edilen kodlar, uzunlukları aynı olsa da bit olarak JPEG'deki kodlarla çakışmayabilir. Huffman algoritması kullanılarak, kodların uzunlukları elde edilir ve kodların kendileri oluşturulur (algoritma basittir - kısa kodlarla başlarlar ve öneki koruyarak bunları tek tek ağaca mümkün olduğunca sola eklerler. Emlak). Örneğin, yukarıdaki ağaç için liste saklanır: 0,2,3,1,1,1,1,1. Ve tabii ki, bir değerler listesi saklanır: 4,6,3,5,7,2,8,1,0,9. Kod çözerken, kodlar aynı şekilde üretilir.

Şimdi sıra geldi. DC'lerin nasıl depolandığını bulduk:
[DC fark uzunluğu için Huffman kodu (bit cinsinden)]
burada DC fark \u003d DC akımı - DC önceki

AC izleme:

Çizim DC farklılıklarının grafiğine çok benzediğinden, prensip aynıdır: [AC uzunluğu için Huffman kodu (bit cinsinden)]. Ama gerçekten değil! Grafikteki ölçek logaritmik olduğundan, sıfır değerlerinin, frekansta bir sonraki 2 değerinden yaklaşık 10 kat daha büyük olduğu hemen fark edilmez. Bu anlaşılabilir bir durum - herkes nicelemeden sağ çıkamadı. Niceleme aşamasında elde edilen değerlerin matrisine geri dönelim (FastStone niceleme matrisini kullanarak,% 90).

Pek çok ardışık sıfır grubu olduğu için, fikir ortaya çıkar - gruptaki yalnızca sıfırların sayısını kaydetmek için. Bu sıkıştırma algoritmasına RLE (Çalışma uzunluğu kodlaması) denir. Geriye "ardışık" geçişin yönünü bulmak için kalır - kim kimin arkasında? Soldan sağa ve yukarıdan aşağıya yazmak çok etkili değildir, çünkü sıfır olmayan katsayılar sol üst köşenin yakınında yoğunlaşır ve sağ alt köşeye ne kadar yakınsa, o kadar fazla sıfır olur.

Bu nedenle, JPEG soldaki şekilde gösterildiği gibi "Zig-zag" adlı bir sıra kullanır. Bu yöntem, sıfır gruplarını iyi ayırt eder. Sağdaki şekil, JPEG ile ilgili olmayan, ancak ilginç bir adla (kanıt) alternatif bir atlama yöntemini gösterir. Taramalı videoyu sıkıştırırken MPEG'de kullanılabilir. Baypas algoritmasının seçimi görüntü kalitesini etkilemez, ancak kodlanmış sıfır gruplarının sayısını artırabilir ve bu da sonuçta dosya boyutunu etkileyebilir.
Kaydımızı değiştirelim. Sıfır olmayan her bir AC - katsayısı için:
[AC'den önceki sıfır sayısı] [AC uzunluğu için Huffman kodu (bit cinsinden)]
Sanırım hemen söyleyeceksiniz - sıfırların sayısı da Huffman tarafından mükemmel bir şekilde kodlanmıştır! Bu çok yakın ve fena olmayan bir cevap. Ancak biraz optimize edebilirsiniz. Öncesinde 7 sıfır bulunan belirli bir AC katsayısına sahip olduğumuzu hayal edin (tabii ki, zikzak sırayla yazarsak). Bu sıfırlar, nicelemeden sağ çıkamayan değerlerin ruhudur. Büyük olasılıkla, katsayımız da kötü bir şekilde hırpalanmış ve küçülmüştür, bu da uzunluğunun kısa olduğu anlamına gelir. Bu, AC'den önceki sıfırların sayısı ve AC'nin uzunluğunun bağımlı miktarlar olduğu anlamına gelir. Dolayısıyla bunu şöyle yazıyorlar:
[Huffman kodu (AC'den önceki sıfır sayısı, AC uzunluğu (bit cinsinden)]
Kodlama algoritması aynı kalır: sık görülen bu çiftler (AC'nin önündeki sıfırların sayısı, AC'nin uzunluğu) kısa kodlar alır ve bunun tersi de geçerlidir.

Bu çiftler ve bir Huffman ağacı için miktarın bağımlılığının bir histogramını oluşturuyoruz.


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

JPEG'de uygulama özellikleri:
Böyle bir çift 1 bayt alır: Sıfırların sayısı için 4 bit ve AC'nin uzunluğu için 4 bit. 4 bit, 0'dan 15'e kadar değerlerdir. AC'nin uzunluğu için, fazlasıyla yeterlidir, ancak 15'ten fazla sıfır olabilir mi? Daha sonra daha fazla çift kullanılır. Örneğin, 20 sıfır için: (15, 0) (5, AC). Yani, 16. sıfır, sıfır olmayan bir katsayı olarak kodlanır. Bloğun sonuna yakın her zaman sıfırlarla dolu olduğundan, son sıfır olmayan katsayıdan sonra (0,0) çifti kullanılır. Kod çözme sırasında karşılaşılırsa, kalan değerler 0'dır.

Kodlanan her bloğun aşağıdaki gibi bir dosyada saklandığını öğrendiniz:
[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ır sayısı, uzunluk AC n]
AC i - sıfır olmayan AC katsayıları.

Renkli görüntü

Renkli bir görüntünün sunulma şekli, seçilen renk modeline bağlıdır. Basit bir çözüm, RGB kullanmak ve görüntünün her renk kanalını ayrı ayrı kodlamaktır. O zaman kodlama gri görüntü kodlamasından farklı olmayacak, sadece iş 3 kat daha fazla. Ancak gözün parlaklıktaki değişikliklere renkten daha duyarlı olduğunu hatırlarsanız görüntü sıkıştırma artırılabilir. Bu, rengin parlaklıktan daha fazla kayıpla saklanabileceği anlamına gelir. RGB'nin ayrı bir parlaklık kanalı yoktur. Her kanalın değerlerinin toplamına bağlıdır. Bu nedenle, bir RGB küpü (bu, tüm olası değerlerin bir temsilidir) köşegen üzerine basitçe "yerleştirilir" - ne kadar yüksekse, o kadar parlak. Ancak bu sınırlı değildir - küp yanlardan hafifçe sıkılır ve bunun yerine paralel bir yüzeye dönüşür, ancak bu sadece gözün özelliklerini hesaba katmak içindir. Örneğin, maviye göre yeşile daha duyarlıdır. YCbCr modeli bu şekilde ortaya çıktı.

(Intel.com üzerinden görüntü)
Y, parlaklık bileşenidir, Cb ve Cr, mavi ve kırmızı renk farkı bileşenleridir. Bu nedenle, görüntüyü daha fazla sıkıştırmak isterlerse, RGB YCbCr'ye dönüştürülür ve Cb ve Cr kanalları yok edilir. Yani, küçük bloklara bölünürler, örneğin 2x2, 4x2, 1x2 ve bir bloğun tüm değerlerinin ortalaması alınır. Ya da başka bir deyişle, bu kanal için görüntü boyutunu dikey ve / veya yatay olarak 2 veya 4 kat azaltı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ı, yani kodlayıcı uygulamasının görüntüyü rastgele renk bileşenlerine (kanallara) bölebilmesi ve her birinin ayrı ayrı kaydedilmesi ilginçtir. Grayscale (1 kanal), YCbCr (3), RGB (3), YCbCrK (4), CMYK (4) kullanıldığının farkındayım. İlk üçü neredeyse herkes tarafından destekleniyor, ancak son 4 kanallılarda sorunlar var. FastStone, GIMP onları doğru şekilde destekliyor ve standart Windows programları, paint.net tüm bilgileri doğru bir şekilde çıkarıyor, ancak daha sonra 4 siyah kanalı atıyorlar, bu yüzden (atmadıklarını söyledi, yorumlarını oku) gösterdiler daha açık bir görüntü. 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 vardır (herhangi bir sürüm) (UPD. Yorumlarda "veya Safari" derler). Makaleyi farklı tarayıcılarda açmayı deneyebilirsiniz.

Ve başka bir şey

Kısaca ek özellikler hakkında.

Aşamalı mod

Elde edilen DCT katsayı tablolarını tabloların toplamına ayıralım (yaklaşık olarak şöyle (DC, -19, -22, 2, 1) \u003d (DC, 0, 0, 0, 0) + (0, -20, -20, 0, 0) + (0, 1, -2, 2, 1)). İlk olarak, tüm ilk terimleri (daha önce öğrendiğimiz gibi: Huffman ve zikzak baypas), sonra ikinciyi vb. Kodluyoruz. Bu numara yavaş bir İnternette kullanışlıdır, çünkü ilk önce yalnızca DC katsayıları yüklenir, bu da bir 8x8 piksellik kaba resim. Ardından rakamı iyileştirmek için yuvarlatılmış AC katsayıları. Sonra onlara kaba düzeltmeler, sonra daha kesin düzeltmeler. Ve bunun gibi. Katsayılar yuvarlanır, çünkü yüklemenin ilk aşamalarında doğruluk çok önemli değildir, ancak yuvarlamanın kodların uzunluğu üzerinde olumlu bir etkisi vardır, çünkü her aşama kendi Huffman tablosunu kullanır.

Kayıpsız mod

Kayıpsız sıkıştırma. DCT no. Üç komşudan 4. noktanın tahmini kullanılır. Tahmin hataları Huffman tarafından kodlanır. Bence hiç olmadığı kadar sık \u200b\u200bkullanılıyor.

Hiyerarik mod

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

Aritmetik kodlama

Huffman'ın algoritması, karakterlerin ağırlığı için en uygun kodları üretir, ancak bu yalnızca kodlarla sabit bir karakter eşleşmesi için geçerlidir. Aritmetiğin böylesine katı bir bağlanması yoktur, bu da kesirli bit sayısına sahip kodların kullanılmasına izin verir. Huffman'a kıyasla dosya boyutunu ortalama% 10 azalttığını iddia ediyor. Patent sorunları nedeniyle yaygın değil, herkes tarafından desteklenmiyor.

Umarım artık JPEG algoritmasını sezgisel olarak anlarsınız. Okuduğunuz için teşekkürler!

UPD
kullanılan yazılımı belirtmek için teklif edildi. Her şeyin mevcut ve ücretsiz olduğunu duyurmaktan memnuniyet duyuyorum:

• Python + NumPy + Matplotlib + PIL (Yastık)... Ana araç. "Matlab ücretsiz alternatif" tarafından bulundu. Ben tavsiye ediyorum! Python'a aşina olmasanız bile, birkaç saat içinde nasıl hesaplamalar yapacağınızı ve güzel grafikler oluşturacağınızı öğreneceksiniz.
• JpegSnoop... Bir jpeg dosyası hakkında ayrıntılı bilgi gösterir.
• yEd... Grafik düzenleyici.
• Inkscape... Huffman algoritması örneği gibi çizimler yaptı. Birkaç ders okudum, çok havalı olduğu ortaya çıktı.
• Daum Denklem Düzenleyicisi... Latex ile pek dost olmadığım için görsel bir formül editörü arıyordum. Daum Equation - Chrome için bir eklenti, bana çok uygun görünüyordu. Fare seçmenin yanı sıra Lateksi düzenleyebilirsiniz.
• FastStone... Onu tanıştırmamıza gerek olduğunu sanmıyorum.
• Picpick... SnagIt'e ücretsiz bir alternatif. Tepsiye oturur, dedikleri yerde ekran görüntüsü alır. Ayrıca cetvel, pipet, iletki vb. Gibi her türlü güzellik.

Etiketler:

• jpeg
• dct
• dft
• fourier
• huffman

Etiket ekle