JP6678445B2 - Quantizer and operation method of quantizer - Google Patents

Description

  The present invention relates to a technique for clustering and holding multidimensional vector data in a vector space.

  For example, in image recognition (or image collation) technology such as similar image search, a method called BoVW (Bag of Visual Words) has recently been used. In this method, a local feature amount, which is multidimensional vector data extracted from a plurality of images (referred to as learning images) serving as a population, is clustered (each cluster is referred to as a visual word, and Visual Words = VW). Vector space region is allocated and held, and if the local feature of the image to be recognized belongs to or does not belong to any cluster, and if it belongs to the cluster, it belongs to that cluster This is a method of specifying an image similar to the recognition image in a population based on the number of appearances (appearance frequencies) of local feature amounts. By quantizing the local feature amount, which is multidimensional data, image recognition and the like can be processed at high speed.

  Here, the accuracy of image recognition tends to depend on the size of the vector space area allocated to each cluster. If it is too wide, an image to be recognized as dissimilar may be extracted as a similar image, and if it is too narrow, an image to be recognized as similar may be determined as a dissimilar image. Therefore, when registering a new visual word in order to keep each area by clustering within an appropriate predetermined range, each registered visual word is searched, and a local feature amount that is the same or close to a predetermined range in the local feature amount is searched. Is not registered as a new visual word (Patent Document 1).

JP 2015-22466 A

  By proceeding with the new registration processing of the visual word as described above, the vector space area is filled with each cluster while each cluster has a predetermined area. Accordingly, the frequency of local feature amounts extracted from the learning image being registered as new visual words decreases. It is useless to continue the process for registering a new visual word even if the number of registered visual words is satisfied.

  As exemplified, when performing analysis or recognition of an object using multidimensional vector data extracted from an object such as an image or a sound, the registration of each cluster in a vector space is stopped under a predetermined condition, It is desirable to suppress unnecessary processing for registering a new cluster.

  Therefore, in order to solve the above problem, the present invention provides the following quantization device and the like. That is, the vector data acquisition unit for acquiring multidimensional vector data, the cluster holding unit for holding a plurality of areas in the vector space in which neighboring multidimensional vector data are clustered, and the acquired multidimensional vector data The inclusion determination unit that determines whether the region is included in the region, and if the determination result by the inclusion determination unit is not included, a new region is stored in the cluster holding unit based on the acquired multidimensional vector data. A cluster registration unit to be registered, an inclusion determination result history recording unit that records an inclusion determination result history that is a history of a determination result that the determination result by the inclusion determination unit is included, and an inclusion determination result record And a stop judging unit for judging whether the inclusion judgment result history in the unit satisfies a predetermined condition for stopping the new registration of the area. Results provide such quantizer having a stop control unit for controlling the cluster registration unit to stop a new registration of a cluster registration unit when a determination result of the predetermined condition is satisfied.

  According to the present invention, a process of newly registering a region in a vector space is stopped based on a history of determination results on whether or not multidimensional vector data extracted for registration is included in a region in an existing vector space. It is possible to prevent the process for new registration from being performed unnecessarily.

FIG. 2 is a block diagram illustrating an example of a functional configuration of the quantization device. Conceptual diagram showing an example of local features extracted from a recognition target image Conceptual diagram showing an example of processing for registering an area in a vector space Diagram showing an example of the inclusion determination result history Diagram showing an example of the inclusion determination result history Schematic diagram illustrating an example of a hardware configuration of the quantization device Flow chart showing an example of the flow of processing in the present quantization device

Hereinafter, embodiments of the present invention will be described with reference to the accompanying drawings. It should be noted that the present invention is not limited to these embodiments at all, and can be implemented in various modes without departing from the gist thereof.
<Embodiment>
<Overview>

