Method of driving a display using non-negative matrix factorization to determine a pair of matrices for representing features of pixel data in an image data matrix and determining weights of said features such that a product of the matrices approximates the image data matrix

• US 7,953,682 B2
• Filed: 11/30/2005
• Issued: 05/31/2011
• Est. Priority Date: 12/23/2004
• Status: Expired due to Fees

• Current Assignee: Cambridge Display Technology Limited (Sumitomo Chemical Company Limited)
• Original Assignee: Cambridge Display Technology Limited (Sumitomo Chemical Company Limited)
• Inventors: Smith, Euan Christopher, Routley, Paul Richard, Foden, Clare Louise
• Primary Examiner(s): Sparks, Donald
• Assistant Examiner(s): Brown, Jr., Nathan H
• Application Number:
  US10/578,659
• Publication Number:
  US 20080291122A1
• Time in Patent Office: 2,008 Days
• Field of Search: 706/25
• US Class Current: 706/25
• CPC Class Codes: G06F 17/16 Matrix or vector computation , e.g. matrix-matrix or matrix-vector multiplication, matrix factorization matrix transposition G06F7/78
• CPC Class Codes: G09G 2310/0208 using active addressing
• CPC Class Codes: G09G 2320/043 Preventing or counteracting the effects of ageing
• CPC Class Codes: G09G 3/3216 using a passive matrix

Abstract

This invention generally relates to methods, apparatus and computer program code processing digital data using non-negative matrix factorisation.

A method of digitally processing data in a data array defining a target matrix (X) using non-negative matrix factorisation to determine a pair of matrices (F, G), a first matrix of said pair determining a set of features for representing said data, a second matrix of said pair determining weights of said features, such that a product of said first and second matrices approximates said target matrix, the method comprising: inputting said target matrix data (X); selecting a row of said one of said first and second matrices and a column of the other of said first and second matrices; determining a target contribution (R) of said selected row and column to said target matrix; determining, subject to a non-negativity constraint, updated values for said selected row and column from said target contribution; and repeating said selecting and determining for the other rows and columns of said first and second matrices until all said rows and columns have been updated.

Claims

1. A method of driving a display, comprising a method of digitally processing data in a data array defining a target matrix (X) using non-negative matrix factorization to determine a pair of matrices (F, G), a first matrix of said pair determining a set of features for representing said data, a second matrix of said pair determining weights of said features, such that a product of said first and second matrices approximates said target matrix, the method of digitally processing data comprising:

inputting said target matrix data (X);

selecting a row of said one of said first and second matrices and a column of the other of said first and second matrices;

determining a target contribution (R) of said selected row and column to said target matrix;

determining, subject to a non-negativity constraint, updated values for said selected row and column from said target contribution; and

repeating said selecting and determining for the other rows and columns of said first and second matrices until all said rows and columns have been updated.

2. A method of driving a display as claimed in claim 1 wherein said determining of updated values comprises determining a new value for said selected row independent of a previous value of said selected row and determining a new value for said selected column independent of a previous value of said selected column, or comprises determining a new value for a said selected row or column dependent on a weighting factor incorporating a previous value of said selected row or column, said weighting factor determining a degree of convergence of successive iterations of said determining updated values.

3. A method of driving a display as claimed in claim 1, wherein said determining of a target contribution (R) comprises determining a difference between said target matrix (X) and a sum of weighted features determined from all said rows and columns of said first and second matrices except said selected row and column.

4. A method of driving a display as claimed in claim 1, wherein said determining of updated values comprises calculating values of G_ia=f₁(R,F) and F_au=f₂(R, G) where R is a matrix with I rows and U columns, F is a matrix with A rows and U columns and G is a matrix with I rows and A columns, where f₁ and f₂ denote first and second functions, and where G_ia denotes a data element in the ith row and ath column of G and F_au denotes a data element in the ath row and uth column of F.

5. A method of driving a display as claimed in claim 4 wherein f₁ and f₂ are selected to minimise a cost function measuring a quality of approximation of a product of said selected row and column to said target contribution.

6. A method of driving a display as claimed in claim 5 wherein said cost function comprises a squared Euclidean distance between a product of said selected row and column and said target contribution.

7. A method of driving a display as claimed in claim 5 wherein said cost function comprises a divergence function between a product of said selected row and column and said target contribution.

8. A method of driving a display as claimed in claim 4, wherein G_ia and F_iu are determined in accordance with:

9. A method of driving a display as claimed in claim 8 wherein Φ

iu is substantially unity for all i and u.

10. A method of driving a display as claimed in claim 8 wherein Φ

_iu has the form Φ

_iu=I/(Z_iu+γ

) where Z_iu denotes a data element in the ith row and uth column of an I by U matrix dependent upon at least one of X and R, and γ

is positive.

11. A method of driving a display as claimed in claim 4, wherein A is less than the smaller of I and U.

12. A method of driving a display as claimed in claim 1, further comprising initialising said first and second matrices.

13. A method of driving a display as claimed in claim 12 wherein said data comprises image data for an image in a time series of images, and wherein said initialising is conditional upon a degree of difference between said image and a previous image.

14. A method of driving a display as claimed in claim 1, wherein said determining subject to a non-negativity constraint comprises setting a said updated value to substantially zero where the updated value would otherwise be negative.

15. A method of driving a display as claimed in claim 1, further comprising constraining said updated values to lie between a minimum and a maximum value.

16. A method of driving a display as claimed in claim 1, further comprising repeating said updating of all said rows and columns of said first and second matrices for a plurality of iterations.

17. A method of driving a display as claimed in claim 1, wherein said data comprises image data defining an image, and wherein said set of features determined by said first matrix comprises a set of subframes which when combined according to said weights determined by said second matrix approximate said image.

18. A method of driving a display as claimed in claim 1 comprising a plurality of pixels arranged in rows and columns, the method comprising employing the method of digital processing defined in claim 1 to process data for display as said target matrix data (X) to determine said first and second matrices (F,G), and driving said display to form an image using a plurality of subframes, each subframe having said rows and columns of pixels driven responsive to a row of one of said first and second matrices and a column of the other of said first and second matrices.

19. A carrier medium carrying processor control code, to, when running, implement the method of claim 1.

20. A computer system configured to implement the method of driving a display as claimed in claim 1, the method comprising inputting said target matrix data (X), the system comprising:

an input for said data for said data array;

an output for outputting said first and second matrices;

data memory for storing said target matrix and said pair of matrices;

program memory storing processor control code; and

a processor coupled to said input, to said output, to said data memory and to said program memory for loading and implementing said processor control code, said code comprising code to, when running implement the method of claim 1.

21. Apparatus for driving a display, the display having a matrix of pixels, said driving comprising digitally processing data in a data array defining a target matrix (X) using non-negative matrix factorization to determine a pair of matrices (F, G), a first matrix of said pair determining a set of features for representing said data, a second matrix of said pair determining weights of said features, such that a product of said first and second matrices approximates said target matrix, the apparatus comprising:

means for inputting said target matrix data (X);

means for selecting a row of said one of said first and second matrices and a column of the other of said first and second matrices;

means for determining a target contribution (R) of said selected row and column to said target matrix;

means for determining, subject to a non-negativity constraint, updated values for said selected row and column from said target contribution; and

means for repeating said selecting and determining for the other rows and columns of said first and second matrices until all said rows and columns have been updated,

wherein each said pixel is addressable by a row electrode and a column electrode;

wherein one of said factor matrices defines row drive signals and the other of said factor matrices defines column drive signals; and

wherein said driving comprises driving using said row and column drive signals.

22. A method of driving an electro-optic display, the display having a matrix of pixels, the method comprising:

inputting image data for said matrix of pixels into an image data matrix;

factorizing said image data matrix into a product of first and second factor matrices by employing non-negative matrix factorization; and

driving said display using said factor matrices; and

wherein

said factorizing comprising iteratively adjusting said factor matrices such that their product approaches said image data matrix; and

wherein

said iterative adjusting comprises adjusting each row of one of said factor matrices and each column of the other of said factor matrices in turn,

wherein each said pixel is addressable by a row electrode and a column electrode;

wherein one of said factor matrices defines row drive signals and the other of said factor matrices defines column drive signals; and

wherein said driving comprises driving using said row and column drive signals.

23. A method as claimed in claim 22 wherein said adjusting of a row or column comprises determining a new value for a said row or column independently of a previous value of said row or column, or comprises determining a new value for a said row or column dependent on a weighting factor incorporating a previous value of said row or column, said weighting factor determining a degree of convergence of successive said iterations.

24. A method as claimed in claim 22 wherein said driving comprises driving a plurality of said row electrodes in combination with a plurality of said column electrodes.

25. A method as claimed in claim 22, wherein said driving comprises driving said display with successive sets of said row and column signals to build up a display image, each said set of signals defining a subframe of said display image, said subframes combining to define said display image.

26. A method as claimed in claim 25 wherein said first factor matrix has dimensions determined by a number of said row electrodes and a number of said subframes, and wherein said second factor matrix has dimensions determined by a number of said column electrodes and said number of subframes.

27. A method as claimed in claim 25, wherein a number of said subframes is no greater than the smaller of a number of said row electrodes and a number of said column electrodes.

28. A method as claimed in claim 22, wherein said display comprises a passive matrix OLED display.

29. A method as claimed in claim 22, wherein said display comprises a plasma display.

30. A method as claimed in claim 22, wherein said display comprises an inorganic LED display.

31. A method as claimed in claim 22, wherein said display comprises a liquid crystal display.

32. A carrier medium carrying processor control code, to, when running, implement the method of claim 22.

33. A driver for an electro-optic display, the display having a matrix of pixels, the driver comprising:

an input to input image data for said matrix of pixels into an image data matrix;

a matrix factorization system to factorize said image data matrix into a product of first and second factor matrices by employing non-negative factorization; and

a driver output to drive said display using said factor matrices, and wherein

said matrix factorization system is configured to iteratively adjust said factor matrices, such that their product approaches said image data matrix, by adjusting each row of one of said factor matrices and each column of the other of said factor matrices in turn.

34. An integrated circuit including the matrix factorization system of claim 33.

35. A method of driving a display, comprising processing a data array defining a target matrix (X) to determine a pair of factor matrices (F,G) such that a product of said factor matrices approximates said target matrix (X), the method comprising:

determining for a single row or column of a first said factor matrix a value to which an updating rule would converge when iteratively applied, said updating rule comprising an updating rule of a factorizing algorithm which iteratively updates two factor matrices to more closely approximate a target matrix using said updating rule wherein said factorizing comprises non-negative matrix factorization;

updating said row or column with said determined value;

repeating said determining and updating for a column or row of a second said factor matrix; and

repeating said determining and updating of said first and second factor matrices to update each row or column of said first factor matrix and each column or row of said second factor matrix.

36. A carrier carrying processor control code to, when running, implement the method of claim 35.