JP4917575B2 - Database device for image search, database management method for image search, and program - Google Patents

Description

  The present invention relates to an image search database device used for image search for outputting an image similar or related to an input image.

  Conventionally, as one of image search methods, a method (image input method) for outputting an image similar to or related to an input image is known. In recent years, as a new approach of this image input method, a method of searching for corresponding points between an input image and an image in a database and hitting the search if the number of corresponding points is large has been proposed. Here, the corresponding point is a combination of coordinate positions (coordinate points) at which patterns match between two images. In this method, an image having a very high degree of similarity with the input image can be output as a search result.

As a method for obtaining the corresponding points, for example, a method of calculating local feature amounts from feature points in an image using a calculation method such as SIFT has been proposed. According to such a method, corresponding points can be obtained accurately (see, for example, Non-Patent Document 1).
David G. Lowe, “Distinctive Image Features from Scale-Invariant Keypoints”, International Journal of Computer Vision (2004), Canada, January 5, 2004

However, in the image search using the local feature amount as described above, although the search accuracy is very high, it is necessary to obtain corresponding points for all images in the database, and a large number of images are stored in the database. Therefore, the amount of calculation required for image search becomes enormous, and it takes a very long time to execute the search. Therefore, conventionally, a method called Visual Words has been proposed (see, for example, Non-Patent Documents 2 and 3).
David Nister, 1 other, “Scalable Recognition with a Vocabulary Tree”, IEEE Conference on Computer Vision and Pattern Recognition (2006), 2006 James Philbin, 4 others, “Object retrieval with large vocabularies and fast spatial matching”, IEEE Conference on Computer Vision and Pattern Recognition (2007), 2007

  In Visual Words, local feature amounts are calculated as 128-dimensional vectors (also referred to as feature amount vectors) for all feature points included in each image, and the feature amount vectors are plotted in a vector space. After all feature vectors have been plotted for all images in the database, the vector space is divided into multiple subspaces (small rooms) based on a certain set of plots (a group of nearby plots). A process of dividing into two (referred to as clustering process) is performed. In this case, clustering processing is performed by expanding the local feature amounts of all feature points in the database on the memory. Then, a search table (also referred to as a search index) indicating the correspondence between each partial space and each image is created. In Visual Words, image search is performed using this search table, so even if there are many images in the database, the calculation amount is small.

  However, in the conventional method using Visual Words, once the search table is prepared, high-precision image search can be performed with a small amount of calculation even if there are many images in the database. In particular, there is a problem that a large capacity memory (working memory) is required for clustering processing.

  In particular, when a large amount of images are stored in the database, there is a problem that memory consumption for clustering processing becomes very large if local feature amounts of all feature points are expanded on a memory. For example, if millions of images are stored in the database, and if there are several thousand feature points in one image, the local feature values of all the feature points are expressed as 128-dimensional vectors. In order to represent and plot in the vector space, an enormous memory capacity of at least several tens to several hundreds GB is required. In this case, it is conceivable to substitute the HDD as a virtual memory, but in this case, there is a problem that the execution speed of the clustering process is significantly reduced.

  Once the search table is prepared and the database is updated (adding a new image), the local feature amounts of all feature points are expanded on the memory and clustering is performed again. There was a problem that it was necessary. Therefore, there is a problem that it is not easy to update the database sequentially (every time a new image is added to the database).

  The present invention has been made in view of the above problems, and even when a large amount of images are stored in the database, the memory capacity required for the clustering process can be reduced, and the database can be sequentially stored. An object of the present invention is to provide a database device for image search that can be updated.

  The image search database device of the present invention is an image search database device in which a plurality of images for image search are registered, and local feature amounts of a plurality of feature points included in each image are used as feature amount vectors. And a clustering process is performed in a vector space including a plurality of the feature amount vectors, the vector space is divided into a plurality of partial spaces, and a search table indicating a correspondence relationship between each partial space and each image is generated. The database device for image search has working storage means for storing a range of the partial space in the vector space and a larger storage capacity than the working storage means for use in the clustering process; For use in clustering processing, the feature vectors of the plurality of images are related to the subspace to which each feature vector belongs. And it includes a large capacity storage means for attaching and storing, the.

  According to this database device for image search, for clustering processing, the range of the partial space in the vector space is stored in the working storage means (memory or the like), and the feature quantity vector representing the local feature quantity is the partial What is necessary is just to memorize | store in mass storage means (HDD etc.) linked | related with space. Therefore, even when a large amount of images are stored in the database, the capacity of the working storage means (memory) necessary for the clustering process can be reduced.

  Further, the image search database device of the present invention includes a vector calculation means for calculating a local feature amount of a feature point included in an additional image newly registered as an image for image search as an additional feature amount vector, Read control means for reading out the feature quantity vector associated with the partial space to which the additional feature quantity vector belongs from the large-capacity storage means to the working storage means, the read feature quantity vector, and the additional feature quantity vector And a clustering processing means for performing a clustering process on the partial space to which the additional feature vector belongs, and subdividing the partial space.

  As a result, when a new image is to be added to the database, the feature amount vector (additional feature amount vector) of the feature point included in the additional image is calculated, and the subspace to which the additional feature amount vector belongs The feature vector associated with is read out. Then, a clustering process is performed on these feature quantity vectors to subdivide the partial space. In this way, the database can be updated sequentially (each time a new image is added to the database).