The quantization device according to the present embodiment performs a process of registering a new cluster based on a history of determination results as to whether or not the multidimensional vector data extracted for registration is included in a region already clustered in the vector space. It is characterized by stopping. With this configuration, it is possible to prevent the process for newly registering the cluster from being performed unnecessarily.
<Structure>

  FIG. 1 is a block diagram illustrating an example of functional blocks of the quantization device according to the present embodiment. The functional blocks of the present apparatus described below can be realized as a combination of hardware and software. Specifically, if a computer is used, a CPU (Central Processing Unit), a main memory, a system bus, or a secondary storage device (a hard disk drive, a non-volatile memory, a storage medium such as a CD or a DVD, and such a medium) Read drive, etc.), input devices used for information input, display devices, and other external peripheral devices, such as hardware components, interfaces for the external peripheral devices, communication interfaces, and control of these hardware Driver programs, other application programs, user interface applications, and the like.

  Then, by arithmetic processing of the CPU in accordance with the program developed on the main memory, data input from an input device or other interfaces and stored in the memory or the hard disk are processed and accumulated, and the above-described hardware, Instructions for controlling software are generated. Alternatively, the functional blocks of the present device may be realized by dedicated hardware. Further, the present apparatus is not limited to the case where the apparatus is configured by one piece of hardware or software, and may be configured by a combination of a plurality of pieces of hardware or software, or may be configured to include a server apparatus via a network.

  The present invention can be realized not only as an apparatus but also as a method. Further, a part of the invention can be configured as software. Further, a program used for causing a computer to execute such software, and a recording medium on which the program is fixed are naturally included in the technical scope of the present invention (the same applies throughout the present specification).

  As shown in FIG. 1, the quantization apparatus 0100 of the present embodiment includes a vector data acquisition unit 0101, a cluster holding unit 0102, an inclusion determination unit 0103, a cluster registration unit 0104, an inclusion determination result history recording unit 0105, It has a suspension determination unit 0106 and a suspension control unit 0107.

