JP5410372B2 - Content search apparatus, method, and program - Google Patents

Description

  The present invention relates to a content search apparatus, method, and program, and in particular, a document in which a region appears and a document in the document in which the captured image of a partial region in a document in which a page break or a line feed position is determined is used as a search query The present invention relates to a content search apparatus, method and program for associating a position in a document with a content for specifying the position and presenting the content related to the position.

  The present invention relates to an apparatus and a method for uniquely identifying from which partial area of a document such as a book a position in which document the area is included, and presenting content associated with the position. This can be applied in various fields. For example, when a user shoots a part of a textbook of science with a mobile phone with a camera, etc., the position of the textbook in which the shooting area is specified is specified, and an experiment video related to the corresponding position of the textbook or related It is possible to present content such as a problem, which can be used to promote the understanding of the user.

  In the above example, a partial area of a document is used as a query, and a document name including the area or a document name and a position in the document is specified from a huge amount of document groups, and contents associated with the position are presented. It can be regarded as a content search device.

  In order to construct a system for acquiring position information from a document group, it is necessary to analyze the document group in advance to create an index and register related contents.

  Such problems have been actively studied in recent years, and many methods have been proposed even now.

  For example, in the case of Japanese, after dividing a document in a document into units of words using a technique such as morphological analysis, the word is used as an index key, and the name of the document including the word, or the document name and the document There is a method in which the position where the word appears is used as an index value.

  Further, a sequence of N characters (or N words) is used as an index key, and a document name including the sequence of the characters (or words), or a position at which the sequence of the characters (or words) appears in the document name and document. There are also methods (character N-gram method, word N-gram method) that use as the index value. The usefulness of the N-gram method has been recognized in a wide range of situations, and many extended methods are still proposed. In addition to the normal N-gram method, a method of changing the value of N according to the situation has been implemented (see, for example, Non-Patent Document 1).

  The simplest method of acquiring a specific position of a specific document from a group of documents and associating content with the specified position is related to the unit of the document structure such as a chapter, section, paragraph, or manually. The target area is specified in content units or content group units and registered in the DB, and when the partial area is given as a query, it is determined whether the partial area is included in the target area to which the partial area is associated. There is a way to associate with content.

"A realization method of N-gram index using Unicode and its evaluation", Information Processing Society of Japan, 2000-NL-136-17, pp.135-142.

  However, the above-described conventional method has a problem that it is necessary to manually specify a target area to be associated with content, and this work requires a great deal of labor. In particular, when the target document is only a paper medium and there is no electronic medium to be printed, the paper medium is read by a scanner, and the read image is converted into characters by an optical character reader (OCR). However, in this case, information on the structure of the document such as chapters, sections, paragraphs, etc. is lost. For this reason, in the method which presupposes that the above target areas exist, manual area specification is inevitable. In this case, when there are tens to millions of documents to be indexed, there is a problem that this work requires enormous effort and cost.

  The present invention has been made in view of the above points, and provides a content search apparatus, method, and program capable of associating a specific position of a document with the content at a low cost without setting a target area to which the content is associated. The purpose is to do.

In order to solve the above problems, the present invention (Claim 1) uses a partial area in a document in which a page break or a line break position is determined as a search query, and the document in which the area appears and the document A content search device that acquires a position and presents content associated with the acquired position,
A document input means for accepting input of documents to be indexed;
Character block extraction means for extracting a character block consisting of a combination of one or more characters from the whole or a partial area of the input document;
An index output means for associating the character block and a page identifier and a page coordinate in the document in which the character block appears, and outputting to the index DB;
Query input means for accepting a partial area in a document as a search query,
Query character block extraction means for extracting a query character block consisting of a combination of one or more characters from the search query;
Search means for searching the index DB based on the query character block and outputting the search result;
The search results are totaled for each page, the page in which the most character blocks are searched is set as a hit page, the center of gravity of the in-page coordinates of the character blocks searched in the hit page is calculated, and the hit position in the page is calculated. A character block center of gravity calculating means;
A content DB that stores the relationship between the page identifier, the position in the page, and the content associated with the position;
Using the hit page calculated by the character block centroid calculating means and the hit position in the page as a query, the page identifier that matches the hit page and the content associated with the page position near the hit position in the page are related to the content Content search means for searching from the content DB.

  The present invention (Claim 2) uses the mean shift method when calculating the center of gravity of the in-page coordinates of the character block in calculating the center of gravity of the character block.

