# US 2018/0025031 A1 · Graph-based online image queries

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2018/0025031 A1
- Document ID: US20180025031A1
- Status: Published application
- Kind: A1
- Application number: 15/215,864
- Filed: 2016-07-21
- Published: 2018-01-25
- Earliest claimed: 2016-07-21
- Assignees: International Business Machines Corporation
- Applicants: International Business Machines Corporation
- Inventors: Jui-Hsin Lai; Ching- Yung Lin; Lifeng Nai; Yinglong Xia
- Web page: https://patentgrep.com/patent/US20180025031A1

## CPC

- G06F 16/51: Indexing; Data structures therefor; Storage structures
- G06F 16/58: Retrieval characterised by using metadata, e.g. metadata not derived from the content or metadata generated manually
- G06F 16/583: using metadata automatically derived from the content
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A query image is obtained. In a database including a plurality of reference image graphs, at least one of the reference image graphs, with feature vectors similar to the query image, is identified. Image querying is carried out by graph traversal on the at least one of the reference image graphs with the feature vectors similar to the query image. An image from the at least one of the reference image graphs having a highest matching score in the graph traversal is returned as a response to the query image. techniques for building the database are also disclosed.

## Claims

### Claim 1

A method comprising:
obtaining a query image;
in a database comprising a plurality of reference image graphs, identifying at least one of said reference image graphs with feature vectors similar to said query image;
carrying out image querying by graph traversal on said at least one of said reference image graphs with said feature vectors similar to said query image; and
returning, as a response to said query image, an image from said at least one of said reference image graphs having a highest matching score in said graph traversal.

### Claim 2 (depends on 1)

The method of claim 1, further comprising building said database.

### Claim 3 (depends on 2)

The method of claim 2, wherein building said database comprises:
obtaining a first uploaded image as a candidate to be added to said database;
comparing said first uploaded image to existing reference image graphs;
eliminating said first uploaded image from consideration for addition to a given one of said reference image graphs to which it is insufficiently similar; and
adding said first uploaded image to another given one of said reference image graphs to which it is sufficiently similar, but not so similar that it does not convey useful information.

### Claim 4 (depends on 3)

The method of claim 3, wherein building said database further comprises:
obtaining a second uploaded image as a candidate to be added to said database;
determining that said second uploaded image is insufficiently similar to any of said existing reference image graphs; and
beginning a new reference image graph with said second uploaded image, responsive to said determining.

### Claim 5 (depends on 4)

The method of claim 4, wherein building said database further comprises:
obtaining a third uploaded image as a candidate to be added to said database;
determining that said third uploaded image is so highly similar to at least one of said existing reference image graphs that it would not convey useful information; and
responsive to said determining that said third uploaded image would not convey useful information, discarding said third uploaded image.

### Claim 6 (depends on 1)

The method of claim 1, further comprising identifying a characteristic image for each of said reference image graphs, wherein said identifying of said at least one of said reference image graphs with feature vectors similar to said query image comprises comparing said query image to each characteristic image for each of said reference image graphs.

### Claim 7 (depends on 6)

The method of claim 6, wherein said identifying a characteristic image for each of said reference image graphs comprises identifying a central image for each of said reference image graphs.

### Claim 8 (depends on 6)

The method of claim 6, wherein said identifying a characteristic image for each of said reference image graphs comprises calculating an average feature vector of all images in each of said reference image graphs.

### Claim 9 (depends on 6)

The method of claim 6, wherein said identifying a characteristic image for each of said reference image graphs comprises calculating a principal feature vector of images in each of said reference image graphs.

### Claim 10 (depends on 6)

The method of claim 6, wherein said graph traversal comprises:
comparing said query image to each image in said at least one of said reference image graphs which is connected to said characteristic image of said at least one of said reference image graphs to determine which of said connected images has a highest score to said query image; and
repeating said comparing step for each image in said at least one of said reference image graphs which is connected to said connected image having a highest score to said query image, until said score declines, wherein said connected image having said highest score prior to said decline comprises said image from said at least one of said reference image graphs having said highest matching score in said graph traversal.

