JP2003254716A - Instrument and method for measuring three-dimensional position and posture, storage medium, and computer program - Google Patents

Abstract

<P>PROBLEM TO BE SOLVED: To measure a position and a posture without being affected by magnetic field, atmospheric pressure, temperature and the like, based on a plurality of optical information sources arranged on an object surface. <P>SOLUTION: Object recognition having a space resolution for three- dimensional position and three-dimensional posture is realized using a photographed image with a two-dimensional image sensor, by attaching a plurality of pieces of optical discrimination information onto the object. For example, three or four markers are arranged on the surface of the measuring object, and positions of the markers are traced in an image-picked-up image. An optimum three-dimensional position and posture estimating algorithm is selected in response to the number of the detected markers and a positional relation thereof to measure the three-dimensional position and posture of the measuring object. <P>COPYRIGHT: (C)2003,JPO

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a three-dimensional position / orientation measuring device and method, a storage medium, and a computer program for measuring the spatial position and orientation of an object placed in the real world, and more particularly to a computer program. , A three-dimensional position / orientation measuring apparatus and method for measuring the position and orientation of an object in space based on a plurality of information signals emitted by the object,
The present invention relates to a storage medium and a computer program.

More specifically, the present invention relates to a three-dimensional position / orientation measuring apparatus and method for measuring the position and orientation of an object placed in the real world by an optical method that is not affected by magnetic fields, atmospheric pressure, temperature, etc. The present invention relates to a storage medium and a computer program, and more particularly, to a three-dimensional position / orientation measuring apparatus and method for measuring the position and orientation of a plurality of optical information sources arranged on the surface of an object, a storage medium,
And computer programs.

[0003]

2. Description of the Related Art In the modern age of advanced information processing technology and information communication technology, information devices such as personal computers and personal digital assistants are ubiquitous in the real world such as offices and homes. To do. In such an environment, actively connect to "Ubiquitous Computing," which connects devices to obtain desired information anytime and anywhere, and the real-world situation (real-world things, user positions, etc.). It is expected that the augmented reality system (Augmented Reality: AR) used for

The concept of ubiquitous computing is that the environment of computers that can be used regardless of where a person moves is the same. In other words, because it is "anytime, anywhere", the ultimate ubiquitous computing is not necessarily a computer or PDA (Personal Dig
Ital Assistant) and information terminals such as mobile phones are not required.

Further, according to the augmented reality system, it is possible to provide a service utilizing the real world situation such as the position of the user. In this case, the user simply holds the mobile terminal, and the system presents information according to real-world things in the vicinity of the user or in the field of view, and uses the vast amount of information on the network to carry out daily life. Can support all aspects. For example, when a user visits a CD shop by holding a camera-equipped mobile terminal in a shopping mall, a recommended new song is displayed on the terminal. Also, looking at the signboard of the restaurant, the impression of the food is displayed.

However, when a computer or a peripheral device (that is, a target such as a user terminal) as a data transfer destination is designated on the network or an attempt is made to obtain information related to the position of the user or a real world object, it is immediately noticeable. It is necessary to know the name (or the ID unique to the device, the network address, the host name, the resource identification information such as the URL / URI) even if the other party is in front of. That is, in terms of user operations, the computers are linked only in an indirect form, and the intuition is somewhat lacking.

Further, as a technique for transferring the identification information of the user while omitting a complicated procedure, such as an RF tag,
Methods using real world computing have been proposed. According to these methods, the user does not need to consciously access the network, and the information related to the object can be acquired from the ID of the object automatically picked up.

The RF tag is a device including unique identification information and a readable / writable storage area, and transmits a radio wave corresponding to the identification information or the stored information in response to reception of a radio wave of a specific frequency. The reading device can read the identification information of the wireless tag and the information written in the storage area. Therefore, a device ID, a network address, and a host name are given as identification information of the wireless tag, and a URL /
By writing the information related to the URI and other objects, the system can execute the registered application (for example, "launch mail") or the network address of the other party based on the recognized ID. Can be searched for to automatically establish a connection, or resource access can be performed based on the recognized URL.

However, in the case of the RF tag, the user has to point or contact the RF tag to the tag reader. That is, it is possible to recognize only an object at a close range and not a far object.

Of course, there are applications in real world situations other than the augmented reality system described above. For example, a real world situation such as a three-dimensional position or orientation of an object can be used as a three-dimensional user interface in a home entertainment device or the like.

In order to obtain the real world situation such as the three-dimensional position and posture of an object, for example, a magnetic method,
It is conceivable to use a measurement system using an ultrasonic method, a mechanical method, an optical method, or the like. The magnetic method is a three-dimensional measurement using magnetic conversion technology, and is an application of a phenomenon in which a current is induced when a coil is placed in a magnetic field. The ultrasonic system is composed of a transmitter and a receiver, and performs three-dimensional measurement from the sound pressure and arrival time of the received ultrasonic waves. The mechanical system has a mechanically movable part such as an articulated arm, and obtains three-dimensional position information from its movement. In the optical method, three or more markers are photographed by a camera, and three-dimensional measurement is performed based on the obtained image information.

However, since the magnetic method applied so far is a measurement system using a magnetic field, it is affected by electronic equipment, metal parts, and geomagnetism that disturb the magnetic field.
Further, since the ultrasonic method measures the phase or arrival time of ultrasonic waves, it is affected by atmospheric pressure and temperature. Further, the mechanical system becomes expensive to obtain a certain degree of accuracy, and the measuring range becomes narrow. Also, considering that a plurality of mechanical devices are handled at the same time, it is more difficult to handle than other devices.

On the other hand, the optical system can measure three-dimensional information over a wide range without being affected by a magnetic field, atmospheric pressure, temperature and the like. The act of "seeing" is very wide range and excellent. However, when the visual information such as the marker is hidden by the hand or other object and the marker is not detected from the acquired image data, it is impossible to measure the three-dimensional information. Further, even when all the markers are detected, it is not always uniquely determined by the algorithm that estimates the three-dimensional position and orientation from the image data, and depends on the image coordinate value, the number, and the combination of the detected markers. To do.

[0014]

An object of the present invention is to provide an excellent three-dimensional position / orientation measuring apparatus and method capable of measuring the position and orientation in space of an object placed in the real world. It is to provide a medium and a computer program.

A further object of the present invention is to provide an excellent three-dimensional position / orientation capable of measuring the position and orientation of an object placed in the real world by an optical system that is not affected by magnetic fields, atmospheric pressure, temperature and the like. A measuring device and method, a storage medium, and a computer program are provided.

A further object of the present invention is to measure the position and orientation of an object based on a plurality of optical information sources arranged on the surface of the object, without being affected by magnetic fields, atmospheric pressure, temperature and the like. It is to provide a robust three-dimensional position / orientation measuring apparatus and method, a storage medium, and a computer program.

[0017]

The present invention has been made in consideration of the above problems, and the first aspect thereof is to estimate the spatial position and orientation of an object in the physical space. A dimensional position / orientation measuring device or method, in which a plurality of optical identification information whose positional relationships are known are arranged on a measurement target object, and a scene in a real space including the measurement target object. An image input section or step for capturing
An identification information extraction unit or step for extracting optical identification information from the input image by the image input unit or step, and a space of the measurement target object according to the state of the optical identification information extracted by the identification information extraction unit or step. A position / orientation calculation method selecting unit or step for selecting a method for calculating the target position and orientation, and the optical information extracted by the identification information extracting unit according to the method selected by the position / orientation calculation method selecting unit. And a position / orientation calculation unit or step for calculating the spatial position and orientation of the object to be measured using the identification information.
An attitude measuring device or method.

According to the three-dimensional position / orientation measuring apparatus or method according to the first aspect of the present invention, the position or orientation of the object is measured based on a plurality of optical information sources arranged on the surface of the object. That is, a plurality of pieces of optical identification information are attached to an object, and an object having a spatial resolution such as a three-dimensional position and orientation is recognized by using an image captured by a two-dimensional image sensor. Since the measurement is based on optical data transmission, the measurement can be performed without being affected by the magnetic field, atmospheric pressure, temperature and the like.

For example, it is possible to arrange optical identification information at three or more points on the surface of a plate-shaped object to be measured and track the spatial position and orientation of these optical identification information in a captured image. The optical identification information referred to here can be composed of, for example, a light emitting element such as an LED that blinks light,
By encoding the identification information and other data into a blinking pattern, data can be transmitted from the measurement target object to the three-dimensional position / orientation measuring device.

Further, four or more pieces of optical identification information whose positional relationship is known may be provided on the object to be measured. Further, it may be arranged such that there is at least one combination of the optical identification information which becomes the four vertices of the parallelogram.

Alternatively, the optical identification information may be arranged at each vertex of the cube-shaped measuring object. In such a case, it is possible to form a large number of combinations of the optical identification information that form the four vertices of the parallelogram. Then, the image input unit can capture some combinations of parallelograms from the cube according to the direction in which the object to be measured is viewed and the occlusion by the user's hand or other obstacle.