In addition, the image search database device of the present invention includes a degree-of-separation calculating means for calculating a degree of separation indicating a degree of separation of the feature amount vector in the partial space to which the additional feature amount vector belongs, and the degree of separation is a predetermined value. It is determined whether or not the threshold value is greater than the threshold value, and when the degree of separation is greater than a predetermined threshold value, clustering processing in the subspace is performed, and when the degree of separation is smaller than the predetermined threshold value, Determination control means for controlling clustering processing in the subspace so as not to perform clustering processing in the subspace;
May be provided.

  Thereby, based on the separation degree of the feature vector in the partial space, it is determined whether or not to perform the clustering process for dividing the partial space. For example, when the degree of separation is large, clustering processing in the subspace is performed, and when the degree of separation is small, clustering processing in the subspace is not performed. As described above, an appropriate clustering process is performed according to the degree of separation of the feature vector in the partial space.

  The database device for image search according to the present invention is a table for updating a correspondence relationship between the divided partial space and each image in the search table when the partial space is subdivided by the clustering processing unit. Update means may be provided.

  Thereby, when the partial space is subdivided by the clustering process, the search table is appropriately updated accordingly. Therefore, it is possible to search for an image reflecting a sequential database update.

  The image search database management method of the present invention is an image search database management method in which a plurality of images for image search are registered. In the image search database, a plurality of feature points included in each image are stored. Each local feature is represented as a feature vector, clustering processing is performed in a vector space including a plurality of the feature vectors, and the vector space is divided into a plurality of subspaces. A search table indicating a correspondence relationship has been generated, and the image search database management method stores a range of the partial space in the vector space in a work storage unit for use in the clustering process, Mass storage means having a larger storage capacity than the working storage means for use in the clustering process Includes, and storing in association with feature vectors of the plurality of images to each feature quantity subspace vector belongs.

  According to this method, for clustering processing, the range of the subspace in the vector space is stored in the working storage means (memory or the like), and the feature quantity vector representing the local feature quantity is associated with the subspace. What is necessary is just to memorize | store in a mass storage means (HDD etc.). Therefore, even when a large amount of images are stored in the database, the capacity of the working storage means (memory) necessary for the clustering process can be reduced.

