dlib C++ Library - scan_image.cpp

// Copyright (C) 2011 Davis E. King (davis@dlib.net)
// License: Boost Software License See LICENSE.txt for the full license.
#include <sstream>
#include <string>
#include <cstdlib>
#include <ctime>
#include "dlib/image_processing.h"
#include "dlib/test/tester.h"
#include "dlib/image_transforms.h"
#include "dlib/pixel.h"
#include "dlib/array2d.h"
#include "dlib/array.h"
// ----------------------------------------------------------------------------------------
namespace 
{
 using namespace test;
 using namespace dlib;
 using namespace std;
 using dlib::array;
 // Declare the logger we will use in this test. The name of the tester 
 // should start with "test."
 logger dlog("test.scan_image");
// ----------------------------------------------------------------------------------------
 template <typename image_type1, typename image_type2>
 void sum_filter_i (
 const image_type1& img,
 image_type2& out,
 const rectangle& rect
 )
 {
 typedef typename image_type1::type pixel_type;
 typedef typename promote<pixel_type>::type ptype;
 integral_image_generic<ptype> iimg;
 iimg.load(img);
 for (long r = 0; r < img.nr(); ++r)
 {
 for (long c = 0; c < img.nc(); ++c)
 {
 const rectangle temp = translate_rect(rect, point(c,r)).intersect(get_rect(iimg));
 if (temp.is_empty() == false)
 out[r][c] += iimg.get_sum_of_area(temp);
 }
 }
 }
// ----------------------------------------------------------------------------------------
 template <
 typename image_array_type
 >
 void scan_image_i (
 std::vector<std::pair<double, point> >& dets,
 const image_array_type& images,
 const std::vector<std::pair<unsigned int, rectangle> >& rects,
 const double thresh,
 const unsigned long max_dets
 )
 {
 typedef typename image_array_type::type::type pixel_type;
 typedef typename promote<pixel_type>::type ptype;
 array<integral_image_generic<ptype> > iimg;
 iimg.set_max_size(images.size());
 iimg.set_size(images.size());
 for (unsigned long i = 0; i < iimg.size(); ++i)
 iimg[i].load(images[i]);
 dets.clear();
 for (long r = 0; r < images[0].nr(); ++r)
 {
 for (long c = 0; c < images[0].nc(); ++c)
 {
 ptype temp = 0;
 for (unsigned long i = 0; i < rects.size(); ++i)
 {
 rectangle rtemp = translate_rect(rects[i].second,point(c,r)).intersect(get_rect(images[0]));
 if (rtemp.is_empty() == false)
 temp += iimg[rects[i].first].get_sum_of_area(rtemp);
 }
 if (temp > thresh)
 {
 dets.push_back(std::make_pair(temp, point(c,r)));
 if (dets.size() >= max_dets)
 return;
 }
 }
 }
 }
// ----------------------------------------------------------------------------------------
 template <
 typename image_array_type
 >
 void scan_image_old (
 std::vector<std::pair<double, point> >& dets,
 const image_array_type& images,
 const std::vector<std::pair<unsigned int, rectangle> >& rects,
 const double thresh,
 const unsigned long max_dets
 )
 {
 dets.clear();
 if (max_dets == 0)
 return;
 typedef typename image_array_type::type::type pixel_type;
 typedef typename promote<pixel_type>::type ptype;
 std::vector<std::vector<ptype> > column_sums(rects.size());
 for (unsigned long i = 0; i < column_sums.size(); ++i)
 {
 const typename image_array_type::type& img = images[rects[i].first];
 column_sums[i].resize(img.nc() + rects[i].second.width(),0);
 const long top = -1 + rects[i].second.top();
 const long bottom = -1 + rects[i].second.bottom();
 long left = rects[i].second.left()-1;
 // initialize column_sums[i] at row -1
 for (unsigned long j = 0; j < column_sums[i].size(); ++j)
 {
 rectangle strip(left,top,left,bottom);
 strip = strip.intersect(get_rect(img));
 if (!strip.is_empty())
 {
 column_sums[i][j] = sum(matrix_cast<ptype>(subm(mat(img),strip)));
 }
 ++left;
 }
 }
 const rectangle area = get_rect(images[0]);
 for (long r = 0; r < images[0].nr(); ++r)
 {
 // set to sum at point(-1,r). i.e. should be equal to sum_of_rects_in_images(images, rects, point(-1,r))
 // We compute it's value in the next loop.
 ptype cur_sum = 0;
 
 // Update the first part of column_sums since we only work on the c+width part of column_sums
 // in the main loop.
 for (unsigned long i = 0; i < rects.size(); ++i)
 {
 const typename image_array_type::type& img = images[rects[i].first];
 const long top = r + rects[i].second.top() - 1;
 const long bottom = r + rects[i].second.bottom();
 const long width = rects[i].second.width();
 for (long k = 0; k < width; ++k)
 {
 const long right = k-width + rects[i].second.right();
 const ptype br_corner = area.contains(right,bottom) ? img[bottom][right] : 0;
 const ptype tr_corner = area.contains(right,top) ? img[top][right] : 0;
 // update the sum in this column now that we are on the next row
 column_sums[i][k] = column_sums[i][k] + br_corner - tr_corner;
 cur_sum += column_sums[i][k];
 }
 }
 for (long c = 0; c < images[0].nc(); ++c)
 {
 for (unsigned long i = 0; i < rects.size(); ++i)
 {
 const typename image_array_type::type& img = images[rects[i].first];
 const long top = r + rects[i].second.top() - 1;
 const long bottom = r + rects[i].second.bottom();
 const long right = c + rects[i].second.right();
 const long width = rects[i].second.width();
 const ptype br_corner = area.contains(right,bottom) ? img[bottom][right] : 0;
 const ptype tr_corner = area.contains(right,top) ? img[top][right] : 0;
 // update the sum in this column now that we are on the next row
 column_sums[i][c+width] = column_sums[i][c+width] + br_corner - tr_corner;
 // add in the new right side of the rect and subtract the old right side.
 cur_sum = cur_sum + column_sums[i][c+width] - column_sums[i][c];
 
 }
 if (cur_sum > thresh)
 {
 dets.push_back(std::make_pair(cur_sum, point(c,r)));
 if (dets.size() >= max_dets)
 return;
 }
 }
 }
 }
// ----------------------------------------------------------------------------------------
 void run_test1()
 {
 dlog << LINFO << "run_test1()";
 print_spinner();
 array2d<unsigned char> img, temp_img;
 img.set_size(600,600);
 assign_all_pixels(img,0);
 rectangle rect = centered_rect(10,10,5,5);
 dlog << LTRACE << "expected: 10,10";
 fill_rect(img, rect, 255); 
 array<array2d<unsigned char> > images;
 std::vector<std::pair<unsigned int, rectangle> > rects;
 for (int i = 0; i < 10; ++i)
 {
 assign_image(temp_img, img);
 images.push_back(temp_img);
 rects.push_back(make_pair(i,centered_rect(0,0,5,5)));
 }
 std::vector<std::pair<double, point> > dets, dets2, dets3;
 dlog << LTRACE << "best score: "<< sum_of_rects_in_images(images,rects,point(10,10));
 scan_image(dets,images,rects,30000, 100);
 scan_image_i(dets2,images,rects,30000, 100);
 scan_image_old(dets3,images,rects,30000, 100);
 dlog << LTRACE << "dets.size(): "<< dets.size();
 dlog << LTRACE << "dets2.size(): "<< dets2.size();
 dlog << LTRACE << "dets3.size(): "<< dets3.size();
 DLIB_TEST(dets.size() == dets2.size());
 DLIB_TEST(dets.size() == dets3.size());
 for (unsigned long i = 0; i < dets.size(); ++i)
 {
 //dlog << LTRACE << "dets["<<i<<"]: " << dets[i].second << " -> " << dets[i].first;
 //dlog << LTRACE << "dets2["<<i<<"]: " << dets2[i].second << " -> " << dets2[i].first;
 //dlog << LTRACE << "dets3["<<i<<"]: " << dets3[i].second << " -> " << dets3[i].first;
 DLIB_TEST(sum_of_rects_in_images(images, rects, dets[i].second) == dets[i].first);
 DLIB_TEST(sum_of_rects_in_images(images, rects, dets2[i].second) == dets2[i].first);
 DLIB_TEST(sum_of_rects_in_images(images, rects, dets3[i].second) == dets3[i].first);
 }
 }
// ----------------------------------------------------------------------------------------
 void run_test2()
 {
 print_spinner();
 dlog << LINFO << "run_test2()";
 array2d<unsigned char> img, temp_img;
 img.set_size(600,600);
 assign_all_pixels(img,0);
 rectangle rect = centered_rect(10,11,5,6);
 dlog << LTRACE << "expected: 10,11";
 fill_rect(img, rect, 255); 
 array<array2d<unsigned char> > images;
 std::vector<std::pair<unsigned int, rectangle> > rects;
 for (int i = 0; i < 10; ++i)
 {
 assign_image(temp_img, img);
 images.push_back(temp_img);
 rects.push_back(make_pair(i,centered_rect(0,0,5,5)));
 rects.push_back(make_pair(i,centered_rect(3,2,5,6)));
 }
 std::vector<std::pair<double, point> > dets, dets2, dets3;
 scan_image(dets,images,rects,30000, 100);
 scan_image_i(dets2,images,rects,30000, 100);
 scan_image_old(dets3,images,rects,30000, 100);
 dlog << LTRACE << "dets.size(): "<< dets.size();
 dlog << LTRACE << "dets2.size(): "<< dets2.size();
 dlog << LTRACE << "dets3.size(): "<< dets3.size();
 DLIB_TEST(dets.size() == dets2.size());
 DLIB_TEST(dets.size() == dets3.size());
 for (unsigned long i = 0; i < dets.size(); ++i)
 {
 //dlog << LTRACE << "dets["<<i<<"]: " << dets[i].second << " -> " << dets[i].first;
 //dlog << LTRACE << "dets2["<<i<<"]: " << dets2[i].second << " -> " << dets2[i].first;
 //dlog << LTRACE << "dets3["<<i<<"]: " << dets3[i].second << " -> " << dets3[i].first;
 DLIB_TEST(sum_of_rects_in_images(images, rects, dets[i].second) == dets[i].first);
 DLIB_TEST(sum_of_rects_in_images(images, rects, dets2[i].second) == dets2[i].first);
 DLIB_TEST(sum_of_rects_in_images(images, rects, dets3[i].second) == dets3[i].first);
 }
 }
// ----------------------------------------------------------------------------------------
 template <typename pixel_type>
 void run_test3(const double thresh)
 {
 dlog << LINFO << "running run_test3("<<thresh<<")";
 dlib::rand rnd;
 rnd.set_seed("235");
 array<array2d<pixel_type> > images;
 images.resize(1);
 images[0].set_size(200,180);
 for (int iter = 0; iter < 50; ++iter)
 {
 print_spinner();
 assign_all_pixels(images[0], thresh - 0.0001);
 for (int i = 0; i < 20; ++i)
 {
 point p1(rnd.get_random_32bit_number()%images[0].nc(),
 rnd.get_random_32bit_number()%images[0].nr());
 point p2(rnd.get_random_32bit_number()%images[0].nc(),
 rnd.get_random_32bit_number()%images[0].nr());
 rectangle rect(p1,p2);
 fill_rect(images[0], rect, static_cast<pixel_type>(rnd.get_random_double()*10 - 5));
 }
 std::vector<std::pair<unsigned int, rectangle> > rects;
 rects.push_back(make_pair(0,centered_rect(0,0,1+rnd.get_random_32bit_number()%40,1+rnd.get_random_32bit_number()%40)));
 rects.push_back(make_pair(0,centered_rect(0,0,1+rnd.get_random_32bit_number()%40,1+rnd.get_random_32bit_number()%40)));
 std::vector<std::pair<double, point> > dets, dets2, dets3;
 scan_image(dets,images,rects,thresh, 100);
 scan_image_i(dets2,images,rects,thresh, 100);
 scan_image_old(dets3,images,rects,thresh, 100);
 dlog << LTRACE << "dets.size(): "<< dets.size();
 dlog << LTRACE << "dets2.size(): "<< dets2.size();
 dlog << LTRACE << "dets3.size(): "<< dets3.size();
 DLIB_TEST(dets.size() == dets2.size());
 DLIB_TEST(dets.size() == dets3.size());
 for (unsigned long i = 0; i < dets.size(); ++i)
 {
 //dlog << LTRACE << "dets["<<i<<"]: " << dets[i].second << " -> " << dets[i].first;
 //dlog << LTRACE << "dets2["<<i<<"]: " << dets2[i].second << " -> " << dets2[i].first;
 //dlog << LTRACE << "dets3["<<i<<"]: " << dets3[i].second << " -> " << dets3[i].first;
 DLIB_TEST_MSG(std::abs(sum_of_rects_in_images(images, rects, dets[i].second) - dets[i].first) < 1e-6,
 "error: "<< sum_of_rects_in_images(images, rects, dets[i].second) - dets[i].first
 << " dets["<<i<<"].second: " << dets[i].second
 );
 DLIB_TEST_MSG(std::abs(sum_of_rects_in_images(images, rects, dets2[i].second) - dets2[i].first) < 1e-6,
 sum_of_rects_in_images(images, rects, dets2[i].second) - dets2[i].first
 );
 DLIB_TEST_MSG(std::abs(sum_of_rects_in_images(images, rects, dets3[i].second) - dets3[i].first) < 1e-6,
 "error: "<< sum_of_rects_in_images(images, rects, dets3[i].second) - dets3[i].first
 << " dets3["<<i<<"].first: " << dets3[i].first
 << " dets3["<<i<<"].second: " << dets3[i].second
 );
 }
 }
 }
// ----------------------------------------------------------------------------------------
 template <typename pixel_type>
 void test_sum_filter (
 )
 {
 dlib::rand rnd;
 for (int k = 0; k < 20; ++k)
 {
 print_spinner();
 array2d<pixel_type> img(1 + rnd.get_random_32bit_number()%100,
 1 + rnd.get_random_32bit_number()%100);
 for (long r = 0; r < img.nr(); ++r)
 {
 for (long c = 0; c < img.nc(); ++c)
 {
 img[r][c] = static_cast<pixel_type>(100*(rnd.get_random_double()-0.5));
 }
 }
 array2d<long> test1(img.nr(), img.nc());
 array2d<double> test2(img.nr(), img.nc());
 array2d<long> test1_i(img.nr(), img.nc());
 array2d<double> test2_i(img.nr(), img.nc());
 assign_all_pixels(test1, 0);
 assign_all_pixels(test2, 0);
 assign_all_pixels(test1_i, 0);
 assign_all_pixels(test2_i, 0);
 for (int i = 0; i < 10; ++i)
 {
 const long width = rnd.get_random_32bit_number()%10 + 1;
 const long height = rnd.get_random_32bit_number()%10 + 1;
 const point p(rnd.get_random_32bit_number()%img.nc(),
 rnd.get_random_32bit_number()%img.nr());
 const rectangle rect = centered_rect(p, width, height);
 sum_filter(img, test1, rect);
 sum_filter(img, test2, rect);
 sum_filter(img, test1_i, rect);
 sum_filter(img, test2_i, rect);
 DLIB_TEST(mat(test1) == mat(test1_i));
 DLIB_TEST(mat(test2) == mat(test2_i));
 }
 }
 }
// ----------------------------------------------------------------------------------------
 template <
 typename image_type1, 
 typename image_type2
 >
 void naive_max_filter (
 const image_type1& img,
 image_type2& out,
 const long width,
 const long height,
 typename image_type1::type thresh
 )
 {
 const rectangle area = get_rect(img);
 for (long r = 0; r < img.nr(); ++r)
 {
 for (long c = 0; c < img.nc(); ++c)
 {
 const rectangle win = centered_rect(point(c,r),width,height).intersect(area);
 out[r][c] += std::max(dlib::max(subm(mat(img),win)), thresh);
 }
 }
 }
// ----------------------------------------------------------------------------------------
 void test_max_filter(long rows, long cols, long width, long height, dlib::rand& rnd)
 {
 array2d<int> img(rows, cols);
 rectangle rect = centered_rect(0,0, width, height);
 array2d<int> out(img.nr(),img.nc());
 assign_all_pixels(out, 0);
 array2d<int> out2(img.nr(),img.nc());
 assign_all_pixels(out2, 0);
 for (long r = 0; r < img.nr(); ++r)
 {
 for (long c = 0; c < img.nc(); ++c)
 {
 img[r][c] = rnd.get_random_32bit_number();
 }
 }
 const int thresh = rnd.get_random_32bit_number();
 naive_max_filter(img, out2, rect.width(), rect.height(), thresh);
 max_filter(img, out, rect.width(), rect.height(), thresh);
 DLIB_TEST_MSG(mat(out) == mat(out2),
 "rows: "<< rows 
 << "\ncols: "<< rows 
 << "\nwidth: "<< width 
 << "\nheight: "<< height );
 }
// ----------------------------------------------------------------------------------------
 void test_max_filter()
 {
 dlib::rand rnd;
 for (int iter = 0; iter < 300; ++iter)
 {
 print_spinner();
 test_max_filter(0,0,1,1,rnd);
 test_max_filter(0,0,3,1,rnd);
 test_max_filter(0,0,3,3,rnd);
 test_max_filter(0,0,1,3,rnd);
 test_max_filter(1,1,1,1,rnd);
 test_max_filter(2,2,1,1,rnd);
 test_max_filter(3,3,1,1,rnd);
 test_max_filter(3,3,3,3,rnd);
 test_max_filter(3,3,2,2,rnd);
 test_max_filter(3,3,3,5,rnd);
 test_max_filter(3,3,6,8,rnd);
 test_max_filter(20,20,901,901,rnd);
 test_max_filter(5,5,1,5,rnd);
 test_max_filter(50,50,9,9,rnd);
 test_max_filter(50,50,9,9,rnd);
 test_max_filter(50,50,10,10,rnd);
 test_max_filter(50,50,11,10,rnd);
 test_max_filter(50,50,10,11,rnd);
 test_max_filter(50,50,10,21,rnd);
 test_max_filter(50,50,20,10,rnd);
 test_max_filter(50,50,20,10,rnd);
 test_max_filter(50,50,9,9,rnd);
 test_max_filter(20,20,1,901,rnd);
 test_max_filter(20,20,3,901,rnd);
 test_max_filter(20,20,901,1,rnd);
 }
 for (int iter = 0; iter < 200; ++iter)
 {
 print_spinner();
 test_max_filter((int)rnd.get_random_8bit_number()%100+1,
 (int)rnd.get_random_8bit_number()%100+1,
 (int)rnd.get_random_8bit_number()%150+1,
 (int)rnd.get_random_8bit_number()%150+1,
 rnd);
 }
 }
// ----------------------------------------------------------------------------------------
 void make_images (
 dlib::rand& rnd,
 array<array2d<unsigned char> >& images,
 long num,
 long nr,
 long nc
 )
 {
 images.resize(num);
 for (unsigned long i = 0; i < images.size(); ++i)
 {
 images[i].set_size(nr,nc);
 }
 for (unsigned long i = 0; i < images.size(); ++i)
 {
 for (long r = 0; r < nr; ++r)
 {
 for (long c = 0; c < nc; ++c)
 {
 images[i][r][c] = rnd.get_random_8bit_number();
 }
 }
 }
 }
 template <
 typename image_array_type
 >
 void brute_force_scan_image_movable_parts (
 std::vector<std::pair<double, point> >& dets,
 const image_array_type& images,
 const rectangle& window,
 const std::vector<std::pair<unsigned int, rectangle> >& fixed_rects,
 const std::vector<std::pair<unsigned int, rectangle> >& movable_rects,
 const double thresh,
 const unsigned long 
 )
 {
 dets.clear();
 if (movable_rects.size() == 0 && fixed_rects.size() == 0)
 return;
 for (long r = 0; r < images[0].nr(); ++r)
 {
 for (long c = 0; c < images[0].nc(); ++c)
 {
 const point p(c,r);
 double score = sum_of_rects_in_images_movable_parts(images,
 window,
 fixed_rects,
 movable_rects,
 p); 
 if (score >= thresh)
 {
 dets.push_back(make_pair(score,p));
 }
 }
 }
 }
 void test_scan_images_movable_parts()
 {
 array<array2d<unsigned char> > images;
 dlib::rand rnd;
 for (int iter = 0; iter < 40; ++iter)
 {
 print_spinner();
 const int num_images = rnd.get_random_32bit_number()%4+1;
 make_images(rnd,images, num_images, 
 rnd.get_random_32bit_number()%50+1,
 rnd.get_random_32bit_number()%50+1
 );
 std::vector<std::pair<double,point> > dets1, dets2;
 std::vector<std::pair<unsigned int, rectangle> > fixed_rects, movable_rects;
 double total_area = 0;
 for (unsigned long i = 0; i < images.size(); ++i)
 {
 fixed_rects.push_back(make_pair(i, centered_rect(
 rnd.get_random_32bit_number()%10-5,
 rnd.get_random_32bit_number()%10-5,
 rnd.get_random_32bit_number()%10,
 rnd.get_random_32bit_number()%10
 )));
 total_area += fixed_rects.back().second.area();
 movable_rects.push_back(make_pair(i, centered_rect(
 0,
 0,
 rnd.get_random_32bit_number()%10+1,
 rnd.get_random_32bit_number()%10+1
 )));
 total_area += movable_rects.back().second.area();
 }
 const rectangle window = centered_rect(0,0, 
 rnd.get_random_32bit_number()%15+1,
 rnd.get_random_32bit_number()%15+1);
 dlog << LINFO << "window size: "<< window.width() << ", " << window.height();
 const double thresh = total_area*130;
 const unsigned long max_dets = get_rect(images[0]).area();
 scan_image_movable_parts(dets1,images,window,fixed_rects,movable_rects,thresh, max_dets);
 brute_force_scan_image_movable_parts(dets2,images,window,fixed_rects,movable_rects,thresh, max_dets);
 dlog << LINFO << "max_possible dets: " << max_dets;
 dlog << LINFO << "regular dets: " << dets1.size();
 dlog << LINFO << "brute force: " << dets2.size();
 DLIB_TEST(dets1.size() == dets2.size());
 array2d<double> check(images[0].nr(), images[0].nc());
 assign_all_pixels(check, 1e-300);
 for (unsigned long i = 0; i < dets1.size(); ++i)
 {
 const point p = dets1[i].second;
 check[p.y()][p.x()] = dets1[i].first;
 }
 for (unsigned long i = 0; i < dets2.size(); ++i)
 {
 const point p = dets2[i].second;
 DLIB_TEST(std::abs(check[p.y()][p.x()] - dets2[i].first) < 1e-10);
 }
 dlog << LINFO << "=======================\n";
 }
 }
// ----------------------------------------------------------------------------------------
 class scan_image_tester : public tester
 {
 public:
 scan_image_tester (
 ) :
 tester ("test_scan_image",
 "Runs tests on the scan_image routine.")
 {}
 void perform_test (
 )
 {
 test_scan_images_movable_parts();
 test_max_filter();
 run_test1();
 run_test2();
 run_test3<unsigned char>(1);
 run_test3<unsigned char>(-1);
 run_test3<double>(1);
 run_test3<double>(-1);
 test_sum_filter<unsigned char>();
 test_sum_filter<double>();
 }
 } a;
}