Face Detection e Face Recognition in Python – Test su Matrix Reloaded e Game of Thrones

Uno dei post che ha generato il maggior interesse in questo blog è certamente quello dedicato alla face detection tramite OpenCV. Riprendiamo questo tema dopo molto tempo parlando degli algoritmi alla frontiera per il Face Detection e Face Recognition. Lo scopo del post è fare il punto sullo stato dell’arte ed indirizzare verso mouduli open source liberamente e facilmente utilizzabili nelle applicazioni reali.

Matrix Reloaded – The Architect

La Face Detection è l’elaborazione che ha lo scopo di rilevare la presenza di volti umani all’interno di un’immagine digitale; nel precedente articolo è stata affrontata solo questa tematica attraverso algoritmi tradizionali ma consolidati.

Gli algoritmi di Face Detection si sono evoluti nel tempo migliorando l’accuratezza della rilevazione anche attraverso l’uso di reti neurali convoluzionarie (CNN) o reti Deep Learning opportunamente strutturate ed addestrate; tale processamento sfrutta massivamente l’eventuale presenza di moderne GPU o NPU per aumentarne l’efficienza ed il parallelismo. Nel nostro caso specifico ci siamo limitati al riconoscimento di volti umani in posizione frontale.

Matrix Reloaded Architect – Face Detection Benchmark MTCNN

Il benchmark estremo che ho utilizzato per mettere alla prova i moduli python individuati, è un breve video tratto dal dialogo tra Neo e l’Architetto in Matrix Reloaded; nel video, in un’atmosfera surreale, sono presenti innumerevoli volti che variano rapidamente per dimensione, inclinazione, espressione, presenza o meno di occhiali. Un video estremo di prova che farà friggere neuroni e sinapsi anche alle più evolute e performanti reti neurali convoluzionarie.

Questo è il video che è stato prodotto attraverso la nostra elaborazione:

Il Benchmark che ho utilizzato per la Face Detection in Python – L’architetto in Matrix Reloaded – questo è il risultato ottenuto tramite l’uso del modulo MTCNN insieme ad OpenCV che ho usato per l’elaborazione del video

Il modulo Python che, almeno nei miei esperimenti, ha dimostrato i migliori risultati in termini di qualità e prestazioni è MTCNN; in esecuzione su una sessione Colab con GPU attiva elabora efficientemente il flusso di frame con un livello di accuratezza molto alto se si escludono i volti in posizione non frontale. Nel video prodotto si trova l’esito dell’elaborazione dove, oltre ai volti, sono stati marcati anche alcuni punti caratteristici del viso (occhi, naso, estremi della bocca). Questo modulo è quello che riesce a rilevare meglio volti di dimensioni più piccole e non perfettamente allineati garantendo anche un’efficienza molto più alta degli altri moduli provati; MTCNN fornisce, per ogni volto rilevato, anche un livello di confidenza nella rilevazione (in tutto il video ho trovato solo un falso positivo pertanto non ho ritenuto necessario introdurre una soglia).

Il Trono di Spade – foto usata come base per l’apprendimento dei principali personaggi

In alternativa, si propone l’uso del modulo: face_recognition che ha comunque garantito un’ottima precisione su volti di dimensioni significative ed un’efficienza adeguata; su tale modulo è possibile variare l’algoritmo di rilevamento (CNN o HOG) ed effettuare del tuning per cercare di rilevare volti di dimensioni minori. Sul benchmark utilizzato la rilevazione CNN non riusciva ad intercettare gli stessi volti di MTCNN mentre la rilevazione HOG, oltre a non velocizzare molto il processamento, riduceva drasticamente il numero di volti rilevati. In condizioni normali anche questo modulo è da considerare un’ottima scelta e noi lo useremo per effettuare anche il Face Recognition. Questo modulo può richiedere un quantitativo di memoria sulla GPU più elevato soprattutto se si vogliono rilevare i volti con dimensioni più piccole.

Tutti i personaggi sono stati correttamente rilevati

Dopo aver rilevato ed isolato i volti, l’elaborazione della Face Recognition ci permette l’associazione di un volto ad una persona. In assenza di informazioni o di preappendimento sulle persone da ricercare, è possibile aggregare i volti su possibili individui basandosi sulla similitudine delle caratteristiche fisiologiche e biometriche. Gli algoritmi per effettuare tale riconoscimento, per codificare un volto in un insieme di parametri comparabili sono davvero molteplici e tutti estremamente interessanti. Anche in questo caso le reti neurali convoluzionarie (CNN) offrono un contributo importante a questi algoritmi.

Tutti i personaggi sono stati correttamente rilevati ad eccezione di Missandei che non era presente nella foto iniziale

Per implementare un Face Recognition in pochissime righe di codice Python ed in modo efficiente è possibile usare il modulo face_recognition; se si vuole approfondire come questo modulo funziona internamente vi consiglio di leggere questo aricolo.

Tutti gli attori presenti nel file di training sono stati correttamente rilevati anche senza abiti ed acconciature di scena. Come atteso Drogo non viene rilevato perché non presente nel file di training.

In questo caso ho creato un notepad colab di test che da una foto iniziale acquisisce le caratteristiche fisiologiche e biometriche dei vari personaggi della serie Il Trono di Spade; il modulo utilizzato, alla versione attuale, dovrebbe rappresentare ciascun volto tramite 128 parametri caratteristici.

tutti gli attori presenti nella foto di training sono stati rilevati anche Daenarys che appare molto differente rispetto al personaggio interpretato

Per testare il rilevamento ho provato a far riconoscere i personaggi su altre foto contenenti anche personaggi non presenti all’interno della foto di apprendimento; i risultati sono impeccabili. Il modulo utilizzato ha un’accuratezza eccellente sia per quanto riguarda i personaggi appresi che per quelli non analizzati che non ha mai classificato come falsi positivi.

