GB2387093A - Image processing apparatus with segmentation testing - Google Patents

Abstract

In an image processing apparatus 2, images of a subject object 210 are processed to calculate the positions and orientations at which the images were recorded, to segment image data relating to the subject object 210 from other image data in at least some images, and to generate a three-dimensional computer model of the subject object 210. To reduce errors in the three-dimensional computer model, each image is tested to determine whether the segmentation processing may generate inaccurate results. Each identified image is then prevented from undergoing segmentation processing, although the segmentation processing may be carried out manually in accordance with user instructions. One way in which the images are tested to identify images unsuitable for automatic segmentation processing is to test whether the viewing direction of the image is within a predetermined angle of vertical. Another way is to project points from the subject object 210 into the image and to test the positions of the projected points.

Description

IMAGE PROCESSING APPARATUS

The present invention relates to the computer processing Of image data defining images of an object recorded at 5 different positions and orientations to calculate the positions and orientations at which the which the images were recorded and to generate a three-dimensional (3D) computer model of the object.

10 Many methods are known for generating 3D computer models of objects. In particular, methods are known in which images of an object to be modelled are recorded at different positions and orientations Each recorded image is then processed to calculate the position and 15 orientation at which it was recorded, and a 3D computer model of the object is generated using the input images and the calculated positions and orientations.

In these known methods, the object to be modelled may be 20 imaged alone, and the position and orientation of each image calculated by matching features on the object between the different input images. Examples of such a technique are described, for example, in EP-A-0898245.

25 Alternatively, the subject object being modelled may be

placed on a calibration object having a known pattern of features thereon, and images of the subject object together with the calibration object recorded at different positions and orientations. Each recorded 5 image is then processed to calculate the position and orientation at which is was recorded on the basis of the positions of the features in the calibration object's pattern in the image. Examples of this technique are described, for example, in "Automatic Reconstruction of 10 3D Objects Using A Mobile Camera" by Niem in Image and Vision Computing 17 (1999) pages 125-134, "The Lumigraph" by Gortler et al in Computer Graphics Proceedings, Annual Conference Series, 1996 ACM-0-89791-764-4/96/008, JP- A-9 170914 and the applicant's co-pending PCT patent 15 application WO-A- 01/39124 (the full contents of which are incorporated herein by cross- reference).

Once the positions and orientations of the input images have been calculated, a popular way to generate the 3D 20 computer model of the subject object is to process each input image to segment (separate) image data relating to the subject object from other image data, and then to perform what is known as voxel carve processing, for example, as described in "Rapid Octree Construction from 25 Image Sequences" by R. Szeliski in CVGIP: Image

Understanding, Volume 58, Number 1, July 1993, pages 23 32 or voxel colouring processing, for example, as described in University of Rochester Computer Sciences Technical Report Number 680 of January 1998 entitled 5 "What Do N Photographs Tell Us About 3D Shape?" and University of Rochester Computer Sciences Technical Report Number 692 of May 1998 entitled "A Theory of Shape by Space Carving", both by Kiriakos N. Kutulakos and Stephen M. Seitz, or silhouette intersection, for example 10 as described in "Looking to Build a Model World: Automatic Construction of Static Object Models Using Computer Vision" by Illingworth and Hilton in IKE Electronics and Communication Engineering Journal, June 1998, pages 103-113.

However, these known methods suffer from a number of problems. For example, the inventors in the present case have found 20 that 3D computer models generated using these techniques can be inaccurate.

Accordingly, it is an object of the present invention to address this problem.

The inventors of the present invention have recognized that inaccuracies in 3D computer models are caused by a number of factors.

5 More particularly, shadows are often cast on the surface on which the subject object is placed for imaging (for example, the ground, a table, or a calibration object) which appear to connect to the bottom of the subject object. Accordingly, when processing recorded images, 10 the processing apparatus cannot distinguish between the subject object and shadow, and the shadows are therefore determined to be part of the subject object, resulting in an inaccurate 3D computer model of the subject object.

15 Further, features on the surface on which the subject object is placed for imaging (such as marks on a floor or table, or features in the pattern on the calibration object) often touch the subject object in a recorded image, and are therefore determined by the processing 20 apparatus to be part of the subject object, again resulting in an inaccurate 3D computer model of the subject object.

Accordingly, it is an object of the present invention to 25 address one or more of these problems.

According to the present invention, there is provided an image processing apparatus and method in which images of a subject object are processed by the apparatus to determine which pixels relate to the subject object and 5 which pixels do not, thereby producing image segmentations. The image segmentations are processed using data defining the viewing positions and directions from which the images were recorded to generate a three dimensional computer model of the subject object. To 10 avoid errors in the image segmentations which cause errors in the three-dimensional computer model, processing is performed to identify each image which is unsuited to the segmentation processing to be performed.

By way of example, such images include images taken with 15 a viewing direction looking down on the subject object such that, in the image, the image data for at least part of the subject object is adjacent to image data relating to the calibration object and/or surface on which the subject object is standing. These images are then 20 excluded from the segmentation processing, and consequently the 3D model surface shape generation processing as well, thereby reducing errors.

The present invention also provides a computer program 25 product for configuring a programmable apparatus to

:: operate in the way described above.

An embodiment of the invention will now be described, by way of example only, with reference to the accompanying 5 drawings, in which like reference numbers are used to designate like parts. Although the embodiment described below relates to the processing of images of a subject object together with a calibration object to calculate the positions and orientations of the input images and 10 to generate a threedimensional computer model of the subject object, the present invention is not limited to this. Instead, the invention is also applicable to the processing of images of the subject object alone for 3D modelling since, as described above, the calibration 15 object is not necessary to calculate the positions and orientations at which the input images were recorded.

In the drawings: Figure 1 schematically shows the components of an 20 embodiment of the invention, together with the notional functional processing units into which the processing apparatus component may be thought of as being configured when programmed by programming instructions; 25 Figure 2 illustrates the recording of images of an object

for which a 3D computer model is to be generated; Figure 3 illustrates images of the object which are input to the processing apparatus in Figure 1; Figures 4a and 4b show the processing operations performed by the processing apparatus of Figure l in a first embodiment to process input data; 10 Figure 5 shows the processing operations performed at step S4-10 in Figure 4; Figures 6a and 6b show the processing operations performed at step S4-16 in Figure 4; Figure 7 shows the processing operations performed at step S4-22 in Figure 4; Figure 8 shows the additional processing operations 20 performed by the processing apparatus of Figure 1 in a second embodiment to calculate a threshold angle for use in the processing at step S4-14; Figure 9 shows an example to illustrate the result of the 25 processing performed at steps S8-6 and S8-8 in Figure 8;

and Figure 10a and 10b shows the processing operations performed by the processing apparatus of Figure 1 in a 5 third embodiment that replace the processing operations performed at steps S4-12 to S4-18 in the first embodiment. First Embodiment Referring to Figure 1, an embodiment of the invention comprises a processing apparatus 2, such as a personal computer, containing, in a conventional manner, one or more processors, memories, graphics cards etc. together 15 with a display device 4, such as a conventional personal computer monitor, user input devices 6, such as a keyboard, mouse etc. a printer 8, and a display panel 10 comprising a flat panel having controllable pixels, such as the PL400 manufactured by WACOM.

The processing apparatus 2 is programmed to operate in accordance with programming instructions input r for example, as data stored on a data storage medium, such as disk 12, and/or as a signal 14 input to the processing 25 apparatus 2, for example form a remote database, by

transmission over a communication network (not shown) such as the Internet or by transmission through the atmosphere, and/or entered by a user via a user input device 6 such as a keyboard.

