Generating sparse sample histograms in image processing

Apparatus for binning an input value into an array of bins, each bin representing a range of input values and the bins collectively representing a histogram of input values, the apparatus comprising: an input for receiving the input value; a memory for storing the array; and a binning controller configured to: derive a plurality of bin values from the input value according to a binning distribution located about the input value, the binning distribution spanning a range of input values and each bin value having a respective input value dependent on the position of the bin value in the binning distribution; and allocate the plurality of bin values to a plurality of bins in the array, each bin value being allocated to a bin selected according to the respective input value of the bin value.

BACKGROUND OF THE INVENTION

This invention relates to apparatus for generating a histogram of input values and to a method of binning input values so as to generate such a histogram.

The processing pipelines of digital cameras commonly make use of histograms to summarise the frequency distribution of parameters captured by pixels of the camera sensor such as exposure or colour channel parameters. A histogram divides the range of possible input values of a parameter into a series of bins, with each bin representing a count of the number of pixels having a parameter falling within the respective range of that bin. Such histograms can be used by the image processing algorithms of the pipeline in order to perform control functions of the camera such as auto-exposure, auto-focus and auto-white balance. A camera sensor will generally include many millions of pixels and the use of such histograms helps to provide a summary of the characteristics of a captured frame at a level of detail which is appropriate and manageable by pipeline algorithms.

BRIEF SUMMARY OF THE INVENTION

According to a first aspect of the present invention there is provided apparatus for binning an input value into an array of bins, each bin representing a range of input values and the bins collectively representing a histogram of input values, the apparatus comprising:an input for receiving the input value;a memory for storing the array; anda binning controller configured to:derive a plurality of bin values from the input value according to a binning distribution located about the input value, the binning distribution spanning a range of input values and each bin value having a respective input value dependent on the position of the bin value in the binning distribution; andallocate the plurality of bin values to a plurality of bins in the array, each bin value being allocated to a bin selected according to the respective input value of the bin value.

The binning distribution may be centred on the input value.

The binning distribution may be a Gaussian distribution or an approximation thereto.

The input value may be an image characteristic derived from one or more pixels of an image frame.

The binning controller may be configured to select the span of the binning distribution according to one or more predefined or adaptive parameters.

The binning controller may be configured to select the span of the binning distribution in dependence on a measure of the sparsity of the histogram represented by the array of bins.

The binning controller may be configured to, prior to allocating each of the plurality of bin values to its respective bin, decay the values held at the array of bins according to a predefined decay factor.

The binning controller may be configured to derive the plurality of bin values from the input value by scaling the binning distribution by the input value, each of the bin values being the scaled height of the binning distribution at the respective bin of the array.

The binning controller may be configured to normalise the histogram such that the bins of the array sum to 1.

Each bin of the array may have a width equal to a unit of the input value.

The input value may be received at the input expressed as a plurality of component values.

According to a second aspect of the present invention there is provided a data processing device for detecting a change in a sequence of input values, the data processing device comprising:apparatus as described herein and configured to generate the histogram of input values by binning a plurality of input values of the sequence into the array of bins; andchange detection logic configured to use the histogram to estimate the likelihood of the received input value and generate a measure of change in the input values in dependence on the estimated likelihood.

The estimated likelihood may represent a measure of probability of the received input value occurring given the frequency distribution of input values represented by the histogram.

The change detection logic may be configured to form the measure of probability in dependence on the value of the bin in the array corresponding to the received input value.

The change detection logic may be configured to derive a normalised histogram from the bins of the array and use the value of the bin of the normalised histogram which corresponds to the received input value as the measure of probability.

The change detection logic may be configured to derive the normalised histogram such that the bins of the histogram sum to 1.

The change detection logic may be configured to generate the measure of change in the input values by comparing the estimated likelihood to a predefined or adaptive threshold.

The measure of change may be indicative of a change in the sequence of input values if the estimated likelihood exceeds the predefined or adaptive threshold.

The change detection logic may be configured to form the adaptive threshold by summing the bins in order of decreasing value and identifying a threshold bin at which that sum first exceeds a predefined total, and to derive the adaptive threshold in dependence on the value of the threshold bin.

The input values may be image characteristics received for a block of pixels of a frame and the data processing device is for detecting motion in the block of pixels.

The indication of change may be a binary value identifying whether or not the estimated likelihood is indicative of change in the sequence of input values.

The input value may be one or more of luminance, hue, lightness, brightness, chroma, colorfulness, saturation, or a measure of variation therein.

