‘çalışmalarım’ etiketli içerik

Ticket to Ride, Monopoly ve Tabu’dan sonra en sevdiğim kutu oyunlarından biri oldu diyebilirim. Geçen dönem yapay zeka dersinde bu oyunu oynayan basit bir yapay zekaya sahip oyuncu geliştirmiştik. Her ne kadar prologda kod yazmak pek zevkli olmasa da oyunu oynaması oldukça zevkli diyebilirim.

Oyunda genel amaç Kuzey Amerika’daki şehirleri birbirine bağlamak. Tamamlanan yollar ne kadar uzunsa o kadar puan kazanılıyor, ayrıca tamamlanan hedef kartları ve en uzun bitişik yol için de ayrıca puan kazanılıyor. Oyunun kuralları hakkında detaylı bilgiye aşağıdaki bağlantıdan ulaşılabilir:

[Ticket to Ride Game Rules - pdf]

Arkadaşla birlikte geliştirdiğimiz basit bir yapay zekaya sahip sanal oyuncunun stratejisi ise aşağıdaki gibi özetlenebilir:

Oyun başında 3 hedef kartının 2′li ve 3′lü kombinasyonları için kartların toplam puanının kullanılması gereken minimum vagon sayısına oranı hesaplanarak fayda oranı en yüksek kart kombinasyonu (genellikle birbiriyle örtüşen yollara sahip hedefler) seçiliyor. Sonraki adımda oyuncu hedef şehirleri birbirine  bağlamaya çalışmaya başlıyor ve oyun bitene kadar yeni hedef kartı çekmiyor. (Gerçek oyuncularda yerine göre yeni hedef kartları çekmek daha mantıklı olabilir.) Oyuncunun tamamlayabileceği bir yol mevcutsa öncelikle yolu tamamlıyor, yoksa çekilebilecek vagon kartlarına bakıyor. Yollar tamamlanırken en kısa yol, şehirlerin harita üzerinde kuş uçuşu mesafesini baz alan aç gözlü (greedy) bir arama algoritması ile hızlı bir şekilde hesaplanıyor. Açık vagon kartlarında ihtiyaç duyulan bir renk varsa çekiliyor, yoksa kapalı desteden vagon kartı çekiliyor. Hedef şehirleri bağlamak için planlanan yollardan biri diğer oyuncular tarafından işgal edildiğinde mümkün olan en kısa yollar tekrar hesaplanıyor. Başlangıçtaki hedef kartları tamamlandıktan sonra oyuncu gösteri moduna geçiyor ve diğer oyuncular hedef kartlarını tamamlayamadan oyunu bitirmeyi ve diğer oyuncuların penaltı alarak puan kaybetmesini sağlamayı amaçlıyor. Gösteri modunda oyuncu bir yandan uzunluğu kısa ve kritik olan yolları işgal ederek diğer oyuncuların hedeflerine ulaşmasını zorlaştırmaya çalışırken bir yandan da elindeki vagonları bir an önce tüketerek diğer oyuncuların hedeflerine ulaşmasına fazla vakit bırakmayarak oyunu bitirmeye çalışıyor.

Evet oyunu arkadaşlarınıza karşı oynadığınızda böyle bir strateji izlemek çok mantıklı olmayabilir, ancak oyuncumuzun rakiplerinin de kendi gibi sanal oyuncular olacağı düşünüldüğünde hızlı ve basit bir strateji ile oyunu kazanması mümkün olmaktadır.

Linear Discriminant Analysis (LDA) and Principal Component Analysis (PCA) are widely used methods for linear dimensionality reduction. Due to its supervised nature LDA may perform better than PCA in many cases if the data set is sufficiently large. In literature, various relevance weighted variants of LDA are offered in order to increase the performance on challenging cases on which the original LDA may fail. In this work LDA with different relevance weighting functions is compared with the original LDA and PCA on a synthetically generated data set and three natural data sets which have previously been used for vision-based recognition tasks.

Introduction