Further, according to the present invention (Claim 3), a partial area in a document in which a page break or a line feed position is fixed is used as a search query, and the document in which the area appears and the position in the document are acquired and acquired. A content search method for presenting content associated with a position,
As a storage means,
Index DB,
In a device having a page identifier, a position in a page, and a content DB that stores a relationship between contents associated with the position,
A document input means for receiving an input of a document to be indexed, and a document input step;
A character block extracting step for extracting a character block consisting of a combination of one or more characters from the whole or a partial area of the input document;
An index output means for associating the character block and a page identifier in the document in which the character block appears with the in-page coordinates and outputting to the index DB;
A query input step in which the query input means accepts a partial area in a document as a search query;
A query character block extracting means for extracting a query character block consisting of a combination of one or more characters from the search query;
A search unit that searches the index DB based on the query character block and outputs the search result;
The character block center of gravity calculation means totals the search results for each page, sets the page where the most character blocks are searched as a hit page, and calculates the center of gravity of the in-page coordinates of the character block searched within the hit page. , A character block centroid calculation step as a hit position in the page,
The content search means uses the hit page calculated in the character block centroid calculating step and the hit position in the page as a query, and associates a page position near the hit position in the page with a page identifier that matches the hit page. And a content search step of searching the content DB for the received content.

Further, according to the present invention (Claim 4), in the character block center of gravity calculation step,
A mean shift method is used to calculate the center of gravity of the in-page coordinates of the character block.

  The present invention (Claim 5) is a program for causing a computer to function as each means constituting the content search device according to Claim 1 or 2.

According to the present invention, a specific position of a specific document is specified from a partial image of a document photographed by a client terminal such as a camera-equipped mobile terminal from the document group, and a content associated with the specific position is selected, and the client terminal The content can be displayed.
In particular, if information about the structure of a document, such as a chapter, section, or paragraph, is missing or lost in the document to which the content is related, the content can be related only by specifying the physical location on the document. This makes it possible to eliminate the need to manually add data related to the document structure such as chapters, sections and paragraphs. This is particularly effective when there are tens of thousands to millions of documents to be indexed.

  Even in the conventional method, in the case of an application in which it is necessary to create an index only at a location where content needs to be associated, it is sufficient to specify an area only at a location associated with the content. When applying to a service that allows content to be associated with any part of the document, it is necessary to index all parts of the document in advance, and manually specify chapters, sections, paragraphs, etc. It was essential to restore the structure. Therefore, the present invention has a particularly excellent effect when applied to such a service.

