It’s my final project for computational photography course.Though time consuming, it’s pretty cool, and very practical. The idea is to minimize manual input when colorize an image. We assume colors are the same, if the intensity is close.

My algorithm is to propagate color along the color_marked image base on the affinity of neighbor pixels.

Matlab codes could be found here : http://homepages.nyu.edu/~xl338/colorization.zip

Here’s the example:

this is a friend of mine. He looks a little bit down with his semi-dead plant in B/W image, let’s make his life colorful!

gray image we want to colorize.

color marked image as an input.

result image, see what a wonderful job it did on the fine details!! Now he’s happy,  and we are happy!

Using the same algorithm, we can do picture matting.The idea is thinking of every pixels in a picture as a combination of foreground and background with a opacity of the foreground alpha. This could be showed as the formula below:

I = a*F + (1-a)*B

a: alpha value form 0-1

F: foreground

B: background

I: pixel value in picture

So in our input file, instead of give color scribbles we define the opacity of the foreground. This method is especially good for fluffy edges i.e. hair, dog, cat, etc.As it needs to take three color channels into consideration, the time for this method is bad, on 2.4G intel computer it’s about 1 min for 500*500 picture.

Here’s a picture I took years ago. the matting picture looks pretty good on the puppy’s edge.

The original picture

the input file

result image, notice the shadow area and hair.

optimize the algorithm

Though the algorithm did a pretty good job, it needs a lot of computational power and consumes a lot of memory. On my 2.4G intel computer, it took the Matlab program 30 seconds and around 200M RAM to run a 100*100 picture, and worse, as the picture grows, the time is bad.

In Matlab we can play some matlab trick to speed up the code. One thing we notice is that the weight matrix is mainly zeros. So instead of using full matrix, we can use sparse matrix. This really save a lot of memory，for a typical two dimensional image, the space for a sparse weight matrix to the full weight matrix is about 9 to the size of image. (i.e. for a 100*100 image, it would be 9 to 10000). But this addresses another problem, as we are adding values into the sparse matrix in the loop, it become very slow. I guess it’s because every time you add something into sparse matrix, it calls memory allocation function. So my solution is to use three matrices when building the weight matrix, one for the value of the weight, other two for the row indies and column indies. and later on build the sparse weight matrix. This works great, it reduce the time for 100*100 image down to less than a seconds, and save good amount of memory.

However, in real life it’s still not good enough. A typical modern cameras can take picture for more than 10 mega pixels. It will take my previous code too long, if possible, to run such one. By close inspection of the code, we may discover that the majority time the code spend is on the calculation weight matrix. (in a 500*500 picture, it spend 8 seconds on the weight matrix out of 12 seconds total time) So weight matrix may be a good thing to start with. Because the code skip the color marked place, in the weight matrix calculation, we can make a pyramid of the image (half size, quarter size, etc,), and run the algorithm on the smallest one first and scale the result up to the next level, and based on that and the color marked image, we calculate the next level image, so on so forth. The idea is to skip as much weight calculation as we can.

Due to short of time, I don’t have time to implement the second optimization.
Contact me if you are interested in more details. At least the puppy is cute!

There’re only two days left, and I still not intimately experience the SNOW yet. So Ken, the peanut butter guy, and Michael come up with this CRAZY idea to go tubing that afternoon. It’s a very simple game, we slide down a snow hill on a inner tube, but it’s lot more fun and exciting than it sounds like.

To kill the time before tubing (not really kill time, we have so many things we want to do), Michael took me to the bank of Mississippi river. It’s so cold, about -10F, not many people in the park, still you can find many dog-footprint. With grill scattered around the park, you can picture how nice it is to barbecue by the side of Mississippi in the summer.

At about 2 o’clock, we, three Michael’s friends , Ken , Michael and I, arrived at the Tubing spot. It’s a very small park, nothing fancy, just a small snow hill, one can’t-be-simpler cable that grab you to the top of the hill, and a pile of tube. But still you can tell how exciting it is, by the screaming from distance. I and my tube, “dog”, as I call it, had a great time. Though most people there are kids, our Professor-lawyer-CSmaster team is the craziest team in the park. We tried different order， V shape，I shape, O shape….

