Boost logo

Boost :

From: Ullrich Koethe (koethe_at_[hidden])
Date: 2006-10-18 14:46:29


Lubomir Bourdev wrote:
>
>>On the other hand, a PixelDereferenceAdapter is semantically
>>also a view, so the use of the view idea could be extended.
>
>
> PixelDereferenceAdapter is not a view. It is a function object to be
> invoked upon pixel access, similar to your Pixel Accessor. You can
> easily attach it to any iterator, locator or a view.
>

Consider the following view-like syntax:

     pixel_view_A(dest_iter) = pixel_view_B(src_iter);

Now, when you absorb the pixel_view objects into the iterators by means of
proxies, you get the GIL style of adaptation:

     *pixel_view_iter_A = *pixel_view_iter_B;

If you replace the assignment with a normal member function, you get VIGRA
data accessors (which, by the way, were invented by Dietmar Kuehl, IIRC):

      pixel_view_A.set(pixel_view_B(src_iter), dest_iter);

All these should be semantically equivalent -- the only difference is
syntax and possibly performance. Hence I'm saying that pixel access
modifiers are essentially views, and treating them in that way may
simplify the documentation.

The following advantages and disdvantages of either approach have already
been pointed out:

Proxies: + nice syntax in algorithms
          + compatible to STL
          + can be chained
          - harder to implement, harder to understand implementation
          - may not work under some exotic circumstances
DataAccessors: + easy to implement, easy to understand
                 + can be chained
                 + do always work (even on non-conforming compilers)
                 - slightly less readable syntax in algorithms

To add some hard data to the comparison, I performed a benchmark were I
timed two proxy implementations vs the accessor approach for the task of
converting a planar RGB image into an interleaved one and vice versa. It
turned out that on my platform (Pentium M 1.7 GHz, cygwin gcc 3.4.4), both
proxy implementations were 30 to 60 percent _slower_ than the equivalent
data accessor version. The code is attached (it's a stand-alone program).

>
> I understand your motivation for using pixel adaptors, but in my opinion
> the benefits of using PixelDereferenceAdapter outweigh its
> disadvantages.
>

I'm not convinced.

>
> GIL incorporates a mechanism for active reduction of code bloat due to
> variant instantiations. I will present this approach at the LCSD
> workshop in the upcoming OOPSLA conference, which is in less than a
> week: http://lcsd.cs.tamu.edu/2006/
>

I'd like to read this paper.

>
>>3. I don't like that the input/output image format (jpeg, png
>>etc.) must be hardcoded in the program (by using
>>jpeg_read_image() etc.).
>
>
> We initially had a combined I/O methods like:
>
> template <typename Image>
> void read_image(const char* file, Image& img) {
> switch (image_type_from_file_name(file)) {
> case kJPEG: jpeg_read_image(file,img); break;
> case kTIFF: tiff_read_image(file,img); break;
> ...
> }
> }
>
> We decided to remove them for three reasons [snip] there are
> plans to put in ASL a more advanced GIL I/O that allows for dynamic
> registration of file format modules.

VIGRA's import/export library almost supports this (the only missing piece
is the possibility to register new converters at runtime - at the moment,
they must be known at compile time, but otherwise there is no need for a
design modification).

>>6. GIL may have alignment problems. For example, the variant
>>template allocates internal memory as "char[MAX_SIZE]" but
>>then reinterpret_casts it to an image type.
>
>
> MAX_SIZE is determined by taking the maximum of the size_of of each
> element in the MPL vector of image types with which the variant is
> instantiated. So for every variant it is different, and the appropriate
> size is evaluated at compile time.
>

I didn't say that the number of bytes was too small. I said that an image
object might be required to start at a multiple-of-8 address (say),
whereas a char array may start at an arbitrary address. So the
reinterpret_cast may return a forbidden address.

>
>>Casts from
>>"signed short *" to "pixel<int16s, rgb_t> *" and similar (see
>>the tutorial) are also problematic
>
>
> This cast is necessary to go from the outside world (pointer to the
> beginning of the image) into GIL.
> It is not obvious to me how to avoid it. How does VIGRA deal with the
> case where the user constructs an 8-bit RGB image by providing VIGRA
> with a raw pointer to the first pixel?
>

The DataAccessor takes care of this -- the iterator uses the original
pointer (see the PlanarAccessor in the attached program).

