Automatic determination of whether a document includes an image gallery

• US 7,788,258 B1
• Filed: 06/21/2004
• Issued: 08/31/2010
• Est. Priority Date: 06/21/2004
• Status: Expired due to Fees

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Yang, Cheng, Zunger, Yonatan, Malpani, Radhika
• Primary Examiner(s): Mofiz; Apu M
• Assistant Examiner(s): Bibbee; Jared M
• Application Number:
  US10/871,030
• Time in Patent Office: 2,262 Days
• Field of Search: None
• US Class Current: 707/724
• CPC Class Codes: G06F 16/532 Query formulation, e.g. graphical querying
• CPC Class Codes: G06F 16/58 Retrieval characterised by using metadata, e.g. metadata not derived from the content or metadata generated manually
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 16/9538 Presentation of query results
• CPC Class Codes: G06F 18/24 Classification techniques

Abstract

Image galleries are automatically located within documents, such as web pages. Documents that are determined to contain image galleries may be treated differently when storing the document for later retrieval by an image search engine. In one implementation, the image galleries are automatically located within a document by calculating position information indicating relative positions of images in the document. The document may be determined to contain an image gallery when the position information indicates that the images in the document are generally evenly distributed.

Claims

1. A computer-implemented method comprising:

identifying, by one or more processors, a document stored on a server in a network;

calculating, by one or more processors, position information indicating relative positions of images in the document, the position information providing an indication of horizontal and vertical distances between the images in the document, the horizontal and vertical distances corresponding to spatial distances between the images when the document is rendered and displayed on a display;

constructing, by one or more processors, a histogram based on the horizontal and vertical distances between the images in the document;

calculating, by one or more processors, a likelihood that the document includes an image gallery based on a peak value in the histogram;

indicating, by one or more processors, that the document contains an image gallery or does not contain an image gallery based on the calculated likelihood; and

in response to an indication that the document contains an image gallery, updating, by one or more processors, an index, stored in a memory, that references the document or a score of the document.

2. The method of claim 1, where indicating that the document contains an image gallery or does not contain an image gallery is further based on links corresponding to images in the document or sizes of images in the document.

3. The method of claim 1, where the calculating the position information includes:

locating tokens in the document; and

generating a token table in which the located tokens are assigned to cells in the token table such that tokens in the token table are arranged to have a logical spatial layout in the token table corresponding to a spatial layout of the images in the document.

4. The method of claim 3, where tokens that are contained in nested tables within the document are assigned to the token table based on a flattened version of the tables within the document.

5. The method of claim 3, where the document is a hypertext markup language (HTML) document and the tokens include references to images using an HTML image tag.

6. The method of claim 5, where the tokens additionally include text delineated with paragraph header or line break HTML tags.

7. The method of claim 1, where the likelihood that the document includes an image gallery is calculated as

1−

e<sup>−

p/3</sup>,

where p is the peak value in the histogram.

8. A device comprising:

means for identifying a document stored on a server in a network;

means for calculating position information indicating relative positions of images in the document, the position information providing an indication of spacing of the images in the document, the means for calculating including;

means for constructing a histogram based on horizontal and vertical distances between the images in the document, the horizontal and vertical distances corresponding to spatial distances between the images when the document is rendered and displayed, and

means for calculating a likelihood that the document includes an image gallery based on a peak value in the histogram;

means for determining that the document contains an image gallery when the calculated position information indicates that the images are uniformly arranged relative to one another within the document;

means for determining that the document does not contain an image gallery when the calculated position information indicates that the images are not uniformly arranged relative to one another in the document; and

means for storing an indication that the document contains the image gallery when the document is determined to contain the image gallery.

9. The device of claim 8, where the means for calculating further includes:

means for locating tokens in the document; and

means for generating a token table based on a spatial layout of the located tokens.

10. The device of claim 9, where tokens that are contained in nested tables within the document are assigned to the token table based on a flattened version of the tables within the document.

11. An image search engine implemented in a computer device, comprising:

a search component to return images relevant to search queries based on a comparison of a search query to a document index; and

an image indexing component to store the document index based on text associated with images in documents, the image indexing component annotating the document index to indicate documents in the document index that include an image gallery, where the image indexing component is to automatically determine that a document includes an image gallery by analyzing the relative positions of images in the document to determine whether the images in the document are evenly spaced in the document with respect to one another, where the image indexing component is to automatically determine whether a document includes an image gallery by;

constructing a two-dimensional histogram of occurrences of images based on horizontal and vertical image spacings from one another, the horizontal and vertical image spacings corresponding to spatial distances between the images when the document is rendered and displayed; and

calculating a likelihood that the document includes an image gallery based on a peak value in the histogram.

28. The image search engine of claim 11, where the likelihood that the document includes an image gallery is calculated as

1−

e<sup>−

p/3</sup>,

where p is the peak value in the histogram.

12. An image search engine implemented in a computer device, comprising:

a search component to return images relevant to search queries based on a comparison of the search query to a document index; and

an image indexing component to store the document index based on text associated with images in documents, the image indexing component annotating the document index to indicate documents in the document index that include an image gallery, the image indexing component to automatically determine that a document includes an image gallery based on relative positions of images within the document, where the image indexing component determines the relative position of images in the document by;

locating tokens in the document, the located tokens corresponding to the images in the document;

generating a token table in which the located tokens are assigned to cells in the token table such that tokens in the token table are arranged to have a logical spatial layout in the token table corresponding to a spatial layout of the images in the document; and

constructing a two-dimensional histogram based on horizontal and vertical distances between the located tokens in the document, the horizontal and vertical distances corresponding to spatial distances between the images when the document is rendered and displayed.