Further, the image search database management method of the present invention calculates a local feature amount of a feature point included in an additional image newly registered as an image for image search as an additional feature amount vector, and the addition Reading out the feature vector associated with the partial space to which the feature vector belongs to the working storage unit from the large-capacity storage unit, and based on the read feature vector and the additional feature vector, Re-dividing the partial space by performing a clustering process in the partial space to which the additional feature vector belongs;
May be included.

  As a result, when a new image is to be added to the database, the feature amount vector (additional feature amount vector) of the feature point included in the additional image is calculated, and the subspace to which the additional feature amount vector belongs The feature vector associated with is read out. Then, a clustering process is performed on these feature quantity vectors to subdivide the partial space. In this way, the database can be updated sequentially (each time a new image is added to the database).

  The image search database management program of the present invention is an image search database management program in which a plurality of images for image search are registered. In the image search database, a plurality of feature points included in each image are stored. Each local feature is represented as a feature vector, clustering processing is performed in a vector space including a plurality of the feature vectors, and the vector space is divided into a plurality of subspaces. A search table indicating the correspondence relationship is generated, and the image search database management program stores the range of the partial space in the vector space in a work storage means for use in the clustering process in a computer. Larger than the working storage means for use in processing and clustering processing. The mass storage means having a Do storage capacity, it is intended to execute a process of storing in association with feature vectors of the plurality of images into subspaces belonging each feature vector.

  Also with this program, for clustering processing, the range of the partial space in the vector space is stored in the working storage means (memory, etc.), and the feature quantity vector representing the local feature quantity is associated with the partial space. What is necessary is just to memorize | store in capacity storage means (HDD etc.). Therefore, even when a large amount of images are stored in the database, the capacity of the working storage means (memory) necessary for the clustering process can be reduced.

  Further, the image search database management program according to the present invention includes a process of calculating a local feature amount of a feature point included in an additional image newly registered as an image search image in the computer as an additional feature amount vector. , A process of reading out the feature quantity vector associated with the partial space to which the additional feature quantity vector belongs from the large-capacity storage means to the working storage means, and the read feature quantity vector and the additional feature quantity vector Based on this, a process of performing a clustering process in the partial space to which the additional feature quantity vector belongs to re-divide the partial space may be executed.

  As a result, when a new image is to be added to the database, the feature amount vector (additional feature amount vector) of the feature point included in the additional image is calculated, and the subspace to which the additional feature amount vector belongs The feature vector associated with is read out. Then, a clustering process is performed on these feature quantity vectors to subdivide the partial space. In this way, the database can be updated sequentially (each time a new image is added to the database).

  According to the present invention, a large amount of images can be stored in a database by providing working storage means for storing a range of a partial space in a vector space and large capacity storage means for storing a feature quantity vector in association with the partial space. Even in such a case, the memory capacity required for the clustering process can be reduced, and the database can be updated sequentially.

  Hereinafter, an image search database apparatus according to an embodiment of the present invention will be described with reference to the drawings. In the present embodiment, the case of an apparatus used for an image search database using Visual Words is exemplified. This apparatus has a function of managing an image search database, and this function is realized by a program stored in a memory, an HDD, or the like of the apparatus.

  First, the configuration of an image search database device (also simply referred to as a database device) according to an embodiment of the present invention will be described with reference to the drawings.

  FIG. 1 is a block diagram for explaining the overall configuration of the database apparatus according to the present embodiment. As shown in FIG. 1, the database device 1 receives an input image and registers it in an image database 2, and an image to be processed from a plurality of images (input image or registered image). An image selection unit 4 that selects a feature point, a feature point extraction unit 5 that extracts a feature point from the selected image, and a local feature amount calculation unit 6 that calculates a local feature amount of the extracted feature point.

  Further, the database device 1 performs a clustering process in a vector space 7 that calculates a local feature amount of a feature point as a high-dimensional (for example, 128-dimensional) vector (a feature amount vector), and a vector space including the feature amount vector. A clustering processing unit 8 is provided. By the clustering process, the vector space is divided into a plurality of subspaces (small rooms called Visual Word). Here, an example in which the local feature amount is represented by a 128-dimensional vector will be described, but the scope of the present invention is not limited to this. The contents of this clustering process will be described later with reference to the drawings.

  Here, the configuration of the clustering processing unit 8 will be described with reference to FIG. As shown in FIG. 2, the clustering processing unit 8 includes a representative vector calculation unit 9 that calculates a representative vector representing a representative point (for example, the center of gravity) of the partial space as the range of the partial space in the vector space. In addition, the clustering processing unit 8 determines a degree of separation that calculates the degree of separation indicating the degree of separation of the feature quantity vectors in the subspace, and determines whether to perform clustering in the subspace based on the degree of separation. A control unit 11 is provided. Here, the degree-of-separation calculating unit 10 corresponds to the degree-of-separation calculating unit of the present invention, and the determination control unit 11 corresponds to the determination control unit of the present invention. The contents of the determination control based on the degree of separation will be described later with reference to the drawings.

  Returning to FIG. 1, the description of the configuration of the database apparatus 1 will be continued. The database apparatus 1 has a high data processing speed and a relatively small capacity memory 12, a large capacity HDD 13 (hard disk drive) having a large storage capacity although the data processing speed is slower than the memory 12, and writing to the memory 12 and the HDD 13. And a storage control unit 14 for controlling reading. The memory 12 stores a representative vector as a range of a partial space in the vector space, and the HDD 13 stores a feature vector associated with the partial space to which the feature vector belongs. Here, the memory 12 corresponds to the working storage means of the present invention, and the HDD 13 corresponds to the mass storage means of the present invention.

  The vector calculation unit 7 also calculates a local feature amount of a feature point as a feature amount vector (additional feature amount vector) for an image (additional image) newly registered in the image database 2. The storage control unit 14 reads out the feature vector associated with the partial space to which the additional feature vector belongs from the HDD 13 into the memory 12. The clustering processing unit 8 has a function of performing a clustering process in the partial space and re-dividing the partial space. Therefore, the vector calculation unit 7 corresponds to the vector calculation unit of the present invention, and the storage control unit 14 corresponds to the read control unit of the present invention. The clustering processing unit 8 corresponds to clustering processing means of the present invention.

  Further, the database device 1 includes a search table generation unit 15 that generates a search table that indicates the correspondence between each partial space and each image based on the result of the clustering process, and a search table storage unit that stores the generated search table 16 is provided. The search table generation unit 15 has a function of updating the search table when the partial space is subdivided. Therefore, the search table generation unit 15 corresponds to search table update means of the present invention. The database device 1 includes a search processing unit 17 that performs image search using the search table. The contents of the search table and image search will be described later with reference to the drawings.

  The operation of the database apparatus 1 configured as described above will be described with reference to the drawings. Here, three operations characteristic of the present invention, that is, initialization of the image database 2 (registration of the first image), update of the image database 2 (registration of the second and subsequent images), and image search are performed. The explanation is centered.