Linear discriminant analysis (LDA) is a commonly used method for supervised linear dimensionality reduction on multivariate data in order to obtain lower dimensional data with increased separability. Even though the original LDA is a powerful tool in many cases, it has weaknesses due to its assumptions on data. In the original LDA it is assumed that the distributions of all the classes have the same covariance matrix which is the average of covariance matrices of all classes weighted by their prior probabilities. In this assumption each class including outlier classes affect the common covariance matrix directly proportional with their priori.

In order to achieve a better classification performance on multi-class data, some relevance weighted variants of LDA are proposed with dissimilarity functions using Euclidean distance, Mahalanobis distance (MD), Bayesian classification accuracy function (BA), approximate pairwise accuracy criterion (aPac) [2], Chernoff criterion (CC)[3] and evolutionary weighting algorithms which use these functions as a first generation of iteration [1].

In this study weighted LDA algorithms with different relevance functions will be compared with the original LDA and principal component analysis (PCA) in terms of classification performance on a synthetically generated data set and three natural data sets that have previously been used for hand gesture recognition, fingerspelling recognition and optical character recognition. The classification accuracy is computed by using k-nearest neighbour (k-NN) classifier for different values of k.

Devamını Oku »

Giyim mağazalarında çoğu zaman bir ürünü almadan önce denemek isteriz, peki ya denemek mümkün değilse? Seçeneklerin artması ile denemenin daha zahmetli hale gelmesi bir yana online alışveriş gibi durumlarda denemek hiç mümkün olmayabilir. Bu yazıda geçenlerde geliştirdiğim bir uygulama olan sanal giyinme odasından bahsedeceğim. Uygulamada kullanıcı sanal bir ortamda giysi seçebilmekte ve seçtiği giysileri üzerinde deneyebilmektedir.

Uygulamayı geliştirirken bir görüntü ve derinlik sensörü olan Microsoft Kinect’i ve Microsoft Research tarafından geliştirilen yazılım geliştirme kitini (Kinect SDK) kullandım, uygulamanın çalışma mantığını genel olarak aşağıdaki gibi özetleyebilirim:

• Derinlik ve kullanıcı etiketi verisinden faydalanılarak kullanıcının canlı video akışından çıkarılması (arkaplan silme),
• İstenmeyen örtüşmelerin engellenmesi için ten rengi algılama,
• Giysi modelinin konum ve rotasyonunun eklem noktalarının koordinatlarına göre hizalanması,
• Giysinin eklemler arası uzaklık ve kameradan uzaklık verisinin kullanılarak ölçeklenmesi,
• Modelin kullanıcının üzerinde gösterilmesi.

Ön işlemler: arkaplan silme ve ten rengi algılama

Arkaplan silme bu uygulamada iki açıdan kolaylık sağlamaktadır. Birincisi kullanıcıyı çıkartarak ileriki işlemler için ilgili olan alanı (ROI) belirlememizi sağlamaktadır. Bu sayede ten rengi algılama aşamasında arkaplandaki ten rengine benzer alanların da ten rengi olarak algılanması problemi çözülmüş olmaktadır. İkincisi ise arkaplanı sildiğimizde herhangi istediğimiz bir arkaplanla değiştirerek sanal bir ortam oluşturabiliriz. KinectSDK’nın sağlamış olduğu derinlik ve kullanıcı etiketi verisini kullanarak basit bir maskeleme ile bu işlemi kolayca gerçekleştirebiliriz.

Giysi modeli görüntünün üstüne eklendiğinden kullanıcının hareketi modelin arkasında kısıtlı kalmaktadır. Bu bağlamda ten rengi algılamada istenmeyen örtüşmelerin engellenmesi amaçlanmıştır.  Uygulamada ten rengine sahip alanlar en üst katmana taşınarak model ile örtüşmeleri engellenmektedir. Bu konuda yapılabilecek daha akıllıca bir çözüm derinlik verisinden faydalanarak giysi modeli ile kullanıcının derinlik sıralamasını ayarlamak olabilir. Burada böyle bir yaklaşımı benimsememin tek nedeni daha kolay olmasıydı. Kameradan gelen RGB görüntü YCbCr renk uzayına dönüştürülüp her renk kanalı için basit bir eşikleme uygulanması ten rengi algılamada en basit çözüm olarak kolayca gerçeklenebilir.

