Toplanmış alan tablosu

Toplanmış alan tablosu, bir ızgaranın dikdörtgen bir alt kümesindeki değerlerin toplamını hızlı ve verimli bir şekilde oluşturmak için bir veri yapısı ve algoritmadır. Görüntü işleme alanında, bütünleşik görüntü (integral image) olarak da bilinir. 1984 yılında Frank Painter tarafından mipmap'lerle kullanılmak üzere bilgisayar grafiklerine tanıtıldı. Bilgisayarla görmede Lewis^[1] tarafından popüler hale getirildi ve ardından "bütünleşik görüntü" adı verildi. 2001'de Viola-Jones nesne algılama çerçevesinde belirgin bir şekilde kullanıldı. Tarihsel olarak, bu ilke, çok boyutlu olasılık dağılım fonksiyonları çalışmasında, yani ilgili kümülatif dağılım fonksiyonlarından 2D (veya ND) olasılıkların (olasılık dağılımının altındaki alan) hesaplanmasında çok iyi bilinmektedir.^[2]

Algoritma değiştir

Adından da anlaşılacağı gibi, herhangi bir noktadaki değer (x, y) toplanmış alan tablosundaki (x, y)’nin yukarısındaki ve solundaki, kendisi de dahil tüm piksellerin toplamıdır:^[3]^[4] $I(x,y)=\sum _{\begin{smallmatrix}x'\leq x\\y'\leq y\end{smallmatrix}}i(x',y')$

burada $i(x,y)$ , (x, y) noktasındaki piksel değeridir.

Toplanmış alan tablosu, (x, y)’deki toplanmış alan tablosundaki değer yalnızca aşağıdaki ifade olduğundan, görüntü üzerinden tek bir geçişte verimli bir şekilde hesaplanabilir:^[5] $I(x,y)=i(x,y)+I(x,y-1)+I(x-1,y)-I(x-1,y-1)\,$ (Toplanmış matrisin sol üst köşeden hesaplandığına dikkat edin)

Toplanmış alan tablosu veri yapısında/algoritmasında bir toplamın hesaplanmasına ilişkin açıklama

Toplanmış alan tablosu hesaplandıktan sonra, herhangi bir dikdörtgen alan üzerindeki yoğunlukların toplamını değerlendirmek, alan boyutuna bakılmaksızın tam olarak dört dizi referansı gerektirir. Yani, şekildeki gösterim üzerinden ifade edilirse, A = (x₀, y₀), B = (x₁, y₀), C = (x₀, y₁) ve D = (x₁, y₁), A, B, C ve D tarafından oluşturulan dikdörtgendeki i(x, y) toplamı aşağıdaki şekilde hesaplanır:

\sum _{\begin{smallmatrix}x_{0}<x\leq x_{1}\\y_{0}<y\leq y_{1}\end{smallmatrix}}i(x,y)=I(D)+I(A)-I(B)-I(C)

Genişlemeler değiştir

Bu yöntem doğal olarak sürekli alanlara genişletilir.^[2]

Yöntem, yüksek boyutlu görüntülere de genişletilebilir.^[6] Dikdörtgenin köşeleri $x^{p}$ ile $p$ içinde $\{0,1\}^{d}$ , dikdörtgenin içerdiği görüntü değerlerinin toplamı aşağıdaki formülle hesaplanır:

\sum _{p\in \{0,1\}^{d}}(-1)^{d-\|p\|_{1}}I(x^{p})\,

burada $I(x)$ bütünleşik görüntü, $x$ ve $d$ görüntü boyutudur. Gösterim $x^{p}$ örnekte $d=2$ , $A=x^{(0,0)}$ , $B=x^{(1,0)}$ , $C=x^{(1,1)}$ ve $D=x^{(0,1)}$ ye karşılık gelir. Nörogörüntülemede görüntülerin boyutları vardır, örneğin; $d=3$ veya $d=4$ , zaman damgalı voksel veya voksel kullanırken.

Bu yöntem, Phan ve diğerlerinin çalışmasında olduğu gibi yüksek dereceli bütünleşik görüntüye genişletilmiştir.^[7] görüntüdeki yerel bloğun standart sapmasını (varyans), çarpıklığını ve basıklığını hızlı ve verimli bir şekilde hesaplamak için iki, üç veya dört bütünleşik görüntü sağladı. Bu aşağıda detaylandırılmıştır:

Bir bloğun varyansını veya standart sapmasını hesaplamak için iki integral resme ihtiyacımız vardır:

I(x,y)=\sum _{\begin{smallmatrix}x'\leq x\\y'\leq y\end{smallmatrix}}i(x',y')

