Bir Video Codec Bileşeni Yazalım - Bölüm 3: Durağan Görüntüler

Bu serinin önceki bölümlerinde Ayrık Kosinüs Dönüşümü'nü matematiksel tanımından gerçek örneklerdeki uygulamasına kadar öğrendik. Ayrıca DCT'nin frekans alanındaki verileri temsil etme yeteneğinin kayıplı veri sıkıştırmayı nasıl mümkün kıldığını da gördük.

Şimdi bir sonraki adıma geçiyoruz. Sonunda tartıştığımız bu soyut sayı dizilerini ve bunların temsil edebileceği gerçek görüntüleri birleştiren çizgiyi çizeceğiz.

Bu makalenin sonunda gerçek JPEG görüntü sıkıştırma işleminin yaklaşık %80'ini yeniden keşfetmiş olacağız.

Matris

Bir önceki yazımızda 2D-DCT'yi tanıtmıştık. Şimdi bu formülün biraz düzeltilmiş versiyonuna bakalım:

u ve v değişkenleri, DCT kodlu 2B dizideki değerin yatay ve dikey uzaklığını temsil eder. α(x) fonksiyonu, x == 0 ise 1/sqrt(2) ye, aksi halde 1 . Son olarak x ve y , pikselin kaynak görüntüdeki konumunu temsil eder.

Bu açık görünmeyebilir, ancak aynı hesaplama aşağıdaki biçimde bir matris çarpımı olarak temsil edilebilir:

Bu formülasyonda DCT , DCT matrisidir, T , matris aktarımını belirtir ve IMG , kaynak görüntüdür.

Bu işlemin karmaşıklığının kaynak görüntünün boyutuyla orantılı olduğunu unutmayın. Her boyuttaki görüntüleri yönetmek ve işi azaltmak için hesaplamalarımızı 8 x 8 piksellik görüntü bloklarıyla sınırlayacağız.

Gerçek görüntüler daha yüksek çözünürlüğe sahip olma eğiliminde olsa da, bunları birçok bağımsız 8x8 bloktan oluşmuş olarak düşünebiliriz.

İstenilen etkiyi üreten DCT matrisini şu şekilde hesaplıyoruz:

 var dctMatrix: [Float] = Array(repeating: 0.0, count: 8 * 8) for i in 0 ..< 8 { for j in 0 ..< 8 { let a: Float if i == 0 { a = sqrt(1.0 / 8.0) } else { a = sqrt(2.0 / 8.0) } dctMatrix[j * 8 + i] = a * cos((2.0 * Float(j) + 1) * Float(i) * Float.pi / (2.0 * 8)) } }

dctMatrix değeri:

 0.35 0.49 0.46 0.42 0.35 0.28 0.19 0.10 0.35 0.42 0.19 -0.10 -0.35 -0.49 -0.46 -0.28 0.35 0.28 -0.19 -0.49 -0.35 0.10 0.46 0.42 0.35 0.10 -0.46 -0.28 0.35 0.42 -0.19 -0.49 0.35 -0.10 -0.46 0.28 0.35 -0.42 -0.19 0.49 0.35 -0.28 -0.19 0.49 -0.35 -0.10 0.46 -0.42 0.35 -0.42 0.19 0.10 -0.35 0.49 -0.46 0.28 0.35 -0.49 0.46 -0.42 0.35 -0.28 0.19 -0.10

Gördüğünüz gibi bu sadece bir sayı dizisi. Dönüşümü her uyguladığımızda matris değerlerini yeniden hesaplamamıza gerek yoktur, böylece bunları kodumuzda sabit bir dizide tutabiliriz.

Bu kod 8x8 matris çarpımı gerçekleştirir:

 func matrixMul8x8(m1: [Float], m2: [Float], result: inout [Float]) { for i in 0 ..< 8 { for j in 0 ..< 8 { var acc: Float = 0.0 for k in 0 ..< 8 { acc += m1[i * 8 + k] * m2[k * 8 + j] } result[i * 8 + j] = acc } } }

8x8 DCT'yi şu şekilde hesaplıyoruz:

 func dct(_ block: [Float]) -> [Float] { var tmpBlock: [Float] = Array(repeating: 0.0, count: 8 * 8) var resultBlock: [Float] = Array(repeating: 0.0, count: 8 * 8) matrixMul8x8(m1: dctMatrixT, m2: block, result: &tmpBlock) matrixMul8x8(m1: tmpBlock, m2: dctMatrix, result: &resultBlock) return resultBlock }

