In questi giorni prima di rimettermi in moto in vista della tesi di laurea, ho ultimato e perfezionato un progetto personale che consiste nel riconoscere i gesti della mano utilizzando EmguCV. Le tecniche con cui è possibile estrarre e riconoscere una mano sono molteplici. Nell’approccio scelto sono andato a lavorare su alcuni spazi di colore quale ad esempio YCrCb oppure Hsv definendo una particolare regione dello spazio che contiene la distribuzione di colore della pelle. Eseguito questo filtraggio si ottiene una maschera binaria della nostra mano, che successivamente viene processata al fine di rimuovere il rumore residuo. Dopo aver ottenuto questa maschera binaria è possibile estrarne il contorno e calcolare la Convex Hull. Da questa attraverso un’analisi della convessità con la quale si formano le varie regioni comprese tra il contorno della mano e la convex hull è possibile ottenere delle misure significative che permettono di calcolare come fatto il numero delle dita. Il riconoscimento dei gesti può essere utilizzato in molteplici scenari applicativi tipici dell’ interazione uomo macchina.

E’ possibile scaricare l’intera solution VS10 sul mio account dropbox:

1) Full Demo Solution (Code + video 43Mb)
http://db.tt/MukGcwB
2) Full Demo Code (5Mb)
http://db.tt/GkT6J9k

Un doveroso ringraziamento ad Andol per avermi già citato in uno dei suo post e per i vari feedback ricevuti.

Ad maiora

Sulla scia del post precedente e dei commenti ricevuti, in particolar modo ho riflettuto molto sull’accusa :) mossa da Antonio circa la violazione dell’information hiding (aka stupro di oggetti) condivido l’approccio che ho seguito nel disegnare il parser per espressioni regolari a discesa ricorsiva (Recursive Descent Parser). Senza scendere troppo nei dettagli di come operi un parser, diciamo che in una prima fase il Parser esegue analisi lessicale appoggiandosi ad un oggetto Tokenizer che ha il compito di trasformare una stringa in input (nel caso in esame una regex) in uno stream di Tokens. Un token rappresenta un elemento di una regex che può essere quindi un semplice simbolo oppure uno dei classici operatori quali unione, concatenazione, iterazione e parentesi.

Per la definizione dei Tokens si possono scegliere diversi approcci, solitamente si definisce un token usando un enum che specifica il tipo di token:

   1: enum Kind{SYM,UNION,CONCAT,...}

   2: struct Token {

   3: public readonly Kind kind;

   4: public readonly string nval;

   5: private Token(Kind k){ kind=k;nval=0; }

   6: private Token(string n){kind=Kind.NUM;nval=n;}

   7:  

   8: static public Token From Kind(Kind k){return new Token(k);}

   9: static public Token From StringRep(string d){return new Token(d);}

  10: }

