Shape Contour with redCV

Another way to analyse shapes in image is to calculate the signature of the shape. Basically, the centroid of the shape given by the rcvGetCentroid is the origin of polar coordinates system. Consequently all pixels that belong to the contour of the shape can be described by the distance rho to the origin according to the angle theta.

RedCV proposes 2 fonctions for that:

rcvGetEuclidianDistance, which get the rho distance of the pixel (as-pair) to the centroid of the shape.

rcvGetAngle which calculate the theta angle (0..359 °) of the pixel.

© Bruno Keymolen 

As demonstrated here, redCV makes the job correctly. When looking for the signature of a circle, we get a line since all pixels are equidistant from the centroid.

For a square, it is also correct and the four angles of the square are clearly identifiable.

Code sample

Red [
    Title:   "Matrix tests "
    Author:  "Francois Jouen"
    File:    %freeman2.red
    Needs:   'View
]


#include %../../libs/redcv.red ; for redCV functions

iSize: 512x512
mat:  rcvCreateMat 'integer! 32 iSize
bMat: rcvCreateMat 'integer! 32 iSize
img: rcvCreateImage iSize
plot:  copy [fill-pen white box 155x155 355x355]
_plot: copy [line-width 1 pen green 
            text 175x480 "Angle"
            line 5x10 5x470 5x470 375x470 375x5 5x10 
            line 190x10 190x470
            text 10x450 "0" text 178x450 "180" text 345x450 "360" 
            line]
plot2: copy _plot
fgVal: 1
canvas: none


processImage: does [
    img: to-image canvas
    rcvImage2Mat img mat     
    rcvMakeBinaryMat mat bmat
    cg: rcvGetMatCentroid bmat img/size     ; get shape centroid
    border: []
    rcvMatGetBorder bmat iSize fgVal border ; get border
    angles: copy []
    foreach p border [
        ; use x y coordinates and calculate rho and theta
        rho: rcvGetEuclidianDistance p cg
        theta: rcvGetAngle p cg
        bloc: copy []
        append bloc theta
        append bloc rho
        append/only angles bloc 
    ]
    sort angles ; 0.. 359  to use with line draw command
    foreach n angles [
        p: as-pair first n 384 - second n 
        p: p + 10x0
        append plot2 (p)
    ]
    canvas2/draw: reduce [plot2]
]



; ***************** Test Program ****************************
view win: layout [
    title "Contour Signature"
    
    r1: radio "Square" [canvas/image: none 
                        canvas2/image: none
                        plot: compose [fill-pen white box 155x155 355x355]
                        plot2: copy _plot
                        canvas/draw: reduce [plot]
                        canvas2/draw: reduce [plot2]
                        ]
    r2: radio "Circle" [canvas/image: none 
                        canvas2/image: none
                        plot: compose [fill-pen white circle 255x255 120] 
                        plot2: copy _plot
                        canvas/draw: reduce [plot]
                        canvas2/draw: reduce [plot2]
                        ]
    r3: radio "Triangle" [canvas/image: none 
                        canvas2/image: none
                        plot: compose [pen white fill-pen white triangle 256x128 128x300 384x400] 
                        plot2: copy _plot
                        canvas/draw: reduce [plot]
                        canvas2/draw: reduce [plot2]
                        ]
    r4: radio "Polygon" [canvas/image: none 
                        canvas2/image: none
                        plot: compose [pen white fill-pen white polygon 256x100 384x300 128x400 128x300 256x10] 
                        plot2: copy _plot
                        canvas/draw: reduce [plot]
                        canvas2/draw: reduce [plot2]
                        ]
    button "Process" [processImage]
    pad 395x0
    button "Quit" [ rcvReleaseImage img
                    rcvReleaseMat mat
                    rcvReleaseMat bmat
                    Quit]
    return
    canvas: base 512x512 black draw plot
    canvas2: base 380x512 black draw plot2
    do  [r1/data: true]
]

Freeman Code Chain with redCV 2

As demonstrated in the previous article, redCV Freeman code chain works perfectly for regular shapes such as square, triangle, or circle. However many shapes in image are often irregular such as illustrated here.

Using Canny Detector and Morphological Operators

The process is two-fold. First, we use a Canny convolution filter to find the edges of the shape with rcvConvolve function. Since Canny detector is rather noise-sensitive, in some cases, edges detection is incomplete and the result of the function is a discret contour with some values equal to 0. In this case, rcvMatGetChainCode function returns an error (-1). The second process is to use a morphological operator like rcvDilate which slightly dilates the contour. With this simple idea, rcvMatGetChainCode, always returns the correct direction for the next  pixel whatever the complexity of the shape.

Code Sample

Red [
    Title:   "Freeman tests "
    Author:  "Francois Jouen"
    File:    %freemanirregular.red
    Needs:   'View
]


