Monthly Archives: November 2011

Realbasic: Canvas Tutorial Lesson 10 – Perspective

Last week I had a question on how to do perspective on images in RealBasic. As the answer is not that easy, I decided to make a blog post on this.

First, let’s look at what actually happens when a rectangle is put into perspective. We have to map the four corners of the picture to four points in the ‘3D’ space as shown in this illustration:

This gives us a framework to map every other point in the picture to its respective point in the 3D world.

The way to do such a mapping is using a technique called BackwardQuadrilateralTransformation. Could be the name of something out of Star Trek 🙂

But this sounds more difficult than it is. The idea of the algorithm is based on homogeneous transformation and its math is described by Paul Heckbert in his
paper. Here is a link for the ones who like to read more on this: http://graphics.cs.cmu.edu/courses/15-463/2008_fall/Papers/proj.pdf

Ready to enter the Matrix? Let’s dive into the code!

First we’ll need a class ABPoint to hold a vector:

x as integer
y as integer

Sub Constructor(x as integer, y as integer)
  me.x = x
  me.y = y
End Sub

Me make a module mPerspective that will hold the code to convert a picture from 2D to 3D space.

The main function is ABBackwardQuadrilateralTransformation. As parameters it takes the source picture, a table containing the four destination corners in the ‘3D’ space, if we want interpolation and what the backcolor of the new picture should be.

The four destination points have to be added in a clockwise order. So P0 -> P1 -> P2 -> P3.
The interpolation prameter can be used so the transformation is more smooth, but it also means it takes more time to do the conversion.

Function ABBackwardQuadrilateralTransformation(srcPic as picture, destinationQuadrilateral() as ABPoint, useInterpolation  as boolean, FillBackColor as Color) As picture

I’ll go a little more over some parts of this function. The full function can be found in the project at the end of this article.

Getting the bounds of the rectangle. What it simply does is getting the 4 most ubound points within a group of points. In our case we only have four of them but this function could find them even if you have a lot of points.

  ...
  'get bounding rectangle of the quadrilateral
  GetBoundingRectangle destinationQuadrilateral, minXY, maxXY

  dim startX as integer = minXY.X
  dim startY as integer = minXY.Y
  dim stopX as integer = maxXY.X
  dim stopY as integer = maxXY.Y
  ...

Here is the function:

Private Sub GetBoundingRectangle(cloud() as ABPoint, byref minXY as ABPoint, byref maxXY as ABPoint)
  dim minX as integer = 10e6
  dim maxX as integer = -10e6
  dim minY as integer = 10e6
  dim maxY as integer = -10e6
  
  dim i as integer
  for i = 0 to UBound(cloud)
    if cloud(i).x < minX then minX = cloud(i).x
    if cloud(i).x > maxX then maxX = cloud(i).x
    if cloud(i).y < minY then minY = cloud(i).y
    if cloud(i).y > maxY then maxY = cloud(i).y
  next
  
  minXY = new ABPoint(minX, minY)
  maxXY = new ABPoint(maxX, maxY)
End Sub

Next, we’ll need to calculate the transformation matrix. This can be done with the MapQuadToQuad() function and here is where the magic happens. You’ll notice there are two functions named MapQuadToQuad but one of them is just a help function for the other one.

The MapQuadToQuad() function will make our matrix given two rectangles. We also need some help functions to multiply two 3×3 matrixes, to calculate the adjugate of a 3×3 matrix and one to calculate the determinant of a 2×2 matrix.

If this sounds like gibberish to you, I’ll suggest you google around and read some math tutorials. Don’t worry, It’s all very basic.

  ...
  'calculate tranformation matrix
  dim srcRect(3) as ABPoint
  srcRect(0) = new ABPoint(0,0)
  srcRect(1) = new ABPoint(srcWidth -1 ,0)
  srcRect(2) = new ABPoint(srcWidth - 1, srcHeight - 1)
  srcRect(3) = new ABPoint(0, srcHeight - 1)
  dim matrix(2,2) as Double = MapQuadToQuad(destinationQuadrilateral, srcRect)
  ...

