# US 2006/0153457 A1 · Information processing apparatus and method, and program

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

- Number: US 2006/0153457 A1
- Document ID: US20060153457A1
- Status: Published application
- Kind: A1
- Application number: 11/324,562
- Filed: 2006-01-04
- Published: 2006-07-13
- Earliest claimed: 2005-01-07
- Assignees: Sony Corporation
- Inventors: Akira Nakamura; Hirotaka Suzuki; Takayuki Yoshigahara
- Web page: https://patentgrep.com/patent/US20060153457A1

## CPC

- G06F 16/583: using metadata automatically derived from the content
- G06F 18/24133: {Distances to prototypes}
- G06F 18/24147: {Distances to closest patterns, e.g. nearest neighbour classification}
- G06V 10/764: using classification, e.g. of video objects
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- G06V: IMAGE OR VIDEO RECOGNITION OR UNDERSTANDING

## Abstract

The present invention is intended to provide quick search of a plurality if any of sets subject to search for desired members. A common representative point setting block sets a common representative point common to sets on the basis of a feature vector stored in a vector information storage block and stores the set point into a common representative point information storage block. A neighborhood table group creation block creates a neighborhood table for each set on the basis of the vector information and common representative point information and stores the created table in a neighborhood table group storage block. A nearest neighborhood vector group search block, upon acquisition of an input vector, searches each set for a nearest neighborhood vector of the input vector on the basis of the vector information, the common representative point information, and the neighborhood table group and outputs the retrieved nearest neighborhood vector as a comparison result. The present invention is applicable to image processing apparatuses.

## Claims

### Claim 1

An information processing apparatus for searching a plurality of sets for a desired element, comprising:
common representative point setting means for setting common representative points that are a predetermined number of elements of a set obtained by averaging features of said plurality of sets;
neighborhood table creation means for creating, for each of said plurality of sets, a neighborhood table that is table information associated with elements of each of said plurality of sets located in the neighborhood of each common representative point on the basis of said common representative points set by said common representative point setting means; and
search means for searching elements registered in said neighborhood table created by said neighborhood table creation means for a desired element.

### Claim 2 (depends on 1)

The information processing apparatus according to claim 1, wherein said common representative point setting means sets said common representative points on the basis of all elements in said plurality of sets.

### Claim 3 (depends on 1)

The information processing apparatus according to claim 1, wherein said common representative point setting means sets said common representative points on the basis of a part of the elements in said plurality of sets.

### Claim 4 (depends on 1)

The information processing apparatus according to claim 1, wherein said search means searches the elements registered in said neighborhood table created by said neighborhood table creation means for an element nearest to an element subject to search as said desired element.

### Claim 5 (depends on 4)

The information processing apparatus according to claim 4, wherein said neighborhood table lists a predetermined number of elements in a nearer order from said common representative point and distance information that is ½ of a distance from said common representative point of each element and
said search means searches said elements registered in said neighborhood table for said desired element only if a distance of said desired element from said common representative point is smaller than a maximum value of said distance information corresponding to said common representative point in said neighborhood table or, otherwise, searches all elements of said plurality of sets for said desired element.

### Claim 6 (depends on 1)

The information processing apparatus according to claim 1, further comprising:
main component analysis means for analyzing a main component of a distribution of elements of said plurality of sets; and
coordinate conversion means for converting coordinates of said elements such that said main component analyzed by said main component analysis means becomes one of coordinate axes.

### Claim 7 (depends on 6)

The information processing apparatus according to claim 6, further comprising:
dimension compression means for compressing the number of dimensions of said distribution of said elements of which coordinate has been converted by said coordinate conversion means, thereby reducing the number of dimensions.

### Claim 8 (depends on 1)

The information processing apparatus according to claim 1, wherein said search means searches for a plurality of elements of different types, thereby searching the elements registered in said neighborhood table for an element near each of said plurality of elements subject to search as said desired element.

### Claim 9 (depends on 8)

The information processing apparatus according to claim 8, wherein said search means searches for an element near one element subject to search and uses a result of this search for a search operation for an element near another element subject to search.

### Claim 10

An information processing method for an information processing apparatus for searching a plurality of sets for a desired element, comprising the steps of:
setting common representative points that are a predetermined number of elements of a set obtained by averaging features of said plurality of sets;
creating, for each of said plurality of sets, a neighborhood table that is table information associated with elements of each of said plurality of sets located in the neighborhood of each common representative point on the basis of said common representative points set by said common representative point setting step; and
searching elements registered in said neighborhood table created by said neighborhood table creation step for a desired element.

### Claim 11

A program for making a computer execute search processing for searching each of a plurality of sets for a desired element, comprising the steps of:
setting common representative points that are a predetermined number of elements of a set obtained by averaging features of said plurality of sets;
creating, for each of said plurality of sets, a neighborhood table that is table information associated with elements of each of said plurality of sets located in the neighborhood of each common representative point on the basis of said common representative points set by said common representative point setting step; and
searching elements registered in said neighborhood table created by said neighborhood table creation step for a desired element.

### Claim 12

An information processing apparatus for searching a plurality of sets for a desired element, comprising:
a common representative point setting section for setting common representative points that are a predetermined number of elements of a set obtained by averaging features of said plurality of sets;
a neighborhood table creation section for creating, for each of said plurality of sets, a neighborhood table that is table information associated with elements of each of said plurality of sets located in the neighborhood of each common representative point on the basis of said common representative points set by said common representative point setting section; and
a search section for searching elements registered in said neighborhood table created by said neighborhood table creation section for a desired element.