Further, the optimum algorithm for estimating the three-dimensional position / orientation from a plurality of positions detected on the image is not unique, and varies depending on the number of detected optical identification information and its situation. . According to the three-dimensional position / orientation measuring apparatus or method according to the first aspect of the present invention, a plurality of algorithms for estimating the three-dimensional position / orientation are prepared in advance, and the optical signals detected from the input image are detected. The optimum three-dimensional position / orientation estimation algorithm can be selected according to the number of pieces of identification information and the positional relationship to measure the three-dimensional position / orientation of the measurement target object.

For example, Robert M. Haralick, Chung-nan
Lee, Karsten Ottenberg, and Michael Nolle, "Analysis and Solutions of The Three Point Persp"
ective Pose Estimation Problem "(In Proceedings of
the Conference on ComputerVision and Pattern Reco
gnition, Maui, Hawaii, USA, pp.592-598, 1991) describes a method for measuring the three-dimensional position and orientation of an object from the known three points on the object. There is.

Therefore, the position / orientation calculation method selection unit or step is responsive to the extraction of three or more optical identification information by the identification information extraction unit or step, and the position of three points on the image. The method by Robert et al., Which mathematically calculates the corresponding three-dimensional position and orientation based on, may be selected.

However, even when three or more pieces of optical identification information are extracted from the input image, at least one side of the triangle formed by the three pieces of optical identification information is in the image input section. If it is substantially parallel to the projection plane, the spatial position of the apex facing this side cannot be uniquely obtained. Therefore, in such a case,
The position / orientation calculation method selection unit or step selects a method other than the mathematical calculation method for obtaining the corresponding three-dimensional position and orientation based on the positions on the image of three points whose spatial positional relationships are known. Is preferred.

A paper entitled "Augmented Reality System Based on Marker Tracking and Its Calibration" by Hirokazu Kato, Mark Billinghurst, Koichi Asano, and Keihachiro Tachibana (Journal of the Virtual Reality Society of Japan, Vol.4, No.4) , 1999)
Describes a method of measuring a three-dimensional position and orientation of a parallelogram based on four markers arranged at each vertex of the parallelogram.

Therefore, the position / orientation calculation method selection unit or step mathematically calculates the corresponding three-dimensional position and orientation based on the positions on the image of four points forming a known parallelogram in the real space. It is also possible to select the method of Kato's work that is calculated dynamically.

Further, when a plurality of combinations of optical identification information which are four vertices of a parallelogram are detected from the input image, the parallelogram having the highest reliability is selected,
The position / orientation may be calculated. The maximum reliability here means that, for example, the area when mapped to a two-dimensional input image becomes maximum.

The position / orientation calculation method selection unit or step mathematically calculates the spatial position and orientation of the object to be measured based on the state of the optical identification information extracted by the identification information extraction unit or step. If it is determined that this is not preferable, the method for estimating the three-dimensional position and orientation of the object to be measured in the previous frame by the image input unit or step may be selected as an initial value. Good.

Further, a second aspect of the present invention is a computer software written so as to execute processing for estimating a spatial position and orientation of an object in a physical space on a computer system. A storage medium physically stored in a readable format, wherein the computer software is provided with a plurality of optical identification information whose mutual positional relationship is known on the object to be measured,
An image input step of capturing a scene in a real space including an object to be measured, an identification information extraction step of extracting optical identification information from an input image by the image input step, and an optical element extracted by the identification information extraction step. Position / orientation calculation method selecting step for selecting a method for calculating the spatial position and orientation of the measurement target object according to the state of the physical identification information, and according to the method selected by the position / orientation calculation method selecting step, And a position / orientation calculation step of calculating a spatial position and orientation of the measurement target object using the optical identification information extracted by the identification information extraction step.

The storage medium according to the second aspect of the present invention is a medium for providing computer software in a computer-readable format to a general-purpose computer system capable of executing various program codes, for example. Such a medium is, for example, a DVD (Digital Vers
atile Disc), CD (Compact Disc), FD (Flexible Disc)
Disk), MO (Magneto-Optical disc), and other removable storage media. Alternatively, it is technically possible to provide computer software to a specific computer system via a transmission medium such as a network (whether the network is wireless or wired).

Further, the storage medium according to the second aspect of the present invention is a computer system having a predetermined computer
A computer for realizing software functions
It defines a structural or functional collaborative relationship between software and a storage medium. In other words, the second aspect of the present invention
By installing the predetermined computer software in the computer system via the storage medium according to the third aspect, the cooperative action is exerted on the computer system, and the three-dimensional position according to the first aspect of the present invention. It is possible to obtain the same effects as those of the posture measuring device or the method thereof.

Further, a third aspect of the present invention is a computer program written so as to execute processing for estimating a spatial position and orientation of an object in a physical space on a computer system. Then, a plurality of optical identification information whose mutual positional relationship is known is disposed on the measurement target object, and an image input step of capturing a scene in real space including the measurement target object, and the image. An identification information extraction step of extracting optical identification information from the input image by the input step, and for calculating the spatial position and orientation of the measurement target object according to the state of the optical identification information extracted by the identification information extraction step The position / orientation calculation method selecting step for selecting the above method, and the identification information extraction step according to the method selected in the position / orientation calculation method selecting step. Is a computer program characterized by comprising Tsu and position and orientation calculation step of calculating a spatial position and orientation of the measured object by using the optical identification information extracted by the flop, the.

A computer according to the third aspect of the present invention
The program defines a computer program written in a computer-readable format so as to realize a predetermined process on a computer system. In other words, by installing the computer program according to the third aspect of the present invention in the computer system, a cooperative action is exerted on the computer system, and the three-dimensional position according to the first aspect of the present invention. It is possible to obtain the same effects as those of the posture measuring device or its method.

Further objects, features and advantages of the present invention are as follows.
It will be apparent from the embodiments of the present invention described later and the more detailed description based on the accompanying drawings.

[0036]

BEST MODE FOR CARRYING OUT THE INVENTION Embodiments of the present invention will be described below in detail with reference to the drawings.

The three-dimensional position / orientation measuring system according to the present invention attaches a plurality of optical identification information to a physical object existing in the real world,
By using a three-dimensional image sensor to perform image processing and image recognition to identify an object and realize object recognition with a spatial resolution such as its three-dimensional position and orientation.

As the optical identification information attached to the real-world object, an optical signal consisting of a blinking light source such as an LED can be used in addition to the visual code encoded in the color space pattern. In the latter case,
The data can be transmitted after being encoded into a time-series optical signal such as a blinking pattern in which the data does not change according to the distance.

The image sensor is, for example, a CMO.
Like an S (Complementary Metal Oxide Semiconductor) sensor or CCD (Charge Coupled Device) sensor, it has a configuration in which a myriad of light-receiving elements, that is, pixels, are arranged in a two-dimensional array, and optical signals and their spatial information are stored in all pixels. Decode with. The image sensor can capture the scene as a normal camera and receive optical signals located in the field of view of the image sensor from long distances.

It is assumed that the plurality of optical identification information attached to the real world object are not only identifiable to each other, but also their spatial positional relationships are known in advance. In such a case, by recognizing the real-world object with a measuring device having a spatial resolution, not only the real-world object is simply identified, but also its three-dimensional position and posture are calculated by a mathematical calculation method or the like. Can be estimated. The spatial position and orientation of a real-world object is, so to speak, a real-world situation.

Therefore, the real world object provided with the optical identification information can be used as a transmitter for transmitting the real world situation. Furthermore, this three-dimensional position / orientation measurement system can be used to realize an augmented reality system (AR) that positively uses the situation of the real world (such as the things in the real world and the position of the user).

According to the augmented reality system, it is possible to provide a service using real world information such as the position of the user. In this case, the user simply holds the mobile terminal, and the system presents information according to real-world things in the vicinity of the user or in the field of view, and uses the vast amount of information on the network to carry out daily life. You can enjoy support in all aspects. For example, if you visit a CD shop in a shopping mall while holding your camera-equipped mobile device,
The recommended new song is displayed on the terminal. Also, looking at the signboard of the restaurant, the impression of the food is displayed.

In the specification of Japanese Patent Application No. 2001-325356 already assigned to the present applicant, an optical signal for carrying or transmitting identification information and other data in an optical format and a high speed signal for capturing the optical signal. Discloses a data communication system which realizes data transmission which has a spatial resolution and can be used even in a long distance by using such a two-dimensional image sensor. In the data communication system described in the specification, a blinking light source such as an LED is used as an optical signal, and data is not changed according to a distance, instead of being encoded into a color space pattern like a visual code. Data is transmitted after being encoded into a time-series optical signal such as a pattern. The image sensor has a configuration in which an infinite number of light receiving elements, that is, pixels, such as a CMOS sensor or a CCD sensor, are arranged in a two-dimensional array, and an optical signal and its spatial information are decoded by all pixels. Thus, the image sensor can capture the scene as a normal camera and receive optical signals located in the field of view of the image sensor from long distances.