anche in questo caso tutti gli attori presenti nella foto di training sono stati individuati correttamente

Per spingere oltre il test abbiamo avviato la detection su foto in cui gli attori non appaiono con i costumi di scena ed hanno acconciature o il colore dei capelli totalmente differente dai personaggi che hanno interpretato; anche in questo caso l’algoritmo non sbaglia e non rileva mai falsi positivi.

Anche se non ho effettuato delle prove dirette, sono convinto che l’algoritmo scali bene all’aumentare del numero delle persone da rilevare; non ho provato a sottoporre qualche foto degli attori quando erano più giovani.

NOTEBOOK COLAB – UTILIZZATO PER LA FACE DETECTION E FACE RECOGNITION

Concludiamo dicendo che oltre alla Face Detection ed alla Face Recognition ai volti possono essere applicati altri algoritmi per l’estrazione di caratteristiche molto importanti come la rilevazione del sesso, dell’età, del sentimento (es. rabbia, gioia, paura, sorpresa, …).

Fatemi sapere i vostri pareri e le vostre esperienze su Face Detection, Face Recognition nei commenti.

Share

Kaggle Competition – Titanic – Machine Learning from Disaster – Predict survival on the Titanic

L’RMS Titanic è stato un transatlantico britannico della classe Olympic naufragato nelle prime ore del tragico 15 aprile 1912, durante il suo viaggio inaugurale, a causa della collisione con un iceberg avvenuta nella notte.

La sfida proposta da Kaggle: Titanic – Machine Learning from Disaster alla quale ho aderito, richiede l’analisi di un dataset contenente informazioni relative ad un sottoinsieme di passeggeri imbarcati sul Titanic con lo scopo di realizzare un modello predittivo che sia in grado di classificare al meglio se un determinato passeggero si salverà dal naufragio.

tassi di sopravvivenza per classe

Alcune delle informazioni disponibili per l’analisi, di cui occorre individuare il livello di correlazione con la probabilità di salvezza, sono: sesso, età, cabina, classe, ponte, numero di parenti a bordo, porto di imbarco, tariffa pagata; moltissime altre informazioni possono essere derivate da elaborazioni più o meno complesse ed implicite tra i dati disponibili come ad esempio dai nomi completi è possibile risalire ai titoli, ad alcune professioni o anche spingersi al raggruppamento delle famiglie.

La grande sfida è quella di spingere al massimo l’accuratezza del modello predittivo al fine di classificare al meglio un insieme di passeggeri di test di cui non è nota la sorte; solo dopo la sottomissione a Kaggle si scoprirà il livello di accuratezza raggiunto.

Il modello predittivo di base che occorre superare e contro il quale ci si deve confrontare, che ho definito come modello baseline, assume semplicemente che tutte le donne si salveranno; applicando questa condizione elementare, si raggiunge un’accuratezza dell’insieme di passeggeri da classificare di poco superiore al 76%.

modello baseline: tutte le donne si salvano raggiunge un’accuratezza dello 0.76555

Questa competizione è un’ottima introduzione alla piattaforma Kaggle e richiede lo sviluppo di tutte le fasi di costruzione di un modello predittivo: analisi dei dati, preparazione e raffinamento dei dati, visualizzazione dei dati, costruzione del modello, validazione del modello e della sua accuratezza, comprensione della piattaforma Kaggle.

Nel mio notebook ho deciso di affrontare la sfida in Python costruendo un modello tramite la libreria XGBoost nota sia per essere alla base delle migliori implementazioni all’avanguardia del settore ma anche perché alla base dei modelli vincenti delle competizioni Kaggle. Tale libreria implementa il framework Gradient Boost in modalità estremamente scalabile, efficiente e portabile.

La mia implementazione, già completamente funzionante, è ancora in evoluzione è raggiungibile a questo indirizzo:

Kaggle Competition – Titanic – Machine Learning from Disaster – Predict survival on the Titanic – Luca Amore

Share

Infection Spread Simulator Construction Kit

Al fine di comprendere meglio l’articolo: Modeling How Infectious Diseases like Coronavirus Spread ed i riferimenti citati, continuando ad approfondire, mi sono ritrovato a costruire il framework: “Infection Spread Simulator Construction Kit”.

Si tratta di un notebook Python su Colab per la modellazione della diffusione di un’infezione attraverso un modello SEIR descritto da un sistema di equazioni differenziali (o un algoritmo); lo stesso modello proposto per l’analisi della diffusione del covid-19 nell’articolo che ha ispirato questo lavoro.

Chiunque, anche senza nessuna base matematica, con una conoscenza basilare di programmazione, può modificare il notebook all’interno della propria sandbox Colab, descrivere un virus o il comportamento di un’infezione ed analizzare la sua diffusione nel tempo per comprendere come la variazione di certi parametri può incidere nella diffusione.

Si tratta di un prototipo, nato per uso strettamente personale, con molti limiti ma voglio comunque condividerlo con la comunità rilasciandolo come software libero sotto la licenza GNU/GPL v.3.

Sarei felice di ricevere i vostri feedback, i vostri modelli, le vostre evoluzioni anche direttamente su github. Nei prossimi giorni, utilizzando questo framework o una sua evoluzione, vorrei provare a realizzare il complesso modello di diffusione del covid-19 descritto nell’articolo.

Segue il link diretto al notebook su github:

NOTEBOOK INFECTION SPREAD SIMULATOR CONSTRUCTION KIT (GITHUB)

MALARIA
Il primo modello reale (non SEIR) che rilascio è quello della malaria. In questo caso ho dovuto apportare delle modifiche più complesse al modello base.

