Rotate & Crop an image takes a lot of time

[shliama]

Hello and thanks for a great library!

So, the issue is - I'm trying to crop a rotated rectangle from an image, therefore I use this code:

CImg<unsigned char> image;
image.assign(file_source_path);
image.rotate(angle, 0, 0).crop(left, top, left + width, top + height).save(file_result_path);

The result is correct, but it takes more than 20 seconds to crop 1000x1000 px region from 4000x5600 px jpeg image. I was also trying to pass different parameters to rotate function, but the nearest type of interpolation seems to be the fastest (linear & cubic took up to 40 seconds). Same for boundary conditions.

However when I'm using OpenCV library to perform the same task with the same image, it takes just 2±1 seconds.

Example code:

Mat src = imread(file_source_path, CV_LOAD_IMAGE_UNCHANGED);
Point2f center(src.cols/2.0, src.rows/2.0);
Mat rot = getRotationMatrix2D(center, angle, 1.0);
Rect bbox = RotatedRect(center,src.size(), angle).boundingRect();
rot.at<double>(0,2) += bbox.width/2.0 - center.x;
rot.at<double>(1,2) += bbox.height/2.0 - center.y;

Mat dst;
warpAffine(src, dst, rot, bbox.size());
Rect myROI(left, top, width, height);
Mat croppedImage = dst(myROI);

imwrite(file_result_path, croppedImage, vector<int>({CV_IMWRITE_JPEG_QUALITY, 80}));

But I don't want to include OpenCV into my project, you library seems to have everything that I need and still very small.

So the question is, am I doing something wrong? Can I optimize the time for such operation and how? Thanks in advance.

[dtschump]

Well, that is not surprising. It's actually not effective to rotate a whole image, then crop a particular region from it. I doubt OpenCV does that looking at the code your provided (it rotates a ROI which is really different).
I think this kind of tasks can be efficiently done in CImg using a warping field, then use method CImg<T>::get_warp() to retrieve the rotated ROI. Give me some time, and I'll put a solution here soon.

[shliama]

Huge thanks for a response, I'll definitely check the warping field (btw cool naming). Of course, solution from you would be more than awesome!

[dtschump]

This should work :

#include "CImg.h"
using namespace cimg_library;

int main(int argc, char **argv) {

  // Set input arguments.
  const CImg<unsigned char> img("image.bmp");
  const int
    x0 = 200, y0 = 200,
    x1 = 400, y1 = 400;
  const float angle = 45; // (in degree).

  // Create warp field.
  CImg<float> warp(cimg::abs(x1 - x0 + 1),cimg::abs(y1 - y0 + 1),1,2);
  const float
    w2 = img.width()/2.0f, h2 = img.height()/2.0f,
    rad = angle*cimg::PI/180, ca = std::cos(rad), sa = std::sin(rad);
  cimg_forXY(warp,x,y) {
    const float  u = x + x0 - w2, v = y + y0 - h2;
    warp(x,y,0) = w2 + u*ca + v*sa;
    warp(x,y,1) = h2 - u*sa + v*ca;
  }

  // Get cropped image.
  const CImg<unsigned char> crop = img.get_warp(warp,0,0,0);

  // Compare with crop on fully rotated image.
  const CImg<unsigned char> full_crop = img.get_rotate(angle,w2,h2,1,0,0).crop(x0,y0,x1,y1);

  (img,crop,full_crop).display();

  return 0;
}

[shliama]

Thanks a lot!
So now it takes up to 5 seconds (which is much better), but something wrong with calculations. When there is non 0 angle, cropped area is shifted, while preserving correct angle. Crop area is OK when angle is 0. I'll try to figure out what can cause the problem but any tips are welcome

[dtschump]

To make it even faster for large images, you need to activate the support of OpenMP, and the program will use several cores to compute the result.
Concerning the shift problem, I'm not sure what is going on. My program shows the difference between the quick crop and the full crop, and as far as I've tested, there are no differences.
Maybe in your case, you need to crop first then rotate, instead of rotate first then crop ?

[shliama]

The thing is, I'm doing it on Android so cannot use .display(), I just save image to file.

I've found that:
const CImg<unsigned char> full_crop = img.get_rotate(angle,w2,h2,1,0,0).crop(x0,y0,x1,y1);
and
const CImg<unsigned char> full_crop = img.get_rotate(angle,0,0).crop(x0,y0,x1,y1);
give me different results (second one is correct). Don't know why, because w2 and h2 are calculated as the center of an image, so results should be the same, am I right?

And another thing:
const CImg<unsigned char> crop = img.get_warp(warp,0,0,0);
gives me the same "wrong" result as full_crop via .get_rotate(angle,w2,h2,1,0,0)

[dtschump]

