JP6035173B2 - Image search system and image search method - Google Patents

Description

  The present invention relates to an image search system and an image search method for searching a corresponding image corresponding to a query image from a large number of reference images.

  When extracting corresponding points between a plurality of images, local image feature amounts are used. For example, if two images obtained by photographing one subject from two different viewpoints are used, triangulation can be performed when device-specific information called internal parameters such as the focal length of the photographed equipment is given. In principle, the distance from the shooting location to the subject can be measured, and the size of the subject can be estimated.

  At this time, a certain point on the subject is projected on each of the two images, and is commonly observed between the two images. In order to detect a point (corresponding point) observed in common between two images, a local image feature amount is used. That is, it is determined that a point where the local image feature amounts match is a corresponding point.

  It is known that image search can be realized by applying this local image feature amount. In this image retrieval technology, a plurality of images are stored in a database, feature points are extracted from all the images, and local image feature amounts of the extracted feature points are calculated, and these are also stored in the database. Keep it. When a query image is input, feature points are extracted from the query image, and their local image feature amounts are calculated. Then, for each of the plurality of images stored in the database, feature points having local image feature amounts that match the local image feature amounts of feature points included in the query image are counted as corresponding points, and the number of corresponding points is It is determined that the most images are the images most similar to the query image.

  Further, in the image search technique using the local image feature amount, the position information of the feature point is also used. As described above, in the image search technique using the local image feature amount, an image having many feature points corresponding to the feature points of the query image is determined as an image close to the query image among the images in the database. Thus, when it is determined that the corresponding point is a comparison point only by comparing the local image feature amounts, it is erroneously determined that the points that do not actually correspond but coincide with each other by chance are the corresponding points. Become.

  In order to prevent such misjudgment due to noise, not only whether or not the local image feature quantity of a feature point of a query image matches the local image feature quantity of a feature point of an image in the database, The geometric projection relationship between the position of the feature point and the position of the feature point of the image in the database is obtained, and it is determined whether the feature point of the query image is correctly projected onto the feature point of the image in the database. In addition, there is a method for determining whether or not those feature points are corresponding points together with the determination result.

  Specifically, when it can be assumed that the subject is a two-dimensional plane such as a paper surface, it is determined whether or not the positions of feature points having the same local image feature amount also match as follows. To do. First, all pairs of feature points having the same local image feature amount are detected between the query image and the image in the database. A homography matrix that projects the position of the feature point of the query image to the position of the feature point of the image in the database paired with the feature point using the RANSAC method for the set of the plurality of feature points Calculate

  Further, the position of the feature point of the query image determined to match the feature point of the image in the database and the local image feature amount is projected again by the homography matrix. And the position obtained as a result is calculated how much the feature point of the query image and the position of the feature point of the image in the database determined to match the local image feature amount (position matching), Based on the calculation result (matching score), it is finally determined whether or not those feature points are corresponding points.

  By the way, when hundreds of feature points are extracted from one image, local image feature amounts for each point are calculated, and when compared with the local image feature amounts of other images, the amount of data used for the calculation Requires a huge memory, a high-speed CPU, and a huge storage for storage. In the case of a SIFT feature quantity generally known as a local image feature quantity, in addition to the local image feature quantity, incidental information such as scale information, position information, and spindle information is used as feature point data representing information of each feature point. Is included. If these are added for all feature points, for example, if one image contains 800 feature points, the data amount is about 422 Kbytes per image. For this reason, for example, when 10,000 images are used as a search target, the amount of data to be handled is (422 Kbytes × 10,000), which is approximately 4.2 Gbytes.

  In response to such a problem, techniques such as ORB, brisk, and CARD have been proposed as techniques for speeding up the extraction of corresponding points by compressing the local image feature quantity of each feature point. Have also filed a patent application regarding such technology (Patent Document 1). In these techniques, the local image feature value is compressed by expressing the local image feature value of each feature point with a binary vector instead of a real vector. In addition, by adopting a calculation method different from the conventional one, high speed calculation of the local image feature amount is realized.

  In addition, there exist the following prior art documents as a prior art relevant to this invention.

JP 2012-160047 A

