The invention relates to a system for combining two or more digital images into a combined image.

The invention further relates to a method for combining two or more digital image objects into a combined image. Such a system and method are utilized in digital image processing when images are combined with each other in order to form an integrated whole.

Digital image processing systems and methods are commonly used nowadays. In such systems and methods, a computer program in a computer is used for manipulating image objects converted into a digital form, such as photographs with different distinct details.

An application of the digital image processing systems and methods is a system and method enabling different images to be combined into an integrated whole, i.e. a composite image.

Such a system and method are known from International patent application WO 02/31774.

In the known system and method the images are decomposed into image objects. In order to do so a logic for determining and separating essential image objects is used. After determining and separating the recognized and separated image objects are combined into a combined image object.

The known system and method requires complicated logic and the user must play an active role. The image objects have to be recognized by the logic as essential image objects, which is not always possible. The essential objects have to be combined by the user. The known system and method therefore is complicated and necessitates an active role of the user.

In particular the known system and method is less suitable for making group portraits. As more people more frequently photograph themselves and each other, group portraits become increasingly commonplace as well and their creation continues as a feature

of contemporary social life. However, taking a group photo has a draw-back: The one that shoots the group photo is not in the photo! Someone outside of the group must take the picture, which someone might not be present, or the "self timer" feature must be used. Using the 'self-timer' feature does not always provide for the desired results. Another alternative is to shoot individual pictures of multiple subjects in non-overlapping positions and then use "image stitching" (or cut and paste). However, cut-and paste is a complicated procedure, which requires knowledge and skill and cannot easily and often not at all be performed 'on the spot'. Cutting and pasting afterwards is prone to failure, and any resulting group photo has to be afterwards sent to the participants of the group. Often, for instance at family gatherings, or gatherings at a particular place at a particular time, the next time this particular group will be together again may be some time in the future or often never again.

It is an object of the invention to provide a relatively simple system and method by which, with no or minimal intervention of the user, a composite image is made from a number of images.

The method in accordance with a first aspect of the invention is characterized in that: at least three digital images are acquired, - in a first method step image blocks of a first of the images are matched to image blocks of a second of the images, for matching blocks a block difference is determined and if the block difference is below a threshold, the relevant image block of the first image is denoted an image block of the composite image, and for the remaining image blocks of the first image for which the block difference is equal to or above the threshold, in a second method step said remaining image blocks of the first of the images are matched to image blocks of the third image, and a block difference is determined and if for two matching blocks in the first image and third image the block difference is below a threshold, the relevant image block of the second image is made an image block of the composite image, and if the block difference is equal to or above the threshold the relevant image block of the first image is made an image block of the composite image.

The system in accordance with the invention is characterized in that it comprises:

an input for at least three digital images, a matcher for matching image blocks of a first of the images to image blocks of a second of the images, a determinator for determining for matching blocks a block difference, - and an assigner to assign blocks of the digital images to blocks of the composite image such that, if for two matching blocks in the first and second image the block difference is below a threshold, the relevant image block of the first image is assigned to be an image block of the composite image, and for the remaining image blocks of the first image for which the block difference is equal to or above the threshold, in a second method step said remaining image blocks of the first of the images are matched to image blocks of a third one of the images, and a block difference is determined and, if for two matching blocks in the first image and the third one of the images the block difference is below a threshold, the relevant image block of the second image is assigned to be an image block of the composite image, and if the block difference is equal to or above the threshold the relevant image block of the first image is assigned to be an image block of the composite image.

The system may and preferably is a camera, in which case the at least three original digital images are acquired by the camera, or it may be for instance a computer system in which the input may come from three images recorded beforehand, for instance on a storing medium, or being sent via internet or e-mail.

Any method of determining a block difference between the image blocks can be used, but a preferred method for matching is by means of using a motion compensation method.

Motion compensated prediction is a powerful and well known method and used extensively in MPEG-I and MPEG-2 video coding standards as a prediction technique. The concept of motion compensation is based on the estimation of motion between images, i.e. if all elements in an image are approximately spatially displaced, the motion between images can be described by a limited number of motion parameters (i.e. by motion vectors for translatory motion). A good, often a best prediction of an actual pixel of block is given by a motion compensated prediction pixel or block from a previously coded image. Since the spatial correlation between motion vectors is often high it is sometimes assumed that one motion vector is representative for the motion of a "block" of adjacent pixels.

