Understanding the prefix-function of the Knuth-Morris-Pratt algorithm

Intuition is nothing but the outcome of earlier intellectual experience.    – Albert Einstein

There are plenty of tutorials about the ideas of the KMP algorithm, leaving us the wonder and owe of its magnificent simplicity and effectiveness. But one important part is frequently missing – why the prefix function can be computed in that particular way; what is the rationale behind the computation of the prefix function. This post aims to demystify the prefix function and elaborate on the proofs to understand why it works.

Let’s first review the computation of the prefix function, as shown below.
Screen Shot 2016-04-20 at 5.37.41 PM Continue reading “Understanding the prefix-function of the Knuth-Morris-Pratt algorithm”

How to do research

One of the biggest questions that graduate students have is “how to do research”. This post summarizes resources online about how to do research, and I hope it is helpful to the audience.

[1] How to do research at MIT AI lab link
reading, making connections, learning other fields, notebooks, writing, talks,  programming, advisors, thesis, research methodology, emotional factors.

[2] How to do research (advice) link
thinking of the question, answering the question, communicating the answer

[3] How to do graduate-level research: some advice link
Personal and professional principles: motivations and goals, tracking progress, time management, dealing with people, collaboration and mentoring, quality, attitude, dealing with failure, taking advantage of opportunities
The craft of research: keeping a notebook, reading, listening, talking, writing, programming, mathematical analysis, background subject knowledge
The art of research: identifying a problem, formulating a well-defined problem, thinking about a research problem, your advisor, the thesis


Histograms of Oriented Gradients Tutorial with Matlab

Histograms of Oriented Gradients is a feature extraction method that can generate descriptors from images. This blog post aims at providing illustrative examples of HOG with Matlab, as well as discussing its interesting characteristics.

HOG Person Detector Tutorial
I have found a very nice and intuitive tutorial here. In this post, I will focus on the illustrative examples with Matlab.

Key Idea
The key idea of HOG is that, “local object appearance and shape can often be characterized rather well by the distribution of local intensity gradients or edge directions, even without precise knowledge of the corresponding gradient or edge positions” [1], meaning the distribution of gradients can represent the appearance of an image to some extent. The transformation from images to HOG achieves invariance to local geometric and photometric transformations by ignoring specific image details while remaining the distribution of gradients.
Continue reading “Histograms of Oriented Gradients Tutorial with Matlab”