The vector data acquisition unit 0101 has a function of acquiring multidimensional vector data. The subject of acquiring multidimensional data, for example, feature quantity of the image and sound, the water level or tide, ground motion (movement of the ground), all that is expressed by numerical values such as density distribution of CO ₂ and PM2.5 atmospheric It is. An example of the multidimensional data is a local feature that can be acquired for an image.

  The local feature amount in an image is a feature amount obtained from a feature region that can be variously defined according to a target or arbitrarily defined by a person who analyzes and recognizes the target. For example, in an image, an area such as a contour or a corner corresponds.

  In addition, various techniques for acquiring vector data from a target already exist depending on the target, and there is no limitation on which one to use. For example, when acquiring vector data for an image, a technique such as SIFT or HoG can be used. The vector data obtained by these methods is hundreds of high-dimensional vector data.

  Hereinafter, each configuration will be described using an image as an example of a target from which vector data is acquired.

  FIG. 2 is a conceptual diagram exemplifying vector data to be obtained when the target for obtaining vector data is an image. As shown in FIG. 2A, the image of the “track” is targeted, and a point indicated by a circle in the figure is a characteristic region, and the characteristic amount in the region is acquired as vector data.

  The cluster holding unit 0102 has a function of holding a plurality of regions in a vector space obtained by clustering neighboring multidimensional vector data. An area that is clustered in such a vector space is called a visual word in technical fields such as image recognition. Then, the vector space is clustered based on the distance between multidimensional vector data (such as the Euclidean distance). For example, FIG. 2B is a conceptual diagram illustrating a vector space divided by 10 visual words.

  The cluster is held, for example, by linking multidimensional vector data representing the cluster with the ID of the cluster. Further, a distance (distance from multidimensional vector data representing the cluster) specified for determining that the cluster is included may be stored together.

  Further, the multidimensional vector data associated with the cluster ID may be the vector data itself obtained from the target, or may be changed as the total number of clusters increases due to the cluster registration process described later.

  The inclusion determining unit 0103 has a function of determining whether the acquired multidimensional vector data is included in any of the regions. As described above, the retained cluster has a predetermined range based on multidimensional vector data representing the cluster and a defined distance. For example, it is a circular area having a radius defined by a distance defined around the multidimensional vector data.

  FIG. 3 is a conceptual diagram schematically showing cluster registration. FIG. 3A is a conceptual diagram in which regions of five held clusters are arranged in a vector space 0300. The cluster 0301 of ID1 has an area within a predetermined range (within a dotted circle). The same applies to the clusters of ID2 to ID5.

  The inclusion determination unit calculates a distance (such as a Euclidean distance) between the acquired multidimensional vector data 0302 and the stored multidimensional vector data associated with each cluster. As a result, it is determined whether the acquired multidimensional vector data is included in any of the cluster regions. In the example of this drawing, a determination result is obtained that the obtained multidimensional vector data 0302 is not included in any of the cluster regions. The process of specifying the existence or non-existence of a cluster including the multidimensional vector data acquired in this way, and the process of specifying the included cluster may be referred to as a cluster search. Also, the existence of a cluster including the vector data obtained by such a search is called a hit.

  The cluster registration unit 0104 has a function of registering a new area in the cluster holding unit based on the acquired multidimensional vector data when the determination result by the inclusion determination unit is not a inclusion result. As described above, it is determined that the obtained multidimensional vector data 0302 is not included in any of the clusters. Therefore, as shown in FIG. 3B, the cluster registration unit registers a new area (ID6) in the cluster holding unit based on the multidimensional vector data.

  Further, as shown in FIG. 3C, when it is determined that the acquired multidimensional vector data 0304 is included in the area of the cluster (ID1) held, based on the acquired multidimensional vector data. Is not registered as a new cluster.

  The inclusion determination result history recording unit 0105 has a function of recording an inclusion determination result history that is a history of a determination result that the determination result of the inclusion determination unit is included. FIG. 4 is a diagram illustrating an example of the inclusion determination result history. As shown in the figure, the cumulative judgment count, the cumulative inclusion judgment count, and the retrospective inclusion judgment count are held as the inclusion judgment result history. The cumulative determination count is the cumulative number of determinations made by the inclusion determination unit up to the latest determination time. In addition, the cumulative inclusion judgment frequency is the number of times that the judgment result of inclusion is obtained in all the determinations made up to the latest determination time. The number of times of retrospective inclusion determination is the number of times that the result of the determination of inclusion in the specified number of times (N) has been retroactive from the time of the most recent determination. In the figure, the prescribed number is set to 100. Also, the number of inclusion determinations may be read as the number of hits.

  It should be noted that both the cumulative inclusion judgment count and the retrospective inclusion judgment count need not always be held, and either one may be held. Further, the number of times that a result indicating that no area is included may be held as the inclusion determination result history. For example, the number of cumulative non-inclusion judgments may be held instead of the cumulative inclusion judgment number, or the number of retrospective non-inclusion judgments may be held instead of the retroactive inclusion judgment number.

  The cancellation determination unit 0106 has a function of determining whether the inclusion determination result history in the inclusion determination result recording unit satisfies a predetermined condition for canceling new registration of a cluster.

  FIG. 5 shows an example in which the relationship of any number of times recorded as the inclusion determination result history illustrated in FIG. 4 is used as a predetermined condition. For example, the cumulative inclusion judgment rate is a ratio of the cumulative inclusion judgment number to the cumulative judgment number. As shown in FIG. 4, the cumulative judgment frequency (A) is “26985” and the cumulative inclusion judgment frequency (B) is “8096”. Therefore, as shown in FIG. 5, the cumulative inclusion judgment rate (B / A) Is 30.0%. Here, when the predetermined condition is that the cumulative inclusion judgment rate exceeds 30%, the predetermined condition is satisfied at this time.

  In addition, the retrospective inclusion rate, which is the ratio of the retrospective inclusion frequency to the prescribed frequency, may be used as the predetermined condition. As shown in FIG. 4, the specified number (N) is “100” and the retrospective inclusion judgment frequency (B ′) is “90”. Therefore, as shown in FIG. 5, the retrospective inclusion judgment rate (B ′ / N) is obtained. ) Is 90.0%. Here, when the predetermined condition is that the retrospective inclusion judgment rate exceeds 90%, the predetermined condition is satisfied at this time.

  The predetermined condition may be one provided as described above, or a plurality of conditions may be superimposed and defined. For example, the condition based on the cumulative inclusion judgment rate and the condition based on the retrospective inclusion judgment rate may be a condition that one of the conditions is satisfied, or a condition that both conditions are satisfied.

  Further, the condition may be that the cumulative number of times of judgment exceeds the threshold X and the cumulative inclusion judgment rate or the retrospective inclusion judgment rate exceeds the respective threshold Y or Y ′. Alternatively, the predetermined condition may be that the cumulative determination count exceeds the threshold X and the determination result that the cumulative determination count includes Z times is continuously obtained. Alternatively, the condition may be a combination of the inclusion judgment rate and the number of clusters. For example, the condition may be set to stop only when the inclusion judgment rate exceeds the threshold value X and the number of clusters exceeds the threshold value C.

  In the case where the number of cumulative non-inclusion judgments is stored as the inclusion judgment result history in place of the cumulative inclusion judgment number, and the number of retroactive non-inclusion judgments is stored in place of the retrospective inclusion judgment number, the same applies to the above description, for example, The stop condition may be determined by, for example, setting a predetermined condition that the judgment rate falls below a specified ratio.

