Method, system and apparatus for updating a scene model

A method of updating a scene model for a foreground segmentation of an input image captured from a camera, is disclosed. One or more visual elements of the input image are determined. A spatial relationship between at least one of the visual elements and the scene model for a foreground segmentation of the input image is determined. The method updates the scene model for determining the foreground segmentation of the input image based on the determined spatial relationship.

REFERENCE TO RELATED PATENT APPLICATION(S)

This application claims the benefit under 35 U.S.C. § 119 of the filing date of Australian Patent Application No. 2013273784, filed Dec. 20, 2013, hereby incorporated by reference in its entirety as if fully set forth herein.

TECHNICAL FIELD

The present disclosure relates to object detection in a video and, in particular, to a method, apparatus and system for segmenting an image. The present disclosure also relates to a computer program product including a computer readable medium having recorded thereon a computer program for foreground segmentation of an image.

BACKGROUND

A video is a sequence of images. The images may also be referred to as frames. The terms ‘frame’ and ‘image’ are used interchangeably throughout this specification to describe a single image in an image sequence, or a single frame of a video. An image is made up of pixels where each pixel is represented by one or more values representing the visual properties at that pixel. For example, in one scenario three (3) values are used to represent Red, Green and Blue colour intensity at the pixel.

Scene modelling, also known as background modelling, involves modelling visual content of a scene, based on an image sequence depicting the scene. A usage of scene modelling is foreground segmentation by background subtraction. Foreground segmentation may also be described by its inverse (i.e., background segmentation). Examples of foreground segmentation applications include activity detection, unusual object or behaviour detection, and scene analysis.

Foreground segmentation allows a video analysis system to distinguish between transient foreground objects and the non-transient background, through scene modelling of the non-transient background, and a differencing operation between that background and incoming frames of video. Foreground segmentation can be performed by using scene modelling and identifying portions of the modelled scene which are either moving, or recently changed/added, or both.

In one scene modelling method, the content of an image is divided into one or more visual elements, and a model of the appearance of each visual element is determined. A scene model may maintain a number of models for each visual element location, each of the maintained models representing different modes of appearance at each location within the scene model. Each of the models maintained by a scene model are known as “mode models” or “background modes”. For example, there might be one mode model for a visual element in a scene with a light being on, and a second mode model for the same visual element at the same location in the scene with the light off.

The description of a mode model may be compared against the description of an incoming visual element at the corresponding location in an image of the scene. The description may include, for example, information relating to pixel values or DCT coefficients. If the description of the incoming visual element is similar to one of the mode models, then temporal information about the mode model, such as age of the mode model, helps to produce information about the scene. For example, if an incoming visual element has the same description as a very old visual element mode model, then the visual element location can be considered to be established background. If an incoming visual element has the same description as a young visual element mode model, then the visual element location might be considered to be background or foreground depending on a threshold value. If the description of the incoming visual element does not match any known mode model, then the visual information at the mode model location has changed and the location of the visual element can be considered to be foreground.

In one method, a visual element is a single pixel. Scene modelling using single pixel visual elements has disadvantages of high storage and computation cost due to pixel level modelling and comparison.

In another method, a group of 8×8 pixels is used as a visual element, referred to as block based scene modelling. The block based scene modelling has lower storage and computation cost compared to single pixel based method but suffers from blocky foreground segmentation. Additionally, the block based method has low robustness against shaky videos, e.g. caused by building tremors for a building mounted camera or caused by the environment for pole mounted cameras.

Hence, there is a need for a scene modelling method which has relatively lower storage and computation cost as well as higher robustness against shaky videos and more accurate object outlines.

SUMMARY

According to one aspect of the present disclosure there, is provided a method of updating a scene model for a foreground segmentation of an input image captured from a camera, the method comprising:

determining one or more visual elements of the input image;

determining a spatial relationship between at least one of the visual elements and the scene model for a foreground segmentation of the input image; and

updating the scene model for determining the foreground segmentation of the input image based on the determined spatial relationship.

According to another aspect, disclosed is an apparatus for updating a scene model for a foreground segmentation of an input image captured by a camera, the apparatus comprising:

means for determining one or more visual elements of the image;

means for determining a spatial relationship between at least one of the visual elements and the scene model for a foreground segmentation of the input image; and

means for updating the scene model for determining the foreground segmentation of the input image based on the determined spatial relationship.

According to another aspect, disclosed is a system for updating a scene model for a foreground segmentation of an input image captured by a camera, the system comprising:

a memory for storing data and a computer program;

a processor coupled to the memory for executing the computer program, the computer program comprising instructions for:

determining one or more visual elements of the input image;

determining a spatial relationship between at least one of the visual elements and the scene model for a foreground segmentation of the input image; and

updating the scene model for determining the foreground segmentation of the input image based on the determined spatial relationship.

Also disclosed is a computer readable medium comprising a computer program stored thereon for updating a scene model for a foreground segmentation of an input image captured by a camera, the program comprising:

code for determining one or more visual elements of the input image;

code for determining a spatial relationship between at least one of the visual elements and the scene model for a foreground segmentation of the input image; and

code for updating the scene model for determining the foreground segmentation of the input image based on the determined spatial relationship.

Other aspects of the invention are also disclosed.

DETAILED DESCRIPTION INCLUDING BEST MODE

Where reference is made in any one or more of the accompanying drawings to steps and/or features that have the same reference numerals, those steps and/or features have for the purposes of this description the same function(s) or operation(s), unless the contrary intention appears.

A computer-implemented method, system, and computer program product for updating/modifying a scene model is described below. The updated/modified scene model may then be used in processing of a video sequence comprising a plurality of images.

FIGS. 1 and 2collectively form a schematic block diagram of a camera system101including embedded components, upon which foreground/background segmentation methods to be described are desirably practiced. The camera system101may be, for example, a digital camera or a mobile phone, in which processing resources are limited. Nevertheless, the methods to be described may also be performed on higher-level devices such as desktop computers, server computers, and other such devices with significantly larger processing resources.

The camera system101is used to capture input images representing visual content of a scene appearing in the field of view (FOV) of the camera system101. Each image captured by the camera system101comprises a plurality of visual elements. A visual element is defined as an image sample. In one arrangement, the visual element is a pixel, such as a Red-Green-Blue (RGB) pixel. In another arrangement, each visual element comprises a group of pixels. In yet another arrangement, the visual element is an 8 by 8 block of transform coefficients, such as Discrete Cosine Transform (DCT) coefficients as acquired by decoding a motion-JPEG frame, or Discrete Wavelet Transformation (DWT) coefficients as used in the JPEG-2000 standard. The colour model is YUV, where the Y component represents luminance, and the U and V components represent chrominance.

As seen inFIG. 1, the camera system101comprises an embedded controller102. In the present example, the controller102has a processing unit (or processor)105which is bi-directionally coupled to an internal storage module109. The storage module109may be formed from non-volatile semiconductor read only memory (ROM)160and semiconductor random access memory (RAM)170, as seen inFIG. 2. The RAM170may be volatile, non-volatile or a combination of volatile and non-volatile memory.

The camera system101includes a display controller107, which is connected to a display114, such as a liquid crystal display (LCD) panel or the like. The display controller107is configured for displaying graphical images on the display114in accordance with instructions received from the controller102, to which the display controller107is connected.

The camera system101also includes user input devices113which are typically formed by a keypad or like controls. In some implementations, the user input devices113may include a touch sensitive panel physically associated with the display114to collectively form a touch-screen. Such a touch-screen may thus operate as one form of graphical user interface (GUI) as opposed to a prompt or menu driven GUI typically used with keypad-display combinations. Other forms of user input devices may also be used, such as a microphone (not illustrated) for voice commands or a joystick/thumb wheel (not illustrated) for ease of navigation about menus.