In a formula form the method reads:

For each block Bl (x,y) of photo 1

Find best matching block B2 in photo 2 with a matching method, for

Instance, MAD 12 (Motion compensation difference between matching blocks in photo 1 and photo 2)

If MAD 12 < threshold then

Bl(x,y)→Bg(x,y)

Else

Find best matching block B3 in third (background) photo with MAD 13 If (MADl 3 < threshold)

B2(x,y) →Bg(x,y) Else

Bl(x,y) → Bg(x,y)

The system comprises an input for digital photos and it comprises a computer program or computer programs or computer program code(s) to perform the above logic, above described as 'determinator, matcher etc.

X and y in the above formula stand for the coordinates/indexes of a block in a bidimensional array/matrix representing the pixels.

A block B(x,y) is an array of pixels having coordinates x, y. The block may in principle be of any shape, but in practice often square blocks 4, 8 or 16 pixels wide are used. Block size and shape can change within an image.

All image blocks B _g (x,y) of the composite image stem from the image blocks of either photo 1 (B ₁ (X ₅ V)) or photo 2 (B2(x,y)). However, although the third photo, in the above logic named the background photo, does not directly contribute to the composite image, it is the use of the data on this background photo which allows an accurate and automatic combining of the photo's into a group photo, without an intervention of the user being necessary.

Thus, what a priori seems to be a superfluous act, namely acquiring a third digital photo, here named the background photo, which photo does not itself contribute image blocks to the composite photo, in fact the use of this third, background, photo allows for an accurate and automatic reproduction of the composite photo as will be explained below.

The method in accordance with the invention allows the combination of photo's into a group photo to be made automatically and possibly on the spot. A relatively simple logic is used.

Preferably the method comprises a following filtering step. During a filtering step an algorithm is used to identify those blocks within the composite image which are out place in respect to neighboring blocks. Such blocks are replaced with the matching blocks of the other photo.

Preferably the filtering step comprises a first step in which median filtering is preformed followed by a step in which region filtering is performed. A second aspect of the invention relates to an alternative method and system in which only two digital images are needed.

The alternative method is characterized in that two images are acquired: image blocks of a first of the images are matched to image blocks of the second of the images, - for matching blocks a block difference is determined and if for two matching blocks the block difference is below a threshold, the relevant image block of the first image is assigned to be an image block of the composite image, and, if not, the relevant image block of the second image is assigned to be an image block of the composite image, where after it is indicated to the user which regions of the composite image have a block difference above the threshold and the method comprises an input step in which the user can invert the assignment of the blocks of an indicated region.

The alternative method is a semi-automatic method, having some steps in common with the fully automatic method. The semi-automatic alternative method requires some action by the user. However, the user is lead to take the proper action and a simple action suffices.

The system in accordance with the alternative method comprises the means, such as a computer program or programs or computer codes to perform the method steps of the alternative method.

The system in accordance with the second aspect of the invention is characterized in that it comprises: an input for at least two digital images, a matcher for matching image blocks of a first of the images to image blocks of the second of the images,

a determinator for determining for matching blocks a block difference and an assigner to assign blocks of the digital images to blocks of the composite image such that for matching blocks a block difference is determined and if for two matching blocks the block difference is below a threshold, the relevant image block of the first image is assigned to be an image block of the composite image, and, if not, the relevant image block of the second image is assigned to be an image block of the composite image, the system further comprising an indicator to indicate to the user which regions of the composite image have a block difference above the threshold and an input by which the user can invert the assignment of the blocks of an indicated region. Within the concept of the invention a 'input', 'matcher', 'determinator',

'indicator', 'assigner' etc are to be broadly understood and to comprise e.g. any piece of hard- ware (button or part of a camera), any circuit or sub-circuit designed for performing a matching, determination, indication, assignment, inversion of assignment function as described as well as any piece of soft-ware (computer program or sub program or set of computer programs, or program code(s)) designed or programmed to perform a matching, determination, indication etc operation in accordance with any aspect of the invention as well as any combination of pieces of hardware and software acting as such, alone or in combination, without being restricted to the below given exemplary embodiments. One program may combine several functions. The invention is also embodied in any computer program comprising program code means for performing a method in accordance with the invention when said program is run on a computer as well as in any computer program product comprising program code means stored on a computer readable medium for performing a method in accordance with the invention when said program is run on a computer, as well as any program product comprising program code means for use in a system in accordance with the invention, for performing the action specific for the invention.