According to a third aspect of the present invention there is provided a method of binning an input value into an array of bins, each bin representing a range of input values and the bins collectively representing a histogram of input values, the method comprising:receiving an input value;deriving a plurality of bin values from the input value according to a binning distribution located about the input value, the binning distribution spanning a range of input values and each bin value having a respective input value indicated by the position of the bin value in the binning distribution; andallocating the plurality of bin values to a plurality of bins, each bin value being allocated to a bin selected according to the respective input value of the bin value.

The method may further comprise, prior to allocating each of the plurality of bin values to its respective bin, decaying the values held at the array of bins according to a predefined decay factor.

The deriving the plurality of bin values from the input value may comprise scaling the binning distribution by the input value, each of the bin values being the scaled height of the binning distribution at the respective bin of the array.

The method may comprise:binning a plurality of input values of the sequence into the array of bins so as to generate the histogram of input values;using the histogram to estimate the likelihood of the received input value; andin dependence on the estimated likelihood, generating a measure of change in the input values.

The estimated likelihood may represent a measure of probability of the received input value occurring given the frequency distribution of input values represented by the histogram.

The using the histogram may comprise forming the measure of probability in dependence on the value of the bin in the array corresponding to the received input value.

The using the histogram may comprise deriving a normalised histogram from the bins of the array and using the value of the bin of the normalised histogram which corresponds to the received input value as the measure of probability.

The generating a measure of change may comprise comparing the estimated likelihood to a predefined or adaptive threshold.

The measure of change may be indicative of change in the sequence of input values if the estimated likelihood exceeds the predefined or adaptive threshold.

The method may further comprise forming the adaptive threshold by:summing the bins in order of decreasing value so as to identify a threshold bin at which that sum first exceeds a predefined total; andderiving the adaptive threshold in dependence on the value of the threshold bin.

The apparatus may be embodied in hardware on an integrated circuit. There may be provided a method of manufacturing, at an integrated circuit manufacturing system, the apparatus. There may be provided an integrated circuit definition dataset that, when processed in an integrated circuit manufacturing system, configures the system to manufacture the apparatus. There may be provided 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 the apparatus.

There may be provided an integrated circuit manufacturing system comprising:a non-transitory computer readable storage medium having stored thereon a computer readable integrated circuit description that describes the apparatus;a layout processing system configured to process the integrated circuit description so as to generate a circuit layout description of an integrated circuit embodying the apparatus; andan integrated circuit generation system configured to manufacture the apparatus according to the circuit layout description.

There may be provided computer program code for performing a method as described herein. There may be provided non-transitory computer readable storage medium having stored thereon computer readable instructions that, when executed at a computer system, cause the computer system to perform the methods as described herein.

DETAILED DESCRIPTION OF THE INVENTION

One example of the use of histograms is for performing motion detection in a sequence of frames captured by a camera sensor. For example, this can be a useful feature in security cameras since it allows the camera to flag up periods of motion in a video feed or to only record or transmit the captured video stream when motion is detected. It is often the case that very limited resources are available in camera hardware or associated processing equipment to perform motion detection and/or it is desired that motion detection is performed at low power. As a result, frames captured by a camera sensor are typically downsampled (e.g. from HD to VGA resolution) and motion detection performed in the downsampled frames at a low frame rate (e.g. at 10-15 frames per second rather than the, say, 30 frames per second provided by the camera sensor).

In order to further reduce the processing burden, frames are typically divided into a set of blocks in respect of which motion detection is performed, with each block comprising a plurality of pixels of the frame. To facilitate motion detection processing (and potentially other image processing functions) on a per-block basis, a camera pipeline may generate histograms for each block representing the frequency distribution of image parameters within a block and potentially over several frames. For example, a histogram may be generated representing a typical measure of luminance for a block and motion may be identified in that block by looking for a sudden change in the luminance of the block which is indicative of motion.

However, the use of a limited number of pixels or sampling points per block for a parameter and/or the use of narrow bins and/or the use of a low frame rate can lead to a sparsely-populated histogram being generated for a block, i.e. a histogram having a substantial proportion of empty bins and gaps in the histogram distribution. Such a histogram may be termed a sparse histogram. An example of a sparse histogram is shown inFIG. 2.