Definita la classe Token poi il Tokenizer ricevendo un input una regex del tipo a(b|c)* andrà ad istanziare lo stream di Tokens con un codice del tipo

   1: public List<Token> Scan(string regexInput)

   2: {

   3:      CharEnumerator tokenEnumerator = regexInput.GetEnumerator();

   4:      List<Token> tokens = new List<Token>();

   5:  

   6:      while (tokenEnumerator.MoveNext())

   7:      {

   8:         switch (tokenEnumerator.Current)

   9:                     {

  10:                         case '*':

  11:                             tokens.Add(Token.FromKind(KIND.Iteration);

  12:                             break;

  13:                         case '|':

  14:                             tokens.Add(Token.FromKind(KIND.Alternation);

  15:                             break;

  16:                         etc...

  17:                     }         

  18:      }

  19: }

Il codice di creazione dei tokens diventa cosi:

   1: public List<Token> Scan(string input)

   2: {

   3:   CharEnumerator tokenEnumerator = input.GetEnumerator();

   4:   while (tokenEnumerator.MoveNext())

   5:     {

   6:        tokens.Add(TokenBuilder.GetTokenFromChar(tokenEnumerator.Current));

   7:     }                        

   8:   return tokens;

   9: }

La creazione dei tokens viene affidata alla classe TokenBuilder che utilizzando un dictionary che ha per chiave un carattere e per valore un delegate, istanzia la corretta tipologia di token tipizzato.

   1: public class TokenCreator

   2:     {

   3:         private Dictionary<char, Func<char, Token>> fromCharKind2Token { get; set; }

   4:  

   5:         public TokenCreator(HashSet<char> terminals)

   6:         {

   7:             fromCharKind2Token = new Dictionary<char, Func<char, Token>>();

   8:  

   9:             Func<char, Token> symbolCreationDelegate = (sym) => new SymbolToken(sym);

  10:  

  11:             foreach (char terminal in terminals)

  12:             {

  13:                 fromCharKind2Token.Add(terminal, symbolCreationDelegate);                                        

  14:             }

  15:  

  16:             fromCharKind2Token.Add('|', (sym) => new AlternationToken());

  17:  

  18:             fromCharKind2Token.Add('.', (sym) => new ConcatenationToken());

  19:  

  20:             fromCharKind2Token.Add('*', (sym) => new IterationToken() );

  21:  

  22:             fromCharKind2Token.Add('(', (sym) => new OpenParenthesisToken());

  23:  

  24:             fromCharKind2Token.Add(')', (sym) => new CloseParenthesisToken());

  25:         }

  26:         

  27:         public Token GetTokenFromChar(char symbol)

  28:         {

  29:             return fromCharKind2Token[symbol].Invoke(symbol);

  30:         }

  31:  

  32:     }

A questo punto lo stream di tokens devono essere analizzati dal Parser per effettuare l’analisi sintattica e costruire l’albero di Parsing, ovvero il famoso ParseTree del post precedente. L’analisi sintattica si basa sulla definizione di una grammatica che permette di dare significato ad un flusso di tokens.

Vediamo quindi come definire la struttura dei nodi che compongono l’albero di Parsing, tenendo presente che nel caso specifico dall’albero di parsing dovrò non tanto ad esempio calcolare il valore dell’espressione come nel caso dei parser aritmetici bensi dovrò convertire l’albero di parsing che rappresenta la mia regex in un automa a stati finiti non deterministico.

La gerarchia di classi del dominio dell’albero di Parsing prevede una classe base astratta TreeNode che oltre ad implementare le apposite interfacce ha come campi privati un Token (classe astratta) ed un campo Id. Gli altri nodi dell’albero sono classi derivate dalla classe base astratta e possono avere un numero variabili di nodi figli. Sfruttando questa gerarchia di classi a questo punto possiamo vedere uno stralcio di codice del parser a discesa ricorsiva…

   1: public class Parser

   2:     {

   3:         private Token[] Tokens { get; set; }

   4:         private int next = 0;                         

   5:                 

   6:         public TreeNode Parse(List<Token> ts)

   7:         {

   8:             Tokens = ts.ToArray();

   9:             return Expr();            

  10:         }

  11:  

  12:         private void Move()

  13:         {

  14:             next++;

  15:         }

  16:  

  17:         private Token NextToken()

  18:         {

  19:             return (next < Tokens.Length) ? Tokens[next] : new EndingToken();

  20:         }

  21:  

  22:         /// <summary>

  23:         /// expr   ::= concat '|' expr | concat

  24:         /// </summary>

  25:         /// <returns></returns>

  26:         private TreeNode Expr()

  27:         {

  28:             TreeNode left = Concat();

  29:  

  30:             if (NextToken() is AlternationToken)

  31:             {

  32:                 Move();

  33:  

  34:                 TreeNode right = Expr();

  35:  

  36:                 AlternationNode exprNode = new AlternationNode(new AlternationToken(),left,right);

  37:  

  38:                 return exprNode;

  39:             }

  40:             else

  41:                 return left;

  42:         }

  43:       ...

  44:       ...

  45:       ...

  46: }

Sfruttando l’ereditarietà il codice risulta fortemente tipizzato e privo dei classici confronti tra simbolo corrente e stringa che vengono fatti nella maggior parte dei parser hand made. Il codice del parser a discesa ricorsiva dipende strettamente dalla grammatica che sta alla base del parser, se la grammatica può subire estensioni frequenti, è necessario un approccio maggiormente flessibile che sfrutta design patterns quali visitor ed abstract factory come descritto in questo ottimo paper (lettura consigliata).

Si accettano feedback :)

Nunc est bibendum, nunc pede libero pulsanda tellus

Sulla scia dei post educativi di Luka e di Antonio ho riflettuto sul codice che sto producendo per il mio ultimo progetto che andrà a breve su codeplex, ovvero un parser di regex con successiva conversione ad automa deterministico minimizzato. L’implementazione “hand made” del parser  (lo scopo del progetto dovrebbe essere propedeutico per gli studenti che affrontano un primo corso sui compilatori o di informatica teorica) segue i consigli dell’ottimo testo Flexible Pattern Matching in Strings.

Questo è la prima implementazione che segue passo passo lo pseudo codice del libro (con l’aggiunta del campo enum sulla tipologia di nodo del parseTree):

   1: private NonDeterministicAutomaton RecursiveTree2Automaton(ParseTree current)

   2: {

   3:     NonDeterministicAutomaton left,right,star;

   4:     left = new NonDeterministicAutomaton();

   5:     right = new NonDeterministicAutomaton();

   6:     star = new NonDeterministicAutomaton();

   7:     if (current.NodeType == NodeType.ConcatenationOp || current.NodeType == NodeType.AlternationOp)

   8:     {

   9:         left = this.RecursiveTree2Automaton(current.Left);

  10:         right = this.RecursiveTree2Automaton(current.Right);

  11:     }

  12:     else if (current.NodeType == NodeType.KleenStarOp)

  13:     {

  14:         star = this.RecursiveTree2Automaton(current.Right);

  15:     }

  16:  

  17:     if (current.NodeType == NodeType.ConcatenationOp)

  18:     {

  19:         return Concatenation.Concatenate2NFA(left, right);

  20:     }

  21:  

  22:     if (current.NodeType == NodeType.AlternationOp)

  23:     {

  24:         return Alternation.Alternate2NFA(left, right);

  25:     }

  26:  

  27:     if (current.NodeType == NodeType.KleenStarOp)

  28:     {

  29:         return KleenStar.Iterate2NFA(star);

  30:     }

  31:     // At this point our current node is a simple char

  32:     //if (current.nodeType == NodeType.Character)

  33:     return new Symbol(current.Symbol.ToString()).Convert2NFA();            

  34: }

Il codice è piuttosto difficile da manutenere e testare a causa della quantità di branch presenti nel codice. Un primo miglioramento apportato è stato quello di inserire uno switch case e compattare la ricorsione con le operazioni di base:

   1: private NonDeterministicAutomaton RecursiveTree2Automaton(ParseTree current)

   2: {

   3:     NonDeterministicAutomaton left,right,star;

   4:     left = new NonDeterministicAutomaton();

   5:     right = new NonDeterministicAutomaton();

   6:     star = new NonDeterministicAutomaton();

   7:     switch (current.NodeType)

   8:     {

   9:         case NodeType.AlternationOp:

  10:             left = this.RecursiveTree2Automaton(current.Left);

  11:             right = this.RecursiveTree2Automaton(current.Right);

  12:             return Alternation.Alternate2NFA(left, right);

  13:  

  14:         case NodeType.ConcatenationOp:

  15:             left = this.RecursiveTree2Automaton(current.Left);

  16:             right = this.RecursiveTree2Automaton(current.Right);

  17:             return Concatenation.Concatenate2NFA(left, right);

  18:  

  19:         case NodeType.KleenStarOp:

  20:             star = this.RecursiveTree2Automaton(current.Right);

  21:             return KleenStar.Iterate2NFA(star);

  22:  

  23:         case NodeType.Character:

  24:             return new AlphabetSymbol(current.Symbol).Convert2NFA();                                                                  

  25:     }

  26:  

  27:     throw new Exception("Unknown conversion symbol");

  28: }

Il codice è maggiormente leggibile ma soffre del problema che se un domani oltre a supportare come operatori per le regex l’unione la concatenazione e la stella di Kleen (operatore asterisco) devo inserire altri case nel codice. Secondo voi è possibile migliorare ulteriormente il codice eliminando di fatto il costrutto switch case?

Di seguito per maggiore chiarezza il codice completo della classe che include il metodo RecursiveTreeToAutomaton

   1: /*  ----------------------------------------------------------------------------

   2:  *  Regex2Automaton

   3:  *  ----------------------------------------------------------------------------

   4:  *  Author:      Luca Del Tongo

   5:  *  Blog:          blogs.ugidotnet.org/wetblog

   6:  *  File:        NFABuilder.cs

   7:  *  Summary:     Class used to build an NFA from a Regex Pattern

   8:  *  Date:         31/03/2010

   9:  *  ----------------------------------------------------------------------------

  10:  *

  11:  */

  12:  

  13: namespace Regex2Automaton

  14: {

  15:     using System;

  16:     using System.Collections.Generic;

  17:     using System.Linq;

  18:     using System.Text;

  19:  

  20:     /// <summary>

  21:     /// Class used to build an NFA from a Regex Pattern

  22:     /// </summary>

  23:     public class NFABuilder

  24:     {

  25:         public RegexParser RegexParser { get; set; }

  26:                 

  27:         public NFABuilder()

  28:         {

  29:             this.RegexParser = new RegexParser();

  30:         }

  31:        

  32:         public NonDeterministicAutomaton BuildNFA(string pattern)

  33:         {

  34:             ParseTree parseTree = RegexParser.BuildParseTree(pattern);

  35:             return this.RecursiveTree2Automaton(parseTree);            

  36:         }

  37:  

  38:         public NonDeterministicAutomaton BuildNFA(ParseTree patternParseTree)

  39:         {            

  40:             return this.RecursiveTree2Automaton(patternParseTree);

  41:         }

  42:  

  43:         private NonDeterministicAutomaton RecursiveTree2Automaton(ParseTree current)

  44:         {

  45:             NonDeterministicAutomaton left,right,star;

  46:             left = new NonDeterministicAutomaton();

  47:             right = new NonDeterministicAutomaton();

  48:             star = new NonDeterministicAutomaton();

  49:             switch (current.NodeType)

  50:             {

  51:                 case NodeType.AlternationOp:

  52:                     left = this.RecursiveTree2Automaton(current.Left);

  53:                     right = this.RecursiveTree2Automaton(current.Right);

  54:                     return Alternation.Alternate2NFA(left, right);

  55:  

  56:                 case NodeType.ConcatenationOp:

  57:                     left = this.RecursiveTree2Automaton(current.Left);

  58:                     right = this.RecursiveTree2Automaton(current.Right);

  59:                     return Concatenation.Concatenate2NFA(left, right);

  60:  

  61:                 case NodeType.KleenStarOp:

  62:                     star = this.RecursiveTree2Automaton(current.Right);

  63:                     return KleenStar.Iterate2NFA(star);

  64:  

  65:                 case NodeType.Character:

  66:                     return new AlphabetSymbol(current.Symbol).Convert2NFA();                                                                  

  67:             }

  68:  

  69:             throw new Exception("Unknown conversion symbol");

  70:         }

  71:     }  

  72: }

Un paio di mesi fà mi sono imbattuto in ThinkCode.TV, una startup nordamericana fondata da tre italiani con l’obiettivo di creare e vendere screencasts di programmazione in italiano. La cosa che inizialmente mi ha fatto riflettere è che la tendenza a lasciare il “bel” paese per  motivi di lavoro “purtroppo” non si arresta, contribuendo di fatto ad un ulteriore impoverimento nazionale. 

A livello tecnico, la cosa che mi ha incuriosito è stata la varietà di tematiche offerte dagli screencasts; si passa infatti attraverso SmallTalk, Python, Jquery, Silverlight fino ad arrivare al TDD. Dopo essere entrato in contatto con gli autori per avere alcune informazioni sia sulla loro esperienza di vita e professionale oltreoceano sia sugli screencast legati al TDD, ho ricevuto un paio di screencast come review copies. Come reviewer ed ancor prima come utente quello che ho notato da subito è stata la trasparenza ed accessibilità dei prezzi e la fiducia che i ragazzi di ThinkCode ripongono nei propri clienti in quanto:

• L’intero percorso formativo sul TDD (11 lezioni), viene offerto ad un prezzo molto abbordabile di 47 € iva inclusa.
• E’ possibile acquistare le singole videolezioni ad un prezzo di circa 7€ (anzi 6.99€ LOL)
• Gli screencast, registrati in vari formati e scaricabili in alta definizione (HD 720p), sono liberi da DRM
• E’ possibile per ogni screencast visionare una preview di un paio di minuti

Quello che mi ha colpito durante la visione degli screencasts è l’approccio utilizzato: inizialmente vengono proposte alcune slides introduttive (necessarie per fissare sin da subito alcuni concetti) e successivamente vengono mostrati i relativi samples attraverso molteplici linguaggi di programmazione ed ambienti di sviluppo; quest’ultimo aspetto aiuta secondo me a mantenere una concentrazione maggiore proprio perchè non si ha la classica sensazione di “familiarità” (tipo la classica coppia C# & VS) che spesso porta ad una minore attenzione. A livello universitario ad esempio un corso del genere sul TDD dovrebbe IMVHO essere introdotto all’interno di un corso di ingegneria del software. L’unico appunto che mi sento di fare ai ragazzi è di essere più celeri nella preparazione dei percorsi formativi in quanto ad oggi ancora molti screencast sono in fase di preparazione.

In questi ultimi mesi mi sto interessando di Computer Vision. Sto cercando di sfruttare gli ultimi mesi ed esami universitari per cercare di capire quale siano le varie aree di ricerca che maggiormente mi interessano e le prospettive presenti sul panorama nazionale.  Dopo essermi concentrato sugli algoritmi e le strutture dati, aver studiato ed implementato alcuni algoritmi di data mining e business intelligence, l’ultimo elaborato che ho svolto per un progetto universitario riguarda proprio la computer vision, in particolar modo il riconoscimento di oggetti. Attualmente sono davvero poche le librerie ed i wrapper C# che implementano algoritmi di computer vision. La libreria che preferisco e che ho utilizzato per alcuni esperimenti piuttosto interessanti è Emgu CV.

Emgu CV è un wrapper .Net della famosa libreria Intel OpenCV. Tra i punti di forza di Emgu CV sicuramente il fatto che sia cross platform e che l’autore abbia un ciclo di sviluppo piuttosto agile; nuove release frequenti corredate da unit test. Gli esperimenti corredati da codice c# realizzati utilizzando Emgu, li potete trovate all’interno della sezione di Emgu CV (di cui sono moderatore) del più importante forum di computer vision, ovvero il forum di Flavio Bernardotti. All’interno del forum ho mostrato esempi di come calcolare il flusso ottico all’interno di un semplice video, di come realizzare riconoscimento facciale etc etc. Ho poi registrato alcuni tutorial in inglese in cui mostro ad esempio come eseguire eye detection oppure come controllare all’interno di una windows form la posizione del mouse semplicemente muovendo la testa.

Chiunque abbia esperienze e/o suggerimenti anche con altre librerie (Aforge.Net su tutte), si faccia vivo :)

Difficilmente posto news, stavolta però farò un eccezione in quanto su codeplex, alcuni sviluppatori di Avanade hanno realizzato un plugin per Sql Server hostato su codeplex che implementa una SVM. Al momento attuale può essere utilizzato per eseguire classificazione confrontando le prestazioni del modello con gli altri che si possono costruire usando gli algoritmi inclusi in SSAS(Decision Trees, Naive Bayes, Neural Network ); ho condotto alcuni esperimenti e devo dire che l'implementazione dell'algoritmo è buona anche se come ho suggerito nel forum è necessario inserire un modo per calcolare i parametri ottimali per l'addestramento della macchina; il mio suggerimento è stato quello di eseguire un ricerca dei parametri utilizzando una grid search verificando la bontà dei parametri utilizzando la cross validazione (quest'ultima inclusa in Sql Server 2008)... insomma un in bocca al lupo ai developer per la bella iniziativa... magari se trovo un pò di tempo sarebbe bello fare una comparazione delle prestazioni tra il plugin e libsvm ma ancora il plugin è giovane e di strada ne dovrà fare molta....

