JP2735866B2 - How to search database data - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION [Industrial Application Field] The present invention relates to a data search method of a database for searching a plurality of stored data, for example, image data by a keyword.

[Summary of the Invention] The present invention focuses on the fact that keyword strings of data obtained by a keyword search are similar, and as data in the keyword search result, sets similar data in the keyword search result. , And the distance between keyword strings of the data obtained by the model search is calculated, and the entire data is automatically classified into a data group in which the keyword strings are particularly similar. Furthermore, the distance between the keyword string of the classified data group and the key string of the key data is calculated, and the priority is determined according to the distance calculation result, that is, the similarity, which is conventionally required. This eliminates the need for classification processing of search results by a human. Furthermore, the keyword string of the data group is output in the form of a character image for each priority order, so that the searcher can confirm the keyword based on the automatic classification and use the keyword for the next keyword search. be able to.

[Related Art] Conventionally, a keyword search method is generally known as a search method for an image database that stores various types of images in a wide field such as broadcasting. In addition, a search method using a vector-type search model for searching data stored in a database for data similar to a search clue is also known.

In the above keyword search method, when one image is stored, a plurality of words corresponding to the contents, that is, keywords are added to the image data and indexed. Next, necessary image data is searched from a plurality of image data stored in the database based on the keyword. Such a keyword search method has a large expressive power for an image as compared with the unified classification of image data.
It is suitable for a database that handles a variety of images that can be viewed from a number of images.

The search method based on the vector-type search model is often applied to a database system for performing document search. In this method, a keyword is assigned to each data stored in the database system, and each keyword assigned to the data is weighted. next,
A search cue is represented by a vector having a keyword weight as an element. At the time of a search, a similarity between a vector having a search cue and a vector having a keyword weight of each data element in a database as an element is calculated. ,next,
The calculated degree of similarity corresponding to each piece of data is expressed as the degree of relevance of the data to the search query. The search results are output in the order of the degree of matching. In this way, by ranking the search results according to the degree of relevance to the search question, an efficient search can be performed.

[Problem to be Solved by the Invention] However, in the keyword search method, all data having a corresponding keyword is output. Therefore, when it is desired to limit the number of search results to a predetermined amount, the intention of the search is determined by the logical It is necessary to express accurately with proper composition. Furthermore, when the number of keywords that can be used in a search is limited, in order to obtain an accurate expression, it is necessary to repeat a search operation by changing a logical combination of keywords. In addition, when the searcher lacks knowledge of the keyword, the conventional keyword search method has a disadvantage that the efficiency of the search trial becomes very poor.

On the other hand, if the search method based on the vector-based search model is applied to the image database, among the images included in the intermediate search results obtained in the course of the search trial by the keyword search, the image closest to the search intention is obtained. An image similar to the keyword string is searched using the keyword string of the image. For this reason, the efficiency of the search trial can be increased. However, when a photographed image is stored in a broadcast station or the like and an image search is performed later, even if a search method based on a vector-type search model is used, a large number of similar images can be obtained as a search result, and these images are also obtained. There are also many types.

Specifically, in each searched image, a keyword with a high weight matches, but a keyword with a low weight often differs. For this reason, there is a drawback that the search cannot be sufficiently organized only by the method of organizing the search results in the order of the similarity. For this reason, in the search method using the vector-type search model, it has been difficult to grasp the search result, and conversely, the efficiency of the search trial has been reduced.

Therefore, an object of the present invention is to provide a data retrieval method for a database that can solve such a problem, classify search results searched by a vector-type search model, and determine the priority of the classified results. Is to do.

[Means for Solving the Problems] In order to achieve such an object, the first embodiment of the present invention performs a keyword search on a plurality of data stored in advance, and selects one of search results obtained by the keyword search. A data search method for a database that selects two data as key data and performs a model search for data similar to the keyword string of the key data from the search results. Is performed, and a plurality of first data groups are created by integrating data for which the result of the distance calculation is equal to or less than a predetermined value. Is performed, and a plurality of second data groups are created by integrating the first data groups in which the result of the distance calculation is equal to or smaller than a predetermined value. Classifying the data obtained by the model search into a plurality of second data groups, and performing a distance calculation between each of the classified keyword strings of the plurality of classified second data groups and the keyword string of the key data; The priorities of a plurality of data groups classified according to the result of the distance calculation are determined.

