Hier, j’ai parcouru un article amusant de Randal S. Olson, intitulé « Here’s Waldo: Computing the optimal search strategy for finding Waldo« . Bon, ce n’est rien de nouveau, je sais, j’arrive un peu en retard, ça date de 2015. Quoi qu’il en soit, j’ai voulu apporter mon petit grain de sable au contenu proposé par Randal. Dans son billet, il explique qu’il a passé son week-end à chercher une stratégie optimale pour trouver Charlie. Vous savez, ce petit personnage en pull rayé rouge et blanc, avec un bonnet à pompom sur la tête. Pour ce faire, Randal a utilisé des techniques de machine learning. Il s’appuie sur une image publiée par Slate (Here’s Waldo, 2013, par Ben Blatt), qui répertorie la position de Charlie dans 68 double pages des albums. Randal extrait les coordonnées de l’image (et les partage gentiment).

Dans une première étape, il estime la densité des points par la méthode du noyau. Et voici ce qu’il trouve :

Densité par la méthode du noyau des positions de Charlie (Randal S. Olson)

Densité par la méthode du noyau des positions de (Randal S. Olson)

J’ai alors décidé de prendre un (tout petit) peu de mon temps pour reproduire ça, et en profiter pour appliquer une correction à la mesure, sur les bords de l’image. En fait, il y a quelques temps, Arthur Charpentier (aka @freakonometrics) et moi avons bossé sur une estimation par la méthode du noyau de la densité de points sur des surfaces en 2D. On a fourni une méthode facile à utiliser qui corrige d’un biais qu’on retrouve près des bords d’une surface dans laquelle les points sont contraints de se trouver (l’article est publié chez Geoinformatica, et vous pouvez trouver quelques explications sur mon blog, ou encore sur celui d’Arthur). En bref, le problème de l’estimation de la densité des positions de Charlie, c’est qu’on sait qu’elles sont forcées d’être sur une surface définie, à savoir la double page d’un album. On sait de facto qu’il est impossible que notre cher Charlie se retrouve en dehors du rectangle qui définit la double page. Aussi, quand on estima le densité des points, on est confronté à un effet de bords, puisqu’on ne prend pas en compte le fait qu’il n’y aura pas de points au-delà de ces bords.

J’ai alors utilisé les codes qu’on avait mis à disposition sur GitHub (il faut d’ailleurs que je compile ça sous forme d’un package, pour que ça soit plus pratique à utiliser…), pour estimer la densité des points, en appliquant cette fois-ci la correction.

Après avoir chargé les données, je graphe les points, et voici ce que j’obtiens:

Positions de Charlie

Positions de Charlie

J’émets l’hypothèse que le rectangle sur lequel on doit chercher Charlie est de largeur 8 et de longueur 13.


bounding_polygon <- data.frame(x = c(0, 0, 13, 13, 0), y = c(0, 8, 8, 0, 0))
bounding_polygon_gpc <- as(bounding_polygon, "gpc.poly")

Je lance le code pour estimer la densité :


# Estimation avec la correction
smoothed_kde <- sKDE(U = waldo[, c("X", "Y")],
                     polygon = bounding_polygon_gpc,
                     optimal=TRUE, parallel = FALSE)

# Estimation sans corriger des effets de bords
smoothed_kde_nc <- sKDE_without_c(U = waldo[, c("X", "Y")],
                                  polygon = bounding_polygon_gpc,
                                  optimal=TRUE)

Ensuite, je graphe les résultats sur deux différentes figures. La première montre la densité estimée sans correction, et la seconde avec correction.

Estimation par la méthode du noyau de la position de Charlie, sans corriger des effets de bords

Estimation par la méthode du noyau de la position de Charlie, sans corriger des effets de bords

Estimation par la méthode du noyau de la position de Charlie, en corrigeant des effets de bords

Estimation par la méthode du noyau de la position de Charlie, en corrigeant des effets de bords

Comme on peut le voir, l'estimation de la densité augmente près des bordes, notamment sur le coin haut droit.

Cependant, dans son billet, Randal indique qu'il est impossible de trouver Charlie dans la petite carte postale qu'on trouve en haut à gauche de chaque double-page. J'ai alors pris en une région correspondant à peu près à cette carte postale, dans laquelle il n'y aura pas de points.


postcard <- data.frame(x = c(1, 1, 3, 3, 1), y = c(5, 7.5, 7.5, 5, 5))
postcard_gpc <- as(postcard, "gpc.poly")

Je retire cette surface de mon rectangle correspondant à la double page :


bound_pol <- gpclib::setdiff(bounding_polygon_gpc, postcard_gpc)

Puis j'estime à nouveau la densité :


# Estimation avec correction des effets de bords
smoothed_kde_post <- 
  sKDE(U = waldo[, c("X", "Y")],
       polygon = bound_pol,
       optimal=TRUE, parallel = FALSE)

# Estimation sans correction
smoothed_kde_post_nc <- 
  sKDE_without_c(U = waldo[, c("X", "Y")],
                 polygon = bound_pol,
                 optimal=TRUE)
Estimation par la méthode du noyau de la position de Charlie, sans corriger des effets de bords, mais en prenant en compte la carte postale

Estimation par la méthode du noyau de la position de Charlie, sans corriger des effets de bords, mais en prenant en compte la carte postale

Estimation par la méthode du noyau de la position de Charlie, en corrigeant des effets de bords, et en prenant en compte la carte postale

Estimation par la méthode du noyau de la position de Charlie, en corrigeant des effets de bords, et en prenant en compte la carte postale

Pour le fun, un petit gif montrant comment l'estimation de la densité évolue dans le cas sans correction (sans la carte postale), et dans le cas avec correction (avec la carte postale) :

Si vous souhaitez reproduire ces graphiques, les codes complets sont disponibles ici.

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *

Time limit is exhausted. Please reload CAPTCHA.