[go: up one dir, main page]

WO2011136276A1 - 三次元物体認識用画像データベースの作成方法および作成装置 - Google Patents

三次元物体認識用画像データベースの作成方法および作成装置 Download PDF

Info

Publication number
WO2011136276A1
WO2011136276A1 PCT/JP2011/060277 JP2011060277W WO2011136276A1 WO 2011136276 A1 WO2011136276 A1 WO 2011136276A1 JP 2011060277 W JP2011060277 W JP 2011060277W WO 2011136276 A1 WO2011136276 A1 WO 2011136276A1
Authority
WO
WIPO (PCT)
Prior art keywords
subspace
query
recognition
database
image
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Ceased
Application number
PCT/JP2011/060277
Other languages
English (en)
French (fr)
Inventor
隆宏 柏木
託海 外山
浩一 黄瀬
古橋　幸人
峯　泰治
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Olympus Corp
Osaka Metropolitan University
Original Assignee
Olympus Corp
Osaka Prefecture University PUC
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Olympus Corp, Osaka Prefecture University PUC filed Critical Olympus Corp
Priority to CN201180021296.XA priority Critical patent/CN103109307B/zh
Priority to HK13111622.8A priority patent/HK1184267B/xx
Priority to US13/643,284 priority patent/US8971610B2/en
Priority to JP2012512888A priority patent/JP5818327B2/ja
Priority to EP11775057.0A priority patent/EP2565844B1/en
Publication of WO2011136276A1 publication Critical patent/WO2011136276A1/ja
Anticipated expiration legal-status Critical
Ceased legal-status Critical Current

Links

Images

Classifications

    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06V—IMAGE OR VIDEO RECOGNITION OR UNDERSTANDING
    • G06V10/00—Arrangements for image or video recognition or understanding
    • G06V10/40—Extraction of image or video features
    • G06V10/46—Descriptors for shape, contour or point-related descriptors, e.g. scale invariant feature transform [SIFT] or bags of words [BoW]; Salient regional features
    • G06V10/462—Salient features, e.g. scale invariant feature transforms [SIFT]
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F18/00—Pattern recognition
    • G06F18/20—Analysing
    • G06F18/21—Design or setup of recognition systems or techniques; Extraction of features in feature space; Blind source separation
    • G06F18/213—Feature extraction, e.g. by transforming the feature space; Summarisation; Mappings, e.g. subspace methods
    • G06F18/2135—Feature extraction, e.g. by transforming the feature space; Summarisation; Mappings, e.g. subspace methods based on approximation criteria, e.g. principal component analysis
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06V—IMAGE OR VIDEO RECOGNITION OR UNDERSTANDING
    • G06V10/00—Arrangements for image or video recognition or understanding
    • G06V10/70—Arrangements for image or video recognition or understanding using pattern recognition or machine learning
    • G06V10/77—Processing image or video features in feature spaces; using data integration or data reduction, e.g. principal component analysis [PCA] or independent component analysis [ICA] or self-organising maps [SOM]; Blind source separation
    • G06V10/7715—Feature extraction, e.g. by transforming the feature space, e.g. multi-dimensional scaling [MDS]; Mappings, e.g. subspace methods
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06V—IMAGE OR VIDEO RECOGNITION OR UNDERSTANDING
    • G06V20/00—Scenes; Scene-specific elements
    • G06V20/60—Type of objects
    • G06V20/64—Three-dimensional objects