As will be described in more detail below, the programming instructions comprise instructions to cause the processing apparatus 2 to become configured to process input data defining a plurality of images of one 10 or more subject objects recorded at different positions and orientations to calculate the positions and orientations at which the input images were recorded and to use the calculated positions and orientations to generate data defining a three-dimensional computer model 15 of the subject object. In this embodiment, the subject object is imaged on a calibration object (a two dimensional photographic mat in this embodiment) which has a known pattern of features thereon, and the positions and orientations at which the input images were 20 recorded are calculated by detecting the positions of the features of the calibration object pattern in the images.

The 3D computer surface model of the subject object is generated using a conventional voxel carving technique.

As a preliminary step to generating the 3D computer 25 model, images of the subject object are processed to

segment image data relating to the subject object from other image data (background image data). Each image

is tested to determine whether the viewing direction of the camera when the image was recorded is within a 5 predetermined angle of being vertical. If this is the case, then automatic segmentation processing is not performed for the image. In addition, the image is not used to generate the 3D computer surface shape model unless the user segments the image data manually (that lO is, the segmentation processing is carried out in accordance with user instructions rather than automatically). In this way, images in which surface features (such as shadows marks, features in the pattern of the calibration object etc) are likely to appear 15 touching the subject object (because of the angle of the viewing direction which causes the camera to look down on the subject object and the surface on which it sits) are excluded from automatic segmentation processing and subsequent processing to generate the 3D computer surface 20 shape model. Consequently, because these excluded images are images for which automatic segmentation processing is likely to generate inaccurate results, the accuracy of the resulting 3D computer surface model is improved.

25 When programmed by the programming instructions,

1 1 processing apparatus 2 can be thought of as being configured as a number of functional units for performing processing operations.

5 Examples of such functional units and their interconnections are shown in Figure 1. The units and interconnections illustrated in Figure 1 are, however, notional and are shown for illustration purposes only to assist understanding; they do not necessarily represent 10 units and connections into which the processor(s), memory etc of the processing apparatus 2 become configured.

Referring to the functional units shown in Figure 1, central controller 20 is operable to process inputs from 15 the user input devices 6, and also to provide control and processing for the other functional units. Memory 24 is provided for use by central controller 20 and the other functional units.

20 Mat generator 30 is operable to generate control signals to control printer 8 or display panel 10 to print a photographic mat 34 on a recording medium such as a piece of paper, or to display the photographic mat on display panel lo. As will be described in more detail below, the 25 photographic mat comprises a predetermined pattern of

e i;. : features and the object(s) for which a three-dimensional computer model is to be generated is placed on the printed photographic mat 34 or on the display panel lO on which the photographic mat is displayed. Images of 5 the object and the photographic mat are then recorded and input to the processing apparatus 2. Mat generator 30 is arranged to write data to memory defining the pattern of features printed or displayed on the photographic mat for use by the processing apparatus 2 in calculating the 10 positions and orientations at which the input images were recorded. More particularly, mat generator 30 is arranged to write data to memory defining the pattern of features together with a coordinate system relative to the pattern of features (which, in effect, defines a 15 reference position and orientation of the photographic mat), and processing apparatus 2 is operable to calculate the positions and orientations at which the input images were recorded in the defined coordinate system (and thus relative to the reference position and orientation).

In this embodiment, the pattern on the photographic mat comprises spatial clusters of features for example as described in co-pending PCT patent application WO-A-01/39124 (the full contents of which are 25 incorporated herein by cross-reference) or any known

pattern of features, such as a pattern of coloured dots, with each dot having a different hue/brightness combination so that each respective dot is unique, for example as described in JP-A-9-170914, a pattern of 5 concentric circles connected by radial line segments with known dimensions and position markers in each quadrant, for example as described in "Automatic Reconstruction of 3D Objects Using A Mobile Camera" by Niem in Image and Vision Computing 17 (1999) pages 125-134, or a pattern 10 comprising concentric rings with different diameters, for example as described in "The Lumigraph" by Gortler et al in Computer Graphics Proceedings, Annual Conference Series, 1996 ACM-0-89791-764- 4/96/008.

15 In the remainder of the description, it will be assumed

that the pattern is printed by printer 8 on a recording medium (in this embodiment, a sheet of paper) to generate a printed photographic mat 34, although, as mentioned above, the pattern could be displayed on display panel 20 10 instead.

Input data store 40 is arranged to store input data input to the processing apparatus 2 for example as data stored on a storage medium, such as disk 42, as a signal 44 25 transmitted to the processing apparatus 2, or using a

user input device 6. The input data defines a plurality of images of one or more subject objects on the photographic mat recorded at different positions and orientations, and an input image showing the background

5 against which the object(s) was imaged. In addition, in this embodiment, the input data also includes data defining the intrinsic parameters of the camera which recorded the images, that is, the aspect ratio, focal length, principal point (the point at which the optical lO axis intersects the imaging plane), first order radial distortion coefficient, and skew angle (the angle between the axes of the pixel grid; because the axes may not be exactly orthogonal).

15 The input data defining the input images may be generated for example by downloading pixel data from a digital camera which recorded the images, or by scanning photographs using a scanner (not shown). The input data defining the intrinsic camera parameters may be input by 20 a user using a user input device 6.

Camera calculator 50 is operable to process each input image to detect the positions in the image of the features on the photographic mat and to calculate the 25 position and orientation of the camera when the input

image was recorded.

Image data segmenter 60 is operable to read the respective viewing direction for each input image 5 calculated by camera calculator 50, to exclude input images from segmentation processing if the viewing direction is within a predetermined angle of vertical, and processes each remaining input image to separate image data corresponding to the subject object from other lo image data in the image.

Image segmentation editor 70 is operable, under user control, to perform segmentation processing for any input image for which segmentation processing was not performed 15 automatically by image data segmenter 60, and also to edit the segmented image data generated by image data segmenter 60. As will be explained in more detail below, this allows the user to segment manually an image for which the viewing direction prevents automatic 20 segmentation, and also allows a user to correct an image segmentation produced by image data segmenter 60. Such correction may be necessary for example to correct pixels mistakenly determined by image data segmenter 60 to relate to the subject object 210 (for example pixels 25 relating to marks or other features visible on the

hi surface on which the photographic mat 34 and subject object are placed for imaging, pixels relating to shadows on the photographic mat 34 and/or surface on which it is placed and pixels relating to a feature on the 5 photographic mat 34 which touches the outline of the subject object in the input image have all been found to be mistakenly classified during image data segmentation and to lead to inaccuracies in the resulting 3D computer model if not corrected).

Surface modeller 80 is operable to process the segmented image data produced by image data segmenter 60 and image segmentation editor 70 and the data defining the positions and orientations at which the images were 15 recorded generated by camera calculator 50, to generate data defining a 3D computer model representing the actual surfaces of the object(s) in the input images. Input images which were not segmented by image data segmenter 60 or by image segmentation editor 70 are not used in the 20 processing by surface modeller 80 to generate the 3D computer surface model.

Surface texturer 90 is operable to generate texture data from the input image data for rendering onto the surface 25 model produced by surface modeller 80. Any of the input

images may used in this processing, irrespective of whether they were segmented by image data segmenter 60 or image segmentation editor 70 or not segmented at all.

5 Icon controller 100 is operable to control the display on display device 4 of icons representing the input images and the processing performed thereon, so that the user can see the input images to be processed and the progress of processing performed by processing apparatus 10 2, and also so that the user can see the results of processing and select any results for editing if necessary. Display processor 110, under the control of central 15 controller 20, is operable to generate data for display on display device 4 defining instructions to the user.

In addition, under the control of central controller 20, display processor 110 is also operable to generate data for display defining images of the 3D computer model of 20 the object from a user-selected viewpoint by processing the surface model data generated by surface modeller 80 and rendering texture data produced by surface texturer 90 onto the surface model.

