Image processing method and apparatus

[0002] The present invention relates to an image processing apparatus and method and, more particularly, to an image processing apparatus and method for generating a mosaic image.

[0003] Mosaic is “a design made by inlaying a combination of small pieces of various colors of stone, glass, marble, and the like into a floor, wall, or the like, or a technique of obtaining such design” (Gendai Kokugo Jiten, Sanseido). Using this technique, a design or an image (mosaic image) can be formed by combining a large number of picture images. A mosaic image is generated by image processing as follows. That is, an original design or image is segmented into tiles, and material images most similar to images of those tiles are pasted on those tile areas.

[0004] However, the above-mentioned technique has the following problem.

[0005] More specifically, since an identical material image may often be pasted on a plurality of segmented tile areas, a concentrated region of identical material images often appears in the generated mosaic image. In such case, the material images generate a texture pattern, and an unexpected pattern may result depending on the original design or image.

[0006] The present invention has been made to solve the above problem, and has as its object to prevent an unexpected texture pattern from being formed upon generating a mosaic image.

[0007] It is another object of the present invention to prevent an unexpected texture pattern from being formed and to improve the image quality of a mosaic image by appropriately limiting use of material image upon generating the mosaic image.

[0008] It is still another object of the present invention to prevent a texture pattern from being formed in a mosaic image by limiting use of each material image to once upon generating the mosaic image.

[0009] It is still another object of the present invention to prevent an unexpected texture pattern from being formed and to improve the image quality of a mosaic image by limiting use of each material image to once and selecting areas to be replaced by material images in a random order upon generating the mosaic image.

[0010] It is still another object of the present invention to prevent an unexpected texture pattern from being formed and to improve the image quality of a mosaic image by limiting the number of times of use of each material image to a plurality of number of times, which is determined in advance.

[0011] It is still another object of the present invention to prevent an unexpected texture pattern from being formed and to improve the image quality of a mosaic image by limiting the number of times of use of each material image to a plurality of number of times, which is determined in advance, and selecting areas to be replaced by material images in a random order.

[0012] It is still another object of the present invention to improve the image quality of a mosaic image by limiting the number of times of use of each material image to a plurality of number of times, which is determined in advance, and inhibiting identical material images from being placed at neighboring positions.

[0013] It is still another object of the present invention to generate a mosaic image according to user's favor by allowing the user to replace desired areas of an automatically generated mosaic image by material images of user's choice.

[0014] Other features and advantages of the present invention will be apparent from the following description taken in conjunction with the accompanying drawings, in which like reference characters designate the same or similar parts throughout the figures thereof.

[0015] The accompanying drawings, which are incorporated in and constitute a part of the specification, illustrate embodiments of the invention and, together with the description, serve to explain the principles of the invention.

[0016] FIG. 1 shows the relationship among a plurality of types of images used in mosaic;

[0017] FIG. 2 is a flow chart for explaining a method of forming an image by mosaic;

[0018] FIG. 3 shows M×N tile areas obtained by segmenting an original image;

[0019] FIG. 4 shows the format of each tile;

[0020] FIG. 5 is a block diagram showing the arrangement of an image processing apparatus for generating a mosaic image;

[0021] FIG. 6 is a flow chart showing an example of mosaic image generation according to the first embodiment of the present invention;

[0022] FIG. 7 shows the format of a material image management table according to the first embodiment;

[0023] FIG. 8 is a flow chart showing an example of mosaic image generation according to the second embodiment of the present invention;

[0024] FIG. 9 is a flow chart showing an example of a process in the second embodiment, which is done to obtain a random tile processing order;

[0025] FIG. 10 is a flow chart showing an example of mosaic image generation according to the third embodiment of the present invention;

[0026] FIG. 11 shows the format of a material image management table according to the third embodiment;

[0027] FIG. 12 is a flow chart showing an example of mosaic image generation according to the fourth embodiment of the present invention;

[0028] FIG. 13 is a flow chart showing an example of mosaic image generation according to the fifth embodiment of the present invention;

[0029] FIG. 14 is a flow chart showing an example of mosaic image generation according to the sixth embodiment of the present invention;

[0030] FIG. 15 is a flow chart showing an example of mosaic image generation according to the seventh embodiment of the present invention;

[0031] FIG. 16 is a block diagram showing the arrangement of a computer system (image processing apparatus) according to the eighth embodiment of the present invention;

[0032] FIG. 17 is an explanatory view of a mosaic image;

[0033] FIG. 18 is a flow chart for explaining the flow of mosaic image generation in the eighth embodiment;

[0034] FIG. 19 is a flow chart showing selection of the next candidate of a material image in step S2 in FIG. 18; and

[0035] FIGS. 20 and 21 show display examples upon selection of the next candidate of a material image in the eighth embodiment.

[0036] Preferred embodiments of the present invention will now be described in detail in accordance with the accompanying drawings.

[0037] FIG. 1 shows the relationship among a plurality of types of images used in mosaic. Referring to FIG. 1, a first image 201 is an original design or image (e.g., a picture image, computer graphics image, or the like) upon forming an image by mosaic. A second image 202 is an image formed by mosaic. Material images 203 are used for forming the second image 202. The number P of material images 203 is a value large enough to prepare colors and textures required for forming the second image 202.

[0038] In FIG. 1, each material image 203 has a size equal to that of a tile for the sake of simplicity. However, the size of the material image 203 need not always be equal to the tile size, and all the material images 203 need not always have equal sizes. When the size of the material image 203 is different from the tile size, the material image 203 to be pasted need only be resized upon pasting that image 203 to the corresponding tile area. Also, the tile shape is not limited to a rectangle but may be an arbitrary shape. Upon pasting the material image 203 on a tile area, the material image 203 need only be cut or deformed to match the tile shape.

[0039] A method of forming a mosaic image using material images will be explained below with reference to FIG. 2.