MALARIA NOTEBOOK (GITHUB)

Share

ffdup – Ultra Fast (and Light) Portable Duplicate File Finder

Alcuni anni fa, avendo la necessità di individuare rapidamente i file duplicati all’interno di file-system Unix residenti su dispositivi embedded o su NAS (es. Synology, QNAP, D-Link), non soddisfatto dei tool che ho trovato in rete, ho realizzato un tool Perl a riga di comando con i seguenti obiettivi:

luca_amore_bubble_bubble_sm

  • molto leggero ed utilizzabile anche su dispositivi embedded (richiesto solo l’interprete Perl 5.7.3 o superiore senza altre dipendenze);
  • massima efficienza su dischi molto lenti o unità di rete.

E’ nata così la prima versione del software libero ffdup che rilascio sotto licenza GNU/GPL v3.0 su:

ffdup – progetto su Github

Nel progetto è incluso lo script bash per la generazione parametrica di una struttura di directory e file per gli unit test automatici.

In una futura versione vorrei introdurre la rilevazione delle directory duplicate.

 

Share

AI: Pac-Man and Ms Pac-Man

E’ da molto che non scrivo in questo blog; semplicemente sono stato impegnato in alcuni progetti che non reputo ancora pubblicabili.

Voglio segnalarvi due interessanti riferimenti nel campo dell’AI, computational intelligence, machine learning; argomenti di cui mi sto occupando in questo periodo.

The Pac-Man Projects

Come base degli esercizi per un corso di intelligenza artificiale, presso l’università di Berkeley, viene proposto agli studenti di sviluppare in python alcuni algoritmi all’interno del famoso gioco del Pac-Man; il corso termina con un multi-player contest.

The Pac-Man Projects

Trovo questa idea geniale e molto efficace dal punto di vista didattico.

Il materiale può essere liberamente utilizzato come base per corsi di intelligenza artificiale ma si richiede di non pubblicare online le soluzioni dei problemi posti.

Pac-Man

Ms Pac-Man vs Ghost Team Competition

Per chi volesse cimentarsi nello sviluppo in java di algoritmi che pilotano Ms Pac-Man o la squadra dei quattro fantasmi è stata organizzata un’avvincente competizione:

Ms Pac-Man vs Ghost Team Competition

Un risultato interessante (che mi sorprende) è che i punteggi ottenuti dai migliori giocatori artificiali sono molto più bassi di quelli umani.

Tra i vari algoritmi utilizzati: Ant Colony Optimization, Genetic Programming, Neural Networks, Influence Maps, Minimax, Rule Based.


Share

Computer vision: OpenCV realtime face detection in Python

Per festeggiare degnamente l’arrivo del mio nuovo portatile in famiglia ho pensato di renderlo in grado di riconoscere volti umani da una sorgente video in tempo reale.

Video dell’applicazione realizzata

Segue il video dimostrativo dell’applicazione realizzata:

OpenCV (Open Source Computer Vision Library)

Era da tempo che desideravo utilizzare la libreria Open CV per tornare a fare qualche esperimento di Computer Vision e per esplorare le sue tanto decantate potenzialità.

OpenCV è una libreria rilasciata sotto licenza BSD dalla Intel per l’elaborazione realtime delle immagini e la Computer Vision.

Scritta in C e C++ è utilizzabile, tramite wrapper (sia ufficiali che non) in diversi linguaggi: Python, Ruby, Java, C# ed è stata portata sui principali sistemi operativi: GNU/Linux, FreeBSD, Mac OS X, Windows ma anche Android e iOS per lo sviluppo di applicazioni su dispositivi mobili.

Alcuni wrapper esportano solo un limitato sottoinsieme di funzionalità.

face-detection demo 009

Mi sono reso conto che le potenzialità di tale libreria sono superiori alle mie più rosee aspettative: c’è tutto quello che può servire (e si può sognare) per realizzare applicazioni avanzate di Computer Vision ed elaborazione delle immagini.

Video di alcune interessanti applicazioni che è possibile realizzare

Sviluppare un’applicazione di ottima qualità per la face detection in realtime, problema normalmente complesso, diventa banale a tal punto che mi sono limitato a fare qualche ricerca su internet ed assemblare poche righe di codice Python trovate in alcuni blog.

Face Detection ed Haar-like features

L’algoritmo molto efficiente che viene utilizzato per la rilevazione dei volti, basato sulle Haar wavelet, è stato elaborato da Viola-Jones nell’ambito dell’object detection ed è stato pensato proprio per il problema della face detection in tempo reale.

Con OpenCV è possibile addestrare nuovi identificatori di oggetti tuttavia sono già presenti i seguenti classificatori (in formato xml):

haarcascade_eye_tree_eyeglasses.xml
haarcascade_eye.xml
haarcascade_frontalface_alt2.xml
haarcascade_frontalface_alt_tree.xml
haarcascade_frontalface_alt.xml
haarcascade_frontalface_default.xml
haarcascade_fullbody.xml
haarcascade_lefteye_2splits.xml
haarcascade_lowerbody.xml
haarcascade_mcs_eyepair_big.xml
haarcascade_mcs_eyepair_small.xml
haarcascade_mcs_lefteye.xml
haarcascade_mcs_mouth.xml
haarcascade_mcs_nose.xml
haarcascade_mcs_righteye.xml
haarcascade_mcs_upperbody.xml
haarcascade_profileface.xml
haarcascade_righteye_2splits.xml
haarcascade_upperbody.xml

Nelle mie prove, dopo aver individuato il volto, ho provato a rilevare anche gli occhi e la bocca ma in questo caso i risultati non mi hanno soddisfatto.

Sorgente Python

