1Pixel Locator 2============= 3 4.. contents:: 5 :local: 6 :depth: 2 7 8Overview 9-------- 10 11A Locator allows for navigation in two or more dimensions. Locators are 12N-dimensional iterators in spirit, but we use a different name because they 13don't satisfy all the requirements of iterators. For example, they don't 14supply increment and decrement operators because it is unclear which dimension 15the operators should advance along. 16N-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 71Two-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 1142D locators can have a dynamic step not just horizontally, but 115vertically. 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 126All locators and image views that GIL provides model 127``HasDynamicYStepTypeConcept``. 128 129Sometimes it is necessary to swap the meaning of X and Y for a given locator 130or image view type (for example, GIL provides a function to transpose an image 131view). 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 141All GIL provided locators and views model ``HasTransposedTypeConcept``. 142 143The locators GIL uses operate over models of ``PixelConcept`` and their x and 144y 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 171Models 172------ 173 174GIL provides two models of ``PixelLocatorConcept`` - a memory-based locator, 175``memory_based_2d_locator`` and a virtual locator ``virtual_2d_locator``. 176 177The ``memory_based_2d_locator`` is a locator over planar or interleaved images 178that have their pixels in memory. It takes a model of ``StepIteratorConcept`` 179over 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 188The step of ``StepIterator`` must be the number of memory units (bytes or 189bits) per row (thus it must be memunit advanceable). The class 190``memory_based_2d_locator`` is a wrapper around ``StepIterator`` and uses it 191to navigate vertically, while its base iterator is used to navigate 192horizontally. 193 194Combining fundamental iterator and step iterator allows us to create locators 195that describe complex pixel memory organizations. First, we have a choice of 196iterator to use for horizontal direction, i.e. for iterating over the pixels 197on the same row. Using the fundamental and step iterators gives us four 198choices: 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 207Of course, one could provide their own custom x-iterator. One such example 208described later is an iterator adaptor that performs color conversion when 209dereferenced. 210 211Given a horizontal iterator ``XIterator``, we could choose the ``y-iterator``, 212the iterator that moves along a column, as 213``memory_based_step_iterator<XIterator>`` with a step equal to the number of 214memory units (bytes or bits) per row. Again, one is free to provide their own 215y-iterator. 216 217Then we can instantiate 218``memory_based_2d_locator<memory_based_step_iterator<XIterator> >`` to obtain 219a 2D pixel locator, as the diagram indicates: 220 221.. image:: ../images/pixel_locator.gif 222 223The ``memory_based_2d_locator`` also offers `cached_location_t` as mechanism 224to store relative locations for optimized repeated access of neighborhood 225pixels. The 2D coordinates of relative locations are cached as 1-dimensional 226raw byte offsets. This provides efficient access if a neighboring locations 227relative to a given locator are read or written frequently (e.g. in filters). 228 229The ``virtual_2d_locator`` is a locator that is instantiated with a function 230object invoked upon dereferencing a pixel. It returns the value of a pixel 231given its X,Y coordinates. Virtual locators can be used to implement virtual 232image views that can model any user-defined function. See the GIL tutorial for 233an example of using virtual locators to create a view of the Mandelbrot set. 234 235Both the virtual and the memory-based locators subclass from 236``pixel_2d_locator_base``, a base class that provides most of the interface 237required by ``PixelLocatorConcept``. Users may find this base class useful if 238they need to provide other models of ``PixelLocatorConcept``. 239 240Here 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 253The standard GIL locators are fast and lightweight objects. For example, the 254locator for a simple interleaved image consists of one raw pointer to the 255pixel location plus one integer for the row size in bytes, for a total of 2568 bytes. ``++loc.x()`` amounts to incrementing a raw pointer (or N pointers 257for planar images). Computing 2D offsets is slower as it requires 258multiplication and addition. Filters, for example, need to access the same 259neighbors for every pixel in the image, in which case the relative positions 260can be cached into a raw byte difference using ``cache_location``. 261In the above example ``loc[above]`` for simple interleaved images amounts to a 262raw array index operator. 263 264Iterator over 2D image 265---------------------- 266 267Sometimes we want to perform the same, location-independent operation 268over all pixels of an image. In such a case it is useful to represent 269the pixels as a one-dimensional array. GIL's ``iterator_from_2d`` is a 270random access traversal iterator that visits all pixels in an image in 271the natural memory-friendly order left-to-right inside 272top-to-bottom. It takes a locator, the width of the image and the 273current X position. This is sufficient information for it to determine 274when 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 292Iterating through the pixels in an image using ``iterator_from_2d`` is slower 293than going through all rows and using the x-iterator at each row. This is 294because two comparisons are done per iteration step - one for the end 295condition of the loop using the iterators, and one inside 296``iterator_from_2d::operator++`` to determine whether we are at the end of a 297row. For fast operations, such as pixel copy, this second check adds about 29815% performance delay (measured for interleaved images on Intel platform). 299GIL overrides some STL algorithms, such as ``std::copy`` and ``std::fill``, 300when invoked with ``iterator_from_2d``-s, to go through each row using their 301base x-iterators, and, if the image has no padding (i.e. 302``iterator_from_2d::is_1d_traversable()`` returns true) to simply iterate 303using the x-iterators directly. 304
