3 Boyutlu Sahnelerin Bakış Noktasına Bağımlı Kodlanması

Abstract

Günümüzde bilgisayar grafik teknolojileri giderek yaygınlaşmaktadıtır. Bu teknolojiler üretimden, eğlenceye ve sağlığa kadar farklı alanlarda uygulama olanağı bulmuşlardır. Ancak giderek çoğalan veri sayısı, bu verilerin etkin kodlanmasını zorunlu kılmaktadır. Bilgisayar grafiği teknolojileri arasında çokgen tabanlı, 3 boyutlu yüzey modelleri, matematiksel basitlikleri ve temsil kolaylığı gibi nedenlerle en sık kullanılan araçlardandır. 3 Boyutlu bilgisayar grafikleri teknolojileri sayesinde bir nesnenin birden fazla bak{\i}\c{s} a\c{c}{\i}s{\i} alt{\i}nda g\ or\ ulebilmesi m\ umk\ un olmu\c{s}tur. Herhangi bir veri sıkıştırma yöntemi, verideki istatistiksel ilişkileri ve izleyicinin görsel algılama özelliklerini değerlendirmelidir. Günümüzde veri sıkıştırmanın istatistiksel doğası oldukça iyi anlaşılmış durumdadır ve bu bilgi yeni ve daha güçlü veri sıkıştırma yöntemleri için kullanılmaktadır. Ancak izleyicilerin görsel algılama özelliklerine dayalı çalışmalar nispeten daha seyrektir ve karmaşıklık kaygıları nedeniyle daha az uygulama bulmaktadır. Ancak kesin sonuçlar yerine, yaklaşıklıklar kullanıldığında, bu karmaşıklık sorununu gidermek mümkündür. 3 boyutlu nesneleri temsil etmek için çeşitli yöntemler geliştirilmiştir. Bunlar genel olarak 2 grupta incelenebilir: hacim tabanlı (voxel) olanlar ve yüzey tabanlı olanlar. Yüzey tabanlı nesne temsili, opak nesnelerin sadece dışının görüleceği, dolayısıyla sadece nesnenin dışının çizilmesinin yeterli olduğu fikrine dayanır. Yarı-opak nesneler de çeşitli yaklaşımlar ile bu şekilde modellenebilir. Bu temsil biçimi, özellikle eğlence, eğitim ve prototip geliştirme uygulamalarında yaygın olarak kullanılmaktadır. Çokgen tabanlı modeller arasında, üçgen modeller, basitlikleri ve düzlemselliği garanti etmeleri sebebi ile en sık kullanılır. Bu çalışmada da üçgen tabanlı yüzey modelleri esas alınmıştır. En genel haliyle, 3 boyutlu bir görüntü, herhangi bir bakış noktasından incelenebilir. Bu nedenle, do\u{g}al olarak, \c{c}o\u{g}u veri s{\i}k{\i}\c{s}t{\i}rma metodu bak{\i}\c{s} a\c{c}{\i}s{\i}ndan ba\u{g}{\i}ms{\i}z olarak kaliteyi değerlendirerek eniyileme yapar. Bu en iyileme için genellikle, 3 boyutlu uzaydaki karesel hata kullanılır. Karesel hata basit bir bozunum ölçütüdür, ancak buna rağmen görülen bozunumu belirli bir başarıyla yansıtır. Bu çalışmada da bazı yerlerde karesel hata ölçütünden yararlanılmıştır. Bir nesnenin belirli bak{\i}\c{s} noktalarından g\ or\ ulebilece\u{g}i durumlar da d\ u\c{s}\ un\ ulebilir. Arkaplandaki nesneler ve kamera ile ayn{\i} h{\i}z ve do\u{g}rultuda hareket eden nesneler buna \ ornektir. Bu nesnelerin 3 boyutlu kodlanmas{\i} belirli bak{\i}\c{s} noktalarından izlenmekten çok (bunun için doğrudan 2 boyutlu resmi de kullanılabilir), farkl{\i} ayd{\i}nlatma ko\c{s}ullar{\i}nda ve farkl{\i} nesnelerle ili\c{s}ki i\c{c}inde görselleştirmeye hizmet etmektedir. Bu durumda sıkıştırma yönteminde bakış noktasına uygun eniyileme yapılabilir. Örneğin uzakta olan nesneler daha kaba bir şekilde kodlanırken, yakındaki nesneler daha ayrıntılı ele alınarak basit bir ``hız ataması sağlanabilir. 3 Boyutlu bir sahnede, tel file modelleri s{\i}k{\i}\c{s}t{\i}rmadan \ once ele al{\i}nmas{\i} gereken baz{\i} temel \ on i\c{s}lemler vard{\i}r. Bunlardan en \ onemlisi, sahnede g\ or\ unmeyen y\ uzlerin ve d\ u\u{g}\ umlerin at{\i}lmas{\i}d{\i}r. Bu i\c{s}lem sayesinde, bit b\ ut\c{c}esi sadece g\ or\ unen y\ uzeyler i\c{c}in harcanm{\i}\c{s} olacakt{\i}r. G\ or\ unmeyen y\ uzlerin at{\i}lmas{\i} i\c{c}in, bu Tez de, h{\i}zl{\i} bir {\i}\c{s}{\i}n-\ u\c{c}gen kesi\c{s}imi algoritmas{\i} kullan{\i}lm{\i}\c{s}t{\i}r. Burada her bir düğüme, izleyicinin bakış noktasından bir ışın gönderilir. Bu ışının kestiği en yakın üçgenin, ilgili düğüme komşu olmaması durumunda, o düğüm görünmez olarak işaretlenir. Bir yüzün (çokgen), tüm köşelerinin görünmez olması durumunda o yüz sahneden atılır. Her bir kesi\c{s}im i\c{s}leminin h{\i}zl{\i} olmas{\i}, i\c{s}lem say{\i}s{\i}n{\i}n d\ u\u{g}\ um say{\i}s{\i}na karesel olarak ba\u{g}l{\i} olmas{\i} nedeniyle, toplam i\c{s}lemin k{\i}sa olmas{\i}nı gerektirmez. Özg\ un tel file modeller \ uzerinde \c{c}al{\i}\c{s}an g\ or\ unmeyen y\ uzlerin at{\i}lmas{\i} i\c{s}leminin olduk\c{c}a pahal{\i} olmas{\i} nedeniyle, bu Tez de tel file modelin uygun bir parametrikle\c{s}tirilmesi yoluyla i\c{s}lemi h{\i}zland{\i}ran yeni bir y\ ontem \ onerilmektedir. Burada, açı koruyan bir parametrikleştirme işlemi yardımıyla, ilgili tel file model, daha basit bir tel file model üzerinde parametrik olarak temsil edilir. Böylece bu basit model üzerinde yapılan görünmeyen yüzlerin atılması işlemi sonuçları tekrar (ters fonksiyon aracılığıyla) özgün modele taşınır. A\c{c}{\i} koruyan parametrikle\c{s}tirme i\c{s}lemi sayesinde, \%95 e varan h{\i}z kazanımları g\ ozlemlenmi\c{s}tir. {. I}\c{s}lemin yakla\c{s}{\i}k bir sonu\c{c} vermesi nedeniyle olu\c{s}an hatan{\i}n ise k\ u\c{c}\ uk oldu\u{g}u g\ ozlemlenmi\c{s}tir. Önerilen yöntem, başarım eğrisinde farklı süre-başarım noktaları seçilmesine olanak vermektedir, böylece ihtiyaca göre süre ve başarım performansı ayarlanabilir. Bir\c{c}ok nesnenin bulundu\u{g}u bir sahnenin s{\i}k{\i}\c{s}t{\i}r{\i}lmas{\i} s{\i}ras{\i}nda gerekli bir ba\c{s}ka \ on i\c{s}lem ise sahnenin b\ olgelere ayr{\i}lmas{\i}d{\i}r. Bu i\c{s}lem kodlay{\i}c{\i} karma\c{s}{\i}kl{\i}\u{g}{\i}n{\i} d\ u\c{s}\ ur\ ur ve video kodlamadaki bloklara ay{\i}rma i\c{s}lemine benzetilebilir. Bu i\c{s}lemle birlikte hangi b\ olgenin, toplam bit b\ ut\c{c}esinden ne kadar bit kullanacağı sorusu hız ataması probleminin daha genel bir hali olarak ortaya çıkar. {. I}zleyici konumuna ba\u{g}l{\i} kodlamada ise bu \c{c}ok daha \ onemli bir sorun olur, çünkü bu durumda sahnedeki bölgeler arasındaki algılanabilirlik farkları büyümüştür. Literat\ urde \ onerilen \c{c}e\c{s}itli y\ ontemler bu sorunsala farkl{\i} \c{c}\ oz\ umler getirir. Ancak bu y\ ontemler ya k{\i}s{\i}tl{\i} ko\c{s}ullar alt{\i}nda optimaldir, ya da sezgisel y\ ontemlerdir ve hangi ko\c{s}ullarda optimal olduklar{\i}ndan bahsedilmez. Farkl{\i} görselleştirme ko\c{s}ullar{\i}nda eniyi sonucu verecek genel bir y\ ontem eksiktir. Bu nedenle, bu Tez de \c{s}u temel soruya cevap aranmaktad{\i}r: hem \c{c}ok \c{c}e\c{s}itli ko\c{s}ullarda eniyi olan hem de kaynak kullan{\i}m{\i} a\c{c}{\i}s{\i}ndan ger\c{c}ek\c{c}i s{\i}n{\i}rlarda olan bir y\ ontem m\ umk\ un m\ ud\ ur? . Literat\ urde daha \ once \ onerilen ve bu \c{c}al{\i}\c{s}mada incelenen y\ ontemler aras{\i}nda, ``ekran uzay{\i} ndaki bozunumlar{\i} eniyileyen, en fazla g\ or\ unen k{\i}s{\i}mlar{\i}n 3 Boyutlu karesel hatalar{\i}n{\i} eniyileyen, izleyiciye en yak{\i}n olan k{\i}s{\i}mlar{\i}n 3 Boyutlu karesel hatalar{\i}n{\i} eniyileyen y\ ontemler vard{\i}r. Tez i\c{c}inde, bu y\ ontemlerin h{\i}z ve ba\c{s}ar{\i}mlar{\i} kar\c{s}{\i}la\c{s}t{\i}r{\i}lm{\i}\c{s}, \ ust\ un ve eksik yanlar{\i} g\ osterilmi\c{s}tir. Yukar{\i}da belirtilen sorunun cevab{\i}na varmak i\c{c}in, \ oncelikle literatürdeki y\ ontemler ile bu \c{c}al{\i}\c{s}mada ilk olarak \ onerilen ve hesaplama karma\c{s}{\i}kl{\i}\u{g}{\i} y\ uksek imge tabanl{\i} y\ ontem kar\c{s}{\i}la\c{s}t{\i}r{\i}lm{\i}\c{s}t{\i}r. Literatürdeki baz{\i} y\ ontemlerin olduk\c{c}a h{\i}zl{\i} olabildi\u{g}i g\ ozlemlenirken, \ onerilen y\ ontem ile arada ba\c{s}ar{\i}m fark{\i}n{\i}n bulundu\u{g}u g\ osterilmi\c{s}tir. Bu gözlemler üzerine, hesaplama karmaşıklığı açısından diğer yöntemlerle rekabet edebilecek ama başarım açısından imge tabanlı yönteme yakın bir yöntem tasarlanmıştır. Bu yeni yöntem için en temel gözlem, uzaklık tabanlı hız atama yönteminin oldukça düşük bir hesaplama karmaşıklığı ve yüksek çalışma hızı ile görüntü tabanlı yöntemin sonucuna oldukça yaklaşabilmesidir. Uzaklık tabanlı hız atama yönteminin vardığı çözüm başlangıç noktası kabul edilerek, adım adım, görüntü tabanlı bozunum ölçütüne göre daha iyi sonuçlar elde eden karma bir yöntem önerilmektedir. Yapılan deneyler sonucunda önerilen yöntemin, literatürdeki diğer yöntemlerden üstün olduğu gözlemlenmiştir. Ekte ise yöntemin hangi koşullar altında eniyi sonucu vereceği kuramsal olarak tartışılmıştır.

3 dimensional graphics technology allows one to examine a visual object in many angles. Thus, naturally, many compression methods are optimized without considering the viewpoint and direction of the observer. However, there are many applications in which one can imagine objects in a scene are only examined from particular viewpoints. Background objects and objects that move synchronously with the camera are examples of this scenerio. In this case there is a lot more room for compression, due to not only excluding the invisible parts from the coding process but also the psycho-visual properties of the objects. There have been several methods proposed to exploit these properties and compress the meshes even further. However, these methods are either optimal in very strict conditions or heuristic in nature. Thus, a general purpose method, that would be optimal under various conditions, is lacking. Consequently, the main question to be answered in this Thesis work is is there a method that would optimize the compression directly for the final image while still being computationally practical ? . The road to the answer contains discussion and comparison of the previously proposed methods and a novel rendering based method that is optimal for the final image. This optimality comes at a high cost in terms of computational resources. The balance is achieved by a hybrid method that initially computes an approximate solution in a very fast manner and then refines this solution via the slower but more optimal method. We show that such a method significantly improves the viewpoint dependent compression performance, surpassing the proposed methods in the literature, while being fast enough for practical applications.