[Ψηφιακη Επεξεργασια Εικονας] 1η Εργασια 2016

[Thmmy.gr portal]

  Thmmy.gr portal
   Forum
   Downloads
   Ενεργ. Λογαριασμού
   Επικοινωνία
  
  Χρήσιμα links
   Σελίδα τμήματος
   Βιβλιοθήκη Τμήματος
   Elearning
   Φοιτητικά fora
   Πρόγραμμα Λέσχης
   Πρακτική Άσκηση
   Ηλεκτρονική Εξυπηρέτηση Φοιτητών
   Διανομή Συγγραμμάτων
   Ψηφιακό Καταθετήριο Διπλωματικών
   Πληροφορίες Καθηγητών
   Instagram @thmmy.gr
   mTHMMY
  
  Φοιτητικές Ομάδες
   ACM
   Aristurtle
   ART
   ASAT
   BEAM
   BEST Thessaloniki
   EESTEC LC Thessaloniki
   EΜΒ Auth
   IAESTE Thessaloniki
   IEEE φοιτητικό παράρτημα ΑΠΘ
   SpaceDot
   VROOM
   Panther
  

THMMY.gr Web

Helios_MultiScribbles2SMF Default ThemeSMFone_Blue

[Ανεβάζετε τα θέματα των εξετάσεων στον τομέα Downloads]

Είσαι πρωτοετής;... Καλώς ήρθες! Μπορείς να βρεις πληροφορίες εδώ. Βοήθεια για τους καινούργιους μέσω χάρτη.

Κατεβάστε εδώ το Android Application για εύκολη πρόσβαση στο forum.

Ανεβάζετε τα θέματα των εξετάσεων στον τομέα Downloads με προσοχή στα ονόματα των αρχείων!

[Πληροφορίες Καθηγητών]

Πληροφορίες Καθηγητών

[WatchDog]

Η πολυπλοκότητα είναι N^2 για το 3.1 , και για το 3.2 NlogN ετσι ? Αφου λέει πως οι διαστάσεις της εικόνας είναι σταθερες?
Ας με διορθώσει κάποιος αν έχω λάθος

[chrisrn]

Η πολυπλοκότητα είναι N^2 για το 3.1 , και για το 3.2 NlogN ετσι ? Αφου λέει πως οι διαστάσεις της εικόνας είναι σταθερες?
Ας με διορθώσει κάποιος αν έχω λάθος

((Ν+1)^2)*log(N+1) στο 3.2 νομίζω

[GiannisM]

Επειδή έχω χαωθεί λίγο, έχει μπερδέψει στην εκφώνηση την h με την y σε σχέση με το data.m έτσι? Δηλαδή στο 2ο ζητούμενο αντί για το y=x*h εμείς στο πρόγραμμα υπολογίζουμε το y*x, και στο 3ο κρατάμε σταθερή την x ή την y και παίζουμε με τυχαίους πίνακες με την άλλη. Δεν είναι ότι θα διαλέξουμε σε μια από τις 2 ένα τυχαίο h και θα βρούμε κάθε φορά τα x*h και y*h ή κάτι τέτοιο σωστά?

[marmota]

Επειδή έχω χαωθεί λίγο, έχει μπερδέψει στην εκφώνηση την h με την y σε σχέση με το data.m έτσι? Δηλαδή στο 2ο ζητούμενο αντί για το y=x*h εμείς στο πρόγραμμα υπολογίζουμε το y*x, και στο 3ο κρατάμε σταθερή την x ή την y και παίζουμε με τυχαίους πίνακες με την άλλη. Δεν είναι ότι θα διαλέξουμε σε μια από τις 2 ένα τυχαίο h και θα βρούμε κάθε φορά τα x*h και y*h ή κάτι τέτοιο σωστά?

Ναι το y απ το data.m είναι το h. Άρα θα έχεις ως όρισμα στις συναρτήσεις σου τα x,y (για να υπολογίσεις τη συνέλιξη των x*y)