As seen inFIG. 1, the camera system101also comprises a portable memory interface106, which is coupled to the processor105via a connection119. The portable memory interface106allows a complementary portable memory device125to be coupled to the electronic device101to act as a source or destination of data or to supplement the internal storage module109. Examples of such interfaces permit coupling with portable memory devices such as Universal Serial Bus (USB) memory devices, Secure Digital (SD) cards, Personal Computer Memory Card International Association (PCMIA) cards, optical disks and magnetic disks.

The camera system101also has a communications interface108to permit coupling of the camera system101to a computer or communications network120via a connection121. The connection121may be wired or wireless. For example, the connection121may be radio frequency or optical. An example of a wired connection includes Ethernet. Further, an example of wireless connection includes Bluetooth™ type local interconnection, Wi-Fi (including protocols based on the standards of the IEEE 802.11 family), Infrared Data Association (IrDa) and the like.

Typically, the controller102, in conjunction with an image sensing device110, is provided to perform the functions of the camera system101. The image sensing device110may include a lens, a focus control unit and an image sensor. In one arrangement, the sensor is a photo-sensitive sensor array. As another example, the camera system101may be a mobile telephone handset. In this instance, the image sensing device110may also represent those components required for communications in a cellular telephone environment. The image sensing device110may also represent a number of encoders and decoders of a type including Joint Photographic Experts Group (JPEG), (Moving Picture Experts Group) MPEG, MPEG-1 Audio Layer 3 (MP3), and the like. The image sensing device110captures an input image and provides the captured image as an input image.

Methods described below may be implemented using the embedded controller102, where the processes ofFIGS. 2 to 17may be implemented as one or more software application programs133executable within the embedded controller102. The camera system101ofFIG. 1implements the described methods. In particular, with reference toFIG. 2, the steps of the described methods are effected by instructions in the software133that are carried out within the controller102. The software instructions may be formed as one or more code modules, each for performing one or more particular tasks. The software may also be divided into two separate parts, in which a first part and the corresponding code modules performs the described methods and a second part and the corresponding code modules manage a user interface between the first part and the user.

The software133of the embedded controller102is typically stored in the non-volatile ROM160of the internal storage module109. The software133stored in the ROM160(i.e., the ROM160has the software133stored thereon) can be updated when required from a computer readable medium. The software133can be loaded into and executed by the processor105. In some instances, the processor105may execute software instructions that are located in RAM170. Software instructions may be loaded into the RAM170by the processor105initiating a copy of one or more code modules from ROM160into RAM170. Alternatively, the software instructions of one or more code modules may be pre-installed in a non-volatile region of RAM170by a manufacturer. After one or more code modules have been located in RAM170, the processor105may execute software instructions of the one or more code modules.

The application program133is typically pre-installed and stored in the ROM160by a manufacturer, prior to distribution of the electronic device101. However, in some instances, the application programs133may be supplied to the user encoded on one or more CD-ROM (not shown) and read via the portable memory interface106ofFIG. 1Aprior to storage in the internal storage module109or in the portable memory125. In another alternative, the software application program133may be read by the processor105from the network120, or loaded into the controller102or the portable storage medium125from other computer readable media. Computer readable storage media refers to any non-transitory tangible storage medium that participates in providing instructions and/or data to the controller102for execution and/or processing. Examples of such storage media include floppy disks, magnetic tape, CD-ROM, a hard disk drive, a ROM or integrated circuit, USB memory, a magneto-optical disk, flash memory, or a computer readable card such as a PCMCIA card and the like, whether or not such devices are internal or external of the device101. Examples of transitory or non-tangible computer readable transmission media that may also participate in the provision of software, application programs, instructions and/or data to the device101include radio or infra-red transmission channels as well as a network connection to another computer or networked device, and the Internet or Intranets including e-mail transmissions and information recorded on Websites and the like. A computer readable medium having such software or computer program recorded on it is a computer program product.

The second part of the application programs133and the corresponding code modules mentioned above may be executed to implement one or more graphical user interfaces (GUIs) to be rendered or otherwise represented upon the display114ofFIG. 1. Through manipulation of the user input device113(e.g., the keypad), a user of the device101and the application programs133may manipulate the interface in a functionally adaptable manner to provide controlling commands and/or input to the applications associated with the GUI(s). Other forms of functionally adaptable user interfaces may also be implemented, such as an audio interface utilizing speech prompts output via loudspeakers (not illustrated) and user voice commands input via the microphone (not illustrated).

FIG. 2illustrates in detail the embedded controller102having the processor105for executing the application programs133and the internal storage109. The internal storage109comprises read only memory (ROM)160and random access memory (RAM)170. The processor105is able to execute the application programs133stored in one or both of the connected memories160and170. When the electronic device101is initially powered up, a system program resident in the ROM160is executed. The application program133permanently stored in the ROM160is sometimes referred to as “firmware”. Execution of the firmware by the processor105may fulfil various functions, including processor management, memory management, device management, storage management and user interface.

The processor105typically includes a number of functional modules including a control unit (CU)151, an arithmetic logic unit (ALU)152and a local or internal memory comprising a set of registers154which typically contain atomic data elements156,157, along with internal buffer or cache memory155. One or more internal buses159interconnect these functional modules. The processor105typically also has one or more interfaces158for communicating with external devices via system bus181, using a connection161.

The application program133includes a sequence of instructions162through163that may include conditional branch and loop instructions. The program133may also include data, which is used in execution of the program133. This data may be stored as part of the instruction or in a separate location164within the ROM160or RAM170.

In general, the processor105is given a set of instructions, which are executed therein. This set of instructions may be organised into blocks, which perform specific tasks or handle specific events that occur in the electronic device101. Typically, the application program133waits for events and subsequently executes the block of code associated with that event. Events may be triggered in response to input from a user, via the user input devices113ofFIG. 1, as detected by the processor105. Events may also be triggered in response to other sensors and interfaces in the electronic device101.

The execution of a set of the instructions may require numeric variables to be read and modified. Such numeric variables are stored in the RAM170. The disclosed method uses input variables171that are stored in known locations172,173in the memory170. The input variables171are processed to produce output variables177that are stored in known locations178,179in the memory170. Intermediate variables174may be stored in additional memory locations in locations175,176of the memory170. Alternatively, some intermediate variables may only exist in the registers154of the processor105.

The execution of a sequence of instructions is achieved in the processor105by repeated application of a fetch-execute cycle. The control unit151of the processor105maintains a register called the program counter, which contains the address in ROM160or RAM170of the next instruction to be executed. At the start of the fetch execute cycle, the contents of the memory address indexed by the program counter is loaded into the control unit151. The instruction thus loaded controls the subsequent operation of the processor105, causing for example, data to be loaded from ROM memory160into processor registers154, the contents of a register to be arithmetically combined with the contents of another register, the contents of a register to be written to the location stored in another register and so on. At the end of the fetch execute cycle the program counter is updated to point to the next instruction in the system program code. Depending on the instruction just executed this may involve incrementing the address contained in the program counter or loading the program counter with a new address in order to achieve a branch operation.

Each step or sub-process in the processes of the methods described below is associated with one or more segments of the application program133, and is performed by repeated execution of a fetch-execute cycle in the processor105or similar programmatic operation of other independent processor blocks in the electronic device101.

A method800of updating a scene model for a foreground and background segmentation of an input image captured by the camera system101is described below with reference toFIG. 8. The method800uses foreground segmentation. The method800may be implemented as one or more software code modules of the software application program133resident in the storage module109and being controlled in its execution by the processor105. As described below, the scene model is based on superpixel segmentation.