David G. Lowe, "Object recognition from local scale-invariant features," International Conference on Computer Vision, Corfu, Greece (September 1999), pp. 1150-1157

  An object of the present invention is to suppress the amount of data used for image search in an image search technique using local image feature amounts.

  When the local image feature amount is compressed, the inventors of the present application have a relatively large proportion of the amount of accompanying information such as position information and spindle information, and further reduce the amount of feature point information and perform computation If the local image feature value is compressed, reducing the data amount of the accompanying information may reduce the additional data amount of the feature point information. It has been found that it is advantageous for reducing the amount of data and increasing the calculation speed.

  That is, the feature point data includes accompanying information such as scale information, position information, and spindle information in addition to the local image feature amount of the point, but when the local image feature amount is not compressed. The ratio of the data amount of the accompanying information to the entire data amount of the feature point data is small, and the data amount of the accompanying information does not become a problem. Specifically, for example, the data amount of scale information, position information, and spindle information is 4 bytes and 8 bytes (4 bytes × 2 because the position is two-dimensional) when expressed in a general real number type. 4 bytes, the total data amount of the accompanying information is 16 bytes. On the other hand, if the local image feature amount is a 128-dimensional real number, the data amount is (128 × 4 =) 512 bytes. Therefore, the ratio of the data amount of the accompanying information to the total data amount is only about 3% (16 / (512 + 16) =).

  On the other hand, in the feature point data including the compressed local image feature amount, since the data amount of the local image feature amount is reduced, scale information, position information, spindle information, etc. are attached to the entire data amount. The ratio of the data amount of information becomes relatively large. Specifically, when the local image feature amount is compressed to 128 bits (= 16 bytes), the ratio of the data amount of the accompanying information to the total data amount is (16 / (16 + 16) =) 50%. Also become.

  In the image search, information on the main axis and scale is not used, so these can be deleted. However, even if they can be deleted, the position information is necessary, and the amount of position information in the feature point data (8 bytes) is (8 / (16 + 8) =) about 33%. Therefore, it is advantageous to reduce information other than the local image feature amount in the feature point data.

  To this end, the image search system of the present invention is an image search system including a query image processing device and a search server device, and the query image processing device includes local image feature quantities of a plurality of feature points in the query image. A feature point including a local image feature quantity extraction unit for extracting the feature point, a feature point position coarse quantization unit for coarsely quantizing the position information of the feature point, and the local image feature quantity and the coarsely quantized position information A query image processing device side communication unit for transmitting data, wherein the search server device receives the feature point data, and the local image feature amount included in the received feature point data And an image search unit that searches for a corresponding image corresponding to the query image from a plurality of reference images using the position information.

  According to this configuration, since the position information of the feature point from which the local image feature amount is extracted is roughly quantized in the query image processing device, the ratio of the data amount of the position information to the entire data amount of the feature point data Can be reduced. In particular, when the local image feature amount is compressed by binary conversion or the like, the effect of reducing the data amount of the position information by coarse quantization becomes large.

  In the image search system, the image search unit may further include a position information conversion unit that converts the coarsely quantized position information into position information of the original image size. According to this configuration, the position information of the feature points of the query image is restored in the image search unit that searches for the corresponding image corresponding to the query image.

  In the image search system, the feature point position coarse quantization unit may be capable of changing a coarse quantization level when performing the coarse quantization. According to this configuration, the data amount of the position information can be changed according to the necessity and possibility of reducing the data amount.

  In the image search system, the feature point position coarse quantization unit may change the coarse quantization level according to a communication state of the query image processing device side communication unit. According to this configuration, it is possible to perform control such as changing the coarse quantization level when the communication state is not good and reducing the amount of position information data.

  In the image search system, the feature point position coarse quantization unit may change the coarse quantization level according to a processing state of the query image processing apparatus. According to this configuration, it is possible to perform control such as changing the coarse quantization level when the processing capacity of the query image processing apparatus is not sufficient, thereby reducing the amount of position information.

  In the image search system, the feature point position coarse quantization unit may change the coarse quantization level in accordance with an image size of the query image. According to this configuration, it is possible to perform control such as reducing the amount of position information as the image size is smaller.

  In the image search system, the feature point position coarse quantization unit may coarsely quantize the feature point position information so as to have a data amount of 2 bytes. According to this configuration, the data amount can be sufficiently reduced as compared with the normal case where the position information that is a real number is expressed by about 8 bytes.

  In the image search system, the search server device may further include an image storage unit that stores the local image feature quantities and position information of a plurality of feature points in the plurality of reference images in association with each other. A comparison matching unit that obtains a pair of feature points corresponding to each other by comparing the local image feature amount of the query image and the local image feature amount of the feature point of the reference image; A projection determination unit that obtains a pair of feature points corresponding to each other by projecting either one of the position information and the position information of the reference image to the other; The reference image including the largest number of feature points determined and determined to correspond by the projection determination unit may be used as the corresponding image.

  According to this configuration, instead of simply comparing the local image feature quantities of feature points, it is possible to search for a corresponding image by counting feature points that correspond to positions as corresponding points. To improve the accuracy of the corresponding image search.

  An image search system according to another aspect of the present invention is an image search system including a query image processing device and a search server device, wherein the query image processing device is a local image feature quantity of a plurality of feature points in a query image. And a query image processing device side communication unit that transmits feature point data including position information, and the search server device includes a search server device side communication unit that receives the feature point data, and a plurality of reference images. Comparing the local image feature quantity of the feature point and the coarsely quantized position information in association with each other, and comparing the local image feature quantity of the query image and the local image feature quantity of the feature point of the reference image A comparison matching unit for obtaining a pair of feature points corresponding to each other, and projecting one of the position information of the query image and the position information of the reference image to the other A projection determination unit that obtains a pair of feature points corresponding to each other, and includes the largest number of feature points that are determined to correspond by the comparison matching unit and that are determined to correspond by the projection determination unit. The reference image is determined to be a corresponding image corresponding to the query image.

  According to this configuration, when a corresponding image corresponding to a query image is searched from a large amount of reference images using feature point data including local image feature amounts and position information of feature points, the feature points of the reference image The capacity of the storage for storing the data can be suppressed, or the feature point data of many reference images can be stored by the storage having a limited capacity.

  In the above-described image search system, the search server device may further include a position information conversion unit that converts the coarsely quantized position information of the reference image into position information of the original image size. With this configuration, when searching for a corresponding image corresponding to a query image from a large number of reference images, position information of feature points of the reference image is restored.

  In the above-described image search system, the query image processing device may be a portable information terminal that further includes an imaging unit that generates the query image by shooting. According to this configuration, the user of the query image processing apparatus can generate a query image by photographing.

  In the above image search system, the search server device side communication unit may transmit the corresponding image and / or related information associated with the corresponding image, and the query image processing device side communication unit may transmit the corresponding image. And / or the related information may be received. According to this configuration, in the query image processing device, it is possible to acquire the corresponding image and related information corresponding to the query image.

  Another aspect of the present invention is the query image processing device in an image search system including a query image processing device and a search server device, wherein the query image processing device is a local image of a plurality of feature points in the query image. A local image feature amount extraction unit for extracting feature amounts; a feature point position coarse quantization unit for coarsely quantizing the position information of the feature points; and the local image feature amount and the coarsely quantized position information. A query image processing device side communication unit that transmits the feature point data to the search server device.

  Also with this configuration, the position information of the feature point from which the local image feature amount has been extracted is roughly quantized, so that the ratio of the data amount of the position information to the entire data amount of the feature point data can be reduced.

  Another aspect of the present invention is the search server device in an image search system including a query image processing device and a search server device, the search server device receiving a plurality of query images from the query image processing device. A communication unit that receives feature point data including local image feature amounts and position information of feature points, and stores local image feature amounts and coarsely quantized position information of a plurality of feature points in a plurality of reference images in association with each other. An image storage unit that compares the local image feature amount of the query image with the local image feature amount of the feature point of the reference image, thereby obtaining a pair of feature points corresponding to each other, and A projection determination unit that obtains a pair of feature points corresponding to each other by projecting one of the position information of the query image and the position information of the reference image to the other. Configuration for determining that the reference image including the largest number of feature points determined to correspond by the comparison matching unit and determined to correspond by the projection determination unit is a corresponding image corresponding to the query image have.

  Even with this configuration, when searching for a corresponding image corresponding to a query image from a large number of reference images using feature point data including local image feature quantities and position information of feature points, the feature point data of the reference image The capacity of the storage for storing the image can be reduced, or the feature point data of many reference images can be stored by the storage having a limited capacity.

  Another aspect of the present invention is an image search method in an image search system including a query image processing device and a search server device, and the image search method is executed by the query image processing device. A local image feature amount extraction step for extracting local image feature amounts of a plurality of feature points, a feature point position coarse quantization step for coarsely quantizing position information of the feature points, and the local image feature amount and coarse quantization A query image processing device side communication step for transmitting feature point data including the position information, and a search server device side communication step for receiving the feature point data, which is executed by the search server device, Image search for searching for a corresponding image corresponding to the query image from a plurality of reference images using the local image feature amount and the position information included in the feature point data And a step.

  Also with this configuration, the position information of the feature point from which the local image feature amount has been extracted is roughly quantized, so that the ratio of the data amount of the position information to the entire data amount of the feature point data can be reduced.

  Another aspect of the present invention is a query image processing program, wherein the query image processing program causes a computer to extract a local image feature quantity of a plurality of feature points in the query image, A feature point position coarse quantization unit that coarsely quantizes position information of feature points, and a communication unit that transmits feature point data including the local image feature amount and the coarsely quantized position information to a search server device; To function as.

  Also with this configuration, the position information of the feature point from which the local image feature amount has been extracted is roughly quantized, so that the ratio of the data amount of the position information to the entire data amount of the feature point data can be reduced.

  Another aspect of the present invention is a search server program, and the search server program associates and stores local image feature amounts of a plurality of feature points and coarsely quantized position information in a plurality of reference images. A computer that includes a storage unit; a communication unit that receives, from the query image processing device, feature image data including local image feature values and position information of a plurality of feature points in the query image; and the local image feature values of the query image A comparison matching unit that obtains a pair of feature points corresponding to each other by comparing the feature points of the reference image with the local image feature amount, and any of the position information of the query image and the position information of the reference image By projecting one of them to the other, it is made to function as a projection determination unit that obtains a pair of feature points corresponding to each other, and it is determined that the comparison matching unit corresponds. Is, and determines that the reference image with the highest concentration feature points determined to correspond to the at the projection determination unit, the corresponding image corresponding to the query image.

  Even with this configuration, when searching for a corresponding image corresponding to a query image from a large number of reference images using feature point data including local image feature quantities and position information of feature points, the feature point data of the reference image The capacity of the storage for storing the image can be reduced, or the feature point data of many reference images can be stored by the storage having a limited capacity.

  According to the present invention, the position information of feature points from which local image feature values are extracted is roughly quantized, so that the ratio of the data amount of position information can be reduced, thereby suppressing the amount of data used for image search. Can do.

