이미지 퀼팅(Image Quilting) 알고리즘
이미지 퀼팅(Image Quilting)이란 작은 텍스쳐 이미지(Texture Image)를 이와 유사한 더 큰 텍스쳐 이미지로 확장하는 방법입니다.
Question.
Explanation
Texture synthesis is the technique for synthesizing a big texture image from a given small input image. For example, assume that we have a small input image in Figure 1(a), and we want to generate a large image like Figure 1(b) which is very similar to the small input image.
We need some techniques to synthesize a large image by combining the parts of small input image. Many different methods have been suggested by many researchers for the texture synthesis. We select the “Image Quilting” technique suggested by Efros and Freeman [1] in 2001.
[1] A.A. Efros and W.T.Freeman, “Image Quilting for Texture Synthesis and Transfer”, SIGGRAPH 2001. (You can download the paper and see various examples at http://www.cs.berkeley.edu/~efros/research/quilting.html)
Algorithm
1) Take some random sub-block from the given input image. We call this sub-block ‘A’.
2) Place the selected block at the upper-left corner of the output image.
1) Randomly select one more block ‘B’ of the same size from the input image.
2) Assume the placement of the block B with some overlap of the current result image A as the following figure.
3) Compute the placement cost of B as follows:
For example,
TotalDiff = 0;
For each pixel i in the overlapped region {
TotalDiff = TotalDiff + (R(A,i) – R(B,i))^2 + (G(A,i) - G(B,i))^2 + (B(A,i) – B(B,i))^2
}
where R(A,i) denotes the RED color value of the pixel i in image A, G(B,i) denotes the GREEN color value of the pixel i in image B, … and so on.
4) Repeat Step (3)-(5) several times for considering other randomly selected blocks.
5) From the candidate second blocks, we select the block having minimum placement cost as the next synthesized block.
6) Compute the minimum error boundary cut for the overlapped region. (See figure and try to think about the algorithm!!)
7) Now we go to select the third block to be synthesized with the same method.
8) In the middle of the synthesis, we probably have the following configurations. You should consider the horizontal and vertical overlaps to compute the cost.
1) Take some random sub-block from the given input image. We call this sub-block ‘A’.
Bitmap Library
You are offered the bitmap library functions to read and write a Windows “.bmp” files. However, as an input image, you should use 24 bit or 32 bit bmp files. If needed, you can convert your 256 color (8 bit) bmp file into 24 bit image using windows paint program.
There are two functions LoadBitmap and WriteBitmapFile to load and write the image file. Each pixel of the loaded image takes 4 bytes (32 bit). 8 bit for red color, 8 bit for green color, 8 bit for blue color, and 8 bit alpha channel. Be careful not to change the alpha value in this project.
Refer to the example project “bitmap” for detailed usage of library functions.
Answer.
* 이 답안은 개인적으로 작성된 것으로 최적의 답안이 아닐 수 있고, 다양한 방법이 있습니다. 또한 현재 더 새로운 알고리즘이 나왔을 수 있습니다. 단지 이와 관련된 자료가 필요하신 분들께서는 참고하셔서 봐주세요. 그리고 영어는 그지같으니, 감안해서 봐주세요.^^;
* 참고 문헌은 포스팅 하단에서 내려 받으실 수 있습니다. (PDF 파일)
* 소스 코드 및 실행 파일
source_image_quilting.zip
- 소스는 Visual Studio 6.0 에서 최종 컴파일 되었습니다. C++로 작성되었으며, 알고리즘은 main.cpp 파일에 구현되었습니다.
- 테스트를 위한 다양한 이미지 파일 또한 첨부되어 있습니다.
1) Describe the usage of your program, if any special usages or options exist.
1-1) Execution Way
At the Console Window, Use a similar form following.
To execute this program, we need one command and four additional parameters
① Execution Command : To execute this program, you input word ‘bitmap’ first at the command line.
② Sub-block Size : First Parameter. Input the Sub-block Size.
③ Overlapping Region Size : Second Parameter. Input the Overlapping Region Size.
④ Block Sampling Count : Third Parameter. Input the Block Sampling Count. It means that how many times do you want sample blocks to select one optimal block.
⑤ Image File Name : Forth Parameter. Input the Image File (Name included extension name) that will be used as a source image.
1-2) Examples
① When you want to get a image the following information,
Information |
Parameter Value |
|
Sub-Block Size |
40 |
|
Overlapping Region Size |
12 |
|
Block Sampling Count |
30 |
|
Image File Name |
Photo01.bmp |
You have to input the following command.
=> C:\> bitmap 40 12 30 Photo01.bmp
② Another Case
Information |
Parameter Value |
|
Sub-Block Size |
60 |
|
Overlapping Region Size |
4 |
|
Block Sampling Count |
100 |
|
Image File Name |
Photo12.bmp |
=> C:\> bitmap 60 4 100 Photo12.bmp
2) What algorithm did you use to compute the “minimum error boundary cut”? (Write the file name and line number having the algorithm implementation, too). Briefly explain the algorithm.
I used the Image Quilting Algorithm (For Image Cut) to compute the minimum error boundary cut.
The File Name : main.cpp (in the ‘source’ folder)
The implementation Part of Algorithm : Line 197 ~ Line 375
- Image Quilting Algorithm -
* Original Method (Reference : Image Quilting for Texture Synthesis and Transfer – Chapter2)
- Go through the image to be synthesized in raster scan order in steps of one block.
- For every location, search the input texture for a set of blocks that satisfy the overlap constraints within some error tolerance. Randomly pick one such block
- Compute the error surface between the newly chosen block and the old blocks at the overlap region. Find the minimum cost path along this surface and make that the boundary of the new block. Paste the block onto the texture. Repeat.
* The Method in my program
① First, in the overlapped region, compute the color difference between image A and image B per pixel. The color difference value includes all red, green and blue color difference. So One pixel has just one value. The value is,
[Picture 2-1]
TotalDifferenceValue = (Red Color Difference between A and B) + (Green Color Difference between A and B) + (Blue Color Difference between A and B)
And I saved these values to the array to make an optimal cut-line.
[Picture 2-2]
② Next, give the weight per pixel, from the top to the bottom (in array) in order.
(Supposing that ‘n’ is value that indicate the second factor value at the array -> Array[*][n], and ‘m’ is value that indicate the first factor value at the array -> Array[m][*])
First, At the top-line elements of array, Find the smallest value among the adjacent three elements(array Array[0][n-1], Array[0][n], Array[0][n+1]), If you find the element that have smallest value among three elements, then add the value to the middle-bottom element(Array[1][n]) at the array. And repeat this calculation until to reach the bottom of array.
(Notice : If the ‘n’ or ‘m‘ is out of the array range, then we regard that there is a infinite value. But It is impossible to express infinite value by computer so that I used the so large number as a substitute. Example - the number is 99999999. (It can’t exceed the allocated memory region)
[Picture 2-3]
③ Next, Find the element that have a smallest value at the array of bottom(Array[max-1][*]). And find the element that have a smallest value at the array of bottom above(Array[max-2][*[]. Repeat it from the bottom of array to the top of array.
[Picture 2-4]
Then, we can get a line that cross the overlapped region. This line must be connected. [Refer to the picture 2-4] It is the optimal cut-line through this algorithm.
④ Finally, Save the elements that across the overlapped region. And I decide the line to a base line that divides the overlapped region into two regions. Left part from the base line is filled with original block’s pixels, and Right part from the base line is filled with original B block’s pixels
[Picture 2-5]
⑤ Apply this algorithm all of blocks adjacent from side to side. Also Apply it all of blocks adjacent up and down.
⑥ End. We can get the optimal image.
3) Attach the input and output image figures here. Present the exact sub-block size and overlapping region size for each example.
3-1) Problem : Try to synthesize 384x384 image from 192x192 input images: input1.bmp ~ input5.bmp. Name the output images as: output1.bmp ~ output5.bmp
① Input1.bmp
l Input image size : 192 x 192 pixel
l Sub-Block size : 48 x 48 pixel
l Overlapping Region size : 8
l Output File : input1-output.bmp (in the output images folder)
② Input2.bmp
l Input image size : 192 x 192 pixel
l Sub-Block size : 48 x 48 pixel
l Overlapping Region size : 8
l Output File : input2-output.bmp
③ Input3.bmp
l Input image size : 192 x 192 pixel
l Sub-Block size : 48 x 48 pixel
l Overlapping Region size : 8
l Output File : input3-output.bmp
④ Input4.bmp
l Input image size : 192 x 192 pixel
l Sub-Block size : 48 x 48 pixel
l Overlapping Region size : 8
l Output File : input4-output.bmp
⑤ Input5.bmp
l Input image size : 192 x 192 pixel
l Sub-Block size : 48 x 48 pixel
l Overlapping Region size : 8
l Output File : input5-output.bmp
3-2) More Examples
3-3) Additional Examples.
This section shows another example images that changed the sub-block size and overlapping region size.
①. input5.bmp
l Input image size : 192 x 192 pixel
l Sub-Block Size : 60 x 60 pixel
l Overlapping Region Size : 12
l Block Sampling Count : 20 times (left), 200 times (right)
l Output-Image File : input5-output2.bmp
②. myInput2.bmp
l Input image size : 300 x 200 pixel
l Sub-Block Size : 30 x 30 pixel
l Overlapping Region Size : 6
l Block Sampling Count : 20 times (left), 200 times (right)
l Output-Image File : myInput2-output2.bmp
③. myInput4.bmp
l Input image size : 300 x 200 pixel
l Sub-Block Size : 34 x 34 pixel
l Overlapping Region Size : 5
l Block Sampling Count : 50 times (left), 500 times (right)
l Output-Image File : myInput4-output.bmp
4) Conclusion: What are the most difficult problems in the implementation? Did you think about any extension of the method or better algorithm for the problem?
① Most Difficult Problem
- It is the most difficult problem to compute the image pixel coordinates. Like you can see at the source code, there are too many operations to access to information of each pixel.
Especially, It is difficult to find the two overlapped part of sub-block’s images and to confront the pixel each other at the overlapped region.
- Also, I have a hard work at changing the cut-line algorithm at ‘right and left’ overlapping region to the ‘up and down’ overlapping region. I think it is not difficult, but it has a problem to compute the pixel coordinates, too.
② Extension of the Method
- If there is more sampling block, the result image bill be more plausible. But getting more sampling block, slower the execution time.
- As change Sub-block Size and Overlapping Region, we can get better images.
- There are another methods to improve the image quality. One of them is to change some pixels’ color that adjacent cut-line. For example, Change the pixels’ color on the cut-line to the middle color tone. (Middle color means the average color among the adjacent pixels’ color.). If this method is applied, the result images will be more natural.
③ Better Algorithm
- I think about the Graph Cut Algorithm. I read the method about the Graph-Cut Algorithm. And Graph-Cut Algorithm shows the better result than Image Quilting. But it is more difficult to implementation. I append some comparison images next page. Also there are more algorithms like as Rotation & Mirroring
[Reference Data]
l Image Quilting for Texture Synthesis and Transfer [Alexei A. Efros, William T. Freeman]
l Graphcut Texture: Image and Video Synthesis Using Graph Cuts [Vivek Kwatra, Arno Schodl, Irfan Essa, Greg Turk, Aaron Bobick]
l http://www.cc.gatech.edu/cpl/projects/graphcuttextures/
1. Image Quilting for Texture Synthesis and Transfer (UC, Berkeley)
[Efros01]ImageQuiltingForTextureSynthesis.pdf
2. On Pixel-Based Texture Synthesis by Non-parametric Sampling (KAIST)
3. Graphcut Textures : Image and Video Synthesis Using Graph Cuts (GVU Center)
'개발&컴퓨터 > 알고리즘' 카테고리의 다른 글
| [알고리즘문제] 다각형의 면적 (0) | 2015.06.22 |
|---|---|
| [알고리즘문제] 볼록 다각형의 교차 영역 (0) | 2015.05.30 |
| [알고리즘문제] 와일드 카드 (0) | 2015.05.03 |
| [알고리즘문제] 숫자 대응 (0) | 2015.04.18 |
| [알고리즘문제] 수열 추정 (0) | 2015.03.31 |
