THMMY.gr

Ανεβηκε η πρωτη εργασια στο ethmmy.

Προθεσμια 23/04

Ο θεωρητικός χρόνος του FFT ποιος είναι μαν μου ?

από την πολυπλοκότητα βγαίνει, θα είναι Α*n^2*logn, Α σταθερά που εξαρτάται από την υλοποίηση

Ναι, δεκτό, υπάρχει όμως ρεαλιστικός τρόπος να βρούμε το A εμείς ? Αφού οτι και να μετρήσουμε απο την Matlab δεν θα είναι θεωρητικός χρόνος, αρά πως επιλέγουμε το διάστημα που παίζει να ανήκει το Α, στη τύχη >?

Να βρεις θεωρητικά τον χρόνο εκτέλεσης δεν γίνεται, γι' αυτόν τον λόγο δεν ζητείται και στην εργασία. Αυτό που ζητείται, και μπορεί να βρει κανείς, είναι απλά η πολυπλοκότητα.

Στο ζητούμενο 3.3, για πόσα και ποια Ν θα μετρήσουμε;;

Ο χρόνος εκτέλεσης της myconv2 πρέπει να προσεγγίζει αυτόν της conv2? Επίσης, θεωρητικά η myconv2freq για μεγάλους πίνακες πρέπει να είναι αρκετά πιο γρήγορη από τις άλλες, κάτι το οποίο δε συμβαίνει με μία πολύ απλή υλοποίηση που έκανα. Δώστε φώτα.

Μπορείς απλά να βάλεις τα Ν που σου λέει και στο Ζητούμενο 1, λογικά αρκούν.


Δεδομένου ότι την myconv2 θα την γράψεις εσύ και η conv2 έρχεται precompiled και optimised από το MATLAB, θα έλεγα ότι δεν υπάρχει περίπτωση οι χρόνοι εκτέλεσης των δύο να είναι έστω παραπλήσιοι.

Η myconv2freq όντως θα έπρεπε να είναι σημαντικά πιο γρήγορη από myconv2/conv2. Αν πχ βάζεις μέγεθος πίνακα 256 και πάνω (και στις δύο διαστάσεις) αλλά δε βλέπεις τάξη μεγέθους διαφοράς στον χρόνο εκτέλεσης, κάτι έχεις κάνει σίγουρα λάθος.

Ναι αλλά δισιαστατη συνελιξη πινάκων 4096x4096 100 φορές θα πάρει κάμποση ώρα :/

Δε διαφωνώ μαζί σου. Μπορείς είτε να δοκιμάσεις μέχρι ένα μικρότερο Ν (και όχι μέχρι 4096) ή να δοκιμάσεις να εκτελείς λιγότερες επαναλήψεις για κάθε Ν (πχ 10, αντί για 100).

Επίσης, λόγω της χρονοβόρας (με υψηλή πολυπλοκότητα) διαδικασίας της 2D συνέλιξης, θα χρειαστεί να αφήσεις το πρόγραμμα σου να εκτελείται για αρκετό καιρό αν θες να έχεις ένα καλό πλήθος και ποικιλία μετρήσεων (πέρυσι κάποιοι το είχαν αφήσει να εκτελείται αρκετές μέρες).

Βασικά έχω τάξη μεγέθους διαφορά αλλά μόνο όταν και τα 2 σήματα είναι NxN. Σύμφωνα με την εκφώνηση το ένα παραμένει όπως είναι με αποτέλεσμα στο zero-padding να έχεις πάρα πολλά μηδενικά στον έναν πίνακα. Όταν έχεις πολλά μηδενικά η conv2 τρέχει πιο γρήγορα από την myconv2freq και είναι λογικό εφόσον έρχεται από το Matlab και είναι optimised. Δεν ξέρω αν είναι σωστή η παρατήρηση

Όταν το ένα σήμα είναι μεγέθους πολύ μικρότερο του Ν, τότε είναι νομίζω όντως λογικό η conv2 να είναι γρηγορότερη.

Η εκτέλεση της συνέλιξης μέσω FFT οδηγεί σε γρηγορότερη εκτέλεση όταν και τα δύο σήματα είναι μεγάλα σε διαστάσεις.

Άρα εφόσον το σήμα h παραμένει σταθερό δεν θεωρείται λάθος με fft να είναι πιο αργή για κάθε N. Cool.

