elhacker.net cabecera Bienvenido(a), Visitante. Por favor Ingresar o Registrarse
¿Perdiste tu email de activación?.

 

 


Tema destacado: Guía actualizada para evitar que un ransomware ataque tu empresa


+  Foro de elhacker.net
|-+  Programación
| |-+  Programación C/C++ (Moderadores: Eternal Idol, Littlehorse, K-YreX)
| | |-+  Algoritmo de detección de bordes de Canny ( C++ Manejo básico de imágines )
0 Usuarios y 1 Visitante están viendo este tema.
Páginas: [1] Ir Abajo Respuesta Imprimir
Autor Tema: Algoritmo de detección de bordes de Canny ( C++ Manejo básico de imágines )  (Leído 7,231 veces)
razormta

Desconectado Desconectado

Mensajes: 18


Ver Perfil
Algoritmo de detección de bordes de Canny ( C++ Manejo básico de imágines )
« en: 18 Abril 2014, 01:55 am »

Hola, hace un par de meses realize un post para pedir que me ayudaran a leer una imagen haha, lo logré hacer por mi cuenta y he aprendido bastante sobre el manejo básico de imagenes.

El siguiente post lo realizo porque me molesta que haya tan pocos artículos en español sobre este tema. Lo que pondré es un algoritmo de detección de bordes de una imagen en c++, lo acabo de terminar xd

Lo pondré luego explicaré cada parte.

