Re: [boost] Boost.Numeric: multi_array requirements

From: Jeremy Siek (jsiek_at_[hidden])
Date: 2001-03-30 11:15:54

On Thu, 29 Mar 2001, Ullrich Koethe wrote:
koethe> Indexing:
koethe> ---------
koethe> 
koethe> Most proposals I've seen so far are using integers for indexing.
koethe> However, in higher dimensions this causes all kinds of trouble - Shall
koethe> we use (i,j,k) or [i][j][k]? Is the horizontal index first or last? Is
koethe> the first index 0 or 1? Therefore, I've found *index objects* a very
koethe> powerful alternative. For example:
koethe> 
koethe> Index2D start = matrix.upperLeft(),
koethe>         end   = matrix.lowerRight().
koethe>         i;
koethe> 
koethe> for(i.y = start.y; i.y < end.y; ++i.y)
koethe> {
koethe>     for(i.x = start.x; i.x < end.x; ++i.x)
koethe>     {
koethe>         matrix[i] = 42;
koethe>     }
koethe> }

Actually, the multi_array spec included an elt() function which takes the
equivalent of one of these index objects. There are two small differences:

  - the index object is just sequence of indices (not data members
     x and y)
  - the elt() function took an iterator to the beginning of the sequence.

So, your example above would have looked like this:

for (i[0] = start[0]; i[0] < end[0]; ++i[0])
  for (i[1] = start[1]; i[1] < end[1]; ++i[1])
    array.elt(i.begin());

I think you'll agree that the "x" and "y" are very must image specific,
and it would be better to go with a sequence of indices.

So what's left to debate:
  - the name of the function. I'm not all that crazy about elt().
    My current favorate is operator() because it is not operator[]
    (which people are use to using with a single integer) and 
    because it is shorter.

  - how to pass the index object. 
    1) As an iterator  (more flexible)
    2) As an container (nicer syntax)

    1) is what we've currently got in the spec, but I actually
      like 2) better.

    Either way, it be cool to make the element access funtion
    templated, so people could make their own index objects.

koethe> Iterators:
koethe> ----------
koethe> 
koethe> A property of images is that all coordinate directions are 'equal'. 
koethe> Therefore, a design like the following, where one direction is the
koethe> 'outer' direction, and the other the 'inner', is very artificial:
koethe> 
koethe> JeremySiek> 1. Use two iterators, the "outer iterator" iterates over
koethe> rows
koethe> JeremySiek> of the image, and the "inner iterator" iterates  down each
koethe> row.
koethe> JeremySiek>
koethe> JeremySiek> PixelRowIterator row_iter = rows_begin(myPix);
koethe> JeremySiek> for (; row_iter != rows_end(myPix); ++row_iter) {
koethe> JeremySiek>   PixelIterator iter = begin(*row_iter);
koethe> JeremySiek>   for (; iter != end(*row_iter); ++iter)
koethe> JeremySiek>     ...
koethe> JeremySiek> }
koethe> 
koethe> In VIGRA, I'm preferring a different iterator concept that doesn't have
koethe> this asymmetry (expet for cache performance):
koethe> 
koethe> ImageIterator start = image.upperLeft(),
koethe>               end = image.lowerRight(),
koethe>               i;
koethe> 
koethe> for(i.y = start.y; i.y < end.y; ++i.y)
koethe> {
koethe>     for(i.x = start.x; i.x < end.x; ++i.x)
koethe>     {
koethe>        *i = 42;
koethe>     }
koethe> }
koethe> 

This isn't really a conceptual difference, just a difference in packaging.
It's interesting, but it produces iterators that are not std conformant.
If I see iterators, I want to be able to use them with std::copy(), etc.
Also, there might be some performance advantage in the "hierarchical"
approach because the index*extent multiplications can be moved to outer
loops, effectivly performing what compiler guys call strength reduction.
With the above iterators, you might as well just use the index objects
instead.

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

Yes, this is a very important capability.

Cheers,
Jeremy

----------------------------------------------------------------------
 Jeremy Siek                        www: http://www.lsc.nd.edu/~jsiek/
 Ph.D. Candidate                  email: jsiek_at_[hidden]
 Univ. of Notre Dame         work phone: [phone]
----------------------------------------------------------------------