knit-algorithm

Introduction
In this section we will present the algorithm that produce the knitted image.

We will first remember the goal of the algorithm. This algorithm assumes a virtual model. These virtual model comes from a physical model. So we will describe the physical model and the virtual model. After that we will look at the pseudo code and the high-level complexity of the algorithm.

Goal of the algorithm
Given an image, the goal is to represent at best the image in the constraint of the model. For the moment, we restrict us to grayscale images.

figure 1: physical model                                    figure 2: virtual model

Physical Model
Imagine that you have multiple hooks, called pins, nail on a white board and a long transparent gray string. One end of the string is bound to a pin. Now, the only move that you are allowed to do is to go from one pin to another pin. Doing this you draw straight lines (see figure 1).

Virtual Model
The virtual model is based on a digital image.  A pin is a single pixel and we draw the string from one pin to the other using digital differential analyzer graphic algorithm (DDA).

We do at least three assumptions with this virtual model. First, we assume that the lines are perfectly straight. Secondly, we assume that the string is more or less of the size of one pixel. Thirdly, we assume that when two strings intersect, the intersection becomes darker.      

Overview of the algorithm
This algorithm is based on a heuristic. At each step we try to know the best next pin based on a score function. (There is multiple ways to evaluate the score and we have a section dedicate to it, but globally we try to reduce the difference between the result image and the original image.) Then, we update the result image, drawing the line we just added.

Algorithm
currentPin = 0
nextPin = -1
While  stepNumber < maxSteps  and stop != true :
     nextPin = findNextBestPin(currentPin)
     decreaseLightness(resultImage,  setOfPixelGivenByTheLineBetween(currentPin, p2), decreaseValue)
     currentPin = nextPin

findnextBestPin(currentPin):
    tempNextPin = 0;
    tempScore =  0;
    bestScore = -infinty;
    For all pin p2:
           tempScore  =   lineScore( setOfPixelGivenByTheLineBetween(currentPin, p2))
           If tempScore > bestScore:
                     bestScore = tempScore
                     tempNextPin = p2
    return tempNextPin

decreaseLightness( image,  setOfPixels, decreaseValue )
     For each pixel P in setOfPixels:
           decrease the lightness on the image by the decreaseValue

Complexity of the algorithm 
O( maxStepsNumber * pinsNumber * numberOfPixelInALine )
If we use the DDA algorithm to draw line, The numberOfPicelInALine is at most the width in pixel of the image. We have:
O(maxStepsNumber * pinsNumber * imageWidth )

Exemple:
In standard case we use: maxStepsNumber = 30000, pinsNumber = 240, imageWidth = 820
We have, 5 904 000 000 high-level operations. These take around 30 minutes on my computer (i5-3320M CPU @ 2.60GHz)