[0040] In step S21 in FIG. 2, the first image 201 is segmented into M×N tiles. As a result, as shown in, e.g., FIG. 3, 4×5 rectangular tiles TL(0, 0), TL(1, 0), TL(2, 0), . . . , TL(2, 4), and TL(3, 4) are generated.

[0041] Referring to FIG. 3, X and Y respectively represent the numbers of horizontal and vertical pixels of the first image 201, and p and q respectively represent the numbers of horizontal and vertical pixels of each segmented tile. Hence, X=p×M and Y=q×N. FIG. 4 shows the format of each tile. Each tile is decomposed into p×q pixel planes of three primary colors, i.e., red, green, and blue.

[0042] Subsequently, in step S22, R, G, and B average luminance values of each of the M×N segmented tiles are calculated by:

[0043] Rd_av=ΣRi/(p×q)

[0044] Gd_av=ΣGi/(p×q)

[0045] Bd_av=ΣBi/(p×q)

[0046] In step S23, R, G, and B average luminance values of each of the P material images 203 are calculated by:

[0047] Rs_av=ΣRi/(p×q)

[0048] Gs_av=ΣGi/(p×q)

[0049] Bs_av=ΣBi/(p×q)

[0050] In step S24, counters X_Pos (0≦X_Pos≦M−1) and Y_Pos (0≦Y_Pos≦N−1) indicating the position of a tile of interest are reset to zero. Note that (X_Pos, Y_Pos)=(0, 0) indicates the upper left tile position of the first image 201.

[0051] In step S25, a material image 203 most suitable for a tile indicated by the counters (X_Pos, Y_Pos) is selected. In this selection method, a distance ΔE given by

[0052] ΔE=(Rs_av−Rd₋av){circumflex over ( )}2+(Gs₋av−Gd₋av){circumflex over ( )}2+(Bs_av−Bd_av){circumflex over ( )}2

[0053] where a{circumflex over ( )}2 is the square of a

[0054] is calculated based on R, G, and B tristimulus values between the average luminance values of each tile and those of each material image 203, and a material image 203 with the smallest ΔE is selected. Upon pasting the selected material image 203 on a tile area, if its size does not match that of the tile area, the material image 203 is enlarged/reduced to have an appropriate size.

[0055] In step S26, the counters (X_Pos, Y_Pos) are counted up or down sequentially in the horizontal and vertical directions, and steps S25 to S27 repeat themselves until it is determined in step S27 that the process in step S25 is done for all tiles.

[0056] Hence, when a mosaic image is generated by the aforementioned processing, if M×N segmented tiles include those which have the same or nearby average luminance values, an identical material image 203 is selected and is pasted on these tile areas. For this reason, in a concentrated region of identical material images 203 in the generated mosaic image 202, those material images 203 form an unexpected pattern, and an unexpected pattern is generated in the mosaic image 202.

[0057] FIG. 5 is a block diagram showing an example of the arrangement of an image processing apparatus for generating a mosaic image according to an embodiment of the present invention.

[0058] Referring to FIG. 5, a reading unit 100 is, e.g., a scanner for reading an image. A storage unit 101 stores and manages images in a storage medium such as a hard disk or the like, and constructs, e.g., an image database. A display 102 is a monitor such as a CRT, LCD, or the like for displaying images stored in the storage unit 101 or an image read by the reading unit 100.

[0059] A CPU 103 controls the overall image processing apparatus in accordance with a program pre-stored in a ROM 104, and takes part in all the aforementioned processes. A RAM 105 is used as a work memory of the CPU 103.

[0060] Note that the image processing apparatus of this embodiment has various other building elements in addition to the above-mentioned units. However, since the arrangement of these elements is not the principal part of the present invention, a detailed description thereof will be omitted.

[0061] Mosaic image generation in the image processing apparatus of this embodiment will be described below with reference to the flow chart in FIG. 6.

[0062] In step S60 in FIG. 6, the first image 201 is segmented into M×N tiles. As a result, as shown in, e.g., FIG. 3, 4×5 rectangular tiles TL(0, 0), TL(1, 0), TL(2, 0), . . . , TL(2, 4), and TL(3, 4) are generated.

[0063] Subsequently, in step S61, R, G, and B average luminance values of each of the M×N segmented tiles are calculated by:

[0064] Rd_av=ΣRi/(p×q)

[0065] Gd_av=ΣGi/(p×q)

[0066] Bd_av=ΣBi/(p×q)

[0067] In step S62, R, G, and B average luminance values of each of the P material images 203 are calculated by:

[0068] Rs_av=ΣRi/(p×q)

[0069] Gs_av=ΣGi/(p×q)

[0070] Bs_av=ΣBi/(p×q)

[0071] Note that the image characteristics such as R, G, and B average luminance values of the material images 203 may be obtained in advance. In this case, the image characteristics may be recorded as header information of each material image 203, or may be recorded in a table which is stored in the storage unit 101 and corresponds to the material image 203.

[0072] FIG. 7 shows an example of the data format of a material image management table according to the first embodiment. In this embodiment, the material image management table shown in FIG. 7 stores feature amounts (average luminance values) calculated in step S62. More specifically, a pair of a material image ID that specifies each material image, and feature amounts of the material image corresponding to that material image ID are registered. When such material image management table is stored in the storage unit 101, the feature amount calculations of the material images need not be repeated.

[0073] In step 63, used flags of all the P material images 203 are reset to OFF. Note that the “used flag” indicates whether or not the corresponding material image 203 is pasted on the first image 201. At the time of step S63, since none of material images 203 have been selected and pasted, the used flags of all the P material images 203 are reset to OFF.

[0074] Note that the used flags are held in the material image management table in units of material images, as shown in FIG. 7.

