# US 10,321,112 B2 · Stereo matching system and method of operating thereof

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

- Number: US 10,321,112 B2
- Document ID: US10321112B2
- Status: Granted
- Kind: B2
- Application number: 15/485,392
- Filed: 2017-04-12
- Published: 2018-01-18
- Granted: 2019-06-11
- Earliest claimed: 2016-07-18
- Assignees: Samsung Electronics Co., Ltd.
- Applicants: Samsung Electronics Co., Ltd.
- Inventors: Yonathan Aflalo; Ariel Orfaig; Sagi Tzur; Ayal Keisar; Nathan Henri Levy
- Web page: https://patentgrep.com/patent/US10321112B2

## CPC

- H04N 13/128: Adjusting depth or disparity
- G06T 7/557: from light fields, e.g. from plenoptic cameras
- G06T 7/593: from stereo images
- H04N 13/133: Equalising the characteristics of different image components, e.g. their average brightness or colour balance
- H04N 13/239: using two two-dimensional [2D] image sensors having a relative position equal to or related to the interocular distance (H04N13/243 takes precedence)
- H04N 13/271: wherein the generated image signals comprise depth maps or disparity maps
- G06T 2207/20016: Hierarchical, coarse-to-fine, multiscale or multiresolution image processing; Pyramid transform
- G06T 2207/20072: Graph-based image processing
- G06T 2207/20076: Probabilistic image processing
- H04N 2013/0081: {Depth or disparity estimation from stereoscopic image signals}
- H04N: PICTORIAL COMMUNICATION, e.g. TELEVISION
- G06T: IMAGE DATA PROCESSING OR GENERATION, IN GENERAL

## Abstract

A first image and a second image of an object taken with different viewing directions are received. The first image and the second image are downscaled in a ratio of a downscale factor DF to generate a first downscaled image and a second downscaled image, respectively. An edge map is generated by detecting an edge pixel from the first downscaled image. An initial cost volume matrix is generated from the first downscaled image and the second downscaled image according to the edge map. An initial disparity estimate is generated from the initial cost volume matrix. The initial disparity estimate is refined using the initial disparity estimate to generate a final disparity set. A depth map is generated from the first image and the second image using the final disparity set.

## Claims

### Claim 1

A method of operating a stereo matching system, the method comprising:
receiving a first image from a first camera of a stereo camera, and a second image from a second camera of a stereo camera, wherein the first and second images are of an object taken with different viewing directions;
downscaling the first image and the second image by a smoothing filter in a ratio of a downscale factor DF to generate a first downscaled image and a second downscaled image, respectively;
generating an edge map by detecting an edge pixel from the first downscaled image;
generating an initial cost volume matrix from the first downscaled image and the second downscaled image according to the edge map;
generating an initial disparity estimate from the initial cost volume matrix;
refining the initial disparity estimate using the initial disparity estimate to generate a final disparity set; and
generating a depth map from the first image and the second image using the final disparity set,
wherein the first image includes a plurality of W column pixels and a plurality of H row pixels,
wherein the first downscaled image includes a plurality of W/DF column pixels, and
wherein the first downscaled image is formed of every DFth column pixels of the pluralty of W column pixels so that a resolution of the first downscaled image is reduced by 1/DF times a resolution of the first image in a row direction.

### Claim 2 (depends on 1)

The method of claim 1,
wherein the downscale factor DF is two (2).

### Claim 3 (depends on 1)

The method of claim 1, further comprising:
wherein the generating of the initial disparity estimate of the edge pixel includes:
generating an initial disparity set including a plurality of initial disparity candidates, wherein a maximum initial disparity candidate of the initial disparity set is equal to dmax/DF, wherein dmax is a maximum disparity;
generating an initial cost volume matrix of H×(W/DF)×(dmax/DF) storing a cost value of each pixel of the first downscaled image; and
searching the initial disparity estimate from the initial cost volume matrix.

### Claim 4 (depends on 3)

The method of claim 3,
wherein the searching of the initial disparity estimate from the initial cost volume matrix includes:
performing an dynamic programming to find the initial disparity estimate,
wherein the dynamic programming is performed in a unit of two scanlines adjacent to each other.

### Claim 5 (depends on 4)

The method of claim 4,
wherein the dynamic programming includes a vertical smoothness between the two scanlines.

### Claim 6 (depends on 4)

