Canlandırılmış Göz Dizilerinin Bakış Noktası Bağımlı Kodlanması

Abstract

Canlandırılmış (dinamik) göz dizi modelleri 3 boyutlu model yüzeylerinin görselleştirilmesi ile üç boyutlu cisimlerin temsilinde sıklıkla kullanılmaktadır. Canlandırılmış sentetik nesnenin hareketi ve diğer değişimler nesne yüzeyinin değişimi ve hareketi ile ifade edilmektedir. Hareketli göz dizi modellerini ifade etmek için gerekli bit sayısı statik göz modellerine kıyasla oldukça fazladır. Video ve resim sıkıştırma arasındaki fark gibi static göz modellerini sıkıştırma ve dinamik göz dizi modellerini sıkıştırma yöntemleri arasında farklılık doğmaktadır. Bu nedenle dinamik göz dizi modellerinin sıkıştırılması üç boyutlu grafik ile ilgili alanlar için önem taşımaktadır. Bakış noktası tarafından görülen bölgenin belirlenmesi, göz dizi modelleri üzerinde yapıan birçok işlemde kullanılmaktadır. Göz dizi modellerini bilgisayar ortamında görselleştirme ve fizik testleri (nesne çarpışmaları, birbirlerine etkileri gibi) gibi işlemlerde kullanılan bakış noktası tarafından görünürlülük testi işlemi sıkıştırma yöntemleri tarafından da kullanılmaya başlanmıştır. Bakış noktası temelli sıkıştırma, yani belli bir bakış noktasından görünmeyen kısımları kodlamayarak sadece bakış noktasından görünen bölgenin kodlanması, static göz modelleri için yakın zamanlı bazı çalışmalarda ele alınmıştır. Görünmeyen bölgenin kodlanmamasına dayanmayan fakat, yine bakış noktası bağımlı olan ve bakış noktasından görünmeyen kısımları daha az bitle dolayısıyla daha fazla kayıpla kodlayan sıkıştırma yöntemleri incelenmiştir. Bu çalışmalar bakış noktasına görünmeyen bölgeleri tamamen çıkartmamakla birlikte bu bölgeler için harcanan bitleri azaltarak görünür hataları arttırmadan (ama görünmeyen bölgede hataları artmasına sebep olarak) dinamik göz dizi modellerini daha az bitle sıkıştırmaktadır. Bu çalışmada, benzer çalışmalarda da varsayılan, alıcı tarafındaki kullanıcı bakış noktası bilgisinin verici tarafında bilindiği varsayımı kabul edilerek, canlandırılmış göz dizi modellerinin sadece görünen yüzey bölgesindeki düğümlerin kodlanması önerilmiştir. Kodlanan bölgenin sınırlandırılması ile kodlanan düğüm sayısınn basit bir varsayımla yarı yarıya azalacağı varsayılmıştır. Bu bağlamda, bit gereksinimini düşürecek temel varsayım zaman içinde (çerçeveden çerçeveye) bakış noktası tarafından görünen yüzey bölgelerinin büyük değişimler göstermememsidir. Bu varsayım sonucunda ardışık çerçevelerin ikisinde de görünen bölgede kalan düğüm sayısının, ardışık bölgelerde görünür bölgeye giren yada çıkan düğüm sayısından çok büyük olması beklenmektedir. Önerilen sistemde bakış noktasından görünmeyen kısımların atılması sonucunda, önceki çerçevede görünmeyen ancak sıkıştırılmak üzere olan çerçevede görünen bölgeye giren düğümler olacaktır. Bu düğümlerin zamansal öngörü ile kodlanması mümkün olmadığından uzamsal öngörü ile kodlanacaktır. Ayrıca kodlanan göz dizilerinde değişen görünürlülük bilgisinin alıcı tarafına gönderilmesi gerekmektedir. Farklı bir söyleyişle, önerilen sistemde kodlama için gerekli bit miktarını değiştiren üç etken vardır. 1. Sıkıştırılacak olan çerçevede görünmeyen düğümleri kodlamayarak gereken bit miktarı düşürülmektedir. 2. Ardışık çerçevelerde görünürlükteki değişimi belirtmek için bir miktar bit gereklidir. 3. Bir önceki çerçevede görünmeyen, ancak sıkıştırılmakta olan çerçevede görünür olan düğümler bulunmaktadır. Bu düğümler için zamansal olarak ilişkilendirme yapılarak, konumu için daha iyi öngörü yapılmasını sağlayan önceki çerçeveye ait düğümler önceki çerçevede kodlanmamıştır. Bu nedenle, zamansal (çerçeveler arası) ilişkilendirme yapılamaz. Sadece uzamsal ilişkilendirme (çerçeve içi) yapılması, düğüm noktasının mevcut konumu için öngörü hesaplayan algoritmasının performansının düşüşüne sebep olacaktır. Bu performans kaybının sebep olduğu bir miktar bit artışı vardır. İlk iki etken direk olarak bit miktarını etkilemekte ancak üçüncü etken zamansal ve uzamsal öndörü algoritmalarınn performans farkı nedeniyle (kodlanması gereken öngörü hatasının büyümesiyle) dolaylı bir etkisi vardır. Çerçeveler arası görünürlülük değişiminin az olması varsayımımızdan yola çıkarak, ilk maddede açıklanan gerekli bit sayısının düşme miktarının, ikinci ve üçüncü maddelerde açıklanan bit sayısı artışından çok daha büyük olması beklenir. Açıklanan işlemleri gerçekleştirmek için sıkıştırmayı yapan gönderici ve göz dizisini yeniden oluşturan alıcı için aşağıdaki adımlar tanımlanmıştır. Gönderici: 1. Görünülürlüğün saptanması 2. Kodlanacak bölgeleri tanımlama 3. Bölgedeki yüzleri ifade etmek için tek tek ziyaret etme 4. Entropi tabanlı kodlama 5. Öngörü Yöntemleri 6. Sayısal ifade yöntemi (nicelleştirne) 7. Entropi tabanlı kodlama 8. Alıcının uygulayacağı adımları gerçekleştirme 8.1. Ters nicelleştirme işlemi 8.2. Öngörü Yöntemleri 8.3. Alıcının aldığı bilgiyi oluşturma Gönderici birinci adımdan dördüncü adıma kadar, çerçeveler arasındaki görünür alanda oluşan fark bölgeleri kodlamaktadır. Daha sonraki üç adım görünür düğüm noktalarınn kodlanmasını içerir. Son olarak sekizinci adımda alıcı tarafın aldığı bilgilerle oluşturacağı göz dizisini oluşturarak, bir sonraki çerçevede uygulanacak zamansal öngörünün ilişkilendirildiği düğüm bilgilerinin aynı olması sağlanmaktadır. Görünürlülüğün saptanması adımında bakış noktasından düğümlere ışınlar gönderilir. Bu ışınlar ilgili düğümden daha yakında herhangi bir yüzle kesiştiği takdirde, ilgili düğüm bakış noktasından görünmez şeklinde işaretlenir. Bu işlem her düğüm için yapıldığında görünürlülük tamamıyla belirlenmiş olur. Kodlanacak bölgeleri tanımlama ve bu bölgelerdeki yüzleri tek tek ziyaret etme işleminde, önceki adımda görünürlülüğü test edilen yüzlerden hangileri ile ilgili bilgi gönderileceği bir önceki çerçeveye bakılarak karar verilir. Alıcıya bildirilmesi gereken yüzler bir önceki çerçeveden sıkıştırılan çerçeveye geçişte, görünürken görünmez olan yada görünmezken görünür olan bölgelerdir. Bu bölgeler Edgebreaker adlı algoritmanın değiştirilmesiyle oluşturduğumuz algoritma ile işaretler haline getirilir. Yukarıda adım dörtde belirtilen entropi tabanlı kodlama işleminde, önceki adımda oluşturulan işaretler aritmetik kodlama ile kodlanarak her işaretin karşılaşılma olasılığı yardımıyla kodlama için gerekli bit miktarı azaltılır. Uzamsal öngörü için paralelkenar oluşturma yöntemi kullanılır. Bu yöntem kodlanan düğümün, komşu üçgen ile bir paralelkenar oluşturduğu varsayımıyla ilgili düğümün gerçek konumuna yaklaşmayı hedefler. Zamansal öngörü yöntemi olarak önceki çerçeve ile ilişkilendirilmiş ortalama algoritması kullanılır. Bu algoritma konumu tahmin edilmek istenen düğümün komşularının, önceki çerçeve ve şu anki çerçevedeki konumlarının ortalaması alır. Önceki çerçevedeki gerçek konumu ile önceki çerçevedeki ortalamasının farkına, şuanki çerçevedeki ortalamayı ekleyerek gerçek konuma yaklaşmaya çalışır. Bir başka deyişle ortalama yöntemi ile önceki çerçevede elde edilen hatanın şu anki çerçevede elde edilecek hataya çok yakın olduğunu varsayarak bu özelliği kullanır. Öngörü yönteminin sonucu ile gerçek konum arasındaki farkin alıcı tarafına gönderilmesi gerekmektedir. Nicelleştirme adımında, devamlı gerçek sayı olan değerler, sınırlı sayıda tamsayıya çevirilir. Bu işlem belirlenen Δ genişliğindeki tüm değerlerin tek bir tamsayı ile ifade edilmesi ile sağlanır. Bu adımda Δ sayısının büyüklüğü, alıcının aldığı değerdeki geri kazanılamayacak olan hata miktarını belirler. Bu adımın sonunda sınırlı bir tam sayı kümesi oluşur ve bu sayılar entropi tabanlı yöntemle kodlanır. Göndericinin son adımı ise, alıcının kayıplı very ile yapacağı işlemlerin aynısını yaparak, daha sonraki çerçevelerdeki öngörü hesaplarında kullanılacak olan düğüm bilgilerinin gönderici-alıcı taraflarında tamamen aynı olamsını sağlamaktadır. Alıcı: 1. Değişim bölgelerinin alınması 1.1. Entropi tabalı kodlama 1.2. Alınan işaret ile ilgili yüzü ziyaret etme 1.3. Bölgeleri tanımlama 1.4. Görünür bölgeyi oluşturma 2. Düğüm bilgilerinin alınması 2.1. Entropi tabanlı kodlama 2.2. Nicelleştirme işlemini ters çevirme 2.3. Öngörü methodları 3. Çerçevenin alıcı tarafında yeniden oluşturulması Alıcı kısmında ilk işlem, göndericitarafından gönderilen görünür bölgenin değişimi ifade eden işaretleri almadır. Bu alınan işaretler entropi tabanlı kodlama yardımıyla, gönderici tarafında entropi kodlamadan önceki anlamlı işaretlere çevirilir. Bu işaretler ilgili bölgenin yüzlerini bir-bir ifade ederek tanımlar. Bu adım sonunda görünür olan ve olamyan bölgeler tamamıyla belirlenmiş olur. Düğüm bilgilerin alınması ile başlayan işlem, entropi kodlayıcının yardımıyla, gönderici tarafında entropi kodlamadan önceki anlamlı tamsayılara çevirilir. Bu tamsayılar nicelleştirme işlemi ile belirlenmiş bir Δ aralığındaki tüm sayıları temsil ettiğinden, gönderilen değer bu aralığın orta değeri olarak kabul edilir. Bu değer göndericinin öngörü algoritması ile yaptığı yaklaşımın hatası olduğundan, aynı işlemler alıcı tarafında yapılarak, göndericinin (şimdi de alıcının) hesapladığı değer ile toplanır. Bu işlem sonucunda Δ aralığının büyüklüğüne bağlı bir hata payı ile alıcı tarafında düğüm konumu belirlenmiş olur. Yukarıda anlatılan önerdiğimiz sistemin tüm adımları gerçekleştirildiğinde, bir göz dizisinin düğümlerinden sadece görünenlerin, ve düğümler arası bağlılık bilgisinin (düğümlerin üçgen şeklinde ilişkilendirilmesi ile oluşan yüzler) de sadece görünür bölgedeki değişimi ifade edecek kadarını gönderilmesi sağlanmış olur. Önerilen sistem, bakış noktası bağımsız olan, entropi kodlama, nicelleştirme ve öngörü hesapları için aynı yöntemleri kullanan diğer yöntemle karşılaştırılmıştır. Bu karşılaştırma "chicken crossing" adlı 3030 düğüm noktası, 5664 yüzü (üçgen yüzey) ve 400 çerçevesi olan bir dinamik göz dizisi ile yapılmıştır. Karşılaştırmada farklı üç bakış noktasına gore hata miktari – bit miktarı bilgileri bakış noktası bağımsız yöntemle karşılaştırılmıştır. Her bir düğümü ifade ermek için 15 bit harcandığı durumla 3 bit harcandığı durum aralığında birçok değer belirlenmiş ve bu değerlerde, %25 ile %47 arasında sıkıştırma kazanımı olduğu gösterilmiştir. Aynı dinamik göz dizisi için çalışmanın başında yapılan düğümlerin yaklaşık yarısının görünmeyeceği varsayımı test edilmiştir. Bu test sonucunda üç farklı bakış noktası için, bir çerçevede bilgisi kodlanan düğümlerin ortalama sayısı 1598.6 bulunmuştur. Yine aynı dinamik göz dizisi ve üç farklı bakış noktası için görünür bölgeye giren yüzleri beilrmek için göz dizisindeki çerçeve başına 54.5 bit, görünür bölgeden çıkan yüzleri belirtmek için çerçeve başına 51.5 bit harcanmıştır. Bu bölgeleri belirtmek için harcanan bit miktarı düğüm başına hesaplandığında, sırasıyla 0.018, ve 0.017 bulunmakta ve düğüm başına harcanan toplam bit sayısının 3 ile 15 arasında değiştiği dikkate alındığında çok makul bir miktar olduğu ortaya çıkmaktadır. Önerilen sistemin harcadığı bit miktarının sıkıştırılan göz dizisindeki nesnenin çeşitli hareketlerine ve diğer değişimlere göre değişimi bakış noktası bağımsız sıkıştırma ile karşılaştırılmıştır. Sıkıştırılan göz dizisindeki nesnenin faklı hareketlerini ve değişimlerini içeren çerçeveler incelendiğinde, önerilen yöntemin bu durumlara karşı bakış noktası bağımsız yöntem ile benzer cevap verdiği yani sıkıştırma başarılarının benzer şekilde değiştiği görülmüştür. Bu sonuç, önerilen yöntemin, bakış noktası tabanlı olmasına rağmen, hızlı hareketler ve dönme hareketleri gibi değişimlere karşı başarısız olmadığını göstermiştir. Bu çalışmada, önerilen sistemin aynı parametrelere bağlı bakış noktası bağımsız kodlamaya gore %47'e varan sıkıştırma kazanımı olduğu ve göz dizisindeki çeşitli değişimlere karşı olumlu sonuç verdiği başarıyla gösterilmiştir. Sistemin alt adımları olan, entropi kodlama, öngörü hesaplamaları ve nicelleştirme gibi işlemleri yeni önerilecek başka methodlarla değiştirilmesi sonucu sistemin geliştirilmesinin mümkün olduğu açıktır. Görünürlülük tespiti için, fazla işlem zamanı gerektiren ama basit olan ışın-üçgen kesişimi methodu kullanılmıştır. Bu algoritmanın hızlandırılmış alternatifi ile değiştirilmesi sonucunda, önerilen sistem gerçek zamanlı bir uygulama için oldukça uygun bir yöntem olacaktır.

