3. The first phase of raster to vector conversion - Producing Spaghetti.

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).

3.1 Edges, vexils, strings, nodes, knots, spaghetti - some definitions

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".

3.2 An overview of how the Spaghetti Machine works.

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.

3.3 Block classes.

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...

xx xx

xx yx

yx yx

yy yx

zx xx

zz xx

xw xx

zx yx

zz yx

xw yx

yw yx

zw xx

zw yx

3.4 Starting up the Spaghetti Machine.

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.

3.5 The Spaghetti Machine.

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

, class block. Thus a new string is created. The horizontal and vertical vexil is placed in the string. As the string dangles southwards, the string is pushed onto the dangleList just before the point indexed by the dangleDex. As the string dangles eastwards, a pointer to the string is placed in the variable eastString.

If the next edge scanned was of the form

z	z
x	x

, then the horizontal vexil would be attached to the string pointed to by eastString.

If a window of the form

x	x
y	x

is scanned, then the horizontal and vertical edges are attached to the string pointed to by eastString, and the string is pushed onto the dangleList just before dangleDex.

If a window of the form

y	x
y	x

is scanned, the dangleDex must be pointing to a string dangling from the north. So the vertical edge is placed on the string, and dangleDex is pushed forward.

If a window of the form

z	x
x	x

is scanned, then the string dangling from the north is removed from the dangleList, and is knotted to the string coming from the west, which is pointed to by eastString.

If a window of the form

x	y
y	x

is scanned, then if x > y this is regarded as a corridor of x's in a field of y's. (Otherwise the other way round)

If a window of the form

z	x
y	x

is scanned, then a node is created, the string dangling from the north, and the string coming from the west, and a newly created string dangling south is attached to the node. The string from the north is replaced on the dangleList by the newly created string going south. The dangleDex is advanced.

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

Error processing SSI file