(Initialization of image database)
First, with reference to FIG. 3 to FIG. 6, an operation when the database apparatus 1 of the present embodiment performs initialization of the image database 2 (registration of the first image) will be described.

  When the image database 2 is initialized, first, an image to be registered first is selected by the image selection unit 4. In the example of FIG. 3, the image a of the computer is selected. The feature extraction unit 5 extracts feature points included in the image a. In this example, eight characteristic parts such as corners of the computer are extracted as characteristic points (shown as black circles in FIG. 8). Although the number of feature points is eight here for convenience of explanation, it goes without saying that the number of feature points is not limited to this.

  Next, the local feature amount calculation unit 6 calculates the local feature amounts of these feature points, and the vector calculation unit 7 expresses the local feature amount as a 128-dimensional feature amount vector. This feature vector is plotted in a 128-dimensional vector space (also referred to as a feature space). FIG. 3 illustrates an example in which eight feature quantity vectors a1 to a8 are plotted in a vector space. In this figure, the vector space is shown as two-dimensional for convenience of explanation.

  The clustering processing unit 8 performs clustering processing in the vector space, and divides the vector space into a plurality of partial spaces. FIG. 4 illustrates an example in which the vector space is divided into three partial spaces (partial spaces A to C). In the clustering process (division into partial spaces), one partial space is assigned for each feature quantity vector that is gathered to some extent. This clustering process is performed based on the degree of separation (or the degree of unity) of feature quantity vectors. As the degree of separation representing the degree of separation of the feature vector, for example, a dispersion ratio (= in-class dispersion / out-class dispersion) is used.

  Then, the representative vector calculation unit 9 calculates a representative vector as a range of each partial space. For example, a centroid vector of a plurality of feature amount vectors included in the partial space is calculated as a representative vector. In the example of FIG. 4, the representative vector of the subspace A is the centroid vector (shown by a circle A in the figure) of the feature vectors a1 to a4, and the representative vector of the subspace B is the feature vector a7. , A8 centroid vector (shown by a circle B in the figure), and the representative vector of the partial space C is a centroid vector of feature vectors a5 and a6 (shown by a circle C in the figure). is there.

  Based on the result of such clustering processing, the search table creation unit creates a search table as shown in FIG. The search table is a table showing the correspondence between each partial space and each image. In this case, the relationship between the partial spaces A to C and the image a is shown. That is, in the example of FIG. 5, it is shown that the partial spaces A to C correspond to the image a.

  The representative vector obtained as a result of the clustering process as described above is stored in the memory 12 by the storage control unit 14. Further, the feature quantity vector subjected to the clustering process at this time is stored in the HDD 13 in association with information indicating which partial space belongs. That is, only the representative vector of each partial space is stored in the memory 12, and the feature amount vector belonging to each partial space is stored in the HDD 13 in association with the partial space. In this case, a range of the partial space is stored in the memory 12, and an identification label (A, B, C, etc.) representing the partial space and a feature vector belonging to the partial space are stored in the HDD 13. It can be said that there is.

  In the example of FIG. 6, representative vectors of three partial spaces (partial spaces A to C) are stored in the memory 12. Even when the number of images and the number of feature points are large, the memory 12 only needs to store representative vectors, and the capacity of the memory 12 can be small. On the other hand, the HDD 13 stores four feature quantity vectors a1 to a4 as feature quantity vectors belonging to the partial space A, and stores two feature quantity vectors a7 and a8 as feature quantity vectors belonging to the partial space B. Two feature quantity vectors a5 and a6 are stored as feature quantity vectors belonging to C. When the number of images and the number of feature points are large, the data amount of these feature amount vectors becomes enormous, and the HDD 13 needs a large storage capacity.