13. The image search engine of claim 12, where tokens that are contained in nested tables within the document are assigned to the token table based on a flattened version of the tables within the document.

14. A computer-implemented method comprising:

calculating, by one or more processors, position information indicating relative positions of images in documents that are stored on at least one server in a network, the position information providing an indication of spacing of the images in the documents, the calculating including;

constructing, by one or more processors, histograms based on horizontal and vertical distances between the images in the documents, the horizontal and vertical distances corresponding to spatial distances between the images when the documents are rendered and displayed on a display;

calculating, by one or more processors, a likelihood that each document, of the documents, includes an image gallery based on a peak value in the histogram;

determining, by one or more processors, that a first document of the documents contains an image gallery when the calculated position information indicates that the images are uniformly arranged relative to one another within the first document;

determining, by one or more processors, that the first document does not contain an image gallery when the calculated position information indicates that the images are not uniformly arranged relative to one another within the first document;

generating, by one or more processors, a document index based on text associated with the images in the first document, the document index being structured such that images that are arranged in image galleries are ranked differently than images that are not arranged in the image galleries;

storing the generated document index in a memory; and

returning, by one or more processors, images relevant to a search query based on a comparison of the search query to the document index.

29. The method of claim 14, where the likelihood that the first document includes an image gallery is calculated as

1−

e<sup>−

p/3</sup>,

where p is the peak value in the histogram.

15. A computer-implemented method comprising:

crawling, by one or more processors, a network to identify documents stored on a server;

determining, by one or more processors, that a document, that is identified, contains an image gallery based on a spatial layout of images in the document and links corresponding to images in the document or sizes of images in the document, where determining that the document contains an image gallery includes;

constructing, by one or more processors, a histogram based on horizontal and vertical distances between images in the document, the horizontal and vertical distances corresponding to spatial distances between the images when the document is rendered and displayed, and

calculating, by one or more processors, a likelihood that the document includes an image gallery based on a peak value in the histogram; and

updating, by one or more processors, an index, in a memory and that includes the document, to indicate that the document contains an image gallery.

16. The method of claim 15, where determining that the document contains an image gallery based on the spatial layout of images in the document further includes:

determining that the document contains an image gallery when the spatial layout of the images in the document indicates that the images are evenly distributed.

17. The method of claim 15, where the spatial layout of the images in the document are determined by:

locating tokens in the document; and

generating a token table based on a spatial layout of the located tokens, the token table representing the spatial layout of the images in the document.

18. The method of claim 17, where tokens that are contained in nested tables within the document are assigned to the token table based on a flattened version of the tables within the document.

19. The method of claim 17, where the document is a hypertext markup language (HTML) document and the tokens include references to images using an HTML image tag.

20. The method of claim 19, where the tokens additionally include text delineated with paragraph header or line break HTML tags.

21. The method of claim 15, where the likelihood that the document includes an image gallery is calculated as

1−

e<sup>−

p/3</sup>,

where p is the peak value in the histogram.

22. A computer-implemented method comprising:

identifying, by one or more processors, a document stored on a server in a network;

locating, by one or more processors, tokens in the document, the tokens representing images in the document;

generating, by one or more processors, a token table based on a spatial layout of the located tokens;

calculating, by one or more processors, position information indicating relative positions of the images in the document based on the token table, the calculating including;

constructing, by one or more processors, and using the token table, a histogram based on the horizontal and vertical distances between the tokens in the token table, the horizontal and vertical distances corresponding to spatial distances between the images when the document is rendered and displayed on a display;

calculating, by one or more processors, a likelihood that the document includes an image gallery based on a peak value in the histogram;

determining, by one or more processors, that the document contains an image gallery when the position information indicates that the images in the document are evenly spaced in the document with respect to one another;

determining, by one or more processors, that the document does not contain an image gallery when the position information indicates that the images in the document are not evenly spaced in the document with respect to one another; and

updating, by one or more processors, an index in a memory based on whether the document is determined to contain an image gallery.

23. The method of claim 22, where tokens that are contained in nested tables within the document are assigned to the token table based on a flattened version of the tables within the document.

24. The method of claim 23, where the tokens additionally include text delineated with paragraph header or line break HTML tags.

25. A computer-readable memory device including computer-executable instructions, the computer-readable memory device comprising:

one or more instructions to identify a document stored on a server in a network;

one or more instructions to calculate position information indicating relative positions of images in the document, the position information providing an indication of spacing of the images in the document, where the one or more instructions to calculate position information includes;

one or more instructions to construct a histogram based on horizontal and vertical distances between the images in the document, the horizontal and vertical distances corresponding to spatial distances between the images when the document is rendered and displayed on a display, and

one or more instructions to calculate, by the processor, a likelihood that the document includes an image gallery based on a peak value in the histogram;

one or more instructions to determine that the document contains an image gallery when the calculated position information indicates that the images are uniformly arranged relative to one another within the document;

one or more instructions to determine that the document does not contain an image gallery when the calculated position information indicates that the images are not uniformly arranged relative to one another within the document; and

one or more instructions to, in response to a determination that the document contains an image gallery, update an index that references the document or a score of the document.

26. The computer-readable memory device of claim 25, where the one or more instructions to calculate the position information comprises:

one or more instructions to locate tokens in the document; and

one or more instructions to generate a token table in which the located tokens are assigned to cells in the token table such that tokens in the token table are arranged to have a logical spatial layout in the token table corresponding to a spatial layout of the images in the document.

27. The computer-readable memory device of claim 26, where tokens that are contained in nested tables within the document are assigned to the token table based on a flattened version of the tables within the document.