σορυ που πεταγομαι σαν την τσουτσου, αλλα εχει δοκιμασει κανεις αυτη τη συνελιξη που γραφετε να την κανει mex function με το matlab coder?

Το είχα κάνει πέρυσι, το .mex ήταν πιο αργό.

Βέβαια σε αυτό λογικά έφταιγε και ο ίδιος ο κώδιακς μου γιατί δεν ήταν αρκούντως optimised/vectorised έτσι ώστε να είναι πιο γρήγορος ο pre-compiled κώδικας στο .mex, με κατάλληλη υλοποίηση ο .mex κώδικας λογικά θα είναι πιο γρήγορος.

Πάντως αν πάρεις τον λίγο-πολύ-standard κώδικα που θα γράψει κάποιος στα πλαίσια της εργασίας και τον μετατρέψεις τυφλά σε .mex λογικά θα χάσεις και δε θα κερδίσεις σε χρόνο εκτέλεσης.

Στο πρώτο ερώτημα, όταν λέει " Ο μεσος χρονος εκτελεσης για την fft2 ως προς το N"  , εννοεί  πως για 100 επαναληψεις ,υπολογίζουμε για κάθε Ν=2^κ(κ=2...10) , τον χρόνο εκτέλεσης σε ενα vector , η αθροίζουμε όλους τους χρόνους για κάθε Ν και διαιρούμε μετά με το Ν? Μου φαίνεται λίγο ασαφές το ερώτημα και δε μπορώ να καταλάβω.

Οριζόντιος άξονας το Ν, κάθετος άξονας ο μέσος χρόνος εκτέλεσης.

Ας δώσει κάποιος αν γνωρίζει κάποια βοήθεια με τα παρακάτω:

- Αρχικά, για να βγάλουμε τα διαγράμματα χρόνου και πολυπλοκότητας,  είπαμε ότι πρέπει να πολλαπλασιάσουμε την θεωρητική πολυπλοκότητα με έναν παράγοντα c. Με τι κριτήρια όμως τον επιλέγουμε?? Τον επιλέγουμε απλά με στόχο να είναι συγκρίσιμες οι δυο καμπύλες??

- Τι μέγεθος είναι προτιμότερο να θεωρήσουμε για την εικόνα h?? Αναφέρει ότι κρατάμε για τα 3 τελευταία demo το μέγεθος h σταθερό, άρα το h είναι το φίλτρο της συνέλιξης. Αν h είναι ένα φίλτρο σχετικά μικρής διάστασης σε σχέση με την εικόνα x, τότε είναι ευκολότερο υπολογιστικά να χρησιμοποιήσουμε αυτά που αναφέρονται στην παράγραφο 3.4.2. του gonzalez woods.  Να κάνουμε δηλαδή zero padding στην εικόνα x , ανάλογα  με τις διαστάσεις του φίλτρου h, και μετά απλά να σέρνουμε το φίλτρο.

Αν όμως το φίλτρο είναι σχετικά μεγάλο, σε σχέση με την εικόνα πχ h=256*256 Και x=512*512, τότε θα γίνουν πολλές επιπλέον πράξεις του φίλτρου h’ , με μηδενικά που προσθέσαμε , με αποτέλεσμα να αυξηθεί ο χρόνος εκτέλεσης.

Στην συγκεκριμένη περίπτωση αφού έχουμε σχετικά μεγάλο φίλτρο σε σχέση με την εικόνα είναι προτιμότερο, να χωρίσουμε την εικόνα σε 9 περιοχές. Για παράδειγμα μια περιοχή είναι η πάνω αριστερή γωνία, όπου το φίλτρο h δεν έχει εισέρθει ακόμα μέσα στην εικόνα ούτε προς την διάσταση x, ούτε προς την διάσταση y.  Μια άλλη περιοχή είναι όταν φίλτρο έχει εισέρθει μέσα στην εικόνα αλλά μόνο ως προς την μια διάσταση, ή όταν στην μια διάσταση έχει αρχίσει να εξέρχεται από την εικόνα και πάει λέγοντας. (κατά το σύρσιμο που το κάνουμε). Εδώ, δεν έχουμε επιπλέον πράξεις με μηδενικά και θα γίνει εκτέλεση πιο σύντομα σε σχέση με πάνω.