Código
  1.  
  2. struct cannyAlgorithm
  3.    {
  4.        unsigned char * image;
  5.  
  6.        unsigned width;
  7.        unsigned height;
  8.        unsigned size;
  9.        unsigned bpp;
  10.  
  11.        short * Gx;
  12.        short * Gy;
  13.  
  14.        short * Direction;
  15.  
  16.        double * Magnitude;
  17.  
  18.        cannyAlgorithm( unsigned char * data, unsigned imgw, unsigned imgh, unsigned bitsperpixel )
  19.        {
  20.            width   = imgw;
  21.            height  = imgh;
  22.  
  23.            size = width* height;
  24.  
  25.            bpp = bitsperpixel;
  26.  
  27.            Gx = new short[ size ];
  28.            Gy = new short[ size ];
  29.  
  30.            Direction = new short[ size ];
  31.  
  32.            Magnitude = new double[ size ];
  33.  
  34.            image = new unsigned char[ size* bpp ];
  35.            memcpy( image, data, size* bpp );
  36.        }
  37.        ~cannyAlgorithm( void )
  38.        {
  39.            delete[] Gx;
  40.            delete[] Gy;
  41.            delete[] Direction;
  42.            delete[] Magnitude;
  43.        }
  44.        int max( int a, int b )
  45.        {
  46.            int c = a > b ? a : b;
  47.            return c;
  48.        }
  49.        int min( int a, int b )
  50.        {
  51.            int c = a < b ? a : b;
  52.            return c;
  53.        }
  54.        short getAngle( double X, double Y )
  55.        {
  56.            short Angle;
  57.  
  58.            if( X* Y > 0 )  // Quadrant 1 or 3
  59.            {
  60.                if( abs( X ) >= abs( Y ) )
  61.                    Angle = 0;
  62.                else
  63.                    Angle = 180;
  64.            }
  65.            else            // Quadrant 2 or 4
  66.            {
  67.                if( abs(X) >= abs(Y) )
  68.                    Angle = 90;
  69.                else
  70.                    Angle = 270;
  71.            }
  72.  
  73.            return( Angle );
  74.        }
  75.        double hypotenuse( double a, double b )
  76.        {
  77.            double h = sqrt( a*a + b*b );
  78.            return(h);
  79.        }
  80.        bool isLocalMax( unsigned offset )
  81.        {
  82.            unsigned bottom     = max(offset - width, 0);
  83.            unsigned top        = min(offset + width, size);
  84.            unsigned left       = max(offset - 1, 0);
  85.            unsigned right      = min(offset + 1, size);
  86.            unsigned bottomLeft = max(bottom - 1, 0);
  87.            unsigned bottomRight= min(bottom + 1, size);
  88.            unsigned topLeft    = max(top - 1, 0);
  89.            unsigned topRight   = min(top + 1, size);
  90.  
  91.            double thisPoint = 0.0;
  92.            double mag[2]    = { 0.0 };
  93.  
  94.            switch( Direction[offset] )
  95.            {
  96.                case 0:
  97.                {
  98.                                /*   90
  99.                                       *
  100.                                       |******
  101.                                       |******
  102.                                 -------------* 0
  103.                                       |
  104.                                       |
  105.  
  106.                                 */
  107.                    thisPoint = abs( Gx[offset]* Magnitude[offset] );
  108.  
  109.                    mag[0] = abs( Gy[offset]* Magnitude[topRight  ] + ( Gx[offset] - Gy[offset] )* Magnitude[right] );
  110.                    mag[1] = abs( Gy[offset]* Magnitude[bottomLeft] + ( Gx[offset] - Gy[offset] )* Magnitude[left ] );
  111.                    }break;
  112.  
  113.                case 90:
  114.                {
  115.                                /*
  116.                                       90
  117.                                       *
  118.                                  *****|
  119.                                  *****|
  120.                             180 *-------------
  121.                                       |
  122.                                       |
  123.                                 */
  124.                    thisPoint = abs(Gx[offset]* Magnitude[offset] );
  125.  
  126.                    mag[0] = abs( Gy[offset]* Magnitude[bottomRight] - ( Gx[offset] + Gy[offset])* Magnitude[right] );
  127.                    mag[1] = abs( Gy[offset]* Magnitude[topLeft    ] - ( Gx[offset] + Gy[offset])* Magnitude[left ] );
  128.                }break;
  129.  
  130.                case 180:
  131.                {
  132.                                /*
  133.                                       |
  134.                                       |
  135.                             180 *-------------
  136.                                 ******|
  137.                                 ******|
  138.                                       *
  139.                                      270
  140.                                 */
  141.                    thisPoint = abs( Gy[offset]* Magnitude[offset] );
  142.  
  143.                    mag[0] = abs( Gx[offset]* Magnitude[topRight  ] + ( Gy[offset] - Gx[offset] )* Magnitude[top   ] );
  144.                    mag[1] = abs( Gx[offset]* Magnitude[bottomLeft] + ( Gy[offset] - Gx[offset] )* Magnitude[bottom] );
  145.                }break;
  146.  
  147.                case 270:
  148.                {
  149.                                /*
  150.                                       |
  151.                                       |
  152.                                 -------------* 0
  153.                                       |*******
  154.                                       |*******
  155.                                       *
  156.                                      270
  157.                                 */
  158.                    thisPoint = abs( Gy[offset]* Magnitude[offset] );
  159.  
  160.                    mag[0] = abs( Gx[offset]* Magnitude[bottomRight] - ( Gy[offset] + Gx[offset] )* Magnitude[bottom] );
  161.                    mag[1] = abs( Gx[offset]* Magnitude[topLeft    ] - ( Gy[offset] + Gx[offset] )* Magnitude[top   ] );
  162.                }break;
  163.  
  164.                default:
  165.                    break;
  166.            }
  167.  
  168.            if( thisPoint >= mag[0] && thisPoint >= mag[1] )
  169.                return( true );
  170.            return( false );
  171.        }
  172.        void grayScaleCompress( void )
  173.        {
  174.            unsigned char * compressed = new unsigned char[ size ];
  175.  
  176.            for( unsigned offset = 0; offset < size; offset++ )
  177.                compressed[offset] = image[offset* bpp];
  178.  
  179.            delete[] image;
  180.            image = new unsigned char[ size ];
  181.            memcpy( image, compressed, size );
  182.  
  183.            delete[] compressed;
  184.        }
  185.        void continuousTracing( unsigned offset, unsigned char * in, unsigned char * out, unsigned thresholding )
  186.        {
  187.            /*
  188.             The concept is sample:
  189.             I found a possible edge and I will follow this edge until its end.
  190.             Test 8 neighboring pixels and if someone is higher than thresholding then
  191.             that pixel will be another edge and I will follow it.
  192.  
  193.             This process is repeated until the value of the current pixel tested is null.
  194.             */
  195.            const unsigned edge = 255;
  196.  
  197.            unsigned dir[2];
  198.            dir[0] = width;      // Top - Bottom
  199.            dir[1] = 1;          // Left - Right
  200.  
  201.            unsigned top = min( offset + dir[0], size );
  202.            if( in[top] >= thresholding )
  203.                do
  204.                {
  205.                    if( !out[top] )
  206.                    {
  207.                        out[top] = edge;
  208.                        continuousTracing( top, in, out, thresholding );
  209.                    }
  210.                    else
  211.                        break;
  212.  
  213.                    top += dir[0];
  214.  
  215.                    if( top > size )
  216.                        break;
  217.  
  218.                }while( in[top] >= thresholding );
  219.  
  220.            unsigned bottom = max( offset - dir[0], 0 );
  221.            if( in[bottom >= thresholding] )
  222.                do
  223.                {
  224.                    if( !out[bottom] )
  225.                    {
  226.                        out[bottom] = edge;
  227.                        continuousTracing( bottom, in, out, thresholding );
  228.                    }
  229.                    else
  230.                        break;
  231.  
  232.                    bottom -= dir[0];
  233.  
  234.                    if( bottom < 0 )
  235.                        break;
  236.  
  237.                }while( in[bottom] >= thresholding );
  238.  
  239.            unsigned right = min( offset + dir[1], size );
  240.            if( in[right] >= thresholding )
  241.                do
  242.                {
  243.                    if( !out[right] )
  244.                    {
  245.                        out[right] = edge;
  246.                        continuousTracing( right, in, out, thresholding );
  247.                    }
  248.                    else
  249.                        break;
  250.  
  251.                    right += dir[1];
  252.  
  253.                    if( right > size )
  254.                        break;
  255.  
  256.                }while( in[right] >= thresholding );
  257.  
  258.            unsigned left = max( offset - dir[1], 0 );
  259.            if( in[left] >= thresholding )
  260.                do
  261.                {
  262.                    if( !out[left] )
  263.                    {
  264.                        out[left] = edge;
  265.                        continuousTracing( left, in, out, thresholding );
  266.                    }
  267.                    else
  268.                        break;
  269.  
  270.                    left -= dir[1];
  271.  
  272.                    if( left < 0 )
  273.                        break;
  274.  
  275.                }while( in[left] >= thresholding );
  276.  
  277.            unsigned topRight = min( offset + dir[0] + dir[1], size );
  278.            if( in[topRight] >= thresholding )
  279.                do
  280.                {
  281.                    if( !out[topRight] )
  282.                    {
  283.                        out[topRight] = edge;
  284.                        continuousTracing( left, in, out, thresholding );
  285.                    }
  286.                    else
  287.                        break;
  288.  
  289.                    topRight += dir[0] + dir[1];
  290.  
  291.                    if( topRight > size )
  292.                        break;
  293.  
  294.                }while( in[topRight] >= thresholding );
  295.  
  296.            unsigned bottomLeft = max( offset - dir[0] - dir[1], 0 );
  297.            if( in[bottomLeft] >= thresholding )
  298.                do
  299.                {
  300.                    if( !out[bottomLeft] )
  301.                    {
  302.                        out[bottomLeft] = edge;
  303.                        continuousTracing( bottomLeft, in, out, thresholding );
  304.                    }
  305.                    else
  306.                        break;
  307.  
  308.                    bottomLeft -= dir[0] - dir[1];
  309.  
  310.                    if( bottomLeft < 0 )
  311.                        break;
  312.  
  313.                }while( in[bottomLeft] >= thresholding );
  314.  
  315.            unsigned topLeft = min( offset + dir[0] - dir[1], size );
  316.            if( in[topLeft] >= thresholding )
  317.                do
  318.                {
  319.                    if( !out[topLeft] )
  320.                    {
  321.                        out[topLeft] = edge;
  322.                        continuousTracing( topLeft, in, out, thresholding );
  323.                    }
  324.                    else
  325.                        break;
  326.  
  327.                    topLeft += dir[0] - dir[1];
  328.  
  329.                    if( topLeft > size )
  330.                        break;
  331.  
  332.                }while( in[topLeft] >= thresholding );
  333.  
  334.            unsigned bottomRight = max( offset - dir[0] + dir[1], 0 );
  335.            if( in[bottomRight] >= thresholding )
  336.                do
  337.                {
  338.                    if( !out[bottomRight] )
  339.                    {
  340.                        out[bottomRight] = edge;
  341.                        continuousTracing( bottomRight, in, out, thresholding );
  342.                    }
  343.                    else
  344.                        break;
  345.  
  346.                    bottomRight -= dir[0] + dir[1];
  347.  
  348.                    if( bottomRight < 0 )
  349.                        break;
  350.  
  351.                }while( in[bottomRight] >= thresholding );
  352.  
  353.            /* Works with feedback and not will be an infinite loop cause I am saving the new data into a new image */
  354.        }
  355.        void computeGradients( void )
  356.        {
  357.            // Compute Gradients in X
  358.            for( unsigned y = 0; y < height; y++ )
  359.            {
  360.                unsigned offset = y* width;
  361.  
  362.                Gx[offset] = image[offset + 1] - image[offset];
  363.  
  364.                offset++;
  365.                for( unsigned x = 1; x < width - 1; x++, offset++ )
  366.                    Gx[offset] = image[offset + 1] - image[offset - 1];
  367.  
  368.                Gx[offset] = image[offset] - image[offset - 1];
  369.            }
  370.            // Compute Gradients in Y
  371.            for( unsigned x = 0; x < width; x++ )
  372.            {
  373.                unsigned offset = x;
  374.  
  375.                Gy[offset] = image[offset + width] - image[offset];
  376.  
  377.                offset += width;
  378.                for( unsigned y = 1; y < height - 1; y++, offset += width )
  379.                    Gy[offset] = image[offset + width] - image[offset - width];
  380.  
  381.                Gy[offset] = image[offset] - image[offset - width];
  382.            }
  383.            // Hypotenuse = sqrt(x^2 + y^2)
  384.            for( unsigned y = 0, offset = 0; y < height; y++ )
  385.                for( unsigned x = 0; x < width; x++, offset++ )
  386.                    Magnitude[offset] = hypotenuse( Gx[offset], Gy[offset] );
  387.            // Okay, edges of the image must be null
  388.            for( unsigned x = 0; x < width; x++ )
  389.                Magnitude[x] = 0;
  390.  
  391.            for( unsigned x = 0, offset = width* (height - 1); x < width; x++, offset++ )
  392.                Magnitude[offset] = 0;
  393.  
  394.            for( unsigned y = 0; y < width* height; y += width )
  395.                Magnitude[y] = 0;
  396.  
  397.            for( unsigned y = 0, offset = width - 1; y < width* height; y += width, offset += width)
  398.                Magnitude[offset] = 0;
  399.        }
  400.        void nonMaxSupress( void )
  401.        {
  402.            /* Compute magnitudes direction and save it */
  403.            for( unsigned y = 0, offset = 0; y < height; y++ )
  404.                for( unsigned x = 0; x < width; x++, offset++ )
  405.                    Direction[offset] = getAngle( Gx[offset], Gy[offset] );
  406.            /*
  407.                 The most complicated part:
  408.                 If the pixel is not a local maximum then kill it.
  409.                 How do I know if my point is a local max ?
  410.                 I will compare the current pixel with neighboring pixels in the gradient direction.
  411.                 Remember: Pixel with null magnitude are not candidate to be an edge.
  412.             */
  413.            for( unsigned y = 0, offset = 0; y < height; y++ )
  414.                for( unsigned x = 0; x < width; x++, offset++ )
  415.                {
  416.                    if( Magnitude[offset] && isLocalMax(offset) )
  417.                        image[offset] = Magnitude[offset] > 255 ? 255 : (unsigned char)Magnitude[offset];
  418.                    else
  419.                        image[offset] = 0;
  420.                }
  421.        }
  422.        void hysteresis( float lowScale, float highScale )
  423.        {
  424.            /*
  425.             We need a High value and a Low value, High value will be the edge color.
  426.             All pixels with color higher than ' Hight value ' will be edges
  427.             and we will follow this pixel until another pixel is founded.
  428.             The pixel founded must be a color higher than ' Low value ', if that is the case
  429.             then we will set this pixel like edge, else it will be background ( null ).
  430.             */
  431.  
  432.            lowScale    = lowScale <= 0.0f ? 0.01f : lowScale > 1.0f ? 1.0f : lowScale;
  433.            highScale   = highScale <= 0.0f ? 0.01f : highScale > 1.0f ? 1.0f : highScale;
  434.  
  435.            unsigned char globalMax = 0;
  436.            for( unsigned offset = 0; offset < size; offset++ )
  437.                if( image[offset] > globalMax )
  438.                    globalMax = image[offset];
  439.  
  440.            unsigned highV = globalMax* highScale;
  441.            unsigned lowV = globalMax* lowScale;
  442.  
  443.            unsigned char * finalPic = new unsigned char[ size ];
  444.            memset( finalPic, 0, size );
  445.  
  446.            for( unsigned y = 1,offset = 1; y < height - 1; y++ )
  447.                for( unsigned x = 1; x < width - 1; x++, offset++ )
  448.                    if( image[offset] >= highV && !finalPic[offset] )
  449.                    {
  450.                        finalPic[offset] = 255;
  451.                        continuousTracing( offset, image, finalPic, lowV );
  452.                    }
  453.  
  454.            delete[] image;
  455.            image = new unsigned char[ size ];
  456.            memcpy( image, finalPic, size );
  457.  
  458.            delete[] finalPic;
  459.        }
  460.        void grayScaleDecompress( void )
  461.        {
  462.            size = width* height* bpp;
  463.            unsigned char * decompressed = new unsigned char[ size ];
  464.  
  465.            for( unsigned offset = 0; offset < width* height; offset++ )
  466.                decompressed[offset*bpp + 0] = decompressed[offset* bpp + 1] = decompressed[offset* bpp + 2] = image[offset];
  467.  
  468.            delete[] image;
  469.            image = new unsigned char[ size ];
  470.            memcpy( image, decompressed, size );
  471.  
  472.            delete[] decompressed;
  473.        }
  474.        void AutoEdgeDetection( unsigned char * data, float lowV, float highV )
  475.        {
  476.            grayScaleCompress();
  477.            computeGradients();
  478.            nonMaxSupress();
  479.            hysteresis(lowV, highV);
  480.            grayScaleDecompress();
  481.  
  482.            memcpy( data, image, size );
  483.        }
  484.        unsigned char * get_data( void )
  485.        {
  486.            grayScaleDecompress();
  487.            return( image );
  488.        }
  489.    };
  490.  
  491.  


