WO2010143573A1 - 物体認識用画像データベースの作成方法、作成装置および作成処理プログラム - Google Patents

物体認識用画像データベースの作成方法、作成装置および作成処理プログラム Download PDF

Info

Publication number
WO2010143573A1
WO2010143573A1 PCT/JP2010/059352 JP2010059352W WO2010143573A1 WO 2010143573 A1 WO2010143573 A1 WO 2010143573A1 JP 2010059352 W JP2010059352 W JP 2010059352W WO 2010143573 A1 WO2010143573 A1 WO 2010143573A1
Authority
WO
WIPO (PCT)
Prior art keywords
registered
vector
value
recognition
identifier
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/JP2010/059352
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.)
Osaka Metropolitan University
Original Assignee
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 Osaka Prefecture University PUC filed Critical Osaka Prefecture University PUC
Priority to EP10786104.9A priority Critical patent/EP2442273A4/en
Priority to JP2011518472A priority patent/JP5354507B2/ja
Priority to CN201080035625.1A priority patent/CN102460511B/zh
Priority to US13/376,890 priority patent/US20120084305A1/en
Publication of WO2010143573A1 publication Critical patent/WO2010143573A1/ja
Anticipated expiration legal-status Critical
Ceased legal-status Critical Current

Links

Images

Classifications

    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
    • G06F16/50—Information retrieval; Database structures therefor; File system structures therefor of still image data
    • G06F16/58—Retrieval characterised by using metadata, e.g. metadata not derived from the content or metadata generated manually
    • G06F16/583—Retrieval characterised by using metadata, e.g. metadata not derived from the content or metadata generated manually using metadata automatically derived from the content