A. System Configuration FIG. 1 schematically shows the configuration of a three-dimensional position / orientation measuring system according to an embodiment of the present invention. As shown in the figure, this system includes a measurement target object 101, a camera 102 that captures the measurement target object 101, and a three-dimensional position / orientation measurement device 103 that performs image processing / image recognition on an image captured by the camera 102. Composed of.

The measurement target object 101 is provided with identifiable markers in order to enable the three-dimensional position / orientation measurement thereof. In the example shown in the figure, three markers 104 a to 104 C are attached to known positions on the measurement target object 101. In addition, the measurement target object 10
Each of the markers 104a to 104c mounted on
Has visual identification information including a unique color, shape, pattern, or blinking pattern of light, and can be identified for each marker. Moreover, each marker 104a-
The optical identification information 104c and each marker 10
The spatial positional relationship between 4a to 104c is a three-dimensional position.
It is assumed that the posture measuring device 103 is known.

The camera 102 uses, for example, an ideal pinhole lens with no lens distortion, and a CCD or C
A two-dimensional image sensor such as a MOS can capture a landscape including the measurement target object 101 and other scenes. The image frame captured by the camera 102 is input to the three-dimensional position / orientation measuring device 103 as reception data having a spatial resolution.

The three-dimensional position / orientation measuring device 103 is composed of a computer system such as a personal computer (PC), and the camera 10 is connected via a USB (Universal Serial Bus) or other external interface.
2 can be connected to capture a captured image in the form of a computer file. On the three-dimensional position / orientation measuring apparatus 103, an application for performing a three-dimensional position / orientation measuring process based on marker detection in an image frame is running, and each marker 10 extracted on the input image is displayed.
Based on the positions of 4a to 104c, the real world situation such as the position and orientation of the measurement target object 101 in the real space is measured.
The three-dimensional position / orientation measuring device 103 may further provide an augmented reality service according to the real world situation based on the measurement result.

FIG. 2 shows the three-dimensional position and
The hardware configuration of the posture measuring apparatus 103 is schematically shown.

CPU (Cent) which is the main controller
The ral processing unit) 101 executes various applications under the control of an operating system (OS).

In the present embodiment, the CPU 1 uses, for example, a three-dimensional position for measuring the spatial position and orientation of the object 101 to be measured based on data having a spatial resolution such as an image captured by the camera 102. Executes a posture measurement application, an AR service application that provides an augmented reality (AR) service that uses the real-world situation of a real-world object such as the spatial position and orientation of the measurement target object 101, and the like. be able to.

As shown in the figure, the CPU 1 is interconnected with other devices (described later) by a bus 8.

The main memory 2 is a storage device used for loading a program code executed in the CPU 1 and temporarily storing work data of an execution program, and is a semiconductor such as a DRAM (Dynamic RAM). Memory is used. For example, a three-dimensional position / orientation measurement application for measuring the spatial position and orientation of the measurement target object 101 based on data having a spatial resolution such as a captured image of the camera 102, and the measurement target object 10
Augmented Reality (A) according to the real-world situation of the real-world object including the spatial position and posture of 1
R) An AR service application or the like that provides a service is loaded into the main memory 2. Also, the camera 10
The calculation result regarding the spatial position and orientation of the measurement target object 101 based on the captured image by 2 and the AR service content generated according to the real world situation obtained from the calculation result are stored in the main memory 2 as work data. Stored temporarily.

The ROM (Read Only Memory) 3 is
A semiconductor memory that permanently stores data, such as a self-diagnosis test (POST: Power On Sel) at startup.
f Test) and hardware input / output program code (BIOS: Basic Input / Output System).

The display controller 4 is a CPU
1 is a dedicated controller for actually processing the drawing command issued by 1. The drawing data processed by the display controller 4 is once written in, for example, a frame buffer (not shown), and then the display 1
The screen is output by 1.

The display screen of the display 11 is generally
It has a role of visually feeding back the input contents from the user, the processing result thereof, or an error or other system message to the user. In addition, in the present embodiment, the measurement target object 1 is displayed on the display screen of the display 11.
A using the real world situation such as 01 spatial position and posture
It is used to display and output R service contents (for example, a mixed reality image in which a part of the physical space is expanded into a virtual world).

The input device interface 5 is a device for connecting user input devices such as the keyboard 12 and the mouse 13 to the three-dimensional position / orientation measuring device 103.

The keyboard 12 and the mouse 13 have a role of taking user input such as data and commands into the system. In this embodiment, the keyboard 12 and the mouse 13
Starts the 3D position / orientation measurement application, A
It is used by the user to instruct activation of R service application, designation of AR service, and the like.

The network interface 6 is E
The system 103 is connected to a LAN (Local Area Net) according to a predetermined communication protocol such as Internet (registered trademark).
work) and even wide area networks such as the Internet.

On the network, a plurality of host terminals (not shown) are connected in a transparent state to construct a distributed computing environment. Distribution services such as software programs and data contents can be provided on the network. For example, a three-dimensional position / orientation measurement application for measuring the spatial position or orientation of the measurement target object 101 based on data having a spatial resolution such as the captured image of the camera 102, or detected from the captured image. A plurality of algorithms (for example, in a library) that perform three-dimensional position / orientation estimation based on a plurality of markers, a real world of a real world object including the spatial position and orientation of the measurement target object 101, and the like. AR service applications that provide augmented reality (AR) services according to the situation can be downloaded via the network. Also, various AR service contents used in the AR service application are distributed to other host devices via the network.
It can be distributed.

The external device interface 7 is a hardware interface.
An external device such as a disk drive (HDD) 14 or a media drive 15 is connected to a three-dimensional position / orientation measuring device 103.
Is a device for connecting to.

The HDD 14 is an external storage device in which a magnetic disk as a storage carrier is fixedly mounted (well known),
It is superior to other external storage devices in terms of storage capacity and data transfer speed. Placing the software program on the HDD 14 in an executable state is called "installing" the program in the system. Usually HDD14
The operating system program code to be executed by the CPU 1, application programs, device drivers, etc. are stored in a non-volatile manner. For example, a three-dimensional position / orientation measurement application for measuring the spatial position or orientation of the measurement target object 101 based on data having a spatial resolution such as an image captured by the camera 102, or the space of the measurement target object 101. HDD 14 includes an AR service application that provides an augmented reality (AR) service according to the real world situation of real world objects such as physical position and posture.
Can be installed on. In addition, a plurality of algorithms (for example, in a library) that perform three-dimensional position / orientation estimation based on a plurality of markers detected from a captured image, AR service contents used in an AR service application, etc. HDD1
4 may be stored in the memory.

The media drive 15 is a CD (Compact
Disc), MO (Magneto-Optical disc), DVD (Dig)
Ital Versatile Disc) is a device for loading a portable medium such as a disc and accessing the data recording surface thereof.

The portable medium mainly backs up software programs, data files, etc. as computer-readable data, and moves them between systems (that is, including sales, distribution and distribution).
It is used for the purpose. For example, a three-dimensional position / orientation measurement application for measuring the spatial position and orientation of the measurement target object 101 based on data having a spatial resolution such as a captured image of the camera 102, and the measurement target object 10
Augmented Reality (A) according to the real-world situation of the real-world object including the spatial position and posture of 1
R) AR services and applications that provide services can be physically distributed / distributed among a plurality of devices using these portable media. In addition, based on the markers of multiple points detected from the captured image,
A portable medium is used to exchange a plurality of algorithms for posture estimation (for example, in a library) and various AR service contents used in AR service applications with other devices. can do.

The camera interface 9 is the camera 1
This is a device for connecting 02, and is configured by a USB interface, for example. Alternatively, it may be configured with an interface that acquires a moving image from the camera 102 like a video capture card. Camera 102
Is a configuration in which pixels are arranged in a two-dimensional array, and an optical signal from the measurement target object 101 and its spatial information are decoded by all pixels.

An example of the three-dimensional position / orientation measuring device 103 as shown in FIG. 2 is a personal computer "PC / AT" (Personal Computer / Advanced) of IBM Corp.
Technology) "compatible machine or a successor machine. Of course, a computer configured with another architecture can also be applied as the three-dimensional position / orientation measuring apparatus 103 according to the present embodiment.

FIG. 3 shows an example of the structure of the measuring object 101. As shown in the figure, the object 101 to be measured has a plate-like triangle, and optically identifiable markers 104a to 104c are arranged at respective vertices thereof.