Sparse histograms tend to be a poor quality representation of the underlying frequency distribution for a parameter. Sparse histograms may be filtered before use in order to form an improved estimate of the underlying frequency distribution for the parameter represented by the histogram. Such filtering is typically performed so as to generate a denser histogram to produce a smoothed distribution without significant gaps. Filtering sparse histograms in this manner requires an additional processing step and can result in a loss of fidelity (e.g. attenuation of intermediate peaks in multi-modal distributions).

Apparatus and methods are described for generating a histogram of an input value which are particularly suitable for use with a sparse dataset of input values. In the examples described herein, the apparatus and methods relate to the performance of motion detection in a sequence of image frames. Generally, the apparatus and methods may be for generating a histogram of any input value for any purpose, including for generating a histogram of any image characteristic received from a camera sensor or pipeline and for generating a histogram of any audio characteristic received from an audio source. Apparatus and methods configured as described herein may be configured for the purpose of detecting a change in the input values: such change detection is not limited to the performance of motion detection in a sequence of image frames. It will be appreciated that any of the examples, features or functions described below with respect to generating a histogram of a particular image characteristic (e.g. luminance or its standard deviation) may be generally applied to the generation of a histogram for any other image characteristic, audio characteristic, or other input value from any source and for any purpose, not limited to motion detection.

Aspects of the present invention will now be described by way of example with respect to the apparatus shown inFIG. 1for performing motion detection in a sequence of video frames captured at a camera.

FIG. 1is a schematic diagram of apparatus which includes a camera module101and a motion detector115. The camera module101comprises a camera sensor102which is arranged to provide frames to an image processor103. The image processor103may generate various image characteristics for use at the motion detector and potentially other processing units on or outside the camera pipeline.

For example, the image processor may gather statistics for use at auto white balance and auto exposure functions of a camera pipeline. The image processor is configured to provide image characteristics for one or more blocks of a frame. For example, each frame may be divided into a set of 16 blocks, with the image processor generating image characteristics in respect of each of the blocks.

A block may be part or all of a frame and any given block may or may not overlap with other blocks of the same frame. A block may be any collection of one or more pixels of a frame and may take any shape. The pixels of a block may or may not be contiguous within a frame. One or more pixels of a frame may not belong to any block defined for the frame. Any given pixel of a frame may belong to one or more blocks.

The image processor may be configured to generate image characteristics independently for one or more of the colour channels of an image frame (e.g. for each of the red, green and blue channels in the case of an RGB image captured at the camera). A measure of luminance provided by the image processor may be provided as a set of colour components or other image characteristics for interpretation at the motion detector as a measure of luminance.

A flowchart400illustrating an exemplary operation of the image processor103is shown inFIG. 4. The image processor receives a raw image401(of input stream104) from the camera sensor102and performs Bayer space processing402and demosaicing403of the image. At404the image processor converts the raw image into an RGB image on which the image processor calculates statistics405for use at auto exposure and auto white balance functions of the camera pipeline (not shown). These statistics may be included in the image characteristics108provided to the motion detector115. The image processor may additionally perform further RGB space processing406, such as colour correction. The image processor converts the RGB image frame into the YUV colour space407so as to generate a YUV image frame408, on which YUV space processing409may be performed (e.g. contrast enhancement). The resulting YUV frames may be provided at one or more different scales410,411according to the requirements of subsequent units taking their input from the image processor, such as encoder106. In this example, scalar410may correspond to the stream of frames105provided to the encoder106for encoding into a video stream107. Encoder106may receive frames via a frame store118at which frame data from the camera sensor, potentially processed by the image processor103, may be stored. In some examples, the motion detector may receive a stream of frames from the image processor103(e.g. scalar411).

Image processing may be performed by image processor103at a lower resolution than that captured by the camera sensor. For example, the camera sensor may be a HD sensor but image processing may be performed at, say, VGA resolution (640×480 pixels). Lower resolutions such as VGA are typically sufficient for the purpose of generating statistics for motion detection and reduces the processing capabilities required of the image processor and/or allows image processing to be performed at low power. In some examples, the image frames captured by the camera sensor may be downscaled before being provided to the image processor, with the camera sensor providing full resolution frames directly to the encoder106(possibly via data store118and/or another unit, e.g. to convert raw frames into YUV frames). The image processor may be configured to provide image characteristics describing one or more blocks of each frame for use at the motion detector but not the image frames themselves.