#include %../../libs/redcv.red ; for redCV functions
iSize: 512x512
rSize: 300x300
img: rcvCreateImage iSize
edges: rcvCreateImage iSize
edges2: rcvCreateImage iSize
mat:  rcvCreateMat 'integer! 32 iSize
bMat: rcvCreateMat 'integer! 32 iSize
visited: rcvCreateMat 'integer! 32 iSize
plot: copy []
fgVal: 1
canvas: none
knlSize: 3x3
knl: rcvCreateStructuringElement/rectangle knlSize
factor: 1.0
delta: 0.0
anim: false
canny: [-1.0 -1.0 -1.0
        -1.0 8.0 -1.0 
        -1.0 -1.0 -1.0]
        
generatePolygon: does [
    canvas/image: none
    clear f0/text
    clear f1/text
    clear f2/text
    clear f3/text
    clear f4/text
    clear r/text
    p1: 128x128 + random rSize p2: 128x128 + random rSize  p3: 128x128 + random rSize 
    p4: 128x128 + random rSize  128x128 +  p5: 128x128 + random rSize
    plot: compose [pen white fill-pen white polygon (p1) (p2) (p3) (p4) (p5)]
    canvas/draw: reduce [plot]
    pgb/data: 0%
]

processImage: does [
    img: to-image canvas
    rcvConvolve img edges canny factor delta    ; edges detection with Canny
    rcvDilate edges edges2 knlSize knl          ; dilates shape to suppress 0 values if exist
    rcvImage2Mat edges2 mat                     ; make first matrix 0..255
    rcvMakeBinaryMat mat bmat                   ; make second matrix 0..1
    lPix: rcvMatleftPixel bmat iSize fgVal
    rPix: rcvMatRightPixel bmat iSize fgVal
    uPix: rcvMatUpPixel bmat iSize fgVal
    dPix: rcvMatDownPixel bmat iSize fgVal
    f1/text: form as-pair lPix/x uPix/y
    f2/text: form as-pair rPix/x uPix/y
    f3/text: form as-pair rPix/x dPix/y 
    f4/text: form as-pair lPix/x dPix/y 
    visited: rcvCreateMat 'integer! 32 iSize            ; for storing visited pixels    
    border: []                                          ; for neighbors
    rcvMatGetBorder bmat iSize fgVal border             ; get border
    foreach p border [rcvSetInt2D visited iSize p 1]    ; values in matrix
    perim: (length? border) / 2                         ; pre-processing multiplies number of pixels
    f0/text: form perim
    p: uPix;first border
    i: 1
    s: copy ""
    clear r/text
    append append plot 'pen 'green
    pix: 1
    ; repeat until all pixels are processed
    while [pix > 0] [
        pix: rcvGetInt2D visited iSize p
        d: rcvMatGetChainCode visited iSize p 1     ; get chain code
        rcvSetInt2D visited iSize p 0               ; pixel processed 
        append append append plot 'circle (p) 2 
        if d > -1 [append s form d]
        if anim [do-events/no-wait]; to show progression
        switch d [
            0   [p/x: p/x + 1]              ; east
            1   [p/x: p/x + 1 p/y: p/y + 1] ; southeast
            2   [p/y: p/y + 1]              ; south
            3   [p/x: p/x - 1 p/y: p/y + 1] ; southwest
            4   [p/x: p/x - 1]              ; west
            5   [p/x: p/x - 1 p/y: p/y - 1] ; northwest
            6   [p/y: p/y - 1]              ; north
            7   [p/x: p/x + 1 p/y: p/y - 1] ; northeast
        ]
        pgb/data: to-percent (i / to-float perim)
        i: i + 1
    ]
    r/text: s
]

; ***************** Test Program ****************************
view win: layout [
    title "Chain Code with Canny Detector"
    button "Generate Polygon" [generatePolygon]
    cb: check "Show Anination" [anim: face/data]
    button "Process" [processImage]
    pgb: progress 160
    f0: field 125
    button "Quit" [
                    rcvReleaseImage img
                    rcvReleaseImage edges
                    rcvReleaseImage edges2
                    rcvReleaseMat mat
                    rcvReleaseMat bmat
                    rcvReleaseMat visited
                    Quit]
    return
    canvas: base iSize black draw plot
    r: area 200x512
    return
    pad 120x0
    f1: field 60
    f2: field 60
    f3: field 60
    f4: field 60
    return  
]




Result

Freeman Code Chain with redCV 1

Freeman code chain 

A chain code is a way to represent shapes in a binary image. The basic idea is very simple: One spot on the outer boundary of a shape is selected as the starting point, we then move along the boundary of the shape and describe each movement with a directional code that describes the movement. We continue tracing the boundary of the shape until we return to the starting point.

The Freeman code encodes the movement as an integer number between 0 and 7.

0: east

1: southeast

2: south

3: southwest

4: west

5: northwest

6: north

7: northeast

