AlbumShaper  1.0a3
tilt.cpp
Go to the documentation of this file.
1 //==============================================
2 // copyright : (C) 2003-2005 by Will Stokes
3 //==============================================
4 // This program is free software; you can redistribute it
5 // and/or modify it under the terms of the GNU General
6 // Public License as published by the Free Software
7 // Foundation; either version 2 of the License, or
8 // (at your option) any later version.
9 //==============================================
10 
11 //Systemwide includes
12 #include <qimage.h>
13 #include <qstring.h>
14 #include <qapplication.h>
15 #include <math.h>
16 
17 #define MIN(x,y) ((x) < (y) ? (x) : (y))
18 #define MAX(x,y) ((x) < (y) ? (x) : (y))
19 
20 //Projectwide includes
21 #include "tilt.h"
22 #include "tilt_internal.h"
23 #include "../../gui/statusWidget.h"
24 
25 //----------------------------------------------
26 // Inputs:
27 // -------
28 // QString filename - location of original image on disk
29 // QPoint p1 and p2 - points along what should have been a vertical
30 // or horizontal edge
31 // StatusWidget* status - widget for making progress visible to user
32 //
33 // Outputs:
34 // --------
35 // QImage* returned - constructed image
36 //
37 // Description:
38 // ------------
39 // This method returned an image rotated as necessary to make points p1
40 // and p2 lie on what should have been a vertical or horizontal edge.
41 // Implicitly this task can be broken up into three steps:
42 //
43 // 1.) Determining the angle by which to rotate the image about it's
44 // center. We do this by computing angle the line supplied makes with the
45 // vertical and horizontal axis. We hypothesize that the smaller angle
46 // indicates the correct axis the user is indicating and hence the
47 // correct angle by which to rotate the image.
48 //
49 // 2.) Now that we have sidestepped having the user input the number
50 // of degrees to rotate the image by hand, we must use the computed angle
51 // to rotate the image. An intermediate image is constructed that is the
52 // same resolution as the original image. Each pixel is set by computed the
53 // un-rotated float coordinates and bilinearly interpolating the original
54 // pixel value. Regions that when un-rotated no-longer fall on the original
55 // image plane remain black and will be clipped during the next step.
56 //
57 // 3.) A side-effect of the rotation by a non-90 degree angle is that
58 // the corners remain undefined (pixels in the corners were not previously
59 // on the image plane and hence we have no data for them). A simplistic
60 // approach would be to paint these regions black and require the user to
61 // handle crop the image to cut these corners out.
62 //
63 // Frankly, I find taking such an approach unacceptable.
64 //
65 // Since understood behavior is for the image to rotate about it's
66 // center, and most likely for the aspect ratio to remain unchanged,
67 // is it necessary to compute the maximal bounding region centered
68 // about the intermediate image center that does not contain any
69 // undefined corner image pixels.
70 //
71 // This seemingly difficult problem can be reduced to 4 rotations
72 // and a number of line intersections! First, one must compute
73 // the rotated locations of the corners of the image. Next,
74 // lines made up by the rotated corners and the the new image
75 // corners are used to find the 8 intersection points (marked with *'s)
76 // as shown in the figure below:
77 //
78 // b
79 // A _____*/_\*___ B
80 // | / \ |
81 // | / \*
82 // */ |\ d
83 // a/| |/
84 // \* *
85 // |*_________*/_|
86 // C \ / D
87 // \ /
88 // \/
89 // c
90 //
91 // By drawing lines from the center to each new image corner (A,B,C,D) and
92 // intersecting these lines with the lopped corners described by the newly
93 // found points (*'s), we can find four new points. It is a rather straight
94 // forward process determing the maximal height and weight of a bounding
95 // area centered about the image that will fall within these four points.
96 //
97 // At this point a true edited image is constructed and returned
98 // by copying pixel values withn the computed maximal bounding
99 // rectangle from the intermediate image previously constructed.
100 //----------------------------------------------
101 
102 //==============================================
103 QImage* correctImageTilt( QString filename, QPoint p1, QPoint p2,
105 {
106  //first compute distance between two points or "radius"
107  int dx = p2.x() - p1.x();
108  int dy = p2.y() - p1.y();
109 
110  //determine tilt angle
111  int delta = 0;
112 
113  //compute recirpocal of distance between points
114  double recip_r = 1.0 / sqrt( (double) (dx*dx + dy*dy) );
115 
116  //compute angle with horizontal axis
117  if( QABS(dx) > QABS(dy) )
118  {
119  delta = dy;
120  if(dx > 0) delta = -delta;
121  }
122  //compute angle with vertical axis
123  else
124  {
125  delta = dx;
126  if(dy < 0) delta = -delta;
127  }
128 
129  double sinTheta = (delta * recip_r);
130  double theta = asin( sinTheta );
131  double cosTheta = cos( theta );
132 
133  //if angle is 0 (improbable but possible) then quit now
134  if( theta == 0 )
135  return NULL;
136 
137  //load original and edited images
138  QImage originalImage( filename );
139 
140  //convert to 32-bit depth if necessary
141  if( originalImage.depth() < 32 ) { originalImage = originalImage.convertDepth( 32, Qt::AutoColor ); }
142 
143  QImage rotatedImage( originalImage.width(), originalImage.height(), originalImage.depth() );
144 
145  //setup progress bar
146  QString statusMessage = qApp->translate( "correctImageTilt", "Correcting Tilt:" );
147  status->showProgressBar( statusMessage, 200 );
148  qApp->processEvents();
149 
150  //during the first phase update the status bar for every 1% of image pixels that are processed
151  int updateIncrement = (int) ( 0.01 * originalImage.width() * originalImage.height() );
152  int newProgress = 0;
153 
154  //set each pixel to the rotated value
155  double xp, yp;
156 
157  double w2 = 0.5 * rotatedImage.width();
158  double h2 = 0.5 * rotatedImage.height();
159 
160  int x,y;
161  uchar* scanLine;
162  QRgb* rgb;
163  for( y=0; y<rotatedImage.height(); y++)
164  {
165  //iterate over each selected pixel in scanline
166  scanLine = rotatedImage.scanLine(y);
167  for( x=0; x<rotatedImage.width(); x++)
168  {
169  //compute unrotated coordinates
170  xp = cosTheta*(x-w2) + sinTheta*(y-h2) + w2;
171  yp = -sinTheta*(x-w2) + cosTheta*(y-h2) + h2;
172 
173  //set unrotated value
174  rgb = ((QRgb*)scanLine+x);
175  *rgb = interpolatedPixelValue( xp, yp, &originalImage);
176 
177  //update status bar if significant progress has been made since last update
178  newProgress++;
179  if(newProgress >= updateIncrement)
180  {
181  newProgress = 0;
182  status->incrementProgress();
183  qApp->processEvents();
184  }
185 
186  }
187  }
188 
189  //find rotated corners
190  double nTheta = -theta;
191  double sinNTheta = sin( nTheta );
192  double cosNTheta = cos( nTheta );
193 
194  DPoint topLeft = DPoint( cosNTheta*(-w2) + sinNTheta*(-h2) + w2,
195  -sinNTheta*(-w2) + cosNTheta*(-h2) + h2 );
196 
197  DPoint topRight = DPoint( cosNTheta*(w2) + sinNTheta*(-h2) + w2,
198  -sinNTheta*(w2) + cosNTheta*(-h2) + h2 );
199 
200  DPoint bottomLeft = DPoint( cosNTheta*(-w2) + sinNTheta*(h2) + w2,
201  -sinNTheta*(-w2) + cosNTheta*(h2) + h2 );
202 
203  DPoint bottomRight = DPoint( cosNTheta*(w2) + sinNTheta*(h2) + w2,
204  -sinNTheta*(w2) + cosNTheta*(h2) + h2 );
205 
206  //determine which of these points are which in their rotated form
207  DPoint top, bottom, left, right;
208  if( theta < 0 )
209  {
210  top = topRight;
211  bottom = bottomLeft;
212  left = topLeft;
213  right = bottomRight;
214  }
215  else
216  {
217  top = topLeft;
218  bottom = bottomRight;
219  left = bottomLeft;
220  right = topRight;
221  }
222 
223  //construct true corners
224  DPoint trueTopLeft ( 0, 0 );
225  DPoint trueTopRight ( rotatedImage.width()-1, 0 );
226  DPoint trueBottomLeft ( 0, rotatedImage.height()-1 );
227  DPoint trueBottomRight( rotatedImage.width()-1, rotatedImage.height()-1 );
228 
229  //find intersections with image boundary
230  DPoint topEdgeL = findTwoLineIntersection( left, top, trueTopLeft, trueTopRight );
231  DPoint topEdgeR = findTwoLineIntersection( top, right, trueTopLeft, trueTopRight );
232 
233  DPoint bottomEdgeL = findTwoLineIntersection( left, bottom, trueBottomLeft, trueBottomRight );
234  DPoint bottomEdgeR = findTwoLineIntersection( bottom, right, trueBottomLeft, trueBottomRight );
235 
236  DPoint leftEdgeT = findTwoLineIntersection( left, top, trueTopLeft, trueBottomLeft );
237  DPoint leftEdgeB = findTwoLineIntersection( left, bottom, trueTopLeft, trueBottomLeft );
238 
239  DPoint rightEdgeT = findTwoLineIntersection( right, top, trueTopRight, trueBottomRight );
240  DPoint rightEdgeB = findTwoLineIntersection( right, bottom, trueTopRight, trueBottomRight );
241 
242  //shot rays out from image center to each true corner and find intersections with clipped corners
243  DPoint center( (int)w2, (int)h2 );
244  DPoint safeTopLeft = findTwoLineIntersection( center, trueTopLeft, leftEdgeT, topEdgeL );
245  DPoint safeTopRight = findTwoLineIntersection( center, trueTopRight, rightEdgeT, topEdgeR );
246  DPoint safeBottomLeft = findTwoLineIntersection( center, trueBottomLeft, leftEdgeB, bottomEdgeL );
247  DPoint safeBottomRight = findTwoLineIntersection( center, trueBottomRight, rightEdgeB, bottomEdgeR );
248 
249  //find constrained area
250  double minY = MAX( safeTopLeft.y(), safeTopRight.y() );
251  double maxY = MIN( safeBottomLeft.y(), safeBottomRight.y() );
252 
253  double minX = MAX( safeTopLeft.x(), safeBottomLeft.x() );
254  double maxX = MIN( safeTopRight.x(), safeBottomRight.x() );
255 
256  //find contrained area in integer coordinates. this is semi-tricky.
257  //if the minimum values decimal porition is nonzero then increment by one
258  // (eg 5.37 -> 6)
259  int xMin = (int) minX;
260  int xMax = (int) maxX;
261 
262  int yMin = (int) minY;
263  int yMax = (int) maxY;
264 
265  if( xMin < minX ) xMin++;
266  if( yMin < minY ) yMin++;
267 
268  //construct cropped rotated image
269  QImage* editedImage = new QImage( xMax - xMin + 1,
270  yMax - yMin + 1,
271  rotatedImage.depth() );
272 
273  //during the second phase update the status bar for every 1% of cropped pixels that are procesed
274  updateIncrement = (int) ( 0.01 * editedImage->width() * editedImage->height() );
275  newProgress = 0;
276 
277  int x2,y2;
278  uchar* scanLine2;
279  QRgb* rgb2;
280 
281  y2 = 0;
282  for( y=yMin; y<=yMax; y++, y2++)
283  {
284  //iterate over each selected pixel in scanline
285  scanLine = rotatedImage.scanLine(y);
286  scanLine2 = editedImage->scanLine(y2);
287 
288  x2 = 0;
289  for( x=xMin; x<=xMax; x++, x2++)
290  {
291  rgb = ((QRgb*)scanLine +x );
292  rgb2 = ((QRgb*)scanLine2+x2);
293  *rgb2 = *rgb;
294 
295  //update status bar if significant progress has been made since last update
296  newProgress++;
297  if(newProgress >= updateIncrement)
298  {
299  newProgress = 0;
300  status->incrementProgress();
301  qApp->processEvents();
302  }
303 
304  }
305  }
306 
307  //remove status bar
308  status->setStatus( "" );
309  qApp->processEvents();
310 
311  //return pointer to edited image
312  return editedImage;
313 }
314 //==============================================
315 QRgb interpolatedPixelValue( double xp, double yp,
316  QImage* image )
317 {
318  //do boundary checking to
319  //ensure we don't read beyond image boundaries
320  if(xp < 0 || xp >= image->width() ||
321  yp < 0 || yp >= image->height() )
322  return qRgb( 0, 0, 0 );
323 
324  //get four pixel colors,
325  int x = (int)xp;
326  int y = (int)yp;
327 
328  uchar* scanLine1 = image->scanLine( y );
329 
330  uchar* scanLine2;
331  if( y < image->height() - 1 )
332  scanLine2 = image->scanLine( y+1 );
333  else
334  scanLine2 = scanLine1;
335 
336  QRgb p1,p2,p3,p4;
337 
338  p1 = *((QRgb*)scanLine1+x);
339  p3 = *((QRgb*)scanLine2+x);
340 
341  if( x < image->width() - 1)
342  {
343  p2 = *((QRgb*)scanLine1+x+1);
344  p4 = *((QRgb*)scanLine2+x+1);
345  }
346  else
347  {
348  p2 = p1;
349  p4 = p3;
350  }
351 
352  //blend four colors
353  double alphaY = yp - y;
354  double alphaX = xp - x;
355 
356  p1 = blendColors( p1, p2, alphaX );
357  p3 = blendColors( p3, p4, alphaX );
358  p1 = blendColors( p1, p3, alphaY );
359  return p1;
360 }
361 //==============================================
362 QRgb blendColors( QRgb color1, QRgb color2, double alpha )
363 {
364  double alpha2 = 1.0-alpha;
365  return qRgb( (int) MAX( MIN( 255, alpha2*qRed (Qt::color1) + alpha*qRed(color2) ), 0 ),
366  (int) MAX( MIN( 255, alpha2*qGreen(Qt::color1) + alpha*qGreen(color2) ), 0 ),
367  (int) MAX( MIN( 255, alpha2*qBlue (Qt::color1) + alpha*qBlue(color2) ), 0 ) );
368 }
369 //==============================================
371  DPoint p3, DPoint p4)
372 {
373  //----------------------------------------------
374  //=== Case 1: neither line has a change in X ===
375  //----------------------------------------------
376  //If there is no change in x for both lines,
377  //either lines will NEVER or ALWAYS intersect.
378  if(p1.x() == p2.x() &&
379  p4.x() == p3.x())
380  {
381  //Ok, if their x values are equal, return
382  //intersection point as line A's point A.
383  //Yes, this is a little arbitratry. But
384  //theoreticaly this section of code will almost
385  //never be executed.
386  if( p1.x() == p3.x() )
387  { return DPoint( p1.x(), p1.y() ); }
388  //Else lines will never intersect,
389  //return pair (-32000,-32000)
390  else
391  { return DPoint( -32000, -32000 ); }
392  }
393  //----------------------------------------------
394  //Else, we know at least one of the lines
395  //does NOT have a slope of infinity!!!
396  //----------------------------------------------
397 
398  //----------------------------------------------
399  //=== Case 2: line A has no change in X ===
400  //----------------------------------------------
401  //If line A has an infinite slope (no change in x)
402  //we know line B does not have an infinite slope...
403  else if( p1.x() == p2.x() )
404  {
405  double slopeB = ((double) (p4.y() - p3.y()) ) / (p4.x() - p3.x());
406 
407  double yInterceptB = p3.y() - slopeB*p3.x();
408 
409  //y = mx+b
410  return DPoint( p2.x(), slopeB*p2.x() + yInterceptB );
411  }
412  //----------------------------------------------
413  //=== Case 3: line B has no change in X ===
414  //----------------------------------------------
415  //If line B has an infinite slope (no change in x)
416  //we know line A does not have an infinite slope...
417  else if( p4.x() == p3.x() )
418  {
419  double slopeA = ((double) (p2.y() - p1.y()) ) / (p2.x() - p1.x());
420 
421  double yInterceptA = p1.y() - slopeA*p1.x();
422 
423  //y = mx+b
424  return DPoint( p4.x(), slopeA*p4.x() + yInterceptA );
425  }
426  //----------------------------------------------
427  //=== Case 4: both lines have non infinite slopes ===
428  //----------------------------------------------
429  else
430  {
431  double slopeA = ((double) (p2.y() - p1.y()) ) / (p2.x() - p1.x());
432  double slopeB = ((double) (p4.y() - p3.y()) ) / (p4.x() - p3.x());
433  double yInterceptA = p1.y() - slopeA*p1.x();
434  double yInterceptB = p3.y() - slopeB*p3.x();
435 
436  //y1 = mx1+b
437  //y2 = nx2+c
438  //at intersection y1=y2 and x1 = x2 so...
439  //mx +b = nx + c
440  //x(m-n) = c-b
441  //x = (c-b)/(m-n)
442  //where m and n are slope and
443  //b and c are y-intercepts.
444  //x = (c-b)/(m-n)
445  double x = (yInterceptB - yInterceptA) / (slopeA - slopeB);
446  return DPoint( x, (slopeA * x) + yInterceptA );
447  }
448 }
449 //==============================================
451 { xpos=0; ypos=0; }
452 //==============================================
453 DPoint::DPoint( double x, double y )
454 {
455  this->xpos = x;
456  this->ypos = y;
457 }
458 //==============================================
459 double DPoint::x() const { return xpos; }
460 double DPoint::y() const { return ypos; }
461 //==============================================
462 
463 
QRgb interpolatedPixelValue(double xp, double yp, QImage *image)
Definition: tilt.cpp:315
QPoint bottomRight
int updateIncrement
QPoint topLeft
QImage * correctImageTilt(QString filename, QPoint p1, QPoint p2, StatusWidget *status)
Definition: tilt.cpp:103
#define MIN(x, y)
Definition: tilt.cpp:17
void incrementProgress()
Updates the progress bar by one step.
void showProgressBar(QString message, int numSteps)
Initializes the progress bar.
DPoint()
Definition: tilt.cpp:450
void setStatus(QString message)
Update message.
#define MAX(x, y)
Definition: tilt.cpp:18
double xpos
Definition: tilt_internal.h:25
StatusWidget * status
int width
Definition: blur.cpp:79
double x() const
Definition: tilt.cpp:459
double y() const
Definition: tilt.cpp:460
QRgb blendColors(QRgb color1, QRgb color2, double alpha)
Definition: tilt.cpp:362
QImage * editedImage
int newProgress
int height
Definition: blur.cpp:79
DPoint findTwoLineIntersection(DPoint p1, DPoint p2, DPoint p3, DPoint p4)
Definition: tilt.cpp:370
double ypos
Definition: tilt_internal.h:25