[0075] In step S64, counters X_Pos (0≦X_Pos≦M−1) and Y_Pos (0≦Y_Pos≦N−1) indicating the position of a tile of interest are reset to zero, so as to start processing from the upper left tile position of the first image 201 corresponding to (X_Pos, Y_Pos)=(0, 0).

[0076] In step S65, a material image 203 most suitable for a tile indicated by the counters (X_Pos, Y_Pos) is selected from those with OFF used flags. In this selection method, a distance ΔE given by

[0077] ΔE=(Rs_av−Rd_—av){circumflex over ( )}2+(Gs_av−Gd_av){circumflex over ( )}2+(Bs_av−Bd_av){circumflex over ( )}2

[0078] is calculated based on R, G, and B tristimulus values between the average luminance values of each tile and those of each material image 203, and a material image 203 with the smallest ΔE is selected. Upon pasting the selected material image 203 on a tile area, if its size or shape does not match that of the tile area, the material image 203 is enlarged/reduced to have an appropriate size or shape.

[0079] In step S66, a used flag in the material image management table shown in FIG. 7 corresponding to the material image 203 which is selected and pasted on the first image 201 is set to be ON, so as to inhibit the selected material image 203 from being pasted on another tile area.

[0080] In step S67, the counters (X_Pos, Y_Pos) are counted up or down sequentially in the horizontal and vertical directions, and steps S65 to S67 repeat themselves until it is determined in step S68 that the process in step S65 is done for all tiles.

[0081] As described above, according to the first embodiment, since a material image selected once is not used again in a single mosaic image, an unexpected texture pattern can be prevented from being formed by identical material images.

[0082] In the first embodiment, an unexpected texture pattern is prevented from being formed using a method of inhibiting a material image 203 which has been pasted on a given tile area from being pasted on another tile area. However, since material images 203 are pasted in the order from the upper left tile to the lower right tile without using identical material images 203, a material image 203, the average luminance values of which are relatively close to those of a tile image, can be selected from many material images 203 in the upper left region on the first image 201, but the number of material images 203 that can be used decreases on the lower right region of the first image 201, and it often becomes harder to select a material image 203 having average luminance values close to those of a tile image. Therefore, a mosaic image generated in this way suffers certain image quality discrepancy between its upper left region and lower right region.

[0083] The second embodiment solves this problem. Note that the arrangement of an image processing apparatus in the second embodiment is the same as that in the first embodiment, and a detailed description thereof will be omitted.

[0084] Mosaic image generation in the image processing apparatus of the second embodiment will be described below with reference to the flow chart in FIG. 8.

[0085] In step S80 in FIG. 8, the first image 201 is segmented into M×N tiles. As a result, as shown in, e.g., FIG. 3, 4×5 rectangular tiles TL(0, 0), TL(1, 0), TL(2, 0), . . . , TL(2, 4), and TL(3, 4) are generated.

[0086] Subsequently, in step S81, R, G, and B average luminance values of each of the M×N segmented tiles are calculated by:

[0087] Rd_av=ΣRi/(p×q)

[0088] Gd_av=ΣGi/(p×q)

[0089] Bd_av=ΣBi/(p×q)

[0090] In step S82, R, G, and B average luminance values of each of the P material images 203 are calculated by:

[0091] Rs_av=ΣRi/(p×q)

[0092] Gs_av=ΣGi/(p×q)

[0093] Bs_av=ΣBi/(p×q)

[0094] Note that the image characteristics such as R, G, and B average luminance values of the material images 203 may be obtained in advance. In this case, the image characteristics may be recorded as header information of each material image 203, or may be recorded in a table which is stored in the storage unit 101 and corresponds to the material image 203.

[0095] In step S83, used flags of all the P material images 203 are reset to OFF. Note that the “used flag” indicates whether or not the corresponding material image 203 is pasted on the first image 201. At the time of step S83, since none of material images 203 have been selected and pasted, the used flags of all the P material images 203 are reset to OFF.

[0096] Note that the image characteristics (average luminance values in this embodiment) obtained in step S82 and used flags are stored in a table shown in FIG. 7, as in the first embodiment.

[0097] In step S84, data indicating a random processing order of tiles are stored in a matrix T_Turn[M*N−1]. Note that the matrix stores data so that the quotient K/(M−1) indicates a Y-coordinate and the remainder indicates an X-coordinate when T_Turn[ ]=K. The method of storing the random processing order of tiles in that matrix will be explained below with reference to the flow chart in FIG. 9.

[0098] Referring to FIG. 9, T_Turn[0]=0, T_Turn[1]=1, T_Turn[2]=2, . . . , T_Turn[M*N−1]=M*N−1 are temporarily stored in the matrix in step S90. M*N−1 is set in counter i in step S91, and a random number R ranging from 1 to i is generated in step S92.

[0099] In step S93, data stored in T_Turn[R] and T_Turn[i] are replaced with each other in accordance with the generated random number R. In step S94, counter i is decremented (i=i−1). If it is determined in step S95 that i≧0, the flow returns to step S92; otherwise, data replacement ends.

[0100] In this way, data for processing tiles in the random order are stored in the matrix T_Turn[M*N−1].

[0101] In step S85 in FIG. 8, counter j is reset to zero. In step S86, a material image 203 having average luminance values closest to those of a tile image designated by T_Turn[j] is selected. The material images 203 as selection candidates are only those with OFF used flags in the material image management table shown in FIG. 7. For example, when T_Turn[j]=0, the tile position is (0, 0), i.e., the upper left tile. In this selection method, a distance ΔE given by

[0102] ΔE=(Rs_av−Rd_av){circumflex over ( )}2+(Gs_av−Gd_av){circumflex over ( )}2+(Bs_av−Bd_av){circumflex over ( )}2