Definitions

  • the present invention relates to a method and apparatus for creating a three-dimensional object recognition image database.
  • the local feature amount is a description of a local region feature of an image by a vector.
  • the local feature amount is usually obtained from hundreds to thousands of various points from various parts of one image. Therefore, even when only a part of the object is shown in the question image or when a part of the object is hidden, the 3D object corresponding to the part shown in the question image can be recognized. . Also, those using local feature quantities are robust to conversions such as similar transformations and rotations when the shooting conditions are different.
  • the simplest method for recognizing a three-dimensional object using local feature values is to capture various objects in advance and register the local feature values obtained from these images in a database. Then, the object is recognized by comparing each local feature obtained from the query image with the local feature registered in the database. At this time, in order to recognize a highly accurate three-dimensional object, it is necessary to be able to recognize the question image from any viewpoint. For that purpose, it is better to shoot an object from various viewpoints, acquire local feature amounts from those images, and register them in the database. However, if all the local feature values are stored as they are, a problem arises that a huge memory capacity is required.
  • Non-Patent Document 5 there is one that reduces the memory capacity by selecting the local feature values and reducing the number of local feature values registered in the database (for example, Non-Patent Document 5).
  • the recognition rate of the object may decrease.
  • the inventors have paid attention to a local area obtained to some extent consistently from a set of continuously changing images, and have newly considered using only the local feature quantity obtained from such a portion. If only such local feature amounts are registered in the database, the memory capacity should be able to be reduced without significantly reducing the accuracy of object recognition. Furthermore, in order to increase the effect of reducing the memory capacity, we considered registering local feature values obtained from the same part of the object together in the database.
  • the CLAFIC method for example, Kenichiro Ishii, Eisaku Maeda, Noriyoshi Ueda, Hiroshi Murase, “Easy-to-understand pattern recognition”, Ohmsha, August 1998, p.147-151, or E. Oja:
  • the present invention has been made in consideration of the above circumstances, and reduces the memory capacity by selecting a local feature amount to be registered in the image database for 3D object recognition, while reducing the selection capacity.
  • the present invention provides a technique that can suppress the reduction of the recognition rate that occurs as a compensation to the extent that it is comparable to the state of no reduction.
  • the present invention is a set of a plurality of sets consisting of a step of extracting local features of each image and representing each as a feature vector when a plurality of images of a three-dimensional object viewed from different viewpoints are input.
  • Subspace generation in which each set generates a set representing local features of the same part of the object viewed from a series of adjacent viewpoints, and generates a plurality of subspaces representing the characteristics of each set using the subspace method
  • the present invention is based on an extraction unit that extracts local features of each image and represents them as feature vectors when a plurality of images of a three-dimensional object viewed from different viewpoints are input, and a feature vector A plurality of sets, each set generating a set representing local features of the same part of the object viewed from a series of adjacent viewpoints, and subspaces representing the characteristics of each set A partial space generation unit generated by the method, and a registration unit that associates the identifier of the object with each partial space and registers it in a three-dimensional object recognition database, and the database is accessed by a three-dimensional object recognition device, When an image obtained by viewing a certain object from a certain viewpoint is given as a search question, the recognition device queries a plurality of feature vectors respectively representing local features of the search question.
  • An object that is extracted as a feature vector determines a partial space that is most similar to each query feature vector, performs an aggregation process for the object ID associated with each partial space for each query feature vector, and is an object that is most similar to the search query
  • An apparatus for creating a three-dimensional object recognition image database having the function of obtaining
  • a method for creating an image database for 3D object recognition includes a plurality of sets of feature vectors, each set representing a local feature in which the same part of the object is viewed from a series of adjacent viewpoints. Generating a plurality of subspaces representing the characteristics of each set by a subspace method, and a registration step of registering each of the subspaces in association with the identifier of the object in a three-dimensional object recognition database Therefore, feature vectors that represent the same part of the object are converted into approximate subspaces in response to successive viewpoint changes, and the subspaces are registered in the database instead of each feature vector.
  • the reduction of the recognition rate that occurs as a price while reducing the memory capacity is not much lower than when registering each feature vector as it is It can be suppressed.
  • the memory capacity can be reduced to about 1/18 of the unreduced state.
  • each step of database creation is executed by a computer.
  • the computer and the computer that executes the recognition process may be the same, but are different. It may be a thing.
  • the computer here may be a single computer, but also includes a mode in which a plurality of devices physically realize the function as one computer, such as so-called cloud computing.
  • a three-dimensional object is an object in which a part is visible and hidden as the viewpoint (photographing angle) changes, unlike a two-dimensional (planar) object.
  • the subspace can be generated by applying a known subspace method.
  • a characteristic aspect of the present invention is that feature vectors of the same part of the same object viewed from a series of viewpoints are combined into one by the subspace method, thereby saving the memory capacity of the database.
  • viewpoint data representing a series of viewpoints is added to a subspace as a set of feature vectors collected together.
  • a specific aspect of the viewpoint data is a shooting angle.
  • the shooting angle corresponds to the rotation angle of the turntable when a three-dimensional object is rotated once on the turntable and the object is shot from different directions.
  • the registration step registers a combination of the identifier of the object and viewpoint data representing the series of viewpoints in association with each partial space
  • the recognition process includes: It may be a step of performing aggregation processing for the combination associated with each partial space to obtain an object that is most similar to the search question and a viewpoint that is most similar.
  • the aggregation processing for the combination of the object ID and the viewpoint data is performed for each query feature vector, so that the recognition rate decrease that occurs as a price for reducing the memory capacity is smaller than when each feature vector is registered as it is. It can be suppressed to the extent that it does not fade.
  • the memory capacity can be reduced to about 1/18 of the unreduced state. . In this way, it is possible not only to recognize the type of object in the question image, but also to estimate the approximate viewpoint of the search question.
  • the subspace generation step calculates the distance between each pair of feature vectors corresponding to adjacent viewpoints, excludes the difference between different pairs exceeding a predetermined reference as noise, and leaves
  • the feature vectors may be a set of feature vectors representing the same location. In this way, a set of feature vectors representing the same location can be obtained by calculating the distance between the feature vectors of adjacent viewpoints, and noise can be excluded and stable acquisition can be performed.
  • the subspace generation step is configured to generate a subspace when the feature vector of each set covers a wider range than a predetermined viewpoint change amount, but not to generate a subspace when the change amount does not satisfy the change amount. May be.
  • the partial space generation step may exclude, as noise, a case where the difference between the pair with the closest distance and the pair with the second closest distance exceeds the reference.
  • the recognition process projects each query feature vector onto a base that defines a coordinate system of each partial space registered in advance in the database, and based on the size of the projection component, each query feature vector and each partial space, And the subspace with the highest similarity may be determined to be the subspace most similar to the query feature vector. In this way, the degree of similarity can be calculated based on the size of the component projected onto each base in each partial space.
  • the base of the first principal component related to the largest eigenvalue in the set of feature vectors in which each subspace represents a characteristic is determined for each subspace, and the normal from the origin on each base of the first principal component
  • Each point is placed at the same distance, and the distance between each point and each query feature vector is obtained by applying an approximate nearest neighbor search method. You may determine that it is a similar partial space.
  • the similarity calculation is processed as a distance calculation, and by applying the approximate nearest neighbor search method to the distance calculation, the similarity calculation is performed compared to the method of projecting to each base. Processing time can be shortened.
  • the query feature vector is projected onto each base of each candidate partial space, and the size of the projection component Based on the above, the similarity between each query feature vector and each subspace may be calculated, and the subspace with the highest similarity may be determined as the subspace most similar to the query feature vector. In this way, it is possible to expect a higher recognition rate than when only the first main component of each partial space is used.
  • the processing time can be reduced because the target (candidate) for similarity calculation is narrowed down.
  • a query related to the search question A plurality of sets of feature vectors, each set generating a set representing local features of the same part of the object viewed from a series of adjacent viewpoints, and a plurality of query parts representing the characteristics of each set A space is generated by a subspace method, and (2) the normalized distance from the origin is set at a predetermined position on each base that defines the coordinate system of each query subspace, and is registered in the database.
  • the normalized distance from the origin on each base of each subspace sets a reference point at the predetermined position, and (3) a portion having a reference point with the shortest distance from each query reference point
  • the viewpoint data may be data of a shooting angle of the object.
  • a shooting angle is used as the viewpoint data, and a partial space is generated on the condition that a vector of the same location is continuously included in the set with respect to a change amount of the shooting angle.
  • the CLAFIC method may be applied to collect the feature vectors as a set to generate a subspace.
  • the number of dimensions of the subspace may be 1 or more and 3 or less.
  • the SIFT feature quantity used in the embodiment is a 128-dimensional vector, but the number of dimensions can be reduced by converting it into a subspace.
  • the extent to which the number of dimensions can be reduced must be determined in consideration of the balance between the two.
  • a recognition rate of 98.9% is obtained for the non-reduced memory state even when the number of dimensions of the subspace is 3D in the aspect of adding the viewpoint data. Maintained. And even if the number of dimensions was increased further, the recognition rate of 98.9% or more was not obtained.
  • the recognition rate of 98.0% was maintained for the unreduced state (see FIG. 6 and Table 1). Even if the viewpoint data is not added, the recognition rate of 98.3% of the maximum value is obtained when the number of dimensions in the subspace is three dimensions, and the recognition rate of 95.8% is maintained even if the number of dimensions is reduced to one dimension. It was done.
  • the various preferable aspects shown here can also be combined.
  • 3D object recognition using local features can be broadly divided into two types: global features and local features.
  • the former uses a pixel value of an image as a feature amount for an entire image, and can be obtained relatively easily. However, if the pixel values of the database image and the question image are completely different, such as when only a part of the object is shown in the question image or part of the image is hidden, the feature value may vary greatly. This makes it difficult to recognize objects.
  • the latter local feature amount is obtained by extracting a characteristic local region from an image and describing the local region with a vector. As described above, since the local feature amount is described as a vector, it is also referred to as a feature vector. It is known that it is effective as a method for dealing with the problem of the global feature quantity because it can be obtained from hundreds to thousands of counts from various parts of one image.
  • SIFT features for example, D. Lowe: “Distinctive image features from scale-invariant keypoints", International Journal of Computer Vision, 60, 2, pp. 91- 110 (2004)
  • a basic method of three-dimensional object recognition using local features see Non-Patent Document 4
  • SIFT Scale-Invariant Feature Transform
  • FIG. 1 is an explanatory diagram showing a state where SIFT feature values, which are conventional local feature values, are extracted from image data viewed from two different viewpoints for a certain object.
  • FIGS. 1A and 1B are images of the same object taken at different shooting angles. What is represented by a white arrow in the figure is the SIFT feature.
  • FIG. 2 is an explanatory diagram showing a state in which SIFT feature values, which are conventional local feature values, are extracted from image data viewed from two different viewpoints for an object different from FIG.
  • 3D object recognition method A 3D object recognition method is briefly described. First, registration in the database is described. Assume that the user has prepared images obtained by photographing an object to be registered in the database from various viewpoints (photographing angles). As the registration process, the computer extracts SIFT feature values from each image obtained by photographing the object to be registered. The extracted SIFT feature value is registered in the database together with an identifier (object ID) unique to the object. The object ID is for identifying each object registered in the database.
  • the recognition process will be described. It is assumed that an object as a search question is photographed from a certain viewpoint and a photographed image is given.
  • the computer searches whether the same object as the given search query image is registered in the database, and if there is the same object, the object ID is specified.
  • the procedure of the recognition process is as follows. Similar to the registration process described above, SIFT feature values are extracted from the question image. The distance between each extracted SIFT feature and each SIFT feature registered in the database is calculated. Then, the SIFT feature value at the smallest distance relative to the SIFT feature value of the query image, that is, the nearest SIFT feature value is found. Vote for the object ID of the object to which the nearest SIFT feature belongs. The other SIFT feature quantities of the query image are also voted for any object ID. As a result of the voting process, the object ID that obtained the most votes is set as the recognition result for the search question.
  • CLAFIC method-classification of local features is a kind of subspace method proposed by Watanabe in 1969. This is a technique for classifying using a subspace created by a method that obtains a subspace that most closely approximates the distribution of the above. In the present invention, it is considered that local feature amounts of the same part extracted from a plurality of images at different shooting angles for a certain object are grouped into the same class using the CLAFIC method. This is clustering of local features.
  • a large number of sample vectors x are prepared for each class, and their autocorrelation matrix Q is expressed by the following equation:
  • the eigenvector is obtained by solving the eigenvalue problem of. If there are n original sample vectors x, generally n eigenvectors are obtained. Of the n eigenvectors, a space spanned by several eigenvectors is called a subspace. If the number of dimensions of the desired subspace is k, the eigenvector corresponding to the top k large eigenvalues
  • the space whose base is (coordinate system) is the subspace to be obtained.
  • the eigenvalue related to the base u i of a sample vector x corresponds to the length (projection component) when the sample vector x is orthogonally projected onto the base u i .
  • the basis u 1 is a basis corresponding to the maximum eigenvalue of the entire class, and is referred to as a first principal component in this specification.
  • Processing for finding local feature values obtained from the same part of an object from a plurality of image data whose shooting angles continuously change is as follows. First, in two pieces of image data with slightly different shooting angles, distance calculation is performed between each local feature amount of the image data of the first frame and each local feature amount of the image data of the second frame. Then, by finding the local feature amounts that are closest to each other, the local feature amounts of the first frame image and the second frame image are associated with each other. At this time, the local feature amount that is the nearest neighbor due to the influence of noise or the like may be obtained from a portion that is not really related. Therefore, if the distance from the nearest local feature is d1, the distance from the second nearest local feature is d2, and the threshold is ⁇ ,
  • FIG. 3 is an explanatory view schematically showing the state of the trace processing according to the present invention.
  • Rectangular frames such as “first frame” and “second frame” indicate images obtained by photographing an object from different viewpoints.
  • a, b, and c represent trajectories in which feature vectors representing the same part of the object appear successively in images at different shooting angles (viewpoints).
  • the feature vector set a corresponds to the feature vector ⁇ 2 belonging to the second frame from the feature vector ⁇ 1 belonging to the first frame
  • the feature vector ⁇ 2 of the second frame did not correspond to any feature vector of the third frame Represents.
  • the feature vector set b represents a state in which feature vectors continuously correspond to the viewpoints from the first frame to the fifth frame.
  • the feature vector set c represents a state in which feature vectors continuously correspond to the viewpoints from the third frame to the fifth frame.
  • the computer combines a set of local feature values obtained by the trace processing into one by creating a subspace of the set. Then, the partial space is registered together with the object ID. At this time, if a partial space is created from a set of local feature quantities with a short trajectory and registered in the database as shown in the trajectory a in FIG. . Therefore, a threshold is set for the length of the trajectory, and a partial space is created only from a set of local feature values that are continuously associated with each other to some extent and registered in the database. This is because a local feature amount with a short trajectory has a smaller imaging range that can be identified than a long trajectory.
  • the subspace created by the present invention is specifically composed of k direction vectors that define a k-dimensional base (coordinate system).
  • Each trajectory corresponds to the class described in the description of the CLAFIC method.
  • the sample vector x for each class corresponds to a local feature amount belonging to each trajectory.
  • the autocorrelation matrix of local features is obtained by the CLAFIC method, and a subspace with the eigenvector as the basis is set. It is only necessary to register k eigenvectors constituting this partial space in the database.
  • the registered eigenvector approximately represents each local feature amount belonging to the subspace.
  • the dimension number k of the subspace takes any dimension number between 1 and 128.
  • the registration process not the local feature value itself but a partial space in which a set of local feature values is combined is registered in the database together with the object ID.
  • the range of the shooting angle of the partial space such as from which viewpoint to which local feature value change is expressed, is also registered.
  • the registration process registers the partial space in association with the object ID and the range of the photographing angle.
  • recognition processing when an image of a search question is given, the computer extracts a local feature amount from the search question image, projects each local feature amount to each partial space in the database, The similarity between the local feature and the subspace is calculated. Then, the partial space having the highest similarity is obtained, and voting processing is performed on the object ID having the partial space. This is performed for all local features. Finally, the object ID that has obtained the most votes is output as the result of object recognition. At this time, since the number of subspaces differs depending on the object, the number of votes is normalized by the number of subspaces.
  • a large number of votes may be collected in an object ID having a large number of subspaces, which may cause erroneous recognition. If the number of subspaces that can identify a shooting angle ⁇ with an object is N ⁇ and the number of votes for the shooting angle ⁇ is G ⁇ ,
  • FIG. 4 is an explanatory view showing the state of the voting process according to the present invention. For example, when a partial space having the highest degree of similarity with each of five local feature values obtained from the query image is obtained, five partial spaces having an object ID and an imaging range as shown in the left of FIG. 4 are obtained. To do. At this time, according to one aspect of the present invention, if voting is simply performed for each object ID, the result is as shown in FIG. However, even if two local feature quantities correspond to partial spaces having the same object ID, they can be said to show different things if the viewpoint ranges are completely different. Therefore, in a different aspect of the present invention, voting is performed in consideration of the shooting angle of the object as shown in FIG.
  • FIG. 4 shows an example in which five partial spaces are extracted from the search question.
  • FIG. 4 shows a voting result when voting is performed only on the object ID. According to the voting result in FIG. 4A, it is impossible to determine which one should be used as the recognition result in order to obtain the same number of objects 1 and objects 2 and the largest number of votes.
  • FIG. 4B shows a voting result when voting is performed for a combination of an object ID and a shooting angle. According to the voting result shown in FIG. 4B, the object 1 can be used as the recognition result because the most obtained vote is obtained in the range of the shooting angle of 20 degrees to 40 degrees among the objects 1. Furthermore, there is also an advantage that a shooting angle of 20 to 40 degrees can be estimated as an approximate shooting angle of the question image.
  • FIG. 13 is an explanatory diagram showing the flow of processing of 3D object recognition according to the present invention.
  • the three-dimensional object recognition process is roughly divided into a registration process and a recognition process.
  • the registration process is a process of creating a database of three-dimensional object images used for recognition.
  • the recognition process is a process in which when an image of a three-dimensional object is given as a search question, the object image indicated in the image is searched from the database and the object is specified.
  • (a) shows the flow of registration processing
  • (b) shows the flow of recognition processing.
  • the registration process a plurality of images obtained by photographing the same object from different viewpoints are input.
  • the computer that performs the registration process extracts a local feature amount from each image (step S1).
  • the local feature amount of the same location continuously included in the images of different viewpoints is obtained using distance calculation, and a partial space is created in which these local feature amounts are combined into one (step S3).
  • the identifier of the object and the range of the shooting angle of the viewpoint are added to the generated partial space and registered in the database (step S5).
  • the recognition process is performed on the assumption that multiple data are registered in the database.
  • an image of a search question is given as an input.
  • the search question is an image obtained by photographing a certain object from a certain viewpoint.
  • the computer that performs the recognition process extracts a local feature amount from the search question (step S11). For each local feature extracted from the search query, the most similar partial space is searched from the database. Then, majority processing is performed on the object ID added to the searched partial space to determine one object ID (step S13). And it outputs so that an operator can recognize the object identified by the object ID (step S15).
  • the database creation device is a computer that captures each process related to registration as a device.
  • Each process is realized by common hardware mainly including the computer.
  • a program for each process is different, a function realized by the computer process is different. This corresponds to the fact that a plurality of parts having different functions are combined to realize one apparatus as a whole, and therefore the invention can be understood as an apparatus in which parts that realize the functions of the respective processes are combined.
  • the extraction unit responsible for the local feature extraction process the partial space generation part responsible for the partial space creation process, and the registration responsible for the database registration process
  • the present invention can be understood as an apparatus for creating a database including a section.
  • the recognition process the part responsible for extracting the local feature quantity from the search question, the partial space most similar to each extracted local feature quantity, are searched, and the object ID added to the partial space is majority processed.
  • it can be understood as a device having a part responsible for the function of determining one object ID and a part responsible for the function of outputting the determined object ID.
  • ⁇ Reduction of processing time In the method described above, a partial space is created using a KL expansion from a set of features obtained from the same local region over multiple frames, and multiple local features are represented together. . By doing so, the feature quantity registered in the database can be greatly reduced, and the memory capacity can be reduced.
  • ANN is used for the mutual subspace method (for details, see Maeda and Watanabe: “Pattern matching method with local structure introduced”, Science theory (D), pp. 345-352 (1985)). As a result, the recognition rate is improved and the processing speed is increased.
  • each query feature vector as a local feature is stored in each database in recognition. You must project to each base of the subspace corresponding to the class and find the similarity. Therefore, the processing time increases as the number of objects registered in the database increases.
  • a method of searching for a partial space with approximately high similarity is employed to reduce processing time.
  • each query feature vector is projected onto each base in each subspace to find the subspace with the highest similarity. This causes a problem that processing time is required. Therefore, in this embodiment, a method is proposed in which the subspace with the highest similarity is obtained by calculating the distance between the local feature obtained from the query and the point on the first principal component of the subspace. If the subspace with the highest similarity can be obtained by the distance calculation, the speed can be increased by various approximate nearest neighbor search methods that have already been proposed.
  • the method for obtaining the subspace with the highest similarity by distance calculation is as follows. First, a point equidistant from the origin is placed on the coordinate axis of each partial space in the database. Then, the distance between these points and the local feature amount obtained from the query is calculated. The shorter this distance, the longer the projection length when the local feature amount is projected onto the partial space. That is, it becomes a partial space with the highest similarity.
  • ANN reduces the number of cells for distance calculation by reducing the radius of the hypersphere by 1 / (1 + ⁇ ⁇ ⁇ ).
  • ANN is a method that approximates a nearby point to a certain point, and it cannot determine the similarity between local features and subspaces. Therefore, in order to use ANN in the subspace method, it is necessary to obtain a subspace having the highest similarity with the local feature amount by distance calculation. In this embodiment, a method for realizing this will be described.
  • a one-dimensional subspace based only on the eigenvector having the largest eigenvalue that is, the set of original local features that created the subspace is expressed sufficiently with only the first principal component. Need to be.
  • a set of local feature values that continuously change is obtained by the trace processing, and a subspace is created from the set. For this reason, there are almost no outliers, and they can be expressed approximately well in a one-dimensional subspace.
  • the similarity between the local feature and the subspace is inversely proportional to the distance between the local feature and the base of the subspace. That is, the partial space with the highest similarity can be obtained by obtaining the partial space closest to the local feature amount.
  • the distance between the local feature quantity and the base of the subspace is generally obtained as the length of the perpendicular drawn from the local feature quantity to the base of each subspace.
  • the distance calculation process using only the first principal component of the subspace reduces the processing time required for recognition compared to the method of calculating the similarity to the k-dimensional subspace. can do.
  • a higher recognition rate can be expected by using a plurality of subspace axes. Therefore, as another embodiment, a mode in which recognition is performed by employing a two-stage process can be cited.
  • as a first step only the first principal component of the subspace is used, and candidates that will become the subspace with the highest similarity are narrowed down by the approximate nearest neighbor search at high speed.
  • the second stage projection is performed in a high dimension using a plurality of axes of each of the partial spaces listed as candidates, and the partial space having the truly highest similarity is obtained.
  • the processing time is reduced because the target (candidate) for similarity calculation is narrowed down can do.
  • ANN Use of ANN in Mutual Subspace Method
  • This embodiment is effective when a moving image or a plurality of images taken continuously is used as a search question.
  • the tracing process is also performed on a plurality of images related to the search question.
  • a subspace is created from a set of local features obtained by the trace processing. By doing so, the partial space of the database can be compared with the partial space obtained from the query image.
  • the subspace obtained from the search query is referred to as a query subspace in this specification.
  • the canonical angles are generally used. However, this method cannot be accelerated. Therefore, an optimum subspace is also obtained here by distance calculation.
  • a point equidistant from the origin is placed on the axis of each subspace, and the distance between the points is calculated. It should be noted that since the query is also a subspace in this embodiment, a point must also be placed on the coordinate axis of the query subspace. A more detailed description will be given below.
  • the mutual subspace method is used when a moving image or an image of a plurality of viewpoints can be used as a search question.
  • a query subspace is also created from a set of local feature values obtained from the search question, and the search question is recognized by comparing the query subspace with the subspace in the database. Since the partial space has less fluctuation than the local feature amount, a high recognition rate can be expected by using it as a search question.
  • the similarity between the query subspace created from the search question and the subspace in the database can be obtained by calculating the canonical angle formed by both.
  • the processing time required to calculate the canonical angle is enormous.
  • a point Si ⁇ having a distance of 1 from the origin is arranged on each base of each partial space registered in the database.
  • An appropriate point Q is also placed on the base of the query subspace obtained from the search question.
  • a subspace having a point Si on the base that minimizes the distance from the point Q is a subspace to be obtained.
  • the point Si ⁇ having the minimum distance from the point Q can be approximately obtained by using ANN.
  • Example 1 A comparison experiment was performed between the basic conventional method of object recognition using local feature amounts and the method of the present invention that expresses a plurality of local feature amounts in a subspace.
  • the comparison index is the memory capacity and the recognition rate.
  • FIG. 5 is an explanatory diagram showing some examples of objects used in the experiment according to the present invention.
  • photographed moving image was acquired, and the image for registration and the search question image which are registered into a database were produced from the frame image.
  • registration images 360 images were created by changing the shooting angle for each object by about 1 degree.
  • 10 images were created as the question images were changed about every 36 degrees for each object.
  • the registration image and the question image are different images. That is, there is no registration image that is completely identical to the search question image.
  • the value of the threshold value ⁇ (refer to the above formula 5) for determining whether or not the local feature amount is obtained from the same part of the object when performing the trace processing is set to 0.6. .
  • a partial space consisting of a set of each local feature amount was obtained, and an object ID and a corresponding range of shooting angles were added to the obtained partial space and registered in the database.
  • the number of subspaces obtained from one object was about 100 to 400 each.
  • FIG. 6 is a graph showing a first experimental result according to the present invention.
  • the horizontal axis represents the number of dimensions of the used subspace, and the vertical axis represents the recognition rate. From the experimental results, even in the case of voting for each object ID, a recognition rate exceeding 95% was obtained, and it was 98.3% when the number of dimensions of the subspace was three-dimensional.
  • false votes were dispersed, and the recognition rate was further improved regardless of the dimensions of the subspace.
  • FIG. 7 is an explanatory diagram showing the object A used as a search question in the experiment of the present invention.
  • FIG. 8 is a graph showing the result of voting only on the object ID for the object A in FIG.
  • FIG. 9 is an explanatory diagram showing an example in which the object A in FIG. 7 is correctly recognized by voting on the combination of the object ID and the shooting angle.
  • the question image in FIG. 7 is obtained by photographing the object A at a certain photographing angle.
  • FIG. 8 shows scores obtained by voting on each object ID and normalizing the number of votes obtained. Originally, the score of object A should be the highest, but the scores of other objects B and C were higher. Therefore, when voting is performed for each object, the question image is recognized as the object C.
  • FIG. 9 shows the score at each shooting angle of object A, object B, and object C when voting for a combination of the object ID and the shooting angle.
  • object C which had the highest score when voting only on the object ID, the number of votes was dispersed by voting on the combination of the object ID and the shooting angle, resulting in a low score.
  • object A votes gathered at a certain range of shooting angles. Therefore, what was recognized as the object C when voting only on the object ID was correctly recognized as the object A by voting on a combination of the object ID and the shooting angle.
  • FIG. 10 is an explanatory diagram showing 68 degree and 69 degree images of the object A used in the experiment of the present invention.
  • (a) is an image of 68 degrees and
  • (b) is an image of 69 degrees.
  • FIG. 11 is an explanatory diagram showing the object D used in the experiment of the present invention.
  • FIG. 12 shows scores of shooting angles of the object D and the object E when the object D shown in FIG. 11 is used as a question image.
  • the number of votes is distributed to some extent like the score of the object E, if the score is high, it will be erroneously recognized.
  • Table 1 shows the recognition rate and memory capacity when using a one-dimensional subspace with the smallest memory capacity (see (1) of the database in Table 1), and the three-dimensional with the highest recognition rate. The recognition rate and the memory capacity (see (2) of the database in Table 1) when using the subspace are respectively shown.
  • the memory capacity when a three-dimensional subspace is used in the present invention can be reduced to about 1/18 of the memory capacity of the database (3) which is not reduced.
  • the recognition that the subspace was created and used was reduced slightly from the unreduced state while reducing the memory capacity to about 1/7. The rate could be recovered.
  • the memory capacity when using a one-dimensional subspace and the database (5) the memory capacity slightly increased compared to (5), but a higher recognition rate was obtained.
  • the reason why the recognition rate improved compared to (5) is as follows.
  • the local feature amount at the center of the trace is merely a representative vector of a plurality of local feature amounts associated by the trace process, and does not represent all the local feature amounts of the set.
  • the subspace used in the present invention well represents the characteristics of any local feature included in the set.
  • the database includes a set A of local feature amounts whose trace range of the object F is 20 degrees to 60 degrees and a set B of local feature amounts 40 degrees to 80 degrees.
  • the question image is obtained by photographing the direction of the object F at 40 degrees.
  • the set A is associated with the object F because the local feature amount of 40 degrees is the representative vector, but the set B has the local feature amount of 60 degrees as the representative vector and the object F It becomes difficult to associate correctly. For this reason, erroneous voting often occurs, and it is easy to be erroneously recognized.
  • subspace including a direction of 40 degrees is created for both of the sets A and B, so that they can be correctly associated.
  • subspace is a technique for classifying so that the characteristics of members of the class are well represented. For this reason, it is considered that the method of the present invention using the subspace method has reduced false voting and improved the recognition rate.
  • the representative vector is only one local feature, and the local feature represents a “point”.
  • the range of the shooting angle represents a “section”
  • the obtained subspace represents a “section”. Therefore, no deviation occurs.
  • the cause of what was correctly recognized when voting for each object was misrecognized by voting for each shooting angle of the object can be considered as follows. Since there are many false votes, votes may be dispersed by voting for each shooting angle even if it is a correct object, or conversely, some votes may overlap the shooting angle of an object that is incorrect. Has increased. In addition, by normalizing the number of votes obtained, the score of the shooting angle of the correct object may be lowered. For example, it is assumed that there is a set of local feature amounts of 20 to 60 degrees, a set of local feature amounts of 60 to 100 degrees, and a set of local feature amounts of 60 to 110 degrees of the object G.
  • a local space that continuously changes can be registered in a database by creating a partial space that can express the change approximately well.
  • the memory capacity was reduced.
  • the memory capacity could be reduced to 1/18 of the unreduced state.
  • voting for each object shooting angle it was possible not only to recognize the type of object in the question image, but also to estimate the approximate direction of the object.
  • Example 2 For the recognition experiment of 1002 objects, we conducted experiments for the purpose of (1) the effectiveness of using ANN and (2) the improvement of the recognition rate by the mutual subspace method. In the first experiment, an object was recognized by comparing a local feature amount and a subspace. In the second experiment, the object was recognized using the mutual subspace method. 2-1. Experiment preparation The database used in this experiment example will be described. In the experimental example, for each of 1002 three-dimensional objects, each object was rotated once on the turntable, and moving images were taken from the front, elevation angles of 15 degrees above and 30 degrees above.
  • FIG. 14 is an explanatory diagram illustrating an example of an object registered in the database. A frame image was obtained from the captured video and used as a database image.
  • SIFT features were extracted from these images, trace processing was performed, and subspaces were created.
  • the set of local feature values for creating the subspace is a set of local feature values corresponding to 50 frames or more continuously by the trace processing.
  • the created subspace was registered in the database along with the object ID.
  • the number of subspaces is about 550 per object.
  • the search question used in this experimental example will be described. Of the 1002 objects used in the database, 100 were selected at random, and the video was shot with the selected objects in hand. A frame image was obtained from the captured moving image and used as a search question image.
  • FIG. 15 is an explanatory diagram illustrating an example of an object photographed for a search question. SIFT features were also extracted from search query images. 2-2.
  • a, b, c feature vector set ⁇ 1, ⁇ 2: feature vector