>
> We have been discussing the accessors/DereferenceAdaptors and promotion
> traits issues in separate threads. Aside from these differences with
> VIGRA, do you see any issues with the GIL interfaces that would prevent
> porting the Vigra algorithms to GIL, or that would affect their
> performance?
> If yes, what interfaces are missing and what algorithms need them?
>

Three things come to mind:
- many more type conversions; e.g. int8 => uint16; RGB <=> LAB etc.
- adaptors for the subsampled image view
- support for multi-dimensional images (e.g. volume data, image sequences)

Another important point are RGBA operations. In most cases, the alpha
channel is to be treated differently from the other channels, so you can't
just use component-wise operators as for the other color models. VIGRA
doesn't have an explicit RGBA type (TinyVector<T, 4> can be used instead),
because so far no-one came up with a convincing proposal for these
operations. But without them, RGBA is pretty useless.

I don't think any of this is a show stopper, but it means considerable work.

And, of course, the documentation has to be improved a lot... (I didn't
look at the test suite.)

Regards
Ulli

-- 
  ________________________________________________________________
|                                                                |
| Ullrich Koethe  Universitaet Hamburg / University of Hamburg   |
|                 FB Informatik        / Dept. of Informatics    |
|                 AB Kognitive Systeme / Cognitive Systems Group |
|                                                                |
| Phone: +49 (0)40 42883-2573                Vogt-Koelln-Str. 30 |
| Fax:   +49 (0)40 42883-2572                D - 22527 Hamburg   |
| Email: u.koethe_at_[hidden]               Germany             |
|        koethe_at_[hidden]                        |
| WWW:   http://kogs-www.informatik.uni-hamburg.de/~koethe/      |
|________________________________________________________________|

#include <vector>
#include <iostream>
#include <time.h>

#define BY_REFERENCE

template <class T>
struct RGBValue
{
    RGBValue()
    {}
    
    RGBValue(T ir, T ig, T ib)
    : r(ir), g(ig), b(ib)
    {}
    
    T r,g,b;
};

typedef std::vector<RGBValue<unsigned char> > Interleaved;

template <class T>
struct PlanarArray
{
    typedef std::vector<T> Data;
    typedef typename Data::iterator DI;
    typedef typename Data::const_iterator DCI;

#ifdef BY_REFERENCE
    struct const_proxy
    {
        const_proxy(T const & ir, T const & ig, T const & ib)
        : r(const_cast<T&>(ir)), g(const_cast<T&>(ig)), b(const_cast<T&>(ib))
        {}
        
        operator RGBValue<T> () const
        {
            return RGBValue<T>(r,g,b);
        }
        
        T & r;
        T & g;
        T & b;
    };
    
    struct proxy : public const_proxy
    {
        proxy(T const & ir, T const & ig, T const & ib)
        : const_proxy(ir, ig, ib)
        {}
        
        proxy & operator=(RGBValue<T> const & rhs)
        {
            this->r = rhs.r;
            this->g = rhs.g;
            this->b = rhs.b;
            return *this;
        }
    };
    
    struct iterator
    {
        iterator(DI p, int o)
        : ptr(p),
          offset(o)
        {}
        
        iterator & operator++()
        {
            ++ptr;
            return *this;
        }
        
        proxy operator*() const
        {
            return proxy(*ptr, ptr[offset], ptr[2*offset]);
        }
        
        DI ptr;
        int offset;
    };

    struct const_iterator
    {
        const_iterator(DCI p, int o)
        : ptr(p),
          offset(o)
        {}
        
        const_iterator & operator++()
        {
            ++ptr;
            return *this;
        }
        
        const_proxy operator*() const
        {
            return const_proxy(*ptr, ptr[offset], ptr[2*offset]);
        }
        
        DCI ptr;
        int offset;
    };
#else
    struct const_proxy
    {
        const_proxy(DCI i, int o)
        : iter(i), offset(o)
        {}
        
        operator RGBValue<T> () const
        {
            return RGBValue<T>(*iter, iter[offset], iter[2*offset]);
        }
        
        DCI iter;
        int offset;
    };
    
    struct proxy
    {
        proxy(DI i, int o)
        : iter(i), offset(o)
        {}
        
        operator RGBValue<T> () const
        {
            return RGBValue<T>(*iter, iter[offset], iter[2*offset]);
        }
        
        proxy & operator=(RGBValue<T> const & rhs)
        {
            *iter = rhs.r;
            iter[offset] = rhs.g;
            iter[2*offset] = rhs.b;
            return *this;
        }
        
        DI iter;
        int offset;
    };
    
    struct iterator
    {
        iterator(DI p, int o)
        : ptr(p),
          offset(o)
        {}
        
        iterator & operator++()
        {
            ++ptr;
            return *this;
        }
        
        proxy operator*() const
        {
            return proxy(ptr, offset);
        }
        
        DI ptr;
        int offset;
    };

    struct const_iterator
    {
        const_iterator(DCI p, int o)
        : ptr(p),
          offset(o)
        {}
        
        const_iterator & operator++()
        {
            ++ptr;
            return *this;
        }
        
        const_proxy operator*() const
        {
            return const_proxy(ptr, offset);
        }
        
        DCI ptr;
        int offset;
    };
#endif

    PlanarArray(int s)
    : size(s),
      data(3*s)
    {}
    
    iterator begin()
    {
        return iterator(data.begin(), size);
    }
    
    const_iterator begin() const
    {
        return const_iterator(data.begin(), size);
    }
    
    int size;
    std::vector<T> data;
};

typedef PlanarArray<unsigned char> Planar;

template <class T>
struct DefaultAccessor
{
    template <class Iterator>
    RGBValue<T> const & operator()(Iterator i) const
    {
        return *i;
    }
    
    template <class Iterator>
    void set(RGBValue<T> const & rgb, Iterator i) const
    {
        *i = rgb;
    }
    
    int offset;
};

template <class T>
struct PlanarAccessor
{
    PlanarAccessor(int o)
    : offset(o)
    {}
    
    template <class Iterator>
    RGBValue<T> operator()(Iterator i) const
    {
        return RGBValue<T>(*i, i[offset], i[2*offset]);
    }
    
    template <class Iterator>
    void set(RGBValue<T> const & rgb, Iterator i) const
    {
        *i = rgb.r;
        i[offset] = rgb.g;
        i[2*offset] = rgb.b;
    }
    
    int offset;
};

int main()
{
    const int repetitions = 10;
    const int size = 1000000;
    Interleaved ia(size);
    Planar pa(size);
    DefaultAccessor<unsigned char> d;
    PlanarAccessor<unsigned char> p(size);
    
    clock_t t1 = clock();
    for(int j = 0; j < repetitions; ++j)
    {
        Interleaved::iterator iia = ia.begin();
        Planar::const_iterator icpa = const_cast<Planar const &>(pa).begin();
        for(int k=0; k < size; ++k, ++iia, ++icpa)
        {
            d.set(*icpa, iia);
        }
    }
    std::cerr << "read proxy: " << (float(clock() - t1) / CLOCKS_PER_SEC / repetitions) << std::endl;
    
    t1 = clock();
    for(int j = 0; j < repetitions; ++j)
    {
        Interleaved::iterator iia = ia.begin();
        Planar::DCI idcpa = const_cast<Planar const &>(pa).data.begin();
        for(int k=0; k < size; ++k, ++iia, ++idcpa)
        {
            d.set(p(idcpa), iia);
        }
    }
    std::cerr << "read accessor: " << (float(clock() - t1) / CLOCKS_PER_SEC / repetitions) << std::endl;
    
    t1 = clock();
    for(int j = 0; j < repetitions; ++j)
    {
        Interleaved::const_iterator icia = const_cast<Interleaved const &>(ia).begin();
        Planar::iterator ipa = pa.begin();
        for(int k=0; k < size; ++k, ++icia, ++ipa)
        {
            *ipa = d(icia);
        }
    }
    std::cerr << "write proxy: " << (float(clock() - t1) / CLOCKS_PER_SEC / repetitions) << std::endl;
    
    t1 = clock();
    for(int j = 0; j < repetitions; ++j)
    {
        Interleaved::const_iterator icia = const_cast<Interleaved const &>(ia).begin();
        Planar::DI idpa = pa.data.begin();
        for(int k=0; k < size; ++k, ++icia, ++idpa)
        {
            p.set(d(icia), idpa);
        }
    }
    std::cerr << "write accessor: " << (float(clock() - t1) / CLOCKS_PER_SEC / repetitions) << std::endl;
}


Boost list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk