TEACH REGIONS                              Aaron Sloman December 1979

=== FINDING REGIONS IN TURTLE PICTURES ===============================

--- How to use LIB REGIONS -------------------------------------------

The SEEPICTURE library program analyses turtle pictures to find lines
and junctions, which it then classifies, storing the junction
descriptions in the DATABASE. The lines are found by the procedure
FINDLINES, and the junctions by FINDJUNCS.

In order to interpret such pictures it is often necessary to find larger
structures than junctions where lines meet. In particular, you may need
to find regions, as Guzman did, and then decide which regions go
together to represent a single body.

The REGIONS program uses the junction information produced by FINDJUNCS
to follow circuits around the picture.

More precisely, it follows circuits around the database of junction
descriptions. In doing this, it builds up objects called CYCLES, which
represent a tour round a picture regions, without crossing any lines.

-- CYCLES -------------------------------------------------------------------
A circuit, or CYCLE, is defined as follows:


1. Given a junction J1 and a neighbouring junction J2, find a new junction J3
by going from J1 to J2, and then taking the rightmost path.

2. Now let J2 become J1, J3 become J2, and start again, to find a new J3.

3. Continue until the J3 you find is the initial J1.


The CYCLE is a list of all the points found.
Which part of this definition ensures that a cycle never crosses over itself?
Draw some pictures of straight lines, with no free ends, and see if you
can find all the cycles using this definition. How many cycles are there
in a square containing a single diagonal?

This procedure is followed by the procedure CYCLEFROM in LIB REGIONS.

CYCLEFROM takes two neighbouring junctions (J1 and J2 in the above rule), and
produces a list containing the complete cycle of points.
(For convenience the initial point is repeated at the end.)

By taking every junction in turn, and following every ray from that junction,
unless it has already been found as part of a cycle, we get all the cycles in
the picture.

For instance, in the square below, we can use A as J1 and B as J2, or D as J2.
We can ignore a new cycle if it is obtainable from an old one by moving
junctions from the back of the list to the front.

It follows that with a simple closed curve like a square there are two
cycles, one defined by the circuit ABCD and one by the circuit ADCB, for
example.

        A****B
        *    *
        *    *
        *    *
        *    *
        D****C

The above procedure finds both cycles, e.g. one by starting from A
towards B and one by starting from A towards C. No more are found.
For instance, the cycle starting from B towards A is the same as the
one starting from A towards D.
You can think of the clockwise cycle as defining the outer boundary of the
square region, and the counter-clockwise cycle as defining the inner
boundary of the background region. The region bounded is always on the
right as you go round the cycle.

Thinking of the region as on the right leads to the idea that you get different angles for
the corners of the regions, so that in the above example, the angles for the
cycle ABCD are [90 90 90 90], and for the other cycle [270 270 270 270].

We can use these angles to find whether the cycle is an inner boundary or an
outer boundary.
As you go round a corner, e.g. from A to D to C, you can distinguish
the TURN angle from the CORNER angle. The TURN angle is the change of heading,
the CORNER angle the angle between the two lines.

An outer boundary has the following property: as you go round it, if you add
up all your changes of heading (positive turns to the left, negative to the
right), then the total will always be 360 degrees. Why?

In the case of the square, the turn-angles are, for the inner bounding cycle,
ADCB, [90 90 90 90], and for the cycle ABCD, [-90 -90 -90 -90].
What would the lists of corner angles and turn angles be for the inner and
outer cycles of an equilateral triangle?

-- Dealing with free ends ---------------------------------------------------

When the picture contains no regions, only a single connected set
of lines, there is only one cycle, for instance the picture:

           A
           *
           *
           *
        B**C**D


has the cycle ACBCDC, or, equivalently, BCDCAC. Can you see why you end up
with essentially the same cycle whether you start with A and C, or C and A as
the initial pair of junctions? In othe words, why must every cycle traverse
each line segment in both directions?
We adopt the convention that if there is a free end, the cycle should
start from one of them. If we allowed turning right as well as turning left,
we'd get two cycles, the above one and also ACDCBC for instance.

-- The Format of a cycle description ----------------------------------------

How should a program describe the cycles it has found?
The convention adopted in the REGIONS package is as follows.
Each cycle found is represented by a seven-element database item of the form
    [CYCLE <number of sides> <INNER or OUTER>
        <SIMPLE or COMPLEX> <number of ENDs in cycle>
        <list of angles at corners>
        [<point1> <point2> <point3> ...<point1>]]

Where a cycle is 'complex' if it contains repeated points, otherwise 'simple'.
The cycle corresponding to the upside-down "T" above is complex, since
the point c is repeated.
If the cycle contains a free end, then the set of points in the seventh item
will start from one of them. Note that the list of points always starts and
ends with the same point.
This simplifies the task of writing programs which traverse the regions.

Examples of such cycle descriptions are given below.

-- Using the REGIONS program ------------------------------------------------

To make the REGIONS program available, type:
    : LIB REGIONS;

You can then use the turtle to draw a picture, and the SEEPICTURE library
program (or your own version) to produce a database of information
about the junctions in the picture. The information about lines is not
needed for finding cycles, so can be removed, by FLUSH([LINE ==]);
The regions program makes use of the fact that the FINDJUNCS program
represents each junction by a pattern of the form
    [JUNC <type> <juncpoint> <point1> <point2> <point3> ...]