The arrangement of camera module101shown inFIG. 1is merely one possibility and it will be appreciated that various other arrangements of a camera module are possible. In particular, the presence or otherwise of encoder106is not relevant to the operation of motion detector115and is included merely for illustrative purposes. The camera module101need only provide image characteristics108for the motion detector which are sufficient for the motion detector to form an output indicative of motion at a block. The image characteristics108may comprise one or more different types of image characteristics, such as exposure information and colour information for one or more colour channels. In other examples the camera module101may be any other source of image characteristics108for use at the motion detector (e.g. module101may derive image characteristics from stored image frames).

In examples of the present invention, the image processor may provide a measure of luminance for each block of a frame as an input value for the motion detector. This could be a measure of average luminance over two or more pixels of a block, a measure of luminance of a randomly selected or predetermined pixel of a block, or any other measure of luminance associated with a block. The measure of luminance in this case represents an image characteristic108on the basis of which motion detection is performed. The measure of luminance may be provided in any suitable manner. For example, a luma value may be used as a measure of luminance for one or more pixels of a block (e.g. a luma component of a YUV colour space), or a measure of luminance for a block could comprise one or more individual colour components each expressing an average value of the respective colour component for a block.

Binning controller109is configured to, for each block, maintain a histogram representing an expected distribution of luminance for the block based on image characteristics108received over time for the block (e.g. in respect of a plurality of frames). Each bin of the histogram represents a range of luminance values. The range of each bin may be a single luminance value. For example, in the case of luminance expressed as a luma value in the range 0 to 255, the histogram may comprise 256 bins with each luminance value being allocated to its respective bin by the binning controller. In other examples, each bin may correspond to multiple bin values. The width of bins may vary over the possible range of input values to the histogram.

The binning controller109is configured to maintain the histogram by, on receiving a luminance input value for a block from the image processor, decaying the bin values of the histogram maintained for that block and allocating the received luminance value to its corresponding bin. Each bin may be a counter such that, on allocating a luminance value to a bin, the binning controller109is configured to increment the count value of the counter corresponding to that bin by some predetermined value (e.g. one). In this manner, a summary of the frequency distribution of the input values is formed.

A flowchart illustrating an example of the operation of the motion detector115which includes the binning controller109is shown inFIG. 6. On receiving a luminance value for a block601(e.g. from camera module101), the binning controller109and block logic110perform their respective functions in order to, respectively, maintain a histogram for the block and form a motion output for the block. The operation of the binning controller and block logic is described in more detail below. The binning controller and block logic may operate in any manner, including in series or concurrently/in parallel. Preferably however, the histogram of a block is used by the block logic prior to the binning controller updating the histogram with the received luminance value. The block logic110represents an example of change detection logic and the motion detector115an example of a data processing device for detecting a change in the input values on which it is configured to operate. In other examples the input values may not be received in respect of a block of a frame and could be, for example, audio samples in which a change in level is to be detected.

An example illustrating how binning controller109may maintain a histogram112at a memory111will now be described with respect toFIGS. 1 and 6. Memory111may be any kind of data store accessible to the motion detector115; it may be internal or external to the data store and may comprise one or more storage elements. Each frame is divided into one or more blocks each comprising one or more pixels of the frame, and in respect of each block a 256 bin histogram is maintained at memory111by the binning controller.

Motion detector115may receive a measure of luminance for each block of a frame (601inFIG. 6). In this example, each frame is divided into 16 non-overlapping blocks and the measure of luminance for each block is a measure of the average luminance over the pixels of the block as calculated by image processor103. In this example, the binning controller109is configured to receive as image characteristics108from the camera module101sums of the red, green and blue channels over the pixels of each block of the image frame captured at the camera sensor102. Such image characteristics are commonly available at a camera pipeline. The image characteristics or statistics may be calculated at image processor103.

The motion detector115may process received image characteristics so as to form a luminance value or other value in respect of which a histogram is to be maintained for one or more blocks of a frame. This may be considered to form part of receiving the luminance for a block601inFIG. 6. For example, a luminance value, Yi, may be calculated for the ithblock of a frame as:

where Ri, Giand Biare the sums of the red, green and blue values across the block which are received as image characteristics, Npixelsis the number of pixels in the block and Nblocksis the number of blocks the image is divided into. In the present example Nblocks=16. The luminance value, Yi, will be referred to as the current luminance value.

The binning controller109is configured to maintain a histogram for one or more blocks of a frame which, for each block, represents the frequency distribution of luminance over time. On receiving a luminance value for a block, the binning controller updates the histogram for the block (603inFIG. 6) with the received luminance value in the manner described below. Each bin of a block's histogram may be initialized with a value appropriate to the implementation. For example, for a histogram having 256 bins, each bin of a histogram could initially be set to:

