For a college project last year, I built a plotter using cd drives. It had two cd drives in it, one for x direction and one for y. Pretty quickly it was drawing basic shapes like circles and squares. This was done by creating a simple function that accepted two arguments : the x and y co-ordinates to move to. Every step of the stepper motors was counted. So the positon of the platform was known. For example if the marker was at position (50,50) and I passed (30,60) to the function. The x-stepper would rotate 20 steps in the negative direction and the y stepper 10 steps in the positive direction. So printing out simple shapes was easy, but I wanted to be able to print out pictures that were made on a computer. Look at the picture below for an example of an image that could be sent to the printer:
If I could find all of the x-y points of the pixels that make up this line, I could pass them to my x-y function and the plotter would draw the line. Sounds easy! Unfortunately there are some more things to think about before this will work properly . The first thing is the computer program that is going to find all of the x-y points of the line. This program won’t ‘follow the line’ as in, it wont start at one end of the line and spit out all of the x-y points in order, as if the line was being traced by hand. Instead it would start at an edge of the image and move across. Wherever it finds a black pixel, this x-y co-ordinate is stored in an array. This is kind of like how a traditional printer works, start at top row of pixels, move across, down one row, move across etc. This is known as the rastor method of printing. Laser cutters and plotters are much better suited to vector plotting. So we need to figure out how to convert the array of pixels from raster to vector. If the array of pixels was sent as is (raster format) to the the laser printer or plotter. This would be the result:
This GIF is presuming that the laser or marker is turned off when moving between the points. If like in my case it was a marker resting on a moving platform. The image would turn out like the gif below because it never leaves the platform surface:
This method of plotting results in a jerky kind of motion as opposed to smoothly following the curve of a line. What we want is for the program to find an x-y point at one side of the line, and then ‘follow’ the line. As in, we want it to start of at one x-y point and then move to the closest x-y point after that (joining the dots). Then keep doing this until all of the points on the line have been recorded.
One way of approaching this problem is to think about a single pixel and it’s immediate neighbours. Most pixels will have eight neighbouring pixels, as shown in the image below.
Take for example this black line:
One way to arrange the points in the way we want is to start at a pixel, say for example the pixel where the line begins in the bottom left of the image. Immediately the x-y co-ordinates of this pixel are added to x-y points list. Then ask the question, are any of my immediate neighbours active? Notice in this case that this pixel has two ‘active’ neighbours. In this case it is always best to move to a pixel that is up, down, left or right. If we moved to the diagonal pixel, the chain could be broken because it may then move to the left pixel. As each new pixel is found, its x-y co-ordinate is added to a list. See the gif below for what I mean:
This is an example of why non-diagonal pixels should be give priority.
If priority is given to the non-diagonal pixels, things work quite nicely. There is an added condition that if a pixel has already been found, don’t move to that pixel. Here is an example of these simple rules in action:
Here is a simulation of what it would look like plotting an image after the points have been re-arranged in a vector type format:
It’s not working perfectly yet, I’m not sure why it traces the first part twice. This is just a rough idea at the moment so the kinks will get worked out later.
Here is the python script:
import numpy as np import cv2 import matplotlib.pyplot as plt import time import math x_pnts = [] y_pnts = [] img = cv2.imread('test4.png') height, width, depth = img.shape print 'height = ',height,' ','width = ',width #cv2.imshow('image',img) i = 0 point = np.array([]) print img[0,0] line_pix = img[...,...,0] <170 print line_pix[0,0] point = np.where(line_pix == 1) y_pnts = point[0] x_pnts = point[1] xy_pnts = np.ndarray((len(x_pnts),2),np.int32) for i in range(len(x_pnts)): xy_pnts[i,0] = x_pnts[i] xy_pnts[i,1] = y_pnts[i] bottom = 0 bottom_left = 0 bottom_right = 0 top_left = 0 top_right = 0 top = 0 right = 0 left = 0 cpix = (0,0) x_vector = [] y_vector = [] line_points = [x_pnts[0],y_pnts[0]] print len(x_pnts) def rastor_to_vector(): cpix = [x_pnts[0],y_pnts[0]] print 'cpix = ',cpix bottom = 0 bottom_left = 0 bottom_right = 0 top_left = 0 top_right = 0 top = 0 right = 0 left = 0 p_skip = 0 for i in range(len(x_pnts)): print 'cpix = ',cpix[0],cpix[1] #print x,y loop = 1 top_skip = 0 bottom_skip = 0 left_skip = 0 right_skip = 0 tl_skip = 0 tr_skip = 0 bl_skip = 0 br_skip = 0 g = 0 while (loop == 1): if (line_pix[cpix[1]+1, cpix[0]] == 1) and top_skip == 0: ## pixel above cpix = [cpix[0],cpix[1]+1] if (already_found(cpix, x_vector, y_vector) == 0): x_vector.append(cpix[0]) y_vector.append(cpix[1]) else: top_skip = 1 print 'already found-above' continue print 'up' elif (line_pix[cpix[1]-1, cpix[0]] == 1) and bottom_skip == 0: ## bottom cpix = [cpix[0], cpix[1]-1] if (already_found(cpix, x_vector, y_vector) == 0): x_vector.append(cpix[0]) y_vector.append(cpix[1]) else: print 'already found-down' bottom_skip = 1 continue print 'down' elif (line_pix[ cpix[1], cpix[0] - 1] == 1) and left_skip == 0: #left cpix = [cpix[0] - 1, cpix[1]] if (already_found(cpix, x_vector, y_vector) == 0): x_vector.append(cpix[0]) y_vector.append(cpix[1]) else: left_skip = 1 print 'already found left' continue print 'left' elif (line_pix[cpix[1], cpix[0] + 1 ] == 1) and right_skip == 0: #right cpix = [cpix[0] + 1, cpix[1]] if (already_found(cpix, x_vector, y_vector) == 0): x_vector.append(cpix[0]) y_vector.append(cpix[1]) else: print 'already found-right' right_skip = 1 continue print 'right' elif (line_pix[cpix[1]+1, cpix[0] -1] == 1) and tl_skip== 0: ##top left cpix = [cpix[0] -1, cpix[1]+1] if (already_found(cpix, x_vector, y_vector) == 0): x_vector.append(cpix[0]) y_vector.append(cpix[1]) else: print 'already found-tl' tl_skip = 1 continue print 'top left' elif (line_pix[cpix[1] - 1, cpix[0] - 1 ] == 1) and bl_skip == 0: #bottom left cpix = [cpix[0] - 1, cpix[1] - 1] if (already_found(cpix, x_vector, y_vector) == 0): x_vector.append(cpix[0]) y_vector.append(cpix[1]) else: print 'already found-bl' bl_skip = 1 continue print 'bottom left' elif (line_pix[cpix[1]-1, cpix[0] + 1] == 1) and br_skip == 0: #bottom right cpix = [cpix[0] + 1,cpix[1] - 1] if (already_found(cpix, x_vector, y_vector) == 0): x_vector.append(cpix[0]) y_vector.append(cpix[1]) else: print 'already found-br' br_skip = 1 continue print 'bottom right' elif (line_pix[cpix[1]+1, cpix[0] + 1 ] == 1) and tr_skip == 0: ##top right cpix = [cpix[0] + 1, cpix[1]+1] if (already_found(cpix, x_vector, y_vector) == 0): x_vector.append(cpix[0]) y_vector.append(cpix[1]) else: print 'already found-tr' tr_skip = 1 continue print 'top right' else: jump_to_nearest_free_pixel(cpix,x_pnts,y_pnts) print 'jumped' print 'found ' + str(len(x_vector)) + ' out of '+ str(len(x_pnts)) print cpix loop = 0 def already_found(cpix, x_vector, y_vector): for i in range(len(x_vector)): if (cpix[0] == x_vector[i]) and (cpix[1] == y_vector[i]): return 1 else: return 0 def dist(x1,y1,x2,y2): d = math.sqrt( (x2-x1)**2 + (y2-y1)**2 ) #print d return d def jump_to_nearest_free_pixel(cpix, x_pnts, y_pnts): old_dist = 100000 for i in range(len(x_pnts)): new_dist = dist(cpix[0],cpix[1],x_pnts[i],y_pnts[i]) if ((new_dist <= old_dist) and already_found((x_pnts[i],y_pnts[i]), x_vector, y_vector) == 0) : closest_pixel = (x_pnts[i],y_pnts[i]) old_dist = new_dist cpix[0] = closest_pixel[0] cpix[1] = closest_pixel[1] rastor_to_vector() plt.axis([0, width, 0, height]) plt.plot(x_vector,y_vector,'r') plt.show() cv2.waitKey(0)
Thanks to Ted Burke and Damon Berry for giving me useful advice on how to go about doing this.