25 Output data store 120 is arranged to store data defining

the camera positions and orientations calculated by camera calculator 50 for each input image, the image data relating to the subject object from each input image generated by image data segmenter 60 and image 5 segmentation editor 70, and also the surface model and the texture data therefor generated by surface modeller 80 and surface texturer 90. Central controller 20 is operable to control the output of data from output data store 120, for example as data on a storage device, such 10 as disk 122, andior as a signal 124. A recording of the output data may be made by recording the output signal 124 either directly or indirectly using recording apparatus (not shown).

15 Referring to Figure 2, the printed photographic mat 34 is placed on a surface 200, and the subject object 210 for which a 3D computer model is to be generated is placed on an object support 220 on the photographic mat 34 so that the object support 220 is surrounded by the 20 features making up the pattern on the mat.

Preferably, the surface 200 is of a substantially uniform colour, which, if possible, is different to any colour in the subject object 210 so that, in input images, image 25 data relating to the subject object 210 can be accurately

distinguished from other image data during segmentation processing by image data segmenter 60.

In this embodiment, the object support 220 comprises a 5 horizontal plate 222 supported by four cylindrical opaque legs 224.

A background screen 228 of a substantially uniform colour

is placed behind the subject object 210 and object 10 support 220. In this way, in images from low elevation viewing directions, the subject object 210 will appear only against the background screen 228, which assists in

separating image data relating to the subject object 210 and object support 220 from other image data during 15 segmentation processing by image data segmenter 60.

Images of the object 210, object support 220 and photographic mat 34 are recorded at different positions and orientations to show different parts of object 210 20 using a digital camera 230. In this embodiment, data defining the images recorded by camera 230 is input to processing apparatus 2 as a signal 44 along wire 232.

More particularly, in this embodiment, camera 230 remains 25 in a fixed position and photographic mat 34 with object

20 L support 220 and object 210 thereon is moved (translated) and rotated (for example in the direction of arrow 240) on surface 200, and photographs of the object 210 at different positions and orientations relative to the 5 camera 230 are recorded. During the rotation and translation of the photographic mat 34 on surface 200, the object support 220 and the object 210 do not move relative to the mat 34. In addition, the camera 230 is moved to record images from high elevation viewing angles 10 showing top views of the object support 220 and subject object 210.

Figure 3 shows examples of images 300, 302, 304, 306 and 308 defined in data input to processing apparatus 2 of 15 the object 210 and photographic mat 34 in different positions and orientations relative to camera 230.

Referring to Figure 3, in the example images shown, images 300, 302, 304 and 306 have been recorded from a 20 relatively low elevation viewing direction, in which the optical axis of camera 230 is substantially in line with the horizontal plate 222 of the object support 220. In this way, in images 300, 302, 304 and 306, the subject object 210 is surrounded by the background screen 228.

25 This enables image data segmenter 60 to segment

automatically image data relating to the subject object 210 accurately.

Image 308, on the other hand, has been recorded from a 5 relatively high elevation viewing direction, looking down on the subject object 210. Consequently, in image 308, the top part of the subject object 210 is outlined against the background screen 228, but the bottom part

of the subject object 210 is outlined against the TO photographic mat 34 and the horizontal plate 222 of the object support 220. This is undesirable because any shadows on the horizontal plate 222 and photographic mat 34 may appear as part of the subject object 210 and hence may not be separated from the subject object 210 by image 15 data segmenter 60 (resulting in errors in the 3D computer surface model subsequently generated). Similarly, one or more features in the pattern on the photographic mat 34 may touch the subject object 210 (as shown in image 308) and therefore appear to be part of the subject 20 object 210, with the result that the touching feature(s) may not be separated from the subject object 210 by image data segmenter 60 (again causing errors in the 3D computer surface model).

25 As will be explained further below, in this embodiment,

image data segmented 60 is arranged to perform segmentation processing for all images for which the viewing direction is below a predetermined angle (set to give.images in which the subject object 210 is surrounded 5 by the background screen 228 enabling the image data to

be segmented accurately) but not to perform segmentation processing for any image recorded from a viewing direction within a predetermined angle of vertical (resulting in images in which the subject object 210 is 10 at least partially surrounded by the pattern on the photographic mat 34 and/or the horizontal plate 222 that is, images for which automatic segmentation processing is likely to produce erroneous results).

15 Consequently, unless a high-elevation viewing direction image which is not automatically segmentated by image data segmenter 60 is subsequently segmented in accordance with user-instructions, then the image is not used in the processing by surface modeller 80 to generate the 3D 20 computer surface model of subject object 210. In this way, inaccuracies in the 3D computer surface model are avoided. In this embodiment, following the recording and input of 25 images of ob ject 210 and photographic mat 34, a further

image is recorded and input to processing apparatus 2.

This further image comprises a "background image", which

is an image of the background screen 228 alone.

5 Figure 4 shows the processing operations performed by processing apparatus 2 to process input data in this embodiment. Referring to Figure 4, at step S4-2, central controller lO 20 causes display processor 110 to display a message on display device 4 requesting the user to input data for processing. At step S4-4, data input by the user in response to the 15 request at step S4-2 is stored in the input data store 40. More particularly, in this embodiment, the input data comprises image data defining the images of the object 210 and mat 34 recorded at different positions and orientations relative to the camera 230, the "background

20 image'' showing the background screen 228, and data

defining the intrinsic parameters of the camera 230 which recorded the input images, that is the aspect ratio, focal length, principal point (the point at which the optical axis intersects the imaging plane), the first 25 order radial distortion coefficient, and the skew angle

(the angle between the axes of the pixel grid).

At step S4-6, icon controller 100 causes display processor llO to display on display device 4 a respective 5 icon for each input image of the subject object 210 stored at step 4-4 6 with the exception of the background

image). More particularly, in this embodiment, each icon comprises a reduced resolution version (a "thumb nails' image) of the corresponding input image. Each thumb nail 10 image is generated in a conventional manner. That is, to generate a thumb nail input image, the corresponding input image is either sub-sampled (so as to take one pixel from each set containing a predetermined number of adjacent pixels, rejecting the other pixels in the set 15 so that they are not displayed in the thumb nail image), or the corresponding input image is processed to calculate a value for each pixel in the thumb nail image by averaging the values of a predetermined number of adjacent pixels in the input image.

At step S4-8, camera calculator 50 processes the input data stored at stS4-4 to determine the imaging parameters of each input image (with the exception of the background image). In this embodiment, the imaging

25 parameters comprise position and orientation (and

consequently direction) of the camera 230 relative to the photographic mat 34, and hence relative to the object 210. This processing comprises, for each input image, detecting the features in the image which make up the 5 pattern on the photographic mat 34 and comparing the features to the stored pattern for the photographic mat to determine the position and orientation of the camera 230 relative to the mat. The processing performed by camera calculator 50 at step S4-14 depends upon the 10 pattern of features used on the photographic mat 34.

Accordingly, suitable processing is described, for example, in co-pending PCT patent application WO-A 01/39124, JP-A-9-170914, "Automatic Reconstruction of 3D Objects Using A Mobile Camera" by Niem in Image and 15 Vision Computing 17 (1999) pages 125-134 and "The Lumigraph" by Gortler et al in Computer Graphics Proceedings, Annual Conference Series, 1996 ACM-0-89791 764-4/96/008.

20 At step S4-10, image data segmenter 60 generates data defining a hash table for use in subsequent image data segmentation processing.

Figure 5 shows the processing operations performed by 25 image data segmented 60 at step S4-10.

Referring to Figure 5, at steps S5-2 to S5-10, image data segmenter 60 builds a hash table of quantised values representing the colours in the input images which represent the background screen 228.

More particularly, at step S5-2, image data segmenter 60 reads the RBG data values for the next pixel in the "background image'' stored at step S4-4 in Figure 4 (that

is, the final image to be input to processing apparatus 10 2 which shows the background screen 228).

