..

Chain Codes -- Overhead (Long)

Contributors: 
David L. Anderson: Author
Lionel (Lon) Shapiro: Author
Additional Credits:
Funding
This module was supported by National Science Foundation Grants #9981217 and #0127561.

 

Introduction to Chain Codes

 

 

ABSOLUTE CHAIN CODES


 

DIRECTIONAL SYSTEM: Points of a compass

The points of the compass give us an absolute set of reference points, it is fixed by the Earth's magnetic fields. We can also fix the direction points to something smaller (like a piece of paper for example, or the computer monitor). The top = N, bottom = S, etc.

 

The chain code that we just produced is an algorithm that gives a symbolic representation of the triangle's shape, size and orientation. This information also provides precise rules for reconstructing that figure in a drawing. We will typically write the chaincode in one of either two ways. Either as

NE
SE
W
or as
NE, SE, W


After you've written down the complete chain code, click the button that says "Completed Chain Code" below, and see if you got it right.


Using numbers in writing chain codes

Since digital computers typically use a numerical system for storing information (everything is coded in "O's" and "1's") it will be a step in the right direction to modify our directional system to a numerical system rather than a letter system. Computer programmers typically use this system.

INSTEAD OF

NE, SE, W

1, 7, 4

 

.It is now time to use an interactive java program where you will get to work with chaincodes. When you go to the Java program, you will find that the objects are all located on a grid. Each move will take us from one intersection point on the grid, to another. Each horizontial and vertical move is of 1 unit length and each diagional move is slightly bigger than 1 unit in length (its length is the square root of 2, to be precise).

So enough of the preliminaries . . . let's go make some chaincodes! Click on the button below and a NEW WINDOW will pop-up with the chaincode activities. When you have completed all of the absolute chain code activities, return to this page and continue the lesson about chain codes where you left off.

Click below to begin the first chaincode program with demo and exercises.

Absolute chain code activities (click here)

WARNING: The "Chaincode Activities" is a Java applet that will NOT run on all browsers. Some browsers do not come with the most up-to-date plug-ins. And we've had consistent difficulties with Netscape. We recommend using Internet Explorer. Also, reliability is higher on PCs than on Macs.


You should now be familiar with absolute chain codes. But there is another type of chain code that also has important applications. We turn to it next.

Relative chain codes


It is possible to base an eight-directional coding system on relative directions. Each of the eight directions will be defined in relation to a moving perspective. Think of it this way. Imagine that you are driving a car around the perimeter of the object, marking a line behind you as you go. From any given point you have eight options. You can continue to go forward ("F") in the same direction that you have been going, you can go backward ("B") in the opposite direction, you can turn to the left ("L") or to the right ("R"). These are the four main points of the compass. The other four directions are derived from the four basic ones, as can be seen in the compass to the right.

 

Write down the relative chain code for this figure on a piece of scratch paper. When you've finished, click the button that says "See Completed Chain Code" below, and see if you got it right.

 

Just as we did with absolute chain codes, we can modify the directional system that we use with relative chain codes, using a numerical system rather than a letter system. The "forward" direction that was represented with an "F" is now represented with the number "2," "Backwards" is "6," "Left" is "4," "Right" is "0," and so on.

It is now time to use some interactive programs where you will get to work with relative chaincodes. In these exercises, you will be using the eight-way numbering system just described. Click below to begin the second chaincode program with demos and exercises

Relative chain code activities (click here)

Now that you've finished practicing with relative chain codes, let's move on. We now have two different methods for recording the shape of an object, one using an absolute point of reference, the other using relative reference points. The next step is to consider how a computer program might encode this information and make use of it to "recognize" objects.

Machines that do chain codes


One of the topics that we've been exploring is that of "machine vision." How might a machine be made to process visual information about the world? Given our present discussion of chain codes, we might ask: What kinds of visual information could a machine acquire using chain codes? As you may have already deduced, each type of chain code has its own advantages.

ABSOLUTE CHAIN CODES =

Comparing chain codes

Since the starting point for a relative chain code is completely arbitrary, we can shift the numbers around to reflect different possible starting positions. Now, we must be careful not to change the serial order of the numbers, because that is an essential part of the way the shape and size of the object is represented. One thing we can change, however, is which number we start with as we generate the series. So, let's say that our machine is trying to determine if the following two chain codes represent objects that are the same size and shape. Let's take the two relative chain codes that we created above. Here are the triangles and the chain codes:

Triangle #1
Chain Code #1
Chain Code #2
Triangle #2
7
0
7
7
0
7

If our computer program compares the numbers in these two lists, it will not produce a match. The top and bottom numbers don't match.

However, the fact that they don't match up could be the result of nothing more than the codes having been started at different vertices of the triangle. So, the only way to tell for certain whether or not the two objects are the same size and shape, is to change the order of the numbers on one of the chain codes, trying every possible starting point. You can visually see how this would work by pulling a number off the bottoom of the chain and moving it to the top.

This preserves the serial order of the numbers. You can cycle through the entire code this way, shifting the starting point one line segment at a time. If you cycle through each number in the code, you will be able to see if the two codes eventually "line up" so that you can visually see (as in column 3 above) that the two codes are exactly the same.

If we wanted to give a machine the ability to compare chain codes, a fairly simple program can be written that can determine whether or not two chain codes are exactly the same. This would give the machine the ability to judge that two shapes were the same, even if they were rotated quite differently.

It is now time for you to get some experience "comparing chain codes". Below you will find another interactive program. There is just one exercise. The program will s where you will get to work with relative chaincodes.

More chain code demos and exercises

It is now time do some activities with relative chain codes. Click below to begin the second chaincode program with demos and exercises

Advanced chain code activities (click here)

WARNING: The "Chaincode Activities" is a Java applet that will NOT run on all browsers. Some browsers do not come with the most up-to-date plug-ins. And we've had consistent difficulties with Netscape. We recommend using Internet Explorer. Also, reliability is higher on PCs than on Macs.


Have you completed the 2 demos and the 5 projects in the "Chaincode Activies" pop-up window? If not, click on the button above and do them all. If you've done them or if you can't find a browser that is capable of running them, then click on the "proceed to NEXT LESSON" button below.

Proceed to NEXT LESSON.

 

 

Copyright: 2006