On receiving a luminance value for a block, each bin of the histogram, by hjold, for that block is decayed (604inFIG. 6) so as to down-weight historical bin values relative to the calculated luminance value. This may be performed before the luminance value is allocated to the histogram (605inFIG. 6). For example, each bin of the histogram of a block may be decayed in dependence on a predefined or adaptive learning coefficient, learnCoeff which takes a value between 0 and 1:
hjdecayed=(1−learnCoeff)*hjold, 0≤j≤255  (3)

Taking a simplistic approach, the Lithhistogram bin of the histogram for the ithblock may then be updated using the current luminance value according to:
hjnew=learnCoeff+hjdecayed, j=Yi(4)

where learnCoeff serves as the contribution of the current luminance value to its respective bin. A suitable value for learnCoeff may be empirically determined.

Over a number of frames, a non-parametric representation of the expected distribution of pixel values for a particular block may be built up which allows for complex multi-modal behaviour to be captured. However, as can be seen from the exemplary histogram shown inFIG. 2, the above simplistic approach tends to lead to a sparse histogram because of the limited number of image characteristics provided for each block and the narrow bins relative to the range of possible luminance values. InFIG. 2, the distribution of luminance values over the bins can be seen to be uneven with gaps201and peaks202. In the present example, a single luminance value is provided, but in other examples more than one value of an image characteristic may be provided (e.g. different image characteristics may be provided for different areas of a block).

An improved approach to allocating image characteristics to the histogram bins will now be described. Rather than allocating each image characteristic received for a block to the respective bin of the corresponding histogram, each image characteristic is used to derive bin values for a plurality of histogram bins located about the respective bin in accordance with a binning distribution. This is602inFIG. 6. The binning distribution may be predefined (e.g. on initialisation of apparatus or binning controller) or defined dynamically (e.g. in dependence on characteristics generated by the image processor for captured frames). For example, in the present case in which a luminance value received for a block expresses a mean luminance over the pixels of the block, the actual luminance values within the block may be assumed to have a Gaussian distribution having a mean, μ, centred on the received value and having a predefined or adaptive standard deviation, σ. Thus, defining the binning distribution as a Gaussian, the bins of a histogram may be updated at603ofFIG. 6using:

where w is the half width of the Gaussian kernel and. By defining the standard deviation in this manner, the kernel may be precalculated into a buffer of length 2w+1. A is a normalization factor, for example:

The allocation of the derived bin values to their respective bins (605inFIG. 6) may be performed after the bins of the histogram have been decayed (604inFIG. 6)—e.g. according to equation 3 above. Once the bin values derived for a luminance value have been allocated to the histogram, the binning controller may move onto the next block (606inFIG. 6) by performing the same steps in respect of a histogram maintained for that next block. A histogram112may be maintained at memory111for one or more blocks of a frame such that, as luminance values are received for the blocks of a sequence of frames, each histogram represents a learned distribution of the frequency of luminance values over time for the corresponding block.

A standard deviation for the binning distribution according to which bin values are derived may be determined empirically for a given system (e.g. through optimising the accuracy of the motion detection performed by motion detector115using the histograms generated by the binning controller). A standard deviation could be determined or defined for an entire frame or for any region of a frame (e.g. a standard deviation could be determined for each block of a frame, with the standard deviation determined for a block being used when binning values of that block). A standard deviation may be adaptively determined by the binning controller or at any other element of the camera module or motion detector—for example, by estimating a standard deviation from a histogram formed by simply binning luminance values (e.g. as discussed above with respect toFIG. 2). This allows a standard deviation to change as, for example, the scene and/or light conditions change. A standard deviation may be a statistic provided by the camera module (e.g. as a result of calculations performed at the image processor103). A standard deviation need not be a true mathematical standard deviation and may be any suitable measure of the width of the underlying or expected distribution of the image characteristic.

The binning controller may be configured to receive multiple luminance values for a block, with each luminance value being binned at a histogram maintained for the block. The binning controller may be configured to receive multiple luminance values for a block, with each luminance value being binned at a separate histogram maintained for the respective luminance value of the block such that multiple histograms are maintained for the block. Each luminance value may be generated for a block in any manner: for example, each luminance value may be generated in respect of a different pixel or group of pixels of the block and/or each luminance value may be calculated in a different way (e.g. a different average of the same or different pixels of a block).