The method800performs scene modelling using dynamic visual elements for foreground segmentation of an input image captured by the camera system101. The term ‘dynamic’ refers to the property of the visual element that specifies that the group of pixels belonging to a visual element for an input image is decided based on the contents of the input image. That is, the size and shape of a visual element is not pre-decided and depends on the contents of the input image.

The method800begins at receiving step810where an input image is received from the image sensing device110under execution of the processor105. After receiving the input image, the method800moves to step820. The input image may be stored in RAM170.

Then at determining step820, the processor105executes a superpixel based image segmentation method on the image received at step810to determine dynamic superpixel visual elements for the image. The superpixel segmentation of an image as a visual element segmentation is a type of image over segmentation where salient features, such as pixels sharing similar colour, of a pixel-based representation are preserved.

FIG. 3is a flow diagram showing a method300of segmenting an input image, as executed at step820, to produce a predetermined number (e.g., one or more) of superpixel segmentations (or superpixel visual elements) from the input image received at step810. The method300may be implemented as one or more software code modules of the software application program133resident in the storage module109and being controlled in its execution by the processor105.

The method300begins at creating step305, where seed points are created under execution of the processor105. Seed points are locations from where the geodesic transform process is started, as described below in relation to step350.

The predetermined number of super-pixels (represented as Ns) is determined based on image dimension and scene characteristics. For example, in one method, superpixels of approximate size, S, equals eighty (81) pixels are used. For such sized superpixels, seed points are initialised at a square grid at regular grid spacing of nine (9) pixels. The seed points are locations used in step350to generate superpixel segments.

Grid based seed points will now be described with reference toFIGS. 7A to 7D.

FIG. 7Ashows pixels in an input image700as black circles.FIG. 7Bshows the input image100.FIG. 7Cshows the image700with four (4) grid points as white circles at the intersection of grids705,706,707and708. The grids points ofFIG. 7Cmay be used as seed points for superpixel segmentation.FIG. 7Dshows the image700after a resulting superpixel segmentation which has divided the image into four (4) segments701,702,703,704.

After creating seed points, the method300moves to determining step310. At step310, a derived image measuring the strength of scene boundary is determined from the input image received at step810. In one arrangement, the derived image is an image of local gradient energy of the input image. The gradient energy image is the sum of the gradient energy in two perpendicular directions such as the x- and y-directions. In one arrangement, the gradients along x- and y-directions are computed using Gaussian derivative filters on the input image. The directional Gaussian derivative filters usually have the same scale σ such as σ=1 pixel.

If the input image received at step810is a multi-channel image such a Red-Green-Blue (RGB) image from a consumer digital camera, in one arrangement, the gradient energy image is computed as the sum of the gradient energy images from all channels. In another arrangement, if the input image received at step810is a multi-channel input image, then the input image is converted to a perceptually linear colour space such as the CIE L*-a*-b* colour space before gradient energy computation to enhance the differences amongst different colours. In another arrangement, the derived image is the local gradient energy raised to a power α, where α>0.5.

The method300then proceeds to adding step320, where a fixed scalar offset is added to the derived image under execution of the processor105. The value of the fixed constant offset typically depends on the dynamic range of the derived image. In one arrangement, the fixed offset is set to the greater of the median intensity of the derived image, and dynamic range of the derived image times 0.0001. The purpose of the fixed offset addition step is described below with reference to step350.

Then at adding step330, a random noise offset, also known as random noise pattern, is added to at least a portion of the derived image under execution of the processor105. The image portion to which noise is added may be region of constant local intensity in the derived image. The purpose of the noise addition step330will be described below with reference to step340. The magnitude of the added noise is typically small such as to incur an imperceptible change to the derived image. In one arrangement, a Gaussian random noise with zero mean and standard deviation of 0.0001 times the dynamic range of the derived image is used. The random noise may be generated with a pre-determined random seed. In one arrangement, if multiple frames of a video captured by a static camera are segmented sequentially, the same random seed is used to produce coherent noise across multiple frames. The resulting image after noise and offset addition may be referred to as a “boundary cost image”.

The method300continues at perturbing step340, where the location of the gridded seed points are perturbed away from strong image boundaries, under execution of the processor105. The seed perturbation is necessary because seed points located right on top of a strong boundary tend to produce tiny superpixels, whose sizes are proportional to the full-width half-maximum of the cross-section of the boundary edge. The perturbed location of a grid point can be the location of the pixel with minimum boundary measure within a local neighbourhood of the grid point. In one arrangement, the local neighbourhood is a 3×3 pixel window around the grid point.

The method300then proceeds to determining step350, where a geodesic distance transform on a geodesic space defined by the boundary cost image given the local seeds generated in step340. A geodesic distance between two points is defined as total cost along a geodesic path between the two points, where a geodesic path is the path of minimum integrated cost along the path. If the cost image is constant and positive, the geodesic path between any two points is a straight line. The boundary cost image is usually not flat since there are visual structures in the input image. The geodesic path between two points on a non-flat cost image is therefore not a straight path. The geodesic distance transform of a cost image is the total cost along a minimum cost path from each pixel to a nearest seed in the geodesic space. A by-product of the geodesic distance transform is a nearest seed transform, which associates each pixel in the image with a nearest seed in the geodesic space. That is, the nearest seed transform partitions the set of all pixels in the cost image into groups of connected pixels, each group sharing a common seed point. The pixels associated with a seed point form a connected segment, which forms a superpixel. Hence, the nearest seed transform is a superpixel segmentation from the given seeds.

A chamfer algorithm used to compute a geodesic distance transform from a non-negative boundary cost image f(x,y) and a set of seed points in step350will now be described in detail by way of example with reference toFIGS. 4A, 4B, 4C and 4D.

As seen inFIG. 4A, x,402and y,403, are the Cartesian coordinates of a sampled boundary cost image. The chamfer algorithm determines an approximation of the geodesic distance transform by approximating any path between two pixels by a discretised path between the two pixels. A discretised path comprises line segments connecting a pixel with one of eight neighbouring pixels within a 3×3 neighbourhood. A minimum cost path from a pixel to a nearest seed, which is also located at a pixel, therefore goes through a series of pixels along the discretised path. All pixels along the discretised minimum cost path share a common nearest seed. As a result, the nearest seed of a pixel is most of the time also the nearest seed of a neighbouring pixel (except when nearest seed of the pixel is located at the pixel itself). Using the property of common nearest seed amongst neighbouring pixels, the chamfer algorithm tries to propagate the nearest seed and the geodesic distance from one pixel to immediate neighbours of the pixel within a 3×3 neighbourhood.

The chamfer algorithm initially assigns a very large distance (such as infinity) to every pixel in the geodesic distance transform image401, except at seed points where the distance is zero. The distance transform image is then updated by several scans over the distance transform image and the boundary cost image, each scan propagating the distance from four causal neighbours to a current pixel P.

The direction of the scans alternate between two directions: from top to bottom, left to right as shown inFIG. 4Aand from bottom to top, right to left as shown inFIG. 4B. Additional scan directions such as from top to bottom, right to left as shown inFIG. 4Cand from bottom to top, left to right as shown inFIG. 4Dcan also be used.

During each scan, for example the top-down, left-right scan409inFIG. 4A, the distance transform d(x1,y1) of a current pixel404is updated using the distance transform of four causal neighbours of the pixel404at location (x1−1,y1−1),405, at location (x1, y1−1),406, at location (x1+1,y1−1),407, and at location (x1−1,y1+1),408, by the following distance propagation Equation (1), as follows:

(i) a=0.9619 and b=1.3604 are optimal chamfer coefficients for the four (4)-connected neighbours406,408and diagonal neighbours405,407, respectively.

