Re: [boost] GIL Review - PixelDereferenceAdaptors vs. DataAccessors

From: Lubomir Bourdev (lbourdev_at_[hidden])
Date: 2006-10-18 14:58:55

Hi Ulli,

We don't use a PixelDereferenceAdaptor to model planar organization. We
only need the adaptor in cases where we want to perform some arbitrary
transformation upon dereferencing. For planar images, say RGB, we have a
planar iterator (planar_ptr) containing three pointers inside and upon
dereferencing it returns a planar reference proxy (planar_ref) that
contains three references. It behaves like a native C reference. For
example, you can use its operator= to assign it an RGB pixel value and
it will properly modify the three locations.

I know exactly what you are after :-)

You want an example where we do some arbitrary transformation upon
dereferencing and we want to be able to assign to the result, i.e. to
run the transformation "backwards". You want to show that doing so is
very tricky and involved.

> But to my big surprise, I couldn't 
> find any PixelDereferenceAdaptor in the public part of GIL 
> which supports lvalue use.

...which leads to my first argument: that cases where you need to do so
(in the context of image processing) simply don't occur frequently in
practice. We could think of some really fancy scenarios where you need
to do so, but I hope you will agree that these are not mainstream by any
means. (To get the nth channel of a memory-based image we simply change
the pixel type and the iterator step)

Now, suppose we find a need to do so. You will say that implementing
this is very tricky, and I will agree. It is tricky, someone might call
it "hacky", and involved but I think it is possible. Here is how I would
approach this:

Create an object that acts as a proxy reference:
- It has a conversion operator that converts it to the value type. This
implements the "read" direction
- It also has an operator= that takes a value type. It implements the
"write" direction.

This basically corresponds to what you call DataAccessor, except that
you provide a different interface. Not so tricky after all, but trickier
than doing a DataAccessor. Note, however, that the difficulty is on the
side of the library designer/extender, which is expected to have higher
expertise with the library, whereas the benefits are on the side of the
_user_. My principles are that it is OK to make the designer's job much
harder, if this leads to even small benefits on the side of the user. 

And what are those benefits?

First, education. People are familiar with iterators, but not so will
data accessors. They have to learn a new concept, as simple as it may
be, and learn to recognize and apply the new interface every time they
iterate over the pixels of an image.

Second, reuse. The promise of generic programming can best be realized
by agreeing to build on the same concepts. PixelAccessors may be
appealing (I think they are in many ways) but unfortunately people have
invested already a lot of effort in writing algorithms that deal just
with iterators. If I want to copy two images I could just use std::copy.
If I want to rotate the pixels 180 degrees, I can use std::reverse. Of
course, as Thorsten pointed out, GIL often provides performance
overloads. But the important thing is, we don't have to ; the algorithms
still work. Besides, in the cases where we do, like std::copy, we
typically still delegate to STL and call their std::copy. We don't
explicitly call memmove, we call std::copy with PODs and STL turns it
into memmove. We want to delegate as much as we can to standard
components because they could be better tested and optimized.
And the story, of course, does not end with the STL. If I want to find
the largest and smallest pixels in my image I can just use
boost::minmax_element. You may say that each of these is a trivial
algorithm and easy to just make a version that works with Vigra, but as
a collection they become a lot, and it is an open-ended set of
algorithms: By conforming to the standard GIL will automatically benefit
from any new algorithms that people may provide in the future. Besides,
I am not sure they are all trivial. I haven't looked into Boost Graph,
but since its algorithms follow standard iterator convention, I wouldn't
be surprised if it is easier to combine with GIL and make algorithms
like Graph Cut that have recently become popular for image segmentation.
A graph cut would be quite non-trivial to reimplement.
Of course, in cases where you need to use standard components you could
argue that you can make one from iterator and DataAccessor (essentially
the DereferenceAdaptor approach). But once you do that, you will have
two ways of doing the same thing; isn't removing DataAccessor going to
simplify things then?

Third, standardization directly decreases the cost of maintaining the
library. Writing algorithms like vigra::transformLine and
vigra::transformLineIf is the least of the work. You will have to
document them, maintain them, extend them, debug them, port them,
performance-optimize them... instead of having this be handled by
someone else.

Fourth, the user code is simplified. Instead of this:

template <class SrcIterator, class SrcAccessor,
          class DestIterator, class DestAccessor, class Functor>
void
transformLine(SrcIterator s,
              SrcIterator send, SrcAccessor src,
              DestIterator d, DestAccessor dest,
              Functor const & f)
{
    for(; s != send; ++s, ++d)
        dest.set(f(src(s)), d);
}

You just need this:

template <typename Src, typename Dst>
void copy(Src first, Src last, Dst dst) 
{
    for (; first!=last; ++first, ++dst)
       *dst = *first;
}

Fewer template parameters, simpler interfaces, shorter code, easier to
read, less opportunity to introduce bugs.

Fifth, conceptually it makes sense to combine the Accessor and the
Iterator into one, because what they really represent is an iterator
over a range of TransformedPixel. Its value type really is
TransformedPixel. 

To summarize my points:
- the cases where lvalue is needed are rare
- while tricky, it is possible to implement this
- the burden is on the side of library designer/extender and is done
once
- the benefit is on the side of the library user. There are many users,
and their threshold of familiarity with the library is lower.
- the benefits include:
   - less education. Users are familiar with the iterator concepts. They
need to learn about accessors
   - reuse of other generic components, like STL and boost libraries
   - standardization helps decrease maintenance and bug fixing cost
   - the user code is simplified. Expressions are cleaner. Functions
take fewer arguments
   - conceptually it makes sense to combine the Accessor and the
Iterator

And finally, DataAccessor is an interesting idea worthy of
investigation, but it spans beyond images. The right way to approach
this, in my opinion, is to try to make the case for DataAccessors as an
addition to the standard. If DataAccessors are accepted, lots of my
objections will no longer hold.

Lubomir