[0103] is calculated based on R, G, and B tristimulus values between the average luminance values of each tile and those of each material image 203, and a material image 203 with the smallest ΔE is selected. Upon pasting the selected material image 203 on a tile area, if its size or shape does not match that of the tile area, the material image 203 is enlarged/reduced to have an appropriate size or shape.

[0104] In step S87, a used flag in the material image management table shown in FIG. 7 corresponding to the material image 203 which is selected and pasted on the first image 201 is set to be ON, so as to inhibit the selected material image 203 from being pasted on another tile area. Counter j is incremented in step S88, and the processes in steps S86 to S88 repeat themselves while it is determined in step S89 that j<M×N, thereby pasting material images 203 on all the tiles.

[0105] As described above, according to the second embodiment, since a material image selected once is not used again in a single mosaic image and tiles are selected in a random order to paste appropriate material images thereon, an unexpected texture pattern can be prevented from being formed, and the entire mosaic image can have uniform image quality, thus generating a mosaic image with higher image quality.

[0106] In the first and second embodiments, a material image 203 which has been pasted on a given tile area is never pasted on another tile area. With this method, an unexpected texture pattern is prevented from being formed. Such method is effective if the number (of types) of material images is sufficiently large. However, when the number (of types) of material images is small, material images to be pasted on tile areas become short, and a material image 203 having image characteristics considerably different from those of a tile may be pasted on that tile area. For this reason, the image quality of a mosaic image generated considerably deteriorates.

[0107] In the third embodiment, a mosaic image formation method that can solve the aforementioned problem will be explained.

[0108] Note that the arrangement of an image processing apparatus according to the third embodiment is the same as that in the first embodiment, and a detailed description thereof will be omitted.

[0109] Mosaic image generation in the image processing apparatus of the third embodiment will be described below with reference to the flow chart in FIG. 10.

[0110] In step S100 in FIG. 10, the first image 201 is segmented into M×N tiles. As a result, as shown in, e.g., FIG. 3, 4×5 rectangular tiles TL(0, 0), TL(1, 0), TL(2, 0), . . . , TL(2, 4), and TL(3, 4) are generated.

[0111] Subsequently, in step S101, R, G, and B average luminance values of each of the M×N segmented tiles are calculated by:

[0112] Rd_av=ΣRi/(p×q)

[0113] Gd_av=ΣGi/(p×q)

[0114] Bd_av=ΣBi/(p×q)

[0115] In step S102, R, G, and B average luminance values of each of the P material images 203 are calculated by:

[0116] Rs_av=ΣRi/(p×q)

[0117] Gs_av=ΣGi/(p×q)

[0118] Bs_av=ΣBi/(p×q)

[0119] Note that the image characteristics such as R, G, and B average luminance values of the material images 203 may be obtained in advance. In this case, the image characteristics may be recorded as header information of each material image 203, or may be recorded in a table which is stored in the storage unit 101 and corresponds to the material image 203.

[0120] FIG. 11 shows an example of the data format of a material image management table according to the third embodiment. In this embodiment, the material image management table shown in FIG. 11 stores feature amounts (average luminance values) calculated in step S102. More specifically, a pair of a material image ID that specifies each material image, and feature amounts of the material image corresponding to that material image ID are registered. When such material image management table is stored in the storage unit 101, the feature amount calculations of the material images need not be repeated.

[0121] A use limit value K of each material image 203 is set in step S103, and use counts S all material images 203 are reset to zero in step S104. The use limit value K must be set at an appropriate value on the basis of the relationship between the number (of types) of material images 203 and the number of (M×N) of tiles. The use count S indicates the number of times each material image 203 is pasted on the first image 201. At the time of step S104, since none of material images 203 have been selected and pasted, the use counts of all the material images 203 are zero.

[0122] In this embodiment, a field for registering the use count S of each material image is assured in the material image management table, as shown in FIG. 11.

[0123] In step S105, counters (X_Pos, Y_Pos) that instruct the position of a tile of interest are reset to (0, 0) to designate the upper left tile of the first image 201. In step S106, a material image 203 having average luminance values closest to those of a tile designated by the position counters (X_Pos, Y_Pos) is selected from those having use counts S which satisfy 0≦S≦K−1, and is pasted on that tile area. In this selection method, a distance ΔE given by

[0124] ΔE=(Rs_av−Rd_av){circumflex over ( )}2+(Gs_av−Gd_av){circumflex over ( )}2+(Bs_av−Bd_av){circumflex over ( )}2

[0125] is calculated based on R, G, and B tristimulus values between the average luminance values of each tile and those of each material image 203, and a material image 203 with the smallest ΔE is selected. Upon pasting the selected material image 203 on a tile area, if its size or shape does not match that of the tile area, the material image 203 is enlarged/reduced to have an appropriate size or shape.

[0126] The use count S of the pasted material image 203 is incremented in step S107, and the counters (X_Pos, Y_Pos) are counted up or down sequentially in the horizontal and vertical directions in step S108. Steps S106 to S108 repeat themselves until it is determined in step S109 that the process in step S106 is done for all tiles.

[0127] As described above, according to the third embodiment, by appropriately setting the use limit value K of each material image 203, even when the number (of types) of material images 203 is small, the material images can be prevented from becoming short, and the image quality of a mosaic image generated can be prevented from deteriorating.

[0128] Note that the use limit value K may be determined as follows. For example, after a mosaic image is generated by setting K at a given default value, mosaic images are generated by increasing/decreasing the default value, and K is finally set by checking the image qualities and the degrees of texture formation on those mosaic images.

[0129] Mosaic image generation according to the fourth embodiment of the present invention will be explained below. In the fourth embodiment, the random processing in the second embodiment is applied to the third embodiment. Note that a detailed description of the same arrangement and processes as those in the third embodiment will be omitted.

[0130] FIG. 12 is a flow chart showing an example of mosaic image generation according to the fourth embodiment. In FIG. 12, steps S120 to S124 are the same as those in steps S100 to S104 shown in FIG. 10, and a detailed description thereof will be omitted.