Here is are the functions:

Private Function MapQuadToQuad(input() as ABPoint, output() as ABPoint) As double(,)
  Dim squareToInput(2,2) as Double = MapQuadToQuad(input)
  Dim squareToOutput(2,2) as Double = MapQuadToQuad(output)
  
  Return MultiplyMatrix(squareToOutput, AdjugateMatrix(squareToInput))
End Function

Private Function MapQuadToQuad(Quad() as ABPoint) As double(,)
  dim sq(2,2) as double
  dim px, py as Double
  
  dim TOLERANCE as double = 1e-13
  
  px = quad(0).X - quad(1).X + quad(2).X - quad(3).X
  py = quad(0).Y - quad(1).Y + quad(2).Y - quad(3).Y
  
  if ( ( px < TOLERANCE ) And ( px > -TOLERANCE ) And ( py < TOLERANCE ) And ( py > -TOLERANCE ) ) then
    sq(0, 0) = quad(1).X - quad(0).X
    sq(0, 1) = quad(2).X - quad(1).X
    sq(0, 2) = quad(0).X
    
    sq(1, 0) = quad(1).Y - quad(0).Y
    sq(1, 1) = quad(2).Y - quad(1).Y
    sq(1, 2) = quad(0).Y
    
    sq(2, 0) = 0.0
    sq(2, 1) = 0.0
    sq(2, 2) = 1.0
  else
    
    dim dx1, dx2, dy1, dy2, del as Double
    
    dx1 = quad(1).X - quad(2).X
    dx2 = quad(3).X - quad(2).X
    dy1 = quad(1).Y - quad(2).Y
    dy2 = quad(3).Y - quad(2).Y
    
    del = Det2( dx1, dx2, dy1, dy2 )
    
    if ( del = 0 ) then
      return sq
    end if
    
    sq(2, 0) = Det2( px, dx2, py, dy2 ) / del
    sq(2, 1) = Det2( dx1, px, dy1, py ) / del
    sq(2, 2) = 1.0
    
    sq(0, 0) = quad(1).X - quad(0).X + sq(2, 0) * quad(1).X
    sq(0, 1) = quad(3).X - quad(0).X + sq(2, 1) * quad(3).X
    sq(0, 2) = quad(0).X
    
    sq(1, 0) = quad(1).Y - quad(0).Y + sq(2, 0) * quad(1).Y
    sq(1, 1) = quad(3).Y - quad(0).Y + sq(2, 1) * quad(3).Y
    sq(1, 2) = quad(0).Y
  end if
  
  return sq  
End Function

Private Function MultiplyMatrix(a(,) as double, b(,) as double) As double(,)
  ' Multiply two 3x3 matrices
  dim c (2,2) as Double
  
  c(0, 0) = a(0, 0) * b(0, 0) + a(0, 1) * b(1, 0) + a(0, 2) * b(2, 0)
  c(0, 1) = a(0, 0) * b(0, 1) + a(0, 1) * b(1, 1) + a(0, 2) * b(2, 1)
  c(0, 2) = a(0, 0) * b(0, 2) + a(0, 1) * b(1, 2) + a(0, 2) * b(2, 2)
  c(1, 0) = a(1, 0) * b(0, 0) + a(1, 1) * b(1, 0) + a(1, 2) * b(2, 0)
  c(1, 1) = a(1, 0) * b(0, 1) + a(1, 1) * b(1, 1) + a(1, 2) * b(2, 1)
  c(1, 2) = a(1, 0) * b(0, 2) + a(1, 1) * b(1, 2) + a(1, 2) * b(2, 2)
  c(2, 0) = a(2, 0) * b(0, 0) + a(2, 1) * b(1, 0) + a(2, 2) * b(2, 0)
  c(2, 1) = a(2, 0) * b(0, 1) + a(2, 1) * b(1, 1) + a(2, 2) * b(2, 1)
  c(2, 2) = a(2, 0) * b(0, 2) + a(2, 1) * b(1, 2) + a(2, 2) * b(2, 2)
 
  return c
