Key-frame selection for parallel tracking and mapping

A method of selecting a first image from a plurality of images for constructing a coordinate system of an augmented reality system. A first image feature in the first image corresponding to the feature of the marker is determined. A second image feature in a second image is determined based on a second pose of a camera, said second image feature having a visual match to the first image feature. A reconstructed position of the feature of the marker in a three-dimensional (3D) space is determined based on positions of the first and second image features, the first and the second camera pose. A reconstruction error is determined based on the reconstructed position of the feature of the marker and a pre-determined position of the marker.

REFERENCE TO RELATED PATENT APPLICATION(S)

This application claims the benefit under 35 U.S.C. §119 of the filing date of Australian Patent Application No. 2011253973, filed 12 Dec. 2011, hereby incorporated by reference in its entirety as if fully set forth herein.

FIELD OF INVENTION

The present invention relates generally to augmented reality (AR) systems and, in particular, to the selection of keyframes from an image sequence for use in accurate and reliable map generation and camera position determination. The present invention also relates to a method and apparatus for selecting a first image from a plurality of images for use in constructing a coordinate system of an augmented reality system. The present invention also relates to a computer program product including a computer readable medium having recorded thereon a computer program for selecting a first image from a plurality of images for use in constructing a coordinate system of an augmented reality system.

DESCRIPTION OF BACKGROUND ART

Augmented reality (AR) is a field of computer research which deals with the combination of real world and computer-generated data, where computer graphics objects are blended into real footage in real time. The majority of augmented reality image capturing systems operate with predetermined information about the environment of a user (i.e. in some form of map). The user is allowed to interact with the environment based on the predetermined information. If the map provided is comprehensive, registration can be performed directly from the map, which is a common method used in camera-based augmented reality tracking. Unfortunately, creating a comprehensive map is difficult and time-consuming. Such a map is often created manually by trained technicians, and the map is generally not sufficiently accurate unless the map is optimized by a minimisation method which is again computationally expensive.

Parallel tracking and mapping (PTAM) is an algorithm, particularly used in handheld devices such as a camera, to perform real-time tracking in scenes without the need of any prior map. A user may first place such a camera above a workspace to be tracked and press a key to select an initial keyframe for map initialisation. Typically, about one thousand (1000) natural features are extracted from the initial keyframe and tracked across subsequent frames. The user may then smoothly translate the camera to a slightly offset position and make a second key-press to provide a second keyframe. A known five-point-pose algorithm may then be used to estimate relative camera pose and triangulate the initial map using the selected key-frames and tracked feature correspondences.

One disadvantage of the five-point-pose algorithm is the requirement for human interactions during map initialisation. Some users do not understand a stereo baseline requirement required for triangulation and attempt to initialise a camera or the like using pure rotation. In addition, the five-point-pose algorithm also requires long uninterrupted tracked features. Any unintentional camera rotation and drastic camera motion may cause feature matching to fail, leaving few tracked features for map initialisation. Another method of performing real-time tracking in scenes assumes a user is initially viewing a planar scene. As the user moves a camera after selecting an initial keyframe, homography hypotheses between a current frame and an initial keyframe are generated at each frame from matched features. Each homography hypothesis is then decomposed into two or more possible three-dimensional (3D) camera poses. A second keyframe is selected based on a condition number. The condition number is the ratio of minimum to maximum eigenvalues of information matrix JTJ, where J is the Jacobian matrix of partial derivatives of each points' projection with respect to eight (8) degrees of freedom (DOF) changes to decomposition. Such a method is also not optimal since the condition number only gives indication of the scale of the errors with respect to parameters in the decomposition and does not relate directly to accuracy of 3D map points.

Another method of performing real-time tracking in scenes is a model-based method, based on the Geometric Robust Information Criterion (GRIC) model. In such a model-based method, a GRIC score is computed based on feature correspondences between an initial keyframe and a current frame. For each frame, a score is computed for each of two models (i.e., epi-polar and homography). The homography model best describes the correspondences for stereo images with a small baseline. The epi-polar model takes scene geometry into account but requires a larger baseline. A second keyframe is selected when the GRIC score of the epi-polar model is lower than the GRIC score of the homography model. However, such model-based methods require long continuous uninterrupted tracked features and computation of re-projection errors for each tracked feature for both homography and epi-polar models, which can be computationally expensive.

Other methods of performing real-time tracking in scenes make an implicit assumption that a sufficiently accurate initial 3D map can be created when either temporal distance between two keyframes or track length of tracked features is larger than a fixed threshold. Such assumptions are often incorrect since distance of the features from a camera affects required distance between keyframes.

SUMMARY OF THE INVENTION

According to one aspect of the present disclosure there is provided a method of selecting a first image from a plurality of images for constructing a coordinate system of an augmented reality system along with a second image, said method comprising:

determining a first image feature in the first image corresponding to the feature of the marker associated with the first image, the first image feature being determined based on a first pose of a camera used to capture the first image;

determining a second image feature in a second image based on a second pose of a camera used to capture the second image, said second image feature having a visual match to the first image feature;

determining a reconstructed position of the feature of the marker based on positions of the first and second image features, the first camera pose and the second camera pose;

determining a reconstruction error based on the reconstructed position of the feature of the marker and a pre-determined position of the marker; and

selecting the first image for constructing the coordinate system of the augmented reality system in an event that the determined reconstruction error indicates that the first pose and the second pose of cameras capturing said first and second images satisfies a pre-determined criterion for scene reconstruction.

According to another aspect of the present disclosure there is provided an apparatus for selecting a first image from a plurality of images, said apparatus comprising:

means for determining a first image feature in the first image corresponding to the feature of a marker associated with the first image, the first image feature being determined based on a first pose of a camera used to capture the first image;

means for determining a second image feature in a second one of the plurality of images based on a second pose of a camera used to capture the second image, said second image feature having a visual match to the first image feature;

means for determining a reconstructed position of the feature of the marker based on positions of the first and second image features, the first camera pose and the second camera pose;

means for determining a reconstruction error based on the reconstructed position of the feature of the marker and a pre-determined position of the marker; and