(Image database update)
Next, with reference to FIG. 7 to FIG. 11, an operation when updating the image database 2 (registering the second and subsequent images) in the database apparatus 1 of the present embodiment will be described. Here, the operation when the second image is added to the image database 2 subjected to the initialization described with reference to FIGS. 3 to 6 will be described as an example.

  When updating the image database 2, first, the image to be registered next is selected by the image selection unit 4. In the example of FIG. 7, the computer image b is selected. Then, the feature points included in the image b are extracted by the feature extraction unit 5. Usually, a plurality of feature points are extracted from the image b, and the following processing is performed for each of the plurality of feature points. Here, for convenience of explanation, one feature point will be described first.

  In FIG. 7, the first feature point (shown as a black triangle mark in FIG. 7) included in the image b is extracted by the feature extraction unit 5. Then, the local feature amount calculation unit 6 calculates a local feature amount for this feature point, the vector calculation unit 7 expresses it as an additional feature amount vector, and is plotted in a vector space as shown in FIG. In this case, the additional feature amount vector b1 is plotted in the partial space A.

  In such a case, the storage control unit 14 reads out the feature quantity vectors a1 to a4 associated with the partial space A to which the additional feature quantity vector b1 belongs from the HDD 13 to the memory 12, and as shown in FIG. The quantity vectors a1 to a4 are plotted in the vector space (subspace A).

  Then, the clustering processing unit 8 performs clustering processing in the partial space A, and subdivides the partial space A into a plurality of partial spaces. FIG. 9 illustrates an example in which the partial space A is subdivided into two partial spaces (partial spaces A and D). This clustering process is also performed based on the degree of feature vector separation in the subspace, as described above. Also in this case, as the degree of separation, for example, a dispersion ratio (= in-class dispersion / out-class dispersion) is used. This degree of separation is calculated by the degree-of-separation calculation unit 10, and the determination control unit 11 determines whether this degree of separation is greater than a predetermined threshold value. In this case, it is determined that the degree of separation is greater than the threshold value, and the subspace A is subdivided by clustering processing.

  The degree of separation of the present invention is not limited to the above dispersion ratio. As the degree of separation, for example, the number of feature quantity vectors included in the partial space may be used. In this case, the determination control unit 11 performs clustering processing in the subspace so that the subspace is subdivided when the number of feature amount vectors included in the subspace exceeds a predetermined number (threshold value). May be controlled.

  When the subspace is subdivided, the representative vector calculation unit 9 calculates a representative vector of the subspace that has been subdivided. In this case, the representative vector of the subspace A that has been subdivided is the centroid vector (shown by a circle A in the figure) of the feature vectors a1 and a2, and the representative vector of the subspace D is the feature vector It is a center-of-gravity vector of a3, a4, and b1 (indicated by a circle D in the figure).

  Based on the result of such clustering processing of the partial space A, the search table creation unit updates the search table as shown in FIG. In this case, in the search table, the correspondence of the image b is added to the partial space A, the item of the partial space D is newly added, and the search table is updated so that the image a corresponds to the partial space D. Is called.

  Also, as shown in FIG. 11, the representative vector obtained as a result of the clustering process of the subspace A is stored in the memory 12 by the storage control unit 14. Further, as a result of the clustering process of the subspace A, the feature quantity vector subjected to the clustering process is stored in the HDD 13 in association with information in the subspace. In the example of FIG. 11, the data stored in the memory 12 is updated and the representative vectors of the two partial spaces A and D are stored. Also, the storage data of the HDD 13 is updated, two feature quantity vectors a1 and a2 are stored as feature quantity vectors belonging to the partial space A, and three feature quantity vectors a3, a4, b1 is stored.