ο πρώτος τρόπος  που ανέφερα είναι πολύ απλός στην υλοποίηση αλλά κοστίζει αρκετά περισσότερο από τον δεύτερο αν το φίλτρο είναι σχετικά μεγάλο σε σχέση με την εικόνα. Η δεύτερη μέθοδος πάλι, είναι πιο σύνθετη στην υλοποίηση .
 
Γενικά, ποιον τρόπο να προτιμήσω και πόσο περίπου να θεωρήσω το μέγεθος του σταθερού φίλτρου h??

Απ'ό,τι κατάλαβα από την εκφώνηση (ζητούμενο 3.3) η εικόνα και το φίλτρο πρέπει να είναι ίδιας διάστασης οπότε το 2ο

"Το προς υποβολή αρχείο πρέπει να περιέχει τα 7 αρχεία κώδικα
και το αρχείο report.pdf το οποίο θα είναι η αναφορά της εργασίας."

Εγώ 6 τα μετράω, εσείς;   :P

κανένα tip για vectorization μπορεί να δώσει κανείς/καμιά ?
 :D :D

Έχω διαβάσει τη σελίδα του Matlab πανω στο θέμα αλλά δε φαίνεται να βοηθάει και ιδιαίτερα στην περίπτωση μας... όχι ?

και εγω το ιδιο - μαλλον λαθος
(του εβαλα και το data.mat για να γινουν 7 :P )

συντομο
http://www.slideshare.net/jbhuang/writing-fast-matlab-code

μη συντομο
http://www.ee.columbia.edu/~marios/matlab/Writing_Fast_MATLAB_Code.pdf

Στο 1ο ζητούμενο οι πίνακες που θα δίνουμε ως είσοδο ποιοι είναι; Δημιουργούμε τυχαίους δικούς μας π.χ.;

Ναι τυχαίους, ρώτησα στην τάξη.

Στο πρώτο ερώτημα για να φανεί η πολυπλοκότητα και ο μέσος χρόνος στο ίδιο γράφημα πολλαπλασιάζουμε με ένα δικό μας threshold ώστε να είναι στην ίδια κλίμακα έτσι?

