I have noticed even people who claim everything is predestined, and that we can do nothing to change it, look before they cross the road (Stephen Hawking)
Imagine a salesman and a set of cities. The salesman has to visit each one of the cities starting from a certain one and returning to the same city. The challenge is finding the route which minimizes the total length of the trip. This is the Travelling Salesman Problem (TSP): one of the most profoundly studied questions in computational mathematics. Since you can find a huge amount of articles about the TSP in the Internet, I will not give more details about it here.
In this experiment I apply an heuristic algorithm to solve the TSP to draw a portrait. The idea is pretty simple:
- Load a photo
- Convert it to black and white
- Choose a sample of black points
- Solve the TSP to calculate a route among the points
- Plot the route
The result is a single line drawing of the image that you loaded. To solve the TSP I used the arbitrary insertion heuristic algorithm (Rosenkrantz et al. 1977), which is quite efficient.
To illustrate the idea, I have used again this image of Frankenstein (I used it before in this other experiment). This is the result:
You can find the code here.
I follow your R-bloggers post. Love it.
Today you wrote “A simple definition of laminar flow is when a fluid flows through a pipe in parallel layers with no disruptions between these layers” Look at wikipedia Kármán vortex street for an example of laminar flow. Laminar flow is not turbulent flow where turbulent flow is chaotic.
Hi Antonio,
Thank you for sharing your code.
I was trying to reproduce your plot but am having some issue with the code. I think its when you use row_number() it gives me an error.
data.frame(id=solution) %>%
mutate(order=row_number()) -> order
so i updated your code to
data.frame(id=solution) %>%
dplyr::mutate(order=row_number()) -> order
and am able to generate the plot but my plot looks like a lot of lines and no where close to frakenstein. Any idea what could be the issue. Thanks.
Regards,
Atmajit
Hi,
I have the following error message:
data.frame(id=solution) %>%
+ mutate(order=row_number()) -> order
Error in rank(x, ties.method = “first”, na.last = “keep”) :
argument “x” is missing, with no default
any idea of whats wrong?
Best regards and many thanks for your code
Cool! But I think this post is a trap to get nerds to say “Frankenstein is the name of the scientist, not the monster”, and I won’t be falling for that.
Very cool, as always 🙂
Hi 🙂 thank you for your code. This is really cool however no matter what image I upload, I still always get Frankenstein back. I was trying to get a Rhinoceros but I still end up with Frankenstein in the end. Is this because the TSP algorithm is linked to the Frankenstein image?
Here is a sample of my code:
install.packages(“imager”)
install.packages(“magrittr”)
install.packages(“dplyr”)
install.packages(“ggplot2”)
install.packages(“scales”)
install.packages(“TSP”)
install.packages(“stringi”)
library(imager)
library(dplyr)
library(ggplot2)
library(scales)
library(TSP)
urlfile=”https://www.conservationmagazine.org/wp-content/uploads/2014/02/white-rhino.jpg”
file=”white-rhino.jpg”
if(!file.exists(file)) download.file(urlfile, destfile = file, mode = ‘wb’)
load.image(file) %>%
grayscale() %>%
threshold(“45%”) %>%
as.cimg() %>%
as.data.frame() %>%
sample_n(8000, weight=(1-value)) %>%
select(x,y) -> data
as.TSP(dist(data)) %>%
solve_TSP(method = “arbitrary_insertion”) %>%
as.integer() -> solution
data_to_plot <- data[solution,]
ggplot(data_to_plot, aes(x,y))+
geom_path() +
scale_y_continuous(trans=reverse_trans())+
coord_fixed()+
theme_void()
ggsave("rhinoTSP.png", dpi = 600, width = 4, height = 5)
Hi, thanks! No, it’s not linked. Did you restarted Rstudio session? If still doesnt work, let me know.