Hizalama ve ölçekleme

Kinect SDK ile sağlanan iskeletsel takipçi (skeletal tracker) vücut eklemlerinin 3 boyutlu koordinatlarını yaklaşık olarak vermektedir. Eklemlerin ekrandaki piksel konumları ve birbirleri ile yaptıkları açılardan faydalanılarak giysi modelinin konumlandırılması ve döndürülmesi sağlanmıştır. Omuzlar arası uzaklık, boy uzunluğu ve kullanıcının kameradan uzaklığı değerlendirilerek giysi modeli ölçeklenmiştir.

Daha neler yapılabilir?

Başarım kriterini kullanıcının giysi modeli ile örtüşme oranı olarak belirleyerek uygulamayı farklı koşullar altında test ettiğimizde %83 ortalama başarı oranı elde ettik. İlerleyen aşamalarda 3 boyutlu giysi modelleri ve fizik motoru kullanılarak daha gerçekçi sonuçlar elde edilebilir. Alternatif olarak giysilerin farklı açılardan çekilmiş fotoğrafları kullanılarak sahte 3d izlenimi oluşturulabilir. Örtüşmelerin işlenmesinde daha önce de bahsettiğim gibi renk özellikleri yerine derinlik verisinden faydalanılabilir.

Gelen geribildirimler üzerine şunu da belirtmek istiyorum evet daha önce yapılmış benzer uygulamalar var, zaten bu fikri ilk benim bulduğum gibi bir iddiada bulunmuyorum. Benimkisi ticari olmayan yalnızca deneysel amaçlı bir çalışma.

Daha detaylı bilgi için:
A more detailed report (in English): [ A Real Time Virtual Dressing Room Application using Kinect ]

HSV renk uzayında bildiğimiz gibi renkler renk özü (hue), doygunluk (saturation) ve parlaklık (brightness, value) değerleri ile tanımlılar. Bu uzaydaki renklerin renk ve doygunluk bileşenlerinin özelliklerinden faydalanarak genel amaçlı görüntü sınıflamada kullanabileceğimiz parlaklıktan bağımsız bir özellik çıkarıcı tanımlayabiliriz. Buradaki örnekte bir görselin “şehir”, “yüz”, “doğa”, “ev – dış görünüm”, “ev – iç mekan”, “ofis” ve “deniz” kategorilerinden hangisine ait olduğunu sınıflamaya çalışacağız.

Burada en basit yaklaşım muhtemelen görüntünün tümünün histogramını bir özellik vektörü olarak kullanmak olacaktır. Renk histogramları görüntülerdeki renklerin olasılık dağılımlarını ifade ettiğinden böyle bir özellik vektörü kullandığımızda sınıflama görüntüdeki genel renk dağılımına göre yapılmış olacaktır. Örneğin deniz görüntülerinde mavi tonlarının dağılımı, şehir görüntülerinde gri tonlarının dağılımı ağırlıklı olacağından bu iki kategorideki görüntüleri birbirinden ayırmak zor olmayacaktır.

Bu yaklaşımda yalnızca renk dağılımlarının dikkate alınması ve konumsal herhangi bir bilginin bulunmaması bazı durumlarda dezavantaj oluşturabilir. Bu örneğe baktığımızda bütün dış mekan görüntülerinin (şehir, doğa, ev, deniz) mavi gökyüzüne sahip olması oldukça muhtemel bir durum, bütün dış mekan görüntülerinde mavinin baskın olması bu sınıflara ait görüntülerin ayırt ediciliğinin azalmasına yol açabilir. Bu durumda görüntüleri  eşit sayıda parçalara bölüp her bir bölme için ayrı histogram hesaplayabiliriz.

