Generating Knitting Patterns from a Sketch: a CSP Approach
Inhaltsverzeichnis
Reference
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
DOI
http://dl.acm.org/citation.cfm?doid=2487276.2487284
Abstract
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
Bibtex
@inproceedings{Kryven:2013:GKP:2487276.2487284,
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 = {http://doi.acm.org/10.1145/2487276.2487284 http://de.evo-art.org/index.php?title=Generating_Knitting_Patterns_from_a_Sketch:_a_CSP_Approach },
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 http://dl.acm.org/citation.cfm?id=2330149&CFID=588525319&CFTOKEN=29804931
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 http://dx.doi.org/10.1007/978-3-642-01129-0_53
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 http://dx.doi.org/10.1016/j.cag.2012.12.007
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 http://dx.doi.org/10.2312/EGWR/EGSR04/033-044
Griswold, R. E. 2007. Mathematical and Computational Topics in Weaving. http://www.cs.arizona.edu/patterns/weaving/webdocs/mo.pdf (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 http://dx.doi.org/10.1023/A:1006350622830
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 http://doi.acm.org/10.1145/2185520.2185545
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 http://doi.acm.org/10.1145/1073204.1073253
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 http://doi.acm.org/10.1145/508530.508536
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 http://doi.acm.org/10.1145/641480.641518
Yuki Mori , Takeo Igarashi, Plushie: an interactive design system for plush toys, ACM Transactions on Graphics (TOG), v.26 n.3, July 2007 http://doi.acm.org/10.1145/1276377.1276433
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 http://doi.acm.org/10.1145/192161.192185
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 http://doi.acm.org/10.1145/258734.258890
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 http://dx.doi.org/10.2312/COMPAESTH/COMPAESTH10/025-032
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 http://doi.acm.org/10.1145/2185520.2185533
Links
Full Text
[extern file]