Μπορείς να κάνεις το γράφημα με την plotyy (http://www.mathworks.com/help/matlab/ref/plotyy.html). Δεν θα συμπίπτουν οι καμπύλες λόγω διαφοράς κλίμακας αλλά η μορφή τους θα είναι παρόμοια.

Ωραίος ευχαριστώ. Δεδομένου ότι το Ν είναι πάντα δύναμη του 2 ο λογάριθμος στην πολυπλοκότητα βάσης 2 είναι σωστά?

Καλά τα λες, αλλά δεν έχει σημασία να βάλεις log10(N) αντί του log2(N) αφού log2(N)=log10(N)/log10(2) και κατά τα γνωστά οι σταθεροί συντελεστές δεν επηρεάζουν την πολυπλοκότητα.

Στο ζητούμενο 2.1, σύμφωνα με τη θεωρία απαιτείται zero padding και στους 2 πίνακες. Σε οποιοδήποτε άλλο έγγραφο έχω ψάξει στο net χρειάζεται ένα -γενναιόδωρο- zero-padding μόνο στο δεύτερο πίνακα για να "φτάσει" τις διαστάσεις του πίνακα του αποτελέσματος.

Αυτό που θέλω να ρωτήσω είναι αν ακολουθήσατε αυτή τη λογική ή κάνατε zero-padding και τους δύο πίνακες.

Έχω κολλήσει με τη myconv2. Στην ουσία είναι η υλοποίηση της εξίσωσης της συνέλιξης, που μας δίνει στην εκφώνηση, στο matlab, σωστά;
Επειδή δε το χω ακόμη με τα vectors, το έχω κάνει με for. Μου βγάζει όμως ότι κάποια στοιχεία είναι εκτός των ορίων των πινάκων που χρησιμοποιώ.
Οι πίνακες των πεπερασμένων xe και he έχουν διαστάσεις [My x Ny]

Θα γράψω ένα παράδειγμα μήπως δεν έχω καταλάβει κάτι σωστά στην υλοποίηση της εξίσωσης της συνέλιξης.
Έστω οι πίνακες των σημάτων εισόδου με διαστάσεις x [2x3] και h[2x2] άρα οι xe, he, y θα έχουν διαστάσεις [3,4].
Έστω ότι θέλω το στοιχείο y(1,1), θα έχω:

y(1,1)= xe(1,1) * he(0,0) + xe(1,2) * ye(0,-1) + xe(1,3) * he(0,-2) +  xe(2,1) * he(-1,0) + xe(2,2) * he(-1,-1) + xe(2,3) * he(-1,-2)

Tα στοιχεία  he(0,0) , he(0,-1) , he(0,-2),..  είναι εκτός των ορίων του πίνακα he και γι αυτό μου βγάζει το αντίστοιχο error. Αν μηδενίσω αυτά τα στοιχεία τότε το y(1,1)=0 που είναι λάθος. Τι δε βλέπω;

Δεν ξέρω τι έκανες λάθος αλλά εμένα με βοήθησε αυτό αρκετά για να βγάλω άκρη:

http://www.mathworks.com/help/vision/ref/2dconvolution.html

Προσπαθώ να τρέξω vectorized τα 2 εξωτερικά loops με meshgrid, όμως έχω εντολές της μορφής

min(n1,n)
max(n1,n)

όπου το n είναι αυτό που τρέχει στο αντίστοιχο for loop και το n1 σταθερός αριθμός (όχι array). Στην εκδοχή με το grid, πως θα υλοποιήσω αυτές τις εντολές, εφόσον τα Ν, Μ τώρα θα αντιστοιχούν στο grid, δηλαδή θα είναι 1D πίνακες, ενώ το n1 θα είναι σταθερά? Θέλω δλδ όπως θα γινόταν για κάθε node του mesh να παρθεί το corresponding n και m από τους Ν,Μ στις σχέσεις που τα εμπλέκουν, να γίνει αυτό και με εντολές min, max.Η διαφορά είναι ότι γενικά στις σχέσεις που εμπλέκουν τα n,m θα έχω μία δομή grid που προσαρμόζεται καθώς αλλάζω κόμβο (όλες όμως οι ποσότητες θα αντιστοιχούν σε ένα κόμβο) ενώ για το n1 δεν ισχύει αυτό. Θα μπορούσα να κάνω κάτι της μορφής:

N1(1:length(N))=n1  

και να έχω την έκφραση

min(Ν1,Ν)  ??


edit ουσιαστικά δεν μπορώ να βρω τρόπο να εφαρμόσω την min και την max elementwise σε πίνακες 2 διαστάσεων και να πάρω στην έξοδο έναν 2D πίνακα που θα έχει για κάθε σημείο το min ή το max από τα 2 corresponding στοιχεία των πινάκων.

Σε ευχαριστώ πολύ, βοήθησε αρκετά να καταλάβω τι παίζει.
Ο τρόπος υλοποίησης που περιγράφει βασίζεται στο κέντρο του πίνακα h. Αν όμως ο πίνακας h δεν έχει κέντρο (πχ. είναι 2x2 ή 3x4) με βάση ποιο στοιχείο του πίνακα κινείσαι;

Στο ζητούμενο 3, η εικόνα x θα είναι ένας τυχαίος πίνακας διαστάσεων [NxN] όπου Ν=2^k, k=2,3,...,10
Για την εικόνα h που ζητάει να είναι σταθερών διαστάσεων τι θεωρούμε; Θα είναι κι αυτή [NxN] σαν τη x;

Όταν είναι σταθερή η εικόνα τότε δεν περιλαμβάνεται στον ορισμό της πολυπλοκότητας (θα έχει ίδιο πολλαπλασιαστικό παράγοντα) άρα μπορεί να θεωρηθεί οποιουδήποτε μεγέθους. Άρα μπορεί αυτό να το έκανε ο ντελόπουλος για να μην έχουμε μεγάλα running times. Στην πρώτη έκδοση της εργασίας δεν το έλεγε αυτό (όπως και έλεγε ότι θέλει μέχρι k=12 ενώ στην νέα έκδοση ζητάει μέχρι k=10).

Δηλαδή θα μπορούσαμε να θεωρήσουμε εικόνα h διαστάσεων όσο και η μικρότερη εικόνα x [4x4] για k=2 ή ακόμη και [2x2] για παράδειγμα;

υποθέτω πως ναι, αν και είναι λίγο ξεφτίλα :P δεν θα έβαζα το μικρότερο προσωπικά, για θέματα robustness

H αλήθεια είναι πως με τόσο μικρή εικόνα η conv2 είναι αρκετά πιο γρήγορη από τη myconv2freq, οπότε θα προτιμήσω μεγαλύτερη  :P
Απλά δεν εχω καταλάβει αν πρέπει να χρησιμοποιήσουμε ένα μεγεθος για όλα τα Ν. Δηλαδή για μια εικόνα [4x4] είναι οκ να χρησιμοποιήσουμε εικόνα h διαστάσεων [256x256];

πρακτικά δεν νομίζω να παίζει μάσκα 256*256, ούτε προφανώς εικόνα 4*4. από εκεί και πέρα, your call

στα demo1b, demo1c και demo1d πρέπει να έχουμε δύο καμπύλες (πειραματική και θεωρητική πολυπλοκότητα) κατ' αντιστοιχία του ζητούμενου 1; αν ναι, τότε πως θα υπολογίσουμε την θεωρητική πολυπλοκότητα του conv2 στο demo1b; υπάρχει κάπου έτοιμη;

Σε mail εμένα πάντως μου απάντησε ότι ένα γράφημα με τις 3 καμπύλες είναι αρκετό (μαζί με σχολιασμό). Οπότε λογικά θέλει ξεχωριστά τα γραφήματα των demo και ένα γράφημα που τα έχει και τα 3. Όσο για πολυπλοκότητα που λες νομίζω απλά θέλει να του γράψεις ποια είναι και τίποτα παραπάνω.

οκ. εμένα η δυσκολία μου φαίνεται οτι υπάρχει στη σύγκριση θεωρητικής - πειραματικής πολυπλοκότητας σε κοινό γράφημα. Εσείς πως το κάνατε, μέσω plotyy με διπλό y άξονα ή υπολογίζοντας την θεωρητική και βάζοντας έναν συντελεστή μπροστά για να έρθουν οι 2 καμπύλες σε κοινή κλίμακα y;

Τσέκαρε πιο πάνω είχα ρωτήσει το ίδιο. Εν τέλει το ίδιο είναι νομίζω.

ναι το είδα τώρα, αλλά μεταφέρω τι ρώτησα και στον μεταπτυχιακό αλλά μ έχει κλάσει μέχρι τώρα:


νομίζω ότι και οι δύο τρόποι δεν δίνουν τόσο καλή εικόνα. Αν κάποιος είναι πολύ βέβαιος για το θέμα ας γράψει τι να κάνουμε, να τελειώνουμε...

Mία ιδέα είναι να λογαριθμήσεις. Το οπτικό αποτέλεσμα είναι καλύτερο.

εγω για τα γραφήματα, δεν τα έβαλα το ενα πανω στο αλλο στο ιδιο γράφημα, αλλα διπλα διπλα.

επισης εκανα και γραμμικα και (semi)λογαριθμικα διαγραμματα, για να ειναι πιο ευκρινεις οι διαφορες για μικρα κ.

Πόσο ανευθυνοι. .. Έχουν αλλάξει την εκφώνηση της εργασίας από την πρώτη φορά π την ανέβασαν... κ ούτε μια ανακοίνωση

ισχύει, πολύ ανεύθυνοι..

(και εμείς λίγο που δεν το γράψαμε εδώ)

Εμείς τρ που την κάναμε με την παλιά τι να κάνουμε ? έστειλα μαιλ στον παπαπαναγιωτου κ δν απαντάει. ..

παιδιά πόση ώρα κάνει η myconv2 σας να τρέξει και με τι μέγεθος εικόνας h; Εγώ που την έκανα με 4 for-loops κάνει γυρω στις 3 ωρες να τρέξει η κάθε επανάληψη για x[128x128] και h[128x128]..   :-\

άμα δυσκολεύεται τόσο, κάνε το h μικρότερη διάσταση, αφού σου δίνει το ελεύθερο να το ορίσεις όπου θες. Εσύ αυτό που θες να εξετάσεις είναι πως αλλάζουν οι χρόνοι συναρτήσει του [nxn] του πίνακα χ, κι από πλευρά ρεαλισμού, μπορεί κάλλιστα μια μάσκα να είναι της τάξης [3x3].

παρ' όλ' αυτά με τετραπλό βρόγχο και πάλι θα δυσκολευτεί για n>128

Παιδιά σχετικά με το ζητούμενο 2.2 . Στην myconvfreq2 , η συνέλιξη  θα πρέπει να είναι padded  και το αποτέλεσμα θα είναι πίνακας 3x4 ?Γιατί στο 2.1 ο πίνακας ειναι 4x5. Αν μπορεί κάποιος να βοηθήσει .

Στα γραφήματα με τις πολυπλοκότητες πρέπει η θεωρητική και η πειραματική πολυπλοκότητα να ταυτίζονται ή αρκεί να έχουν περίπου ίδιο τρόπο αύξησης?

τσέκαρε παραπάνω έχει παίξει ολόκληρη κουβέντα για το θέμα - (χωρις σαφή απάντηση βέβαια)

Ναι και εγώ συμμετείχα στην κουβέντα αλλά δεν καταλήξαμε κάπου. Εμένα πάντως μου βγαίνουν περίπου ίδιες αλλά όχι ακριβώς η μία πάνω στην άλλη.

κάνε pad τους αρχικούς πίνακες να φτάσουν και οι 2 το 4Χ5 (μετά απο εδώ ότι βρεις θα είναι 4Χ5)..Μετά τα κάνεις ένα shift,τα πας στο Fourier και τα πολλαπλασιάζεις..κάνεις τον inv Fourier και τα inv shift,. μετά από αυτό βγαίνει ίδιο αποτέλεσμα με την conv2 της matlab

Shift ? Τι shift? Μπορείς να κάνεις κατευθείαν ifft(fft2(A).*fft2(B)) , όπου Α και Β είναι οι padded - πίνακες αντίστοιχα.... όχι ?

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

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

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

Επειδή έχω χαωθεί λίγο, έχει μπερδέψει στην εκφώνηση την 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)

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

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


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

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

