Optimize Edilmiş Ardışık Ortalama Niceleme Dönüşümü

Ardışık Ortalama Niceleme Dönüşümü (SMQT) algoritması, verilerin organizasyonunu veya yapısını ortaya çıkaran ve kazanç ve önyargı gibi özellikleri ortadan kaldıran doğrusal olmayan bir dönüşümdür. Ardışık Ortalama Niceleme Dönüşümü başlıklı bir makalede, SMQT “konuşma işleme ve görüntü işlemede uygulanmaktadır”. Algoritma görüntülere uygulandığında “bir görüntüdeki ayrıntılara aşamalı bir odaklanma olarak görülebilir”.

SMQT-based Tone Mapping Operators for High Dynamic Range Images başlıklı başka bir makaleye göre, "gelişmiş ayrıntılara sahip bir görüntü" verecektir. Kağıt, bu dönüşümü bir görüntüye uygulamanın iki tekniğini açıklar.

1. Her pikselin parlaklığına SMQT uygulayın - her pikselin RGB'sinden parlaklığı elde etmek için formülü açıklar.

2. SMQT'yi RGB'nin her kanalına ayrı ayrı uygulayın - ayrı ayrı R, G ve B kanalları için.

Aşağıdaki resim iki tekniğin sonucunu göstermektedir:

İkinci tekniği gece Bruin Tiyatrosu'nun bir resmine uygulayarak, algoritmanın görüntünün ayrıntılarını aşamalı olarak nasıl yakınlaştırdığını ve başlangıçta karanlıkta gizlenen ayrıntıları nasıl ortaya çıkardığını görebiliriz:

Bu yazıda, bu algoritmanın nasıl çalıştığına daha yakından bakacağız ve pratik görüntü işleme uygulamalarında algoritmanın çok daha performanslı olmasını sağlayan basit bir optimizasyonu keşfedeceğiz.

SMQT Algoritması

Orijinal makalede, algoritma soyut bir şekilde açıklanmıştır. SMQT'yi daha iyi anlamak için bazı basit örnekleri inceleyeceğiz.

Aşağıdaki vektöre sahip olduğumuzu varsayalım (bunu bir dizi gibi düşünebilirsiniz):

Renkli bir görüntü söz konusu olduğunda, bunu her biri belirli bir renk kanalını (RGB) temsil eden üç ayrı vektör ve vektörün her bir öğesi karşılık gelen pikselin yoğunluğunu temsil eden üç ayrı vektör olarak düşünebiliriz.

SMQT algoritmasının uygulanmasında yer alan adımlar şunlardır:

1. Bu durumda 29.58 olan vektörün ortalamasını hesaplayın.

2. Vektörü ikiye bölün, sol yarıda 29.58'den küçük veya eşit sayıları ve sağ yarıda daha büyük sayıları bırakarak:

   15	4	0	5	18	32	48	60	64	59	47	31
   0	0	0	0	0	1	1	1	1	1	1	1

   İkinci satır ise her bir değer için oluşturacağımız koddur. 29,58'den küçük veya buna eşit olan değerler kodunda 0 alır ve 29,58'den büyük sayılar 1 alır (bu ikilidir).

3. Şimdi ortaya çıkan her iki vektör de aynı kuralı izleyerek özyinelemeli bir şekilde ayrı ayrı bölünür. Örneğimizde birinci vektörün ortalaması (15 + 4 + 0 + 5 + 18) / 5 = 8.4 ve ikinci vektörün ortalaması (32 + 48 + 60 + 64 + 59 + 47 + 31) / 7 = 48.7. Bu iki vektörün her biri, iki vektöre daha bölünür ve ortalama ile karşılaştırılmasına bağlı olarak her birine ikinci bir kod parçası eklenir. Bu sonuç:

   4	0	5	15	18	32	47	31	48	60	64	59
   00	00	00	01	01	10	10	10	11	11	11	11

   Ortalamadan küçük veya ortalamaya eşit sayılar için (her vektör için) 0 ve ortalamadan büyük sayılar için 1 eklendiğine dikkat edin.