At step S5-4, image data segmenter 60 calculates a quantized red (R) value, a quantised green (G) and a quantised blue (B) value for the pixel in accordance with 15 the following equation: (p +t/2) q =..., (1) t 20 where:.'q" is the quantized value; tip'' is the R. G or B value read at step S5-2;

tt'' is a threshold value determining how near ROB values from an input image showing the object 210 need to be to background colours to

be labelled as background. In this

5 embodiment, "t" is set to 4.

At step S5-6, image data segmenter 60 combines the quantised R. G and B values calculated at step S5-4 into a "triple value" in a conventional manner.

At step S5-8, image data segmenter 60 applies a hashing function to the quantised R. G and B values calculated at step S5-4 to define a bin in a hash table, and adds the "triple" value defined at step S5-6 to the defined 15 bin. More particularly, in this embodiment, image data segmenter 60 applies the following hashing function to the quantized R. G and B values to define the bin in the hash table:

20 h(q)=(qre&7)*2 6+(qgreen&7)*2 3+(qblue&7) (2) That is, the bin in the hash table is defined by the three least significant bits of each colour. This function is chosen to try and spread out the data into 25 the available bins in the hash table, so that each bin

has only a small number of "triple.' values. In this embodiment, at step S5-8, the ''triple" value is added to the bin only if it does not already exist therein, so that each "triple" value is added only once to the hash 5 table,

At step S5-10, image data segmenter 60 determines whether there is another pixel in the background image. Steps

S5-2 to S5-10 are repeated until each pixel in the 10 "background" image has been processed in the manner

described above. As a result of this processing, a hash table is generated containing values representing the colours in the "background" image.

15 Referring again to Figure 4, step S4-12, image data segmenter 60 selects the next input image stored at step S4-4 for processing (this being the first input image the first time step S4-12 is performed).

20 At step S4-14, image data segmenter 60 determines whether the viewing direction calculated at step S4-8 for the image selected at step S4-12 is within a predetermined angle of being vertically down, More particularly, in this embodiment, image data segmenter 60 determines 25 whether the viewing direction is within 30 degrees of the

vertical down direction. Thus, image data segmentor 60 determines whether the viewing direction of the input image is within a range of viewing directions defining a cone having a vertical axis and an apex angle of 60 .

Consequently, by performing this processing at step S4 14, image data segmenter 60 determines whether the input image selected at step S4-12 is an image for which automatic data segmentation processing is likely to 10 generate accurate results or whether the image is such that automatic image data segmentation processing is likely to generate inaccurate results (because the viewing direction of the image is sufficiently elevated that it results in an image such as image 308 shown in 15 Figure 3, in which the subject object 210 is at least partially surrounded by the pattern on the photographic mat 34 and/or by the horizontal plate 222 of the object support 220).

20 If it is determined at step S4-14 that the viewing direction is not within the predetermined angle of the vertical, then processing proceeds to step S4-16, at which image data segmenter 60 performs automatic segmentation processing of the image. On the other hand, 25 if it is determined at step S4-14 that the viewing

direction of the image is within the predetermined angle of vertical (such that the image is likely to be of a composition for which automatic image data segmentation processing may produce inaccurate results) then the 5 processing at step S4-16 is omitted.

At step S4-16, image data segmented 60 uses the hash table generated at step S4-10 to segment the data in the input image selected at step S4-12 relating to the 10 subject object 210 from the data in the image relating to the background screen 228. While the segmentation

processing is being performed, the corresponding icon displayed on display device 4 is changed so that the user can monitor the progress of the processing for the input 15 image (by looking at the corresponding icon).

Figure 6 shows the processing operations performed by image data segmenter 60 at step S4-16.

20 Referring to Figure 6, at step S6-2, image data segmented 60 reads the R. G and B values for the next pixel in the input image currently being processed (this being the first pixel the first time step S6-2 is performed).

25 At step S6-4, image data segmenter 60 calculates a

quantised R value, a quantised G value and a quantised B value for the pixel using equation (1) above.

At step S6-6, image data segmenter 60 combines the 5 quantised R. G and B values calculated at step S6-4 into a "triple value".

At step S6-8, image data segmenter 60 applies a hashing function in accordance with equation (2) above to the 10 quantised values calculated at step S6-4 to define a bin in the hash table generated at step S4-10.

At step S6-10, image data segmenter 60 reads the "triple" values in the hash table bin identified at step S6-8, 15 these ''triple" values representing the colour(s) of the background screen 228.

At step S6-12, image data segmenter 60 determines whether the "triple" value generated at step S6-6 for the pixel 20 in the input image currently being considered is the same as any of the background "triple" values in the hash

table bin read at step S6-10.

If it is determined at step S6-12 that the ''triple" value 25 of the pixel is the same as a background ''triple'' value,

then, at step S6-14, it is determined that the pixel is a background pixel and the value of the pixel is set to

"black". 5 On the other hand, if it is determined at step S6-12 that the "triple" value of the pixel is not the same as any "triple" value of the background, then, at step S6-16,

it is determined that the pixel is part of the subject object 210 and image data segmenter 60 sets the value of 10 the pixel to "white".

At step S6-18, image data segmented 60 determines whether there is another pixel in the input image. Steps S6-2 to S6-18 are repeated until each pixel in the input image 15 has been processed in the manner described above.

At steps S6-20 to S6-34, image data segmenter 60 performs processing to correct any errors in the classification of image pixels as background pixels or object pixels,

20 and to update the corresponding thumb nail image to show the current status of the segmentation processing.

More particularly, at step S6-20, image data segmenter 60 defines a circular mask for use as a median filter.

25 In this embodiment, the circular mask has a radius of 4

pixels. At step S6-22, image data segmenter 60 performs processing to place the centre of the mask defined at 5 step S6-20 at the centre of the next pixel in the binary image generated at steps S6-14 and S6-16 (this being the first pixel the first time step S6-22 is performed).

At step S6-24, image data segmenter 60 counts the number 10 of black pixels and the number of white pixels within the mask. At step S6-26, image data segmenter 60 determines whether the number of white pixels within the mask is greater 15 than or equal to the number of black pixels within the mask. If it is determined at step S6-26 that the number of white pixels is greater than or equal to the number of 20 black pixels, then, at step S6-28 image data segmenter 60 sets the value of the pixel on which the mask is centred to white. On the other hand, if it is determined at step S6-26 that the number of black pixels is greater than the number of white pixels then, at step S6-30, 25 image data segmenter 60 sets the value of the pixel on

which the mask is centred to black.

At step S6-32, icon controller 100 causes display processor 110 to update the icon displayed on display 5 device 4 for the input image for which segmentation processing is currently being carried out. More particularly, in this embodiment, the icon corresponding to the image for which segmentation is being performed is changed by icon controller 100 to take account of the 10 result of the segmentation processing previously performed on the pixel at steps S6-22 to S6-30. Thus, the icon is updated incrementally as each pixel in the input image is processed. In this embodiment, icon controller 100 causes display processor 110 to change the 15 thumb nail image so that image data in the input image which is determined to represent the background is

presented as a predetermined colour, for example blue, in the thumb nail image.

20 As a result of changing the icons in this way, not only can the user see which parts of the input image have been processed and also which complete input images remain to be processed, but the user can also see the result of the segmentation processing and hence can determine whether 25 any amendment is necessary.

At step S6-34' image data segmenter 60 determines whether there is another pixel in the binary image to be processed, and steps S6-22 to S6- 34 are repeated until eachpixel has been processed in the way described above.

