{"id":1125,"date":"2015-03-06T11:16:34","date_gmt":"2015-03-06T16:16:34","guid":{"rendered":"https:\/\/blogs.mathworks.com\/loren\/?p=1125"},"modified":"2015-03-09T08:50:26","modified_gmt":"2015-03-09T13:50:26","slug":"why-wheres-waldo","status":"publish","type":"post","link":"https:\/\/blogs.mathworks.com\/loren\/2015\/03\/06\/why-wheres-waldo\/","title":{"rendered":"Why &#8220;Where&#8217;s Waldo&#8221;?"},"content":{"rendered":"<div class=\"content\"><!--introduction--><p>Today I'd like to introduce guest blogger Seth DeLand who works for the MATLAB Product Marketing team here at MathWorks. Today, Seth will be discussing some different optimization techniques that he used for developing a strategy for the puzzle-books \"Where's Waldo?\".<\/p><!--\/introduction--><h3>Contents<\/h3><div><ul><li><a href=\"#88bf6b14-1274-41f2-ae1b-854f2da80068\">Finding the shortest path<\/a><\/li><li><a href=\"#ab043243-f2de-4853-94c3-fc67bd9b86a9\">A different take on the shortest path<\/a><\/li><li><a href=\"#3bb4e52b-2cbd-4bda-a498-f6d4d25c462a\">Analyzing the solution<\/a><\/li><\/ul><\/div><p>There was a nice <a href=\"http:\/\/www.randalolson.com\/2015\/02\/03\/heres-waldo-computing-the-optimal-search-strategy-for-finding-waldo\/\">post on Randal Olson&#8217;s blog<\/a> last week about techniques for the popular puzzle-books &#8220;Where's Waldo?&#8221; (originally &#8220;Where&#8217;' Wally?&#8221; in the UK).<\/p><p>As a kid, I spent hours going through my collection of Where's Waldo? books, so I was inspired by Randal's post to do some of my own analysis. It would be great if I could show that in the last 20 years, I&#8217;ve learned enough to have a little better strategy for finding Waldo.<\/p><p>I started by grabbing the data for the Waldo locations in every book, and plotting the points:<\/p><pre class=\"codeinput\">pts = webread(<span class=\"string\">'http:\/\/www.randalolson.com\/wp-content\/uploads\/wheres-waldo-locations.csv'<\/span>);\r\nplot(pts.X,pts.Y,<span class=\"string\">'*'<\/span>);\r\n<\/pre><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/images\/loren\/2015\/waldoWriteup_01.png\" alt=\"\"> <h4>Finding the shortest path<a name=\"88bf6b14-1274-41f2-ae1b-854f2da80068\"><\/a><\/h4><p>The next thing I wanted to do was try to reproduce some of Randal&#8217;s results.  The traveling salesman problem (What is the shortest path that goes through all of the points?) is always fun to dig into.  I used the same start and end points for my path as in the original post, but took a different approach for finding the solution.  Instead of using a genetic algorithm, I chose to formulate this as a binary programming problem, similar to what is done in <a href=\"https:\/\/www.mathworks.com\/help\/optim\/examples\/travelling-salesman-problem.html\">this example<\/a>.  This approach has 2 advantages:<\/p><div><ol><li>It's really fast for problems of this size (on the order of 100 stops)<\/li><li>We can prove we&#8217;ve actually found the shortest possible path<\/li><\/ol><\/div><p>Let's look at the results:<\/p><pre class=\"codeinput\">[order,pathLength,output] = shortestPathAToB([pts.X pts.Y],1,67);\r\nhold <span class=\"string\">on<\/span>\r\nplot(pts.X(order),pts.Y(order))\r\n<\/pre><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/images\/loren\/2015\/waldoWriteup_02.png\" alt=\"\"> <p>Examining the output from the INTLINPROG optimization solver, we see that the Absolute Gap is 0, meaning we have found the shortest possible path.<\/p><pre class=\"codeinput\">output.absolutegap\r\n<\/pre><pre class=\"codeoutput\">ans =\r\n     0\r\n<\/pre><h4>A different take on the shortest path<a name=\"ab043243-f2de-4853-94c3-fc67bd9b86a9\"><\/a><\/h4><p>Solving the traveling salesman problem is nice, but when you&#8217;re actually searching for Waldo you&#8217;re looking at a region instead of a point.  It&#8217;s kind of like you&#8217;re applying a circular mask to the page, and you can see everything within that circle.  So this got me thinking: what if we tried to find the shortest path, such that if you translated a circle of radius &#8220;r&#8221; along that path, you would cover all of the Waldo locations? This makes the problem a bit more complex, since we have to compute distances from all of the Waldo locations to arbitrary line segments making up the path.<\/p><p>I chose to formulate it as a nonlinear programming problem, where again the objective is to minimize the total distance, and we add a nonlinear constraint that says all of the Waldo points must be within &#8220;r&#8221; of some point on the path.  The solution from the last problem serves as a good starting point.  We then have enough to turn FMINCON loose on the problem.  To make things interesting, I solved for 4 different values of &#8220;r&#8221;.<\/p><pre class=\"codeinput\">r = 0.25:0.25:1;\r\n\r\npts = pts(order,:);\r\nnpts = length(pts.X);\r\nx0 = [pts.X; pts.Y]; <span class=\"comment\">% Initial guess at solution<\/span>\r\nlb = zeros(2*npts,1); <span class=\"comment\">% All variables &gt;= 0<\/span>\r\nub = [13*ones(npts,1); 8*ones(npts,1)]; <span class=\"comment\">% x-variables are &lt;= 13, y-variables are &lt;= 8<\/span>\r\noptions = optimoptions(<span class=\"string\">'fmincon'<\/span>,<span class=\"keyword\">...<\/span>\r\n    <span class=\"string\">'Algorithm'<\/span>,<span class=\"string\">'sqp'<\/span>,<span class=\"keyword\">...<\/span>\r\n    <span class=\"string\">'Display'<\/span>,<span class=\"string\">'none'<\/span>,<span class=\"keyword\">...<\/span>\r\n    <span class=\"string\">'TolFun'<\/span>,1E-3,<span class=\"keyword\">...<\/span>\r\n    <span class=\"string\">'MaxFunEvals'<\/span>,1E5);\r\n\r\nxopt = zeros(length(x0),length(r));\r\nfval = zeros(1,length(r));\r\n<span class=\"keyword\">parfor<\/span> i = 1:length(r)\r\n    noncon = @(x) nonlcon(x,[pts.X,pts.Y],r(i));\r\n    [xopt(:,i),fval(i)] = fmincon(@objfcn,x0,[],[],[],[],lb,ub,noncon,options);\r\n<span class=\"keyword\">end<\/span>\r\n\r\nfigure;\r\n<span class=\"keyword\">for<\/span> i = 1:length(r)\r\n    subplot(2,2,i);\r\n    drawPath(xopt(:,i),pts,r(i));\r\n    title({[<span class=\"string\">'View Radius = '<\/span> num2str(r(i))]; <span class=\"keyword\">...<\/span>\r\n        [<span class=\"string\">'Path Length = '<\/span> num2str(fval(i))]});\r\n<span class=\"keyword\">end<\/span>\r\n<\/pre><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/images\/loren\/2015\/waldoWriteup_03.png\" alt=\"\"> <h4>Analyzing the solution<a name=\"3bb4e52b-2cbd-4bda-a498-f6d4d25c462a\"><\/a><\/h4><p>As expected, as the value of &#8220;r&#8221; increases, the length of the path decreases.  Here&#8217;s an animation of what it would look like traversing this path for a view radius of 1:<\/p><p><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/images\/loren\/2015\/findingWaldo.gif\" alt=\"\"> <\/p><p>The path length shrinks from a length of 58.8 when we explicitly visit each stop, to 31.2 when we have a radius of 1.  So we have managed to shorten our search path by quite a bit.  Looking at the path, I would describe it as a Z then an uppercase Lambda, or:<\/p><p>$$Z\\Lambda$$<\/p><p>That makes it easy enough to remember.  All of the code I used for this analysis is available in <a href=\"https:\/\/github.com\/sdeland\/Wheres_Waldo\">this GitHub repository<\/a>.<\/p><p>Who has a different idea for finding Waldo?  Have any of you image processing gurus tried tackling this problem? Let us know <a href=\"https:\/\/blogs.mathworks.com\/loren\/?p=1125#respond\">here<\/a>.<\/p><script language=\"JavaScript\"> <!-- \r\n    function grabCode_ad9a68cee5a84ee3ad681deefc0555b3() {\r\n        \/\/ Remember the title so we can use it in the new page\r\n        title = document.title;\r\n\r\n        \/\/ Break up these strings so that their presence\r\n        \/\/ in the Javascript doesn't mess up the search for\r\n        \/\/ the MATLAB code.\r\n        t1='ad9a68cee5a84ee3ad681deefc0555b3 ' + '##### ' + 'SOURCE BEGIN' + ' #####';\r\n        t2='##### ' + 'SOURCE END' + ' #####' + ' ad9a68cee5a84ee3ad681deefc0555b3';\r\n    \r\n        b=document.getElementsByTagName('body')[0];\r\n        i1=b.innerHTML.indexOf(t1)+t1.length;\r\n        i2=b.innerHTML.indexOf(t2);\r\n \r\n        code_string = b.innerHTML.substring(i1, i2);\r\n        code_string = code_string.replace(\/REPLACE_WITH_DASH_DASH\/g,'--');\r\n\r\n        \/\/ Use \/x3C\/g instead of the less-than character to avoid errors \r\n        \/\/ in the XML parser.\r\n        \/\/ Use '\\x26#60;' instead of '<' so that the XML parser\r\n        \/\/ doesn't go ahead and substitute the less-than character. \r\n        code_string = code_string.replace(\/\\x3C\/g, '\\x26#60;');\r\n\r\n        copyright = 'Copyright 2015 The MathWorks, Inc.';\r\n\r\n        w = window.open();\r\n        d = w.document;\r\n        d.write('<pre>\\n');\r\n        d.write(code_string);\r\n\r\n        \/\/ Add copyright line at the bottom if specified.\r\n        if (copyright.length > 0) {\r\n            d.writeln('');\r\n            d.writeln('%%');\r\n            if (copyright.length > 0) {\r\n                d.writeln('% _' + copyright + '_');\r\n            }\r\n        }\r\n\r\n        d.write('<\/pre>\\n');\r\n\r\n        d.title = title + ' (MATLAB code)';\r\n        d.close();\r\n    }   \r\n     --> <\/script><p style=\"text-align: right; font-size: xx-small; font-weight:lighter;   font-style: italic; color: gray\"><br><a href=\"javascript:grabCode_ad9a68cee5a84ee3ad681deefc0555b3()\"><span style=\"font-size: x-small;        font-style: italic;\">Get \r\n      the MATLAB code <noscript>(requires JavaScript)<\/noscript><\/span><\/a><br><br>\r\n      Published with MATLAB&reg; R2015a<br><\/p><\/div><!--\r\nad9a68cee5a84ee3ad681deefc0555b3 ##### SOURCE BEGIN #####\r\n%% Why \"Where's Waldo\"?\r\n% Today I'd like to introduce guest blogger Seth DeLand who works for the\r\n% MATLAB Product Marketing team here at MathWorks. Today, Seth will be\r\n% discussing some different optimization techniques that he used for\r\n% developing a strategy for the puzzle-books \"Where's Waldo?\".\r\n%\r\n%%\r\n% There was a nice\r\n% <http:\/\/www.randalolson.com\/2015\/02\/03\/heres-waldo-computing-the-optimal-search-strategy-for-finding-waldo\/\r\n% post on Randal Olson\u00e2\u20ac\u2122s blog> last week about techniques for the popular\r\n% puzzle-books \u00e2\u20ac\u0153Where's Waldo?\u00e2\u20ac\ufffd (originally \u00e2\u20ac\u0153Where\u00e2\u20ac\u2122' Wally?\u00e2\u20ac\ufffd in the UK).\r\n%\r\n% As a kid, I spent hours going through my collection of Where's Waldo? \r\n% books, so I was inspired by Randal's post to do some of my own analysis. \r\n% It would be great if I could show that in the last 20 years, I\u00e2\u20ac\u2122ve learned\r\n% enough to have a little better strategy for finding Waldo.\r\n%\r\n% I started by grabbing the data for the Waldo locations in every book, and\r\n% plotting the points:\r\n\r\npts = webread('http:\/\/www.randalolson.com\/wp-content\/uploads\/wheres-waldo-locations.csv');\r\nplot(pts.X,pts.Y,'*');\r\n\r\n%% Finding the shortest path\r\n% The next thing I wanted to do was try to reproduce some of Randal\u00e2\u20ac\u2122s \r\n% results.  The traveling salesman problem (What is the shortest path that \r\n% goes through all of the points?) is always fun to dig into.  I used the \r\n% same start and end points for my path as in the original post, but took \r\n% a different approach for finding the solution.  Instead of using a \r\n% genetic algorithm, I chose to formulate this as a binary programming \r\n% problem, similar to what is done in <https:\/\/www.mathworks.com\/help\/optim\/examples\/travelling-salesman-problem.html this example>.  This approach has 2 \r\n% advantages: \r\n% \r\n% # It's really fast for problems of this size (on the order of 100 stops)\r\n% # We can prove we\u00e2\u20ac\u2122ve actually found the shortest possible path\r\n% \r\n% Let's look at the results:\r\n\r\n[order,pathLength,output] = shortestPathAToB([pts.X pts.Y],1,67);\r\nhold on\r\nplot(pts.X(order),pts.Y(order))\r\n\r\n%%\r\n% Examining the output from the INTLINPROG optimization solver, we see \r\n% that the Absolute Gap is 0, meaning we have found the shortest possible \r\n% path.  \r\noutput.absolutegap\r\n\r\n%% A different take on the shortest path\r\n% Solving the traveling salesman problem is nice, but when you\u00e2\u20ac\u2122re actually \r\n% searching for Waldo you\u00e2\u20ac\u2122re looking at a region instead of a point.  It\u00e2\u20ac\u2122s \r\n% kind of like you\u00e2\u20ac\u2122re applying a circular mask to the page, and you can see\r\n% everything within that circle.  So this got me thinking: what if we \r\n% tried to find the shortest path, such that if you translated a circle of \r\n% radius \u00e2\u20ac\u0153r\u00e2\u20ac\ufffd along that path, you would cover all of the Waldo locations?  \r\n% This makes the problem a bit more complex, since we have to compute \r\n% distances from all of the Waldo locations to arbitrary line segments \r\n% making up the path.  \r\n%\r\n% I chose to formulate it as a nonlinear programming problem, where again \r\n% the objective is to minimize the total distance, and we add a nonlinear \r\n% constraint that says all of the Waldo points must be within \u00e2\u20ac\u0153r\u00e2\u20ac\ufffd of some \r\n% point on the path.  The solution from the last problem serves as a good\r\n% starting point.  We then have enough to turn FMINCON loose on the \r\n% problem.  To make things interesting, I solved for 4 different values \r\n% of \u00e2\u20ac\u0153r\u00e2\u20ac\ufffd.\r\n\r\nr = 0.25:0.25:1;\r\n\r\npts = pts(order,:);\r\nnpts = length(pts.X);\r\nx0 = [pts.X; pts.Y]; % Initial guess at solution\r\nlb = zeros(2*npts,1); % All variables >= 0\r\nub = [13*ones(npts,1); 8*ones(npts,1)]; % x-variables are <= 13, y-variables are <= 8\r\noptions = optimoptions('fmincon',...\r\n    'Algorithm','sqp',...\r\n    'Display','none',...\r\n    'TolFun',1E-3,...\r\n    'MaxFunEvals',1E5);\r\n\r\nxopt = zeros(length(x0),length(r));\r\nfval = zeros(1,length(r));\r\nparfor i = 1:length(r) \r\n    noncon = @(x) nonlcon(x,[pts.X,pts.Y],r(i));\r\n    [xopt(:,i),fval(i)] = fmincon(@objfcn,x0,[],[],[],[],lb,ub,noncon,options);\r\nend\r\n\r\nfigure;\r\nfor i = 1:length(r)\r\n    subplot(2,2,i);\r\n    drawPath(xopt(:,i),pts,r(i));\r\n    title({['View Radius = ' num2str(r(i))]; ...\r\n        ['Path Length = ' num2str(fval(i))]});\r\nend\r\n\r\n%% Analyzing the solution\r\n% As expected, as the value of \u00e2\u20ac\u0153r\u00e2\u20ac\ufffd increases, the length of the path \r\n% decreases.  Here\u00e2\u20ac\u2122s an animation of what it would look like traversing \r\n% this path for a view radius of 1:\r\n% \r\n% <<findingWaldo.gif>>\r\n% \r\n% The path length shrinks from a length of 58.8 when we explicitly visit \r\n% each stop, to 31.2 when we have a radius of 1.  So we have managed to \r\n% shorten our search path by quite a bit.  Looking at the path, I would\r\n% describe it as a Z then an uppercase Lambda, or:\r\n% \r\n% $$Z\\Lambda$$\r\n% \r\n% That makes it easy enough to remember.  All of the code I used for this\r\n% analysis is available in <https:\/\/github.com\/sdeland\/Wheres_Waldo this\r\n% GitHub repository>.\r\n%\r\n% Who has a different idea for finding Waldo?  Have any of you image\r\n% processing gurus tried tackling this problem? Let us know\r\n% <https:\/\/blogs.mathworks.com\/loren\/?p=1125#respond here>.\r\n\r\n##### SOURCE END ##### ad9a68cee5a84ee3ad681deefc0555b3\r\n-->","protected":false},"excerpt":{"rendered":"<div class=\"overview-image\"><img decoding=\"async\"  class=\"img-responsive\" src=\"https:\/\/blogs.mathworks.com\/images\/loren\/2015\/waldoWriteup_03.png\" onError=\"this.style.display ='none';\" \/><\/div><!--introduction--><p>Today I'd like to introduce guest blogger Seth DeLand who works for the MATLAB Product Marketing team here at MathWorks. Today, Seth will be discussing some different optimization techniques that he used for developing a strategy for the puzzle-books \"Where's Waldo?\".... <a class=\"read-more\" href=\"https:\/\/blogs.mathworks.com\/loren\/2015\/03\/06\/why-wheres-waldo\/\">read more >><\/a><\/p>","protected":false},"author":39,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":[],"categories":[33,60],"tags":[],"_links":{"self":[{"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/posts\/1125"}],"collection":[{"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/users\/39"}],"replies":[{"embeddable":true,"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/comments?post=1125"}],"version-history":[{"count":4,"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/posts\/1125\/revisions"}],"predecessor-version":[{"id":1139,"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/posts\/1125\/revisions\/1139"}],"wp:attachment":[{"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/media?parent=1125"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/categories?post=1125"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/tags?post=1125"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}