Lo puse todo en una estructura para que sea más portable y además para que  no dependa de otras librerias añadí funciones como max, min y hypotenuse, creo que solo debe incluir la libreria <cmath> para la funcion abs

Se preguntarán: Okay, tengo el algorithmo, ¿ Ahora qué ?.

fácil, para usarlo deben iniciailizarlo con el ancho y alto de la imagen, la cantidad de bits por pixel( 1 , 2 , 3 o 4 ) y el unsigned char de la data de la imagen, ejemplo:

Código
  1.  
  2.    gaussianBlur(15, 2);
  3.    grayScale();
  4.    cannyAlgorithm cpix( ~self.data, self.width, self.height, self.bpp / 8 );
  5.  
  6.    cpix.AutoEdgeDetection( ~self.data, 0.2f, 0.25f );
  7.  
  8.  

seguire explicando abajo


« Última modificación: 18 Abril 2014, 02:17 am por razormta » En línea

razormta

Desconectado Desconectado

Mensajes: 18


Ver Perfil
Re: Algoritmo de detección de bordes de Canny ( C++ Manejo básico de imágines )
« Respuesta #1 en: 18 Abril 2014, 02:02 am »

Código
  1.    gaussianBlur(15, 2);
  2.    grayScale();
  3.    cannyAlgorithm cpix( ~self.data, self.width, self.height, self.bpp / 8 );
  4.  
  5.    cpix.AutoEdgeDetection( ~self.data, 0.2f, 0.25f );
  6.  