[chrisrn]

Στα demo το h παραμένει σταθερό αρά δεν θα είναι το y που μας δίνει αυτός στο data.mat?

[PanteGrv]

Είναι αυτό που έλεγε στη τάξη ότι πολλαπλασιάζεις με την(-1)^(ν1+ν2) για να φέρεις το 0,0 στο κέντρο του πίνακα..τώρα αν δουλεύει και χωρίς αυτό dunno

δουλεύει χωρίς αυτό. το θέμα είναι δουλεύει ΜΕ αυτό? γιατί και η μάσκα θα πρέπει να είναι shifted για να δουλέψει (γι αυτό γίνεται το shift νομίζω, γιατί παίρνεις την μάσκα shifted)

((Ν+1)^2)*log(N+1) στο 3.2 νομίζω

είναι όπως λέει για την γενική περίπτωση Ο(Ν*Μ*log(N*M)), που για Μ=const δίνει O(N*logN)

[chrisrn]

δουλεύει χωρίς αυτό. το θέμα είναι δουλεύει ΜΕ αυτό? γιατί και η μάσκα θα πρέπει να είναι shifted για να δουλέψει (γι αυτό γίνεται το shift νομίζω, γιατί παίρνεις την μάσκα shifted)

είναι όπως λέει για την γενική περίπτωση Ο(Ν*Μ*log(N*M)), που για Μ=const δίνει O(N*logN)

Ναι απλά το Μ δεν αναφέρεται στο άλλο σήμα που παραμένει σταθερό αλλά στο σήμα που αλλάζει δηλαδή Μ=Ν άρα γίνεται (Ν^2)logN. Βγαίνει και με βάση την πολυπλοκότητα της fft2 που στις 2 διαστάσεις είναι αυτή.

[PanteGrv]

Ναι απλά το Μ δεν αναφέρεται στο άλλο σήμα που παραμένει σταθερό αλλά στο σήμα που αλλάζει δηλαδή Μ=Ν άρα γίνεται (Ν^2)logN. Βγαίνει και με βάση την πολυπλοκότητα της fft2 που στις 2 διαστάσεις είναι αυτή.

μμ όντως

πάντως για το θέμα με τα διαγράμματα, στο 1 δεν μου βγάζει τόσο καλή ασυμπτωτική συμπεριφορά, ούτε με semilog (δλδ η κλίση των καμπυλών δεν είναι ίδια)

[Napoleon]

Η πολυπλοκότητα είναι N^2 για το 3.1 , και για το 3.2 NlogN ετσι ? Αφου λέει πως οι διαστάσεις της εικόνας είναι σταθερες?
Ας με διορθώσει κάποιος αν έχω λάθος

Στο 3.1 ο z θέλει Ο(Ν^2) για όλα τα στοιχεία του και Ο(Ν^2) για να βρεις το κάθε ένα. Άρα Ο(Ν^4). όχι?

[PanteGrv]

Στο 3.1 ο z θέλει Ο(Ν^2) για όλα τα στοιχεία του και Ο(Ν^2) για να βρεις το κάθε ένα. Άρα Ο(Ν^4). όχι?

όχι γιατί η μάσκα σου είναι περιορισμένη, οπότε θέλει Μ^2 το δεύτερο μέρος. Άρα σταθερά, άρα Ο(Ν^2) ουσιαστικά

[Napoleon]

όχι γιατί η μάσκα σου είναι περιορισμένη, οπότε θέλει Μ^2 το δεύτερο μέρος. Άρα σταθερά, άρα Ο(Ν^2) ουσιαστικά

Δεύτερο μέρος εννοείς το διπλό άθροισμα για κάθε στοιχείο z(m,n)? Αν ναι, για να υπολογιστεί δεν χρειαζόμαστε στοιχεία του χ και άρα αποκλείεται να έχει σταθερή πολυπλοκότητα?