It is a block diagram of the search system in one embodiment of this invention. It is an example of the document page in one embodiment of this invention. It is a flowchart of the index creation process in one embodiment of the present invention. It is the example which made the text file list in one embodiment of this invention. It is an example of extraction of the character block at the time of the index creation process in one embodiment of this invention. It is the example which applied the character block extraction rule at the time of the index creation process in one embodiment of this invention. It is a process result (index DB) of the character block extraction part at the time of the index creation process in one embodiment of this invention. It is an example of content DB in one embodiment of this invention. It is a figure for demonstrating the application for storage. It is a flowchart of the process which inquires to a server part from the client part in one embodiment of this invention. It is an example of the produced | generated image file in one embodiment of this invention. It is an example of the text data obtained using the optical character recognition apparatus in one embodiment of this invention. It is an example of the character block extraction at the time of the inquiry process in one embodiment of this invention. It is the example which applied the character block extraction rule at the time of the inquiry process in one embodiment of this invention. It is an example of the process result of the character block extraction part at the time of the inquiry process in one embodiment of this invention. It is an example of the inquiry result in one embodiment of this invention. It is an example of the search result (content) in one embodiment of this invention. It is an example of the content display means in one embodiment of this invention.

  Embodiments of the present invention will be described below with reference to the drawings.

  FIG. 1 shows a configuration diagram of a search system according to an embodiment of the present invention. The system shown in the figure is roughly composed of a server unit 300, a client unit 400, and external devices (document reading device 100, optical character recognition device 110).

  The server unit 300 includes a data input unit 310, a character block extraction unit 320, an index output unit 330, an index DB 340, a content DB 390, a server side data transmission / reception unit 350, a DB inquiry unit 360, a character block centroid calculation unit 370, and a content search unit 380. Consists of.

  The client unit 400 includes a client side device 410, a document photographing unit 411 constituting the client side device 410, a content display unit 412 constituting the client side device, and a client side data transmission / reception unit 420.

  The external device includes a document reading device 100 and an optical character recognition device 110.

  Documents 200 and 210 in the present embodiment are paper books made up of a set of pages including characters, or electronic media including character arrangement information by line feed. In the case of a paper medium, it is converted into an electronic medium by being input to the document reading apparatus 100.

  An example of each page constituting the input document group 200 and the document page 210 input to the client unit is shown in FIG.

  The document reading device 100 is connected to the data input unit 310 of the server unit 300. The optical character recognition device 110 is connected to the server-side data transmission / reception unit 350.

  In this embodiment, (1) an operation of creating an index in the server unit 300 and (2) an operation of inquiring the server unit 300 from the client unit 400 are performed.

(1) Work to create an index in the server part:
FIG. 3 is a flowchart of index creation processing according to an embodiment of the present invention.

  ● Input step: Enter the document to be indexed.

  Step 310) Each page of each document in the document group is read by the document reading device 100 and passed to the data input unit 310.

  Here, the document reading device 100 is a general device that reads text printed on a paper medium and converts it into a text file, and corresponds to a scanner with an OCR function. Here, it is assumed that the text in each page is converted into a text file while maintaining the page break position and line feed position in a state printed on a paper medium. However, when the input document group is given as an electronic medium including character layout information such as a line feed code, this processing can be omitted.

  Step 320) The data input unit 310 reads the text file group passed from the document reading device, lists it with the data structure shown in FIG. 4, and passes it to the character block extraction unit 320 of the server unit 300. For convenience of explanation, a file name is assigned to each page here, but it is not always necessary to hold a file for each page. The page identifier is information that can uniquely identify the page, such as random number, UUID, ISBN number of the book and page number converted to ID by hash function such as SHA-1, and what kind of information is used. It doesn't matter.

  Character block extraction step: Character blocks are extracted from each page of each document.

  Step 330) The character block extraction unit 320 of the server unit 300 reads each page described in the list passed from the data input unit 310, extracts a character block group from each page according to the character block extraction rule, Each character block, the file name of the extraction source page of each character block, and the appearance position of the character block on the page are associated with each other and passed to the index output unit 330.

  Here, the “character block” is a group of one or more characters extracted in a prescribed shape from a character string arranged in a page. Here, the prescribed shape is extracted as a box shape as shown in FIG.

  The “character block extraction rule” is a rule that defines how a character block is extracted from a document. The rule is stored in a memory (not shown) of the server unit 300 and referenced by the character block extraction unit 320. Shall be. Here, as shown in FIG. 6, extraction is performed while shifting by two characters from the upper left corner toward the lower right corner.

  The “appearance position of the character block” is position information indicating at which position of the character block the character block appears in an arbitrary granularity according to the purpose of the system.

  FIG. 7 shows the processing result of the character block extraction unit in one embodiment of the present invention. This figure shows the result of the processing in step 330 performed by the character block extraction unit 320, and this data is passed to the index output unit 330. Here, the character block is expressed by arranging the characters constituting the character block in order from the top and the left.

  In the present embodiment, the appearance position of each character block is not expressed as a row or a column, but is expressed as a position coordinate within the page called a position within the page. Specifically, the upper left coordinate of the page is (0, 0), the lower right coordinate is (1, 1), and [0, 1] is represented by a real number having a range.

  Output step: Outputs an index for executing a search.

  Step 340) The index output unit 330 stores each character block passed from the character block extraction unit 320 in the index DB 340 with the data structure of FIG. This implements an index DB that uses a character block as an inquiry key and returns a file name and an appearance position as an inquiry result.