These and other objects of the various aspects of the invention will be apparent from and elucidated with reference to the embodiments described hereinafter.

Fig. 1 illustrates a first image taken by a person in a group;

Fig. 2 illustrates a second image taken by another person in the same group;

Fig. 3 illustrates a background image;

Fig. 4 illustrates a matching of images;

Fig. 5 illustrates the distribution of blocks after the main steps of the method; Fig. 6 illustrates the distribution of image blocks after a median filtering step; Fig. 7 illustrates the distribution of blocks after a region filtering step; Fig. 8 illustrates the final composite image; Fig. 9 illustrates a composite image wherein areas of the image having a block difference above a threshold are indicated;

Fig. 10 schematically illustrates a system in accordance with a first aspect of the invention;

Fig. 11 schematically illustrates a system in accordance with a second aspect of the invention.

The Figures are not drawn to scale. Generally, identical components are denoted by the same reference numerals in the Figures.

This method in a first aspect of the invention requires taking three photos: a first and a second photo and a third photo, one of which photo is herein below denoted the background photo. In practice often two group photos are taken by two different subjects belonging to the group and one photo of the background without subjects.

For example let us consider a group of three subjects: A, B and C. The first photo (Fig. 1) includes B and C and is taken by A. The second photo

(Fig. 2) includes A and B and is taken by C. The third photo (Fig. 3) is the background. In a first step blocks in photo's 1 and 2 are matched. An image difference algorithm, for instance and preferably motion compensated image difference, between photos 1 and 2, locates the blocks of the two images 1 and 2 whose block difference, for instance and preferably the motion compensated difference (MAD ₁₂ ) is below a threshold. Existing algorithms for motion compensation can be used to find for each block of image 1 the best matching block of image 2. The block- matching algorithm preferably searches a restricted neighborhood of the original block. Advanced block matching algorithms can be applied that use different block sizes, shapes and complex motion. Block matching algorithm are well known in the art.

The blocks for which MAD ₁₂ is below the threshold are the blocks common to both photo's 1 and 2. These blocks are chosen to be part of the final group photo (i.e. B _g (x,y) (i.e. the block in the composite image at position X ₅ V)=B ₁ (X ₅ V) (i.e. the corresponding block in the first photo). The blocks of the first photo whose motion compensated difference MAD ₁₂

is above the threshold are compared using motion compensation image difference with the background photo (MAD ₁₁ ,). If this motion average difference MAD ₁₁ , is below a threshold the relevant block in the first photo is also part of the background, but is not part of the second photo (since MAD ₁₂ is above the threshold), consequently the image block of the second photo is chosen. The final group photo is composed of the blocks that are common to both images (first step) or to one of the photo's (second and third step) but that are not part of the background. More formally the algorithm is as follows:

For each block Bl (x,y) of photo 1

Find best matching block B2 in photo 2 with MAD 12

If MAD 12 < threshold then

Bl(x,y) → Bg(x,y) Else

Find best matching block B3 in background photo with MAD 13

If (MADl 3 < threshold)

B2(x,y) → Bg(x,y)

Else

Bl(x,y) → Bg(x,y)

X and y in the above formula stand for the coordinates/indexes of a block in a bidimensional array/matrix representing the pixels.

A block B(x,y) is an array of pixels having center coordinates x, y. The block may in principle be of any shape, but in practice often square blocks 4, 8 or 16 pixels wide are used. Block size and shape can change within an image. Matching is performed by taking a block B ₁ of image 1 and blocks B ₂ of image 2 and for each combination of said block of image 1 and a block of image 2 summing up all the differences between characteristic values (e.g. luminosity) of corresponding pixels. For each pair of blocks such a sum is found, When luminosity is compared and the sum is divided by the number of pixels the resulting value gives the mean absolute luminosity difference, the MAD value. The block of image 2 with the lowest block difference, in this example the lowest MAD value compared to the block in image 1 is the block of image 2 which best matches the block of image 1. Other ways of comparing blocks exist (e.g. using also the chrominance values of the corresponding pixels of the blocks). In such methods some type of block difference is used to find matching blocks. In more complicated schemes