La linea 1 es necesaria y asumo que ya tienen una funcion llamada "gaussian blur" que aplica el algoritmo gaussiano para disminuir el ruido de una imagen, si no la tienen pueden continuar , pero notaran la diferencia.

La linea 2 es necesaria, asumo que ya tienen una funcion llamada "grayscale" que convierta la imagen a escala de grises , el concepto es sencillo , gray = (r + g + b) / 3
r = g = b = gray

la linea 3 es la inicializacion del algoritmo en mi caso ~self.data es el unsigned char, self.width el ancho, self.height el alto, self.bpp / 8 los bits por pixel.

la linea 4 es iniciar la dectecion de bordes , le introduzco el unsigned char de salida , y dos valores decimales que luego explicare el porque los introduje



Código
  1. grayScaleCompress();
  2. computeGradients();
  3. nonMaxSupress();
  4. hysteresis(lowV, highV);
  5. grayScaleDecompress();

Son las  5 fases del algoritmo, sin contar la fase de aplicacion de Gauss, iré explicando una por una  y al final mostrare imagenes de lo que obtuve.

1) Gray scale compresión

La imagen introducida debe tener 1 byte por pixel o superior, y se va a trabajar con una imagen que obligatoriamente debe ser de 1 byte por pixel, para eso se comprime la imagen, para evitar errores, ademas se obtiene un mejor resultado si la imagen esta en escala de grises.

Código
  1.         void grayScaleCompress( void )
  2.        {
  3.            unsigned char * compressed = new unsigned char[ size ];
  4.  
  5.            for( unsigned offset = 0; offset < size; offset++ )
  6.                compressed[offset] = image[offset* bpp];
  7.  
  8.            delete[] image;
  9.            image = new unsigned char[ size ];
  10.            memcpy( image, compressed, size );
  11.  
  12.            delete[] compressed;
  13.        }

Como se ve facilmente, se crea una nueva data con un tamaño de solo ancho x alto y se obliga a la imagen a estar en escala de grises , osea, se convierte a 1 byte por pixel


2) Calcular gradientes

Tuve que leer demasiado ... No soy el mejor en matemáticas , pero se me dan bien y me encuentro con esto. Gradientes ?

Gradientes esta definido como la velocidad con que una función varia.
En nuestro caso estamos trabajando con colores !, es necesario calcular y guardar la velocidad con que en un punto I los colores varian en el eje X y en el eje Y