I miei esperimenti sono stati effettuati su una macchina GNU/Linux Ubuntu 11.04 con OpenCV 2.1.

E’ richiesto il pacchetto python-opencv, presente nei repository ufficiali e si assume che nel path dello script sia presente una directory haarcascades contenente i vari xml necessari per la detection.

Su Ubuntu 11.04 è possibile trovarli nella directory:

/usr/share/doc/opencv-doc/examples/haarcascades/haarcascades/

segue il codice sorgente utilizzato per la realizzazione del video:

#!/usr/bin/python

#----------------------------------------------------------------------------
# Face Detection Test (OpenCV)
#
# thanks to:
# http://japskua.wordpress.com/2010/08/04/detecting-eyes-with-python-opencv
#----------------------------------------------------------------------------

import cv
import time
import Image

def DetectFace(image, faceCascade):

    min_size = (20,20)
    image_scale = 2
    haar_scale = 1.1
    min_neighbors = 3
    haar_flags = 0

    # Allocate the temporary images
    grayscale = cv.CreateImage((image.width, image.height), 8, 1)
    smallImage = cv.CreateImage(
            (
                cv.Round(image.width / image_scale),
                cv.Round(image.height / image_scale)
            ), 8 ,1)

    # Convert color input image to grayscale
    cv.CvtColor(image, grayscale, cv.CV_BGR2GRAY)

    # Scale input image for faster processing
    cv.Resize(grayscale, smallImage, cv.CV_INTER_LINEAR)

    # Equalize the histogram
    cv.EqualizeHist(smallImage, smallImage)

    # Detect the faces
    faces = cv.HaarDetectObjects(
            smallImage, faceCascade, cv.CreateMemStorage(0),
            haar_scale, min_neighbors, haar_flags, min_size
        )

    # If faces are found
    if faces:
        for ((x, y, w, h), n) in faces:
            # the input to cv.HaarDetectObjects was resized, so scale the
            # bounding box of each face and convert it to two CvPoints
            pt1 = (int(x * image_scale), int(y * image_scale))
            pt2 = (int((x + w) * image_scale), int((y + h) * image_scale))
            cv.Rectangle(image, pt1, pt2, cv.RGB(255, 0, 0), 5, 8, 0)

    return image

#----------
# M A I N
#----------

capture = cv.CaptureFromCAM(0)
#capture = cv.CaptureFromFile("test.avi")

#faceCascade = cv.Load("haarcascades/haarcascade_frontalface_default.xml")
#faceCascade = cv.Load("haarcascades/haarcascade_frontalface_alt2.xml")
faceCascade = cv.Load("haarcascades/haarcascade_frontalface_alt.xml")
#faceCascade = cv.Load("haarcascades/haarcascade_frontalface_alt_tree.xml")

while (cv.WaitKey(15)==-1):
    img = cv.QueryFrame(capture)
    image = DetectFace(img, faceCascade)
    cv.ShowImage("face detection test", image)

cv.ReleaseCapture(capture)

Share

Cammelli labirinti e depth-first search: realizzazione di un generatore e risolutore di labirinti in Perl

labirinto 20 x 20 generato da maze.pl

Se Téseo (Θησεύς), eroe spregiudicato nonchè figlio del re ateniese Ègeo (Αἰγεύς), avesse conosciuto qualche rudimento di Perl, avrebbe potuto risolvere brillantemente il problema del Labirinto di Cnosso adottando l’algoritmo deep-first search, sconfiggere il Minotauro (Μινώταυρος) Asterione ma – soprattutto – non avrebbe spezzato il cuore della povera Arianna (Αριάδνη), figlia di Minosse e Pasifae (ed anche madre del Minotauro), seducendola per ottenere il risolutivo gomitolo di filo rosso (un surrogato di stack analogico ideato da Dedalo ) per poi abbandonarla ancora dormiente nell’isola deserta di Nasso (pare pure dopo una lunga notte di “festeggiamenti” nella sua nave).

A chi mi obietta – ingiustamente – che ai tempi non era disponibile un interprete Perl così come un notebook agevolmente trasportabile in un Labirinto, ma anche a tutti gli altri che gridano vendetta contro il comportamento di Téseo nei confronti della povera Arianna, consiglio vivamente la lettura dell’avvincente leggenda del Minotauro; scoprirete che la storia di Téseo, per opera di Poseidone, si conclude in modo tragico a causa dell’inversione di un’informazione booleana (1 bit) ma vitale: il colore delle vele della sua imbarcazione.

Dopo questa mitologica premessa, certo di esser perdonato per eventuali errori sulla mitologia greca, sperando di non deludere il forse unico temerario lettore che avrà avuto l’ardore di proseguire nella lettura di questo articolo, vi presento un semplicissimo generatore e risolutore di labirinti scritto interamente in Perl.

Labirinto 60 x 40 generato da maze.pl

Questo progetto è ispirato da un articolo che ho letto nel blog di Eriol in cui il problema viene affrontato in Python.

In rete esistono anche molti riferimenti sui labirinti (storia, classificazione, generazione, risoluzione, miti e leggende) dove è piacevole perdersi:

Nella mia implementazione, esaltando alcune caratteristiche tipiche del Perl, ho progettato delle strutture dati leggere ed efficienti (memorizzo solo le aperture del labirinto) ed ho adottato la versione dell’algoritmo depth-first search ricorsiva sia per la costruzione del labirinto (metodo Maze::asterione) che per la ricerca del percorso che conduce dall’ingresso all’uscita (metodo Maze::teseo).

Sono disponibili:

l’output del labirinto generato e risolto in modalità ASCII (Maze::toText):


lookee@grog:~/devel/maze$ ./maze.pl