Each of the markers 104a to 104c has optically unique identification information consisting of a unique color, shape, pattern, or blinking pattern of light, and can be identified for each marker. It is assumed that the visual identification information of each of the markers 104a to 104c and the spatial positional relationship between the markers are known to the three-dimensional position / orientation measuring device 103. Therefore, when the measurement target object 101 is attached to a certain real-world object, the measurement target object 101 gives information for identifying this object by the combination of the identification information held by the markers 104a to 104c, and the spatial position and orientation of the object. Can give information about real world situations.

For example, each of the markers 104a to 104c is L
When configured with a device that blinks light such as an ED, each of the markers 104a to 104c can encode data and transmit it in a time-series optical signal such as a blinking pattern. In such a case, each of the markers 104a to 104
The measurement target object 101 provided with c can function not only as an index for measuring the identification information and the spatial position and orientation of the real world object, but also as a transmitting device. Further, since the data of the optical signal does not change depending on the distance, it is possible to perform robust data transmission with respect to the distance from each of the markers 104a to 104c.

On the other hand, the camera 102 connected to the three-dimensional position / orientation measuring device 103 is an image in which an infinite number of light receiving elements, that is, pixels are arranged in a two-dimensional array, such as a CMOS sensor or a CCD sensor. A sensor (not shown) is provided and has a spatial resolution for each of the markers 104a to 104c on the measurement target object 101.

FIG. 4 schematically shows the operating characteristics of the camera 102 and the three-dimensional position / orientation measuring device 103 when the measurement object 101 is equipped with three light emitting diodes as the markers 104a to 104c. ing. Each of the light emitting diodes can encode the data to be transmitted into a blinking pattern of light and transmit the encoded data. Of course, the baseband signal composed of the transmission data may be represented as it is by a light blinking pattern, or the optical signal may be output after performing modulation processing such as frequency modulation or amplitude modulation.

In this case, the blinking pattern of each light emitting diode is controlled by the condenser lens system (not shown).
An image is formed on the light receiving surface of the two-dimensional two-dimensional image sensor, and is detected by the light receiving element at a position corresponding to the position and orientation of the measurement target object 101 in the real space.

For example, the coordinate values of the light receiving elements (pixels) on which the light emitted from the light emitting diodes 104a to 104c are imaged on the two-dimensional light receiving surface of the image sensor are (10, 10) and (90, 90), respectively. , (40, 70), the blinking pattern of the corresponding light emitting diode at each pixel position is detected as a temporal change in the received light intensity (brightness). By binarizing the received light intensity with a predetermined threshold value, the 1/0 bit string corresponding to the original transmission data can be restored.

Thus, the three-dimensional position / orientation measuring device 1
03 decodes the captured image of the scene including the measurement target object 101 with all the pixels by the camera 102 to acquire the optical signals sent from the markers 104a to 104c and the spatial information of the measurement target object 101. be able to. That is, it is possible to perform data transmission with the measurement target object 101 by an optical signal, and to provide an augmented reality service based on the real world situation that spatial information means.

B. Three-dimensional position / orientation measuring method Next, the three-dimensional position / orientation measuring apparatus 1 according to the present embodiment.
A method of measuring the three-dimensional position / orientation of the measurement target object 101 according to No. 03 will be described.

B-1 Measurement Target with Three Markers Arranged
Three-dimensional position / orientation measurement of an object The three-dimensional positional relationship of all the markers 104a to 104c arranged on the measurement target object 101 is known. Assuming that the measurement target object 101 is rotated by α around the X axis, β around the Y axis, and γ around the Z axis, the rotation matrix R of the measurement target object 101 is expressed as follows.

[0076]

[Equation 1]

If the object 101 to be measured is moved to the position (X _t , Y _t , Z _t ) in the camera coordinate system, the translation matrix T is expressed as follows.

[0078]

[Equation 2]

Here, after the marker 104 located at the point (X _m , Y _m , Z _m ) on the object 101 to be measured rotates and translates, it is converted into the point (X _c , Y _c , Z _c ). Assuming that, these relationships are expressed as follows.

[0080]

[Equation 3]

In the above equation, if three markers having known spatial positional relationships can be detected from the image of the object 101 to be measured, R and T, that is, the object 101 to be measured, can be obtained as the solution of the simultaneous equations. It is shown that the three-dimensional position and orientation of can be obtained. For example, Robert M. Ha
ralick, Chung-nan Lee, Karsten Ottenberg, and Mich
ael Nolle co-authored paper "Analysis and Solutions of The
Three Point Perspective Pose Estimation Problem "
(In Proceedings of the Conference on ComputerVisi
on and Pattern Recognition, Maui, Hawaii, USA, pp.
592-598, 1991), a known 3 mounted on the target object.
A method for measuring the three-dimensional position and orientation of the object from the position of a point is described.

The coordinate values (X, Y) on the two-dimensional captured image of the marker 104 moved to the point (X _c , Y _c , Z _c ) are as follows.

[0083]

[Equation 4]

If three markers having known spatial positional relationships can be detected from the captured image, R and T, that is, the three-dimensional position and orientation of the object 101 to be measured, can be obtained as the solution of the simultaneous equations. You can However, as an exception to this, an arbitrary side a of the measurement target object 101
When b is parallel to the projection screen 102 ′ of the camera 102 (see FIG. 5), the solution of simultaneous equations is a multiple solution. For this reason, it is not possible to uniquely determine whether the remaining point c configuring the measurement target object 101 is located at 104c-1 or 104c-2 from only one captured image.

In such a case, matching is performed in which the marker 104 on the rotated or moved measurement object 101 is two-dimensionally mapped and the position of the marker in the image data is matched to estimate the three-dimensional position and orientation. The method can be applied.

FIG. 6 schematically illustrates an example of the matching method. For example, when the object to be measured in the previous frame captured by the camera 102 is designated by reference numeral 101 ′, error components Δα, Δβ, Δγ that are allowed around each of the X-axis, Y-axis, and Z-axis are parallel to this. An error component ΔT that is allowed for movement is applied to map on the projection screen 102 ′ of the camera 102. Then, the optimum three-dimensional position / orientation of the measurement target object 101 is estimated by performing image registration (Image Registration) so that the amount of deviation from each of the markers 104a to 104c in the current captured image is minimized. be able to.

Even with such a matching method, the problem of multiple solutions as shown in FIG.
Object 101 to be measured in the previous frame captured in 02
When the three-dimensional position and orientation of are used as initial values, it can be expected to converge to the closest solution. Therefore, if the moving speed of the measurement target object 101 is not higher than the frame rate, the optimum three-dimensional position / orientation is estimated.

In this matching method, the object to be measured is minimized so that the error between the positions of the markers 104a to 104c on the image data and the positions obtained by mapping these on the two-dimensional plane (that is, the light receiving surface of the image sensor) is minimized. Estimating the spatial position and orientation of 101, this problem can be replaced by a minimum search problem.

Various methods have been proposed as solutions to the minimum value search problem. However, in many cases, a three-dimensional position / orientation measuring device requires real-time performance, so that a relatively high speed such as a mountain climbing method is required. Any search method is suitable. However, the hill climbing method has a drawback that it tends to converge to a local solution and largely depends on the initial value. As described above, in the minimum value search problem, there is a trade-off relationship between the global search and the calculation time, and it is difficult to find an optimum solution in a short calculation time.

Object to be measured 101 in which three markers 104a to 104c whose positional relationships are known in advance are arranged.
Each marker 10 detected on the input image by photographing
3 of the measurement target object 101 based on the positions of 4a to 104c.
Although it is possible to estimate the dimensional position / orientation, there are various methods, and each has advantages and disadvantages. Therefore, the present inventors consider that when estimating the spatial position and orientation of a captured image of the measurement target object 101, a hybrid method that complements the disadvantages of each method is desired.

FIG. 7 shows three markers 104a to 104.
An example of a processing procedure for estimating the three-dimensional position / orientation based on the captured image of the measurement target object 101 in which c is arranged is shown in the form of a flowchart. This processing procedure includes a method of mathematically calculating a three-dimensional position / orientation by using simultaneous equations (a mathematical calculation method: the above (Robert et al.)) And a method of estimating a three-dimensional position / orientation by matching (matching). Method: A method in which the above (see FIG. 6)) is hybridized is adopted. Actually, CP
This processing procedure is performed by inputting the captured image of the measurement target object 101 into the three-dimensional position / orientation measurement application being executed by U1. Hereinafter, the three-dimensional position / orientation estimation processing will be described with reference to the flowchart shown in FIG. 7.

First, various variables used for three-dimensional position / orientation measurement such as three-dimensional position data of the markers 104a to 104c arranged on the object 101 to be measured are initialized (step S1).

Next, image data is input from the camera 102 (step S2).

Then, the input image data is searched to extract the markers 104a to 104c (step S3). As described above, each of the markers 104a to 104
c is composed of an LED or the like that emits a blinking pattern in which data corresponding to identification information is encoded, and can be identified. In this processing step, the identification information of each of the markers 104a to 104c existing on the input image and the respective image coordinates are calculated.