4. Bu algoritma özyinelemeli olarak tekrarlanır:

   0	4	5	15	18	32	31	47	48	60	64	59
   000	001	001	010	011	100	100	101	110	111	111	111

   0	4	5	15	18	31	32	47	48	60	59	64
   0000	0010	0011	0100	0110	1000	1001	1010	1100	1110	1110	1111

   0	4	5	15	18	31	32	47	48	59	60	64
   00000	00100	00110	01000	01100	10000	10010	10100	11000	11100	11101	11110

   Bu noktada her vektörün sadece bir elemanı vardır. Böylece, her ardışık adım için bir 0 eklenecektir, çünkü sayı her zaman kendisine eşit olacaktır (0'ın koşulu, sayının ortalamadan küçük veya ona eşit olması gerektiğidir, ki bu kendisidir).

Şimdiye kadar L=5 bir niceleme düzeyine sahibiz. L=8 kullanacaksak, her koda üç tane 0 eklemeliyiz. Her kodu ikiliden tam sayıya dönüştürmenin sonucu (L=8 için):

Son vektör artan düzende sıralanır. Çıktı vektörünü elde etmek için girdi vektörünün orijinal değerini koduyla değiştirmeliyiz.

Ortaya çıkan vektörde şunlara dikkat edin:

• Kazanç kaldırıldı. Orijinal olanın kazancı 0'dan 64'e kadar olan düşük bir kazanıma sahipti. Şimdi kazancı 0'dan 240'a çıkıyor, bu da neredeyse 8 bitlik aralığın tamamına tekabül ediyor. Kazancın kaldırıldığı söylenir, çünkü orijinal vektörün tüm öğelerini 2 gibi bir sayı ile çarpmamız veya hepsini 2'ye bölmemiz önemli değil, çıktı vektörü aşağı yukarı aynı olacaktır. Aralığı, hedef vektörün tüm aralığı hakkında olacaktır (L=8 için 8 bit). Girdi vektörünü iki ile çarparsak, çıktı vektörü aslında aynı olacaktır, çünkü her adımda ortalamanın altında veya üstünde olan aynı sayılar bunun altında veya üstünde olmaya devam edecek ve aynı 0'ları veya 1'leri ekleyeceğiz. çıktıya. Sadece bölersek sonuç aşağı yukarı aynı olur ve tam olarak aynı olmaz çünkü 15 gibi tek sayıların yuvarlanması gerekecek ve o zaman hesaplamalar değişebilir. Tüm aralığı kullanarak, pikselleri koyu renklerden (0) daha açık renklere (240) kadar değişen bir karanlık görüntüden bir görüntüye geçtik.
• Bu örnekte tam olarak gözlemleyemesek de, yanlılık kaldırılmıştır. Bunun nedeni, en düşük değerimiz 0 olduğu için bir önyargımız olmamasıdır. Gerçekten bir önyargımız olsaydı, kaldırılırdı. Herhangi bir 'K' sayısını alır ve onu girdi vektörünün her bir elemanına eklersek, her adımda ortalamanın üstündeki ve altındaki sayıların hesaplanması değişmeyecektir. Çıktı yine aynı olacaktır. Bu aynı zamanda, koyu renkten açık renklere kadar değişen görüntüler olamayacak kadar parlak olan görüntüleri de oluşturacaktır.
• Gelişmiş ayrıntılara sahip bir resmimiz var. Attığımız her özyinelemeli adım için aslında ayrıntılara nasıl yakınlaştığımıza ve bu ayrıntıları mümkün olduğunca ortaya çıkararak çıktıyı oluşturduğumuza dikkat edin. Ve bu tekniği her RGB kanalına uygulayacağımız için, her rengin orijinal tonları hakkında bilgi kaybetmekle birlikte, mümkün olduğunca çok ayrıntı ortaya çıkaracağız.

Her noktası R için 8 bit, G için 8 ve B için 8 bit olan bir RGB piksel vektörü gibi bir görüntü verildi; ondan her renk için bir tane olmak üzere üç vektör çıkarabilir ve algoritmayı her vektöre uygulayabiliriz. Daha sonra bu üç çıktı vektöründen RGB vektörünü yeniden oluşturuyoruz ve Bruin Tiyatrosu'nda olduğu gibi SMQT ile işlenmiş görüntüye sahibiz.

karmaşıklık

Algoritma, her niceleme (L) seviyesi için, her vektörün ortalamasını bulmak için ilk geçişte N elemanın incelenmesini ve ardından ikinci bir geçişte, bu N elemanın her birinin aşağıdaki karşılık gelen ortalama ile karşılaştırılması gerektiğini gerektirir. sırayla her vektörü bölmek için. Son olarak, N eleman kendi kodları ile değiştirilmelidir. Bu nedenle algoritmanın karmaşıklığı O((L*2*N) + N) = O((2*L + 1)*N), yani O(L*N).

Kağıttan çıkarılan grafik, O(L*N) karmaşıklığı ile tutarlıdır. L ne kadar düşükse, yaklaşık olarak doğrusal bir şekilde işleme o kadar hızlıdır (saniyede daha fazla kare sayısı). İşlem hızını artırmak için kağıt, L değerlerinin düşürülmesini önermektedir: "daha düşük bir L düzeyi seçmek, işleme hızını düşürmenin doğrudan bir yolu olabilir, ancak görüntü kalitesi düşer".

Gelişim

Burada görüntü kalitesini düşürmeden hızı artırmanın bir yolunu bulacağız. dönüşüm sürecini analiz edeceğiz ve daha hızlı bir algoritma bulacağız. Bu konuda daha eksiksiz bir bakış açısı elde etmek için tekrarlanan sayılarla bir örnek görelim:

Vektörler artık bölünemez ve istenen L'ye ulaşana kadar sıfırlar eklenmelidir.

Basit olması açısından, örnekte görüldüğü gibi girdinin 0'dan 31'e ve çıktının 0'dan 7'ye (L=3) gidebileceğini varsayalım.

İlk vektörün (16 + 25 + 31 + 31 + 25 + 16 + 7 + 1 + 1 + 7) / 10 = 16 ortalamasını hesaplamanın, tüm son vektörün ortalamasını hesaplamakla aynı sonucu verdiğini unutmayın, çünkü öğeleri farklı sırada olan aynı vektör: (1 + 1 + 7 + 7 + 16 + 16 + 25 + 25 + 31 + 31) / 10 = 16.

İkinci adımda, her vektörü özyinelemeli olarak hesaplamalıyız. Böylece ilk 6 eleman ((16 + 16 + 7 + 1 + 1 + 7) / 6 = 8) olan grileştirilmiş girdilerin ortalamasını ve son 4 eleman olan boş girdinin ortalamasını hesaplıyoruz. ((25 + 31 + 31 + 25) / 4 = 28):

Son vektörü, tamamen sıralı olanı kullanırsak, sonuçların aynı olacağına tekrar dikkat edin. İlk 6 element için: ((1 + 1 + 7 + 7 + 16 + 16) / 6 = 8) ve son 4 element için: ((25 + 25 + 31 + 31) / 4 = 28) . Bu sadece bir ekleme olduğu için toplamların sırası önemli değil.

Aynısı bir sonraki adım için de geçerlidir:

Hesaplamalar son vektörle aynıdır: ((7 + 1 + 1 + 7) / 4 = 4) ((1 + 1 + 7 + 7) / 4 = 4)'e eşit olacaktır.

Ve aynısı diğer vektörler ve adımlar için de geçerli olacaktır.

Ortalamanın hesaplanması, aralıktaki elemanların değerlerinin toplamının aralıktaki eleman sayısına bölünmesidir. Bu, tüm bu değerleri önceden hesaplayabileceğimiz ve bu hesaplamayı L kez tekrar etmekten kaçınabileceğimiz anlamına gelir.

Örneğimize FastSMQT algoritması diyeceğimiz şeyi uygulama adımlarını görelim:

1. Aşağıda gördüğünüz gibi 32 sütun ve 3 satırdan oluşan bir tablo oluşturun. Tablodaki ilk satır, tablonun indeksini (0 ila 31) temsil eder ve tablo kodlanırken dahil edilmesi gerekli değildir. Ancak, örneğin takip edilmesini kolaylaştırdığı açıkça gösterilmiştir.

2. Her değerin frekansını sayarak N öğelerini yineleyin. Örneğimizde, 1, 7, 16, 25 ve 31 öğelerinin hepsinin frekansı 2'dir. Diğer tüm öğelerin frekansı 0'dır. Bu adımın karmaşıklığı O(N)'dir.

3. Artık frekans vektörü doldurulduğuna göre, o vektörü yinelememiz gerekiyor (giriş vektörü değil, frekans vektörü). Artık N öğelerini yinelemiyoruz, ancak R (R, 2^L aralığındadır), bu durumda 32 (0 ila 31). Pikselleri işlerken N, milyonlarca (megapiksel) olabilir, ancak R genellikle 256'dır (her renk için bir vektör). Örneğimizde 32. Tablonun aşağıdaki iki satırını aynı anda dolduracağız. Bu satırlardan ilki (tablonun ikincisi) o ana kadarki frekansların toplamına sahip olacaktır. İkincisi (tablonun üçüncüsü), o ana kadar görünen tüm öğelerin değerlerinin toplamına sahip olacaktır.

   Örneğimizde 1'e ulaştığımızda tablonun ikinci satırına 2 koyuyoruz çünkü şimdiye kadar iki tane 1 çıktı. Ayrıca tablonun üçüncü satırına da 2 koyuyoruz çünkü 1+1 = 2. 7'ye ulaşana kadar sonraki konumların her birine bu iki değeri yazmaya devam ediyoruz. ikinci sıranın akümülatörü, çünkü şimdiye kadar 4 sayı çıktı (1, 1, 7, 7). Ve üçüncü satıra 7 + 7 = 14 ekleyerek 2 + 14 = 16 elde ederiz, çünkü 1 + 1 + 7 + 7 = 16. Bu elemanları yinelemeyi bitirene kadar bu algoritmaya devam ederiz. Bu adımın karmaşıklığı, bizim durumumuzda O(32) olan O(2^L)'dir ve RGB piksellerle çalışırken O(256)'dır.

   i	0	1	2	...	6	7	8	...	15	16	17	...	24	25	26	...	30	31
   n	0	2	0	...	0	2	0	...	0	2	0	...	0	2	0	...	0	2
   n-kümülatif	0	2	2	...	2	4	4	...	4	6	6	...	6	8	8	...	8	10
   toplam	0	2	2	...	2	16	16	...	16	48	48	...	48	98	98	...	98	160

4. Bir sonraki adım, frekansı 0 olan elementlere sahip sütunları tablodan çıkarmaktır ve örneği daha net görmek için, göreceğiniz gibi artık alakalı olmadığı için ikinci satırı da kaldıracağız.

   i	1	7	16	25	31
   n	2	4	6	8	10
   toplam	2	16	48	98	160

5. Her adım için hesaplamaları yapmak için son (tamamen sıralanmış) vektörü kullanabileceğimizi ve sonuçların yine aynı olacağını unutmayın. Burada, bu tabloda, önceden yapılmış tüm ön hesaplamaları içeren son vektöre sahip olduğumuzu unutmayın.

   Temel olarak SMQT algoritmasını bu küçük vektör üzerinde yapmamız gerekiyor, ancak bunu başladığımız orijinal vektör üzerinde yapmaktan farklı olarak, bu çok daha kolay olacak.

   İlk önce tüm örneklerin ortalamasını hesaplamamız gerekiyor. Bunu kolayca bulabiliriz: sum[31] / n[31] = 160 / 10 = 16. Böylece tabloyu iki vektöre böldük ve her biri için ikili kodu yazmaya başlıyoruz:

   i	1	7	16	25	31
   n	2	4	6	8	10
   toplam	2	16	48	98	160
   kod	0	0	0	1	1

   Şimdi her vektörü tekrar bölüyoruz. Birinci vektörün ortalaması: toplam[16] / n[16] = 48 / 6 = 8. İkinci vektörün ortalaması ise: (toplam[31] – toplam[16]) / (n[31]'dir. – n[16]) = (160 – 48) / (10 – 6) = 112 / 4 = 28.

   i	1	7	16	25	31
   n	2	4	6	8	10
   toplam	2	16	48	98	160
   kod	00	00	01	10	11

   Bölünecek tek bir vektör kaldı. Ortalama şudur: toplam[7] / n[7] = 16 / 4 = 4.

   i	1	7	16	25	31
   n	2	4	6	8	10
   toplam	2	16	48	98	160
   kod	000	001	010	100	110

   Gördüğünüz gibi, orijinal algoritmayı izlemiş olsaydık, her öğenin kodu aynıdır. Ve SMQT'yi N elemanlı olandan çok daha küçük bir vektör üzerinde yaptık ve ayrıca ortalamayı bulmak için ihtiyaç duyduğumuz tüm değerleri önceden hesapladık, bu yüzden elde edilen vektörü hesaplamak kolay ve hızlı.

   Bu adımın karmaşıklığı, O(L*(2^L)) olup, bir L=8 için ve pratik görüntü işleme ihtiyaçlarında O(8*(256)) = O(2048) = sabittir.

6. Son adım, öğeyi her öğe için koduyla değiştirerek N öğeyi bir kez daha yinelemektir: öğe[i] = kod[i]. Karmaşıklık O(N)'dir. FastSMQT'nin karmaşıklığı O(N) + O(2^L) + O(L*(2^L)) + O(N) = O(2*N) + O((L + 1)*(2'dir) ^L)) = O(N + L*(2^L)) .

paralellik

Her iki algoritma da paralelleştirilebilir, ancak birden fazla vektörün dönüştürülmesi gerekiyorsa, bunun yerine çekirdek başına bir algoritma çalıştırmak daha verimlidir. Örneğin, görüntüleri işlerken, bu üç hesaplamanın her birini paralelleştirmek yerine her bir RGB kanalını farklı bir çekirdekte işleyebiliriz.

SMQT algoritmasını paralelleştirmek için, bir vektörü ikiye böldüğümüzde, eğer bir çekirdek mevcutsa (aslında bir alt vektör mevcut çekirdekte ve diğeri yeni bir çekirdekte) her alt vektörü yeni bir çekirdekte işleyebiliriz. Bu, toplam kullanılabilir çekirdek sayısına ulaşana kadar özyinelemeli olarak yapılabilir. Değerlerin kodlarla değiştirilmesi de paralel olarak yapılabilir.

FastSMQT algoritması da paralelleştirilebilir. İlk adımda, girdi vektörü mevcut çekirdek sayısına (C) bölünmelidir. Bu parçaların her biri için bir frekans sayımı vektörü oluşturulmalı ve paralel olarak doldurulmalıdır. Daha sonra bu vektörlerin değerlerini elde edilen bir frekans vektörüne ekliyoruz. Paralelleştirilebilecek bir sonraki adım, değerleri kodlarıyla değiştirdiğimiz son adımdır. Bunun için paralel olarak yapılabilir.

Karmaşıklık Karşılaştırması

Orijinal SMQT algoritmasının toplam karmaşıklığı, O(L*N) olan O((2*L + 1)*N)'dir.

FastSMQT'nin karmaşıklığı O(N) + O(2^L) + O(L*(2^L)) + O(N) = O(2*N) + O((L + 1)*(2'dir) ^L)) = O(N + L*(2^L))).