+..+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|..|.. ..|              |  |           |           |        |
+..+..+..+  +--+--+--+  +  +  +  +--+  +  +  +--+  +  +--+  +
|.. ..|..|  |              |  |  |     |  |     |     |     |
+--+--+..+  +--+--+--+--+  +  +  +  +--+--+--+  +--+--+  +--+
|.. .. ..|              |  |  |  |              |     |  |  |
+..+--+--+--+  +--+--+  +--+  +  +--+--+  +--+--+--+  +  +  +
|..|.. .. ..|  |     |        |     |     |        |     |  |
+..+..+--+..+  +  +  +--+--+--+--+  +--+--+  +--+  +  +--+  +
|.. ..|  |..|     |  |           |  |        |     |        |
+--+--+  +..+--+--+  +--+  +--+  +  +  +--+--+  +--+--+--+--+
|        |.. ..|  |     |     |  |     |.. ..|     |        |
+  +--+--+--+..+  +--+  +--+  +--+--+  +..+..+--+  +  +--+  +
|           |..|              |.. ..|  |..|.. ..|        |  |
+--+--+--+  +..+  +--+--+--+--+..+..+--+..+--+..+--+--+--+  +
|           |..|  |     |.. ..|..|.. .. ..|  |.. .. ..|     |
+  +--+--+  +..+  +  +--+..+..+..+--+--+--+  +--+--+..+..+  +
|  |     |  |..|     |.. ..|..|.. ..|     |        |.. ..|  |
+  +  +  +--+..+--+--+..+--+..+--+..+  +  +  +  +--+--+..+--+
|     |      .. .. .. ..|   .. .. ..|  |     |         .. ..|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+..+

l’output in formato PNG(Maze::toImage):

labirinto 200 x 100 generato da maze.pl

Per la generazione dell’immagine si richiedono le librerie GD.

Il tutto sarebbe ottimizzabile e migliorabile ma al momento sono già abbastanza soddisfatto dei risultati ottenuti!

Potete scaricare i sorgenti di maze.pl nel repository del progetto su github (software libero rilasciato sotto licenza GNU/GPL v. 3)


#!/usr/bin/perl

#------------------------------------------------------------------------
# M A Z E
#------------------------------------------------------------------------

use strict;
use warnings;

package Maze;

use Carp qw(croak verbose);
use GD;

sub new {
my ($class, $x, $y) = @_;

my $self = {
x => $x,
y => $y,
doors => [],
solution => [],
};

bless $self;
$self->openWall(0, 0, 'N');
$self->openWall($x - 1, $y - 1, 'S');

return $self;
}

sub _getWallIndex($$$){
my ($self, $x, $y, $dir) = @_;

my @idx =
$dir eq 'N' ? ($x,      $y,     'N') :
$dir eq 'S' ? ($x,      $y + 1, 'N') :
$dir eq 'W' ? ($x,      $y,     'E') :
$dir eq 'E' ? ($x + 1,  $y,     'E') :
croak "wrong direction";

return @idx;
}

sub isWallOpen($$$){
my ($self, $x, $y, $dir) = @_;

my ($wx, $wy, $wdir) = $self->_getWallIndex($x, $y, $dir);

return $self->{door}[$wx][$wy]{$wdir} || 0;
}

sub openWall($$$) {
my ($self, $x, $y, $dir) = @_;

my ($wx, $wy, $wdir) = $self->_getWallIndex($x, $y, $dir);

$self->{door}[$wx][$wy]{$wdir} = 1;
}

sub getCellNeighbors($$$){
my ($self, $x, $y) = @_;
grep {
$_->[0] >= 0 and $_->[0] < $self->{x} and
$_->[1] >= 0 and $_->[1] < $self->{y}
} (
[$x - 1, $y    , 'W'],
[$x + 1, $y    , 'E'],
[$x    , $y - 1, 'N'],
[$x    , $y + 1, 'S']
);
}

sub getCellOpenedNeighbors($$$){
my ($self, $x, $y) = @_;
grep {
my (undef, undef, $dir) = @$_;
$self->isWallOpen($x, $y, $dir)
} $self->getCellNeighbors($x, $y);
}

sub isCellExit($$$){
my ($self, $x, $y) = @_;
return
($x == $self->{x} -1 ) && ($y == $self->{y} -1 );
}

sub markSolution($$$){
my ($self, $x, $y) = @_;
$self->{solution}[$x][$y] = 1;
}

sub isSolution($$$){
my ($self, $x, $y) = @_;
$self->{solution}[$x][$y];
}

# generate maze
sub asterione($$$$){
no warnings 'recursion';
my ($self, $x, $y, $visited) = @_;
$visited->[$x][$y] = 1;
return if $self->isCellExit($x,$y);
my @neighbors = $self->getCellNeighbors($x, $y);
while (scalar @neighbors){
my ($tox, $toy, $dir) =
@{ splice(@neighbors, rand(@neighbors), 1) };
next if $visited->[$tox][$toy];
$self->openWall($x, $y, $dir);
$self->asterione($tox, $toy, $visited);
}
}

# solve maze
sub teseo($$$$){
no warnings 'recursion';
my ($self, $x, $y, $visited) = @_;
$visited->[$x][$y] = 1;
if ($self->isCellExit($x, $y)){
$self->markSolution($x, $y);
return 1;
}
my @neighbors = $self->getCellOpenedNeighbors($x, $y);
while (scalar @neighbors){
my ($tox, $toy, $dir) =
@{ splice(@neighbors, rand(@neighbors), 1) };
next if $visited->[$tox][$toy];
my $isSolution = $self->teseo($tox, $toy, $visited);
if ($isSolution){
$self->markSolution($x, $y);
return 1;
}
}
return 0;
}

