Sistemi operativi - tesina robot di sistemi operativi

1

AIELLO MARCO

MATR. 045 / 004437

C.D.L. ING. ELETTRONICA V.O.

ESERCITAZIONI DI SISTEMI

OPERATIVI VARIANTE DELLA

ESERCITAZIONE 2 , 2° SOLUZIONE

“SISTEMA DI VISIONE ROBOTICA PER

LA NAVIGAZIONE AUTONOMA” 1

INTRODUZIONE

La realizzazione di un semplice micro robot dotato un elementare sistema di visione

artificiale per la navigazione autonoma , ben si presta ad offrire una 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. 1

E’ 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.

E’ 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

• 1

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 all’ 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 una 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ò 1

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);

col quale si è ottenuta la seguente matrice:

G = 1

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:

H(i,j) =

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à , 1

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 1

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 , 1

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 immagi-

ne 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 grigio

pause;

indice1=160; %dimensione colonne immagine

indice2=120; %dimensione righe immagine

PSF = [ %matrice gaussiana 10 x 10 usata come kernel per il blurring dell'immagi-

ne 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; 1

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 1

%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

5 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 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 11 11 11 11 11 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 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 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= 2*sqrt_vett(media); % soglia per Sobel è 2*(media)^1/2

%soglia= sqrt_vett(media); % soglia per Sobel è 2*(media)^1/2

soglia= 5*sqrt_vett(media); % soglia per Sobel è 2*(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;

% apprssimo 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; 1

%ricerca l'ostacolo più prossimo nell'immagine binarizzata (è quello a minima or-

dinata)

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); 1

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 una 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 1

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);