Ad maiora

Apro questo post ringraziando gli amici che hanno accompagnato la mia avventura da student partner, bella esperienza terminata lo scorso anno... non voglio dilungarmi sulle motivazioni di questa decisione, resta il fatto che il bello di essere studenti DOVREBBE essere quello di avere la libertà di scegliere senza avere vincoli o restrizioni del caso... detto questo lo scorso fine settimana è arrivato il premio per il "lavoro" che ho svolto da MSP... un bel Lego Mindstorm NXT!!!! Il kit è davvero bello e dopo aver preso contatto con i vari sensori e aver costruito il primo semplice robottino ho deciso di creare la prima applicazioncina VPL, la classica drive by wire.... ora nei tutorial presenti dentro la documentazione di MSRS è presente un diagramma VPL drive by wire ma dato che non ho condiviso alcune scelte che hanno fatto, ho deciso di crearne uno modificato (in meglio spero) che permetta di pilotare il robottino a proprio piacimento!!!! Allego lo screenshot del VPL per chi fosse interessato :)

Proprio prima di Natale, con il mio amico Granville abbiamo rilasciato un aggiornamento del libro gratuito che abbiamo scritto su algoritmi e strutture dati. Sono stati introdotti alcuni capitoli aggiuntivi e revisionati quelli già presenti nella prima release. I numeri lasciano spesso il tempo che trovano però aver ricevuto oltre 14.000 download per l'ultima release fà davvero piacere.

