Methods and apparatus to enable parallel processing when solving linear equations in a computer vision processing system

One or more non-transitory machine-readable storage media comprising machine-readable instructions that, when executed, cause one or more processors to at least:

• identify a set of equations to be solved, respective ones of the set of equations corresponding to respective pixels of an input image;
• divide the set of equations into partitions, the partitions containing mutually independent subsets of the equations, wherein to divide the set of equations into partitions, the instructions, when executed, cause the one or more processors to:
• populate a matrix with zero values;
• define a mask based on a relationship between the pixels;
• iteratively place the mask on the matrix of zero values with the mask centered on respective ones of the zero values in the matrix during respective iterations;
• during the respective iterations, select respective non-zero values corresponding to the respective ones of the zero values, based on the coverage of the matrix by the mask;
• and
• during the respective iterations, replace, in the matrix, the respective zero values with the respective, selected non-zero values;
• and
• based on the partitions, place the subsets of the set of equations into groups to be solved in parallel by a set of successive over relaxation processors, results generated by the successive over-relaxation processors forming an enhanced version of the input image.

An apparatus to prepare equations for a successive over relaxation processor, the apparatus comprising:

• means for identifying the equations, respective ones of the set of equations corresponding to respective pixels of an input image;
• means for dividing the equations into partitions, the partitions containing mutually independent subsets of the equations, the means for dividing to:
• form a matrix of elements containing zeros;
• successively mask the elements of the matrix over a set of iterations;
• successively select non-zero values for respective ones of the elements of the matrix based on values of the subsets of the elements masked by the mask;
• and
• replace the zero values of the matrix with the non-zero values selected by the value selector;
• and
• means for collecting the subsets of the equations into groups to be solved in parallel by the successive over relaxation processor.

A method to parallelize solving a set of linear equations associated with first image data, the method including:

• identifying, by executing one or more instructions with one or more processors, equations to be solved, respective ones of the equations corresponding to respective pixels of the first image data, the equations arranged in a first matrix;
• determining, by executing one or more instructions with the one or more processors, subsets of the equations that are mutually independent of each other based on a second matrix, the determining of the subsets of the equations including:
• initializing elements of the second matrix to zero;
• successively masking the elements of the second matrix over a set of iterations;
• successively selecting, during respective ones of the iterations, non-zero values for respective ones of the elements of the second matrix based on values of subsets of the elements masked by the mask;
• and
• during the respective ones of the iterations, replacing, in the second matrix, respective zero values with the corresponding, selected non-zero values;
• placing, by executing one or more instructions with the one or more processors, the subsets of the equations into groups by rearranging the positions of the equations in the first matrix based on the second matrix so that equations included in a same subset are near each other in the first matrix;
• supplying, by executing one or more instructions with the one or more processors, the groups of equations to a plurality of successive over relaxation processors;
• and
• solving the groups of equations in parallel with the successive over relaxation processors to determine second image data.

A method to parallelize solving a set of linear equations associated with first image data, the method including:

• identifying, by executing one or more instructions with one or more processors, equations to be solved, respective ones of the equations corresponding to respective pixels of the first image data;
• determining, by executing one or more instructions with the one or more processors, subsets of the equations that are mutually independent of each other, the determining of the subsets including:
• initializing a matrix of zero values;
• defining a mask based on a connectivity of the pixels;
• placing the mask on the matrix of zero values with the mask centered on respective ones of the zero values in the matrix during a set of iterations;
• during respective ones of the iterations, selecting respective non-zero values corresponding to the respective ones of the zero values, based on the coverage of the matrix by the mask;
• and
• during respective ones of the iterations, replacing, in the matrix, the respective zero values with the respective, selected non-zero values;
• and
• supplying, by executing one or more instructions with the one or more processors, the subsets of equations to a plurality of successive over relaxation processors;
• and
• solving the subsets of equations in parallel with the successive over relaxation processors to determine second image data.