Sistemi operativi - tesina robot di sistemi operativi

Aiello Marco Matricola 045 / 004437

C.d.l. Ing. Elettronica V.O.

Esercitazioni di sistemi operativi

Variante dell'esercitazione 2, 2° soluzione

Sistema di visione robotica per la navigazione autonoma

Introduzione

La realizzazione di un semplice micro robot dotato di un elementare sistema di visione artificiale per la navigazione autonoma ben si presta ad offrire un'applicazione sul campo delle nozioni acquisite di sistemi operativi e di programmazione concorrente. In particolare il robot è dotato di una coppia di motori in corrente continua che gli permettono di andare dritto, di sterzare a destra, a sinistra e di fermarsi.

È provvisto inoltre di una scheda di potenza per il pilotaggio dei motori. I comandi a tale scheda vanno inoltrati rispettando un apposito protocollo di comunicazione su porta seriale impostata per una trasmissione di otto bit dati, un bit di stop, niente parità e con una Baud rate di 9600 bps.

È presente inoltre una webcam che viene usata per acquisire delle immagini in grayscale utilizzate come ingresso per il sistema di visione artificiale e di navigazione. Il robot, per poter funzionare, deve eseguire l’acquisizione dell’immagine, la sua elaborazione ed infine sulla base del risultato di questa, deve provvedere ad aggiornare la direzione nella quale sta attualmente muovendosi.

Pertanto è possibile strutturare il tutto come un problema di singolo produttore e singolo consumatore: il produttore si occupa di acquisire un frame in grayscale dalla webcam e lo deposita in un buffer di memoria condivisa. Il consumatore invece, preleva il frame dal buffer e lo elabora opportunamente ed aggiorna infine su porta seriale la direzione di navigazione.

Anche i vincoli del problema produttore/consumatore sono rispettati: il consumo del buffer di memoria comune (allocato dal processo padre) da parte del processo consumatore non può avvenire se non dopo che il processo produttore vi abbia depositato un contenuto, e all'atto del consumo tale contenuto viene cancellato. Infatti se prima non acquisisco un nuovo frame, non posso elaborarlo e non posso di conseguenza aggiornare la direzione di navigazione. Il processo produttore non può depositare nel buffer di memoria comune un nuovo contenuto se il precedente non è stato ancora consumato, altrimenti rischierei di far pervenire al consumatore un frame corrotto. A garanzia della consistenza del contenuto del buffer condiviso, processo consumatore e processo produttore devono accedervi in mutua esclusione.

Descrizione dell'algoritmo di navigazione

Per la navigazione robotica ci si è ampiamente ispirati all’algoritmo di navigazione implementato originariamente per il robot “Polly” sviluppato al M.I.T. nel 1992 (ampiamente descritto nell’articolo “A simple cheap and robust visual navigation system”, Ian Horswill, SAB92, 1992). Il primo passo dell’algoritmo consiste nell’acquisire un'immagine in grayscale dalla webcam con una bassa risoluzione di 120 x 160 pixel. Sebbene la webcam sia capace di acquisire immagini a colori in formato RGB, ciò sarebbe stato inutilmente oneroso visto che non si è fatto uso di nessuna informazione di tipo colorimetrico. L’overhead computazionale derivante dall’avere a che fare con una matrice di terne RGB quindi, vista l’applicazione, non sarebbe stato per niente giustificabile e per tale motivo, si è scelto di acquisire l’immagine in grayscale.

In tale formato, ogni elemento della matrice rappresenta l’intensità di ogni pixel tramite un intero senza segno ad otto bit, i cui valori pertanto cadono nell’intervallo [0,255]. Successivamente si effettua un “blurring” dell’immagine mediante filtraggio gaussiano che attenua le componenti ad alta frequenza, non provoca una grossa perdita dei dettagli e sfuma i contorni creando un effetto di foto mossa e sfuocata: tale filtraggio viene effettuato mediante il prodotto di convoluzione dell’immagine originaria in grayscale con una matrice gaussiana quadrata di ordine 10 (che è il cosiddetto “kernel” o anche “maschera” del filtro). Tale matrice è stata ottenuta in MATLAB tramite il comando: PSF = fspecial('gaussian',10,10);

Detto F(i,j) un pixel dell’immagine originaria da filtrare e G(i,j) un elemento del kernel del filtro, il pixel H(i,j) della matrice filtrata viene ottenuto tramite un prodotto di convoluzione discreta, come di seguito indicato:

