{"id":234,"date":"2012-09-06T22:42:01","date_gmt":"2012-09-07T02:42:01","guid":{"rendered":"http:\/\/antoine.wojdyla.free.fr\/blog\/?p=234"},"modified":"2012-09-24T11:11:50","modified_gmt":"2012-09-24T15:11:50","slug":"perceptive-hash","status":"publish","type":"post","link":"http:\/\/antoine.wojdyla.fr\/blog\/2012\/09\/06\/perceptive-hash\/","title":{"rendered":"Perceptive hash"},"content":{"rendered":"

Continuing with metrics…<\/p>Everybody can easily recognize a tune, a famous painting or the face of a friend. Not so for a computer, who must first digitize<\/em> the information, and operate on this dataset to find similarities. Back in the beginning of computer era, people though that it would be easy to recognize characters or voice, but technology had hard time with these issues. OCR<\/a> is still perfectible, while voice recognition is still not common (things are getting better, but Siri<\/a> is still fallible)<\/p>\n

\"\"<\/a><\/p><\/p>This is of particular importance nowadays, since our societies tend to control more and more the population, in the name of terrorism prevention. Since they cannot employ as much operator as there are citizens, there is strong need automation and recognition. The general problem of recognition is to find patterns<\/em> that reflects a feature<\/em>.<\/p>I discovered the notion of “perceptive hash”, which is essentially the problem of recognition through the simplification of data, wondering how websites such as TinEye<\/a>, worked in their way to find similar images. I subsequently discovered that there is an open source library called pHash<\/a> that allows this kind of features (not to mention computer vision frameworks such as OpenCV<\/a>, or the incredible Accord.net<\/a> developped by Cesar Souza)<\/p>To find similar pictures<\/strong>, there are serveral hurdles. First : all the pictures might not have the same size, they can be cropped, (slightly) modified\u00a0 or rotated.It seems that there are two solutions. The first consists in a brutal dowsizing of the images, followed by a Fourier transform : the Fourier coefficients will capture the fingerprint of the image (this is somehow similar to how How Shazam works<\/a>) for comparison to a database.
\nAnother option is consider the histogram instead of the picture, and perform comparision using least-square or Bhattacharya distance<\/a>.<\/p>\n

\n

\"\"<\/a><\/p>\n

Size reduction and\/or histograms to find similar images<\/p>\n<\/div>

I guess this is the one used by TinEye
\nThese methods are rather robust to slight changes in the image, for there is no information on scale, and because the actual location of pixels <\/em>is erased <\/em>.
\nNote that Google image search is based on contextual informations, rather than on actual images.<\/p>Face recognition<\/strong> is another problem. First, one has to dectect a face. This is done through machine learning and particulare metrics. I remember (when I used it) that a popular algorithm was Viola-Jones algorithm<\/a>. The underlying idea is to compute what is called the so-called integral image<\/a>,where each pixel is the some of all the preceding pixels and comparision with Haar basis function. It turns out that a face is (perceptively) the combination of certain Haar functions, the successful combinations being determined by learning. For Facial<\/em> recognition (i.e. to tell two person apart, in software such as iPhoto or facebook), I don’t know how they do!<\/p>Spell correction<\/strong> is also a class of feature recognition. A good explanation of how it works is detailed here<\/a>. I first thought that the employed method would use specific word weighting, but no : it seems to be only inferences ;-(. I want to mention the map of Paris metro made only with anagrams<\/a> which really impressionned me. I still don’t know how the guy managed to get all these anagrams. Not by hand, I hope!<\/p>\"\"<\/a>For optical character recognition<\/strong>, they also use neural networks, probably in conjunction with wavelet<\/a> or mathematical morphology<\/a> to remove all unwanted features. But I never got very deep into that problem… Can somebody give me information on the state of the art?<\/p> <\/p>I want to mention here the website Hook theory<\/a> (and the companion iPad book<\/a>) which tries to explain<\/em> how music works, emotionnally.
\nI guess that understanding why<\/em> a feature is the way it is is more sutble than brute-force search for patterns.
\nEmotion vs<\/em>. Reason. Again<\/p>\n","protected":false},"excerpt":{"rendered":"

Continuing with metrics…Everybody can easily recognize a tune, a famous painting or the face of a friend. Not so for a computer, who must first digitize the information, and operate on this dataset to find similarities. Back in the beginning of computer era, people though that it would be easy to recognize characters or voice, […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[11,13,9],"tags":[],"class_list":["post-234","post","type-post","status-publish","format-standard","hentry","category-english","category-epistemology","category-science"],"_links":{"self":[{"href":"http:\/\/antoine.wojdyla.fr\/blog\/wp-json\/wp\/v2\/posts\/234","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/antoine.wojdyla.fr\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/antoine.wojdyla.fr\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/antoine.wojdyla.fr\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/antoine.wojdyla.fr\/blog\/wp-json\/wp\/v2\/comments?post=234"}],"version-history":[{"count":9,"href":"http:\/\/antoine.wojdyla.fr\/blog\/wp-json\/wp\/v2\/posts\/234\/revisions"}],"predecessor-version":[{"id":557,"href":"http:\/\/antoine.wojdyla.fr\/blog\/wp-json\/wp\/v2\/posts\/234\/revisions\/557"}],"wp:attachment":[{"href":"http:\/\/antoine.wojdyla.fr\/blog\/wp-json\/wp\/v2\/media?parent=234"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/antoine.wojdyla.fr\/blog\/wp-json\/wp\/v2\/categories?post=234"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/antoine.wojdyla.fr\/blog\/wp-json\/wp\/v2\/tags?post=234"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}