Next, it is separately defined which of the mathematical calculation method and the matching method is used to obtain the three-dimensional position / orientation of the measurement target object 101 based on the image coordinates of the marker existing on the input image. It is selected by the selected selection routine (step S4).

The mathematical calculation method referred to here is, for example, the three markers 104a to 104c detected on the photographed image.
This is a method of obtaining a rotation matrix R and a translation sequence T as solutions of simultaneous equations from the position of, and is described in a paper by Robert et al. The matching method is a method of estimating the spatial position and orientation of the measurement target object 101 so that the error between the position of each of the markers 104a to 104c on the captured image and the position where these markers are two-dimensionally mapped is minimized. Yes (see Figure 6). In the example shown in FIG. 7, these two types of algorithms are selected, but an algorithm that is a selection candidate may be prepared. However, it is desirable that these selection candidate algorithms are algorithms that complement each other's disadvantages.

Optimal three-dimensional position in step S4
After the posture estimation algorithm is selected, the process returns to step S5, and the process according to each algorithm is performed based on the selected algorithm. When the mathematical calculation method is selected, the three-dimensional position / orientation estimation processing is performed in steps S5 and S6, and when the matching method is selected, in steps S7 and S8, respectively.

After these processes, the estimated three-dimensional position / orientation is stored (step S9), and the process proceeds to step S10. The stored three-dimensional position / orientation is used as an initial value (described later) when the matching method is selected in the next loop. If the three-dimensional position / orientation is not used in the next loop, step S9 may be omitted. If the three-dimensional position / orientation estimation algorithm is not selected, nothing is done and the process proceeds to the next step S10.

In step S10, it is determined whether or not to continue the three-dimensional position / orientation measurement. If it is to continue, the process returns to step S2, and if it is not to continue, this processing routine is finished. Here, the end condition may be, for example, an input from the user or a predetermined rule within the application (for example, game over in a game). Also, restrictions on hardware or software such as memory full may be set as the end condition.

FIG. 8 shows, in the form of a flowchart, a more detailed processing procedure for selecting an algorithm for obtaining the three-dimensional position / orientation of the measuring object 101 in step S4 in FIG.

First, the number of markers that can be detected on the input image is determined (step S11). If all three markers can be extracted from the input image, the process proceeds to step S12.

In step S12, a discriminant is calculated from the image coordinates of the three markers extracted from the input image.
As already described with reference to FIG. 5, when an arbitrary side ab of the measurement target object 101 is parallel to the projection screen of the camera 102, the solution of the simultaneous equations becomes a multiple solution, and therefore the remaining The position where the point c exists cannot be uniquely obtained. The discriminant here is for determining whether or not the solution of simultaneous equations is a multiple solution, and is described in a paper by Robert et al.

In step S13, it is determined whether there are multiple solutions based on this discriminant. If it is determined that there is no multiple solution,
In step S14, a mathematical calculation method is selected as the three-dimensional position / orientation estimation algorithm.

On the other hand, when it is determined that there are multiple solutions,
In step S15, it is further determined whether the trustworthy initial value is set. For example, it is checked whether or not the three-dimensional position / orientation is measured in the previous loop (that is, the position / orientation estimation process in the previous image frame). When the input is time-series image data and the interval is shorter than the moving speed of the measurement target object 101, the three-dimensional position / orientation measured in the previous loop is used as an initial value (reference data). Because you can.

If the initial value has been set, it is further determined whether the matching method has continued n times (step S16). If they are not continuous, the process proceeds to the next step S17 and the matching method is selected as the three-dimensional position / orientation estimation algorithm.

The determination in step S16 means that the matching method is given up when the matching method has already been repeated n times. This is because it is considered that the accuracy and reliability of the solution have already been lost when the estimated solution is already used by repeating the matching method n times. In addition, the matching method easily converges to a local solution, and once it converges to a local solution, it becomes difficult to find an optimal solution. When a method such as a simulated annealing method or a genetic algorithm that is relatively difficult to converge to a local solution is used as the optimum value search method, step S16 may be omitted.

When it is determined in step S11 that the number of markers is 3 points, when it is determined in step S15 that the initial value of the matching method is not set to a reliable value, and when the matching method is determined in step S16. If it is determined that the n-th position is continuous, the process proceeds to step S18, and the three-dimensional position / orientation estimation algorithm is not selected. In this case, the result that the three-dimensional position / orientation measurement is impossible is returned.

B-2.4 Measurement Target with Four Markers Arranged
Three-dimensional position / orientation measurement of object In the embodiment described in the previous section, the position of the measurement target object 101 in which three markers each having unique identification information (or transmitting) and having a known mutual positional relationship are arranged.・ It measures the posture. On the other hand, in this section, a method of measuring a three-dimensional position / orientation in the case where four markers having identification information and having a known positional relationship with each other are arranged on the measurement target object 101 will be described.

FIG. 9 shows another example of the structure of the measuring object 101. As shown in FIG.
Has a plate-like shape, and four markers 104a to 104d are arranged at the respective vertices so as to be the respective vertices of the parallelogram.

Similar to the above, each of the markers 104a to 104d
Has an optically unique identification information such as a unique color, shape, pattern, or blinking pattern of light,
It is possible to identify each marker. Moreover, each marker 104a-
These three-dimensional position / orientation measuring device 103 is used for the optical positional information of 104d and the spatial positional relationship between each marker.
Known to. The measurement target object 101 can give information for identifying this object by a combination of identification information held by the respective markers 104a to 104d, and also give information on a real world situation such as a spatial position and orientation.

For example, Hirokazu Kato, Mark Billinghurst,
"Augmented Reality System Based on Marker Tracking and Its Calibration" co-authored by Koichi Asano and Keihachiro Tachibana (Journal of Virtual Reality Society of Japan, Vol.4, No.4, 199)
9) describes a method for measuring the three-dimensional position and orientation of a parallelogram based on four markers arranged at each vertex of the parallelogram. In order to measure the position / orientation of the measurement target object 101 as shown in FIG. 9 according to the document, four markers 104a to 104d should be arranged in a parallelogram shape. It should be fully understood that more accurate measurement can be expected by using the information of 4 points rather than 3 points.

FIG. 10 shows an example of a processing procedure for estimating the three-dimensional position / orientation of the object 101 to be measured, on which four markers 104a to 104d forming the vertices of a parallelogram are arranged. Is shown in the form of a flow chart. This processing procedure is performed by a method of mathematically calculating a three-dimensional position / orientation using a geometric constraint condition (a mathematical calculation method: the above-mentioned (Kato Soga)) and matching.
A hybrid method of the method of estimating the dimensional position / orientation (matching method: the above (see FIG. 6)) is adopted. Actually, the three-dimensional position being executed by the CPU 1
This processing procedure is performed by inputting the captured image of the measurement target object 101 into the posture measurement application. Hereinafter, referring to the flowchart shown in FIG. 7,
This three-dimensional position / orientation estimation process will be described.

First, various variables used for three-dimensional position / orientation measurement such as three-dimensional position data of the markers 104a to 104d arranged on the measurement object 101 are initialized (step S21).

Next, the image data is input from the camera 102 (step S22), the input image data is searched, and the markers 104a to 104d are extracted (step S23). As described above, each marker 104a
.About.104d are composed of LEDs or the like that emit unique flashing patterns, and can be identified. In this processing step, each marker 1 existing on the input image is
The identification information of 04a to 104d and the image coordinates of each will be calculated.

Next, based on the number of markers existing on the input image, the three-dimensional position / position of the measuring object 101 is calculated by using either a mathematical calculation method or a matching method.
Whether to obtain the posture is selected by a separately defined selection routine (step S24).

The mathematical calculation method referred to here is, for example, the position / orientation of the object 101 to be measured by tracking four markers 104a to 104d arranged at the positions forming the vertices of a parallelogram in the input image. Is a method for mathematically obtaining, and is described in a paper by Kato Soga (above). In addition, the matching method is performed by each marker 104a on the captured image.
This is a method of estimating the spatial position and orientation of the measurement target object 101 so that the error between the positions of 104d and the two-dimensionally mapped positions of them is minimized (see FIG. 6). In the example shown in FIG. 10, these two types of algorithms are selected, but an algorithm that is a selection candidate may be prepared. However, it is desirable that these selection candidate algorithms are algorithms that complement each other's disadvantages.

In the mathematical calculation method, the four vertices of the parallelogram must be extracted when calculating from the position information of four points. Therefore, in step S24, which of the mathematical calculation method and the matching method is used to determine the three-dimensional position / orientation can be selected depending on the number of markers existing on the input image.

After selecting the optimum three-dimensional position / orientation estimation algorithm in step S24, step S25
Then, the process according to each algorithm is performed based on the selected algorithm. When the mathematical calculation method is selected, in steps S25 and S26,
When the matching method is selected, the three-dimensional position / orientation estimation process is performed in steps S27 and S28.