(2) Work inquiring from the client unit to the server unit The content DB 390 of the server unit 300 includes a page identifier of each book created by a book publisher or a general user, content related to the position in the page, and the content. Store information. Examples of contents include experiences of tourists who have visited various places for tourist attractions, and chemical experiment videos for chemical textbooks. Here, the substance of the content is stored in the data storage area on the server unit 300, and the relationship among the content, the page identifier, and the position in the page is stored in a data structure as shown in FIG. In order to store content and information related to the content in the content DB 390, a dedicated storage work terminal may be prepared separately, or a storage work Web application as shown in FIG. Content and information related to the content may be freely stored through a Web browser. In FIG. 9, the position where the content is associated is specified by pointing the position of the document image displayed on the right side of the screen with the mouse. The content to be associated is performed by inputting the form on the right side. With this configuration, when specifying the position of the content, instead of manually specifying the chapter, section, paragraph, etc. area as in the prior art, the point where the content is set is specified with the mouse. It only needs to be specified, and it is not necessary to manually assign area data such as chapters, sections and paragraphs in advance.

  FIG. 9 shows the flow of processing for inquiring from the client unit to the server unit in one embodiment of the present invention.

  ● Input step: Enter a part of the page to be indexed.

  Step 910) The document photographing unit 411 optically photographs all or a part of the document page, saves the photographing content as an image file in a memory (not shown), and passes it to the client side data transmitting / receiving unit 420. The client-side data transmission / reception unit 420 passes the image file passed from the document photographing unit 411 to the data transmission / reception unit 350 of the server unit 300 via the network.

  The document page 210 is one page of one book included in the document group. The document page 210 is assigned a unique page identifier as described above. Here, it is assumed that a part of the page shown in FIG. 5 is photographed and the image file shown in FIG. 11 is created.

Step 920) The server-side data transmission / reception unit 350 uses the optical character recognition device 110 to extract the text data shown in FIG. 12 from the image file passed from the client-side data transmission / reception unit 420, and sends it to the character block extraction unit 320. hand over. The optical character recognition device 110 is a general OCR software or the like, and is a general device that extracts character information from an image but converts it into a format that can be used by a computer as text data.
In this OCR process, as shown in FIG. 12, there is a possibility that “family” is “fee”, “pizza” is “visa”, “pass” is “lotus”, etc. Since the blocks are divided into small blocks, many blocks that are not erroneously recognized remain, so that the position can be identified by whether or not a certain number or more of these blocks remain.

  Character block extraction step: Extract character blocks from a part of the input page.

  Step 930) The character block extraction unit 320 reads the text data passed from the server-side data transmission / reception unit 350, extracts a character block group from the text data according to the character block extraction rule, and passes it to the DB inquiry unit 360.

  Here, the “character block” is extracted in a box shape as in step 330 as shown in FIG. The shape of the block does not have to be a box shape, and an arbitrary shape such as an L shape or a cross shape can be considered.

  The “character block extraction rule” is extracted while shifting one character at a time from the upper left corner toward the lower right corner as shown in FIG. FIG. 15 shows the result of the processing in step 930 performed by the character block extraction unit 320, and this data is passed to the DB inquiry unit 360. Here, the character block is expressed by arranging the characters constituting the character block in order from the top and the left.

  Inquiry step: An inquiry is made to the index, and content associated with a part of the input page is specified.

  Step 940) The DB inquiry unit 360 makes an inquiry to the index DB 340 using the list of FIG. As described above, the index DB 340 stores data in the structure shown in FIG. The DB inquiry unit 360 inquires about the page identifier and the position in the page corresponding to each character block in FIG. 15, and acquires the inquiry result in the format shown in FIG.

  Step 950) The character block center-of-gravity calculation unit 370 counts the overlapping page identifiers obtained in FIG. 16 and sets the page identifier with the highest frequency as the hit page. In this example, “5440566ca69690a43d15fd89943316cf” is obtained.

  When selecting a hit page, if the number of overlapping page identifiers is simply the largest, and if the subject being photographed is not indexed in the first place, the hit page will be mistaken for the case where the same block was accidentally hit. May be recognized as. In order to prevent this, the minimum number of hits is set as a threshold value k, and if it is less than or equal to k, it is not set as a hit page, but a message indicating that the position could not be specified via the server-side data transmission / reception unit 350. To the client unit 400. As another example, instead of simply setting with a threshold value, a value that varies according to the number Nq of character blocks extracted from the query image and the number Np of character blocks extracted from the page, For example,