I^{2}(x,y)=\sum _{\begin{smallmatrix}x'\leq x\\y'\leq y\end{smallmatrix}}i^{2}(x',y')

Varyans aşağıdaki şekilde hesaplanır:

\operatorname {Var} (X)={\frac {1}{n}}\sum _{i=1}^{n}(x_{i}-\mu )^{2}.

$S_{1}$ ve $S_{2}$ sırasıyla $I$ ve $I^{2}$ 'nin $ABCD$ bloğun özetini göstersin. $S_{1}$ ve $S_{2}$ integral görüntü ile hızlı bir şekilde hesaplanır. Şimdi, varyans denklemini şu şekilde değiştirebiliriz:

\operatorname {Var} (X)={\frac {1}{n}}\sum _{i=1}^{n}(x_{i}^{2}-2\cdot \mu \cdot x_{i}+\mu ^{2})={\frac {1}{n}}(\sum _{i=1}^{n}(x_{i})^{2}-2\cdot \sum _{i=1}^{n}(\mu \cdot x_{i})+\sum _{i=1}^{n}(\mu ^{2}))={\frac {1}{n}}(\sum _{i=1}^{n}(x_{i})^{2}-2\cdot \sum _{i=1}^{n}(\mu \cdot x_{i})+n\cdot (\mu ^{2}))

={\frac {1}{n}}(\sum _{i=1}^{n}(x_{i})^{2}-2\cdot \mu \cdot \sum _{i=1}^{n}(x_{i})+n\cdot (\mu ^{2}))={\frac {1}{n}}(S_{2}-2\cdot S_{1}/n\cdot S_{1}+n\cdot ((S_{1}/n)^{2}))={\frac {1}{n}}(S_{2}-(S_{1})^{2}/n)

burada $\mu =S_{1}/n$ ve $S_{2}=\sum _{i=1}^{n}(x_{i}^{2})$ 'dir.

Ortalamanın tahminine benzer ( $\mu$ ) ve varyans ( $Var$ ), bu, sırasıyla görüntünün birinci ve ikinci gücünün integral görüntülerini gerektirir (yani $I,I^{2}$ ); görüntülerin üçüncü ve dördüncü kuvvetlerine yukarıda bahsedilenlere benzer manipülasyonlar yapılabilir (ör. $I^{3}(x,y),I^{4}(x,y)$ .) çarpıklık (skewness) ve basıklığı (kurtosis) elde etmek için.^[7] Ancak, F Shafait ve diğerleri tarafından belirtildiği gibi, yukarıdaki yöntemler için akılda tutulması gereken önemli bir uygulama ayrıntısı,^[8] 32 bitlik tam sayıların kullanılması durumunda yüksek dereceli integral görüntüler için meydana gelen tam sayı taşmasıdır.

Kaynakça değiştir

^ Lewis, J. P. (1995). Fast template matching. Proc. Vision Interface. ss. 120-123.
^ ^a ^b Finkelstein, Amir (2010). Wolfram Demonstration Project"Double Integrals By Summing Values Of Cumulative Distribution Function". 16 Ocak 2011 tarihinde kaynağından arşivlendi. Erişim tarihi: 29 Aralık 2020.
^ Crow, Franklin (1984), "Summed-area tables for texture mapping" (PDF), SIGGRAPH '84: Proceedings of the 11th annual conference on Computer graphics and interactive techniques, ss. 207-212, 4 Haziran 2011 tarihinde kaynağından (PDF) arşivlendi, erişim tarihi: 29 Aralık 2020
^ Viola, Paul; Jones, Michael (2002), "Robust Real-time Object Detection" (PDF), International Journal of Computer Vision, 25 Ocak 2021 tarihinde kaynağından arşivlendi (PDF), erişim tarihi: 29 Aralık 2020
^ Kelly (BADGERATI), Matthew (3 Eylül 2010). computersciencesource.wordpress.com"Computer Vision – The Integral Image". 11 Ocak 2012 tarihinde kaynağından arşivlendi. Erişim tarihi: 13 Şubat 2017.
^ Tapia, Ernesto (Ocak 2011). "A note on the computation of high-dimensional integral images". Pattern Recognition Letters. 32 (2): 197-201. doi:10.1016/j.patrec.2010.10.007.
^ ^a ^b Phan, Thien; Sohoni, Sohum; Larson, Eric C.; Chandler, Damon M. (22 Nisan 2012). Performance-analysis-based acceleration of image quality assessment (PDF). 2012 IEEE Southwest Symposium on Image Analysis and Interpretation. ss. 81-84. CiteSeerX 10.1.1.666.4791 $2. doi:10.1109/SSIAI.2012.6202458. ISBN 978-1-4673-1830-3. 24 Mayıs 2014 tarihinde kaynağından (PDF) arşivlendi. Erişim tarihi: 29 Aralık 2020.
^ Shafait, Faisal; Keysers, Daniel; Breuel, Thomas M. (Ocak 2008). "Efficient implementation of local adaptive thresholding techniques using integral images" (PDF). Electronic Imaging. Document Recognition and Retrieval XV. 6815: 681510-681510-6. CiteSeerX 10.1.1.109.2748 $2. doi:10.1117/12.767755. 15 Aralık 2014 tarihinde kaynağından arşivlendi (PDF). Erişim tarihi: 29 Aralık 2020.

