Generating Knitting Patterns from a Sketch: a CSP Approach

Aus de_evolutionary_art_org
Wechseln zu: Navigation, Suche


Marta Kryven, Elodie Fourquet: Generating Knitting Patterns from a Sketch: a CSP Approach. In: Donald H. House, Cindy Grimm (Eds.): Workshop on Computational Aesthetics, 2013. 53-62



Graphic patterns in knitting are composed of relatively large pixels and create a picture when seen from a distance, while on close viewing the image falls apart into its constituent stitches. Such patterns are constrained in use of colors due to the nature of the medium and in spacing between pixels as a durability concern and are a challenge to create. This paper shows how to convert an arbitrary line-drawing or photograph to a constraint-compliant Fair-Isle knitting pattern for a programmable knitting machine or a manual knitter by formulating it as a Constraint Satisfaction Problem (CSP). First we generate a constraint-inconsistent starting pixel assignment. Then we produce a perceptually similar constraint compliant solution, by minimizing and randomly distributing pixel flips to preserve gestalt features of the original design. We evaluate ways of generating a starting assignment using thresholding and dithering and of solving the problem using pseudo-random texturing and search: Random Walk, GSAT and Min-Conflict. Two hybrid solutions that achieve an improved design-dependent result are described. To test the algorithms an interactive knitting pattern generator was implemented.

Extended Abstract


author = {Kryven, Marta and Fourquet, Elodie},
title = {Generating Knitting Patterns from a Sketch: A CSP Approach},
booktitle = {Proceedings of the Symposium on Computational Aesthetics},
series = {CAE '13},
year = {2013},
isbn = {978-1-4503-2203-4},
location = {Anaheim, California},
pages = {53--61},
numpages = {9},
url = { },
doi = {10.1145/2487276.2487284},
acmid = {2487284},
publisher = {ACM},
address = {New York, NY, USA},
keywords = {constraint solving, knitting, non-photorealistic, nontraditional media, sketch-based rendering},

Used References

Arnheim, R. 1974. Art and Visual Perception: A Psychology of the Creative Eye, 2nd ed. University of California Press.

Bayer, B. 1973. An optimal method for two-level rendition of continuous-tone pictures. In Proceedings of the IEEE International Conference on Communications, vol. 1, 11--15.

Simon Colton , Blanca Pérez Ferrer, No photos harmed/growing paths from seed: an exhibition, Proceedings of the Symposium on Non-Photorealistic Animation and Rendering, June 04-06, 2012, Annecy, France

Simon Colton , Pedro Torres, Evolving Approximate Image Filters, Proceedings of the EvoWorkshops 2009 on Applications of Evolutionary Computing: EvoCOMNET, EvoENVIRONMENT, EvoFIN, EvoGAMES, EvoHOT, EvoIASP, EvoINTERACTION, EvoMUSART, EvoNUM, EvoSTOC, EvoTRANSLOG, April 15-17, 2009, Tübingen, Germany

Colton, S. 2008. Experiments in constraint-based automated scene generation. In Proceedings of the 5th international workshop on Computational Creativity.

Cutting, J. E. 2002. Representing motion in a static image: constraints and parallels in art, science, and popular culture. Perception 31, 10, 1165--1193.

Eschbach, R., and Knox, K. T. 1991. Error-diffusion algorithm with edge enhancement. J. Opt. Soc. Am. A 8, 12, 1844--1850.

Floyd, R. W., and Steinberg, L. 1976. An Adaptive Algorithm for Spatial Greyscale. Proceedings of the Society for Information Display 17, 2, 75--77.

Timothy Gerstner , Doug Decarlo , Marc Alexa , Adam Finkelstein , Yotam Gingold , Andrew Nealen, Special Section on Expressive Graphics: Pixelated image abstraction with integrated user constraints, Computers and Graphics, v.37 n.5, p.333-347, August, 2013

Stéphane Grabli , Emmanuel Turquin , Frédo Durand , François X. Sillion, Programmable style for NPR line drawing, Proceedings of the Fifteenth Eurographics conference on Rendering Techniques, June 21-23, 2004, Norrköping, Sweden

Griswold, R. E. 2007. Mathematical and Computational Topics in Weaving. (accessed May 2013).

Holger H. Hoos , Thomas Stützle, Local Search Algorithms for SAT: An Empirical Evaluation, Journal of Automated Reasoning, v.24 n.4, p.421-481, May 2000

Igarashi, Y., Igarashi, T., and Suzuki, H. 2008. Knitting a 3D model. Computer Graphics Forum, 27, 7, 1737--1743.

Yuki Igarashi , Takeo Igarashi , Jun Mitani, Beady: interactive beadwork design and construction, ACM Transactions on Graphics (TOG), v.31 n.4, p.1-9, July 2012

Takashi Ijiri , Shigeru Owada , Makoto Okabe , Takeo Igarashi, Floral diagrams and inflorescences: interactive flower modeling using botanical structural constraints, ACM Transactions on Graphics (TOG), v.24 n.3, July 2005

Pierre-Marc Jodoin , Emric Epstein , Martin Granger-Piché , Victor Ostromoukhov, Hatching by example: a statistical approach, Proceedings of the 2nd international symposium on Non-photorealistic animation and rendering, June 03-05, 2002, Annecy, France

Lagae, A., Lefebvre, S., Cook, R., DeRose, T., Drettakis, G., Ebert, D., Lewis, J., Perlin, K., and Zwicker, M. 2010. A Survey of Procedural Noise Functions. Computer Graphics Forum, 29, 8, 2579--2600.

Sylvain Lefebvre , Fabrice Neyret, Pattern based procedural textures, Proceedings of the 2003 symposium on Interactive 3D graphics, April 27-30, 2003, Monterey, California

Yuki Mori , Takeo Igarashi, Plushie: an interactive design system for plush toys, ACM Transactions on Graphics (TOG), v.26 n.3, July 2007

Ostromoukhov, V. 2013. Non-photorealistic Shading and Hatching. In Image and Video-Based Artistic Stylisation, vol. 42 of Computational Imaging and Vision. Springer London.

P. Prusinkiewicz , Aristid Lindenmayer, The algorithmic beauty of plants, Springer-Verlag New York, Inc., New York, NY, 1990

Radcliffe, M. 2008. The Essential Guide to Color Knitting Techniques. Storey Publishing, LLC.

Stuart Russell , Peter Norvig, Artificial Intelligence: A Modern Approach, Prentice Hall Press, Upper Saddle River, NJ, 2009

Michael P. Salisbury , Sean E. Anderson , Ronen Barzel , David H. Salesin, Interactive pen-and-ink illustration, Proceedings of the 21st annual conference on Computer graphics and interactive techniques, p.101-108, July 1994

Michael P. Salisbury , Michael T. Wong , John F. Hughes , David H. Salesin, Orientable textures for image-based pen-and-ink illustration, Proceedings of the 24th annual conference on Computer graphics and interactive techniques, p.401-406, August 1997

Salomone, A., 2013. Personal communication, May 18, 2013.

Mayank Singh , Scott Schaefer, Suggestive hatching, Proceedings of the Sixth international conference on Computational Aesthetics in Graphics, Visualization and Imaging, June 14-15, 2010, London, United Kingdom

Cem Yuksel , Jonathan M. Kaldor , Doug L. James , Steve Marschner, Stitch meshes for modeling knitted clothing with yarn-level detail, ACM Transactions on Graphics (TOG), v.31 n.4, p.1-12, July 2012


Full Text

[extern file]

intern file

Sonstige Links