TEACH SEEPICS Aaron Sloman August 2009 Some examples of the use of LIB * SEEPICTURE To make the facilities here available do uses turtle CONTENTS - (Use g to access required sections) -- Introduction -- An example of a 'dotty' picture -- -- Structures perceivable in the picture -- -- Lines can form junctions of several types -- From 2-D interpretations to 3-D interpretations -- 2.5D interpretations -- Exercise -- Related teach files -- Using turtle drawings -- Using the seepicture library to find lines in turtle drawings -- Using findlines() and findjuncs() -- Running findjuncs(); -- Running paintpicture(); -- Introduction This file shows how some of the libraries in Pop-11 support a slightly quirky but useful introduction to computer vision that could be understood by relatively young learners whose understanding of the complexity of processes of visual perception would be enhanced. -- An example of a 'dotty' picture Before reading on you should consider what you see here, and how you could describe it. ***** * ** ***** * ********* * * * * ** ** * **** * * * * * ** ** * * * * ***** * * ********* * * * * * * * * * * * * * *********** ******** * * * * * ** * * * * * * * * * * * ******* * * * * * * * * ** * * * * ***** * * * * * * * * * * * * ** ** * ** ******* *********** -- -- Structures perceivable in the picture At one level all you see is a collection of asterisks forming a 2-D structure. At another level of description you can see horizontal, vertical and diagonal continuous lines represented by the asterisks, although the lines are not there in the picture. -- -- Lines can form junctions of several types Those lines can also be seen as meeting at *junctions* of various sorts including these types of junction (not all in the above picture) ELL junctions where two lines meet at a common end, like these two: * * * * * * ***** * * * TEE junctions where one line ends on the interior of another: * * * * * ** ******* * * * * * ARROW junctions where three lines meet forming a point: * * * * * * ** * ***** ****** * * * Y-junctions, where three lines meet in a point without forming an arrow: * * * * * * ***** ***** * * * * * * And K-junctions where four lines meet at a point, two of them collinear. Another way to see a K-junk is as a line that has the corner of an L junction on it, like these: ************ * * * * * * * * * * * * ** ** * * * ******* * * ** * * * * * * * -- From 2-D interpretations to 3-D interpretations Besides these 2-D structures, if you look at the first picture above, or the picture below you will probably naturally interpret it not just as a collection of 2-D configurations of asterisks or lines, but as representing a 3-D structure. Not everyone will agree on the precise shape of the 3-D structure, but it is likely that many will see it as one rectangular block partly occuding another larger one, which is on the far side of it. ********* * ** * * * * * * ********* * * * * * * * ******* * * * ** * * * * * * * ******* * * * * * * ** * * ***** * * * * * * * ** ******* -- 2.5D interpretations ;;; It is also prossible to produce pictures that look as if they have flat ;;; sheets some of which partially cover others. ;;; Get a library for drawing outline figures. uses outlines ;;; this provides the procedure rect, which can be given a point in the ;;; form of a list of two numbers and a width and height as integers. ;;; make a new picture newpicture(30,20); rect([9 3], 15, 10); display(); 0 9 8 7 6 5 4 3 **************** 2 * * 1 * * 0 * * 9 * * 8 * * 7 * * 6 * * 5 * * 4 * * 3 T*************** 2 1 123456789012345678901234567890 Position = ( 9.0, 3.0 ), Heading = 0 (E) ;;; We can draw another rectangle rect([3 7], 20, 12); ;;; Before looking at the output of the display() procedure can you work out ;;; how many lines it will find, of each orientation, and how many junctions ;;; it will find? ;;; You will need to know that when rect(place, width, height) draws a ;;; rectangle if it crosses an existing line then it switches between ;;; drawing and not drawing as it moves. display(); 0 9 ********************* 8 * * 7 * * 6 * * 5 * * 4 * * 3 * **************** 2 * * * 1 * * * 0 * * * 9 * * * 8 * * * 7 T****** * 6 * * 5 * * 4 * * 3 **************** 2 1 123456789012345678901234567890 Position = ( 3.0, 7.0 ), Heading = 0 (E) ;;; we can empty the database, and run seepicture, which will ;;; run findlines, findjuncs then paintpicture [] -> database; seepicture(); display(); 0 9 l-------------------l 8 | | 7 | | 6 | | 5 | | 4 | | 3 | l-------------tl 2 | | | 1 | | | 0 | | | 9 | | | 8 | | | 7 l-----t | 6 | | 5 | | 4 | | 3 l--------------l 2 1 123456789012345678901234567890 Position = ( 0.0, 0.0 ), Heading = 0 (E) database ==> ** [[junc ell [23 19] [3 19] [23 13]] [junc ell [24 13] [23 13] [24 3]] [junc ell [9 13] [9 7] [23 13]] [junc ell [3 19] [3 7] [23 19]] [junc ell [3 7] [9 7] [3 19]] [junc tee [9 7] [9 13] [3 7] [9 3]] [junc ell [9 3] [24 3] [9 7]] [junc tee [23 13] [24 13] [23 19] [9 13]] [junc ell [24 3] [24 13] [9 3]] [line vrt [24 3] [24 13]] [line vrt [23 13] [23 19]] [line vrt [9 3] [9 7]] [line vrt [9 7] [9 13]] [line vrt [3 7] [3 19]] [line hrz [3 19] [23 19]] [line hrz [9 13] [23 13]] [line hrz [23 13] [24 13]] [line hrz [3 7] [9 7]] [line hrz [9 3] [24 3]]] ;;; Try again with different lines and rectangles in the picture. -- Exercise Can you find a way to make the program learn names for types of shape, by abstracting away from the actual positions of the lines and corners and merely considering the patterns they make? For this you will have to find a way of taking the database produced by of running findlines(), and findjuncs(), and combining the information to form a shape specification. Can you teach the program about different shapes and then ask it to draw shapes of the kind that it has previously analysed, and for which it has learnt names? E.g. Draw a triangle and then a square to the right of it. draw a square partly overlapping a triangle. This could be a hard project, suitable for a group of students working together. You may find LIB REGIONS useful. See TEACH REGIONS -- Related teach files The TEACH seepicture file and some of the others associated with it including TEACH PICTURES TEACH REGIONS TEACH LABELLING TEACH WALTZ All introduce simple versions of important AI ideas concerned with the interpretation of images. No claim is made here that the techniques presented are adequate to the 'real' problems of machine vision involving analysis and interpretation of images of static and changing natural scenes. -- Using turtle drawings ---------------------------------------------- The drawings that are used as input to the programs can be produced using the earliest 'turtle geometry' package added to pop-11, which 'paints' pictures in an array of characters. The idea of Logo turtle graphics goes back to the late 1960s and was used by Papert, Bobrow, Feurzig, Minsky and others to develop a way of teaching programming through commands to a physical or virtual "turtle", that could move around on a surface either with its "pen" in the "down" position so that it leaves a trail of ink, or in the "up" position so that it moves without leaving a trail. For more on this kind of language and its uses see http://en.wikipedia.org/wiki/Turtle_graphics http://en.wikipedia.org/wiki/Logo_(programming_language) http://web.media.mit.edu/~minsky/papers/Logoworks.html Pop-11 has a package like that as part of the 2-D graphical facilities, namely LIB * RC_GRAPHIC, described in TEACH * RC_GRAPHIC (though instead of having pendown and penup commands, it provides rc_draw and rc_jump commands, so that it is clear from the move command itself whether it is or is not leaving a trail). That package draws on the screen of a graphical terminal, like many implementations of Logo turtle graphics. Some illustrations of its use are here http://www.cs.bham.ac.uk/research/projects/poplog/figs/rclib/rc_graphic.html However, long before we had graphical terminals that could support such things, the Pop-11 teaching libraries included an unusual implementation of the idea of Logo turtle graphics, in which the drawing commands, instead of causing things to appear on a screen, caused a virtual turtle to crawl around a 2-D array, leaving printable characters as its trail. The array could be printed out like any other text, but it could also be inspected by a program. This meant that the turtle could be used to draw lines to make a picture, and the programs in the SEEPICTURE library could then inspect that picture, look for lines, find where they meet to form junctions, and find regions bounded by lines. This file merely gives a taste of what can be done learners playing with these packages. -- Using the seepicture library to find lines in turtle drawings First draw a simple "L" using the turtle. uses turtle ;;; Make a new 8x8 picture with nothing in it. newpicture(8,8); ;;; If displayed it is seen to be empty. ;;; The display() command prints out coordinates but shows nothing in ;;; the picture display(); 8 7 6 5 4 3 2 1T 12345678 Position = (1, 1), Heading = 0 (E) ;;; Now make a bigger picture and draw two lines in it newpicture(20,20); jumpto(2,18); ;;; make the turtle face down the page and draw -90 -> heading; draw(15); ;;; make the turtle face right and draw turn(90); draw(15); ;;; print out the picture display(); 0 9 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 * 0 * 9 * 8 * 7 * 6 * 5 * 4 * 3 ***************T 2 1 12345678901234567890 Position = (17.0, 3.0), Heading = 0 (E) The T shows were the turtle is. Work out where the coordinates of the lines are and how you would describe the junction they form. -- Using findlines() and findjuncs() ;;; make the library available uses seepicture ;;; empty the database as a precaution [] -> database; ;;; search for lines, and print out the database, where the information ;;; about lines is recorded. findlines(); database ==> ** [[line vrt [2 3] [2 18]] [line hrz [2 3] [17 3]]] ;;; Two lines have been found, one vertical described as 'vrt' and ;;; one horizontal described as 'hrz' Let's draw another line going up and left from where the turtle is. It will first have to turn 135 degrees: heading => ** 0 turn(135); heading => ** 135 ;;; draw a line of length 12, and display the picture draw(12); display(); 0 9 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 * T 0 * * 9 * * 8 * * 7 * * 6 * * 5 * * 4 * * 3 **************** 2 1 12345678901234567890 Position = ( 8.5, 11.5 ), Heading = 135 (NW) ;;; Find all the lines now: findlines(); database ==> ** [[line lft [17 3] [9 11]] [line vrt [2 3] [2 18]] [line hrz [2 3] [17 3]]] ;;; In addition to the vertical (VRT) and horizontal (HRZ) lines that ;;; were there previously there is now also a line that slopes up to ;;; the left (LFT) -- Running findjuncs(); ;;; the findjuncs procedure will not look at the picture. It merely ;;; uses the information about lines in the database, and searches ;;; for points common to two or more lines and then works out the ;;; type of junction at easch such point. findjuncs(); database ==> ** [[junc end [2 18] [2 3]] [junc end [9 11] [17 3]] [junc ell [2 3] [17 3] [2 18]] [junc ell [17 3] [9 11] [2 3]] [line lft [17 3] [9 11]] [line vrt [2 3] [2 18]] [line hrz [2 3] [17 3]]] ;;; In addition to the three lines that were there before it has now ;;; found four "junctions", where an end counts as a junction involving ;;; only one line. -- Running paintpicture(); ;;; We can can run the paintpicture procedure which finds the lines and ;;; junctions and then uses paintpicture() to repaint the picture to ;;; show the orientations of the lines found, by using suitable ;;; characters for points on the lines, and uses letters to indicate the ;;; labels of the junctions found. paintpicture(); ;;; show how the picture has been painted to show the interpretation. ;;; The turtle has been moved to the bottom left, and is no longer ;;; shown. display(); 12345678901234567890 Position = ( 0.0, 0.0 ), Heading = 135 (NW) 0 9 8 e 7 | 6 | 5 | 4 | 3 | 2 | 1 | e 0 | \ 9 | \ 8 | \ 7 | \ 6 | \ 5 | \ 4 | \ 3 l--------------l 2 1 12345678901234567890 Position = ( 0.0, 0.0 ), Heading = 135 (NW) -- SEE ALSO TEACH TURTLE TEACH PICTURES TEACH SEEPICTURE TEACH REGIONS TEACH PICDEM --- $usepop/pop/packages/teaching/teach/seepics --- Copyright University of Birmingham 2009. All rights reserved.