The Spaghetti Machine must check each pixel in a 2 by 2 window for every pixel in the image. For every edge found, it must be placed at the top or the bottom of the string. The time complexity of this operation depends entirely on the implementation of the string object. (Whether simple stack, or list with front and end pointers whatever.) Once the string is complete, it is output, requiring a further operation for every edge vexil. Note that edge vexils pointing in the same direction as the vexil on the end of the string do not grow the string, but merely extend the last vexil.
The parsing operation performs one operation per vexil on the string.
Smoothing North-East, North-West, South-East, South-West strings needs only operate on the first two and last two vertices.
Smoothing complex strings, (nne, ene, ese, sse, etc), requires one operation per vertex but each operation requires one operation per point in the line space simplex. Usually there are around four to six points in the simplex, although for a string with irrational slope, the number of points in the simplex can grow with every point on the string.
Outputting the smoothed string requires one operation per vertex on the smoothed string.
Thus adopting the philosophy of the "Fig-leaf" notation, the number of operations the Spaghetti Machine requires to scan the image is of the order of the number of pixels in the image. The number of operations required to smooth the vexils is of the order of the number of vexils output from the Spaghetti Machine.
Thus the algorithm is approximately of linear order. (I say approximate, in that no images that this program was designed to deal with have lines of any significant length with irrational slope. The number of classes within the image does not affect the speed of the algorithm.
However for ease of programming, and I wasn't expecting very long strings, I implemented the string object as a descendant of the stack type. Thus to scan to the bottom takes of the order of the number of elements on the stack. Thus making the time complexity of the current implementation quadratic. This has shown up as a problem when dealing with images of large rivers. However for small strings the simple stack is possibly faster. One of the virtues of the OOPS approach is that I can trivially change the string object to inherit from an array based stack or stack with front and back pointers.
| Previous | Next | Contents |