图像马赛克处理

2023年4月25日发(作者：什么仪器测甲醛最准确)

Image Application of Photo-mosaic

Wang Wenxiu

School of Information Engineering，Politecnico di Milano，Como，Italy (22100)

E-mail：nju_wangwx@

Abstract

Photo Mosaic is an exciting art form made from thousands of small pictures, placed in patterns like

original mosaics made from colored cells, but each cell is an actual photo. This application is a little

program for to create mosaic made with photos with two different algorithms, one is Mean-Variance

and another one is Cauchy-Schwarz Inequality.

Keywords：photo-mosaic，image process

1. Introduction

Photo Mosaic is an exciting art form made from thousands of small pictures, placed in patterns like

original mosaics made from colored cells, but each cell is an actual photo. [4] So there are two

important parts for photo mosaic. They are the original image and the cell images also called tiles. The

Main Image is a single image that will be used to map the cell Images in order to create a photo mosaic.

And the Cell Images are the many pictures that make up the photo mosaic. When creating a Photo

Mosaic, each cell is analyzed and is optimally placed in patterns. [1]

This application is a little program for to create mosaic made with photos. To create such kind of

mosaic we need a collection of images that are going to be the tiles of the mosaic and we also need an

image to use for the original, as a matrix for the mosaics. The application is composed by 3 main

components: the main library which contains all the relevant code, an application to pre-process and

store them in the database and a front-end for the mosaic code in the library that lets the user control

the parameters (algorithm used, tile size, dithering, etc.) of the photo mosaic process.

2. Algorithms Details

Two different algorithms were used in the application. The first one is based on the mean pixel values

and image variance and it's been called “MV” (Mean-Variance); the second one also uses the chromatic

information from the mean values on the RGB channels, but uses the Matched Filter Detector in the

second stage; this algorithm is called “CSI”, from Cauchy-Schwarz Inequality.

2.1 Mean–Variance

The MV algorithm operates using the mean value on the RGB channels and the variance of the images.

In the first stage each images in the set is mapped as a point in a 3 dimensional space (RGB); then the

euclidean distance between each point and the input block:

dist=R−R+G−G+B−B

()()()

refirefirefi

222

1

is computed and the “closest” images are selected and used in the second stage. In the second

5

stage the variance of the 5 images is computed (after the scaling) and the image whose variance is the

most similar to the variance of the input block is

1. Five is an arbitrary number; if the number is too big there is the risk that unsuitable images are

carried on to the second stage; if the number is too small the dithering algorithm doesn't work well.

selected. This last step prevents a highly textured image to be used to cover an almost flat area and vice

versa.

- 1 -

2.2 Cauchy-Schwarz Inequality

The Cauchy-Schwarz Inequality [2] states that in a given vector space :

V

<v,w>≤w⋅v,

∀v,.w∈V

With equality holding if and only if :

v=w

α

The Matched Filter Detector is based on the principle that the inequality is maximized when the two

elements are linearly dependent; if and are functions then the linear dependency basically

vw

means that the functions have the same shape.

If we have a template signal

f(t)

and we want to select the best matching signal from a set

gt

i

()

of candidates, then the Matched Filter Detector states that:

best

=

argmax

i

<>

ftgt

(),()

i

gt

i

()

In the application the Matched Filter Detector is used to select an image from the samples set that

“looks like” the block from the input image; unfortunately the similarity granted by the MF Detector is

not enough, because it doesn't take into account the chromatic information when selecting the “similar”

image. [3] For this reason the MF Detector is used only as a second stage and operates on a set of

candidates selected using the color information. The first stage of the algorithms computes the mean

difference of intensity on the 3 RGB channels between the candidate and the input block:

diff=

R−R+G−G+B−B

refirefirefi

3

2

The best matches are then fed to the Matched Filter Detector for the final decision.

5

2.3 Dithering algorithm

Both algorithms tend to select always the same image to fill uniform areas; while technically correct it

creates a regular pattern that distract the observer from the overall picture. The dithering algorithm

works preventing any tile to be used more than once in a given area; in the current version the dithering

is done using a 3x3 (blocks, not pixel) matrix.

The algorithm works after the five images selected either by MV or CSI have been sorted using the

result of the algorithm. If the best – as selected by either MV or CSI – tile is rejected by the dithering

algorithm then the second one is tried and so on. If all the five tiles are rejected then one tile is chosen

randomly.

Even if the dithering matrix is small and the amount of available samples is limited the algorithm

works quite well in preventing the creation of spurious patterns. Tests have shown that on the one hand

enlarging the matrix doesn't improve the result since the number of tiles available is small (5); on the

other hand increasing the number of tiles may lead to worse results since tiles that have significant

differences from the input block may be used in the final decision.