(Another example of updating the image database)
In the above description, the example in which the subspace is subdivided when the image database 2 is updated has been described. Next, an example in which the subspace is not redivided when the image database 2 is updated will be described with reference to FIGS. Here, the operation when the second feature point is extracted following the extraction of the first feature point included in the image b described in FIGS. 7 to 11 will be described as an example.

  In FIG. 12, the second feature point (shown as a black triangle mark in FIG. 12) included in the image b is extracted by the feature extraction unit 5. Also for this feature point, the local feature quantity is calculated by the local feature quantity calculation unit 6, expressed as an additional feature quantity vector by the vector calculation unit 7, and plotted in a vector space as shown in FIG. 12. In this case, the additional feature vector b2 is plotted in the subspace D.

  Next, the storage control unit 14 reads out the feature quantity vectors a3, a4, b1 associated with the partial space D to which the additional feature quantity vector b2 belongs from the HDD 13 to the memory 12, and as shown in FIG. The quantity vectors a3, a4, b1 are plotted in the vector space (subspace D).

  In this case, the feature amount vectors belonging to the partial space D are gathered to some extent (not separated so much), and it is determined that the degree of separation of the feature amount vectors in the partial space D is smaller than the threshold value. Therefore, the clustering processing unit 8 does not perform the clustering process in the subspace D.

  Thereafter, the representative vector calculation unit 9 calculates the representative vector of the partial space D. In this case, the representative vector of the partial space D is the centroid vector (shown by a circle D in the figure) of the feature amount vectors a3, a4, b1, and b2.

  Based on the addition of the feature quantity vector b2, the search table creation unit updates the search table as shown in FIG. In this case, in the search table, the search table is updated so that the image a and the image b correspond to the partial space D.

  Further, as shown in FIG. 15, the representative vector obtained as a result of adding the feature vector b2 is stored in the memory 12 by the storage control unit 14. Further, as a result of the addition of the feature vector b2, the association between the partial space and the feature vector stored in the HDD 13 is updated. In the example of FIG. 15, an additional feature vector b2 is added to the subspace D.