means for selecting the first image for constructing a coordinate system of an augmented reality system in an event that the determined reconstruction error indicates that the first pose and the second pose of cameras capturing said first and second images satisfies a pre-determined criterion for scene reconstruction.

According to still another aspect of the present disclosure there is provided a system for selecting a first image from a plurality of images, said system comprising:

a memory for storing data and computer program;

a processor coupled to said memory for executing said computer program, said computer program comprising instructions for:determining a first image feature in the first image corresponding to the feature of a marker associated with the first image, the first image feature being determined based on a first pose of a camera used to capture the first image;determining a second image feature in a second one of the plurality of images based on a second pose of a camera used to capture the second image, said second image feature having a visual match to the first image feature;determining a reconstructed position of the feature of the marker based on positions of the first and second image features, the first camera pose and the second camera pose;determining a reconstruction error based on the reconstructed position of the feature of the marker; andselecting the first image for constructing a coordinate system of an augmented reality system in an event that the determined reconstruction error indicates that the first pose and the second pose of cameras capturing said first and second images satisfies a pre-determined criterion for scene reconstruction.

According to still another aspect of the present disclosure there is provided a computer readable medium having a computer program recorded thereon for selecting a first image from a plurality of images, said program comprising:

code for determining a first image feature in the first image corresponding to the feature of a marker associated with the first image, the first image feature being determined based on a first pose of a camera used to capture the first image;

code for determining a second image feature in a second one of the plurality of images based on a second pose of a camera used to capture the second image, said second image feature having a visual match to the first image feature;

code for determining a reconstructed position of the feature of the marker based on positions of the first and second image features, the first camera pose and the second camera pose;

code for determining a reconstruction error based on the reconstructed position of the feature of the marker; and

code for selecting the first image for constructing a coordinate system of an augmented reality system in an event that the determined reconstruction error indicates that the first pose and the second pose of cameras capturing said first and second images satisfies a pre-determined criterion for scene reconstruction.

According to still another aspect of the present disclosure there is provided a method of selecting a first image from a plurality of images captured by a multi-view camera system comprising a plurality of cameras, said method comprising:

determining a first image feature in the first image corresponding to the feature of a marker associated with the first image, the first image feature being determined based on a first pose of a camera used to capture the first image;

determining a second image feature in a second one of the plurality of images based on a second pose of a camera used to capture the second image, said second image feature having a visual match to the first image feature;

determining a reconstructed position of the feature of the marker based on positions of the first and second image features, the first camera pose and the second camera pose;

determining a reconstruction error based on the reconstructed position of the feature of the marker; and

selecting the first image for constructing a coordinate system of an augmented reality system in an event that the determined reconstruction error indicates that the first pose and the second pose of cameras capturing said first and second images satisfies a pre-determined criterion for scene reconstruction.

According to still another aspect of the present disclosure there is provided an apparatus for selecting a first image from a plurality of images captured by a multi-view camera system comprising a plurality of cameras, said apparatus comprising:

means for determining a first image feature in the first image corresponding to the feature of a marker associated with the first image, the first image feature being determined based on a first pose of a camera used to capture the first image;

means for determining a second image feature in a second one of the plurality of images based on a second pose of a camera used to capture the second image, said second image feature having a visual match to the first image feature;

means for determining a reconstructed position of the feature of the marker based on positions of the first and second image features, the first camera pose and the second camera pose;

means for determining a reconstruction error based on the reconstructed position of the feature of the marker; and

means for selecting the first image for constructing a coordinate system of an augmented reality system in an event that the determined reconstruction error indicates that the first pose and the second pose of cameras capturing said first and second images satisfies a pre-determined criterion for scene reconstruction.

According to still another aspect of the present disclosure there is provided a system for selecting a first image from a plurality of images captured by a multi-view camera system comprising a plurality of cameras, said system comprising:

a memory for storing data and computer program;

a processor coupled to said memory for executing said computer program, said computer program comprising instructions for:determining a first image feature in the first image corresponding to the feature of a marker associated with the first image, the first image feature being determined based on a first pose of a camera used to capture the first image;determining a second image feature in a second one of the plurality of images based on a second pose of a camera used to capture the second image, said second image feature having a visual match to the first image feature;determining a reconstructed position of the feature of the marker based on positions of the first and second image features, the first camera pose and the second camera pose;determining a reconstruction error based on the reconstructed position of the feature of the marker; andselecting the first image for constructing a coordinate system of an augmented reality system in an event that the determined reconstruction error indicates that the first pose and the second pose of cameras capturing said first and second images satisfies a pre-determined criterion for scene reconstruction.

According to still another aspect of the present disclosure there is provided a computer readable medium having a computer program recorded thereon for selecting a first image from a plurality of images captured by a multi-view camera system comprising a plurality of cameras, said program comprising:

code for determining a first image feature in the first image corresponding to the feature of a marker associated with the first image, the first image feature being determined based on a first pose of a camera used to capture the first image;

code for determining a second image feature in a second one of the plurality of images based on a second pose of a camera used to capture the second image, said second image feature having a visual match to the first image feature;

code for determining a reconstructed position of the feature of the marker based on positions of the first and second image features, the first camera pose and the second camera pose;

code for determining a reconstruction error based on the reconstructed position of the feature of the marker; and

code for selecting the first image for constructing a coordinate system of an augmented reality system in an event that the determined reconstruction error indicates that the first pose and the second pose of cameras capturing said first and second images satisfies a pre-determined criterion for scene reconstruction.

Other aspects of the invention are also disclosed.

DETAILED DESCRIPTION OF EMBODIMENTS OF THE INVENTION

FIG. 2Ashows a video system200. The video system200comprises a moving camera220for capturing images of, for example, a scene293. The scene293is static. The moving camera220is connected to a communications network290. The communications network290may be a wide-area network (WAN), such as the Internet, a cellular telecommunications network, or a private WAN.

As seen inFIG. 2A, the video system200also includes: a computer module201; input devices such as a keyboard202, a mouse pointer device203, a scanner226and a microphone280; and output devices including a printer215, a display device214and loudspeakers217.