3. Implementation Details

All the logic is encapsulated in the ImageLib library, that can be used with any front-end. All the photo

mosaic classes implements the same interface and hence are interchangeable. For API details see the

standard XML documentation.

Database

Images and their data is stored in a DBMS; in our application we used PostgreSQL, but any DBMS

2. Again, an arbitrary number.

- 2 -

with a .NET connector and BLOB support can be used to host the data. For each image the mean

values of the RGB channels are precomputed and stored in the time at insertion time; in this way there's

no need to recalculate them every time.

SimpleMosaic

The SimpleMosaic class is a proof of concept implementation of image selection based on the RGB

means. The class use its own synthetic set of tiles and does not use the database at all. The class if

provided for reference is not used in the test program.

MvMosaic

MvMosaic is the implementation of the “mean-variance” algorithm. Two version of the class are

provided:

– MvMosaic query the database for every input block, delegating the selection of the images using the

mean to the DBMS; this version puts a heavy load on the DBMS and due to a memory leak in

the .NET connector it ends up using a huge amount of memory.

– MvMosac2 is the implementation of the same algorithm, but query the database only at load time. All

the images are loaded at startup, scaled down to tile size and cached in memory; memory usage is

usually acceptable (about 50MB for 900 images and 8x8 tiles) but grows quadratically with tile size.

The cache makes this implementation very fast.

CsiMosaic

CsiMosaic is the implementation of the algorithm based on the Matched Filter Detector. Again, two

different versions are provided.

– CsiMosaic uses only the MF Detector and, while the output doesn't look quiet good, it is provided as

reference since it shows how the MF Detector operates.

– CsiMosaic2 uses the algorithm described in the previous sections, using chromatic information (mean

value on the channels) in the first stage and the MF Detector in the second stage to further refine

the selection. This class is intended for “real” use the output is rather good.

4. User Manual

Step:

1. Create a collection of tiles

2. First of all we need a directory where to store all the images to use as tiles of the mosaic. We can

select some images from Internet. The image have to be JPG or BMP files, they are the most used

format for photographs. We can also place the images in subdirectories for to organize better the

images.

The next step is to tell the program where the collection of images to use. The program will analyze all

the images and the result will be stored in the database. The database contains the basic information of

every image (the name of the image, the size, and the mean values of three channels).

(1). Execute “AddImage”

(2). Press the button “Add”

Fig 1. “Add” interface

(3). In the next window we have to select the images that to be used as tiles and then save them.

- 3 -

Fig 2. Select images

(4). Now the program will analyze all the images and store the information into database. We have

to wait that the program will reach 100%.

Fig 3. Wait for 100%

3. Create the mosaic

(1). Execute “Tester”.

(2). Set the parameters of the mosaic. We should set the tile size and choose the algorithm that you

want. MV algorithm is based on “mean-variance”, while CSI algorithm is based on the Matched

Filter Detector of the tile and the image.

Fig 4. MV algorithm

(3). In order to accelerate the speed of creating mosaic, we can load the image stored in

database to cache. We also have another choice “Dithering” which can make the effect of the

mosaic better. Press the button “Load cache” and then wait the program will reach 100%.

- 4 -

Fig 5. MV algorithm

(4). The last step is to create the mosaic. You only have to press the button “Mosaic” to choose a

main image. After the program reach 100%, we should choose the path for saving the mosaic of

the input image.

Results:

Fig 6. Output of the "MV" algorithm.

Fig 7. Output of the "CSI" algorithm.

5. Conclusions

The output of all the algorithms greatly depends on the number and the distribution of the images in the

database; for example if there are few “green” images and the input image has large green areas then

the result won't be good, regardless the used algorithm. For the tests I used a database of about 900

images and MvMosaic and CsiMosaic both provides a good output that closely resembles the input

image.

Both algorithms will remove details that are smaller than the tile size and tend to behave badly when

the must cover uniform areas (they create a textured area) even with the dithering check enabled. An

example showing the worst case scenario is the Stonehenge image: the sky and the grass are almost

- 5 -

uniform, with the grass having a fine grained texture; the columns have small gaps between them that

prove to be very hard to be handled.

References

[1] R Raskar, J van Baar, “A Low-Cost Projector Mosaic with Fast Registration”, Asian Conference on Computer

Vision (ACCV), 2002

[2] G Buskes, A van Rooij, Almost f-algebras: Commutativity and the Cauchy-Schwarz Inequality, Birkhäuser

Basel, 2000

[3] G Turin, An introduction to matched filters, Information Theory, IEEE Transactions on, 1960

[4] Site about How-To: Make your own photo mosaics

/2004/10/19/how-to-make-your-own-photo-mosaics/

- 6 -