Definitions

  • the present invention relates to an object recognition image database creation method, creation apparatus, and creation processing program. More specifically, when there is a set whose elements are data, this is a data structure that associates the value assigned to each data (key) based on that key, and allows data by allowing false positives (False Positive)
  • the present invention relates to a compressed representation of a feature vector using an associative data structure for compressing capacity and its application to specific object recognition.
  • Identified object recognition is a task that recognizes an instance of an object.
  • specific object recognition using a local feature such as SIFT (for example, see Non-Patent Document 1) will be described.
  • the local feature amount is a real-valued vector having several tens to several hundreds of dimensions, and has high discrimination, so that it is suitable for the purpose of identifying a large number of objects.
  • the basic recognition process is a process of collating a local feature obtained from an unknown object with a local feature obtained from a known object.
  • Non-Patent Document 5 scalar quantization
  • selection of feature vectors see, for example, Non-Patent Document 6 and Non-Patent Document 4.
  • scalar quantization see, for example, Non-Patent Document 5
  • selection of feature vectors see, for example, Non-Patent Document 6 and Non-Patent Document 4.
  • the present invention has been made in view of the above circumstances, and provides a value assigned to each “key” as an element of a data set based on the key in order to solve the above-described problems.
  • a method for creating and retrieving a spatially efficient image database using an associative data structure is provided.
  • the associative data structure is a combination of data structures that allow false positives as a price to compress data capacity, that is, to reduce the amount of memory required for data storage and to obtain high space efficiency.
  • the data structure is used to check (search) whether or not a certain key is registered in a state where a large number of keys are registered.
  • the above-mentioned false positives may occur when a search returns a value that is not assigned to that key, or a value may be returned even though the key is not registered That is.
  • the data structure can be said to be a stochastic data structure. In other words, even if there is no guarantee that the correct answer is obtained and an incorrect result may be returned, the probability of returning the incorrect result should be low enough that there is no practical problem.
  • One option is to allow false positives in order to reduce the amount of memory needed to create the database.
  • the present invention provides a feature extraction step of extracting a plurality of feature vectors representing local features of an image from an image of an object to be registered in the object recognition image database; A registration step of registering each feature vector extracted from a certain object so that an identifier pre-assigned to the object can be associated with the data structure with respect to a data structure capable of determining whether or not it has been registered
  • the computer executes each step, and an object of registration is assigned an identifier of n bits (n is a natural number), and the registration step is for zero value registration and one value registration of each bit of the identifier. For the prepared 2 ⁇ n data structures, either one of zero value registration and one value registration for each bit according to the identifier of the object from which each feature vector is extracted.
  • Each of the feature vectors is registered in a data structure, and the image database is configured to perform recognition processing on whether or not the same object is registered when an image of an object is given as a search question.
  • the recognition process extracts a plurality of feature vectors from the search question as a search question vector, checks whether or not a feature vector equivalent to each search question vector is registered in each data structure, and all When a feature vector of the same value is registered for either zero value or 1 value for n bits, an n-bit value corresponding to the value of each registered bit is obtained as a candidate for an identifier, and obtained for each search query vector.
  • Object recognition image database characterized by finding candidate identifiers that match search queries Provides a method of creating.
  • the present invention provides a feature extraction unit that extracts a plurality of feature vectors representing local features of an image from an image of an object to be registered in the object recognition image database, and data
  • a data structure part consisting of a set of data structures that can be determined and whether or not certain data has been registered, and an identifier pre-assigned to each object from each feature vector extracted from a certain object are derived from the feature vector
  • the feature vector is registered in one of the data structures for zero value registration and one value registration of each bit according to the body identifier, and the image database is given an image of an object as a search query Accessed by a recognition device that performs recognition processing of whether or
  • the present invention has a feature extraction process for extracting a plurality of feature vectors representing local features of an image from an image of an object to be registered in the object recognition image database, and data can be registered.
  • a registration process for registering each feature vector extracted from a certain object so that an identifier pre-assigned to the object is associated with the data structure for a data structure that can determine whether or not the data has been registered;
  • the object related to the registration is assigned an identifier of n bits (n is a natural number), and the registration process is prepared for zero value registration and one value registration of each bit of the identifier. For 2 ⁇ n data structures, either one of zero-value registration data and one-value registration data for each bit according to the identifier of the object from which each feature vector is extracted.
  • Each of the feature vectors is registered in a structure, and the image database is processed by the computer or another computer to perform a recognition process as to whether or not the same object is registered when an image of the object is given as a search question. Accessed, the recognition process extracts a plurality of feature vectors from the search question as a search question vector, checks whether a feature vector equivalent to each search question vector is registered in each data structure, and all bits When a feature vector of the same value is registered for either zero value or 1 value for n, an n-bit value corresponding to each registered bit value is obtained as an identifier candidate, and the candidate obtained for each search query vector
  • a database of object recognition images, characterized by finding identifiers that match search queries Provides a processing program.
  • the registration step includes features for 2 ⁇ n data structures prepared for zero value registration and one value registration of each bit of the identifier.
  • the feature vector is registered in one of the data structures for zero value registration and one value registration of each bit, so that the feature vector is for zero value of each bit or 1
  • the identifier value can be associated with the feature vector based on whether or not the data structure is registered in the data structure for the value. Since the data structure compresses the data capacity by allowing false positives, a larger-scale object recognition image database can be realized with the same amount of memory as in the past. As shown in FIG. 9, FIG. 10, FIG. 15, FIG. 16, and the like, which will be described later, the present invention can further reduce the amount of memory when compared with a method of performing an approximate nearest neighbor search using a hash table. It has been experimentally verified.
  • a specific example of what can be applied as the data structure is a Bloom filter
  • a specific example of what can be applied as the associative data structure is a Bloomier filter (Bloomier Filter, For example, see Non-Patent Document 6).
  • the blue mire filter is a data structure known as a technique for associating values assigned to a plurality of keys as elements to be registered based on the keys.
  • an association means a mechanism that allows a value associated with a key to be obtained in a short time by a predetermined data structure when a key is given. It can be said that the value associated with is obtained.
  • a bluemere filter is generally composed of a plurality of bloom filters (m-bit bit array) having a plurality of common hash functions, and each bloom is obtained using a hash value obtained from each hash function when a certain key is given.
  • a value associated with the key can be obtained based on the reference result by referring to the filter. Details thereof will be described later.
  • What is registered in the object recognition image database of the present invention is an image representing an object, and a search question (query) is also given as an image. If an object matching the object represented by the search query image can be searched from the image database, it can be said that the object has been recognized. In such object recognition, it is important to complete the object recognition in a short time and to realize an image database with a small amount of memory. The two are often in a trade-off relationship, but the present invention has a problem of reducing the amount of memory among them. In other words, this is an effective technique for constructing an image database in which a large amount of image data is registered.
  • the above-described effects are the same for the object recognition image database creation apparatus and creation processing program according to the present invention.
  • FIG. 6 is a graph showing the recognition rate of an object when t is changed in the method of the present invention (Experiment 2, 5000 2D object recognition experiment).
  • FIG. 6 is a first graph showing the effectiveness of an error detection blue mia filter in the method of the present invention (55 three-dimensional object recognition experiments).
  • FIG. It is the 2nd graph which shows the effectiveness of an error detection blue mia filter in the method of this invention (recognition experiment of 55 three-dimensional objects).
  • It is a 3rd graph which shows the effectiveness of an error detection blue mia filter in the method of this invention (recognition experiment of 5000 two-dimensional objects).
  • FIG. 11 is a fourth graph showing the effectiveness of an error detection blue mia filter in the method of the present invention (recognition experiment of 5000 two-dimensional objects).
  • FIG. It is the 1st explanatory view explaining the example of database creation processing concerning this invention. It is the 2nd explanatory view explaining the example of database creation processing concerning this invention.
  • each data structure may reduce the capacity of a memory for storing data by allowing false positives.
  • the registration step applies a predetermined rule to obtain a value for error detection related to the identifier, registers the obtained value in the data structure for error detection, and the recognition process
  • the candidate and the value registered in the error detection data structure are collated, and if the two match, the determination result for the search query vector is subject to statistical processing, and if not, the subject is not subject to statistical processing Also good.
  • the registration step obtains an error detection value by applying a predetermined rule to the identifier value, and further registers the obtained value in the error detection data structure.
  • the error detection data structure is It is possible to search for an image related to the search query vector with higher accuracy than when not using it.
  • the error detection value may be composed of at least one bit, and the error detection data structure may be prepared for registering a bit zero value and for registering a single value.
  • the number of bits for which it is determined that the same search query vector is registered in both data structures for zero value and one value registration because of false positive is a predetermined number. May exceed the determination result for the search question vector from the target of statistical processing. In this way, when a value exceeding a predetermined number is obtained as an identifier of an image related to a certain search query vector due to a so-called false positive, the determination result including many erroneous values is excluded from a specific basis. Thus, it is possible to search for an image related to the search query vector with higher accuracy than when the exclusion is not performed.
  • the recognition process gives a predetermined score to an identifier value determined to be related to the search question vector, and there is no identifier determined to be related to the search question vector.
  • the identifier that has obtained the highest score may be determined based on statistical processing on the search question vector extracted from the search question without giving a score to any identifier. In this way, even if the determination result of a plurality of search query vectors is majority processed, so-called voting processing, even if the probability that each individual determination result is correct is not 100%, an appropriate result can be obtained by majority processing. .
  • the data structure may be a Bloom filter.
  • each data structure may have a number m of bits (m is a natural number) constituting the data structure larger than a predetermined maximum number of registered vectors. More preferably, m is determined such that each data structure after each registration vector is registered is in a sparse state that includes moderately zero-valued bits. In this way, it is possible to reduce the probability of erroneous detection of the data structure, that is, the probability of occurrence of false positives. However, if m is made too large, the space efficiency decreases. The designer may determine a reasonable value experimentally or empirically from the balance between the two. The various preferable aspects shown here can also be combined.
  • Non-Patent Document 7 In specific object recognition using local features, reducing the amount of memory is an important issue.
  • Conventional methods for reduction include those that perform vector quantization of feature vectors (see Non-Patent Document 7) and those that perform scalar quantization (see Non-Patent Document 3).
  • the former method of vector quantization reduces the amount of memory by replacing multiple feature vectors with representative vectors called Visual ⁇ Word.
  • Visual ⁇ Word representative vectors
  • the amount of memory is reduced by scalar quantization of each dimension of the feature vector.
  • This method is effective even for large-scale object recognition to some extent, but even if the number of feature vectors is expressed in 1 bit, the amount of memory increases in proportion to the number of feature vectors. There are limits to recognition. For this reason, there is a limit to the method for reducing the capacity of the feature vector itself.
  • the amount of memory is reduced by storing only the pointer to the recording location in the main memory.
  • the amount of memory is reduced by selecting feature vectors effective for recognition. Even with this method, in order to perform large-scale object recognition, there is a limit to the number of feature vectors that can be reduced, and if the number beyond that is reduced, the recognition rate decreases.
  • Noguchi's method is based on PCA-SIFT (for example, Y. Ke and R. Sukthankar: "PCA-SIFT: A more distinctive representation for local image descriptors", Proc. Of CVPR2004, Vol. 2, pp. 506-513 ( This is a specific object recognition method using the 36-dimensional feature vector obtained in 2004).
  • the method of Noguchi et al. Is divided into a database creation process for registering a feature vector in a hash table and a recognition process for recognizing an object based on a voting process using this database.
  • specific processing will be described. 2-1. Create database
  • the index to be registered in the hash table is obtained from the hash function.
  • H size is the size of the hash table.
  • the object ID for the feature vector p is registered in the obtained index.
  • the object ID corresponds to the “identifier” of the present invention.
  • the index of the hash table is obtained in the same manner as the database creation process using the feature vector obtained from the question image by PCA-SIFT. Then, all the object IDs registered in the obtained hash index are voted. This process is performed on all feature vectors obtained from the question image, and finally the object having the largest number of votes is used as the recognition result. Specific processing will be described below.
  • the index of the hash table is obtained from the feature vector obtained from the question image.
  • a threshold value b is provided for the number of dimensions to be processed. Thereby, in the most cases, the number of bit vectors u ′ used for the search is suppressed to 2 b .
  • a plurality of discriminators as shown in FIG. 1 are arranged in series in order to improve processing efficiency.
  • This multi-stage configuration can also be applied to the present invention.
  • the processing when the question image is applied to the recognizer will be specifically described.
  • the question image is recognized by repeating this process.
  • the feature of the recognition method by the multi-stage of the classifier is that, when the stage of the classifier moves, the difference searchability is such that recognition is performed using a bit vector other than the bit vector used for the search in the previous stage. That is. For this reason, even if the discriminator moves to the final stage discriminator, it can be recognized in substantially the same processing time as that using 2 b bit vectors from the beginning. 2-3. Problems of Noguchi's method
  • the present invention uses a data structure that compresses the capacity of data by allowing false positives as a data structure that is much more space efficient than a hash table.
  • An example of a specific configuration of the data structure is a Bloom filter, and an example of a specific configuration of the associative data structure is a blue mire filter. 3. Bloom filter and bluemere filter
  • a Blue Mire filter (see Non-Patent Document 6) applicable as an associative data structure according to the present invention and a Bloom filter as a basis thereof (for example, BH Bloom: “Space / Time Trade-offs in Hash Coding with Allowable Errors ", Commun. ACM, Vol. 13, No. 7, pp. 422-426 (1970)).
  • BH Bloom “Space / Time Trade-offs in Hash Coding with Allowable Errors ", Commun. ACM, Vol. 13, No. 7, pp. 422-426 (1970)
  • Bloom filters are much more space efficient data structures compared to balanced binary search trees and hash tables.
  • This Bloom filter is used to determine whether an element is a member of a data set given a data set and element.
  • This method has the problem that the possibility of false positive (False Positive) that is determined to be a member of a set even though an element is not a member of the data set, or the original from the data set There is a problem that the element cannot be extracted.
  • this method has an advantage that any number of elements can be added to the data set without increasing the amount of memory. Of course, the more elements are added, the higher the possibility of false positives, but the number of elements that can be stored with the same amount of memory is overwhelmingly large compared to balanced binary search trees and hash tables.
  • the bloom filter is used for the compression expression of the feature vector by utilizing the good space efficiency.
  • the discussion proceeds with the elements of the data set as feature vectors.
  • specific processing of the feature vector registration method to the Bloom filter and the feature vector recognition method will be described.
  • FIG. 2 shows a flow of feature vector registration processing.
  • an m bit array is prepared as an empty Bloom filter, and all bits are initialized with 0.
  • m is referred to as “TableSize”.
  • k hash functions are prepared, and a hash value is calculated for each hash function using a feature vector as a key.
  • the obtained hash value is an integer value of 1 to m.
  • a hash value is obtained from each hash function using the feature vector as a key. If all the bits corresponding to the obtained hash value are 1, it is assumed that the feature vector is included in the data set. 3-2. Blue Mia Filter
  • a Bloomier filter is a data structure used to associate a value associated with a registered feature vector by using a plurality of Bloom filters.
  • this method also has the problem that there is a possibility of false positives and the problem that the original feature vector cannot be extracted from the data set, it is overwhelmingly more space efficient than a hash table.
  • this property is used, and the blue mia filter is used for specific object recognition.
  • the operation of the blue mia filter will be described in detail.
  • an object ID used for recognizing a specific object by using the operation of the above-described blue mire filter.
  • the object ID is expressed by n bits, this is realized by preparing two Bloom filters for each bit.
  • N Bloom filters are required, but log 2 N Bloom filters can be obtained by using a Bluemire filter. Can identify an object. 4.
  • the number of feature vectors obtained from all objects whose i-th bit is 0 when the object ID is expressed in bits is the value of M
  • a feature vector is registered for n Bloom filters. For example, when expressing an object ID in 2bit, When expressed in the third object ID "10", 1 bit-th bit string is "1", for 2 bit-th is "0", Y 1 and The feature vector obtained from the object with the object ID 3 is stored in the X 2 Bloom filter. Specific processing will be described below.
  • the bit vector u is created using the d dimension of the feature vector, as in the method of Noguchi et al.
  • the feature vector converted to the bit vector is considered not very effective for recognition and is not registered in the database.
  • the obtained bit vector u is used as a key, and k hash functions are used to determine which bit of the Bloom filter is set to 1.
  • k 8 and the hash function is General Purpose Hash Function Algorithms, [online], searched on June 3, 2009, ⁇ URL: http://www.partow.net/programming/ hashfunctions / index.html # RSHashFunction.>
  • the above processing is performed on all feature vectors to create a database.
  • the original feature vector cannot be extracted from the database.
  • the feature vector can be expressed by compressing the amount of memory considerably rather than storing the original feature vector as it is. . 4-2.
  • the feature vector obtained from the question image is generally different from the feature vector used for database creation for each dimension value. For this reason, in this embodiment as well, in the same way as the method of Noguchi et al., An allowable variation width e of each dimension value is provided to deal with the variation.
  • the i th bit of the object ID is set to 0, and if it exists in the Bloom filter Y i , the i th bit of the object ID is set to 1. If it is not included in both X i and Y i , the feature vector using this bit vector as a key is not registered in the database, and the i-th and subsequent processes are terminated.
  • the process can be terminated at an intermediate stage, so that the recognition process can be performed efficiently.
  • a process for detecting a voting error at the time of voting is also proposed.
  • a bluemear filter for error detection is also created. This is a simple error detector for deciding whether or not to actually vote for an ID obtained by recognition processing using a feature vector obtained from a certain search query image.
  • This error detection blue mia filter is created as follows. First, two Bloom filters P 0 and P 1 are prepared. When the object ID is expressed in 2 bits, a feature vector obtained from an even number of object IDs is registered in P 0 and a feature vector obtained from an odd number of object IDs is registered in P 1 To do.
  • the TableSize of each Bloom filter is given in the same way as Equation (4).
  • the recognition process it is determined using an error detection blue mia filter whether or not to vote for the object with the obtained object ID. At this time, if it is not registered in the error detection blue mia filter, or if it is registered in both, the determined object ID is determined to be an incorrect ID and voting is not performed.
  • the Bloom filter for registering the feature vector is determined.
  • the object ID3 is expressed by 2 bits
  • a bit string of 10 is assigned to the object ID3.
  • the Bloom filter Y 1 that associates the first digit in the bit string with 1 and the second digit in the bit string 0 registers the feature vector Bloom filter X 2 reminds.
  • the object ID expressed in bit column 1 because an odd number appears, it registers the feature vector to the error detection Bloom filter P 1.
  • the feature vector obtained from the object with the object ID 3 is registered in the procedure as shown in FIG.
  • a bit vector is created using the d dimension from the first dimension of the feature vector obtained from the object of object ID3.
  • P 1 (24, -500, 249, 32)
  • P 2 (239, 123, -11, -57)
  • d 3
  • P 1 , P 2 ...
  • u 1 (1, 0, 1)
  • u 2 (1, 1, 0)
  • the feature vectors converted to this bit vector are considered to be not effective for recognition because they are similar, and are used for subsequent processing. Not in.
  • each Bloom filter has all elements 0 (zero). It is.
  • first, k 3 hash values are obtained from the k hash functions described above using the bit vector u 1 as a key. If the obtained hash values are 1, 2, and 4, the first , second , and fourth bits of the Bloom filters Y 1 , X 2 , and P 1 initialized to (00000000) are set to 1. Y 1 , X 2 , and P 1 after u 1 registration are all (11010000) (see FIG. 23A).
  • Bloom filter Y 1 is (11011010).
  • a hash value is obtained for the bit vector u 1 ′ obtained from the feature vector q1 of the search question, since u 1 ′ is the same value as u 1 at the time of registration, hash values 1, 2, and 4 similar to those in the registration process are obtained. Is obtained. Bloom Filter Y 1 's 1 , 2 and 4th bits are all 1's. In this case, q 1 is determined to be registered in the Bloom filter Y 1 .
  • the Bloom filter may be determined to be registered even though it is not registered.
  • q 2 is a feature vector that is not actually registered in the Bloom filter.
  • the hash values obtained from the bit vector u 2 ′ obtained from q 2 are 2, 4, and 5.
  • the i-th bit of the object ID is set to 0.
  • the i-th bit of the object ID is set to 1. If the feature vector is registered in Y 1 and X 2 , the bit string of the object ID is “10”, so the object of ID 3 is voted.
  • the Bloom filter has a false positive and it is determined that a feature vector is registered in both X i and Y i .
  • the present invention tries both possibilities. That is, for the search query feature vector, as shown in FIG. 23, voting is performed for both an object whose i-th bit is 0 and an object whose object ID is 1. For example, if it is determined as a result of the search processing that a search query feature vector has been registered in X 1 , Y 1 , and X 2 , two ID candidates of object ID bit strings 00 and 10 are prepared. Then, an object ID that may be voted on is determined by referring to the error detection Bloom filter.
  • the above search process and voting process are performed on all feature vectors obtained from the search query image.
  • the object having the largest number of votes is finally set as the recognition result.
  • the votes may be weighted. For example, when the number of feature vector object ID is registered in the database are extracted from the object i is N i number may be voting with a weight of 1 / ⁇ N i to vote for the object ID .
  • FIG. 3 shows an example of a three-dimensional object used in this experiment.
  • images taken by rotating an object every 5 ° with a web camera from an angle of 15 ° and 30 ° upward from the front in front of the object were used.
  • the webcam is manufactured by Logitech Co., Ltd., product type name Qcam (registered trademark) Pro 9000, resolution: 640480.
  • database creation images 36 images with rotation angles of 0 °, 10 °,..., 350 ° ⁇ 108 in 3 directions were used per object, and the remaining images were used as search query images.
  • the number of feature vectors obtained from the database creation image is about 1.2 million.
  • FIG. An example is shown in FIG. During collection, images with a size of 600 ⁇ 600 pixels or less were excluded, and the image was reduced so that the long side of the image was 640 pixels or less. Also excluded are images that have 100 or fewer feature vectors. The number of feature vectors obtained from the database creation image is about 10 million.
  • Search query images were prepared as follows. First, a total of 500 images in the database, 100 images collected from Google Image Search, 200 images obtained from the PCA-SIFT site, and 200 images collected from Flickr, were randomly selected. Selected. Next, these images were printed on A4 paper using a color laser printer (product name: C5200n, manufactured by Oki Data Corporation), and the camera (product name: EOS Kiss Digital, manufactured by Canon Inc., 6.3 million pixels). , And attached lens model name: EF-S (18-55mm) USM).
  • FIG. 5 An example of the photographed image is shown in FIG. As shown in FIG. 5, the angle ⁇ of the optical axis of the camera with respect to the paper surface was changed to 90 °, 75 °, and 60 ° in an arrangement in which the entire paper surface was captured. A part of the paper was photographed at an angle of 90 °. As a result, a total of four images were obtained on one sheet of paper. Furthermore, the captured image was reduced to 512 x 341 pixels, and the feature vector was obtained by PCA-SIFT.
  • the feature vector storage capacity a and the number of dimensions t for dealing with false positives were also changed to examine the object recognition rate.
  • the horizontal axis shows the recognition rate, and the vertical axis shows the processing time.
  • Fig. 8 shows an example of comparison of recognition rates when b is changed.
  • the method of the present invention requires a longer processing time for recognition of a single sheet than the method of Noguchi et al., Some results are obtained with a slightly better object recognition rate.
  • the method of Noguchi et al. It is possible to vote just by searching the hash table once for one search question vector q.
  • 2n Bloom filters are used as the cause of the recognition process taking time. It is mentioned that you can't vote without searching.
  • Fig. 14 shows an example of comparison of recognition rates when b is changed.
  • FIG. 15 shows the result of comparing the amount of memory required for the recognition processing when the parameter c is changed between the method of changing the parameter a of the method of the present invention and the method of Noguchi et al.
  • the horizontal axis shows the parameter c
  • the vertical axis shows the memory amount.
  • FIG. 17 shows the experimental results.
  • the horizontal axis shows the recognition rate
  • the vertical axis shows the average processing time taken to recognize one sheet. From the experimental results, when the amount of memory to be used is almost the same, the method of the present invention takes much processing time compared with the comparative method, but the recognition rate can be considerably improved by the parameters. From this, it can be said that the method of the present invention can efficiently compress the feature vector representation.
  • the present invention has proposed a technique using a Blue Mia filter that is much more space efficient than a hash table or the like as a technique for reducing the amount of memory without calculating feature vector distances.
  • a technique using a Blue Mia filter that is much more space efficient than a hash table or the like as a technique for reducing the amount of memory without calculating feature vector distances.
  • the method using a hash table was compared with the present invention, and its effectiveness was verified.

Landscapes

  • Engineering & Computer Science (AREA)
  • Library & Information Science (AREA)
  • Theoretical Computer Science (AREA)
  • Data Mining & Analysis (AREA)
  • Databases & Information Systems (AREA)
  • Physics & Mathematics (AREA)
  • General Engineering & Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Image Analysis (AREA)
  • Information Retrieval, Db Structures And Fs Structures Therefor (AREA)