An external Modulator-Demodulator (Modem) transceiver device216may be used by the computer module201for communicating to and from the communications network290via a connection221. Where the connection221is a telephone line, the modem216may be a traditional “dial-up” modem. Alternatively, where the connection221is a high capacity (e.g., cable) connection, the modem216may be a broadband modem. A wireless modem may also be used for wireless connection to the communications network290.

The computer module201typically includes at least one processor unit205, and a memory unit206. For example, the memory unit206may have semiconductor random access memory (RAM) and semiconductor read only memory (ROM). The computer module201also includes a number of input/output (I/O) interfaces including: an audio-video interface207that couples to the video display214, loudspeakers217and microphone280; an I/O interface213that couples to the keyboard202, mouse203, scanner226, camera227and optionally a joystick or other human interface device (not illustrated); and an interface208for the external modem216and printer215. In some implementations, the modem216may be incorporated within the computer module201, for example within the interface208. The computer module201also has a local network interface211, which permits coupling of the computer module201via connection223to a local-area communications network222, known as a Local Area Network (LAN).

As illustrated inFIG. 2A, the local communications network222may also couple to the wide network290via a connection224, which would typically include a so-called “firewall” device or device of similar functionality. The local network interface211may comprise an Ethernet™ circuit card, a Bluetooth™ wireless arrangement or an IEEE 802.11 wireless arrangement; however, numerous other types of interfaces may be practiced for the interface211.

The I/O interfaces208and213may afford either or both of serial and parallel connectivity, the former typically being implemented according to the Universal Serial Bus (USB) standards and having corresponding USB connectors (not illustrated). Storage devices209are provided and typically include a hard disk drive (HDD)210. Other storage devices such as a floppy disk drive and a magnetic tape drive (not illustrated) may also be used. An optical disk drive212is typically provided to act as a non-volatile source of data. Portable memory devices, such optical disks (e.g., CD-ROM, DVD, Blu-ray Disc™), USB-RAM, portable, external hard drives, and floppy disks, for example, may be used as appropriate sources of data to the video system200.

The components205to213of the computer module201typically communicate via an interconnected bus204and in a manner that results in a conventional mode of operation of the video system200known to those in the relevant art. For example, the processor205is coupled to the system bus204using a connection218. Likewise, the memory206and optical disk drive212are coupled to the system bus204by connections219. Examples of computers on which the described arrangements can be practised include IBM-PC's and compatibles, Sun Sparcstations, Apple Mac™ or alike computer systems.

Methods described below may be implemented using the video system200wherein the processes ofFIGS. 1 to 6, to be described, may be implemented as one or more software application programs233executable within the video system200. In particular, the steps of the described method are effected by instructions231(seeFIG. 2B) in the software233that are carried out within the video system200. The software instructions231may be formed as one or more code modules, each for performing one or more particular tasks. The software may also be divided into two separate parts, in which a first part and the corresponding code modules performs the described methods and a second part and the corresponding code modules manage a user interface between the first part and the user.

The software may be stored in a computer readable medium, including the storage devices described below, for example. The software233is typically stored in the HDD210or the memory206. The software is loaded into the video system200from the computer readable medium, and then executed by the video system200. Thus, for example, the software233may be stored on an optically readable disk storage medium (e.g., CD-ROM)225that is read by the optical disk drive212. A computer readable medium having such software or computer program recorded on the computer readable medium is a computer program product. The use of the computer program product in the computer system200preferably effects an advantageous apparatus for implementing the described methods.

In some instances, the application programs233may be supplied to the user encoded on one or more CD-ROMs225and read via the corresponding drive212, or alternatively may be read by the user from the networks290or222. Still further, the software can also be loaded into the video system200from other computer readable media. Computer readable storage media refers to any non-transitory tangible storage medium that provides recorded instructions and/or data to the computer system200for execution and/or processing. Examples of such storage media include floppy disks, magnetic tape, CD-ROM, DVD, Blu-ray Disc, a hard disk drive, a ROM or integrated circuit, USB memory, a magneto-optical disk, or a computer readable card such as a PCMCIA card and the like, whether or not such devices are internal or external of the computer module201. Examples of transitory or non-tangible computer readable transmission media that may also participate in the provision of software, application programs, instructions and/or data to the computer module201include radio or infra-red transmission channels as well as a network connection to another computer or networked device, and the Internet or Intranets including e-mail transmissions and information recorded on Websites and the like.

The second part of the application programs233and the corresponding code modules mentioned above may be executed to implement one or more graphical user interfaces (GUIs) to be rendered or otherwise represented upon the display214. Through manipulation of typically the keyboard202and the mouse203, a user of the video system200and the application may manipulate the interface in a functionally adaptable manner to provide controlling commands and/or input to the applications associated with the GUI(s). Other forms of functionally adaptable user interfaces may also be implemented, such as an audio interface utilizing speech prompts output via the loudspeakers217and user voice commands input via the microphone280.

FIG. 2Bis a detailed schematic block diagram of the processor205and a “memory”234. The memory234represents a logical aggregation of all the memory modules (including the HDD209and semiconductor memory206) that can be accessed by the computer module201inFIG. 2A.

When the computer module201is initially powered up, a power-on self-test (POST) program250executes. The POST program250is typically stored in a ROM249of the semiconductor memory206ofFIG. 2A. A hardware device such as the ROM249storing software is sometimes referred to as firmware. The POST program250examines hardware within the computer module201to ensure proper functioning and typically checks the processor205, the memory234(209,206), and a basic input-output systems software (BIOS) module251, also typically stored in the ROM249, for correct operation. Once the POST program250has run successfully, the BIOS251activates the hard disk drive210ofFIG. 2A. Activation of the hard disk drive210causes a bootstrap loader program252that is resident on the hard disk drive210to execute via the processor205. This loads an operating system253into the RAM memory206, upon which the operating system253commences operation. The operating system253is a system level application, executable by the processor205, to fulfil various high level functions, including processor management, memory management, device management, storage management, software application interface, and generic user interface.