The last day in Minneapolis, Michael took me the the Mall of American, the biggest mall in US. It’s huge, but, both of us were not interested in it, so after visit Ken’s peanut butter shop, we get away as fast as we can.

It’s snow every where

on the way to NorthField

most gas stations are help-your-self station

dormitory

many foot print

the church where Micheal and Misti got married

isn’t the class building looks like castle?

he’s so happy with his GIANT hotdog!

the street of a small town– NorthField, not seems small to me

see how excited Micheal was with his hamburge

Micheal used to be a chef in this restaurant

most road looks like this

road across a small town

Micheal’s making me the secret soup!

some rice, mmmm….m yamy!

it’s called sartay (sound), kind like fry. The garlic smells great!

box wine, but it tastes not so interesting as it’s decoration.

is that milk? are you serious, Micheal? Milk in the soup, I’ve never tried any thing like that!

the soup’s almost done

then the roast chicken!

chicken in the oven

I don’t like coffee very mush, but that morning I tried Michael’s favorite Mocca with an extra shot! And it was great, indeed, rich and creamy, but I don’t want to addict to coffee, for one thing it’s expensive , also caffeine’s not good to me in a long run. For all these days I’m in the US, I was all in big cities, New York, Minneapolis… It’s said life in small towns in the US is very different from life in big cities, and that’s real American life. Michael know I want to see some small town, so he decided to show me the small town he and Misti went to college and got married in! The town named NorthField, but ironically it’s located at 1 hour south of Minneapolis. We went to see the college first, it located on a hillside, that reminds me of the Zhijiang campus of my undergraduate school. The college use to run by religion, but not anymore, but many professors there also ministers. Michael and Misti was married by their professor, who was also a minister, in a church in the college. Then we went to the small town surround the campus. Micheal said it’s not a very small town with a population around 15,000. I would have to say, in China such population is just a tiny village! In this small town we found a 2en-handed book store, any bought my first English fiction — Harry Potter! Micheal told me he use to work as a chef in a local restaurant, and he love to cook. So he decided to show me some real American roast chicken and his secret chicken soup! Right, lots of chicken!!

As how he make the soup and the chicken is top secret, so I will only show you the pictures But I need to tell you, if you every went to Minnesota, you got to try Micheal’s secret chicken soup, it’s really delicious! Maybe I will open a restaurant in China serve Micheal’s secret soup after graduate, haha.

It’s their tradition to send Xmas card with their (kids) photos

It’s a flier poste, I forget the name, but it’s closely associated with chaos, it looks like a chaos though.

beautiful campus ！

inside the library

delicious dinner!!

showing us the VCR in Ghana

this is the texture they bought in Africa!

The schedule was visiting MU(Minnesota University) and have dinner with J and David (an interesting couple, friends of M&M).

Minnesota University is very different from NYU, it has two campuses (actually NYU is different from most other universities) , one in Minneapolis the other in St. Paul. Michael had studied anthropology and chemistry here 17 years ago, and then changed his major to law. Minnesota University like many Chinese universities, are very big and open. It’s winter brake, but still, many students in the campus. I saw some Chinese students were taking pictures in the snow, may be they are from south too. We discussed a lot about education in college and when and how to decide major. When we realize we were lost tracking of time, it was 1.30 in the afternoon.

We went back home for a while, then prepared for visiting J & David. It’s a courtesy to bring wine to dinner, so lucky for me, I can explore the wine-culture of Minnesota. We went to a liquor & spirit store, according to US law, drinking or purchase alcohol under 21 is illegal, so everyone entering the shop has to show his/her ID with DOB. It’s very different from China.

The couple we visited that night is very interesting people, they are curious about anything. They had been to China before, ten years ago, they love Beijing, and want to visit China again some time. The husband David is Africa American, last month, they and the whole family went to Ghana to find David’s ancestors, and they found it!! J talked and talked, wanted to tell us about everything in their trip! They showed us the VCR and the texture they bought from Africa. They are very good couple, while J likes to talk, David keeps track time, they are so right for each other! Oh, before I forget, I should tell you David is a great chief! The soup, tofu, fish and dessert were all delicious!! And all food served in their 25th anniversary China!

