[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[libcvd-members] libcvd/cvd vision.h morphology.h vision_excepti...
From: |
Edward Rosten |
Subject: |
[libcvd-members] libcvd/cvd vision.h morphology.h vision_excepti... |
Date: |
Tue, 29 Sep 2009 15:13:51 +0000 |
CVSROOT: /cvsroot/libcvd
Module name: libcvd
Changes by: Edward Rosten <edrosten> 09/09/29 15:13:51
Modified files:
cvd : vision.h
Added files:
cvd : morphology.h vision_exceptions.h
Log message:
Homogeneous morphology like operations. (erode, dilate, binary median).
No general median filter yet.
CVSWeb URLs:
http://cvs.savannah.gnu.org/viewcvs/libcvd/cvd/vision.h?cvsroot=libcvd&r1=1.32&r2=1.33
http://cvs.savannah.gnu.org/viewcvs/libcvd/cvd/morphology.h?cvsroot=libcvd&rev=1.1
http://cvs.savannah.gnu.org/viewcvs/libcvd/cvd/vision_exceptions.h?cvsroot=libcvd&rev=1.1
Patches:
Index: vision.h
===================================================================
RCS file: /cvsroot/libcvd/libcvd/cvd/vision.h,v
retrieving revision 1.32
retrieving revision 1.33
diff -u -b -r1.32 -r1.33
--- vision.h 23 Jul 2009 15:39:21 -0000 1.32
+++ vision.h 29 Sep 2009 15:13:51 -0000 1.33
@@ -25,7 +25,7 @@
#include <vector>
#include <memory>
-#include <cvd/exceptions.h>
+#include <cvd/vision_exceptions.h>
#include <cvd/image.h>
#include <cvd/internal/pixel_operations.h>
#include <cvd/utility.h>
@@ -36,38 +36,7 @@
#include <TooN/helpers.h>
#endif
-namespace CVD {
-
-namespace Exceptions {
-
- /// %Exceptions specific to vision algorithms
- /// @ingroup gException
- namespace Vision {
- /// Base class for all Image_IO exceptions
- /// @ingroup gException
- struct All: public CVD::Exceptions::All {};
-
- /// Input images have incompatible dimensions
- /// @ingroup gException
- struct IncompatibleImageSizes : public All {
- IncompatibleImageSizes(const std::string & function)
- {
- what = "Incompatible image sizes in " + function;
- };
- };
-
- /// Input ImageRef not within image dimensions
- /// @ingroup gException
- struct ImageRefNotInImage : public All {
- ImageRefNotInImage(const std::string & function)
- {
- what = "Input ImageRefs not in image in " + function;
- };
- };
- };
-};
-
-
+namespace CVD{
/** Subsamples an image to 2/3 of its size by averaging 3x3 blocks in to 2x2
blocks.
@param in input image
@param out output image (muze be <code>out.size() == in.size()/2*3 </code>)
Index: morphology.h
===================================================================
RCS file: morphology.h
diff -N morphology.h
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ morphology.h 29 Sep 2009 15:13:51 -0000 1.1
@@ -0,0 +1,445 @@
+#ifndef CVD_INCLUDE_MORPHOLOGY_H
+#define CVD_INCLUDE_MORPHOLOGY_H
+
+#include <cvd/vision_exceptions.h>
+#include <cvd/image.h>
+#include <map>
+#include <vector>
+
+
+namespace CVD
+{
+ namespace Internal
+ {
+ namespace MorphologyHelpers
+ {
+ using namespace std;
+
+ //Compute pointer offsets for a bunch of ImageRef
offsets.
+ template<class T> vector<ptrdiff_t> offsets(const
vector<ImageRef>& v, const SubImage<T>& s)
+ {
+ vector<ptrdiff_t> off;
+
+ for(unsigned int i=0; i < v.size(); i++)
+ off.push_back(v[i].x + v[i].y *
s.row_stride()-1);
+ return off;
+ }
+
+ //Split a list of ImageRefs up in to rows.
+ vector<vector<ImageRef> > row_split(const
vector<ImageRef>& v, int y_lo, int y_hi)
+ {
+ vector<vector<ImageRef> > rows(y_hi - y_lo + 1);
+
+ for(unsigned int i=0; i < v.size(); i++)
+ rows[v[i].y - y_lo].push_back(v[i]);
+
+ return rows;
+ }
+ }
+ }
+
+ /// Perform a morphological operation on the image.
+ ///
+ /// At the edge of the image, the structuring element is cropped to the
image
+ /// boundary. This function is for homogenous structuring elements, so
it is
+ /// suitable for erosion, dialtion and etc, not hit-and-miss and so on.
+ ///
+ /// For example:
+ /// @code
+ /// Image<byte> image, eroded;
+ /// vector<ImageRef> structuring_element = getDisc(10);
+ ///
+ /// ...
+ ///
+ /// morphology(image, structure_element, Erode<byte>(), eroded);
+ /// @endcode
+ ///
+ /// Morphology is performed efficiently using an incremental algorithm.
As the
+ /// structuring element is moved across the images, only pixels on it's
edge are
+ /// added and removed. Other morphological operators can be added by
creating a
+ /// class with the following methods:
+ ///
+ /// @code
+ /// template<class T> struct Operation
+ /// {
+ /// void insert(const T&); //Add a pixel
+ /// void remove(const T&); //Remove a pixel
+ /// void clear(const T&); //Remove all pixels
+ /// T get(); //Get the current value.
+ /// }
+ /// @endcode
+ ///
+ /// Grayscale erode could be implemented with a multiset to store and
remove pixels. Get would simply
+ /// return the first element in the multiset.
+ ///
+ /// @param in The source image.
+ /// @param selem The structuring element. See e.g. getDisc()
+ /// @param a_ The morphological operation to perform. See Morphology
+ /// @param out The destination image.
+ /// @ingroup gVision
+ template<class Accumulator, class T>
+ void morphology(const SubImage<T>& in, const std::vector<ImageRef>&
selem, const Accumulator& a_, SubImage<T>& out)
+ {
+ using Internal::MorphologyHelpers::offsets;
+ using Internal::MorphologyHelpers::row_split;
+ using std::min;
+ using std::max;
+ using std::vector;
+
+ if(in.size() != out.size())
+ throw
Exceptions::Vision::IncompatibleImageSizes(__FUNCTION__);
+
+ //Cases are:
+ //
+ // Small selem compared to image:
+ // Topleft corner, top row, top right corner
+ // left edge, centre, right edge
+ // etc
+
+ ////////////////////////////////////////////////////////////////
+ //Find the extents of the structuring element
+ int x_lo = selem[0].x;
+ int x_hi = selem[0].x;
+ int y_lo = selem[0].y;
+ int y_hi = selem[0].y;
+
+ for(unsigned int i=0; i < selem.size(); i++)
+ {
+ x_lo = min(x_lo, selem[i].x);
+ x_hi = max(x_hi, selem[i].x);
+ y_lo = min(y_lo, selem[i].y);
+ y_hi = max(y_hi, selem[i].y);
+ }
+
+
////////////////////////////////////////////////////////////////
+ //Shift the structure element by one and find the differeneces
+ vector<ImageRef> structure_element = selem;
+ vector<ImageRef> shifted;
+
+ sort(structure_element.begin(), structure_element.end());
+ for(unsigned int i=0; i < structure_element.size(); i++)
+ shifted.push_back(structure_element[i] + ImageRef(1,
0));
+
+ vector<ImageRef> add, remove;
+ set_difference(shifted.begin(), shifted.end(),
structure_element.begin(), structure_element.end(), back_inserter(add));
+ set_difference(structure_element.begin(),
structure_element.end(), shifted.begin(), shifted.end(), back_inserter(remove));
+
+
/////////////////////////////////////////////////////////////////
+ //
+ //Compute the integer offsets to pixels for speed;
+ vector<ptrdiff_t> add_off = offsets(add, in);
+ vector<ptrdiff_t> remove_off = offsets(remove, in);
+
+
+
/////////////////////////////////////////////////////////////////
+ //
+ // Split by rows, to make the top and bottom edges easier.
+ //
+ //Because of set operations, the ImageRefs are ordered within
each row.
+ vector<vector<ImageRef> > split_selem =
row_split(structure_element, y_lo, y_hi);
+ vector<vector<ImageRef> > split_add = row_split(add, y_lo,
y_hi);
+ vector<vector<ImageRef> > split_remove= row_split(remove, y_lo,
y_hi);
+
+ Accumulator acc(a_);
+ //If the image is at least as wide as the structuring element
+ if(x_hi - x_lo + 1 <= in.size().x)
+ for(int y=0; y < in.size().y; y++)
+ {
+ //Find the rows which overlap with the image.
Only work with these rows.
+ int startrow = max(0, - y_lo - y);
+ int endrow = split_selem.size() - max(0, y +
y_hi - in.size().y+1);
+
+ //Figure out the range of the "easy" bit.
+ int x_first_full = max(0, -x_lo);
//This is the first position at which we have a full kernel in
the image
+ int x_after_last_full = min(in.size().x,
in.size().x - x_hi); //This is one beyone the end of the position where the
last kernel fits in the image.
+
+ //Clear the accumulator
+ acc.clear();
+
+ //Fill in the accumulator sitting up against
the left hand side of the image.
+ for(int i=startrow; i < endrow; i++)
+ for(int j=(int)split_selem[i].size()-1;
j >=0 && split_selem[i][j].x >=0; j--)
+ acc.insert(in[y +
split_selem[i][0].y][split_selem[i][j].x]);
+
+ out[y][0] = acc.get();
+
+ //Shift the kernel until we get to the point
where
+ //we can start shifting the kernel without
testing to
+ //see it fits withing the image width.
+ for(int x=1; x <= x_first_full ; x++)
+ {
+ for(int i=startrow; i < endrow; i++)
+ for(int
j=(int)split_remove[i].size()-1; j >=0 && split_remove[i][j].x+x-1 >=0; j--)
+ acc.remove(in[y +
split_remove[i][0].y][x+split_remove[i][j].x-1]);
+
+ for(int i=startrow; i < endrow; i++)
+ for(int
j=(int)split_add[i].size()-1; j >=0 && split_add[i][j].x+x-1 >=0; j--)
+ acc.insert(in[y +
split_add[i][0].y][x+split_add[i][j].x-1]);
+
+ out[y][x] = acc.get();
+ }
+
+ //Go through the two incremental kernels to
figure out which
+ //indices are fit within the image. This
removes a test from
+ //the following shift section.
+ int add_start=0, add_end=0, remove_start=0,
remove_end=0;
+ for(int i=0; i < startrow; i++)
+ {
+ add_start+=split_add[i].size();
+ remove_start+=split_remove[i].size();
+ }
+ for(int i=0; i < endrow; i++)
+ {
+ add_end+=split_add[i].size();
+ remove_end+=split_remove[i].size();
+ }
+
+ //Shift the kernel in the area which requires
no tests.
+ for(int x=max(0, -x_lo+1); x <
x_after_last_full; x++)
+ {
+ for(int i=remove_start; i < remove_end;
i++)
+ acc.remove(*(in[y] + x +
remove_off[i]));
+
+ for(int i=add_start; i < add_end; i++)
+ acc.insert(*(in[y] + x +
add_off[i]));
+
+ out[y][x] = acc.get();
+ }
+
+ //Now perform the right hand edge
+ for(int x=x_after_last_full; x < in.size().x ;
x++)
+ {
+ for(int i=startrow; i < endrow; i++)
+ for(int j=0; j <
(int)split_remove[i].size() && split_remove[i][j].x+x-1 < in.size().x; j++)
+ acc.remove(in[y +
split_remove[i][0].y][x+split_remove[i][j].x-1]);
+
+ for(int i=startrow; i < endrow; i++)
+ for(int j=0; j <
(int)split_add[i].size() && split_add[i][j].x+x-1 < in.size().x; j++)
+ acc.insert(in[y +
split_add[i][0].y][x+split_add[i][j].x-1]);
+
+ out[y][x] = acc.get();
+ }
+ }
+ else
+ {
+ //The image is too narrow to have a clear area in the
middle.
+
+ for(int y=0; y < in.size().y; y++)
+ {
+ //Find the rows which overlap with the image.
Only work with these rows.
+ int startrow = max(0, - y_lo - y);
+ int endrow = split_selem.size() - max(0, y +
y_hi - in.size().y+1);
+
+ //Clear the accumulator
+ acc.clear();
+
+ //Fill in the accumulator sitting up against
the left hand side of the image.
+ for(int i=startrow; i < endrow; i++)
+ for(int j=0; j <
(int)split_selem[i].size(); j++)
+ {
+ int xp = split_selem[i][j].x;
+ if(xp >= 0 && xp < in.size().x)
+ acc.insert(in[y +
split_selem[i][0].y][xp]);
+ }
+
+ out[y][0] = acc.get();
+
+ //Shift the kernel using the incrementals
+ for(int x=1; x < in.size().x ; x++)
+ {
+ for(int i=startrow; i < endrow; i++)
+ for(int j=0; j <
(int)split_remove[i].size(); j++)
+ {
+ int xp = x +
split_remove[i][j].x - 1;
+ if(xp >= 0 && xp <
in.size().x)
+ acc.remove(in[y
+ split_add[i][0].y][xp]);
+ }
+
+ for(int i=startrow; i < endrow; i++)
+ for(int j=0; j <
(int)split_add[i].size(); j++)
+ {
+ int xp = x +
split_add[i][j].x - 1;
+ if(xp >= 0 && xp <
in.size().x)
+ acc.insert(in[y
+ split_add[i][0].y][xp]);
+ }
+
+ out[y][x] = acc.get();
+ }
+ }
+ }
+ }
+
+ #ifndef DOXYGEN_IGNORE_INTERNAL
+ namespace Internal
+ {
+ template<class C, class D> class PerformMorphology{};
+
+ template<class C, class D> struct
ImagePromise<PerformMorphology<C, D> >
+ {
+ ImagePromise(const SubImage<C>& im, const D&
acc, const std::vector<ImageRef>& s_)
+ :i(im),a(acc),s(s_)
+ {}
+
+ const SubImage<C>& i;
+ const D& a;
+ const std::vector<ImageRef>& s;
+
+ template<class E> void execute(Image<E>& j)
+ {
+ j.resize(i.size());
+ morphology(i, s, a, j);
+ }
+ };
+ };
+
+ template<class C, class D>
Internal::ImagePromise<Internal::PerformMorphology<C, D> > morphology(const
SubImage<C>& c, const std::vector<ImageRef>& selem, const D& a)
+ {
+ return
Internal::ImagePromise<Internal::PerformMorphology<C, D> >(c, a, selem);
+ }
+ #else
+
+ /// Perform a morphological operation on the image.
+ ///
+ /// @param in The source image.
+ /// @param selem The structuring element. See e.g. getDisc()
+ /// @param a_ The morphological operation to perform. See
Morphology
+ /// @param out The destination image.
+ /// @ingroup gVision
+ Image<T> morphology(const SubImage<T>& in, const
std::vector<ImageRef>& selem, const Accumulator& a_);
+
+ #endif
+
+ ///Image morphology operations
+ ///@ingroup gVision
+ namespace Morphology
+ {
+ ///A helper class for performing basic grayscale morphology
+ ///on an image. The comparator determines the ordering, and
hence
+ ///the morphological operation. See morphology().
+ ///@ingroup gVision
+ template<class T, template<class> class Cmp> struct BasicGray
+ {
+ private:
+ std::map<T, int, Cmp<T> > pix;
+
+ public:
+ void clear()
+ {
+ pix.clear();
+ }
+ void insert(const T& t)
+ {
+ pix[t]++;
+ }
+
+ void remove(const T& t)
+ {
+ --pix[t];
+ }
+
+ T get()
+ {
+ assert(pix.begin()->second);
+
+ typedef typename std::map<T, int,
Cmp<T> >::iterator it;
+
+ for(it i=pix.begin(); i != pix.end();)
+ {
+ it old = i;
+ i++;
+
+ if(old->second == 0)
+ pix.erase(old);
+ else
+ return old->first;
+ }
+
+ assert(0);
+ return 0;
+ }
+ };
+
+
+ ///Class for performing geryscale erosion. See morphology().
+ ///@ingroup gVision
+ template<class T> class Erode: public BasicGray<T, std::less>
+ {
+ };
+
+
+ ///Class for performing geryscale dilation. See morphology().
+ ///@ingroup gVision
+ template<class T> class Dilate: public BasicGray<T,
std::greater>
+ {
+ };
+
+ ///Class for performing binary morphology. This class is
incomplete and
+ ///used to build actual functions such as BinaryErode,
BinaryDilate and BinaryMedian. See morphology().
+ ///@ingroup gVision
+ template<class T> struct BasicBinary
+ {
+ int t, f;
+ BasicBinary()
+ :t(0),f(0)
+ {}
+
+ void insert(bool b)
+ {
+ if(b)
+ t++;
+ else
+ f++;
+ }
+
+ void remove(bool b)
+ {
+ if(b)
+ t--;
+ else
+ f--;
+ }
+
+ void clear()
+ {
+ t=f=0;
+ }
+ };
+
+ ///Class for performing binary erosion. See morphology().
+ ///@ingroup gVision
+ template<class T=bool> struct BinaryErode : public
BasicBinary<T>
+ {
+ using BasicBinary<T>::f;
+ T get()
+ {
+ return !f;
+ }
+ };
+
+ ///Class for performing binary dilation. See morphology().
+ ///@ingroup gVision
+ template<class T=bool> struct BinaryDilate : public
BasicBinary<T>
+ {
+ using BasicBinary<T>::t;
+ T get()
+ {
+ return t!= 0;
+ }
+ };
+
+ ///Class for performing binary median filtering. See
morphology().
+ ///@ingroup gVision
+ template<class T=bool> struct BinaryMedian : public
BasicBinary<T>
+ {
+ using BasicBinary<T>::t;
+ using BasicBinary<T>::f;
+ T get()
+ {
+ return (t > f);
+ }
+ };
+ }
+
+}
+
+#endif
Index: vision_exceptions.h
===================================================================
RCS file: vision_exceptions.h
diff -N vision_exceptions.h
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ vision_exceptions.h 29 Sep 2009 15:13:51 -0000 1.1
@@ -0,0 +1,39 @@
+#ifndef CVD_INCLUDE_VISION_EXCEPTIONS_H
+#define CVD_INCLUDE_VISION_EXCEPTIONS_H
+
+#include <cvd/exceptions.h>
+
+namespace CVD {
+
+ namespace Exceptions {
+
+ /// %Exceptions specific to vision algorithms
+ /// @ingroup gException
+ namespace Vision {
+ /// Base class for all Image_IO exceptions
+ /// @ingroup gException
+ struct All: public CVD::Exceptions::All {};
+
+ /// Input images have incompatible dimensions
+ /// @ingroup gException
+ struct IncompatibleImageSizes : public All {
+ IncompatibleImageSizes(const std::string &
function)
+ {
+ what = "Incompatible image sizes in " +
function;
+ };
+ };
+
+ /// Input ImageRef not within image dimensions
+ /// @ingroup gException
+ struct ImageRefNotInImage : public All {
+ ImageRefNotInImage(const std::string & function)
+ {
+ what = "Input ImageRefs not in image in
" + function;
+ };
+ };
+ };
+ }
+}
+
+#endif
+
[Prev in Thread] |
Current Thread |
[Next in Thread] |
- [libcvd-members] libcvd/cvd vision.h morphology.h vision_excepti...,
Edward Rosten <=