A second aspect of the present invention is characterized in that a keyword string included in each of the plurality of second data groups is output in the form of an image representing a character according to a priority order.

[Operation] The present invention focuses on the fact that the keyword strings of the data obtained by the keyword search are similar. One of the data in the keyword search result is used as key data, and similar data is used as the keyword search result. , A distance between keyword strings of data obtained by the model search is calculated, and the entire data is automatically classified into a data group in which the keyword strings are particularly similar. Further, a distance calculation is performed between the keyword column of the classified data group and the keyword column of the key data, and the distance calculation result,
That is, since the priority order is determined according to the similarity, the classification process of the search result by a human, which is conventionally required, becomes unnecessary. Furthermore, the keyword string of the data group is output in the form of a character image for each priority order, so that the searcher can confirm the keyword based on the automatic classification and use the keyword for the next keyword search. be able to.

[Example] Hereinafter, an example of the present invention will be described in detail with reference to the drawings.

Prior to the description of the present invention, a system configuration of an image search system to which the present invention is applied will be described with reference to FIG.

2, the image search system includes a host computer 1, a keyword search unit 2, a similar image search unit 3, a frame memory 4, an image display device 5, a storage device 6, and an image classification unit 11.
It is mainly composed of

 Next, the function of each of the components described above will be described.

The host computer 1 controls the operation of each component and displays an image search result and a classification result of the image search result on the image display device 5 via the frame memory 4.

The keyword search unit 2 searches the image data stored in the storage device 6 based on the keyword, and extracts image data that matches the keyword.

The similar image search unit 3 calculates a distance between a keyword sequence of image data serving as a search base (key) and a keyword sequence assigned to each image data, and extracts image data having a threshold or less.

The frame memory 4 stores information to be displayed on the image display device 5, for example, retrieved image data and classified character strings described below in order of priority.

An image keyword number matrix file (PK
An area for storing a matrix file (referred to as a matrix file) 8, a keyword file 9 and an image data file 10 is provided.

As shown in FIG. 3, the image keyword number matrix file 8 stores, for each image number of the stored image data, a keyword number previously assigned to the image data.

As shown in FIG. 4, the keyword file 9 stores a character string serving as a keyword used in the search, its number, and a numerical value indicating the weight of the keyword.

In the image data file 10, together with the image number, for example,
One screen of image data is stored.

The image classification unit 11 according to the present invention includes a keyword search unit 2
A plurality of search results searched by the similar image search unit 3 are automatically classified using a method described later.

FIG. 1 shows a circuit configuration of the image classification unit 11 shown in FIG.

In FIG. 1, an image classification unit 11 includes an input buffer 12, an initial classification circuit 13, a classification integration circuit 15, a classification order determination circuit 17, a classification name generation circuit 19, an image vector generation circuit 21, a classification vector generation circuit 22, and a vector distance. It is constituted by a calculation circuit 23. Of these, the initial classification circuit 13, the classification integration circuit 15, and the classification order determination circuit 17 are connected to the image vector generation circuit 21, the classification vector generation circuit 22, the vector distance calculation circuit via the internal bus 24.
Connected to 23. The image vector generation circuit 21, the classification vector generation circuit 22, the vector distance calculation circuit 23, and the classification name generation circuit 19 are connected to the storage device 6 via the bus 7, and the image keyword number matrix file 8 stored in the storage device 6 , A process described later is performed with reference to the storage data of the keyword file 9.

The above circuits 13, 15, 17, 19, 21, 22, 23 are respectively
An arithmetic processor or a logical operation circuit may be used.

 The circuit operation of the image classification unit 11 shown in FIG. 1 will be described.

By the similar image search unit 3, for example, the image number “2”,
“5”, “7”, “9”, “15”, “23”, “24”, “31”, “33” total 9
Two similar image numbers are obtained as search results, and the number of search results “9” and similar image numbers (hereinafter, referred to as similar image number array 27) are stored in the input buffer 12, as shown in FIG.
Is stored.

Next, the initial classification circuit 13 performs the following control procedure shown in FIG. 6 to initially classify the similar image number array 27 stored in the input buffer 12.

Step S10) Similar image number array 2 from input buffer 12
7 is read, and the distance threshold d _{th is set} to the similar image search unit 3.
Receive from. The distance threshold value d _th is a distance threshold value used for extracting a similar image number executed in the similar image search unit 3, and a numerical value of 0.6 is used in this embodiment.

