Fully parallel, low complexity approach to solving computer vision problems

Patent metadata

Field	Value
Publication number	US-2018300588-A1
Application number	US-201815925141-A
Country	US
Kind code	A1
Filing date	Mar 19, 2018
Priority date	Mar 17, 2017
Publication date	Oct 18, 2018
Grant date	—

Abstract

Values of pixels in an image are mapped to a binary space using a first function that preserves characteristics of values of the pixels. Labels are iteratively assigned to the pixels in the image in parallel based on a second function. The label assigned to each pixel is determined based on values of a set of nearest-neighbor pixels. The first function is trained to map values of pixels in a set of training images to the binary space and the second function is trained to assign labels to the pixels in the set of training images. Considering only the nearest neighbors in the inference scheme results in a computational complexity that is independent of the size of the solution space and produces sufficient approximations of the true distribution when the solution for each pixel is most likely found in a small subset of the set of potential solutions.

First claim

What is claimed is:

1 . A method comprising:
mapping values of pixels in an image to a binary space using a first function that preserves characteristics of values of the pixels; iteratively assigning labels to the pixels in the image in parallel based on a second function, wherein the label assigned to each pixel is determined based on values of a set of nearest-neighbor pixels.

2 . The method of claim 1 , further comprising:
training the first function to map values of pixels in a set of training images to the binary space; and training the second function to assign labels to the pixels in the set of training images.

3 . The method of claim 2 , wherein training the first and second functions comprises reconstructing estimated values of pixels in the set of training images from the values of the pixels in the binary space and iteratively updating the first and second functions based on a comparison of actual values of the pixels in the set of training images and the estimated values.

4 . The method of claim 3 , wherein training the first and second functions comprises learning a set of hyperplanes and a task function that minimize a loss function subject to an anti-sparsity constraint.

5 . The method of claim 4 , wherein training the first and second functions comprises training first and second regularizer functions using the set of training images, wherein the first and second regularizer functions encourage corresponding structures for the set of hyperplanes and the task function.

6 . The method of claim 5 , wherein learning the set of hyperplanes comprises iteratively updating values of the set of hyperplanes based on the first regularizer, wherein the first regularizer is chosen to induce sparse solutions in the set of hyperplanes.

7 . The method of claim 6 , wherein learning the task function comprises iteratively updating values of the task function using a gradient descent technique.

8 . The method of claim 1 , wherein iteratively assigning the labels to the pixels in parallel comprises estimating distributions of labels of the pixels as independent marginal functions.

9 . The method of claim 8 , wherein estimating the distributions of the labels of the pixels as independent marginal functions comprises estimating the distributions of the labels of the pixels as Dirac δ functions.

10 . The method of claim 9 , wherein iteratively assigning the labels to the pixels in parallel comprises assigning, during an iteration, the labels of the pixels to a maximal value of the marginal functions of the nearest neighbor pixels.

11 . The method of claim 8 , wherein iteratively assigning the labels to the pixels in parallel comprises iteratively assigning the labels to the pixels in parallel using a coordinate ascent procedure until convergence.

12 . An apparatus comprising:
a processor configured to map values of pixels in an image to a binary space using a first function that preserves characteristics of values of the pixels and iteratively assign labels to the pixels in the image in parallel based on a second function, wherein the label assigned to each pixel is determined based on values of a set of nearest-neighbor pixels; and a memory to store the labels of the pixels.

13 . The apparatus of claim 12 , wherein the first function is trained to map values of pixels in a set of training images to the binary space and the second function is trained to assign labels to the pixels in the set of training images.

14 . The apparatus of claim 13 , wherein training the first and second functions comprises reconstructing estimated values of pixels in the set of training images from the values of the pixels in the binary space and iteratively updating the first and second functions based on a comparison of actual values of the pixels in the set of training images and the estimated values.

15 . The apparatus of claim 14 , wherein training the first and second functions comprises learning a set of hyperplanes and a task function that minimize a loss function subject to an anti-sparsity constraint.

16 . The apparatus of claim 15 , wherein training the first and second functions comprises training first and second regularizer functions using the set of training images, wherein the first and second regularizer functions encourage corresponding structures for the set of hyperplanes and the task function.

17 . The apparatus of claim 16 , wherein learning the set of hyperplanes comprises iteratively updating values of the set of hyperplanes based on the first regularizer, wherein the first regularizer is chosen to induce sparse solutions in the set of hyperplanes.

18 . The apparatus of claim 17 , wherein learning the task function comprises iteratively updating values of the task function using a gradient descent technique.

19 . The apparatus of claim 12 , wherein the processor is configured to estimate distributions of labels of the pixels as independent marginal functions.

20 . The apparatus of claim 19 , wherein the processor is configured to estimate the distributions of the labels of the pixels as Dirac δ functions.

21 . The apparatus of claim 20 , wherein the processor is configured to assign, during an iteration, the labels of the pixels to a maximal value of the marginal functions of the nearest neighbor pixels.

22 . The apparatus of claim 19 , wherein the processor is configured to iteratively assign the labels to the pixels in parallel using a coordinate ascent procedure until convergence.

23 . A non-transitory computer readable medium embodying a set of executable instructions, the set of executable instructions to manipulate at least one processor to:
map values of pixels in an image to a binary space using a first function that preserves characteristics of values of the pixels; iteratively assign labels to the pixels in the image in parallel based on a second function, wherein the label assigned to each pixel is determined based on values of a set of nearest-neighbor pixels.

24 . The non-transitory computer readable medium of claim 23 , wherein the set of executable instructions is to manipulate the at least one processor to:
train the first function to map values of pixels in a set of training images to the binary space; and train the second function to assign labels to the pixels in the set of training images.

25 . The non-transitory computer readable medium of claim 24 , wherein the set of executable instructions is to manipulate the at least one processor to reconstruct estimated values of pixels in the set of training images from the values of the pixels in the binary space and iteratively updating the first and second functions based on a comparison of actual values of the pixels in the set of training images and the estimated values.

26 . The non-transitory computer readable medium of claim 25 , wherein the set of executable instructions is to manipulate the at least one processor to learn a set of hyperplanes and a task function that minimize a loss function subject to an anti-sparsity constraint.

27 . The non-transitory computer readable medium of claim 26 , wherein the set of executable instructions is to manipulate the at least one processor to train first and second regularizer functions using the set of training images, wherein the first and second regularizer functions encourage corresponding structures for the set of

Assignees

• Google Llc

Inventors

• Fanello Sean Ryan
• Valentin Julien Pascal Christophe
• Kowdle Adarsh Prakash Murthy
• Rhemann Christoph
• Tankovich Vladimir
• Davidson Philip L
• Izadi Shahram

Classifications

• G06F18/24147

  Distances to closest patterns, e.g. nearest neighbour classification · CPC title

• G06K9/6202

  Physics · mapped topic

• G06K9/6256 Primary

  Physics · mapped topic

• G06K9/6276

  Physics · mapped topic

• G06F18/10 Primary

  Pre-processing; Data cleansing · CPC title