# US 2003/0068082 A1 · Systems and methods for automatic scale selection in real-time imaging

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

- Number: US 2003/0068082 A1
- Document ID: US20030068082A1
- Status: Published application
- Kind: A1
- Application number: 10/147,092
- Filed: 2002-05-16
- Published: 2003-04-10
- Earliest claimed: 2001-05-16
- Assignees: Siemens Corporate Research, Inc.
- Inventors: Dorin Comaniciu; Visvanathan Ramesh
- Web page: https://patentgrep.com/patent/US20030068082A1

## CPC

- G06T 7/13: Edge detection
- G06F 18/2321: using statistics or function optimisation, e.g. modelling of probability density functions
- G06T 7/90: Determination of colour characteristics
- G06V 30/166: Normalisation of pattern dimensions
- G06T 2207/20016: Hierarchical, coarse-to-fine, multiscale or multiresolution image processing; Pyramid transform
- G06T 2207/20048: Transform domain processing
- G06V 30/10: Character recognition
- G06T: IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- G06V: IMAGE OR VIDEO RECOGNITION OR UNDERSTANDING

## Abstract

A system and method for automatic scale selection in real-time image and video processing and computer vision applications. In one aspect, a non-parametric variable bandwidth mean shift technique, which is based on adaptive estimation of a normalized density gradient, is used for detecting one or more modes in the underlying data and clustering the underlying data. In another aspect, a data-driven bandwidth (or scale) selection technique is provided for the variable bandwidth mean shift method, which estimates for each data point the covariance matrix that is the most stable across a plurality of scales. The methods can be used for detecting modes and clustering data for various types of data such as image data, video data speech data, handwriting data, etc.

## Claims

### Claim 1

A method for performing variable bandwidth selection, comprising the steps of:
receiving one of image data, video data, speech data and handwriting data, and extracting feature data points from the data;
selecting a plurality of analysis scales;
for each analysis scale, partitioning the data into one or more modes and determining a mean/covariance pair for each mode, wherein each data point is associated with a detected mode and a corresponding mean/covariance pair of the mode for each of the analysis scales;
for each data point, determining the most stable mean/covariance pair associated with the data point; and
for each data point, selecting for output the covariance of the most stable mean/covariance pair as a variable bandwidth for the data point, wherein the variable bandwidths are used for analyzing features of the data.

### Claim 2 (depends on 1)

The method of claim 1, wherein the step of partitioning the data comprises:
performing a fixed bandwidth mean shift process for each data point using each analysis scale; and
partitioning the data by grouping all mean shift vector trajectories that converge to a similar node.

### Claim 3 (depends on 2)

The method of claim 2, wherein the step of determining a mean/covariance pair of a given mode comprises fitting a normal surface to density of the given mode using mean shift trajectory points associated with the mode.

### Claim 4 (depends on 3)

The method of claim 3, wherein the step of fitting comprises using a least squares solution of a mean shift vector for determining the covariance.

### Claim 5 (depends on 4)

The method of claim 4, wherein the mean is determined as the location of the mode.

### Claim 6 (depends on 1)

The method of claim 1, wherein the step of determining the most stable mean/covariance pair for a given data point comprises the steps of:
defining a distribution for each mean/covariance pair; and
determining a dissimilarity between a given distribution and neighboring distributions across the scales.

### Claim 7 (depends on 6)

The method of claim 6, wherein the dissimilarity is measured using an extension of the Jensen-Shannon divergence.

### Claim 8 (depends on 1)

The method of claim 1, further comprising the step of using the selected variable bandwidths of the data points for detecting modes in the data set.

### Claim 9 (depends on 8)

The method of claim 8, wherein the modes are detected by applying the selected variable bandwidths in a variable bandwidth mean shift process.

### Claim 10

A method for detecting modes in a set of data, comprising the steps of:
receiving one of image data, video data, speech data and handwriting data, and extracting feature data points from the data;
determining a bandwidth for each data point; and
performing a variable bandwidth mean shift process for each data point using the bandwidth for the data point to detect modes in the data set.

### Claim 11 (depends on 10)

The method of claim 10, wherein the step of performing a variable bandwidth mean shift process comprises adaptively estimating a normalized density gradient of an underlying density to detect a mode in the data set.

### Claim 12 (depends on 10)

The method of claim 10, further comprising the step of clustering the data using the detected modes.