Step S11) The classification threshold value c _th is obtained from the distance threshold value d _th according to the following equation.

c _th = μ × d _th (1) Here, μ is a predetermined constant of 0 ≦ μ ≦ 1 and, for example, μ = 0.55.

Step S12) The image distance calculation circuit 14 calculates the distance between the images corresponding to the image numbers included in the similar image number array 27.
To obtain a distance matrix D between similar images.

For this purpose, the image distance calculation circuit 14 sends the similar image number array 27 to the vector distance calculation circuit 23 to execute the calculation of the following equation (2).

d _AB = 1−W _AB / (W _AA × W _BB ) ^0.5 ... (2) d _AB : distance between vectors A and B W _AB : weight element corresponding to a keyword element commonly included in A and B Square sum W _AA : Square sum of weight elements of A W _BB : Square sum of weight elements of B Here, the vectors A and B are image vectors (see FIG. 8). The image vector is composed of a keyword element and a weight element of the image of each image number.

In the image vector generation circuit 21, the similar image number array 27
Select the two image numbers in, and PK based on the image numbers
A keyword element and a weight element corresponding to an image number are read from the matrix file 8 and the keyword file 9 to generate an image vector.

Next, using the vectors A and B created by the image vector generation circuit 21, the calculation of the above equation (1) is performed by the vector distance calculation circuit 23. Next, the vector distance calculation circuit
23 changes the combination of the image numbers in the similar image number array 27 and calculates the distance between the images in the same procedure as described above.

Each distance calculation result _dij thus obtained is an element of the similar image distance matrix D.

Step S13) Each element _dij of the similar image distance matrix D is compared with the classification threshold value c _th calculated in step S11, and a similar image relation matrix R using the comparison result _rij as an element is obtained. Here, when d _ij > c _th , r _ij = 0 When d _ij ≦ c _th , r _ij = 1 (3) Step S14) The maximum complete partial graph of the graph expression of the similar image relation matrix R is supported. Subset of similar image numbers
C ₁ ,…, C _N are described, for example, in the literature Co by C. Bron and J. Kerbosch.
Determined according to the algorithm of mmunications of ACM.Vol.16.No.9 (1973) p.577. In the present embodiment, the elements of the similar image relation matrix R corresponding to the images included in the same subset
r _ij becomes “1”, that is, a subset of image numbers of similar images is extracted.

From the subsets C ₁ ,..., C _N , a classification image number array 28 is generated as shown in FIG. An example of each matrix obtained in the above calculation process is shown in FIG.

Classification integration circuit 15 executes the control procedure shown in FIG. 10, the subset C ₁ by the processing in step S21~ step S24 to be described below, ..., performs integration of C _N.

That is, Step S20) Distance threshold d _th and classification number array 28
Enter

Step S21) Change the classification threshold value c _th to the distance threshold value d _th
Is obtained in accordance with equation (1).

Step S22) The distance between the classifications and the classification vector included in the classification image number array 28 are calculated by the classification distance calculation circuit 16 (first
Calculate according to the figure). Specifically, the classification distance calculation circuit 16 sends the classification image number array to the classification vector generation circuit 22.
The image number of the image belonging to each classification of 28 is sent, and the classification vector generation circuit 22 generates a classification vector. The classification vector of the specific example shown in FIG. 12 is the sum of the image vectors corresponding to the image numbers included in the classification. After an image vector is generated by the image vector generation circuit 21 based on the image number specified by the classification vector generation circuit 22, a classification vector is generated based on the generated image vector (see FIG. 11).

