Title of Invention	A METHOD OF SEARCHING FOR AN OBJECT IN AN IMAGE BY PROCESSING SIGNALS
Abstract	The present invention relates to a method of representing an object appearing in an image or a sequence of images, by processing signals corresponding to the image, the method comprising deriving a curvature scale space (CSS) representation of the shape of the object characterized in that the method comprises quantising the co-ordinate values of peaks of the CSS representation to derive a coded representation of the shape, wherein, the peaks of the CSS representation are ordered in decreasing order of the peak height component values, and the quantisation range for a peak height component value is based on the value of the preceding peak height component value. (Figure 3)

Title of Invention

A METHOD OF SEARCHING FOR AN OBJECT IN AN IMAGE BY PROCESSING SIGNALS

Abstract

The present invention relates to a method of representing an object appearing in an image or a sequence of images, by processing signals corresponding to the image, the method comprising deriving a curvature scale space (CSS) representation of the shape of the object characterized in that the method comprises quantising the co-ordinate values of peaks of the CSS representation to derive a coded representation of the shape, wherein, the peaks of the CSS representation are ordered in decreasing order of the peak height component values, and the quantisation range for a peak height component value is based on the value of the preceding peak height component value. (Figure 3)

Full Text	The present invention relates to the representation of an object appearing, for example, in a still or video image, such as an image stored in a multimedia database, and particularly to the coding of such a representation. In applications such as image or video libraries, it is desirable to have an efficient representation and storage of the outline or shape of objects or parts of objects appearing in still or video images. A known technique for shape-based indexing and retrieval uses Curvature Scale Space (CSS) representation. Details of the CSS representation can be found in the papers "Robust and Efficient Shape Indexing through Curvature Scale Space" Proc. British Machine Vision conference, pp 53-62, Edinburgh, UK, 1996 and "Indexing an Image Database by Shape Content using Curvature Scale Space" Proc. IEE Colloquium on Intelligent Databases, London 1996, both by F. Mokhtarian, S. Abbasi and J. Kittler, the contents of which are incorporated herein by reference. The CSS representation uses a curvature function for the outline of the object, starting from an arbitrary point on the outline. The curvature function is studied as the outline shape is evolved by a series of deformations which smooth the shape. More specifically, the zero crossings of the derivative of the curvature function convolved with a family of Gaussian filters are computed. The zero crossings are plotted on a graph, known as the Curvature Scale Space, where the x-axis is the normalised arc-length of the curve and the y-axis is the evolution parameter, specifically, the paramete of the filter applied. The plots on the graph form loops characteristic of the outline. Each convex or concave part of the object outline corresponds to a loop in the CSS image. The co-ordinates of the peaks of the most prominent loops in the CSS image are used as a representation of the outline. To search for objects in images stored in a database matching the shape of an input object, the CSS representation of an input shape is calculated. The similarity between an input shape and stored shapes is determined by comparing the position and height of the peaks in the respective CSS images using a matching algorithm. The number of bits required to express the properties of the contour shape in a descriptor should be as small as possible to facilitate efficient storage and transmission. The invention can offer a very compact representation (in terms of number of bits used for storage) without any significant deterioration in retrieval performance. Embodiments of the present invention will be described with reference to the accompanying drawings of which : Fig. 1 is a block diagram of a video database system ; Fig. 2 is a CSS representation of an outline ; Fig. 3 is a diagram illustrating coding of co-ordinate values of the CSS representation. Fig. 1 shows a computerised video database system according to an embodiment of the invention. The system includes a control unit 2 in the form of a computer, a display unit 4 in the form of a monitor, a pointing device 6 in the form of a mouse, an image database 8 including stored In the above, represents convolution and subscripts represent derivatives. The number of curvature zero crossings changes as a changes, and when a is sufficiently high is a convex curve with no zero crossings. The zero crossing points (u, σ) are plotted on a graph, known as the CSS image space. This results in a plurality of curves characteristic of the original outline. The peaks of the characteristic curves are identified and the corresponding co-ordinates are extracted and stored. In general terms, this gives a set of n co-ordinate pairs [(xl, yl), (x2, y2),.... (xn, yn)], where n is the number of peaks, and xi is the arc-length position of the ith peak and yi is the peak height. The order and position of characteristic curves and the corresponding peaks as they appear in the CSS image space depends on the starting point for the curvature function described above. The peak co-ordinates are re ordered, as described below. Let us assume that the contour from which parameter are extracted has n peaks, with the peak parameters forming a set {(x1,y1), (x2,y2),..., (xn,yn)} as shown in Fig. 2. The peaks are then ordered based on height (that is the y coordinate value) in either increasing or decreasing order{(x1y1, (x2,y2)y- (xn.Yn)} (subscripts denote the peak order number after ordering). Let us assume that peaks are ordered in decreasing order, so that the highest peak is the first one (x1Y1), and each of the subsequent peaks is lower than or equal its predecessor in the set (Fig. 3). These re-ordered peak co-ordinates form the basis of the descriptor for the object outline. Additional parameters of the shape, such as circularity C, eccentricity E and compactness D, some extracted from the so called "prototype contour shape" can also be computed and stored to be used in the matching process as described in Patent no. GB 2352076, the contents of which are incorporated herein by reference. Next, coarse quantisation of the peak heights is performed. The range over which quantisation is performed is different for each peak, and depends on the values of the higher peaks (e.g.heights of the peaks which are predecessors in the ordered set). Referring to Fig. 3, the first peak is quantised over a range 11= [0,Y max], where Ymax is the maximum value for the peak that is expected on a certain class of shapes. Each of the remaining peaks is quantised to the range which depends on the value of one or several of the previous peaks. For example, peak y2 is quantised over the interval 12= [0,y1], (Fig. 3) peak y3 over the interval [0,y2] etc. In this embodiment, the first peak is quantised over the interval [0,1024] using 7 bits and the remaining peaks are quantised to 3 bits over the appropriate respective range, as discussed above. Supposing the height of the first peak is 893, say, then y2 is quantised over the range [0, 893], using 3 bits, and so on. Accordingly, for peaks y2 to y5, the quantisation interval is reduced, giving greater accuracy despite using fewer bits. The x position of each peak are quantised to 6 bits uniformly distributed on (0, 1) interval. The x value may be the original x value, as shown for example, in Fig. 2, or after shifting along the x axis by an amount such that the x value for the highest peak is at 0. Let us examine the gain from the presented invention. In the conventional solution each peak requires two floating point numbers, 4 bytes each. Thus, for a typical shape with 9 peaks, the storage requirement is 924=72 Bytes (576 bits). After application of the proposed embodiment, the first peak requires 7 bits, assuming that the x value is treated as zero, and each consecutive peak 6+3 bits, thus 79 bits in total. Instead of a range [0, y1, a range [0, R(y1)) could be used, where R(y1) is the reconstruction of the value yi after inverse quantisation. An alternative embodiment which will have a similar effect is to divide the height of each of the peaks {y2, y3,...,yn} (except the highest one) by the value of the respective previous peak. After this operation, the range of all yi is from the set (0, 1]. This allows the use of much coarser quantisation for all yi. In either example, good results can be obtained by using 7 or 6 bit quantisation for the highest peak and 4 or 3 bit quantisation for all the remaining peaks. Other numbers of bits can be used. The above operations can also be performed after the co-ordinate values have been subjected to a binormal filtering and a non-linear transformation, as described in Patent no. 2352075, the contents of which are incorporated herein by reference. The x co-ordinates can be coded along the lines described above instead of or as well as the y values. The resulting values can be stored for use, for example, in a suitable matching procedure, such as described in Patent Nos. GB23 52075, GB2351826 and GB2352076, with appropriate modifications, for example, by performing inverse quantisation on the stored descriptors before performing matching. WE CLAIM: 1. A method of searching for an object in an image by processing signals corresponding to images, the method comprising inputting a query object, deriving a representation of the query object, comparing the query representation with a plurality of representation of objects in images, and selecting and displaying those objects in images for which the representations indicate a degree of similarity to the query, characterized in that the representation of objects in images are quantised co-ordinate values of peaks of a curvature scale space (CSS) representation of the shape of the object, wherein the peaks of the CSS representation are ordered in decreasing order of the peak height component values and the quantisation range for a peak height component value is based on the value of the preceding peak height value. 2. The method as claimed in claim 1 wherein the query is compared with stored representations of objects in images and/or representations of objects in stored images. 3. The method as claimed in claim 1 or 2 wherein the representation of the query object and/or the representation of an object in an image to be compared is derived by a method comprising deriving a CSS representation of the shape of the object, quantising the co-ordinate values of the peaks of the CSS representation to derive a coded representation of the shape, ordering the peaks of the CSS representation in decreasing order of the peak height component values, wherein the quantisation range for a peak height component value is based on the value of the preceding peak height component value. 4. The method as claimed in any one of the preceding claim wherein the number of bits allocated to the quantised of a peak height component value is less than the number of bits allocated to the quantised representation of a preceding peak height component value. 5. A control device (2) programmed to perform the method as claimed in any one of claims 1 to 4. 6. An apparatus comprising means for carrying out the steps of the method as claimed in any one of claims 1 to 4. 7. The apparatus as claimed in claim 6 comprising a control device (2) as claimed in claim 5 and storage means (8, 10) for storing images and/or representations of images. 8. A computer program for implementing a method of any one of claims 1 to 4, or a computer-readable storage medium storing such a computer program, or a computer system programmed to operate according to any one of claims 1 to 4. Dated this 26 day of December 2006

Full Text

The present invention relates to the representation of an object appearing, for example, in a still or video image, such as an image stored in a multimedia database, and particularly to the coding of such a representation.
In applications such as image or video libraries, it is desirable to have an efficient representation and storage of the outline or shape of objects or parts of objects appearing in still or video images. A known technique for shape-based indexing and retrieval uses Curvature Scale Space (CSS) representation. Details of the CSS representation can be found in the papers "Robust and Efficient Shape Indexing through Curvature Scale Space" Proc.
British Machine Vision conference, pp 53-62, Edinburgh, UK, 1996 and
"Indexing an Image Database by Shape Content using Curvature Scale
Space"
Proc. IEE Colloquium on Intelligent Databases, London 1996, both by F.
Mokhtarian, S. Abbasi and J. Kittler, the contents of which are incorporated
herein by reference.
The CSS representation uses a curvature function for the outline of the object, starting from an arbitrary point on the outline. The curvature function is studied as the outline shape is evolved by a series of deformations which smooth the shape. More specifically, the zero crossings of the derivative of the curvature function convolved with a family of Gaussian filters are computed. The zero crossings are plotted on a graph, known as the Curvature Scale Space, where the x-axis is the normalised arc-length of the curve and the y-axis is the evolution parameter, specifically, the paramete of the filter applied. The plots on the graph form loops characteristic of the outline. Each convex or concave part of the object

outline corresponds to a loop in the CSS image. The co-ordinates of the peaks of the most prominent loops in the CSS image are used as a representation of the outline.
To search for objects in images stored in a database matching the shape of an input object, the CSS representation of an input shape is calculated. The similarity between an input shape and stored shapes is determined by comparing the position and height of the peaks in the respective CSS images using a matching algorithm.
The number of bits required to express the properties of the contour shape in a descriptor should be as small as possible to facilitate efficient storage and transmission.
The invention can offer a very compact representation (in terms of number of bits used for storage) without any significant deterioration in retrieval performance.
Embodiments of the present invention will be described with reference to the accompanying drawings of which :
Fig. 1 is a block diagram of a video database system ;
Fig. 2 is a CSS representation of an outline ;
Fig. 3 is a diagram illustrating coding of co-ordinate values of the CSS representation.
Fig. 1 shows a computerised video database system according to an embodiment of the invention. The system includes a control unit 2 in the form of a computer, a display unit 4 in the form of a monitor, a pointing device 6 in the form of a mouse, an image database 8 including stored

In the above, represents convolution and subscripts represent derivatives.
The number of curvature zero crossings changes as a changes, and when a is sufficiently high is a convex curve with no zero crossings.
The zero crossing points (u, σ) are plotted on a graph, known as the CSS image space. This results in a plurality of curves characteristic of the original outline. The peaks of the characteristic curves are identified and the corresponding co-ordinates are extracted and stored. In general terms, this gives a set of n co-ordinate pairs [(xl, yl), (x2, y2),.... (xn, yn)], where n is the number of peaks, and xi is the arc-length position of the ith peak and yi is the peak height.
The order and position of characteristic curves and the corresponding peaks as they appear in the CSS image space depends on the starting point for the curvature function described above. The peak co-ordinates are re ordered, as described below.
Let us assume that the contour from which parameter are extracted has n peaks, with the peak parameters forming a set {(x1,y1), (x2,y2),..., (xn,yn)} as shown in Fig. 2. The peaks are then ordered based on height (that is the y coordinate value) in either increasing or decreasing order{(x1y1, (x2,y2)y- (xn.Yn)} (subscripts denote the peak order number after ordering). Let us assume that peaks are ordered in decreasing order, so that the highest peak is the first one (x1Y1), and each of the subsequent peaks is lower than or equal its predecessor in the set (Fig. 3).

These re-ordered peak co-ordinates form the basis of the descriptor for the object outline. Additional parameters of the shape, such as circularity C, eccentricity E and compactness D, some extracted from the so called "prototype contour shape" can also be computed and stored to be used in the matching process as described in Patent no. GB 2352076, the contents of which are incorporated herein by reference.
Next, coarse quantisation of the peak heights is performed. The range over which quantisation is performed is different for each peak, and depends on the values of the higher peaks (e.g.heights of the peaks which are predecessors in the ordered set).
Referring to Fig. 3, the first peak is quantised over a range 11= [0,Y max], where Ymax is the maximum value for the peak that is expected on a certain class of shapes. Each of the remaining peaks is quantised to the range which depends on the value of one or several of the previous peaks. For example, peak y2 is quantised over the interval 12= [0,y1], (Fig. 3) peak y3 over the interval [0,y2] etc.
In this embodiment, the first peak is quantised over the interval [0,1024] using 7 bits and the remaining peaks are quantised to 3 bits over the appropriate respective range, as discussed above. Supposing the height of the first peak is 893, say, then y2 is quantised over the range [0, 893], using 3 bits, and so on. Accordingly, for peaks y2 to y5, the quantisation interval is reduced, giving greater accuracy despite using fewer bits. The x position of each peak are quantised to 6 bits uniformly distributed on (0, 1) interval. The x value may be the original x value, as shown for example, in Fig. 2, or after shifting along the x axis by an amount such that the x value for the highest peak is at 0.

Let us examine the gain from the presented invention. In the conventional solution each peak requires two floating point numbers, 4 bytes each. Thus, for a typical shape with 9 peaks, the storage requirement is 9*2*4=72 Bytes (576 bits). After application of the proposed embodiment, the first peak requires 7 bits, assuming that the x value is treated as zero, and each consecutive peak 6+3 bits, thus 79 bits in total.
Instead of a range [0, y1, a range [0, R(y1)) could be used, where R(y1) is the reconstruction of the value yi after inverse quantisation.
An alternative embodiment which will have a similar effect is to divide the height of each of the peaks {y2, y3,...,yn} (except the highest one) by the value of the respective previous peak. After this operation, the range of all yi is from the set (0, 1]. This allows the use of much coarser quantisation for all yi.
In either example, good results can be obtained by using 7 or 6 bit quantisation for the highest peak and 4 or 3 bit quantisation for all the remaining peaks. Other numbers of bits can be used.
The above operations can also be performed after the co-ordinate values have been subjected to a binormal filtering and a non-linear transformation, as described in Patent no. 2352075, the contents of which are incorporated herein by reference. The x co-ordinates can be coded along the lines described above instead of or as well as the y values.
The resulting values can be stored for use, for example, in a suitable matching procedure, such as described in Patent Nos. GB23 52075, GB2351826 and GB2352076, with appropriate modifications, for example, by performing inverse quantisation on the stored descriptors before performing matching.
WE CLAIM:
1. A method of searching for an object in an image by processing signals corresponding to images, the method comprising inputting a query object, deriving a representation of the query object, comparing the query representation with a plurality of representation of objects in images, and selecting and displaying those objects in images for which the representations indicate a degree of similarity to the query, characterized in that the representation of objects in images are quantised co-ordinate values of peaks of a curvature scale space (CSS) representation of the shape of the object, wherein the peaks of the CSS representation are ordered in decreasing order of the peak height component values and the quantisation range for a peak height component value is based on the value of the preceding peak height value.
2. The method as claimed in claim 1 wherein the query is compared with stored representations of objects in images and/or representations of objects in stored images.
3. The method as claimed in claim 1 or 2 wherein the representation of the query object and/or the representation of an object in an image to be compared is derived by a method comprising deriving a CSS representation of the shape of the object, quantising the co-ordinate values of the peaks of the CSS representation to derive a coded representation of the shape, ordering the peaks of the CSS representation in decreasing order of the peak height component values, wherein the quantisation range for a peak height component value is based on the value of the preceding peak height component value.

4. The method as claimed in any one of the preceding claim wherein the number of bits allocated to the quantised of a peak height component value is less than the number of bits allocated to the quantised representation of a preceding peak height component value.
5. A control device (2) programmed to perform the method as claimed in any one of claims 1 to 4.
6. An apparatus comprising means for carrying out the steps of the method as claimed in any one of claims 1 to 4.
7. The apparatus as claimed in claim 6 comprising a control device (2) as claimed in claim 5 and storage means (8, 10) for storing images and/or representations of images.
8. A computer program for implementing a method of any one of claims 1 to 4, or a computer-readable storage medium storing such a computer program, or a computer system programmed to operate according to any one of claims 1 to 4.
Dated this 26 day of December 2006

Documents:

4741-CHENP-2006 AMENDED PAGES OF SPECIFICATION 29-09-2011.pdf

4741-CHENP-2006 AMENDED CLAIMS 29-12-2011.pdf

4741-CHENP-2006 AMENDED CLAIMS 29-09-2011.pdf

4741-CHENP-2006 CORRESPONDENCE OTHERS 29-11-2011.pdf

4741-CHENP-2006 EXAMINATION REPORT REPLY RECEIVED 29-09-2011.pdf

4741-CHENP-2006 FORM-1 29-09-2011.pdf

4741-CHENP-2006 FORM-3 29-09-2011.pdf

4741-CHENP-2006 OTHER PATENT DOCUMENT 29-09-2011.pdf

4741-CHENP-2006 POWER OF ATTORNEY 29-11-2011.pdf

4741-CHENP-2006 CORRESPONDENCE OTHERS 29-12-2011.pdf

4741-CHENP-2006 CORRESPONDENCE OTHERS 28-03-2011.pdf

4741-CHENP-2006 CORRESPONDENCE PO.pdf

4741-CHENP-2006 FORM-18.pdf

4741-CHENP-2006 FORM-3 29-11-2011.pdf

4741-CHENP-2006 FORM-5 29-11-2011.pdf

4741-CHENP-2006 FORM-6 07-05-2007.pdf

4741-chenp-2006 power of attorney 07-05-2007.pdf

4741-CHENP-2006 AMENDED CLAIMS 29-11-2011.pdf

4741-chenp-2006-abstract.pdf

4741-chenp-2006-abstractimage.jpg

4741-chenp-2006-claims.pdf

4741-chenp-2006-correspondnece-others.pdf

4741-chenp-2006-description(complete).pdf

4741-chenp-2006-drawings.pdf

4741-chenp-2006-form 1.pdf

4741-chenp-2006-form 3.pdf

4741-chenp-2006-form 5.pdf

« Previous Patent

Next Patent »

Patent Number

250494

Indian Patent Application Number

4741/CHENP/2006

PG Journal Number

02/2012

Publication Date

13-Jan-2012

Grant Date

06-Jan-2012

Date of Filing

26-Dec-2006

Name of Patentee

MITSUBISHI DENKI KABUSHIKI KAISHA

Applicant Address

20 FREDRICK SAGER ROAD THE SURREY RESEARCH PARK GUILDFORD SURREY GU2 5YD UNITED KINGDOM

Inventors:

#	Inventor's Name	Inventor's Address
1	BOBER, MIROSLAW	21 WYKEHAM ROAD MERROW GUILDFORD SURREY GUI 2SE GREAT BRITAIN

PCT International Classification Number

G06T 9/20

PCT International Application Number

PCT/GB2001/000835

PCT International Filing date

2001-02-27

PCT Conventions:

#	PCT Application Number	Date of Convention	Priority Country
1	0004859.5	2000-02-29	U.K.