Poiché questa operazione è computazionalmente molto onerosa (nel nostro caso infatti bisogna fare 120 x 160 x 10 prodotti e somme in virgola mobile), nella pratica raramente si usano kernel più grossi di 15 x 15 elementi, una dimensione tipicamente utilizzata è di 3 x 3 elementi. In questo modo viene eliminato anche il cosiddetto rumore “salt and pepper” costituito da punti luminosi su uno sfondo scuro e punti scuri su sfondo illuminato.

L’algoritmo di navigazione è stato reso, entro certi limiti, più robusto nei confronti di condizioni di illuminazione non uniformi o peggio ancora; variabili nel tempo, utilizzando una semplice tecnica di “adaptive thresholding” in cui si usa una soglia variabile dinamicamente per la binarizzazione dell’immagine. Infatti, sulla versione filtrata di ogni frame acquisito, viene preliminarmente fatto il calcolo del valore medio dei pixel costituenti l’immagine e poi, il valore di soglia, viene ottenuto a partire da tale parametro. Per essere più precisi, si sceglie come valore di soglia cinque volte la radice quadrata del valore medio di tutti i pixel dell’immagine filtrata.

Successivamente si ricorre all’algoritmo di “edge detection” di Sobel per poter trovare all’interno dell’immagine i contorni di tutti gli oggetti ripresi dalla webcam nel frame attualmente esaminato. Quest’algoritmo in pratica, si occupa di trovare le zone dell’immagine in cui si hanno cambiamenti di contrasto (ossia zone in cui ho variazioni di intensità), infatti in tali zone si trovano i contorni degli oggetti poiché essi sono di intensità diversa dallo sfondo. Quindi, poiché i contorni si trovano laddove ho un brusco cambiamento di intensità, per rilevarli si effettua una differenziazione dell’immagine per localizzarli (la differenza tra punti vicini approssima la derivata prima nel loro intorno). Poiché differenziando una zona a intensità costante ottengo un risultato nullo, ho così una nuova matrice in cui mappo le variazioni di intensità, più queste sono brusche in un punto e ivi è tanto maggiore in modulo l’elemento della matrice.

L’algoritmo di Sobel in particolare differenzia tra loro pixel adiacenti sia in verticale, in modo da trovare contorni verticali, che in orizzontale; per la localizzazione invece di contorni orizzontali. In questo modo sommando tra loro i due contributi ottengo il quadrato del modulo del gradiente in ogni punto dell’immagine originaria. L’algoritmo usa come kernel del prodotto di convoluzione le seguenti matrici: Di cui la prima Sx, serve a trovare i contorni orizzontali e la seconda Sy, quelli verticali.

L’effetto della sua applicazione sull’immagine sfuocata è il seguente: A questo punto è possibile finalmente trovare i contorni degli oggetti tramite un processo di binarizzazione dell’immagine sottoposta all’algoritmo di edge detection di Sobel. In pratica si tratta di scandire un pixel alla volta l’immagine, sostituendo al pixel originario un pixel bianco se il valore del gradiente approssimato è in modulo maggiore della soglia preventivamente calcolata, oppure un pixel nero se questo valore di soglia non viene superato. Il risultato del processo di binarizzazione è il seguente:

A questo punto si riescono a ricavare i bordi degli oggetti (che sono le parti bianche dell’immagine formata dai soli due colori: bianco e nero) ed ora è possibile creare una mappatura della distanza degli ostacoli. Infatti scandendo da sinistra verso destra e dal basso verso l’alto l’immagine binarizzata si ottiene un grafico composto dalle minime ordinate dei pixel bianchi trovati in ciascuna colonna: in questo modo ottengo il vettore della distanza degli ostacoli più vicini, successivamente viene effettuato un filtraggio ed una riduzione della dimensione di tale vettore, sostituendo ad ogni dieci valori il loro valore medio:

A questo punto il vettore viene diviso in tre parti, una per ciascuna delle tre direzioni di marcia, ed in ognuna di esse viene effettuata successivamente la ricerca del valore massimo. In questo modo; si sterza nella direzione in cui si è trovato tale massimo, che è così anche la direzione in cui si è trovato l’ostacolo più lontano.

Per la messa a punto dell’algoritmo è stato di vitale importanza l’uso del MATLAB che ha permesso di testare rapidamente il suo funzionamento, senza occuparsi di dettagli di basso livello per la comunicazione con le periferiche e per la gestione della memoria e di altri aspetti di natura hardware.