Landscapes

  • Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • Computer Vision & Pattern Recognition (AREA)
  • General Physics & Mathematics (AREA)
  • Physics & Mathematics (AREA)
  • Multimedia (AREA)
  • Artificial Intelligence (AREA)
  • Evolutionary Computation (AREA)
  • Databases & Information Systems (AREA)
  • Software Systems (AREA)
  • Medical Informatics (AREA)
  • General Health & Medical Sciences (AREA)
  • Computing Systems (AREA)
  • Health & Medical Sciences (AREA)
  • Data Mining & Analysis (AREA)
  • Life Sciences & Earth Sciences (AREA)
  • Bioinformatics & Cheminformatics (AREA)
  • Bioinformatics & Computational Biology (AREA)
  • Evolutionary Biology (AREA)
  • General Engineering & Computer Science (AREA)
  • Image Analysis (AREA)
  • Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
  • Processing Or Creating Images (AREA)

Abstract

　三次元物体認識用画像データベースに登録する局所特徴量の取捨選択を行 ってメモリ容量を削減しつつ、認識率の低下を抑制する。　三次元の物体を異なる視点から見た複数の画像が入力され、各画像の局所的特徴を抽出し特徴ベクトルとしてそれぞれ表す工程と、特徴ベクトルからなる複数の集合であって、各集合が、隣り合う一連の視点から前記物体の同一箇所を見た局所的特徴を表す集合を生成し、それぞれの集合の特性を表す複数の部分空間を生成する工程と、各部分空間に前記物体のＩＤを付加しデータベースに登録する工程と、ある物体をある視点から見た画像が検索質問として与えられたとき、その検索質問の局所的特徴を表す複数の特徴ベクトルを抽出し、各特徴ベクトルに最も類似する部分空間をそれぞれ決定し、各部分空間に付加された物体ID について集計処理を行い、前記検索質問に最も類似する物体を得る工程からなる三次元物体認識用画像データベースの作成方法。

Description