Abstract

　確率的な連想データ構造を用いた、空間的効率の良い画像データベースの作成手法および検索手法を提供する。　画像データベースに登録されるべき画像であって物体を表す画像から、その画像の各所の局所的な特徴をそれぞれ表現する１以上の特徴ベクトルを局所特徴量としてそれぞれ抽出する特徴抽出工程と、登録されるべき要素としての複数のキーにそれぞれ割り当てられた値をそのキーに基づいて連想させる連想データ構造であって、偽陽性を許容することによりデータの容量を圧縮する圧縮データ構造を構成要素として含む連想データ構造を用い、各特徴ベクトルをキーとして前記連想データ構造に登録する登録工程とを備える。

Description

物体認識用画像データベースの作成方法、作成装置および作成処理プログラム
　この発明は、物体認識用画像データベースの作成方法、作成装置および作成処理プログラムに関する。より詳細には、データを要素とする集合があるとき各データ（キー）に割り当てられた値をそのキーに基づいて連想させるデータ構造であって、偽陽性(False Positive)を許容することによりデータ容量を圧縮する連想データ構造を用いてなる、特徴ベクトルの圧縮表現とその特定物体認識への応用に関する。
　特定物体認識とは、物体のインスタンスを認識するタスクである。この明細書では、SIFT（例えば、非特許文献１参照）などの局所特徴量を用いた特定物体認識について述べる。
　我々の周囲には物体のインスタンスが無数にあるため、特定物体認識を真に実用的なものとするには、識別できる物体数の大規模化が必須である。局所特徴量は数十から数百の次元を持つ実数値ベクトルであり、高い識別性を持つため、多数の物体を識別する目的に適している。認識処理の基本は、未知の物体から得た局所特徴量と既知の物体から得た局所特徴量を照合する処理である。特徴ベクトルの照合は最近傍探索によって容易に実現できるものの、その大規模化には、まだいくつかの障害を乗り越える必要がある。最も重要な障害は、処理速度とメモリ量に関するものである。
　幸い、処理速度については、これまでに有効な手法が提案されている。その中には、k-d木などの木構造に基づくもの（例えば、前記非特許文献１参照）、ハッシュに基づくもの（例えば、特許文献１、非特許文献２参照）などがある。これらの手法では、近似最近傍探索を用いることによって、処理速度を大幅に改善している。
　一方、メモリ量の問題については十分な解決策は得られていない。局所特徴量は画像あたり数百から数千個にもなるため、物体数が大規模になるとその記録には膨大なメモリが必要となる。
　これまでに、特徴ベクトルをVisual Word （例えば、非特許文献３参照）と呼ばれる代表ベクトルに置換することで必要なメモリ量を削減する手法が提案されている。この手法は、画像に写っている物体のクラス（例えば、一般的な「車」というカテゴリー）を認識する「一般物体認識」には有効な手法といえる。しかし、画像中の物体のインスタンス（例えば、前者の「車」というカテゴリーの中の特定のモデル名）まで認識する「特定物体認識」への適合性は高いとはいえない。大規模な特定物体認識を行うためには、Visual Wordの数を多くしなければならない。高い認識率を得るためには、一つのVisual Wordに2～3個の特徴ベクトルを対応付けるのが限界でありそれより多くの特徴ベクトルを一つのVisual Wordで代表させるようにすると認識率が低下してしまう（例えば、非特許文献４参照）。特定物体認識におけるメモリ量削減の決め手にはなり得ない。
　この他のメモリ量削減手法として、スカラ量子化（例えば、非特許文献５参照）や特徴ベクトルの取捨選択（例えば、非特許文献６、前記非特許文献４参照）などがある。しかし、上記の近似最近傍探索を用いた照合では、特徴ベクトル間の距離を計算する必要があるため、いずれにせよ個々の特徴ベクトルを記録しなければならない。従って、記録する特徴ベクトル数に応じたメモリ量が必要となり、その削減には限界が生じる。
　また、この問題を解決する一つの考え方は、照合に際して距離計算を放棄することである。これにより特徴ベクトルの記録も不要となるため、メモリ量の大幅な削減が可能となる。実際、特徴ベクトルをハッシュ表に登録しておき、それを検索することによって認識する手法が提案されている（例えば、特許文献１、前記非特許文献２参照）。この手法では、特徴ベクトルの照合を、距離あるいは類似度という量的な概念に基づく類似検索ではなく、ハッシュ関数の値（ハッシュ値）が同じかどうかという一致検索によって実現している。ハッシュ表には特徴ベクトルの有無が記録されるだけなので、メモリ量の大幅な削減が可能となる。
国際公開第2008/026414号パンフレット
D. Lowe: "Distinctive Image Features from Scale-Invariant Keypoints", International Journal of Computer Vision, Vol. 60, No. 2, pp. 91-110 (2004). 野口和人, 黄瀬浩一, 岩村雅一："近似最近傍探索の多段階化による物体の高速認識", 画像の認識・理解シンポジウム(MIRU2007)論文集、OS-B2-02, pp. 111-118 (2007). K. Kise, K. Noguchi and M. Iwamura: "Memory Efficient Recognition of Specific Objects with Local Features", Proc. of the 19th International Conference of Pattern Recognition (ICPR2008) WeAT3.1 (2008). 井上勝文, 三宅弘志, 黄瀬浩一："局所記述子に基づく3次元物体認識のためのメモリ削減－局所記述子の取捨選択によるアプローチ－", 画像の認識・理解シンポジウム(MIRU2008)論文集、OS15-3, pp. 363-370 (2008). 本道貴行, 黄瀬浩一："特定物体認識のためのデータベース容量削減法の検討～局所特徴量の量子化と取捨選択～", 電子情報通信学会技術研究報告、Vol. 108，No. 484，PRMU2008-265, pp. 171-176 (2009). B. Chazelle, J. Kilian, R. Rubinfeld and A. Tal: "The Bloomier Filter: An Efficient Data Structure for Static Support Lookup Table", Proc. 15th Annual ACM-SIAM SODA, pp. 30-39 (2004).
　ところが、この手法にもまだメモリ量削減の余地がある。正しい認識のためには、類似した特徴ベクトルが同じハッシュ値を持つようにしなければならない。ところが、これによって、ハッシュ表に記録される特徴ベクトルに偏りが生じる。その結果、ハッシュ表の大部分には何も記録されず、空間効率、即ち、メモリ空間のうちで有効利用されるメモリ領域の割合が悪化する。
　この発明は、以上のような事情を考慮してなされたものであって、前述の課題を解決するため、データ集合の要素としての「キー」にそれぞれ割り当てられた値をそのキーに基づいて提供する連想データ構造を用いた、空間的効率の良い画像データベースの作成手法および検索手法を提供する。前記連想データ構造は、データ容量の圧縮、即ち、データの格納に必要なメモリ量を削減し高い空間効率を得る代償として偽陽性を許容するデータ構造を組み合わせてなる。前記データ構造は、多数のキーが登録されている状態で、あるキーが登録されているか否かを調べる（検索する）ために用いられる。前述の偽陽性は、検索を行うとそのキーに割り当てられていない値が返される場合があったり、そのキーが登録されていないにもかかわらず値が返されたりすることが起こることがあり得ることである。その意味で、前記データ構造は、確率的なデータ構造といえる。つまり、正解が得られる保証がなく誤った結果が返されることがあっても、誤った結果を返す確率が実用上支障のない程度に低ければよいとするのである。データベースの作成に要するメモリ量を抑制するために、偽陽性を許容することも一つの選択肢である。
　上記のハッシュ表を用いる代わりに前記データ構造を用いて、特徴ベクトルが記録されているかどうかを検索できる。大きな違いは、記録されていない特徴ベクトルを誤って検出するという偽陽性が生じるかどうかにある。ハッシュ表を用いる手法では偽陽性は生じ得ない。一方、前記データ構造を用いる手法では、一定の偽陽性を容認することの引き替えに、高い空間効率を得ることが可能となる。
　この発明は、物体認識用画像データベースに登録されるべき物体が撮影された画像から、その画像の局所的特徴を表す複数の特徴ベクトルを抽出する特徴抽出工程と、データを登録できかつあるデータが登録済か否かを判定し得るデータ構造に対し、ある物体から抽出された各特徴ベクトルを、その物体に予め割り当てられた識別子が前記特徴ベクトルから連想されるように登録する登録工程とを備え、各工程をコンピュータが実行し、前記登録に係る物体は、ｎビット（ｎは自然数）の識別子が割り当てられ、前記登録工程は、前記識別子の各ビットのゼロ値登録用と１値登録用として用意された２×ｎ個の前記データ構造に対し、各特徴ベクトルが抽出された物体の識別子に応じて各ビットのゼロ値登録用と１値登録用の何れか一方のデータ構造に前記特徴ベクトルをそれぞれ登録し、前記画像データベースは、検索質問としてある物体の画像が与えられたとき同じ物体が登録されているか否かの認識処理を行うべく、前記コンピュータまたは他のコンピュータによってアクセスされ、前記認識処理は、前記検索質問から複数の特徴ベクトルを検索質問ベクトルとして抽出し、各検索質問ベクトルと同値の特徴ベクトルが各データ構造に登録されているか否かを調べ、すべてのビットについてゼロ値または１値のいずれかに同値の特徴ベクトルが登録されているときは登録された各ビットの値に応じたｎビット値を識別子の候補として得、各検索質問ベクトルにつき得られた候補を統計処理して検索質問に適合する識別子を見出すことを特徴とする物体認識用画像データベースの作成方法を提供する。
　また、異なる観点から、この発明は、物体認識用画像データベースに登録されるべき物体が撮影された画像から、その画像の局所的特徴を表す複数の特徴ベクトルを抽出する特徴抽出部と、データを登録できかつあるデータが登録済か否かを判定し得るデータ構造体の集合からなるデータ構造部と、ある物体から抽出された各特徴ベクトルからその物体に予め割り当てられた識別子が前記特徴ベクトルから連想されるように前記特徴ベクトルを前記データ構造部に登録する登録部とを備え、前記登録に係る物体は、ｎビット（ｎは自然数）の識別子が割り当てられ、前記データ構造部は、前記識別子の各ビットのゼロ値登録用および１値登録用として２×ｎ個のデータ構造体を少なくとも有し、前記登録部は、各特徴ベクトルが抽出された物体の識別子に応じて各ビットのゼロ値登録用と１値登録用の何れか一方のデータ構造に前記特徴ベクトルをそれぞれ登録し、前記画像データベースは、検索質問としてある物体の画像が与えられたとき同じ物体が登録されているか否かの認識処理を行う認識装置によってアクセスされ、前記認識装置は、前記検索質問から複数の特徴ベクトルを検索質問ベクトルとして抽出し、各検索質問ベクトルと同値の特徴ベクトルが各データ構造に登録されているか否かを調べ、すべてのビットについてゼロ値または１値のいずれかに同値の特徴ベクトルが登録されているときは登録された各ビットの値に応じたｎビット値を識別子の候補として得、各検索質問ベクトルにつき得られた候補を統計処理して検索質問に適合する識別子を見出すことを特徴とする物体認識用画像データベースの作成装置を提供する。
　さらに、この発明は、物体認識用画像データベースに登録されるべき物体が撮影された画像から、その画像の局所的特徴を表す複数の特徴ベクトルを抽出する特徴抽出処理と、データを登録できかつあるデータが登録済か否かを判定し得るデータ構造に対し、ある物体から抽出された各特徴ベクトルを、その物体に予め割り当てられた識別子が前記特徴ベクトルから連想されるように登録する登録処理とをコンピュータに実行させ、前記登録に係る物体は、ｎビット（ｎは自然数）の識別子が割り当てられ、前記登録処理は、前記識別子の各ビットのゼロ値登録用と１値登録用として用意された２×ｎ個の前記データ構造に対し、各特徴ベクトルが抽出された物体の識別子に応じて各ビットのゼロ値登録用と１値登録用の何れか一方のデータ構造に前記特徴ベクトルをそれぞれ登録し、前記画像データベースは、検索質問としてある物体の画像が与えられたとき同じ物体が登録されているか否かの認識処理を行うべく、前記コンピュータまたは他のコンピュータによってアクセスされ、前記認識処理は、前記検索質問から複数の特徴ベクトルを検索質問ベクトルとして抽出し、各検索質問ベクトルと同値の特徴ベクトルが各データ構造に登録されているか否かを調べ、すべてのビットについてゼロ値または１値のいずれかに同値の特徴ベクトルが登録されているときは登録された各ビットの値に応じたｎビット値を識別子の候補として得、各検索質問ベクトルにつき得られた候補を統計処理して検索質問に適合する識別子を見出すことを特徴とする物体認識用画像データベースの作成処理プログラムを提供する。
　この発明の物体認識用画像データベースの作成方法において、前記登録工程は、前記識別子の各ビットのゼロ値登録用と１値登録用として用意された２×ｎ個の前記データ構造に対し、各特徴ベクトルが抽出された物体の識別子に応じて各ビットのゼロ値登録用と１値登録用の何れか一方のデータ構造に前記特徴ベクトルをそれぞれ登録ので、特徴ベクトルが各ビットのゼロ値用または１値用のデータ構造に登録されているか否か、いずれのデータ構造に登録されているかに基づいてその特徴ベクトルから識別子の値を連想することができる。前記データ構造は、偽陽性を許容することによりデータ容量を圧縮するものであるから、従来と同じメモリ量でより大規模な物体認識用画像データベース実現することができる。後述する図９、図１０、図１５、図１６などに示すように、本願発明は、ハッシュ表を用いて近似最近傍探索を行う手法と比較した場合に、より一層メモリ量の削減が可能であることが実験的に検証されている。
　この発明において、前記データ構造として適用可能なものの具体的な一例は、ブルーム・フィルタ（Bloom Filter）であり、前記連想データ構造として適用可能なものの具体的な一例は、ブルーミア・フィルタ（Bloomier Filter、例えば、前記非特許文献６参照）である。ブルーミア・フィルタは、登録されるべき要素としての複数のキーにそれぞれ割り当てられた値をそのキーに基づいて連想させるための手法として知られたデータ構造である。ここで、連想とは、あるキーが与えられたときに、所定のデータ構造によりそのキーに対応付けられた値を短時間で得ることのできる仕組みを意味し、連想するとは、その仕組みによりキーに対応付けられた値を得ることといえる。ブルーミア・フィルタは、一般に複数の共通なハッシュ関数を有する複数のブルーム・フィルタ（ｍビットのビット配列）で構成され、あるキーが与えられたとき各ハッシュ関数から得られるハッシュ値を用いて各ブルーム・フィルタを参照し、参照結果に基づいて前記キーに対応付けられた値を得ることができる。その詳細は後述する。
　この発明の物体認識用画像データベースに登録されるものは、物体を表す画像であり、検索質問（クエリー）も画像として与えられる。検索質問の画像が表す物体と一致する物体を前記画像データベースから検索できれば、その物体が認識されたといえる。
　このような物体認識では、短時間のうちに物体認識が完了すること、および、少ないメモリ量で画像データベースを実現することが重要である。両者は、しばしばトレードオフの関係にあるが、この発明は、どちらかといえば、それらのうちメモリ量の削減に課題の重点がある。即ち、多量の画像データが登録される画像データベースを構築するときに有効な手法である。
　以上の作用効果は、この発明による物体認識用画像データベースの作成装置および作成処理プログラムについても同様である。
従来の物体認識において認識時間を短縮するため識別器を直列に多段階化した構成を示す説明図である。 この発明に係るブルーム・フィルタへの登録処理の流れを示す説明図である。 この発明の実験例で用いた3次元物体の例を示す説明図である。 この発明の実験例で用いた2次元物体の例を示す説明図である。 この発明の実験例で検索質問として用いた画像であって、前記2次元物体の画像をみる視点の角度を変えて撮影した画像の様子を示す説明図である。 この発明の手法と比較例である野口らの手法の各種パラメータを変えたときの物体の認識率を示す第１のグラフである（実験1、55個の3次元物体の認識実験）。 この発明の手法と比較例である野口らの手法の各種パラメータを変えたときの物体の認識率を示す第２のグラフである（実験1、55個の3次元物体の認識実験）。 比較例である野口らの手法の各種パラメータを変えたときの物体の認識率を示す第３のグラフである（実験1、55個の3次元物体の認識実験）。 この発明の手法と比較例としての野口らの手法とで、パラメータcを変化させたとき、認識処理に必要なメモリ量を比較した結果を示す第１のグラフである（実験1、55個の3次元物体の認識実験）。 この発明の手法と比較例としての野口らの手法とで、パラメータcを変化させたとき、認識処理に必要なメモリ量を比較した結果を示す第２のグラフである（実験1、55個の3次元物体の認識実験）。 この発明の手法で、パラメータtを変化させたとき、認識率を示すグラフである（実験1、55個の3次元物体の認識実験）。 この発明の手法と比較例である野口らの手法の各種パラメータを変えたときの物体の認識率を示す第１のグラフである（実験2、5000個の2次元物体の認識実験）。 この発明の手法と比較例である野口らの手法の各種パラメータを変えたときの物体の認識率を示す第２のグラフである（実験2、5000個の2次元物体の認識実験）。 比較例である野口らの手法の各種パラメータを変えたときの物体の認識率を示す第３のグラフである（実験2、5000個の2次元物体の認識実験）。 この発明の手法と比較例としての野口らの手法とで、パラメータcを変化させたとき、認識処理に必要なメモリ量を比較した結果を示す第１のグラフである（実験2、5000個の2次元物体の認識実験）。 この発明の手法と比較例としての野口らの手法とで、パラメータcを変化させたとき、認識処理に必要なメモリ量を比較した結果を示す第２のグラフである（実験2、5000個の2次元物体の認識実験）。 同程度のメモリが使える状況で、この発明の手法、比較例である野口らの手法のd=28、d=24についてパラメータb,cを変化させたときの認識率と処理時間を示すグラフである（実験2、5000個の2次元物体の認識実験）。 この発明の手法において、tを変化させたときの物体の認識率を示すグラフである（実験2、5000個の2次元物体の認識実験）。 この発明の手法において、誤り検出ブルーミア・フィルタの有効性を示す第１のグラフである（55個の3次元物体の認識実験）。 この発明の手法において、誤り検出ブルーミア・フィルタの有効性を示す第２のグラフである（55個の3次元物体の認識実験）。 この発明の手法において、誤り検出ブルーミア・フィルタの有効性を示す第３のグラフである（5000個の2次元物体の認識実験）。 この発明の手法において、誤り検出ブルーミア・フィルタの有効性を示す第４のグラフである（5000個の2次元物体の認識実験）。 この発明に係るデータベース作成処理の具体例を説明する第１の説明図である。 この発明に係るデータベース作成処理の具体例を説明する第２の説明図である。
　以下、この発明の好ましい態様について説明する。
　この発明の物体認識用画像データベースの作成方法において、各データ構造は、偽陽性を許容することによりデータを格納するメモリの容量を削減するものであってもよい。
　前記登録工程は、所定の規則を適用して前記識別子に係る誤り検出用の値を得、得られた値を前記誤り検出用のデータ構造に登録し、前記認識処理は、得られた識別子の候補と前記誤り検出用データ構造に登録された値とを照合し、両者が一致する場合は前記検索質問ベクトルについての判定結果を統計処理の対象とし、一致しない場合は統計処理の対象としなくてもよい。このようにすれば、前記登録工程は、前記識別子の値に所定の規則を適用して誤り検出用の値を得、得られた値を前記誤り検出用データ構造にさらに登録するので、検索質問ベクトルがあるビット桁のゼロ値にも１値にも登録されていると判断された場合にも、誤り検出用データ構造に登録された値との整合性を判定し、誤り検出用データ構造を用いない場合よりも高い精度で検索質問ベクトルに関連する画像を検索することができる。
　また、前記誤り検出用の値が少なくとも１ビットからなり、前記誤り検出用データ構造は、ビットのゼロ値登録用と１値登録用としてデータ構造が用意されてなるものでもよい。このようにすれば、２×ｎ個の前記データ構造を用いて識別子を連想する連想データ構造が構成されるところ、さらに前記データ構造を追加することにより検出用データ構造を構成することができる。
　また、前記認識処理は、偽陽性のために、ゼロ値および１値登録用のいずれのデータ構造にも同一の検索質問ベクトルが登録されていると判断されるビットの数が予め定められた数を超える場合、その検索質問ベクトルについての判定結果を統計処理の対象から除外してもよい。このようにすれば、いわゆる偽陽性によりある検索質問ベクトルに関連する画像の識別子として所定の数を超える値が得られた場合、誤った値を多数含むその判断結果を特定の基礎から除外することにより、前記除外を行わない場合よりも高い精度で検索質問ベクトルに関連する画像を検索することができる。
　さらにまた、前記認識処理は、前記検索質問ベクトルに関連があると判定される識別子の値に対して所定の得点を与え、前記検索質問ベクトルに関連があると判定される識別子が存しない場合はいずれの識別子にも得点を与えず、前記検索質問から抽出される検索質問ベクトルについての統計処理に基づき最多得点を得た識別子を決定してもよい。このようにすれば、複数の検索質問ベクトルの判断結果を多数決処理する、いわゆる投票処理により、個々の判断結果が正しい確率が100％でなくても、多数決処理により妥当な結果を得ることができる。
　前記データ構造は、ブルーム・フィルタであってもよい。
　また、前述の作成方法および検索方法において、各データ構造は、それを構成するビットの数ｍ（ｍは自然数）が予め定められた登録ベクトルの最大数よりも大きくてもよい。より好ましくは、ｍは、各登録ベクトルが登録された後の各データ構造が、適度にゼロ値のビットを含む疎な状態になるように決定される。このようにすれば、データ構造の誤検出の確率、即ち、偽陽性の発生確率を低い値にすることができる。ただし、あまりmを大きくしすぎると空間効率が低下する。設計者は、両者の兼ね合いから実験的にあるいは経験的に妥当な値を決定すればよい。
　ここで示した種々の好ましい態様は、それら複数を組み合わせることもできる。
　以下、図面を用いてこの発明をさらに詳述する。なお、以下の説明は、すべての点で例示であって、この発明を限定するものと解されるべきではない。
　この発明の詳細な説明に先立ち、その技術的意義を把握しやすくするために関連研究について、少し詳しく説明しておく。
　1. 関連研究について
　局所特徴量を用いた特定物体認識では、メモリ量の削減が重要な課題である。削減の従来手法には、特徴ベクトルのベクトル量子化を行うもの（前記非特許文献７参照）や、スカラ量子化を行うもの（前記非特許文献３参照）がある。
　前者の、ベクトル量子化をする手法では、複数の特徴ベクトルをVisual Wordと呼ばれる代表ベクトルに置き換えることでメモリ量を削減している。しかし大規模な認識を行うためには、一つのVisual Wordに2～3個の特徴ベクトルを対応付けるのが限度であり、それ以上の数を一つのVisual Wordに対応付けると認識率が低下することが報告されている（前記非特許文献５参照）。
　一方、後者のスカラ量子化する手法では、特徴ベクトルの各次元をスカラ量子化することでメモリ量を削減している。この手法では、ある程度大規模な物体認識でも有効であるが、特徴ベクトルの数を1 bitで表現したとしても、特徴ベクトルの数に比例してメモリ量が増加するため、更なる大規模な物体認識を行うには限界がある。このため、特徴ベクトルそのものの容量を削減する手法には限界がある。
　特徴ベクトル自体の容量を削減する以外のアプローチには、主記憶ではなく補助記憶を利用する手法がある（例えば、F. Fraundorfer, H. Stewenius and D. Nister: "A Binning Scheme for Fast Hard Drive Based Image Search", Proc. of CVPR2007, pp. 1-6 (2007)参照。また、姫井教考, 和田俊和："B+木を用いた補助記憶装置上での近似最近傍探索", 電子情報通信学会技術研究報告、Vol. 108，No. 484，PRMU2008-273, pp. 223-228 (2009)参照）。その他、データベースに登録する特徴ベクトルをサンプリングする手法（例えば、前記非特許文献５、４参照）がある。
　補助記憶を利用する手法では、記録している場所へのポインタのみを主記憶に保存することでメモリ量を削減している。この手法では、かなり大規模な物体認識を行えるが、認識処理に時間がかかるという問題点が生じる。
　特徴ベクトルをサンプリングする手法では、認識に有効な特徴ベクトルを取捨選択することによりメモリ量を削減している。この手法でも、大規模な物体認識を行うためには、削減できる特徴ベクトルの数に限界があり、それ以上の数を削減すると認識率が低下してしまう。
　上に述べたような手法では、特徴ベクトルの距離を計算するため、どの手法でも個々の特徴ベクトル自体を記録する必要があり、認識に必要なメモリ量を削減するには限界がある。
　この問題を解決するための一つのアプローチとして、特徴ベクトルの距離計算を放棄することが考えられる。このような考えに基づいた手法として、ハッシュ表を用いた手法（前記特許文献１、非特許文献２参照）が提案されている。しかし、この手法にも問題点があり、ハッシュ表に登録される特徴ベクトルに偏りがあり、ハッシュ表の大部分が何も記録されず、空間効率が悪い。そこでこの発明では、特徴ベクトルの距離計算を行わないという考えに基づき、ハッシュ表と比べてはるかに空間効率の良いブルーミア・フィルタを用い、メモリ量を削減する手法を提案する。
　2. 野口らの手法
　本節では、この発明の基礎となる野口らの手法（前記特許文献１、非特許文献２参照）について説明する。野口らの手法は、PCA-SIFT（例えば、Y. Ke and R. Sukthankar: "PCA-SIFT:A more distinctive representation for local image descriptors", Proc. of CVPR2004, Vol. 2, pp. 506-513 (2004)参照）で求めた36次元の特徴ベクトルを用いる特定物体認識手法である。野口らの手法は、ハッシュ表に特徴ベクトルを登録するデータベース作成処理と、このデータベースを用い、投票処理に基づいて物体を認識する認識処理の二つに分かれる。以下に、具体的な処理について説明する。
　2-1. データベース作成
　本節では、野口らの手法のデータベース作成処理について説明する。野口らの手法ではまず、特徴ベクトルpの第1次元から第d次元(d≦36)までをとり、p'=(p1, p2, …, pd)を作成する。次にこのベクトルp'を用い、
Figure JPOXMLDOC01-appb-M000001
 によって各次元を２値化したビットベクトル u=(u1,…,ud)を作成する、そして、
