Systems and Methods of Forming Virtual Models
The present invention relates to systems and methods of forming virtual models. In particular, the present invention relates to systems and method of forming virtual models corresponding to a plurality of physical tokens.
Background to the Invention
Virtual models are digital representations of real-world objects. Some virtual models are exact replicas of real-world objects. Exact replica virtual models are typically created by using exhaustive laser or optical scanning techniques to map every feature of a real-world object. Such exact models generally require expensive scanning equipment and are time-consuming to make.
Alternatively, a virtual model may be created by extracting a recognisable feature of an object from an image and then retrieving a known virtual representation of the entire object from a local or network-connected source. This alternative method is quicker and computationally far simpler, although it relies on having a virtual representation of a given real-world object available.
These recognisable features within an image are known in the art as fiduciary markers, which are effectively measurement or reference points that allow a computer to recognise objects within an image. Systems which can extract one or more fiduciary markers from an image can use these markers as the basis for augmented reality techniques. These augmented reality techniques use fiducial markers to represent physical objects and make them recognisable to the software. These techniques superimpose a three-dimensional model over a captured image, and update the model as the image alters.
There are a number of systems that use augmented reality techniques. For example, the
NINTENDO 3DS system and the GOOGLE GLASS system. Whilst these systems are capable of generating virtual models from real-world objects, they provide a virtual model which is only an instantaneous snap-shot of an object, or objects, which cannot be manipulated thereafter by a user.
There are some systems which can provide a more permanent virtual model of a realworld object using fiduciary marker extraction techniques. An example of such a system is the computer game level builder system, BLOXELS BUILDER. This system enables a user to arrange real-world objects within a pre-defined grid, each object relating to a computer game element. An imaging device then takes a photo or video of the arranged real-world objects and a virtual model is generated by assembling virtual representations of each object. This virtual model is then saved by the system and can be added to and/or manipulated thereafter by a user. However, this system and method of generating a virtual model both is time consuming and limited in its functionality.
Therefore, there exists a need to provide improved systems and methods for generating virtual models of real-world objects.
Summary of the Invention
In a first aspect, the present invention provides a method of forming a virtual model of a plurality of physical tokens, each physical token comprising a visual design, the method comprising the steps of: arranging the plurality of physical tokens into a pattern based on the visual design on each of the plurality of physical tokens; capturing a plurality of digital images of the arranged plurality of physical tokens with a computing device; forming a master virtual model of the plurality of physical tokens in accordance with the pattern, based on an aspect of each of the plurality of physical tokens that is recognisable to the computing device.
In a second aspect, the present invention provides a method of forming a virtual model, comprising: capturing a plurality of digital images of a plurality of physical tokens, wherein each image includes one or more of the markers; from a first of said images, generating an intermediate virtual model comprising virtual representations of the physical markers captured in that image; for each subsequent digital image: a) generating an image-specific virtual model comprising virtual representation of the physical markers in the subsequent image; b) comparing the image-specific virtual model with the intermediate virtual model to determine a quality score representing a degree of similarity between the image-specific virtual model and the intermediate virtual; and c) in the event that the quality score exceeds a threshold, merging the imagespecific virtual model with the intermediate model to update the intermediate virtual model; repeating steps a) to c) for each subsequent digital image.
Further features of the invention are defined in the appended dependent claims.
Brief Description of the Drawings
By way of example only, the present invention will now be described with reference to the drawings, in which:
Figure 1 is a diagram of four physical tokens in accordance with an embodiment of the present invention;
Figure 2 is a representation of an imaging device in accordance with an embodiment of the present invention;
Figure 3 is a flow chart showing a method in accordance with an embodiment of the present invention;
Figure 4 is a flow chart of a further method in accordance with an embodiment of the present invention;
Figure 5 is a flow chart showing a further method in accordance with an embodiment of the present invention;
Figure 6 is a diagram of the graphical user interface of an imaging device in accordance with an embodiment of the present invention;
Figure 7 is a diagram of four physical tokens in accordance with an embodiment of the present invention;
Figure 8 is a diagram of the graphical user interface of an imaging device in accordance with an embodiment of the present invention;
Figure 9 is a diagram of four physical tokens in accordance with an embodiment of the present invention;
Figure 10 is a diagram of the graphical user interface of an imaging device in accordance with an embodiment of the present invention;
Figure 11 is a flow chart of a method in accordance with an embodiment of the present invention;
Figure 12 is a diagram of four physical tokens in accordance with an embodiment of the present invention; and
Figure 13 is a diagram of the graphical user interface of an imaging device in accordance with an embodiment of the present invention.
Detailed Description of Preferred Embodiments
Figure 1 shows a plurality of physical tokens in accordance with an embodiment of the present invention. Four physical tokens 101 to 104 are shown, however the present invention works equally well with any number of physical tokens. The physical tokens 101 to 104 have images printed on one surface (not shown). These images correspond to elements of a virtual model that may be generated as described below. For example, the physical tokens may include different sections of a racetrack. The user arranges the physical tokens to form a racetrack. As described below, in embodiments of the invention, an imaging device produces a virtual model of the racetrack that corresponds to the racetrack formed by the physical tokens.
Each physical token 101 to 104 comprises an identifier (not shown). The identifier is a fiducial marker which enables the physical token to be recognised within an image of the physical token. Additionally, the identifier is orientation specific, meaning the identifier enables the orientation of the physical token to be recognised within an image. Preferably, the identifier is a machine readable code such as a matrix barcode (hereinafter known as a QR code), or a barcode. The identifier may however be any feature of the physical token. The identifier may be machine recognisable and orientation specific. The physical token may also include an image with integrated high-contrast features (for example, high contrast corners or edges) that can be detected using imaging techniques. The physical token may also be a three-dimensional object that can be recognised by its colour, outline or texture.
The physical tokens 101 to 104 may be any 2-dimensional or 3-dimensional object. Preferably, the physical tokens 101 to 104 are substantially flat shapes cut out of plastic, paper or metal. The identifiers may be transferred onto the physical tokens 101 to 104 by any suitable method such as printing, etching or engraving. Optionally, the physical tokens 101 to 104 are shaped such that they tessellate with each other. The physical tokens 101 to 104 shown in Figure 1 are hexagons.
Figure 2 is a schematic diagram of an imaging device 200 in accordance with an embodiment of the present invention. The imaging device 200 comprises a processor 201, and a non-volatile memory 202. Processor 201 may comprise one or more individual processor cores. The imaging device 200 comprises an imaging means 203 capable of capturing still and/or video images. The imaging device 200 further comprises a display 210 and a user interface 220. The imaging device 200 may be a desktop computer, laptop or tablet device, smartphone or other computing device. In some examples, the imaging device 200 will be a single complete unit. In other examples the imaging device 200 may be two or more discrete units, in data communication with each other. In some examples the display 210 will be integrated into the imaging device 200. The user interface 220 may be a keyboard and/or mouse arrangement, or may utilise a touch screen where appropriate. The computing device 200 also comprises an operating system (not shown). The methods described herein may run on the operating system (not shown) of computing device 200.
A method of forming a virtual model in accordance with the present invention will now be described by reference to Figure 3. Figure 3 is a flow chart setting out the method steps in accordance with the present invention.
Firstly, the physical tokens 101, 102, 103 and 104 are arranged by a user into a desired pattern (S301), as illustrated in Figure 1. As noted above, this may be, for example, a racetrack. A video stream of the physical tokens is captured by the imaging device (S3 02). An image-specific virtual model is created for each image of the video stream (S303). These models are combined to create a master virtual model (S304).
The method of forming the image-specific virtual models is described in connection with Figure 4.
At step S401, the user begins capturing a stream of images of the physical tokens 101 to 104 with the imaging device 200. This may be done by capturing a video stream, which is a series of digital images, or by otherwise capturing multiple digital images. As the imaging device moves to capture all of the physical tokens, each digital image is different. Each image may include different subsets of the physical tokens, captured from different angles.
Depending on the arrangement of the physical tokens 101 to 104 and the capabilities of the imaging device 200, a single image may capture all of the physical tokens. However, as will be seen below, there are advantages to capturing multiple images of the tokens.
The imaging device 200 analyses the captured images in real-time. As such, a virtual model is built up as the digital images are captured. At step S402, the imaging device 200 analyses the first image that has been captured and extracts the identifier of each of the physical tokens 101 to 104.
At step S403, the imaging device 200 determines, based on the identifiers, the orientation of each of the physical tokens 101 to 104 present in the first image.
At step S404, the imaging device 200 retrieves a virtual representation of each physical token present in the first image. The virtual representation may be a virtual copy of the physical token, or may be a virtual element related to the physical token. The imaging device 200 may retrieve the virtual representations from local non-volatile storage if available. Alternatively, the imaging device 200 may contact a storage server and request suitable virtual representations based on the determined identifiers. Such contact may be, for example, over a wired or wireless internet connection.
At step S405, the imaging device 200 orientates each virtual representation depending on the determined orientation of the respective physical tokens.
At step S406, the imaging device 200 determines the relative position of the physical tokens 101 to 104 present in the first image, based on the position of the identifier of each physical token. In the present example, each of the physical tokens 101 to 104 can be considered to be a 2-dimensional physical token, enabling the imaging device to determine relative position and orientation of each physical token relative to a common 2-dimensional plane. If the physical tokens 101 to 104 are all arranged on a single plane, the imaging device may produce a more accurate estimation of their position and rotation in 3D space.
At step S407, the imaging device 200 arranges the orientated virtual representations in accordance with the determined relative positions of the physical tokens 101 to 104, to form an image-specific virtual model of the physical tokens.
As each new image-specific virtual model is created, it is compared with earlier models to determine if the models can be combined. As long as there is sufficient overlap between the models, they can be combined. If the only virtual model available is the first image-specific model, the new image-specific model is compared with that model, and if appropriate combined with it (as will be described in more detail below). Once two virtual models are combined, an intermediate virtual model is created. Any subsequent image-specific virtual models are then compared and combined with the intermediate virtual model.
The method of generating a master model will now be described with reference to Figure 5.
Firstly, the imaging device 200 compares the image-specific virtual model with any image-specific virtual models (S501). The imaging device 200 looks for a subset of virtual representations that have similar relative positions and orientations.
Where a match is found between a subset of the virtual representations, a score is calculated that measures the quality of the match (S502). If the score is over a certain threshold, the imaging device merges the image-specific virtual models to create an intermediate virtual model (S503).
Any further image-specific virtual models may be combined with the intermediate model in the same manner. Assuming all image-specific models are combined with the intermediate model, once all images have been analysed, the intermediate model becomes the master virtual model.
In the event that an image-specific virtual model does not pass the match quality score, the image-specific model is saved separately. Any further image-specific models are compared with the intermediate model. If there is not match, they are compared with the saved image-specific model. If there is a match, a second intermediate model is created. In this manner, more than one intermediate model may be active at any one time. After processing each image, the intermediate models are also compared with each, and if there is a match with a quality score above the threshold, the intermediate models are combined.
The skilled person would understand that the present invention is not restricted to the exact order of steps as defined above.
Figure 6 is a diagram of a graphical user interface 600 of the imaging device 200 illustrating a master virtual model resulting from the above described method. The graphical user interface 600 is a visual representation of an operating system, such as
MICROSOFT WINDOWS ™ and any applications running on the operating system. In
Figure 6, the graphical user interface 600 is displaying the operating system 610 and a virtual model application window 620. The virtual model application window 620 is a graphical representation of software executing computer-readable instructions in accordance with above described method.
Within the virtual model application window 620 is displayed a master virtual model 630. The virtual model corresponds to the physical tokens 101 to 104 shown in Figure
1. The virtual model 630 can now be manipulated as required within the virtual model application window 620.
One advantage of the present invention is that it supports the presence and use of multiple identical physical tokens within a single image. Since the system recognises the position of each physical token relative to every other physical token identified in an image, multiple identical physical tokens can be identified and discriminated within a single image. Consequently, the number of unique physical tokens may be drastically reduced for a given pattern of physical tokens. In this manner, the number of possible physical token identifiers is not quickly exhausted. Furthermore, manufacturing of the physical tokens is simplified.
Figures 7 and 8 illustrate the method of amending the virtual model 630. Figure 7 shows the physical tokens 101, 102, 103 and 104 of Figure 1. However, physical token 104 has been moved from its original position (as indicated by the dashed line) to a new position 704, as illustrated by arrow 710.
Moving one or more of the physical tokens in this way allows the virtual model to be altered and previewed, enabling a user to quickly and easily make design alterations. Furthermore, adjusting just part of the virtual model is computationally far simpler than generating a completely new virtual model. To enable the virtual model to be updated, at least one of the physical tokens will have to remain in its original position to enable the system to identify the relative positions of the moved physical tokens to the physical tokens in the original image. Furthermore, physical tokens should not be moved during the image capturing process as this will confuse the system as to how to combine the moved physical tokens with the originally captured physical tokens. Figure 8 is a diagram of the graphical user interface 600 of the imaging device 200 illustrating the virtual model 630 resulting from the movement of physical token 104.
Within the virtual model application window 620 of Figure 8 is displayed an amended virtual model 801. The virtual model 801 corresponds to the physical tokens 101, 102, 103 and 704 shown in Figure 7.
Figures 9 and 10 illustrate the method of expanding the virtual model 630. Figure 9 shows the physical tokens 101, 102 of Figure 1. However, Figure 9 includes new physical tokens 901 and 902, arranged adjacent to physical tokens 101 and 102. Physical tokens 901 and 902 may be completely new physical tokens, or may be original physical tokens 103 and 104 moved to a new position or orientation.
Moving one or more of the physical tokens, or adding additional physical tokens, allows a large virtual model to be constructed from a small number of physical tokens. However, at least one of the physical tokens will have to remain in its original position to enable the system to identify the relative positions of the moved physical tokens to the physical tokens in the original image. Furthermore, physical tokens should not be moved during the image capturing process as this will confuse the system as to how to combine the moved physical tokens with the originally captured physical tokens.
Figure 10 is a diagram of the graphical user interface 600 of the imaging device 200 illustrating the virtual model 1001 resulting from the addition of physical tokens 901 and 902. Within the virtual model application window 620 of Figure 10 is displayed the expanded virtual model 1001. The virtual model 1001 corresponds to the physical tokens 101, 102, 103, 104 shown in Figure 1, with additional physical tokens 901 and 902 shown in Figure 9.
In an alternative, to creating multiple virtual models from multiple images and then combining them into a single virtual model, the multiple images may first be stitched together using panorama stitching methods and then a single virtual model created from the stitched image.
In some examples, the user creating a second virtual model may be a second user, using a second imaging device 200. In this case, the second imaging device 200 will be in data communication (such as by BLUETOOTH or WIFI) with the first imaging device so virtual models can be shared. This enables multiple users to scan in the same environment collaboratively using their own imaging devices. Implementing this invention with two, or more, users thus enables large virtual models to be quickly created from a large number of physical tokens.
An advantage of the present invention is that it provides a computationally efficient system and method to work around the fact that information captured by an imaging device is often noisy and unreliable. This may lead to the presence of physical tokens within an image frame may not always being correctly detected. Further, even when physical tokens are detected, the exact position and/or rotation of the physical tokens between frames may not always be consistent. These problems can be exacerbated by changes in lighting, low resolution imaging devices and motion blur from the user, or users, moving their devices too fast.
To overcome these difficulties, the present invention is built to be capable of dealing with physical tokens that appear and disappear from frame to frame. The present invention can use multiple images to gradually build up a virtual model of all of the physical tokens, based upon physical tokens detected in the same position and/or rotation across multiple images. Moreover, the present invention may also combine multiple sightings of a particular physical token to gradually build a more accurate view of the relative positions of the physical tokens.
In some of the circumstances set out above, a second virtual model may not be combinable with the first virtual model if a match between physical tokens in the two models cannot be obtained. In this case, the second virtual model may be stored and used as a potential target for merging with subsequent virtual models. If this second virtual model is not stored, the user will have to be prompted to re-image the physical tokens until the two virtual models can be successfully combined. This can lead to a frustrating user experience.
Therefore, the system may at any one time be storing a number of different partial virtual models. Each newly created virtual models is then compared with each stored virtual model. Once a satisfactory match has been obtained, two or more of the virtual models can then be combined as described above. This method is explained below:
1. A first image is taken, the first image comprises three physical tokens, physical tokens 1, 2 and 3. This image forms frame 1. A virtual model of the three physical tokens may now be created, as described above.
2. A second image is taken, the second image comprises physical tokens 2, 3 and
4. This image forms frame 2. Frame 2 can be directly merged into frame 1 using common physical tokens 2 and 3, and a combined virtual model created based on frames 1 and 2. Alternatively, a second virtual model may be created based on frame 2. Subsequently, the first and second virtual models may be combined into a single virtual model using common physical tokens 2 and 3.
3. A third image is taken, the third image comprises physical tokens 5, 6 and 7. This image forms frame 3. There is no commonality between the physical tokens in frame 3 and the previously imaged physical tokens. Therefore, frame 3's virtual model, once created, is stored without being merged.
4. A fourth image is taken, the fourth image comprises physical tokens 6, 7 and 8.
This image forms frame 4. Frame 4 can be directly merged into frame 3 using common physical tokens 5 and 6 and a combined virtual model created based on frames 3 and 4. Alternatively, a virtual model may be created based on frame
4. Subsequently, the virtual models of frames 3 and 4 may be combined into a single virtual model using common physical tokens 5 and 6. However, there are still no common physical tokens between the virtual model of step 2 and step 4. Therefore, at this step of the method, there are still two disparate virtual models.
5. A fifth image is taken, the firth image comprises physical tokens 1, 2, 7 and 8. This image forms frame 5. Frame 5 could be merged into either of the existing virtual models, but let's assume it is merged into the one created in respect of frames 3 and 4. Frame 3 and 4's model now comprises physical tokens 1,2, 5, 6, 7 and 8. Frame 1 and 2's model comprises physical tokens 1, 2, 3 and 4. Now, because physical tokens 1 and 2 are common to both virtual models, they can be merged into a single virtual model comprising 8 physical tokens.
In a further embodiment of the invention, systems and methods are provided for tracking the imaging device 200 and adjusting the first virtual model 630 based on the tracking of the imaging device 200.
To enable device tracking, the imaging device 200 may further comprise one or more sensors for position and/or orientation tracking (not shown). The sensors may be one or more of an accelerometer, a magnetometer and a gyroscope. Such sensors are generally provided in imaging devices such as mobile phones and laptops. Alternatively, tracking of the imaging device 200 may be achieved by an optical technique such as optical flow or feature extraction. These optical techniques work on the presumption that objects in a digital image stream are fixed and thus any movement of the object in the image must relate to movement of the imaging device 200.
An exemplary method of adjusting the first virtual model 630 based on the tracking of the imaging device 200 will now be explained by reference to Figure 11. Figure 11 is a flow chart showing an exemplary method.
At step SI 101, a virtual model is created in accordance with an embodiment of the invention described above.
At step SI 102, the movement of an imaging device 200 is tracked. The tracking comprises monitoring the orientation of the device 200 and/or the relative position of the device 200.
At step SI 103, a change in the orientation and/or the relative position of the imaging device 200 is detected.
At step SI 104, the imaging device adjusts the virtual model based on the detected change in the orientation device.
The virtual model may be adjusted by orientating the virtual model in correspondence to changes in orientation of the imaging device 200. This enables a user of the imaging device to intuitively rotated and examine the virtual model.
Additionally, the virtual model may be adjusted by being translated in correspondence to changes in the relative position of the imaging device 200. This enables a user of the imaging device to intuitively move and explore the virtual model.
An exemplary use of the presently invention will now be described by reference to Figures 12 and 13. Figure 12 shows plurality of physical tokens 1201, 1202, 1203 and 1204 in accordance with the present invention. Figure 13 shows a graphical user interface 1300 illustrating the virtual model resulting from physical tokens 1201, 1202, 1203 and 1204.
Each of the plurality of physical tokens 1201, 1202, 1203 and 1204 comprises an identifier (not shown) as explained previously. In addition, each of the plurality of physical tokens 1201, 1202, 1203 and 1204 has a pattern on its surface. In the present example, the pattern relates to sections of a car racing track. For example, on physical token 1201 the pattern may be a representation of a straight section of track, on physical token 1202 the pattern may be a representation of a comer in the track, on physical token 1203 the pattern may be a representation of a start/finish line, and so on. A user may arrange these physical tokens 1201, 1202, 1203 and 1204 in many different arrangements and orientations, each creating a different combined pattern. This in turn results in a different car racing track being produced. Figure 12 shows one potential arrangement of physical tokens 1201, 1202, 1203 and 1204 which results in one particular combined pattern 1240.
Figure 13 shows a graphical user interface 1300 illustrating the virtual model resulting from physical tokens 1201, 1202, 1203 and 1204, by following a method of forming a virtual model as described above.
Figure 13 shows the graphical user interface 1300 displaying the operating system 610 and a virtual model application window 620. Within the virtual model application window 620 of Figure 13 is displayed a virtual model 1330. The virtual model 1330 corresponds to the physical tokens 1201, 1202, 1203 and 1204 shown in Figure 12.
Virtual model 1330 is formed of four virtual representations (not individually marked) corresponding to the physical tokens 1201, 1202, 1203 and 1204. In the present example, each of the four virtual representations are playable video game elements, corresponding to sections of a car racing track. In contrast to the virtual models shown in Figures 6, 8 and 10, virtual model 1230 is not an exact copy of the respective physical tokens. Instead, the four virtual representations forming virtual model 1230 conform to pattern 1220 in the shape of the resultant race track but comprise further visual elements. These further elements include the sides 1335 of the race track 1330 and a moveable element in the form of a racing car 1340.
The race track 1335 may now be extended by the user rearranging physical tokens 1201, 1202, 1203 and 1204.
When the user is finished creating the virtual model, the virtual model may be finalised, published, or otherwise completed for use. To allow the system to know that the virtual model is complete, the user may provide a suitable input to the system to indicate completion. Alternatively, the system may automatically detect that it has scanned in the full set of physical tokens that is required. For example, in the example of race track 1335, the system may detect that the virtual model now forms a complete circuit. The system may also detect completion by the incorporation of particular physical tokens that are used to indicate a start and finish. Alternatively, the system may detect completion upon the number of scanned physical tokens reaching a threshold number. Alternatively, the system may detect completion upon recognition of a special pattern of physical tokens (for example, a 4 by 4 grid of physical tokens).
Forming a virtual model of a car racing track is provided as an example of a use of the present invention. The present invention is not limited however to modelling car racing tracks or for creating playable video games. Instead, the present invention provides a powerful and intuitive method of creating virtual models of real-world objects.
The above embodiments describe one way of implementing the present invention. It will be appreciated that modifications of the features of the above embodiments are possible within the scope of the independent claims. For example, the methods described herein may be applied to any kind of window. The features of the browser 5 windows and web windows described herein are for example only and should not be seen as limiting to the claimed invention.
Features of the present invention are defined in the appended claims. While particular combinations of features have been presented in the claims, it will be appreciated that 10 other combinations, such as those provided above, may be used.