{"id":41,"date":"2009-04-10T13:58:57","date_gmt":"2009-04-10T03:58:57","guid":{"rendered":"http:\/\/www.computer-vision-software.com\/blog\/?p=41"},"modified":"2009-11-30T12:58:17","modified_gmt":"2009-11-30T02:58:17","slug":"fixing-opencv","status":"publish","type":"post","link":"http:\/\/www.computer-vision-software.com\/blog\/2009\/04\/fixing-opencv\/","title":{"rendered":"&#8220;Fixing&#8221; the OpenCV&#8217;s implementation of Viola-Jones algorithm"},"content":{"rendered":"<p>Today&#8217;s story is about improving performance of OpenCV library on the ARM-based platforms.<\/p>\n<p>As you already know (from <a onclick=\"javascript:pageTracker._trackPageview('\/outgoing\/www.computer-vision-software.com\/blog\/2009\/04\/opencv-vs-apple-iphone\/');\" title=\"here\"  href=\"http:\/\/www.computer-vision-software.com\/blog\/2009\/04\/opencv-vs-apple-iphone\/\" target=\"_blank\">here<\/a> or from <a onclick=\"javascript:pageTracker._trackPageview('\/outgoing\/www.computer-vision-software.com\/blog\/2009\/03\/arm-wrestling-with-opencv\/');\"  href=\"http:\/\/www.computer-vision-software.com\/blog\/2009\/03\/arm-wrestling-with-opencv\/\" target=\"_blank\">here<\/a> or may be even from <a onclick=\"javascript:pageTracker._trackPageview('\/outgoing\/www.computer-vision-software.com\/blog\/2009\/03\/profiling-opencv\/');\" title=\"here\"  href=\"http:\/\/www.computer-vision-software.com\/blog\/2009\/03\/profiling-opencv\/\">here<\/a>), face detection algorithm implemented by OpenCV library doesn&#8217;t work perfectly on ARM processors. Science doesn&#8217;t know for certain why this happens. There might be several possible reasons. One of our assumption was missing of hardware support for floating point operations. So we tried to translate Viola-Jones algorithm from floating point to fixed point. And that&#8217;s how we did this&#8230;<\/p>\n<p><!--more--><\/p>\n<p>First of all, to make life easier it was decided to limit functionality of cvHaarDetectObjects a little:<\/p>\n<ul>\n<li>Our version will work with one specific cascade for frontal face detection from the bundle distributed with OpenCV<\/li>\n<li>We will not support Canny pruning<\/li>\n<li>No image scaling<\/li>\n<\/ul>\n<p>Actually, it is not necessary to use only frontal face cascade &#8211; any cascade without trees (stump based cascade) can be used.<\/p>\n<p>Second. We made few observations:<\/p>\n<ul>\n<li>Sizes of rectangles, which are used as classifiers, in the frontal face cascade are integer numbers. In OpenCV implementations they are defined as float though.<\/li>\n<li>Rectangles weights are also integers.<\/li>\n<li>&#8220;Left&#8221; and &#8220;right&#8221; values for rectangles are floating-point numbers in the range (0, 1). Their sum is not bigger than few thousands. Thus, they can be easily converted to integer by multiplying them by some constant. We choose 65536. This provides good enough accuracy (you will still loose some precision).<\/li>\n<li>The same is valid for stage threshold.<\/li>\n<\/ul>\n<p>Also we replaced using of sqrt with its integral version. This let us calculate variance in integer numbers.<\/p>\n<p>Thus, with all above it became possible to convert entire detection algorithm to integer numbers. The only floating point calculation, we still have, are calculations of current search window according to the scale factor. But their input in the overall execution time is very insignificant.<\/p>\n<p>So, what are the numbers you&#8217;ll ask. And I tell you.<\/p>\n<p>With OpenCV Lena&#8217;s face (everybody knows Lena, right?) was found on the iPhone in about <strong>3-16 seconds <\/strong>(depending on the parameters).<br \/>\nWith our fixed-point based algorithm the same face was found in <strong>0.5-3 seconds <\/strong>(depends on parameters).<\/p>\n<p>Thus switching from floating- to fixed-point improves detection performance up to 5 times. Search will not be as precise as in the original OpenCV version (it might not find face on some pictures), but it will be accurate enough for the most of the tasks.<\/p>\n<p>Precision problem can be solved if OpenCV implementation is not reworked as radically as in our version &#8211; some of floating-point calculations can be left as is. This will keep original accuracy of Viola-Jones, but increase performance (in about 2 times).<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Today&#8217;s story is about improving performance of OpenCV library on the ARM-based platforms. As you already know (from here or from here or may be even from here), face detection algorithm implemented by OpenCV library doesn&#8217;t work perfectly on ARM processors. Science doesn&#8217;t know for certain why this happens. There might be several possible reasons. [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[84],"tags":[19,29,32,31,20,6,28,30],"class_list":["post-41","post","type-post","status-publish","format-standard","hentry","category-opencv","tag-apple","tag-face-detection","tag-fixed-point","tag-haar","tag-iphone","tag-opencv","tag-performance","tag-viola-jones"],"_links":{"self":[{"href":"http:\/\/www.computer-vision-software.com\/blog\/wp-json\/wp\/v2\/posts\/41","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/www.computer-vision-software.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.computer-vision-software.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.computer-vision-software.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.computer-vision-software.com\/blog\/wp-json\/wp\/v2\/comments?post=41"}],"version-history":[{"count":0,"href":"http:\/\/www.computer-vision-software.com\/blog\/wp-json\/wp\/v2\/posts\/41\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.computer-vision-software.com\/blog\/wp-json\/wp\/v2\/media?parent=41"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.computer-vision-software.com\/blog\/wp-json\/wp\/v2\/categories?post=41"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.computer-vision-software.com\/blog\/wp-json\/wp\/v2\/tags?post=41"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}