Örnek olarak her bir görüntüyü 4′e bölüp her bir bölme için hesapladığımız histogramlara ilave olarak tüm görüntünün histogramını da aldığımızda toplam 5 histogramdan oluşan bir  görüntü tanımlayıcısı elde edebiliriz. Her bir histogram için 4 aralık değeri kullandığımızda toplamda 4 (aralık sayısı)*2 (kanal sayısı)*5 (histogram sayısı) = 40 boyutlu bir özellik vektörü elde etmiş oluruz.

Sınıflama için herhangi bir sınıflayıcı kullanabiliriz. Bu örnekte ben bir Destek Vektör Makinası (Support Vector Machine) kütüphanesi olan LIBSVM‘yi kullandım. Google görseller üzerinde yaptığım sınıflama %70 doğruluk oranı ile sonuçlandı.

Bugün neredeyse bütün kamera ve görüntü işleme yazılımlarının sahip olduğu görüntü birleştirme (panoramik çekim) özelliğinin nasıl çalıştığını merak ettiniz mi? Bu yazıda en basit anlamda görüntü birleştirmenin nasıl yapılabileceğine değineceğim, kaynak kodları ve daha detaylı raporu yazının ekinde bulabilirsiniz.

Birleştirilecek görüntüler farklı perspektiflerden çekilmiş olduğundan doğrudan görüntüleri uç uca ekleyerek güzel sonuçlar almamız pek mümkün değil. Bu yüzden ilk olarak görüntülerin perspektiflerini birbirine göre hizalamamız gerekiyor. Neyi neye göre hizalamamız gerektiğini bulmak için öncelikle ardışık iki görüntünün kesiştiği alandaki bazı ortak noktaları buluyoruz.

1. Ortak Noktaların Bulunması

Ortak noktaları SIFT veya SURF gibi çeşitli anahtar nokta tanımlayıcı algoritmalar yardımı ile otomatik olarak bulabiliriz ancak bu örnekte karmaşıklığı artırmamak için noktaları el ile işaretliyoruz. Örneğin iki görüntüde de yer alan binaların köşe noktalarını işaretleyebiliriz.

2. Görüntülerin Hizalanması

İlk görüntüde bulduğumuz ortak noktalardan oluşan matrise X, bu noktalara karşılık gelen ikinci görüntüdeki noktaların koordinatlarından oluşan matrise x diyecek olursak bu noktaları arasında eşleşme yapmamıza olanak sağlayacak “X = Hx” eşitliğini sağlayan bir dönüşüm matrisi (H) bulmamız gerekir (daha detaylı matematiksel açıklama için ekteki rapora bakabilirsiniz).

Dönüşüm matrisini bulduktan sonra ilk görüntüdeki bütün noktaların koordinatlarına bu dönüşümü uygulayarak hizalamadan sonra olması gereken koordinatlarını bulabiliriz. Bu şekilde bir dönüşüm uygulandığında bir bakıma noktalara birebir eşleme yapmış oluyoruz. Bu durumda görüntüdeki toplam nokta sayısı değişmemiş oluyor ve küçük bir görüntüden daha büyük bir görüntüye eşleme yaptığımızda elde edilen piksellerde boşluklar bulunması muhtemel olacaktır. Bu sebeple kaynak görüntüdeki her nokta için yeni değer hesaplamak yerine hedef görüntüdeki her noktanın olması gereken değerini interpolasyon ile hesaplamak (inverse mapping) daha mantıklı olacaktır.

3. Görüntülerin Birleştirilmesi

Görüntüler hizalandıktan sonra birleştirme aşamasında kesişen bölgelerde basitçe iki görüntünün ortalaması alınabilir veya yakın olan görüntünün ağırlığı daha yüksek olacak şekilde ağırlıklı ortalama alınabilir. Bu örnekte daha basit olması için kesişen bölgelerde en parlak pikselin değeri alınmıştır.