Referring again to Figure 4, at step S4-18, image data segmenter 60 determines whether there is another input image stored at step S4-4 to be processed. Steps S4-12 to S4-18 are repeated until each input image has been 10 processed in the way described above.

At step S4-20, central controller 20 determines whether a signal has been received from a user via a user input device 6 indicating that the user wishes to segment 15 manually an input image which was excluded from automatic segmentation processing at step S4-16 because of the test at step S4-14 or indicating that the user wishes to amend an image segmentation generated at step S4-16 (this signal being generated in this embodiment by the user 20 pointing and clicking on the icon corresponding to the image/segmentation which it is desired to segment/amend).

If it is determined at step S4-20 that an input image is to be segmented manually or that an image segmentation 25 is to be changed manually then, at step S4-22, image

segmentation editor 70 segments the selected input image or amends the selected segmentation in accordance with user input instructions.

5 Figure 7 shows the processing operations performed by image segmentation editor 70 at step S4-20 during the interactive segmentation of an input image or the interactive amendment of an image segmentation.

10 Referring to Figure 7, at step S7-2, image segmentation editor 70 causes display processor 110 to display the input image or image segmentation selected by the user at step S4-20 (by pointing and clicking on the corresponding icon) on display device 4 for editing.

15 More particularly, in this embodiment, the input image or image segmentation selected by the user at step S4-20 is displayed in a window in a form larger than that in the icon image (in this embodiment, it is displayed with the same number of pixels as the original input image).

Also at step S7-2, image segmentation editor 70 causes display processor 110 to display a window moveable by the user over the displayed input image/image segmentation.

In addition, image segmentation editor 70 causes display 25 processor 110 to display a second window in which the

part of the image segmentation contained in the moveable window is shown in magnified form so that the user can see the pixels therein more clearly.

5 At step S7-4, image segmentation editor 70 changes the pixels displayed in the second window from background

pixels to object pixels (that is, pixels representing object 210) and/or changes object pixels to background

pixels in accordance with user instructions. More 10 particularly, for editing purposes, image segmentation editor 70 causes display processor 110 to display a pointer which, in this embodiment, has the form of a brush, which the user can move using a user input device 6 such as a mouse to designate pixels to be changed in 15 the second window. In this embodiment, each pixel which the user touches with the pointer changes to an object pixel if it was previously a background pixel or changes

to a background pixel if it was previously an object

pixel. In this embodiment, segmentation editor 70 causes 20 display processor 110 to display a first user-selectable button, the selection of which causes the pointer to become wider (so that more pixels can be designated at the same time thereby enabling large areas in the second window to be changed quickly) and a second user 25 selectable button, the selection of which causes the

pointer to become narrower.

By performing processing in this way, the user is able to segment manually any input image excluded from the 5 automatic segmentation processing at step S4-16 as a result of the viewing direction test at step S4-14. In addition, the user is, for example, able to edit a segmentation generated by image data segmenter 60 at step S4-16 to designate as background pixels any pixels

10 mistakenly determined by image data segmenter 60 to relate to the subject object 210 and/or to designate as background pixels pixels relating to each feature on the

photographic mat 34 which touches the outline of the subject object 210 in an image segmentation. Similarly, 15 the user is able to designate as background pixels pixels

relating to shadows on the photographic mat 34 and/or surface 200 which have mistakenly been determined by image data segmenter 60 to be pixels relating to the subject object 210.