Figure JPOXMLDOC01-appb-M000002
というハッシュ関数より、ハッシュ表に登録するためのインデックスを求める。ここで、Hsizeは、ハッシュ表のサイズである。求まったインデックスに、特徴ベクトルpに対する物体IDを登録する。ここで、物体IDは、この発明の「識別子」に対応する。
　野口らの手法では、特徴ベクトルの登録時に衝突が生じた場合、リストとして特徴ベクトルを登録していく。但し、計算コストの削減のために、リスト長に閾値cを設け、リスト長がcよりも長くなる場合、リスト全体をハッシュ表から削除し、以後の登録を禁止する。これは、同じハッシュ値を持つ特徴ベクトルは互いに類似しているため、物体認識にあまり寄与しないという考えに基づく。以上の処理を全ての特徴ベクトルに対して行い、データベースを作成する。
　2-2. 認識処理
　野口らの手法では、質問画像からPCA-SIFTで求めた特徴ベクトルを用い、データベース作成処理と同様に、ハッシュ表のインデックスを求める。そして、求めたハッシュインデックスに登録されている物体ID全てに投票を行う。この処理を、質問画像から得られる特徴ベクトル全てに対して行い、最終的に最も得票数が多い物体を認識結果とする。以下に具体的な処理について説明する。
　まず、質問画像から得られる特徴ベクトルから、ハッシュ表のインデックスを求める。このとき、野口らの手法で用いるハッシュ関数の性質より、次のような問題が発生する。検索質問画像とデータベースの画像が全く同じになるということはほとんどないため、質問画像から得られる特徴ベクトルは、各次元の値がデータベース作成に用いる特徴ベクトルと異なったものとなる。これが原因で異なったビットベクトルに変換されてしまうと、真に対応する物体IDをハッシュ表より検索することができなくなる。そこで、この問題に対処するために、各次元の値に、許容変動幅eを設ける。具体的に説明すると、検索質問となる特徴ベクトル q=(q1, q2, …, qd)において、
Figure JPOXMLDOC01-appb-M000003
 を満たす次元jに対して、ujだけではなく