[0131] In step S125, data indicating a random processing order of tiles are stored in a matrix T_Turn[M*N−1]. Note that the matrix stores data so that the quotient K/(M−1) indicates a Y-coordinate and the remainder indicates an X-coordinate when T_Turn[ ]=K. The method of storing the random processing order of tiles in that matrix is as has been described earlier with reference to the flow chart in FIG. 9.

[0132] In step S126 in FIG. 12, counter j is reset to zero. In step S127, a material image 203 having average luminance values closest to those of a tile image designated by T_Turn[j] is selected from the material images with use counts S which satisfy 0≦S≦K−1. For example, when T_Turn[j]=0, the tile position is (0, 0), i.e., the upper left tile. In this selection method, a distance ΔE given by

[0133] ΔE=(Rs_av−Rd_av){circumflex over ( )}2+(Gs_av−Gd_av){circumflex over ( )}2+(Bs_av−Bd_av){circumflex over ( )}2

[0134] is calculated based on R, G, and B tristimulus values between the average luminance values of each tile and those of each material image 203, and a material image 203 with the smallest ΔE is selected. Upon pasting the selected material image 203 on a tile area, if its size or shape does not match that of the tile area, the material image 203 is enlarged/reduced to have an appropriate size or shape.

[0135] The use count S of the pasted material image 203 in the material image management table (FIG. 11) is incremented in step S128, and counter j is incremented in step S129. The processes in steps S127 to S129 repeat themselves while it is determined in step S130 that j<M×N, thereby pasting material images 203 on all the tiles.

[0136] As described above, according to the fourth embodiment, since the number of times of use of an identical material image in a single mosaic image is limited to K and tiles are selected in a random order to paste appropriate material images thereon, an unexpected texture pattern can be prevented from being formed, and material images 203 can be prevented from becoming short even when the number (of types) of material images 203 is small. Hence, the entire mosaic image can have uniform image quality, and a mosaic image with higher image quality can be generated.

[0137] When the use count S is reflected in evaluation of ΔE in the third and fourth embodiments, use of material images 203 with larger use counts S may be limited, and formation of an unexpected texture pattern can be minimized. In this case, for example, the evaluation formula of ΔE is rewritten as:

[0138] ΔE={(Rs_av−Rd_av){circumflex over ( )}2+(Gs_av−Gd₋av){circumflex over ( )}2+(Bs_av−Bd_av){circumflex over ( )}2}(S+1)

[0139] In the third and fourth embodiments, the image quality of a mosaic image is improved by limiting the number of times of use of each material image. However, identical material images may be placed at neighboring positions in a mosaic image even under such limitation. Upon displaying an image which includes identical material images placed at neighboring positions, the portion of the identical material images is emphasized, resulting in low image quality of the mosaic image.

[0140] The fifth embodiment solves the aforementioned problem. Note that the arrangement of an image processing apparatus according to the fifth embodiment is the same as that in the first embodiment, and a detailed description thereof will be omitted.

[0141] Mosaic image generation according to the fifth embodiment will be explained below with reference to the flow chart in FIG. 13. FIG. 13 is a flow chart showing the mosaic image generation method according to the fifth embodiment.

[0142] Referring to FIG. 13, the first image is segmented into M×N tiles in step S140. As a result, M×N rectangular tiles TL(0, 0), TL(1, 0), TL(2, 0), . . . , TL(2, 4), and TL(3, 4) are generated. As described above, FIG. 3 shows the first image segmented into M×N rectangles. Referring to FIG. 3, X and Y respectively represent the numbers of horizontal and vertical pixels of the first image 201, and p and q respectively represent the numbers of horizontal and vertical pixels of each tile upon segmenting the first image into M×N rectangular tiles TL(0, 0), TL(1, 0), TL(2, 0), . . . , TL(2, 4), and TL(3, 4). Hence, X=p=M and Y=q×N.

[0143] Also, as shown in FIG. 4, each tile is composed of p×q three primary color (red (R), green (G), and blue (B)) data.

[0144] Subsequently, in step S141, the R, G, and B average luminance values of each of the M×N tiles segmented in step S140 are calculated to obtain feature amounts by:

[0145] Rd_av=(1/(p×q))×ΣRi

[0146] Gd_av=(1/(p×q))×ΣGi

[0147] Bd_av=(1/(p×q))×ΣBi

[0148] Note that d is an abbreviation for destination.

[0149] In step S142, R, G, and B average luminance values of each of P material images are calculated by equations below. The feature amount calculation method is the same as that used in step S141.

[0150] Rs_av=(/(p×q))×ΣRi

[0151] Gs_av=(/(p×q))×ΣGi

[0152] Bs_av=(/(p×q))×ΣBi

[0153] Note that s is an abbreviation for source.

[0154] In step S143, the use limit value of each material image is set at K. In step S144, use counts S of all the P material images are reset (initialized) to zero. Note that the use count indicates the number of times each material image 203 is pasted on the first image. At the time of step S144, since none of material images have been selected and pasted, the use counts of all the P material images are zero. Note that the feature amounts of the material images calculated in step S142 and the use counts S are stored in the material image management table shown in FIG. 11.

[0155] In step S145, counters X_Pos (0≦X_Pos≦M−1) and Y_Pos (0≦Y_Pos≦N−1) indicating the position of a tile of interest are reset to zero. (X_Pos, Y_Pos)=(0, 0) indicates the upper left tile of the first image. In step S146, a material image suitable for the tile indicated by the position counters X_Pos and Y_Pos is selected from the material images. For example, when X_Pos−Y_Pos=0, the tile position is (0, 0), i.e., indicates the upper left position. Note that material images serving as selection candidates are limited to those having use counts S falling within the range from 0 to K−1.