At step S7-6, after the user has finished editing the input image/segmentation currently displayed (which is indicated to apparatus 2 by the user pointing and clicking on a different icon or by pointing and clicking 25 on a continue processing' button), icon controller 100

causes display processor 110 to change the displayed icon corresponding to the input image/segmentation edited by the user at step S7-4 to show the changes made thereto.

5 Referring again to Figure 4, at step S4-24, image segmentation editor 70 determines whether the user wishes to segment manually any further input images and/or whether the user wishes to make any further changes to an image segmentation, that is, whether the user has 10 pointed and clicked on a further icon.

When it is determined at step S4-20 or step S4-24 that no further input images are to be manually segmented and that no further changes are to be made to an image 15 segmentation (that is, the user has pointed and clicked on the "continue processing" button), then processing proceeds to step S4-26.

At step S4-26, surface modeller 80 performs processing 20 to generate data defining a 3D computer model of the surface of subject object 210 and the object support 220.

In this embodiment, the processing at step S4-26 is performed in a conventional manner, and comprises the 25 following three stages:

ll: (1) The camera positions and orientations generated at step S4-18 and the segmented image data generated at steps S4-16 and S4-22 is processed to generate a voxel carving, which comprises data defining a 3D 5 grid of voxels enclosing the object.

Consequently, any input image which is not segmented automatically by image data segmenter 60 at step S4-16 or manually by the user at step S422 10 is excluded from the processing to generate the 3D computer model defining the surface for the subject object 210.

Surface modeller 80 performs processing for this 15 stage in a conventional manner, for example as described in "Rapid Octree Construction from Image Sequences" by R. Szeliski in CVGIP: Image Understanding, Volume 58, Number 1, July 1993, pages 23-32. However, in this embodiment, the 20 start volume defined by surface modeller 80 on which to perform the voxel carve processing comprises a cuboid having vertical side faces and horizontal top and bottom faces. The vertical side faces are positioned so that they touch the edge of 25 the pattern of features on the photographic mat 34

(and therefore wholly contain the subject object 210). The position of the top face is defined by intersecting a line from the focal point of the -camera 230 through the top edge of any one of the 5 input images stored at step S4-4 with a vertical line through the centre of the photographic mat 34.

More particularly, the focal point of the camera 230 and the top edge of an image are known as a result of the position and orientation calculations 10 performed at step S4-8 and, by setting the height of the top face to correspond to the point where the line intersects a vertical line through the centre of the photographic mat 34, the top face will always be above the top of the subject object 15 210 (provided that the top of the subject object 210 is visible in each input image). The position of the horizontal base face is set to be the plane of the photographic mat 34, By setting the position of the base face in this way, features in 20 the pattern on the photographic mat 34 (which were not separated from the subject object in the image segmentation performed at step S4-16 or step S4-22) will be disregarded during the voxel carving processing and a 3D surface model of the subject 25 object 210 and object support 220 alone will be

generated. (2) The data defining the voxel carving is processed to generate data defining a 3D surface mesh of 5 triangles defining the surface of the object 210 and the surface of object support 220. In this embodiment, this stage of the processing is performed by surface modeller 80 in accordance with a conventional marching cubes algorithm, for 10 example as described in W.E.Lorensen and H.E.Cline: Marching Cubes: A High Resolution 3D Surface Construction Algorithm", in Computer Graphics, SIGGRAPH 87 proceedings, 21: 163-169, July 1987, or J. Bloomenthal: "An Implicit Surface Polygonizer", 15 Graphics Gems IV, AP Professional, 1994, ISBN 0123361559, pp 324-350.

(3) The number of triangles in the surface mesh generated at stage 2 is substantially reduced by 20 performing a decimation process.

In stage 3, surface modeller 80 performs processing in this embodiment to carry out the decimation process by randomly removing vertices from the triangular mesh 25 generated in stage 2 to see whether or not each vertex

contributes to the shape of the surface of object 210 or object support 220. Vertices which do not contribute to the shape are discarded from the triangulation, resulting in fewer vertices (and hence fewer triangles) in the 5 final model. The selection of vertices to remove and test is carried out in a random order in order to avoid the effect of gradually eroding a large part of the surface by consecutively removing neighbouring vertices.

The decimation algorithm performed by surface modeller 10 80 in this embodiment is described below in pseudo-code.

INPUT Read in vertices Read in triples of vertex IDs making up triangles PROCESSING

Repeat NVERTEX times Choose a random vertex V, which hasn't been chosen before 20 Locate set of all triangles having V as a vertex, S Order S so adjacent triangles are next to each other Re-triangulate triangle set, ignoring V (i.e. remove selected triangles & V and then fill in hole) 25 Find the maximum distance between V and the plane

i of each triangle If (distance < threshold) Discard V and keep new triangulation Else 5 Keep V and return to old triangulation OUPUT Output list of kept vertices Output updated list of triangles Since the absolute positions of the features on photographic mat 34 are known (the features having been printed in accordance with prestored data defining the positions), the 3D computer model of the surface of 15 object 210 and object support 220 is generated at step S4-26 to the correct scale.

At step S4-28, surface texturer 90 processes the input image data to generate texture data for each surface 20 triangle in the surface model generated by surface modeller 80 at step S4-26.

More particularly, in this embodiment, surface texturer 90 performs processing in a conventional manner to select 25 each triangle in the surface mesh generated at step S4-26

and to find the input image "i" which is most front facing to a selected triangle. That is, the input image is found for which the value n.vi is largest, where no is the triangle normal and vi is the viewing direction 5 for the "i"th image. This identifies the input image in which the selected surface triangle has the largest projected area.

The selected surface triangle is then projected into the 10 identified input image, and the vertices of the projected triangle are used as texture coordinates to define an image texture map.

Consequently, image data from an input image may be used 15 to generate texture data at step S4-28 even if the input image was not segmented by the processing at step S4-16 or step S4-22 and consequently was not used in the processing to generate the 3D surface model at step S4 26. The result of performing the processing described above is a VRML (or similar format) model of the surface of object 210 and object support 220, complete with texture coordinates defining image data to be rendered onto the 25 model.

l At step S4-30, central controller 20 outputs the data defining the 3D computer model from output data store 120, for example as data stored on a storage device such as disk 122 or as a signal 124 (Figure 1). In addition, 5 or instead, central controller 20 causes display processor 110 to display an image of the 3D computer model rendered with texture data in accordance with a viewpoint input by a user, for example using a user input device 6. Alternatively, the data defining the position 10 and orientation of the camera 230 for each input image generated at step S418 and the data defining the segmentation of each input image generated at steps S4-16 and S4-22 may be output, for example as data recorded on a storage device such as disk 122 or as a signal 124.

15 This data may then be input into a separate processing apparatus programmed to perform steps S4-26 and S4-28.

Second Embodiment 20 second embodiment of the invention will now be described. In the processing performed at step S4-14 in the first embodiment described above, the viewing direction of each 25 input image is compared against a prestored angle to

identify which input images are to undergo automatic segmentation processing at step S4-16 and which input images are not to undergo automatic segmentation processing. However, it is not necessary for the threshold angle used in the processing at step S4-14 to be predefined and prestored in processing apparatus 2 with the result that the threshold angle is the same for all input images lo irrespective of the subject object shown in the input images. Instead, as will now be described in the second embodiment, processing may be performed to calculate the 15 threshold angle to be used in the processing at step S4 14 in dependence upon the relative sizes of the subject object and photographic mat. In this way, the threshold angle used in the processing at step S4- 14 will vary for each set of input images to be processed, depending upon 20 the subject object shown in the input images and the size of photographic mat.

The components of the second embodiment and the processing operations performed thereby are the same as 25 those in the first embodiment, with the exception that,

firstly, the user is requested at step S4-2 to input data defining the radius (or diameter) of photographic mat 34, (this data then being stored at step S4-4) and, secondly, image data segmentor 60 performs additional processing 5 before the processing operations starting at step S4-12 in Figure 4 are performed. As will be explained below, these additional processing operations are carried out to calculate the threshold angle to be used in the processing at step S4-14.

Figure 8 shows the processing operations performed by image data segmentor 60 to calculate the threshold angle to be used in the processing at step S4-14. In this embodiment, these processing operations are performed 15 between the processing operations at steps S4-10 and S4- 12 in Figure 4.

Referring to Figure 8, at step S8-2, image data segmentor 60 selects the input image having the viewing 20 direction closest horizontal (the respective viewing direction for each input image having been previously calculated at step S4-8).

At step S8-4, image data segmentor 60 processes the input 25 image selected at step S8-2 to segment the image data of

the object from the background image data, and to change

the corresponding thumb nail image displayed to the user.

The processing operations performed at step S8-4 are the same as those performed at step S4-16 described above, 5 and accordingly these processing operations will not be described again here.

At step S8-6, image data segmentor 60 identifies the top most pixel in the input image determined during the 10 processing at step S8-4 to be a pixel relating to the subject object 210, and projects a plane through the horizontal line of pixels in the image containing the identified pixel into three-dimensional world space.

This projection is carried out using the camera 15 parameters previously stored at step S4-4 and the imaging parameters calculated at step S4-8. It should be noted that the resulting plane is not necessarily horizontal in three-dimensional world space even through the projected line is horizontal in the image (this being a 20 consequence of the projection).

Figure 9 shows an example illustrating the result of the processing performed at step S8-6.

25 Referring to Figure 9, input image 301 is assumed to be

the input image selected at step S8-2 and segmented at step S8-4, The line 350 represents the horizontal line of pixels in 5 the image 301 containingthe top-most "object'' pixel in the image (that is, the top- most pixel in the image determined at step S8-4 to relate to the subject object 210 rather than background). Plane 360 is the

plane defined by the projection of the horizontal lO line 350 into 3D space in accordance with the camera parameters of camera 230 and imaging parameters of image 301.

Referring again to Figure 8, at step S8-8, image data 15 segmentor 60 determines the point of intersection (370 in Figure 9) of the projected plane 360 with the vertical line through the centre of the photographic mat (line 380 in Figure 9). In addition, image data segmentor 60 calculates the height of the intersection point 370 above 20 the plane of the photographic mat 34. This height represents the combined height of the subject object 210 and object support 220.

At step S8-10, image data segmentor 60 performs 25 processing using the height calculated at step S8-8 and

the radius of the photographic mat stored at step S4-4 to calculate a threshold angle in accordance with the following equation: = arctan (r/h). ...(3) where "r" the radius of the photographic mat 34, and "hi' is the height of the intersection point 370 calculated at step S8-8.

In subsequent processing, image data segmentor 60 performs processing operations S4-12 to S4-30 as described above in the first embodiment, but with the difference that the input image previously selected at 15 step S8-2 is not subsequently selected for processing again at step S4-12, and the threshold angle used in the processing at step S4-14 is the angle calculated at step S8-10.

20 As a result of performing the processing described above in the second embodiment, processing apparatus 2 calculates the angle to be used in the processing at step S4-14 to determine whether or not an input image is to be automatically segmented. In this embodiment, the 25 calculation is carried out in dependence upon the height

of the subject object 210 and object support 220 relative to the radius of the photographic mat 34, with the result that the calculated angle becomes 'smeller for taller subject objects and object supports.

As a modification of the second embodiment, processing apparatus 2 may be arranged to perform processing so that the user is not required to input the radius of the photographic mat 34. For example, processing apparatus lO 2 may be arranged to perform processing as described in co-pending PCT application GBOO/04469 (WO-A-01/39l24), the full contents of which are incorporated herein by cross-reference. In this processing, processing

apparatus 2 controls the printing of the photographic mat 15 34 and stores data defining the radius of the photographic mat which it has instructed the printer to print. In addition, or instead, the processing apparatus 2 may be arranged to define the coordinate system in which the height of the subject object 210 and object 20 support 220 is calculated at step S8-8 in units of the photographic mat radius - that is, the size of one unit in the coordinate system is set to be equal to the radius of the photographic mat 34. In this way, the height of the subject object 210 and object support 220 is 25 calculated at step S8-8 in units of the photographic mat

radius. Third Embodiment 5 A third embodiment of the invention will now be described. In the first and second embodiments described above, the processing carried out at step S4-14 to determine whether 10 an input image is to be included or excluded from automatic segmentation processing is based on the viewing direction of the input image.

However, processing may be carried out to determine 15 whether or not an input image is to undergo automatic segmentation processing in dependence upon other imaging parameters calculated for the input image at step S4-8.

For example, a third embodiment will now be described 20 in which the calculated viewing position of an input image is used to determine whether automatic segmentation processing is to be performed for the input image or whether the input image is to be excluded from such processing.

The components of the second embodiment and the processing operations performed thereby are the same as those in the first embodiment, with the exception that the processing performed by image data segmentor 60 at 5 steps S4-12 to S4-18 in the first embodiment is replaced by different processing. Accordingly, only this different processing will be described below, because the other processing operations have already been described in the first embodiment.

Figure 10 shows the processing operations performed by image data segmentor 60 in the third embodiment to replace the processing performed at steps S4-12 to S4-18 in the first embodiment.

Referring to Figure 10, at steps S10-2 to S10-6, image data segmentor 60 performs processing corresponding to the processing performed at steps S82 to S8-6 in the second embodiment. Because this processing has already 20 been described, it will not be described again here.

At step S10-8, image data segmentor 60 determines the point of intersection "P" of the plane 360 projected at step S10-6 with the vertical line 380 through the centre 25 of the photographic mat 34 (the point "P" being the point

370 in Figure 9).

At step S10-10, image data segmentor 60 selects the next input image remaining to be processed (these images 5 comprising all images except the input image previously selected at step S10-2 and processed at step SlO-4).

At step S10-12, image data segmentor 60 projects the point "Pt' calculated at step S10-8 into the image 10 selected at step S10-10 using the camera parameters of camera 230 stored at step S4-4 and the imaging parameters of the input image calculated at step S4-8.

In addition, image data segmentor 60 also projects each 15 of the features making up the pattern on the photographic mat 34 into the input image in the same way.

At step S10-14, image data segmentor 60 calculates a polygon bounding the projections of the mat features in 20 the image. In this embodiment, the bounding polygon comprises a bounding box (rectangle), having sides parallel to the sides of the input image.

At step S10-16, image data segmentor 60 determines 25 whether the position in the image of the projected point

P calculated at step S10-12 lies within the bounding box calculated at step Sl0-14.

If the projected point "P'' is not inside the bounding 5 box, then it is likely that the top of the subject object 210 appears against the background screen 2Z8 in

the input image and not against the photographic mat 34.

Accordingly, in this case, processing proceeds to step Sl0-18, at which image data segmentor 60 performs 10 processing to segment the image data of the object from the background image data and to change the corresponding

thumb nail image. The processing performed by image data segmentor 60 at step Sl0-18 is the same as the processing described above with reference to step S4-16 in the first 15 embodiment, and accordingly will not be described again here. On the other hand, if it is determined at step S1016 that the projection of the point "P" is inside the 20 bounding box of the projections of the mat features, then it is likely that the top of the subject object appears surrounded by the photographic mat 34 in the input image, with the result that the automatic segmentation processing is likely to generate erroneous results.

25 Consequently, in this case, step S10-18 is not performed

with the result that automatic segmentation processing is not performed for the input image.

At step S10-20, image data segmentor 60 determines 5 whether there is another input image remaining to be processed. Steps S10-10 to S10-20 are repeated until each remaining input image has been processed in the way described above.

10 Fourth Embodiment A fourth embodiment of the invention will now be described. 15 In the second embodiment described above, the threshold angle to be used in the processing at step S4-14 is calculated by image data segmentor 60 by processing the image data of an input image to determine the height of the subject object 210 and object support 220, and then 20 using the ratio of the calculated height to the photographic mat radius to calculate the threshold angle.

However, in the fourth embodiment, at step S4-2, the user is requested to input data defining the height of the 25 subject object 210 and object support 220 as well as data

defining the radius of the photographic mat 34. Image data segmentor 60 is then arranged to calculate the threshold angle to be used in the processing at step S4-14 in accordance with equation t3) ate. Be and the data 5 input by the user.