Figure JPOXMLDOC01-appb-M000004
も用いて特徴ベクトルを検索する。例を示すと、ビットベクトル u=(1, 0, 0, 1)の第3次元目がこの処理の対象であった場合、u'=(1, 0, 1, 1)も用いて検索する。しかし、この処理を全ての次元に対して行うと、処理時間が膨大になってしまうため、処理の対象とする次元数に閾値bを設ける。これにより、最も多い場合で、検索に用いるビットベクトルu'の数を2b個に抑えている。
Figure JPOXMLDOC01-appb-M000005
 となる次元数がb個より多くなる場合、次元のインデックスの大きいものからb個採用する。
　以上の処理を行うことで、ハッシュ表に登録されている物体IDに投票を行い、最も得票数の多い物体を認識結果とする。
　野口らの手法では、処理を効率化するために図１に示すような複数の識別器を直列に並べた構成とする。この多段階化の構成は、本願発明にも適用可能である。第s段では、b = s-1とした識別器を用いる。質問画像をこの認識器にかけた場合の処理について具体的に説明する。まず第1段では、b=0としたときのビットベクトルを用いて認識する。このとき、得票数が一位の物体と他の物体との得票数の差が十分に大きければ、この時点で得票数一位の物体を認識結果として出力する。十分な得票数差が得られなければ、第2段の識別器に移り、b=1としたときのビットベクトルを用いて認識する。この処理を繰り返すことにより質問画像を認識する。この識別器の多段階化による認識手法の特徴は、識別器の段が移ったとき、前の段で検索に用いられたビットベクトル以外のビットベクトルを用いて認識を行うという、差分探索性があることである。このため、最終段の識別器まで移ったとしても、最初から2b個のビットベクトルを用いて認識するのとほぼ同じ処理時間で認識できる。
　2-3. 野口らの手法の課題
　野口らの手法では、認識率を確保するために、ビットベクトルの次元dの値を大きくする必要がある。しかし、dの値を大きくすればハッシュ表の大きさも指数的に増加する。
またHsize = 2dとした予備実験により、約一千万個のPCA-SIFT特徴ベクトルを野口らの手法でハッシュ表にマッピングしてみたところ、d=24のとき65%以上、d=28のとき96%以上のハッシュインデックスが、一つの特徴ベクトルにも対応しない、またはリストが削除された状態となっていることが分かった。以上から、野口らの手法には、ハッシュ表の空間効率の観点から、なお改善の余地があるといえる。
　この課題に対処すべく、この発明ではハッシュ表と比べると、はるかに空間効率の良いデータ構造として、偽陽性を許容することによりデータの容量を圧縮するデータ構造を用いることにした。前記データ構造の具体的な構成の一例は、ブルーム・フィルタであり、前記連想データ構造の具体的な構成の一例は、ブルーミア・フィルタである。
　3. ブルーム・フィルタとブルーミア・フィルタ
　本節では、この発明に係る連想データ構造として適用可能なブルーミア・フィルタ（前記非特許文献６参照）と、その基礎となるブルーム・フィルタ（詳細は、例えば、B. H. Bloom: "Space/Time Trade-offs in Hash Coding with Allowable Errors", Commun. ACM, Vol. 13, No. 7, pp. 422-426 (1970)参照）について説明する。
　3-1. ブルーム・フィルタ
　ブルーム・フィルタは、平衡2分探索木やハッシュ表と比べてはるかに空間効率の良いデータ構造である。このブルーム・フィルタは、あるデータ集合と要素が与えられたとき、この要素がデータ集合のメンバであるか否かを調べるために用いられる。この手法には、ある要素がデータ集合のメンバではないにもかかわらず、集合のメンバであると判断される偽陽性(False Positive)の可能性が高くなるという問題点や、データ集合から元の要素を取り出すことができないという問題点がある。一方この手法には、メモリ量を増やすことなくデータ集合にいくらでも要素を追加することができるという利点がある。もちろん要素を追加すればするほど偽陽性の可能性は高くなるが、同じメモリ量で保存できる要素数は、平衡2分探索木やハッシュ表と比べると圧倒的に多い。
　この発明では、この空間効率の良さを利用し、ブルーム・フィルタを特徴ベクトルの圧縮表現に用いる。この明細書では、以後データ集合の要素を特徴ベクトルとして話を進める。以下に、ブルーム・フィルタへの特徴ベクトル登録方法と特徴ベクトルの認識方法の具体的な処理について説明する。
　図２に特徴ベクトルの登録処理の流れを示す。まず、空のブルーム・フィルタとしてm bitの配列を用意し、全てのbitを0で初期化する。以下では、mを"TableSize"と呼ぶこととする。次に、k個のハッシュ関数を用意し、それぞれのハッシュ関数に対して、特徴ベクトルをキーとしてハッシュ値を計算する。ここで、得られるハッシュ値は1～mの整数値とする。そして、得られたk個のハッシュ値 x1, x2, …, xkを基に、ブルーム・フィルタのxi(i=1, 2, …, k)番目のbitを1にすることで特徴ベクトルを登録する。特徴ベクトルの認識処理も探索処理と同様に、特徴ベクトルをキーとしてそれぞれのハッシュ関数からハッシュ値を得る。そして、得られたハッシュ値に対応するbitが全て1になっていれば、データ集合にその特徴ベクトルが含まれているとする。
　3-2. ブルーミア・フィルタ
　この発明で、ブルーミア・フィルタ（Bloomier Filter）は、複数のブルーム・フィルタを用いることで、登録した特徴ベクトルと関連する値を連想させるために用いられるデータ構造である。この手法にも、偽陽性の可能性があるという問題点や、元の特徴ベクトルをデータ集合から取り出すことができないという問題点があるものの、ハッシュ表などと比べると、圧倒的に空間効率が良いという利点がある。この発明では、この性質を利用し、ブルーミア・フィルタを特定物体認識に用いる。以下に、ブルーミア・フィルタの動作について具体的に説明する。
　ブルーミア・フィルタで連想させる値が0と1の二種類のみの例について説明する。まず2つのブルーム・フィルタ XとYを用意する。次に、特徴ベクトルに連想させたい値が0である場合、ブルーム・フィルタ Xに特徴ベクトルを登録しておき、連想させたい値が1である場合、ブルーム・フィルタ Yに特徴ベクトルを登録しておく。これによりある特徴ベクトルを認識させたとき、ブルーム・フィルタ Xに存在すれば、その特徴ベクトルから連想される値は0である可能性が高く、また、ブルーム・フィルタ Yに存在すれば、連想される値は1である可能性が高いとすることができる。
　この発明では、上記のブルーミア・フィルタの動作を利用し、特定物体を認識するために用いる物体IDを連想させることを考える。物体IDをn bitで表現するとしたとき、bitごとに二つのブルーム・フィルタを用意することで、これを実現させる。これにより、N個の物体を識別するために、物体ごとにブルーム・フィルタを用意するとN個のブルーム・フィルタが必要となるが、ブルーミア・フィルタを用いることで、log2N個のブルーム・フィルタで物体を識別することができる。
　4. この発明の手法
　本節では、ブルーミア・フィルタを用いた特定物体認識手法について述べる。この発明でも、野口らの手法と同様に、画像からPCA-SIFTによって求めた特徴ベクトルを用いる。まず、ブルーミア・フィルタへ特徴ベクトルを登録するデータベース作成処理について説明する。次に、ブルーミア・フィルタを用いた物体認識手法について具体的に説明する。
　4-1. データベース作成
　本節では、ブルーミア・フィルタへ特徴ベクトルを登録するデータベース作成処理について説明する。まず、物体を識別するために用いる物体IDをn bitで表現するとしたとき、2n個のブルーム・フィルタを用意する。このとき0を連想させるブルーム・フィルタをX1, X2, …, Xn、1を連想させるブルーム・フィルタをY1, Y2, …, Ynとする。それぞれのブルーム・フィルタのTableSizeは、
Figure JPOXMLDOC01-appb-M000006
 とする。ここで、
Figure JPOXMLDOC01-appb-M000007
 は物体IDのf番目のbitがgである物体から得られる特徴ベクトルの総数、aは一特徴ベクトルを何bitで保存するかを表す値である。
　具体例を示すと、ブルーム・フィルタ Xiの場合、物体IDをbit表現したときにi番目のbitが0である全ての物体から得られる特徴ベクトル数がMの値となり、
Figure JPOXMLDOC01-appb-M000008
 がXiのTableSizeとなる。
