libs/gil/doc/design/pixel_iterator.rst

   1 Pixel Iterator
   2 ==============
   3
   4 .. contents::
   5    :local:
   6    :depth: 2
   7
   8 Overview
   9 --------
  10
  11 Pixel iterators are random traversal iterators whose ``value_type
  12 models`` ``PixelValueConcept``.
  13
  14 Fundamental Iterator
  15 --------------------
  16
  17 Pixel iterators provide metafunctions to determine whether they are mutable
  18 (i.e. whether they allow for modifying the pixel they refer to), to get the
  19 immutable (read-only) type of the iterator, and to determine whether they are
  20 plain iterators or adaptors over another pixel iterator:
  21
  22 .. code-block:: cpp
  23
  24   concept PixelIteratorConcept<RandomAccessTraversalIteratorConcept Iterator>
  25       : PixelBasedConcept<Iterator>
  26   {
  27     where PixelValueConcept<value_type>;
  28     typename const_iterator_type<It>::type;
  29         where PixelIteratorConcept<const_iterator_type<It>::type>;
  30     static const bool  iterator_is_mutable<It>::value;
  31     static const bool  is_iterator_adaptor<It>::value;   // is it an iterator adaptor
  32   };
  33
  34   template <typename Iterator>
  35   concept MutablePixelIteratorConcept : PixelIteratorConcept<Iterator>, MutableRandomAccessIteratorConcept<Iterator> {};
  36
  37 .. seealso::
  38
  39   - `PixelIteratorConcept<Iterator> <reference/group___pixel_iterator_concept_pixel_iterator.html>`_
  40   - `MutablePixelIteratorConcept<Iterator> <reference/structboost_1_1gil_1_1_mutable_pixel_iterator_concept.html>`_
  41
  42 Models
  43 ^^^^^^
  44
  45 A built-in pointer to pixel, ``pixel<ChannelValue,Layout>*``, is GIL model for
  46 pixel iterator over interleaved homogeneous pixels. Similarly,
  47 ``packed_pixel<PixelData,ChannelRefVec,Layout>*`` is GIL model for an iterator
  48 over interleaved packed pixels.
  49
  50 For planar homogeneous pixels, GIL provides the class
  51 ``planar_pixel_iterator``, templated over a channel iterator and color space.
  52 Here is how the standard mutable and read-only planar RGB iterators over
  53 unsigned char are defined:
  54
  55 .. code-block:: cpp
  56
  57   template <typename ChannelPtr, typename ColorSpace>
  58   struct planar_pixel_iterator;
  59
  60   // GIL provided typedefs
  61   typedef planar_pixel_iterator<const bits8*, rgb_t> rgb8c_planar_ptr_t;
  62   typedef planar_pixel_iterator<      bits8*, rgb_t> rgb8_planar_ptr_t;
  63
  64 ``planar_pixel_iterator`` also models ``HomogeneousColorBaseConcept`` (it
  65 subclasses from ``homogeneous_color_base``) and, as a result, all color base
  66 algorithms apply to it. The element type of its color base is a channel
  67 iterator. For example, GIL implements ``operator++`` of planar iterators
  68 approximately like this:
  69
  70 .. code-block:: cpp
  71
  72   template <typename T>
  73   struct inc : public std::unary_function<T,T>
  74   {
  75     T operator()(T x) const { return ++x; }
  76   };
  77
  78   template <typename ChannelPtr, typename ColorSpace>
  79   planar_pixel_iterator<ChannelPtr,ColorSpace>&
  80   planar_pixel_iterator<ChannelPtr,ColorSpace>::operator++()
  81   {
  82     static_transform(*this,*this,inc<ChannelPtr>());
  83     return *this;
  84   }
  85
  86 Since ``static_transform`` uses compile-time recursion, incrementing an
  87 instance of ``rgb8_planar_ptr_t`` amounts to three pointer increments.
  88 GIL also uses the class ``bit_aligned_pixel_iterator`` as a model for a pixel
  89 iterator over bit-aligned pixels. Internally it keeps track of the current
  90 byte and the bit offset.
  91
  92 Iterator Adaptor
  93 ----------------
  94
  95 Iterator adaptor is an iterator that wraps around another iterator. Its
  96 ``is_iterator_adaptor`` metafunction must evaluate to true, and it needs to
  97 provide a member method to return the base iterator, a metafunction to get its
  98 type, and a metafunction to rebind to another base iterator:
  99
 100 .. code-block:: cpp
 101
 102   concept IteratorAdaptorConcept<RandomAccessTraversalIteratorConcept Iterator>
 103   {
 104     where SameType<is_iterator_adaptor<Iterator>::type, mpl::true_>;
 105
 106     typename iterator_adaptor_get_base<Iterator>;
 107         where Metafunction<iterator_adaptor_get_base<Iterator> >;
 108         where boost_concepts::ForwardTraversalConcept<iterator_adaptor_get_base<Iterator>::type>;
 109
 110     typename another_iterator;
 111     typename iterator_adaptor_rebind<Iterator,another_iterator>::type;
 112         where boost_concepts::ForwardTraversalConcept<another_iterator>;
 113         where IteratorAdaptorConcept<iterator_adaptor_rebind<Iterator,another_iterator>::type>;
 114
 115     const iterator_adaptor_get_base<Iterator>::type& Iterator::base() const;
 116   };
 117
 118   template <boost_concepts::Mutable_ForwardIteratorConcept Iterator>
 119   concept MutableIteratorAdaptorConcept : IteratorAdaptorConcept<Iterator> {};
 120
 121 .. seealso::
 122
 123   - `IteratorAdaptorConcept<Iterator> <reference/structboost_1_1gil_1_1_iterator_adaptor_concept.html>`_
 124   - `MutableIteratorAdaptorConcept<Iterator> <reference/structboost_1_1gil_1_1_mutable_iterator_adaptor_concept.html>`_
 125
 126 Models
 127 ^^^^^^
 128
 129 GIL provides several models of ``IteratorAdaptorConcept``:
 130
 131 - ``memory_based_step_iterator<Iterator>``: An iterator adaptor that changes
 132   the fundamental step of the base iterator
 133   (see :ref:`design/pixel_iterator:Step Iterator`)
 134
 135 - ``dereference_iterator_adaptor<Iterator,Fn>``: An iterator that applies a
 136   unary function ``Fn`` upon dereferencing. It is used, for example, for
 137   on-the-fly color conversion. It can be used to construct a shallow image
 138   "view" that pretends to have a different color space or channel depth.
 139   See :doc:`image_view` for more. The unary function ``Fn`` must
 140   model ``PixelDereferenceAdaptorConcept`` (see below).
 141
 142 Pixel Dereference Adaptor
 143 -------------------------
 144
 145 Pixel dereference adaptor is a unary function that can be applied upon
 146 dereferencing a pixel iterator. Its argument type could be anything (usually a
 147 ``PixelConcept``) and the result type must be convertible to ``PixelConcept``:
 148
 149 .. code-block:: cpp
 150
 151   template <boost::UnaryFunctionConcept D>
 152   concept PixelDereferenceAdaptorConcept:
 153       DefaultConstructibleConcept<D>,
 154       CopyConstructibleConcept<D>,
 155       AssignableConcept<D>
 156   {
 157     typename const_t;         where PixelDereferenceAdaptorConcept<const_t>;
 158     typename value_type;      where PixelValueConcept<value_type>;
 159     typename reference;       where PixelConcept<remove_reference<reference>::type>;  // may be mutable
 160     typename const_reference;   // must not be mutable
 161     static const bool D::is_mutable;
 162
 163     where Convertible<value_type, result_type>;
 164   };
 165
 166 Models
 167 ^^^^^^
 168
 169 GIL provides several models of ``PixelDereferenceAdaptorConcept``:
 170
 171 * ``color_convert_deref_fn``: a function object that performs color conversion
 172
 173 * ``detail::nth_channel_deref_fn``: a function object that returns a grayscale
 174   pixel corresponding to the n-th channel of a given pixel
 175
 176 * ``deref_compose``: a function object that composes two models of
 177   ``PixelDereferenceAdaptorConcept``. Similar to ``std::unary_compose``,
 178   except it needs to pull the additional typedefs required by
 179   ``PixelDereferenceAdaptorConcept``
 180
 181 GIL uses pixel dereference adaptors to implement image views that perform
 182 color conversion upon dereferencing, or that return the N-th channel of the
 183 underlying pixel. They can be used to model virtual image views that perform
 184 an arbitrary function upon dereferencing, for example a view of the Mandelbrot
 185 set. ``dereference_iterator_adaptor<Iterator,Fn>`` is an iterator wrapper over
 186 a pixel iterator ``Iterator`` that invokes the given dereference iterator
 187 adaptor ``Fn`` upon dereferencing.
 188
 189 Step Iterator
 190 -------------
 191
 192 Sometimes we want to traverse pixels with a unit step other than the one
 193 provided by the fundamental pixel iterators. Examples where this would be
 194 useful:
 195
 196 * a single-channel view of the red channel of an RGB interleaved image
 197 * left-to-right flipped image (step = -fundamental_step)
 198 * subsampled view, taking every N-th pixel (step = N*fundamental_step)
 199 * traversal in vertical direction (step = number of bytes per row)
 200 * any combination of the above (steps are multiplied)
 201
 202 Step iterators are forward traversal iterators that allow changing the step
 203 between adjacent values:
 204
 205 .. code-block:: cpp
 206
 207   concept StepIteratorConcept<boost_concepts::ForwardTraversalConcept Iterator>
 208   {
 209     template <Integral D> void Iterator::set_step(D step);
 210   };
 211
 212   concept MutableStepIteratorConcept<boost_concepts::Mutable_ForwardIteratorConcept Iterator>
 213       : StepIteratorConcept<Iterator>
 214   {};
 215
 216 GIL currently provides a step iterator whose ``value_type models``
 217 ``PixelValueConcept``. In addition, the step is specified in memory units
 218 (which are bytes or bits). This is necessary, for example, when implementing
 219 an iterator navigating along a column of pixels - the size of a row of pixels
 220 may sometimes not be divisible by the size of a pixel; for example rows may be
 221 word-aligned.
 222
 223 To advance in bytes/bits, the base iterator must model
 224 ``MemoryBasedIteratorConcept``. A memory-based iterator has an inherent memory
 225 unit, which is either a bit or a byte. It must supply functions returning the
 226 number of bits per memory unit (1 or 8), the current step in memory units, the
 227 memory-unit distance between two iterators, and a reference a given distance
 228 in memunits away. It must also supply a function that advances an iterator a
 229 given distance in memory units. ``memunit_advanced`` and
 230 ``memunit_advanced_ref`` have a default implementation but some iterators may
 231 supply a more efficient version:
 232
 233 .. code-block:: cpp
 234
 235   concept MemoryBasedIteratorConcept
 236   <
 237       boost_concepts::RandomAccessTraversalConcept Iterator
 238   >
 239   {
 240     typename byte_to_memunit<Iterator>; where metafunction<byte_to_memunit<Iterator> >;
 241     std::ptrdiff_t      memunit_step(const Iterator&);
 242     std::ptrdiff_t      memunit_distance(const Iterator& , const Iterator&);
 243     void                memunit_advance(Iterator&, std::ptrdiff_t diff);
 244     Iterator            memunit_advanced(const Iterator& p, std::ptrdiff_t diff) { Iterator tmp; memunit_advance(tmp,diff); return tmp; }
 245     Iterator::reference memunit_advanced_ref(const Iterator& p, std::ptrdiff_t diff) { return *memunit_advanced(p,diff); }
 246   };
 247
 248 It is useful to be able to construct a step iterator over another iterator.
 249 More generally, given a type, we want to be able to construct an equivalent
 250 type that allows for dynamically specified horizontal step:
 251
 252 .. code-block:: cpp
 253
 254   concept HasDynamicXStepTypeConcept<typename T>
 255   {
 256     typename dynamic_x_step_type<T>;
 257         where Metafunction<dynamic_x_step_type<T> >;
 258   };
 259
 260 All models of pixel iterators, locators and image views that GIL provides
 261 support ``HasDynamicXStepTypeConcept``.
 262
 263 .. seealso::
 264
 265   - `StepIteratorConcept<Iterator> <reference/structboost_1_1gil_1_1_step_iterator_concept.html>`_
 266   - `MutableStepIteratorConcept<Iterator> <reference/structboost_1_1gil_1_1_mutable_step_iterator_concept.html>`_
 267   - `MemoryBasedIteratorConcept<Iterator> <reference/structboost_1_1gil_1_1_memory_based_iterator_concept.html>`_
 268   - `HasDynamicXStepTypeConcept<T> <reference/structboost_1_1gil_1_1_has_dynamic_x_step_type_concept.html>`_
 269
 270 Models
 271 ^^^^^^
 272
 273 All standard memory-based iterators GIL currently provides model
 274 ``MemoryBasedIteratorConcept``. GIL provides the class
 275 ``memory_based_step_iterator`` which models ``PixelIteratorConcept``,
 276 ``StepIteratorConcept``, and ``MemoryBasedIteratorConcept``. It takes the base
 277 iterator as a template parameter (which must model ``PixelIteratorConcept``
 278 and ``MemoryBasedIteratorConcept``) and allows changing the step dynamically.
 279 GIL implementation contains the base iterator and a ``ptrdiff_t`` denoting the
 280 number of memory units (bytes or bits) to skip for a unit step. It may also be
 281 used with a negative number. GIL provides a function to create a step iterator
 282 from a base iterator and a step:
 283
 284 .. code-block:: cpp
 285
 286   // Iterator models MemoryBasedIteratorConcept, HasDynamicXStepTypeConcept
 287   template <typename Iterator>
 288   typename dynamic_x_step_type<Iterator>::type make_step_iterator(Iterator const& it, std::ptrdiff_t step);
 289
 290 GIL also provides a model of an iterator over a virtual array of pixels,
 291 ``position_iterator``. It is a step iterator that keeps track of the pixel
 292 position and invokes a function object to get the value of the pixel upon
 293 dereferencing. It models ``PixelIteratorConcept`` and ``StepIteratorConcept``
 294 but not ``MemoryBasedIteratorConcept``.