[boost] Boost.Numeric: multi_array requirements

From: Ullrich Koethe (koethe_at_[hidden])
Date: 2001-03-29 13:36:57

I'd like to add a new perspective to this discussion. So far, the array
class has been defined with linear algebra in mind. However, image
representation and processing would be an important application of
arrays as well. Here are some requirements:

1. Dynamic arrays up to dimension 4 (or perhaps 5)
2. Tiny static arrays up to dimension 2
3. Indexing 
4. Iterators
5. Subimages/Slices
6. Different views on the actual pixel data.

I think points 1 and 2 are clear. Point 3 is interesting:

Indexing:
---------

Most proposals I've seen so far are using intergers for indexing.
However, in higher dimensions this causes all kinds of trouble - Shall
we use (i,j,k) or [i][j][k]? Is the horizontal index first or last? Is
the first index 0 or 1? Therfore, I've found *index objects* a very
powerful alternative. For example:

Index2D start = matrix.upperLeft(),
        end   = matrix.lowerRight().
        i;

for(i.y = start.y; i.y < end.y; ++i.y)
{
    for(i.x = start.x; i.x < end.x; ++i.x)
    {
        matrix[i] = 42;
    }
}

The nice thing about this approach is that you can do all kinds of
clever things with indexes:

- define different index classes
- overload Matrix::operator[] for different indices
- convert index types into each other
- create slices as special indices 
- hide from users how indxing is actually implemented

Indices are like iterators, except that they dont have operator* (they
are only used with the matrix' operator[]). 

Iterators:
----------

A major property of images is that all coordinate directions are 'equal
'. Therefore, a design like the following, where one direction is the
'outer' direction, and the other the 'inner', is very artificial:

JeremySiek> 1. Use two iterators, the "outer iterator" iterates over
rows
JeremySiek> of the image, and the "inner iterator" iterates  down each
row.
JeremySiek>
JeremySiek> PixelRowIterator row_iter = rows_begin(myPix);
JeremySiek> for (; row_iter != rows_end(myPix); ++row_iter) {
JeremySiek>   PixelIterator iter = begin(*row_iter);
JeremySiek>   for (; iter != end(*row_iter); ++iter)
JeremySiek>     ...
JeremySiek> }

In VIGRA, I'm preferring a different iterator concept that doesn't have
this asymmetry (expet for cache performance):

ImageIterator start = image.upperLeft(),
              end = image.lowerRight(),
              i;

for(i.y = start.y; i.y < end.y; ++i.y)
{
    for(i.x = start.x; i.x < end.x; ++i.x)
    {
       *i = 42;
    }
}

Note the similarity to indices - the only difference is operator*. Note
also that rectangular subimages are represented by a pair of iterators .

Iterator adapters can be implemented for slices and other subsets. Most
importantly, I need RowIterator and ColumnIterator which are STL
compatible random-access-iterators that go accross a row and down a
column respectively. Also, rectangular

Slices:
-------

I seldom need slices, because iterarator adapters almost always allow a
more elegant solution.

Different views on the pixel data:
----------------------------------

This has proven more important than I expected. Consider, for example,
an image that contains complex numbers (e.g. the Fourier transform of an
image). Now, the magnitude of a complex number is a scalar that can be
used in any algorithm that requires a scalar image (for example, image
display). By using *data accessors* to create a magnitude view, I can
calculate the magnitude on the fly, without creating an extra magnitude
image.

displayImage(complex_image, MagnitudeAccessor());

Comments welcome

Ulli
-- 
 ________________________________________________________________
|                                                                |
| Ullrich Koethe  Universität Hamburg / University of Hamburg    |
|                 FB Informatik / Dept. of Computer Science      |
|                 AB Kognitive Systeme / Cognitive Systems Group |
|                                                                |
| Phone: [phone]                Vogt-Koelln-Str. 30 |
| Fax:   [phone]                D - 22527 Hamburg   |
| Email: u.koethe_at_[hidden]               Germany             |
|        koethe_at_[hidden]                        |
| WWW:   http://kogs-www.informatik.uni-hamburg.de/~koethe/      |
|________________________________________________________________|