Data Structures and Algorithms: Annotated Reference with Examples

Molto spesso frequentando le community di webdesigner e sviluppo web in generale mi sono imbattuto in banner pubblicitari che effettuano il famoso servizio di conversione PSD-to-HTML. Finalmente anche nel panorama italiano, nasce un progetto piuttosto ambizioso, codename Braincode , creato da una web agency italiana X-brain. Il servizio offerto permette di trasformare formati grafici quali psd, jpeg, png in pagine xhtml e css, promettendo una conversione piuttosto rapida nell' arco di 2/3 giorni lavorativi, in base alla complessità del progetto. La prima cosa che ho fatto per verificare se davvero fossero artigiani del codice come da slogan è stata quella di spulciare attraverso il portfolio, il codice che hanno prodotto per i clienti e devo dire che in effetti il codice è davvero ben fatto.... ritengo quindi utile avere un servizio del genere per chi sviluppa web sia perchè velocizza lo sviluppo sia perchè avere un codice statico ben fatto fornisce secondo me quello che deve essere cmq l'output generato utilizzando cmq asp.net. E' proprio per questo che il mio migliore amico come al solito è il Repeater!!!

Per concludere, altrimenti sembra pubblicità occulta, è possibile avere integrazione con diversi cmq, per la verità adesso Joomla! e Wordpress ma sembra che il supporto venga esteso anche a cms a noi più congeniali, poi alla fin fine l'integrazione la possiamo fare anche da soli :)

Abbiamo appena rilasciato la versione 0.6 della nostra libreria Data Structure and Algorithms. Questa nuove release include come feature principali:

• AVL Tree (albero bilanciato)
• Deque (double ended queue)
• Radix Sort (algoritmo ordinamento)

Download Data Structures and Algorithms 0.6!