Method and system for identifying image relatedness using link and page layout analysis

• US 7,293,007 B2
• Filed: 04/29/2004
• Issued: 11/06/2007
• Est. Priority Date: 04/29/2004
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Ma, Wei-Ying, Wen, Ji-Rong, He, Xiaofei, Cai, Deng
• Primary Examiner(s): Wong; Don
• Assistant Examiner(s): Lie; Angela M
• Application Number:
  US10/834,483
• Publication Number:
  US 20050246623A1
• Time in Patent Office: 1,286 Days
• Field of Search: 707/1
• US Class Current: 1/1
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 16/9538 Presentation of query results
• CPC Class Codes: Y10S 707/99931 Database or file accessing

Abstract

A method and system for determining relatedness of images of pages based on link and page layout analysis. A link analysis system determines relatedness between images by first identifying blocks within web pages, and then analyzing the importance of the blocks to web pages, web pages to blocks, and images to blocks. Based on this analysis, the link analysis system determines the degree to which each image is related to each other image. The link analysis system may also use the relatedness of images to generate a ranking of the images. The link analysis system may also generate a vector representation of the images based on their relatedness and apply a clustering algorithm to the vector representations to identify clusters of related images.

Claims

1. A method in a computer system for determining relatedness between images within blocks of pages, the method comprising:

for each combination of a block and a page, calculating a value indicator for the block to the page;

for each combination of a page and a block, calculating a value indicator for the page to the block;

for each combination of an image and a block, calculating a value indicator for the image to the block;

calculating image-to-image indicators of relatedness of ordered pairs of images by combining the value indicators for the blocks to pages, the value indicators for the pages to blocks, and the value indicators for the images to blocks; and

storing in a computer-readable medium the calculated image-to-image indicators of relatedness of an image to another image

wherein the value indicator for an image to a block is a probability of a user focusing on the image of the block.

2. The method of claim 1 wherein the value indicator for a page to a block is a probability of a user selecting a link from the block that leads to the other page.

3. The method of claim 1 wherein the value indicator for a block to a page is a probability of a user focusing on the block of the page.

4. The method of claim 1 including calculating a rank of the images from the image-to-image indicators.

5. The method of claim 4 wherein the calculated rank is based on a stationary probability distribution of a user starting at an arbitrary image transitioning to another image.

6. A method in a computer system for determining relatedness between images within block of pages, the method comprising:

for each combination of a block and a page, calculating a value indicator for the block to the page;

for each combination of a page and a block, calculating a value indicator for the page to the block;

for each combination of an image and a block, calculating a value indicator for the image to the block;

calculating image-to-image indicators of relatedness of ordered pairs of images by combining the value indicators for the blocks to pages, the value indicators for the page to blocks, and the value indicators for the images to the blocks; and

storing in a computer-readable medium the calculated image-to-image indicators of relatedness of an image to another image

wherein the value indicator for a page to a block is a probability of a user selecting a link from the block that leads to the page, the value indicator for a block to a page is a probability of a user focusing on the block of the page, and the value indicator for an image to a block is a probability of a user focusing on the image of the block.

7. A method in a computer system for determining relatedness between images within blocks of pages, the method comprising:

for each combination of a block and a page, calculating a value indicator for the block to the page;

for each combination of a page and a block, calculating a value indicator for the page to the block;

for each combination of an image and a block, calculating a value indicator for the image to the block;

calculating image-to-image indicators of relatedness of ordered pairs of images by combining the value indicators of the blocks to pages, the value indicators for the pages to blocks, and the value indicators for the images to the blocks; and

storing in a computer-readable medium the calculated image-to-image indicators of relatedness of an image to another image

wherein the image-to-image indicators are calculated as follows;

W_I=Y^TW_BY

where W_I is a matrix of the image-to-image indicators, Y is a matrix of image-to-block indicators, and

W_B=ZX

where W_B is a matrix of block-to-block indicators, Z is a matrix of the indicators for pages to blocks, and X is a matrix of the value indicators for blocks to pages.

8. A method in a computer system for determining relatedness between images within blocks of pages, the method comprising:

for each combination of a block and a page, calculating a value indicator for the block to the page;

for each combination of a page and a block, calculating a value indicator for the page to the block;

for each combination of an image and a block, calculating a value indicator for the image to the block;

calculating image-to-image indicators of relatedness of ordered pairs of images by combining the value indicators for the blocks to pages, the value indicators for the pages to blocks, and the value indicator for the images to blocks;

generating a vector representation of each image based on the image-to-image indicators; and

identifying clusters of images based on their vector representations wherein images in a cluster are related

wherein the value indicator for an image to a block is a probability of a user focusing on the image of the block.

9. A computer system for determining relatedness between images within blocks of pages, comprising:

for each combination of a page and a block, a value indicator for the page to the block;

for each combination of a page and a block, a value indicator for the block to the page;

for each combination of an image and a block, a value indicator for an image to a block;

means for calculating image-to-image indicators of relatedness of ordered pairs of images by combining the value indicator for blocks to pages, the value indicators for pages to blocks, and the value indicators for images to blocks; and

means for calculating the value indicator for an image to a block as a probability of a user focusing on the image of the block.

10. The computer system of claim 9 including means for calculating a value indicator for a page to a block as a probability of a user selecting a link from a block that leads to the page.

11. The computer system of claim 9 including means for calculating a value indicator for a block to a page as a probability of a user focusing on the block of the page.

12. The computer system of claim 9 including means for calculating a rank of the images from the image-to-image indicators.

13. The computer system of claim 12 wherein the calculated rank is based on a stationary probability distribution of a user starting at an arbitrary image transitioning to another image.

14. The computer system of claim 9 including:

means for generating a vector representation of each image based on the image-to-image indicators; and

means for identifying clusters of images based on their vector representations wherein images in a cluster are related.