The simple idea is to look for the neighbors of the current pixel and get the direction according to the neighbor value.

Freeman Code Chain in redCV

We do implement basic Freeman code chain in redCV which requires some image preprocessing.

First of all we need a binary image. This is easy done with 2 redCV functions:

rcvImage2Mat which transforms any red image to a binary matrix [0..255] and 

rcvMakeBinaryMat which makes a binary [0..1] matrix.

Then we have to get all points that belong to the shape. Just call rcvMatGetBorder function that looks for all value (0 or 1) that are part of shape boundary. Found pixels in binary matrix are stored in a block such as border. When found you have to copy pixel in another matrix which will be used then to store visited pixel (foreach p border [rcvSetInt2D visited iSize p 1]).

Then redCV uses the rcvMatGetChainCode to get the successive movement direction such as in the code sample:

p: first border
i: 1
while [i < perim] [
    d: rcvMatGetChainCode visited iSize p fgVal
    idx: (p/y * iSize/x + p/x) + 1  
    visited/:idx: 0; pixel is visited
    append s form d
    switch d [
        0   [p/x: p/x + 1]              ; east
        1   [p/x: p/x + 1 p/y: p/y + 1] ; southeast
        2   [p/y: p/y + 1]              ; south
        3   [p/x: p/x - 1 p/y: p/y + 1] ; southwest
        4   [p/x: p/x - 1]              ; west
        5   [p/x: p/x - 1 p/y: p/y - 1] ; northwest
        6   [p/y: p/y - 1]              ; north
        7   [p/x: p/x + 1 p/y: p/y - 1] ; northeast
    ]
    i: i + 1
]

It is very important to ensure that the current pixel was processed; if not the pixel can be again processed and the chain code could be invalid. This is why we set to 0 visited  pixel in shape matrix (visited/:idx: 0; pixel is visited).

Then according to the direction value returned by the  rcvMatGetChainCode function we move to the new pixel to be analyzed.

Code Sample

Red [
    Title:   "Matrix tests "
    Author:  "Francois Jouen"
    File:    %freeman.red
    Needs:   'View
]


#include %../../libs/redcv.red ; for redCV functions

plot: []
iSize: 512x512
img: rcvCreateImage iSize
mat:  rcvCreateMat 'integer! 32 iSize
bMat: rcvCreateMat 'integer! 32 iSize
visited: rcvCreateMat 'integer! 32 iSize
fgVal: 1
canvas: none


generateImage: does [
    canvas/image: none
    p1: random 400x400
    p2: random 400x400
    color: 255.255.255
    plot: compose [fill-pen (color) box (p1) (p2)]
    processImage
]


processImage: does [
    canvas/draw: reduce [plot]
    img: to-image canvas
    rcvImage2Mat img mat     
    rcvMakeBinaryMat mat bmat
    lPix: rcvMatleftPixel bmat iSize fgVal
    rPix: rcvMatRightPixel bmat iSize fgVal
    uPix: rcvMatUpPixel bmat iSize fgVal
    dPix: rcvMatDownPixel bmat iSize fgVal
    f1/text: form as-pair lPix/x uPix/y 
    f2/text: form as-pair rPix/x uPix/y 
    f3/text: form as-pair rPix/x dPix/y 
    f4/text: form as-pair lPix/x dPix/y
    clear r/text
    visited: rcvCreateMat 'integer! 32 iSize
    border: copy []
    rcvMatGetBorder bmat iSize fgVal border
    foreach p border [rcvSetInt2D visited iSize p 1]
    perim: length? border
    p: first border
    i: 1
    s: copy ""
    while [i < perim] [
        d: rcvMatGetChainCode visited iSize p fgVal
        idx: (p/y * iSize/x + p/x) + 1  
        visited/:idx: 0; pixel is visited
        append s form d
        switch d [
            0   [p/x: p/x + 1]              ; east
            1   [p/x: p/x + 1 p/y: p/y + 1] ; southeast
            2   [p/y: p/y + 1]              ; south
            3   [p/x: p/x - 1 p/y: p/y + 1] ; southwest
            4   [p/x: p/x - 1]              ; west
            5   [p/x: p/x - 1 p/y: p/y - 1] ; northwest
            6   [p/y: p/y - 1]              ; north
            7   [p/x: p/x + 1 p/y: p/y - 1] ; northeast
        ]
        i: i + 1
    ]
    r/text: s
]



; ***************** Test Program ****************************
view win: layout [
    title "Chain Code"
    button "Generate Shape"     [generateImage]
    pad 580x0
    button "Quit"               [rcvReleaseImage img
                                 rcvReleaseMat mat
                                 rcvReleaseMat bmat
                                 rcvReleaseMat visited
                                 Quit]
    return
    canvas: base iSize black draw plot
    r: area 256x512
    return
    pad 100x0
    f1: field 60
    f2: field 60
    f3: field 60
    f4: field 60
]

Result