Quadratic pseudo-Boolean optimisation: differenze tra le versioni

Versione delle 16:02, 30 dic 2018

Versione delle 19:53, 1 gen 2019

Riga 3:

:<math> f(\mathbf{x}) = w_0 + \sum_{p \in V} w_p(x_p) + \sum_{(p, q) \in E} w_{pq}(x_p, x_q) </math>

nelle variabili binarie <math>x_p \in \{0, 1\} \; \forall p \in V = \{1, \dots, n\}</math>, con <math>E \subseteq V \times V</math>. Se <math>f</math> è submodulare QPBO produce un ottimo globale in maniera equivalente a [[graph cut]], mentre se <math>f</math> contiene termini non submodulari l'algoritmo produce una soluzione parziale con specifiche proprietà di ottimalità, in entrambi i casi in tempo polinomiale.<ref name="review" />

QPBO haè applicazioniusato nell'inferenza su [[campo di Markov casuale|campi di Markov casuali]] (MRF) e [[campo condizionale casuale|campi condizionali casuali]] (CRF), ampiamentee usatiha applicazioni in applicazioniproblemi di [[visione artificiale]] come [[segmentazione di immagini|segmentazione]] e [[stereo matching]].<ref name="rother" />

== Ottimizzazione di funzioni non submodulari ==