(Image search)
Finally, with reference to FIG. 16 to FIG. 20, an operation when performing an image search in the database apparatus 1 of the present embodiment will be described. Here, an example in which an image search is performed using the image database 2 generated by the initialization / update as described above will be described.

  First, the image database 2 used for image search will be described. FIG. 16 illustrates a plot of feature quantity vectors when three images (images a to c) of a computer are registered in the image database 2. In this example, eight feature points are extracted from the image a, and eight feature quantity vectors (a1 to a8) are plotted. Also, six feature points are extracted from the image b, and six feature quantity vectors (b1 to b6) are plotted. Further, six feature points are extracted from the image c, and six feature quantity vectors (c1 to c6) are plotted. The vector space is divided into seven partial spaces (partial spaces A to G). In the example of FIG. 16, an example in which three images are registered in the image database 2 will be described for convenience of explanation, but it goes without saying that the number of images is not limited to this.

  In the above example, a search table as shown in FIG. 17 is created. In this search table, the images a and c correspond to the partial space A, and the images a and c correspond to the partial space B. Further, the image a corresponds to the partial space C, and the image b corresponds to the partial space D. Further, the images a and b correspond to the partial space E, and the images b and c correspond to the partial space F. Then, the images a to c correspond to the partial space G.

  In this case, as shown in FIG. 18, the memory 12 stores the representative vectors of the partial spaces A to G, and the HDD 13 stores the feature vector belonging to the partial space in association with the partial space. Has been. Specifically, three feature quantity vectors a1, a2, and c1 are stored as feature quantity vectors belonging to the partial space A, and three feature quantity vectors a7, a8, and c6 are stored as feature quantity vectors belonging to the partial space B. ing. Further, two feature quantity vectors a5 and a6 are stored as feature quantity vectors belonging to the partial space C, and three feature quantity vectors b2, b3 and b4 are stored as feature quantity vectors belonging to the partial space D. Further, two feature quantity vectors a3 and b1 are stored as feature quantity vectors belonging to the partial space E, and two feature quantity vectors b5 and c5 are stored as feature quantity vectors belonging to the partial space F. Then, five feature quantity vectors a4, b6, c2, c3, c4 are stored as feature quantity vectors belonging to the partial space G.

  Next, an image search operation using the search table will be described. When performing an image search, first, as shown in FIG. 19, an input image is selected by the image selection unit 4, and feature points included in the input image are extracted by the feature extraction unit 5. In this example, six feature points (shown as black stars in FIG. 19) are extracted.

  Next, the local feature quantity of these feature points is calculated by the local feature quantity calculation unit 6, and the local feature quantity is expressed as a feature quantity vector by the vector calculation unit 7. Then, this feature vector is plotted in a vector space. In the example of FIG. 19, feature vectors are plotted in the subspaces D, E, F, and G.

  The search processing unit 17 reads the search table and counts the number of images corresponding to the partial spaces (partial spaces D, E, F, and G) on which the feature amount vectors are plotted. In the example of FIG. 20, the number of images a corresponding to the partial spaces D, E, F, and G is two, and the number of images b corresponding to the partial spaces D, E, F, and G is four, The number of images c corresponding to the partial spaces D, E, F, and G is two. As a result, it can be seen that the number of images b is the largest. Therefore, in this case, a search result called image b is obtained as the image most similar to the input image.

  In such a search using Visual Words, it is only necessary to determine which partial space (Visual Word) the local feature amount of the input image belongs to, so that the search can be executed very quickly. Note that the subspace (Visual Word) to which the feature vector belongs can be efficiently found by using a nearest neighbor search algorithm such as a Best-Bin-First algorithm.

  According to such an image search database device 1 of the present embodiment, by providing the memory 12 that stores the range of the partial space in the vector space and the HDD 13 that stores the feature quantity vector in association with the partial space, Even when a large amount of images are stored in the database, the capacity of the memory 12 required for the clustering process can be reduced, and the database can be updated sequentially.

  That is, in this embodiment, for clustering processing, a representative vector of a partial space is stored in the memory 12, and a feature vector representing a local feature is stored in the HDD 13 in association with the partial space. Good. Therefore, even when a large amount of images are stored in the database, the capacity of the memory 12 required for the clustering process can be reduced.

  In this embodiment, when a new image is to be added to the database, a feature amount vector (additional feature amount vector) of a feature point included in the additional image is calculated, and the additional feature amount vector The feature quantity vector associated with the partial space to which the data belongs is read from the HDD 13 to the memory 12. Then, a clustering process is performed on these feature quantity vectors to subdivide the partial space. In this way, the database can be updated sequentially (each time a new image is added to the database).

  Specifically, in the conventional Visual Words method, when n images are registered in the image database 2, the calculation amount o (n) required for executing the clustering process increases according to the number n of images. . Therefore, when a large number of images are registered in the database, it takes a very long time to execute the clustering process. On the other hand, in the present embodiment, the calculation amount o (1) required for executing the clustering process does not depend on the number n of images. Therefore, even when a large number of images are registered in the database, the clustering process can be executed in a short time, and the database can be updated sequentially.

  In the present embodiment, based on the degree of separation of the feature quantity vectors in the partial space, it is determined whether or not to perform clustering processing for dividing the partial space. For example, when the degree of separation is large, clustering processing in the subspace is performed, and when the degree of separation is small, clustering processing in the subspace is not performed. Thereby, an appropriate clustering process according to the degree of separation of the feature quantity vectors in the partial space is performed.

  In the present embodiment, when the subspace is subdivided by the clustering process, the search table is appropriately updated accordingly. Therefore, it is possible to search for an image reflecting a sequential database update.

  The embodiments of the present invention have been described above by way of example, but the scope of the present invention is not limited to these embodiments, and can be changed or modified according to the purpose within the scope of the claims. is there.

  As described above, the database device for image search according to the present invention requires a small memory capacity for the clustering process even when a large amount of images are stored in the database. It is useful as an image search database using Visual Words.

It is a block diagram which shows the structure of the database apparatus for image search in this Embodiment. It is a block diagram which shows the structure of a clustering process part. It is explanatory drawing of the plot of the feature-value vector when registering the 1st image. It is explanatory drawing of the clustering process in vector space. It is a figure which shows the search table when registering the 1st image. It is a figure which shows the data memorize | stored in a memory and HDD. It is explanatory drawing of the plot of the additional feature-value vector when registering the 2nd image. It is explanatory drawing of the reading of the feature-value vector in a partial space. It is explanatory drawing of the clustering process in a partial space. It is explanatory drawing of the update of a search table. It is a figure which shows the data memorize | stored in a memory and HDD. It is explanatory drawing of the plot of the additional feature-value vector when registering the 2nd image. It is explanatory drawing of the reading of the feature-value vector in a partial space. It is explanatory drawing of the update of a search table. It is a figure which shows the data memorize | stored in a memory and HDD. It is explanatory drawing of the plot of the feature-value vector when a some image is registered. It is a figure which shows a search table when a several image is registered. It is a figure which shows the data memorize | stored in a memory and HDD. It is explanatory drawing of the plot of the feature-value vector contained in an input image. It is explanatory drawing of the image search using a search table.

Explanation of symbols