を閾値してもよい。ただし、k₀，k_p，k_qは定数である。これは、クエリ画像またはページから抽出された文字ブロックの数が多ければ多い程、偶然ヒットする数が多くなるからである。

May be thresholded. However, k ₀ , k _p , and k _q are constants. This is because the greater the number of character blocks extracted from the query image or page, the greater the number of chance hits.

  Step 960) The character block center of gravity calculation unit 370 calculates the center of gravity coordinates based on the set H of all the in-page positions included in the hit page.

により算出し、その座標をページ内ヒット位置と呼ぶ。具体的には、図１６のようにヒットしたページ内位置の集合Hが、
{(0.2123, 0.4542), (0.2614, 0.4542), (0.2123, 0.4921), (0.2614, 0.4921)}
の４カ所であるケースにおいては、ページ内ヒット位置はその重心により計算し、(0.2368, 0.4732)となる。

And the coordinates are referred to as in-page hit positions. More specifically, as shown in FIG.
{(0.2123, 0.4542), (0.2614, 0.4542), (0.2123, 0.4921), (0.2614, 0.4921)}
In the case of these four places, the hit position in the page is calculated from the center of gravity, and becomes (0.2368, 0.4732).

  Since it is almost impossible in the system configuration that a block of a different page is shot in one shooting by the client unit 400, a block having a page identifier that is not the most frequent page identifier is a coincidence. It is a hit block and can be regarded as noise. As described above, these noises can be removed by the process of calculating the center of gravity of the position in the page of the block included in the hit page.

  In calculating the centroid coordinates, the centroid of the position coordinates in the page of the character block having the same page identifier may be simply calculated as described above. For example, Reference 1 “Y. Cheng. Mean shift, mode seeking, IEEE Transactions on Pattern Analysis and Machine Intelligence, 17 (8), pp. 790-799 (1995) ”, and the region based on the rectangular region corresponding to the captured query image. By finding the most central coordinate position while shifting, it is possible to reduce the problem that the coordinates are greatly shifted due to the character block that is located away from the query image and accidentally hit in the hit page.

  When applying the mean shift method, it is necessary to specify the size of the rectangular area, but it is desirable to set the size according to the imaging area of the query image. However, depending on the resolution of the captured image, just because it is a large query image, the captured region is not necessarily wide. Therefore, in the present embodiment, using the property that the number Nq of character blocks extracted from the query image changes according to the area of the query image, a square rectangle having a length proportional to the square root of Nq as one side. The mean shift method is applied using an area or a rectangular area having a 4: 3 aspect ratio of a general camera image.

  Output step: Displays the content obtained as a result of the inquiry on the client unit.

  Step 970) The content search unit 380 passes, to the server-side data transmission / reception unit 350, a search result that satisfies a certain condition among the above inquiry results.

  In the present embodiment, the designated number of contents that are closest to the in-page hit position of the hit page described above are extracted. In this embodiment, since the hit page is 5440566ca69690a43d15fd89943316cf and the hit position within the page is (0.2368, 0.4732), the content DB 390 is searched from the nearest content, and the result is shown in FIG. In this way, “tomato_1.mp4” and “tomato_2.mp4” are extracted. These are transferred to the server-side data transmitting / receiving unit 350 as a search result together with the file type. The server-side data transmission / reception unit 350 passes the search result passed from the content search unit 380 to the client-side data transmission / reception unit 420 via the network.

  Step 980) The client side data transmitting / receiving unit 420 passes the search result passed from the server side data transmitting / receiving unit 350 to the content display unit 412. The content display unit 412 displays the search result passed from the client-side data transmission / reception unit 420 using content display means (FIG. 9) preset in the content display unit 412.

  As described above, when associating content with a document, the document structure such as a document chapter, section, paragraph, etc. is ignored, and the content is simply associated with a physical document position, and the client unit (client terminal) The content search device that selects content based on the physical distance between the barycentric coordinates of the block group acquired from the photographed image and the content makes it possible to save the trouble of manually registering the document structure.

  In addition, the operation of each component of the server unit 300 shown in FIG. 3 in the above embodiment is constructed as a program and installed in a computer used as the server unit (content search device) to be executed, or the network is It is possible to circulate through.

  Further, the constructed program can be stored in a portable storage medium such as a hard disk, a flexible disk, or a CD-ROM, and installed in a computer or distributed.

  The present invention is not limited to the above-described embodiment, and various modifications and applications can be made within the scope of the claims.