Código
  1. void computeGradients( void )
  2.        {
  3.            // Compute Gradients in X
  4.            for( unsigned y = 0; y < height; y++ )
  5.            {
  6.                unsigned offset = y* width;
  7.  
  8.                Gx[offset] = image[offset + 1] - image[offset];
  9.  
  10.                offset++;
  11.                for( unsigned x = 1; x < width - 1; x++, offset++ )
  12.                    Gx[offset] = image[offset + 1] - image[offset - 1];
  13.  
  14.                Gx[offset] = image[offset] - image[offset - 1];
  15.            }
  16.            // Compute Gradients in Y
  17.            for( unsigned x = 0; x < width; x++ )
  18.            {
  19.                unsigned offset = x;
  20.  
  21.                Gy[offset] = image[offset + width] - image[offset];
  22.  
  23.                offset += width;
  24.                for( unsigned y = 1; y < height - 1; y++, offset += width )
  25.                    Gy[offset] = image[offset + width] - image[offset - width];
  26.  
  27.                Gy[offset] = image[offset] - image[offset - width];
  28.            }
  29.            // Hypotenuse = sqrt(x^2 + y^2)
  30.            for( unsigned y = 0, offset = 0; y < height; y++ )
  31.                for( unsigned x = 0; x < width; x++, offset++ )
  32.                    Magnitude[offset] = hypotenuse( Gx[offset], Gy[offset] );
  33.            // Okay, edges of the image must be null
  34.            for( unsigned x = 0; x < width; x++ )
  35.                Magnitude[x] = 0;
  36.  
  37.            for( unsigned x = 0, offset = width* (height - 1); x < width; x++, offset++ )
  38.                Magnitude[offset] = 0;
  39.  
  40.            for( unsigned y = 0; y < width* height; y += width )
  41.                Magnitude[y] = 0;
  42.  
  43.            for( unsigned y = 0, offset = width - 1; y < width* height; y += width, offset += width)
  44.                Magnitude[offset] = 0;
  45.        }
  46.  
  47.  

Solo piensen, estan en el centro a su izquierda el color negro, a la derecha el azul, la velocidad con que varian es la resta de ellos dos, calculo entonces esta variacion en todos los puntos I , compruebo la variacion hacendo (I+1) - (I -1), pixel de la derecha - pixel de la izquierda.

Realizo lo mismo con el eje Y, pixel de arriba - pixel de abajo: (I + ancho) - ( I - ancho )


Bien, ahora tengo el array de las variaciones en X y las variaciones en Y ahora calculo la magnitud, que ?? magnitud??

la magnitud de un vector es la distancia entre P1 y P2, la distancia entre el punto de X y el punto de Y , la hipotenusa ! , okay okay, para que hago esto ? porque hago todo esto ?

haha Un borde es facil de detectar porque hay una variacion de colores cuando termina una imagen y comienza otra.
Debemos calcular donde ocurren esas variaciones y hacia donde son más altas



3 ) Supresión de los falsos positivos


Oka, hasta ahora todo parece lógico, fácil de entender. Esta es la parte más  dificil de entender ,por ende dificil de explicar.

Código
  1.          void nonMaxSupress( void )
  2.        {
  3.            /* Compute magnitudes direction and save it */
  4.            for( unsigned y = 0, offset = 0; y < height; y++ )
  5.                for( unsigned x = 0; x < width; x++, offset++ )
  6.                    Direction[offset] = getAngle( Gx[offset], Gy[offset] );
  7.            /*
  8.                 The most complicated part:
  9.                 If the pixel is not a local maximum then kill it.
  10.                 How do I know if my point is a local max ?
  11.                 I will compare the current pixel with neighboring pixels in the gradient direction.
  12.                 Remember: Pixel with null magnitude are not candidate to be an edge.
  13.             */
  14.            for( unsigned y = 0, offset = 0; y < height; y++ )
  15.                for( unsigned x = 0; x < width; x++, offset++ )
  16.                {
  17.                    if( Magnitude[offset] && isLocalMax(offset) )
  18.                        image[offset] = Magnitude[offset] > 255 ? 255 : (unsigned char)Magnitude[offset];
  19.                    else
  20.                        image[offset] = 0;
  21.                }
  22.        }

Primero, si la variacion de colores es positiva en X y la variacion de colores es positiva en Y , eso significa que en el plano cartesiano, los colores varian hacia el primer cuadrante, entre los grados 0 - 90

Calculare hacia que direccion apunta la variacion de colores de cada pixel
eso se nota en el primer ciclo, en el segundo ciclo viene lo bueno...

Si saben programar y pueden manipular este codigo a voluntad e intentan visualizar la imagen como va en  esta fase, tendrian algo como esto


Los bordes son muy gruesos ...y hay demasiados bordes, no pareciera, pero si los hay, si pusieran todos los colores de los bordes actuales en 255, la imagen se pondria toda blanca ... porque no esta listo ?? que es la supresion de los falsos positivos ?

Explicare ...

Mencione que al llegar al borde en una imagen hay un cambio de color porque pasas a otro objeto no ? bueno, si tienes un cubo blanco, y te situas en un pixel, de que color es el pixel de la derecha ( I + 1 ) ? blanco no ? y el pixel de la izquierda ( I - 1 ) ? blanco tambien xd entonces la gradiente cuanto sera ? blanco - blanco = 0 !

oka resulta que no solo la gradiente en X es 0 sino la gradiente en Y tambien es 0, que se obtiene ? cuanto vale la hipotenusa ? ?? 0 ! xd

hipotenusa = sqrt( x*x + y*y )

Magnitud = hipotenusa.

lo que se hizo en la imagen de arriba es setear el color del pixel cuya magnitud sea 0 en negro, oka, pero quedan pixeles con magnitud de 2 3 6, que aun es muy bajo ! ... esos son los falsos positivos, puntos en la imagen que no son bordes pero que no se han eliminado, por eso se realiza este proceso


Entonces, como sabemos que un pixel es un verdadero positivo ? un verdadero borde ? comparamos el pixel con la magnitudes de los pixeles en la direccion del gradiente... no es tan complicado como suena xd

