Feature descriptor encoding apparatus, feature descriptor encoding method, and program

• US 9,239,850 B2
• Filed: 11/15/2012
• Issued: 01/19/2016
• Est. Priority Date: 11/18/2011
• Status: Active Grant

• Current Assignee: NEC Corporation
• Original Assignee: NEC Corporation
• Inventors: Iwamoto, Kota, Mase, Ryota
• Primary Examiner(s): Mehta, Bhavesh
• Assistant Examiner(s): Niu, Feng
• Application Number:
  US14/359,229
• Publication Number:
  US 20140321765A1
• Time in Patent Office: 1,160 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 16/51 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/583 using metadata automatically derived from the content
• CPC Class Codes: G06T 9/00 Image coding bandwidth or redundancy reduction for static pictures H04N1/41; coding or decoding of static colour picture signals H04N1/64; methods or arrangements for coding, decoding, compressing or decompressing digital video signals H04N19/00
• CPC Class Codes: H04N 19/54 using feature points or meshes

Abstract

An object of the present invention is to reduce the size of encoded feature descriptors. A feature descriptor encoding apparatus includes a feature point detection unit that detects feature points from an image and outputs coordinate values; a local feature descriptor extracting unit that extracts local feature descriptors from local regions centered on the coordinate values of the feature points; a coordinate value scanning unit that converts the coordinate values into index values according to a specific scanning method; a sorting unit that sorts the index values; a difference calculation unit that calculates a differential value between two adjacent index values of the sorted index values and outputs a sequence of differential values; a differential encoding unit that encodes the sequence of the differential values in a sequential permutation; and a local feature descriptor encoding unit that encodes the local feature descriptors of the corresponding feature points in the same permutation as that of the sorted index values.

Claims

1. A feature descriptor encoding apparatus comprising:

a feature point detection unit configured to detect feature points from an image and outputs coordinate values;

a local feature descriptor extracting unit configured to extract local feature descriptors from local regions centered on the coordinate values of the feature points;

a coordinate value scanning unit configured to convert the coordinate values into index values according to a specific scanning method;

a sorting unit configured to sort the index values;

a difference calculation unit configured to calculate a differential value between two adjacent index values of the sorted index values and output a sequence of differential values;

a differential encoding unit configured to encode the sequence of the differential values in a sequential permutation; and

a local feature descriptor encoding unit configured to encode the local feature descriptors of the corresponding feature points in the same permutation as that of the sorted index values,

wherein the differential encoding unit includes;

a first encoding unit configured to perform M-bit fixed-length encoding by encoding the differential value when the differential value is in an encodable value area, and by encoding an escape code indicating that the differential value is outside the encodable value area when the differential value is outside the encodable value area;

a second encoding unit configured to perform N-bit fixed length encoding by encoding the differential values by an encoding method different from that of the first encoding unit when the first encoding unit has encoded the escape code, N being larger than M; and

an optimum encoding parameter determination unit configured to determine M and N from the sequence of the differential values such that a code length of the sequence of the encoded differential values is the shortest.

2. The feature descriptor encoding apparatus according to claim 1, wherein

the optimum encoding parameter determination unit is configured to calculate the code length while M and N are changed, and determine M and N such that the code length is the shortest.

3. The feature descriptor encoding apparatus according to claim 2, wherein

the optimum encoding parameter determination unit is configured to determine a minimum N based on an equation, N=ceil (log₂(D_MAX−

2^M+2), where D_MAX is a maximum value of the sequence of the differential values.

4. The feature descriptor encoding apparatus according to claim 3, wherein

the optimum encoding parameter determination unit is configured to determine M based on an equation, L=M×

A+(M+N)×

(Z−

A), such that the code length is the shortest, where L, A,

a function of detecting feature points from an image and outputting coordinate values;

a function of extracting local feature descriptors from local regions centered on the coordinate values of the feature points;

a function of converting the coordinate values into index values according to a specific scanning method;

a function of sorting the index values;

a function of calculating a differential value between two adjacent index values of the sorted index values and outputting a sequence of differential values;

a function of encoding the sequence of the differential values in a sequential permutation; and

a function of encoding the local feature descriptors of the corresponding feature points in the same permutation as that of the sorted index values,

wherein said encoding of the sequence of the differential values includes;

performing M-bit fixed-length encoding by encoding the differential value when the differential value is in an encodable value area, and by encoding an escape code indicating that the differential value is outside the encodable value area when the differential value is outside the encodable value area;

performing N-bit fixed length encoding by encoding the differential values by an encoding method different from that of the first encoding unit when the first encoding unit has encoded the escape code, N being larger than M; and

determining M and N from the sequence of the differential values such that a code length of the sequence of the encoded differential values is the shortest. and Z are the code length, a number of the differential values in the value area, and a number of the differential values in the sequence of the differential values, respectively.

5. A feature descriptor encoding method for causing a computer to execute:

detecting feature points from an image and output coordinate values;

extracting local feature descriptors from local regions centered on the coordinate values of the feature points;

converting the coordinate values into index values according to a specific scanning method;

sorting the index values;

calculating a differential value between two adjacent index values of the sorted index values and output a sequence of differential values;

encoding the sequence of the differential values in a sequential permutation; and

encoding the local feature descriptors of the corresponding feature points in the same permutation as that of the sorted index values,

wherein said encoding of the sequence of the differential values includes;

performing M-bit fixed-length encoding by encoding the differential value when the differential value is in an encodable value area, and by encoding an escape code indicating that the differential value is outside the encodable value area when the differential value is outside the encodable value area;

performing N-bit fixed length encoding by encoding the differential by encoding method different from that of the first encoding unit when the first encoding unit has encoded the escape code, N being larger than M; and

determining M and N from the sequence of the differential values such that a code length of the sequence of the encoded differential values is the shortest.

6. A non-transitory computer-readable storage medium storing a program for causing a computer to realize.