Photographic document images are often rotated, if only slightly. This code mediates an input of a series of four points--assumed to be the corners of a rectangular document--in any order, as mouse clicks. Then it determines the orientation of the points and calculates a "quality" value, as an indication to the user of how well the four points s/he has chosen approximate to the corners of a rotated rectangle. Finally, it makes the information that it has been passed, or that it has been able to glean, available to the script that invoked it.
Python, 143 lines
Download
Copy to clipboard1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 | from sets import Set
class onePoint :
def __init__ ( self, X, Y ) :
self . x = X
self . y = Y
def __repr__ ( self ) :
return 'onePoint ( %s, %s )' % ( self . x, self . y )
def DistanceSq ( P0, P1 ) :
return ( P0 . x - P1 . x ) ** 2 + ( P0 . y - P1 . y ) ** 2
class FourCorners :
"""http://www.mathpages.com/home/kmath201.htm:
... area of the ... triangle
(x2-x3)(y1-y2) - (x1-x2)(y2-y3)
A = -------------------------------
2
In this same way it's easy to deduce that the area enclosed by a
general quadralateral can be expressed in terms of the coordinates
of its verticies as
(x2-x4)(y1-y3) - (x1-x3)(y2-y4)
A = -------------------------------
2
1 / \
= - ( (x2y1-x1y2) + (x3y2-x2y3) + (x4y3-x3y4) + (x1y4-x4y1) )
2 \ /
It's worth noting that, assuming all the verticies are in the ++
quadrant of the xy coordinate system (i.e., all the coordinates are
positive), these formulas give the positive area only if the verticies
are numbered clockwise around the perimeter. If they are counter-
clockwise, the computed area is negative. Of course, a quadralateral
can have crossing edges, such that the verticies are clockwise around
one region and counter-clockwise around the other. Thus, the computed
area of a non-degenerate quadralateral can vanish, as in the case of
the quadralateral shown in Figure 3.
"""
def __init__ ( self, alignmentImageSize, originalImageSize ) :
self . _four = [ ]
self . alignmentImageSize = alignmentImageSize
self . originalImageSize = originalImageSize
def buildResult ( self, status ) :
pointsCriterion = PointsCriterion ( * self . _four )
result = { }
for item in self . __dict__ :
result [ item ] = self . __dict__ [ item ]
for item in pointsCriterion . __dict__ :
result [ item ] = pointsCriterion . __dict__ [ item ]
result [ 'number' ] = len ( self . _four )
return result
def send ( self, pointTuple ) :
point = onePoint ( * pointTuple )
for aFour in self . _four :
if aFour . x == point . x and aFour . y == point . y :
if len ( self . _four ) < 4 :
return { 'number': len ( self . _four ), 'status': "Duplicate point (rejected)", }
else :
return self . buildResult ( "Duplicate point (rejected)" )
if len ( self . _four ) == 4 :
distances = { }
for aFour in self . _four :
distances [ DistanceSq ( aFour, point ) ] = aFour
self . _four . remove ( distances [ min ( distances ) ] )
self . _four . append ( point )
if len ( self . _four ) < 4 :
return { 'number': len ( self . _four ), 'status': "Need four distinct points", }
return self . buildResult ( 'Have four points' )
class PointsCriterion :
def QuadrilateralAreaAux ( self, P0, P1, P2, P3 ) :
return 0.5 * ( ( P1 . x - P3 . x ) * ( P0 . y - P2 . y ) - ( P0 . x - P2 . x ) * ( P1 . y - P3 . y ) )
def TriangleAreaAux ( self, P0, P1, P2 ) :
return 0.5 * ( ( P1 . x - P2 . x ) * ( P0 . y - P1 . y ) - ( P0 . x - P1 . x ) * ( P1 . y - P2 . y ) )
def __init__ ( self, P0, P1, P2, P3 ) :
areas = { }
tours = [ [ 0, 1, 2, 3 ], [ 0, 1, 3, 2 ], [ 0, 2, 1, 3 ], [ 0, 3, 1, 2 ], ]
points = [ P0, P1, P2, P3 ]
for tour in tours :
area = self . QuadrilateralAreaAux ( * tuple ( [ points [ t ] for t in tour ] ) )
if area :
if area < 0 :
tour . reverse ( )
areas [ abs ( area ) ] = tour
area = max ( areas )
clockwiseCorners = areas [ area ]
comparisonArea = 2. * self . TriangleAreaAux ( * tuple ( [ points [ t ] for t in clockwiseCorners [ : 3 ] ] ) )
corners = [ points [ p ] for p in clockwiseCorners ]
horizontals = [ corner . x for corner in corners ]
horizontals . sort ( )
verticals = [ corner . y for corner in corners ]
verticals . sort ( )
lefts = Set ( [ corner for corner in corners if corner . x in horizontals [ : 2 ] ] )
rights = Set ( [ corner for corner in corners if corner . x in horizontals [ -2 : ] ] )
uppers = Set ( [ corner for corner in corners if corner . y in verticals [ : 2 ] ] )
lowers = Set ( [ corner for corner in corners if corner . y in verticals [ -2 : ] ] )
self . upperLeft = lefts . intersection ( uppers ) . pop ( )
self . lowerLeft = lefts . intersection ( lowers ) . pop ( )
self . upperRight = rights . intersection ( uppers ) . pop ( )
self . lowerRight = rights . intersection ( lowers ) . pop ( )
self . horizontalRacking = self . lowerLeft . x - self . upperLeft . x
self . verticalRacking = self . upperRight . y - self . upperLeft . y
self . upperMost = min ( [ P . y for P in corners ] )
self . leftMost = min ( [ P . x for P in corners ] )
self . rightMost = max ( [ P . x for P in corners ] )
self . lowerMost = max ( [ P . y for P in corners ] )
self . quality = area / comparisonArea
self . corners = corners
if __name__ == "__main__" :
fourCorners = FourCorners ( ( 110, 110 ), ( 500, 500 ) )
for corner in [ ( 0, 0 ), ( 0, 0 ), ( 100, 100 ), ( 0, 100 ), ( 0, 100 ), ( 100, 0 ), ( 5, 0 ), ( 100, 0 ), ( 100, 120 ), ( 100, 101 ), ( 100, 0 ), ] :
result = fourCorners . send ( corner )
for item in result :
print item, result [ item ]
print 100 * '='
|
Tags: graphics