[0156] In the selection method, a distance ΔE of R, G, and B tristimulus values is calculated using the evaluation formula

[0157] ΔE=(Rs_av−Rd_av){circumflex over ( )}2+(Gs_av−Gd_av){circumflex over ( )}2+(Bs_av−Bd_av){circumflex over ( )}2

[0158] where “{circumflex over ( )}” indicates a power, and “X{circumflex over ( )}2” is the square of and a material image with the smallest ΔE is selected.

[0159] In step S147, upon pasting the material image selected by the evaluation formula onto a tile area, it is checked if the material image to be pasted is the same as one of those pasted on eight surrounding tiles, i.e., tiles located at (X_Pos−1, Y_Pos−1), (X_Pos−1, Y_Pos), (X_Pos−1, Y_Pos+1), (X_Pos, Y_Pos−1), (X_Pos, Y_Pos+1), (X_Pos+1, Y_Pos−1), (X_Pos+1, Y_Pos), and (X_Pos+1, Y_Pos+1). If the same material image is found, the use count S of the currently selected image in the material image management table is set at K+S so as to inhibit the selected material image from being used at that tile position, and the flow returns to step S146 to make the same decision (step S148). In the fifth embodiment, the processing progresses from the left to right tiles on a single horizontal line, and upon completion of processing for one horizontal line, the horizontal line to be processed shifts to the lower neighboring line. Therefore, of the eight surrounding tiles, those already pasted with material images are four tiles, i.e., (X_Pos−1, Y_Pos−1), (X_Pos−1, Y_Pos), (X_Pos, Y_Pos−1), and (X_Pos+1, Y_Pos−1).

[0160] In this way, after the material image which has no identical image at neighboring positions is selected, the selected image is pasted on the tile area of interest. Upon pasting the selected image on the tile area, if their sizes do not match, the selected image is enlarged/reduced to an appropriate size.

[0161] In step S149, the use count S of the pasted material image is incremented by 1. In step S150, K is subtracted from the use counts S of material images whose use count≧K+1, so as to restore the use counts S of material images, which are inhibited from being used due to the presence of identical images at neighboring positions in steps S147 and S148. In this fashion, a material image which has no identical images at neighboring positions is selected.

[0162] The aforementioned processes are continuously done in the horizontal and vertical directions until all tiles are processed (steps S151 and S152). In this manner, corresponding material images are pasted on all the tiles of the first image.

[0163] As described above, according to the fifth embodiment, since the number of times of use of each material image is limited to K, and identical material images are inhibited from being located at neighboring positions, a mosaic image with improved image quality can be generated even when the number of material images is small.

[0164] In the fifth embodiment, upon determining a material image to be pasted on a given tile, a material image, which has no identical images at neighboring positions and has feature amounts close to those of the corresponding block of the first image, is selected. At this time, the tile processing order is set to process each horizontal line from the left to right, and select a lower horizontal line upon completion of the processing of a given horizontal line. However, the tile processing order is not limited to such specific order, but may be determined, as will be described below in the sixth embodiment. Note that the arrangement of an image processing apparatus in the sixth embodiment is the same as that in the first embodiment (FIG. 5), and a detailed description thereof will be omitted.

[0165] FIG. 14 is a flow chart showing the mosaic image generation method according to the sixth embodiment. In FIG. 14, steps S160 to S164 are the same as steps S140 to S144 in FIG. 13.

[0166] In step S145, the processing order of tiles is stored in a matrix T_Turn[M*N−1] that indicates the processing order of tiles. The method for storing the processing order in the matrix T_Turn[M*N−1] is as has been described earlier with reference to the flow chart in FIG. 9.

[0167] In step S166, counter j is reset to zero. In step S167, an image having average luminance values closest to those of a tile designated by a value stored in T_Turn[j] is selected from the material images. Note that material images serving as selection candidates are limited to those having use counts S falling within the range from 0 to K−1. In the selection method of the material image, the distance ΔE of R, G, and B tristimulus values is calculated, and an image with the smallest ΔE is selected, as in step S146.

[0168] In step S168, upon pasting the image selected in step S167 on a tile area, it is checked if the image to be pasted has already been used on eight surrounding tiles of the tile of interest. More specifically, it is checked if the material image to be pasted is the same as one of those already pasted on tiles located at (X_Pos−1, Y_Pos−1), (X_Pos−1, Y_Pos), (X_Pos−1, Y_Pos+1), (X_Pos, Y_Pos−1), (X_Pos, Y_Pos+1), (X_Pos+1, Y_Pos−1), (X_Pos+1, Y_Pos), and (X_Pos+1, Y_Pos+1). In the sixth embodiment, since tiles are randomly selected, the positions of tiles on which material images have been pasted around a given tile are not uniquely determined.

[0169] If the material image selected in step S167 is pasted on one of the eight surrounding tiles, the use count S of that selected image is set at K+S to inhibit use of the material image on that tile in step S169. The flow returns to step S167 to repeat the same processes.

[0170] In this way, a material image which is different from those on its surrounding tiles is finally pasted. Upon pasting the selected image to a tile area, if their sizes do not match, the size of the selected image is enlarged/reduced to an appropriate size.

[0171] In step S170, the use count S of the pasted material image in the material image management table (FIG. 11) is incremented by 1. In step S171, K is subtracted from the use counts S of material images whose use count≧K+1, so as to restore the use counts of material images, which are inhibited from being used due to the presence of identical images at neighboring positions in steps S168 and S169.

[0172] The aforementioned process repeats itself until j=M×N−1, i.e., all the tiles on the first image are processed (steps S172 and S173).

[0173] As described above, according to the sixth embodiment, since the number of times of use of each material image is limited to K to prevent identical material images from being located at neighboring positions, and the selection order of tiles is randomly determined, a mosaic image which is free from texture and has improved image quality can be generated even when the number of material images is small.

