Using Clustering to Assist Understanding of Digital Ink in Low Attention Environments
Richard Anderson, Craig Prince, Beth Simon -- 2005
Summary:
The paper talks about sketch clustering in classroom and/or similar environments. Digital ink is used in these classrooms to aid in learning, by giving tablet PCs to the students and the teacher. The aim is to develop a system which will group students’ answer submissions and present them to the teacher in such a way that the cognitive load of the teacher is reduced while evaluating the submissions. The student submissions are mentioned as “slides” through the paper since the students draw their submissions on PowerPoint slides.
The authors use an image-based system for slide clustering. Hand drawn diagrams are rasterized using a grid. The pixels of the grid are painted if the strokes pass through them, generating a binary image. This binary image is then used to obtain a distance image. For each pixel in the distance image the number corresponds to the distance to the nearest pixel in the binary image. Using this distance metric, a K-means clustering algorithm is used to perform the clustering.
The authors carry a classroom experience study to learn about the advantages and disadvantages of diagram clustering. A group of about 60 students are presented 20 tablets which they share with each other. Four tasks (single graph drawing, dual graph drawing, ui layout design and tree drawing) with different number of submissions are evaluated. To test the accuracy of clustering, the authors first group the student slides manually.
The results of the clustering system are compared with manual clustering. However, for the time being, the authors use cleaned up versions of student slides. In other words, “doodles” and preliminary work toward solving the tasks are manually removed from the submitted diagrams. The algorithm makes some errors such as putting obviously different slides into the same clusters. Another error is putting the same group of submissions into different clusters (i.e. splitting). Also, visually minor but otherwise important features of some of the slides are either missed or interpreted wrong. A mean slide for each cluster is given, which represents the slide closest to the mean of that cluster. With different number of clusters, the mean slides of clusters seem to be stable (they do not change with increasing number of clusters). The authors argue that this is an important result, which shows that the mean slides are still representative of their group. It is also said that choosing an incorrect number of clusters is not detrimental; instead it is possible to adjust the number by trying different number of clusters since the algorithm is fast.
Another comparison is given for non-cleaned slides. The results are worse as expected, making more errors than cleaned up versions. It is inferred that removing non-pertinent ink is vital to successful clustering.
Discussion:
The authors accept that their algorithm is not novel, but their dealing with digital ink media in the classroom setting is new. As an initial study on this domain, their results are satisfactory. If the simple algorithm they use is also taken into account, it is clear that diagram clustering is a very open area for further study.
It is important to note that there is no well-defined metric to measure the success rate of clustering. The article gives some comparisons, but they use manually done groupings as ground-truth data. It is really difficult to do a distinction between minor and major features of a hand drawn diagram since it is strongly dependent on the domain. For example, in the graph drawing task, the slopes of the graph is important for the answer, but the algorithm usually disregards subtle differences between flat and sloppy graphs.
Another point is the cleaning-up task mentioned in the article. To overcome the negative effect of non-pertinent strokes on the grouping performance, the user may be forced to draw those strokes on a digital “scratch-paper” interface. Afterwards, only the digital “answer pad” can be used to draw the answer. However, this will restrict the users and impose additional cognitive loads. The article gives this problem as a planned work.
While an image based technique is used in this system, a stroke based technique might be employed in other studies. The article says that simple stroke based features have been tried, but an extensive study does not seem to be done. Today’s sketch recognition systems are very robust in symbol recognition, and they may be used for this task, probably giving much better clustering performance.