　次に、物体IDを連想させるために、n個のブルーム・フィルタに対して特徴ベクトルを登録していく。例えば、2bitで物体IDを表現するとき、物体IDの3を"10"で表現したとすると、bit列の1 bit目が"1"、2 bit目が"0"であるため、Y1とX2のブルーム・フィルタに物体ID3の物体から得られる特徴ベクトルを保存する。以下に具体的な処理を説明する。
　この発明では野口らの手法と同様に、特徴ベクトルのd次元を用いて、ビットベクトルuを作成する。データベースに登録する特徴ベクトル全てをビットベクトルで表現したとき、同じビットベクトルが閾値c個以上あれば、そのビットベクトルに変換される特徴ベクトルは、認識にはあまり有効でないと考え、データベースに登録しない。それ以外の場合は、求めたビットベクトルuをキーとし、k個のハッシュ関数を用いて、ブルーム・フィルタのどのビットを1にするかを決める。
　この実施形態では、k=8とし、ハッシュ関数にインターネット上のGeneral Purpose Hash Function Algorithms, [online]、平成21年6月3日検索、＜URL: http://www.partow.net/programming/hashfunctions/index.html#RSHashFunction.＞ で紹介されている8個のハッシュ関数を用いる。ただし、これは一例にすぎず、他のハッシュ関数を用いてもよい。
　以上の処理を全ての特徴ベクトルに対して行い、データベースを作成する。この発明では、データベースから元の特徴ベクトルを取り出すことができないが、ブルーム・フィルタの性質上、元の特徴ベクトルをそのまま保存するよりも、かなりメモリ量を圧縮して特徴ベクトルを表現することができる。
　4-2. 物体認識
　本節では、ブルーミア・フィルタを用いた物体認識手法について説明する。まず、提案する物体認識手法の処理の流れを説明する。この手法では、検索質問画像から得られる特徴ベクトルqを用い、物体IDのi(i=1, 2, …, n)番目のbitが0か1かを求めるために、XiとYiのブルーム・フィルタにqに対応する特徴ベクトルが登録されているかを調べる。このとき、Xiに登録されていれば、物体IDのi番目のbitを0とし、Yiに登録されていれば、物体IDのi番目のbitを1とする。そして、全てのbitに対して値を求め、最終的に求まった物体IDの物体に投票を行う。この処理を検索質問画像から得られる特徴ベクトル全てに対して行い、最も得票数の多かった物体を認識結果とする。以下に具体的な処理について説明する。
　質問画像から得られる特徴ベクトルは、一般に各次元の値がデータベース作成に用いる特徴ベクトルのものと異なったものとなる。このためこの実施形態でも、野口らの手法と同様に、各次元の値の許容変動幅eを設け変動に対処する。また、この処理を行う次元数を閾値b個以下に制限し、次元数がbを上回るときには、次元のインデックスの大きいものからb個を採用する。そしてこれらのビットベクトルを用いて、物体IDのi(i=1, 2, …, n)番目のbitが0か1かを求める。
　このとき、ブルーム・フィルタ Xiに存在していれば、物体IDのi番目のbitを0とし、ブルーム・フィルタ Yiに存在していれば、物体IDのi番目のbitを1とする。XiとYiの両方に含まれていない場合は、このビットベクトルをキーとした特徴ベクトルはデータベースに登録されていないとし、i番目以降の処理を打ち切る。
　この処理では、XiとYiの両方に含まれていた場合に問題が起こる。これは、どちらかのブルーム・フィルタが偽陽性を引き起こし、実際には登録されていないにもかかわらず、登録されていると判断されるために起こる。この発明では、このような場合、両方の可能性を試すことにより対処する。具体的には、物体IDのi番目のbitが0となる物体IDと1となる物体IDの両方を投票の対象とする。但し、全てのbitに対して上記の処理を行うと誤投票が増加してしまうため、この発明では、偽陽性に対処する物体IDの次元数に閾値tを設け、投票する物体ID数を2t個に制限する。対処する次元数がt個を超える場合、次元の小さいものからt個採用する。
　上記の処理を繰り返し、求まった物体IDの物体に投票する。この処理を検索質問画像から得られる全ての特徴ベクトルに対して行い、最終的に最も得票数の多かった物体を認識結果とする。
　またこの実施形態では、認識処理の効率化を図るために、野口らの手法と同様に、第s段がb = s-1とした識別器を用いて認識を行う。これによって、十分に他の物体との得票数差が得られれば、途中の段で処理を打ち切ることができるため、認識処理を効率的に行うことができる。
　4-3. 誤り検出
　この発明では、上記の処理で作成したデータベースに加え、投票時に投票誤りを検出するための処理も提案する。まず、データベース作成の際には、上記の通常のブルーミア・フィルタに加え、誤り検出用のブルーミア・フィルタも作成する。これは、ある検索質問画像から得られた特徴ベクトルを用いて認識処理で求まったIDに、本当に投票を行ってよいかを決めるための簡易的な誤り検出器である。
　この誤り検出ブルーミア・フィルタを以下のように作成する。まず、二つのブルーム・フィルタ P0, P1を用意する。そして、物体IDを2bit表現したとき、1の数が偶数個の物体IDから得られる特徴ベクトルをP0に登録し、1の数が奇数個の物体IDから得られる特徴ベクトルをP1に登録する。それぞれのブルーム・フィルタのTableSizeは、式(4)と同様に与えられる。
　認識処理では、求まった物体IDの物体に投票を行うかどうかを、誤り検出ブルーミア・フィルタを用いて決める。このとき、誤り検出ブルーミア・フィルタに登録されていなかった場合や、両方に登録されていた場合、求まった物体IDは誤ったIDと判断し、投票を行わない。
　5. データベース作成処理、認識処理の具体例
　前節で述べたデータベース作成処理、認識処理についての具体例を本節に示す。なお、説明を理解しやすくするため、本節では非常に小さな物体IDのbit数、特徴ベクトル数を例示しているが、実際に本願発明が適用される場面では、後述する実験例、あるいはそれよりさらに大規模なデータベースが処理の対象となる。
　5-1. データベース作成処理
　いま、物体IDが「3」の物体から得られる特徴ベクトルをデータベースに登録する処理について具体的に述べる。まず特徴ベクトルを登録するブルーム・フィルタを決める。ここで、物体ID3を2bitで表現するとしたとき、物体ID3に10というbit列を割り当てたとする。例では、bit列の1番目の数字が1，2番目の数字が0であるので、bit列の1番目の数字に1を連想させるブルーム・フィルタ Y1と、bit列の2番目の数字に0を連想させるブルーム・フィルタ X2に特徴ベクトルを登録する。
　また、物体IDをbit列で表現したとき、1が奇数個現れるので、誤り検出ブルーム・フィルタ P1にも特徴ベクトルを登録する。次に、物体ID3の物体より得られる特徴ベクトルを、図２に示すような手順で登録する。
　まず、物体ID3の物体から得られる特徴ベクトルの1次元目からd次元を用い、ビットベクトルを作成する。特徴ベクトルの各次元の値が非負であるとき1とし、負であるとき0に変換する。具体的に説明すると、今物体ID3の物体から得られる特徴ベクトルとして、
P1 = ( 24,-500, 249, 32),
P2 = (239, 123, -11, -57),
…
があるとき、d=3とすると、P1，P2，・・・はそれぞれ低次元側（左側）から3ビットの各要素を0または1に符号化してなるビットベクトル、
u1 = (1, 0, 1),
u2 = ( 1, 1, 0),
…
に変換される。
　このとき、同じビットベクトルに変換される特徴ベクトルがc個以上あった場合、このビットベクトルに変換される特徴ベクトルは、類似しているため認識にはあまり有効でないと考え、以後の処理に用いない。
　次に、ビットベクトルをキーとしてk個のハッシュ関数からそれぞれハッシュ値を得る。そして、得られたハッシュ値に対応するブルーム・フィルタのbitを1にする。ここで、対象のブルーム・フィルタは、前述のごとくY1, X2, P1であり、何も登録されていない初期後の状態で、各ブルーム・フィルタは、全ての要素が0（ゼロ）である。
　ここで、kをk=3とし、ブルーム・フィルタのTableSizeをm=8としたとき、ビットベクトルu1，u2を登録する例を図２３に示す。
　図２３で、まず、ビットベクトルu1をキーとして、前述のk個のハッシュ関数からk=3個のハッシュ値を求める。いま、求まったハッシュ値が1，2，4であったとき、(00000000)に初期化されたブルーム・フィルタ Y1, X2, P1の1，2，4番目のbitを1にする。u1登録後のY1, X2, P1は、いずれも（11010000）になる（図２３(a)参照）。
　続いてu2をキーとし、前述のk個のハッシュ関数から2，5，7というハッシュ値が求まったとすると、既に、u1が登録されたY1, X2, P1のベクトル（11010000）のうち2，5，7番目のbitを1にする。u2登録後のY1, X2, P1は、いずれも（11011010）になる（図２３(b)参照）。
　以上の処理を、物体ID3の物体から得られる全ての特徴ベクトルについて繰り返し、ブルーム・フィルタY1とX2とP1に登録する。
　さらに、他の物体IDについても同様の処理行う。例えば、物体ID4について、11というbit列を割り当てたとする。bit列の1番目および2番目の数字がいずれも1であるので、bit列の1番目の数字に1を連想させるブルーム・フィルタ Y1と、bit列の2番目の数字に1を連想させるブルーム・フィルタ Y2と、偶数ビットの誤り検出ブルーム・フィルタ P0とに、物体ID4の物体から得られる全ての特徴ベクトルを登録する。
　以上のようにして、各物体の各特徴ベクトルについて登録を行い、データベースを作成する。
　5-2. 認識処理
　続いて、認識処理の具体例について述べる。まず、検索質問画像から得られる特徴ベクトルを用いて、全てのブルーム・フィルタに対して検索を行う。
　いま、検索質問画像から得られる特徴ベクトル（検索質問特徴ベクトル）として、
q1 = ( 31,-480, 220, 49),
q2 = (239, 20, 113, -82),
…
があるとき、データ登録処理時と同様に、特徴ベクトルからビットベクトル、
u1' = ( 1, 0, 1),
u2' = ( 1, 1, 1),
…
を作成する。
　このビットベクトルをキーとして、前述のk=3個のハッシュ関数からそれぞれハッシュ値を求める。物体IDのビット列に対応する各ブルーム・フィルタ X1, X2, Y1, Y2について、対応するbitが全て1になっているかを調べる。もし、全てのbitが1となっていれば、キーの特徴ベクトルがそのブルーム・フィルタに登録されているとする。
　具体的に述べると、ブルーム・フィルタ Y1が（11011010）となっているとする。
　検索質問の特徴ベクトルq1から得られたビットベクトルu1'についてハッシュ値を求めると、u1'は登録時のu1と同じ値であるから、登録処理と同様のハッシュ値1，2，4が得られる。ブルーム・フィルタ Y1の1，2，4番目のbitをみると全てが1になっている。この場合、q1はブルーム・フィルタ Y1に登録されていると判断する。
　但し、一般に、ブルーム・フィルタでは、登録されていないにも関わらず、登録されていると判断されることがある。今q2が実際にはブルーム・フィルタに登録されていない特徴ベクトルであると仮定する。q2より求めたビットベクトルu2'からハッシュ値を求めると2，4，5であったとする。このハッシュ値よりブルーム・フィルタ Y1＝（11011010）の対応する第2，4，5 bitを調べると、全て1になっている。このように、実際には登録されていない特徴ベクトルでも、ブルーム・フィルタが偽陽性を起こし、登録されていると判断されることがある。
　説明を続ける。このように、検索質問の各特徴ベクトルにつき、前述した手順で検索処理を行うことで、物体IDのi番目のbitが何であるかを判断する。ある検索質問の特徴ベクトルがブルーム・フィルタ Xiに登録されていたとする。この場合、物体IDのi番目のbitを0とする。一方、その特徴ベクトルがYiに登録されていたとすると、物体IDのi番目のbitを1とする。仮に、Y1とX2に特徴ベクトルが登録されていたとすると、物体IDのbit列は「10」となるため、ID3の物体に投票を行う。
　このとき、ブルーム・フィルタが偽陽性を起こし、XiとYiの両方に特徴ベクトルが登録されていると判断されたとする。その場合、この発明では両方の可能性を試す。即ち、その検索質問特徴ベクトルについては、図２３に示すように、物体IDのi番目のbitが0の物体と1となる物体の両方に投票を行うこととする。例えば、検索処理の結果、ある検索質問特徴ベクトルがX1，Y1，X2に登録されていたと判断されると、物体IDのbit列00と10の2つのID候補を用意する。そして、誤り検出ブルーム・フィルタを参照し、投票してもよい物体IDを決める。即ち、誤り検出ブルーム・フィルタ P0に特徴ベクトルが登録されていたとき、前記ID候補のうち物体IDに1が偶数個のID「00」のみ投票を行い、逆に、P1に特徴ベクトルが登録されていたとき、物体IDに1が奇数個のID「10」のみ投票を行う（図２４参照）。なお、ここでは、ブルーム・フィルタを用いた誤り検出の一例を示したが、誤り検出に代えて、例えば、複数のブルーム・フィルタにより公知の誤り符号訂正の手法を適用できるように構成してもよい。このようにすれば、偽陽性に起因する誤った判断をより低減することができる。
　上記の検索処理および投票処理を検索質問画像から得られる全ての特徴ベクトルに対して行う。その結果、最終的に最も得票数の多かった物体を認識結果とする。
　なお、投票に際しては、票に重みを付けてもよい。例えば、物体IDがiの物体から抽出されデータベースに登録された特徴ベクトル数がNi個のとき、その物体IDへの投票に1／√Niの重みを付けて投票するようにしてもよい。
　5. 実験例
　本節では、この発明の有効性を確かめるために、55個の3次元物体を用いたデータセットと、5000個の2次元物体を用いたデータセットに対して行った実験の結果について述べる。
　5-1. 実験条件
　まず、55個の3次元物体のデータセットについて説明する。図３に本実験で用いた3次元物体の例を示す。本実験では、物体に対して、真正面、真正面から上へ15°、30°の角度から、ウェブカメラで、5°ごとに物体を回転させて撮影した画像を用いた。ウェブカメラは、株式会社ロジクール製、製品型名 Qcam（登録商標） Pro 9000、解像度：640480のものである。このうち、データベース作成用画像として、回転角度が0°, 10°, …, 350°の画像36枚×3方向の、1物体当たり108枚を用い、残りの画像を検索質問画像とした。データベース作成用画像から得られる特徴ベクトルの数は、約120万個である。
　次に、5000個の2次元物体のデータセットについて説明する。本実験では、Googleイメージ検索において、"雑誌"、"ポスター"、"表紙"等の検索キーワードで収集した1667枚の画像と、PCA-SIFTのサイトで公開されていた1667枚の画像と、写真共有サイトのFlickrにおいて、"animal"、"birthday"、"food"、"japan"等のタグにより収集した1666枚の画像をデータベース作成用画像とした。
　　図４に例を示す。なお、収集の際には、600×600 pixel以下のサイズの画像は除外し、画像の長辺が640pixel以下になるように縮小した。また、得られる特徴ベクトルが100個以下になる画像も除外した。データベース作成用画像から得られる特徴ベクトルの数は、約1千万個である。検索質問画像としては、次のように用意した。まず、データベースに含まれる画像の内、Googleイメージ検索で収集した画像から100枚、PCA-SIFTのサイトから得た画像から200枚、Flickrから収集した画像から200枚の合計500枚を無作為に選択した。次に、これらの画像をA4の用紙にカラーレーザプリンタ（株式会社沖データ製、製品型名 C5200n）を用いて印刷し、カメラ（キャノン株式会社社製、製品型名 EOS Kiss Digital、630万画素、付属レンズ型名：EF-S 18-55mm USM）で撮影した。
　撮影した画像の例を図５に示す。図５に示す通り、紙面全体が写る配置で、紙面に対するカメラの光軸の角度θを 90°, 75°, 60°に変化させた。また、角度を90°として紙面の一部分を撮影した。その結果、1枚の紙面に対して、合計4通りの画像を得た。さらに、撮影した画像を512×341pixelに縮小し、PCA-SIFTにより特徴ベクトルを求めた。
　両実験において、この発明と野口らの手法を用いてそれぞれ物体の認識を行った場合の、物体の認識率と、質問画像一枚の認識にかかった平均の処理時間と、認識に必要なメモリ量を比較した。但し、処理時間に特徴ベクトルの抽出時間等は含めないものとする。
　本実験では、この発明と野口らの手法で用いられているパラメータの内、両方のビットベクトルを試す次元数b、ハッシュのリスト長c、ビットベクトルの次元数dを変化させて物体の認識率を調べた。ここで各パラメータの変動幅は、b=0, 1, …, 10、c=1, 2, …, 10、d=24,28である。また両手法において、特徴ベクトルの許容変動幅eはe=200とした。使用した計算機は、CPUがAMD Opteron8378 2.4GHz、メモリが128GBのものである。
　5-2. 実験1：55個の3次元物体を用いた実験
　この発明の手法において、前節で述べたパラメータ以外に、特徴ベクトルの保存容量a、偽陽性に対処する次元数tも変化させて物体の認識率を調べた。aとtの変動幅は、a=8, 16, 24, 32、t=1, 2, 3, 4, 5とする。野口らの手法のハッシュ表のハッシュサイズは、Hsize=2dとした。d=24のときの結果を図６、d=28のときの結果を図７に示す。横軸に認識率、縦軸に処理時間を示す。
　図６、7に示す実験結果より、この発明の手法ではbの値を大きくすれば物体の認識率が高くなるが、大きくしすぎると認識率が低下し、処理時間も増加することが分かった。これは、bによって特徴ベクトルの変動に対処することができるが、bを増加しすぎると誤投票が多くなるため認識率が低下し、さらに投票回数が増加することが、処理時間の増加に繋がっていると考えられる。
　図８にbを変化させたときの認識率を比較した例を示す。ここで用いたパラメータは、a=8, d=28で最も認識率の高かったc=8, t=2を用いた。また結果より、この発明の手法の方が野口らの手法と比べて、一枚の認識にかかる処理時間は多くかかるものの、物体の認識率では若干良い結果を得るものがあった。認識処理に時間がかかる原因として、野口らの手法では、一つの検索質問ベクトルqに対してハッシュ表を一度検索するだけで投票を行えるが、この発明の手法では、2n個のブルーム・フィルタを検索しなければ投票を行えないことが挙げられる。
　次に、この発明の手法のパラメータaを変化させたものと、野口らの手法とで、パラメータcを変化させたとき、認識処理に必要なメモリ量を比較した結果をdごとに図９と図１０に示す。横軸にパラメータc、縦軸にメモリ量を示す。
　図９と図１０に示す実験結果より、この発明の手法の方が野口らの手法と比べて、かなり空間効率がよいことが分かる。これは、野口らの手法ではメモリ量の大部分がハッシュ表のエントリに用いられていることに起因している。
　上記の結果より、この発明の手法は野口らの手法と比べ、認識にかかる処理時間は多くかかるものの、認識率とメモリ量の点で優れているといえる。
　最後に、この発明の手法において、tを変化させたときの物体の認識率を比較した。実験では、a=8, d=28のときに最も認識率の高かったパラメータb=3, c=8を用いた。図１１に実験結果を示す。結果より、tの値を大きくすれば物体の認識率が高くなるが、大きくしすぎると認識率が低下することが分かった。これは、tを増加させることで誤投票が増加してしまうことが原因として挙げられる。
　5-3. 実験2：5000個の2次元物体を用いた実験
　実験1と同様に、5.1節で述べたパラメータ以外に、パラメータa, tも変化させて物体の認識率を調べた。パラメータの変動幅は、実験1と同じである。また野口らの手法に用いるハッシュ表のサイズも実験1と同じサイズとした。d=24のときの結果を図１２、d=28のときの結果を図１３に示す。横軸に認識率、縦軸に一枚の認識にかかった平均の処理時間を示す。結果より、実験1と同様に、bを大きくすれば認識率が増加するが、さらに大きくすると認識率が低下し、処理時間も長くなることが分かった。
　図１４にbを変化させたときの認識率を比較した例を示す。ここで用いたパラメータは、a=8, d=28で最も認識率の高かったc=2, t=3を用いた。また実験結果より、処理時間ではこの発明の手法は野口らの手法と比べて、特にd=24のとき大きく劣ることが分かったが、認識率ではd=28のとき、若干良い結果を得るものがあった。d=24で認識率、処理時間共に野口らの手法に比べて劣る原因として、検索処理時に同じビットベクトルに変換される割合が大きくなるため、投票処理時に他の物体との得票数差が開かないことが挙げられる。
　次に、この発明の手法のパラメータaを変化させたものと、野口らの手法とで、パラメータcを変化させたとき、認識処理に必要なメモリ量を比較した結果をdごとに図１５と図１６に示す。横軸にパラメータc、縦軸にメモリ量を示す。
　図１５と図１６に示す実験結果より、d=24の結果において、a=24, 32のとき野口らの手法より認識に必要なメモリ量が多くなってしまったが、d=28のとき、野口らの手法に比べてこの発明の手法はかなり空間効率がよいことが分かった。d=24、a=24, 32のときにメモリ量が多くなった原因として、この発明の手法では、一つの特徴ベクトルに対して、n個のブルーム・フィルタに登録しなればならないことが原因として挙げられる。
　さらに、同程度のメモリが使える状況での比較を行った。メモリ量がほぼ同じであるこの発明の手法のd=28、a=8,16と、比較手法1として野口らの手法のd=24と、比較手法2として、野口らの手法においてd=28、Hsize = 224-1としたときの手法の3手法に着目する。これらの3手法でb,cの値を変化させたときの認識率と処理時間の違いを調べた。但しこの発明の手法では、tの値もt=1, 2, 3, 4, 5と変化させて実験を行った。
　図１７に、その実験結果を示す。横軸に認識率、縦軸に1枚の認識にかかった平均の処理時間を示す。実験結果より、使用するメモリ量をほぼ同じにしたとき、この発明の手法は、比較手法と比べて処理時間は多くかかるものの、パラメータによって認識率をかなり向上させることができた。このことからこの発明の手法は、効率よく特徴ベクトル表現を圧縮できているといえる。
　最後に、この発明の手法において、tを変化させたときの物体の認識率を比較した。実験では、a=8, d=28のときに最も認識率の高かったパラメータb=6, c=2を用いた。図１８にその実験結果を示す。実験1と同様に、tを大きくすれば認識率が増加するが、さらに大きくすると認識率が低下してしまうことが分かった。
　5-4. 誤り検出の効果
　最後に、前述の誤り検出ブルーミア・フィルタの有効性を調べるために、bおよびtを変化させ、誤り検出ブルーミア・フィルタを用いる場合と用いない場合の認識率を比較した。bを変化させた場合の実験およびtを変化させた場合の実験で用いたパラメータは、それぞれ最も認識率の高いものを用いた。
　まず、55物体を対象とした実験について述べる。用いたパラメータを表1に、bに関する実験結果を図１９に、tに関する実験結果を図２０にそれぞれ示す。
　図１９と図２０に示す実験結果より、b,t共に大きくすれば認識率が増加するが、大きくしすぎると認識率が低下してしまうことが分かった。これは、値を増加させると、誤投票も増加してしまうことが原因であると考えられる。また実験結果より、特にtを変化させた場合、誤り検出ブルーミア・フィルタを用いた場合、誤った投票を検出することで誤投票が抑えられるため、用いない場合より高い認識率を得ることができると分かった。このため、誤り検出ブルーミア・フィルタを用いることは有効であるといえる。
　次に２次元物体の結果について述べる。ただし、この実験については、物体数を5000ではなく1万とした。用いたパラメータを表2に、bに関する実験結果を図２１に、tに関する実験結果を図２２にそれぞれ示す。55物体の結果と同様に、共に大きくすれば認識率が増加するが、大きくしすぎると認識率が低下してしまうことが分かった。また、誤り検出ブルーミア・フィルタを用いた場合、用いない場合より高い認識率を得ることができると分かった。このため、誤り検出ブルーミア・フィルタを用いることは有効であるといえる。
　前述した実施の形態の他にも、この発明について種々の変形例があり得る。それらの変形例は、この発明の範囲に属さないと解されるべきものではない。この発明には、請求の範囲と均等の意味および前記範囲内でのすべての変形とが含まれるべきである。
　特定物体を認識する手法に、局所特徴量を表す特徴ベクトルの最近傍探索を用いる手法がある。この手法では、特徴ベクトル間の距離を計算するために、特徴ベクトルそのものを記録する必要があるが、一般に物体認識に関与する特徴ベクトルの数は膨大であるため、莫大なメモリ量が必要となる。この問題を解決するため、特徴ベクトルの距離を計算しない枠組みが必要となる。
　この発明は、特徴ベクトルの距離を計算しないメモリ量削減手法として、ハッシュ表などと比べてはるかに空間効率の良いブルーミア・フィルタを用いる手法を提案した。また、平面および3次元特定物体の認識実験を通して、ハッシュ表を用いる手法とこの発明を比較し、その有効性を検証した。
　１　　画像データベース