Daha detaylı bilgi ve MATLAB kodları için:
More detailed report (in English) and the source code: [Image Stitching /Mosaicing by Furkan Isikdogan]

Zar sayısının, arka plan renginin veya zarların renginin belli olmadığı bir ortamda zarların kaç geldiğini otomatik olarak nasıl algılayabiliriz? Zarların daima açık renklerde olacağını varsayacak olursak akla gelen ilk cevap basit eşikleme uygulamak olabilir. Ancak aşağıdaki temsili histogramdaki gibi arka planın tek renk olmaması ve zar renklerinin arka plan renklerinin arasındaki değerlerde yoğunlaşmış olması probleme yol açacaktır.

Bu durumda zarların masada az yer kapladıklarını varsayarsak görüntüdeki en baskın renklerin arka plan deseni üzerinde yer alan renkler olacağını düşünebilir ve bu renk aralıklarını maskeleyerek zarların temiz görüntüsüne ulaşabiliriz. Ulaşırız demiyorum çünkü bu uygulamanın benim elimdeki veri setinde başarılı sonuçlar vermiş olması her koşulda iyi sonuçlar vereceğini göstermeyebilir.

Önerdiğim algoritmayı aşağıdaki gibi özetleyebiliriz:

- Görüntünün histogramının elde edilmesi,
- Histograma ortalama filtresi uygulanarak ( y[i] = (y[i-1] + y[i] + y[i+1])/3 ) keskinliklerin giderilmesi,
- Histogramda en baskın renklerin bulunması ve bu renklere belirli bir tölerans değerinden daha yakın olan renklerin görüntü üzerinde maskelenmesi,
- Görüntüye adaptif eşitleme uygulanması,
- Elde edilen ikili(binary) görüntüdeki bağlı bileşenlerin bulunması ve her biri içinde kalan boşlukların sayılması.

Çıktı: {5,2}

Not: Soldaki temsili histogram sağdaki görüntülere ait değildir.

Elde edilen bağlı bileşenlerin bize zarları vereceğini ve içlerinde kalan boşluk sayılarının da zarların kaç geldiğini vereceğini düşünürsek görüntüde kaç tane zar olduğunu ve her birinin kaç geldiğini bulabiliriz.

Edit: Ön işleme aşamasında baskın renklerin maskelenmesi yerine Biliteral Filter (Photoshop’taki adıyla Surface Blur) kullanmak bu problemde daha iyi sonuçlar veriyor.

Polonya’daki stajımın son haftasında bilim günü isimli etkinlikte küçük çocuklar için sergilenmek üzere kamera kontrollü küçük bir oyun geliştirdim. Oyunu kullanıcı etkileşimi ve oyun mantığı olmak üzere iki bölümde inceleyebiliriz.

Kullanıcı Etkileşimi
Oyun kontrolünün farklı renklerde başlıklar giyen oyuncuların kuş bakışı bir kameradan alınan görüntüleri aracılığıyla sağlanması amaçlanmaktadır. Ancak test aşamasında kullanım kolaylığı nedeniyle normal kamera ve kullanıcıları temsilen renkli işaretçiler kullanılmıştır.

Her kullanıcı için bir renk aralığı tanımlanmakta ve bu aralığa göre eşikleme uygulanmaktadır. Elde edilen görüntünün ağırlık merkezi bulunarak kullanıcının konumu belirlenmektedir. Ağırlık merkezinin x ve y koordinat değerleri görüntü momentleri kullanılarak bulunabilir. Aşağıdaki formülde I(x,y) görüntünün (x,y) koordinatlarına karşılık gelen piksel değerini ifade etmektedir.

Position(x) = M₁₀/M₀₀
Position(y) = M₀₁/M₀₀