The operating system253manages the memory234(209,206) to ensure that each process or application running on the computer module201has sufficient memory in which to execute without colliding with memory allocated to another process. Furthermore, the different types of memory available in the system200ofFIG. 2Ais used properly so that each process can run effectively. Accordingly, the aggregated memory234is not intended to illustrate how particular segments of memory are allocated (unless otherwise stated), but rather to provide a general view of the memory accessible by the computer system200and how such is used.

As shown inFIG. 2B, the processor205includes a number of functional modules including a control unit239, an arithmetic logic unit (ALU)240, and a local or internal memory248, sometimes called a cache memory. The cache memory248typically include a number of storage registers244-246in a register section. One or more internal busses241functionally interconnect these functional modules. The processor205typically also has one or more interfaces242for communicating with external devices via the system bus204, using a connection218. The memory234is coupled to the bus204using a connection219.

The application program233includes a sequence of instructions231that may include conditional branch and loop instructions. The program233may also include data232which is used in execution of the program233. The instructions231and the data232are stored in memory locations228,229,230and235,236,237, respectively. Depending upon the relative size of the instructions231and the memory locations228-230, a particular instruction may be stored in a single memory location as depicted by the instruction shown in the memory location230. Alternately, an instruction may be segmented into a number of parts each of which is stored in a separate memory location, as depicted by the instruction segments shown in the memory locations228and229.

In general, the processor205is given a set of instructions which are executed therein. The processor205waits for a subsequent input, to which the processor205reacts to by executing another set of instructions. Each input may be provided from one or more of a number of sources, including data generated by one or more of the input devices202,203, data received from an external source across one of the networks290,202, data retrieved from one of the storage devices206,209or data retrieved from a storage medium225inserted into the corresponding reader212, all depicted inFIG. 2A. The execution of a set of the instructions may in some cases result in output of data. Execution may also involve storing data or variables to the memory234.

The described arrangements use input variables254, which are stored in the memory234in corresponding memory locations255,256,257. The described arrangements produce output variables261, which are stored in the memory234in corresponding memory locations262,263,264. Intermediate variables258may be stored in memory locations259,260,266and267.

Referring to the processor205ofFIG. 2B, the registers244,245,246, the arithmetic logic unit (ALU)240, and the control unit239work together to perform sequences of micro-operations needed to perform “fetch, decode, and execute” cycles for every instruction in the instruction set making up the program233. Each fetch, decode, and execute cycle comprises:

(a) a fetch operation, which fetches or reads an instruction231from a memory location228,229,230;

(b) a decode operation in which the control unit239determines which instruction has been fetched; and

(c) an execute operation in which the control unit239and/or the ALU240execute the instruction.

Thereafter, a further fetch, decode, and execute cycle for the next instruction may be executed. Similarly, a store cycle may be performed by which the control unit239stores or writes a value to a memory location232.

Each step or sub-process in the processes ofFIGS. 4 to 6is associated with one or more segments of the program233and is performed by the register section244,245,247, the ALU240, and the control unit239in the processor205working together to perform the fetch, decode, and execute cycles for every instruction in the instruction set for the noted segments of the program233.

The described methods may alternatively be implemented in dedicated hardware such as one or more integrated circuits performing the functions or sub functions of described methods. Such dedicated hardware may include field-programmable gate arrays (FPGA), application-specific integrated circuits (ASIC), graphic processors, digital signal processors, or one or more microprocessors and associated memories. The dedicated hardware may also include devices embedded within the cameras220,220A to220E which would otherwise have comparable functions to the arrangements performed solely in software executed within the computer module201.

In one arrangement, the described methods may be implemented as software being executed by a processor of one or more of the cameras220,220A to220E, or may be implemented using dedicated hardware within the cameras. In a still alternative arrangement, the described methods may be implemented using a hybrid arrangement of software and hardware modules.

In the example ofFIG. 2A, the scene293in a three-dimensional (3D) space comprises a 3D spherical object299, a 3D square object297and a calibration marker pattern298.

The calibration marker pattern298may be a 2D calibration marker pattern as shown inFIG. 1A, which may be used for augmented reality systems. Alternatively, the calibration marker pattern298may be a 3D calibration marker pattern as shown inFIG. 1B. Again, the 3D calibration marker pattern ofFIG. 1Bmay be used for augmented reality systems.

The calibration marker pattern298defines the scale of captured objects and the origin of a global coordinate system in the scene293. The calibration marker pattern298is assumed to be visible by the moving camera220initially for the purpose of map initialisation and is not required for later tracking and mapping operations. The calibration marker pattern298is not limited to the 2D and 3D calibration marker patterns shown inFIGS. 1A and 1B, respectively. The calibration marker pattern298may be of any type or shape as long as the calibration marker pattern298is fixed at known location and dimensions in space and is detectable in the captured image.

In one arrangement, the moving camera220is a digital still-image camera capturing images of the scene293. In an alternative arrangement, the moving camera220is a digital video camera capturing images of the scene293in the 3D space continuously at a pre-determined frame rate. In a further arrangement, the camera220is a multi-lens camera system such as a stereo camera. In yet another arrangement, a multi-view camera system comprising two or more separate cameras may be used to capture the images of the scene.

The moving camera220may be calibrated using any suitable camera calibration algorithm for determining camera intrinsic parameters. The camera intrinsic parameters, such as focal length, principal points and lens distortion parameters, may be pre-determined for the moving camera220. The moving camera220is at an initial location, denoted by the camera220in dotted lines, with respect to the scene293. As seen inFIG. 2A, captured image291represents a view of the scene293as captured by the camera220when at the initial location. The moving camera220may then be moved, as represented by arrow296, to a new location as denoted by the camera220in solid lines, where the new location is different from the initial location. For clarity, the moving camera220shown in solid lines represents the same moving camera220shown in dotted lines after the moving camera220is moved from the initial location to a new location. As seen inFIG. 2B, captured image292represents a view of the scene293as captured by the camera220at the new location.

The images291and292may be downloaded sequentially, using the processor205, from the moving camera220to the computer module201, via the communications network290. Alternatively, upon being captured, the images291and292may be sent to the computer module201by the camera220.

The computer module201receives the input images291and292captured by the moving camera220, via the network290. The images291and292may be stored within the memory206and/or the hard disk drive210. One or more keyframes (or key images) may be selected from the images291and292in accordance with a method400which will be described in detail below with reference toFIGS. 4A,4B and4C.