End Function

Private Function AdjugateMatrix(a(,) as double) As double(,)
  ' Calculates adjugate 3x3 matrix
  dim b(2,2) as double
  b(0, 0) = Det2( a(1, 1), a(1, 2), a(2, 1), a(2, 2) )
  b(1, 0) = Det2( a(1, 2), a(1, 0), a(2, 2), a(2, 0) )
  b(2, 0) = Det2( a(1, 0), a(1, 1), a(2, 0), a(2, 1) )
  b(0, 1) = Det2( a(2, 1), a(2, 2), a(0, 1), a(0, 2) )
  b(1, 1) = Det2( a(2, 2), a(2, 0), a(0, 2), a(0, 0) )
  b(2, 1) = Det2( a(2, 0), a(2, 1), a(0, 0), a(0, 1) )
  b(0, 2) = Det2( a(0, 1), a(0, 2), a(1, 1), a(1, 2) )
  b(1, 2) = Det2( a(0, 2), a(0, 0), a(1, 2), a(1, 0) )
  b(2, 2) = Det2( a(0, 0), a(0, 1), a(1, 0), a(1, 1) )
  
  return b 
End Function

Private Function Det2(a as double, b as double, c as double, d as double) As double
  ' Calculates determinant of a 2x2 matrix
  return ( a * d - b * c )
End Function

Now we are ready to continue with our main function ABBackwardQuadrilateralTransformation() where we will manipulate the picture.
I worked out the two systems: with and without interpolation.

Basically what it does is map every pixel from the source rectangle to the target rectangle using the matrix we just created. When we use interpolation, we’ll use the pixels around our pixel to calculate a new color that is the mix of all those colors. This smooths the picture a little.

  dim x,y as integer
  
  dim  factor, srcX, srcY as Double
  dim tgtPic as Picture
  tgtPic = NewPicture(srcWidth, srcHeight, 32)
  tgtPic.Graphics.ForeColor = FillBackColor
  tgtPic.Graphics.FillRect 0,0, srcWidth, srcHeight
  
  dim srcRGB, tgtRGB as RGBSurface
  srcRGB = srcPic.RGBSurface
  tgtRGB = tgtPic.RGBSurface
  
  if useInterpolation then
    Dim srcWidthM1 as integer = srcWidth - 1
    Dim srcHeightM1 as Integer = srcHeight - 1
    
    'coordinates of source points
    dim dx1, dy1, dx2, dy2 as Double
    dim sx1, sy1, sx2, sy2 as Integer
    
    ' temporary pixels
    dim p1,p2,p3, p4 as Color
    dim r, g , b as integer
    
    ' for each row
    for y = startY to stopY
      'for each pixel
      for x = startX to stopX
        factor = matrix(2, 0) * x + matrix(2, 1) * y + matrix(2, 2)
        srcX = ( matrix(0, 0) * x + matrix(0, 1) * y + matrix(0, 2) ) / factor
        srcY = ( matrix(1, 0) * x + matrix(1, 1) * y + matrix(1, 2) ) / factor
        if srcX >= 0 and srcY >= 0 and srcX< srcWidth and srcY < srcHeight then
          sx1 = srcX
          if sx1 = srcWidthM1 then
            sx2 = sx1
          else
            sx2 = sx1 + 1
          end if 
          dx1 = srcX - sx1
          dx2 = 1.0 - dx1
          
          sy1 = srcY
          if sy1 = srcHeightM1 then
            sy2 = sy1 
          else
            sy2 = sy1 + 1
          end if
          dy1 = srcY - sy1
          dy2 = 1.0 - dy1
          
          ' copy the pixel from the source to the target using interpolation of 4 points
          p1 = srcRGB.Pixel(sx1, sy1)
          p2 = srcRGB.Pixel(sx2, sy1)
          p3 = srcRGB.Pixel(sx1, sy2)
          p4 = srcRGB.Pixel(sx2, sy2)
          
          r = dy2 * ( dx2 * ( p1.red ) + dx1 * ( p2.red ) ) + dy1 * ( dx2 * ( p3.red ) + dx1 * ( p4.red ) ) 
          g = dy2 * ( dx2 * ( p1.green ) + dx1 * ( p2.green ) ) + dy1 * ( dx2 * ( p3.green ) + dx1 * ( p4.green ) ) 
          b = dy2 * ( dx2 * ( p1.blue ) + dx1 * ( p2.blue ) ) + dy1 * ( dx2 * ( p3.blue ) + dx1 * ( p4.blue ) ) 
          tgtRGB.Pixel(x,y) = RGB(r,g,b)
        end if
      next
    next
  else
    ' for each row
    for y = startY to stopY
      'for each pixel
      for x = startX to stopX
        factor = matrix(2, 0) * x + matrix(2, 1) * y + matrix(2, 2)
        srcX = ( matrix(0, 0) * x + matrix(0, 1) * y + matrix(0, 2) ) / factor
        srcY = ( matrix(1, 0) * x + matrix(1, 1) * y + matrix(1, 2) ) / factor
        if srcX >= 0 and srcY >= 0 and srcX< srcWidth and srcY < srcHeight then
          ' copy the pixel from the source to the target
          tgtRGB.Pixel(x,y) = srcRGB.Pixel(srcX, srcY)
        end if
      next
    next
  end if
  
  Return tgtPic  