Oyun Mantığı
Oyunda kullanıcılar, oyun nesneleri ve bunların ilişkileri aşağıdaki oyun kuralları çerçevesinde tasarlanmıştır:
(1) Her oyuncu yalnızca kendi rengindeki bayrakları alabilir ve her bayrak için bir puan değeri oyun başlangıcında tanımlanabilmektedir. (2) Bomba ikonu bütün kullanıcılar tarafından alınabilmektedir ve alınması durumunda bütün diğer oyuncular kurulum sırasında tanımlanmış değer kadar puan kaybetmektedirler. (3) Her nesne için belirli bir zaman aşımı bulunmaktadır ve hiçbir oyuncu tarafından yakalanmayan nesneler tanımlanan süre sonunda kaybolmaktadır.

Bu arada telif hakları problem olmasın diye oyun grafiklerini de kendim tasarladım.

PSNC’deki 3. haftamın sonunda tamamladığım bu proje ile kamera görüş alanı içerisinde hareket eden öğelerin tespit edilmesi ve her ögenin kendi tanımlayıcı numarası ile takip edilmesi sağlanıyor. Bir önceki projemde olduğu gibi bu uygulamayı da Java ile OpenCV kütüphanesi arasında bir köprü niteliğinde olan JavaCV sarmalayıcısını kullanarak geliştirdim. Projenin temel işleyiş biçimini aşağıdaki başlıklar altında özetleyebiliriz.

Mevcut anlık görüntü içerisinde nesne bulma (Blob Detection)
Anlık görüntü içerisinde hareket eden cisimlerin bulunması için uygulanan yöntemler;
Mixture of Gaussians yaklaşımı ile dinamik arkaplan çıkarımı,
Elde edilen görüntünün eşikleme uygulanarak binary görüntüye dönüştürülmesi,
Biçimsel işlemler ile gürültünün giderilmesi ve nesne içi kopuklukların kapatılması,
Bağlı bileşenlerin bulunması ve çevreleyen dikdörtgenlerin elde edilmesi şeklinde özetlenebilir.

Bulunan nesnelerin bir önceki anlık görüntü ile ilişkilendirilmesi
Videonun ardışık çerçevelerinde aynı nesnelerin birbirleriyle ilişkilendirilmesini sağlamak için temel olarak aşağıdaki adımlar uygulanmıştır;
Bir önceki görüntüdeki nesnelerin mevcut nesnelere koordinat uzaklıklarının bulunması,
Görüntünün RGB renk uzayından HSV uzayına dönüştürülmesi ve nesnelerin Hue-Saturation histogramlarının elde edilmesi,
Histogramların normalizasyonu ve birbirine olan uzaklıklarının bulunması,
Ardisik iki görüntüdeki nesnelerin koordinat ve histogram uzaklıklarının karşılaştırılması,
Mesafe ve renk olarak en yakın olan nesnelerin uzaklığı belirli bir değerin altındaysa nesne tanımlayıcılarının (ID) eşleştirilmesi, değilse nesneye yeni ID atanması.

Çerçeveler arası süreksizlik probleminin çözümü
Anlık çerçevede bir nesne kaybolduğunda nesnenin önceki çerçevelerdeki hareketi göz önünde bulundurularak lineer regresyon ile yeni konumu hesaplanmaktadır. Nesnenin gerçekten kaybolmuş olabileceği durumunu da ele alabilmek için hesaplanarak konumu tahmin edilen nesneler hayalet nesne olarak işaretlenmekte ve ardisik çerçeve sayısı cinsinden bir ömür atanmaktadır. İlerileyen çerçevelerde nesne tekrar tespit edilirse yakalanmakta ve gerçek nesne olarak işaretlenmekte, ömrü bitene kadar tespit edilemezse silinmektedir. Bir nesnenin kisa bir sure icin kaybolmasi sorun oldugu gibi, genellikle görüntüdeki küçük hareketliliklerden kaynaklanan (örneğin ağaçların rüzgarla hareket etmesi) kisa sureli istenmeyen nesnelerin ortaya çıkması da problem olmaktadir. Bu sorun da benzer şekilde her nesneye bir yaşam süresi atanması ve belirli bir süreden daha uzun süre varlığını sürdürmeyen nesnelerin silinmesi ile çözülmüştür.