DESCRIPTION OF SYMBOLS 1 Database apparatus 2 Image database 3 Image reception part 4 Image selection part 5 Feature point extraction part 6 Local feature-value calculation part 7 Vector calculation part 8 Clustering process part 9 Representative vector calculation part 10 Separation degree calculation part 11 Judgment control part 12 Memory 13 HDD
14 Storage Control Unit 15 Search Table Generation Unit 16 Search Table Storage Unit 17 Search Processing Unit

Claims (4)

An image search database device in which a plurality of images for image search are registered,
Each local feature amount of a plurality of feature points included in each image is represented as a feature amount vector, and clustering processing is performed in a vector space including the plurality of feature amount vectors to divide the vector space into a plurality of partial spaces. And a search table showing the correspondence between each partial space and each image is generated,
The image search database device comprises:
Working storage means for storing a range of the subspace in the vector space for use in the clustering process;
A large-capacity storage unit that has a larger storage capacity than the working storage unit, and stores the feature amount vectors of the plurality of images in association with a partial space to which each feature vector belongs, for use in the clustering process;
Vector calculation means for calculating a local feature amount of a feature point included in an additional image newly registered as an image for image search as an additional feature amount vector;
Read control means for reading out the feature quantity vector associated with the partial space to which the additional feature quantity vector belongs from the mass storage means to the working storage means;
Clustering processing means for performing a clustering process on the partial space to which the additional feature quantity vector belongs based on the read feature quantity vector and the additional feature quantity vector, and subdividing the partial space;
When the partial space is subdivided by the clustering processing means, a table updating means for updating a correspondence relationship between the divided partial space and each image in the search table;
An image search database device comprising: A degree-of-separation calculating means for calculating a degree of separation indicating the degree of separation of the feature amount vector in the partial space to which the additional feature amount vector belongs;
It is determined whether or not the degree of separation is greater than a predetermined threshold value. If the degree of separation is greater than the predetermined threshold value, clustering processing in the subspace is performed, and the degree of separation is determined to be a predetermined threshold value. A determination control means for controlling the clustering process in the subspace so as not to perform the clustering process in the subspace, if smaller than the value;
The database device for image search according to claim 1 , further comprising: A method of managing an image search database in which a plurality of images for image search are registered,
In the image search database, local feature amounts of a plurality of feature points included in each image are represented as feature amount vectors, and clustering processing is performed in a vector space including the plurality of feature amount vectors. Is divided into a plurality of subspaces, and a search table showing the correspondence between each subspace and each image is generated,
The image search database management method includes:
Storing the range of the subspace in the vector space in a working storage means for use in the clustering process;
Storing the feature quantity vectors of the plurality of images in association with the partial space to which each feature vector belongs in a large capacity storage means having a larger storage capacity than the working storage means for use in the clustering process;
Calculating a local feature amount of a feature point included in an additional image newly registered as an image for image search as an additional feature amount vector;
Reading out the feature vector associated with the partial space to which the additional feature vector belongs from the large-capacity storage unit to the working storage unit;
Based on the read feature quantity vector and the additional feature quantity vector, clustering processing is performed in the partial space to which the additional feature quantity vector belongs, and the subspace is subdivided;
When the partial space is subdivided by the clustering process, updating the correspondence relationship between the divided subspace and each image in the search table;
A database management method for image retrieval, comprising: An image search database management program in which a plurality of images for image search are registered,
In the image search database, local feature amounts of a plurality of feature points included in each image are represented as feature amount vectors, and clustering processing is performed in a vector space including the plurality of feature amount vectors. Is divided into a plurality of subspaces, and a search table showing the correspondence between each subspace and each image is generated,
The image search database management program is stored in a computer.
A process for storing a range of the partial space in the vector space in a working storage means for use in the clustering process;
A process of storing the feature quantity vectors of the plurality of images in association with the partial space to which each feature quantity vector belongs in a large capacity storage means having a larger storage capacity than the working storage means for use in the clustering process;
Processing for calculating a local feature amount of a feature point included in an additional image newly registered as an image for image search as an additional feature amount vector;
A process of reading a feature vector associated with a partial space to which the additional feature vector belongs from the large-capacity storage unit to the working storage unit;
Based on the read feature quantity vector and the additional feature quantity vector, a process of performing a clustering process in the partial space to which the additional feature quantity vector belongs to re-divide the partial space;
When the subspace is subdivided by the clustering process, in the search table, a process of updating a correspondence relationship between the divided subspace and each image;
The database management program for image retrieval characterized by performing this.