sub toText(){

my $self = shift;

my ($x, $y, @l1, @l2);
my $out = '';
for ($y = 0; $y < $self->{y}; $y++){
@l1 = @l2 = ();
for ($x = 0; $x < $self->{x}; $x++){
my $solution = $self->isSolution($x, $y) ? '.' : ' ';
push(@l1, $self->isWallOpen($x, $y, 'N') ? $solution x 2 : '-' x 2);
push(@l2, $self->isWallOpen($x, $y, 'W') ? ' ' : '|');
push(@l2, $solution x 2);
}
push(@l2, $self->isWallOpen($x, $y, 'E') ? ' ' : '|');
$out .=
'+' . join('+',@l1) . '+' . "\n" .
join('',@l2) . "\n";
}

@l1 = ();
for ($x = 0; $x < $self->{x}; $x++){
my $solution = $self->{solution}[$x][$self->{y} -1] ? '.' : ' ';
push(@l1,
$self->isWallOpen($x, $self->{y} -1, 'S') ?
$solution x 2 : '-' x 2
);
}

$out .= '+' . join('+', @l1) . '+' . "\n";

print $out;
}

sub toImage($$){

my ($self, $FILENAME) = @_;

my ($WX, $WY) = (10, 10);

my ($SIZEX, $SIZEY) = ($self->{x} * $WX, $self->{y} * $WY);

my $img = new GD::Image->newTrueColor($SIZEX,$SIZEY)
or croak "Can't create GD::Image";

my $cl_white = $img->colorAllocate(255,255,255);
my $cl_black = $img->colorAllocate(  0,  0,  0);
my $cl_red   = $img->colorAllocate(255,  0,  0);

$img->fill( 0, 0, $cl_white);

open(my $fh, '>', $FILENAME)
or croak "Can't open $FILENAME: $!";

binmode $fh;

my ($xx, $yy);

YY: for ($yy = 0; $yy < $self->{y}; $yy++){

XX: for ($xx = 0; $xx < $self->{x}; $xx++){

$img->filledRectangle(
$xx * $WX, $yy * $WY, ($xx + 1) * $WX, ($yy + 1) * $WY,
$cl_red
)
if $self->isSolution($xx, $yy);

$img->line(
$xx * $WX, $yy * $WY, ($xx + 1) * $WX, $yy * $WY,
$cl_black
)
unless $self->isWallOpen($xx, $yy, 'N');

$img->line(
$xx * $WX, $yy * $WY, $xx * $WX, ($yy + 1) * $WY,
$cl_black
)
unless $self->isWallOpen($xx, $yy, 'W');
}

$img->line(
$xx * $WX - 1, $yy * $WY, $xx * $WX -1, ($yy + 1) * $WY,
$cl_black
)
unless $self->isWallOpen($xx - 1, $yy, 'E');
}

for ($xx = 0; $xx < $self->{x}; $xx++){
$img->line(
$xx * $WX, $yy * $WY - 1, ($xx + 1) * $WX, $yy * $WY - 1,
$cl_black
)
unless $self->isWallOpen($xx, $yy - 1, 'S');
}

print $fh $img->png(0);
close $fh;
}

package main;

# init
my $m = Maze->new(60,40);

# generate paths
$m->asterione(0,0,[]);

# solve maze
$m->teseo(0,0,[]);

# generate PNG
$m->toImage('out.png');

# print ASCII
#$m->toText();

Share

Erlang e frattali: fuga verso l’infinito…

Nello scorso articolo, tramite poche righe di codice perl, abbiamo curiosato all’interno del frastagliato universo frattale, rappresentando gli insiemi di Mandelbrot e Julia in modalità rigorosamente monocromatica.

Mandelbrot, I: 40 Z: -2.5, 1.0 x -1.0, 1.0

E’ davvero meraviglioso quando la natura ci sorprende facendo coesistere l’infinitamente semplice con lo smisuratamente complesso come in questo caso. Solo Lei può permettersi di farlo in modo così raffinato ed esuberante: una banale successione quadratica nel dominio dei numeri complessi, apparentemente insignificante ed innocua, è in grado di generare ricorsivamente “uno dei più complessi oggetti della matematica”; così è stato definito l’insieme di Mandelbrot da Benoît MandelbrotHeinz-Otto Peitgen e John H. Hubbard suoi iniziali divulgatori.

Il comportamento dei sistemi caotici ha ancora misteriose proprietà che l’uomo non è stato ancora in grado di decifrare; mattoncini matematici che la natura ha combinato per la costruzione dell’universo e di cui – forse – potremmo parlare nei prossimi articoli.

Erlang e frattali

In questo articolo, ho deciso di realizzare un’applicazione distribuita per la rappresentazione in Erlang degli insiemi frattali di Mandelbrot e Julia in Erlang introducendo anche i colori.

Mandelbrot, I: 500 Z: -0.981,-0.6457 x 0.0169, 0.3527

Un bel frullato di: caos, frattali, colori, concorrenza, programmazione funzionale, emozioni, infinito. Una frizzante e fatale alchimia di argomenti dalla quale non è possibile esser risucchiati!

Erlang

L’Erlang è un linguaggio funzionale progettato da Joe Armstrong, per conto di Ericsson, con lo scopo di favorire lo sviluppo di applicazioni: distribuite, soft-realtime, con un elevato grado di concorrenza ed affidabilità nel campo delle telecomunicazioni. La prima versione proprietaria del linguaggio è stata rilasciata internamente nel 1986 mentre, dopo varie vicessitudini, nel 1998 Erlang è stato distribuito opensource.

Concorrenza e gestione dei processi

The world is concurrent
Things in the world don’t share data
Things communicate with messages
Things fail – Joe Armstrong