Claims (9)

  1. 　物体認識用画像データベースに登録されるべき物体が撮影された画像から、その画像の局所的特徴を表す複数の特徴ベクトルを抽出する特徴抽出工程と、
    データを登録できかつあるデータが登録済か否かを判定し得るデータ構造に対し、ある物体から抽出された各特徴ベクトルを、その物体に予め割り当てられた識別子が前記特徴ベクトルから連想されるように登録する登録工程とを備え、
    各工程をコンピュータが実行し、
    前記登録に係る物体は、ｎビット（ｎは自然数）の識別子が割り当てられ、
    前記登録工程は、前記識別子の各ビットのゼロ値登録用と１値登録用として用意された２×ｎ個の前記データ構造に対し、各特徴ベクトルが抽出された物体の識別子に応じて各ビットのゼロ値登録用と１値登録用の何れか一方のデータ構造に前記特徴ベクトルをそれぞれ登録し、
    前記画像データベースは、検索質問としてある物体の画像が与えられたとき同じ物体が登録されているか否かの認識処理を行うべく、前記コンピュータまたは他のコンピュータによってアクセスされ、
    前記認識処理は、前記検索質問から複数の特徴ベクトルを検索質問ベクトルとして抽出し、各検索質問ベクトルと同値の特徴ベクトルが各データ構造に登録されているか否かを調べ、すべてのビットについてゼロ値または１値のいずれかに同値の特徴ベクトルが登録されているときは登録された各ビットの値に応じたｎビット値を識別子の候補として得、各検索質問ベクトルにつき得られた候補を統計処理して検索質問に適合する識別子を見出すことを特徴とする物体認識用画像データベースの作成方法。
  2. 　各データ構造は、偽陽性を許容することによりデータを格納するメモリの容量を削減するものである請求項１に記載の作成方法。
  3. 　前記登録工程は、所定の規則を適用して前記識別子に係る誤り検出用の値を得、得られた値を前記誤り検出用のデータ構造に登録し、
    前記認識処理は、得られた識別子の候補と前記誤り検出用データ構造に登録された値とを照合し、両者が一致する場合は前記検索質問ベクトルについての判定結果を統計処理の対象とし、一致しない場合は統計処理の対象としない請求項１または２に記載の作成方法。
  4. 　前記誤り検出用の値が少なくとも１ビットからなり、
    前記誤り検出用データ構造は、ビットのゼロ値登録用と１値登録用としてデータ構造が用意されてなる請求項３に記載の作成方法。
  5. 　前記認識処理は、偽陽性のために、ゼロ値および１値登録用のいずれのデータ構造にも同一の検索質問ベクトルが登録されていると判断されるビットの数が予め定められた数を超える場合、その検索質問ベクトルについての判定結果を統計処理の対象から除外する請求項２～４のいずれか一つに記載の作成方法。
  6. 　前記認識処理は、前記検索質問ベクトルに関連があると判定される識別子の値に対して所定の得点を与え、前記検索質問ベクトルに関連があると判定される識別子が存しない場合はいずれの識別子にも得点を与えず、
    前記検索質問から抽出される検索質問ベクトルについての統計処理に基づき最多得点を得た識別子を決定する請求項１～５のいずれか一つに記載の作成方法。
  7. 　前記データ構造はブルーム・フィルタである請求項１～６のいずれか一つに記載の作成方法。
  8. 　物体認識用画像データベースに登録されるべき物体が撮影された画像から、その画像の局所的特徴を表す複数の特徴ベクトルを抽出する特徴抽出部と、
    データを登録できかつあるデータが登録済か否かを判定し得るデータ構造体の集合からなるデータ構造部と、
    ある物体から抽出された各特徴ベクトルからその物体に予め割り当てられた識別子が前記特徴ベクトルから連想されるように前記特徴ベクトルを前記データ構造部に登録する登録部とを備え、
    前記登録に係る物体は、ｎビット（ｎは自然数）の識別子が割り当てられ、
    前記データ構造部は、前記識別子の各ビットのゼロ値登録用および１値登録用として２×ｎ個のデータ構造体を少なくとも有し、
    前記登録部は、各特徴ベクトルが抽出された物体の識別子に応じて各ビットのゼロ値登録用と１値登録用の何れか一方のデータ構造に前記特徴ベクトルをそれぞれ登録し、
    前記画像データベースは、検索質問としてある物体の画像が与えられたとき同じ物体が登録されているか否かの認識処理を行う認識装置によってアクセスされ、
    前記認識装置は、前記検索質問から複数の特徴ベクトルを検索質問ベクトルとして抽出し、各検索質問ベクトルと同値の特徴ベクトルが各データ構造に登録されているか否かを調べ、すべてのビットについてゼロ値または１値のいずれかに同値の特徴ベクトルが登録されているときは登録された各ビットの値に応じたｎビット値を識別子の候補として得、各検索質問ベクトルにつき得られた候補を統計処理して検索質問に適合する識別子を見出すことを特徴とする物体認識用画像データベースの作成装置。
  9. 　物体認識用画像データベースに登録されるべき物体が撮影された画像から、その画像の局所的特徴を表す複数の特徴ベクトルを抽出する特徴抽出処理と、
    データを登録できかつあるデータが登録済か否かを判定し得るデータ構造に対し、ある物体から抽出された各特徴ベクトルを、その物体に予め割り当てられた識別子が前記特徴ベクトルから連想されるように登録する登録処理とをコンピュータに実行させ、
    前記登録に係る物体は、ｎビット（ｎは自然数）の識別子が割り当てられ、
    前記登録処理は、前記識別子の各ビットのゼロ値登録用と１値登録用として用意された２×ｎ個の前記データ構造に対し、各特徴ベクトルが抽出された物体の識別子に応じて各ビットのゼロ値登録用と１値登録用の何れか一方のデータ構造に前記特徴ベクトルをそれぞれ登録し、
    前記画像データベースは、検索質問としてある物体の画像が与えられたとき同じ物体が登録されているか否かの認識処理を行うべく、前記コンピュータまたは他のコンピュータによってアクセスされ、
    前記認識処理は、前記検索質問から複数の特徴ベクトルを検索質問ベクトルとして抽出し、各検索質問ベクトルと同値の特徴ベクトルが各データ構造に登録されているか否かを調べ、すべてのビットについてゼロ値または１値のいずれかに同値の特徴ベクトルが登録されているときは登録された各ビットの値に応じたｎビット値を識別子の候補として得、各検索質問ベクトルにつき得られた候補を統計処理して検索質問に適合する識別子を見出すことを特徴とする物体認識用画像データベースの作成処理プログラム。