μμ όντως

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

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

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

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

Σημ: Πάντως το διάγραμμα για N^4 μου βγαίνει σχεδόν ίδιο με το πειραματικό, σε αντίθεση με το Ν^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);

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

Όσον αφορά στις πολυπλοκότητες  το κομμάτι του κώδικά μου για την 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 . Όχι;

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

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

Εμενα μου βγαινει αυτό!

τι στο καλό και η conv2 Ν^2*logN βγαίνει? (h σταθερός)

Στο ζητούμενο 2.2 φαντάζομαι απαγορεύεται η χρήση της fft2, e;

Tην fft2 θα χρησιμοποιήσεις. Υπάρχει και κάπου παραπάνω νομίζω πως το κανεις.

edit:

Στην εκφώνηση του 2.1 λέει απαγορεύονται έτοιμες συναρτήσεις του MATLAB όπως η conv2. Το να χρησιμοποιήσεις κάποια συνάρτηση για rotate ή για zero-padding θεωρείται "νόμιμο" ελπίζω ε;

φαντάζομαι πως εννοεί έτοιμες συναρτήσεις που να κάνουν την συνέλιξη :P

Ναι κι εγώ αυτό καταλαβαίνω, thx! :D

Στην myconv2freq πως σας βγαινουν οι καμπύλες, γιατί εμενα δε φαινεται να ταιριαζει με την Ν^2logN