In accordance with the method400, expected quality of a three dimensional (3D) map295, as seen inFIG. 7, to be generated using the images291and292, is determined. If the expected quality of the 3D map295is better than a pre-determined accuracy, the two images291and292are set as keyframes (or key images) and triangulation is performed using extracted match points from the keyframes (key images) to generate the 3D map295. If the expected quality of the 3D map295is unsatisfactory, then the method400is re-executed using a different initial keyframe (key image).

FIG. 3shows an alternative configuration of the video system200, where the system200comprises multiple stationary cameras220A,220B,220C,220D, and220E connected to the network290. Each stationary camera220A,220B,220C,220D or220E operates independently. Images of the scene293, similar to the images291and292, captured by each camera220A to220E may be downloaded to the computer module201and be processed in accordance with the method400.

The method400of selecting a keyframe (key image) from a plurality of images will now be described in detail with reference toFIGS. 4A,4B and4C. The method400will be described by way of example with reference to the images291and292ofFIG. 2Acaptured by the moveable camera220. The method400may be implemented as one or more code modules of the software application program233resident in the hard disk drive210and being controlled in its execution by the processor205.

As seen inFIG. 4A, the method400begins at image download step401, where the processor205is used to download a current frame from the moving camera220, via the network290. In accordance with the present example ofFIG. 2A, in the first iteration of the method400, the current frame is the image291, which is a raw image ready to be processed in accordance with the method400. As described above, the downloaded image291may be stored within the memory206and/or the hard disk drive210.

In an alternative arrangement, the images291and292may be compressed by the moving camera220using a conventional coding scheme, such as JPEG, JPEG2000, Motion JPEG2000, MPEG1, MPEG2, MPEG4 and H.264. In such an alternative arrangement, the method400may include a step to decode the images291and292to generate raw pixel data.

In decision step402, the processor205is used to detect the presence of a calibration marker pattern298in the current frame (e.g., image291). If the calibration marker pattern298is detected in the current frame (e.g., image291), then the method400proceeds to step403. Otherwise, the method of setting the initial keyframe400returns to the downloading step401to process a next input frame.

In one arrangement, the current frame may be binarised at the detecting step402to determine connected groups of dark pixels below a certain gray value threshold. In this instance, the contour of each group of dark pixels is extracted, and those groups of pixels surrounded by four straight lines are marked as potential markers. Four corners of every potential marker are used to determine a homography in order to remove perspective distortion. Once the internal pattern of a calibration marker is brought to a canonical front view, a grid of N×N binary values are determined. The binary values of the grid form a feature vector that is compared to the feature vector of the calibration marker pattern298by correlation. The output of the comparison is a confidence factor. If the confidence factor is greater than a pre-determined threshold, then the calibration marker pattern298is considered to be detected in the current frame at step402.

In an alternative arrangement, instead of binarising the current frame using a fixed gray value threshold, at the detecting step402, edge pixels may be detected using an edge detector. In this instance, the edge pixels are linked into segments, which in turn are grouped into quadrangles. The four corners of each quadrangle are used to determine a homography to remove the perspective distortion. An interior pattern is then sampled and compared to the feature vector of a known calibration marker pattern298by correlation. The calibration marker pattern298is considered to be found if the output of the comparison is greater than a pre-determined threshold.

Referring toFIG. 4A, in camera pose determination step403, the processor205is used to determine the camera pose for the current frame (e.g., image291) based on the known position and orientation of the calibration marker pattern298detected in the current frame at step401and on appearance of the detected calibration marker pattern298.

In one arrangement, the four straight contour lines and the four corners of the calibration marker pattern298may be determined at pose calculating step403in a similar manner to step402. The detected marker is then normalised using a perspective transformation given in Equation. (1), below. All variables in the transformation matrix are determined by substituting image coordinates and marker coordinates of the four vertices of the detected calibration marker pattern298for (xc, yc) and (Xm, Ym), respectively.

where h is an arbitrary scale factor.

The normal vectors of the planes formed by two parallel lines of the calibration marker pattern298may then be determined. The equations of the two parallel lines in the image coordinates are given by Equation. (2), as follows:
a1x+b1y+c1=0,a2x+b2y+c2=0  (Eq. 2)

where a1, b1and c1as well as a2, b2and c2are constant parameters for each of the parallel lines respectively.

Given that the moving camera220is pre-calibrated, the perspective project matrix P may be expressed as a 4×4 matrix, in accordance with Equation. (3), as follows:

Accordingly, Equation (1) may be expressed in accordance with Equation (4) as follows:

[hxchych1]=P⁡[XcYcZc1](Eq.⁢4)
where (Xc, Yc, Zc) are the camera coordinates of a corner of the calibration marker pattern298.

The equations of the planes that include the two sides of the calibration marker pattern298, respectively, may be represented in accordance with Equation. (5), below, in the camera coordinates by substituting xcand ycin Equation. (3) for x and y in Equation. (2).
a1P11Xc+(a1P12+b1P22)Yc+(a1P13+b1P23+c1)Zx=0,
a2P11Xc+(a2P12+b2P22)Yc+(a2P13+b2P23+c2)Zx=0  (Eq. 5)

From Equation. (5), the normal vectors of the planes including the two sides of the calibration marker pattern298are determined and represented by n1and n2, respectively. The direction vector v1of the parallel two sides of the calibration marker pattern298is given by the outer product n1×n2. The second set of parallel lines may then be used to determine direction vector v2. The two direction vectors v1and v2are refined to compensate for errors due to noise and image processing errors, such that v1and v2become exactly perpendicular.

A unit direction vector v3that is perpendicular to both v1and v2is also determined. The unit direction vectors v1, v2, and v3collectively form the rotation component of the transformation matrix T from marker coordinates to camera coordinates shown in Equation. (6), as follows:

