coco
360 lines
11 KiB
C++
360 lines
11 KiB
C++
// Copyright (C) 2011 Davis E. King (davis@dlib.net)
|
|
// License: Boost Software License See LICENSE.txt for the full license.
|
|
#ifndef DLIB_LABEL_CONNeCTED_BLOBS_H_
|
|
#define DLIB_LABEL_CONNeCTED_BLOBS_H_
|
|
|
|
#include "label_connected_blobs_abstract.h"
|
|
#include "../geometry.h"
|
|
#include <stack>
|
|
#include <vector>
|
|
#include "thresholding.h"
|
|
#include "assign_image.h"
|
|
#include <queue>
|
|
|
|
namespace dlib
|
|
{
|
|
|
|
// ----------------------------------------------------------------------------------------
|
|
|
|
struct neighbors_24
|
|
{
|
|
void operator() (
|
|
const point& p,
|
|
std::vector<point>& neighbors
|
|
) const
|
|
{
|
|
for (long i = -2; i <= 2; ++i)
|
|
for (long j = -2; j <= 2; ++j)
|
|
if (i!=0||j!=0)
|
|
neighbors.push_back(point(p.x()+i,p.y()+j));
|
|
}
|
|
};
|
|
|
|
struct neighbors_8
|
|
{
|
|
void operator() (
|
|
const point& p,
|
|
std::vector<point>& neighbors
|
|
) const
|
|
{
|
|
neighbors.push_back(point(p.x()+1,p.y()+1));
|
|
neighbors.push_back(point(p.x()+1,p.y() ));
|
|
neighbors.push_back(point(p.x()+1,p.y()-1));
|
|
|
|
neighbors.push_back(point(p.x(),p.y()+1));
|
|
neighbors.push_back(point(p.x(),p.y()-1));
|
|
|
|
neighbors.push_back(point(p.x()-1,p.y()+1));
|
|
neighbors.push_back(point(p.x()-1,p.y() ));
|
|
neighbors.push_back(point(p.x()-1,p.y()-1));
|
|
}
|
|
};
|
|
|
|
struct neighbors_4
|
|
{
|
|
void operator() (
|
|
const point& p,
|
|
std::vector<point>& neighbors
|
|
) const
|
|
{
|
|
neighbors.push_back(point(p.x()+1,p.y()));
|
|
neighbors.push_back(point(p.x()-1,p.y()));
|
|
neighbors.push_back(point(p.x(),p.y()+1));
|
|
neighbors.push_back(point(p.x(),p.y()-1));
|
|
}
|
|
};
|
|
|
|
// ----------------------------------------------------------------------------------------
|
|
|
|
struct connected_if_both_not_zero
|
|
{
|
|
template <typename image_type>
|
|
bool operator() (
|
|
const image_type& img,
|
|
const point& a,
|
|
const point& b
|
|
) const
|
|
{
|
|
return (img[a.y()][a.x()] != 0 && img[b.y()][b.x()] != 0);
|
|
}
|
|
};
|
|
|
|
struct connected_if_equal
|
|
{
|
|
template <typename image_type>
|
|
bool operator() (
|
|
const image_type& img,
|
|
const point& a,
|
|
const point& b
|
|
) const
|
|
{
|
|
return (img[a.y()][a.x()] == img[b.y()][b.x()]);
|
|
}
|
|
};
|
|
|
|
// ----------------------------------------------------------------------------------------
|
|
|
|
struct zero_pixels_are_background
|
|
{
|
|
template <typename image_type>
|
|
bool operator() (
|
|
const image_type& img,
|
|
const point& p
|
|
) const
|
|
{
|
|
return img[p.y()][p.x()] == 0;
|
|
}
|
|
|
|
};
|
|
|
|
struct nothing_is_background
|
|
{
|
|
template <typename image_type>
|
|
bool operator() (
|
|
const image_type&,
|
|
const point&
|
|
) const
|
|
{
|
|
return false;
|
|
}
|
|
|
|
};
|
|
|
|
// ----------------------------------------------------------------------------------------
|
|
|
|
template <
|
|
typename image_type,
|
|
typename label_image_type,
|
|
typename background_functor_type,
|
|
typename neighbors_functor_type,
|
|
typename connected_functor_type
|
|
>
|
|
unsigned long label_connected_blobs (
|
|
const image_type& img_,
|
|
const background_functor_type& is_background,
|
|
const neighbors_functor_type& get_neighbors,
|
|
const connected_functor_type& is_connected,
|
|
label_image_type& label_img_
|
|
)
|
|
{
|
|
// make sure requires clause is not broken
|
|
DLIB_ASSERT(is_same_object(img_, label_img_) == false,
|
|
"\t unsigned long label_connected_blobs()"
|
|
<< "\n\t The input image and output label image can't be the same object."
|
|
);
|
|
|
|
const_image_view<image_type> img(img_);
|
|
image_view<label_image_type> label_img(label_img_);
|
|
|
|
std::stack<point> neighbors;
|
|
label_img.set_size(img.nr(), img.nc());
|
|
assign_all_pixels(label_img, 0);
|
|
unsigned long next = 1;
|
|
|
|
if (img.size() == 0)
|
|
return 0;
|
|
|
|
const rectangle area = get_rect(img);
|
|
|
|
std::vector<point> window;
|
|
|
|
for (long r = 0; r < img.nr(); ++r)
|
|
{
|
|
for (long c = 0; c < img.nc(); ++c)
|
|
{
|
|
// skip already labeled pixels or background pixels
|
|
if (label_img[r][c] != 0 || is_background(img,point(c,r)))
|
|
continue;
|
|
|
|
label_img[r][c] = next;
|
|
|
|
// label all the neighbors of this point
|
|
neighbors.push(point(c,r));
|
|
while (neighbors.size() > 0)
|
|
{
|
|
const point p = neighbors.top();
|
|
neighbors.pop();
|
|
|
|
window.clear();
|
|
get_neighbors(p, window);
|
|
|
|
for (unsigned long i = 0; i < window.size(); ++i)
|
|
{
|
|
if (area.contains(window[i]) && // point in image.
|
|
!is_background(img,window[i]) && // isn't background.
|
|
label_img[window[i].y()][window[i].x()] == 0 && // haven't already labeled it.
|
|
is_connected(img, p, window[i])) // it's connected.
|
|
{
|
|
label_img[window[i].y()][window[i].x()] = next;
|
|
neighbors.push(window[i]);
|
|
}
|
|
}
|
|
}
|
|
|
|
++next;
|
|
}
|
|
}
|
|
|
|
return next;
|
|
}
|
|
|
|
// ----------------------------------------------------------------------------------------
|
|
|
|
template <
|
|
typename in_image_type,
|
|
typename out_image_type
|
|
>
|
|
unsigned long label_connected_blobs_watershed (
|
|
const in_image_type& img_,
|
|
out_image_type& labels_,
|
|
typename pixel_traits<typename image_traits<in_image_type>::pixel_type>::basic_pixel_type background_thresh,
|
|
const double smoothing = 0
|
|
)
|
|
{
|
|
// make sure requires clause is not broken
|
|
DLIB_ASSERT(is_same_object(img_, labels_) == false,
|
|
"\t unsigned long segment_image_watersheds()"
|
|
<< "\n\t The input images can't be the same object."
|
|
);
|
|
|
|
using label_pixel_type = typename image_traits<out_image_type>::pixel_type;
|
|
|
|
DLIB_ASSERT(smoothing >= 0);
|
|
COMPILE_TIME_ASSERT(is_unsigned_type<label_pixel_type>::value);
|
|
|
|
|
|
struct watershed_points
|
|
{
|
|
watershed_points() = default;
|
|
watershed_points(const point& p_, float score_, label_pixel_type label_): p(p_), score(score_), label(label_) {}
|
|
|
|
point p;
|
|
float score = 0;
|
|
label_pixel_type label = std::numeric_limits<label_pixel_type>::max();
|
|
|
|
bool is_seed() const { return label == std::numeric_limits<label_pixel_type>::max(); }
|
|
|
|
bool operator< (const watershed_points& rhs) const
|
|
{
|
|
// If two pixels have the same score then we take the one with the smallest
|
|
// label out of the priority queue first. We do this so that seed points
|
|
// that are downhill from some larger blob will be consumed by it if they
|
|
// haven't grown before the larger blob's flooding reaches them. Doing
|
|
// this helps a lot to avoid spuriously splitting blobs.
|
|
if (score == rhs.score)
|
|
{
|
|
return label > rhs.label;
|
|
}
|
|
return score < rhs.score;
|
|
}
|
|
|
|
};
|
|
|
|
const_image_view<in_image_type> img(img_);
|
|
image_view<out_image_type> labels(labels_);
|
|
|
|
labels.set_size(img.nr(), img.nc());
|
|
// Initially, all pixels have the background label of 0.
|
|
assign_all_pixels(labels, 0);
|
|
|
|
std::priority_queue<watershed_points> next;
|
|
|
|
|
|
// Note that we never blur the image values we use to check against the
|
|
// background_thresh. We do however blur, if smoothing!=0, the pixel values used
|
|
// to do the watershed.
|
|
in_image_type img2_;
|
|
if (smoothing != 0)
|
|
gaussian_blur(img_, img2_, smoothing);
|
|
const_image_view<in_image_type> img2view(img2_);
|
|
// point us at img2 if we are doing smoothing, otherwise point us at the input
|
|
// image.
|
|
const auto& img2 = smoothing!=0?img2view:img;
|
|
|
|
// first find all the local maxima
|
|
for (long r = 1; r+1 < img.nr(); ++r)
|
|
{
|
|
for (long c = 1; c+1 < img.nc(); ++c)
|
|
{
|
|
|
|
if (img[r][c] < background_thresh)
|
|
continue;
|
|
|
|
auto val = img2[r][c];
|
|
// if img2[r][c] isn't a local maximum then skip it
|
|
if (val < img2[r+1][c] ||
|
|
val < img2[r-1][c] ||
|
|
val < img2[r][c+1] ||
|
|
val < img2[r][c-1]
|
|
)
|
|
{
|
|
continue;
|
|
}
|
|
|
|
next.push(watershed_points(point(c,r), val, std::numeric_limits<label_pixel_type>::max()));
|
|
}
|
|
}
|
|
|
|
|
|
const rectangle area = get_rect(img);
|
|
|
|
|
|
label_pixel_type next_label = 1;
|
|
|
|
|
|
std::vector<point> neighbors;
|
|
neighbors_8 get_neighbors;
|
|
while(next.size() > 0)
|
|
{
|
|
auto p = next.top();
|
|
next.pop();
|
|
|
|
label_pixel_type label;
|
|
// If the next pixel is a seed of a new blob and is still labeled as a
|
|
// background pixel (i.e. it hasn't been flooded over by a neighboring blob and
|
|
// consumed by it) then we create a new label for this new blob.
|
|
if (p.is_seed() && labels[p.p.y()][p.p.x()] == 0)
|
|
{
|
|
label = next_label++;
|
|
labels[p.p.y()][p.p.x()] = label;
|
|
}
|
|
else
|
|
{
|
|
label = p.label;
|
|
}
|
|
|
|
|
|
neighbors.clear();
|
|
get_neighbors(p.p, neighbors);
|
|
for (auto& n : neighbors)
|
|
{
|
|
if (!area.contains(n) || labels[n.y()][n.x()] != 0 || img[n.y()][n.x()] < background_thresh)
|
|
continue;
|
|
|
|
labels[n.y()][n.x()] = label;
|
|
next.push(watershed_points(n, img2[n.y()][n.x()], label));
|
|
}
|
|
}
|
|
|
|
return next_label;
|
|
}
|
|
|
|
template <
|
|
typename in_image_type,
|
|
typename out_image_type
|
|
>
|
|
unsigned long label_connected_blobs_watershed (
|
|
const in_image_type& img,
|
|
out_image_type& labels
|
|
)
|
|
{
|
|
return label_connected_blobs_watershed(img, labels, partition_pixels(img));
|
|
}
|
|
|
|
// ----------------------------------------------------------------------------------------
|
|
|
|
}
|
|
|
|
#endif // DLIB_LABEL_CONNeCTED_BLOBS_H_
|
|
|