# US 10,762,594 B2 · Optimized memory access for reconstructing a three dimensional shape of an object by visual hull

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

- Number: US 10,762,594 B2
- Document ID: US10762594B2
- Status: Granted
- Kind: B2
- Application number: 16/202,899
- Filed: 2018-11-28
- Published: 2019-06-27
- Granted: 2020-09-01
- Earliest claimed: 2017-12-27
- Assignees: Fujitsu Limited
- Applicants: Fujitsu Limited
- Inventors: Tomonori Kubota; Yasuyuki Murata
- Web page: https://patentgrep.com/patent/US10762594B2

## CPC

- G06T 1/60: Memory management
- G06F 17/12: Simultaneous equations {, e.g. systems of linear equations}
- G06T 7/543: from line drawings
- G06T 7/564: from contours
- G06T 17/00: Three-dimensional [3D] modelling for computer graphics
- G06T 2207/10012: Stereo images
- G06T: IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

An apparatus reconstructs a three dimensional shape of an object from a plurality of images captured from different viewpoints by visual hull. The apparatus stores, into a first memory provided for the apparatus, silhouette image data of the object extracted from the plurality of images, and determines a group of a plurality of epipolar lines having inclinations within a predetermined range in images designated as reference views among the plurality of images, based on positions of neighboring silhouette pixels in an image designated as a target view among the plurality of images. The apparatus further determines, based on the determined group and a capacity of a cache provided for the apparatus, a cache area to be used in a search for a line segment indicating a range where the object exists in each of the plurality of epipolar lines in the group.

## Claims

### Claim 1

An information processing apparatus that reconstructs a three dimensional shape of an object from a plurality of images captured from different viewpoints by visual hull, comprising:
a cache configured to store part of silhouette image data of the object extracted from the images;
a processor coupled to the cache and configured to:
determine a group of a plurality of epipolar lines having inclinations within a predetermined range in images designated as reference views among the plurality of images, based on positions of neighboring silhouette pixels in an image designated as a target view among the plurality of images, and
determine, based on the determined group and a capacity of the cache, a cache area to be used in a search for a line segment indicating a range where the object exists in each of the plurality of epipolar lines in the group, wherein
the processor determines the cache area based on a position of an epipole at which the plurality of epipolar lines in the group intersect each other, a divergence among the plurality of epipolar lines in an area targeted for line segment searches, and a capacity of the cache.

### Claim 2 (depends on 1)

The information processing apparatus according to claim 1, further comprising a first memory configured to store the silhouette image data for the plurality of images, wherein
the processor reads a part of the silhouette image data corresponding to the cache area from the first memory and stores the read part in the cache.

### Claim 3 (depends on 2)

The information processing apparatus according to claim 2, wherein:
the processor is configured to include the cache; and
the processor is coupled to the first memory via a bus.

### Claim 4 (depends on 3)

The information processing apparatus according to claim 3, wherein:
the processor includes a second memory configured to store a part of the silhouette image data; and
the processor divides the cache area into groups based on at least one of a latency and a processing time for the second memory.

### Claim 5 (depends on 1)

The information processing apparatus according to claim 1, wherein:
the processor determines a rectangular area in each of the images as the cache area; and
when a width of the cache area is narrower than a predetermined width, the processor divides the cache area into a plurality of cache areas.

### Claim 6 (depends on 1)

The information processing apparatus according to claim 1, wherein:
the processor determines a rectangular area in the images as a cache area; and
when a width of the cache area is wider than a predetermined width, the processor divides the cache area in a width direction into a plurality of partial areas, and stores data of each of the partial areas in the cache stepwise.

### Claim 7 (depends on 1)

The information processing apparatus according to claim 1, wherein
the processor is further configured to search for the line segment indicating the range where the object exists in each of the plurality of epipolar lines in the group, based on the silhouette image data stored in the cache.

### Claim 8

An information processing method performed by an information processing apparatus that reconstructs a three dimensional shape of an object from a plurality of images captured from different viewpoints by visual hull, the information processing method comprising:
storing, into a first memory provided for the information processing apparatus, silhouette image data of the object extracted from the plurality of images;
determining a group of a plurality of epipolar lines having inclinations within a predetermined range in images designated as reference views among the plurality of images, based on positions of neighboring silhouette pixels in an image designated as a target view among the plurality of images; and
determining, based on the determined group and a capacity of a cache provided for information processing apparatus, a cache area to be used in a search for a line segment indicating a range where the object exists in each of the plurality of epipolar lines in the group, wherein
the cache area is determined based on a position of an epipole at which the plurality of epipolar lines in the group intersect each other, a divergence among the plurality of epipolar lines in an area targeted for line segment searches, and a capacity of the cache.

### Claim 9 (depends on 8)

The information processing method of claim 8, further comprising:
reading a part of the silhouette image data corresponding to the cache area from the first memory and storing the read part in the cache; and
searching for the line segment indicating the range where the object exists in each of the plurality of epipolar lines in the group, based on the silhouette image data stored in the cache.

### Claim 10

A non-transitory, recording medium having stored therein a program for causing a computer included in an information processing apparatus to execute a process, the information processing apparatus being configured to reconstruct a three dimensional shape of an object from a plurality of images captured from different viewpoints by visual hull, the process comprising:
storing, into a first memory provided for the information processing apparatus, silhouette image data of the object extracted from the plurality of images;
determining a group of a plurality of epipolar lines having inclinations within a predetermined range in images designated as reference views among the plurality of images, based on positions of neighboring silhouette pixels in an image designated as a target view among the plurality of images; and
determining, based on the determined group and a capacity of a cache provided for information processing apparatus, a cache area to be used in a search for a line segment indicating a range where the object exists in each of the plurality of epipolar lines in the group, wherein
the cache area is determined based on a position of an epipole at which the plurality of epipolar lines in the group intersect each other, a divergence among the plurality of epipolar lines in an area targeted for line segment searches, and a capacity of the cache.

### Claim 11 (depends on 10)

The non-transitory, recording medium of claim 10, the process further comprising:
reading a part of the silhouette image data corresponding to the cache area from the first memory and storing the read part in the cache; and
searching for the line segment indicating the range where the object exists in each of the plurality of epipolar lines in the group, based on the silhouette image data stored in the cache.

### Claim 12

An information processing apparatus that reconstructs a three dimensional shape of an object from a plurality of images captured from different viewpoints by visual hull, comprising:
a cache configured to store part of silhouette image data of the object extracted from the images;
a processor coupled to the cache and configured to:
determine a group of a plurality of epipolar lines having inclinations within a predetermined range in images designated as reference views among the plurality of images, based on positions of neighboring silhouette pixels in an image designated as a target view among the plurality of images, and
determine, based on the determined group and a capacity of the cache, a cache area to be used in a search for a line segment indicating a range where the object exists in each of the plurality of epipolar lines in the group, wherein to determine the cache area further comprises
determining, among the group of the plurality of epipolar lines, a first epipolar line with a maximum inclination (Imax) and a second epipolar line with a minimum inclination (IMin);
using the linear equation of y=a/b*x+c/b for the first epipolar line IMax and the second epipolar line Imin, setting the cache area to a width equal to the difference between x values of the IMax and the IMin and setting the number of lines within the cache area to the difference between y values of the IMax and the IMin.