The suspension control unit has a function of controlling the cluster registration unit to suspend the new registration in the cluster registration unit when the result of the determination by the suspension determination unit is a determination result that the predetermined condition is satisfied. By stopping the new registration of the cluster when the above-described predetermined condition is satisfied, it is possible to prevent the process for the new registration from being performed unnecessarily. The control of the suspension may be performed immediately after the condition for suspension is satisfied, or may be performed after a predetermined number of searches (processing of inclusion determination) are performed after the condition is satisfied.
<Hardware configuration>

  FIG. 6 is a schematic diagram illustrating an example of the configuration of the present quantization device when the above functional components are implemented as hardware. The operation of each hardware configuration according to the present quantization device will be described with reference to FIG.

  As shown in this figure, the quantization device includes a CPU 0601 for executing various arithmetic processing, a main memory 0602, a secondary storage device 0603, a communication interface 0604, and the like. The secondary storage device stores objects such as images and sounds, multidimensional vector data obtained from the objects, a cluster database, a history of inclusion determination results, conditions for canceling new registration, and various programs such as a vector data acquisition program. Have been. Note that the target from which the multidimensional vector data is obtained may be obtained from outside via the communication interface 0604.

  The CPU executes these various programs after expanding them in the main memory. The above-described hardware components are mutually connected by a data communication path such as a system bus 0605, and perform transmission / reception and processing of information.

First, the CPU executes a vector data acquisition program to acquire target multidimensional vector data such as an image and store it in a predetermined storage area. Then, it is determined whether or not the multidimensional vector data obtained by executing the inclusion determining program is included in any of the cluster areas held. If it is determined that the area is not included, the cluster registration program is executed, and a new area is registered based on the multidimensional vector data. In the case of a judgment result of inclusion, an inclusion judgment result history is recorded. Then, the suspension determination program is executed to determine whether the inclusion determination history satisfies a predetermined condition. If it is determined that the condition is satisfied, the suspension control program is executed to control the suspension of the new registration of the cluster.
<Process flow>

  FIG. 7 is a flowchart illustrating an example of a processing flow in the quantization device. The following steps may be executed by each hardware configuration of the computer as described above, or may be processing steps recorded on a medium and constituting a program for controlling the computer. I do not care.

  As shown in the figure, first, multidimensional vector data is obtained (vector data obtaining step: S0701). Then, it is determined whether the acquired multidimensional vector data is included in any of the cluster regions (inclusion determination step: S0702). If it is determined that the area is not included, a new area is registered in the cluster holding unit based on the obtained multidimensional vector data (cluster registration step: S0703). If the judgment result in the inclusion judgment step is a judgment result indicating inclusion, the inclusion judgment result history, which is the history, is recorded (inclusion judgment result history recording step: S0704).