PCT/JP2010/059352 2009-06-10 2010-06-02 物体認識用画像データベースの作成方法、作成装置および作成処理プログラム Ceased WO2010143573A1 (ja)

Priority Applications (4)

Application Number Priority Date Filing Date Title
EP10786104.9A EP2442273A4 (en) 2009-06-10 2010-06-02 OBJECT IDENTIFICATION IMAGE DATABASE GENERATION PROCESS, GENERATION DEVICE AND PRODUCTION PROCESSING PROGRAM
JP2011518472A JP5354507B2 (ja) 2009-06-10 2010-06-02 物体認識用画像データベースの作成方法、作成装置および作成処理プログラム
CN201080035625.1A CN102460511B (zh) 2009-06-10 2010-06-02 用于物体识别的图像数据库的制作方法以及制作装置
US13/376,890 US20120084305A1 (en) 2009-06-10 2010-06-02 Compiling method, compiling apparatus, and compiling program of image database used for object recognition

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
JP2009139148 2009-06-10
JP2009-139148 2009-06-10

Publications (1)

Publication Number Publication Date
WO2010143573A1 true WO2010143573A1 (ja) 2010-12-16

Family

ID=43308828

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/JP2010/059352 Ceased WO2010143573A1 (ja) 2009-06-10 2010-06-02 物体認識用画像データベースの作成方法、作成装置および作成処理プログラム

Country Status (5)

Country Link
US (1) US20120084305A1 (ja)
EP (1) EP2442273A4 (ja)
JP (1) JP5354507B2 (ja)
CN (1) CN102460511B (ja)
WO (1) WO2010143573A1 (ja)

Cited By (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2013246810A (ja) * 2012-05-30 2013-12-09 Denso It Laboratory Inc 情報検索装置、情報検索方法及びプログラム
KR101546653B1 (ko) 2012-06-26 2015-08-25 한국과학기술원 증강현실 기반의 실시간 관심 컨텍스트 등록 시스템 및 그 방법
WO2017009958A1 (ja) * 2015-07-14 2017-01-19 富士通株式会社 圧縮プログラム、圧縮方法および圧縮装置
JP2017517799A (ja) * 2014-05-14 2017-06-29 インテル・コーポレーション ソートミドルアーキテクチャにおけるフレームのフレームコヒーレンシへの活用

Families Citing this family (8)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US9087267B2 (en) 2011-06-10 2015-07-21 Image Vision Labs, Inc. Image scene recognition
US9223804B2 (en) 2012-08-27 2015-12-29 Qualcomm Incorporated Determining capacity of search structures
US8972337B1 (en) 2013-02-21 2015-03-03 Amazon Technologies, Inc. Efficient query processing in columnar databases using bloom filters
US20160117631A1 (en) * 2014-10-22 2016-04-28 Honeywell International Inc. Orphaned item identification
US9704245B2 (en) 2015-08-18 2017-07-11 International Business Machines Corporation Determining localization from images of a vicinity
CN109740037B (zh) * 2019-01-02 2023-11-24 山东省科学院情报研究所 多源、异构流态大数据分布式在线实时处理方法及系统
US11797206B2 (en) * 2020-12-17 2023-10-24 EMC IP Holding Company LLC Hash migration using a gold image library management system
US11892980B2 (en) * 2021-09-16 2024-02-06 EMC IP Holding Company LLC Memory optimized algorithm for evaluating deduplication hashes for large data sets

Citations (1)

* 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

Family Cites Families (5)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US7043474B2 (en) * 2002-04-15 2006-05-09 International Business Machines Corporation System and method for measuring image similarity based on semantic meaning
JP4479478B2 (ja) * 2004-11-22 2010-06-09 株式会社日立製作所 パターン認識方法および装置
KR100903961B1 (ko) * 2007-12-17 2009-06-25 한국전자통신연구원 시그니처 파일을 이용한 고차원 데이터 색인 및 검색방법과 그 시스템
CN100592297C (zh) * 2008-02-22 2010-02-24 南京大学 一种基于表示转换的多义数字图像检索方法
US7970808B2 (en) * 2008-05-05 2011-06-28 Microsoft Corporation Leveraging cross-document context to label entity

Patent Citations (1)

* 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

Non-Patent Citations (14)

* Cited by examiner, † Cited by third party
Title
"PCA-SIFT: A more distinctive representation for local image descriptors", PROC. OF CVPR2004, vol. 2, 2004, pages 506 - 513
B. CHAZELLE; J. KILIAN; R. RUBINFELD; A. TAL: "The Bloomier Filter: An Efficient Data Structure for Static Support Lookup Table", PROC. 15TH ANNUAL ACM-SIAM SODA, 2004, pages 30 - 39, XP008148797
B. H. BLOOM: "Space/Time Trade-offs in Hash Coding with Allowable Errors", COMMUN. ACM, vol. 13, no. 7, 1970, pages 422 - 426, XP002490170, DOI: doi:10.1145/362686.362692
BERNARD ET AL.: "The Bloomier filter: an efficient data structure for static support lookup tables", PROCEEDINGS OF THE FIFTEENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, 2004, pages 30 - 39, XP008148797 *
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
F. FRAUNDORFER; H. STEWENIUS; D. NISTER: "A Binning Scheme for Fast Hard Drive Based Image Search", PROC. OF CVPR2007, 2007, pages 1 - 6, XP031114431
HIROYA MINAMI: "WWW ni Okeru Bunsan Caching Gijutsu", NTT GIJUTSU JOURNAL, vol. 12, no. 5, 1 May 2000 (2000-05-01), pages 59 - 62, XP008148816 *
K. KISE; K. NOGUCHI; M. IWAMURA: "Memory Efficient Recognition of Specific Objects with Local Features", PROC. OF THE 19TH INTERNATIONAL CONFERENCE OF PATTERN RECOGNITION (ICPR2008) WEAT3.1, 2008
KATSUFUMI INOUE; HIROSHI MIYAKE; KOICHI KISE: "A Memory Reduction Method for 3D Object Recognition based on Local Descriptors - An Approach by Selecting Local Descriptors", MEETING ON IMAGE RECOGNITION AND UNDERSTANDING (MIRU2008), OS15-3, 2008, pages 363 - 370
KAZUTO NOGUCHI ET AL.: "Efficient Recognition of Specific Objects by Cascading Approximate Nearest Neighbor Searchers", MEETING ON IMAGE RECOGNITION AND UNDERSTANDING (MIRU2007) RONBUNSHU, 30 July 2007 (2007-07-30), pages 111 - 118, XP008148817 *
KAZUTO NOGUCHI; KOICHI KISE; MASAKAZU IWAMURA: "Efficient Recognition of Objects by Cascading Approximate Nearest Neighbor Searches", MEETING ON IMAGE RECOGNITION AND UNDERSTANDING (MIRU2007), OS-B2-02, 2007, pages 111 - 118, XP008148817
NORITAKA HIMEI; TOSHIKAZU WADA: "Approximate nearest neighbor search algorithm on HDD based on B+ tree", IEICE, vol. 108, no. 484, 2009, pages 223 - 228
See also references of EP2442273A4
TAKAYUKI HONDO; KOICHI 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, vol. 108, no. 484, 2009, pages 171 - 176

Cited By (6)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2013246810A (ja) * 2012-05-30 2013-12-09 Denso It Laboratory Inc 情報検索装置、情報検索方法及びプログラム
KR101546653B1 (ko) 2012-06-26 2015-08-25 한국과학기술원 증강현실 기반의 실시간 관심 컨텍스트 등록 시스템 및 그 방법
JP2017517799A (ja) * 2014-05-14 2017-06-29 インテル・コーポレーション ソートミドルアーキテクチャにおけるフレームのフレームコヒーレンシへの活用
WO2017009958A1 (ja) * 2015-07-14 2017-01-19 富士通株式会社 圧縮プログラム、圧縮方法および圧縮装置
JPWO2017009958A1 (ja) * 2015-07-14 2018-04-26 富士通株式会社 圧縮プログラム、圧縮方法および圧縮装置
US10747725B2 (en) 2015-07-14 2020-08-18 Fujitsu Limited Compressing method, compressing apparatus, and computer-readable recording medium

Also Published As

Publication number Publication date
CN102460511A (zh) 2012-05-16
US20120084305A1 (en) 2012-04-05
JPWO2010143573A1 (ja) 2012-11-22
EP2442273A4 (en) 2014-04-23
JP5354507B2 (ja) 2013-11-27
EP2442273A1 (en) 2012-04-18
CN102460511B (zh) 2014-04-16

Similar Documents

Publication Publication Date Title
JP5354507B2 (ja) 物体認識用画像データベースの作成方法、作成装置および作成処理プログラム
Wang et al. Contextual weighting for vocabulary tree based image retrieval
Zheng et al. SIFT meets CNN: A decade survey of instance retrieval
JP5294342B2 (ja) 物体認識用画像データベースの作成方法、処理装置および処理用プログラム
JP4883649B2 (ja) 画像認識方法、画像認識装置および画像認識プログラム
US8254697B2 (en) Scalable near duplicate image search with geometric constraints
Jégou et al. On the burstiness of visual elements
Zheng et al. Packing and padding: Coupled multi-index for accurate image retrieval
US8892542B2 (en) Contextual weighting and efficient re-ranking for vocabulary tree based image retrieval
US9053386B2 (en) Method and apparatus of identifying similar images
Zheng et al. Visual phraselet: Refining spatial constraints for large scale image search
CN103324650A (zh) 一种图像检索方法及系统
JP5598925B2 (ja) 高次元の特徴ベクトルを高精度で検索する検索装置及びプログラム
JP6017277B2 (ja) 特徴ベクトルの集合で表されるコンテンツ間の類似度を算出するプログラム、装置及び方法
Amato et al. Large scale image retrieval using vector of locally aggregated descriptors
Zhou et al. Visual word expansion and BSIFT verification for large-scale image search
JP5833499B2 (ja) 高次元の特徴ベクトル集合で表現されるコンテンツを高精度で検索する検索装置及びプログラム
JP6364387B2 (ja) 特徴量生成装置、方法、及びプログラム
CN116737973A (zh) 一种基于倒排索引融合的多特征图像检索方法
Nayef et al. Efficient symbol retrieval by building a symbol index from a collection of line drawings
CN114595350B (zh) 一种百亿级图像快速搜索的方法
Kubytskyi et al. An Effective Approach to Image Embeddings for E-Commerce.
Feng et al. Efficient indexing for mobile image retrieval
CN121074913A (zh) 一种基于深度学习的工业图纸相似度检测方法
Inoue et al. Analysis of the effect of dataset differences on object recognition: the case of recognition methods based on exact matching of feature vectors

Legal Events

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

Ref document number: 201080035625.1

Country of ref document: CN

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

Ref document number: 10786104

Country of ref document: EP

Kind code of ref document: A1

WWE Wipo information: entry into national phase

Ref document number: 2011518472

Country of ref document: JP

WWE Wipo information: entry into national phase

Ref document number: 13376890

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: 2010786104

Country of ref document: EP