Sabit bir L verildiğinde, karmaşıklık her ikisi için de sadece O(N) olur. Ancak N'yi çarpan sabit, FastSMQT için çok daha küçüktür ve göreceğimiz gibi işlem süresinde büyük bir fark yaratır.

Aşağıdaki grafik, görüntü işleme için geçerli olan L=8 için hem SMQT hem de FastSMQT algoritmalarının performansını karşılaştırmaktadır. Grafik, N öğeyi işlemek için geçen süreyi (milisaniye cinsinden) gösterir. L=8 için SMQT'nin karmaşıklığının (sabitlerle) O(17*N), FastSMQT için ise O(2*N + 2304) olduğuna dikkat edin.

N ne kadar büyükse, SMQT'nin görüntüyü işlemesi o kadar uzun sürer. FastSMQT için ise büyüme çok daha yavaş.

Daha da büyük N değerleri için performanstaki fark çok daha belirgindir:

Burada SMQT belirli görüntüleri işlemek için birkaç saniyeye kadar zaman alırken, FastSMQT hala "birkaç milisaniye" alanı içindedir.

Birden fazla çekirdekle (bu durumda iki) bile FastSMQT, yalnızca SMQT'den açıkça üstündür:

FastSMQT, L'ye bağlı değildir. Öte yandan, SMQT, L değerine doğrusal olarak bağlıdır. Örneğin, N = 67108864 ile, SMQT'nin çalışma süresi, artan L değeriyle artarken FastSMQT şunları yapmaz:

Çözüm

Tüm optimizasyon teknikleri, tüm algoritmalar için geçerli değildir ve bir algoritmanın performansını iyileştirmenin anahtarı, genellikle algoritmanın nasıl çalıştığına dair bazı bilgilerde gizlidir. Bu FastSMQT algoritması, değerlerin önceden hesaplanması olanaklarından ve ortalama hesaplamaların doğasından yararlanır. Sonuç olarak, orijinal SMQT'den daha hızlı işlemeye izin verir. Hız, L'nin artışından etkilenmez, ancak L normal 8'den çok daha büyük olamaz çünkü bellek kullanımı 2^L'dir, bu 8 için kabul edilebilir bir 256'dır (sıklık tablomuzdaki sütun sayısı), ancak performans kazancı bariz pratik faydaları vardır.

Hızdaki bu gelişme, MiddleMatter'in algoritmayı düşük ışık koşullarında çekilen resimleri ve videoları iyileştiren bir iOS uygulamasında (ve bir Android uygulamasında) uygulamasına izin verdi. Bu iyileştirme ile, iOS cihazları için çok yavaş olan uygulamada video işleme yapmak mümkün oldu.

SMQT ve FastSMQT algoritmaları için C++ kodu GitHub'da mevcuttur.