Image processing apparatus and method

• US 6,898,326 B2
• Filed: 05/17/1999
• Issued: 05/24/2005
• Est. Priority Date: 03/31/1995
• Status: Expired due to Term

• Current Assignee: Canon Kabushiki Kaisha (Canon Inc.)
• Original Assignee: Canon Kabushiki Kaisha (Canon Inc.)
• Inventors: Washizawa, Teruyoshi
• Primary Examiner(s): Johnson, Timothy M.
• Assistant Examiner(s): DESIRE, GREGORY M
• Application Number:
  US09/312,841
• Publication Number:
  US 20030053705A1
• Time in Patent Office: 2,199 Days
• Field of Search: 382/251, 382/253, 382/266, 382/277, 382/195, 382/247, 382/250, 375/240.02, 375/240.22, 375/240.03, 375/240.2, 348/404.1
• US Class Current: 382/253
• CPC Class Codes: G06T 9/008 Vector quantisation
• CPC Class Codes: H04N 19/124 Quantisation
• CPC Class Codes: H04N 19/13 Adaptive entropy coding, e.g. adaptive variable length coding [AVLC] or context adaptive binary arithmetic coding [CABAC]
• CPC Class Codes: H04N 19/136 Incoming video signal characteristics or properties
• CPC Class Codes: H04N 19/146 Data rate or code amount at the encoder output
• CPC Class Codes: H04N 19/149 by estimating the code amount by means of a model, e.g. mathematical model or statistical model
• CPC Class Codes: H04N 19/15 by monitoring actual compressed data size at the memory before deciding storage at the transmission buffer
• CPC Class Codes: H04N 19/17 the unit being an image region, e.g. an object
• CPC Class Codes: H04N 19/172 the region being a picture, frame or field
• CPC Class Codes: H04N 19/176 the region being a block, e.g. a macroblock
• CPC Class Codes: H04N 19/54 using feature points or meshes
• CPC Class Codes: H04N 19/60 using transform coding
• CPC Class Codes: H04N 19/91 Entropy coding, e.g. variable length coding [VLC] or arithmetic coding
• CPC Class Codes: H04N 19/94 Vector quantisation
• CPC Class Codes: H04N 5/2628 Alteration of picture size, shape, position or orientation, e.g. zooming, rotation, rolling, perspective, translation

Abstract

A transformation unit 102 transforms an entered image to multi-resolution space. A quantizer 105 performs vector quantization on a local pattern of an image of a multi-resolution representation. A perspective-order calculating unit 107 extracts a plurality of code words, positions corresponding thereto and/or angle of rotation and/or scale, and the perspective-order relationship of a plurality of these representative vectors, from the quantized image. An algebraic encoder 108 encodes the input image based upon the extracted information. As a result, there are provided an image processing apparatus and method for asymmetric encoding without motion in three dimensions and extraction of a three-dimensional structure. Further, a transformation unit 1103 transforms an entered image to vector field, and a singularity detector 1104 detects a singularity in the transformed image. A transformation encoder 1105 partitions the vector field into areas which include detected feature points, and each area is encoded by functional approximation. As a result, a finite number of feature points can be obtained with ease and an image processing apparatus and method exhibiting strong resistance to the effects of noise are provided.

Claims

1. An image processing apparatus, comprising:

a transformation section, arranged to transform data space of an input image to discrete multi-resolution space and outputting a discrete multi-resolution representation of the input image;

a detector, arranged to detect a singularity in the input image;

an extractor, arranged to extract a local pattern in the neighborhood of each singularity in the discrete multi-resolution representation of the input image, with regard to each of a plurality of depths;

a code book creator, arranged to create a quantization code book by registering the extracted local pattern as a representative vector with a code word;

a calculator, arranged to calculate an inner product of any two representative vectors in the code book;

a remover, arranged to remove one of the two representative vectors it the inner product is larger than a predetermined value;

a quantization section, arranged to replace each local pattern of respective depths of the discrete multi-resolution representation by a code word using the code book; and

an encoder, arranged to algebraicallv encode data which includes position coordinates of the singularity in the input image and the code word provided by said quantization section.

2. The apparatus according to claim 1, further comprising a counter arranged to count frequency of occurrence of the local pattern, wherein said code book creator registers a local pattern in the code book when the frequency counted by said counter is higher than a threshold.

3. The apparatus according to claim 2, further comprising:

a memory, arranged to store degree of conformity or quantization error, calculated by said quantization section when, the local pattern is allocated to a representative vector; and

a decider, on the basis of the degree of conformity or quantization error, arranged to decide the order relating to the perspective depth between any two representative vectors contained in the code data,

wherein said encoder encodes the order relating to the perspective depth.

4. An image processing apparatus comprising the image processing apparatus described in claim 3, wherein said image processing apparatus is applied to image recognition to retrieve image data from a partial image.

5. An image processing apparatus comprising:

a decoder, arranged to decode a code generated by the image processing apparatus described in claim 3;

an inverse quantization section, arranged to generate a local pattern from a code word contained in code data decoded by said decoder; and

a synthesizer, arranged to combine a plurality of local patterns, which have been generated by said inverse quantization section, based upon position coordinates of a singularity decoded by said decoder, and order information relating to depth of a plurality of representative vectors.

6. The apparatus according to claim 5, further comprising a memory arranged to store code data and output the code data stored in said memory to said decoder.

7. An image processing method, comprising the steps of:

transforming data space of an input image to discrete multi-resolution space and outputting a discrete multi-resolution representation of the input image;

detecting a singularity in the input image;

extracting a local pattern in the neighborhood of each singularity in the discrete multi-resolution representation of the input image, with regard to each of a plurality of depths;

creating a quantization code book by registering the extracted local pattern as a representative vector with a code word;

calculating an inner product of any two representative vectors in the code book;

removing one of the two representative vectors if the inner product is larger than a predetermined value; and

replacing each local pattern of respective depths of the discrete multi-resolution representation by a code word using the code book; and

algebraically encoding data which includes position coordinates of the singularity in the input image and the code word obtained in the replacing step.

8. The method according to claim 7, further comprising a step of counting frequency of occurrence of the local pattern, wherein the creating step registers a local pattern in the code book when the frequency counted in the counting step is higher than a threshold.

9. The method according to claim 8, further comprising the steps of:

calculating, in the creating step, degree of conformity or quantization error when the local pattern is allocated to a representative vector; and

deciding the order relating to the perspective depth between any two representative vectors contained in the code data based on the degree of conformity or quantization error,

wherein the encoding step encodes the order relating to the perspective depth.

10. The method according to claim 9, further comprising the steps of:

decoding a code encoded in the encoding step;

generating a local pattern from a code word contained in code data decoded in the decoding step; and

combining a plurality of local patterns, which have been generated in the quantizing step, based upon position coordinates of a singularity decoded in the decoding step, and order information relating perspective depth of a plurality of representative vectors.