Dr. Squirrel And Magic Glasses

Augmented Reality with Leap Motion, OpenCV, Three.js

2014-12-19T00:52:00.002-08:00

Another happy exploring with IPython notebook.
OpenCV is used to calibrating the camera, and find out the position of the camera in Leap motion coordinate. Then, match the webgl camera setting, and have some fun.

See also a google hangout presentation with the help of leapmition.

Finding low and high md5/sha512 hashes with OpenCL and Python

2014-09-19T17:55:00.001-07:00

Currently the leader of The Famous Hash Game(for MD5) and hash|challenge, with my HD7970, IPython notebook, and PyOpenCL, atitweak, and kernels modified from oclcrack and John the Ripper.
Source code can be found at http://nbviewer.ipython.org/github/tjwei/tjw_ipynb/blob/master/lowest%20md5.ipynb
and http://nbviewer.ipython.org/github/tjwei/tjw_ipynb/blob/master/lowest%20sha512.ipynb
The hash rate on my HD7970 GE is about 6.8 ghash/s for md5 and 175 mhash/s for sha512

Real Programmers Use One-Way Hash Function

2014-09-10T01:52:00.001-07:00

GNU nano is a text editor - a program often used to edit the source code of other programs. Emacs, Vim and ed are all progressively more "hard core" editors. cat is a Unix program that concatenates and outputs the contents of files. Things get steadily more ridiculous from here. Using a magnetised needle to flip bits on a hard drive requires nanometer precision and binary mastery, but in the early days of programming people did use needles sometimes to fix bugs on Punched cards. The use of a magnetized needle may also be a reference to the Apollo AGC guidance computer, whose instructions were physically written as patterns of wires looped around or through cylindrical magnets in order to record binary code. -- http://www.explainxkcd.com/wiki/index.php/378:_Real_Programmers

For a real programmer, writing binary executable directly seems to be a bit too easy, even with magnetized needles. The real hard core way is using one-way hash functions, like sha2 or md5.

In the spirit of Great Python Challenge, which were used to promote PyCon APAC 2014, I posted a challenge on my Facebook, aksing if anyone can use one-way hash function to write program, for example:

cat 0.c| shasum -a 384 | xxd -p -r > a.out && chmod a+x a.out && ./a.out

