# US 9,436,707 B2 · Content-based image ranking > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 9,436,707 B2 - Document ID: US9436707B2 - Status: Granted - Kind: B2 - Application number: 14/330,195 - Filed: 2014-07-14 - Published: 2015-06-11 - Granted: 2016-09-06 - Earliest claimed: 2009-08-25 - Assignees: Google Inc. - Applicants: Google Inc. - Inventors: Sanjiv Kumar; Henry Allan Rowley; Ameesh Makadia - Web page: https://patentgrep.com/patent/US9436707B2 ## CPC - G06F 16/54: Browsing; Visualisation therefor - G06F 16/583: using metadata automatically derived from the content - G06F 18/22: Matching criteria, e.g. proximity measures - G06F 18/2323: based on graph theory, e.g. minimum spanning trees [MST] or graph cuts - G06V 10/761: {Proximity, similarity or dissimilarity measures} - G06V 2201/10: Recognition assisted with metadata - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) - G06V: IMAGE OR VIDEO RECOGNITION OR UNDERSTANDING ## Abstract Methods, systems, and apparatus, including computer program products, for ranking search results for queries. The method includes calculating a visual similarity score for one or more pairs of images in a plurality of images based on visual features of images in each of the one or more pairs; building a graph of images by linking each of one or more images in the plurality of images to one or more nearest neighbor images based on the visual similarity scores; associating a respective score with each of one or more images in the graph based on data indicative of user behavior relative to the image as a search result for a query; and determining a new score for each of one or more images in the graph based on the respective score of the image, and the respective scores of one or more nearest neighbors to the image. ## Claims ### Claim 1 A computer-implemented method comprising: extracting a first set of features from visual content of a particular image; accessing, for one or more image pairs in a plurality of images, a visual similarity score representing a level of similarity between visual features of images in each of the one or more pairs; identifying, a first set of features from visual content for a particular image from the plurality of images and by one or more processors, a set of nearest neighbor images based on the visual similarity scores of the one or more image pairs that include the particular image and identifying one or more nearest neighbor images based on a distance measure between the first set of features and a second set of features of visual content of the one or more nearest neighbor images; accessing, for each of one or more nearest neighbor images in the set of nearest neighbor images, historical click data specifying a count of user interactions with the nearest neighbor image when the nearest neighbor image was presented as a search result responsive to a query, and wherein a presentation time of the nearest neighbor image after the user interaction exceeded a pre-determined threshold; and determining, for the particular image and by one or more processors, a score based on the historical click data as weighted by the visual similarity to the particular image. ### Claim 2 (depends on 1) The method of claim 1, further comprising ranking each of the plurality of images based on the score. ### Claim 3 (depends on 1) The method of claim 1, further comprising determining the distance measure based on a combination of basic distances from multiple visual features. ### Claim 4 (depends on 1) The method of claim 1, further comprising determining the distance measure based on a joint equal contribution. ### Claim 5 (depends on 1) The method of claim 1, wherein determining the score comprises calculating C=(1−α*(I−(α*W))−1*c, where c is a vector representing the visual similarity scores, C is a vector representing the determined scores, W is a matrix representing normalized weights, I is an identity matrix, and α is a determined parameter. ### Claim 6 (depends on 5) The method of claim 5, where determining the score includes: iteratively calculating the score until convergence. ### Claim 7 A non-transitory computer readable medium encoded with a computer program that causes one or more processors to perform operations comprising: accessing, for one or more image pairs in a plurality of images, a visual similarity score representing a level of similarity between visual features of images in each of the one or more pairs; extracting a first set of features from visual content of a particular image; identifying, a first set of features from visual content for a particular image from the plurality of images and by one or more processors, a set of nearest neighbor images based on the visual similarity scores of the one or more image pairs that include the particular image and identifying one or more nearest neighbor images based on a distance measure between the first set of features and a second set of features of visual content of the one or more nearest neighbor images; accessing, for each of one or more nearest neighbor images in the set of nearest neighbor images, historical click data specifying a count of user interactions with the nearest neighbor image when the nearest neighbor image was presented as a search result responsive to a query, and wherein a presentation time of the nearest neighbor image after the user interaction exceeded a pre-determined threshold; and determining, for the particular image and by one or more processors, a score based on the historical click data as weighted by the visual similarity to the particular image. ### Claim 8 (depends on 7) The non-transitory computer readable medium of claim 7, wherein the computer program causes the one or more processors to perform operations further comprising ranking each of the plurality of images based on the score. ### Claim 9 (depends on 7) The non-transitory computer readable medium of claim 7, wherein the computer program causes the one or more processors to perform operations further comprising determining the distance measure based on a combination of basic distances from multiple visual features. ### Claim 10 (depends on 7) The non-transitory computer readable medium of claim 7, wherein the computer program causes the one or more processors to perform operations further comprising determining the distance measure based on a joint equal contribution. ### Claim 11 (depends on 9) The non-transitory computer readable medium of claim 9, wherein determining the score comprises calculating C=(1−.alpha.)*(I−(.alpha.*W)).sup.−1*c, where c is a vector representing the visual similarity scores, C is a vector representing the determined scores, W is a matrix representing normalized weights, I is an identity matrix, and .alpha. is a determined parameter. ### Claim 12 A system, comprising: a machine readable storage device including a computer program; and one or more processors that interact with the machine readable storage device and upon execution of the computer program performs operations comprising: accessing, for one or more image pairs in a plurality of images, a visual similarity score representing a level of similarity between visual features of images in each of the one or more pairs; extracting a first set of features from visual content of a particular image; identifying, a first set of features from visual content for a particular image from the plurality of images and by one or more processors, a set of nearest neighbor images based on the visual similarity scores of the one or more image pairs that include the particular image and identifying one or more nearest neighbor images based on a distance measure between the first set of features and a second set of features of visual content of the one or more nearest neighbor images; accessing, for each of one or more nearest neighbor images in the set of nearest neighbor images, historical click data specifying a count of user interactions with the nearest neighbor image when the nearest neighbor image was presented as a search result responsive to a query, and wherein a presentation time of the nearest neighbor image after the user interaction exceeded a pre-determined threshold; and determining, for the particular image and by one or more processors, a score based on the historical click data as weighted by the visual similarity to the particular image. ### Claim 13 (depends on 12) The system of claim 12, wherein the computer program causes the one or more processors to perform operations further comprising ranking each of the plurality of images based on the score. ### Claim 14 (depends on 12) The system of claim 12, wherein the computer program causes the one or more processors to perform operations further comprising determining the distance measure based on a combination of basic distances from multiple visual features. ### Claim 15 (depends on 12) The system of claim 12, wherein further comprising determining the distance measure based on a joint equal contribution. ### Claim 16 (depends on 12) The system of claim 12, wherein determining the score comprises calculating C=(1−α)*(I−(α*W))−1*c, where c is a vector representing the visual similarity scores, C is a vector representing the determined scores, W is a matrix representing normalized weights, I is an identity matrix, and α is a determined parameter. ### Claim 17 (depends on 16) The system of claim 16, wherein determining the score includes: iteratively calculating the score until convergence.