Main Page | Namespace List | Class Hierarchy | Class List | File List | Class Members | File Members

tilt.cpp

Go to the documentation of this file.
00001 //============================================== 00002 // copyright : (C) 2003-2005 by Will Stokes 00003 //============================================== 00004 // This program is free software; you can redistribute it 00005 // and/or modify it under the terms of the GNU General 00006 // Public License as published by the Free Software 00007 // Foundation; either version 2 of the License, or 00008 // (at your option) any later version. 00009 //============================================== 00010 00011 //Systemwide includes 00012 #include <qimage.h> 00013 #include <qstring.h> 00014 #include <qapplication.h> 00015 #include <math.h> 00016 00017 //Projectwide includes 00018 #include "tilt.h" 00019 #include "tilt_internal.h" 00020 #include "../../gui/statusWidget.h" 00021 00022 //---------------------------------------------- 00023 // Inputs: 00024 // ------- 00025 // QString filename - location of original image on disk 00026 // QPoint p1 and p2 - points along what should have been a vertical 00027 // or horizontal edge 00028 // StatusWidget* status - widget for making progress visible to user 00029 // 00030 // Outputs: 00031 // -------- 00032 // QImage* returned - constructed image 00033 // 00034 // Description: 00035 // ------------ 00036 // This method returned an image rotated as necessary to make points p1 00037 // and p2 lie on what should have been a vertical or horizontal edge. 00038 // Implicitly this task can be broken up into three steps: 00039 // 00040 // 1.) Determining the angle by which to rotate the image about it's 00041 // center. We do this by computing angle the line supplied makes with the 00042 // vertical and horizontal axis. We hypothesize that the smaller angle 00043 // indicates the correct axis the user is indicating and hence the 00044 // correct angle by which to rotate the image. 00045 // 00046 // 2.) Now that we have sidestepped having the user input the number 00047 // of degrees to rotate the image by hand, we must use the computed angle 00048 // to rotate the image. An intermediate image is constructed that is the 00049 // same resolution as the original image. Each pixel is set by computed the 00050 // un-rotated float coordinates and bilinearly interpolating the original 00051 // pixel value. Regions that when un-rotated no-longer fall on the original 00052 // image plane remain black and will be clipped during the next step. 00053 // 00054 // 3.) A side-effect of the rotation by a non-90 degree angle is that 00055 // the corners remain undefined (pixels in the corners were not previously 00056 // on the image plane and hence we have no data for them). A simplistic 00057 // approach would be to paint these regions black and require the user to 00058 // handle crop the image to cut these corners out. 00059 // 00060 // Frankly, I find taking such an approach unacceptable. 00061 // 00062 // Since understood behavior is for the image to rotate about it's 00063 // center, and most likely for the aspect ratio to remain unchanged, 00064 // is it necessary to compute the maximal bounding region centered 00065 // about the intermediate image center that does not contain any 00066 // undefined corner image pixels. 00067 // 00068 // This seemingly difficult problem can be reduced to 4 rotations 00069 // and a number of line intersections! First, one must compute 00070 // the rotated locations of the corners of the image. Next, 00071 // lines made up by the rotated corners and the the new image 00072 // corners are used to find the 8 intersection points (marked with *'s) 00073 // as shown in the figure below: 00074 // 00075 // b 00076 // A _____*/_\*___ B 00077 // | / \ | 00078 // | / \* 00079 // */ |\ d 00080 // a/| |/ 00081 // \* * 00082 // |*_________*/_| 00083 // C \ / D 00084 // \ / 00085 // \/ 00086 // c 00087 // 00088 // By drawing lines from the center to each new image corner (A,B,C,D) and 00089 // intersecting these lines with the lopped corners described by the newly 00090 // found points (*'s), we can find four new points. It is a rather straight 00091 // forward process determing the maximal height and weight of a bounding 00092 // area centered about the image that will fall within these four points. 00093 // 00094 // At this point a true edited image is constructed and returned 00095 // by copying pixel values withn the computed maximal bounding 00096 // rectangle from the intermediate image previously constructed. 00097 //---------------------------------------------- 00098 00099 //============================================== 00100 QImage* correctImageTilt( QString filename, QPoint p1, QPoint p2, 00101 StatusWidget* status) 00102 { 00103 //first compute distance between two points or "radius" 00104 int dx = p2.x() - p1.x(); 00105 int dy = p2.y() - p1.y(); 00106 00107 //determine tilt angle 00108 int delta = 0; 00109 00110 //compute recirpocal of distance between points 00111 double recip_r = 1.0 / sqrt( (double) (dx*dx + dy*dy) ); 00112 00113 //compute angle with horizontal axis 00114 if( QABS(dx) > QABS(dy) ) 00115 { 00116 delta = dy; 00117 if(dx > 0) delta = -delta; 00118 } 00119 //compute angle with vertical axis 00120 else 00121 { 00122 delta = dx; 00123 if(dy < 0) delta = -delta; 00124 } 00125 00126 double sinTheta = (delta * recip_r); 00127 double theta = asin( sinTheta ); 00128 double cosTheta = cos( theta ); 00129 00130 //if angle is 0 (improbable but possible) then quit now 00131 if( theta == 0 ) 00132 return NULL; 00133 00134 //load original and edited images 00135 QImage originalImage( filename ); 00136 00137 //convert to 32-bit depth if necessary 00138 if( originalImage.depth() < 32 ) { originalImage = originalImage.convertDepth( 32, Qt::AutoColor ); } 00139 00140 QImage rotatedImage( originalImage.width(), originalImage.height(), originalImage.depth() ); 00141 00142 //setup progress bar 00143 QString statusMessage = qApp->translate( "correctImageTilt", "Correcting Tilt:" ); 00144 status->showProgressBar( statusMessage, 200 ); 00145 qApp->processEvents(); 00146 00147 //during the first phase update the status bar for every 1% of image pixels that are processed 00148 int updateIncrement = (int) ( 0.01 * originalImage.width() * originalImage.height() ); 00149 int newProgress = 0; 00150 00151 //set each pixel to the rotated value 00152 double xp, yp; 00153 00154 double w2 = 0.5 * rotatedImage.width(); 00155 double h2 = 0.5 * rotatedImage.height(); 00156 00157 int x,y; 00158 uchar* scanLine; 00159 QRgb* rgb; 00160 for( y=0; y<rotatedImage.height(); y++) 00161 { 00162 //iterate over each selected pixel in scanline 00163 scanLine = rotatedImage.scanLine(y); 00164 for( x=0; x<rotatedImage.width(); x++) 00165 { 00166 //compute unrotated coordinates 00167 xp = cosTheta*(x-w2) + sinTheta*(y-h2) + w2; 00168 yp = -sinTheta*(x-w2) + cosTheta*(y-h2) + h2; 00169 00170 //set unrotated value 00171 rgb = ((QRgb*)scanLine+x); 00172 *rgb = interpolatedPixelValue( xp, yp, &originalImage); 00173 00174 //update status bar if significant progress has been made since last update 00175 newProgress++; 00176 if(newProgress >= updateIncrement) 00177 { 00178 newProgress = 0; 00179 status->incrementProgress(); 00180 qApp->processEvents(); 00181 } 00182 00183 } 00184 } 00185 00186 //find rotated corners 00187 double nTheta = -theta; 00188 double sinNTheta = sin( nTheta ); 00189 double cosNTheta = cos( nTheta ); 00190 00191 DPoint topLeft = DPoint( cosNTheta*(-w2) + sinNTheta*(-h2) + w2, 00192 -sinNTheta*(-w2) + cosNTheta*(-h2) + h2 ); 00193 00194 DPoint topRight = DPoint( cosNTheta*(w2) + sinNTheta*(-h2) + w2, 00195 -sinNTheta*(w2) + cosNTheta*(-h2) + h2 ); 00196 00197 DPoint bottomLeft = DPoint( cosNTheta*(-w2) + sinNTheta*(h2) + w2, 00198 -sinNTheta*(-w2) + cosNTheta*(h2) + h2 ); 00199 00200 DPoint bottomRight = DPoint( cosNTheta*(w2) + sinNTheta*(h2) + w2, 00201 -sinNTheta*(w2) + cosNTheta*(h2) + h2 ); 00202 00203 //determine which of these points are which in their rotated form 00204 DPoint top, bottom, left, right; 00205 if( theta < 0 ) 00206 { 00207 top = topRight; 00208 bottom = bottomLeft; 00209 left = topLeft; 00210 right = bottomRight; 00211 } 00212 else 00213 { 00214 top = topLeft; 00215 bottom = bottomRight; 00216 left = bottomLeft; 00217 right = topRight; 00218 } 00219 00220 //construct true corners 00221 DPoint trueTopLeft ( 0, 0 ); 00222 DPoint trueTopRight ( rotatedImage.width()-1, 0 ); 00223 DPoint trueBottomLeft ( 0, rotatedImage.height()-1 ); 00224 DPoint trueBottomRight( rotatedImage.width()-1, rotatedImage.height()-1 ); 00225 00226 //find intersections with image boundary 00227 DPoint topEdgeL = findTwoLineIntersection( left, top, trueTopLeft, trueTopRight ); 00228 DPoint topEdgeR = findTwoLineIntersection( top, right, trueTopLeft, trueTopRight ); 00229 00230 DPoint bottomEdgeL = findTwoLineIntersection( left, bottom, trueBottomLeft, trueBottomRight ); 00231 DPoint bottomEdgeR = findTwoLineIntersection( bottom, right, trueBottomLeft, trueBottomRight ); 00232 00233 DPoint leftEdgeT = findTwoLineIntersection( left, top, trueTopLeft, trueBottomLeft ); 00234 DPoint leftEdgeB = findTwoLineIntersection( left, bottom, trueTopLeft, trueBottomLeft ); 00235 00236 DPoint rightEdgeT = findTwoLineIntersection( right, top, trueTopRight, trueBottomRight ); 00237 DPoint rightEdgeB = findTwoLineIntersection( right, bottom, trueTopRight, trueBottomRight ); 00238 00239 //shot rays out from image center to each true corner and find intersections with clipped corners 00240 DPoint center( (int)w2, (int)h2 ); 00241 DPoint safeTopLeft = findTwoLineIntersection( center, trueTopLeft, leftEdgeT, topEdgeL ); 00242 DPoint safeTopRight = findTwoLineIntersection( center, trueTopRight, rightEdgeT, topEdgeR ); 00243 DPoint safeBottomLeft = findTwoLineIntersection( center, trueBottomLeft, leftEdgeB, bottomEdgeL ); 00244 DPoint safeBottomRight = findTwoLineIntersection( center, trueBottomRight, rightEdgeB, bottomEdgeR ); 00245 00246 //find constrained area 00247 double minY = QMAX( safeTopLeft.y(), safeTopRight.y() ); 00248 double maxY = QMIN( safeBottomLeft.y(), safeBottomRight.y() ); 00249 00250 double minX = QMAX( safeTopLeft.x(), safeBottomLeft.x() ); 00251 double maxX = QMIN( safeTopRight.x(), safeBottomRight.x() ); 00252 00253 //find contrained area in integer coordinates. this is semi-tricky. 00254 //if the minimum values decimal porition is nonzero then increment by one 00255 // (eg 5.37 -> 6) 00256 int xMin = (int) minX; 00257 int xMax = (int) maxX; 00258 00259 int yMin = (int) minY; 00260 int yMax = (int) maxY; 00261 00262 if( xMin < minX ) xMin++; 00263 if( yMin < minY ) yMin++; 00264 00265 //construct cropped rotated image 00266 QImage* editedImage = new QImage( xMax - xMin + 1, 00267 yMax - yMin + 1, 00268 rotatedImage.depth() ); 00269 00270 //during the second phase update the status bar for every 1% of cropped pixels that are procesed 00271 updateIncrement = (int) ( 0.01 * editedImage->width() * editedImage->height() ); 00272 newProgress = 0; 00273 00274 int x2,y2; 00275 uchar* scanLine2; 00276 QRgb* rgb2; 00277 00278 y2 = 0; 00279 for( y=yMin; y<=yMax; y++, y2++) 00280 { 00281 //iterate over each selected pixel in scanline 00282 scanLine = rotatedImage.scanLine(y); 00283 scanLine2 = editedImage->scanLine(y2); 00284 00285 x2 = 0; 00286 for( x=xMin; x<=xMax; x++, x2++) 00287 { 00288 rgb = ((QRgb*)scanLine +x ); 00289 rgb2 = ((QRgb*)scanLine2+x2); 00290 *rgb2 = *rgb; 00291 00292 //update status bar if significant progress has been made since last update 00293 newProgress++; 00294 if(newProgress >= updateIncrement) 00295 { 00296 newProgress = 0; 00297 status->incrementProgress(); 00298 qApp->processEvents(); 00299 } 00300 00301 } 00302 } 00303 00304 //remove status bar 00305 status->setStatus( "" ); 00306 qApp->processEvents(); 00307 00308 //return pointer to edited image 00309 return editedImage; 00310 } 00311 //============================================== 00312 QRgb interpolatedPixelValue( double xp, double yp, 00313 QImage* image ) 00314 { 00315 //do boundary checking to 00316 //ensure we don't read beyond image boundaries 00317 if(xp < 0 || xp >= image->width() || 00318 yp < 0 || yp >= image->height() ) 00319 return qRgb( 0, 0, 0 ); 00320 00321 //get four pixel colors, 00322 int x = (int)xp; 00323 int y = (int)yp; 00324 00325 uchar* scanLine1 = image->scanLine( y ); 00326 00327 uchar* scanLine2; 00328 if( y < image->height() - 1 ) 00329 scanLine2 = image->scanLine( y+1 ); 00330 else 00331 scanLine2 = scanLine1; 00332 00333 QRgb p1,p2,p3,p4; 00334 00335 p1 = *((QRgb*)scanLine1+x); 00336 p3 = *((QRgb*)scanLine2+x); 00337 00338 if( x < image->width() - 1) 00339 { 00340 p2 = *((QRgb*)scanLine1+x+1); 00341 p4 = *((QRgb*)scanLine2+x+1); 00342 } 00343 else 00344 { 00345 p2 = p1; 00346 p4 = p3; 00347 } 00348 00349 //blend four colors 00350 double alphaY = yp - y; 00351 double alphaX = xp - x; 00352 00353 p1 = blendColors( p1, p2, alphaX ); 00354 p3 = blendColors( p3, p4, alphaX ); 00355 p1 = blendColors( p1, p3, alphaY ); 00356 return p1; 00357 } 00358 //============================================== 00359 QRgb blendColors( QRgb color1, QRgb color2, double alpha ) 00360 { 00361 double alpha2 = 1.0-alpha; 00362 return qRgb( (int) QMAX( QMIN( 255, alpha2*qRed (color1) + alpha*qRed(color2) ), 0 ), 00363 (int) QMAX( QMIN( 255, alpha2*qGreen(color1) + alpha*qGreen(color2) ), 0 ), 00364 (int) QMAX( QMIN( 255, alpha2*qBlue (color1) + alpha*qBlue(color2) ), 0 ) ); 00365 } 00366 //============================================== 00367 DPoint findTwoLineIntersection(DPoint p1, DPoint p2, 00368 DPoint p3, DPoint p4) 00369 { 00370 //---------------------------------------------- 00371 //=== Case 1: neither line has a change in X === 00372 //---------------------------------------------- 00373 //If there is no change in x for both lines, 00374 //either lines will NEVER or ALWAYS intersect. 00375 if(p1.x() == p2.x() && 00376 p4.x() == p3.x()) 00377 { 00378 //Ok, if their x values are equal, return 00379 //intersection point as line A's point A. 00380 //Yes, this is a little arbitratry. But 00381 //theoreticaly this section of code will almost 00382 //never be executed. 00383 if( p1.x() == p3.x() ) 00384 { return DPoint( p1.x(), p1.y() ); } 00385 //Else lines will never intersect, 00386 //return pair (-32000,-32000) 00387 else 00388 { return DPoint( -32000, -32000 ); } 00389 } 00390 //---------------------------------------------- 00391 //Else, we know at least one of the lines 00392 //does NOT have a slope of infinity!!! 00393 //---------------------------------------------- 00394 00395 //---------------------------------------------- 00396 //=== Case 2: line A has no change in X === 00397 //---------------------------------------------- 00398 //If line A has an infinite slope (no change in x) 00399 //we know line B does not have an infinite slope... 00400 else if( p1.x() == p2.x() ) 00401 { 00402 double slopeB = ((double) (p4.y() - p3.y()) ) / (p4.x() - p3.x()); 00403 00404 double yInterceptB = p3.y() - slopeB*p3.x(); 00405 00406 //y = mx+b 00407 return DPoint( p2.x(), slopeB*p2.x() + yInterceptB ); 00408 } 00409 //---------------------------------------------- 00410 //=== Case 3: line B has no change in X === 00411 //---------------------------------------------- 00412 //If line B has an infinite slope (no change in x) 00413 //we know line A does not have an infinite slope... 00414 else if( p4.x() == p3.x() ) 00415 { 00416 double slopeA = ((double) (p2.y() - p1.y()) ) / (p2.x() - p1.x()); 00417 00418 double yInterceptA = p1.y() - slopeA*p1.x(); 00419 00420 //y = mx+b 00421 return DPoint( p4.x(), slopeA*p4.x() + yInterceptA ); 00422 } 00423 //---------------------------------------------- 00424 //=== Case 4: both lines have non infinite slopes === 00425 //---------------------------------------------- 00426 else 00427 { 00428 double slopeA = ((double) (p2.y() - p1.y()) ) / (p2.x() - p1.x()); 00429 double slopeB = ((double) (p4.y() - p3.y()) ) / (p4.x() - p3.x()); 00430 double yInterceptA = p1.y() - slopeA*p1.x(); 00431 double yInterceptB = p3.y() - slopeB*p3.x(); 00432 00433 //y1 = mx1+b 00434 //y2 = nx2+c 00435 //at intersection y1=y2 and x1 = x2 so... 00436 //mx +b = nx + c 00437 //x(m-n) = c-b 00438 //x = (c-b)/(m-n) 00439 //where m and n are slope and 00440 //b and c are y-intercepts. 00441 //x = (c-b)/(m-n) 00442 double x = (yInterceptB - yInterceptA) / (slopeA - slopeB); 00443 return DPoint( x, (slopeA * x) + yInterceptA ); 00444 } 00445 } 00446 //============================================== 00447 DPoint::DPoint() 00448 { xpos=0; ypos=0; } 00449 //============================================== 00450 DPoint::DPoint( double x, double y ) 00451 { 00452 this->xpos = x; 00453 this->ypos = y; 00454 } 00455 //============================================== 00456 double DPoint::x() const { return xpos; } 00457 double DPoint::y() const { return ypos; } 00458 //============================================== 00459 00460

Generated on Sun Mar 4 19:42:57 2007 for AlbumShaper by doxygen 1.3.7