Median value determination in a data processing system
AssigneeImagination Technologies Limited
InventorTimothy Lee
Life of this patent
Estimating the term…
Abstract
Median values for a stream of received data values in a data processing system (e.g. an image processing system) are determined. A first median value of the received data values within a first subset of data values of the received stream is determined, and intermediate data used for determining the first median value is stored. The stored intermediate data is used to determine a median value of the received data values within a second subset of data values of the received stream, wherein the second subset at least partially overlaps with the first subset. The determined median values are outputted for use in the data processing system, e.g. for further processing.
Claims22
A data processing system configured to process a stream of data values, the data processing system comprising a median determining unit which is configured to receive data values of the stream and determine median values for use in the data processing system, the median determining unit comprising:
- data storage logic configured to store intermediate data for use in determining median values;
- and
- processing logic configured to:
- determine intermediate data for use in determining a median value of a first subset of the received data values of the stream, and to cause the determined intermediate data to be stored in the data storage logic;
- determine a median value of the received data values within the first subset using the determined intermediate data;
- and
- for each of at least one further subset of the received data values of the stream:
- retrieve the intermediate data determined for a previous subset of data values from the data storage logic;
- use the retrieved intermediate data for the previous subset of data values to determine intermediate data for use in determining a median value of the current subset of received data values of the stream, wherein the current subset of data values at least partially overlaps with the previous subset of data values;
- cause the determined intermediate data for the current subset of data values to be stored in the data storage logic;
- and
- determine a median value of the received data values within the current subset using the determined intermediate data for the current subset;
- wherein the median determining unit is further configured to output the determined median values for use in the data processing system, and
- wherein the intermediate data for a subset of data values comprises, for each pairing of data values within the subset, an indication of which of the data values of the pairing is greater.
A method of determining median values in a data processing system which processes a stream of data values, the method comprising:
- receiving data values of the stream;
- determining and storing intermediate data for use in determining a median value of a first subset of the received data values of the stream;
- determining a median value of the received data values within the first subset using the determined intermediate data;
- and
- for each of at least one further subset of the received data values of the stream:
- using the stored intermediate data determined for a previous subset of data values to determine intermediate data for use in determining a median value of the current subset of received data values of the stream, wherein the current subset of data values at least partially overlaps with the previous subset of data values;
- storing the determined intermediate data for the current subset of data values;
- and
- determining a median value of the received data values within the current subset using the determined intermediate data for the current subset;
- the method further comprising outputting the determined median values for use in the data processing system,
- wherein the intermediate data for a subset of data values comprises, for each pairing of data values within the subset, an indication of which of the data values of the pairing is greater.
A non-transitory computer readable storage medium having stored thereon a computer readable description of an integrated circuit that, when processed in an integrated circuit manufacturing system, causes the integrated circuit manufacturing system to manufacture a data processing system which is configured to process a stream of data values, the data processing system comprising a median determining unit which is configured to receive data values of the stream and determine median values for use in the data processing system, the median determining unit comprising:
- data storage logic configured to store intermediate data for use in determining median values;
- and
- processing logic configured to:
- determine intermediate data for use in determining a median value of a first subset of the received data values of the stream, and to cause the determined intermediate data to be stored in the data storage logic;
- determine a median value of the received data values within the first subset using the determined intermediate data;
- and
- for each of at least one further subset of the received data values of the stream:
- retrieve the intermediate data determined for a previous subset of data values from the data storage logic;
- use the retrieved intermediate data for the previous subset of data values to determine intermediate data for use in determining a median value of the current subset of received data values of the stream, wherein the current subset of data values at least partially overlaps with the previous subset of data values;
- cause the determined intermediate data for the current subset of data values to be stored in the data storage logic;
- and
- determine a median value of the received data values within the current subset using the determined intermediate data for the current subset;
- wherein the median determining unit is further configured to output the determined median values for use in the data processing system, and
- wherein the intermediate data for a subset of data values comprises, for each pairing of data values within the subset, an indication of which of the data values of the pairing is greater.
A data processing system configured to process a stream of data values, the data processing system comprising a median determining unit which is configured to receive data values of the stream and determine median values for use in the data processing system, the median determining unit comprising:
- data storage logic configured to store intermediate data for use in determining median values;
- and
- processing logic configured to:
- determine intermediate data for use in determining a median value of a first subset of the received data values of the stream, and to cause the determined intermediate data to be stored in the data storage logic;
- determine a median value of the received data values within the first subset using the determined intermediate data;
- and
- for each of at least one further subset of the received data values of the stream:
- retrieve the intermediate data determined for a previous subset of data values from the data storage logic;
- use the retrieved intermediate data for the previous subset of data values to determine intermediate data for use in determining a median value of the current subset of received data values of the stream, wherein the current subset of data values at least partially overlaps with the previous subset of data values;
- cause the determined intermediate data for the current subset of data values to be stored in the data storage logic;
- and
- determine a median value of the received data values within the current subset using the determined intermediate data for the current subset;
- wherein the median determining unit is further configured to output the determined median values for use in the data processing system, and
- wherein the intermediate data for a subset of data values comprises, for each of the data values in the subset, an index value indicating a sorted position of the data value within the subset, wherein the processing logic is configured to determine a median value of the data values within a subset of data values by selecting one of the data values in the subset based on the index values.
A method of determining median values in a data processing system which processes a stream of data values, the method comprising:
- receiving data values of the stream;
- determining and storing intermediate data for use in determining a median value of a first subset of the received data values of the stream;
- determining a median value of the received data values within the first subset using the determined intermediate data;
- and
- for each of at least one further subset of the received data values of the stream:
- using the stored intermediate data determined for a previous subset of data values to determine intermediate data for use in determining a median value of the current subset of received data values of the stream, wherein the current subset of data values at least partially overlaps with the previous subset of data values;
- storing the determined intermediate data for the current subset of data values;
- and
- determining a median value of the received data values within the current subset using the determined intermediate data for the current subset;
- the method further comprising outputting the determined median values for use in the data processing system,
- wherein the intermediate data for a subset of data values comprises, for each of the data values in the subset, an index value indicating a sorted position of the data value within the subset, wherein a median value of the data values within a subset of data values is determined by selecting one of the data values in the subset based on the index values.
A non-transitory computer readable storage medium having stored thereon a computer readable description of an integrated circuit that, when processed in an integrated circuit manufacturing system, causes the integrated circuit manufacturing system to manufacture a data processing system which is configured to process a stream of data values, the data processing system comprising a median determining unit which is configured to receive data values of the stream and determine median values for use in the data processing system, the median determining unit comprising:
- data storage logic configured to store intermediate data for use in determining median values;
- and
- processing logic configured to:
- determine intermediate data for use in determining a median value of a first subset of the received data values of the stream, and to cause the determined intermediate data to be stored in the data storage logic;
- determine a median value of the received data values within the first subset using the determined intermediate data;
- and
- for each of at least one further subset of the received data values of the stream:
- retrieve the intermediate data determined for a previous subset of data values from the data storage logic;
- use the retrieved intermediate data for the previous subset of data values to determine intermediate data for use in determining a median value of the current subset of received data values of the stream, wherein the current subset of data values at least partially overlaps with the previous subset of data values;
- cause the determined intermediate data for the current subset of data values to be stored in the data storage logic;
- and
- determine a median value of the received data values within the current subset using the determined intermediate data for the current subset;
- wherein the median determining unit is further configured to output the determined median values for use in the data processing system, and
- wherein the intermediate data for a subset of data values comprises, for each of the data values in the subset, an index value indicating a sorted position of the data value within the subset, wherein the processing logic is configured to determine a median value of the data values within a subset of data values by selecting one of the data values in the subset based on the index values.
Dependencies are inferred from the claim text.