三次元物体認識用画像データベースの作成方法および作成装置
　この発明は、三次元物体認識用画像データベースの作成方法および作成装置に関する。
　近年、デジタルカメラやカメラ付き携帯電話の普及および高性能化により、画像データを手軽に生成し活用できるようになった。それに伴い、画像データを用いた研究が盛んに行われている。その一つとして、画像データ中に表された三次元物体を認識する研究がある。
　コンピュータ処理によって三次元物体を認識する手法として、物体の幾何形状を用いて認識する手法がある（例えば、非特許文献１、２参照）。また、物体を撮影した平面画像を利用して認識する手法がある（例えば、非特許文献３、４参照）。この発明では、前述の手法のうち、後者、即ち、平面画像を利用して三次元物体を認識する手法に焦点を当てる。
　その手法の一つに、局所特徴量を用いるものがある。局所特徴量とは、画像の局所的な領域の特徴をベクトルで記述したものである。局所特徴量は、通常、1枚の画像の様々な個所から計数百個から数千個ほど得られる。そのため、質問画像に物体の一部しか写っていないような場合や物体の一部が隠れている場合なども、質問画像に写っている部分を手がかりに対応する三次元物体を認識することができる。また、局所特徴量を用いるものは、撮影条件が異なる場合や相似変換や回転などの変換にも頑健である。
　局所特徴量を用いて三次元物体を認識する最も単純な手法は、予め様々な物体を撮影しておき、それらの画像から得られる局所特徴量をデータベースに登録しておくものである。そして、質問画像から得た各局所特徴量とデータベースに登録した局所特徴量とを比較することによって物体の認識を行う。このとき、高精度な三次元物体の認識を行うためには、質問画像がどのような視点から撮影されたものであっても認識できるようにする必要がある。そのためには、物体を様々な視点から撮影し、それらの画像から局所特徴量を取得して、データベースに登録しておくほうがよい。しかし、それら局所特徴量のすべてをそのまま保存しようとすれば膨大なメモリ容量が必要になるという問題が生じる。
　この問題を解決する手法として、これまでにも多くの手法が提案されてきた。その一つとして、局所特徴量の取捨選択を行いデータベースに登録する局所特徴量の数を減らすことで、メモリ容量を削減するものがある（例えば、非特許文献５）。
P. J. Besl and R. C. Jain: "Three-Dimensional Object Recognition", ACM Computing Surveys, 17, 1, pp. 75-145 (1985). F. Rothganger, S. Lazebnik, C. Schmid and J. Ponce: "3D Object Modeling and Recogniton Using Local Affine-Invariant Image Descriptores and Multi-View Spatial Constraints", International Journal of Computer Vision, 66, 3 (2006). 村瀬、S. K. Nayar："2次元照合による三次元物体認識　－パラメトリック固有空間法－"、信学論(D-II)、vol.J77-D-II, no.11, pp. 2179-2187 (1994). 井上、三宅、黄瀬："三次元物体認識に用いる局所特徴量の取捨選択によるメモリ使用量削減手法の実験的検討"、電子情報通信学会論文誌D, J92-D, 9, pp. 1686-1689 (2009) 本道、黄瀬："特定物体認識のためのデータベース容量削減法の検討～局所特徴量の量子化と取捨選択～"、電子情報通信学会技術研究報告 (2009)
　しかし、局所特徴量の格納に要するメモリ容量を節約しようとして無作為に局所特徴量の取捨選択を行うと、物体の認識率が低下する可能性がある。認識率を低下させることなく効率良くメモリ容量を削減するためには、認識に有用な局所特徴量のみを保存する必要がある。
　そこで発明者らは、連続して変化する画像の集合から、ある程度一貫して得られる局所領域に注目し、そのような部分から得られる局所特徴量のみを用いることを新たに考えた。そのような局所特徴量のみをデータベースに登録すれば、物体認識の精度をあまり低下させずにメモリ容量を削減することができるはずである。さらに、メモリ容量の削減効果を高めるため、物体の同じ部分から得られる局所特徴量を一つにまとめてデータベースに登録することを考えた。具体的には、CLAFIC法（例えば、石井健一郎、前田英作、上田修功、村瀬洋著、「わかりやすいパターン認識」、オーム社、1998年8月、p.147-151、あるいは、E. Oja: "Subspace methods of pattern recognition", Research Studies Press (1983)を参照。また、下の実施の形態でも説明を述べている。）として知られる技術を適用してそれらの局所特徴量の集合ごとに部分空間を作成する。それによって複数の局所特徴量を一つにまとめて表現することができる。
　この発明は、以上のような事情を考慮してなされたものであって、三次元物体認識用画像データベースに登録する局所特徴量の取捨選択を行ってメモリ容量を削減しつつ、前記取捨選択の代償として生じる認識率の低下を無削減の状態と遜色ない程度に抑制できる手法を提供するものである。
　この発明は、三次元の物体を異なる視点から見た複数の画像が入力されたとき、各画像の局所的特徴を抽出し特徴ベクトルとしてそれぞれ表す工程と、特徴ベクトルからなる複数の集合であって、各集合が、隣り合う一連の視点から前記物体の同一箇所を見た局所的特徴を表す集合を生成し、それぞれの集合の特性を表す複数の部分空間を部分空間法により生成する部分空間生成工程と、各部分空間に前記物体の識別子を関連づけて三次元物体認識用データベースに登録する登録工程とを備え、前記データベースは、三次元物体の認識処理のため、コンピュータによりアクセスされ、前記認識処理は、ある物体をある視点から見た画像が検索質問、即ち、クエリとして与えられたとき、その検索質問の局所的特徴をそれぞれ表す複数の特徴ベクトルをクエリ特徴ベクトルとして抽出し、各クエリ特徴ベクトルに最も類似する部分空間をそれぞれ決定し、各部分空間に関連づけられた物体IDについて集計処理を行い、前記検索質問に最も類似する物体を得る工程により実現される三次元物体認識用画像データベースの作成方法を提供する。
　また、異なる観点から、この発明は、三次元の物体を異なる視点から見た複数の画像が入力されたとき、各画像の局所的特徴を抽出し特徴ベクトルとしてそれぞれ表す抽出部と、特徴ベクトルからなる複数の集合であって、各集合が、隣り合う一連の視点から前記物体の同一箇所を見た局所的特徴を表す集合を生成し、それぞれの集合の特性を表す複数の部分空間を部分空間法により生成する部分空間生成部と、各部分空間に前記物体の識別子を関連づけて三次元物体認識用データベースに登録する登録部とを備え、前記データベースは、三次元物体の認識装置によりアクセスされ、前記認識装置は、ある物体をある視点から見た画像が検索質問として与えられたとき、その検索質問の局所的特徴をそれぞれ表す複数の特徴ベクトルをクエリ特徴ベクトルとして抽出し、各クエリ特徴ベクトルに最も類似する部分空間をそれぞれ決定し、各部分空間に関連づけられた物体IDについての集計処理を各クエリ特徴ベクトルについて行い、前記検索質問に最も類似する物体を得る機能を有する三次元物体認識用画像データベースの作成装置を提供する。
　この発明による三次元物体認識用画像データベースの作成方法は、特徴ベクトルからなる複数の集合であって、各集合が、隣り合う一連の視点から前記物体の同一箇所を見た局所的特徴を表す集合を生成し、それぞれの集合の特性を表す複数の部分空間を部分空間法により生成する部分空間生成工程と、各部分空間に前記物体の識別子を関連づけて三次元物体認識用データベースに登録する登録工程とを備えるので、連続した視点の変化に対して前記物体の同一箇所を表す特徴ベクトルを一つにまとめて近似的な部分空間に変換し、各特徴ベクトルに代えて前記部分空間をデータベースに登録することでメモリ容量を削減しつつその代償として生じる認識率の低下を、各特徴ベクトルをそのまま登録するときと比べてあまり低下しない程度に抑制できる。
　効果検証の実験によれば、各特徴ベクトルをそのまま登録する無削減状態に対して98.3％の認識率を維持する一方、メモリ容量は無削減状態の約1/18にすることができた。
　前記方法と実質的に対応する、この発明の三次元物体認識用画像データベースの作成装置についても、同様の作用効果を奏する。
　なお、この発明の三次元物体認識用画像データベースの作成方法において、データベース作成の各工程はコンピュータにより実行されるが、そのコンピュータと認識処理を実行するコンピュータとは同一であってもよいが、異なるものであってもよい。ここでいうコンピュータは、単一のものであってもよいが、いわゆるクラウドコンピューティングのように物理的に複数の装置が一つのコンピュータとしての機能を実現する態様も含む。
　三次元物体は、二次元（平面）的な物体と異なり、視点（撮影角度）の変化に伴ってある部分が見え隠れする物体である。部分空間は周知の部分空間法を適用して生成可能である。この発明の特徴的な一側面は、一連の視点から見た同一物体の同一箇所の特徴ベクトルを部分空間法により一つにまとめ、データベースのメモリ容量を節約する点にある。
　他の特徴的な一側面は、一つにまとめられた特徴ベクトルの集合としての部分空間に一連の視点を表す視点データを付加する点にある。視点データの具体的な一態様は、撮影角度である。後述する実施形態において、撮影角度は、三次元物体をターンテーブルで一回転させて異なる方向からその物体を撮影したときのターンテーブルの回転角度に相当する。
従来の局所特徴量であるSIFT特徴量を、ある物体を異なる二つの視点から見た画像からそれぞれ抽出した様子を示す説明図である。 従来の局所特徴量であるSIFT特徴量を、図１と異なる物体を異なる視点から見た画像からそれぞれ抽出した様子を示す説明図である。 この発明に係るトレース処理の様子を模式的に表す説明図である。 この発明に係る投票処理の様子を示す説明図である。 この発明に係る実験例１に使用した物体のいくつかの例を示す説明図である。 この発明において操作角度を考慮した投票処理が認識率にどの程度影響するかを示すグラフである。 この発明の実験例１に検索質問として用いた物体Aを示す説明図である。 図７の物体Aに対して物体IDのみに投票を行った結果を示すグラフである。 図７の物体Aに対して物体IDと撮影角度との組み合わせに投票を行った結果を示す説明図である。 この発明の実験例１に用いた物体Aの撮影角度68度と69度の画像を示す説明図である。 この発明に係る実験例１に用いた物体Dを示す説明図である。 図１１に示す物体Dを質問画像としたときの、物体Dと物体Eの各撮影角度に対するスコアを表したものである。 この発明に係る三次元物体認識の処理の流れを示す説明図である。 この発明に係る実験例２で、データベースに登録した物体の一例を示す説明図である。 この発明に係る実験例２で、検索質問用に撮影した物体の一例を示す説明図である。
　以下、この発明の好ましい態様について説明する。
　この発明による三次元物体認識用画像データベースの作成方法において、前記登録工程は、前記物体の識別子および前記一連の視点を表す視点データの組み合わせを各部分空間に関連づけて登録し、前記認識処理は、各部分空間に関連づけられた前記組み合わせについて集計処理を行い、前記検索質問に最も類似する物体および最も類似する視点を得る工程であってもよい。
　このようにすれば、物体IDおよび視点データの組み合わせについての集計処理を各クエリ特徴ベクトルについて行うので、メモリ容量削減の代償として生じる認識率の低下を、各特徴ベクトルをそのまま登録するときと比べて遜色のない程度に抑制できる。
　後述する効果検証の実験によれば、各特徴ベクトルをそのまま登録する無削減状態に対して98.9％の認識率を維持する一方、メモリ容量は無削減状態の約1/18にすることができた。
　また、このようにすれば、質問画像の物体の種類を認識するだけでなく、検索質問のおおよその視点を推定することができる。
　また、前記部分空間生成工程は、隣り合う視点に対応する各対の特徴ベクトルの距離を計算し、異なる対との距離が予め定められた基準を超えて相違するものをノイズとして除外し、残った特徴ベクトルを同一箇所を表す特徴ベクトルの集合としてもよい。このようにすれば、隣り合う視点の各特徴ベクトルの距離計算を行うことにより同一箇所を表す特徴ベクトルの集合を得ることができ、かつ、ノイズを除外し安定した取得が可能になる。
　前記部分空間生成工程は、各集合の特徴ベクトルが予め定められた視点の変化量より広範囲に渡る場合は部分空間を生成するが、前記変化量に満たない場合は部分空間を生成しないように構成してもよい。このようにすれば、広範な視点変化に渡って同一箇所を表す特徴ベクトルがデータベースに登録されるので、撮影角度の変化によって生じたノイズは登録対象から除去され、安定した精度の高い認識が可能になる。
　前記部分空間生成工程は、各対のうち、最も近い距離の対と２番目に近い距離の対との相違が前記基準を超えるものをノイズとして除外してもよい。
　さらにまた、前記認識処理は、各クエリ特徴ベクトルを前記データベースに予め登録された各部分空間の座標系を定める基底にそれぞれ射影して射影成分の大きさに基づき各クエリ特徴ベクトルと各部分空間との類似度を算出し、最も高い類似度の部分空間を、そのクエリ特徴ベクトルに最も類似する部分空間であると決定してもよい。このようにすれば、各部分空間の各基底への射影成分の大きさに基づいて、類似度を算出することができる。
　前記認識処理は、各部分空間が特性を表す特徴ベクトルの集合において最大の固有値に係る第一主成分の基底を各部分空間についてそれぞれ決定し、第一主成分の各基底上において原点からの正規化された距離が等しい位置にそれぞれ点をおき、各点と各クエリ特徴ベクトルとの距離を近似最近傍探索の手法を適用して求め、最も近い距離の部分空間を、そのクエリ特徴ベクトルに最も類似する部分空間であると決定してもよい。このようにすれば、類似度の計算を距離計算として処理し、その距離計算に近似最近傍探索の手法を適用することによって、各基底への射影を行う手法に比べて類似度の計算にかかる処理時間を短縮することができる。
　さらに、前述の方法により各クエリ特徴ベクトルに類似する部分空間を幾つかの候補に絞り込んだ後、候補とされた各部分空間の各基底にそのクエリ特徴ベクトルをそれぞれ射影して射影成分の大きさに基づき各クエリ特徴ベクトルと各部分空間との類似度を算出し、最も高い類似度の部分空間を、そのクエリ特徴ベクトルに最も類似する部分空間であると決定してもよい。
　このようにすれば、各部分空間の第一主成分のみを用いる場合に比べて高い認識率を見込むことができる。一方、各部分空間の各基底に各特徴ベクトルを射影して類似度を求める場合に比べて、類似度計算の対象（候補）を絞り込むので、処理時間を削減することができる。
　前記認識処理は、各クエリ特徴ベクトルに最も類似する部分空間を決定する処理に代えて、（１）一連の視点から見た複数の画像が検索質問として与えられたとき、その検索質問に係るクエリ特徴ベクトルからなる複数の集合であって、各集合が、隣り合う一連の視点から前記物体の同一箇所を見た局所的特徴を表す集合を生成し、それぞれの集合の特性を表す複数のクエリ部分空間を部分空間法により生成し、（２）各クエリ部分空間の座標系を定める各基底上において原点からの正規化された距離が所定の位置にそれぞれクエリ基準点をおき、前記データベースに登録された各部分空間の各基底上において原点からの正規化された距離が前記所定の位置にそれぞれ基準点をおき、（３）各クエリ基準点から最短距離の基準点を有する部分空間を各近似最近傍探索の手法を適用して決定することにより、各クエリ部分空間に最も類似する部分空間を決定してもよい。
　このようにすれば、近似最近傍探索の手法を適用した距離計算によって各クエリ部分空間に最も類似する部分空間を決定することができるので、近似最近傍探索の手法を用いない場合に比べて処理時間を短縮でき、かつ、各クエリ特徴ベクトルに対して最も類似する部分空間を決定する場合に比べて、クエリ部分空間との比較を行うので高い認識率を見込むことができる。
　前記視点データは、前記物体の撮影角度のデータであってもよい。このようにすれば、前記視点データとして撮影角度を用い、かつ、撮影角度の変化量に対して連続して同一箇所のベクトルが集合に含まれることをノイズ除去の条件として部分空間を生成することができる。
　前記部分空間生成工程は、CLAFIC法を適用して特徴ベクトルを集合としてまとめ、部分空間を生成してもよい。
　部分空間の次元数は、１以上３以下であってもよい。実施例で用いたSIFT特徴量は128次元のベクトルであるが、部分空間に変換することによってその次元数を減らすことができる。しかし、認識率低下とのトレードオフが生じると予想されるため、どこまで次元数が減らせるかは、両者のバランスを考慮して決定しなければならない。ところが、後述する検証実験によれば、発明者にとっても意外なことに、視点データを付加する態様において部分空間の次元数が三次元のときもメモリ無削減状態に対して98.9％の認識率が維持された。そして、次元数をそれ以上増やしても98.9％以上の認識率を得ることはなかった。また、究極の一次元まで次元数を減らしても、無削減状態に対して98.0％の認識率が維持されたのである（図６および表１参照）。視点データを付加しない態様であっても、部分空間の次元数が三次元のときに極大値の98.3％の認識率が得られ、一次元まで次元数を減らしても95.8％の認識率が維持された。
　ここで示した種々の好ましい態様は、それら複数を組み合わせることもできる。
　以下、図面を用いてこの発明をさらに詳述する。なお、以下の説明は、すべての点で例示であって、この発明を限定するものと解されるべきではない。
　≪関連技術の説明≫
　発明をよりよく理解できるようにするため、まず、この発明の基礎となる技術について簡単に説明する。
１．局所特徴量を用いた三次元物体認識
　画像から得ることができる特徴量には、大きく分けて大域特徴量と局所特徴量の2つがある。前者は、画像の画素値などを用いて1枚の画像全体を特徴量とするもので、比較的容易に得ることができる。しかし、質問画像に物体の一部しか写っていない場合や一部が隠れている場合など、データベースの画像と質問画像の画素値が全く異なると、特徴量の値も大きく変動するという問題が生じ、物体の認識が困難になる。一方、後者の局所特徴量は画像から特徴的な局所領域を取り出し、その局所領域をベクトルで記述したものである。このように局所特徴量はベクトルとして記述されるので、特徴ベクトルともいう。1枚の画像の様々な個所から計数百個から数千個ほど得られるため、大域特徴量がもつ問題に対処する方法として、有効であることが知られている。
　ここでは、局所特徴量の代表的なものの一つであるSIFT特徴量（例えば、D. Lowe: "Distinctive image features from scale-invariant keypoints", International Journal of Computer Vision, 60, 2, pp. 91-110 (2004)参照）と、局所特徴量を用いた三次元物体認識の基本的な手法（前記非特許文献４参照）について簡単に説明する。
１－１．SIFT（Scale-Invariant Feature Transform）特徴量
　Loweらによって提案されたSIFT特徴量は、画像内の輝度の勾配を利用することで局所領域を取得し、その座標、方向、大きさなどを特徴ベクトルで表したものである。SIFT特徴量は、128次元のベクトルで表され、相似変換や回転などの変換に対して頑健である。
　図１は、従来の局所特徴量であるSIFT特徴量をある物体について異なる二つの視点から見た画像データからそれぞれ抽出した様子を示す説明図である。図１（ａ）と（ｂ）は、同一の物体を異なる撮影角度で撮影したものである。図中に白い矢印で表したものが、SIFT特徴量である。図２は、従来の局所特徴量であるSIFT特徴量を図１と異なる物体について異なる二つの視点から見た画像データからそれぞれ抽出した様子を示す説明図である。
１－２．三次元物体の認識手法
　三次元物体の物体認識手法について簡単に説明する。まず、データベースへの登録について述べる。データベースに登録したい物体を様々な視点（撮影角度）から撮影した画像がユーザーによって用意されているとする。登録処理として、コンピュータは、登録すべき物体が撮影された各画像からSIFT特徴量を抽出する。抽出されたSIFT特徴量を、前記物体に固有の識別子（物体ID）とともにデータベースに登録する。物体IDは、データベースに登録された各物体を識別するためのものである。
　次に、認識処理について説明する。検索質問としての物体がある視点から撮影され、撮影された画像が与えられたとする。認識処理は、与えられた検索質問画像と同一の物体が前記データベースに登録されているかをコンピュータが検索し、同一物体があればその物体IDを特定するものである。認識処理の手順は次のとおりである。前述の登録処理と同様に、質問画像からもSIFT特徴量を抽出する。抽出された各SIFT特徴量とデータベースに登録された各SIFT特徴量との距離計算を行う。そして、質問画像のSIFT特徴量に対して最も小さい距離にあるSIFT特徴量、即ち、最近傍のSIFT特徴量を見出す。最近傍のSIFT特徴量が属する物体の物体IDに対して投票を行う。質問画像の他のSIFT特徴量についてもいずれかの物体IDに対しそれぞれ投票を行う。投票処理の結果、最多得票を得た物体IDをその検索質問に対する認識結果とする。
２．CLAFIC法－局所特徴量の分類
　CLAFIC法(CLAss-Featuring Information Compression)は、1969年にWatanabeが提案した部分空間法の一種であり、クラスごとにKL展開（Karhunen-Loeve展開の略であり、ベクトルの分布を最もよく近似する部分空間を求める手法）により作成した部分空間を用いてクラス分類を行う手法である。この発明では、ある物体について異なる撮影角度の複数の画像から抽出される同一部分の局所特徴量を、CLAFIC法を用いて同一クラスにまとめることを考える。局所特徴量のクラスタリングである。
　一般に、CLAFIC法により部分空間を作成するにはまず、クラスごとに多数のサンプルベクトルxを用意し、それらの自己相関行列Qを以下の式、
Figure JPOXMLDOC01-appb-M000001
 によって計算する。そして、λiをQの固有値、uiをそれに対する固有ベクトルとするとき、
