Tesi Robotica Un coprocessore per Visual Search: Keypoint... | Page 62

3.3. COSTRUZIONE DEL KERNEL E VALUTAZIONE COMPUTAZIONALE

ˆ

62

snoltre vengono ripetute diverse volte le medesime oper—zioniD ™on un
—ggr—vio sul ™osto ™omput—zion—le (n—leF

porti di queste ™onsider—zioni pro™edi—mo ™on l9ottimizz—zione dell9—lgoritmoF

3.3.2 Applicazione della proprietà di separabilità: ltro
1+1D
ger™hi—mo di trov—re un— soluzione —ll— e™™essiv— ™omplessità ™omput—zion—le
evidenzi—te nel pre™edente p—r—gr—fo d—ll— nostr— —n—lisi del (ltro ™on m—s™her—
— ™onvoluzione ˜idimension—leF €er r—ggiungere il nostro o˜iettivo prendi—mo
spunt— d— un— proprietà dell— funzione q—ussi—n— ™he —˜˜i—mo già des™ritto nel
p—r—gr—fo dedi™—to —ll9—rgomentoF giò ™he ™i interess— è l— proprietà di sep—r—E
˜ilità funzioneF …n— funzione g—ussi—n— ˜idimension—le risult— otteni˜ile ™ome
il prodotto di due funzioni g—ussi—ne monodimension—li senz— —l™un— perdit— di
inform—zioneF porm—lmente possi—mo s™rivereX

G(x, y) = G(x) · G(y) = Ae

−x2
2
2σ1

· Be

−y 2
2
2σ2

uest— proprietà è molto interess—nte d—to ™he ™i permette di ride(nire ™omE
plet—mente l9oper—zione di ™onvoluzione pre™edentemente introdott— eD ™ome veE
dremoD di ridurre l— ridond—nz— dell— nostr— m—s™her—F ƒfrutt—ndo l— proprietà
di sep—r—˜ilità possi—mo des™rivere l— ™onvoluzione dell— g—ussi—n— ˜idimensionE
—le in questo modoX

G(x, y) ∗ I(x, y) =
=

M −1
α=0

G(α)

M −1
α=0

N −1
β=0

N −1
β=0

G(α, β) · I(x − α, y − β) =

G(β) · I(x − α, y − β)

ove G(α) e G(β) r—ppresent—no le due g—ussi—ne monodimension—li il ™ui
prodotto ™i fornis™e l— g—ussi—n— ˜idimension—leF
enzi™hé utilizz—re un— ™ostruzione ˜idimension—le usi—mo due —rr—yD inE
du™endo si™ur—mente un— sempli(™—zione nelle strutture su ™ui l9—lgoritmo l—vor—
e un primo risp—rmio di lo™—zioni di memori—F snoltre intui—mo ™he il risp—rmio
non si limit— solo — questoX moltipli™—ndo preventiv—mente tutti i ™oe0™ienti
presenti su un— rig— @o ™olonn— A dell9imm—gine ™—mpione ™i permette di ridurre