FIG. 3shows a histogram301maintained by binning controller109such that luminance values received for a block are allocated to the block's histogram according to a Gaussian distribution. It can be seen that the histogram learned by the binning controller does not suffer from a sparsity of values and represents a better approximation to the true luminance probability distribution of a block. The binning controller may be configured to allocate luminance values using an approximation to a true Gaussian distribution. Generally, any suitable distribution may be used which is considered to provide sufficiently good performance for the particular application—for example, a triangular distribution or a rectangular distribution.

For image characteristics other than luminance, it may be appropriate to allocate image characteristics to histogram bins in accordance with distributions other than Gaussian distributions which reflect the underlying distribution of values of that image characteristic over a block.

InFIG. 1, binning controller109is shown as being part of a motion detector115. This is merely an example and it will be appreciated that a binning controller need not be provided at a motion detector; a binning controller may be provided at any kind of apparatus, as a discrete unit, or in software.

A learned histogram112maintained at memory111for a block of a sequence of frames by the binning controller109may be used by the block logic110as a representation of the probability distribution of a particular luminance value occurring for a block. The probability of a received luminance value belonging to the histogram distribution, Pbackground, may be determined by the block logic110by means of a lookup into the learned histogram at the bin corresponding to the received luminance value. This is607inFIG. 6. The histogram may be a normalised version of the histogram:

Each histogram may be stored in normalised form at memory111or the normalised value of each bin may be calculated by the motion detector115(e.g. at block logic110). For example, the sum of the bins Σk=0255hkused in equation 8 may be stored with a histogram such that the normalised value of each histogram bin may be trivially formed from a stored histogram112by the motion detector according to equation 8.

Generally the block logic may be configured to form some measure of the likelihood of a received luminance value occurring given the frequency distribution represented by the histogram. This is608inFIG. 6. The likelihood need not be a true probability and may take any suitable range of values, not necessarily between 0 and 1.

The bin probability calculation may be performed using the histogram prior to a received luminance value being allocated to the histogram. Because the binning controller allocates luminance values to a histogram in accordance with some binning distribution, the histogram maintained for each block is smooth and can be directly sampled without the errors due to the uneven distribution (and hence inaccurate probabilities) which would occur with a sparse histogram.

The direct sampling of probabilities by the block logic110may not be entirely accurate because the incoming luminance value which is compared to the learned histogram has itself a distribution associated it. This can be addressed by assuming the same Gaussian distribution (or other distribution, as appropriate to the particular implementation) and convolving this with the sampled probabilities. The probability of an incoming luminance value belonging to the histogram distribution may then be calculated by the block logic as:

Again, the distribution may be approximated. For example, if computational resources are severely limited, the distribution could be approximated with a box kernel:

The block logic110uses the probability calculated in respect of a luminance value received for a block in order to determine whether a block is likely to represent motion or not. For example, the block logic may form a binary decision as to whether a luminance value received for a block indicates that the block contains motion (i.e. represents foreground in the captured scene), with a decision of foreground motion being Fi=1 and a decision that the block represents background being Fi=0. One approach is to compare the probability that a luminance value belongs to the histogram distribution maintained for that block (i.e. is background) to a predefined or adaptive threshold, T:

A suitable threshold may be identified in any way, including: empirically determined; derived from the sequence of frames (e.g. as one or more statistics generated at the image processor); and adaptively calculated in any suitable manner. This is609inFIG. 6in the case that the threshold is adaptive.

Using a predefined threshold does not typically take into account the possible multi-modal nature of the luminance probability distribution represented by a histogram. The more modes a block may be in, the less overall probability is assigned to each mode meaning a lower threshold value should be used; whereas for a single mode block a higher threshold is more appropriate. It is therefore preferred that an adaptively calculated threshold is used.

For example, a suitable adaptive threshold may be determined as follows. A normalized histogram for a block is sorted into order of bin value as shown inFIG. 5(which corresponds to the histogram ofFIG. 3). This is610inFIG. 6. The bins of the histogram are then summed in order of decreasing bin value so as to identify a value for n which satisfies:
Σk=0hksorted≤Tuser(12)