(ii) f(x1,y1) is the boundary cost at the current pixel (x1, y1).(iii) The ‘min’ operator selects the minimum distance amongst the four distances propagated from the four causal neighbours.

The causal neighbour from which the current pixel404gets a corresponding minimum geodesic distance from also passes on a nearest seed to the current pixel. Out of bound neighbouring pixels (i.e., neighbouring pixels whose coordinates are outside the coverage area of the input image) are ignored in distance propagation Equation (1).

After a forward pass409is performed over the whole distance transform image401, a backward pass419is then applied to the updated distance transform image. InFIG. 4B, the distance transform d(x1,y1) of a current pixel414is updated using the distance transform of four causal neighbours of the pixel414at location (x1+1,y1+1),415, at location (x1,y1+1),416, at location (x1−1,y1+1),417, and at location (x1+1,y1),418, in a similar fashion to the forward pass409in accordance with Equation (2), as follows:

Similarly, inFIG. 4C, a top-down, right to left scan429propagates the distance transform from four causal neighbours of pixel424at location (x1+1,y1−1),425, at location (x1,y1−1),426, at location (x1−1,y1−1),427, and at location (x1+1,y1)428to the current pixel424at location (x1,y1) in accordance with Equation (3), as follows:

InFIG. 4D, a bottom-up, left to right scan439propagates the distance transform from four causal neighbours at location (x1−1,y1+1),435, at location (x1,y1+1),436, at location (x1+1,y1+1),437, at location (x1−1,y1),438, to the current pixel434at location (x1,y1), in accordance with Equation (4), as follows:

The chamfer geodesic distance transform algorithm requires only a few passes over the boundary cost image. In one arrangement, a forward pass409followed by a backward pass419followed by another pair of backward429and forward439passes may be used to produce a non-fragmented nearest seed transform.

The reason for adding a fixed offset to the derived image in step320is now described within the framework of a geodesic distance transform in step350. If the cost image is constant and positive, the geodesic path between any two points is a straight line, which is the shortest path in the Euclidean space. The geodesic distance transform on a flat space is therefore equivalent to the Euclidean distance transform. The nearest seed transform then produces a polygon tessellation of the 2-D image space which is also known as a Voronoi tessellation. The polygon segments of a Voronoi tessellation are called Voronoi cells. Given the same set of seeds, Voronoi tessellation produces the most regular sized and shaped segments that completely cover the 2-D image space. The boundary cost image is usually not flat since there are visual structures in the input image. As a result, the geodesic paths between any two points are usually not straight. The noisier the boundary cost image is, the jaggier the geodesic paths become.

Irregular geodesic paths produce irregular nearest seed transform, therefore irregular superpixel segmentation. To make geodesic superpixels become more regular as the Voronoi cells, the boundary cost image is altered such that geodesic paths become straighter. A constant positive offset added to the boundary cost image make geodesic superpixels more regular as the total cost over any path is now increased by the length of the path times the constant offset. Jaggier paths therefore have a larger total cost than straighter paths. Straighter paths are then more likely to be a minimum cost path, which improves the regularity of the tessellation.

At decision step360, the processor105is used to determine whether or not to perform superpixel refinement by seed re-centroiding followed by another iteration of geodesic distance transform. After step350, the produced superpixels are already regular due to the placement of seeds at local minima of the boundary cost image and the constant offset added to the boundary cost image as described in steps340and350, respectively. However, depending on the applications, more regular superpixels may be desirable.

One characteristic of a regular-shaped superpixel is that the centroid of the superpixel coincides with the seed of the superpixel, where the centroid of a segment is located at average coordinates of all pixels within the segment. By iteratively re-positioning the seeds to the centroids of previously computed superpixels (rounded to the nearest pixels) and by re-growing the superpixels using a geodesic distance transform, the superpixel segmentation can become even more regular. If the decision is to perform further re-centroidal refinement, then the method300proceeds from step360to step370. Otherwise, the method300concludes.

In one arrangement, the decision to continue superpixel re-centroidal refinement at step360may be predetermined based on a pre-determined number of iterations of steps350,360and370, (e.g., four (4). The number of iterations is reduced by one every time step370is executed. Eventually when the number of iterations reduces to zero, the decision at step360will be to exit the loop and the method300concludes.

In another arrangement, the decision to perform further superpixel re-centroidal refinement at step360is determined automatically by the algorithm after a convergence test. If after seed re-centroiding, the locations of the new seeds do not differ from the locations of old seeds, the iterative seed re-centroiding process of steps350,360and370is said to have converged. Once the seed re-centroiding process is converged, the superpixels attain their maximally possible regularity. The decision at step360is then to exit the loop and the method300concludes.

At step370, the seed points are reintialised to the centroids of previously determined superpixels as described above.

Other methods of determining the superpixel segmentations may be executed at step820, such as Simple Linear Iterative Clustering (SLIC). However, for segmentation of successive frames in a video, and for use with a scene model, regularity in shape is an important characteristic for consistent segmentation over time. The superpixel segmentation used in the method800and other methods may determine regularly shaped segments for consistent segmentation.

Returning to the method800, after step820, the method800progresses to extracting step830. At extracting step830, visual features of the dynamic visual elements determined at step820are extracted under execution of the processor105. The dynamic visual elements will be referred to below as “superpixel visual elements”. In one arrangement, the input image is in Red, Green, Blue (RGB) colour format so that there are three (3) values representing red, green and blue colour values for each pixel.

In one arrangement, the YCbCr colour domain is used for feature representation at step830. In a YCbCr colour domain arrangement, the image received at step810is converted from RGB to the YCbCr color domain in accordance with Equation (5) as follows:

Equation (5) may be used for eight (8) bit R, G and B values. To represent visual characteristics of a visual element (i.e. the colour distribution of pixels in a visual element (e.g. R, G and B colour values)), visual features are determined. Let I·{right arrow over (V)}krepresent a visual feature vector for a kthvisual element of the input image (I) received at step810. In one arrangement, the mean of colour values of all pixels belonging to a superpixel visual element is used as a visual feature vector in accordance with Equation (6), as follows:
I·{right arrow over (V)}k={V1input,k,V2input,k,V3input,k}  (6)
where,

In another arrangement, multi-variate Gaussian mixture models are used at step830to fit colour values of pixels in a superpixel visual element if the pixel colours do not satisfy a univariate normality test of kurtosis and skewness.

In another arrangement, apart from visual colour features, features to describe shape of a superpixel visual element may also be used at step820. For example, length of a superpixel segment in four (4) directions, 0 degrees, 90 degrees, 180 degrees and 270 degrees from horizontal x-axis, may be represented as shown inFIG. 9for the superpixel visual element703by arrows901,902,903, and904respectively. In another arrangement, eight (8) directions may be used at step830to represent shape of a superpixel visual element. Shape of a superpixel visual element may also be represented by an ellipse approximation at step830.

The output of step830is a list of visual feature vectors for all superpixel visual elements determined at step820for the input image. The list of visual feature vectors may be stored in RAM170. In one arrangement, the list of visual feature vectors representing the extracted visual features determined at step820is arranged in a row-major order arrangement of two dimensional (2D) gridded seed points. For the example input image700ofFIGS. 7A to 7D, the list visual feature vectors includes superpixel visual element701as a first element, visual element702as a second element, visual element703as a third element and visual element704as a fourth element.

After extracting visual features of the input image the method800moves to decision step840. If the input image received at step810is a first image (or frame) to be processed, then the method800moves to initialising step850. Otherwise, if the input image is not the first image (frame) to be processed, then the method moves to matching step860.

If the input image received at step810is the first image (frame) to be processed, at step850, a scene model for the input image is initialised within RAM170using the visual features determined at step830for the input image. The scene model uses superpixel visual elements as building blocks to represent scene activity. In one arrangement, the number of element model sets in the scene model is initialised to be the same as the total number of superpixel visual elements used to segment the input image.FIG. 10shows a scene model1001containing four (4) element model sets (e.g.,1002). Each list index represents a corresponding superpixel visual element position arranged in the same order as the list of the visual features determined at step830.

An element model set contains one or more element models. In the example ofFIG. 10, the element model set—(e.g.,1002) refers to an adaptive representation of a region. As seen inFIG. 10, the element model set1002contains visual information including visual features as well as temporal information about a region surrounding the seed point associated with the list index as shown respectively by visual descriptor1003and temporal descriptor1004. Each of the element model sets (e.g.,1002) is associated with a corresponding seed point. For example, the element model set1is associated with a seed of the superpixel visual element701, the element model set2is associated with a seed of the superpixel visual element702, the element model set3is associated with a seed of the superpixel visual element703, and the element model set4is associated with a seed of the superpixel visual element704.

Each element model of an element model set may be referred to as a “mode” or “mode model”. For ease of explanation, each element model of an element model set will be referred to below as a mode. The number of modes in an element model set depends on scene characteristics. In a scene with lots of activities and changing background, more modes are required for scene modelling. In one arrangement, a maximum of five (5) modes is used for each element model set (e.g.,1002). For a given image (e.g., as indicated by a frame number), one or more modes may be active. As part of a scene model update performed at step870, as described below, scene model management is performed when all modes are active and a new mode needs to be created.

The temporal descriptor1004contains temporal information related to the element model set1002. In one example arrangement, the temporal information includes:

(i) Cf: when the mode was created,

(ii) Lmf: when the mode was matched with an input visual element in an input image last,

(iii) Mc: how many times the mode has been matched with an input visual element in an input image,

(iv) Df: frame number when the model is marked for deletion.

A mode is either a foreground mode or a background mode at a point in time. A mode which is a foreground mode may become a background mode over time.

The scene model (e.g.,1001) is initialised at step850using the visual features. One mode for each superpixel visual element model is set using corresponding visual features of the input image. For example, the visual descriptor of “Mode1” of Element Model Set1002is set to the visual features of superpixel visual element701. The temporal features of Mode1are initially set as follows:
Cf=1
Lmf=1
Mc=1

Frame number Df for deletion of a mode is determined as a function of match counts Mc and last match frame Lmf. In one arrangement, the Frame number Df may be determined in accordance with Equation (7), as follows:
Df=Lmf+A*Mc+B(7)
where, A and B are pre-defined user parameters. In one arrangement, A=16 and B=30 images (frames) for video sequences captured at ten (10) images (frames) per second. Using the above expression, Df=47 images (frames) is set during scene initialisation.

The temporal features for all other modes are initially set to zero to signal that other modes are inactive. Inactive modes do not contain scene related information.

The other element model sets (i.e., Element Model Set2, Element Model Set3, and Element Model Set4) are also initialised in the same manner. After finishing the scene model initialisation, the method800moves to matching step860.

At matching step860, the input image is matched to the scene model configured within RAM170and foreground/background status of the superpixel visual elements of the input image is determined. A method500of matching a scene model to an image, as executed at step860, will now be described with reference toFIG. 5. The method500may be implemented as one or more software code modules of the software application program133resident in the storage module109and being controlled in its execution by the processor105.

The method500begins at a first decision step510, where the processor105is used to check if all the input superpixel visual elements of the input image have been compared to the scene model. If all input superpixel visual elements have been compared to the scene model, then the method500concludes. Otherwise, the method500proceeds to step530.

Then at selecting step530, under execution of the processor105, a next input superpixel visual element is selected from the list of superpixel visual elements generated at step830.

The method500then continues to determining step540, where the spatial relationship between at least the input superpixel visual element selected at step530and element model sets of the scene model for the input image is determined under execution of the processor105. At step540, the processor105is used to select a set of seed points whose corresponding element model sets will be used to compare to the superpixel visual element selected at step530. The spatial relationship is determined at step540using the seed points selected in accordance with the method1100.

A method1100of selecting a seed point, as executed at step540, will be described below with reference toFIG. 11. The method1100may be implemented as one or more software code modules of the software application program133resident in the storage module109and being controlled in its execution by the processor105.

The method1100begins at determining step1101, where the centroid of the superpixel visual element selected at step530is determined under execution of the processor105. Then the method1100continues to determining step1102, where the processor105is used to determine a number of seed points in the selected visual element. There are two possible cases which are checked at decision step1103, as follows:

1. There are one or more seed points which lie inside the selected superpixel visual element in the input image received at step810.

2. There are no seed points which lie inside the selected superpixel visual element in the input image received at step810.

If the number of seed points lying inside the selected superpixel visual element is zero, then the method1100proceeds to selecting step1104. Otherwise, the method1100proceeds to selecting step1106. At step1104, the processor105is used for selecting the nearest seed point in a neighbourhood outside the selected superpixel visual element to access the associated element model sets. In one arrangement, at step1104, all visual elements surrounding the input superpixel visual element to be checked are used to select a nearest seed point in each of the visual elements neighbouring the selected visual element. In another arrangement, a plurality of seed points (e.g., all seed points) in the visual elements neighbouring the selected visual element are selected at step1104.

Following step1104, the method1100proceeds to step storing step1105, where the seed points selected at step1104are stored in RAM170for use in the method500.

As described above, if the number of seed points lying inside the selected superpixel visual element is non-zero at step1103, then the method1100continues to selecting step1106. As step1106, the nearest seed point to the centroid of the selected superpixel visual element is selected to access the associated element model sets of the scene model for the input image. In another arrangement, a plurality of seed points (e.g., all seed points) which lie within the superpixel visual element are selected at step1106to access associated element model sets.

The method1100then proceeds to storing step1107where the seed points selected at step1106are stored in RAM170for use in the method500.

The determination of the spatial relationship between the input superpixel visual element selected at step530and element model sets of the scene model, as executed at step540, will now be further described with reference toFIG. 14andFIG. 15.

FIG. 14Ashows an example of a first image (frame)1450of a scene, as an input image in a video sequence, where the image1450has three (3) structures1401,1402and1403. In the example ofFIG. 14Athe image1450is received at step810and processed in accordance with the method1100.

FIG. 14Bshows grid points and grid based seed points determined for the example image1450. In the example ofFIG. 14B, there are a total of eighteen (18) seed points marked from1400-1to1400-18in row-major order. As seen inFIG. 14B, seed points 1 to 18 are marked as1400-1to1400-18. The seed points1400-1to1400-18are initial points determined using method300described inFIG. 3.

FIG. 14Cshows a possible superpixel segmentation of the example image1450(as determined at step820) which is used to initialise the scene model for the image1450(as at step850). For example, segment1410represents a superpixel visual element corresponding to seed1400-1, segment1415represents a superpixel visual element corresponding to seed1400-2and so on. The initialised scene model for the example image1450will have eighteen (18) visual element model sets (i.e., visual element model set one (1) to visual element model set eighteen (18)) where each visual element model is initialised using characteristics from a corresponding superpixel visual element as described in step850. For example, in the example ofFIG. 14C, visual element model1is initialised using visual characteristics of superpixel visual element1410.

FIG. 15Ashows a second image (frame)1500as an input image of the scene in the video sequence ofFIG. 14A. The image1500comprises an object1501in the scene. In the example ofFIG. 15A, the second image (frame)1500is captured after the first image (frame)1450.FIG. 15Bshows a possible superpixel segmentation of the image1500shown inFIG. 15A(as determined at step820). The superpixel visual elements in the image1500are marked from1510-1to1510-18. In the image1500, there are two types of superpixel visual elements:

1. Superpixel visual elements which have non-zero seed points which lie inside the visual element: The visual elements1510-1,1510-2,1510-3,1510-4,1510-5,1510-6,1510-7,1510-8,1510-9,1510-10,1510-11,1510-13,1510-14,1510-15,1510-16,1510-17and1510-12have one (1) or more seed points which lie within the superpixel visual element.

2. Superpixel visual elements which have zero (0) seed points which lie inside the visual element: The visual element1510-18has zero seed points.

A spatial relationship may be determined for scene model matching for the input image1500inFIG. 15B, according to method1100described inFIG. 11. A spatial relationship is determined with respect to the scene model initialised at step850, using the image1450shown inFIG. 14C.

In one arrangement, for a superpixel visual element in the input image1500, all visual element model sets corresponding to the seed points which lie within the superpixel visual element are selected in the method1100. For example, for superpixel visual element1510-1, visual element model set1corresponding to seed point1400-1is selected. Similarly, for superpixel visual elements1510-2,1510-3,1510-4,1510-5,1510-6,1510-7,1510-8,1510-9,1510-10,1510-11,1510-13,1510-14,1510-15,1510-16and1510-17, visual element model set two (2), three (3), four (4), five (5), six (6), seven (7), eight (8), nine (9), ten (10), eleven (11), thirteen (13), fourteen (14), fifteen (15), sixteen (16) and seventeen (17) are respectively selected. For superpixel visual element1510-12, there are two (2) seed points1400-12,1400-18, which lie inside the superpixel visual element1510-12. Thus, superpixel visual element model sets corresponding to both seed points1510-12and1510-18are selected for matching.

The superpixel visual element1510-18does not have any seed points which lie within the superpixel visual element1510-18. In the example of element1510-18, all neighbouring superpixel visual elements are identified firstly by boundary pixel analysis for all boundary pixels of the superpixel visual element1510-17and by identifying superpixel visual elements of eight (8)-connected neighbouring pixels of the boundary pixels. As shown in theFIG. 15B, superpixel visual elements1510-12,1510-6, and1510-17are determined as neighbouring superpixel visual elements. The seeds points which lie in the neighbouring superpixel visual elements are seed points1400-6,1400-12,1400-17, and1400-18. The visual element model sets corresponding to the seed points1400-6,1400-12,1400-17and1400-18which lie within the neighbouring superpixel visual elements are selected for matching in the method1100.

In another arrangement, a centroid of a superpixel visual element is firstly selected by using x and y locations of all pixels which lie within the superpixel visual element. For example,FIG. 5Bshows the centroid1511of the superpixel visual element1510-12. The seed point which is nearest to the centroid1511is identified. In one arrangement, the nearest seed point to the centroid1511is determined using Euclidean distance formulation. In another arrangement, the nearest seed point to the centroid1511is determined using sum of absolute difference distance formulation. In one example shown inFIG. 15B, seed point1400-12is the closest seed point to centroid1511using Euclidean distance formulation. Thus, the visual element model set twelve (12) is selected for scene model matching.

The set of seed points at either of steps1104or1106(i.e., depending on step1103) are used to access all associated element model sets from the scene model for matching. The output of spatial relationship matching as executed at step540is the set of element model sets associated with the selected seed points (i.e., the seed points selected at either of steps1104or1106).

The method500proceeds from step540to step determining step550, where all modes in the set of element model sets of the scene model are used to compare the superpixel visual element selected at step530to determine a best matched mode. The input to the step550is a set of element model sets of the scene model for the input image. Each element model set consists of multiple modes (e.g., Element Model Set1consists of Modes1to5as seen inFIG. 10). A method1200of determining a best matching mode, as executed at step550, will now be described with reference toFIG. 12. In the method1200, the input modes are compared to the superpixel visual element selected at step530.

The method1200may be implemented as one or more software code modules of the software application program133resident in the storage module109and being controlled in its execution by the processor105. The method1200is used to determine the best matching mode that matches the superpixel visual element selected at step530in the input image received at step810.

The method1200begins at a first decision step1210, where the processor105is used to check if all the modes in the set of element models associated with a selected seed point (i.e., a seed point selected at step1104or1106) have been compared to the input superpixel visual element in the input image (i.e., Are there unprocessed modes for the input visual element?). If all of the modes have been compared to the input visual element, then the method1200continues to the select best matching mode step1260.

If there are remaining modes to be compared, then the method1200continues on to selecting step1220where an unprocessed mode is selected under execution of the processor10.

Then at a second decision step1230, if the selected mode is active, based on temporal information in a temporal descriptor such as descriptor1003. The selected mode is deleted if the current frame number of the input image is greater than the frame number for deletion Df. If the selected mode is not active and deleted, the method1200returns to step1210via NO arrow. If the selected mode is active, then the method1200continues to determining step1240via YES arrow.

At step1240, a match score between the visual descriptor of the selected mode and a visual feature of the input superpixel visual element is determined under execution of the processor105. A high match score signifies that the superpixel input visual element and the mode are a match and probably belong to a same physical entity in the scene.

In one arrangement, the match score is determined at step1240via probabilistic modelling of two class classification, the match and non-match class, using an absolute difference between the visual descriptors of the mode and the input superpixel visual features. In such an arrangement using the absolute difference, the match score lies between zero (0) and one (1) where zero (0) represents no-match and one (1) represents a perfect match. In one arrangement, the match class is modelled as a Gaussian model while the non-match is modelled as a uniform distribution. In another model, a probabilistic support vector machine (SVM) classifier is used for match/non-match classification. The method1200continues at collecting step1250, where the processor105is used to collect an index number of the matched mode and corresponding match score in an array, configured within RAM170to be used in step1260.

After step1250, the method1200continues to decision step1210. If there are no remaining unprocessed modes, then the method1200takes the NO arrow to selecting step1260. At step1260, the mode with the best match score is selected under execution of the processor105and stored in the RAM170. The output of method1200executed at step550is the best matched mode among the input set of modes for the input visual element.

After determining the best match mode, the method500(i.e., as executed at step860inFIG. 8) continues from the step550to the status determining step570. At step570the foreground/background status of the visual element selected at step530is determined under execution of the processor105. At step570, the processor105is firstly used to determine whether the best match mode having the highest match score is a good enough match or not by comparing the match score with a pre-determined threshold value which is referred to below as the “sensitivity level”.

If the match score is determined to be lower than the sensitivity level at step570, then a new mode creation event is created and the selected superpixel visual element is classified as Foreground. The new mode creation event will be used for scene model update in step870.

The sensitivity level defines how different an input visual element needs to be, compared to existing element models to create a new element model. The sensitivity level may be selected based on machine learning from sample data. In one arrangement, the sensitivity level is 0.5.

The sensitivity level can be said to control how often new modes are created. A low sensitivity level results in fewer new modes being created, and therefore more matches to existing modes. With a lower sensitivity level there will be more matches to background modes as fewer foreground modes will be created, and thus fewer matched foreground modes will be determined. A high sensitivity level will result in more new modes being created, and therefore fewer matches to existing modes. As new modes are initially foreground modes, with a high sensitivity level more matched foreground modes and more newly created foreground modes are determined

If the match score is higher than the sensitivity level, the temporal characteristics of the corresponding matching mode are used to determine foreground/background status of the selected superpixel visual element. In one arrangement, age of the mode amis calculated at step570in accordance with Equation (8) as follows:
am=current frame number−creation frame  (8)

The age of the mode amis compared with a pre-determined threshold (am). If am<ath, the selected superpixel visual element is classified as foreground else background. In one arrangement, athis calculated in accordance with Equation (9) as follows:
ath=max(floor(Cth*(current frame number−1)),ath-max)  (9)
where Cthis a number between zero (0) and one (1) and floor( ) represents a mathematical floor function which rounds the input number to the nearest integer towards minus infinity; and ath-maxrepresents maximum value of age threshold. A lower value of Cthrepresents that new observations are turned background faster. In one arrangement, Cth=0.8 is used.

Accordingly, the outputs of step570are (i) the input superpixel visual element foreground/background status; and (ii) Information about the match mode and whether a new mode needs to be created or not.

After step570, the method500continues to the decision step510which checks if there are more input superpixel visual elements to process. If all input superpixel visual elements have been processed, then the method500concludes.

After step860, the method800continues to updating step870, where the processor105is used for updating the scene model for foreground segmentation of the input image received at step810, which is captured by the camera system101based on scene model matching results from step860. The scene model is updated for a foreground segmentation of the image captured by camera system101based on the spatial relationship determined at step860.

A method600of updating a scene model, as executed at step870, will now be described with reference toFIG. 6. The method600may be implemented as one or more software code modules of the software application program133resident in the storage module109and being controlled in its execution by the processor105.

The method600updates the scene model for each superpixel visual element of the input image received at step810, which is captured by the camera system101. The method600begins at decision step610, where if there are input superpixel visual elements of the input image remaining to be processed, then the method600proceeds to selecting step620via the YES arrow. Otherwise, the method600concludes.

At step620, a superpixel visual element of the input image which has not been processed for scene model update is selected under execution of the processor105.

After selecting an input superpixel visual element at step620, the method600proceeds to decision step630. If it is determined, under execution of the processor105, that a new mode needs to be created based on scene model matching results from step860, for the selected input superpixel visual element, then the method600continues to step650via the YES arrow. Otherwise, the method600proceeds to step640.

To create a new mode, one or more seed points are selected to identify corresponding element model sets in the scene model. In one arrangement, the seed point associated with the element model including modes which is matched with the input superpixel visual element is selected at step650. A new mode is created based on the input superpixel visual element and associated with the selected seed point as one mode in a corresponding visual element model set. Accordingly, a new mode is created at each seed point selected for scene matching. For example, when a new mode is created for the input superpixel visual element1510-12, the new mode is associated with both seed points1400-12and1400-18. After selecting one or more seed points at step650, the method600proceeds to creating step660.

The creation of a new mode at a seed point at step660will now be described. Firstly, it is determined if an inactive mode exists in the element model set corresponding to the input superpixel visual element selected at step620. If an inactive mode exists, a new mode is created by using the visual features of the selected superpixel visual element and a temporal descriptor of the newly created mode is initialised as described above in the scene model initialisation step850. If all modes of the element model set corresponding to the superpixel visual element selected at step620are active, then a mode is selected for deletion. In one arrangement, the mode which is marked for earliest deletion based on temporal descriptor Df is selected at step660and initialised using the visual features of the superpixel visual element selected at step620. New modes are created at all seed points selected at step650.

After step660, the method600continues to decision step610to check if there more visual elements to be processed. If all input visual elements have been processed, the method600ends.

If it is determined at step630that a new mode is not required to be created, then the method600continues to update step640via the NO arrow. At step640, the visual and temporal descriptor of the matching mode determined at step550are updated under execution of the processor105.

The temporal descriptor is updated at step640using the current state of the temporal information as described above, and the current frame number although the creation time Cf of the mode is unchanged. The match count for the element model is incremented, until a maximum match count is reached. The last match frame for the mode is set to the current frame number at step640. The deletion time for the element model is updated using the deletion time expression shown in Equation (7) above. The visual descriptor is updated using the visual features of the input superpixel visual element. In one arrangement, an approximated median update method is used using a learning rate threshold LRmax. The learning rate threshold LRmaxrepresents the maximum change allowed for a mode feature per update. An approximate median filter used in the approximated median method is defined in accordance with Equation (10) as follows:
Cvt+1=f(Cvi,Ct,LRmax)  (10)
where Cvtdenotes the coefficient value at time t for mode v which is used in scene matching step860, Cvt+1represents an updated mode coefficient value which will be used for scene matching in a next image (or frame) (i.e., at time t+1), Ctrepresents the coefficient of the corresponding input element in the input image and f represents the approximated median updating function which can be further defined in accordance with Equation (11) as follows:

FIG. 13is a graph1300that shows how the value of the learning rate threshold LRmaxcontrols a maximum change in the mode coefficient value per update. As shown inFIG. 13, vertical axis1310on the graph1300is an absolute update amount to be applied to the mode coefficient value. The absolute update amount is added to the coefficient value for the mode where the input coefficient value is greater than the mode coefficient value. The absolute update amount is subtracted from the coefficient value where the input coefficient value is less than the mode coefficient value.

The horizontal axis1320on the graph1300is the absolute difference between the input coefficient value and mode coefficient value, which will be referred to below as the absolute difference. The line1340represents an absolute update amount1340applied to the mode coefficient value, for a given absolute difference. When the absolute difference is less than the value of the learning rate threshold LRmax1330, the absolute difference is the absolute update amount1340. When the absolute difference is greater than the learning rate threshold LRmax1330, the value of the learning rate threshold LRmaxis the absolute update amount1340.

In contrast, foreground that obscures background can briefly appear as background with a significant change over a small period of time. Therefore, the high learning rate threshold is limited. (i.e., high learning rate threshold is not infinite). In one arrangement, LRmax=10 for eight (8) bit input colour features. Following step640, the method600returns to decision step610.

If it is determined at step610that all input superpixel visual elements have been processed, then method600concludes via NO arrow.

After the scene model has been updated at step870, then the method800continues to generating step880, pixel level foreground segmentation is generated under execution of the processor105based on foreground/background status determined in the scene model matching step860. All pixels belonging to superpixel visual elements which have foreground status as determined at step880are marked foreground. Remaining pixels are marked background. The execution of step880results in a pixel level foreground segmentation mask which may be stored in the RAM170.

After step880, the method800continues to decision step890to check if there are more input images to be processed. If there are more input images to process, then the method800continues to step810via the YES arrow. If all the input images have been processed, then the method800ends via the NO arrow.

The superpixel segmentation in the method800described above uses grid based seed point placement. In another arrangement, non-grid based seed points may be used in the method800. A method1600of segmenting input images in a video sequence, using non-grid based superpixel segmentation which may be alternatively executed at step820will now be described.

The method1600is very similar to the process previously described in relation to step310. The method1600may be implemented as one or more software code modules of the software application program133resident in the storage module109and being controlled in its execution by the processor105.

The method1600begins at creating step1605, where an appropriate number of seeds points are created for the input image received at step810in the manner described above in relation to step305. Once the number of required superpixel segments has been determined, then the method1600moves to step1610.

Processing steps1610,1620and1630are the same as processing steps310,320and330of the process300as described above. At step1610, a derived image measuring the strength of scene boundary is determined from the input image received at step810in the manner described above for step310. Then at step1620, a fixed scalar offset is added to the derived image under execution of the processor105in the manner described above for step320. Then at step1630, a random noise offset, also known as random noise pattern, is added to at least a portion of the derived image under execution of the processor105in the manner described above for step330.

After finishing step1630, the method1600moves to step1640, where local minima of the boundary cost image is detected under execution of the processor105. A local minimum is a point with a lowest measure of boundary strength within a neighbourhood of the point. The local minima determined at step1630will be used as seeds for superpixel segmentation in step1650. The noise addition in step1630ensures an even distribution of detected local minima everywhere in the cost image, including in flat regions in the derived image. In one arrangement, the neighbourhood used in step1640comprises pixels in a square window of size (2r+1)-by-(2r+1) around the neighbourhood centre. The neighbourhood radius r relates to a desired average area of the output superpixels. The average superpixel area equals the ratio between the total number of pixels in the input image received at step810and the desired number of output superpixels as estimated in step1605. Such local minima over a fixed size neighbourhood can be found using a non-maximal suppression technique. Non-maximal suppression detects local maxima over a rectangular neighbourhood. To find local minima, non-maximal suppression is applied to a negated boundary cost image. Non-maximal suppression guarantees a minimum separation distance between the selected minima. However, non-maximal suppression does not produce an exact number of desired local minima. In another arrangement, an exact number of desired local minima is determined from the boundary cost image using adaptive non-maximal suppression. Adaptive non-maximal suppression selects an oversupply of initial local maxima using non-maximal suppression with a small neighbourhood window. A suppression radius is then determined for each local maximum, where suppression radius refers to the radius of a largest square neighbourhood, whose pixels are all smaller than the local maximum. A desired number of local maxima with the highest suppression radii are then selected from the list of initial local maxima. The output of step1640is the location of seed points which may be stored in RAM170.

The processing steps1650,1660and1670are similar to processing steps350,360,370and380. At determining step1650, a geodesic distance transform on a geodesic space defined by the boundary cost image is generated using the seed points generated in step1640in the manner described above for step350. Then at step1660, the processor105is used to determine whether or not to perform superpixel refinement by seed re-centroiding followed by another iteration of geodesic distance transform in the manner described above for step360. At step1670, the seed points are reintialised to the centroids of previously determined superpixels in the manner described above for step370.

The method1600generates non-gridded seed point based superpixel segmentation. An example of non-gridded seed point based superpixel segmentation is shown inFIGS. 17A, 17B and 17C.

FIG. 17Ashows an example input image1710.FIG. 17Bshows the position of seed points in the input image1710andFIG. 17Cshows a resulting superpixel segmentation.

A method1800of updating a scene model for an image using non-gridded superpixel visual elements. The method1800may be implemented as one or more software code modules of the software application program133resident in the storage module109and being controlled in its execution by the processor105.

The method1800begins at receiving step1810which is the same as step810of method800. At step1810, an input image is received from the image sensing device110under execution of the processor105and is stored in the RAM170in the manner described above for step810.

Then at determining step1820, the processor105executes superpixel based image segmentation method1600on the image received at step1610to determine dynamic superpixel visual elements for the image. After generating non-gridded superpixel segmentation, the method1800continues to step1830.

At extracting step1830, visual and location features for superpixel visual elements are extracted under execution of the processor105. The visual feature extraction performed at step1830is similar to the process described above in relation to step830. However, extraction of the location features will now be described. In one arrangement, the centroid of a superpixel visual element is used as a location feature. In another arrangement an elliptic approximation is fitted to represent shape of a superpixel visual element using [μxμyσx2σxyσy2] where, μxand μyare mean of x and y coordinates of all pixels which lie within the superpixel visual element, and σx2, σy2and σxyare x-variance, y variance and xy co-variance respectively. The output of step1830is a list of visual and location features for each superpixel visual element.

After extracting visual features of the input image the method1800moves to decision step1840. If the input image is the first image (frame) to be processed, the method1800proceeds to step1850. If the input image is not the first image (frame) to be processed, then the process method1800proceeds to step1860.

Initialising step1850is similar to step850. At step1850the scene model for the input image received at step1810is initialised using the features determined in step1830. However, as described in relation to step850, a scene model comprises visual element model sets where each visual element model set comprises multiple modes. In contrast, in the case of non-gridded based superpixel segmentation, each location of the non-gridded seed points may change image (frame) by image (frame). Therefore, each visual element model set also stores location features (e.g. location of the centroid of a superpixel visual element) as part of a location descriptor per set to associate a visual element model set with the corresponding location feature (e.g. location of the centroid of the superpixel visual element).FIG. 20shows an example of a structure of a scene model for non-gridded based superpixel segmentation.FIG. 20shows that a location descriptor1002including the location features is associated with Element Model Set11002. The remainder of the step1850is same as step850as described.

After finishing the scene model initialisation, the method1800moves to matching step1860.

At matching step1860, the input image is matched to the scene model and the foreground/background status of the superpixel visual elements of the input image is determined. A method1900of matching a scene model to an image, as executed at step1860, will now be described with reference toFIG. 19. The steps1910,1920,1930,1950and1970of the method1900are similar to steps510,520,530,550and570respectively of the method500shown inFIG. 5.

The method1900may be implemented as one or more software code modules of the software application program133resident in the storage module109and being controlled in its execution by the processor105.

The method1900begins at a first decision step1910, where the processor105is used to check if all the input superpixel visual elements of the input image have been compared to the scene model in the same manner to that described for step510. If all input superpixel visual elements have been compared to the scene model, then the method1900concludes. Otherwise, the method1900proceeds to step1930.

Then at selecting step1930, under execution of the processor105, a next input superpixel visual element is selected from the list of superpixel visual elements generated at step1830, in the manner described above for step530.

The method1900continues at determining step1940, where the processor105is used to determine visual element model sets for each input superpixel visual element for scene model matching. In one arrangement, when a centroid is used as the location feature for a superpixel visual element in the input image, a closest visual element model set having a location feature is identified from the scene model at step1940. In another arrangement, a Euclidean distance formulation is used at step1940to determine a closest visual element model set. In another arrangement, a Sum of Absolute Difference is used at step1940as a distance formulation to determine a closest visual element model set.

In another arrangement, all visual element model sets with in a pre-determined distance region from the centroid of the superpixel visual element are selected at step1940. A possible value for the pre-determined distance is

The output of step1940is selected visual element model sets which are used to match the superpixel visual element selected at step1930.

The method1900then proceeds to1950, where all modes in the set of element model sets of the scene model are used to compare the superpixel visual element selected at step1930to determine a best matched mode in the manner described above for step550.

After determining the best match mode, the method1900continues from the step1950to the status determining step1970. At step1970the foreground/background status of the visual element selected at step1930is determined under execution of the processor105. Following step1970, the method1900returns to step1910.

Returning to the method1800, after finishing step1860, the method1800moves to updating step1870where the scene model is updated based on the scene model matching results from step1860. Each location feature in the location descriptor for each element model set is updated, for example, every image (frame). In one arrangement, for each element model set, the nearest location of a centroid of a visual element in the input image to a location feature associated with each element model set is determined at step1870. Then the location feature is updated to the nearest location. The nearest location may be the same for more than one element model set by accident. In that case, the element model sets are merged. In another arrangement, the location feature is only updated if a best match score based on the matching result from step1860is higher than a threshold say 0.7.

Steps1880and1890are the same as steps880and890respectively. At generating step1880, pixel level foreground segmentation is generated under execution of the processor105based on foreground/background status determined in the scene model matching step1860. Then at decision step1890, if there are more input images to be processed, then the method1800continues to step1810via the YES arrow. If all the input images have been processed, then the method1800ends via the NO arrow. The superpixel visual element based scene modelling and foreground segmentation described above has several advantages. Since each superpixel is a collection of pixels, superpixel visual element based scene modelling and foreground segmentation has similar memory and computation cost as a block based approach and much lower cost than a pixel-based approach.

Further, superpixel segmentation preserves salient features of images by respecting edges. Preserving salient features of images by respecting edges allows higher robustness to shaky videos and video scenarios with dynamic background compared to block based approaches. Additionally, superpixel visual element based scene modelling also achieves more accurate foreground mask compared to block-based methods because block-based methods generate blocky outputs while superpixel segmentation follows edges in the image.

INDUSTRIAL APPLICABILITY

The arrangements described are applicable to the computer and data processing industries and particularly for image processing.