more than one block difference might be computed, a difference value for luminosity (Dl) and for chrominance (D2). The best matching block can then be found by finding the block in image 2 which has the best set of difference values (D1,D2). This block of image 2 would then be the 'best matching block'. The threshold within the framework of the invention would then be an threshold area within Dl, D2 space. If the difference set Dl, D2 of the best matching block of image 2 falls within the threshold area, then Bi(x,y) — > B _g (x,y), If this is not the case, the next steps are taken. If three differences are taken into consideration for instance luminance and color point values (Dl, D2, D3), then the threshold become a threshold volume within a three dimensional Dl, D2, D3 space. The background photo in fact does not contribute to the image blocks of the composite image (B ₃ ≠B _g (x,y)). Thus, prima facie it seems superfluous to take the third image, since it does not contribute to the composite image. However, without the background image the resulting photo inversion of entire a priori unknown regions, by means of an appropriate user interface would be needed to compose the group photo. This is the subject of an alternative embodiment of the invention which will be described below. The thresholds may be set beforehand or calculated from the photos. In practice the two thresholds will often be the same. In practice the block difference will often show a very noted distribution, almost all block differences will be relatively small, since the photos are in most areas very similar, except for those parts where the subjects have moved, where the difference will be very distinct. This distribution allows the threshold to be set or easily calculated.

Fig. 4 schematically illustrates the matching process of the first step of the method of the invention, where M stands for matching. Fig. 5 shows the results of this intermediate step where it is indicated which blocks are derived from which photos. The gray level of each block is proportional to the MAD ₁₂ value. It is to be noted that some anomalies A may occur, i.e. islands of image blocks derived from one photo (in this case photo 2) in areas derived form the other photo (in this case photo 1). This may be correct, but may also be due to errors. Therefore, preferably an optional step of filtering the results is performed. Each block of the final group photo has now associated a label representing their source photo. To obtain uniform results over the whole image median filtering is applied. Median filtering compares each block with neighboring blocks. The median filter is not applied to the pixels values of the image, but to the blocks: a mask of MxN (for instance NxN) blocks is used.

For example: let us consider a 3x3 median filter and a part of a photo with the following blocks:

1 1 2

1 2 1

1 1 1

The numbers 1 and 2 in the 3x3 mask stand for the assignment of the blocks of the composite image, i.e. whether the blocks are derived from image 1 (B ₁ (X ₅ V^Bg(X ₅ V)) or from image 2 (B2(x,y)→B _g (x,y))). The assignment of the central block is 2, i.e. it stems form image 2.

To apply the median filter operation to the central block, the blocks are sorted: 1 1 1 1 1 1 1 2 2 and then we select the block in the middle position which is, in this case, a 1. 1 1 2

1 1 1

1 1 1

The result is that the assignment of the central block is changed from 2 to 1, i.e. instead of stemming from image 2 the central block is made to stem from image 1. Other schemes of filtering are possible for instance by taking a rectangular mask (M≠N) or using larger masks (5x5 for instance) or by giving different filtering weights to blocks as they are further away from the central block of the mask. When larger masks are used i.e. masks in which the central block is surrounded with layers of nearest neighboring blocks, next-nearest neighboring blocks, next-next-nearest neighboring blocks etc. it is preferred to use different filtering weights as the blocks of the mask are further away from the central block.

Fig. 6 shows the results of the median filter on the previous example.

To further remove possible artifacts left after the median filtering operation, a region filtering operation is performed. Region filtering comprises computing connected components on the labeled image. Connected components whose area is below a certain threshold are considered artifacts and their label is changed.

Fig. 7 shows the results of the region filtering on the result given in Fig. 6.

The end result is one area of the photo coming from photo 2 (corresponding to person A) the rest of the blocks coming from photo 1. Automatically, i.e. without intervention of the user, and without needing a 'cut-and-paste' procedure a composite image is made. The algorithm is very simple.