After these processes, the estimated three-dimensional position / orientation is stored (step S29), and the process proceeds to step S30. The stored three-dimensional position / orientation is used as an initial value (described later) when the matching method is selected in the next loop. If the three-dimensional position / orientation is not used in the next loop, step S29 may be omitted. If the three-dimensional position / orientation estimation algorithm is not selected, nothing is done and the process proceeds to the next step S30.

In step S30, it is determined whether or not to continue the three-dimensional position / orientation measurement. If it is to continue, the process returns to step S22, and if it is not to continue, the entire processing routine is ended. Here, the end condition may be, for example, an input from the user or a predetermined rule within the application (for example, game over in a game). Further, hardware or software restrictions such as memory full may be set as the end condition.

FIG. 11 shows, in the form of a flowchart, a more detailed processing procedure for selecting an algorithm for obtaining the three-dimensional position / orientation of the measuring object 101 in step S24 in FIG.

First, it is determined whether the number of markers detected in the input image is four (step S31).

When the number of detected markers is 4, the process proceeds to the next step S32, and the mathematical calculation method is selected as the three-dimensional position / orientation estimation algorithm.

On the other hand, if the number of markers is not four, it is determined whether the number of detected markers is three (step S33). If it is determined that there are three points, the process proceeds to step S34, and it is further determined whether a reliable initial value is set. For example, it is checked whether or not the three-dimensional position / orientation is measured in the front loop. When the input is time-series image data and the interval is shorter than the moving speed of the measurement target object 101, the three-dimensional position / orientation measured in the previous loop is used as an initial value (reference data). Because you can. When the initial value is set, it is further determined whether the matching method is repeated n times (step S35). If they are not continuous, the process proceeds to the next step S36 and the matching method is selected as the three-dimensional position / orientation estimation algorithm.

When it is determined in step S33 that the number of markers detected from the input image is not 3 points, or when it is determined in step S34 that the initial value of the matching method is not set to a reliable value. ,
If it is determined in step S35 that the matching method has continued n times, the process proceeds to step S37, and the three-dimensional position / orientation estimation algorithm is not selected. In this case, the result that the three-dimensional position / orientation measurement is impossible is returned.

As described above, the three-dimensional position / orientation estimation algorithm may be selected according to the number of markers on the input image.

B-3. Place a marker at each vertex of the cube
Three-dimensional position / orientation measurement when the object is measured In the above two embodiments, the plate-shaped measurement target object 101
By arranging markers of 3 points or 4 points on the surface of the object and tracking the positions of these markers in the captured image, the object to be measured 10 according to each mathematical or matching algorithm.
The three-dimensional position / orientation of No. 1 is measured.

However, when it is desired to measure the three-dimensional position / orientation of the object 101 to be measured while holding the object 101 in the hand and moving the object 101, even if one of the markers is hidden by the hand or another object, it is 3
It becomes impossible to estimate the dimensional position and orientation. For example, considering the application of a three-dimensional position / orientation measuring device as a home entertainment device (such as a controller of a game device), it is usability that the user can freely move the measurement target object without being aware of occlusion. It is one of the main factors that In other words, it is important to change the shape of the measurement target object according to the actual condition of the application and the operation method thereof, and arrange the markers so that occlusion does not occur. Depending on the case, a shape such as a rod or a grip may be attached to the object to be measured, and the object may be instructed to be held and operated.

In FIG. 12, considering occlusion,
The structural example of the measurement target object 101 in which the number of markers is increased by arranging in three dimensions is shown. In the example shown in the figure, the measurement target object 101 is in the shape of a cube, and eight markers 104a to 104h are provided at each apex thereof.

By arranging the markers 104a to 104h three-dimensionally in this way, the probability that at least one surface of the measurement target object 101 will be extracted becomes high even during manual operation, and the mathematical positions It becomes easy to detect the three-point or four-point markers required to realize the posture estimation method (described above). Therefore, the user can freely measure the measurement target object 10 without being aware of the occlusion problem.
It is possible to move or rotate 1.

In FIG. 13, a marker 10 is added to each vertex of the cube.
An example of a processing procedure for estimating the three-dimensional position / orientation based on the captured image of the measurement target object 101 in which 4a to 104h are arranged is shown in the form of a flowchart. This processing procedure is performed mathematically by using geometric constraint conditions.
A hybrid of a method of calculating a three-dimensional position / orientation (a mathematical calculation method: the above (Kato Soga)) and a method of estimating a three-dimensional position / orientation by matching (a matching method: the above (see FIG. 6)). The method is adopted. Actually, this processing procedure is performed by inputting the captured image of the measurement target object 101 to the three-dimensional position / orientation measurement application being executed by the CPU 1. Below, FIG.
This three-dimensional position / orientation estimation processing will be described with reference to the flowchart shown in FIG.

First, various variables used for three-dimensional position / orientation measurement such as three-dimensional position data of each of the markers 104a to 104h arranged at each vertex of the object 101 to be measured are initialized (step S41).

Next, image data is input from the camera 102 (step S42), the input image data is searched, and each marker 104a to 104h is tried to be extracted (step S43). As already mentioned, each marker 10
4a to 104h are LEDs that emit a unique flashing pattern
, Etc., and each can be identified. In this processing step, the identification information of the marker detected on the input image and each image coordinate are calculated.

Next, it is separately defined which of the mathematical calculation method and the matching method is used to obtain the three-dimensional position / orientation of the measurement target object 101 based on the image coordinates of the marker existing on the input image. It is selected by the selected selection routine (step S44).

The mathematical calculation method referred to here is, for example, the object to be measured 101 which is measured by tracking four markers arranged at the positions forming the vertices of a parallelogram in the input image.
This is a method for mathematically determining the position and orientation of the, and is described in a paper by Kato Soga (above). In addition, the matching method uses the measurement target object 1 so that the error between the position of each marker on the captured image and the position where these markers are two-dimensionally mapped is minimized.
This is a method for estimating the spatial position and orientation of 01 (FIG. 6).
checking). In the example shown in FIG. 13, these two types of algorithms are selected, but an algorithm that is a selection candidate may be prepared. However, it is desirable that these selection candidate algorithms are algorithms that complement each other's disadvantages.

In the mathematical calculation method, the four vertices of the parallelogram must be extracted when calculating from the position information of four points. Therefore, in step S44, which of the mathematical calculation method and the matching method is used to determine the three-dimensional position / orientation can be selected according to the number of markers existing on the input image and the combination thereof. If two or more parallelogram combinations can be extracted from a plurality of markers extracted from the input image, a combination most suitable for position / orientation measurement is selected (described later).

After selecting the optimum three-dimensional position / orientation estimation algorithm in step S44, step S45
Then, the process according to each algorithm is performed based on the selected algorithm. When the mathematical calculation method is selected, in steps S45 and S46,
When the matching method is selected, the three-dimensional position / orientation estimation process is performed in steps S47 and S48.

After these processes, the estimated three-dimensional position / orientation is stored (step S49), and the process proceeds to step S50. The stored three-dimensional position / orientation is used as an initial value (described later) when the matching method is selected in the next loop. If the three-dimensional position / orientation is not used in the next loop, step S49 may be omitted. If the three-dimensional position / orientation estimation algorithm is not selected, nothing is done and the process proceeds to the next step S50.

In step S50, it is determined whether to continue the three-dimensional position / orientation measurement. If it is to continue, the process returns to step S42, and if it is not to continue, this processing routine is completed. Here, the end condition may be, for example, an input from the user or a predetermined rule within the application (for example, game over in a game). Further, hardware or software restrictions such as memory full may be set as the end condition.

FIG. 14 shows, in the form of a flowchart, a more detailed processing procedure for selecting an algorithm for obtaining the three-dimensional position / orientation of the object 101 to be measured in step S44 in FIG.

First, it is determined whether the number of markers detected in the input image is four or more (step S51).

If the number of markers is four or more, it is further determined whether there is a combination of markers forming a parallelogram (step S52).

A combination of markers that form a parallelogram is 1
If there is more than one, the optimal parallelogram combination for measuring the position / orientation of the measurement target object 101 is selected by a separately defined selection routine (step S53). Here, the optimum parallelogram is, for example, a surface closest to the camera, that is, an area of a surface formed by four points on the image if all parallelograms have the same area. Then, a mathematical calculation method using the selected combination of parallelograms is selected (step S54).

On the other hand, if the number of markers is not 4 or more, it is determined whether the number of detected markers is 3 (step S55).