Dış bağlantılar değiştir

Nesne algılamada özet tablo uygulaması 11 Kasım 2020 tarihinde Wayback Machine sitesinde arşivlendi.

Ders videoları

Entegre görüntü algoritmasının arkasındaki teoriye giriş (Youtube Video) 9 Mart 2021 tarihinde Wayback Machine sitesinde arşivlendi.
Wolfram Demonstrations Project'ten entegre görüntü algoritmasının sürekli bir versiyonunun gösterimi (Youtube Video) 4 Temmuz 2015 tarihinde Wayback Machine sitesinde arşivlendi.

İlave okumalar değiştir

Ömer Faruk SÖYLEMEZ, (Ekim 2012), İNSAN YÜZÜ İMGELERİNDE DAİRESEL HOUGH DÖNÜŞÜMÜ KULLANILARAK GÖZ DURUMU TESPİTİ, Fırat Üniversitesi, Yüksek Lisans Tezi, s. 12
Mehmet Emin Tenekeci, Abdülkadir Gümüşçü, Ahmet Baytak, Emrah Aslan, (2014), Görüntüden OpenCV ile Duygu Analizi, Bildiri 31 Ekim 2017 tarihinde Wayback Machine sitesinde arşivlendi.
Gökmen, Muhittin & Bayhan, Mehmet Şerif, (Haziran 2008), Ölçekten Ve Pozdan Bağımsız Gerçek Zamanlı Yüz Bulma Ve İzleme, Yüksek Lisans Tezi

[1] Lewis, J. P. (1995). Fast template matching. Proc. Vision Interface. ss. 120-123.

[Finkelstein2010-2] Finkelstein, Amir (2010). Wolfram Demonstration Project"Double Integrals By Summing Values Of Cumulative Distribution Function". 16 Ocak 2011 tarihinde kaynağından arşivlendi. Erişim tarihi: 29 Aralık 2020.

[3] Crow, Franklin (1984), "Summed-area tables for texture mapping" (PDF), SIGGRAPH '84: Proceedings of the 11th annual conference on Computer graphics and interactive techniques, ss. 207-212, 4 Haziran 2011 tarihinde kaynağından (PDF) arşivlendi, erişim tarihi: 29 Aralık 2020

[4] Viola, Paul; Jones, Michael (2002), "Robust Real-time Object Detection" (PDF), International Journal of Computer Vision, 25 Ocak 2021 tarihinde kaynağından arşivlendi (PDF), erişim tarihi: 29 Aralık 2020

[5] Kelly (BADGERATI), Matthew (3 Eylül 2010). computersciencesource.wordpress.com"Computer Vision – The Integral Image". 11 Ocak 2012 tarihinde kaynağından arşivlendi. Erişim tarihi: 13 Şubat 2017.

[6] Tapia, Ernesto (Ocak 2011). "A note on the computation of high-dimensional integral images". Pattern Recognition Letters. 32 (2): 197-201. doi:10.1016/j.patrec.2010.10.007.

[Phan-April2012-7] Phan, Thien; Sohoni, Sohum; Larson, Eric C.; Chandler, Damon M. (22 Nisan 2012). Performance-analysis-based acceleration of image quality assessment (PDF). 2012 IEEE Southwest Symposium on Image Analysis and Interpretation. ss. 81-84. CiteSeerX 10.1.1.666.4791 $2. doi:10.1109/SSIAI.2012.6202458. ISBN 978-1-4673-1830-3. 24 Mayıs 2014 tarihinde kaynağından (PDF) arşivlendi. Erişim tarihi: 29 Aralık 2020.

[8] Shafait, Faisal; Keysers, Daniel; Breuel, Thomas M. (Ocak 2008). "Efficient implementation of local adaptive thresholding techniques using integral images" (PDF). Electronic Imaging. Document Recognition and Retrieval XV. 6815: 681510-681510-6. CiteSeerX 10.1.1.109.2748 $2. doi:10.1117/12.767755. 15 Aralık 2014 tarihinde kaynağından arşivlendi (PDF). Erişim tarihi: 29 Aralık 2020.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]