11 Haziran 2017 Pazar

Algoritma Analizi

Yüz Algılama Projesi

Projemiz, upload edilen bir fotoğrafın veya videonun içeriğinde bulunan yüzleri algılayarak, bu yüzleri kare açan bir uygulamadır. 

Karmaşıklık
       

      
     for (i = 0; i < seq.length; i++) if (node[i].element) {
        for (var root = i; node[root].parent != -1; ) root = node[root].parent;
        for (j = 0; j < seq.length; j++) if (i != j && node[j].element && gfunc(node[i].element, node[j].element)) {
         for (var root2 = j; node[root2].parent != -1; ) root2 = node[root2].parent;
            if (root2 != root) {
               node[root].rank > node[root2].rank ? node[root2].parent = root : (node[root].parent = root2, 
               node[root].rank == node[root2].rank && node[root2].rank++, root = root2);
               for (var temp, node2 = j; node[node2].parent != -1; ) temp = node2, node2 = node[node2].parent, 
               node[temp].parent = root;
               for (node2 = i; node[node2].parent != -1; ) temp = node2, node2 = node[node2].parent, 
               node[temp].parent = root;
               }
            }
         }
       
 

Yukarıdan da görüldüğü gibi, algoritmanın karmaşıklığı O(n^4).
Uygulamanın inputları, 24x24 boyutundan büyük fotoğraf veya video dosyalarıdır.
Eğitim için kullanılan algoritma: Haar feature-based cascade 

Haar feature-based Yöntemi

Haar feature-based cascade sınıflandırıcılarını kullanan Nesne Algılama, Paul Viyola ve Michael Jones'un kağıtlarında "Basit Özelliklerin Yaygınlaştırılmış Bir Basamaklandırmasını Kullanan Hızlı Nesne Algılama" adlı çalışmasında 2001'de önerilen etkili bir nesne saptama yöntemidir. Bu, bir makine öğrenmeye dayalı bir yaklaşımdır; Cascade işlevi bir çok olumlu ve olumsuz görüntülerden eğitim alır. Ardından, diğer görüntülerdeki nesneleri algılamak için kullanılır.Burada yüz tanımayla çalışacağız. Başlangıçta, algoritmanın sınıflandırıcıyı eğitmek için bir çok pozitif resim (yüz resimleri) ve negatif resimler (yüzleri olmayan resimler) gerekir. Ardından, özellik eklemeliyiz. Bunun için, aşağıdaki resimde gösterilen Haar feature-based özellikleri kullanılır. Her özellik, siyah dikdörtgen altındaki piksellerin toplamından beyaz dikdörtgen altındaki piksellerin toplamını çıkararak elde edilen tek bir değerdir.







Artık, her bir çekirdeğin olası tüm boyutları ve konumları, birçok özelliği hesaplamak için kullanılabilinir. (Sadece ne kadar çok hesaplamanın gerekeceğini, 160000 özellikli üzerinden 24x24 pencere bile alınır). Her özellik hesabı için, beyaz ve siyah dikdörtgenlerin altındaki piksellerin toplamını bulmamız gerekir. Bunu çözmek için, integral görüntüleri tanıtılır. Sadece dört piksel içeren bir işlem için piksel toplamının hesaplanmasını, piksel sayısının ne kadar büyük olabileceğini basitleştirilir.Bu işlemleri çok hızlı yapar.


Ancak hesapladığımız bu özelliklerin hepsinde, bunların çoğu ilgisizdir. Örneğin, aşağıdaki resmi düşünün. Üstteki satır iki iyi özelliği gösterir. Seçilen ilk özellik, göz bölgelerinin genellikle burun ve yanak bölgelerinden daha koyu olduğu özelliklere odaklandığı görülüyor. Seçilen ikinci özellik, gözlerin burun köprüsünden daha koyu olduğu özelliklerine dayanır. Ancak yanaklarda veya başka bir yerde uygulanan pencerelerin alakasız olduğu söylenebilir. Peki, 160000+ özelliğin en iyi özelliklerini nasıl seçebiliriz? Adaboost tarafından sağlanır.


Bunun için her eğitim görüntüsüne her bir özelliği uyguluyoruz. Her özellik için yüzleri pozitif ve negatif olarak sınıflandıran en iyi eşiği bulur. Ancak açıkçası, hatalar veya yanlış sınıflamalar olacaktır. Asgari hata oranına sahip özellikleri seçiyoruz; bu, yüzü ve yüz olmayan resimleri en iyi sınıflandıran özellikler anlamına geliyor. (Süreç bu kadar basit değildir Her görüntünün başında eşit ağırlık verilmektedir Her bir sınıflandırmadan sonra, yanlış sınıflandırılmış görüntülerin ağırlığı artar, sonra aynı işlem yapılır Yeni hata oranları hesaplanır Ayrıca yeni ağırlıklar da hesaplanır. Gerekli doğruluk veya hata oranı elde edilene veya gerekli özellik sayısı bulunana kadar işlem devam eder).


Aşağıdaki değişkenler bulunan yüzlerin bir dizisini nesne olarak döndürür:
X - resimdeki yüzün X koordinatı
Y - resimdeki yüzün Y koordinatı
Width - yüzün genişliği
Height - yüzün yüksekliği
PositionX - dosyaya göre X konumu
PositionY - dosyaya göre Y konumu
OffsetX - ofset ebeveyine göre X konumu
OffsetY - ofset ebeveyine göre Y konumu
ScaleX - Orijinal görüntü genişliği ile görüntülenen genişlik arasındaki oran
ScaleY - Orijinal görüntü yüksekliği ile görüntülenen yükseklik arasındaki oran
Confidence - Güven düzeyi

Ayarlar
interval - Aralık (default 4 )
MinNeighbors - Dikdörtgen gruplarını atmak için kesme seviyesini yüz olarak ayarlayan minimum komşu eşiği (default 1)
confidence - Minimum güven (default null)
async - Kişi varsa senkronizasyon modu (default false). Eşzamansız mod kişileri kullanır ve komut dosyasının aynı etki alanında olması gerekir.
grayscale - İşlenmeden önce gri tonlamaya dönüşür. (default true)
complete - Geri arama fonksiyonu, algılama tamamlandıktan sonra tetiklenir.
complete: function (faces) {
   // ...
}
error - Hatalar durumunda geri arama fonksiyonu tetiklenir.
error: function (code, message) {
   // ...
}
JQuery ve eklentiyi dahil ettik.
<script src="http://code.jquery.com/jquery-1.11.1.min.js"></script>
<script src="path/to/dist/jquery.facedetection.min.js"></script>

HTML sayfamızda yüzleri olan bir resim ayarladık.
<img id="picture" src="img/face.jpg">
Eklentiyi bu görüntüye uyguladık ve yüz koordinatlarını elde ettik.
<script>
   $('#picture').faceDetection({
       complete: function (faces) {
           console.log(faces);
       }
   });
</script>
github linki

video linki

Hiç yorum yok:

Yorum Gönder