Si riporta di seguito lo script usato in MATLAB che implementa il sistema di navigazione precedentemente descritto:

clc; clear; %pulisce il workspace rgb = imread('C:\Documents and Settings\z80\Desktop\Image004.jpg'); %legge immagine a colori da file imshow(rgb); %la mostra pause; gray=rgb2gray(rgb); %converte in toni di grigio 0.2989*R +0.5870*G +0.1140*B imshow(gray); %mostra immagine in toni di grigi pause; indice1=160; %dimensione colonne immagine indice2=120; %dimensione righe immagine PSF = [ %matrice gaussiana 10 x 10 usata come kernel per il blurring dell'immagine in toni di grigio 0.0089 0.0092 0.0095 0.0097 0.0098 0.0098 0.0097 0.0095 0.0092 0.0089; 0.0092 0.0096 0.0099 0.0101 0.0102 0.0102 0.0101 0.0099 0.0096 0.0092; 0.0095 0.0099 0.0102 0.0104 0.0105 0.0105 0.0104 0.0102 0.0099 0.0095; 0.0097 0.0101 0.0104 0.0106 0.0107 0.0107 0.0106 0.0104 0.0101 0.0097; 0.0098 0.0102 0.0105 0.0107 0.0108 0.0108 0.0107 0.0105 0.0102 0.0098; 0.0098 0.0102 0.0105 0.0107 0.0108 0.0108 0.0107 0.0105 0.0102 0.0098; 0.0097 0.0101 0.0104 0.0106 0.0107 0.0107 0.0106 0.0104 0.0101 0.0097; 0.0095 0.0099 0.0102 0.0104 0.0105 0.0105 0.0104 0.0102 0.0099 0.0095; 0.0092 0.0096 0.0099 0.0101 0.0102 0.0102 0.0101 0.0099 0.0096 0.0092; 0.0089 0.0092 0.0095 0.0097 0.0098 0.0098 0.0097 0.0095 0.0092 0.0089]; %blurring con filtraggio a correlazione con matrice gaussiana 10 x 10 mio_blurring = zeros(indice2-9,indice1-9); %crea matrice di tutti zeri for j=1:(indice1-9) %effettua blurring con prod. di convoluzione tra immagine e kernel PSF for i=1:(indice2-9) tmp=0; for k = 1 :10 for l=1:10 pixel_corrente=single(gray(i+k-1,j+l-1)); tmp=tmp+(PSF(k,l)*pixel_corrente); end mio_blurring(i,j)=uint8(tmp); end end end my_blurring=uint8(mio_blurring); imshow(my_blurring); %mostra immagine blurred pause; %edge detection del primo ordine con algoritmo di Sobel e soglia automatica mio_edge = zeros(indice2-9,indice1-9); %crea matrice di tutti uni (tutto bianco) x_mask=[-1 -2 -1; 0 0 0; 1 2 1]; %kernel per edge detection lungo x y_mask=[ 1 0 -1; 2 0 -2; 1 0 -1]; %kernel per edge detection lungo y elements = (indice1-9)*(indice2-9); ed_im_dims0 = indice1-9; ed_im_dims1 = indice2-9; conta=0; sog=0; for Y=1:ed_im_dims1 %indice di riga for X=1:ed_im_dims0 %indice di colonna sog=sog + int32(my_blurring(Y,X)); conta=conta+1; end end media=sog/conta; %trovo la media degli elementi dell'immagine in grayscale %per ottenerlo faccio: % 1) a=linspace(1,256,256) ed ottengo un vettore dei numeri da 1 a 256 % 2) sqa=sqrt(a) ed ho le radici quadrate di 1 a 256 con la virgola % 3) flsqa=floor(sqa) e tolgo la virgola alle radici % e poi lo copio dal workspace sqrt_vett = [1 1 1 2 2 2 2 2 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5 5 6 6 6 6 6 6 6 6 6 6 6 6 6 6 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 16]; %vettore delle radici quadrate da 1 a 255 trattate con floor soglia= 5*sqrt_vett(media); %soglia per Sobel è 5*(media)^1/2 %calcola il prodotto di convoluzione coi due kernel for Y=1:ed_im_dims1-1 %indice di riga for X=1:ed_im_dims0-1 %indice di colonna if( Y==0 || Y==ed_im_dims1-1) %se sono ai bordi dell’immagine(righe ) SUM = 0; elseif( X==0 || X==ed_im_dims0-1) %se sono ai bordi dell’immagine(col ) SUM = 0; else s_lungo_x = 0; s_lungo_y = 0; SUM = 0; %approssimo gradient lungo x ed y for I=1:3 for J=1:3 prod_parz_x = int16(my_blurring(Y+J-1,X+I-1)) * x_mask(J,I); prod_parz_y = int16(my_blurring(Y+J-1,X+I-1)) * y_mask(J,I); s_lungo_x = s_lungo_x + prod_parz_x; s_lungo_y = s_lungo_y + prod_parz_y; end end end x=abs(s_lungo_x); y=abs(s_lungo_y); SUM = x+y; if(SUM > 255) %saturazione dei valori SUM = 255; %bianco=1 elseif(SUM < 0) SUM = 0; %nero=0 end if(SUM > soglia) %effettuo binarizzazione mio_edge(Y,X) = 1; else mio_edge(Y,X) = 0; end end imshow(mio_edge); %mostra immagine binarizzata dopo l'edge detection pause; %ricerca l'ostacolo più prossimo nell'immagine binarizzata (è quello a minima ordinata) picco= zeros(indice1-9,1); %costruisce vettore delle minime ordinate di dove ho trovato il bianco (spigolo) for mm = 1:indice1-9 %per ogni ascissa picco(mm)=indice2-9; %inizializzo end for mm =1:indice1-9 %per ogni ascissa for nn = indice2-9-5:-1:5 %per ogni ordinata if(mio_edge(nn,mm)==1) %trova la minima ascissa del pixel bianco picco(mm)=indice2-nn-9; %e salva l'ordinata nel vettore picco break; end end end plot(picco); pause; media= zeros(30,1); %costruisce vettore della media delle minime ordinate indice=1; for mm = 0:5:(indice1-10)-9 somma = 0; for nn = 0:4 somma=somma+picco(nn+mm+1); %picco è il vettore che dice la max ordinata del pixel bianco dell'immagine binarizzata end media(indice)=floor(somma/10); indice=indice+1; end plot(media); pause; %trova il massimo nel vettore delle medie degli oggetti più vicini nella zona destra dell'immagine max_sx=media(1); for i=1:10 if(media(i)>max_sx) max_sx=media(i); end end %trova il massimo nel vettore delle medie degli oggetti più vicini nella zona centrale dell'immagine max_centro=media(10); for i=10:20 if(media(i)>max_centro) max_centro=media(i); end end %trova il massimo nel vettore delle medie degli oggetti più vicini nella zona sinistra dell'immagine max_dx=media(20); for i=20:30 if(media(i)>max_dx) max_dx=media(i); end end %decide dove sterzare if(max_sx>max_dx && max_sx>max_centro) direzione='sinistra'; elseif(max_dx>max_sx && max_dx>max_centro) direzione='destra'; else direzione='centro'; end disp('********************************'); disp(''); disp('girare a ....'); disp(direzione); disp(''); disp('********************************');