A set of classification vectors generated for each classification is referred to as a classification vector array 30. The classification distance calculation circuit 16 sequentially sends the generated classification vectors to the vector distance calculation circuit 23, and instructs the calculation of the distance between the classification vectors. In response to this instruction, the vector distance calculation circuit 23 calculates the distance between the classification vectors according to the equation (2) as in the case of calculating the distance between image vectors (step S12). Next, the minimum value Cdmin in the calculation result is extracted, and a set of classification numbers (c ₁ , c ₂ ) that gives the minimum value Cdmin is detected.

Step S23) Next, the minimum classification distance cdmin and threshold
Compare c _th .

When cd _min ≧ c _th , the similarity between the classifications is low, that is, it is determined that the classification processing has been completed, and the classification image number array 28 is changed to the classification image number array 29 (see FIG. 14), and the classification vector array 30 Is input to the classification order determination circuit 17.

FIG. 14 shows the contents of the classification image number array 29. In FIG. 14, reference numeral 29-1 denotes a classification number, and reference numeral 29-2.
Indicates the number of images included in the classification image number array 29. Code 29
-3 indicates an image number included in the classification image number array 29.

When cd _min <c _th, the process proceeds to the next step S24.

Step S24) The classification number c ₁ in the classification image number array 28,
c. The union C of the image number sets belonging to the classification of ₂ is obtained to integrate the classifications. Next, the classification corresponding to the classification numbers c ₁ and c ₂ is deleted from the classification image number array 28 to update the classification number. The union C at the end of the updated classified image number array 28
Is added as a new classification. The classification image array obtained in this manner is used as a new classification image number array 28, and the process returns to step S22, and the above-described steps S22 to S24 are repeated until the minimum distance cdmin becomes larger than c _th .

By repeating the above procedure in the classification integration circuit 15,
An image data group of a classification in which similar classification results among the classification results initially classified by the initial classification circuit are integrated is automatically generated. In the classification order determination circuit 17, the classification integration circuit 15
Then, the distance between each classification vector of the classification vector array 30 output from and the image vector of the image corresponding to the key image number 25 (not shown) is calculated by the image classification distance calculation circuit 18. That is, the image classification distance calculation circuit 18 sends the key image number 25 to the image vector generation circuit 21, obtains the image vector of the key image number 25, and
The 30 classification vectors are sequentially sent to the vector distance calculation circuit 23 to determine the distance between the key image and the classification vector corresponding to each classification.

Next, we consider that the smaller the distance, the higher the priority.
Classification image number array 29, classification vector array 30
Are sorted by the sorting order determination circuit 17. The rearrangement results are classified image number array 31 (see FIG. 15),
It is output as a classification vector array 32 (see FIG. 16).

FIG. 15 shows the configuration of the classification image number array 31. In FIG. 15, reference numeral 31-1 denotes a classification number, and reference numeral 31-2.
Denotes the number of images of the image number, and reference numeral 31-3 denotes an image number included in the classified image array 31.

FIG. 16 shows the configuration of the classification vector array 32.
In the figure, reference numeral 32-1 indicates a classification number, and reference numeral 32-2 indicates the number of elements. Reference numeral 32-3 indicates a keyword number included in the classification vector array 32, and reference numeral 32-3 indicates the weight of the keyword number.

The classification name generation circuit 19 receives the classification vector array 32 from the classification order determination circuit 17. Next, the classification name generation circuit 19 has a size of 1 / n or more of the larger ones among the weight elements of the classification vectors corresponding to each class of the classification vector array 32,
In addition, the element having the weight from the largest to the m-th is selected. Next, the classification name generating circuit 19 outputs a keyword character string of the keyword number of the keyword element corresponding to the selected element from the keyword file 9 in the storage device 6 to the bus 7.
And outputs the keyword character strings as a character string array 33 (see FIG. 17) in which images representing the characters of the classification name keywords, which are collected for each classification, are arranged. Here, n and m are integer constants, for example, n = 2 and m = 3.

FIG. 17 shows an example of the contents of the classification name keyword character string array 33. In FIG. 17, reference numeral 33-1 denotes a classification number,
Reference numeral 33-2 denotes an element, and reference numeral 33-3 denotes a keyword string constituting the element.

