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.