### Claim 13 (depends on 10)

The method of claim 10, wherein the step of performing a variable bandwidth mean shift process comprises iteratively computing a sequence of successive locations of a kernel until convergence at a point of zero gradient.

### Claim 14 (depends on 10)

The method of claim 10, wherein the step of performing a variable bandwidth mean shift process comprises associating a differently scaled kernel to each data point.

### Claim 15 (depends on 10)

The method of claim 10, wherein the step of determining a bandwidth for each data point comprises the steps of:
determining a fixed bandwidth parameter and pilot estimate;
determining a proportionality constant using the pilot estimate;
determining an adaptive bandwidth for each data point using the fixed bandwidth, the pilot estimate and the proportionality constant.

### Claim 16 (depends on 10)

The method of claim 10, wherein the step of determining a bandwidth for each data point comprises the steps of;
selecting a plurality of analysis scales;
for each analysis scale, partitioning the data set into one or more modes and determining a mean/covariance pair for each mode, wherein each data point is associated with a detected mode and a corresponding mean/covariance pair of the mode for each of the analysis scales;
for each data point, determining the most stable mean/covariance pair associated with the data point; and
for each data point, selecting for output the covariance of the most stable mean/covariance pair as a variable bandwidth for the data point.

### Claim 17

A method for segmenting video data, comprising the steps of:
receiving video data comprising pixels;
determining a color bandwidth by determining an adaptive bandwidth from a fixed bandwidth;
determining a local spatial bandwidth for each pixel using a data-driven variable bandwidth scale selection process;
clustering the video data using a variable bandwidth mean shift process in the joint spatial-color domain by applying the local spatial bandwidths and color bandwidths.

### Claim 18 (depends on 17)

The method of claim 17, wherein the step of clustering comprises identifying blobs as groups of pixels having similar points of convergence as determined by the variable bandwidth mean shift process.

### Claim 19 (depends on 17)

The method of claim 17, wherein the step of determining a color bandwidth for each pixel, comprises the steps of:
(i) generating a plurality of color components, the color components comprising orthogonal color features that represent RGB colors in the video data;
(ii) for each pixel, determining a fixed bandwidth for each color component;
(iii) for each pixel, determining an adaptive color bandwidth for each color component using the corresponding fixed bandwidth; and
(iv) repeating steps (ii) and (iii) for each spatial scale.

### Claim 20 (depends on 19)

The method of claim 19, wherein the step of determining a fixed bandwidth for each color component comprises using a one dimensional plug in rule independently for each color component.

### Claim 21 (depends on 19)

The method of claim 19, wherein the color component comprise orthogonal f features I1=(R+G+B)/3, I2=(R−B)/2 and I3−(2G−R−B)/4.

### Claim 22 (depends on 17)

The method of claim 17, wherein the step of determining a local spatial bandwidth for each pixel using a data-driven variable bandwidth scale selection process, comprises the steps of;
selecting a plurality of analysis scales;
for each analysis scale, partitioning the data set into one or more modes and determining a mean/covariance pair for each mode, wherein each data point is associated with a detected mode and a corresponding mean/covariance pair of the mode for each of the analysis scales;
for each pixel, determining the most stable mean/covariance pair associated with the data point; and
for each pixel, selecting for output the covariance of the most stable mean/covariance pair as a variable bandwidth for the data point.

### Claim 23

A method for segmenting video data, comprising the steps of:
receiving video data comprising a plurality of pixels;
determining an illumination invariant representation of RGB color data associated with each pixel;
determining a covariance matrix associated with the illumination invariant representation of each pixel;
determining modes in the video data using a variable bandwidth mean shift process, wherein local bandwidths for each pixel used in the variable bandwidth mean shift process are determined by the covariance associated with the pixel;
grouping pixels that converge to the same mode; and
determining image segments by identifying valleys surrounding the determined modes.

### Claim 24 (depends on 23)

The method of claim 23, wherein the step of determining an illumination invariant representation comprises transforming the RGB data to a normalized rg space, wherein r=R/(R+G+B) and g=G/(R+G+B).

### Claim 25 (depends on 24)

The method of claim 24, further comprising the step of determining a joint spatial-color domain comprising a 4-dimensional space.

### Claim 26 (depends on 23)

The method of claim 23, wherein the step of determining pixel covariance comprises the steps of:
determining sensor noises and
determining the covariance using the determined sensor noise.