[Effects of the Invention] The present invention focuses on the fact that keyword strings of data obtained by a keyword search are similar, and uses one piece of data in a keyword search result as key data, and searches data similar to this as a keyword search. A model search is performed from the results, and the distance between keyword strings of data obtained by the model search is calculated, and the entire data is automatically classified into a data group in which the keyword strings are particularly similar. Further, a distance calculation is performed between the keyword column of the classified data group and the keyword column of the key data, and the distance calculation result,
That is, since the priority order is determined according to the similarity, the classification process of the search result by a human, which is conventionally required, becomes unnecessary. Furthermore, the keyword string of the data group is output in the form of a character image for each priority order, so that the searcher can confirm the keyword based on the automatic classification and use the keyword for the next keyword search. be able to.

[Brief description of the drawings]

FIG. 1 is a block diagram showing a circuit configuration of the image classification unit 11 shown in FIG. 2, FIG. 2 is a block diagram showing a system configuration of the embodiment of the present invention, and FIG. 3 is an image keyword number matrix of the embodiment of the present invention. FIG. 4 is an explanatory diagram showing the contents of the keyword file 9 of the embodiment of the present invention, FIG. 5 is an explanatory diagram showing the contents of the similar image number array 27 of the embodiment of the present invention, 6 is a flowchart showing the processing procedure of the initial classification circuit 13 shown in FIG. 1, FIG. 7 is an explanatory diagram showing the processing contents of the initial classification circuit 13 shown in FIG. 1, and FIG. 8 is an image of the embodiment of the present invention. FIG. 9 is an explanatory diagram showing the contents of the vector, FIG. 9 is an explanatory diagram showing the contents of the classification image number array 28 according to the embodiment of the present invention, FIG. 10 is a flowchart showing the processing procedure of the classification integration circuit 15 shown in FIG. FIG. 11 shows the classification vector of the classification vector generation circuit 22 shown in FIG. FIG. 12 is an explanatory diagram showing the contents of the classification vector of the embodiment of the present invention. FIG. 13 is an explanatory diagram showing the contents of the classification vector array 30 of the embodiment of the present invention. FIG. 15 is an explanatory diagram showing the contents of the classification image number array 29 of the embodiment of the present invention. FIG. 15 is an explanatory diagram showing the contents of the classification image number array 31 of the embodiment of the present invention. FIG. 16 is a classification vector array of the embodiment of the present invention. FIG. 17 is an explanatory diagram showing the contents of 32. FIG. 17 is a classification name keyword character string array 33 according to the embodiment of the present invention.
It is an explanatory view showing the contents of. 1 Host computer 3 Similar image search unit 6 Storage device 8 Image keyword number matrix (PK matrix) file 9 Keyword file 10 Image data file 11 Image Classification unit, 12: Input buffer, 13: Initial classification circuit, 15: Classification integration circuit, 17: Classification order determination circuit, 19: Classification name generation circuit, 20: Output buffer

Claims (2)

(57) [Claims] 1. A keyword search for a plurality of data stored in advance, one of search results obtained by the keyword search is selected as key data, and a keyword string of the key data is selected from the search results. A data search method for a database that searches for a model similar to that of a database, in which a distance calculation is performed for a keyword string of each data obtained by the model search, and the result of the distance calculation is equal to or less than a predetermined value. To create a plurality of first data groups, perform a distance calculation for the created keyword strings between the plurality of first data groups, and perform a distance calculation where the result of the distance calculation is equal to or less than a predetermined value. A plurality of second data groups are created by integrating one data group, and the data obtained by the model search is stored in the plurality of second data groups. And performing a distance calculation between each of the keyword strings of the plurality of classified second data groups and the keyword string of the key data. According to a result of the distance calculation, the plurality of classified data groups are classified. A method for retrieving data from a database, wherein priorities of data groups are determined. 2. The data retrieval method for a database according to claim 1, wherein a keyword string included in each of the plurality of second data groups is output in the form of an image representing a character in accordance with the priority order. The database data retrieval method to be used.