The method of claim 4,
wherein the dynamic programming is performed in a first direction on an even-numbered row pixel, and
wherein the dynamic programming is performed in a second direction opposite to the first direction on an odd-numbered row pixel.

### Claim 7 (depends on 1)

The method of claim 1,
wherein the generating of the initial cost volume matrix further includes:
generating an aggregated cost volume matrix from the initial cost volume matrix.

### Claim 8 (depends on 1)

The method of claim 1,
wherein the generating of the initial cost volume matrix includes:
if a pixel is determined as an edge pixel, computing a cost for the edge pixel over an initial disparity set and storing the cost to the initial cost volume matrix; and
if a pixel is determined as a non-edge pixel, assigning a predetermined maximum cost to the initial cost volume matrix without computing a cost.

### Claim 9 (depends on 1)

The method of claim 1,
wherein the refining of the initial disparity estimate using the first image and the second image includes:
generating a final disparity set using the initial disparity estimate;
computing a final matching cost volume using the final disparity set from the first image and the second image; and
determining a final disparity candidate of the final disparity set from a minimum final cost.

### Claim 10 (depends on 9)

The method of claim 9,
wherein the final disparity set includes a plurality of final disparity candidates, and
wherein a number of the plurality of final disparity candidates is 2*DF+1.

### Claim 11 (depends on 1)

The method of claim 1,
wherein the receiving of the first image and the second image further comprising:
rectifying a left image and a right image; and
compensating an intensity of the left image and an intensity of the right image to generate the first image and the second image.

### Claim 12 (depends on 11)

The method of claim 11,
wherein the generating of the edge map includes:
if the edge pixel is determined, assigning a value indicating to a non-edge pixel to pixels adjacent to the edge pixel within a predetermined range step.

### Claim 13

A method of generating a three-dimensional image, the method comprising:
receiving a first image from a first camera of a stereo camera, and a second image from second camera of a stereo camera, wherein the first and second images are of an object taken with different viewing directions, and wherein each of the first image and the second image includes a plurality of W column pixels and a plurality of H ow pixels;
downscaling the first image and the second image by a smoothing filter in a ratio of a downscale factor DF to generate a first downscaled image arid a second downscaled image, respectively, so that each of the first image and the second image includes a plurality of W/DF column pixels and the plurality H row pixels; and
generating an initial cost volume matrix of the first downscaled image and the second downscaled image with an initial disparity set by calculating a cost for an edge pixel of the first downscaled image,
wherein the initial cost volume matrix has a dimension of H×(W/DF)×dmax, and
wherein dmax is a maximum initial disparity of the initial disparity set, and
performing a dynamic program on the initial cost volume matrix to search an initial disparity estimate.

### Claim 14 (depends on 13)

The method of claim 13, further comprising:
refining the initial disparity estimate to generate a final disparity set;
calculating a final matching cost volume matrix from the first image and the second image using the final disparity set; and
searching a minimum final cost from the final matching cost volume matrix to generating a depth map.

### Claim 15 (depends on 13)

The method of claim 13,
wherein the generating of the initial cost volume matrix of the first downscaled image and the second downscaled image further includes:
assigning a predetermined maximum cost to a non-edge pixel without computing a cost for the non-edge pixel.

### Claim 16 (depends on 15)

The method of claim 15, further comprising:
detecting the edge pixel and the non-edge pixel from the downscaled first image.

### Claim 17

A stereo matching system comprising:
a smoothing filter receiving a first image and a second image and generating a first downscaled image and a second downscaled image in a ratio of a downscale factor DF;
an edge detector receiving the first downscaled image and generating an edge map;
a cost volume matrix generator receiving the first downscaled image and the second downscaled image and generating an initial cost volume matrix, wherein the cost volume matrix generator computes a cost for an edge pixel and assigns a predetermined maximum cost value tor a non-edge pixel;
a disparity estimator receiving the initial cost volume matrix and generating an initial disparity estimate; and
a disparity refiner receiving the initial disparity estimate and generating a plurality of final disparity candidates, wherein a number of the plurality of final disparity candidates is 2*DF+1.

### Claim 18 (depends on 17)

The stereo matching system of claim 17, further comprising:
a rectifier receiving a left image and a right image; and
an illumination correction circuit receiving the left image and the right image and generating the first image and the second image to compensate differences in intensities between the left image and the right image.