Main Page | Namespace List | Class Hierarchy | Class List | Directories | 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   QImage rotatedImage( originalImage.width(), originalImage.height(), originalImage.depth() );
00137   
00138   //setup progress bar
00139   QString statusMessage = qApp->translate( "correctImageTilt", "Correcting Tilt:" );
00140   status->showProgressBar( statusMessage, 200 );
00141   qApp->processEvents();  
00142   
00143   //during the first phase update the status bar for every 1% of image pixels that are processed
00144   int updateIncrement = (int) ( 0.01 * originalImage.width() * originalImage.height() );
00145   int newProgress = 0;
00146   
00147   //set each pixel to the rotated value
00148   double xp, yp;
00149   
00150   double w2 = 0.5 * rotatedImage.width();
00151   double h2 = 0.5 * rotatedImage.height();
00152   
00153   int x,y;
00154   uchar* scanLine;
00155   QRgb* rgb;
00156   for( y=0; y<rotatedImage.height(); y++)
00157   {   
00158     //iterate over each selected pixel in scanline
00159     scanLine = rotatedImage.scanLine(y);
00160     for( x=0; x<rotatedImage.width(); x++)
00161     {
00162       //compute unrotated coordinates
00163       xp = cosTheta*(x-w2) + sinTheta*(y-h2) + w2;
00164       yp = -sinTheta*(x-w2) + cosTheta*(y-h2) + h2;
00165 
00166       //set unrotated value
00167       rgb = ((QRgb*)scanLine+x);
00168       *rgb = interpolatedPixelValue( xp, yp, &originalImage);
00169 
00170       //update status bar if significant progress has been made since last update
00171       newProgress++;
00172       if(newProgress >= updateIncrement)
00173       {
00174         newProgress = 0;
00175         status->incrementProgress();
00176         qApp->processEvents();  
00177       }
00178       
00179     }
00180   }
00181   
00182   //find rotated corners
00183   double nTheta = -theta;
00184   double sinNTheta = sin( nTheta );
00185   double cosNTheta = cos( nTheta );
00186   
00187   DPoint topLeft = DPoint( cosNTheta*(-w2) + sinNTheta*(-h2) + w2,
00188                            -sinNTheta*(-w2) + cosNTheta*(-h2) + h2 );
00189 
00190   DPoint topRight = DPoint( cosNTheta*(w2) + sinNTheta*(-h2) + w2,                           
00191                             -sinNTheta*(w2) + cosNTheta*(-h2) + h2 );
00192   
00193   DPoint bottomLeft = DPoint( cosNTheta*(-w2) + sinNTheta*(h2) + w2,                           
00194                               -sinNTheta*(-w2) + cosNTheta*(h2) + h2 );
00195   
00196   DPoint bottomRight = DPoint( cosNTheta*(w2) + sinNTheta*(h2) + w2,                           
00197                                -sinNTheta*(w2) + cosNTheta*(h2) + h2 );
00198   
00199   //determine which of these points are which in their rotated form
00200   DPoint top, bottom, left, right;
00201   if( theta < 0 )
00202   {
00203     top = topRight;
00204     bottom = bottomLeft;
00205     left = topLeft;
00206     right = bottomRight;
00207   }
00208   else
00209   {
00210     top = topLeft;
00211     bottom = bottomRight;    
00212     left = bottomLeft;
00213     right = topRight;
00214   }
00215   
00216   //construct true corners
00217   DPoint trueTopLeft    ( 0, 0 );
00218   DPoint trueTopRight   ( rotatedImage.width()-1, 0 );
00219   DPoint trueBottomLeft ( 0, rotatedImage.height()-1 );
00220   DPoint trueBottomRight( rotatedImage.width()-1, rotatedImage.height()-1 );
00221   
00222   //find intersections with image boundary
00223   DPoint topEdgeL = findTwoLineIntersection( left, top, trueTopLeft, trueTopRight );
00224   DPoint topEdgeR = findTwoLineIntersection( top, right, trueTopLeft, trueTopRight );
00225                                             
00226   DPoint bottomEdgeL = findTwoLineIntersection( left, bottom, trueBottomLeft, trueBottomRight );
00227   DPoint bottomEdgeR = findTwoLineIntersection( bottom, right, trueBottomLeft, trueBottomRight );
00228 
00229   DPoint leftEdgeT = findTwoLineIntersection( left, top, trueTopLeft, trueBottomLeft );
00230   DPoint leftEdgeB = findTwoLineIntersection( left, bottom, trueTopLeft, trueBottomLeft );
00231     
00232   DPoint rightEdgeT = findTwoLineIntersection( right, top, trueTopRight, trueBottomRight );
00233   DPoint rightEdgeB = findTwoLineIntersection( right, bottom, trueTopRight, trueBottomRight );
00234   
00235   //shot rays out from image center to each true corner and find intersections with clipped corners
00236   DPoint center( (int)w2, (int)h2 );
00237   DPoint safeTopLeft     = findTwoLineIntersection( center, trueTopLeft, leftEdgeT, topEdgeL );
00238   DPoint safeTopRight    = findTwoLineIntersection( center, trueTopRight, rightEdgeT, topEdgeR );
00239   DPoint safeBottomLeft  = findTwoLineIntersection( center, trueBottomLeft, leftEdgeB, bottomEdgeL );
00240   DPoint safeBottomRight = findTwoLineIntersection( center, trueBottomRight, rightEdgeB, bottomEdgeR );
00241   
00242   //find constrained area
00243   double minY = QMAX( safeTopLeft.y(), safeTopRight.y() );
00244   double maxY = QMIN( safeBottomLeft.y(), safeBottomRight.y() );
00245   
00246   double minX = QMAX( safeTopLeft.x(), safeBottomLeft.x() );
00247   double maxX = QMIN( safeTopRight.x(), safeBottomRight.x() );
00248 
00249   //find contrained area in integer coordinates. this is semi-tricky.
00250   //if the minimum values decimal porition is nonzero then increment by one 
00251   // (eg 5.37 -> 6)
00252   int xMin = (int) minX;
00253   int xMax = (int) maxX;
00254   
00255   int yMin = (int) minY;
00256   int yMax = (int) maxY;
00257   
00258   if( xMin < minX ) xMin++;
00259   if( yMin < minY ) yMin++;
00260   
00261   //construct cropped rotated image
00262   QImage* editedImage = new QImage( xMax - xMin + 1,
00263                                     yMax - yMin + 1,
00264                                     rotatedImage.depth() );    
00265 
00266   //during the second phase update the status bar for every 1% of cropped pixels that are procesed
00267   updateIncrement = (int) ( 0.01 * editedImage->width() * editedImage->height() );
00268   newProgress = 0;
00269   
00270   int x2,y2;
00271   uchar* scanLine2;
00272   QRgb* rgb2;
00273 
00274   y2 = 0;
00275   for( y=yMin; y<=yMax; y++, y2++)
00276   {   
00277     //iterate over each selected pixel in scanline
00278     scanLine = rotatedImage.scanLine(y);
00279     scanLine2 = editedImage->scanLine(y2);
00280 
00281     x2 = 0;
00282     for( x=xMin; x<=xMax; x++, x2++)
00283     {
00284       rgb  = ((QRgb*)scanLine +x );
00285       rgb2 = ((QRgb*)scanLine2+x2);
00286       *rgb2 = *rgb;      
00287 
00288       //update status bar if significant progress has been made since last update
00289       newProgress++;
00290       if(newProgress >= updateIncrement)
00291       {
00292         newProgress = 0;
00293         status->incrementProgress();
00294         qApp->processEvents();  
00295       }
00296     
00297     }
00298   }
00299   
00300   //remove status bar
00301   status->setStatus( "" );
00302   qApp->processEvents();  
00303   
00304   //return pointer to edited image
00305   return editedImage;
00306 }
00307 //==============================================
00308 QRgb interpolatedPixelValue( double xp, double yp,
00309                              QImage* image )
00310 {
00311   //do boundary checking to 
00312   //ensure we don't read beyond image boundaries
00313   if(xp < 0 || xp >= image->width() ||
00314      yp < 0 || yp >= image->height() )
00315     return qRgb( 0, 0, 0 );
00316 
00317   //get four pixel colors, 
00318   int x = (int)xp;
00319   int y = (int)yp;
00320   
00321   uchar* scanLine1 = image->scanLine( y );
00322 
00323   uchar* scanLine2;
00324   if( y < image->height() - 1 )
00325     scanLine2 = image->scanLine( y+1 );
00326   else
00327     scanLine2 = scanLine1;
00328   
00329   QRgb p1,p2,p3,p4;
00330   
00331   p1 = *((QRgb*)scanLine1+x);
00332   p3 = *((QRgb*)scanLine2+x);
00333         
00334   if( x < image->width() - 1)
00335   {
00336     p2 = *((QRgb*)scanLine1+x+1);
00337     p4 = *((QRgb*)scanLine2+x+1);     
00338   }
00339   else
00340   {
00341     p2 = p1;
00342     p4 = p3;
00343   }
00344   
00345   //blend four colors
00346   double alphaY = yp - y;
00347   double alphaX = xp - x;
00348   
00349   p1 = blendColors( p1, p2, alphaX );
00350   p3 = blendColors( p3, p4, alphaX );
00351   p1 = blendColors( p1, p3, alphaY );
00352   return p1;
00353 }
00354 //==============================================
00355 QRgb blendColors( QRgb color1, QRgb color2, double alpha )
00356 {
00357   double alpha2 = 1.0-alpha;
00358   return qRgb( (int) QMAX( QMIN( 255, alpha2*qRed  (color1) + alpha*qRed(color2)   ), 0 ),
00359                (int) QMAX( QMIN( 255, alpha2*qGreen(color1) + alpha*qGreen(color2) ), 0 ),
00360                (int) QMAX( QMIN( 255, alpha2*qBlue (color1) + alpha*qBlue(color2)  ), 0 ) );
00361 }
00362 //==============================================
00363 DPoint findTwoLineIntersection(DPoint p1, DPoint p2,
00364                                DPoint p3, DPoint p4)
00365 {
00366   //----------------------------------------------
00367   //=== Case 1: neither line has a change in X ===
00368   //----------------------------------------------
00369   //If there is no change in x for both lines, 
00370   //either lines will NEVER or ALWAYS intersect.
00371   if(p1.x() == p2.x() &&
00372      p4.x() == p3.x())
00373   {
00374     //Ok, if their x values are equal, return 
00375     //intersection point as line A's point A.
00376     //Yes, this is a little arbitratry. But 
00377     //theoreticaly this section of code will almost
00378     //never be executed.
00379     if( p1.x() == p3.x() )
00380     { return DPoint( p1.x(), p1.y() ); }
00381     //Else lines will never intersect,
00382     //return pair (-32000,-32000)
00383     else
00384     { return DPoint( -32000, -32000 ); }
00385   } 
00386   //----------------------------------------------
00387   //Else, we know at least one of the lines 
00388   //does NOT have a slope of infinity!!!
00389   //----------------------------------------------
00390   
00391   //----------------------------------------------
00392   //=== Case 2: line A has no change in X      ===
00393   //----------------------------------------------
00394   //If line A has an infinite slope (no change in x)
00395   //we know line B does not have an infinite slope...
00396   else if( p1.x() == p2.x() )
00397   {
00398     double slopeB = ((double) (p4.y() - p3.y()) ) / (p4.x() - p3.x());
00399     
00400     double yInterceptB = p3.y() - slopeB*p3.x();
00401     
00402     //y = mx+b
00403     return DPoint( p2.x(), slopeB*p2.x() + yInterceptB );
00404   }
00405   //----------------------------------------------
00406   //=== Case 3: line B has no change in X      ===
00407   //----------------------------------------------
00408   //If line B has an infinite slope (no change in x)
00409   //we know line A does not have an infinite slope...
00410   else if( p4.x() == p3.x() )
00411   {
00412     double slopeA = ((double) (p2.y() - p1.y()) ) / (p2.x() - p1.x());
00413     
00414     double yInterceptA = p1.y() - slopeA*p1.x();
00415     
00416     //y = mx+b
00417     return DPoint( p4.x(), slopeA*p4.x() + yInterceptA );
00418   }
00419   //----------------------------------------------
00420   //=== Case 4: both lines have non infinite slopes ===
00421   //----------------------------------------------
00422   else
00423   {
00424     double slopeA = ((double) (p2.y() - p1.y()) ) / (p2.x() - p1.x());
00425     double slopeB = ((double) (p4.y() - p3.y()) ) / (p4.x() - p3.x());
00426     double yInterceptA = p1.y() - slopeA*p1.x();
00427     double yInterceptB = p3.y() - slopeB*p3.x();
00428     
00429     //y1 = mx1+b
00430     //y2 = nx2+c
00431     //at intersection y1=y2 and x1 = x2 so...
00432     //mx +b = nx + c
00433     //x(m-n) = c-b
00434     //x = (c-b)/(m-n)
00435     //where m and n are slope and
00436     //b and c are y-intercepts.
00437     //x = (c-b)/(m-n)
00438     double x = (yInterceptB - yInterceptA) / (slopeA - slopeB);
00439     return DPoint( x, (slopeA * x) + yInterceptA );
00440   }
00441 }
00442 //==============================================
00443 DPoint::DPoint()
00444 { xpos=0; ypos=0; }
00445 //==============================================
00446 DPoint::DPoint( double x, double y )
00447 {
00448   this->xpos = x;
00449   this->ypos = y;
00450 }
00451 //==============================================
00452 double DPoint::x() const { return xpos; }
00453 double DPoint::y() const { return ypos; }
00454 //==============================================
00455 
00456 

Generated on Sat Apr 2 05:44:04 2005 for AlbumShaper by  doxygen 1.3.9.1