Figure JPOXMLDOC01-appb-M000002
 の固有値問題を解くことで固有ベクトルを求める。元のサンプルベクトルxがn個あるとすると、一般にn個の固有ベクトルが求まる。そのn個の固有ベクトルのうち、いくつかの固有ベクトルによって張られる空間を部分空間という。求めたい部分空間の次元数をkとすると、上位k個の大きな固有値に対応する固有ベクトル
Figure JPOXMLDOC01-appb-M000003
 を基底（座標系）とする空間が、求めたい部分空間である。あるサンプルベクトルxの基底uiに係る固有値は、サンプルベクトルxを基底uiに正射影したときの長さ（射影成分）に相当する。基底u1は、クラス全体として最大の固有値に対応する基底であって、この明細書において第一主成分と呼ぶ。この部分空間をクラスごとに作成し、未知パターンのベクトルx'との類似度Dを計算することで、未知パターンのクラスを識別することができる。未知パターンのベクトルx'は、最大の射影成分を持つ部分空間のクラスに識別されることになる。類似度Dは、
Figure JPOXMLDOC01-appb-M000004
 より求めることができる。
　≪この発明の説明≫
　三次元物体の認識手法で述べたように、SIFT特徴量を用いた物体認識の従来手法によれば、高精度な認識結果を得るために、様々な視点（撮影角度）から撮影した画像から得た局所特徴量（特徴ベクトル）をそのままデータベースに登録する。そのため、メモリ容量が莫大なものになってしまう。そこでこの発明では、一連の視点の画像データから得られる同一部分の局所特徴量を、部分空間を用いて一つにまとめ、まとめられたものをデータベースに登録することによってメモリ容量を削減することを考える。また、部分空間に撮影角度の情報を対応づけておくことで、物体認識と併せて検索質問のおおよその撮影角度を得る。
１．局所特徴量の選定
　局所特徴量の格納に要するメモリ容量が莫大になるという問題の解決策として、データベースに登録する局所特徴量の数の削減を考える。しかし、局所特徴量を無作為に削減すると、認識率が大きく低下するおそれがある。そこで、同一の物体を示しかつ撮影角度が連続して変化する複数の画像データから抽出される、ある程度一貫性のある局所領域に注目し、そのような局所領域から得られる局所特徴量のみを物体認識に用いることを考える。なぜなら、撮影角度の変化に対してある程度一貫した局所特徴量が得られなければ、その局所特徴量は撮影角度の変化によって生じたノイズの可能性が高いからである。撮影角度が連続して変化する複数の画像データにおいて、物体の同じ部分から得られた局所特徴量は少しずつ変化する。そのような局所特徴量の変化を近似的に精度よく記述することができる部分空間を作成することで、複数の局所特徴量を一つにまとめて表現するのである。
　撮影角度が連続して変化する複数の画像データから、物体の同じ部分から得た局所特徴量を見つけ出す処理は以下のようになる。まず、撮影角度がわずかに異なる2枚の画像データにおいて、1フレーム目の画像データの各局所特徴量と2フレーム目の画像データの各局所特徴量との距離計算を行う。そして、それぞれ一番距離が近い局所特徴量を見つけることで、1フレーム目画像と2フレーム目画像の局所特徴量の対応づけを行う。このとき、ノイズなどの影響により、最近傍となった局所特徴量が、本当はあまり関連のない部分から得られたものであることがある。そこで、一番近い局所特徴量との距離をd1、二番目に近い局所特徴量との距離をd2とし、閾値をαとすると、
Figure JPOXMLDOC01-appb-M000005
を満たす局所特徴量の組のみを、物体の同じ部分から得られたものであるとする。これを満たさない局所特徴量はノイズであると考える。これを連続するすべての画像データ間で行い、局所特徴量の軌跡を得る。以下、このような処理をトレース処理とよぶ。前記軌跡は特徴ベクトルの集合ともいえる。なお、一番近い局所特徴量と二番目に近い局所特徴量との距離の差異を閾値と比較してノイズを除去する手法を述べたが、その変形例として、画像中の近い箇所から抽出された局所特徴量の距離の差異を閾値と比較してノイズを除去する手法が考えられる。
　図３は、この発明に係るトレース処理の様子を模式的に表す説明図である。「1フレーム目」、「2フレーム目」等の矩形枠は異なる視点から物体を撮影した各画像を示す。ａ，ｂおよびｃは前記物体の同一箇所を表す特徴ベクトルが異なる撮影角度（視点）の画像に連続して出現する軌跡を表す。例えば、特徴ベクトル集合aは1フレーム目に属する特徴ベクトルα1から2フレーム目に属する特徴ベクトルα2に対応づき、2フレーム目の特徴ベクトルα2は3フレーム目のどの特徴ベクトルにも対応づかなかったことを表している。また、特徴ベクトル集合ｂは1フレーム目から5フレーム目までの各視点に特徴ベクトルが連続して対応づいた様子を表している。特徴ベクトル集合ｃは、3フレーム目から5フレーム目までの各視点に特徴ベクトルが連続して対応づいた様子を表している。
２．部分空間の作成・登録処理
　この発明に係る登録処理においてコンピュータは、トレース処理によって得られた局所特徴量の集合を、その集合の部分空間を作成することで一つにまとめる。そして、その部分空間を物体IDとともに登録する。このとき、図３の軌跡ａのように、軌跡が短い局所特徴量の集合からも部分空間を作成しデータベースに登録すると、登録する部分空間の数が多くなり、メモリ容量の削減があまりなされない。そこで、軌跡の長さに閾値を設け、ある程度以上連続して対応づけられた局所特徴量の集合のみから部分空間を作成し、データベースに登録する。これは、局所特徴量の軌跡が短いものは、軌跡が長いものに比べて、識別できる撮影範囲が少ないためである。
　この発明により作成される部分空間は、具体的にはk次元の基底（座標系）を定めるk個の方向ベクトルで構成される。各軌跡はCLAFIC法の説明で述べたクラスに相当する。クラスごとのサンプルベクトルxは、各軌跡に属する局所特徴量に相当する。CLAFIC法により局所特徴量の自己相関行列を求め、その固有ベクトルを前記基底とする部分空間を張る。データベースには、この部分空間を成すk個の固有ベクトルを登録すればよい。登録された固有ベクトルは、その部分空間に属する各局所特徴量を近似的に表す。
　部分空間の次元数kが小さいほどメモリ容量は削減することができる。SIFT特徴量は128次元のベクトルで表現されるので、その部分空間の次元数kは1以上128未満のいずれかの次元数をとる。後述する実験例では、各部分空間の次元数kを一律に定めた。即ち、図６に示すようにk=1から8の８通りの場合をそれぞれ定め、それぞれの場合について実験している。しかし、次元数kの値は、部分空間ごとに適応的に決めてもよい。
　先に述べたように、登録処理では、局所特徴量そのものではなく、局所特徴量の集合を一つにまとめた部分空間を物体IDとともにデータベースに登録する。このとき、登録する部分空間が、どの視点からどの視点までの局所特徴量の変化を表現しているかといった、その部分空間の撮影角度の範囲も併せて登録する。認識処理の際に撮影角度の情報を用いることで、認識率の向上と質問画像がどの視点から撮影されたものであるかという大まかなパラメータの検出が可能となる。よって、登録処理は、部分空間を物体IDおよび撮影角度の範囲と関連付けて登録するものである。
３．認識処理
　この発明に係る認識処理において、コンピュータは、検索質問の画像が与えられたとき、その検索質問画像から局所特徴量を抽出し、各局所特徴量をデータベース中の各部分空間に射影し、局所特徴量と部分空間の類似度を計算する。そして最も類似度の高い部分空間を求め、その部分空間をもつ物体IDに投票処理を行う。これをすべての局所特徴量において行う。最終的に、最多得票数を得た物体IDを物体認識の結果として出力する。この際、物体によって部分空間の数が異なるため、得票数を部分空間の数で正規化する。正規化を行わなければ、部分空間の数が多い物体IDに多数の得票が集まってしまい、誤認識を起こす可能性がある。物体のある撮影角度ωを識別することができる部分空間の数をNωとし、撮影角度ωの得票数をGωとすると、
Figure JPOXMLDOC01-appb-M000006
 によって、得票数の正規化を行う。