si la variacion de colores de tu pixel apunta hacia el noroeste, lo compararemos con las variaciones de colores de los pixeles del noroeste y del suroeste y si es mayor es un verdadero positivo, o tambien llamado un maximo local , entonces el pixel es un posible borde,sino es background


Código
  1. if( Magnitude[offset] && isLocalMax(offset) )




4 ) Histeresis.

oka, despues de la non maximal suppression tendriamos una imagen con bordes muy delgados, pero no conectados. osea, un borde llega a un punto y no conecta a otro hasta varios pixeles despues, entonces venimos con esta fase del algoritmo de canny que nos dice que debemos introducir dos valores

El primer valor ( High Value ) Es el valor minimo que debe tener el inicio de un borde.

Debemos tener una imagen de salida toda negra, y mirar en la imagen de entrada( nuestra imagen con la nms apilcada ) si el color de un pixel es >= que el high Value, si esto es cierto entonces boom empieza el trazado de un borde

Código
  1. void hysteresis( float lowScale, float highScale )
  2.        {
  3.            /*
  4.             We need a High value and a Low value, High value will be the edge color.
  5.             All pixels with color higher than ' Hight value ' will be edges
  6.             and we will follow this pixel until another pixel is founded.
  7.             The pixel founded must be a color higher than ' Low value ', if that is the case
  8.             then we will set this pixel like edge, else it will be background ( null ).
  9.             */
  10.  
  11.            lowScale    = lowScale <= 0.0f ? 0.01f : lowScale > 1.0f ? 1.0f : lowScale;
  12.            highScale   = highScale <= 0.0f ? 0.01f : highScale > 1.0f ? 1.0f : highScale;
  13.  
  14.            unsigned char globalMax = 0;
  15.            for( unsigned offset = 0; offset < size; offset++ )
  16.                if( image[offset] > globalMax )
  17.                    globalMax = image[offset];
  18.  
  19.            unsigned highV = globalMax* highScale;
  20.            unsigned lowV = globalMax* lowScale;
  21.  
  22.            unsigned char * finalPic = new unsigned char[ size ];
  23.            memset( finalPic, 0, size );
  24.  
  25.            for( unsigned y = 1,offset = 1; y < height - 1; y++ )
  26.                for( unsigned x = 1; x < width - 1; x++, offset++ )
  27.                    if( image[offset] >= highV && !finalPic[offset] )
  28.                    {
  29.                        finalPic[offset] = 255;
  30.                        continuousTracing( offset, image, finalPic, lowV );
  31.                    }
  32.  
  33.            delete[] image;
  34.            image = new unsigned char[ size ];
  35.            memcpy( image, finalPic, size );
  36.  
  37.            delete[] finalPic;
  38.        }
  39.  


Entonces, que es el trazado de un borde ?, imaginate dibujando algo, tu lapiz empieza en un punto X,Y y lo mueves hasta otro punto X,Y dependiendo de lo que quieras dibujar ...

si deseas dibujar una linea recta y vertical, entonces tu lapiz se movera unicamente hacia arriba:

Repeat (X, Y+1) Until Y >= limite de la linea a dibujar.

eso es lo que se hara a continuacion , pero no dibujaremos una linea recta, dibujaremos en diferentes direcciones ! , arriba, abajo, izquierda , derecha , etc ! ... dibujaremos siempre y cuando el pixel sobre el que vayamos a dibujar sea mayor que el Low Value