### Claim 11 (depends on 1)

The method of claim 1, wherein:
said query image is obtained at a database application executing in a workload layer of a cloud computing environment, via a network connection from a remote computing device;
said identifying and carrying out image querying steps are carried out by said database application executing in said workload layer of a cloud computing environment; and
said returning of said image is carried out by said database application executing in said workload layer of said cloud computing environment, sending, via said network connection, to said remote computing device, said image from said at least one of said reference image graphs having said highest matching score in said graph traversal.

### Claim 12

A system comprising:
a plurality of hardware servers;
a database application executing in a workload layer on top of said plurality of hardware servers; and
a network interface in data communication with said database application;
wherein:
said database application obtains a query image over said network interface;
said database application comprises a plurality of reference image graphs, and identifies at least one of said reference image graphs with feature vectors similar to said query image;
said database application carries out image querying by graph traversal on said at least one of said reference image graphs with said feature vectors similar to said query image; and
said database application returns, as a response to said query image, via said network interface, an image from said at least one of said reference image graphs having a highest matching score in said graph traversal.

### Claim 13 (depends on 12)

The system of claim 12, wherein said database adds new images by:
obtaining a first uploaded image as a candidate to be added to said database;
comparing said first uploaded image to existing reference image graphs;
eliminating said first uploaded image from consideration for addition to a given one of said reference image graphs to which it is insufficiently similar; and
adding said first uploaded image to another given one of said reference image graphs to which it is sufficiently similar, but not so similar that it does not convey useful information.

### Claim 14 (depends on 13)

The system of claim 13, wherein said database further adds new images by:
obtaining a second uploaded image as a candidate to be added to said database;
determining that said second uploaded image is insufficiently similar to any of said existing reference image graphs; and
beginning a new reference image graph with said second uploaded image, responsive to said determining.

### Claim 15 (depends on 14)

The system of claim 14, wherein said database further adds new images by:
obtaining a third uploaded image as a candidate to be added to said database;
determining that said third uploaded image is so highly similar to at least one of said existing reference image graphs that it would not convey useful information; and
responsive to said determining that said third uploaded image would not convey useful information, discarding said third uploaded image.

### Claim 16

A non-transitory computer readable medium comprising computer executable instructions which when executed by a computer cause the computer to perform the method of:
obtaining a query image;
in a database comprising a plurality of reference image graphs, identifying at least one of said reference image graphs with feature vectors similar to said query image;
carrying out image querying by graph traversal on said at least one of said reference image graphs with said feature vectors similar to said query image; and
returning, as a response to said query image, an image from said at least one of said reference image graphs having a highest matching score in said graph traversal.

### Claim 17 (depends on 16)

The non-transitory computer readable medium of claim 16, wherein said method further comprises building said database.

### Claim 18 (depends on 17)

The non-transitory computer readable medium of claim 17, wherein said method step of building said database comprises:
obtaining a first uploaded image as a candidate to be added to said database;
comparing said first uploaded image to existing reference image graphs;
eliminating said first uploaded image from consideration for addition to a given one of said reference image graphs to which it is insufficiently similar; and
adding said first uploaded image to another given one of said reference image graphs to which it is sufficiently similar, but not so similar that it does not convey useful information.

### Claim 19 (depends on 18)

The non-transitory computer readable medium of claim 18, wherein said method step of building said database further comprises:
obtaining a second uploaded image as a candidate to be added to said database;
determining that said second uploaded image is insufficiently similar to any of said existing reference image graphs; and
beginning a new reference image graph with said second uploaded image, responsive to said determining.

### Claim 20 (depends on 19)

The non-transitory computer readable medium of claim 19, wherein said method step of building said database further comprises:
obtaining a third uploaded image as a candidate to be added to said database;
determining that said third uploaded image is so highly similar to at least one of said existing reference image graphs that it would not convey useful information; and
responsive to said determining that said third uploaded image would not convey useful information, discarding said third uploaded image.