　図４は、この発明に係る投票処理の様子を示す説明図である。例えば、質問画像から得られたある5つの局所特徴量とそれぞれ最も類似度の高い部分空間を求めたところ、図４の左のような物体IDと撮影範囲をもつ5つの部分空間が得られたとする。このとき、この発明の一態様に従い、もし単に物体IDごとの投票を行うとすると、図４の(a)のようになる。ところが、ある2つの局所特徴量が同じ物体IDをもつ部分空間に対応づいたとしても、視点の範囲が全く異なれば、それらは異なるものを示しているといえる。そこでこの発明の異なる態様においては、図４の(b)のように物体の撮影角度を考慮して投票を行う。
　具体的には、最も類似度の高い部分空間を求め、投票する際、その部分空間を作成した物体IDと、その部分空間を構成する局所特徴量が得られた物体の撮影角度との組み合わせに対して投票を行う。図４では、検索質問から５つの部分空間が抽出された例を示している。
　図４の(a)は、単に物体IDに対してのみ投票をおこった場合の投票結果を示している。図４の(a)の投票結果によれば、物体1と物体2が同数で最多の得票を得るためにどちらを認識結果とすればよいか判断できない。一方、図４の(b)は、物体IDと撮影角度の組み合わせに対して投票を行った場合の投票結果を示している。図４の(b)の投票結果によれば、物体1のうち撮影角度が20度から40度の範囲が最多得票を得るので、物体1を認識結果とすることができる。さらに、撮影角度20度から40度を質問画像のおおよその撮影角度として推定できるという利点もある。
　≪処理の流れ≫
　図１３は、この発明に係る三次元物体認識の処理の流れを示す説明図である。図１３に示すように、三次元物体認識の処理は、登録処理と認識処理に大別される。登録処理は、認識に用いる三次元物体の画像のデータベースを作成する処理である。認識処理は、検索質問として三次元物体の画像が与えられたとき、その画像に示された物体の画像を前記データベースの中から検索し、物体を特定する処理である。
　図１３で、（ａ）は登録処理の流れを示し、（ｂ）は認識処理の流れを示す。
　登録処理は、同一の物体を異なる視点から撮影した複数の画像が入力になる。登録処理を行うコンピュータは、前記入力が与えられると、各画像から局所特徴量を抽出する（ステップＳ１）。そして、異なる視点の画像に連続して含まれる同一箇所の局所特徴量を距離計算を用いて求め、それらの局所特徴量を一つにまとめる部分空間を作成する（ステップＳ３）。そして、生成された部分空間に前記物体の識別子と視点の撮影角度の範囲を付加し、データベースに登録する（ステップＳ５）。
　認識処理は、データベースに複数のデータが登録されていることを前提として行われる。認識処理は、入力として検索質問の画像が与えられる。ここで、検索質問はある物体をある視点から撮影した画像である。検索質問が入力されると、認識処理を行うコンピュータは、検索質問から局所特徴量を抽出する（ステップＳ１１）。検索質問から抽出された各局所特徴量について、最も類似する部分空間を前記データベースの中からそれぞれ検索する。そして、検索された部分空間に付加された物体IDを多数決処理し、一つの物体IDを定める（ステップＳ１３）。そして、その物体IDによって識別される物体をオペレーターが認識できるように出力する（ステップＳ１５）。
　この発明のデータベース作成装置は、登録に係る各処理を実行するコンピュータを装置としての観点で捉えたものである。各処理を実現するのは前記コンピュータを主とする共通のハードウェアであるが、各処理のプログラムが異なればコンピュータ処理によって実現される機能が異なる。これは、異なる機能を持つ複数の部品が組み合わされて全体として一つの装置が実現されることに対応するので、各処理の機能を実現する部分が組み合わされた装置として発明を捉えることができる。
　即ち、装置の観点から発明を捉えた場合は、局所特徴量の抽出処理の機能を担う抽出部、部分空間の作成処理の機能を担う部分空間生成部、データベースへの登録処理の機能を担う登録部を備えるデータベースの作成装置としてこの発明を捉えることができる。
なお、認識処理についても、検索質問から局所特徴量を抽出する機能を担う部分、抽出された各局所特徴量に最も類似する部分空間を検索し、その部分空間に付加された物体IDを多数決処理して一つの物体IDを決定する機能を担う部分、決定された物体IDを出力する機能を担う部分を備える装置として捉えることができる。
　≪処理時間の削減≫
　以上に述べた手法では、複数フレームに渡って同一の局所領域から得られた特徴量の集合から、KL 展開を用いて部分空間を作成し、複数の局所特徴量を一つにまとめて表現する。そうすることで、データベースに登録する特徴量を大幅に減らすことができ、メモリ容量を削減することができる。
　しかし、メモリ容量の削減が実現できても、一方で、処理時間の削減が課題となる。即ち、前述の手法では認識の際に、検索質問から得られた局所特徴量をデータベース内の部分空間のすべての基底に射影し、類似度を求めて認識を行っている。そのため、データベースに登録する物体数が増えると、適切な部分空間を探索するために時間を要する。射影して類似度を求めることで、各検索質問の局所特徴量に対応する部分空間を求める処理に代えて、距離計算によって適切な部分空間を求めることができれば、処理時間の削減の目処が立つ。既に提案されているANN(Approximate Nearest Neighborの略、詳細は、R. S. S. Arya, D. M. Mount and A. Y. Wu: “An optimal algorithm for approximate nearest neighbor searching”, Journal of the ACM, pp. 891-923 (1998)参照)を用いた近似最近傍探索の手法により、距離計算にかかる処理時間の短縮が可能になるからである。
　また、データベースに登録される物体の数が非常に大きかったり、検索質問に隠れ（オクルージョン）や照明条件などの変化が加わったりして実験条件が厳しくなると、局所特徴量と部分空間の比較だけでは認識が非常に困難になる。この実施形態では、相互部分空間法（詳細は、前田、渡辺：“局所構造を導入したパターン・マッチング法”、信学論(D)、pp. 345-352 (1985)参照）にANN を用いることで、認識率の向上と処理の高速化を実現する。
　１．処理時間削減手法の具体的手法
　各クラスに対応するk次元の部分空間との類似度を計算する前述の手法では、認識を行う際に、局所特徴量としての各クエリ特徴ベクトルをデータベース中の各クラスに対応する部分空間のそれぞれの基底に射影し、類似度を求めなければならない。そのためデータベースに登録する物体の増加に伴って、処理時間が大きくなる。この実施形態では、近似的に類似度の高い部分空間を探索する手法を採用し処理時間を削減する。
　１－１．ANNを用いた距離計算への置換
　k次元の部分空間への射影による認識処理では、各クエリ特徴ベクトルをデータベース中の各部分空間の各基底に射影し、最も類似度の高い部分空間を見つけるため、処理時間がかかるという問題が生じる。そこで、この実施形態では、最も類似度の高い部分空間を、クエリから得られた局所特徴量と部分空間の第一主成分上の点との距離計算によって求める方法を提案する。距離計算によって、最も類似度の高い部分空間を求めることができれば、既に提案されている様々な近似最近傍探索の手法により、高速化することができる。
　距離計算により、最も類似度の高い部分空間を求める方法は以下のようになる。まず、データベース中の各部分空間の座標軸上に、原点から等距離の点をおく。そして、これらの点とクエリから得られた局所特徴量との距離計算を行う。この距離が短ければ短いほど、局所特徴量をその部分空間へ射影したときの射影長が長くなる。すなわち、最も類似度の高い部分空間となる。
　以上が、ANNを用いた距離計算による処理時間の削減手法の概要である。さらに、詳細な説明を以下に述べる。
　近似最近傍探索の手法の一つとして、ANN と呼ばれる手法が提案されている。この手法は、木構造(kd-tree)をベースにしたもので、処理ソフトウェアが利用可能なため容易にANNの処理を試すことができる。ANN での処理の概要を以下に示す。
　まずデータベースに登録された局所特徴量（特徴ベクトル）の集合である特徴空間を2 分割してゆき、分割した領域中の特徴ベクトルが唯一になるまで繰り返す。分割した結果、最終的に得られる領域をセルと呼ぶ。次に、与えられたクエリ特徴ベクトルがどのセルに属するかを木構造を辿ることにより判定する。そして、このセルに対応づけられている特徴ベクトルとクエリ特徴ベクトルとの距離r を求める。このとき、真の最近傍点は半径r の超球内に存在する。そこで。この超球と重なりをもつすべてのセルにある特徴ベクトルと距離計算を行うことで、最近傍となる点を発見することができる。ANN では、超球の半径を1/(1 + ε) 倍して縮小することで、距離計算を行うセルを減らす。これにより、正しい最近傍が得られなくなるというリスクは負うものの、大幅な処理時間の削減、即ち、高速化が可能となる。
　しかし、ANN はある点に対する近傍点を近似的に求める手法であり、局所特徴量と部分空間の類似度を求めることはできない。そのため、部分空間法でANN を利用するためには、局所特徴量と最も類似度の高い部分空間を距離計算により求めることが必要である。この実施形態では、それを実現する手法を示す。
　まずこの実施形態の前提条件として、最も固有値の大きな固有ベクトルのみを基底とする１次元の部分空間、即ち、第一主成分のみで、部分空間を作成した元の局所特徴量の集合が十分よく表現されている必要がある。先に述べたk次元の部分空間を用いる手法では、トレース処理により連続的に変化する局所特徴量の集合を求め、その集合から部分空間を作成している。そのため、外れ値がほとんど存在せず、１次元の部分空間で近似的に十分よく表現できている。このとき、局所特徴量と部分空間の類似度は、局所特徴量と部分空間の基底との距離に反比例するといえる。すなわち、局所特徴量と最も距離の近い部分空間を求めることで、最も類似度の高い部分空間を求めることができる。
　局所特徴量と部分空間の基底との距離は、一般には局所特徴量から各部分空間の基底に下した垂線の長さとして求められる。しかしながら、これでは点と直線の距離を求めることとなり、ANN を用いて近似最近某探索を行うことができない。そこで、各部分空間の基底上に原点からの長さを正規化した点Si(∥Si∥ = 1)をそれぞれおき、点Si と局所特徴量の距離dSi を求める。この距離dSi から、局所特徴量と部分空間の距離を正確に求めることはできないが、局所特徴量と各部分空間との距離の遠近関係を知ることができる。つまり、距離dSi が最小となる部分空間が、最近傍の部分空間であり、最も類似度の高い部分空間である。
　１－２．近似最近傍探索による絞込み
　前述のように、部分空間の第一主成分のみを用いて距離計算を行う手法により、k次元の部分空間に対する類似度を求める手法に比べて認識に要する処理時間を削減することができる。しかし、部分空間の複数の軸を用いたほうが、より高い認識率を見込むことができる。
　そこで、別の実施形態として、２段階の処理を採用して認識を行う態様を挙げることができる。この実施形態では、まず１段階目として、部分空間の第一主成分のみを用いて、近似最近傍探索により高速に最も類似度の高い部分空間となるであろう候補を絞り込む。そして２段階目に、その候補に挙げられた各部分空間の複数の軸を用いて高次元に射影し、真に最も類似度の高い部分空間を求める。２段階目の処理を加えることによって、各部分空間の第一主成分のみを用いる場合に比べて高い認識率を見込むことができる。一方、２段階目のみの態様、即ち、各部分空間の各基底に各特徴ベクトルを射影して類似度を求める場合に比べて、類似度計算の対象（候補）を絞り込むので、処理時間を削減することができる。
　１－３．相互部分空間法におけるANNの利用
　この実施形態は、検索質問に動画もしくは連続撮影した複数の画像を用いる場合に有効である。この態様によれば、データベースを作成する際と同様に、検索質問に係る複数画像に対してもトレース処理を行う。トレース処理によって得られた局所特徴量の集合から部分空間を作成する。そうすることで、データベースの部分空間と質問画像から得た部分空間とを比較することができる。検索質問から得られた部分空間を、この明細書ではクエリ部分空間と呼ぶ。部分空間同士を比較し最適な部分空間を見つけるには、一般的にそれらの正準角を用いる。しかし、その手法では高速化が望めない。そこで、ここでも距離計算によって最適な部分空間を求める。既に述べたANNの距離計算と同様、各部分空間の軸上に、原点から等距離の点を置き、その点と点との距離計算を行う。この実施形態ではクエリも部分空間であるから、そのクエリ部分空間の座標軸上にも点を置く必要がある点に留意すべきである。以下、さらに詳細な説明を述べる。
　相互部分空間法（Mutual Subspace Method）は、検索質問として動画像や複数の視点の画像を利用できる場合に用いられる。検索質問から得た局所特徴量の集合からもクエリ部分空間を作成し、クエリ部分空間とデータベース内の部分空間との比較によって検索質問を認識する。局所特徴量に比べ部分空間は変動が少ないため、検索質問として用いることで高い認識率を見込むことができる。ここで、検索質問から作成したクエリ部分空間とデータベース内の部分空間の類似度は、両者がなす正準角を算出することで求めることができる。しかし、正準角の算出にかかる処理時間は莫大なものになる。
　そこで、処理時間の削減を実現するため、この実施形態においてもANNを用いて処理時間を削減することを考える。まず、データベースに登録する各部分空間のそれぞれの基底上に、原点からの距離が１となるような点Si を配置する。また、検索質問から得たクエリ部分空間の基底上にも、適当な点Q をおく。このとき、点Q との距離が最小となる点Si を基底上にもつ部分空間が、求めたい部分空間である。点Qとの距離が最小となる点Si は、ANN を用いることで近似的に求めることができる。これにより、相互部分空間法におけるクエリ部分空間と部分空間との比較が短い処理時間で実現できる。
　≪実験例１≫
　局所特徴量を用いた物体認識の基本的な従来手法と、複数の局所特徴量を部分空間で表現するこの発明の手法との比較実験を行った。比較の指標はメモリ容量と認識率である。
１－１．実験の説明
　本実験で用いたデータセットについて説明する。本実験では、55個の三次元物体をターンテーブルで一回転させ、動画を撮影した。
　図５は、この発明に係る実験に使用した物体のいくつかの例を示す説明図である。そして、撮影された動画を構成する各フレーム画像を取得し、そのフレーム画像の中からデータベースに登録する登録用画像と検索質問画像を作成した。登録用画像は、各物体につき撮影角度を約1度ごとに変化させた360枚の画像を作成した。また、質問画像は、各物体につき約36度ごとに変化させた10枚の画像を作成した。ここで、登録用画像と質問画像は、異なる画像とした。つまり、検索質問画像と完全に同一の登録用画像は存在しない。データベースを作成するために、登録用画像からSIFT特徴量を抽出した。１枚の登録用画像から100～400個ほどの局所特徴量をそれぞれ得た。仮に1枚あたり300個の局所特徴量が得られたとすると、１つの物体の局所特徴量は300個×360枚＝108,000個であり、55個の物体に係る局所特徴量の総数はその55倍の5,940,000個である。検索質問は、全部で10枚×55個＝550枚である。１枚の画像につきそれぞれ物体認識を行うので、最大550通りの物体認識が行われる。図６の縦軸の認識率はそれらの平均である。
　そして、前述のトレース処理によって、それらの局所特徴量から、20個以上連続して対応づいたもののみを選定した。つまり、撮影角度20度以上の範囲に渡り局所特徴量が対応づいたものを登録の対象とした。このとき、トレース処理を行う際に物体の同じ部分から得られた局所特徴量であるかどうかを判定するための閾値α（前述の「数５」の式を参照）の値を0.6に定めた。その各局所特徴量の集合からなる部分空間を求め、求まった部分空間に物体IDと対応する撮影角度の範囲とを付加してデータベースに登録した。一つの物体から得られる部分空間の数は、それぞれ100～400個ほどであった。
１－２．実験結果・考察
　まず、この発明の認識処理において、投票を行う際、図４(b)のように物体に加えその撮影角度を考慮して投票を行うことが、どのくらい認識率に影響を及ぼしているかを調べる第１の実験を行った。
　図６は、この発明に係る第１の実験結果を示すグラフである。横軸は用いた部分空間の次元数を、縦軸は認識率を表している。実験結果より、物体IDごとに投票を行う態様であっても、95％を超える認識率が得られ、部分空間の次元数が三次元のときに98.3％となった。物体の撮影角度ごとに投票を行うと誤投票が分散され、部分空間の次元に関係なく認識率がさらに向上した。単なる物体IDでなく、物体IDと撮影角度との組み合わせに投票を行った場合、部分空間の次元数が三次元のときに98.9％となった。意外にも、次元数をそれ以上増やしても98.9％以上の認識率を得ることはなかった。この理由としては、部分空間の次元数を増やすと、部分空間と部分空間の間で重なりが増加し、部分空間の識別性が低下するためではないかと考えられる。つまり、求めたい部分空間との類似度だけが高くなるだけでなく、他の部分空間との類似度も高くなる可能性があるのである。
　図７は、この発明の実験に検索質問として用いた物体Aを示す説明図である。
　図８は、図７の物体Aに対して物体IDのみに投票を行った結果を示すグラフである。
　また、図９は、図７の物体Aに対して物体IDと撮影角度との組み合わせに投票を行うことで正しく認識されるようになった例を示す説明図である。図７の質問画像は、物体Aをある撮影角度で撮影したものである。図８に、各物体IDに投票を行い得票数を正規化して得られるスコアを示す。本来ならば物体Aのスコアが最も高くなるべきであるが、他の物体Bや物体Cのスコアのほうが高くなった。そのため、物体ごとに投票を行った場合、質問画像は物体Cと認識された。
　一方、図９は、物体IDと撮影角度の組み合わせに投票したときの物体A、物体B、物体Cの各撮影角度におけるスコアの様子を示す。物体IDのみに投票を行ったとき最もスコアが高かった物体Cでは、物体IDと撮影角度の組み合わせに投票することで得票数が分散し、スコアが低くなった。また、物体Aでは、ある範囲の撮影角度に票が集まった。そのため、物体IDのみに投票を行ったときには物体Cと認識されたものが、物体IDと撮影角度の組み合わせに投票を行うことで物体Aと正しく認識された。このとき、認識を行うと同時に、最もスコアが高くなった物体Aの68度と69度を、質問画像のおおよその撮影角度と推定することができた。
　図１０は、この発明の実験に用いた物体Aの68度と69度の画像を示す説明図である。(a)は68度、(b)は69度の画像である。図１０からわかるように、物体Aの撮影角度が正しく推定できているといえる。一方、この発明で認識できなかった例を次に示す。
　図１１は、この発明の実験に用いた物体Dを示す説明図である。図１２は、図１１に示す物体Dを質問画像としたときの、物体Dと物体Eの各撮影角度のスコアを表したものである。本来ならば、物体Dの最もスコアが高い132度から144度が認識結果として得られることが望ましい。しかし、物体Eのスコアのように、得票数がある程度分散しているにも関わらず、スコアが高い場合は誤認識となってしまう。
　次に、物体IDと撮影角度の組み合わせに対して投票するこの発明の、メモリ容量を調べる実験を行った。実験結果より、部分空間の次元数が1次元のときに19.98MBとなり、次元が増えるごとに約8.26MBずつ増えることがわかった。表1に、最もメモリ容量が少なかった1次元の部分空間を用いたときの認識率とメモリ容量（表１中のデータベースの(1)を参照）、および、最も認識率が高くなった三次元の部分空間を用いたときの認識率とメモリ容量（表１中のデータベースの(2)を参照）をそれぞれ示す。
　さらに、この発明がどのくらいメモリ削減に有用でありかつ認識率が維持されるかを比較するために、局所特徴量同士の最近傍探索による手法を用いて以下のデータベースで実験を行った。比較に用いたデータベースは、(3)データベースを作成するために用いたすべての局所特徴量を登録したもの、(4)トレース処理で得られた局所特徴量をすべて登録したもの、(5)トレース処理後、各局所特徴量の集合の中からその中央に位置する局所特徴量のみを、その集合の代表ベクトルとして登録したものの3つである。表1に、それらのデータベースで実験を行ったときの認識率とメモリ容量を示す。
Figure JPOXMLDOC01-appb-T000007
　この発明で三次元の部分空間を用いたときのメモリ容量は、無削減状態であるデータベース(3)のメモリ容量の約1/18にすることができた。また、トレース処理で得られた局所特徴量をすべて登録したデータベース(4)と比較すると、部分空間を作成し用いることで、メモリ容量を約1/7にしながら、無削減状態から若干低下した認識率を回復させることができた。さらに、1次元の部分空間を用いたときのメモリ容量とデータベース(5)と比較すると、(5)に対してメモリ容量はわずかに増加するが、より高い認識率が得られた。
　(5)に対して認識率が向上した理由は、次の理由による。トレースの中央の局所特徴量は、トレース処理によって対応づけられた複数の局所特徴量の代表ベクトルであるだけで、その集合のすべての局所特徴量を表しているわけではいない。これに対し、この発明で用いた部分空間はその集合に含まれるいずれの局所特徴量の特性をもよく表している。
　より具体的に説明する。例えば、データベースに物体Fのトレース範囲が20度から60度の局所特徴量の集合Ａと40度から80度の局所特徴量の集合Ｂがあったとする。このとき、質問画像が物体Fの40度の向きを撮影したものであるとする。トレースの中央の局所特徴量を用いる手法では、集合Ａは40度の局所特徴量が代表ベクトルとなるので物体Fと対応づけられるが、集合Ｂは60度の局所特徴量が代表ベクトルとなり物体Fと正しく対応づけることが難しくなる。そのため、誤投票を行うことが多くなってしまい、誤認識されやすい。一方、部分空間法を用いたこの発明では、集合Ａ、Ｂのどちらとも40度の向きを含んだ部分空間が作成されるので、正しく対応づけることができる。そもそも部分空間は、そのクラスのメンバーの特性がよく表されるようにクラス分類を行う手法だからである。そのため、部分空間法を用いたこの発明の手法では誤投票が少なくなり、認識率が向上したと考えられる。異なる表現をすれば、代表ベクトルは一つの局所特徴量にすぎず、局所特徴量は「点」を表すものである。これに対して撮影角度の範囲は「区間」を表すため、「区間」を「点」で表現するとどうしてもズレが生じる。一方、部分空間法では、得られる部分空間は「区間」を表す。そのためズレは生じない。
　次に、データベース(5)を用いて、物体IDと撮影角度の組み合わせに投票する実験を行った。すなわち、トレース処理後の局所特徴量の集合から選択した一つの局所特徴量に、その局所特徴量が含まれるトレースが何度から何度まで対応しているかという情報をもたせ、投票の際に最近傍となった局所特徴量が対応する撮影角度の範囲に投票を行った。その結果、認識率は96.36％となり、物体ごとに投票を行った結果とほとんど認識率が変わらず、厳密には少し低下する結果となった。これより、トレースの中央の局所特徴量のみを登録しただけのデータベースでは、撮影角度ごとに投票することにあまり意味がないといえる。もちろん、物体ごとに投票した際に誤認識となっていたものが、物体の撮影角度ごとに投票することで正しく認識されるようになったものもある。しかし、逆に物体の撮影角度ごとに投票することで誤認識となったものもあり、結果的に認識率が向上しなかったのである。
　物体ごとに投票した際は正しく認識されたものが、物体の撮影角度ごとに投票することで誤認識となったものの原因は、次のように考えられる。誤投票が多いため、正解の物体であっても撮影角度ごとに投票することで票が分散してしまったり、逆に誤りである物体の撮影角度に票が偶然いくつか重なってしまったりすることが多くなったのである。また、得票数の正規化を行うことで、正解の物体の撮影角度のスコアが低くなってしまうこともある。例えば、物体Gの20度から60度の局所特徴量の集合と60度から100度の局所特徴量の集合と60度から110度の局所特徴量の集合があったとする。物体Gの60度を表している代表ベクトルは3つあることになるが、実際には代表ベクトルは物体Gの40度と80度と85度のものであるから、質問画像が物体Gの60度である場合には、なかなか対応づけることが難しい。そのため、正規化を行う際の分母√Nωが必要以上に大きくなってしまい、スコアが低くなってしまう傾向がある。
　以上に述べたように、この発明によれば、連続して変化する局所特徴量を、その変化を近似的によく表現することができる部分空間を作成して一つにまとめてデータベースに登録することで、メモリ容量を削減した。その結果、98.9％の認識率を得ながら、メモリ容量は無削減状態の約1/18にすることができた。また、物体の撮影角度ごとに投票することによって、質問画像の物体の種類を認識するだけでなく、おおよその物体の向きを推定することもできた。
　≪実験例２≫
　1002 個の物体の認識実験に対して、（１）ANN を用いることの有効性と（２）相互部分空間法による認識率の向上を確かめることを目的としてそれぞれ実験を行った。第１の実験では局所特徴量と部分空間の比較により物体を認識した。第２の実験では相互部分空間法を用いて物体を認識した。
　２－１．実験準備
　この実験例で用いたデータベースについて説明する。実験例では、1002 個の３次元物体につき各物体をターンテーブルで１回転させ、正面、上15 度および上30 度の仰角からの動画をそれぞれ撮影した。
　図１４は、データベースに登録した物体の一例を示す説明図である。撮影された動画からフレーム画像を取得し、データベース用画像とした。これらの画像からSIFT 特徴量を抽出し、トレース処理を行い、部分空間を作成した。ここで、部分空間を作成する局所特徴量の集合は、トレース処理によって50 フレーム以上連続して対応づいた局所特徴量の集合とした。作成した部分空間を物体ID とともにデータベースに登録した。部分空間の数は、１物体あたり約550 個である。
　次に、この実験例で用いた検索質問について説明する。データベースに用いた1002 物体のうち、無作為に100 物体を選び、選んだ物体を手で持って動画を撮影した。そして、撮影動画からフレーム画像を取得し、検索質問用画像とした。図１５は、検索質問用に撮影した物体の一例を示す説明図である。検索質問用画像からもSIFT 特徴量を抽出した。
　２－２．ANNを用いた距離計算に関する実験
　第１の実験として、ANN を用いた距離計算の有効性を検証するため、最近傍探索を行った際と、ANNを用いて近似最近傍探索を行った際の認識率と処理時間の比較を行った。各検索質問用画像に対して撮影した物体を認識した。
　結果を以下の表２に示す。
Figure JPOXMLDOC01-appb-T000008
　表２に示す実験結果から、近似最近傍探索を行った場合、最近傍探索によって認識を行った場合と比べてほとんど認識率を落とすことなく、処理時間が大幅に短縮できることがわかる。また、ANN の近似の度合いを示すパラメータεを変化させても処理時間がほとんど変わらない原因は、εの値が小さくても十分処理時間が短く、誤差によるものだと考えられる。
　２－３．相互部分空間法に関する実験
　相互部分空間法による認識率の向上を確かめることを目的として実験を行った。各物体の検索質問用フレーム画像に対して、トレース処理を行い、クエリ部分空間を作成した。クエリ部分空間を作成した局所特徴量の集合は、トレース処理によってT フレーム以上対応づいたもののみとした。T の値は[8, 13, 25, 38, 50] と変化させた。
　また、相互部分空間法の比較対象として、複数の検索質問用フレーム画像を一つの検索質問として認識実験を行った。一つにまとめるフレーム画像の間隔をI として、I の値を[5, 20, 40, 100] と変化させた。
　結果を以下の表３に示す。
Figure JPOXMLDOC01-appb-T000009
　１枚の画像を検索質問に用いる前記項目２－２の実験と比較すると、動画として複数フレーム画像を検索質問に用いるほうが、１枚の画像を用いるよりもよい認識率を得ることができることがわかる。検索質問として用いるフレーム画像の間隔が短く（画像の数が多く）なればなるほどなればなるほど、認識率の向上を見込むことができる。また、T = 8 のときの物体ごとの部分空間の数は平均5200 個であり、I = 5 のときの物体ごとの局所特徴量の数は平均45600 個であった。そのことから、複数のフレーム画像から得た局所特徴量をそのまま認識に用いるより。クエリ部分空間を作成して認識を行ったほうが、認識率・処理時間とも向上したといえる。
　２－４．実験例２のまとめ
　この実施形態では、部分空間法において、最も高い類似度の部分空間を求める処理を高速化する手法を示した。この実施形態によれば、局所特徴量と最も高い類似度となる部分空間を求めるにあたり、各部分空間の各基底への射影成分ではなく、各部分空間の基底上の定点との距離の大小関係に基づいて求めた。距離の大小関係によって求めることで、ANN を用いて近似最近傍探索を行うことができ、処理時間の高速化が実現できた。
　その結果、従来の部分空間法では処理時間が190 秒、認識率が34% であったものが、ANN を使うことで認識率を略同程度に保ちながら処理時間を0.012 秒にすることができた。また、相互部分空間法にも提案手法を適用し、処理時間の高速化と同時に、大幅な認識率の向上を可能にした。
　前述した実施の形態の他にも、この発明について種々の変形例があり得る。それらの変形例は、この発明の範囲に属さないと解されるべきものではない。この発明には、請求の範囲と均等の意味および前記範囲内でのすべての変形とが含まれるべきである。
　ａ，ｂ，ｃ：特徴ベクトル集合
　α1，α2：特徴ベクトル