Πιο πολύ μοιάζει με την N^3logN

Τζιρο , γενικά πάντως την έχει αλλάξει την άσκηση και τρέχει απο 2^κ μ κ=[2,10] .

Από την άλλη όπως και σε εμένα πολλαπλασιάζοντας με τον κατάλληλο παράγοντα Α  και βάζοντάς τες στο ίδιο διάγραμμα δείχνουν να έχουν κοινή συμπεριφορά. Όμως σίγουρα δεν έχουν τις ίδιες τιμές , δεν ξέρω πως το έβγαλες να είναι τοοοσο κοντά.

Για την freq έγραψα στο ποστ μου στην 5η σελιδα κάτι , είναι λάθος;

εδιτ : αυτό μου βγαίνει για την myconv2 - αριστερά ο μέσος χρόνος εκτέλεσης για τα αντιστοιχα NxN με Ν=2^κ και δεξιά η θεωρητική πολυπλοκότητα με Α=1/78000000...

Για ποιες διαστάσεις του h σου βγαίνει αυτός ο χρόνος εκτέλεσης; Η πολυπλοκότητα σου είναι O(N^4) ή O(N^2);

τις διαστάσεις της h που λέει να τις κρατήσουμε σταθερές,
τι διαστάσεις επιλέξατε εσείς ?