Erlang è progettato per la concorrenza massiva. Per spingere tale caratteristica a livelli estremi, si è ben pensato di progettare un gestore di processi ed uno scheduler interni alla virtual-machine. Tali componenti non delegano i loro compiti al kernel del sistema operativo (come fa la quasi totalità degli altri linguaggi) e sono in grado di gestire processi con un’efficientissima gestione della memoria e dello scheduling.

Julia, I: 150 K: -0.835+0.2321i Z: -1.8,1.8 x -1.0, 1.0

Scrivere applicazioni distribuite, scalabili e robuste in Erlang è normalmente più semplice che in altri linguaggi. I processi possono esser distribuiti trasparentemente su più core oppure su più macchine e comunicano tramite message-passing asincrono.

Apprendere l’Erlang

Se siete semplicemente curiosi di conoscere la sintassi del linguaggio, potreste provare questo breve tutorial online che simula via web la shell di Erlang: Tryerlang.

Per un corso online è possibile visitare: Learn You Some Erlang oppure Erlang for Skeptics

I libri che non possono mancare nella biblioteca di chi ama tale linguaggio (sui quali ho studiato l’Erlang):

Applicazione Erlang: frk

Segue il codice sorgente in Erlang, del modulo principale, che ho scritto per la mia applicazione: frk.

-module(frk).
-author('LucaAmore').
-export([save/11, save/9, julia/9, mandelbrot/7]).

%------------------------------------------------------------------------
%    Copyright (C) 2011 Luca Amore <luca.amore at gmail.com>
%------------------------------------------------------------------------

% extract all screen coords
screen(W, H)->
    [ {X,Y} || Y <- lists:seq(0, H - 1), X <- lists:seq(0, W - 1) ].

% convert bitmap point to complex point
complex(X, Y, MinX, MinY, FactX, FactY)->
    { MinX + X * FactX, MinY + Y * FactY }.

iterate(_, _, _, _, MaxIterations, Iterations) 
    when Iterations >= MaxIterations -> Iterations;

iterate(Zre, Zim, _, _,  _, Iterations) 
    when Zre * Zre + Zim * Zim  > 4 -> Iterations;

iterate(Zre, Zim, Cre, Cim, MaxIterations, Iterations)->
    iterate(
        Zre * Zre - Zim * Zim + Cre, 
        2 * Zre * Zim + Cim, 
        Cre, Cim,
        MaxIterations, Iterations+1
    ).

%------------------------------------------------------------------------
% Julia's set
%
% Z1 = C0, Zn+1 = Zn^2 + K
%------------------------------------------------------------------------
julia(X, Y, MinX, MinY, FactX, FactY, Kre, Kim, MaxIterations)->
    {Cre, Cim} = complex(X, Y, MinX, MinY, FactX, FactY),
    iterate(Cre, Cim, Kre, Kim, MaxIterations, 0).

%------------------------------------------------------------------------
% Mandelbrot's set
%
% Z1 = 0, Zn+1 = Zn^2 + C0
%------------------------------------------------------------------------
mandelbrot(X, Y, MinX, MinY, FactX, FactY, MaxIterations)->
    {Cre, Cim} = complex(X, Y, MinX, MinY, FactX, FactY),
    iterate(0, 0, Cre, Cim, MaxIterations, 0).

% Julia's set exploration
generate(julia, W, H, MinX, MaxX, MinY, MaxY, Kre, Kim, MaxIterations) 
    when W > 0, H > 0, MaxX > MinX, MaxY > MinY, MaxIterations > 0 ->
    FactX = (MaxX - MinX) / W,
    FactY = (MaxY - MinY) / H,
    [ julia(X, Y, MinX, MinY, FactX, FactY, Kre, Kim, MaxIterations) || 
        {X, Y} <- screen(W, H) ].

% Mandelbrot's set exploration
generate(mandelbrot, W, H, MinX, MaxX, MinY, MaxY, MaxIterations) 
    when W > 0, H > 0, MaxX > MinX, MaxY > MinY, MaxIterations > 0 ->
    FactX = (MaxX - MinX) / W,
    FactY = (MaxY - MinY) / H,
    [ mandelbrot(X, Y, MinX, MinY, FactX, FactY, MaxIterations) || 
        {X, Y} <- screen(W, H) ].

% save Julia's set in ppm format
save(julia, W, H, MinX, MaxX, MinY, MaxY, Kre, Kim, MaxIterations, FileName) 
    when W > 0, H > 0, MaxX > MinX, MaxY > MinY, MaxIterations > 0 ->
    M = [
            paletteblu:color(Iterations, MaxIterations) || 
                Iterations <- generate(
                    julia, W, H, MinX, MaxX, MinY, MaxY, Kre, Kim, MaxIterations
                )
    ],
    ppm:save(image, W, H, 255, FileName, M).

% save Mandelbrot's set in ppm format
save(mandelbrot, W, H, MinX, MaxX, MinY, MaxY, MaxIterations, FileName) 
    when W > 0, H > 0, MaxX > MinX, MaxY > MinY, MaxIterations > 0 ->
    M = [
            palettered:color(Iterations, MaxIterations) || 
                Iterations <- generate(
                    mandelbrot, W, H, MinX, MaxX, MinY, MaxY, MaxIterations
                )
    ],
    ppm:save(image, W, H, 255, FileName, M).

Mandelbrot, I: 40 Z: -1.825,-1.705 x -0.06, 0.06

Per non appesantire troppo il codice ho deciso di utilizzare come formato delle immagini di output PPM (tra i più semplici disponibili) e poi convertirlo in PNG, tramite script bash, utilizzando l’utility convert di ImageMagick.

Tutte le immagini dei frattali di questo articolo sono stati generati da frk.