Da verifiche sul campo, si è dimostrato computazionalmente troppo oneroso l’uso di un’immagine di 160 x 120 pixel. Poiché la webcam permette in hardware di acquisire come minima risoluzione possibile, solo immagini in tale formato, è stato necessario dunque ridurne le dimensioni via software. L’algoritmo utilizzato a tal fine, scandisce l’immagine dall’alto verso il basso e da sinistra verso destra, poi ad ogni quattro pixel adiacenti, sostituisce la media aritmetica del loro valore, ottenendo in tal modo il nuovo pixel dell’immagine ridotta. In questo modo si riesce a ridurre della metà le dimensioni dell’immagine acquisita. Lo script Matlab che realizza tale riduzione è il seguente:

gray = dlmread('C:\Documents and Settings\z80\Desktop\gray_inv.doc'); imshow(uint8(gray)); disp('immagine originale'); pause; indice1=160; %dimensione colonne immagine indice2=120; %dimensione righe immagine % crea matrice per resize mio_resize = zeros(indice2/2,indice1/2-2); %crea matrice di tutti zeri ind_ri=1; %indice riga matrice resized ind_co=1; %indice colonna matrice resized for i=1:2:indice2 %per tutte le righe disp('i ='); disp(i); for j=1:2:indice1 %per tutte le colonne disp('j ='); disp(j); a=gray(i,j); b=gray(i,j+1); c=gray(i+1,j); d=gray(i+1,j+1); media=a+b+c+d; media=media/4; mio_resize(ind_ri,ind_co)=uint8(media); ind_co=ind_co+1; disp('******************* ind_co ='); disp(ind_co);