Chequerboard Corner Detection

Camera calibration is a fundamental problem in computer vision. In the third episode of the Computer Vision for the Robotic Age podcast I am demonstrating a robust algorithm for identifying the corners of a chequerboard pattern. Identifying the corners of a calibration grid is the initial step for camera calibration.

require 'rubygems'
require 'hornetseye_ffmpeg'
require 'hornetseye_xorg'
include Hornetseye
class Node
  # Non-maxima suppression for corners
  def nms(threshold)
    # compare image with dilated image and threshold
    self >= dilate.major(threshold)
  end
  # Find a component with 'n' corners
  def have(n, corners)
    # compute number of corners for each component
    hist = mask(corners).histogram max + 1
    # compare number of corners with desired number
    msk = hist.eq n
    if msk.inject :or
      # get label of connected component
      id = argmax { |i| msk.to_ubyte[i] }.first
      # get component mask
      eq id
    else
      # return nil
      nil
    end
  end
  def corners(sigma = 5.0, size = 21)
    size2 = size / 2
    # generate chequer pattern
    f1 = finalise(size, size) do |i,j|
      x, y = i - size2, j - size2
      x * y * Math.exp( -(x ** 2 + y ** 2) / sigma ** 2)
    end
    # generate chequer pattern rotated by 45°
    f2 = finalise(size, size) do |i,j|
      x, y = i - size2, j - size2
      0.5 * (x ** 2 - y ** 2) * Math.exp( -(x ** 2 + y ** 2) / sigma ** 2)
    end
    # apply filter pair and compute corner strength
    Math.hypot convolve(f1), convolve(f2)
  end
end
# relative threshold for corner image
CORNERS = 0.6
# absolute threshold for greylevel image
THRESHOLD = 90
# width and height of calibration grid
W, H = 8, 5
W2, H2 = 0.5 * (W - 1), 0.5 * (H - 1)
N = W * H
# dilation constant
GRID = 7
# open input video
input = AVInput.new 'calibration.avi'
width, height = input.width, input.height
X11Display.show do
  # read colour image
  img = input.read_ubytergb
  # convert to greyscale
  grey = img.to_ubyte
  # call method for computing corner image
  corners = grey.corners
  # call method for non-maxima suppression
  nms = corners.nms CORNERS * corners.max
  # threshold image
  binary = grey > THRESHOLD
  # find edges using dilation and erosion
  edges = binary.dilate(GRID).and binary.erode(GRID).not
  # find connected edges
  components = edges.components
  # check for edge region with 'N' corners
  grid = components.have N, nms
  if grid
    # visualise calibration grid
    grid.and(nms).dilate.conditional RGB(255, 255, 0), img
  else
    # visualise detected corners
    nms.dilate.conditional RGB(255, 0, 0), img
  end
end

You can download a better quality version of the video here

See also:

Ruby Video Player

This is the second episode of my new Computer Vision for the Robotic Age podcast. This episode is about video-I/O. The podcast demonstrates how a video player with proper audio/video synchronisation can be implemented with the Interactive Ruby Shell. The Sintel short film (Copyright Blender Foundation) was used as a video for testing.

Here’s the source code of the Ruby video player created in the podcast:

require 'rubygems'
# load FFMPEG bindings
require 'hornetseye_ffmpeg'
# load X.Org bindings
require 'hornetseye_xorg'
# load ALSA bindings
require 'hornetseye_alsa'
# include the namespace
include Hornetseye
# open a video file
input = AVInput.new 'sintel.mp4'
# open sound output with sampling rate of video
alsa = AlsaOutput.new 'default:0', input.sample_rate, input.channels
# read first audio frame
audio_frame = input.read_audio
# display images using width of 600 pixels and XVideo hardware acceleration
X11Display.show 600, :output => XVideoOutput do |display|
  # read an image
  img = input.read
  # while there is space in the audio output buffer ...   
  while alsa.avail >= audio_frame.shape[1]
    # ... write previous frame to audio buffer
    alsa.write audio_frame
    # read new audio frame
    audio_frame = input.read_audio
  end
  # compute difference of video clock to audio clock
  delay = input.video_pos - input.audio_pos + (alsa.delay + audio_frame.shape[1]).quo(alsa.rate)
  # suspend program in order to synchronise the video with the audio
  display.event_loop [delay, 0].max
  # display image
  img
end

You can also download the video here

See Also:

Background Replacement

This is the first episode of my new Computer Vision for the Robotic Age podcast. This episode is on replacing the background of a live video with another video. The background replacement algorithm is implemented live using the HornetsEye real-time computer vision library for the Ruby programming language.

You can also download the video here

I am new to podcasting. So feel free to let me know any suggestions.

See Also:

Camera Calibration

I am currently working on camera calibration. Many implementations require the user to manuallly point out corners. Here is an idea on how to detect and label corners automatically.

  1. Apply Otsu Thresholding to input image.
  2. Take difference of dilated and eroded image to get edge regions.
  3. Label connected components.
  4. Compute corners of input image (and use non-maxima suppression).
  5. Count corners in each component.
  6. Look for a component which contains exactly 40 corners.
  7. Get largest component of inverse of grid (i.e. the surroundings).
  8. Grow that component and find all corners on it (i.e. corners on the boundary of the grid).
  9. Find centre of gravity of all corners and compute vectors from centre to each boundary corner.
  10. Sort boundary corners by angle of those vectors.
  11. Use non-maxima suppression on list of length of vectors to get the 4 “corner corners” (convexity).
  12. Use the locations of the 4 “corner corners” to compute a planar homography mapping the image coordinates of the 8 times 5 grid to the ranges 0..7 and 0..4 respectively.
  13. Use the homography to transform the 40 corners and round the coordinates.
  14. Order the points using the rounded coordinates.

Further work is about taking several images to perform the actual camera calibration.

Thanks to Manuel Boissenin for suggesting convexity for finding the “corner corners”.

Update:

After calibrating the camera the ratio of focal length to pixel size is known (also see Zhengyou Zhang’s camera calibration). Once the camera is calibrated, it is possible to estimate the 3D pose of the calibration grid in every frame.

I have created a screencast on how to locate the chequerboard calibration pattern.

See also:

Broken Tonight