Ters DCT, normal ve transpoze DCT matrislerinin değiştirilmesiyle basit bir şekilde elde edilebilir:

 func idct(_ block: [Float]) -> [Float] { var tmpBlock: [Float] = Array(repeating: 0.0, count: 8 * 8) var resultBlock: [Float] = Array(repeating: 0.0, count: 8 * 8) matrixMul8x8(m1: dctMatrix, m2: block, result: &tmpBlock) matrixMul8x8(m1: tmpBlock, m2: dctMatrixT, result: &resultBlock) return resultBlock }

Büyük resim

Artık bilgimizi gerçek görüntülere uygulamaya hazırız. Hadi bununla çalışalım:

Bu görüntüyü, her birinin karşılık gelen konumdaki bir pikselin parlaklığını temsil ettiği bir sayı dizisi olarak yükleyen bir koda sahip olduğumuzu hayal edin:

 func loadImage(width: Int, height: Int) -> [Float] { ... }

Görüntünün 256x256 piksel olduğunu varsayarsak, aşağıdaki değerler sol üst köşeye karşılık gelir:

 -2.00 3.00 -7.00 -6.00 -3.00 -5.00 -13.00 -9.00 -2.00 4.00 -7.00 -6.00 -3.00 -5.00 -13.00 -9.00 -3.00 -1.00 -8.00 -7.00 -6.00 -8.00 -14.00 -12.00 -7.00 -13.00 -9.00 -15.00 -15.00 -12.00 -23.00 -22.00 -18.00 -17.00 -11.00 -15.00 -11.00 -14.00 -20.00 -20.00 -21.00 -19.00 -20.00 -20.00 -18.00 -17.00 -19.00 -19.00 -16.00 -17.00 -20.00 -19.00 -17.00 -21.00 -24.00 -21.00 -19.00 -18.00 -20.00 -22.00 -19.00 -25.00 -20.00 -22.00

Matematiksel kolaylık sağlamak için piksel parlaklığını 0.0 ila 255.0 arasında bir sayı olarak ifade etmek yerine 128.0 çıkarırız. Başka bir deyişle değeri 128.0 yerine 0.0 civarında ortalıyoruz.

Daha sonra dct fonksiyonunu görüntünün her 8x8 bloğuna uyguluyoruz:

 let values: [Float] = loadImage() // convert RGB to -128.0 ... 128.0 var destinationValues: [Float] = Array(repeating: 0.0, count: values.count) for j in 0 ..< height / 8 { for i in 0 ..< width / 8 { let block = extractBlock(values: values, width: width, x: i * 8, y: j * 8) let resultBlock: [Float] = dct(block) storeBlock(values: &destinationValues, width: width, block: resultBlock, x: i * 8, y: j * 8) } } storeImage(destinationValues) // convert back to RGB

Sonuç şu görüntü:

Fotoğraf olarak pek tanınmasa da bazı desenler (şapka gibi) hala görülebilmektedir. İlginç bir şekilde çok sayıda siyah piksel var. Aslında piksellerin çoğu siyahtır. 8x8 bloklardan birine yakınlaşalım:

Bu 8x8 blok, frekans alanı temsilinin neyle ilgili olduğunu göstermektedir. Sıfır olmayan değerler bloğun sol üst köşesinde kümelenme eğilimindedir. Sağ alt köşeye doğru ilerledikçe büyük bir değerin çıkma olasılığı önemli ölçüde azalır.

Bu, sol üstteki değerlerin görüntü için daha fazla önem taşıdığını gösterir.

Bunu, sağ alt değerlerden bazılarını 0.0 olarak ayarlayarak ortadan kaldıran bir "sıkıştırma" işlevi yazarak gösterebiliriz:

 func compress(_ block: [Float], level: Int) -> [Float] { var resultBlock: [Float] = block for y in 0 ..< 8 { for x in 0 ..< 8 { if x >= 8 - level || y >= 8 - level { resultBlock[y * 8 + x] = 0.0 } } } return resultBlock }

İşleme döngümüzü ayarladıktan sonra:

 for j in 0 ..< height / 8 { for i in 0 ..< width / 8 { var block = extractBlock(values: values, width: width, x: i * 8, y: j * 8) block = dct(block) block = compress(block, level: 3) block = idct(block) storeBlock(values: &destinationValues, width: width, block: block, x: i * 8, y: j * 8) } }

Bu görüntüyü elde ediyoruz:

Ne olduğunu düşünmek için bir dakikanızı ayırın. Her görüntü bloğu için 64 değerden 39'unu eledik ve yine de orijinaline çok benzeyen bir görüntü ürettik. Bu, yalnızca matrislerin çarpılması ve verilerin deterministik olarak atılmasıyla elde edilen %60'lık bir sıkıştırma oranıdır!

DCT katsayılarının %86'sını attığımız zaman şu olur:

Niceleme

DCT katsayılarını, genellikle 4 baytlık depolama gerektiren kayan nokta sayıları olarak depolamak inanılmaz derecede israf olacaktır. Bunun yerine onları en yakın tam sayıya yuvarlamalıyız. 8x8 bloklar için her değer 2 baytlık bir tam sayı ile temsil edilebilir.

Daha önce incelediğimiz bloğu tekrar gözden geçirelim. (Yuvarlatılmış) sayısal gösterimi şöyledir:

 209 -296 -49 43 -38 22 -6 1 39 24 -37 11 -4 -3 2 6 -15 16 -17 0 13 -4 0 5 16 4 2 4 -6 4 -3 -5 -11 4 -1 3 1 -3 6 3 6 -2 2 4 -2 -2 -4 -1 -6 1 0 1 -1 0 3 -1 0 0 0 0 -1 -1 -2 1

Daha önce görsel olarak da teyit ettiğimiz gibi, sol üst köşeye yakın yerlerde daha büyük değerlerin ortaya çıkma olasılığı daha yüksektir. Ancak her blok bu modeli izlemez. İşte resmimizden başka bir blok:

Bu blok DCT değerlerinin ortak dağılımına uymamaktadır. Sağ alt değerleri körü körüne göz ardı etmeye devam edersek görüntünün bazı kısımlarında daha fazla sıkıştırma kusuru görüntülenebilir. Bunu önlemek için hangi blokların diğerlerinden daha fazla veriye ihtiyaç duyduğuna karar vermemiz gerekiyor.

Basit ama zarif bir çözüm, daha önce keşfettiğimiz kümelenme özelliğinden yararlanır. Buna "kuantizasyon" denir. DCT değerlerimizi farklı katsayılara bölüyoruz. Kolaylık olması açısından her DCT katsayısı için bir değer içeren bir tablo kullanacağız:

 16.50 11.50 10.50 16.50 24.50 40.50 51.50 61.50 12.50 12.50 14.50 19.50 26.50 58.50 60.50 55.50 14.50 13.50 16.50 24.50 40.50 57.50 69.50 56.50 14.50 17.50 22.50 29.50 51.50 87.50 80.50 62.50 18.50 22.50 37.50 56.50 68.50 109.50 103.50 77.50 24.50 35.50 55.50 64.50 81.50 104.50 113.50 92.50 49.50 64.50 78.50 87.50 103.50 121.50 120.50 101.50 72.50 92.50 95.50 98.50 112.50 100.50 103.50 99.50

Daha önemli konumlar daha düşük bölenlere karşılık gelir ve bunun tersi de geçerlidir. Kuantize edilmiş verileri tablodaki katsayılarla çarparak dekuantizasyon adımını gerçekleştiriyoruz.

Bu işlevler sırasıyla kuantizasyon ve dekuantizasyon adımlarını gerçekleştirir:

 func quantize(_ block: [Int], table: [Float]) -> [Int] { var result: [Int] = Array(repeating: 0, count: block.count) for i in 0 ..< block.count { result[i] = Int(round(Float(block[i]) / table[i])) } return result } func dequantize(_ block: [Int], table: [Float]) -> [Float] { var result: [Float] = Array(repeating: 0, count: block.count) for i in 0 ..< block.count { result[i] = Float(block[i]) * table[i] } return result }

Kodumuza kuantizasyon ve dekuantizasyon işlemlerini dahil edelim:

 block = dct(block) var iblock = rounded(block) iblock = quantize(iblock, table: testTable) block = dequantize(iblock, table: testTable) block = idct(block)

İlk blok nicelendiğinde şu şekilde görünür:

 13 -26 -5 3 -2 1 0 0 3 2 -3 1 0 0 0 0 -1 1 -1 0 0 0 0 0 1 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Bu da ikinci blok:

 -5 18 -10 0 1 1 1 0 0 3 1 -2 0 1 0 0 -4 0 1 0 1 1 0 0 -1 0 0 -2 0 0 0 0 0 1 -1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

İkinci blokta sıfırdan farklı değerlerin daha fazla olduğunu fark edeceksiniz. Böylece, niceleme adımı daha yararlı verileri saklamamıza ve geri kalanını atmamıza olanak tanır.

Sonuç ve Sırada Ne Var?

Temel matematikten gerçek görüntüleri kodlama ve kod çözme aşamasına geçtik. DCT'nin rastgele verileri nasıl bir frekans kümesine dönüştürdüğünü ve bazı frekansların diğerlerinden nasıl daha önemli olduğunu görsel olarak gördük.

Temel sıkıştırmaya alıştıktan sonra, depolama gereksinimlerini daha da azaltan niceleme kavramını tanıttık.

Bir sonraki bölümde RGB görüntülere geçeceğiz ve elde edilen verileri daha da sıkıştırmanın yollarını keşfedeceğiz.

Bu makalenin kodunu https://github.com/petertechstories/image-dct adresinde bulabilirsiniz.