sha384 was chosen because it is possible to fit an ELF binary into sha384 digest (see http://www.muppetlabs.com/~breadbox/software/tiny/teensy.html).

After I posted the challenge, I was trying to find a solution myself too. It turns out that it is possible to do so.
Follow below steps (Copy& Paste) to try the code:

mkdir test
cd test
wget https://raw.githubusercontent.com/tjwei/tjw_ipynb/master/0.c
sh 0.c
gcc 0.c && ./a.out
cat 0.c | shasum -a 384 | xxd -p -r > a.out && chmod a+x a.out
./a.out

The story

The first solution is https://github.com/tjwei/tjw_ipynb/blob/master/a.c
Sort of working, but I am not satisfied because I'd expect it can at least say "Hello World!".
My 2nd attpemt is https://raw.githubusercontent.com/tjwei/tjw_ipynb/aa733143a5a76f460122e93028f49693d53931e8/0.c
which is not bad, it does say "Hello World!", but still has some issues I don't like.
I realized that I have to search the solution harder. First thing I did was to reduce the length of the code to fit in 112 bytes, so that the whole code can be fit in one sha512 block. This can speed up the hashing by a factor of 5~7. In order to do that, all description, which was in the comment of the code, were moved to a webpage and the url is shortened.
Then, I use OpenCL and a customized kernel to do the sha384 hashing. On my HD7970 ghz edition, it can do 160 mhash/s, without overclocking the card.
You can find the final result: https://github.com/tjwei/tjw_ipynb/blob/master/0.c
And working notebook at:
http://nbviewer.ipython.org/github/tjwei/tjw_ipynb/blob/master/RealMan2.ipynb

And

Since it is a challenge, I do receive some replies. An answer from Kuo-Tung is quite good too, see http://paste.plurk.com/show/1982392/

Poor man's Holograph

2014-09-09T05:24:00.003-07:00

This is a simple proof of concept, using an Android Phone as a Swept-volume display. Above showing a cube, two of the sides display english letters. Because the refresh rate of the the my android screen the the frame rate of my video recoreder, the actual result is better than it seems on the video (kind of like recording a CRT wtih a video recoreder)

You can find a lot of POV Display videos on youtube

and Volume Display like Led Cube

Swept-volume display is something in between of led cude and POV.
The good thing is X,Y resolution is much better than LED cube, the phone (old acer stream) has a 480x800 AMOLED screen. However, the resolution on Z-axis is ver low, 6～8 pixels if we are lucky.

A GIF image can be run as Python, Ruby, JavaScript, and Jave program.

2014-09-09T05:12:00.001-07:00

The above image, face6.gif, is a proper GIF can be run as python script in window/linux/mac/cygwin.
That is, try
python face6.gif
in command line, it can be executed (by CPython).
Moreover, it can run as ruby, perl, and java program.
ruby -x face6.gif
perl -x face6.gif
java -jar face6.gif

If you rename face6.gif to face6.html and open it with a web browser, the javascript code with print "Python rocks".

You can also try
rar x face6.gif
and not suprising, you can use also open it with any image viewer.

Since it is a jar file, so using unzip -v face6.gif, you can find java classes. It also contains a __main__.py, but __main__.py won't be executed by CPython. This is because CPython does not like zip files with comment.

Enhace PyCon APAC video recordings with the help of slides and OpenCV

2014-09-09T04:02:00.000-07:00

The quality of some of the video recordings of PyCon APAC 2014 are really poor (see below examples). Since most of speakers release their slide files under creative common license, we thought we might use these slides to repair the video.
The basic ideal to render the slides as images, and match the video recordings, and then use the rendered slides to replace the poor images in the video recordings.
First, I was thinking about some like feature matching and tried to use ORB to find key points on videos and slides. Unfortunately, the quality of video recordings is so poor, that feature matching does not work, at least not work if we use ORB.
My second attempts is using linear algebra to do template matching. It turns out that CV_TM_CCOEFF_NORMED method works good enough.
However, we need to manually find the position of the slide image in the video recordings. The position depends on speakers laptop and perhaps the video connector. But it seems to be fixed for the entire talk. So we only need to adjust the parameter once for each talk.
With the help of IPython interactive widgets, it is not too difficult to do that manually. And by using SIFT feature matching, we can find the parameters semi-automatically.
All we need to do manually is to find a frame of video recordings and a rendered image of the slides that match each other.
I guess it won't be to hard to make the whole process full automatic, but the semi-automatic tools is good enough for our original purpose.
The followings are the tools we uses.

VideoSlidesSyncWrite.ipynb automatically sync the video and slides and then encode the video (see below).
Interactive_compare.ipynb interactive tool to find the parameters(above picture)

The following is the outline of our process

Extract pdf as a series of png images. Althoug there are python modules like wand can do that in python, we shamelessly using shell call to do that with ImageMagick convert.
Find out the coordinates and size of the slides in the video recording using interactive tool
convert the images to 256x256 gray scale, using CV_TM_CCOEFF_NORMED to find the matching slide. 256x256 is a quite arbitrary choice, and perhaps more than enough. Perhaps 128x128 should work just fine.
The cut-off parameter does not need to be to precise. Some value between 0.5 and 0.95 should work most the time.
Manually put some slides into black list. This is mostly because pdf files does not contain the slides animation that used in the actual talk. If the pdf includes the animation that can be generated into a series of png images, then our algorithm works very well.
Because don't know how to encode video with audio with OpenCV, So shamelessly call the avconv to do merge the generated video and original audio track.

Followings are some scree shot of the enhanced videos and original videos.

Toomore's talk. This recording is the "motivation" of this project.

The text of original recording is unreadable.

Tseng's talk. The quality of the video recording is equally poor.

The final result is quite good, but the slides has been updated, so the match failed for the cover slide.

Cheng-Lung Sung's talk is different, seems like perspective transformation might be needed.

We thought we might need to modified our interactive tools, however, affine transformation works.

Even with recordings with better quality, like the recording of Andy's talk, our tools still enhance the quality significantly.

feature matching in the interactive tool

The followings are the enhanced videos

Solve HITCON 2014 CTF with IPython notebook

2014-09-09T03:06:00.002-07:00

This my first CTF, try to solve it with IPython noteook. I only got 7 flags, but solve it with IPython notebook is a fun experience for me, very interactive and I can visualize my progress. See QR maze video below. Using IPython notebook and the power of python, the telnet based maze can be easily visualized in a web browser, and I won't lose my progress between the telnet connections, because every thing is kept in the IPython kernel.
Most of ipynb files can be found at http://nbviewer.ipython.org/github/tjwei/tjw_ipynb/tree/master/

Some of my draft papers on mental poker

2014-06-22T21:22:00.001-07:00

Source code can be found at https://github.com/tjwei/mental_poker

First you learn to code, then you code to learn

2013-12-22T01:33:00.002-08:00

Great Python Challenge

2013-10-31T19:34:00.001-07:00

Just like "The Great Giraffe Challenge", let us take the Great Python Challenge.

The answer will be a piece of very short, one-liner like Python code. So it won't take too much of your time.

As usual, if you failed, changed your profile to a python related picture until, say, you find out the answer.

Are you ready?

Please write a simple http server in less than 40 characters of Python code.

A server can only send "Error Response" or worse does not count. A server can only serve one request does not count. It has to be something like a SimpleHTTPServer at least.
You can use either standard CPython 2.x or 3.x. Only the standard library are allowed.
The solution should not rely on command line argument, environment variable, or similar technique to by pass the limit.
All you can use is CPython and it's standard library.

So, got your answer yet?
.
.
.
.
.
.
If you think you know Python, then chances are you can do that.
If your code contains exactly 40 characters, please try harder.

But there are more,

Same as above, but please write it in less than 35 characters.

A bit more fun and challenging, right?
Can you do that?
.
.
.
.
.
.
But we are not done yet, now

Same as above, but please write it in less than 30 characters.

I didn't find the last answer by myself without the help from friends, so I changed my facebook profile to the picture on the top of this post.

.
.
.
.
.
.
If you can write a python web server in 29, 28 or even 25 characters, then very well done, good job.
We have one more task for you,

Same as above, but please write it in less than 25 characters.

2013-04-24T22:50:00.000-07:00

The reflect package of Go 1.1 adds functions SliceOf, ChanOf，and MakeFunc.
With the help of these new functions, we can do things similar to Python's map, list, iterator comprehension, and decorator in Go.
The followings is a simple demonstration of functionality similar to Python's map function and list comprehension.

Math Proofs of Google Code Jam Qualification Round 2013 Problems

2013-04-15T06:37:00.000-07:00

Problems of Google Code Jam Qualification Round 2013 can be found at http://code.google.com/codejam/contest/2270488/dashboard

$\newcommand{\lyxlock}{}$

Warning: MathJax requires JavaScript to correctly process the mathematics on this page. Please enable JavaScript on your browser.

1 Problem A. Tic-Tac-Toe-Tomek

No math involved, but complex number is builtin in python and go, so I use

to represent “ “, T, O, X. So if

, then some one won.

2 Problem B. Lawnmower

Theorem.

is a possible pattern if

for every

Proof.

Can be easily proved by induction on

, where

3 Problem C. Fair and Square

Let

, where

and

. Denote by

the

-th digit of

, then we have

Assume

is a palindrome, i.e.,

for every

Let

be the coefficient of

that is,

Theorem.

is also a palindrome iff

for all

Proof.

(

)

Trivial.

(

)

Observe that

for all

. We prove the statement by mathematical induction on

for

Case

Since

and

it is easy to see that

. So

Moreover, we also know that

has

digits and hence

for all

Case

Suppose

for all

, we want to show

By the induction hypothesis, we know that

for all

. So

On the other hand,

Therefore,

, hence

Corollary.

is also a palindrome iff

Proof.

(

)

for every

by Cauchy-Schwarz inequility.

(

)

Trivial.

In particular, if

, then

4 Problem D. Treasure

Let

be the set of all key types. Assume

Construct a directed graph

as following:

iff we starts with at least one key of type .
If , then iff there is a key of type in a box of type . for every palidrone by Cauchy-Schwarz inequility.

Denote by

the number of boxes of type

and

the total number of keys of type

(including the keys you start with and keys in boxes).

Theorem. All box can be opened iff for every

and there is a directed path from

in graph

Proof.

(

)

, then we don’t have enough keys of type

to open all boxes of type

If there is no path from

, then it means we are unable to get any key of type

(

)

We prove this by induction on the number of boxes. Denote by

the number of boxes.

Assume for every

and there is a directed path from

in graph

Case

Then all vertices in

are leaves except

and the type of the only box. So there must be an edge from 0 to the type of the box.

Case

Suppose the theorem holds for the case with

boxes.

There are at least one

. Consider we open a box of type

(that contains a key of type

if possible). Assume we destroy the key and the box just opened, then we have a setting of

boxes. In this setting, we still have

for all

. Let

be the directed graph of this

-box setting.

, then all children of

become children of

can still reach all other types in

Assume

, then we can open a box of type

that contains a key of type

Otherwise, because

, we still hold at least one key of type

after we open a box of type

(and destroy the key).

Either way,

. Therefore, for every child

, either

(if a key of type

is in the box we just opened), or

and so there is a path from

and then to

can still reach very vertex in

By induction hypothesis, the remaining

can also be opened.

By the proof of the theorem, there is a simple algorithm to open all boxes: open any box unless you have just one key of that type and box does not contain a key that can open itself.

However, this algorithm may not yield a "lexicographically smallest" way to open the boxes.

The solve the problem, you should open the box with smallest number such that either this box is the last one of type

or there is still a way to get a type

key.

Py Girl 3rd try

2013-03-19T09:17:00.000-07:00

Py Girl impersonate (or perhaps it counts as cosplay) Haruhi Suzumiya.

Anime style.

Black white manga style.

Blender renderd and edited in gimp

Project Euler Problem 198

2013-03-12T22:40:00.000-07:00

Original post in Chinese: 2008/06/project-euler-198.html

Project Euler Problem 198 asek you to find all ambiguous numbers between 0~0.01 with denominator no more than 10^8, where by definition, a real number x ambiguous, if there is at least one denominator bound m for which x possesses two best rational approximations. For example, let x=9/40 and m=6, then 1/5 and 1/4 are both best rational approximation of x with denominator no more than 6. Clearly, an ambiguous number is necessarily rational.
This seems to be difficult if you don't have certain number theory background knowledge. On the other hand, if you do have the certain knowledge, you may think 10^8 is kind of too small for a Euler project problem. IIRC, you can find a nice algorithm in Knuth's The Art of Computer Programming.
However, it is pretty straightforward to solve it by recursion using Haskell:

f a b l m | a*b>l || (a==1 && b > m)  = 0
         | otherwise = (f a c l m)+1+(f c b l m) where c=a+b
main = putStrLn $ show result
      where result= (f 1 100 l2 m) + 49+l2-m
      l = 10^8
      l2 = l `div` 2
      m = floor (sqrt (fromIntegral l2)

As easy as 7 lines of code, yet the code is a pretty straightforward translation of the mathematics behind it. However, using Python to solve it is a totally different story. The above recursion exceeds the limit of numbers of function calls in python. The following is a loop based solution:



def p198(M=10**8, z=100, cnt=0):
 M2=M/2
 a=m=int(M2**0.5)
 stack=range(z,m)
 while stack:
     b=stack[-1]
     if a*b>M2:
         a=stack.pop()
     else:
         cnt+=1
         stack.append(a+b)
 return cnt+M2-z/2

The code is directly copy from the code I gave on Project Euler website, so it does not look good.
With the help of psyco, it is fairly fast, but is not very readable by human and can not be considered as a straightforward interpretation of the mathematics behind the problem.
On the contrary, doing some easy tasks in Haskell is not so elegant. For example, suppose we want to find the integer part of the square root of an integer n, and then print it on the screen. Doing this task in python is as simple as you can imagine.

print int(x**0.5).

To do this in Haskell, you will have to convert the integer n to a float point number, then take square root, then take floor, then covert it to an integer, and then convert it to a text before it is ready to print on screen.

putStrLn.show $ (floor . sqrt) (fromIntegral n)

If there are a lot of float point numbers and integers involved, then you probably need to do the coversion every here and there in your code. I know that those conversions exist for a good reason, however, sometimes you just fell like to do a quick and simple computation.
Sure Haskell can make complicate tasks simple and make simple tasks complicate.

Py Girl, 2nd try

2013-03-10T09:24:00.000-07:00

Looks a bit better than the first try, but still not quite there.

It is created using blender + freestyle like before. I also use gimp to auto balance the color. The original blender rendered image can be found below.

The basic idea of this image is inspired by Nüwa and Zhao Ling'er, as suggested by Jenny JS Liang.
The background image features a landscape painting of Fan Kuan.

The .blend file can be downloaded at Blend Swap.

Blender Renderting Time (On computers available to me)

2013-03-10T09:03:00.003-07:00

This a simple test of of the rendering time of blender internal render.
I was curious how Xoom or Azure compares to my desktops and laptops. However, running blender in the chrooted ubuntu of my xoom causes a segment fault ( for both the ubuntu blender and a 2.66 blender compiled by me).

The test .blend file is my Python Girl video. The video has 800 blender rendered frames (frame 600 - frame 1400). But in this test, only one of every 4 frames between frame 1250 and frame 1346 are rendered. We measure the difference between the modified time of 1250.png and 1346.png.

The blender used in this test is freestyle branch. On windows, a 32bit executable is used. 64 bit binaries are used on linux and OSX.
The followings are the results：

Core i7-2700 Ubuntu 12.10: 19min 16sec
Azure extra large 8 core Ubuntu 12.10: 32min 45sec
Core 2 Quads Q9500 Win7: 53min 8 sec
Macbook Air Core i5-3317u: 60min
Win8 Core 2 Duo T5600: about 3 hours (I had a train to catch, so unable to finish the rendering)

The segment fault on Xoom could be caused by kernel incompatibility or because Xoom does not have enough RAM. But compiling blender on Xoom took like 10 hours while compiling on my Core i7 desktop took only 10-20 minutes.
If possible, it would be interesting to run the same test on an ipad, iphone, EC2, raspberry Pi, or high end android phone like HTC One, Butterfly, or may padfone infinity, S4.

The Life of Py : Girl Py Debut

2013-03-06T00:08:00.000-08:00

Girl Py or Python Girl is an anthropomorphic character of Python programming language. The original purpose of this character is to promote PyCon Taiwan.

Most tools used to create Girl Py are python related.

The main tool is Blender with freestyle, which is no doubt a python related 3d rendering and modeling tools.

The body of the character is created using Makehuman. Makehuman contains a lot of Python code, in fact, the version I used is the pure python branch. Makehuman is designed for modeling realistic human bodies instead of manga style ones. Fotunately, makehuman support customized skin and target. I made a manga skin and manga target for it. The result of first draft looks like the following.

The hair color is actually black, but the light was too strong, so it looks very pink.

The face generated by my manga target is kind of ugly and scary, but does not look that bad with smooth modifer.

After playing with makehuman and blender awhile, I was getting more familier with these tools and improve the target a bit.

It looks less scary and more smooth now but still ugly.

After adding some manga style material, it looks like the following

Still not good. Because of the time constraint, I decided to model the face by blender directly instead. Using the models list at the end of the video as reference and inspiration, the result is the following:

It looks like this in Blender's opengl view

The python code featured in the video is PyLottery of PyCon Taiwan 2012, which generates an animated snake to fetch random lottery balls.

Other software used in this project are OpenShot and gimp, all python related.

The next image is the credit at the end of the video

PyCon Taiwan 2013 is Calling for proposals, you are welcome to submit your proposals.