The block diagram which shows the structure of the image search system in embodiment of this invention The block diagram which shows the structure of the feature point data generation part in embodiment of this invention The figure which shows the example of the comparison matching in embodiment of this invention Flow chart for calculating transformation matrix in the embodiment of the present invention

  Hereinafter, an image search system according to an embodiment of the present invention will be described with reference to the drawings. The embodiment described below shows an example when the present invention is implemented, and the present invention is not limited to the specific configuration described below. In carrying out the present invention, a specific configuration according to the embodiment may be adopted as appropriate.

  FIG. 1 is a diagram showing a configuration of an image search system according to an embodiment of the present invention. In the image search system 100, a query image processing apparatus 10 and a search server apparatus 20 are connected to be communicable via a network NW. A part of the network NW may be wireless. The query image processing apparatus 10 may be a portable information terminal, and the configuration shown in FIG. 1 may be realized by executing an application.

  The query image processing apparatus 10 is an apparatus that captures an image to be searched and transmits it as a query image to the search server apparatus 20 and acquires related information related to the query image from the search server apparatus 20. When the search server device 20 receives the query image from the query image processing device 10, the search server device 20 searches for an image including a subject corresponding to the subject included in the query image, and associates it with the searched image and / or the searched image. The related information is returned to the query image processing apparatus 10 as information related to the query image.

  The image search system 100 can be applied in various ways depending on the image stored in the search server device 20 and the related information associated therewith. In the present embodiment, an example in which the image search system 100 is applied as a system for searching posters will be described. That is, the search server device 20 stores a plurality of poster images as search target images, and each poster image is associated with related information related to the poster. When the user captures a poster image in the query image processing apparatus 10 and sends the data to the search server apparatus 20, the search server apparatus 20 searches for an image corresponding to the captured poster image. The searched image and related information accompanying it are returned to the query image processing apparatus 10.

  The application example of the image search system 100 is not limited to this. For example, a large number of book cover images are stored in the search server device 20 and each stored image is accompanied by information such as a user review of each book, information for purchase, and other related books as related information. By doing so, the image search system 100 can be applied as a book search system. Moreover, the image search system 100 can be applied as a sightseeing spot guidance system by storing an image of a building or the like peculiar to a sightseeing spot in the search server device 20 and a description of the building as related information. Furthermore, the image search system 100 can be applied as a bird search system by storing the image of the bird in the search server device 20 and the URL of the web page describing the description of the bird as related information.

  The query image processing apparatus 10 includes an imaging unit 11, a feature point data generation unit 12, a communication unit 13, a communication state measurement unit 14, and a coarse quantization level determination unit 15. The imaging unit 11 is a general camera unit including an optical system, an imaging element, a signal processing circuit, and the like. The imaging unit 11 captures a subject through an optical system, and outputs an image signal (hereinafter simply referred to as “image”) from the signal processing circuit to the feature point data generation unit 12.

  FIG. 2 is a block diagram illustrating a configuration of the feature point data generation unit 12. The feature point data generation unit 12 includes a feature point detection unit 31, a local image feature amount extraction unit 32, a binary conversion unit 33, a feature point position rough quantization unit 34, and a data synthesis unit 35. An image generated by shooting by the imaging unit 11 (see FIG. 1) is input to the feature point detection unit 31.

  The feature point detection unit 31 detects feature points from the input image. The feature point detection unit 31 extracts an edge from the image to generate an edge image, and detects the feature point from the edge image. Any existing algorithm can be adopted as an algorithm for detecting feature points. The feature point detector 31 also detects the size of the input image. The feature point detection unit 31 outputs, for all the detected feature points, feature point information including information for identifying the feature points, image size, and information on the position of the feature points in the image, to the local image feature amount extraction unit 32 and The result is output to the feature point position coarse quantization unit 34. Note that the feature point position information is the X coordinate and Y coordinate of the feature point, and the X coordinate and Y coordinate values are based on one pixel of the input image. Since the feature point is determined like an intersection of two straight lines, its X coordinate and Y coordinate are generally not integers but single precision real numbers (32 bits). Note that the X coordinate and Y coordinate of the position information may be obtained as double-precision real number (64-bit) data or a real number type with higher accuracy.

  The local image feature amount extraction unit 32 extracts the local image feature amount of each feature point detected by the feature point detection unit 31. A known technique can be used as a method for extracting a local image feature quantity. For example, as a method for calculating a local image feature quantity as a 128-dimensional vector, a method using a SIFT feature quantity (David G. Lowe, “Distinctive image features from scale-invariant keypoints,” International Journal of Computer Vision, 60, 2 (2004), pp. 91-110. In the local image feature quantity extraction unit 32, the local image feature quantity is obtained as a single-precision real vector. The local image feature amount extraction unit 32 outputs the extracted local image feature amount together with the identification information of each feature point to the binary conversion unit 33.

The binary conversion unit 33 converts the local image feature values of all the detected feature points into binary codes. Since the local image feature amount extracted by the local image feature amount extraction unit 32 is a 128-dimensional vector vεR ¹²⁸ , the binary conversion unit 33 converts the local image feature amount into a binary code by the following equation (1). Convert.

また、ベクトルｗ_kは、１２８次元における半径１の超球上の点から、一様分布に従ってランダムサンプリングをして得られるベクトルである。ｗ_k（ｋ＝１，……ｄ）は、１２８行ｄ列の行列として表現できる。本実施の形態では、バイナリコードのビット長を１２８ビットとし、即ちｄ＝１２８とする。バイナリ変換部３３は、各特徴点について、その識別情報とともに、バイナリコードに変換された局所画像特徴量をデータ合成部３５に出力する。 In equation (1), d is the size (that is, the number of bits) of the binary code after conversion, and the sgn function is given by the following equation (2).

The vector w _k is a vector obtained by random sampling according to a uniform distribution from a point on a hypersphere having a radius of 1 in 128 dimensions. w _k (k = 1,... d) can be expressed as a matrix of 128 rows and d columns. In this embodiment, the bit length of the binary code is 128 bits, that is, d = 128. The binary conversion unit 33 outputs the local image feature amount converted into the binary code together with the identification information for each feature point to the data synthesis unit 35.

  The feature point position coarse quantization unit 34 roughly quantizes the position information of each feature point detected by the feature point detection unit 31. The level of coarse quantization (granularity) is specified by the coarse quantization level determination unit 15 (see FIG. 1). A method for determining the coarse quantization level will be described later. As described above, the position coordinates of feature points are given as single-precision real numbers. The feature point position coarse quantization unit 34 roughly quantizes a real value obtained by dividing the X coordinate and Y coordinate values of the feature point by the width and height of the input image at a designated coarse quantization level.

  For example, the image size of the input image is 320 × 240, the position coordinates of a certain feature point are (21.568987..., 37.908325...), And the coarse quantization level is 256 (8 Bit), the X coordinate 21.568987 ... 21.568987 ... × (256/320) = 17.25 ... and the Y coordinate 37.908325 ... 37.908325 ... × (256/240) = 40.43 ... Therefore, the position coordinates of the coarsely quantized feature points are (17, 40). The amount of data of the position information of the coarsely quantized feature point is 16 bits (2 bytes) as a whole because the X coordinate and the Y coordinate are 8 bits (1 byte) each. It should be noted that by adjusting the coarse quantization level, the feature point position coarse quantization unit 34 may coarsely quantize the feature point position information so that the X coordinate and the Y coordinate are each 16 bits (2 bytes). Good.

  For each feature point, the feature point position coarse quantization unit 34 generates a feature point identification information, an image size of the input image, a coarse quantization level, and a position coordinate of the coarsely quantized feature point. 35. The data composition unit 35 determines the image size of the input image obtained by the feature point position coarse quantization unit 34 with respect to the local image feature amount generated by the binary conversion unit 33 for the feature points having the same identification information. And the coarse quantization level and the position coordinates of the coarsely quantized feature points are attached as accompanying information to generate feature point data. The feature point data generated by the data synthesis unit 35 in this way is output to the communication unit 13 (see FIG. 1).

  Returning to FIG. 1, the description of the image search system 100 will be continued. The communication unit 13 transmits a plurality of feature point data of the query image generated by the feature point data generation unit 12 to the search server device 20 via the network NW.

  Note that the above-described series of processing by the imaging unit 11, the feature point data generation unit 12, and the communication unit 13 may be performed on one image generated by the release operation at the imaging unit 11. In addition, images generated in the past by the imaging unit 11 are stored in a storage (not shown), and the feature point data generation unit 12 and the communication unit 13 can select and specify the stored images. The above-described processing may be performed. Further, the preview moving image may be continuously generated by the imaging unit 11, and the above-described processing by the feature point data generating unit 12 and the communication unit 13 may be sequentially performed on each frame image of the preview moving image.

  The communication state measurement unit 14 measures the communication state by the communication unit 13. Here, the communication state may be the received electric field strength when the query image processing apparatus 10 is a wireless terminal. The communication state may be a communication speed or a line speed.

  The coarse quantization level determination unit 15 determines the coarse quantization level according to the communication state measured by the communication state measurement unit 14. Specifically, the coarse quantization level determination unit 15 decreases the coarse quantization level as the communication state is poor, and increases the coarse quantization level as the communication state is good. The coarse quantization level is information indicating the number of stages in which feature point position information (X coordinate and Y coordinate) is expressed. The rough quantization level determination unit 15 outputs the determined rough quantization level to the feature point position rough quantization unit 34 of the feature point data generation unit 12.

  Next, the search server device 20 will be described. The search server device 20 includes a reference image acquisition unit 21, a feature point data generation unit 22, and an image database 23 as a configuration for constructing a reference image database. The reference image acquisition unit 21 acquires an image to be stored in the image database 23. The reference image acquisition unit 21 may acquire a reference image from the outside via the communication unit 24, or may acquire a reference image by another method.

  The feature point data generation unit 22 receives the image acquired by the reference image acquisition unit 21 and generates feature point data for a plurality of feature points included in each image. The configuration is the same as the configuration of the feature point data generation unit 12 of the query image processing apparatus 10 described with reference to FIG. However, the coarse quantization level employed by the feature point position coarse quantization unit 34 may be fixed, specified by the user, or specified by some other means. The feature point data generated by the feature point data generation unit 22 is stored in the image database 23.

  The image database 23 stores image data, feature point data, and related information data in association with each reference image. Note that the image data and the related information data may be stored in another storage unit and associated with the feature point data stored in the image database 23 by identification information or the like.

  Here, the related information is information returned to the query image processing apparatus 10 as one of the image search results. The image search system 100 according to the present embodiment searches for a poster image as described above, and as related information, detailed information on the notification by the poster or a website to which such detailed content is posted. An access method (URL or the like) is included. That is, when the user of the query image processing apparatus 10 sees a poster in the city, for example, if the user captures the poster and requests the search server apparatus 20 for detailed contents, the search server apparatus 20 adds the captured image to the captured image. A corresponding reference image is searched, and related information associated with the detected reference image is returned to the user. Thereby, the user can know the detailed contents of the photographed poster.

  The search server device 20 further includes a communication unit 24, a comparison matching unit 25, a position information conversion unit 26, a conversion matrix calculation unit 27, and a projection determination unit 28 as a configuration for performing an image search. A configuration including the comparison matching unit 25, the position information conversion unit 26, the conversion matrix calculation unit 27, and the projection determination unit 28 corresponds to an image search unit. The communication unit 24 receives feature point data transmitted from the query image processing apparatus 10.

  The comparison matching unit 25 compares the feature point data received by the communication unit 24 with all feature point data of all stored reference images, and calculates a matching score indicating the degree of matching. Since the local image feature quantities of the query image and the reference image are both binary-coded into the same number of bits, the degree of coincidence can be calculated at high speed by calculating their Hamming distance. The comparison matching unit 25 employs a Hamming distance for evaluating the degree of coincidence of the binary code.

  Regardless of the position of the feature point, the comparison matching unit 25 counts the set of feature points having the highest degree of matching, in other words, the set of feature points having the smallest difference in local image feature amounts as the corresponding points. In this way, it is determined that all feature points of the query image correspond to any feature point of any reference image, that is, all feature points of the query image are voted for any reference image. Become.

  FIG. 3 is a diagram illustrating an example of comparison matching in the comparison matching unit 25. In the example of FIG. 3, eleven feature points are detected from the query image C, and the local image feature amounts are extracted. In the reference images R1 to R4, the feature points shown in FIG. The amount has been extracted. In practice, several hundred feature points are detected from one image, but only some feature points are shown in FIG. 3 for the sake of simplicity.

  In FIG. 3, sets of feature points having the highest degree of coincidence (hereinafter simply referred to as “corresponding points”) are connected by lines. In the example of FIG. 3, the corresponding points are detected from the reference images R1 to R3 at 5 points, 2 points, and 4 points, respectively, and no corresponding points are detected from the reference image R4. The comparison matching unit 25 detects an image having a predetermined number of corresponding points or more as a corresponding image candidate. In the example of FIG. 3, the comparison matching unit 25 detects a reference image having three or more corresponding points as a corresponding image candidate. As a result, reference images R1 and R3 are detected as corresponding image candidates.

  With respect to the corresponding points of these corresponding image candidates, in the subsequent processing, the position information also corresponds, it is determined whether or not it is a true corresponding point, and the corresponding points that are determined to correspond also to the position information The reference image with the largest number of is determined to be the corresponding image of the query image. Hereinafter, a configuration for determining whether or not position information corresponds will be described.

  The position information conversion unit 26 converts the position information of the feature points of the query image and the corresponding image candidate acquired from the comparison matching unit 25. The position information conversion unit 26 converts the position information by performing processing reverse to the rough quantization of the position information performed by the feature point position rough quantization unit 34. At this time, the position information conversion unit 26 converts the position information of the coarsely quantized feature points using the information of the image size and the coarse quantization level among the information attached to the image.

  In the above example, the position coordinates of the coarsely quantized feature points are (17, 40), the image size is 320 × 240, and the coarse quantization level is 256. In this example, the X coordinate of the converted position is (17 × (320/256) =) 22.2500, the Y coordinate is (40 × (240/256) =) 37.5000, The position coordinates are (22.2500, 37.5000). Since the original coordinates are (21.568987... 37.908325...), A slight error occurs due to coarse quantization and subsequent restoration. There is no problem if the error is sufficiently larger than this error.

  When the position information of all corresponding points of the query image and the corresponding image candidate is converted in this way, the conversion matrix calculating unit 27 calculates a conversion matrix for projecting the corresponding point for each corresponding image candidate. Specifically, the transformation matrix calculation unit 27 calculates a homography matrix as a transformation matrix using the RANSAC method. Specifically, it is as follows.

FIG. 4 is a flowchart of the conversion matrix calculation in the conversion matrix calculation unit 27. The conversion matrix calculation unit 27 performs the processing of the flowchart of FIG. 4 for each corresponding image candidate, and obtains a conversion matrix for each corresponding image candidate. Assume that there are n pairs of corresponding points between a query image and a corresponding image candidate. The corresponding points of the query image are a _i (x _i , y _i ), and the corresponding points of the corresponding image candidate are A _i (X _i , Y _i ) (i = 1 to n). At this time, assuming that the subject is a two-dimensional plane, there exists a transformation matrix H that satisfies the following (3).

（４）においてｗを消去すると以下の（５）の連立方程式が得られる。

When (3) is expanded, the following (4) is obtained.

When w is eliminated in (4), the following simultaneous equations (5) are obtained.

Since the two simultaneous equations of (5) above are obtained for one set of corresponding points, if there are four sets of corresponding points, eight simultaneous equations are obtained, and by solving this, a transformation matrix is obtained. Eight elements (h ₁₁ , h ₁₂ , h ₁₃ , h ₂₁ , h ₂₂ , h ₂₃ , h ₃₁ , h ₃₂ ) included in H can be obtained.

Therefore, the conversion matrix calculation unit 27 selects any four sets of corresponding points from the n sets of corresponding points between the query image and the corresponding image candidate, and obtains the conversion matrix H as described above (step S41). . Next, the transformation matrix calculation unit 27 uses this transformation matrix H to obtain a projection error for all n pairs of corresponding points (step S42). Specifically, the projection error e _i of each pair of corresponding points is calculated by the following (6).

Next, the transformation matrix calculation unit 27, for each corresponding point, the projection error e _i is a predetermined threshold (tolerance) is smaller than inliers (inliers) or, each project errors e _i is equal to or greater than the predetermined threshold out It is determined whether it is an outlier, the total number of inliers is counted, and it is determined whether the total number of inliers has increased (step S43). When the total number of inliers increases (YES in step S43), the transformation matrix H is updated with the transformation matrix H at that time (step S44). When the total number of inliers has not increased (NO in step S43), the transformation matrix H is not updated.

  Next, it is determined whether or not the processing of steps S41 to 44 has reached the specified number of times (step S45), and if not (NO in step S45), steps S41 to S43 are repeated. When the specified number of times has been reached (YES in step S45), the conversion matrix H at that time is determined as a conversion matrix for converting the query image into the corresponding image candidate and output (step S46).

  The projection determining unit 28 projects all corresponding points of the corresponding image candidate with the conversion matrix H determined for each corresponding image candidate by the conversion matrix calculating unit 27, and the projection error between the corresponding points of the query image. Ask for. For each corresponding point, it is determined whether the projection error is smaller than the predetermined threshold (allowable error) (inlier) or the projection error is equal to or greater than the predetermined threshold (outlier), and the total number of inliers is finally determined The number of points. A set of corresponding points of the inlier is a set of corresponding points satisfying the geometric consistency. The projection determination unit 28 performs such processing on all corresponding image candidates, and determines that the corresponding image candidate having the largest final corresponding points is a corresponding image including the same subject as the subject in the query image. .

  The projection determining unit 28 reads related information associated with the reference image determined to be a corresponding image from the image database 23 and outputs the related information to the communication unit 24. The communication unit 24 transmits related information to the query image processing apparatus 10. As a result, the user of the query image processing apparatus 10 can acquire related information related to the subject photographed by the user from the search server apparatus 20.

  As described above, in the present embodiment, the query image processing apparatus 10 that transmits query image data and receives related information related to the query image, and receives the query image and searches for the corresponding image. In the search server device 20 that returns the associated related information to the query image processing device 10, a configuration is adopted in which the amount of data is reduced by coarse quantization of the position information of the feature points extracted from the local image feature amounts.

  By reducing the amount of feature point position information in the query image processing apparatus 10, there is an advantage that communication delay can be reduced or prevented, and communication costs can be reduced. For example, if 500 average feature points are detected per image and the line speed is 1 Mbps, the time required to transmit all feature point data for one image is not compressed. Then, (500 × (128 × 4 + 4 + 8 + 4) / 125000 =) is about 2 seconds, and when only the local image feature amount is converted into a binary code and compressed, it becomes about 0.08 second, and the position information of the feature point is further obtained. When coarse quantization and compression are performed, it takes about 0.02 seconds.

  Further, by reducing the data amount of the feature point position information in the search server device 20, the capacity of the storage for storing a large amount of reference images can be reduced, or the storage of a limited capacity There is an advantage that more reference images can be stored. For example, if 1000 feature points are detected for each of 1000 reference images, and an average of 500 feature points per image is detected, the capacity required for storing the feature point data of 1000 reference images Is (1000 × 500 × (128 × 4 + 4 + 8 + 4) =) 264 Mbytes, and when only the local image feature amount is converted into binary code and compressed, it becomes (1000 × 500 × (4 + 4 + 8 + 4) =) 10 Mbytes, When the positional information of the feature points is coarsely quantized and compressed, (1000 × 500 × (4 + 2) =) 3 MB.

  As described above, in each of the query image processing device 10 and the search server device 20, an effect is obtained by adopting a configuration in which the amount of data is reduced by rough quantization of the position information of the feature points from which the local image feature values are extracted. Therefore, only one of the query image processing device 10 and the search server device 20 may employ a configuration in which the amount of data is reduced by coarsely quantizing the position information of feature points obtained by extracting local image feature amounts. In addition, it has been confirmed by experiments by the inventors of the present application that the search result of the corresponding image is not affected even when the position information is subjected to coarse quantization at least as described above.

  Note that the search server device 20 not only determines the reference image with the most final corresponding points as the corresponding image, but also the reference images with the second largest number of corresponding points in the second, third,. Alternatively, the related information may be read from the image database 23 and transmitted to the query image processing apparatus 10 together with the reference image having the most final corresponding points or in response to a request from the query image processing apparatus 10.

  In the above embodiment, the comparison matching unit 25 uses only reference images having a predetermined number or more of corresponding points as corresponding image candidates to perform position information matching and obtain final corresponding points. All reference images including at least one point may be set as corresponding image candidates.

  In the above-described embodiment, the comparison matching unit 25 counts a pair of feature points having the smallest difference in local image feature values as corresponding points, but the method of comparison matching is not limited to this. For example, the comparison matching unit 25 compares the local image feature amounts of all feature points of the query image C with the local image feature amounts of all feature points included in the reference images R1 to R4, and the degree of coincidence is predetermined. A set of feature points that exceed the threshold value, that is, a set of feature points in which the difference in the local image feature amount is within a predetermined error range may be detected. In this case, each feature point of the query image may be voted for a plurality of reference images, and may not be voted for any reference image.

  In the above embodiment, the coarse quantization level determination unit 15 may determine the coarse quantization level according to the image size. In this case, the coarse quantization level may be the same as the image size. That is, the feature point position rough quantum unit 34 roughly rounds the X and Y coordinates of the feature point position obtained by the feature point detection unit 31 to a whole number by rounding down or rounding up the feature point position. It may be quantized. For example, when the position coordinates of the feature points are (21.568987 ..., 37.908325 ...) as described in the above embodiment, the feature point position coarse quantization unit 34 May be rounded off to obtain the position coordinates (22, 38) of the coarsely quantized feature points.

  The coarse quantization level determination unit 15 detects the processing state in the query image processing device 10, specifically, the available memory capacity and / or the calculation speed (utilization rate of the arithmetic processing device), and detects the detected state. It may be determined based on the value.

  Further, in the above embodiment, the transformation matrix H is a matrix that projects the feature points of the reference image, and the feature points of the reference image are projected by the transformation matrix H and projected with the corresponding feature points of the query image. Although the error was evaluated, conversely, the matrix that projects the feature points of the query image to the feature points of the reference image is used as a transformation matrix, the feature points of the query image are projected by the transformation matrix, The projection error may be evaluated.

  According to the present invention, since the position information of the feature point from which the local image feature amount is extracted is coarsely quantized, the ratio of the data amount of the position information can be reduced, thereby suppressing the amount of data used for the image search. It is useful as a search system and an image search method for searching for a corresponding image corresponding to a query image from a large number of reference images.

DESCRIPTION OF SYMBOLS 100 Image search system 10 Query image processing apparatus 11 Imaging part 12 Feature point data generation part 13 Communication part 14 Communication state measurement part 15 Coarse quantization level determination part 20 Search server apparatus 21 Reference image acquisition part 22 Feature point data generation part 23 Image Database 24 Communication unit 25 Comparison matching unit 26 Location information conversion unit 27 Transformation matrix calculation unit 28 Projection determination unit 31 Feature point detection unit 32 Local image feature amount extraction unit 33 Binary conversion unit 34 Feature point position coarse quantization unit 35 Data synthesis unit

Claims (19)

An image search system comprising a query image processing device and a search server device,
The query image processing device includes:
A local image feature amount extraction unit that extracts local image feature amounts of a plurality of feature points in the query image;
A feature point position coarse quantization unit for coarsely quantizing the position information of the feature points;
A query image processing device side communication unit for transmitting feature point data including the local image feature value and the coarsely quantized position information;
With
The search server device
A search server device side communication unit for receiving the feature point data;
An image search unit that searches for a corresponding image corresponding to the query image from a plurality of reference images using the local image feature amount and the position information included in the received feature point data;
With
The image retrieval unit, crude quantized images retrieval system that is characterized in that further comprising a position information converting unit that converts the position information of the original image size the position information. An image search system comprising a query image processing device and a search server device,
The query image processing device includes:
A local image feature amount extraction unit that extracts local image feature amounts of a plurality of feature points in the query image;
A feature point position coarse quantization unit for coarsely quantizing the position information of the feature points;
A query image processing device side communication unit for transmitting feature point data including the local image feature value and the coarsely quantized position information;
With
The search server device
A search server device side communication unit for receiving the feature point data;
An image search unit for searching for a corresponding image corresponding to the query image from a plurality of reference images using the local image feature amount and the position information included in the received feature point data;
With
The feature point position rough quantization unit images retrieval system that characterized in that it is changing the coarse quantization levels when performing the coarse quantization. The image search system according to claim 2 , wherein the feature point position coarse quantization unit changes the coarse quantization level according to a communication state of the query image processing device side communication unit. The image search system according to claim 2 , wherein the feature point position coarse quantization unit changes the coarse quantization level according to a processing state of the query image processing apparatus. The image search system according to claim 2 , wherein the feature point position coarse quantization unit changes the coarse quantization level according to an image size of the query image. An image search system comprising a query image processing device and a search server device,
The query image processing device includes:
A local image feature amount extraction unit that extracts local image feature amounts of a plurality of feature points in the query image;
A feature point position coarse quantization unit for coarsely quantizing the position information of the feature points;
A query image processing device side communication unit for transmitting feature point data including the local image feature value and the coarsely quantized position information;
With
The search server device
A search server device side communication unit for receiving the feature point data;
An image search unit for searching for a corresponding image corresponding to the query image from a plurality of reference images using the local image feature amount and the position information included in the received feature point data;
With
The feature point position coarse quantization unit coarsely quantizes the position information of the feature point so as to have a data amount of 2 bytes. The search server device further includes an image storage unit that stores local image feature amounts and position information of a plurality of feature points in the plurality of reference images in association with each other,
The image search unit
A comparison matching unit for obtaining a set of feature points corresponding to each other by comparing the local image feature amount of the query image and the local image feature amount of the feature point of the reference image;
A projection determination unit for obtaining a pair of feature points corresponding to each other by projecting one of the position information of the query image and the position information of the reference image to the other;
The reference image including the largest number of feature points determined to correspond by the comparison matching unit and determined to correspond by the projection determination unit is defined as the corresponding image. 7. The image retrieval system according to any one of items 6 to 6 . An image search system comprising a query image processing device and a search server device,
The query image processing device includes a query image processing device side communication unit that transmits feature point data including local image feature amounts and position information of a plurality of feature points in the query image,
The search server device
A search server device side communication unit for receiving the feature point data;
An image storage unit that associates and stores local image feature quantities and coarsely quantized position information of a plurality of feature points in a plurality of reference images;
A comparison matching unit for determining a set of feature points corresponding to each other by comparing the local image feature amount of the query image and the local image feature amount of the feature point of the reference image;
A projection determination unit for obtaining a pair of feature points corresponding to each other by projecting one of the position information of the query image and the position information of the reference image to the other;
A position information conversion unit that converts the position information roughly quantized of the reference image into position information of an original image size;
The reference image including the most feature points determined to correspond by the comparison matching unit and determined to correspond by the projection determination unit is determined to be a corresponding image corresponding to the query image. An image search system characterized by The image search system according to any one of claims 1 to 8 , wherein the query image processing device is a portable information terminal further including an imaging unit that generates the query image by photographing. The search server device side communication unit transmits the corresponding image and / or related information associated with the corresponding image,
The query image processing apparatus side communication unit, the corresponding image and / or image retrieval system according to any one of claims 1 to 9, characterized in that to receive the relevant information. The query image processing device in an image search system comprising a query image processing device and a search server device,
A local image feature amount extraction unit that extracts local image feature amounts of a plurality of feature points in the query image;
A feature point position coarse quantization unit for coarsely quantizing the position information of the feature points;
A query image processing device side communication unit for transmitting feature point data including the local image feature amount and the coarsely quantized position information to the search server device;
Equipped with a,
The query image processing apparatus, wherein the feature point position coarse quantization unit is capable of changing a coarse quantization level when performing the coarse quantization .   The query image processing device in an image search system comprising a query image processing device and a search server device,
  A local image feature amount extraction unit that extracts local image feature amounts of a plurality of feature points in the query image;
  A feature point position coarse quantization unit for coarsely quantizing the position information of the feature points;
  A query image processing device side communication unit for transmitting feature point data including the local image feature amount and the coarsely quantized position information to the search server device;
  With
  The feature point position coarse quantization unit coarsely quantizes the feature point position information so as to have a data amount of 2 bytes. The search server device in an image search system comprising a query image processing device and a search server device,
A communication unit that receives feature point data including local image feature amounts and position information of a plurality of feature points in the query image from the query image processing device;
An image storage unit that associates and stores local image feature quantities and coarsely quantized position information of a plurality of feature points in a plurality of reference images;
A comparison matching unit for determining a set of feature points corresponding to each other by comparing the local image feature amount of the query image and the local image feature amount of the feature point of the reference image;
A projection determination unit for obtaining a pair of feature points corresponding to each other by projecting one of the position information of the query image and the position information of the reference image to the other;
A position information conversion unit that converts the position information roughly quantized of the reference image into position information of an original image size;
The reference image including the most feature points determined to correspond by the comparison matching unit and determined to correspond by the projection determination unit is determined to be a corresponding image corresponding to the query image. And a search server device. An image search method in an image search system comprising a query image processing device and a search server device,
A local image feature amount extraction step for extracting local image feature amounts of a plurality of feature points in the query image, which is executed by the query image processing device;
A feature point position coarse quantization step for coarsely quantizing the position information of the feature points;
A query image processing device side communication step for transmitting feature point data including the local image feature amount and the coarsely quantized position information;
A search server device side communication step for receiving the feature point data, which is executed by the search server device;
An image search step of searching for a corresponding image corresponding to the query image from a plurality of reference images using the local image feature amount and the position information included in the received feature point data;
Only including,
The image search method includes a position information conversion step of converting the coarsely quantized position information into position information of an original image size .   An image search method in an image search system comprising a query image processing device and a search server device,
  Executed by the query image processing apparatus
  A local image feature amount extraction step for extracting local image feature amounts of a plurality of feature points in the query image;
  A feature point position coarse quantization step for coarsely quantizing the position information of the feature points;
  A query image processing device side communication step for transmitting feature point data including the local image feature amount and the coarsely quantized position information;
  Executed in the search server device
  A search server side communication step of receiving the feature point data;
  An image search step of searching for a corresponding image corresponding to the query image from a plurality of reference images using the local image feature amount and the position information included in the received feature point data;
  Including
  The image search method, wherein the feature point position coarse quantization unit can change a coarse quantization level when performing the coarse quantization.   An image search method in an image search system comprising a query image processing device and a search server device,
  Executed by the query image processing apparatus
  A local image feature amount extraction step for extracting local image feature amounts of a plurality of feature points in the query image;
  A feature point position coarse quantization step for coarsely quantizing the position information of the feature points;
  A query image processing device side communication step for transmitting feature point data including the local image feature amount and the coarsely quantized position information;
  Executed in the search server device
  A search server side communication step of receiving the feature point data;
  An image search step of searching for a corresponding image corresponding to the query image from a plurality of reference images using the local image feature amount and the position information included in the received feature point data;
  Including
  In the feature point position coarse quantization step, the position information of the feature point is coarsely quantized so as to have a data amount of 2 bytes. Computer
A local image feature amount extraction unit that extracts local image feature amounts of a plurality of feature points in the query image;
A feature point position coarse quantization unit that coarsely quantizes the position information of the feature point, and a communication unit that transmits feature point data including the local image feature amount and the coarsely quantized position information to a search server device ,
To function as,
The feature point position coarse quantization unit is a query image processing program capable of changing a coarse quantization level when performing the coarse quantization .   Computer
  A local image feature amount extraction unit that extracts local image feature amounts of a plurality of feature points in the query image;
  A feature point position coarse quantization unit for coarsely quantizing the position information of the feature points; and
  A communication unit that transmits feature point data including the local image feature value and the coarsely quantized position information to a search server device;
  Function as
  The feature point position coarse quantization unit is a query image processing program that coarsely quantizes the position information of the feature point so as to have a data amount of 2 bytes. A computer including an image storage unit that stores the local image feature quantities of the plurality of feature points in the plurality of reference images and the coarsely quantized position information in association with each other;
A communication unit that receives feature point data including local image feature amounts and position information of a plurality of feature points in the query image from the query image processing device;
A comparison matching unit that determines a pair of feature points corresponding to each other by comparing the local image feature amount of the query image and the local image feature amount of a feature point of the reference image ;
A projection determination unit for obtaining a pair of feature points corresponding to each other by projecting one of the position information of the query image and the position information of the reference image to the other; and
A position information conversion unit that converts the position information roughly quantized of the reference image into position information of an original image size;
The reference image including the largest number of feature points determined to correspond by the comparison matching unit and determined to correspond by the projection determination unit is a corresponding image corresponding to the query image. A search server program characterized by determining.

Images