Σημ: Πάντως το διάγραμμα για N^4 μου βγαίνει σχεδόν ίδιο με το πειραματικό, σε αντίθεση με το Ν^2

[marmota]

Ναι απλά το Μ δεν αναφέρεται στο άλλο σήμα που παραμένει σταθερό αλλά στο σήμα που αλλάζει δηλαδή Μ=Ν άρα γίνεται (Ν^2)logN. Βγαίνει και με βάση την πολυπλοκότητα της fft2 που στις 2 διαστάσεις είναι αυτή.

Η πολυπλοκότητα δε θα είναι Ο(My∙Ny∙log(My∙Ny )) και αφού My=Mx+Mh -1 και  Νy=Νx+Νh-1 και h σταθερή θα γίνει Ο(Mx∙Nx∙log(My∙Ny )) ;
Μες στο λογαριθμο τι γίνεται; Θεωρώ κι εκεί log(Mx∙Nx); και μετά αυτό που λες Mx=Nx=N άρα γίνεται Ο((Ν^2)logN);

[PanteGrv]

Δεύτερο μέρος εννοείς το διπλό άθροισμα για κάθε στοιχείο z(m,n)? Αν ναι, για να υπολογιστεί δεν χρειαζόμαστε στοιχεία του χ και άρα αποκλείεται να έχει σταθερή πολυπλοκότητα?

Σημ: Πάντως το διάγραμμα για N^4 μου βγαίνει σχεδόν ίδιο με το πειραματικό, σε αντίθεση με το Ν^2

εγώ το έχω κάνει με υποπίνακες (χωρίς zero pad). ο υποπίνακας θα είναι Μ*Μ το πολύ, οπότε τότε βγαίνει σταθερό αυτό

[Maylo]

Όσον αφορά στις πολυπλοκότητες  το κομμάτι του κώδικά μου για την freq είναι 

            Xe=fft2(xpad);
            Ye=fft2(ypad);
           
            Ze=Xe.*Ye;
            z=ifft2(Ze);

Πάνω σε αυτό πχ  έχουμε για ΝχΝ πίνακες N^2logN για το fft2 στα Xe & Ye  , Ν^2 για το Ze και υποθέτω (νομίζω) και N^2logN για το ifft2 στο z .

Συνεπώς 3*Ν^2logN +N^2 => Ν^2logN +N^2 =>Ν^2(1+logN) =>Ο(Ν^2logN) .

για το  myconv2 με 4 for loops πιστεύω είναι O(N^4) γιατί δεν μένουμε μόνο στις 2-3 πράξεις του βρόχου αλλά το γενικεύουμε , οπότε με τα εμφολευμένα
ισχύει το γινόμενο .


Θα ήθελα να ρωτήσω , ποιά είναι η θεωρητική πολυπλοκότητα της conv2 στο matlab;

Γενικά για τα παραπάνω διορθώστε με αν έχω κάπου λάθος.


edit: δεν είδα οτι κρατάμε και τις διαστάσεις του h σταθερές .
 Όμως ακόμα και έτσι πέφτει έτσι κι αλλιώς padding  οπότε  θα έχεις για την h(3χ4) ας πουμε : (N+2)*(N+3)log((N+2)*(N+3)) που είναι και πάλι
 Ν^2 log N^2 το 2 πάει έξω και γινεται 2*Ν^2 logN . Άρα  Ν^2 logN για το freq . Όχι;

[marmota]

Κι εγώ έχω θέμα με τα διπλά γραφήματα. Μου βγαίνει ο μέσος χρόνος πιο ψηλά από τη θεωρητική πολυπλοκότητα, ακόμη και στο πρώτο με το fft2. Το έκανα με plotyy και όταν όρισα τον κάθε άξονα στο max του έχω αυτό το αποτέλεσμα της εικόνας.

Την ίδια εικόνα έχω ακόμη κι οταν ορίσω κατάλληλο συντελεστή A για τη θεωρητική πολυπλοκότητα.