Real-time edge detection in camera viewport - Revision history

Hamishwillee: Hamishwillee - Change to use new video player which works with Lumia 920 and other mobile browsers

2013-01-30T04:58:42Z

Hamishwillee - Change to use new video player which works with Lumia 920 and other mobile browsers

Hamishwillee: Text replace - "`" to ""`


2012-10-11T01:18:33Z
Text replace - "<code cpp>" to "<code cpp-qt>"

			
			
			
			
		
		← Older revision
		Revision as of 01:18, 11 October 2012
		
Line 42:
Line 42:
  Below is an implementation of an edge detection algorithm ([http://en.wikipedia.org/wiki/Sobel_operator Sobel operator]) for RGB image. The implementation has purposefully been written to be inefficient so we can demonstrate how it can be improved.   Below is an implementation of an edge detection algorithm ([http://en.wikipedia.org/wiki/Sobel_operator Sobel operator]) for RGB image. The implementation has purposefully been written to be inefficient so we can demonstrate how it can be improved.
    
− <code cpp> + <code cpp-qt>
  function calcLuma(QRgb val)   function calcLuma(QRgb val)
  {   {
Line 85:
Line 85:
  The first problem is that we shouldn't use {{Icode|pixel()}} and {{Icode|setPixel()}} functions. They are inefficient because multiplication is used to calculate position of pixel - internally it most probably look like this: {{Icode|y * bytes_per_line + x * bytes_per_pixel}}. It is much better to use {{Icode|bits()}} and {{Icode|scanLine()}} functions to get position of all image or position of line in memory respectively. In this case we will use {{Icode|bits()}} function to get position of first line and will get address of next line by adding {{Icode|bytesPerLine()}} to previous line (notice that we are iterating over {{Icode|lines(y)}} in our algorithm). This way we can replace {{Icode|image.pixel(x,y)}} functions with something like this:   The first problem is that we shouldn't use {{Icode|pixel()}} and {{Icode|setPixel()}} functions. They are inefficient because multiplication is used to calculate position of pixel - internally it most probably look like this: {{Icode|y * bytes_per_line + x * bytes_per_pixel}}. It is much better to use {{Icode|bits()}} and {{Icode|scanLine()}} functions to get position of all image or position of line in memory respectively. In this case we will use {{Icode|bits()}} function to get position of first line and will get address of next line by adding {{Icode|bytesPerLine()}} to previous line (notice that we are iterating over {{Icode|lines(y)}} in our algorithm). This way we can replace {{Icode|image.pixel(x,y)}} functions with something like this:
    
− <code cpp> + <code cpp-qt>
  uchar* lineAddress = image.bits();   uchar* lineAddress = image.bits();
  ....   ....
Line 111:
Line 111:
  The last thing to solve is square root calculation - it is really expensive operation. Again we can optimize by precalculating values here: sqrt(x*x+y*y) will always be more than 255 when x or y is more than 255. In such case we need to create table of size 256x256 and precalculate square roots. Try using sqrt ({{Icode|qSqrt()}} function) instead of precalculated values and you will notice that view is lagging from about 0.5 to 2 seconds (depends on your phone's CPU). Here is MeeGo Harmattan implementation for precalculating square roots and using them:   The last thing to solve is square root calculation - it is really expensive operation. Again we can optimize by precalculating values here: sqrt(x*x+y*y) will always be more than 255 when x or y is more than 255. In such case we need to create table of size 256x256 and precalculate square roots. Try using sqrt ({{Icode|qSqrt()}} function) instead of precalculated values and you will notice that view is lagging from about 0.5 to 2 seconds (depends on your phone's CPU). Here is MeeGo Harmattan implementation for precalculating square roots and using them:
    
− <code cpp> + <code cpp-qt>
       for (int y = 0; y < 255; y++)        for (int y = 0; y < 255; y++)
           for (int x = 0; x < y; x++)            for (int x = 0; x < y; x++)



Hamishwillee: Text replace - "Category:MeeGo" to "Category:MeeGo Harmattan"
2012-06-13T10:57:52Z
Text replace - "Category:MeeGo" to "Category:MeeGo Harmattan"

			
			
			
			
		
		← Older revision
		Revision as of 10:57, 13 June 2012
		
Line 1:
Line 1:
− [[Category:Qt]][[Category:Multimedia]][[Category:Symbian]][[Category:MeeGo]][[Category:Code Examples]][[Category:Optimization]][[Category:Graphics]][[Category:Imaging]][[Category:Camera]][[Category:Symbian^3]][[Category:Symbian Anna]][[Category:Nokia Belle]] + [[Category:Qt]][[Category:Multimedia]][[Category:Symbian]][[Category:MeeGo Harmattan]][[Category:Code Examples]][[Category:Optimization]][[Category:Graphics]][[Category:Imaging]][[Category:Camera]][[Category:Symbian^3]][[Category:Symbian Anna]][[Category:Nokia Belle]]
  {{FeaturedArticle|timestamp=20120527}}   {{FeaturedArticle|timestamp=20120527}}
  {{Abstract|This article explains how to optimise an image edge detection algorithm so that it can be used for "real-time" previewing of video in the camera's viewport. }}   {{Abstract|This article explains how to optimise an image edge detection algorithm so that it can be used for "real-time" previewing of video in the camera's viewport. }}



Kiran10182: Kiran10182 - FA template added
2012-05-27T08:50:51Z
Kiran10182 - FA template added

			
			
			
			
		
		← Older revision
		Revision as of 08:50, 27 May 2012
		
Line 1:
Line 1:
  [[Category:Qt]][[Category:Multimedia]][[Category:Symbian]][[Category:MeeGo]][[Category:Code Examples]][[Category:Optimization]][[Category:Graphics]][[Category:Imaging]][[Category:Camera]][[Category:Symbian^3]][[Category:Symbian Anna]][[Category:Nokia Belle]]   [[Category:Qt]][[Category:Multimedia]][[Category:Symbian]][[Category:MeeGo]][[Category:Code Examples]][[Category:Optimization]][[Category:Graphics]][[Category:Imaging]][[Category:Camera]][[Category:Symbian^3]][[Category:Symbian Anna]][[Category:Nokia Belle]]
  + {{FeaturedArticle|timestamp=20120527}}
  {{Abstract|This article explains how to optimise an image edge detection algorithm so that it can be used for "real-time" previewing of video in the camera's viewport. }}   {{Abstract|This article explains how to optimise an image edge detection algorithm so that it can be used for "real-time" previewing of video in the camera's viewport. }}
    



Hamishwillee: Hamishwillee - fix typo
2012-05-17T06:29:35Z
Hamishwillee - fix typo

			
			
			
			
		
		← Older revision
		Revision as of 06:29, 17 May 2012
		
Line 90:
Line 90:
  </code>   </code>
    
− This code will pass 4 bytes to {{Icode|calcLuma()}} function from position (x-1, y-1) because {{Icode|-bytes_per_line = y-1. x}} must be multiplied by 4 because we are working with RGB data and each pixel takes 4 bytes. Again since we are iterating over x as well instead of multiplying by 4 we can calculate next x value by adding 4 (again 4 bytes per pixel) to it. Basically if we want to eliminate using {{Icode|pixel()}} and {{Icode|setPixel()}} functions from our code we should work with image data directly. + This code will pass 4 bytes to {{Icode|calcLuma()}} function from position (x-1, y-1) because {{Icode|-bytes_per_line  &#61; y-1. x}} must be multiplied by 4 because we are working with RGB data and each pixel takes 4 bytes. Again since we are iterating over x as well instead of multiplying by 4 we can calculate next x value by adding 4 (again 4 bytes per pixel) to it. Basically if we want to eliminate using {{Icode|pixel()}} and {{Icode|setPixel()}} functions from our code we should work with image data directly.
    
  The next inefficient thing in our code is that we are recalculating same luma (brightness) values much more times than necessary. E.g. we are calculating luma for point (3, 3) when we are calculating gradient magnitude for all 8 points around this point). Solution to this is to calculate luma points only for 3 lines that are currently relevant to us for first line. For subsequent lines we only have to calculate next line. E.g.: let's say we are working in line 1 and already know luma points for line 0, 1 and 2:      The next inefficient thing in our code is that we are recalculating same luma (brightness) values much more times than necessary. E.g. we are calculating luma for point (3, 3) when we are calculating gradient magnitude for all 8 points around this point). Solution to this is to calculate luma points only for 3 lines that are currently relevant to us for first line. For subsequent lines we only have to calculate next line. E.g.: let's say we are working in line 1 and already know luma points for line 0, 1 and 2:   



Hamishwillee: Hamishwillee - Minor subedit
2012-05-17T06:27:11Z
Hamishwillee - Minor subedit

			
			
			
			
		
		← Older revision
		Revision as of 06:27, 17 May 2012
		
Line 1:
Line 1:
− [[Category:Qt]][[Category:Multimedia]][[Category:Symbian]][[Category:MeeGo]][[Category:Code Examples]] + [[Category:Qt]][[Category:Multimedia]][[Category:Symbian]][[Category:MeeGo]][[Category:Code Examples]][[Category:Optimization]][[Category:Graphics]][[Category:Imaging]][[Category:Camera]][[Category:Symbian^3]][[Category:Symbian Anna]][[Category:Nokia Belle]]
− {{Abstract|This article explains how to detect edges in real-time and display result in camera's viewport. }} + {{Abstract|This article explains how to optimise an image edge detection algorithm so that it can be used for "real-time" previewing of video in the camera's viewport. }}
    
  {{Note|This is an entry in the [[PureView Imaging Competition 2012Q2]]}}   {{Note|This is an entry in the [[PureView Imaging Competition 2012Q2]]}}
Line 29:
Line 29:
  == Introduction ==   == Introduction ==
    
− It is quite easy to write image editing algorithms using Qt and you can write Instragram like application quite fast (see here [[Image editing techniques and algorithms using Qt]] for some samples). Now if you try to use the very same algorithms in real-time (while displaying in viewport) you will notice that view in camera's viewport is displayed with some delay (e.g. moving object will be displayed only after some seconds). Here I will try to explain how to optimize edge detection algorithm for performance and you will be able to apply same techniques for other algorithms. + Image editing algorithms that take several seconds to complete are acceptable for Instagram-like static image editing, where quality is more important than speed (see [[Image editing techniques and algorithms using Qt]] for examples). However these same algorithms are not suitable for real-time usage (e.g. display in the camera's viewport) as they would result in visibly poor frame rates.  
  +  
  + This article explains how to optimize an edge detection algorithm for calculation speed (possibly sacrificing some level of "quality") so that it can be applied to a video feed in real-time. The hope is that you will be able to apply same techniques for optimising other algorithms.
    
  == Camera viewport technical details ==   == Camera viewport technical details ==
    
− Before starting to work let's overview how we should handle Camera in Qt in order to manipulate viewport. For this task we will need to use [http://doc.qt.nokia.com/qtmobility/qabstractvideosurface.html QAbstractVideoSurface]. You have to subclass this class and implement some specific methods. In present() method you get frame data that you can convert to image (QImage class) and draw where you want to using painter (QPainter class). Please note that where is problem in Meego with frame data and it is covered in [[MeeGo Camera VideoSurface manipulation]] (we will return to MeeGo in this article as well). + Before starting to work let's overview how we should handle Camera in Qt in order to manipulate viewport. For this task we will need to use {{Qapiname|QAbstractVideoSurface}}. You have to subclass this class and implement some specific methods. In {{Icode|present()}} method you get frame data that you can convert to image ({{Qapiname|QImage}} class) and draw where you want to using painter ({{Qapiname|QPainter}} class). Please note that there is a problem in Meego with frame data; this is covered in [[MeeGo Camera VideoSurface manipulation]] (we will return to MeeGo in this article as well).
    
  == Edge detection optimization ==   == Edge detection optimization ==
    
− Let's say here is our edge detection algorithm ([http://en.wikipedia.org/wiki/Sobel_operator Sobel operator]) for RGB image (written on purpose to be completely inefficient): + Below is an implementation of an edge detection algorithm ([http://en.wikipedia.org/wiki/Sobel_operator Sobel operator]) for RGB image. The implementation has purposefully been written to be inefficient so we can demonstrate how it can be improved.
    
  <code cpp>   <code cpp>
Line 80:
Line 82:
  This code will work but it is really slow and inefficient. So let's see what we could do better.   This code will work but it is really slow and inefficient. So let's see what we could do better.
    
− At first we shouldn't use pixel() and setPixel() functions. They are inefficient because multiplication is used to calculate position of pixel - internally it most probably look like this: y * bytes_per_line + x * bytes_per_pixel. It is much better to use bits() and scanLine() functions to get position of all image or position of line in memory respectively. In this case we will use bits() function to get position of first line and will get address of next line by adding bytesPerLine() to previous line (notice that we are iterating over lines(y) in our algorithm). This way we can replace image.pixel(x,y) functions with something like this: + The first problem is that we shouldn't use {{Icode|pixel()}} and {{Icode|setPixel()}} functions. They are inefficient because multiplication is used to calculate position of pixel - internally it most probably look like this: {{Icode|y * bytes_per_line + x * bytes_per_pixel}}. It is much better to use {{Icode|bits()}} and {{Icode|scanLine()}} functions to get position of all image or position of line in memory respectively. In this case we will use {{Icode|bits()}} function to get position of first line and will get address of next line by adding {{Icode|bytesPerLine()}} to previous line (notice that we are iterating over {{Icode|lines(y)}} in our algorithm). This way we can replace {{Icode|image.pixel(x,y)}} functions with something like this:
    
− <code> + <code cpp>
  uchar* lineAddress = image.bits();   uchar* lineAddress = image.bits();
  ....   ....
Line 88:
Line 90:
  </code>   </code>
    
− This code will pass 4 bytes to calcLuma function from position (x-1, y-1) because -bytes_per_line = y-1. x must be multiplied by 4 because we are working with RGB data and each pixel takes 4 bytes. Again since we are iterating over x as well instead of multiplying by 4 we can calculate next x value by adding 4 (again 4 bytes per pixel) to it. Basically if we want to eliminate using pixel() and setPixel() functions from our code we should work with image data directly. + This code will pass 4 bytes to {{Icode|calcLuma()}} function from position (x-1, y-1) because {{Icode|-bytes_per_line = y-1. x}} must be multiplied by 4 because we are working with RGB data and each pixel takes 4 bytes. Again since we are iterating over x as well instead of multiplying by 4 we can calculate next x value by adding 4 (again 4 bytes per pixel) to it. Basically if we want to eliminate using {{Icode|pixel()}} and {{Icode|setPixel()}} functions from our code we should work with image data directly.
    
− Next inefficient thing in our code is that we are recalculating same luma (brightness) values much more times than necessary. E.g. we are calculating luma for point (3, 3) when we are calculating gradient magnitude for all 8 points around this point). Solution to this is to calculate luma points only for 3 lines that are currently relevant to us for first line. For subsequent lines we only have to calculate next line. E.g.: let's say we are working in line 1 and already know luma points for line 0, 1 and 2:    + The next inefficient thing in our code is that we are recalculating same luma (brightness) values much more times than necessary. E.g. we are calculating luma for point (3, 3) when we are calculating gradient magnitude for all 8 points around this point). Solution to this is to calculate luma points only for 3 lines that are currently relevant to us for first line. For subsequent lines we only have to calculate next line. E.g.: let's say we are working in line 1 and already know luma points for line 0, 1 and 2:   
− <code> + <code text>
  0 . . . . . <- known luma points   0 . . . . . <- known luma points
  1 . . . . . <- known luma points   1 . . . . . <- known luma points
Line 106:
Line 108:
  Note: In MeeGo Harmattan we have image data with luma already and it is much more efficient to use that data directly. In code sample that is attached to this article luma data is used directly in MeeGo Harmattan case.   Note: In MeeGo Harmattan we have image data with luma already and it is much more efficient to use that data directly. In code sample that is attached to this article luma data is used directly in MeeGo Harmattan case.
    
− The last thing to solve is square root calculation - it is really expensive operation. Again we can optimize by precalculating values here: sqrt(x*x+y*y) will always be more than 255 when x or y is more than 255. In such case we need to create table of size 256x256 and precalculate square roots. Try using sqrt (qSqrt() function) instead of precalculated values and you will notice that view is lagging from about 0.5 to 2 seconds (depends on your phone's CPU). Here is MeeGo Harmattan implementation for precalculating square roots and using them: + The last thing to solve is square root calculation - it is really expensive operation. Again we can optimize by precalculating values here: sqrt(x*x+y*y) will always be more than 255 when x or y is more than 255. In such case we need to create table of size 256x256 and precalculate square roots. Try using sqrt ({{Icode|qSqrt()}} function) instead of precalculated values and you will notice that view is lagging from about 0.5 to 2 seconds (depends on your phone's CPU). Here is MeeGo Harmattan implementation for precalculating square roots and using them:
    
  <code cpp>   <code cpp>




Chintandave er: Chintandave er - moved note for pureview contest on top
2012-05-16T19:34:22Z
Chintandave er - moved note for pureview contest on top

			
			
			
			
		
		← Older revision
		Revision as of 19:34, 16 May 2012
		
Line 1:
Line 1:
  [[Category:Qt]][[Category:Multimedia]][[Category:Symbian]][[Category:MeeGo]][[Category:Code Examples]]   [[Category:Qt]][[Category:Multimedia]][[Category:Symbian]][[Category:MeeGo]][[Category:Code Examples]]
  {{Abstract|This article explains how to detect edges in real-time and display result in camera's viewport. }}   {{Abstract|This article explains how to detect edges in real-time and display result in camera's viewport. }}
  + 
  + {{Note|This is an entry in the [[PureView Imaging Competition 2012Q2]]}}
    
  {{ArticleMetaData <!-- v1.2 -->   {{ArticleMetaData <!-- v1.2 -->
Line 177:
Line 179:
  == Summary ==   == Summary ==
    
− In this article I have demonstrated how to optimise algorithm (that uses complex calculations) for real-time image processing and displaying from camera.   + In this article I have demonstrated how to optimise algorithm (that uses complex calculations) for real-time image processing and displaying from camera.
−   + 
− {{Note|This is an entry in the [[PureView Imaging Competition 2012Q2]]}} + 




Hamishwillee: Hamishwillee - Bot update - Fix metadata etc
2012-05-16T04:06:35Z
Hamishwillee - Bot update - Fix metadata etc

			
			
			
			
		
		← Older revision
		Revision as of 04:06, 16 May 2012
		
Line 9:
Line 9:
  |platform= Symbian^3 and later, Meego   |platform= Symbian^3 and later, Meego
  |devicecompatability= All Symbian^3 and later, All Meego   |devicecompatability= All Symbian^3 and later, All Meego
− |dependencies= <!-- Any other/external dependencies e.g.: Google Maps Api v1.0 -->   + |dependencies= <!-- Any other/external dependencies e.g.: Google Maps Api v1.0 -->
− |signing=Self-Signed + |signing= Self-Signed
  |capabilities= UserEnvironment   |capabilities= UserEnvironment
  |keywords= QCamera, QAbstractVideoSurface   |keywords= QCamera, QAbstractVideoSurface
  |language= <!-- Language category code for non-English topics - e.g. Lang-Chinese -->   |language= <!-- Language category code for non-English topics - e.g. Lang-Chinese -->
  |translated-by= <!-- [[User:XXXX]] -->   |translated-by= <!-- [[User:XXXX]] -->
− |translated-from-title= <!-- Title only -->   + |translated-from-title= <!-- Title only -->
  |translated-from-id= <!-- Id of translated revision -->   |translated-from-id= <!-- Id of translated revision -->
− |review-by=<!-- After re-review: [[User:username]] --> + |review-by= <!-- After re-review: [[User:username]] -->
  |review-timestamp= <!-- After re-review: YYYYMMDD -->   |review-timestamp= <!-- After re-review: YYYYMMDD -->
  |update-by= <!-- After significant update: [[User:username]]-->   |update-by= <!-- After significant update: [[User:username]]-->
  |update-timestamp= <!-- After significant update: YYYYMMDD -->   |update-timestamp= <!-- After significant update: YYYYMMDD -->
  |creationdate= 20120512   |creationdate= 20120512
− |author=[[User:daliusd]] + |author= [[User:daliusd]]
  }}   }}
    
Line 55:
Line 55:
       int lxm1ym0 = calcLuma(image.pixel(x-1, y  ));        int lxm1ym0 = calcLuma(image.pixel(x-1, y  ));
       int lxm1yp1 = calcLuma(image.pixel(x-1, y+1));        int lxm1yp1 = calcLuma(image.pixel(x-1, y+1));
−      int lxm0ym1 = calcLuma(image.pixel(x  , y-1)); +      int lxm0ym1 = calcLuma(image.pixel(x, y-1));
−      int lxm0yp1 = calcLuma(image.pixel(x  , y+1)); +      int lxm0yp1 = calcLuma(image.pixel(x, y+1));
       int lxp1ym1 = calcLuma(image.pixel(x+1, y-1));        int lxp1ym1 = calcLuma(image.pixel(x+1, y-1));
       int lxp1ym0 = calcLuma(image.pixel(x+1, y-1));        int lxp1ym0 = calcLuma(image.pixel(x+1, y-1));



Daliusd: Daliusd - /* Summary */
2012-05-12T19:58:05Z
Daliusd - - Summary

			
			
			
			
		
		← Older revision
		Revision as of 19:58, 12 May 2012
		
Line 177:
Line 177:
  == Summary ==   == Summary ==
    
− In this article I have demonstrated how to optimize algorithm that uses complex calculations for real-time image processing and displaying from camera.   + In this article I have demonstrated how to optimise algorithm (that uses complex calculations) for real-time image processing and displaying from camera.  
    
  {{Note|This is an entry in the [[PureView Imaging Competition 2012Q2]]}}   {{Note|This is an entry in the [[PureView Imaging Competition 2012Q2]]}}




Daliusd: Daliusd -
2012-05-12T19:45:16Z
Daliusd -
New page
[[Category:Qt]][[Category:Multimedia]][[Category:Symbian]][[Category:MeeGo]][[Category:Code Examples]]

{{Abstract|This article explains how to detect edges in real-time and display result in camera's viewport. }}



{{ArticleMetaData <!-- v1.2 -->

|sourcecode= [[Media:Camera edge 2.zip]]

|installfile= <!-- Link to installation file (e.g. [[Media:The Installation File.sis]]) -->

|devices= Nokia N8, Nokia N950

|sdk= Qt SDK 1.2.1

|platform= Symbian^3 and later, Meego

|devicecompatability= All Symbian^3 and later, All Meego

|dependencies= <!-- Any other/external dependencies e.g.: Google Maps Api v1.0 --> 

|signing=Self-Signed

|capabilities= UserEnvironment

|keywords= QCamera, QAbstractVideoSurface

|language= <!-- Language category code for non-English topics - e.g. Lang-Chinese -->

|translated-by= <!-- [[User:XXXX]] -->

|translated-from-title= <!-- Title only --> 

|translated-from-id= <!-- Id of translated revision -->

|review-by=<!-- After re-review: [[User:username]] -->

|review-timestamp= <!-- After re-review: YYYYMMDD -->

|update-by= <!-- After significant update: [[User:username]]-->

|update-timestamp= <!-- After significant update: YYYYMMDD -->

|creationdate= 20120512

|author=[[User:daliusd]]

}}



== Introduction ==



It is quite easy to write image editing algorithms using Qt and you can write Instragram like application quite fast (see here [[Image editing techniques and algorithms using Qt]] for some samples). Now if you try to use the very same algorithms in real-time (while displaying in viewport) you will notice that view in camera's viewport is displayed with some delay (e.g. moving object will be displayed only after some seconds). Here I will try to explain how to optimize edge detection algorithm for performance and you will be able to apply same techniques for other algorithms.



== Camera viewport technical details ==



Before starting to work let's overview how we should handle Camera in Qt in order to manipulate viewport. For this task we will need to use [http://doc.qt.nokia.com/qtmobility/qabstractvideosurface.html QAbstractVideoSurface]. You have to subclass this class and implement some specific methods. In present() method you get frame data that you can convert to image (QImage class) and draw where you want to using painter (QPainter class). Please note that where is problem in Meego with frame data and it is covered in [[MeeGo Camera VideoSurface manipulation]] (we will return to MeeGo in this article as well).



== Edge detection optimization ==



Let's say here is our edge detection algorithm ([http://en.wikipedia.org/wiki/Sobel_operator Sobel operator]) for RGB image (written on purpose to be completely inefficient):



<code cpp>

function calcLuma(QRgb val)

{

    int luma = (int)(0.2126 * (val >> 16 & 0xff) + 0.7152 * (val >> 8 & 0xff) + (0.0722 * (val & 0xff)));

    return luma

}



...



QImage newImage = QImage(image.width(), image.height(), QImage::Format_RGB32)



for (int y = 1; y < image.height()-1; y++)

    for (int x = 1; x < image.width()-1; x++)

    {

    // calculate luma (brightness) for points around this one

    int lxm1ym1 = calcLuma(image.pixel(x-1, y-1));

    int lxm1ym0 = calcLuma(image.pixel(x-1, y  ));

    int lxm1yp1 = calcLuma(image.pixel(x-1, y+1));

    int lxm0ym1 = calcLuma(image.pixel(x  , y-1));

    int lxm0yp1 = calcLuma(image.pixel(x  , y+1));

    int lxp1ym1 = calcLuma(image.pixel(x+1, y-1));

    int lxp1ym0 = calcLuma(image.pixel(x+1, y-1));

    int lxp1yp1 = calcLuma(image.pixel(x+1, y-1));



    // calculate gradients

    int dx = - lxm1ym1 - lxm1ym0 * 2 - lxm1yp1 + lxp1ym1 + lxp1ym0 * 2 + lxp1yp1;

    int dy = - lxm1ym1 - lxm0ym1 * 2 - lxp1ym1 + lxm1yp1 + lxp0ym1 * 2 + lxp1yp1;





    // calculate gradient magnitude

    int mag = qSqrt(dx*dx+dy*dy);

    if (mag > 255)

        mag = 255;



    // set pixel

    newImage.setPixel(x, y, mag + mag << 8 + mag << 16);

    }

</code>



This code will work but it is really slow and inefficient. So let's see what we could do better.



At first we shouldn't use pixel() and setPixel() functions. They are inefficient because multiplication is used to calculate position of pixel - internally it most probably look like this: y * bytes_per_line + x * bytes_per_pixel. It is much better to use bits() and scanLine() functions to get position of all image or position of line in memory respectively. In this case we will use bits() function to get position of first line and will get address of next line by adding bytesPerLine() to previous line (notice that we are iterating over lines(y) in our algorithm). This way we can replace image.pixel(x,y) functions with something like this:



<code>

uchar* lineAddress = image.bits();

....

int lxm1ym1 = calcLuma((int)*(lineAddress - bytes_per_line + (x-1) * 4));

</code>



This code will pass 4 bytes to calcLuma function from position (x-1, y-1) because -bytes_per_line = y-1. x must be multiplied by 4 because we are working with RGB data and each pixel takes 4 bytes. Again since we are iterating over x as well instead of multiplying by 4 we can calculate next x value by adding 4 (again 4 bytes per pixel) to it. Basically if we want to eliminate using pixel() and setPixel() functions from our code we should work with image data directly.



Next inefficient thing in our code is that we are recalculating same luma (brightness) values much more times than necessary. E.g. we are calculating luma for point (3, 3) when we are calculating gradient magnitude for all 8 points around this point). Solution to this is to calculate luma points only for 3 lines that are currently relevant to us for first line. For subsequent lines we only have to calculate next line. E.g.: let's say we are working in line 1 and already know luma points for line 0, 1 and 2:  

<code>

0 . . . . . <- known luma points

1 . . . . . <- known luma points

2 . . . . . <- known luma points

3 . . . . . <- unknown luma points

</code>



Now when we need to calculate gradient magnitudes for points in line 2 we just reuse luma points from lines 1 and 2 and only have to calculate luma points in line 3.



Here we can make another optimization with memory as well (we should save memory usage in mobile devices if we can and if it doesn't hurt performance). Since we are calculating luma points for lines around current line it is actually safe to write on top of current image. This way we don't need to create new image in memory and will save about 1Mb of memory.



Next thing to optimize is luma calculation formula: Y = 0.2126 * R + 0.7152 * G + 0.0722 * B. First problem with this formula is that it uses real numbers and real numbers arithmetics is slower on computers than integer arithmetics. Therefore we change our formula in this way: Y = (0.2126 * 256 * R + 0.7152 * 256 * G + 0.0722 * 256 * B) / 256 = (54 * R + 183 * G + 18 * B) >> 8 - shift operation is faster than division operation on binary CPU what are majorities of CPUs nowadays and we now have formula that deals with integer numbers. And we can optimise this even more: R, G and B values are from range 0 to 255 therefore we can precalculate multiplication operations into arrays and our formula will be simple as (lumaR[R] + lumaG[G] + lumaB[B]) >> 8.



Note: In MeeGo Harmattan we have image data with luma already and it is much more efficient to use that data directly. In code sample that is attached to this article luma data is used directly in MeeGo Harmattan case.



The last thing to solve is square root calculation - it is really expensive operation. Again we can optimize by precalculating values here: sqrt(x*x+y*y) will always be more than 255 when x or y is more than 255. In such case we need to create table of size 256x256 and precalculate square roots. Try using sqrt (qSqrt() function) instead of precalculated values and you will notice that view is lagging from about 0.5 to 2 seconds (depends on your phone's CPU). Here is MeeGo Harmattan implementation for precalculating square roots and using them:



<code cpp>

    for (int y = 0; y < 255; y++)

        for (int x = 0; x < y; x++)

            {

            int val = (int)qSqrt(x*x+y*y);

            val = val > 255 ? 255 : val;

            sqrt_table[x][y] = val;

            sqrt_table[y][x] = val;

            }

    ....





    unsigned char *dst = m_bits + m_width * 4;

    const unsigned char *src = source.bits() + m_width * 2;





    for (int y = 1; y < m_height-1; ++y) {

        unsigned char *d_x = dst + 4;

        const unsigned char *s_x = src + 2 + 1;

        dst = dst + m_width * 4; // four bytes per pixel

        src = src + m_width * 2; // two bytes per pixel



        for (int x = 1; x < m_width-1; ++x)

        {

            int gx = qAbs(-(*(s_x-m_width*2-2)) - *(s_x-2)*2 - *(s_x+m_width*2-2) + *(s_x-m_width*2+2) + *(s_x+2)*2 + *(s_x+m_width*2+2));

            int gy = qAbs(-(*(s_x-m_width*2-2)) - *(s_x-m_width*2)*2 - *(s_x-m_width*2-2) + *(s_x+m_width*2-2) + *(s_x+m_width*2)*2 + *(s_x+m_width*2+2));



            int g;

            // Try using this instead of sqrt_table to see performance penalty

            // g = (int)qSqrt(gx*gx+gy*gy);

            // g = (g > 255 ? 255 : g);



            if (gx > 255 || gy > 255)

                g = 255;

            else

                g = sqrt_table[gx][gy];



            *d_x = g;

            *(d_x+1) = g;

            *(d_x+2) = g;

            *(d_x+3) = 0;



            d_x+=4;

            s_x+=2;

        }

    }



</code>



That's actually it: we have eliminated square root extraction and all multiplication operations from our algorithm and it now can be used in real-time. Download sample application from here to see complete algorithm: [[Media:Camera edge 2.zip]]



Here is what you might see using this app:



[[File:View edge.png]]



And here are videos of this application in action. On Nokia N950:



{{#ev:youtube|C3x4OqaBiMY}}





On Nokia N8:



{{#ev:youtube|ZaZrnS7fG7I}}





Nokia N950 screencast to show details that are not visible in filmed videos:



{{#ev:youtube|5FvNBoh1VEQ}}



== Summary ==



In this article I have demonstrated how to optimize algorithm that uses complex calculations for real-time image processing and displaying from camera. 



{{Note|This is an entry in the [[PureView Imaging Competition 2012Q2]]}}

← Older revision		Revision as of 08:50, 27 May 2012
Line 1:		Line 1:
	[[Category:Qt]][[Category:Multimedia]][[Category:Symbian]][[Category:MeeGo]][[Category:Code Examples]][[Category:Optimization]][[Category:Graphics]][[Category:Imaging]][[Category:Camera]][[Category:Symbian^3]][[Category:Symbian Anna]][[Category:Nokia Belle]]		[[Category:Qt]][[Category:Multimedia]][[Category:Symbian]][[Category:MeeGo]][[Category:Code Examples]][[Category:Optimization]][[Category:Graphics]][[Category:Imaging]][[Category:Camera]][[Category:Symbian^3]][[Category:Symbian Anna]][[Category:Nokia Belle]]
		+	{{FeaturedArticle\|timestamp=20120527}}
	{{Abstract\|This article explains how to optimise an image edge detection algorithm so that it can be used for "real-time" previewing of video in the camera's viewport. }}		{{Abstract\|This article explains how to optimise an image edge detection algorithm so that it can be used for "real-time" previewing of video in the camera's viewport. }}

Real-time edge detection in camera viewport - Revision history

Hamishwillee: Hamishwillee - Change to use new video player which works with Lumia 920 and other mobile browsers

Hamishwillee: Text replace - "" to ""

Hamishwillee: Text replace - "Category:MeeGo" to "Category:MeeGo Harmattan"

Kiran10182: Kiran10182 - FA template added

Hamishwillee: Hamishwillee - fix typo

Hamishwillee: Hamishwillee - Minor subedit

Chintandave er: Chintandave er - moved note for pureview contest on top

Hamishwillee: Hamishwillee - Bot update - Fix metadata etc

Daliusd: Daliusd - /* Summary */

Daliusd: Daliusd -

Hamishwillee: Text replace - "`" to ""`