Fig. 8 shows the resulting group photo.

It is remarked that the fact the fully automatic solution is provided does not exclude the possible use of 'patching-up' steps by users to embellish the resulting composite image.

One preferred embodiment of the method and system of the invention is that a pair of composite images are made of a pair of first and second images. In the above given example most of the pixels of the composite image are derived from the first photo and a small part of the second photo. However, the choice of first and second photo is arbitrary. Therefore based on a pair of photo and a third, background, photo two photos can be made. Both of these photos will show the group, however, the photos are not exactly the same. By making a pair photos the user can choose the 'best photo'. The best photo may not always be the photo with the best image quality, but for instance the one in which on average the subject in the group photo put on a more pleasing smile.

The above described method and system is fully automatic. The user takes or selects three images and the method or system has as an output a composite image. In an alternative embodiment of the invention a semiautomatic solution is provided.

In the semiautomatic solution the method is characterized in that at least two digital images are acquired, in a first method step image blocks of a first of the images are matched to image blocks of a second of the images, for matching blocks a block difference is determined and if for two matching blocks the block difference is below a threshold, the relevant image block of the first image is assigned to be an image block of the composite image, and for the remaining image blocks of the first image for which the block difference is equal to or above the threshold and if the block difference is equal to or above the threshold the relevant image block of the first image is assigned to be an image block of the composite image.

The algorithm changes as follows:

For each block Bl (x,y) of photo 1

Find best matching block B2 in photo 2 with MAD 12

If MAD 12 < threshold then

Bl(x,y) → Bg(x,y) Else

B2(x,y) → Bg(x,y)

The method comprises a following step of indicating to the user which regions have a value of MAD^threshold and an input step in which the user can invert the label of the blocks of an indicated region. Basically in the above algorithm these areas are those areas in which the image blocks are derived from photo 2. Preferably the indication is performed after filtering steps, for instance as described above.

Prior to the indicating step preferably a filtering step such as described above is performed.

Most cameras nowadays have displays, the image after the application of the above algorithm would be shown on a display as for instance shown in Fig. 9. The areas of the composite image that are derived from image 2 are indicated in the image shown in the display. Clearly, although the third person is not in the image, the outline of this person is indicated. The method enables the user (e.g. by means of a mouse pointer and a mouse click, when a computer is used) to invert the label of the white-outlined right hand area, in which case the third person shows up in the composite image, where after the composite image may be saved. The resulting image comprises all persons, i.e. it is a complete group portrait. The semi-automatic solution requires not more knowledge or ability from a user than to invert the label of an area, which can be easily done by a mouse click. In fact the user will probably not realize that he/she is inverting the label, he/she will simply notice that when the indicated area is selected and he/she clicks on the mouse, the missing person appears in the group photo, and he/she will save the image. Such a method may also be performed on a camera, which nowadays is provided with a display, and a set of buttons. For instance, the camera may have a function by which, using e.g. arrow buttons, a selection within the indicated areas may be made, and with an 'enter' button an inversion of a label of a selected area may be made, where after the composite image is shown and if the image is to the satisfaction of the user, with a second click on the 'enter' button, the composed image is saved.

Fig. 10 illustrates schematically a system in accordance with the first aspect of the invention. Three digital images are acquired in acquirer 1. The acquirer may be a part of the system, for instance when the system is a camera, alternatively, when the system is e.g. a PC the data may be acquired from a device outside the system as such, for instance form e- mail. The images are divided in blocks B ₁ (X ₅ V), B2(x,y), B ₃ (x,y). The data is stored in 2. In a matcher 3 matching data blocks in photo 1 and 2 are found and the block difference, for instance the MAD ₁₂ is determined. For those blocks where MAD^threshold the block Bi(x,y) of photo 1 is assigned to the composite photo, for the other blocks a further matching is performed (4) between blocks of photo 1 and photo 3. The block difference MAD ₁₃ of

matching blocks of photo 1 and 3 is determined (4), and depending on whether or not MAD ₁₃ is above or below or equal to a threshold, the blocks of photo 1 or photo 2 (MAD ₁₃ <threshold) are assigned to the group photo. Finally all blocks of the composite photo are gathered (5) and the composite photo is created either directly without filtering (dotted line), or after filtering through filter 6.

