Monday, May 28, 2018

Polygonal knitting!

Hi folks, this is a quick little computational knitting thing.  Years ago, I looked into how you could work out knitting pictures into circular knitting - this is a little tricky because you first need to convert your picture into radial coordinates, but you would also like to account for the knitting not being perfectly circular (because there's pooling with the increases).  The solution I came up with was to purposely knit a polygon, then map these into 2D cartesian coordinates.  This, along with some radial curves led to this:

This was quite cumbersome, took a lot of set-up, and particularly required me to express the heart shape as a mathematical equation - so it's pretty hard to generalise.  What I've aimed to do this time is to come up with a system which makes all of this automatic, using the existing declarative knitting framework I've got set up.
So, how does it work? You provide an image, and a target number of colours.  The system then picks out the dominant colours and flattens the image to use just those (this is important because I want to be able to do this with photos as well as block graphics).  Here's the sample image I made to test this with:
Next, you specify the number of sides you would like your polygon to have.  The system uses this to work out a pattern of increases.  The trick here is that you want an average of ~4 increases per row, and will have increases at both ends of each side.  Once that's done, we can take the location of each stitch in that pattern and work out it's location in cartesian coordinates - this isn't quite radial, instead you need to find the side it's on and interpolate between the two vertices.  This can then be output as a spreadsheet:
Of course, it's quite hard to know if that's right!  It looks plausible, but it's hard to be confident without doing a test knit.  So using this pattern, I made these two little doilies!  The shapes aren't perfect, but I think a lot of that is because the stranding has altered the tension slightly.  I'm definitely impressed with how close it came, and it's certainly better than I could have done by hand!

Next step with this will be to write up another little modules for Declarative Knitting Tools which provides a web front end to kick it all off!

Happy knitting,

Declarative knitting in the cloud!

I've talked a bit about getting this up and running, and now the website is live:

The idea will be that it's a place to put little knitting tools for generating different kinds of knitting patterns.  Each tool will be quite small, and probably quite niche, but the idea is to build up into a collection of curiosities.  For now it's just got one, which generates shadow knitting patterns, but over time I'll be looking to add more - ideally adding a new tool should be quite quick - particularly, the majority of the effort should go into solving the actual computational problem, rather than building the website.

For now it's hosted on an EC2 instance on AWS - I'm keen to transfer it over into a serverless arrangement, but this may be a little difficult since it has a dependency on an installed copy of OpenCV for image processing.  I don't believe this would be possible in Lambda, but it's possible there's an approach with containers and ECS which would be a good fit.

Sunday, May 13, 2018

Declarative knitting

Hi folks!
There's a project I've made a start at a few times, but not entirely followed through, to make a kind of programmable knitting pattern generation toolkit.  The aim of this would be to make a kind of API for specifying knitting patterns programmatically - this would allow patterns to be generated based on data and computation, where this would be complex or laborious to do by hand, and to make the infrastructure behind it shared and re-usable.
My motivation for this comes from a few different projects I've done in the past to make mathematical shapes - I found that usually the computation part was quite straightforward, but outputting this as something I could knit took up most of the effort.  For example, calculating surfaces of revolution, or mapping images into polar coordinates.  At the same time, I design a lot of toys, and find that the bulk of this, especially the shaping, uses a pretty small number of concepts, which can easily by layered on top of each other.
The big idea behind how I'd like this to work is for the patterns to be expressed in a "declarative" style - a designer should be able to express "work in stocking stitch, increase evenly along the edges, for 10 rows", and leave the program to work out which specific stitches needs to do what.  The system should then be able to generate a fully detailed pattern, and express it in common formats - as text, charts, or others.  And of course this should be extensible, so that it's easy to add in new "rules" which can be used, particularly as there are so many styles of knitting that it would be impossible to express them all beforehand.
Then my big aim with all of this is that it would become possible to create "rules" based on complex computation too.  I'm working on a few of these initially - one which creates shadow knitting patterns based on images, one which creates lace patterns using edge detection, and one which will makes lace patterns from cellular automata.  Of course, these are only examples, but my hope is that I'll be able to take quirky ideas like these and make them accessible as a website where knitters can automatically generate patterns of their own.

The code for all this will be open source, and is on github:
The web services I'm hoping to get deployed on AWS in the next few weeks.

I'm pretty excited about it all!

Data Structures

Hi folks, I haven't posted any new projects for a while, and I've got a few waiting!
What I'd like to write about today, is my set of data structures.  The big idea here is that concepts are easier to explain and understand when you boil them down to their essence, and make them as concrete as possible - it forces you to think about what you really mean by them.  And because of that, it also makes it easier to explain to other people - so these are designed to be educational toys.
At the same time, data structures are a key part of computer science.  Writing good algorithms usually comes down to how you structure the data they need to work on, and good algorithms allow us to solve problems cleanly, elegantly, and fast.  They're a key enabler for how computers have changed the world, and they will only become more important over time.

The idea of the pieces is that each structure has a starting point (the purple ring), a number of arrows (which act as references), and a number of brown cups.  The "data" is represented by the plastic balls, which can be put in, taken out and moved around.  These are removable, which shows that the structure doesn't depend on the data objects themself, it just organises them.
So, the structures I've made, and what they tell us: 

Linked list

One thing you definitely need to do with a set of data is look through it.  Linked lists are very good if you just want to look through all the objects you've got in order.  You start at the initial point, and follow the arrows to look through the items.  This is great, and very flexible, and makes it easy to add new items to the list.  What it's very bad at is if you want to find a specific object - then you might need to look through the whole list to find it.
So this is good if you're going to need to add and remove objects a lot, and if you mostly care about looking through them in order.


So next up we have an array!  This time you have a rigid structure, with references at fixed intervals along it.  This means you can still look through the objects in order easily, but if you want to go to a specific entry (say the fourth), you know how far to go down the rod to find it (four steps), so you can go to that location in one step, without having to go through each of the other entries.  The down side is that if you want to add new entries, you might need to do a lot of work moving other entries around, and of course the array is a fixed size so if it's too short you'll just have to make a new one (and if it's too long, it's just wasted space.
So this is good if you've got a set of things which won't change much, and you want to pick out specific entries.

 Binary tree

But we can do better!  Suppose our data items come with some kind of order - here I've ordered the balls by colour, red to purple.  If we want to find a specific one now, we can start at the top and at each step ask, is the current one our item?  If not, is it further towards red than ours?  If so, go left.  Or is it further towards purple?  In that case, go right.  Clearly that's more complicated, but you can see that here we've got 8 objects and can find any of them in at most 3 steps.
I wanted to get across too that balance is difficult for binary trees.  Not all the branches have the same length, and you can see the one on the left only has one branch - this points to the problem you have with adding and removing entries in a tree, that you might have to do some extra work rebalancing the tree, or you might accept some inefficiency if you let it get out of hand.

(One structure I'd like to make in future is a red-black tree, to tell the next step in this story.  They're a wonderful concept, and already beautifully graphic!)

Hash table

The last of my data structures for now is a hash table - the idea now is that if you have a kind of summary of your data object (a hash function, here I'm using the colour of the ball), you can arrange it so that to find it, you just need to follow the arrow of that particular colour, and again this can be done without needing to look through all the entries.  But then we have an awkward question of what we do if two data items have the same colour (hash collisions!) - to be able to store both we need to fit both into a "hash bucket".  I'd hope this could lead to an interesting discussion of why a good hash function is important, and how using this structure efficiently can need us to think a bit about the distribution of our data.

So those are my data structures!  There's a couple more of these I'd like to do, and I am planning to write up a pattern for these.  I'm also interested in other data structures people would like to see - I've had requests for a 2D array, and for a ring buffer, which are both interesting challenges, so I'll have to see if I can come up with a way to represent them!

Happy knitting,

Saturday, April 15, 2017

Permutation cardi

There's some maths behind this one!  The idea here is that there are exactly 6 ways to permute 3 elements, and each of the cable represents one of these two permutations.

We can describe a permutation by writing down what it does to the elements 1, 2 and 3 - so the two cables on the front represent (1, 3, 2) and (2, 1, 3).

The ones on the back are slightly more complex - these ones represent (2, 3, 1) and (3, 1, 2), but in these cases you've got one element moving two places, which distorts the knitting a little more, so I've broken these into two steps each containing a single crossing.

The arms are the bit I'm most excited about - of the 6 possible permutations, there are two pairs which are mirror images (the ones we've seen), but the remaining two are their own mirror images, so they don't have a relationship - (3, 2, 1) and the trivial permutation (1, 2, 3), which leaves everything unchanged.  These give this nice asymmetry between the two arms.  (3, 2, 1) again has elements moving two places, but it's hard to break this up into two steps, so here I've added an extra chain stitch to extend the cables.

Also exciting, the length of the repeats varies between permutations -  this gives their order in the symmetry group: (1, 3, 2), (2, 1, 3) and (3, 2, 1) all have order 2, (2, 3, 1) and (3, 1, 2) are order 3, and (1, 2, 3) is order 1, so the lengths of their repeats is different.  It's cool too that these all divide 6, so if you could fit in exactly 6 repeats, all the cables would end up in the right place after the same number of rows.

You could go much further with this too!  These permutations are at the heart of bell-ringing, although taken much further - for example here.  I love the intricate patterns this gives, but I would be wary of doing this with intarsia cables - as much as I love the colours, this ends up with the yarn getting crossed and needing to be constantly untangled.  Still, imagine that beautiful scarf with rainbows weaving together!

Saturday, March 4, 2017

Foxtato pattern!

Also!  I should have mentioned here, I finally got around to posting my Foxtato pattern - you can see this on Ravelry here, and it's available for free download: Ravelry download

Looking forward to seeing other people's projects, and to see them Doing The Thing!


Data structures

Hi folks!  (I aten't dead)
I was thinking recently that I haven't made nearly enough things to do with computer science, the same way I did for maths, and it's time to fix that!
So this project is to knit a family of data structures.  The idea will be to take a bunch of plastic toy balls to represent data items, and knit wrapper cups, connected together in different ways, to represent the data structure itself.
I've got ideas for a few of these:

  • Linked list - each node has a link to the next node.
  • Doubly linked list - each node has forward and backward links.
  • Binary tree - each node has two children.  I'd like this to be unbalanced, so some of the branches will be longer than others.
  • Red-black tree - another binary tree, but with coloured nodes (and this one will be balanced).
  • Hash table - a single parent has a bunch of child nodes, each with a coloured rim to represent the hash value of the objects to place in it.  Some of the child nodes will also form (small) linked lists, of the same colour.
  • Array - a string of references, only some of which have a node attached.  (It might be more accurate if he nodes are all there, but only some of them are filled, but I think this would make it harder to distinguish from the linked list.
I'm planning to write up a pattern for this one - it should be pretty simple since the only components are the cups and the references.  But I'd love to see people knitting some other structures too, and maybe they'll be useful as teaching aids at some point?  The one drawback is this means I need to knit a *lot* of identical cups, I think the whole project will need about 40 of them.

Happy knitting,