[0174] The seventh embodiment will be explained below. In the fifth embodiment, material images are placed so as to use each material image within a use count and not to locate identical material images at neighboring positions. In the sixth embodiment, since the selection order of tiles where material images are pasted is randomly determined, a further reduction of texture is achieved. In both the fifth and sixth embodiments, tiles of an original image are selected one by one, and a material image which is to replace the selected tile is selected and pasted. In the seventh embodiment, when a material image is selected for one tile, tiles having feature amounts close to those of the selected material image are selected, and replacement is done using that material image to its use limit value. The seventh embodiment will be explained below.

[0175] Since the arrangement of an image processing apparatus according to the seventh embodiment is the same as that in the first embodiment, a detailed description thereof will be omitted. The mosaic image generation sequence in the image processing apparatus of the seventh embodiment will be explained below with reference to the flow chart in FIG. 15.

[0176] FIG. 15 is a flow chart showing the mosaic image generation method according to the seventh embodiment. In FIG. 15, steps S180 to S186 are the same as steps S140 to S146 in the fifth embodiment, and a detailed description thereof will be omitted.

[0177] In step S187, the selected material image is pasted on a tile indicated by position counters, and the use count S of that material image in the material image management table (FIG. 11) is incremented by 1. If the use count S is smaller than an absolute use count K and there are non-processed tiles (step S188), a tile having image characteristics closest to those of the selected material image is selected from tile positions where no identical images are present at neighboring positions (step S189). The flow returns to step S187 to increment the use count S of that material image, and the processing continues until the use count S reaches the absolute use count or processing is complete for all the tiles.

[0178] In this way, if the use count S becomes equal to or larger than the absolute use count K, the flow advances to step S190, and the position counters are updated to select the next tile to be processed. It is checked in step S191 based on the values of the position counters if processing is complete for all the tiles. If YES in step S191, this sequence ends. On the other hand, if non-processed tiles remain, the flow advances to step S192 to check if a material image has already been pasted on the tile designated by the updated values of the position counters. If YES in step S192, the flow returns to step S190 to further update the position counters. In this manner, when a non-processed tile is designated by the position counters, the flow returns from step S192 to step S186 to repeat the aforementioned processing.

[0179] The above processing is continuously done in the horizontal and vertical directions until all the tiles are processed (steps S190, S191, and S192).

[0180] As described above, according to the seventh embodiment, since the absolute use count of each tile is set at K and identical material images are inhibited from being located at neighboring positions, a mosaic image with improved image quality can be generated even when the number of material images is small. Since a maximum of K identical images can be pasted, a mosaic image that allows a Japanese card game called “Sinkei Suijyaku” can be generated.

[0181] In the first to seventh embodiments, a material image is selected in accordance with an evaluation value based on the distance between the segmented original image area and the material image. However, by evaluating only the color distance, the selected material image and original image area may have improper colors.

[0182] The eighth embodiment provides an image processing method and apparatus, which allow the user to replace a desired tile area on an automatically generated mosaic image with a material image of his or her choice.

[0183] FIG. 16 is a block diagram showing the arrangement of a computer system which implements image processing according to the eighth embodiment of the present invention. Note that the system arrangement shown in FIG. 16 is substantially the same as that shown in FIG. 5.

[0184] Referring to FIG. 16, reference numeral 1101 denotes a CPU, which controls the entire system in accordance with a program which is stored in a hard disk 1106 and is loaded onto a RAM 1105. Reference numeral 1102 denotes a keyboard, which is used together with a mouse 1102ato input various commands and data to the system of this embodiment. Reference numeral 1103 denotes a display which comprises, e.g., a CRT, a liquid crystal display, or the like. A ROM 1104 and the RAM 1105 construct a storage unit in the system of this embodiment, and store a program to be executed by the system, data used by the system, and the like. The hard disk 1106 and a floppy disk device 1107 construct an external storage device which is used by a file system of the system of this embodiment. Reference numeral 1108 denotes a printer.

[0185] The hard disk 1106 stores a plurality of (P) tile images which serve as building elements of a mosaic image, and a mosaic image is generated by inlaying M×N images selected from those images in an M×N (horizontal×vertical) matrix, as shown in FIG. 17. The generated mosaic image is stored as an image file in the hard disk 1106, and is displayed on the CRT 1103 or is printed out via the printer 1108.

[0186] FIG. 18 is a flow chart showing the outline of the processing flow of a mosaic image generation method in the computer system of the eighth embodiment.

[0187] In step S201, an original image 201 is segmented into a plurality of areas (tiles), and a material image having a color closest to that of each tile area is selected, thus generating a mosaic image.

[0188] This processing may use that described earlier with reference to the flow chart in FIG. 2. Also, the mosaic image generation processing according to each of the first to seventh embodiments described above with reference to FIGS. 6 to 15 may be used.

[0189] Since the mosaic image is automatically generated on the basis of the distance (difference) between colors of each tile area of the original image and material image, it is not always a combination of optimal material images when the user observes it.

[0190] In this embodiment, as shown in the flow chart in FIG. 18, material images as appropriate “next candidates” are displayed on the screen in correspondence with the mosaic image generated in step S201 and each tile of that mosaic image (step S202) to prompt the user to select an optimal one of the material images and to determine the selected material image as that of the corresponding tile area of the image 201 (step S203), thereby generating a mosaic image having higher quality for the user on the basis of the automatically generated mosaic image.

[0191] FIG. 19 is a flow chart showing material image selection in step S202 in the flow chart shown in FIG. 18.

[0192] In step S221, a mosaic image generated in step S201 in FIG. 18 is displayed on the display 1103.

[0193] FIG. 20 shows a display example on the display 1103.