Código
  1. void continuousTracing( unsigned offset, unsigned char * in, unsigned char * out, unsigned thresholding )
  2.        {
  3.            /*
  4.             The concept is sample:
  5.             I found a possible edge and I will follow this edge until its end.
  6.             Test 8 neighboring pixels and if someone is higher than thresholding then
  7.             that pixel will be another edge and I will follow it.
  8.  
  9.             This process is repeated until the value of the current pixel tested is null.
  10.             */
  11.            const unsigned edge = 255;
  12.  
  13.            unsigned dir[2];
  14.            dir[0] = width;      // Top - Bottom
  15.            dir[1] = 1;          // Left - Right
  16.  
  17.            unsigned top = min( offset + dir[0], size );
  18.            if( in[top] >= thresholding )
  19.                do
  20.                {
  21.                    if( !out[top] )
  22.                    {
  23.                        out[top] = edge;
  24.                        continuousTracing( top, in, out, thresholding );
  25.                    }
  26.                    else
  27.                        break;
  28.  
  29.                    top += dir[0];
  30.  
  31.                    if( top > size )
  32.                        break;
  33.  
  34.                }while( in[top] >= thresholding );
  35.  
  36.            unsigned bottom = max( offset - dir[0], 0 );
  37.            if( in[bottom >= thresholding] )
  38.                do
  39.                {
  40.                    if( !out[bottom] )
  41.                    {
  42.                        out[bottom] = edge;
  43.                        continuousTracing( bottom, in, out, thresholding );
  44.                    }
  45.                    else
  46.                        break;
  47.  
  48.                    bottom -= dir[0];
  49.  
  50.                    if( bottom < 0 )
  51.                        break;
  52.  
  53.                }while( in[bottom] >= thresholding );
  54.  
  55.            unsigned right = min( offset + dir[1], size );
  56.            if( in[right] >= thresholding )
  57.                do
  58.                {
  59.                    if( !out[right] )
  60.                    {
  61.                        out[right] = edge;
  62.                        continuousTracing( right, in, out, thresholding );
  63.                    }
  64.                    else
  65.                        break;
  66.  
  67.                    right += dir[1];
  68.  
  69.                    if( right > size )
  70.                        break;
  71.  
  72.                }while( in[right] >= thresholding );
  73.  
  74.            unsigned left = max( offset - dir[1], 0 );
  75.            if( in[left] >= thresholding )
  76.                do
  77.                {
  78.                    if( !out[left] )
  79.                    {
  80.                        out[left] = edge;
  81.                        continuousTracing( left, in, out, thresholding );
  82.                    }
  83.                    else
  84.                        break;
  85.  
  86.                    left -= dir[1];
  87.  
  88.                    if( left < 0 )
  89.                        break;
  90.  
  91.                }while( in[left] >= thresholding );
  92.  
  93.            unsigned topRight = min( offset + dir[0] + dir[1], size );
  94.            if( in[topRight] >= thresholding )
  95.                do
  96.                {
  97.                    if( !out[topRight] )
  98.                    {
  99.                        out[topRight] = edge;
  100.                        continuousTracing( left, in, out, thresholding );
  101.                    }
  102.                    else
  103.                        break;
  104.  
  105.                    topRight += dir[0] + dir[1];
  106.  
  107.                    if( topRight > size )
  108.                        break;
  109.  
  110.                }while( in[topRight] >= thresholding );
  111.  
  112.            unsigned bottomLeft = max( offset - dir[0] - dir[1], 0 );
  113.            if( in[bottomLeft] >= thresholding )
  114.                do
  115.                {
  116.                    if( !out[bottomLeft] )
  117.                    {
  118.                        out[bottomLeft] = edge;
  119.                        continuousTracing( bottomLeft, in, out, thresholding );
  120.                    }
  121.                    else
  122.                        break;
  123.  
  124.                    bottomLeft -= dir[0] - dir[1];
  125.  
  126.                    if( bottomLeft < 0 )
  127.                        break;
  128.  
  129.                }while( in[bottomLeft] >= thresholding );
  130.  
  131.            unsigned topLeft = min( offset + dir[0] - dir[1], size );
  132.            if( in[topLeft] >= thresholding )
  133.                do
  134.                {
  135.                    if( !out[topLeft] )
  136.                    {
  137.                        out[topLeft] = edge;
  138.                        continuousTracing( topLeft, in, out, thresholding );
  139.                    }
  140.                    else
  141.                        break;
  142.  
  143.                    topLeft += dir[0] - dir[1];
  144.  
  145.                    if( topLeft > size )
  146.                        break;
  147.  
  148.                }while( in[topLeft] >= thresholding );
  149.  
  150.            unsigned bottomRight = max( offset - dir[0] + dir[1], 0 );
  151.            if( in[bottomRight] >= thresholding )
  152.                do
  153.                {
  154.                    if( !out[bottomRight] )
  155.                    {
  156.                        out[bottomRight] = edge;
  157.                        continuousTracing( bottomRight, in, out, thresholding );
  158.                    }
  159.                    else
  160.                        break;
  161.  
  162.                    bottomRight -= dir[0] + dir[1];
  163.  
  164.                    if( bottomRight < 0 )
  165.                        break;
  166.  
  167.                }while( in[bottomRight] >= thresholding );
  168.  
  169.            /* Works with feedback and not will be an infinite loop cause I am saving the new data into a new image */
  170.        }
  171.  


Se dibujara en la imagen de salida, si el punto a pintar ya estaba pintado entonces se rompe el ciclo y se impide que ocurra un bucle infinito..

mi primera función que logra re alimentarse ella misma xd



RESULTADOS FINALES
[/size]





Listop, no puse más porque me da pereza, esto lo hize con la mera intencion de que si alguien busca en google "Canny algorithm" y busca resultados en español, obtenga una buena ayuda.

Y perdonen si mi codigo es desordenado, volvi a la programacion hace un par de meses y solo he leido un par de tutoriales .. en ingles depaso xd


« Última modificación: 18 Abril 2014, 04:02 am por Eternal Idol » En línea

eferion


Desconectado Desconectado

Mensajes: 1.248


Ver Perfil
Re: Algoritmo de detección de bordes de Canny ( C++ Manejo básico de imágines )
« Respuesta #2 en: 21 Abril 2014, 10:38 am »

La idea está genial. Enhorabuena.

Lo que no veo del todo claro es que en "cannyAlgorithm" tenga que ser todo público.

Quizás sería mejor crear una clase para gestionar la imagen y pasar una instancia de dicha clase a cannyAlgoritm para hacer el trabajo... incluso cannyAlgoritm podría almacenar los resultados en una nueva instancia de imagen y devolverla con un return... así la imagen original no sufre cambios.

Otra idea puede ser la utilización de "interfaces", que en C++ son clases virtuales puras. La idea es poder tener una colección de filtros y usarlos a discrección sin importar su tipo.

La cosa es tener una clase base con un método virtual puro para forzar a sus derivadas a implementarlo... después se hace que los diferentes filtros hereden de la clase base y así puedes usarlos todos de la misma forma ( incluso meterlos en un vector para poder ejectuar diferentes filtros en un orden concreto sin importar su tipo ).

Un ejemplo:

