libs/gil/doc/design/pixel_locator.rst

   1 Pixel Locator
   2 =============
   3
   4 .. contents::
   5    :local:
   6    :depth: 2
   7
   8 Overview
   9 --------
  10
  11 A Locator allows for navigation in two or more dimensions. Locators are
  12 N-dimensional iterators in spirit, but we use a different name because they
  13 don't satisfy all the requirements of iterators. For example, they don't
  14 supply increment and decrement operators because it is unclear which dimension
  15 the operators should advance along.
  16 N-dimensional locators model the following concept:
  17
  18 .. code-block:: cpp
  19
  20   concept RandomAccessNDLocatorConcept<Regular Loc>
  21   {
  22     typename value_type;        // value over which the locator navigates
  23     typename reference;         // result of dereferencing
  24     typename difference_type; where PointNDConcept<difference_type>; // return value of operator-.
  25     typename const_t;           // same as Loc, but operating over immutable values
  26     typename cached_location_t; // type to store relative location (for efficient repeated access)
  27     typename point_t  = difference_type;
  28
  29     static const size_t num_dimensions; // dimensionality of the locator
  30     where num_dimensions = point_t::num_dimensions;
  31
  32     // The difference_type and iterator type along each dimension. The iterators may only differ in
  33     // difference_type. Their value_type must be the same as Loc::value_type
  34     template <size_t D> struct axis {
  35         typename coord_t = point_t::axis<D>::coord_t;
  36         typename iterator; where RandomAccessTraversalConcept<iterator>; // iterator along D-th axis.
  37         where iterator::value_type == value_type;
  38     };
  39
  40     // Defines the type of a locator similar to this type, except it invokes Deref upon dereferencing
  41     template <PixelDereferenceAdaptorConcept Deref> struct add_deref {
  42         typename type;        where RandomAccessNDLocatorConcept<type>;
  43         static type make(const Loc& loc, const Deref& deref);
  44     };
  45
  46     Loc& operator+=(Loc&, const difference_type&);
  47     Loc& operator-=(Loc&, const difference_type&);
  48     Loc operator+(const Loc&, const difference_type&);
  49     Loc operator-(const Loc&, const difference_type&);
  50
  51     reference operator*(const Loc&);
  52     reference operator[](const Loc&, const difference_type&);
  53
  54     // Storing relative location for faster repeated access and accessing it
  55     cached_location_t Loc::cache_location(const difference_type&) const;
  56     reference operator[](const Loc&,const cached_location_t&);
  57
  58     // Accessing iterators along a given dimension at the current location or at a given offset
  59     template <size_t D> axis<D>::iterator&       Loc::axis_iterator();
  60     template <size_t D> axis<D>::iterator const& Loc::axis_iterator() const;
  61     template <size_t D> axis<D>::iterator        Loc::axis_iterator(const difference_type&) const;
  62   };
  63
  64   template <typename Loc>
  65   concept MutableRandomAccessNDLocatorConcept
  66       : RandomAccessNDLocatorConcept<Loc>
  67   {
  68     where Mutable<reference>;
  69   };
  70
  71 Two-dimensional locators have additional requirements:
  72
  73 .. code-block:: cpp
  74
  75   concept RandomAccess2DLocatorConcept<RandomAccessNDLocatorConcept Loc>
  76   {
  77     where num_dimensions==2;
  78     where Point2DConcept<point_t>;
  79
  80     typename x_iterator = axis<0>::iterator;
  81     typename y_iterator = axis<1>::iterator;
  82     typename x_coord_t  = axis<0>::coord_t;
  83     typename y_coord_t  = axis<1>::coord_t;
  84
  85     // Only available to locators that have dynamic step in Y
  86     //Loc::Loc(const Loc& loc, y_coord_t);
  87
  88     // Only available to locators that have dynamic step in X and Y
  89     //Loc::Loc(const Loc& loc, x_coord_t, y_coord_t, bool transposed=false);
  90
  91     x_iterator&       Loc::x();
  92     x_iterator const& Loc::x() const;
  93     y_iterator&       Loc::y();
  94     y_iterator const& Loc::y() const;
  95
  96     x_iterator Loc::x_at(const difference_type&) const;
  97     y_iterator Loc::y_at(const difference_type&) const;
  98     Loc Loc::xy_at(const difference_type&) const;
  99
 100     // x/y versions of all methods that can take difference type
 101     x_iterator        Loc::x_at(x_coord_t, y_coord_t) const;
 102     y_iterator        Loc::y_at(x_coord_t, y_coord_t) const;
 103     Loc               Loc::xy_at(x_coord_t, y_coord_t) const;
 104     reference         operator()(const Loc&, x_coord_t, y_coord_t);
 105     cached_location_t Loc::cache_location(x_coord_t, y_coord_t) const;
 106
 107     bool      Loc::is_1d_traversable(x_coord_t width) const;
 108     y_coord_t Loc::y_distance_to(const Loc& loc2, x_coord_t x_diff) const;
 109   };
 110
 111   concept MutableRandomAccess2DLocatorConcept<RandomAccess2DLocatorConcept Loc>
 112       : MutableRandomAccessNDLocatorConcept<Loc> {};
 113
 114 2D locators can have a dynamic step not just horizontally, but
 115 vertically. This gives rise to the Y equivalent of
 116 ``HasDynamicXStepTypeConcept``:
 117
 118 .. code-block:: cpp
 119
 120   concept HasDynamicYStepTypeConcept<typename T>
 121   {
 122     typename dynamic_y_step_type<T>;
 123         where Metafunction<dynamic_y_step_type<T> >;
 124   };
 125
 126 All locators and image views that GIL provides model
 127 ``HasDynamicYStepTypeConcept``.
 128
 129 Sometimes it is necessary to swap the meaning of X and Y for a given locator
 130 or image view type (for example, GIL provides a function to transpose an image
 131 view). Such locators and views must be transposable:
 132
 133 .. code-block:: cpp
 134
 135   concept HasTransposedTypeConcept<typename T>
 136   {
 137     typename transposed_type<T>;
 138         where Metafunction<transposed_type<T> >;
 139   };
 140
 141 All GIL provided locators and views model ``HasTransposedTypeConcept``.
 142
 143 The locators GIL uses operate over models of ``PixelConcept`` and their x and
 144 y dimension types are the same. They model the following concept:
 145
 146 .. code-block:: cpp
 147
 148   concept PixelLocatorConcept<RandomAccess2DLocatorConcept Loc>
 149   {
 150     where PixelValueConcept<value_type>;
 151     where PixelIteratorConcept<x_iterator>;
 152     where PixelIteratorConcept<y_iterator>;
 153     where x_coord_t == y_coord_t;
 154
 155     typename coord_t = x_coord_t;
 156   };
 157
 158   concept MutablePixelLocatorConcept<PixelLocatorConcept Loc> : MutableRandomAccess2DLocatorConcept<Loc> {};
 159
 160 .. seealso::
 161
 162   - `HasDynamicYStepTypeConcept<T> <reference/structboost_1_1gil_1_1_has_dynamic_y_step_type_concept.html>`_
 163   - `HasTransposedTypeConcept<T> <reference/structboost_1_1gil_1_1_has_transposed_type_concept.html>`_
 164   - `RandomAccessNDLocatorConcept<Locator> <reference/structboost_1_1gil_1_1_random_access_n_d_locator_concept.html>`_
 165   - `MutableRandomAccessNDLocatorConcept<Locator> <reference/structboost_1_1gil_1_1_mutable_random_access_n_d_locator_concept.html>`_
 166   - `RandomAccess2DLocatorConcept<Locator> <reference/structboost_1_1gil_1_1_random_access2_d_locator_concept.html>`_
 167   - `MutableRandomAccess2DLocatorConcept<Locator> <reference/structboost_1_1gil_1_1_mutable_random_access2_d_locator_concept.html>`_
 168   - `PixelLocatorConcept<Locator> <reference/structboost_1_1gil_1_1_pixel_locator_concept.html>`_
 169   - `MutablePixelLocatorConcept<Locator> <reference/structboost_1_1gil_1_1_mutable_pixel_locator_concept.html>`_
 170
 171 Models
 172 ------
 173
 174 GIL provides two models of ``PixelLocatorConcept`` - a memory-based locator,
 175 ``memory_based_2d_locator`` and a virtual locator ``virtual_2d_locator``.
 176
 177 The ``memory_based_2d_locator`` is a locator over planar or interleaved images
 178 that have their pixels in memory. It takes a model of ``StepIteratorConcept``
 179 over pixels as a template parameter. (When instantiated with a model of
 180 ``MutableStepIteratorConcept``, it models ``MutablePixelLocatorConcept``).
 181
 182 .. code-block:: cpp
 183
 184   // StepIterator models StepIteratorConcept, MemoryBasedIteratorConcept
 185   template <typename StepIterator>
 186   class memory_based_2d_locator;
 187
 188 The step of ``StepIterator`` must be the number of memory units (bytes or
 189 bits) per row (thus it must be memunit advanceable). The class
 190 ``memory_based_2d_locator`` is a wrapper around ``StepIterator`` and uses it
 191 to navigate vertically, while its base iterator is used to navigate
 192 horizontally.
 193
 194 Combining fundamental iterator and step iterator allows us to create locators
 195 that describe complex pixel memory organizations. First, we have a choice of
 196 iterator to use for horizontal direction, i.e. for iterating over the pixels
 197 on the same row. Using the fundamental and step iterators gives us four
 198 choices:
 199
 200 - ``pixel<T,C>*`` - for interleaved images
 201 - ``planar_pixel_iterator<T*,C>`` - for planar images
 202 - ``memory_based_step_iterator<pixel<T,C>*>`` - for interleaved images with
 203   non-standard step)
 204 - ``memory_based_step_iterator<planar_pixel_iterator<T*,C> >`` - for planar
 205   images with non-standard step
 206
 207 Of course, one could provide their own custom x-iterator. One such example
 208 described later is an iterator adaptor that performs color conversion when
 209 dereferenced.
 210
 211 Given a horizontal iterator ``XIterator``, we could choose the ``y-iterator``,
 212 the iterator that moves along a column, as
 213 ``memory_based_step_iterator<XIterator>`` with a step equal to the number of
 214 memory units (bytes or bits) per row. Again, one is free to provide their own
 215 y-iterator.
 216
 217 Then we can instantiate
 218 ``memory_based_2d_locator<memory_based_step_iterator<XIterator> >`` to obtain
 219 a 2D pixel locator, as the diagram indicates:
 220
 221 .. image:: ../images/pixel_locator.gif
 222
 223 The ``memory_based_2d_locator`` also offers `cached_location_t` as mechanism
 224 to store relative locations for optimized repeated access of neighborhood
 225 pixels. The 2D coordinates of relative locations are cached as 1-dimensional
 226 raw byte offsets. This provides efficient access if a neighboring locations
 227 relative to a given locator are read or written frequently (e.g. in filters).
 228
 229 The ``virtual_2d_locator`` is a locator that is instantiated with a function
 230 object invoked upon dereferencing a pixel. It returns the value of a pixel
 231 given its X,Y coordinates. Virtual locators can be used to implement virtual
 232 image views that can model any user-defined function. See the GIL tutorial for
 233 an example of using virtual locators to create a view of the Mandelbrot set.
 234
 235 Both the virtual and the memory-based locators subclass from
 236 ``pixel_2d_locator_base``, a base class that provides most of the interface
 237 required by ``PixelLocatorConcept``. Users may find this base class useful if
 238 they need to provide other models of ``PixelLocatorConcept``.
 239
 240 Here is some sample code using locators:
 241
 242 .. code-block:: cpp
 243
 244   loc=img.xy_at(10,10);            // start at pixel (x=10,y=10)
 245   above=loc.cache_location(0,-1);  // remember relative locations of neighbors above and below
 246   below=loc.cache_location(0, 1);
 247   ++loc.x();                       // move to (11,10)
 248   loc.y()+=15;                     // move to (11,25)
 249   loc-=point<std::ptrdiff_t>(1,1);// move to (10,24)
 250   *loc=(loc(0,-1)+loc(0,1))/2;     // set pixel (10,24) to the average of (10,23) and (10,25) (grayscale pixels only)
 251   *loc=(loc[above]+loc[below])/2;  // the same, but faster using cached relative neighbor locations
 252
 253 The standard GIL locators are fast and lightweight objects. For example, the
 254 locator for a simple interleaved image consists of one raw pointer to the
 255 pixel location plus one integer for the row size in bytes, for a total of
 256 8 bytes. ``++loc.x()`` amounts to incrementing a raw pointer (or N pointers
 257 for planar images). Computing 2D offsets is slower as it requires
 258 multiplication and addition. Filters, for example, need to access the same
 259 neighbors for every pixel in the image, in which case the relative positions
 260 can be cached into a raw byte difference using ``cache_location``.
 261 In the above example ``loc[above]`` for simple interleaved images amounts to a
 262 raw array index operator.
 263
 264 Iterator over 2D image
 265 ----------------------
 266
 267 Sometimes we want to perform the same, location-independent operation
 268 over all pixels of an image. In such a case it is useful to represent
 269 the pixels as a one-dimensional array. GIL's ``iterator_from_2d`` is a
 270 random access traversal iterator that visits all pixels in an image in
 271 the natural memory-friendly order left-to-right inside
 272 top-to-bottom. It takes a locator, the width of the image and the
 273 current X position. This is sufficient information for it to determine
 274 when to do a "carriage return". Synopsis:
 275
 276 .. code-block:: cpp
 277
 278   template <typename Locator>  // Models PixelLocatorConcept
 279   class iterator_from_2d
 280   {
 281   public:
 282     iterator_from_2d(const Locator& loc, int x, int width);
 283
 284     iterator_from_2d& operator++(); // if (++_x<_width) ++_p.x(); else _p+=point_t(-_width,1);
 285
 286     ...
 287   private:
 288     int _x, _width;
 289     Locator _p;
 290   };
 291
 292 Iterating through the pixels in an image using ``iterator_from_2d`` is slower
 293 than going through all rows and using the x-iterator at each row. This is
 294 because two comparisons are done per iteration step - one for the end
 295 condition of the loop using the iterators, and one inside
 296 ``iterator_from_2d::operator++`` to determine whether we are at the end of a
 297 row. For fast operations, such as pixel copy, this second check adds about
 298 15% performance delay (measured for interleaved images on Intel platform).
 299 GIL overrides some STL algorithms, such as ``std::copy`` and ``std::fill``,
 300 when invoked with ``iterator_from_2d``-s, to go through each row using their
 301 base x-iterators, and, if the image has no padding (i.e.
 302 ``iterator_from_2d::is_1d_traversable()`` returns true) to simply iterate
 303 using the x-iterators directly.