Fig. 11 illustrates schematically a system in accordance with the second aspect of the invention. Two digital images are acquired in acquirer 1. The image are divided in blocks B ₁ (X ₅ V), B2(x,y). The data is stored in 2. In a matcher 3 matching data blocks in photo 1 and 2 are found and the block difference, for instance the MAD ₁₂ is determined. For those blocks where MAD ₁₂ <threshold the block Bi(x,y) of photo 1 is assigned to the composite photo, for the other blocks the blocks of photo 2 are assigned to the group photo. All blocks are gathered and the resulting photo is displayed either directly or after filtering through filter 6. The areas which differ in the two photo is indicated, and the user can invert the label through input 7 of inverter I. Finally the composite photo is created. For each of the two method and systems, it is an arbitrary choice which one of the photo's 1 and 2 is labeled 1 and 2. Thus for each pair of photos there are two a priori equally valid choices. In preferred embodiments the method and the system provides a pair of photo in accordance with the two possibilities and the user is provided with the choice of these two possibilities. In short the invention can be described (for the first aspect) by:

Two or more digital images are combined. Three digital images are taken, Image blocks (B ₁ (X ₅ V)) of a first image are matched to image blocks (B ₂ (X ₅ V)) of a second image, and for matching blocks a block difference (MAD ₁₂ ) is determined.

If this block difference is below a threshold, the relevant image block of the first image is assigned to be an image block (B _g (x,y)) of the composite image. The remaining image blocks of the first image are matched to image blocks (B ₃ (x,y)) of the third image, and a further block difference (MAD ₁₃ ) is determined. If said further block difference is below a threshold, the relevant image block of the second image is assigned to be an image block of the composite image, otherwise the relevant image block of the first image is assigned to be an image block of the composite image.

The second aspect can be described in short as: Two digital images are acquired, image blocks (B ₁ (X ₅ V)) of a first of the images are matched to image blocks (B ₂ (x,y)) of the second of the images and a block difference (MAD ₁₂ ) is determined. If for two matching blocks the block difference is below a

threshold, the relevant image block of the first image is assigned to be an image block of the composite image, otherwise the relevant image block of the second image is assigned to be an image block of the composite image. Thereafter it is indicated to the user which regions of the composite image have a block difference above the threshold and the method comprises an input step in which the user can invert the assignment of the blocks of an indicated region. It will be clear that within the framework of the invention many variations are possible. It will be appreciated by persons skilled in the art that the present invention is not limited by what has been particularly shown and described hereinabove. The invention resides in each and every novel characteristic feature and each and every combination of characteristic features. Reference numerals in the claims do not limit their protective scope. Use of the verb "to comprise" and its conjugations does not exclude the presence of elements other than those stated in the claims. Use of the article "a" or "an" preceding an element does not exclude the presence of a plurality of such elements.

For instance several possible further embodiments are possible within the concept of the invention:

To facilitate and improve the results of the algorithm the photos preferably are taken from approximately the same position and angles. To help users finding back the camera position and angles after the a previous taken photo, the system has in a preferred embodiment a positioning system (e.g. GPS) and/or appropriate tilting sensors. The camera system has, in a preferred embodiment, an (audio)visual feedback system to provide the user feedback to find back the previous position and angles. The positioning system may for instance be a GPS system or any other system which determines the position and angle of the camera with respect to an outside reference system. The positioning system may also be an internal reference system, for instance a system in which on the view finder a faintly visible image of (parts of) a previously taken image are made visible. The user may then easily find the best position to match as good as possible the to be taken image to the already taken image, by ensuring that the faintly visible parts of the previously taken image coincide with the same parts of the to be taken image. Such a ghost-image may be a whole image, or only some parts, for instance some most distinguishable parts, for instance sharp edge in the image, of the previously taken image. The system may have an indicator to indicate, for instance by means of a red or green light indicator visible in the view finder, when the coincidence between the already taken and the to be taken image is within reasonable limits.

Alternatively the different position and angles information can be used to adjust the images before applying the matching algorithm.

To reduce computational load, the system preferably has means for a user to give an approximate indication of the area of photo 1 that should be integrated with photo 2.