Claims (13)

  1. 　三次元の物体を異なる視点から見た複数の画像が入力されたとき、各画像の局所的特徴を抽出し特徴ベクトルとしてそれぞれ表す工程と、
    特徴ベクトルからなる複数の集合であって、各集合が、隣り合う一連の視点から前記物体の同一箇所を見た局所的特徴を表す集合を生成し、それぞれの集合の特性を表す複数の部分空間を部分空間法により生成する部分空間生成工程と、
    各部分空間に前記物体の識別子を関連づけて三次元物体認識用データベースに登録する登録工程とを備え、
    前記データベースは、三次元物体の認識処理のため、コンピュータによりアクセスされ、
    前記認識処理は、ある物体をある視点から見た一つの画像または一連の視点から見た複数の画像が検索質問として与えられたとき、その検索質問の局所的特徴をそれぞれ表す複数の特徴ベクトルをクエリ特徴ベクトルとして抽出し、各クエリ特徴ベクトルに最も類似する部分空間をそれぞれ決定し、各部分空間に関連づけられた物体IDについて集計処理を行い、前記検索質問に最も類似する物体を得る工程により実現される三次元物体認識用画像データベースの作成方法。
  2. 　前記登録工程は、前記物体の識別子および前記一連の視点を表す視点データの組み合わせを各部分空間に関連づけて登録し、
    前記認識処理は、各部分空間に関連づけられた前記組み合わせについて集計処理を行い、前記検索質問に最も類似する物体および最も類似する視点を得る工程である請求項１に記載の方法。
  3. 　前記部分空間生成工程は、隣り合う視点に対応する各対の特徴ベクトルの距離を計算し、異なる対との距離が予め定められた基準を超えて相違するものをノイズとして除外し、残った特徴ベクトルを同一箇所を表す特徴ベクトルの集合とする請求項１または２に記載の方法。
  4. 　前記部分空間生成工程は、各集合の特徴ベクトルが予め定められた視点の変化量より広範囲に渡る場合は部分空間を生成するが、前記変化量に満たない場合は部分空間を生成しない請求項１～３のいずれか一つに記載の方法。
  5. 　前記部分空間生成工程は、各対のうち、最も近い距離の対と２番目に近い距離の対との相違が前記基準を超えるものをノイズとして除外する請求項４に記載の方法。
  6. 　前記認識処理は、各クエリ特徴ベクトルを前記データベースに予め登録された各部分空間の座標系を定める基底にそれぞれ射影して射影成分の大きさに基づき各クエリ特徴ベクトルと各部分空間との類似度を算出し、最も高い類似度の部分空間を、そのクエリ特徴ベクトルに最も類似する部分空間であると決定する請求項１～５のいずれか一つに記載の方法。
  7. 　前記認識処理は、各部分空間が特性を表す特徴ベクトルの集合において最大の固有値に係る第一主成分の基底を各部分空間についてそれぞれ決定し、第一主成分の各基底上において原点からの正規化された距離が等しい位置にそれぞれ点をおき、各点と各クエリ特徴ベクトルとの距離を近似最近傍探索の手法を適用して求め、最も近い距離の部分空間を、そのクエリ特徴ベクトルに最も類似する部分空間であると決定する請求項１～５のいずれか一つに記載の方法。
  8. 　前記認識処理は、請求項７に記載の方法により各クエリ特徴ベクトルに類似する部分空間を幾つかの候補に絞り込んだ後、候補とされた各部分空間の各基底にそのクエリ特徴ベクトルをそれぞれ射影して射影成分の大きさに基づき各クエリ特徴ベクトルと各部分空間との類似度を算出し、最も高い類似度の部分空間を、そのクエリ特徴ベクトルに最も類似する部分空間であると決定する三次元物体認識用画像データベースの作成方法。
  9. 　前記認識処理は、各クエリ特徴ベクトルに最も類似する部分空間を決定する処理に代えて、
    （１）一連の視点から見た複数の画像が検索質問として与えられたとき、その検索質問に係るクエリ特徴ベクトルからなる複数の集合であって、各集合が、隣り合う一連の視点から前記物体の同一箇所を見た局所的特徴を表す集合を生成し、それぞれの集合の特性を表す複数のクエリ部分空間を部分空間法により生成し、
    （２）各クエリ部分空間の座標系を定める各基底上において原点からの正規化された距離が所定の位置にそれぞれクエリ基準点をおき、前記データベースに登録された各部分空間の各基底上において原点からの正規化された距離が前記所定の位置にそれぞれ基準点をおき、
    （３）各クエリ基準点から最短距離の基準点を有する部分空間を各近似最近傍探索の手法を用いて決定することにより、
    各クエリ部分空間に最も類似する部分空間を決定する請求項１～５の何れか一つに記載の方法。
  10. 　前記視点データは、前記物体の撮影角度のデータである請求項１～９のいずれか一つに記載の方法。
  11. 　前記部分空間生成工程は、CLAFIC法を適用して特徴ベクトルを集合としてまとめ、部分空間を生成する請求項１～１０のいずれか一つに記載の方法。
  12. 　部分空間の次元数は、１以上３以下である請求項１～６のいずれか一つに記載の方法。
  13. 　三次元の物体を異なる視点から見た複数の画像が入力されたとき、各画像の局所的特徴を抽出し特徴ベクトルとしてそれぞれ表す抽出部と、
    特徴ベクトルからなる複数の集合であって、各集合が、隣り合う一連の視点から前記物体の同一箇所を見た局所的特徴を表す集合を生成し、それぞれの集合の特性を表す複数の部分空間を部分空間法により生成する部分空間生成部と、
    各部分空間に前記物体の識別子を関連づけて三次元物体認識用データベースに登録する登録部とを備え、
    前記データベースは、三次元物体の認識装置によりアクセスされ、
    前記認識装置は、ある物体をある視点から見た一つの画像または一連の視点から見た複数の画像が検索質問として与えられたとき、その検索質問の局所的特徴をそれぞれ表す複数の特徴ベクトルをクエリ特徴ベクトルとして抽出し、各クエリ特徴ベクトルに最も類似する部分空間をそれぞれ決定し、各部分空間に関連づけられた物体IDについての集計処理を各クエリ特徴ベクトルについて行い、前記検索質問に最も類似する物体を得る機能を有する三次元物体認識用画像データベースの作成装置。