Fifth Embodiment A fifth embodiment of the invention will now be 10 described. In the second and fourth embodiments described above, the threshold angle to be used in the processing at step S4 14 is calculated by image data segmentor 60.

However, in the fifth embodiment, the threshold angle to be used in the processing at step S4-14 is calculated by the user in accordance with equation (3) above and is input to the processing apparatus 2 and stored at step 20 S4-4.

Modifications and Variations Many modifications and variations can be made to the 25 embodiments described above within the scope of claims.

In the embodiments described above, at step S4-4, data input by a user defining the intrinsic parameters of camera 230 is stored. However, instead, default values may 'tee assumed for some, or all, of the intrinsic camera 5 parameters, or processing may be performed to calculate the intrinsic parameter values in a conventional manner, for example as described in "Euclidean Reconstruction From Uncalibrated Views" by Hartley in Applications of Invariance in Computer Vision, Mundy, Zisserman and 10 Forsyth eds, pages 237-256, Azores 1993.

In the embodiments described above, image data from an input image relating to the subject object 210 is segmented from the image data relating to the background

15 as described above with reference to Figures 5 and 6.

However, other segmentation methods may be used instead.

For example, a segmentation method may be used in which a single RGB value representative of the colour(s) of the background screen 228 is stored and each pixel in an

20 input image is processed to determine whether the Euclidean distance in RGB space between the RGB background value and the RGB pixel value is less than a

specified threshold.

25 In the embodiments described above, an input image or a

* segmentation is selected for editing at step S4-20 by the user pointing and clicking on the corresponding displayed icon. However, an input image/segmentation can be selected for editing in a way other than selecting the 5 corresponding icon. For example, a number may be entered by the user corresponding to the input image/segmentation In the embodiments described above, at step S4-26, 10 surface modeller 80 generates data defining a 3D computer model using a voxel carving technique. However, other techniques may be used, such as a voxel colouring technique for example as described in University of Rochester Computer Sciences Technical Report Number 680 15 of January 1998 entitled "What Do N Photographs Tell Us About 3D Shape?" and University of Rochester Computer Sciences Technical Report Number 692 of May 1998 entitled A Theory of Shape by Space Carving", both by Kiriakos N Kutulakos and Stephen M. Seitz. Alternatively, the 20 3D computer model may be generated using the processing described in co-pending UK patent application 0114157.1, the full extents of which are incorporated herein by cross-reference.

25 In the embodiments above, image segmentation editor 70

is arranged to perform processing at editing step S7-4 so that each pixel which the user touches with the pointer changes to an object pixel if it was previously a background pixel or changes to a background pixel if

5 it was previously an object pixel. However, instead, image segmentation editor 70 may be arranged to perform processing so that the user selects a background-to

object pixel editing mode using a user input device 6 and, while this mode is selected, each pixel which the 10 user touches with the pointer changes to an object pixel if it was previously a background pixel, but object

pixels do not change to background pixels. Similarly,

the user may select an object-to-background change.mode,

in which each pixel which the user touches with the 15 pointer changes to a background pixel if it was

previously an object pixel, but background pixels do not

change to object pixels.

In the embodiments described above, the processing 20 performed by surface model 80 at step S4-26 generates a 3D surface model of the subject object 210 and the object support 220. Further processing may be performed to remove the part of the 3D computer model representing the surface of the object support 220. This further 25 processing may be performed in a conventional manner/ for