where the points after the third element correspond to the points
you'd see if you turned around the junction point in a counter-clockwise
rotation.

Assuming the database contains such information, you can then type
    : REGIONS();

to produce a description of the cycles in the picture.
You may find it useful to trace some or all of the following procedures:
    CYCLEFROM CYCLETYPE NEXTRIGHT

-- Examples of cycle-finding ------------------------------------------------

    : draw(5); turn(90); draw(5); drawto(1,1);
    : display();

        6     *
        5    **
        4   * *
        3  *  *
        2 *   *
        1******
         1234567890

        : seepicture();
        :
        : database ==>

        ** [[junc ell [6 6] [1 1] [6 1]]
         [junc ell [6 1] [6 6] [1 1]]
         [junc ell [1 1] [6 1] [6 6]]
         [line rht [1 1] [6 6]]
         [line vrt [6 1] [6 6]]
         [line hrz [1 1] [6 1]]]
        : flush([line ==]);   ;;; not needed by cycle finder.
        :
        : regions();
        :
        : database ==>
        ** [[cycle 3 outer simple 0 [45 45 90] [[1 1] [6 6] [6 1] [1 1]]]
         [cycle 3 inner simple 0 [315 270 315] [[1 1] [6 1] [6 6] [1 1]]]
         [junc ell [1 1] [6 1] [6 6]]
         [junc ell [6 1] [6 6] [1 1]]
         [junc ell [6 6] [1 1] [6 1]]]


Both the cycles have 3 points and both are simple.
Both have 0 ends. They have different angles, though the same
points in a different order.
Notice that the angles given are CORNER angles not TURN angles.

Now a more complex figure:

        : repeat 4 times draw(4); turn(90) close;
        : drawto(5,5);
        : display();

        5*****
        4*  **
        3* * *
        2**  *
        1*****
         1234567890

        : seepicture();
        : flush([line ==]);

        : regions();

        : database ==>
        ** [[cycle 4 inner simple 0
                [270 270 270 270]
                [[5 1] [5 5] [1 5] [1 1] [5 1]]]
         [cycle 3 outer simple 0 [90 45 45] [[1 5] [5 5] [1 1] [1 5]]]
         [cycle 3 outer simple 0 [90 45 45] [[5 1] [1 1] [5 5] [5 1]]]
         [junc ell [5 1] [5 5] [1 1]]
         [junc ell [1 5] [1 1] [5 5]]
         [junc arw [1 1] [5 1] [5 5] [1 5]]
         [junc arw [5 5] [1 5] [1 1] [5 1]]]
        :

This shows more clearly that outer boundaries of inner regions are traversed
clockwise.

Now try something with free ends.

        : drawto(6,6); drawto(11,1);
        : jumpto(3,3); drawto(9,3); display();

        6     *
        5    * *
        4   *   *
        3  *******
        2 *       *
        1*         *
         12345678901

        : seepicture();
        : flush([line ==]);
        :
        : regions();
        : database ==>
        ** [[cycle 7 inner complex 2
                [360 135 135 360 180 270 180]
                [[1 1] [3 3] [9 3] [11 1] [9 3] [6 6] [3 3] [1 1]]]
         [cycle 3 outer simple 0 [90 45 45] [[6 6] [9 3] [3 3] [6 6]]]
         [junc end [1 1] [3 3]]
         [junc end [11 1] [9 3]]
         [junc ell [6 6] [3 3] [9 3]]
         [junc tee [3 3] [1 1] [9 3] [6 6]]
         [junc tee [9 3] [6 6] [3 3] [11 1]]]

-- Exercises ----------------------------------------------------------------

1.  Compare the output of the procedure SEEPICTURE and the procedure
REGIONS, and discuss their relative merits as a basis for recognising
shapes like letters, squares, triangles, etc.

2.  What additional problems arise if there are several items in the picture,
or if items overlap?

3.  Do you think finding junctions or finding cycles or regions has any
connection with the strategies you use (unconsciously) for recognising
structures? What kind of evidence could help to support an answer to
this question?

4.  Is there any connection between this work and (a) template matching,
(b) Winston's work on learning structural descriptions from examples,
(c) Minsky's 'frames' theory, (d) statistical pattern recognition?

5.  You could try designing your own programs similar to those described above.
One useful tip is to use MATCH to decide if a pair of points occur in
sequence in a cycle (e.g. when you need to decide if a ray from some
junction already occurs in one of the cycles. You can also use MATCH
to find the next point in a cycle after a given point.

What could the information about cycles in the picture be used for?
Is it more useful for recognition of shapes than the output of FINDJUNCS?
Would it be useful for a program which tries to interpret a picture as
representing a blocks world?
    : LIB FINDREGIONS;

is available for dealing with pictures made of disconnected parts some of which
may be contained in others, e.g. a triangle inside a square.
This package renames the REGIONS procedure, calling it FINDCYCLES.
It defines a new procedure FINDREGIONS which operates on the output
of FINDCYCLES. The procedure REGIONS is then defined to call first
FINDCYCLES then FINDREGIONS.
Try something like the following sequence:

    <draw your picture with some regions inside others>
    : SEEPICTURE();
    : DATABASE ==>
    : FLUSH([LINE ==]);
    : LIB FINDREGIONS;
    : TRACE FINDCYCLES FINDREGIONS PTINSIDE;
    : REGIONS();
    : DATABASE ==>