Subsequently, it is determined whether or not the inclusion determination result history satisfies a predetermined condition for stopping new registration of a cluster (stop determination step: S0705). If the result of the determination in the stop determination step is not satisfied, it is determined whether the determination of whether or not all the acquired multidimensional vector data is included in any of the cluster regions has been completed (the completion determination step). : S0706). If the result of the judgment in the completion judging step is not completed, the process in the inclusion judging step is performed on the uncompleted multidimensional vector data. If the result of the determination in the completion determination step is that the processing has been completed, the processing ends. If the result of the determination in the stop determination step is satisfied, control is performed to stop the new registration in the cluster registration step (stop control step: S0707). Then, the process ends.
<Effect>

  According to the present quantization device, the process of registering a new area is stopped based on the history of the determination result of whether or not the multidimensional vector data acquired for registration is included in the area in the existing vector space. Therefore, it is possible to prevent the process for new registration from being performed unnecessarily.

0100 Quantization device 0101 Multidimensional data acquisition unit 0102 Cluster holding unit 0103 Inclusion judgment unit 0104 Cluster registration unit 0105 Inclusion judgment result history recording unit 0106 Stop judgment unit 0107 Stop control unit

Claims (4)

A vector data acquisition unit for acquiring multidimensional vector data,
A cluster holding unit for holding a plurality of regions in a vector space obtained by clustering neighboring multidimensional vector data,
An inclusion determining unit that determines whether the acquired multidimensional vector data is included in any of the regions,
A cluster registration unit that registers a new area in the cluster holding unit based on the obtained multidimensional vector data when the determination result in the inclusion determination unit is a determination result that it is not included,
An inclusion determination result history recording unit that records an inclusion determination result history that is a history of the determination result that the determination result in the inclusion determination unit is included,
An interruption determination unit that determines whether the inclusion determination rate in the inclusion determination result history in the inclusion determination result recording unit satisfies a predetermined condition for stopping new registration of an area,
If the determination result in the suspension determination unit is a determination result that satisfies a predetermined condition, a suspension control unit that controls the cluster registration unit to suspend the new registration in the cluster registration unit;
A quantization device having:   The predetermined condition is determined by a relationship between the number of times that the result of not being included in any of the determination results in the predetermined number of times in the inclusion determination unit and the number of times that the result of being included in any of the determination results are obtained. The quantization device according to claim 1, wherein An operation method of a quantization device having a cluster holding unit for holding a plurality of regions in a vector space obtained by clustering neighboring multidimensional vector data,
A vector data acquisition step of acquiring multidimensional vector data;
An inclusion determining step of determining whether the obtained multidimensional vector data is included in any of the regions,
A cluster registration step of registering a new area in the cluster holding unit based on the obtained multidimensional vector data if the determination result in the inclusion determination step is a determination result that the area is not included,
An inclusion judgment result history recording step of recording an inclusion judgment result history that is a history of the judgment result that the judgment result in the inclusion judgment step is included,
A cancellation determination step of determining whether the inclusion determination rate in the inclusion determination result history in the inclusion determination result recording step satisfies a predetermined condition for stopping new registration of an area,
A stop control step of controlling the new registration in the cluster registration step to be stopped if the result of the determination in the stop determination step is a determination result that satisfies a predetermined condition;
The operation method of the quantization device having A program for operating a quantization device having a cluster holding unit for holding a plurality of regions in a vector space obtained by clustering neighboring multidimensional vector data,
A vector data acquisition step of acquiring multidimensional vector data;
An inclusion determining step of determining whether the obtained multidimensional vector data is included in any of the regions,
A cluster registration step of registering a new area in the cluster holding unit based on the obtained multidimensional vector data if the determination result in the inclusion determination step is a determination result that the area is not included,
An inclusion judgment result history recording step of recording an inclusion judgment result history that is a history of the judgment result that the judgment result in the inclusion judgment step is included,
A cancellation determination step of determining whether the inclusion determination rate in the inclusion determination result history in the inclusion determination result recording step satisfies a predetermined condition for stopping new registration of an area,
A stop control step of controlling the new registration in the cluster registration step to be stopped if the result of the determination in the stop determination step is a determination result that satisfies a predetermined condition;
A program that causes a computer to execute

Images