Final Year Project

FYP CA2

Introduction

Augmented Reality is defined as the modification of human visual perception of reality by imposing additional stimuli generated by the computer, such as 3D images. The stimuli can take many forms such as audio, visual markings, or even tactile feedback. As a comparison, virtual reality completely substitutes the real world with computer-generated reality.

There are many applications of AR in the modern world. Those include advertising, task support (e.g. medical surgery), navigation, entertainment and military services (e.g. for training purposes).

Areas of research

According to “Trends in Augmented Reality Tracking, Interaction and Display: A Review of Ten Years of ISMAR”, the core research of AR can be broken down into 5 main research areas:

1.       Tracking techniques

2.       Interaction techniques

3.       Calibration and registration

4.       AR applications

5.       Display techniques

However, the focus is mainly on tracking and calibration and registration as they are the fundamentals of AR.

In order to augment something, an image of the real world is required, and tracking algorithms are applied onto it. There are 2 types of tracking: marker-based tracking and natural feature tracking. Marker-based, as the name suggests, requires a fiducial marker in order to augment an object. Those markers are commonly square markers, as shown in figure 1.1. Natural feature tracking tracks an image by means of estimating the keypoints of the image, as shown in figure 1.2.

figure 1.1

figure 1.2

For natural feature tracking, the object that is to be detected is trained for its robust keypoints and stored into a database. Robust keypoints of an object are points that are stable, i.e. those points are robust to changes in illumination, noise, and minor changes in viewpoint. In addition, they are highly distinctive, relatively easy to extract and allow for correct object identification with low probability of mismatch. Elaboration on tracking will be discussed in the sections below.

Calibration is to determine the intrinsic properties of the camera, as well as the camera position when it is viewing the image. Intrinsic properties include the focal length coefficients and the principal points of the camera. The camera position refers to the transformation matrix (rotation and translation) of the camera in the real world when viewing the image. This transformation matrix can be estimated using algorithms such as EPnP (Efficient Perspective n Points).

Registration is the augmenting of virtual objects onto the image. Those virtual objects can be drawn onto the screen using graphic libraries such as OpenGL. After a square marker that exist in the database is found in the image (for marker-based tracking), or an object in the database is detected in the image (for nature feature tracking), the virtual object is drawn onto the image. Orientation of the virtual object is determined by the transformation matrix of the camera position calculated as mentioned in the above paragraph.

Research Question

The research question is to form a new algorithm by combining existing open-sources to accommodate real-time tracking and rendering on the mobile platform navigation, and making it open-source.

FYP overview

As mentioned in the introduction above, there are many applications for AR. However, the aim of this FYP is to develop an AR training system for Military purposes, namely for the CBRD (Chemical, Biological and Radiological Defense) of the SAF.

During operations and trainings, soldiers of the CBRD have to wear the MOPP (Mission Oriented Protective Posture) suit, which includes the protective gas mask. This makes it impossible for the soldier to be equipped with Head-Mounted Device (HMD) of any sort. Hence, until there is improvement on the hardware factor of the HMD, the usage of mobile devices, such as tablets, is the best option.

Special posters are used as feature points for AR tracking and augmenting during training. Those posters are placed at desired places for virtual objects to be augmented at.

Existing Similar AR SDKs on the Mobile Platform

There exist similar mobile AR SDKs in the market. 3 of the most popular SDKs are listed below:

1.       QualComm

2.       Metaio

3.       Layar

QualComm

The QualComm AR SDK (QCAR) supports multiple development tools including Eclipse (for Android), Xcode (for iOS), and Unity. It uses its own QualComm patented FastCV algorithms for tracking and detecting, which is optimised for the mobile platform. Images from users are processed via cloud computing to QualComm’s server and the results are sent back to the user. However, it is closed-source.

figure 2

Metaio

The Metaio Unifeye works similarly with QualComm, which also uses cloud computing. It requires purchase. The Metaio Unifeye is fully configured and controlled via graphical control elements, thus programming knowledge is not required. It features marker tracking, 2D planar markerless tracking, face tracking and extensible tracking. Like QualComm, its implementations are close-source.

Layar

The Layar, too, uses cloud computing for processing the images. Layar requires subscription. Payment is made per matches of the image. Layar uses images of users to extract fingerprints (of the image). The user remains the owner of his reference images but Layar owns the fingerprints and reserves the rights to use them in all its products. It features nature feature tracking, and excels on planar surfaces. However, Layar is also close-source.

Since the existing SDKs are close-source, users do not know that is being done to their images. Through this FYP, users can use or modify the codes to suit their purpose. Furthermore, these existing SDKs cannot be used with the CBRD training system, as all changes made to the SDKs must be consulted with the companies of the SDKs.

Tracking Algorithms

As mentioned before, tracking is the first thing needed for AR. Currently, there are many algorithms for tracking and detection, with SIFT (scale-invariant feature tracking) and SURF (speeded-up robust feature) being the most popular algorithms used. Some of these algorithms have already been implemented into the OpenCV library, hence the choice of using the OpenCV library in this FYP. Furthermore, being an open source library, improvements can be implemented into the library when necessary.