Given the rotation component of the transformation matrix, the four corners of the marker in the marker coordinates, and the corresponding vertices of the detected marker in the current frame, eight equations (including translation component W3×1) are generated and the values of the translation component may be obtained from the eight equations. The transformation matrix T gives a rough estimation of the camera pose. It is important to note that, in the presence of image noise, motion blur, and inaccuracy of the camera calibration, the determined transformation matrix T based on a single image of the calibration marker pattern298is generally not sufficiently accurate for augmented reality systems.

Following step403, at subsequent checking step404the processor205is used to check whether an initial keyframe (or key image) has been set. If the initial keyframe has been previously set, then the method400proceeds to the projecting step406as seen inFIG. 4B. In the present example, a determination at step404that the initial key-frame has been set means that the current frame is the image292ofFIG. 2A. Otherwise, if the initial keyframe has not been set (i.e. this is the first time a calibration marker pattern298is detected), then in accordance with the present example the current frame is the image291and the method400proceeds to the setting step405. At step405, the processor205sets the current frame (e.g., image291) as the initial keyframe, and the method400returns to the reading step401to read the next input frame (e.g., the image292) from memory206and/or the hard disk drive210.

At projection step406, the processor205is used to project a set of corners from the known calibration marker pattern298to the initial keyframe (e.g., image291) and the current frame (e.g., image292) based on the camera poses determined in step403, to estimate expected image coordinates of the calibration marker pattern298. The set of corners from the known calibration marker pattern298is pre-determined and may be accessed at step406from the memory206or storage device210. In another arrangement, the set of corners may also be accessed from disk storage medium225and/or the computer network (920or922). It is desirable that the set of corners from the known calibration marker pattern298are sparsely and evenly distributed over the entire area of the calibration marker pattern298. In one arrangement, at least twenty (20) corner features are selected from the calibration marker pattern298.

As described in detail below, in following steps407to409as seen inFIG. 4B, the processor205is used in the method400for determining a first image feature in a first image (e.g., the initial keyframe in the form of the image291) corresponding to the feature of the calibration marker pattern298associated with the first image. The first image feature is determined based on a first pose of the camera220used to capture the first image. The processor205is then used for determining a second image feature in a second one (e.g., the image292) of the plurality of images based on a second pose of the camera used to capture the second image, the second image feature having a visual match to the first image feature.

In detection step407, the processor205is used to detect salient image features from the initial keyframe (e.g., image291) and the current frame (e.g., image292) using a corner detector. In one arrangement, a FAST-10 corner detector with non-maximal suppression may be used. Alternatively, a Harris corner detector, Moravec corner detector, SUSAN corner detector, SIFT, or SURF corner detector may also be used for detecting salient image features in the initial keyframe (e.g., image291).

In an alternative arrangement, only image regions near the expected image coordinates of the corners of the calibration marker pattern298in the initial keyframe (e.g., image291) and the current frame (e.g., image292) determined in projecting step406are examined at step407. The size of the image regions may be determined based on the size, position and orientation of the calibration marker pattern298and on the camera pose determined in step403.

The method400then proceeds from the detecting step407to matching step408, to determine matched image features corresponding to the corners of the calibration marker pattern298in the initial keyframe (e.g., image291) and the current frame (e.g., image292) stored in memory206and/or the hard disk drive210.

A method500of determining matched image features, as executed at step408, will now be described with reference toFIG. 5. The method500may be implemented as one or more code modules of the software application program233resident on the hard disk drive210and being controlled in its execution by the processor205.

In a first selection step510of the method500, the processor205is used to determine whether all corners of the calibration marker pattern298have been processed. If no more corners remain for processing, all matched image features of the corners between the initial keyframe (e.g., image291) and the current frame (e.g.,292) are determined, and the method500concludes and the method400continues at the estimating step409. Otherwise, the method500proceeds to determining step520.

At the determining step520, the processor205is used to determine a set of candidate salient image features in the initial keyframe (e.g., image291) corresponding to the corner of the calibration marker pattern298. The set of candidate salient image features is determined based on Euclidean distance of the salient image feature from expected image coordinates of the selected corner determined in step406.

In one arrangement, a circular search region may be defined with a radius of ten (10) pixels centred at the expected image coordinates of the selected corner. Any salient image feature found in the circular search region is considered to be a potential candidate for the location of the projected corner. In an alternative arrangement, a rectangular search region may be used, and the dimension of the rectangular search region may depend on the position and orientation of the estimated camera pose determined in step403.

Following the step520, at subsequent checking step530the processor205is used to check whether any candidate image features remain for processing. If all candidate image features are processed, then the method500returns to checking step510to process the next corner of the calibration marker pattern298. Otherwise, the method500proceeds to step540.

In matching step540, each selected candidate image feature determined at step520from the initial keyframe is matched against a set of image features in the current frame stored within memory206and/or the hard disk drive210. The set of image features in the current frame to be matched is determined based on Euclidean distance of the image feature from the expected image coordinates of the selected corner determined in step406. Following step540, the method500returns to step530and step540is repeated until the best match feature is found for a given corner currently processed.

In one arrangement, 8×8 patches centred at the location of the salient image feature in both the initial keyframe and the current frame are extracted at step540. The 8×8 patches are then matched using zero-mean sum of squared differences (ZSSD) measure. The pair of image features with the highest ZSSD score is selected as the best match for the current corner of the calibration marker pattern298. Alternatively, the pair of image features which is closest to the expected image coordinates of the selected corner and has a ZSSD score above a pre-determined threshold is selected as the best match for the current corner of the calibration marker pattern298.

In an alternative arrangement, a different patch size such as a 16×16 or 32×32 patch and a different similarity measure, such as sum of squared differences (SSD) or sum of absolute differences (SAD), may be used for matching the selected candidate image feature with the set of image features in the current frame at the finding step540.

Referring back toFIG. 4B, the method400proceeds to the estimating step409, which follows the determining step408. At the estimating step409, the processor205is used for determining a reconstructed position of the feature of the calibration marker pattern298based on positions of the first and second image features, the first camera pose and the second camera pose.

At estimating step409, the processor205is used to estimate the 3D position of the corners of the calibration marker pattern298by triangulation based on the image coordinates of the match features corresponding to corners of the calibration marker pattern298determined in step408and the relative pose between the initial keyframe (e.g., image291) and the current frame (e.g., image292). The relative camera pose is determined based on the camera poses of the initial keyframe and the current frame determined in step403of the method400.