PCT/JP2011/060277 2010-04-28 2011-04-27 三次元物体認識用画像データベースの作成方法および作成装置 Ceased WO2011136276A1 (ja)

Priority Applications (5)

Application Number Priority Date Filing Date Title
CN201180021296.XA CN103109307B (zh) 2010-04-28 2011-04-27 用于制作三维物体识别用图像数据库的方法和装置
HK13111622.8A HK1184267B (en) 2010-04-28 2011-04-27 Creation method and creation device of three-dimensional object recognition-use image database
US13/643,284 US8971610B2 (en) 2010-04-28 2011-04-27 Method and apparatus of compiling image database for three-dimensional object recognition
JP2012512888A JP5818327B2 (ja) 2010-04-28 2011-04-27 三次元物体認識用画像データベースの作成方法および作成装置
EP11775057.0A EP2565844B1 (en) 2010-04-28 2011-04-27 Creation method and creation device of three-dimensional object recognition-use image database

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
JP2010103543 2010-04-28
JP2010-103543 2010-04-28

Publications (1)

Publication Number Publication Date
WO2011136276A1 true WO2011136276A1 (ja) 2011-11-03

Family

ID=44861574

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/JP2011/060277 Ceased WO2011136276A1 (ja) 2010-04-28 2011-04-27 三次元物体認識用画像データベースの作成方法および作成装置

Country Status (5)

Country Link
US (1) US8971610B2 (ja)
EP (1) EP2565844B1 (ja)
JP (1) JP5818327B2 (ja)
CN (1) CN103109307B (ja)
WO (1) WO2011136276A1 (ja)

Cited By (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN103136751A (zh) * 2013-02-05 2013-06-05 电子科技大学 一种改进型sift图像特征匹配算法
WO2015015554A1 (ja) * 2013-07-29 2015-02-05 Ｎｅｃソリューションイノベータ株式会社 ３ｄプリンタ装置、３ｄプリント方法及び立体造形物の製造方法
WO2017017808A1 (ja) * 2015-07-29 2017-02-02 株式会社日立製作所 画像処理システム、画像処理方法及び記憶媒体
CN110047275A (zh) * 2018-01-13 2019-07-23 丰田自动车株式会社 多个连接的车辆的观察结果之间的关联和相似度学习

Families Citing this family (15)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP5906071B2 (ja) * 2011-12-01 2016-04-20 キヤノン株式会社 情報処理方法、情報処理装置、および記憶媒体
US9418427B2 (en) * 2013-03-15 2016-08-16 Mim Software Inc. Population-guided deformable registration
US9495389B2 (en) * 2013-03-15 2016-11-15 Qualcomm Incorporated Client-server based dynamic search
CN104133807B (zh) * 2014-07-29 2017-06-23 中国科学院自动化研究所 学习跨平台多模态媒体数据共同特征表示的方法及装置
TW201719572A (zh) * 2015-11-19 2017-06-01 國立交通大學 三維模型分析及搜尋方法
CN109074369B (zh) * 2016-03-08 2022-03-04 河谷控股Ip有限责任公司 用于基于图像的对象识别的图像特征组合
US20170323149A1 (en) * 2016-05-05 2017-11-09 International Business Machines Corporation Rotation invariant object detection
CN110147460B (zh) * 2019-04-23 2021-08-06 湖北大学 基于卷积神经网络与多视角图的三维模型检索方法及装置
CN110389703A (zh) * 2019-07-25 2019-10-29 腾讯数码（天津）有限公司 虚拟物品的获取方法、装置、终端和存储介质
US11328170B2 (en) * 2020-02-19 2022-05-10 Toyota Research Institute, Inc. Unknown object identification for robotic device
WO2022015236A1 (en) * 2020-07-17 2022-01-20 Hitachi, Ltd. Method of image processing for object identification and system thereof
CN112463952B (zh) * 2020-12-22 2023-05-05 安徽商信政通信息技术股份有限公司 一种基于近邻搜索的新闻文本聚合方法及系统
US11886445B2 (en) * 2021-06-29 2024-01-30 United States Of America As Represented By The Secretary Of The Army Classification engineering using regional locality-sensitive hashing (LSH) searches
JP7113469B1 (ja) * 2021-12-24 2022-08-05 学校法人明治大学 物体認識システム、物体認識プログラム及び、物体認識方法
CN117033718B (zh) * 2023-09-14 2024-06-07 上海交通大学 基于光线追踪的近似近邻搜索方法、系统、介质及设备

Citations (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
WO2008026414A1 (fr) * 2006-08-31 2008-03-06 Osaka Prefecture University Public Corporation Procédé de reconnaissance d'image, dispositif de reconnaissance d'image et programme de reconnaissance d'image
WO2009133855A1 (ja) * 2008-04-30 2009-11-05 公立大学法人大阪府立大学 ３次元物体認識用画像データベースの作成方法、処理装置および処理用プログラム
JP2010009332A (ja) * 2008-06-27 2010-01-14 Denso It Laboratory Inc 画像検索用データベース装置、画像検索用データベース管理方法およびプログラム

Family Cites Families (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
WO2004008392A1 (ja) * 2002-07-10 2004-01-22 Nec Corporation ３次元物体モデルを用いた画像照合システム、画像照合方法及び画像照合プログラム
US7706603B2 (en) * 2005-04-19 2010-04-27 Siemens Corporation Fast object detection for augmented reality systems

Patent Citations (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
WO2008026414A1 (fr) * 2006-08-31 2008-03-06 Osaka Prefecture University Public Corporation Procédé de reconnaissance d'image, dispositif de reconnaissance d'image et programme de reconnaissance d'image
WO2009133855A1 (ja) * 2008-04-30 2009-11-05 公立大学法人大阪府立大学 ３次元物体認識用画像データベースの作成方法、処理装置および処理用プログラム
JP2010009332A (ja) * 2008-06-27 2010-01-14 Denso It Laboratory Inc 画像検索用データベース装置、画像検索用データベース管理方法およびプログラム

Non-Patent Citations (11)

* Cited by examiner, † Cited by third party
Title
D. LOWE: "Distinctive image features from scale-invariant keypoints", INTERNATIONAL JOURNAL OF COMPUTER VISION, vol. 60, no. 2, 2004, pages 91 - 110, XP019216426, DOI: doi:10.1023/B:VISI.0000029664.99615.94
E. OJA: "Subspace methods of pattern recognition", 1983, RESEARCH STUDIES PRESS
F. ROTHGANGER; S. LAZEBNIK; C. SCHMID; J. PONCE: "3D Object Modeling and Recognition Using Local Affine-Invariant Image Descriptors and Multi-View Spatial Constraints", INTERNATIONAL JOURNAL OF COMPUTER VISION, vol. 66, 2006, pages 3
HONDO; KISE: "Inspection of Memory Reduction Methods for Specific Object Recognition: Approaches by quantization and selection of Local Features", TECHNICAL REPORT OF THE INSTITUTE OF ELECTRONICS, INFORMATION, AND COMMUNICATION ENGINEERS, 2009
INOUE; MIYAKE; KISE: "Experimental Investigation of a Memory Reduction for 3D Object Recognition Based on Selection of Local Features", THE IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS D, vol. J92-D, no. 9, 2009, pages 1686 - 1689
KENICHIRO ISHII; EISAKU MAEDA; NAONORI UEDA; HIROSHI MURASE: "Plain Pattern Recognition", August 1998, OHMSHA LTD., pages: 147 - 151
MAEDA; WATANABE: "Pattern matching using local structure", THE TRANSACTIONS OF THE INSTITUTE OF ELECTRONICS, INFORMATION AND COMMUNICATION ENGINEERS (D, 1985, pages 345 - 352
MURASE; S. K. NAYAR: "3D object Recognition from appearance - parametric eigenspace method", THE TRANSACTIONS OF THE INSTITUTE OF ELECTRONICS, INFORMATION AND COMMUNICATION ENGINEERS (D-II, vol. J77-D-II, no. 11, 1994, pages 2179 - 2187
P. J. BESL; R. C. JAIN: "Three-Dimensional Object Recognition", ACM COMPUTING SURVEYS, vol. 17, no. 1, 1985, pages 75 - 145, XP008018762, DOI: doi:10.1145/4078.4081
R. S. S. ARYA; D. M. MOUNT; A. Y. WU: "An optimal algorithm for approximate nearest neighbor searching", JOURNAL OF THE ACM, 1988, pages 891 - 923
See also references of EP2565844A4

Cited By (5)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN103136751A (zh) * 2013-02-05 2013-06-05 电子科技大学 一种改进型sift图像特征匹配算法
WO2015015554A1 (ja) * 2013-07-29 2015-02-05 Ｎｅｃソリューションイノベータ株式会社 ３ｄプリンタ装置、３ｄプリント方法及び立体造形物の製造方法
WO2017017808A1 (ja) * 2015-07-29 2017-02-02 株式会社日立製作所 画像処理システム、画像処理方法及び記憶媒体
JPWO2017017808A1 (ja) * 2015-07-29 2018-03-08 株式会社日立製作所 画像処理システム、画像処理方法及び記憶媒体
CN110047275A (zh) * 2018-01-13 2019-07-23 丰田自动车株式会社 多个连接的车辆的观察结果之间的关联和相似度学习

Also Published As

Publication number Publication date
US20130039569A1 (en) 2013-02-14
CN103109307B (zh) 2015-11-25
JP5818327B2 (ja) 2015-11-18
CN103109307A (zh) 2013-05-15
EP2565844A4 (en) 2014-12-03
HK1184267A1 (zh) 2014-01-17
EP2565844A1 (en) 2013-03-06
US8971610B2 (en) 2015-03-03
EP2565844B1 (en) 2016-04-06
JPWO2011136276A1 (ja) 2013-07-22

Similar Documents

Publication Publication Date Title
JP5818327B2 (ja) 三次元物体認識用画像データベースの作成方法および作成装置
JP4963216B2 (ja) コンピュータにより実施される、データサンプルのセットについて記述子を作成する方法
US9141871B2 (en) Systems, methods, and software implementing affine-invariant feature detection implementing iterative searching of an affine space
Darom et al. Scale-invariant features for 3-D mesh models
Mian et al. On the repeatability and quality of keypoints for local feature-based 3d object retrieval from cluttered scenes
Bagri et al. A comparative study on feature extraction using texture and shape for content based image retrieval
US9542593B2 (en) Image-based feature detection using edge vectors
Salti et al. A performance evaluation of 3d keypoint detectors
US20110286628A1 (en) Systems and methods for object recognition using a large database
JP5705147B2 (ja) 記述子を用いて３ｄオブジェクトまたはオブジェクトを表す方法
US20120301014A1 (en) Learning to rank local interest points
CN105069457B (zh) 图像识别方法和装置
CN106650580A (zh) 基于图像处理的货架快速清点方法
Salti et al. On the affinity between 3D detectors and descriptors
Mouine et al. Combining leaf salient points and leaf contour descriptions for plant species recognition
CN118351113A (zh) 基于人工智能的微塑料智能识别定位和尺寸计算系统
Wu et al. A vision-based indoor positioning method with high accuracy and efficiency based on self-optimized-ordered visual vocabulary
Tang et al. A GMS-guided approach for 2D feature correspondence selection
Razzaghi et al. A new invariant descriptor for action recognition based on spherical harmonics
KR101306576B1 (ko) 차분 성분을 고려한 조명 변화에 강인한 얼굴 인식 시스템
WO2015178001A1 (ja) 画像照合システム、画像照合方法、およびプログラムを記憶する記録媒体
Kalaiyarasi et al. Enhancing logo matching and recognition using local features
HK1184267B (en) Creation method and creation device of three-dimensional object recognition-use image database
Robert et al. Efficient real-time contour matching
Meenakshi et al. Multi-View Point Panorama Construction With Wide-Baseline Geo-Graphical Images

Legal Events

Date Code Title Description
WWE Wipo information: entry into national phase

Ref document number: 201180021296.X

Country of ref document: CN

121 Ep: the epo has been informed by wipo that ep was designated in this application

Ref document number: 11775057

Country of ref document: EP

Kind code of ref document: A1

WWE Wipo information: entry into national phase

Ref document number: 2012512888

Country of ref document: JP

WWE Wipo information: entry into national phase

Ref document number: 13643284

Country of ref document: US

NENP Non-entry into the national phase

Ref country code: DE

WWE Wipo information: entry into national phase

Ref document number: 2011775057

Country of ref document: EP