Before applying those algorithms, the image has to undergo gray-scaling. Then, Gaussian Blurring (also known as Gaussian Smoothing) is applied in order to reduce image noise and details, usually with an octave of 4.

figure 3: Original image

figure 4: image blurred using Gaussian blur

Below is a list of some popular tracking algorithms and their comparison.

SIFT:

SIFT feature descriptor is invariant to uniform scaling, orientation, and affine distortion. Important characteristic of these features is that the relative positions between them in the original scene should not change from one image to another.

Scale-space approximation

In the first step of SIFT, several octaves of the original image are generated. Each octave’s image size is half the previous one. Within an octave, images are progressively blurred using the Gaussian Blur operator (Utkarsh). Scale spaces are usually implemented as an image pyramid, where the images are scaled down with the same ratio. Those Gaussian-blurred images are sub-sampled through Difference of Gaussian (DoG) in order to achieve a higher level of the pyramid.

figure 5: Difference of Gaussian (DoG)

After creating the Gaussian Pyramid, keypoints of the image can then be found. Finding keypoints is done by locating Maxima/minima in DoG images.

Locating Keypoints

This is done by iterating through each pixel and check against all its neighbours. This check is done within the current image, the image above it and as well as below it.

figure 6:Checking the pixel marked ‘X’ against its neighbours, marked green

The process is illustrated in figure 6. The pixel X is marked as a keypoint if it is the greatest or least of all 26 neighbours. However, a keypoint almost never lies exactly on a single pixel. Therefore, subpixel values are generated using Taylor expansion of the image around the estimated keypoint.

Keypoints Removal

Several keypoints are generated with some of them lying on an edge or not having enough contrast, hence not useful as feature keypoints.

Low contrast keypoints

To remove low contrast keypoints, the magnitude of the intensity of the pixel/subpixel in the DoG image is checked against a certain value. If the magnitude is less, the keypoint is rejected.

Keypoints along an edge

2 gradients, both perpendicular to each other, are calculated. Based on the image around the keypoint, three possibilities exist:

1.       A flat region: both gradients will be small.

2.       An edge: one gradient will be big (perpendicular to the edge) and the other will be small (along the edge)

3.       A “corner”: both gradients will be big.

A corner makes an excellent feature point, hence algorithm similar to the Harris Corner Detection is used to check if it is a corner. The keypoint is rejected if it is not a corner.

By reducing the number of unnecessary keypoints, efficiency and robustness of SIFT is increased.

Keypoint Orientation Assignment

An “orientation collection region” is formed around the keypoint. Within this region, the most prominent orientation is calculated and assigned to that keypoint. The following formula is used to calculate the magnitude and orientation of each pixel in the region:

where m(x,y) is the magnitude and θ(x,y) is the orientation.

A histogram is then created using the results:

figure 7: Histogram of magnitude proportion and orientation bins

In the above histogram, the 360 degrees of orientation are broken into 36 bins (each 10 degrees). For example, the gradient direction at a certain point (in the “orientation collection region”) is 18.759 degrees, and it will be classified under the 10-19 degree bin. And the “amount” that is added to the bin is proportional to the magnitude of gradient at that point. The orientation with the highest peak will then be assigned to the current keypoint that is being checked.

SIFT feature generation

The last step is to generate unique fingerprints for each of the keypoints left. A 16×16 window of sub-pixels around the keypoint is chosen and then split into sixteen 4×4 windows. From each 4×4 window, a histogram of 8 bins is generated. Each bin corresponding to 0-44 degrees, 45-89 degrees, etc. Gradient orientations from the 4×4 are put into these bins. This is done for all 4×4 blocks, giving a result consisting of 4×4×8 (128) values. Finally, the 128 values are normalized, giving the keypoint a unique feature vector.

SURF (Speeded-Up Robust Features):

SURF is a method inspired by the SIFT algorithm with some differences in determine the keypoints.

Difference in Scale-space approximation

In SIFT, the image is scaled and blurred in a Gaussian Pyramid way. However, in SURF, the image is filtered “using a box filter approximation of second-order Gaussian partial derivatives, since integral images allow the computation of rectangular box filters in near constant time” (Luo, Gwun).

Hessian Matrix-Based Keypoints

The SURF detector is based on the Hessian matrix determinant. If the determinant of that pixel is a maximum, it is a keypoint. This method is accurate and much faster than SIFT.

FERNS:

The FERNS algorithm follows the same steps as the SIFT from the beginning until and including the part where keypoints are reduced, i.e. both algorithms have different ways of assigning unique identity to the keypoints of an image.

Approach

Problems of matching keypoints of an object are casted into classification problems. Firstly, the image undergoes partitioning, using algorithms such as k-means clustering, to create patches around its keypoints of the image. Ferns are then used to classify those patches. A visual representation of this approach is given in figure 8.The Semi-Naïve Bayesian approach is used for patch recognition between objects in the database and the image.

figure 8: Visual Representation of classifying patches