In one arrangement, linear triangulation is performed at step409. For example, given two observations, x and x′ of a point X in space and the projection matrices P and P′ for the initial keyframe (e.g., image291) and the current frame (e.g., image292) respectively, the depth of the point X may be determined in accordance with Equations (7) and (8):

x=PX(Eq.⁢7)x′=P′⁢X(Eq.⁢8)P=K⁡[R|t]=[p11p12p13p14p21p22p23p24p31p32p33p34]=[p1⁢Tp2⁢Tp3⁢T]
By taking cross product in Eq. 7,
x×(PX)=PX×PX=0  (Eq. 9)
Equation. (9) may be re-written as three linear equations, as follows:
u(p3TX)−(p1TX)=0
v(p3TX)−(p2TX)=0
u(p2TX)−v(p1TX)=0
where piTare the rows of the projection matrix P. An equation of the form AX=0 may then be composed in accordance with Equation. (10), as follows

The four equations of Equation. (10) with four homogenous unknowns may be solved by performing Singular Value Decomposition (SVD) according to Equation. (11), as follows.
A=UΣVT(Eq. 11)
where U and V are 4×4 matrices, VTis a conjugate transpose of V, and Σ is a 4×4 diagonal matrix. A solution X of Equation (11) corresponds to the last column of the matrix V.

In one arrangement, an iterative or non-iterative algorithm that minimises a suitable cost function such as a Sampson distance measure may be used to determine the 3D positions of the corners of the calibration marker pattern298.

The method400then proceeds from estimating step409to determining step410, where the processor205is used for determining a 3D reconstruction error in a 3D space based on the reconstructed position of the feature of the calibration marker pattern298. The reconstruction error is determined for each corner of the calibration marker pattern298. The reconstruction error for each corner may be stored by the processor205within memory206and/or the hard disk drive210. In one arrangement, the reconstruction error is measured in the constructed coordinate system of an augmented reality system. For example, with reference toFIG. 6, the reconstruction error601is the Euclidean distance between actual position of a corner of the pattern Xmarkerand the position of reconstruction Xreconst602determined in step409. The reconstructed position Xreconst602of such a corner of the pattern Xmarkeris based on matched calibration features and relative camera pose. As seen inFIG. 6, due to on inaccuracy, noise and motion blur, camera poses (e.g.,603) may be inaccurate.FIG. 6shows observed corner features604(i.e., xLand xR), and projected corners605(i.e., {circumflex over (x)}2and {circumflex over (x)}R). The projected corners (e.g.,605) may be determined based on determined camera pose. The actual position of a corner of the pattern Xmarkeris a pre-determined position, which may be given as an input during map initialisation. In one implementation, the actual position of the pattern Xmarkeris fed in during the map initialisation step by a user. In another implementation, the actual position of the pattern Xmarkeris obtained through a geo-tagged beacon received by the computer module201, which determines the actual location based on the received beacon.

In the following steps411to413, the processor205is used for selecting a first image (i.e., in the form of the current frame) for constructing a coordinate system of an augmented reality system in an event that the determined reconstruction error satisfies a pre-determined criterion for scene reconstruction. In decision step411, the processor205is used to determine whether quality of the 3D reconstruction of the corners of the calibration marker pattern298is satisfactory. If the quality of the reconstruction is satisfactory, the method400proceeds to setting step412to set the current frame (e.g., image292) as a keyframe. Otherwise, the method500proceeds to decision step415.

In one arrangement, the quality of the 3D reconstruction of the corners of the calibration marker pattern298is considered to be satisfactory if:

1) the reconstruction error indicates that the reconstruction of a corner is successful (i.e., if the reconstruction error of the corner is less than a first threshold T1); and

2) the number of corners successfully reconstructed is larger than a second threshold T2.

In an alternative arrangement, the threshold T1is not fixed. The threshold T1may be dynamically adjusted depending on the required accuracy of an augmented reality system implementing the described methods, as set by user of the system.

In a further arrangement, the quality criteria of the 3D reconstruction may be based on mean and variance of the reconstruction errors of the corners of the calibration marker pattern298.

The method400then proceeds to step412. Since the quality of the reconstructed corners of the calibration marker pattern298are determined in step411to be satisfactory, at step412, the processor205is used to set the current frame (e.g., image292) stored within the memory206and/or the hard disk drive210as a second keyframe. The initial keyframe (e.g., image291) and the current frame (e.g., image292) form a stereo image pair to be used in map initialisation step413to construct an initial 3D map (e.g., map295as seen inFIG. 7).

Following step412, at constructing step413of the method400, the processor205is used to perform map initialisation to construct a map of the scene293, within memory206and/or the hard disk drive210, based on the initial keyframe (e.g., image291) and the second keyframe (i.e., the current frame) (e.g., image292). A set of natural image features, including those from 3D spherical object299and 3D square object297ofFIGS. 2A and 3, are extracted from the initial keyframe (e.g., image291) using a corner detector such as a FAST-10 corner detector. Alternatively, a Harris corner detector, Moravec corner detector, SUSAN corner detector, SIFT, or SURF corner detector may also be used for detecting corners in the initial key-frame (e.g., image291). Also at map initialization step413, the processor205is used to perform an epi-polar search to determine the feature correspondences in the current frame (e.g., image292) based on the relative camera pose determined in estimating step409. Given the relative camera pose between a pair of stereo images, such as the images291and292, a point in one image corresponds to a so-called epi-polar line in the second image. Patch search is performed to locate the match point along the epi-polar line. The processor205is then used to perform triangulation at step413to determine the 3D coordinates of the corners corresponding to those natural image features based on the determined image coordinates of the feature correspondences and the relative camera pose. The output of step413is an initial 3D map, which according to the example ofFIG. 2Ais the 3D point cloud map295as seen inFIG. 7. The 3D map295constructed in accordance with the method400may be stored within the memory206and/or hard disk drive210. The calibration marker pattern can be removed from the scene after the 3D point cloud295is generated by the process400.

