<jupyter_start><jupyter_text>Project - LineArtTSP Group member: <NAME>, <NAME>, <NAME>  Introduction:Approximate images using a single closed curve generated by halftoning the image and finding a cycle by solving TSP on the generated stippling points.The backbone of this project will consist of these major components:Halftone an arbitrary image and convert points to graph object Find non self intersection Hamiltonian cycle on nodes by solving TSP using heuristic Plot the resulting curve  HalftoningThe purpose of halftoning is to approximate an image with a set of points.Introduction to our Halftoning implementation: Takes a random selection of n points (see below) from the image. If one is using the contrast halftoning method, it will compare these points to the point x_pixel_distance and y_pixel_distance away from the chosen point(see docstring for specific information) and accept the point if it is sufficiently different from this neighbor point, based on the application of a euclidean metric to RGB values, conditioned on an input contrast_threshold value.One can 'smoothen' this acceptance of points (i.e. accepting points in a neighborhood of the contrast based on a probability function) by setting the smoothing_constant to a value between 0 and 1 (0 means no smoothing, 1 means mostgenerous probability function). If one is using the brightness method, it will convert the image to grayscale, and perform rejection sampling (see https://en.wikipedia.org/wiki/Rejection_sampling) on n points, based on the brightness of n randomly chosen points. For either method, one can set 'invert' to True in order to reverse the functions of each of these methods. This ends up meaning exactly what one would intuitively expect - for the contrast method, it will instead only choose points that are similar to nearby points, and for the brightness method, it will choose points that are lighter, rather than points that are darker.An interesting extension about halftone: https://tabreturn.github.io/code/processing/python/2019/02/09/processing.py_in_ten_lessons-6.3-_halftones.html  TSPTSP is the traveling salesman problem, the purpose of which is to find the shortest cycle that includes all nodes in a graph. In our case, this means we will attempt to find the shortest cycle that goes through every halftoning point, as this willapproximate our image with one line, instead of a series of points.We do not implement a TSP solver ourselves, we use the OR-tools package from Google to do this, see more here:https://developers.google.com/optimization/routing/tsp  GuideFirst you should decide on a couple of things:1. Which image do you want to convert to a line drawing?2. n - The number of points that the graph will use (think of it as the resolution of your output image)3. timelimit - How long are you willing to let the TSP solver run? (the longer the better the result)4. imagestyle - Which style do you want your halftoning to have?5. style - Which style do you want your output to have?There are three different styles to choose, one is points, which is result of an image after halftoning, and the other two styles are line and spline, which connected selected points by a closed line, the latter being a smoothened variant.  First we import our custom class and halftoning function:<jupyter_code>from graph import Graph
from halftoning import rejectionSampling<jupyter_output>%pylab is deprecated, use %matplotlib inline and import the required libraries.
Populating the interactive namespace from numpy and matplotlib<jupyter_text>Set the path variable to the path of your chosen image.Set n to the amount of points you want.Halftone the image based on desired imagestyle (halftoning or brightness; for now, we will use brightness, with an example of when contrast can be better to use). Our program will select points randomly, and use rejection sampling based on the grey_scale value of these points (in the case of brightness) in order to choose whether the point will be accepted - this results in darker regions of an image having more points selected, and hence being accentuated more in the final product.By increasing n (number of points), the clarify of the resultant graph can be increased.<jupyter_code># Generate test data points
n=1000
# Path to image file
path = 'recurrentTheme.jpg'
# Generate points
nodes1 = rejectionSampling(n, path, imagestyle = "brightness")

#See the image here:
from IPython.display import Image
Image(filename=path)<jupyter_output><empty_output><jupyter_text>Then, we create our graph object, set the nodes to those chosen in our halftoning process, and calculate the distance matrix of these nodes.Finally, we solve the traveling salesman problem based on a time limit - the code will attempt to find an optimal path during this time, and return the best path at the end of the time.<jupyter_code># Create graph object solve TSP
G = Graph()
G.setNodes(nodes1)
G.setDistMatrix()
G.TSP(timelimit=30);<jupyter_output>100%|██████████| 990/990 [00:05<00:00, 197.09it/s]<jupyter_text>Here is an example of the points chosen by the brightness method, plotted, i.e. the 'points' style.<jupyter_code>G.plot(style="point")<jupyter_output><empty_output><jupyter_text>Here is an example of the graph following an application of the traveling salesman problem, with nodes connected by lines, i.e. the 'lines' style.<jupyter_code>G.plot(style="line")<jupyter_output><empty_output><jupyter_text>Finally, here is an example of the graph following an application of the traveling salesman problem, with nodes connected by splines, i.e. the 'splines' style.<jupyter_code>G.plot(style="spline")<jupyter_output><empty_output><jupyter_text>If, instead, we choose to use the imagestyle "contrast", then our halftoning will instead select points based on how different they are from a neighboring point, on a scale of 0 to 1.(this neighboring point can be determined, for all points, by using x_pixel_distance and y_pixel_distance parameters) using the euclidean metric applied to RGB values. How much contrast we use is determined by our contrast_threshold, which has a default value of 0.15 - this can be changed by setting contrast_threshold to the desired value in the rejectionSampling parameters.The contrast method tends to be a superior option when working with an image where regions of color are clearly separated, or where one determines that there is more value to be had in graphing the 'edges' of these images, rather than the contents of the regions of color - this method falls short where neighboring points of any point are almost ubiquitously sufficiently contrasting, such as in an extremely detailed painting like the 'Mona Lisa'.<jupyter_code>path2 = 'fedex.jpg'
nodes2 = rejectionSampling(n, path2, imagestyle = "contrast")
R = Graph()
R.setNodes(nodes2)
R.setDistMatrix()
R.TSP(timelimit=30);
R.plot(style="point")<jupyter_output>100%|██████████| 977/977 [00:04<00:00, 235.32it/s]<jupyter_text>An image such as the Fedex logo, for example, yields a better end result when using the contrast method.<jupyter_code>nodes3 = rejectionSampling(n,path2,imagestyle='brightness')
A = Graph()
A.setNodes(nodes3)
A.setDistMatrix()
A.TSP(timelimit=30);
A.plot(style="point") 
R.plot(style="line")
A.plot(style="line")

R.plot(style="spline")
A.plot(style="spline")<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.05999183784519113, 'fraction_numerical': 0.011835124472860835, 'mean_word_length': 5.460456942003515, 'pattern_counts': {'":': 0, '<': 35, '<?xml version=': 0, '>': 33, 'https://': 3, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '8', 'dir': 'jupyter-structured-clean-dedup', 'id': '511314', 'license': 'MIT', 'n_tokens_mistral': 2003, 'n_tokens_neox': 1894, 'n_words': 1000, 'path': 'demo_file.ipynb', 'repo_name': 'Lussebullen/LineArtTSP', 'size': '7372'}