Animated mesh sequence models are popularly used for many visualization of moving synthetic objects in computer simulation, film and game industries. 3D objects are represented by their surface, and all changes are represented by changes in surface. View-dependent processing of 3D meshes are used for many applications like visualization and physical test (such as, collision, impact of objects to others and lightening). View-dependency in compression is relatively new research area. View-dependent compression methods are represented in literature for static meshes. Moreover, some view-dependent methods for mesh sequences are represented. These methods mostly based on coarse quantization or similar methods that reduce bitrate for invisible parts. In our study, we propose a new method that completely removes invisible vertices from coding scheme. For such a purpose, visibility for all vertices must be detected and change in visible region must sent to decoder. We use ray-triangle intersection for visibility detection. Ray triangle intersection creates rays between viewpoint and each vertex. If any face intersects ray in a point near then the tested vertex, then the vertex is flaged as invisible. Otherwise, the vertex is flagged as visible. After detecting visibility, regions (faces), which become visible or invisible currently, must be sent to decoder. For this purpose, a revised version of Edgebreaker is developed. Resulting symbols of the algorithm are encoded with arithmetic coding. Decoder does inverse of each step reversely to recover connectivity of visible regions. Vertices in visible region are predictied with predictors: parallelogram predictor if no temporal reference available and motion vector averaging predictor otherwise. Prediction errors are quantized with uniform deadzone quantizer and encoded with adaptive arithmetic coding. Decoder does inverse of each step reversely to recover geometry (vertex positions) of current frame. We compare our proposed method with viewpoint independent system, which uses same predictor, quantizer and entropy coder. We used proposed method with three viewpoints to compress chicken crossing mesh. Chicken crossing mesh has 3030 vertices, 5664 faces and 400 frames. Our experiments showed that view-dependent coding significantly reduces bitrate (%25 to %47) with compared to viewpoint independent compression. Regions, which become visible or invisible in proceeding frames, are coded with average of 54.5 and 51.5 bits per frame respectively. This concludes their bitrates are 0.018 and 0.017 bit per vertex per frame respectively, which is significantly low with compared to bitrate required to encode geometry (3 to 15 bpvf in our test scope). Proposed system is adaptable to most of predictive methods, quantization methods and entropy coding. Thus, proposed system could be improved by improvement in any of these steps of proposed systems. A simple method ray triangle intersection is used. Ray triangle intersection has high computational complexity. With replacement of visibility detection method and low complexity of all other steps, proposed system is highly applicable to real-time purposes.