[0194] Referring to FIG. 20, the original image 201 (denoted by reference numeral 51) is displayed on the left side on the screen, and a mosaic image 52 based on this original image 201 is displayed on the right side of the screen. When the original image 201 and mosaic image are displayed at neighboring positions, the user can edit the image while visually comparing these images. Note that the original image need not always be displayed. For example, when the display area of the screen is not large enough, the image 51 need not be displayed. On the other hand, one of the image 51 and mosaic image 52 may be displayed, and may be selectively displayed by the user using, e.g., the mouse 1102a.

[0195] The flow advances to step S222. In step S222, the user moves the mouse cursor to a desired tile position 54 of the mosaic image 52 on the screen of the display 1103, and clicks the button of the mouse 1102aat that position, as shown in FIG. 20. In this manner, the tile 54 is selected, and material image candidates corresponding to that tile are displayed as shown in, e.g., a subwindow 61 in FIG. 21 (step S223).

[0196] Referring to FIG. 21, reference numerals 62ato 62ddenote material image candidates corresponding to the tile 54. These material image candidates are selected in turn from those in ascending order of the evaluation values calculated in step S201. If no desired material image is included in those displayed on the subwindow 61, the user selects and clicks an icon “Next” 64 using the mouse cursor, thus displaying a subwindow including a next material image candidate group.

[0197] If the user finds a desired material image on the displayed subwindow 61, he or she clicks that material image (one of the images 62ato 62d) (step S224), thus displaying the selected material image pasted at the position of the tile 54. In this case as well, if the size of the material image does not match that of the tile 54, the selected material image is enlarged/reduced in correspondence with the size of the tile 54, as described above. In this way, since the replacement result of the tile 54 of the mosaic image 52 by the selected material image 62bis displayed as the mosaic image 52, it is convenient for the user to edit an image while confirming the mosaic image 52 in which a desired tile is replaced by a desired material image. When the material image to be replaced is finally determined, the user clicks an “OK” button 65, thus determining a material image corresponding to the tile 54. After the material image corresponding to the tile 54 is determined, the subwindow 61 disappears from the screen, and the display state on the display 1103 returns to that shown in FIG. 20.

[0198] If the user clicks an “Exit” button 53 in FIG. 20, “YES” is determined in step S204 in FIG. 18, thus ending mosaic image generation. On the other hand, if the user clicks another tile in FIG. 20, the flow returns to step S202 to repeat the aforementioned processing.

[0199] In this fashion, the processes in steps S202 and S203 in FIG. 18 repeat themselves until the user determines that there are no tiles to be replaced.

[0200] In FIG. 21, reference numeral 63 denotes a “Cancel” key for canceling processing; and 53, an “Exit” key for ending material image selection.

[0201] Note that material image candidates may be randomly selected from a plurality of material images. Also, as described above, images may be selected in turn. For example, an image with the second smallest distance ΔE (step S201) between the tile and material image may be selected as the next candidate, an image with the third smallest ΔE as still next candidate, and so forth. In this case, selected material images are less likely to differ from the color of the designated tile 54.

[0202] Upon canceling this processing, if the mouse 1102ahas two, right and left buttons, the processing may be canceled by clicking the subwindow 61 using the right button, in place of using the “Cancel” button 63.

[0203] In the example shown in FIG. 21, four material image candidates are displayed on the subwindow. However, the present invention is not limited to this, and more candidates may be simultaneously displayed if the screen has an enough space. If material image candidates are displayed as thumbnail images, more candidates can be displayed while the screen size remains the same.

[0204] As described above, according to the eighth embodiment, a mosaic image using optimal material images according to the user's favor can be generated in place of an automatically generated mosaic image.

[0205] Material images that form the mosaic image can be replaced by quickly reflecting the operator's will, thus improving the image quality of the mosaic image.

[0206] In the eighth embodiment, in FIG. 21, the subwindow 61 is displayed at a lower position near the center of the screen. In place of permanently displaying the subwindow 61 at that position, the display position may be changed every time the subwindow 61 is displayed. For example, when a lower tile of the mosaic image 52 is to be edited, the subwindow 61 displayed at the position shown in FIG. 21 conceals the tile to be edited. In such case, the subwindow 61 is preferably automatically or manually moved to and displayed at an upper position.

[0207] When the subwindow 61 is automatically moved and displayed, it is controlled by the CPU 1101 not to conceal the tile of interest.

[0208] Note that the present invention may be applied to either a system constituted by a plurality of devices (e.g., a host computer, an interface device, a reader, a printer, and the like), or an apparatus consisting of a single equipment (e.g., a copying machine, a facsimile apparatus, or the like).

[0209] The objects of the present invention are also achieved by supplying a storage medium, which records a program code of a software program that can realize the functions of the above-mentioned embodiments to the system or apparatus, and reading out and executing the program code stored in the storage medium by a computer (or a CPU or MPU) of the system or apparatus.

[0210] In this case, the program code itself read out from the storage medium realizes the functions of the above-mentioned embodiments, and the storage medium which stores the program code constitutes the present invention.

[0211] As the storage medium for supplying the program code, for example, a floppy disk, hard disk, optical disk, magneto-optical disk, CD-ROM, CD-R, magnetic tape, nonvolatile memory card, ROM, and the like may be used.

[0212] The functions of the above-mentioned embodiments may be realized not only by executing the readout program code by the computer but also by some or all of actual processing operations executed by an OS (operating system) running on the computer on the basis of an instruction of the program code.

[0213] Furthermore, the functions of the above-mentioned embodiments may be realized by some or all of actual processing operations executed by a CPU or the like arranged in a function extension board or a function extension unit, which is inserted in or connected to the computer, after the program code read out from the storage medium is written in a memory of the extension board or unit.

[0214] As many apparently widely different embodiments of the present invention can be made without departing from the spirit and scope thereof, it is to be understood that the invention is not limited to the specific embodiments thereof except as defined in the appended claims.