Πράγματι, παράξενο

edit για μεγαλύτερα k φαίνεται ότι το N^3logN αποκλίνει πολύ. απλά γίνεται matching στην περιοχή που μας ενδιαφέρει και παρασύρει. αντιθέτως, η N^2logN έχει καλή συμπεριφορά για μεγάλα Ν

μία άλλη λύση που χρησιμοποίησα για να είναι εφικτή η σύγκριση των δύο καμπυλών, είναι να κανονικοποιήσεις τα αποτελέσματα. Διαίρεσα όλες τις θεωρητικές τιμές κι όλες τις πειραματικές τιμές με την αντίστοιχη μέγιστη τιμή ( max() ). Εν τέλει και οι δύο καμπύλες πέφτουν η μία πάνω στην άλλη με ελάχιστη απόκλιση. Το μόνο αρνητικό είναι ότι δεν είναι οι πραγματικοί χρόνοι εκτέλεσης. Έκανα αυτή τη λύση κι έγραψα σχόλιο στην αναφορά... Δείτε για παράδειγμα πως βγήκε το διάγραμμα για την FFT.

το h έχει τις αρχικές διαστάσεις που μας δίνει η άσκηση στο data.mat για το x . Το γιατί είναι οι διαστάσεις του x και όχι του y το καταλαβαίνεις νομίζω από τα συμφραζόμενα στην εκφώνηση. Είναι 3χ4 και η πολυπλοκότητα O(Ν^4)  αλλά μάλλον επειδή οι διαστάσεις της h είναι σταθερές , η πολυπλοκοτητα να είναι όντως Ο(Ν^2) . Για πειτε...

εξαρτάται και από την υλοποίησή σου αυτό, αν κάνεις zero padding, μάλλον  O(Ν^4) θα σου βγει

Zero padding στην myconv2? Όχι ρε συ , στην freq μόνο padding έκανα. Οπότε τελικά νομίζω είναι Ο(Ν^2). Επίσης λογικό να εμφανίζονται και ακραίοι χρόνοι για Ο(Ν^4) παρά την παρόμοια συμπεριφορά. :o :o

παρόμοια συμπεριφορά για Ο(Ν^4) και Ο(Ν^2) εννοείς?? εμένα με την myconv2 μου έχει βγει ένα Ο(Ν^2) όσο δεν πάει! καλύτερο match και από το fft2 :P

Οταν κανω τα διαγράμματα για το 1ο ζήτημα δε μου , αυτό για τη θεωρητική βγαίνει εκτός plot ,δε φαινεται καν.Ξερει κανείς τι μπορεί να φταίει?

Θέλει κανονικοποιηση γιατί η μια καμπυλη εχει πολύ μεγαλες τιμές σε σχέση με την άλλη.

Όταν λες με την μέγιστη τιμή? Ποιας καμπύλης της θεωρητικής η του execution time?Γιατι και εμένα έχουν αρκετή απόκλιση

τι εννοεί ο ποιητής με το encoding σε utf-8? θέλει και επέκταση .txt? (αρχεία κειμένου)

Εγώ τα έγραψα κανονικά στο MATLAB στην default κωδικοποιησή τους και μετά απλά τα άνοιξα όλα με ένα απλό notepad και τα έκανα ένα ένα save as αλλάζοντας την κωδικοποίηση.
Η επέκταση παραμένει .m. Απλά όταν τα ξανάνοιξα στο MATLAB για να δω αν έχει αλλάξει κάτι μου έβγαζε δύο χαρακτήρες περίεργους στην αρχή. Τους διέγραψα και ήμουν οκ.

Προφανώς το πιο εύκολο και ορθόδοξο είναι να αλλάξεις την κωδικοποίηση που χρησιμοποιεί το ΜΑΤLAB αλλά η $!%^@^ δε μ'άφηνε να πειράξω το startup.m αρχείο, οπότε, για να μη χάνω πολύ χρόνο, το παράτησα.

Υ.Γ. Αφού αλλάξετε κωδικοποίηση έτσι, μπακάλικα, κάνετε ένα test run σε όλα καλού κακού...

το αλλάζω και από μέσα αλλά απ ότι κατάλαβα δεν είναι κάτι ουσιαστικό