The digitisation of the humble daisy granny square was one of the challenges that Prof Lynette van Zijl from Stellenbosch University's Computer Science division put to her Honours class at the beginning of this year.
At first glance, it sounds simple: “Basically, we want to digitise a pattern in order to extract meaning from it," she explains.
But while the techniques to do so for one dimensional linear diagrams are fairly well understood, it is another kettle of fish when dealing with a multi-layered non-linear diagram such as the diagram for a crochet pattern.
Adri Lochner, who graduated with a BScHons-degree cum laude in Computer Science this week, decided to tackle the granny square problem as her BScHons project for the year. Not because she can crochet, but rather to learn more about machine learning and optical recognition.
She says the biggest challenge was to think of different ways by which one could recognise the diagrams: “Then there were several sub-problems which had to be solved in order to achieve better results. Each of these sub-problems were like a project on its own!"
Lochner used a supervised learning algorithm (based on Support Vector Machines) and “trained" it to recognise and correctly classify each of the individual symbols used in crochet patterns. For example, the symbol for a slip stitch is a black dot and for a chain stitch it is an oval. She used a dataset of 57 600 images and split it up into a training, a validation and a test set.
But how do you train an algorithm to recognise the combination of three double crochet stitches? In her solution, she draws a “bounding box" around each connected component. The three double crochet stitches for a daisy petal thus become a single component.
But it was the simple chain stitch that caused the biggest headache. The algorithm could not separate individual chain stitches from each other. She then removed the largest outer contour of the image, thereby separating the chain stitches from each other:
In the end, the recognition method she used achieved an accuracy level of above 70%.
Prof Van Zijl says molecule and circuit diagrams present the same problem: “We want to be able, one day, to convert complicated images to text and vice versa. This would open up many new possibilities, such as improved searching through images, improved classification of images, and improved access to diagrammatic information for the blind.
However, at the moment, the general recognition of a complex diagram such as the humble daisy square still has a long way to go, she concludes.
Lochner, a former learner from Stellenbosch High School, is now on her way to Pretoria where she will start working as a software engineer. In the near future she wants to continue with postgraduate research and perhaps continue in the field of diagram recognition.
Prof Lynette van Zijl
T: 021 808 4232