if: example by editing the data defining the 3D computer model in accordance with user instructions to remove the polygons therein designated by the user as corresponding to the surface of object support 220. Alternatively, 5 processing may be performed to generate a 3D computer model of the surface of subject object 210 alone as described in co-pending European Patent Application 01308112.0 and co-pending US Patent Application 09/963635, the full contents of both of which are 10 incorporated herein by cross-reference.

In the embodiments described above, processing is performed by a computer using processing routines defined by programming instructions. However, some, or all, of 15 the processing could be performed using hardware.

Claims (1)

1. A method of processing data in a processing apparatus defining a plurality of images of an object 5 recorded at different positions and orientations relative to the object to generate data defining a three dimensional computer model of the object, the method comprising: processing the image data to calculate the 10 respective viewing position and direction of each image; processing the image data to segment image data relating to the object from other image data in some, but not all, of the images; and generating data defining a three-dimensional 15 computer model of the object using the results of the segmentation processing and the calculated viewing positions and directions of the images; wherein: processing is performed to test the images to 20 identify images for which segmentation processing is not to be performed, each image tested being tested in dependence upon at least one of the viewing position and direction calculated for the image; and the segmentation processing is not performed for the 25 identified images.

64 _ 2. A method according to claim 1, wherein each image is tested to determine whether segmentation processing is to be performed by testing whether the viewing 5 direction of the image is within a defined angular range.

3. A method according to claim 2, further comprising performing processing to calculate the angular range.

10 4. A method according to claim 3, wherein the angular range is calculated in dependence upon the height of the object. 5. A method according to claim 3 or claim 4, wherein 15 the angular range is calculated by processing the image data for at least one image.

6. A method according to claim 1, wherein: processing is performed to calculate the three 20 dimensional position of at least one point on the object using the image data for at least one image; and each image is tested to determine whether segmentation processing is to be performed in dependence upon the position of the calculated point when projected 25 into the image.

7. A method according to claim 6, wherein each image to be processed shows the object and a pattern of calibration features, and wherein each image is tested 5 to determine whether segmentation processing is to be performed in dependence upon the position of the calculated point when projected into the image relative to the positions of the calibration features in the Image. 8. A method according to claim 7, wherein each image is tested to determine whether segmentation processing is to be performed by testing whether the position of the calculated point when projected into the image is within 15 a polygon bounding the calibration features in the image.

9. A method according to any preceding claim, further comprising segmenting image data relating to the object from other image data in accordance with instructions 20 received from a user in at least one image for which the segmentation processing was not previously performed, and wherein the data defining the three-dimensional computer model is generated in dependence upon the results of the segmentation processing previously carried out and also 25 the results of the segmentation processing carried out

in accordance with user instructions.

10. A method according to any preceding claim, further comprising generating texture data for the three 5 dimensional computer model in dependence upon image data from at least one image for which segmentation processing was performed and at least one image for which segmentation processing was not performed.

10 11. An image processing method performed in a processing apparatus of processing data defining a plurality of images of an object recorded at different viewing positions and with different viewing directions relative to the object to generate data defining a three 15 dimensional computer model of the object, the method comprising: processing the image data to calculate viewing parameters of each image; identifying images for which automatic processing 20 to classify the data therein as either image data relating to the object or as other image data may generate erroneous results; processing the image data automatically to classify data as either image data relating to the object or as 25 other image data in at least some images, but not in any identified images; and

generating data defining a three-dimensional computer model of the object using the results of the automatic classification processing and the calculated viewing parameters of the corresponding images.

12. A method according to claim 11, wherein images for which automatic classification processing may generate erroneous results are identified in dependence upon at least one of the calculated viewing parameters.

13. A method according to any preceding claim, further comprising generating a signal carrying the data defining the three-dimensional computer model.

15 14. A method according to claim 13, further comprising making a recording of the signal either directly or indirectly. 15. Apparatus for processing data defining a plurality 20 of images of an object recorded with different viewing positions and directions relative to the object to generate data defining a three-dimensional computer model of the object, the apparatus comprising: means for processing the image data to calculate the 25 respective viewing position and direction of each image; segmentation processing means for processing the

image data to segment image data relating to the object from other image data; and model generating means for generating data defining a threedimensional computer model of the object using 5 the results of the segmentation processing and the calculated viewing positions and directions of the Images; wherein: the apparatus further comprises means for testing 10 the images to identify images for which segmentation processing is not to be performed in dependence upon at least one of the viewing position and direction of each image tested; and the segmentation processing means is arranged to be 15 responsive to the image test results so as not to perform segmentation processing for any identified image.

16. Apparatus according to claim 15, wherein the means for testing the images is operable to test each image 20 to determine whether segmentation processing is to be performed by testing whether the viewing direction of the image is within a defined angular range.

17. Apparatus according to claim 16, further comprising 25 means for calculating the angular range.

1B. Apparatus according to claim 17, wherein the means for calculating the angular range is operable to calculate the angular range in dependence upon the height of the object.

l9. Apparatus according to claim 17 or claim 18, wherein the means for calculating the angular range is operable to calculate the angular range by processing the image data for at least one image.

20. Apparatus according to claim 15, wherein the means testing the images is operable to test the images by: calculating the three-dimensional position of at least one point on the object using the image data for 15 at least one image; and testing each image to determine whether segmentation processing is to be performed in dependence upon the position of the calculated point when projected into the image. 21. Apparatus according to claim 20, wherein each image to be processed shows the object and a pattern of calibration features, and wherein the means for testing the images is operable to test each image to determine 25 whether segmentation processing is to be performed in dependence upon the position of the calculated point when

projected into the image relative to the positions of the calibration features in the image.

22. Apparatus according to claim 21, wherein the means 5 for testing the images is operable to test each image to determine whether segmentation processing is to be performed by testing whether the position of the calculated point when projected into the image is within a polygon bounding the calibration features in the image.

23. Apparatus according to any preceding claim, further comprising means for segmenting image data relating to the object from other image data in accordance with instructions received from a user, and wherein the model 15 generating means is operable to generate the data defining the threedimensional computer model in dependence upon the results of the segmentation carried out by the segmentation processing means and also the results of the segmentation processing carried out in 20 accordance with user instructions.

24. Apparatus according to any of claims 15 to 23, further comprising texture data generating means operable to generate texture data for the three-dimensional 25 computer model in dependence upon image data from at least one image for which segmentation processing was

performed and at least one image for which segmentation processing was not performed.

25. Apparatus for processing data defining a plurality 5 of images of an object to generate data defining a three dimensional computer model of the object, the apparatus comprising: means for processing the image data to calculate at least one viewing parameter of each image; 10 image testing means for identifying images for which automatic processing to classify the data therein as either image data relating to the object or as other image data may generate erroneous results; image data classification means for processing the 15 image data automatically to classify data as either image data relating to the object or as other image data, the image data classification means being arranged not to process the image data of any image identified by the image testing means as being an image for which the 20 classification processing may generate erroneous results; and means generating data defining a three-dimensional computer model of the object using the results of the automatic classification processing and the calculated 25 viewing parameters of the corresponding images.

26. Apparatus according to claim 25, wherein the image testing means is operable to identify images for which automatic classification processing may generate erroneous results in dependence upon at least one 5 calculated viewing parameter.

27. Processing apparatus comprising a memory and a processor, the processor being operable to perform processing operations in accordance with computer 10 executable instructions stored in the memory, and the memory storing computer-executable instructions for causing the processor to perform a method as set out in at least one of claims 1 to 14.

15 28. A storage medium storing instructions for programming a programmable processing apparatus to become operable to perform a method as set out in at least one of claims 1 to 14.

20 29. A signal carrying instructions for programming a programmable processing apparatus to become operable to perform a method as set out in at least one of claims 1 to 14.