And we’re done! In the project you can download I added a system so you can easily change the four ‘3D’ points and see the result of the transformation.

Here is a little demo video of the program at work:

And here is the project:
http://www.gorgeousapps.com/Tut10.zip

Until next time!

Click here to Donation if you like my work

Advertisements

Realbasic: Emboss filter


I’m checking out several ways to do computer vision and Embossing may be a pre-filter I will use to find endges fast.

Writing an Emboss filter turned out to be easier than I thought. The principle is that a pixel in the image is replaced either by a highlight or a shadow, depending if the boundaries in the picture are light or dark.

If the contrast is low, then it becomes gray.

Here is the code for an emboss filter in Realbasic.

Function Emboss(tmpPic as picture) As picture
  dim width as integer = tmpPic.Width
  dim height as integer = tmpPic.Height
  
  dim srcSurf as RGBSurface = tmpPic.RGBSurface
  
  Dim dst as Picture
  dst = NewPicture(width, height, 32)
  
  dim dstSurf as RGBSurface = dst.RGBSurface
  
  dim i, j as integer
  dim upperLeft, LowerRight as Color
  dim redDiff, greenDiff, blueDiff, Diff  as integer
  dim grayColor as integer
  dim newColor as Color
  
  for i  = 0 to height - 1
    for j = 0 to width - 1
      if i > 0 and j > 0 then
        upperLeft = srcSurf.Pixel(j-1,i-1)
      end if
      if i < height - 2 and j < width - 2 then
        LowerRight = srcSurf.Pixel(j+1,i+1)
      end if
      redDiff = bitwise.bitAnd(LowerRight.Red, 255) - bitwise.bitAnd(upperLeft.Red, 255)
      redDiff = bitwise.bitAnd(LowerRight.Green, 255) - bitwise.bitAnd(upperLeft.Green, 255)
      blueDiff = bitwise.bitAnd(lowerRight.Blue, 255) - bitwise.bitAnd(upperLeft.Blue, 255)
      
      diff = redDiff
      if (abs(greenDiff) > abs(diff)) then
        diff = greenDiff
      end if
      if (abs(blueDiff) > abs(diff)) then
        diff = blueDiff
      end if
      
      grayColor = 128 + diff
      
      if (grayColor > 255) then
        grayColor = 255
      elseif (grayColor < 0) then
        grayColor = 0
      end if
      newColor = RGB(grayColor, grayColor, grayColor)
      
      dstSurf.Pixel(j, i) = newColor
    next
  next
  
  Return dst
  
End Function

See ya!

Click here to Donation if you like my work


%d bloggers like this: