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

4.2. SOLUZIONE ALLE PROBLEMATICHE DELL’ARCHITETTURA LUT

90

4.2.4 Algoritmo di scomposizione
v9—lgoritmo proposto iter— su tutti i possi˜ili v—lori d— H — PSSD ™he ™ostituis™ono
i v—lori —ssumi˜ili d— un pixel ™on livelli di grigio — V ˜itF ƒuddivide il r—nge degli
interi positivi in n CI intorniDuno per ogni p—rte dell— p—rtizioneF ygnuno degli
interv—lli è limit—to d— un v—lore ™he nel nostro list—to è ™ontenuto nel —rr—y
vettoresntorniF v9—rr—y vettore€otenze ™ontiene i ™oe0™ienti dell— p—rtizione di
f—™hetF vsws„i de(nis™e l9intero positivo sull— qu—le l— p—rtizione di f—™het
viene ™ostruit—F
h—t— l— p—rte λi dell— p—rtizioneD l9intorno ™orrispondente h— un r—ggio p—ri
—ll— somm— di tutte le λj ™on j ∈ {0, 1, 2..., i − 1}F v9el—˜or—zione prevede
™he ogni intero positivo in input veng— di volt— in volt— ™onfront—to ™on i limE
iti degli intorni dei ™oe0™ienti dell— p—rtizioneF u—l9or— l9intero risult— m—gE
giore del limite dell9iEesimo intorno —llore d—ll9intero v— sottr—tto il ™oe0™iente
dell— p—rtizione ™orrispondente —ll9intornoF e questo punto v—nno v—lut—te Q
™ondizioniX
IF ƒe il risult—to dell— sottr—zione è un v—lore m—ggiore di HD vuol dire ™he
l— p—rte dell— p—rtizione —ppen— sottr—t— f— p—rte dell— s™omposizione di
f—™het dell9intero e il f—ttore βi = 1F v— ™omput—zione ™ontinu— per il
su™™essivo intornoY
PF ƒe il risult—to dell— sottr—zione è un v—lore minore di HD vuol dire ™he
l— p—rte dell— p—rtizione —ppen— sottr—t— f— p—rte dell— s™omposizione di
f—™het dell9intero e il f—ttore βi = −1F v— ™omput—zione ™ontinu— per
il su™™essivo intorno utilizz—ndo nell— ™omput—zione il v—lore —ssoluto del
risult—toY
QF ƒe il risult—to è p—ri — H —llor— l9—lgoritmo termin—F
v9—n—lisi ™omput—zion—le dell9—lgoritmo è piuttosto immedi—t—F f—st— ™onsiderE
—re ™he il numero delle oper—zioni ™ompute per ogni intorno è presso™™hè ™ost—nte
e il numero di intorni è p—ri — log3 (m) + 1Fgiò ™i ™ondu™e —d un— ™omplessità
™omput—zion—le y@log@nAAF