The design of this algorithm was constrained by the need to vectorize large images, typically 7000 by 8000 pixel images, on a computer with a relatively small amount of memory, (4 megabytes).
The real world is "imaged" by a scanning device. The output of the scanning device is an image. The image is classified into different classes, resulting in a classification. A classification is made up of regions. The regions are bordered by edges. Each region is made up of pixels. The edges run between pixels. Each pixel is square. The border of a square pixel is made up by four vexils.
(The name "pixel" is commonly used and derives from "PIcture X ELement", and other common terms such as "voxel" from "VOlume X ELement", and "mixel" from "MIXture pixEL" are well known. However, "vexil" is, admittedly, my own term arising from "VEctor X pIcture eLement".
A string is a list of vexils. Hence an edge of a region is a string of vexils.
Sometimes three or four regions meet at the same point. This point is called a node. All strings start at a node and end at a node. No string goes through a node.
If a region is surrounded by one and only one other class, (think of an island in an ocean), then the string of vexils bounding this region must meet itself. This meeting point also called a node, but a special kind of node called a knot.
In GIS parlance, vector strings without the associated topological information are termed "spaghetti".
The program shifts a 2 by 2 window from left to right over the image looking for edges. Edges found are joined into strings. A container called dangleList holds all incomplete strings which are dangling down from north to south. An index attached to the dangleList moves with the window from one dangling string to the next.
Spaghetti inspects each 2 by 2 block of pixels,
separates the blocks into classes based on the edges within the block
and not on the actual pixel values.
Thus for example, the block:-
12 | 12 |
12 | 3 |
contains one 'Southward' vertical edge and one 'Eastward' horizontal edge and is handled in exactly the same way, by the same bit of code, as the block :-
98 | 98 |
98 | 1 |
as the edges are the same even if the pixel values are different.
Whereas the block :-
13 | 12 |
12 | 2 |
is handled in a different manner to both blocks above.
Here is a complete list of all possible block varieties...
|
|
|
|
|
|
|
|
|
|
|
|
|
A buffer is created in memory that is at least 2 lines long, and the lines are 2 pixels longer than the image lines.
The first few lines of the image are read into the buffer starting at the second line of the buffer, with the first pixel of image data starting at the second pixel of the buffer. The first line of the buffer are set to theWorld value. The first and last pixels of each line in the buffer is set to theWorld. ("theWorld" is a nominal class value for the scene beyond the image)
A container object called the dangleList is created and initialised, and an index object called the dangleDex is attached to the container. An Index object acts as an index into the container it is attached to, and can be moved around the container. Objects within the container can be accessed via the index.
The buffer and the container is passed to the Spaghetti Machine which vectorizes each buffer.
The last line of the buffer is copied to the first line of the buffer, and the next group of lines are read from the image into the buffer starting at the second line second pixel. If this is the last bufferfull to be processed the last line of the buffer is set to theWorld. The buffer is fed to the Spaghetti Machine and this process is repeated until the image has been completely processed.
Starting at the second line, second pixel of the buffer, scanning as one reads, from west to east then north to south.
For each line in the buffer :-
Set the dangleDex to point to the front of the dangleList.
For each pixel in the line, (starting at the second pixel), check each 2 by 2 window for edges. (Place the bottom left hand corner of the window over the pixel.)
The very first edge scanned has to be in a
y | y |
y | x |
If the next edge scanned was of the form
z | z |
x | x |
If a window of the form
x | x |
y | x |
If a window of the form
y | x |
y | x |
If a window of the form
z | x |
x | x |
If a window of the form
x | y |
y | x |
If a window of the form
z | x |
y | x |
In a similar manner, every block class is handled. Note :- when the strings are told to attach themselves to a node, they check if both ends are now attached. If so, they smooth themselves, then move themselves out of memory onto the disk.
Previous | Next | Contents |