Re: [boost] Boost.Numeric: multi_array requirements

From: David Abrahams (abrahams_at_[hidden])
Date: 2001-03-29 20:22:30

Interesting ideas with obvious advantages in the dense matrix case (e.g.,
image processing). I think the approach has undesirable characteristics when
dealing with sparse matrices, though. The advantage of MTL iterators is that
you can avoid processing elements that aren't stored. Probably we'd want
both approaches for dealing with different problem domains.

-Dave

----- Original Message -----
From: "Ullrich Koethe" <koethe_at_[hidden]>

> 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