where Tuseris a predefined threshold. This is611inFIG. 6. This threshold represents the total probability of a luminance value received for a block belonging to the histogram distribution (i.e. representing background in the scene captured by the camera sensor). It will be appreciated that the sorting step may not be explicitly performed and that the bins may be summed in order of decreasing bin value in any suitable manner. It will be appreciated that a high n indicates a spread out histogram whereas a low n indicates a tightly clustered histogram. Note that the 256 bins representing the histogram ofFIG. 3are represented schematically inFIGS. 3 and 5by a smaller number of bins.

InFIG. 5, the sum of the first n bins corresponds to the sum of the bin values in the light shaded region501such that the threshold is crossed at bin502: the value of this bin, which is indicated by line503in the figure, is taken as an adaptive threshold Tadaptive:
Tadaptive=hn+1sorted(13)

This is612inFIG. 6. The adaptive threshold Tadaptivemay be used to identify whether a block represents motion according to:

with a decision that a block represents foreground motion being Fi=1 and a decision that the block represents background being Fi=0. This is613inFIG. 6. A decision generated by the block logic represents a measure of the change in the luminance values received by the motion detector. In other examples the output of the block logic may represent a measure of the change in other input values. Generally a measure of change may be provided in any suitable manner and be expressed as values having any suitable range, including as a binary value as in the present example.

Where the probability of a luminance value belonging to the distribution represented by a histogram of a block is lower than the adaptive threshold, the block logic is configured to identify that block as representing motion in the captured scene. Otherwise the block logic is configured to identify the block as not representing motion in the captured scene. It will be apparent that the adaptive threshold will be lower for more spread out, multi-modal, probability distributions, and higher for more tightly clustered histograms.

By forming a binary decision as to whether each block of a frame is considered to represent motion, block logic110may store a motion matrix114in memory111which represents the block-wise motion determined to be present in a received frame. An example of the information held at stored matrix114is shown inFIG. 7for a frame701. The frame is divided into 16 blocks, with the motion matrix114indicating which of the blocks represents motion in the frame: blocks (e.g.703) which are indicative of motion are labelled in the figure with an ‘M’, and blocks (e.g.702) which are not indicative of motion are not labelled in the figure with an ‘M’. These labels are merely illustrative in the figure; in general any indication of whether or not motion is determined to be present at a block may be used. Motion matrix114may represent motion information for one or more blocks of a frame in any suitable manner, including, for example, as a binary string, an array of values, or as information encoded into or associated with the frame itself. A motion matrix may or may not be a rectangular array of values.

In the above examples, luminance is provided to the motion detector115as the image characteristic on the basis of which motion is assessed in each block of a frame. However, using luminance can under certain conditions suffer from poor performance—for example, changes in lighting conditions in a scene can lead to false positive motion detections. More robust performance may be achieved using a measure of the spread of one or more components for a block (e.g. the red, green and blue channels of an RGB frame) and/or measure of the spread of the luminance of a block. A measure of spread may be any suitable measure of the variation in an image characteristic, such as a variance or a standard deviation.

An example will now be described with respect toFIG. 1in which motion detection is performed by the motion detector on the basis of a spatial standard deviation formed for each of the red, green, and blue channels of a block. The camera module101is configured to provide as image characteristics108for each block of a frame the sum of the squared values over the pixels of the block for each of red, green and blue channels. From these sums it is possible to calculate the spatial standard deviation of each of the red, green and blue channels. For example, the standard deviation of the red channel within a block may be determined according to:

where Riare the red channel pixel values of the pixels of the block, and Npixelsis the number of pixels in the block.

A compound spatial standard deviation for pixel values within a block may be calculated directly from the red, green and blue pixel values of each pixel. Such a compound spatial standard deviation could formed at the binning controller109so as to represent a standard deviation in the luminance of the block. For example, the standard deviation in the luminance of a block may be calculated at the binning controller from red, green and blue pixel values (or their squares) received as image characteristics:

where the luminance of a pixel Yi, (or its square) may, for example, be received from the camera module101as an image characteristic108or calculated from red, green and blue pixel values (or their squares) received for each pixel.

The standard deviation in the luminance of a block σluminancemay be used in place of a luminance value Yiin equations 2 to 14 above. Any of the examples, alternatives, or options described above with respect toFIGS. 1 to 7and equations 1 to 14 to the use of luminance values apply mutatis mutandis to the use of standard deviation (or other measures of spread) in luminance or other image characteristics. Using standard deviation in place of luminance, the binning controller109is configured to maintain, for each block, a probability distribution of the spatial standard deviation in the luminance of the block. Thus, at each frame, the standard deviation received for a block is binned into the learned distribution for that block according to a binning distribution. The block logic110is configured to form a binary decision as to the presence or otherwise of motion in one or more blocks of a sequence of frames. The decision may be formed based on a predefined or adaptive threshold as described above.