L’applicazione frk. rilasciata come software libero sotto licenza GNU/GPL, è disponibile presso:

Repository GIT su GITHUB di FRK

Share

Rappresentazione dell’insieme frattale di Mandelbrot in Perl

Mandelbrot

La rappresentazione dell’insieme di Mandelbrot, considerato uno dei frattali più popolari, è tra i miei algoritmi di prova preferiti quando studio un nuovo linguaggio di programmazione.

L’algoritmo di base è estremamente semplice e si presta facilmente ad esser parallelizzato.

Recentemente, all’interno dei Google Labs, è stata rilasciata un’applicazione Web che, sfruttando le API di Google Maps e canvas di HTML5, permette la navigazione all’interno dell’insieme di Mandelbrot o di altri frattali (es. Julia); vi consiglio di utilizzarla per un tour veloce.

Definizione formale

L’insieme di Mandelbrot è definito come il sottoinsime del piano complesso per cui la successione ricorsiva:

  P^c_n=  \begin{cases}  & Z_0=0  \\  & Z_{n+1}=Z_n^2+c  \end{cases}

 

al tendere di n all’infinito, rimane limitata nel suo modulo, ovvero:

  M=\left\{c\in \mathbb{C} : \exists s \in \mathbb{R}, \forall n \in \mathbb{N},|P_n^c| \leq s \right\}

 

Sorgente perl

Ecco un sorgente perl che rappresenta l’insieme in modalità rigorosamente monocromatica:

#!/usr/bin/perl

##########################
# M A N D E L B R O T
# Luca Amore
##########################

use strict;
use warnings;

use GD;

my $FILENAME = 'mandelbrot.png';
my $ITERATIONS = 30;
my ($SIZEX, $SIZEY) = (700, 400);
my ($RE_MIN, $RE_MAX) = (-2.5, 1.0);
my ($IM_MIN, $IM_MAX) = (-1.0, 1.0);

my $re_factor = ($RE_MAX - $RE_MIN) / $SIZEX;
my $im_factor = ($IM_MAX - $IM_MIN) / $SIZEY;

my $img = new GD::Image->newTrueColor($SIZEX,$SIZEY)
    or die "Can't create GD::Image";

# palette
my $cl_black = $img->colorAllocate(  0,  0,  0);
my $cl_white = $img->colorAllocate(255,255,255);

open(my $fh, '>', $FILENAME) 
    or die "Can't open $FILENAME: $!";

binmode $fh;

my $C_im = $IM_MIN;

YY: for (my $yy=0; $yy < $SIZEY; $yy++){
   
    my $C_re = $RE_MIN;

    XX: for (my $xx=0; $xx < $SIZEX; $xx++){
    
        my ($Z_re, $Z_im, $i) = (0,0);

        # Z0=0, Zn+1 = Zn^2 + C
        ESCAPE_ITERATIONS: for ($i = 1; $i<$ITERATIONS; $i++){

            my ($Z_re2, $Z_im2) = ($Z_re * $Z_re, $Z_im * $Z_im);

            last ESCAPE_ITERATIONS unless ($Z_re2 + $Z_im2 < 4);

            # (a+bi)^2 = a^2 + 2abi - b^2
            $Z_im = 2 * $Z_re * $Z_im + $C_im;
            $Z_re = $Z_re2 - $Z_im2 + $C_re;

        } # end: ESCAPE_ITERATIONS

        # draw pixel
        $img->setPixel(
            $xx, $yy, $i == $ITERATIONS ? $cl_black : $cl_white
        );

        $C_re += $re_factor;

    } # end: XX

    $C_im += $im_factor;

} # end: YY

# save image
print $fh $img->png(0);
close $fh;

Il codice è stato mantenuto semplice per facilitare le modifiche e la comprensione.

E’ richiesto il package GD per la produzione dell’immagine di output in formato PNG: “mandelbrot.png“.

mandelbrot.png generato dal sorgente perl

 

Colori

Normalmente, per rendere tale frattale più gradevole, nella sua rappresentazione più semplice, si colorano i punti esterni all’insieme in funzione della velocità con la quale divergono a più infinito. Per la colorazione dei punti interni ed esterni esistono una miriade di algoritmi di complessità crescente; alcuni spunti interessanti.

Insieme di Julia

Una variante dell’insieme di Mandelbrot è l’insieme di Julia definito in questo modo:

  Q_n^K(c)=  \begin{cases}  & Z_0=c  \\  & Z_{n+1}=Z_n^2+K  \end{cases}

 

Rispetto all’insieme di Mandelbrot cambia la successione ricorsiva ed è stata introdotta una costante complessa K.

Analogamente a Mandelbrot i punti appartenenti all’insieme di Julia sono quelli per cui il modulo della successione ricorsiva non diverge.

  J=\left\{c\in \mathbb{C} : \exists s \in \mathbb{R}, \forall n \in \mathbb{N},|Q_n^K(c)| \leq s \right\}

 

Alcuni valori di K che si consiglia di esplorare:

  • K = 0.353+0.288i
  • K = -0.70176-0.3842i
  • K = -0.835-0.2321i
  • K= -0.45+0.1428i

Dopo aver adeguato lo script perl, ho rappresentato questi insiemi di Julia:

Insieme di Julia (K=0.353+0.288i)

    Insieme di Julia (K=-0.835-0.2321i)

    Riferimenti

    Mandelbrot Set – Wikipedia
    Mu-Ency – The Encyclopedia of the Mandelbrot Set
    The Mandelbrot Set (algoritmo tracciamento)
    Julia Set – Wikipedia

    Esplorazione

    Visual Guide To Patterns In The Mandelbrot SetMandelbrot: World Map and Popular Tourist Areas

    Share