When it is determined that the number of markers detected in step S55 is three, and in step S52
If it is determined that there is no combination of markers forming the parallelogram in step S56, the process proceeds to step S56, and it is further determined whether a reliable initial value is set. For example, it is checked whether or not the three-dimensional position / orientation is measured in the front loop. When the input is time-series image data and the interval is shorter than the moving speed of the measurement target object 101, the three-dimensional position / orientation measured in the previous loop is used as an initial value (reference data). Because you can. When the initial value is set, it is further determined whether the matching method has continued n times (step S5).
7). If they are not continuous, the process proceeds to the next step S58 and the matching method is selected as the three-dimensional position / orientation estimation algorithm. If three markers can be detected, the mathematical calculation method according to the article by Robert et al. (Mentioned above) may be applied instead of the matching method.

If it is not determined in step S55 that the number of markers detected from the input image is three points, or if it is determined in step S56 that the initial value of the matching method is not set to a reliable value. ,
If it is determined in step S57 that the matching method has continued n times, the process proceeds to step S59, and the three-dimensional position / orientation estimation algorithm is not selected. In this case, the result that the three-dimensional position / orientation measurement is impossible is returned.

As described above, in selecting the three-dimensional position / orientation measurement algorithm, a more appropriate one may be selected according to the number and combination of the markers on the input image. Further, as shown in FIG. 12, by arranging a plurality of markers on the measurement target object 101 three-dimensionally, a situation in which the 3D position / orientation estimation algorithm is not selected, that is, 3D position / orientation measurement is impossible. It is possible to reduce the probability of becoming, and to realize more robust 3D position / orientation measurement.

In this embodiment, as a mathematical calculation method for measuring the three-dimensional position and orientation of an object, Hirokazu Kato,
Mark Billinghurst, Koichi Asano, and Keihachiro Tachibana, "Augmented Reality System Based on Marker Tracking and Its Calibration" (Journal of the Virtual Reality Society of Japan, Vol.4, No.4, 1999), A method of measuring a three-dimensional position and orientation of a parallelogram based on four markers is applied.

In this case, the precondition is that the markers forming the four vertices of the parallelogram are extracted from the input image. In addition, 2 from the plurality of markers extracted from the input image
When the above parallelogram combination can be extracted, it is necessary to select a combination that is most suitable for position / orientation measurement. Hereinafter, a method for detecting the four markers forming the parallelogram will be described.

In the case of an object to be measured in which markers are arranged at the respective vertices of a cube as shown in FIG. 15, the set of vertices forming the parallelogram is 6 planes ab constituting each face of the cube.
cd, dcfe, efgh, hgba, hade, bg
fc, and a six-sided abf composed of diagonal vertices
e, dcgh, bged, cfha, dagf, cbh
There are a total of 12 sets of e.

First, from the markers extracted in step S43, it is checked whether there are 12 sets of markers forming the parallelogram. For example, the marker a,
When b, c, d, and e are extracted, the set forming the parallelogram is only one set of abcd. In addition, the markers a, b,
When c, d, e, and f are extracted, the groups forming the parallelogram are three groups of abcd, dcfe, and abfe.

Further, for example, when the markers a, b, c, e, and h are extracted, there is no set forming a parallelogram, and the mathematical calculation method described in the paper by Kato, et al. Therefore, the three-dimensional position and orientation of the measurement target object 101 cannot be measured. In such a case, as in the case where the number of the extracted markers is three, the matching method, etc.
A method of estimating the three-dimensional position and orientation from the positional relationship of points is applied.

Next, when a plurality of pairs forming the parallelogram are detected, the optimum parallelogram is selected from the pairs. The optimum parallelogram referred to here is a parallelogram for which the most accurate three-dimensional position and orientation measurement can be expected.

Generally, it can be expected that the calculation error becomes smaller as the area of the quadrangle obtained by mapping the parallelogram in the three-dimensional space in two dimensions becomes larger, and the parallelogram having the maximum area can be obtained. Optimal parallelogram. If the calculation time does not matter, calculate the three-dimensional position and orientation of each of the detected parallelograms, and use the average of these as the three-dimensional position and orientation of the object to be measured. Is also possible.

In this way, the four markers forming the parallelogram are extracted from the plurality of markers, and the three-dimensional position / position is calculated based on the mathematical calculation method described in the paper by Kato Soga.
The posture can be measured. However, this mathematical calculation method is a method of calculating the three-dimensional position / orientation of the parallelogram, and the three-dimensional position / orientation of the parallelogram is measured.
It has to be converted into 1-dimensional 3D position / orientation.

For example, when the three-dimensional position / orientation is measured for a parallelogram hade, the position / orientation with respect to the coordinate system whose origin is the center of the parallelogram as shown in FIG. 16 and whose normal is the z-axis direction. Is measured. However, when the coordinate system of the measurement target object is a coordinate system whose origin is the center of the measurement target object as shown in FIG. 15, the parallelogram hade is (0,
Since it is located at 0, k), it is necessary to offset by this amount. That is, the parallelogram had shown in FIG.
When e is converted to the position of FIG. 16 (moved by −k in the z-axis direction), an offset is applied, and when the calculated position of the parallelogram is (x, y, z), the position of the measurement target object is (X, y, z−k).