In the examples described herein, decision logic116may be configured to use the motion information generated at the motion detector115(e.g. a motion matrix) for one or more blocks of a frame to form a motion output for a frame117. For example, block logic116may be configured to identify motion in a frame when motion is detected in one or more blocks which lie within a defined area of interest, or motion may be identified when a predetermined contiguous number of blocks are indicative of motion. A motion output117for a frame may take any suitable form, including as a binary indication or some measure of the degree of motion observed in a frame (e.g. a number or proportion of blocks which the motion detector115has identified as being representative of motion).

The decision logic may further receive (e.g. along with or included in a motion matrix) measures of the likelihood of block luminance values (e.g. as formed at the block logic) occurring given the frequency distribution represented by a histogram formed by the binning controller for those blocks. This can allow the decision logic to further interpret the motion matrix formed for a frame. For example, the decision logic could be configured to check whether one or more blocks in which motion is not indicated in a motion matrix are surrounded in their respective frame by blocks in which motion is indicated in the motion matrix, and, if that is the case, interpret those surrounded blocks as also being indicative of motion if their respective measures of likelihood lie close to the predefined or adaptive threshold determined by the block logic.

A motion detector115configured according to the principles described herein may be embodied at a low power processor. A motion output for a block or frame (e.g.117) generated by the motion detector or associated decision logic117may be arranged to wake up another processor, such as encoder106. This particular example enables motion-activated recording to be implemented in an energy efficient manner.

A frame comprises a plurality of pixels each having an associated image characteristic. The term pixel is used herein to refer to any kind of image element in respect of which an image characteristic is calculated, sampled, sensed or otherwise formed. A pixel is not limited to having a one-to-one correspondence to a sensing element of a digital camera (e.g. a red, green or blue sensing element or a collection thereof). The term random as used herein encompasses both truly random and pseudorandom distributions, selections, or values; the term pseudorandom encompasses both truly random and pseudorandom distributions, selections, or values.

The camera module and motion detector ofFIG. 1are shown as comprising a number of functional blocks. This is schematic only and is not intended to define a strict division between different logic elements of such entities. Each functional block may be provided in any suitable manner. It is to be understood that intermediate values described herein as being formed by any of the entities of a camera module or motion detector need not be physically generated by the camera module or motion detector at any point and may merely represent logical values which conveniently describe the processing performed by the camera module or motion detector between its input and output.

The flowcharts ofFIGS. 4 and 6are schematic only. The spacing and relative position of the steps in the examples shown in those flowcharts is not to be taken as indicative of the precise time when each step occurs in absolute terms or relative to other steps. The flowcharts merely illustrate an exemplary order in which steps may be performed in accordance with the examples described herein.

An integrated circuit definition dataset may be in the form of computer code, for example as a netlist, code for configuring a programmable chip, as a hardware description language defining an integrated circuit at any level, including as register transfer level (RTL) code, as high-level circuit representations such as Verilog or VHDL, and as low-level circuit representations such as OASIS® and GDSII. Higher level representations which logically define an integrated circuit (such as RTL) may be processed at a computer system configured for generating a manufacturing definition of an integrated circuit in the context of a software environment comprising definitions of circuit elements and rules for combining those elements in order to generate the manufacturing definition of an integrated circuit so defined by the representation. As is typically the case with software executing at a computer system so as to define a machine, one or more intermediate user steps (e.g. providing commands, variables etc.) may be required in order for a computer system configured for generating a manufacturing definition of an integrated circuit to execute code defining an integrated circuit so as to generate the manufacturing definition of that integrated circuit.

An example of processing an integrated circuit definition dataset at an integrated circuit manufacturing system so as to configure the system to manufacture apparatus for binning an input value into an array of bins will now be described with respect toFIG. 8.

FIG. 8shows an example of an integrated circuit (IC) manufacturing system1002which comprises a layout processing system1004and an integrated circuit generation system1006. The IC manufacturing system1002is configured to receive an IC definition dataset (e.g. defining apparatus as described in any of the examples herein), process the IC definition dataset, and generate an IC according to the IC definition dataset (e.g. which embodies apparatus as described in any of the examples herein). The processing of the IC definition dataset configures the IC manufacturing system1002to manufacture an integrated circuit embodying apparatus as described in any of the examples herein.