DESCRIPTION OF SYMBOLS 100 Document reader 110 Optical character recognition apparatus 200 Document group 210 Document page 300 Server part 310 Data input part 320 Character block extraction part 330 Index output part 340 Index DB
350 Server-side data transmission / reception unit 360 DB inquiry unit 370 Character block gravity center calculation unit 380 Content search unit 390 Content DB
400 Client unit 410 Client side device 411 Document photographing unit 412 Content display unit 420 Client side data transmission / reception unit

Claims (5)

A content search that uses a partial area in a document in which a page break or a line break position is determined as a search query, acquires the document in which the area appears and the position in the document, and presents the content associated with the acquired position A device,
A document input means for accepting input of documents to be indexed;
Character block extraction means for extracting a character block consisting of a combination of one or more characters from the whole or a partial area of the input document;
An index output means for associating the character block and a page identifier and a page coordinate in the document in which the character block appears, and outputting to the index DB;
Query input means for accepting a partial area in a document as a search query,
Query character block extraction means for extracting a query character block consisting of a combination of one or more characters from the search query;
Search means for searching the index DB based on the query character block and outputting the search result;
The search results are totaled for each page, the page in which the most character blocks are searched is set as a hit page, the center of gravity of the in-page coordinates of the character blocks searched in the hit page is calculated, and the hit position in the page is calculated. A character block center of gravity calculating means;
A content DB that stores the relationship between the page identifier, the position in the page, and the content associated with the position;
Using the hit page calculated by the character block centroid calculating means and the hit position in the page as a query, the page identifier that matches the hit page and the content associated with the page position near the hit position in the page are related to the content Content search means for searching from the content DB;
A content search apparatus comprising: The character block centroid calculating means
The content search apparatus according to claim 1, wherein a mean shift method is used when calculating the center of gravity of the in-page coordinates of the character block. A content search that uses a partial area in a document in which a page break or a line break position is determined as a search query, acquires the document in which the area appears and the position in the document, and presents the content associated with the acquired position A method,
As a storage means,
Index DB,
In a device having a page identifier, a position in a page, and a content DB that stores a relationship between contents associated with the position,
A document input means for receiving an input of a document to be indexed, and a document input step;
A character block extracting step for extracting a character block consisting of a combination of one or more characters from the whole or a partial area of the input document;
An index output means for associating the character block and a page identifier in the document in which the character block appears with the in-page coordinates and outputting to the index DB;
A query input step in which the query input means accepts a partial area in a document as a search query;
A query character block extracting means for extracting a query character block consisting of a combination of one or more characters from the search query;
A search unit that searches the index DB based on the query character block and outputs the search result;
The character block center of gravity calculation means totals the search results for each page, sets the page where the most character blocks are searched as a hit page, and calculates the center of gravity of the in-page coordinates of the character block searched within the hit page. , A character block centroid calculation step as a hit position in the page,
The content search means uses the hit page calculated in the character block centroid calculating step and the hit position in the page as a query, and associates a page position near the hit position in the page with a page identifier that matches the hit page. A content search step of searching the content DB for the obtained content;
The content search method characterized by performing. In the character block centroid calculating step,
The content search method according to claim 3, wherein a mean shift method is used when calculating the center of gravity of the in-page coordinates of the character block.   The program for functioning a computer as each means which comprises the content search device of Claim 1 or 2.

Images