- Research Overview
- MPhil Information
- Wireless Comms
- Bat System
- Broadband Phone
- Sentient Vehicles
- Task Assignment
- Computing for the Future of the Planet
- Active Floor
- Open-Source CSK Energy
DTG Local Pages
- Cambridge Weather
- Contact Details
Image Processing Algorithms
Cantag contains a large number of algorithms for different parts of the image processing pipeline. Systems designers are free to compose them in whichever way is most suitable for the application in mind. Detailed documentation can be found in the source code itself, but the following summarises the main algorithms for different pipeline tasks.
The thresholding algorithms transform a greyscale or colour image into a 1-bit binary image.
ThresholdGlobal?: A simple global thresholding. All pixels with an intensity greater than the threshold value are set to 1 and all remaining pixels are set to 0. This algorithm is computationally light and suitable for scenes with even illumination over the tracked tags.
ThresholdAdaptive?: An implementation of Pierre Wellner's Adaptive Thresholding algorithm. A sliding window (of configurable size) is moved accross the image, the average value of this window is used as the threshold. See Wellner P. "Adaptive thresholding on the DigitalDesk." EuroPARC Technical Report EPC-93-110, 1993
Contour following is performed to extract the edges in a 1-bit binary image.
ContourFollowerTree?: An implementation of Suzuki and Abe's topological structural analysis algorithm. This constructs a tree of contours from the image. Each node in the tree corresponds to a contour, all descendants of the node correspond to child-contours wholly contained within the parent. See S. Suzuki and K. Abe "Topological Structural Analysis of Digitized Binary Images by Border Following", Computer Vision, Graphics, and Image Processing, Volume 30(1), 1985
Camera Distortion Correction
At present we assume that a given camera/lens combination is calibrated offline, using something like Camera Calibration Toolbox for Matlab®. Cantag can then be sconfigured to compensate for the camera model distortion. Note that Cantag does not curretly compensate for tangential distortion, only the more common radial distortion. There are two algorithms that can be used to undistort an image:
DistortionCorrection?: A basic apprximation to the correct undistorion process. The implementation is simple and the resulting code runs fast. In most cases, this is sufficient.
DistortionCorrectionIterative?: An iterative solution to the problem of undoing radial distortion which is slower but much more accurate. if you need maximum accuracy, use this.
Shape fitting is applied to contours found in the image in order to identify those that may be a valid perspective projection of the invariant shape used in the image for inferring position and pose.
Convex Hull: This algorithm forms a convex hull of the contour. It is not a shape fitting algorithm, but a precursor to provide hints for the real algotihms.
FitEllipseLS: Fits an ellipse to the contour using a least squares approach. Costly, but accurate.
FitEllipseSimple?: A simple alternative to the least squares fitting, the approach runs faster but is less accurate
RemoveNonConcentricEllipse?: A 'helper' algorithm to remove ellipses that aren't concentric from consideration (When this occurs it is likely that the interior ellipse is not an ellipse or the overall shape is not a marker).
FitQuadTangleConvexHull?: This uses the convex hull of the points to identify the most likely candidates for the 4 corners of a quadrilateral. Used on its own, the results can be mixed.
FitQuadTangleCorner?: A simple algorithm that looks for high curvature along the contour and associates corners at the 4 highest. Although this is fast, it can suffer at high perspective distortion.
FitQuadTanglePolygon?: A Polygon simplification routine
FitQuadTangleRegression?: This algorithm can use any of the 3 above as an estimate of where the corners of a quadrilateral are. It then performs 4 linear regressions on the bodies of points between the estimates. If the regressions show a good fit, the candidate is a good one and the intersectionss of the 4 regressed lines give good estimates of the corner positions. In general, the best results are obtained when using this in conjunction with FitQuadTangleConvexHull?.
TransformQuadTangleCyberCode?: An implementation of the algorithm used to recover position and pose in Sony's Cyber Code fiducial system. A good algorithm, but susceptible to scaling errors.
TransformQuadTangleProjective?: An implementation of the widely-used linearised approach to recovering position and pose from perspective projections of squares. This is very fast, but very prone to error if the contours are noisy.
TransformQuadTangleSpaceSearch?: The most accurate (and most costly) algorithm for recovering position and pose from square markers. This postulates a marker position and pose and then iteratively improves the estimate using a minimisation algorithm. It does not suffer from any form of scaling error in the transform (unlike the other algorithms)
TransformRotateToPayload?: Until a marker has been identified it is not possible to determine an 'up' direction, and thus the orientation can only be determined to within an axis of symmetry. Once identification is complete, an 'up' direction is implicitly established, and this algorithm rotates the transform to match it.
Symbolic Code Sampling
SampleTagCircle?: Sample at the optimal point for a cicular bit patter made of sectora and rings of data.
SampleTagSquare?: Assume a regular grid for the bit pattern and sample appropriately.
CRCSymbolChunkCoder: Incorporates a CRC in the marker bit pattern so there is evidence that the marker was correctly decoded.
ParityCoder?: Uses simple parity bits to provide a level of Forward Error correction.
RawCoder?: No FEC coding, just the raw bit pattern read from the marker. Likely to contain noise.
SymbolChunkCoder?: Encode data in 'chunks'.
TripOriginalCoder?: The coding scheme used in the original implementation of the TRIP fiducial tracking system.
Render to Image
DrawEntity?: Draw a given entity (e.g. a contour, a shape, sampling points, inal marker position) to the screen
Print to Stream
PrintEntity?: Print the entity details to a stream.
Camera Position Estimation
AccumulateCorrespondences?: Searches an image for markers and forms a list of correspondences between image pixels and known 3D positions. This list can then be used to iteratively estimate the camera position in a global frame of reference.