Código
  1. class Filtro
  2. {
  3.  public:
  4.  
  5.    Filtro( );
  6.  
  7.    // El destructor virtual, esto es importante en herencia
  8.    virtual ~Filtro( );
  9.  
  10.    // Imagen es la clase que te he comentado, se pasa por referencia porque asi
  11.    // te aseguras de que no te pasan punteros nulos
  12.    // el '= 0' es para indicar que esta clase no implementa esta funcion, es
  13.    // responsabilidad de las hijas implementarla.
  14.    // En este caso la imagen que se pasa como argumento se modifica segun el filtro.
  15.    virtual void Filtrar( Imagen& imagen ) = 0;    
  16. };
  17.  
  18. class FiltroCanny
  19.  : public Filtro
  20. {
  21.  public:
  22.  
  23.    FiltroCanny( );
  24.  
  25.    // Este destructor ya no es necesario declararlo virtual, pero tampoco hace ningun mal
  26.    // Es buena idea acostumbrarse a declarar los destructores siempre virtuales
  27.    // para evitar problemas
  28.    virtual ~FiltroCanny( );
  29.  
  30.    // Esta funcion sera la que implemente tu algoritmo de deteccion de bordes
  31.    // Luego en private puedes poner todas las funciones auxiliares que necesites
  32.    virtual void Filtrar( Imagen& imagen );
  33. };
  34.  
  35. // Esta clase representa un filtro que convierte una imagen a escala de grises
  36. class FiltroGrayScale
  37.  : public Filtro
  38. {
  39.  public:
  40.  
  41.    FiltroGrayScale( );
  42.  
  43.    virtual ~FiltroGrayScale( );
  44.  
  45.    virtual void Filtrar( Imagen& imagen );
  46. };
  47.  
  48. // En esta funcion se supone que se va a convertir una imagen en escala de grises
  49. // y despues se va a pasar tu algoritmo
  50. // Es un ejemplo sencillo para ilustrar un poco la flexibilidad de este diseño.
  51. void func( Imagen& imagen )
  52. {
  53.  std::vector< Filtro* > filtros;
  54.  filtros.push_back( new FiltroGrayScale( ) );
  55.  filtros.push_back( new FiltroCanny( ) );
  56.  
  57.  for ( int i = 0; i < filtros.size( ); i++ )
  58.    filtros[ i ]->Filtrar( imagen );
  59.  
  60.  for ( int i = 0; i < filtros.size( ); i++ )
  61.    delete filtros[ i ];  
  62. }
En línea

razormta

Desconectado Desconectado

Mensajes: 18


Ver Perfil
Re: Algoritmo de detección de bordes de Canny ( C++ Manejo básico de imágines )
« Respuesta #3 en: 22 Abril 2014, 02:08 am »

La idea está genial. Enhorabuena.

Lo que no veo del todo claro es que en "cannyAlgorithm" tenga que ser todo público.

Quizás sería mejor crear una clase para gestionar la imagen y pasar una instancia de dicha clase a cannyAlgoritm para hacer el trabajo... incluso cannyAlgoritm podría almacenar los resultados en una nueva instancia de imagen y devolverla con un return... así la imagen original no sufre cambios.

Otra idea puede ser la utilización de "interfaces", que en C++ son clases virtuales puras. La idea es poder tener una colección de filtros y usarlos a discrección sin importar su tipo.

La cosa es tener una clase base con un método virtual puro para forzar a sus derivadas a implementarlo... después se hace que los diferentes filtros hereden de la clase base y así puedes usarlos todos de la misma forma ( incluso meterlos en un vector para poder ejectuar diferentes filtros en un orden concreto sin importar su tipo ).

Un ejemplo:

Código
  1. class Filtro
  2. {
  3.  public:
  4.  
  5.    Filtro( );
  6.  
  7.    // El destructor virtual, esto es importante en herencia
  8.    virtual ~Filtro( );
  9.  
  10.    // Imagen es la clase que te he comentado, se pasa por referencia porque asi
  11.    // te aseguras de que no te pasan punteros nulos
  12.    // el '= 0' es para indicar que esta clase no implementa esta funcion, es
  13.    // responsabilidad de las hijas implementarla.
  14.    // En este caso la imagen que se pasa como argumento se modifica segun el filtro.
  15.    virtual void Filtrar( Imagen& imagen ) = 0;    
  16. };
  17.  
  18. class FiltroCanny
  19.  : public Filtro
  20. {
  21.  public:
  22.  
  23.    FiltroCanny( );
  24.  
  25.    // Este destructor ya no es necesario declararlo virtual, pero tampoco hace ningun mal
  26.    // Es buena idea acostumbrarse a declarar los destructores siempre virtuales
  27.    // para evitar problemas
  28.    virtual ~FiltroCanny( );
  29.  
  30.    // Esta funcion sera la que implemente tu algoritmo de deteccion de bordes
  31.    // Luego en private puedes poner todas las funciones auxiliares que necesites
  32.    virtual void Filtrar( Imagen& imagen );
  33. };
  34.  
  35. // Esta clase representa un filtro que convierte una imagen a escala de grises
  36. class FiltroGrayScale
  37.  : public Filtro
  38. {
  39.  public:
  40.  
  41.    FiltroGrayScale( );
  42.  
  43.    virtual ~FiltroGrayScale( );
  44.  
  45.    virtual void Filtrar( Imagen& imagen );
  46. };
  47.  
  48. // En esta funcion se supone que se va a convertir una imagen en escala de grises
  49. // y despues se va a pasar tu algoritmo
  50. // Es un ejemplo sencillo para ilustrar un poco la flexibilidad de este diseño.
  51. void func( Imagen& imagen )
  52. {
  53.  std::vector< Filtro* > filtros;
  54.  filtros.push_back( new FiltroGrayScale( ) );
  55.  filtros.push_back( new FiltroCanny( ) );
  56.  
  57.  for ( int i = 0; i < filtros.size( ); i++ )
  58.    filtros[ i ]->Filtrar( imagen );
  59.  
  60.  for ( int i = 0; i < filtros.size( ); i++ )
  61.    delete filtros[ i ];  
  62. }

gracias por la idea xd tengo otros filtros , pensare en lo que dijiste y tal ves vuelva con otro post xd
En línea

El Benjo


Desconectado Desconectado

Mensajes: 392



Ver Perfil WWW
Re: Algoritmo de detección de bordes de Canny ( C++ Manejo básico de imágines )
« Respuesta #4 en: 22 Abril 2014, 06:21 am »

Un excelente aporte colega, se ven pocas aplicaciones que valgan la pena por acá. Un saludo y una gran felicitación.
En línea

www.es.neftis-ai.com

Sí hay un mejor lenguaje de programación y es ese con el que puedes desarrollar tus objetivos.
Páginas: [1] Ir Arriba Respuesta Imprimir 

Ir a:  

WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines