Content independent method of motion determination using sparse matrices

• US 9,875,552 B1
• Filed: 07/26/2016
• Issued: 01/23/2018
• Est. Priority Date: 07/26/2016
• Status: Active Grant

• Current Assignee: Teradici Corporation (HP Inc.)
• Original Assignee: Teradici Corporation (HP Inc.)
• Inventors: Savage, Joseph Michel Kenneth, Helter, Paul Andrew, Longhurst, Peter William
• Primary Examiner(s): Strege, John
• Application Number:
  US15/219,897
• Time in Patent Office: 546 Days
• CPC Class Codes: G06T 2207/10016 Video; Image sequence
• CPC Class Codes: G06T 7/246 using feature-based methods, e.g. the tracking of corners or segments
• CPC Class Codes: H04N 19/51 Motion estimation or motion compensation

Abstract

A method and apparatus for motion determination comprising generating a hash value for each changed pixel in a frame of an image display sequence, the changed pixels indicated in a set of sparse display coordinates, for each changed pixel, overwriting (X, Y) information at a position in a symbol table indexed by the hash value, the (X, Y) information comprising one display coordinate associated with the each changed pixel, generating motion vectors for a frame, each motion vector specifying a pixel area determined from at least one (X, Y) delta between one of the changed pixels represented in the symbol table and a previously changed pixel represented at the position in a previous frame symbol table for a previous frame in the image display sequence, and transmitting the motion vectors from the host computer over a network to a client computer.

Claims

1. A method for motion determination in an image display sequence comprising:

generating, at a host computer, a hash value for each changed pixel of changed pixels in a frame of the image display sequence, the changed pixels indicated in a set of sparse display coordinates;

for each changed pixel, overwriting (X, Y) information at a position in a symbol table indexed by the hash value, the (X, Y) information comprising one display coordinate pair in the set of sparse display coordinates associated with the each changed pixel;

generating motion vectors for a frame in the image display sequence, each motion vector specifying a pixel area determined from at least one (X, Y) delta in the (X, Y) information between one of the changed pixels represented in the symbol table and a previously changed pixel represented at the position in a previous frame symbol table, the previous frame symbol table for a previous frame in the image display sequence; and

transmitting the motion vectors from the host computer over a network to a client computer.

2. The method of claim 1 further comprising:

generating, at the host computer, additional hashes for unchanged pixels correspondingly indicated in the set of sparse display coordinates, wherein each of the additional hashes is generated following an age of a corresponding pixel in the unchanged pixels.

3. The method of claim 2 wherein the age is determined from a count of the overwritten (X, Y) information following a change in the corresponding pixel in the unchanged pixels.

4. The method of claim 1 wherein the set of sparse display coordinates is defined by a unit 2D Golomb ruler replicated over the frame.

5. The method of claim 1 wherein pixel density within the set of sparse display coordinates is adjusted based on at least one of CPU availability of the host computer and bandwidth availability of the network.

6. The method of claim 1 wherein the hash value is generated by hardware encryption circuitry of the host computer.

7. The method of claim 1 wherein the (X, Y) information includes select significant bits of the hash value.

8. The method of claim 1 wherein each of the motion vectors is selected based on a ranking of counts associated with the at least one (X, Y) delta.

9. The method of claim 1 wherein each of the motion vectors is selected based on a threshold number of counts associated with the at least one (X, Y) delta.

10. The method of claim 1 wherein each of the motion vectors is validated by confirming that the pixel area in the frame matches a second pixel area at the at least one (X, Y) delta in the previous frame.

11. The method of claim 1, further comprising:

recasting the symbol table as the previous frame symbol table following the generation of the motion vectors.

12. The method of claim 1 wherein the changed pixels comprise at least one portion of the frame, exclusive of video pixels, the video pixels identified as continuously changing at a rate of at least five frames per second for a period of at least 1 second.

13. The method of claim 1 wherein the set of sparse display coordinates is partitioned across a plurality of frame buffers associated with the frame.

14. The method of claim 1 wherein the set of sparse display coordinates is determined prior to acquiring an image comprising the changed pixels.

15. The method of claim 1 wherein the hash value for each of the changed pixels is generated from a hash set associated with one pixel in the changed pixels and wherein the hash set comprises a common spatial arrangement.

16. The method of claim 1, wherein the set of sparse display coordinates is arranged in X and Y dimensions according to a ruler of nine markings spread over a total of sixty-four divisions.

17. The method of claim 16 wherein the nine markings are located at positions 0, 4, 7, 19, 37, 42, 43, 51 and 53 on the ruler.

18. An apparatus for motion determination in an image display sequence comprising:

a host processor of a host computer comprising;

a hash engine that;

generates a hash value for each changed pixel of changed pixels in a frame of the image display sequence, the changed pixels indicated in a set of sparse display coordinates; and

a central processing unit that;

for each changed pixel, overwrites (X, Y) information at a position in a symbol table indexed by the hash value, the (X, Y) information comprising one display coordinate in the set of sparse display coordinates associated with each changed pixel; and

generates motion vectors for a frame in the image display sequence, each motion vector specifying a pixel area determined from at least one (X, Y) delta in the (X, Y) information between one of the changed pixels represented in the symbol table and a previously changed pixel represented at the position in a previous frame symbol table, the previous frame symbol table for a previous frame in the image display sequence,

wherein the host processor transmits the motion vectors from the host computer over a network to a client computer.

19. The apparatus of claim 18, wherein the set of sparse display coordinates are defined by a unit 2D Golomb ruler replicated over the frame.

20. The apparatus of claim 19, wherein pixel density within the set of sparse display coordinates is adjusted based on at least one of CPU availability of the host computer and bandwidth availability of the network.