In one arrangement, the method400uses all detected corner features in the initial keyframe for map initialisation, to generate a very dense 3D map295.

In an alternative arrangement, only a subset of the detected corner features in the initial keyframe is selected for map initialisation. The number of selected image features may be limited to a pre-defined threshold value, and the selected features are sparsely and evenly distributed in the initial keyframe.

If the quality of the reconstruction of the corners is poor at decision step411, then the method400continues from step411to decision step415as seen inFIG. 4C. At step415, the processor205is used to determine whether the amount of time elapsed since the initial keyframe is captured exceeds a pre-determined threshold T. If the time elapsed since the initial keyframe is captured is less than the threshold T, then the method400returns to step401of the method400to process the next input frame. Otherwise, the method400proceeds to decision step416.

In step416of the method400, the processor205is used to determine whether the threshold T is smaller than a pre-determined threshold value, MAX, stored within the memory206and/or the hard disk drive210. If the current value of T is smaller than MAX, then the method400proceeds to setting step417and the threshold T is doubled to handle slow camera motion. In contrast, if the threshold T is larger than or equal to MAX, then map initialisation is determined to have failed and the method400proceeds to setting step419. At setting step419, the threshold T is re-initialised to a default setting value, DEFAULT.

Following steps417and419, a subsequent setting step418sets the current frame (e.g., image292) as the initial keyframe, and the method400returns to step401to process the next input frame.

In one further arrangement, the video system200inFIG. 2Aprovides a visual and/or audible indication of the distance and the direction of the moving camera220required for successful map initialisation. The visual and/or audible indication may be provided, for example, via the video display214and/or the loudspeakers217. Given that an initial keyframe has been selected by the method400, the moving camera220should be moved side-ways by a certain distance from the position of the initial keyframe to satisfy a stereo baseline requirement. Stereo baseline is related to scene depth which is, in this case, the distance between the moving camera220at the position of the initial keyframe and the calibration marker pattern298. The relationship between the stereo baseline and scene depth is often determined experimentally and, in one arrangement, the stereo baseline distance is set approximately equal to one-tenth of the scene depth. Alternatively, the quality of the reconstruction determined at step411may also be used to estimate the camera movement for successful map initialisation. Reconstruction error (i.e. depth resolution) is approximately inversely proportional to the baseline distance for a scene of a given depth. The processor205can therefore estimate the required camera movement from a current position of the moving camera by multiplying the baseline distance with the estimated reconstruction errors determined at step411and then dividing the result of the multiplication by the desired level of reconstruction errors. The direction of the camera movement is restricted to be in parallel to the surface of the calibration marker pattern298.

The method400will now be further described by way of example. In one example, the method400may be used for an indoor navigation system, where the mapping of newly observed objects in a scene and localising camera poses (i.e. position and orientation) from tracked objects are performed in parallel in real-time. In such an indoor navigation application, a user looks at an indoor scene such as inside a demonstration home (“demo home”) through a capture-display device such as a camera phone or an optical see-through head mounted display (HMD). The user may firstly initialise the indoor navigation system by looking directly towards a calibration marker pattern, such as the calibration marker pattern298shown inFIG. 1Aor1B. In this instance, the calibration marker pattern defines the scale of the visible objects and the global coordinate system in the scene. The calibration marker pattern may appear, for example, on the main entrance door, on the floor near the entrance, or on top of a shoe shelf at the demo home. The indoor navigation system may then automatically detect the presence of the calibration marker pattern in the captured images, in accordance with the method400, and provide the first image with the detected calibration marker pattern as an initial keyframe. The video system200may provide visual and audio instructions for the desired user movement for map initialisation if the reconstruction error does not satisfy the predetermined criterion. For example,FIG. 8shows a blinking arrow801and text802showing the direction and estimated distance (i.e., 1 m) of desired user movement at the bottom right-hand corner on the video display214. At the same time, the processor105may cause the loudspeakers217to produce an instruction such as “Move sideway to the left by 1 m”. As the user enters the demo home through the entrance while looking at the calibrated marker pattern, one of the subsequent images may be selected in accordance with the method400for map initialisation.

Continuing the demo home example, once the second keyframe is determined in accordance with the method400(i.e., as at step412), natural features (e.g. corner points) are extracted from both the initial and second keyframes. Feature matching is then performed based on learnt epi-polar geometry derived from the calibration marker pattern. The 3D location of points in space is determined based on the known epi-polar geometry. Pairs of feature correspondences are also determined by triangulation. The initial 3D map of the scene within the demo home is then generated (as at step413). The calibrated marker pattern is not required for later tracking and localisation.

Any suitable parallel tracking and mapping algorithm may then be performed to keep track of the existing objects in the 3D map generated for the demo home. Such a parallel tracking and mapping algorithm may be used to determine the current camera pose (position and orientation) based on locations of detected features and corresponding map points. Newly detected natural features may be added into the generated 3D map as the user moves further into the demo home and enters into unexplored regions of the environment. Such an indoor navigation system may overlay supplementary text information or synthetic objects onto images. The supplementary text information may show current position of the user in terms of the global coordinate system and the distance travelled since an initial user position. Synthetic objects may include paintings on the walls, furniture, household appliances, and even a virtual ocean-view when the user looks out from the windows or balcony of the demo home.

The methods described above may be used for product design. As an example, a textured cube with a calibrated marker pattern (e.g., the calibrated marker pattern298) on one side of the cube. In this instance, a designer may firstly initialise an augmented reality (AR) system by looking at the calibrated marker pattern through a camera phone or a head mounted display (HMD) and moves the textured cube to a new location. A pair of keyframes may be determined for generating the initial map as described above. Computer graphics representing, for example, a photocopier may be superimposed into the images when viewed through the camera phone or head mounted display. The designer may move about or rotate the cube to inspect the design from different viewing angles and positions. Buttons on synthetic printers may then be selected to see a computer animation that simulates the operation of the photocopier in response to the button selections.

In the context of this specification, the word “comprising” means “including principally but not necessarily solely” or “having” or “including”, and not “consisting only of”. Variations of the word “comprising”, such as “comprise” and “comprises” have correspondingly varied meanings.