after 4 hrs delay, I finialy arrived at Misti&Michael’s home in Minneapolis!!!

Michael’s sister’s house, where M&M(it’s not a chocolate) now live

-15C!! I love snow

This is the frozen lake!!! a giant block of ice, you can even drive on it!!

“Roger this is it, the lake” “but where is the lake?”

found it, it’s under my feet!

“someone please clean this construction garbage!”

it’s fun!

come on Michael, am I that boring?

The wonderful trip has a not very attractive, a bit annoy actually, start: the plan delayed in LGA NY for 3 hrs, more worse, on the run way. There were 20+ planes before us waiting for taking off! And when we arrived at Minneapolis, the delay was not over, due to snow, we have wait on the run way for another 1 hour to get off the plane. Finally after 6 months, in the other country, in a very different temperature, Michael Misti and I met again!!

After showing me my lovely room on the second of their temporary home, Misti told me the general about Minneapolis and St. Paul, known as the twin city. It’s the capital of Minnesota, the two city divided by the Mississippi river from the middle is located in the very north point of the lower-48-state. It’s winter temperature could drop to below zero F, which is almost -20C. The cities are not very big with couple thousands population, actually compare to Chinese cities, it’s just a small town. But the area it big, people usually live in houses, and car is, of course, their major way to go and back from work.

The first night, they took me to a very neat pizza restaurant, the food’s great, the restaurant’s great too, but they just didn’t let me to pay for anything. We had a long argument about this, finally they won, which I think is not fair, maybe we should have a Chinese argument some time . Then we went back home, and had a long, great conversation. I was nervous before visiting them, worry about nothing to say with my poor English. But Misti and Michael just so supportive, all I need to do is say whatever in my head, they will interpret the code. After 10 o’clock, Michael went to sleep on the couch, it’s said to be his tradition . Misti and I continue talked for hours about politics, culture difference, education, etc etc, despite the snore and my poor English. I’m really amazed by how much I can say in English, and of course, how much Misti can understand!!

The next day, after drove Misti to work, Michael drove me around Minneapolis and took me to the frozen lake! I never saw a frozen lake before, when I step my feet on the gigantic ice, it just feel awesome!! But Michael told me the ice is only couple inches thick, and many fish can survive beneath the ice shell. That night we had dinner with M&M’s good friends Ken, who is a very interesting person, guess what he sells? Peanut butter! and further more, with different flavors, have you heard about curry peanut butter? chocolate peanut butter? Ask Ken!! And it’s him, who suggested go tubing. That’s how we (3 lawyers 1 professor and a CS graduate student) ended up like 5 snow man later on..

I was visiting Michael and Misti last week.

6 months before when we first met at Tiger Leaping Gorge China

It maybe a little bit late to say so long to 2007, there’re so many things happened in the passed year, some make my life totally differnet. But among which, the most exciting thing is travel in YunNan China with my Mom, where I met a lovely couple from US: Michael and Misti!

weeks ago, I am invited to visit them in Minneapolis!! How excited that is, after 6 months, we can meet again!!

Michael and Misti are both lawyers in Minneapolis, they are open-mind people, very interesting people. Last year, they quit their job and spent 3months travel in Asia, India, Thailand, China(where me met, and I’m glad they love China), and when they return to the US, they just didn’t feel have had enough! So they continued another CRAZY adventure in the US: drove almost 3 months, visited 13 national parks, across almost half America even into Alaska!!! Now, after 6 months of traveling, they decided to work again(maybe have to ^-^ ), but before that, they want to show me some real Minnesota, real American live!!!

During the week in Minneapolis, they took me tried different food, met interesting friends, see small town and college, tubing, Michael even cooked his secret soup for me! It’s a perfect trip, except they didn’t let me pay for anything.

I’ll post more pictures soon!