Trovare il massimo...

[marcus81]

Salve,
sto implementando un algoritmo in matlab e devo trovare il valore definito nell'intervallo tra 0 e 255 che mi massimizza una certa funzione.
Attualmente l'ho implementato in modo brutale, cioè con un ciclo for da 0 a 255 che mi calcola ogni volta il valore della funzione e che controlla se ho trovato un nuovo massimo.
Ovviamente l'algoritmo, che lavora su immagini, risulta piuttosto lento...
avete consigli al riguardo?
Grazie :)

[71104]

dipende dalla funzione :)
puoi riportarla qui?

[Blackat]

se non ricordo male dovrebbe essere

> max(f([0..255])

dove f è la funzione che devi massimizzare. :confused:

[71104]

appunto, io volevo sapere com'è fatta f...

[lombardp]

appunto, io volevo sapere com'è fatta f...

Blackat, se interpreto bene quello che 71104 vuole dirti, se si conosce la funzione f di cui parli, la ricerca del massimo potrebbe essere fattibile per via analitica, il che semplificherebbe molto la ricerca. Altrimenti non c'è modo, l'unico miglioramente che puoi ottenere è nell'implementazione in C/C++.

...sempre che abbia capito il problema.

[Blackat]

Attualmente l'ho implementato in modo brutale, cioè con un ciclo for da 0 a 255 che mi calcola ogni volta il valore della funzione e che controlla se ho trovato un nuovo massimo.

Lombardp io ho capito che lui ha una funzione f, fa un ciclo da 0 a 255
e ogni volta calcola il valore di f applicato all'indice del ciclo.

Volevo rispondere a 71104 dicendo che dipende da che calcolo deve
fare la funzione f.

Ricorda che il motore di matlab lavora con gli array e le matrici e che
quindi i cicli for risultano molto lenti.

Per utilizzare le operazioni come moltiplicazione e divisione
tra matrici o array devi utilizzare il punto prima dell'operatore.
Se devi fare, ad esempio, la somma tra due array dovresti scrivere:

> [ 1 2 3 ] + [ 4 5 6 ]
[5 7 9]

> [1 2 3] .* [ 4 5 6 ]
[4 10 18]

le funzioni in matlab si definiscono come
function [r1,r2,...,rn] = f(p1,p2,...pn)
.....
.....

....

dove r1,r2, ..., rn sono i valori di ritorno e p1,p2,pn sono i
parametri in input.
La funzione deve essere salvata in un unico file che si chiama
con lo stesso nome della funzione e con estensione ".m" .

Esempio ( somma.m )

function r = somma(a,b)
r = a + b

[71104]

morta'... :mbe:
allora possono essere funzioni qualunque, e quindi non c'è scampo a meno che non sia possibile fare proprio il parsing della funzione e far procedere il programma come se fosse un essere umano che studia la funzione :mbe:
dovresti fare la derivata e trovare i punti in cui si annulla... abbastanza facile una volta fatto il parsing, ma il parsing chi lo fa? :D

[lombardp]

morta'... :mbe:
allora possono essere funzioni qualunque, e quindi non c'è scampo a meno che non sia possibile fare proprio il parsing della funzione e far procedere il programma come se fosse un essere umano che studia la funzione :mbe:
dovresti fare la derivata e trovare i punti in cui si annulla... abbastanza facile una volta fatto il parsing, ma il parsing chi lo fa? :D

Si infatti, allora avevo capito bene, se c'è possibilità di farlo per via analitica bene, altrimenti on c'è scampo.

[marcus81]

Salve ragazzi, la funzione non è semplicissima.
Perchè calcola la media dei pixel di 2 classi ricavate da un'immagine, poi effettua la deviazione standard e altre cosette.
L'ho alleggerita parecchio grazie al fatto che calcolo la media invece che sui pixels dell'immagine direttamente, sui valori dell'istogramma dell'immagine.
Adesso calcola il massimo in modo quasi immediato!
Più di questo non credo si possa fare, anche perchè ripeto la funzione non è banale.
Cmq grazie a tutti ;)

[71104]

Salve ragazzi, la funzione non è semplicissima.
Perchè calcola la media dei pixel di 2 classi ricavate da un'immagine, poi effettua la deviazione standard e altre cosette.
L'ho alleggerita parecchio grazie al fatto che calcolo la media invece che sui pixels dell'immagine direttamente, sui valori dell'istogramma dell'immagine.
Adesso calcola il massimo in modo quasi immediato!
Più di questo non credo si possa fare, anche perchè ripeto la funzione non è banale.
Cmq grazie a tutti ;)
quindi non erano funzioni qualunque: questa tua funzione era comunque ricondicibile a qualche forma canonica; forse ti sarebbe stato di aiuto studiarne la derivata in questa forma canonica e trovare i punti in cui si annulla (anche se in funzione di qualche variabile).

[marcus81]

Si ma sarebbe stato molto lungo come procedimento. Con il for ho fatto prima e siccome la variabile va da 0 a 255 non risulta per niente pesante ;)

[a2000.1]

Salve,
sto implementando un algoritmo in matlab e devo trovare il valore definito nell'intervallo tra 0 e 255 che mi massimizza una certa funzione.
Attualmente l'ho implementato in modo brutale, cioè con un ciclo for da 0 a 255 che mi calcola ogni volta il valore della funzione e che controlla se ho trovato un nuovo massimo.
Ovviamente l'algoritmo, che lavora su immagini, risulta piuttosto lento...
avete consigli al riguardo?
Grazie :)

algoritmo dei 5 punti o della sezione aurea.

[Marcalessio]

L'algoritmo della sezione aurea è utile e veloce solo che da delle informazioni di tipo locale...

[marcus81]

Come funziona, in sintesi, questo algoritmo della sezione aurea?
sono curioso :D

[giannimesa]

se non erro quindi il problema è di ricerca operativa...di solito viene ricercato il minimo... di una f... invece te devi cercare il max... bhe... basta invertire la f... :)
poi dovresti applicare a mio avviso un algoritmo del simplesso... matlab dovrebbe lavorarci bene... però se te hai bisogno di un numero nell'intervallo [0, 255] allora il problema è più complesso e devi andare sulla programmazione lineare intera...PLI...o ILP (inglese), un algoritmo che andrebbe bene dovrebbe essere quello del Cutting Plane...ma ce ne sono molti altri... fatto sta che per capirli ci vogliono delle nozioni di Programmazione lineare, in particolare bisogna conoscere il metodo del simplesso...con i varii test di ottimalità, aggiornamento di base, e aggiornamento della matrice inversa della base (corrente).... :p si insomma non è proprio una passeggiata, ma se ti interessa la velocità penso sia il miglior metodo...

Tra l'altro trovi diversi programmini che sviluppano l'algoritmo del simplesso... CIAO ;)