I don't know what OpenMP is doing exactly, so maybe this is slightly different than just 'rotate and crop'.
Also, please study the source code I wrote carefully, maybe run it on a regular PC. The code I wrote make a crop of a rotated image, and shows that is equivalent to doing it explicitely (rotate the image first, then crop it). Also, check your CImg version is recent enough.

[shliama]

I'm using the latest version which was downloaded for the website yesterday cimg_version 170
And yes, I do need rotate & only then crop an image.

Thanks a lot for your code and answers, but I'm just wondering why these two lines could give me different results?

1. const CImg<unsigned char> full_crop = img.get_rotate(angle,w2,h2,1,0,0).crop(x0,y0,x1,y1);
2. const CImg<unsigned char> full_crop = img.get_rotate(angle,0,0).crop(x0,y0,x1,y1);

The second one gives correct result, and first one gives shifted result (same as code that uses warp, that's why your sample shows that they are equivalent, but unfortunately equivalently wrong).

If those two lines of code give the same results for you, well I'll try to figure out what's wrong, but I'm pretty sure about it - tripple checked that.

[dtschump]

The difference between the two methods CImg<T>::rotate() are as follow :

1. The first one takes the center of rotation as arguments, and it rotates the image while keeping its initial size. This is the method described here : http://cimg.eu/reference/structcimg__library_1_1CImg.html#a741283114c5057fb71a18c4ef65132ed
   Of course, keeping the same size makes some pixel disappear (except for very specific angles like 180°). This is probably why you call it 'shifted', because some pixels are actually outside the initial canvas.
2. The second one does not take the rotation center coordinates as arguments, and it adapts the returned image size so that all pixels of the initial images are still visible. This is the method described here : http://cimg.eu/reference/structcimg__library_1_1CImg.html#acefe47177c67d0ac1caa75631b2d5f09

Note they have the same name, but performs not exactly the same.

To me, it wouldn't make so much sense to crop the image generated by the second method, as the returned image size depends on the rotation angle given as a parameter. That's why I used the first method to generate the 'full crop' to compare my method with.

[shliama]

Oh, now it's clear.
The thing is, angle, and x0,y0,x1,y1 values that I pass are calculated in a way that fits logic of the second CImg<T>::rotate() method.
So that's why result for the first one is "shifted" (and here I mean, XY coords are shifted) - it keeps the image initial size and I expect another image size after rotation.

[dtschump]

So I guess you just have to customize the warping field a little bit to make it correspond to the desired crop :) This will depend on the rotated image size, which can be obtained from this piece of code (taken from CImg method CImg<T>::get_rotate()).

    const float
      rad = (float)(nangle*cimg::PI/180.0),
      ca = (float)std::cos(rad),
      sa = (float)std::sin(rad),
      ux = cimg::abs(_width*ca), uy = cimg::abs(_width*sa),
      vx = cimg::abs(_height*sa), vy = cimg::abs(_height*ca),
      w2 = 0.5f*_width, h2 = 0.5f*_height,
      dw2 = 0.5f*(ux + vx), dh2 = 0.5f*(uy + vy);
    res.assign((int)(ux + vx),(int)(uy + vy),_depth,_spectrum);

There's still a little work to be done by the way.

[shliama]

Awesome, thanks! I think I'll figure out the rest.
Live long and prosper

[shliama]

Finally had free time to solve this issue :) Again - thanks a lot for your help, appreciate it.
Maybe someone someday will look for solution like this, so here is the code:

const CImg<unsigned char> img(file_source_path);
const int
x0 = left, y0 = top,
x1 = left + width, y1 = top + height;

// Create warp field.
CImg<float> warp(cimg::abs(x1 - x0 + 1), cimg::abs(y1 - y0 + 1), 1, 2);

const float
rad = angle * cimg::PI/180,
ca = std::cos(rad), sa = std::sin(rad),
ux = cimg::abs(img.width() * ca), uy = cimg::abs(img.width() * sa),
vx = cimg::abs(img.height() * sa), vy = cimg::abs(img.height() * ca),
w2 = 0.5f * img.width(), h2 = 0.5f * img.height(),
dw2 = 0.5f * (ux + vx), dh2 = 0.5f * (uy + vy);

cimg_forXY(warp, x, y) {
    const float
    u = x + x0 - dw2, v = y + y0 - dh2;

    warp(x, y, 0) = w2 + u*ca + v*sa;
    warp(x, y, 1) = h2 - u*sa + v*ca;
}

img.get_warp(warp, 0, 0, 0).save(file_result_path);

[dtschump]

Nice ! Thanks for sharing :)
Also, try compiling it with the OpenMP support (#define cimg_use_openmp before #include "CImg.h") to speed up the warping process if needed.