Similarly, when the three-dimensional position / orientation is calculated for the parallelogram abcd, the parallelogram abcd shown in FIG. 15 is converted into the position shown in FIG. 15 (rotated about the y axis by −90 degrees, z Offset is applied as much as it moves by -k in the axial direction. This offset is determined by the coordinate system of each parallelogram with respect to the coordinate system of the object to be measured, and needs to be obtained in advance for each parallelogram.

[Supplement] The present invention has been described in detail with reference to the specific embodiments. However, it is obvious that those skilled in the art can modify or substitute the embodiments without departing from the scope of the present invention. That is, the present invention has been disclosed in the form of exemplification, and the contents of this specification should not be construed in a limited manner. In order to determine the gist of the present invention, the section of the claims described at the beginning should be taken into consideration.

[0159]

As described above in detail, according to the present invention,
It is possible to provide an excellent three-dimensional position / orientation measuring apparatus and method, a storage medium, and a computer program capable of measuring the position and orientation in space of an object placed in the real world.

Further, according to the present invention, it is possible to measure the position and orientation of an object placed in the real world by an optical method which is not affected by magnetic field, atmospheric pressure, temperature, etc. An attitude measuring device and method, a storage medium, and a computer program can be provided.

Further, according to the present invention, it is possible to measure the position and orientation of a plurality of optical information sources arranged on the surface of an object without being affected by the magnetic field, atmospheric pressure, temperature and the like. A robust three-dimensional position / orientation measuring apparatus and method, a storage medium, and a computer program can be provided.

According to the three-dimensional position / orientation measuring apparatus and method of the present invention, the image coordinate value of the optical information (visual code, other marker, or optical signal such as an optical beacon) detected from the imaged image of the object. , The algorithm for estimating the three-dimensional position and orientation can be switched based on the number and the combination, and more robust three-dimensional position / orientation measurement can be realized.

Furthermore, according to the three-dimensional position / orientation measuring apparatus and method of the present invention, the optimum three-dimensional position / orientation estimation algorithm is selected according to the coordinate value, number and combination of the markers on the input image. , 3D position of the target object
The posture can be suitably measured. Therefore, the object to be measured can be freely moved without being conscious of occlusion, and it can be applied to a three-dimensional user interface in a home entertainment device or the like.

[Brief description of drawings]

FIG. 1 is a diagram schematically showing a configuration of a three-dimensional position / orientation measuring system according to an embodiment of the present invention.

FIG. 2 is a three-dimensional position / orientation measuring apparatus 1 according to this embodiment.
It is the figure which showed the hardware constitutions of 03 typically.

FIG. 3 is a diagram showing a configuration example of a measurement target object 101.

FIG. 4 is a diagram illustrating an object to be measured 101 having markers 104a to 10a;
It is the figure which showed typically the operating characteristic by the side of the camera 102 and the three-dimensional position and orientation measuring device 103 when three light emitting diodes are equipped as 4c.

FIG. 5 is a diagram showing an object to be measured 1 even if three markers whose spatial positional relationships are known can be detected from the captured image.
It is the figure which showed the case where the three-dimensional position and orientation of 01 could not be calculated | required.

FIG. 6 is a diagram showing an example of a matching method.

FIG. 7 is a flowchart showing a processing procedure for estimating a three-dimensional position / orientation based on a captured image of the measurement target object 101 on which three markers 104a to 104c are arranged.

FIG. 8 is a measurement target object 1 in step S4 in FIG.
13 is a flowchart showing a processing procedure of algorithm selection for obtaining the three-dimensional position / orientation of 01.

FIG. 9 is a diagram showing another configuration example of the measurement target object 101.

FIG. 10 shows a three-dimensional position of a measurement target object 101 based on a captured image in which four markers 104a to 104d are arranged.
6 is a flowchart showing a processing procedure for estimating a posture.

11 is a flowchart showing a processing procedure of algorithm selection for obtaining the three-dimensional position / orientation of the measurement target object 101 in step S24 in FIG.

FIG. 12 is a diagram showing a configuration example of a measurement target object 101 in which the number of markers is increased in consideration of occlusion.

FIG. 13 shows markers 104a to 104h at each vertex of the cube.
Based on the captured image of the measurement target object 101 in which
6 is a flowchart showing a processing procedure for estimating a dimensional position / orientation.

14 is a flowchart showing a processing procedure of algorithm selection for obtaining the three-dimensional position / orientation of the measurement target object 101 in step S44 in FIG.

FIG. 15 is a diagram for explaining a method of selecting an optimal combination for position / orientation measurement.

FIG. 16 is a diagram for explaining a method of selecting an optimal combination for position / orientation measurement.

[Explanation of symbols]

1 ... CPU 2 ... Main memory, 3 ... ROM 4 ... Display controller 5: Input device interface 6 ... Network interface 7 ... External device interface 8 ... Bus, 9 ... Camera interface 11 ... Display 12 ... Keyboard, 13 ... Mouse 14 ... Hard disk drive 15 ... Media drive 101 ... Object to be measured 102 ... camera 103 ... Three-dimensional position / orientation measuring device 104a to 104h ... Markers

   ─────────────────────────────────────────────────── ─── Continued front page    F term (reference) 2F065 AA04 AA37 BB05 BB29 FF04                       JJ03 JJ26 QQ31                 5B057 AA20 BA02 CA12 CB13 CD14                       CH01 CH14 CH16 DA07 DA16

Claims (22)

[Claims] 1. A three-dimensional position / orientation measuring apparatus for estimating a spatial position and orientation of an object in a physical space, wherein a plurality of optical identifications whose mutual positional relations are known on an object to be measured. Information is arranged, an image input unit that captures a scene in a real space including an object to be measured, an identification information extraction unit that extracts optical identification information from an image input by the image input unit, and the identification A position / orientation calculation method selection unit that selects a method for calculating the spatial position and orientation of the measurement target object according to the state of the optical identification information extracted by the information extraction unit, and the position / orientation calculation method selection A position / orientation calculation unit that calculates the spatial position and orientation of the object to be measured using the optical identification information extracted by the identification information extraction unit according to the method selected by the unit. That the three-dimensional position and orientation measurement device. 2. The three-dimensional position / orientation according to claim 1, wherein three or more pieces of optical identification information whose positional relationship is known are arranged on the object to be measured. Measuring device. 3. An object to be measured is provided with four or more pieces of optical identification information whose positional relationship is known, and a combination of the optical identification information which forms the four vertices of a parallelogram. The three-dimensional position / orientation measuring device according to claim 1, wherein there is at least one. 4. The three-dimensional position / orientation measuring apparatus according to claim 1, wherein the optical identification information is provided for each vertex of the measurement object having a cubic shape. 5. The position / orientation calculation method selection unit is responsive to three or more pieces of optical identification information extracted by the identification information extraction unit, and has three spatial positional relationships known. The three-dimensional position / orientation measuring apparatus according to claim 1, wherein a method for mathematically calculating the corresponding three-dimensional position and orientation is selected based on the position on the image. 6. The position / orientation calculation method selection unit is configured such that at least one side of a triangle formed by three pieces of optical identification information extracted from an input image is substantially parallel to a projection plane in the image input unit. If it is, a method other than the mathematical calculation method for obtaining the corresponding three-dimensional position and orientation based on the positions of three points on the image is selected, and the three-dimensional position according to claim 5. -Attitude measuring device. 7. The position / orientation calculation method selection unit is known in the physical space in response to the optical identification information which forms the four vertices of the parallelogram being extracted by the identification information extraction unit. 3. The three-dimensional method according to claim 1, wherein a method for mathematically calculating a corresponding three-dimensional position and orientation is selected based on the positions of four points forming the parallelogram on the image. Position / orientation measuring device. 8. When a plurality of combinations of optical identification information which form four vertices of a parallelogram are detected from an input image, the parallelogram having the highest reliability is selected and its position / orientation is selected. The three-dimensional position / orientation measuring apparatus according to claim 7, wherein 9. The three-dimensional position / orientation measuring apparatus according to claim 8, wherein the reliability is an area when mapped to two-dimensional input coordinates. 10. It is not preferable that the position / orientation calculation method selection unit mathematically calculates the spatial position and orientation of the measurement target object based on the state of the optical identification information extracted by the identification information extraction unit. If it is determined that the method for estimating the three-dimensional position and orientation of the measurement target object in the previous frame by the image input unit as an initial value is selected, the method is selected. The described three-dimensional position / orientation measuring device. 11. A three-dimensional position / orientation measuring method for estimating a spatial position and orientation of an object in a physical space, wherein a plurality of optical identifications whose positional relationships are known on an object to be measured. Information is arranged, an image input step of capturing a scene in a real space including an object to be measured, an identification information extraction step of extracting optical identification information from the input image by the image input step, and the identification A position / orientation calculation method selecting step for selecting a method for calculating the spatial position and orientation of the measurement target object according to the state of the optical identification information extracted by the information extraction step; and the position / orientation calculation method selection A position for calculating the spatial position and orientation of the measurement target object using the optical identification information extracted by the identification information extraction unit according to the method selected in step 3-dimensional position and orientation measuring method characterized by comprising an attitude calculation step. 12. Three or more pieces of optical identification information whose positional relationship is known are arranged on the object to be measured.
The three-dimensional position / orientation measuring method according to claim 11, wherein. 13. Four or more pieces of optical identification information whose positional relationships are known are arranged on the object to be measured,
2. There is at least one combination of optical identification information that forms four vertices of a parallelogram.
The three-dimensional position / orientation measuring method described in 1. 14. The three-dimensional position / orientation measuring method according to claim 11, wherein the optical identification information is provided for each vertex of the measurement target object having a cubic shape. 15. In the position / orientation calculation method selecting step, in response to the three or more pieces of optical identification information being extracted by the identification information extracting section, three spatial positional relationships are known. The three-dimensional position / orientation measuring method according to claim 11, wherein a method for mathematically calculating the corresponding three-dimensional position and orientation based on the position on the image is selected. 16. In the position / orientation calculation method selection step, at least one side of a triangle formed by three pieces of optical identification information extracted from the input image is substantially parallel to the projection plane in the image input step. 16. In the case of, the three-dimensional position according to claim 15, wherein a method other than the mathematical calculation method for obtaining the corresponding three-dimensional position and orientation based on the positions of three points on the image is selected. -Attitude measurement method. 17. The position / orientation calculation method selecting step is known in real space in response to the optical identification information forming the four vertices of the parallelogram being extracted in the identification information extracting step. 12. The three-dimensional according to claim 11, wherein a method for mathematically calculating the corresponding three-dimensional position and orientation is selected based on the positions of the four points forming the parallelogram on the image. Position / orientation measurement method. 18. When a plurality of combinations of optical identification information which form four vertices of a parallelogram are detected from an input image, the parallelogram having the highest reliability is selected and its position / orientation is selected. The three-dimensional position / orientation measuring method according to claim 17, wherein 19. The three-dimensional position / orientation measuring method according to claim 18, wherein the reliability is an area when it is mapped to a two-dimensional input image. 20. In the position / orientation calculation method selection step, it is not preferable to mathematically calculate the spatial position and orientation of the measurement target object based on the state of the optical identification information extracted in the identification information extraction step. If it is determined that the position and orientation of the measurement target object in the previous frame by the image input step are set to initial values,
The three-dimensional position / orientation measuring method according to claim 11, wherein a method for estimating a dimensional position and orientation is selected. 21. A memory in which computer software is physically stored in a computer-readable format so as to execute processing for estimating a spatial position and orientation of an object in a physical space on a computer system. As a medium, the computer software is provided with a plurality of optical identification information whose positional relationship is known on the object to be measured. An image input step of capturing, an identification information extraction step of extracting optical identification information from the input image by the image input step, and a measurement target object according to the state of the optical identification information extracted by the identification information extraction step A position / orientation calculation method selecting step for selecting a method for calculating a spatial position and orientation; According to the method selected in the selection step, a position / orientation calculation step of calculating a spatial position and orientation of the measurement target object using the optical identification information extracted in the identification information extraction step. Storage medium. 22. A computer program written to execute a process for estimating a spatial position and orientation of an object in a physical space on a computer system, wherein the objects to be measured are mutually reciprocal. A plurality of pieces of optical identification information whose positional relationship is known are provided, and an image input step of capturing a scene in a real space including an object to be measured, and an optical identification from the input image by the image input step. Identification information extraction step for extracting information, and position / orientation calculation for selecting a method for calculating the spatial position and orientation of the measurement target object according to the state of the optical identification information extracted by the identification information extraction step According to the method selection step and the method selected in the position / orientation calculation method selection step, extracted by the identification information extraction step. Computer program, characterized by comprising a position and orientation calculation step of calculating a spatial position and orientation of the measurement object by using a histological identification information.