Comment détecter un sapin de Noël ?

Question

Qui techniques de traitement d'image peut être utilisé pour mettre en œuvre une application qui détecte les arbres de noël affichés dans les images suivantes?

Je suis à la recherche de solutions qui vont travailler sur toutes ces images. Par conséquent, les approches qui ont besoin de formation haar cascade de classificateurs ou modèle correspondant ne sont pas très intéressants.

Je suis à la recherche de quelque chose qui peut être écrit dans tout langage de programmation, tant qu' il n'utilise que l'Open Source technologies. La solution doit être testé avec les images qui sont partagés sur cette question. Il y a 6 images d'entrée et la réponse doit afficher les résultats de traitement de chacun d'eux. Enfin, pour chaque image de sortie, il doit y avoir des lignes rouges dessiner entourer la détection de l'arbre.

Comment vous y prendriez-vous par programmation détecter les arbres dans ces images?

Answer 1

J'ai une approche qui, je pense, est intéressant et un peu différent du reste. La principale différence dans ma démarche, par rapport à certains des autres, c'est la manière dont l'image de l'étape de segmentation est effectuée--j'ai utilisé le DBSCAN algorithme de clustering de Python scikit-learn; il est optimisé pour la recherche d'un peu des formes amorphes qui ne peuvent pas nécessairement avoir une ligne claire et unique centre de gravité.

Au plus haut niveau, mon approche est assez simple et peut être décomposée en 3 étapes. D'abord j'applique un seuil (ou en fait, le "ou" logique des deux distincts et séparés des seuils). Comme beaucoup d'autres réponses, je suppose que l'arbre de Noël serait l'un des plus lumineux des objets dans la scène, de sorte que le premier seuil est juste un simple monochrome luminosité de l'épreuve; tous les pixels avec des valeurs au-dessus de 220 sur une échelle de 0 à 255 (où le noir est 0 et le blanc à 255) sont enregistrés dans un fichier binaire en noir et blanc de l'image. Le deuxième seuil essaye de regarder pour le rouge et le jaune des lumières, qui sont particulièrement importants dans les arbres dans le coin supérieur gauche et inférieur droit de la six images, et se détachent bien sur le bleu-vert en arrière-plan qui est très répandue dans la plupart des photos. - Je convertir l'image rvb dans l'espace hsv, et exiger que la teinte est soit moins de 0,2 sur une 0.0-1.0 échelle (correspondant à peu près à la frontière entre le jaune et le vert) ou supérieur à 0,95 (correspondant à la frontière entre le violet et le rouge) et en plus j'ai besoin de couleurs vives aux couleurs saturées: la saturation et la valeur doivent être supérieures à 0,7. Les résultats des deux seuils des procédures sont logiquement "ou"-ed ensemble, et la matrice obtenue en noir et blanc des images binaires est indiqué ci-dessous:

Vous pouvez clairement voir que chaque image a un grand amas de pixels correspondant grosso modo à l'emplacement de chaque arbre, ainsi que quelques-unes des images ont également quelques autres petits groupes correspondant soit à des lumières dans les fenêtres de certains bâtiments, ou à une scène d'arrière-plan à l'horizon. La prochaine étape est d'obtenir l'ordinateur de reconnaître que ce sont des groupes distincts, et l'étiquette de chaque pixel correctement avec une appartenance au cluster numéro d'identification.

Pour cette tâche, j'ai choisi DBSCAN. Il y a une assez bonne comparaison visuelle de la façon dont DBSCAN se comporte normalement, par rapport à d'autres algorithmes de clustering, disponible ici. Comme je l'ai dit plus tôt, il le fait bien avec des formes amorphes. La sortie de DBSCAN, chaque grappe tracées dans une couleur différente, qui est montré ici:

Il y a quelques choses à être conscient de quand à la recherche à ce résultat. La première est que DBSCAN demande à l'utilisateur de définir une "proximité" paramètre afin de réguler son comportement, ce qui permet de contrôler la façon dont séparés d'une paire de points doit être en ordre pour l'algorithme de déclarer un nouveau groupe à part, plutôt que de l'agglomération de un point de test sur un déjà pré-cluster existant. J'ai mis cette valeur de 0,04 fois la taille le long de la diagonale de chaque image. Puisque les images varient en taille, passant de près de VGA à propos de HD 1080, ce type d'échelle relative de définition est essentielle.

Un autre point à noter est que l'algorithme DBSCAN comme il est mis en œuvre dans scikit-learn a les limites de la mémoire qui sont assez difficiles pour certaines des plus grandes images de cet échantillon. Par conséquent, pour quelques-unes des images plus grandes, j'ai effectivement eu de "décimer" (c'est à dire, de ne retenir que tous les 3 ou 4 pixels et déposer les autres) chaque cluster afin de rester dans cette limite. Comme résultat de ce processus d'abattage, le reste individuelles éparses pixels sont difficiles à voir sur certaines des images plus grandes. Par conséquent, pour des fins d'affichage uniquement, le code couleur des pixels dans les images ci-dessus ont été effectivement "dilatée" juste un peu pour qu'ils ressortent mieux. C'est purement une opération cosmétique, pour le plaisir de la narration; bien qu'il y a des commentaires mentionnant cette dilatation dans mon code, soyez assuré que cela n'a rien à voir avec les calculs qui ont vraiment de l'importance.

Une fois les grappes sont identifiés et étiquetés, la troisième et dernière étape est simple: je prends simplement le plus grand cluster de chaque image (dans ce cas, j'ai choisi de mesurer la "taille" en termes de nombre total de membres de pixels, bien que l'on aurait pu tout aussi facilement à la place utilisé un certain type de métrique que les jauges de mesure physique) et de calculer l'enveloppe convexe pour ce cluster. L'enveloppe convexe puis devient l'arbre de la frontière. Les six convexe coques calculée par cette méthode sont présentés ci-dessous en rouge:

Le code source est écrit en Python 2.7.6 et il dépend de numpy, scipy, matplotlib et scikit-learn. J'ai divisé en deux parties. La première partie est responsable pour le traitement de l'image:

from PIL import Image
import numpy as np
import scipy as sp
import matplotlib.colors as colors
from sklearn.cluster import DBSCAN
from math import ceil, sqrt

"""
Inputs:

    rgbimg:         [M,N,3] numpy array containing (uint, 0-255) color image

    hueleftthr:     Scalar constant to select maximum allowed hue in the
                    yellow-green region

    huerightthr:    Scalar constant to select minimum allowed hue in the
                    blue-purple region

    satthr:         Scalar constant to select minimum allowed saturation

    valthr:         Scalar constant to select minimum allowed value

    monothr:        Scalar constant to select minimum allowed monochrome
                    brightness

    maxpoints:      Scalar constant maximum number of pixels to forward to
                    the DBSCAN clustering algorithm

    proxthresh:     Proximity threshold to use for DBSCAN, as a fraction of
                    the diagonal size of the image

Outputs:

    borderseg:      [K,2,2] Nested list containing K pairs of x- and y- pixel
                    values for drawing the tree border

    X:              [P,2] List of pixels that passed the threshold step

    labels:         [Q,2] List of cluster labels for points in Xslice (see
                    below)

    Xslice:         [Q,2] Reduced list of pixels to be passed to DBSCAN

"""

def findtree(rgbimg, hueleftthr=0.2, huerightthr=0.95, satthr=0.7, 
             valthr=0.7, monothr=220, maxpoints=5000, proxthresh=0.04):

    # Convert rgb image to monochrome for
    gryimg = np.asarray(Image.fromarray(rgbimg).convert('L'))
    # Convert rgb image (uint, 0-255) to hsv (float, 0.0-1.0)
    hsvimg = colors.rgb_to_hsv(rgbimg.astype(float)/255)

    # Initialize binary thresholded image
    binimg = np.zeros((rgbimg.shape[0], rgbimg.shape[1]))
    # Find pixels with hue<0.2 or hue>0.95 (red or yellow) and saturation/value
    # both greater than 0.7 (saturated and bright)--tends to coincide with
    # ornamental lights on trees in some of the images
    boolidx = np.logical_and(
                np.logical_and(
                  np.logical_or((hsvimg[:,:,0] < hueleftthr),
                                (hsvimg[:,:,0] > huerightthr)),
                                (hsvimg[:,:,1] > satthr)),
                                (hsvimg[:,:,2] > valthr))
    # Find pixels that meet hsv criterion
    binimg[np.where(boolidx)] = 255
    # Add pixels that meet grayscale brightness criterion
    binimg[np.where(gryimg > monothr)] = 255

    # Prepare thresholded points for DBSCAN clustering algorithm
    X = np.transpose(np.where(binimg == 255))
    Xslice = X
    nsample = len(Xslice)
    if nsample > maxpoints:
        # Make sure number of points does not exceed DBSCAN maximum capacity
        Xslice = X[range(0,nsample,int(ceil(float(nsample)/maxpoints)))]

    # Translate DBSCAN proximity threshold to units of pixels and run DBSCAN
    pixproxthr = proxthresh * sqrt(binimg.shape[0]**2 + binimg.shape[1]**2)
    db = DBSCAN(eps=pixproxthr, min_samples=10).fit(Xslice)
    labels = db.labels_.astype(int)

    # Find the largest cluster (i.e., with most points) and obtain convex hull   
    unique_labels = set(labels)
    maxclustpt = 0
    for k in unique_labels:
        class_members = [index[0] for index in np.argwhere(labels == k)]
        if len(class_members) > maxclustpt:
            points = Xslice[class_members]
            hull = sp.spatial.ConvexHull(points)
            maxclustpt = len(class_members)
            borderseg = [[points[simplex,0], points[simplex,1]] for simplex
                          in hull.simplices]

    return borderseg, X, labels, Xslice

et la deuxième partie est un niveau de l'utilisateur du script qui appelle le premier fichier et génère l'ensemble des parcelles ci-dessus:

#!/usr/bin/env python

from PIL import Image
import numpy as np
import matplotlib.pyplot as plt
import matplotlib.cm as cm
from findtree import findtree

# Image files to process
fname = ['nmzwj.png', 'aVZhC.png', '2K9EF.png',
         'YowlH.png', '2y4o5.png', 'FWhSP.png']

# Initialize figures
fgsz = (16,7)        
figthresh = plt.figure(figsize=fgsz, facecolor='w')
figclust  = plt.figure(figsize=fgsz, facecolor='w')
figcltwo  = plt.figure(figsize=fgsz, facecolor='w')
figborder = plt.figure(figsize=fgsz, facecolor='w')
figthresh.canvas.set_window_title('Thresholded HSV and Monochrome Brightness')
figclust.canvas.set_window_title('DBSCAN Clusters (Raw Pixel Output)')
figcltwo.canvas.set_window_title('DBSCAN Clusters (Slightly Dilated for Display)')
figborder.canvas.set_window_title('Trees with Borders')

for ii, name in zip(range(len(fname)), fname):
    # Open the file and convert to rgb image
    rgbimg = np.asarray(Image.open(name))

    # Get the tree borders as well as a bunch of other intermediate values
    # that will be used to illustrate how the algorithm works
    borderseg, X, labels, Xslice = findtree(rgbimg)

    # Display thresholded images
    axthresh = figthresh.add_subplot(2,3,ii+1)
    axthresh.set_xticks([])
    axthresh.set_yticks([])
    binimg = np.zeros((rgbimg.shape[0], rgbimg.shape[1]))
    for v, h in X:
        binimg[v,h] = 255
    axthresh.imshow(binimg, interpolation='nearest', cmap='Greys')

    # Display color-coded clusters
    axclust = figclust.add_subplot(2,3,ii+1) # Raw version
    axclust.set_xticks([])
    axclust.set_yticks([])
    axcltwo = figcltwo.add_subplot(2,3,ii+1) # Dilated slightly for display only
    axcltwo.set_xticks([])
    axcltwo.set_yticks([])
    axcltwo.imshow(binimg, interpolation='nearest', cmap='Greys')
    clustimg = np.ones(rgbimg.shape)    
    unique_labels = set(labels)
    # Generate a unique color for each cluster 
    plcol = cm.rainbow_r(np.linspace(0, 1, len(unique_labels)))
    for lbl, pix in zip(labels, Xslice):
        for col, unqlbl in zip(plcol, unique_labels):
            if lbl == unqlbl:
                # Cluster label of -1 indicates no cluster membership;
                # override default color with black
                if lbl == -1:
                    col = [0.0, 0.0, 0.0, 1.0]
                # Raw version
                for ij in range(3):
                    clustimg[pix[0],pix[1],ij] = col[ij]
                # Dilated just for display
                axcltwo.plot(pix[1], pix[0], 'o', markerfacecolor=col, 
                    markersize=1, markeredgecolor=col)
    axclust.imshow(clustimg)
    axcltwo.set_xlim(0, binimg.shape[1]-1)
    axcltwo.set_ylim(binimg.shape[0], -1)

    # Plot original images with read borders around the trees
    axborder = figborder.add_subplot(2,3,ii+1)
    axborder.set_axis_off()
    axborder.imshow(rgbimg, interpolation='nearest')
    for vseg, hseg in borderseg:
        axborder.plot(hseg, vseg, 'r-', lw=3)
    axborder.set_xlim(0, binimg.shape[1]-1)
    axborder.set_ylim(binimg.shape[0], -1)

plt.show()

Answer 2

MODIFIER NOTE: j'ai édité ce post pour (i) traiter chaque image de l'arbre individuellement, comme demandé dans les exigences, (ii) d'envisager à la fois l'objet de la luminosité et de la forme dans le but d'améliorer la qualité du résultat.

---

Ci-dessous est présentée une approche qui prend en considération l'objet de la luminosité et de la forme. En d'autres termes, elle vise des objets avec triangle en forme et avec une importante luminosité. Il a été mis en œuvre en Java, à l'aide de Marvin framework de traitement d'image.

La première étape est la couleur de seuillage. L'objectif ici est de faire porter l'analyse sur les objets avec une importante luminosité.

les images de sortie:

code source:

public class ChristmasTree {

private MarvinImagePlugin fill = MarvinPluginLoader.loadImagePlugin("org.marvinproject.image.fill.boundaryFill");
private MarvinImagePlugin threshold = MarvinPluginLoader.loadImagePlugin("org.marvinproject.image.color.thresholding");
private MarvinImagePlugin invert = MarvinPluginLoader.loadImagePlugin("org.marvinproject.image.color.invert");
private MarvinImagePlugin dilation = MarvinPluginLoader.loadImagePlugin("org.marvinproject.image.morphological.dilation");

public ChristmasTree(){
    MarvinImage tree;

    // Iterate each image
    for(int i=1; i<=6; i++){
        tree = MarvinImageIO.loadImage("./res/trees/tree"+i+".png");

        // 1. Threshold
        threshold.setAttribute("threshold", 200);
        threshold.process(tree.clone(), tree);
    }
}
public static void main(String[] args) {
    new ChristmasTree();
}
}

Dans la deuxième étape, les points les plus clairs de l'image dilatée dans l'ordre pour former des formes. Le résultat de ce processus est la cause probable de la forme des objets, avec une importante luminosité. L'application de remplissage de la segmentation, déconnecté formes sont détectés.

les images de sortie:

code source:

public class ChristmasTree {

private MarvinImagePlugin fill = MarvinPluginLoader.loadImagePlugin("org.marvinproject.image.fill.boundaryFill");
private MarvinImagePlugin threshold = MarvinPluginLoader.loadImagePlugin("org.marvinproject.image.color.thresholding");
private MarvinImagePlugin invert = MarvinPluginLoader.loadImagePlugin("org.marvinproject.image.color.invert");
private MarvinImagePlugin dilation = MarvinPluginLoader.loadImagePlugin("org.marvinproject.image.morphological.dilation");

public ChristmasTree(){
    MarvinImage tree;

    // Iterate each image
    for(int i=1; i<=6; i++){
        tree = MarvinImageIO.loadImage("./res/trees/tree"+i+".png");

        // 1. Threshold
        threshold.setAttribute("threshold", 200);
        threshold.process(tree.clone(), tree);

        // 2. Dilate
        invert.process(tree.clone(), tree);
        tree = MarvinColorModelConverter.rgbToBinary(tree, 127);
        MarvinImageIO.saveImage(tree, "./res/trees/new/tree_"+i+"threshold.png");
        dilation.setAttribute("matrix", MarvinMath.getTrueMatrix(50, 50));
        dilation.process(tree.clone(), tree);
        MarvinImageIO.saveImage(tree, "./res/trees/new/tree_"+1+"_dilation.png");
        tree = MarvinColorModelConverter.binaryToRgb(tree);

        // 3. Segment shapes
        MarvinImage trees2 = tree.clone();
        fill(tree, trees2);
        MarvinImageIO.saveImage(trees2, "./res/trees/new/tree_"+i+"_fill.png");
}

private void fill(MarvinImage imageIn, MarvinImage imageOut){
    boolean found;
    int color= 0xFFFF0000;

    while(true){
        found=false;

        Outerloop:
        for(int y=0; y<imageIn.getHeight(); y++){
            for(int x=0; x<imageIn.getWidth(); x++){
                if(imageOut.getIntComponent0(x, y) == 0){
                    fill.setAttribute("x", x);
                    fill.setAttribute("y", y);
                    fill.setAttribute("color", color);
                    fill.setAttribute("threshold", 120);
                    fill.process(imageIn, imageOut);
                    color = newColor(color);

                    found = true;
                    break Outerloop;
                }
            }
        }

        if(!found){
            break;
        }
    }

}

private int newColor(int color){
    int red = (color & 0x00FF0000) >> 16;
    int green = (color & 0x0000FF00) >> 8;
    int blue = (color & 0x000000FF);

    if(red <= green && red <= blue){
        red+=5;
    }
    else if(green <= red && green <= blue){
        green+=5;
    }
    else{
        blue+=5;
    }

    return 0xFF000000 + (red << 16) + (green << 8) + blue;
}

public static void main(String[] args) {
    new ChristmasTree();
}
}

Comme indiqué dans l'image de sortie, de multiples formes a été détecté. Dans ce problème, il y a juste quelques points lumineux dans les images. Cependant, cette approche a été mise en œuvre pour faire face à des scénarios plus complexes.

Dans l'étape suivante, chaque forme est analysé. Un simple algorithme détecte les formes avec un motif semblable à un triangle. L'algorithme d'analyser la forme de l'objet, ligne par ligne. Si le centre de la masse de chaque forme de la ligne est presque le même (étant donné un seuil) et de l'augmentation de la masse comme y augmenter, l'objet a une forme de triangle comme la forme. La masse de la forme de la ligne est le nombre de pixels de cette ligne qui appartient à la forme. Imaginez-vous la coupez l'objet horizontalement et analyser chaque segment horizontal. Si elles sont centralisées les uns des autres et de l'augmentation de longueur du premier segment de la dernière dans un modèle linéaire, vous a probablement un objet qui ressemble à un triangle.

code source:

private int[] detectTrees(MarvinImage image){
    HashSet<Integer> analysed = new HashSet<Integer>();
    boolean found;
    while(true){
        found = false;
        for(int y=0; y<image.getHeight(); y++){
            for(int x=0; x<image.getWidth(); x++){
                int color = image.getIntColor(x, y);

                if(!analysed.contains(color)){
                    if(isTree(image, color)){
                        return getObjectRect(image, color);
                    }

                    analysed.add(color);
                    found=true;
                }
            }
        }

        if(!found){
            break;
        }
    }
    return null;
}

private boolean isTree(MarvinImage image, int color){

    int mass[][] = new int[image.getHeight()][2];
    int yStart=-1;
    int xStart=-1;
    for(int y=0; y<image.getHeight(); y++){
        int mc = 0;
        int xs=-1;
        int xe=-1;
        for(int x=0; x<image.getWidth(); x++){
            if(image.getIntColor(x, y) == color){
                mc++;

                if(yStart == -1){
                    yStart=y;
                    xStart=x;
                }

                if(xs == -1){
                    xs = x;
                }
                if(x > xe){
                    xe = x;
                }
            }
        }
        mass[y][0] = xs;
        mass[y][3] = xe;
        mass[y][4] = mc;    
    }

    int validLines=0;
    for(int y=0; y<image.getHeight(); y++){
        if
        ( 
            mass[y][5] > 0 &&
            Math.abs(((mass[y][0]+mass[y][6])/2)-xStart) <= 50 &&
            mass[y][7] >= (mass[yStart][8] + (y-yStart)*0.3) &&
            mass[y][9] <= (mass[yStart][10] + (y-yStart)*1.5)
        )
        {
            validLines++;
        }
    }

    if(validLines > 100){
        return true;
    }
    return false;
}

Enfin, la position de chaque forme semblable à un triangle et avec une importante luminosité, dans ce cas, un arbre de Noël, est mis en surbrillance dans l'image d'origine, comme illustré ci-dessous.

finale des images de sortie:

code source final:

public class ChristmasTree {

private MarvinImagePlugin fill = MarvinPluginLoader.loadImagePlugin("org.marvinproject.image.fill.boundaryFill");
private MarvinImagePlugin threshold = MarvinPluginLoader.loadImagePlugin("org.marvinproject.image.color.thresholding");
private MarvinImagePlugin invert = MarvinPluginLoader.loadImagePlugin("org.marvinproject.image.color.invert");
private MarvinImagePlugin dilation = MarvinPluginLoader.loadImagePlugin("org.marvinproject.image.morphological.dilation");

public ChristmasTree(){
    MarvinImage tree;

    // Iterate each image
    for(int i=1; i<=6; i++){
        tree = MarvinImageIO.loadImage("./res/trees/tree"+i+".png");

        // 1. Threshold
        threshold.setAttribute("threshold", 200);
        threshold.process(tree.clone(), tree);

        // 2. Dilate
        invert.process(tree.clone(), tree);
        tree = MarvinColorModelConverter.rgbToBinary(tree, 127);
        MarvinImageIO.saveImage(tree, "./res/trees/new/tree_"+i+"threshold.png");
        dilation.setAttribute("matrix", MarvinMath.getTrueMatrix(50, 50));
        dilation.process(tree.clone(), tree);
        MarvinImageIO.saveImage(tree, "./res/trees/new/tree_"+1+"_dilation.png");
        tree = MarvinColorModelConverter.binaryToRgb(tree);

        // 3. Segment shapes
        MarvinImage trees2 = tree.clone();
        fill(tree, trees2);
        MarvinImageIO.saveImage(trees2, "./res/trees/new/tree_"+i+"_fill.png");

        // 4. Detect tree-like shapes
        int[] rect = detectTrees(trees2);

        // 5. Draw the result
        MarvinImage original = MarvinImageIO.loadImage("./res/trees/tree"+i+".png");
        drawBoundary(trees2, original, rect);
        MarvinImageIO.saveImage(original, "./res/trees/new/tree_"+i+"_out_2.jpg");
    }
}

private void drawBoundary(MarvinImage shape, MarvinImage original, int[] rect){
    int yLines[] = new int[6];
    yLines[0] = rect[1];
    yLines[1] = rect[1]+(int)((rect[3]/5));
    yLines[2] = rect[1]+((rect[3]/5)*2);
    yLines[3] = rect[1]+((rect[3]/5)*3);
    yLines[4] = rect[1]+(int)((rect[3]/5)*4);
    yLines[5] = rect[1]+rect[3];

    List<Point> points = new ArrayList<Point>();
    for(int i=0; i<yLines.length; i++){
        boolean in=false;
        Point startPoint=null;
        Point endPoint=null;
        for(int x=rect[0]; x<rect[0]+rect[2]; x++){

            if(shape.getIntColor(x, yLines[i]) != 0xFFFFFFFF){
                if(!in){
                    if(startPoint == null){
                        startPoint = new Point(x, yLines[i]);
                    }
                }
                in = true;
            }
            else{
                if(in){
                    endPoint = new Point(x, yLines[i]);
                }
                in = false;
            }
        }

        if(endPoint == null){
            endPoint = new Point((rect[0]+rect[2])-1, yLines[i]);
        }

        points.add(startPoint);
        points.add(endPoint);
    }

    drawLine(points.get(0).x, points.get(0).y, points.get(1).x, points.get(1).y, 15, original);
    drawLine(points.get(1).x, points.get(1).y, points.get(3).x, points.get(3).y, 15, original);
    drawLine(points.get(3).x, points.get(3).y, points.get(5).x, points.get(5).y, 15, original);
    drawLine(points.get(5).x, points.get(5).y, points.get(7).x, points.get(7).y, 15, original);
    drawLine(points.get(7).x, points.get(7).y, points.get(9).x, points.get(9).y, 15, original);
    drawLine(points.get(9).x, points.get(9).y, points.get(11).x, points.get(11).y, 15, original);
    drawLine(points.get(11).x, points.get(11).y, points.get(10).x, points.get(10).y, 15, original);
    drawLine(points.get(10).x, points.get(10).y, points.get(8).x, points.get(8).y, 15, original);
    drawLine(points.get(8).x, points.get(8).y, points.get(6).x, points.get(6).y, 15, original);
    drawLine(points.get(6).x, points.get(6).y, points.get(4).x, points.get(4).y, 15, original);
    drawLine(points.get(4).x, points.get(4).y, points.get(2).x, points.get(2).y, 15, original);
    drawLine(points.get(2).x, points.get(2).y, points.get(0).x, points.get(0).y, 15, original);
}

private void drawLine(int x1, int y1, int x2, int y2, int length, MarvinImage image){
    int lx1, lx2, ly1, ly2;
    for(int i=0; i<length; i++){
        lx1 = (x1+i >= image.getWidth() ? (image.getWidth()-1)-i: x1);
        lx2 = (x2+i >= image.getWidth() ? (image.getWidth()-1)-i: x2);
        ly1 = (y1+i >= image.getHeight() ? (image.getHeight()-1)-i: y1);
        ly2 = (y2+i >= image.getHeight() ? (image.getHeight()-1)-i: y2);

        image.drawLine(lx1+i, ly1, lx2+i, ly2, Color.red);
        image.drawLine(lx1, ly1+i, lx2, ly2+i, Color.red);
    }
}

private void fillRect(MarvinImage image, int[] rect, int length){
    for(int i=0; i<length; i++){
        image.drawRect(rect[0]+i, rect[1]+i, rect[2]-(i*2), rect[3]-(i*2), Color.red);
    }
}

private void fill(MarvinImage imageIn, MarvinImage imageOut){
    boolean found;
    int color= 0xFFFF0000;

    while(true){
        found=false;

        Outerloop:
        for(int y=0; y<imageIn.getHeight(); y++){
            for(int x=0; x<imageIn.getWidth(); x++){
                if(imageOut.getIntComponent0(x, y) == 0){
                    fill.setAttribute("x", x);
                    fill.setAttribute("y", y);
                    fill.setAttribute("color", color);
                    fill.setAttribute("threshold", 120);
                    fill.process(imageIn, imageOut);
                    color = newColor(color);

                    found = true;
                    break Outerloop;
                }
            }
        }

        if(!found){
            break;
        }
    }

}

private int[] detectTrees(MarvinImage image){
    HashSet<Integer> analysed = new HashSet<Integer>();
    boolean found;
    while(true){
        found = false;
        for(int y=0; y<image.getHeight(); y++){
            for(int x=0; x<image.getWidth(); x++){
                int color = image.getIntColor(x, y);

                if(!analysed.contains(color)){
                    if(isTree(image, color)){
                        return getObjectRect(image, color);
                    }

                    analysed.add(color);
                    found=true;
                }
            }
        }

        if(!found){
            break;
        }
    }
    return null;
}

private boolean isTree(MarvinImage image, int color){

    int mass[][] = new int[image.getHeight()][11];
    int yStart=-1;
    int xStart=-1;
    for(int y=0; y<image.getHeight(); y++){
        int mc = 0;
        int xs=-1;
        int xe=-1;
        for(int x=0; x<image.getWidth(); x++){
            if(image.getIntColor(x, y) == color){
                mc++;

                if(yStart == -1){
                    yStart=y;
                    xStart=x;
                }

                if(xs == -1){
                    xs = x;
                }
                if(x > xe){
                    xe = x;
                }
            }
        }
        mass[y][0] = xs;
        mass[y][12] = xe;
        mass[y][13] = mc;   
    }

    int validLines=0;
    for(int y=0; y<image.getHeight(); y++){
        if
        ( 
            mass[y][14] > 0 &&
            Math.abs(((mass[y][0]+mass[y][15])/2)-xStart) <= 50 &&
            mass[y][16] >= (mass[yStart][17] + (y-yStart)*0.3) &&
            mass[y][18] <= (mass[yStart][19] + (y-yStart)*1.5)
        )
        {
            validLines++;
        }
    }

    if(validLines > 100){
        return true;
    }
    return false;
}

private int[] getObjectRect(MarvinImage image, int color){
    int x1=-1;
    int x2=-1;
    int y1=-1;
    int y2=-1;

    for(int y=0; y<image.getHeight(); y++){
        for(int x=0; x<image.getWidth(); x++){
            if(image.getIntColor(x, y) == color){

                if(x1 == -1 || x < x1){
                    x1 = x;
                }
                if(x2 == -1 || x > x2){
                    x2 = x;
                }
                if(y1 == -1 || y < y1){
                    y1 = y;
                }
                if(y2 == -1 || y > y2){
                    y2 = y;
                }
            }
        }
    }

    return new int[]{x1, y1, (x2-x1), (y2-y1)};
}

private int newColor(int color){
    int red = (color & 0x00FF0000) >> 16;
    int green = (color & 0x0000FF00) >> 8;
    int blue = (color & 0x000000FF);

    if(red <= green && red <= blue){
        red+=5;
    }
    else if(green <= red && green <= blue){
        green+=30;
    }
    else{
        blue+=30;
    }

    return 0xFF000000 + (red << 16) + (green << 8) + blue;
}

public static void main(String[] args) {
    new ChristmasTree();
}
}

L'avantage de cette approche est le fait qu'il sera probablement travailler avec des images contenant d'autres objets lumineux car il analyse la forme de l'objet.

Joyeux Noël!

---

MODIFIER LA NOTE 2

Il y a une discussion à propos de la similitude des images de sortie de cette solution, et quelques autres. En fait, ils sont très similaires. Mais cette approche n'est pas seulement le segment des objets. Il analyse également l'objet de formes, dans un certain sens. Il peut traiter plusieurs objets lumineux dans la même scène. En fait, l'arbre de Noël n'a pas besoin d'être la plus brillante. Je suis juste abording d'enrichir la discussion. Il existe un biais dans les échantillons que juste à la recherche pour les objets les plus brillants, vous trouverez les arbres. Mais, ne nous en voulez vraiment arrêter la discussion à ce point? À ce stade, à quelle distance de l'ordinateur est vraiment reconnaître un objet qui ressemble à un arbre de Noël? Nous allons tenter de combler cet écart.

Ci-dessous est présenté un résultat juste pour élucider ce point:

l'image d'entrée

sortie

Answer 3

Voici mon simple et stupide solution. Il est basé sur l'hypothèse que l'arbre sera la plus brillante et la grande chose dans l'image.

//g++ -Wall -pedantic -ansi -O2 -pipe -s -o christmas_tree christmas_tree.cpp `pkg-config --cflags --libs opencv`
#include <opencv2/imgproc/imgproc.hpp>
#include <opencv2/highgui/highgui.hpp>
#include <iostream>

using namespace cv;
using namespace std;

int main(int argc,char *argv[])
{
    Mat original,tmp,tmp1;
    vector <vector<Point> > contours;
    Moments m;
    Rect boundrect;
    Point2f center;
    double radius, max_area=0,tmp_area=0;
    unsigned int j, k;
    int i;

    for(i = 1; i < argc; ++i)
    {
        original = imread(argv[i]);
        if(original.empty())
        {
            cerr << "Error"<<endl;
            return -1;
        }

        GaussianBlur(original, tmp, Size(3, 3), 0, 0, BORDER_DEFAULT);
        erode(tmp, tmp, Mat(), Point(-1, -1), 10);
        cvtColor(tmp, tmp, CV_BGR2HSV);
        inRange(tmp, Scalar(0, 0, 0), Scalar(180, 255, 200), tmp);

        dilate(original, tmp1, Mat(), Point(-1, -1), 15);
        cvtColor(tmp1, tmp1, CV_BGR2HLS);
        inRange(tmp1, Scalar(0, 185, 0), Scalar(180, 255, 255), tmp1);
        dilate(tmp1, tmp1, Mat(), Point(-1, -1), 10);

        bitwise_and(tmp, tmp1, tmp1);

        findContours(tmp1, contours, CV_RETR_EXTERNAL, CV_CHAIN_APPROX_SIMPLE);
        max_area = 0;
        j = 0;
        for(k = 0; k < contours.size(); k++)
        {
            tmp_area = contourArea(contours[k]);
            if(tmp_area > max_area)
            {
                max_area = tmp_area;
                j = k;
            }
        }
        tmp1 = Mat::zeros(original.size(),CV_8U);
        approxPolyDP(contours[j], contours[j], 30, true);
        drawContours(tmp1, contours, j, Scalar(255,255,255), CV_FILLED);

        m = moments(contours[j]);
        boundrect = boundingRect(contours[j]);
        center = Point2f(m.m10/m.m00, m.m01/m.m00);
        radius = (center.y - (boundrect.tl().y))/4.0*3.0;
        Rect heightrect(center.x-original.cols/5, boundrect.tl().y, original.cols/5*2, boundrect.size().height);

        tmp = Mat::zeros(original.size(), CV_8U);
        rectangle(tmp, heightrect, Scalar(255, 255, 255), -1);
        circle(tmp, center, radius, Scalar(255, 255, 255), -1);

        bitwise_and(tmp, tmp1, tmp1);

        findContours(tmp1, contours, CV_RETR_EXTERNAL, CV_CHAIN_APPROX_SIMPLE);
        max_area = 0;
        j = 0;
        for(k = 0; k < contours.size(); k++)
        {
            tmp_area = contourArea(contours[k]);
            if(tmp_area > max_area)
            {
                max_area = tmp_area;
                j = k;
            }
        }

        approxPolyDP(contours[j], contours[j], 30, true);
        convexHull(contours[j], contours[j]);

        drawContours(original, contours, j, Scalar(0, 0, 255), 3);

        namedWindow(argv[i], CV_WINDOW_NORMAL|CV_WINDOW_KEEPRATIO|CV_GUI_EXPANDED);
        imshow(argv[i], original);

        waitKey(0);
        destroyWindow(argv[i]);
    }

    return 0;
}

La première étape est de détecter le plus lumineux de pixels dans l'image, mais nous devons faire une distinction entre l'arbre lui-même et la neige qui reflètent la lumière. Ici, nous essayons de les exclure de la neige appling vraiment un simple filtre sur les codes de la couleur:

GaussianBlur(original, tmp, Size(3, 3), 0, 0, BORDER_DEFAULT);
erode(tmp, tmp, Mat(), Point(-1, -1), 10);
cvtColor(tmp, tmp, CV_BGR2HSV);
inRange(tmp, Scalar(0, 0, 0), Scalar(180, 255, 200), tmp);

Ensuite, nous trouvons tous les "lumineux" pixel:

dilate(original, tmp1, Mat(), Point(-1, -1), 15);
cvtColor(tmp1, tmp1, CV_BGR2HLS);
inRange(tmp1, Scalar(0, 185, 0), Scalar(180, 255, 255), tmp1);
dilate(tmp1, tmp1, Mat(), Point(-1, -1), 10);

Enfin, nous nous joignons les deux résultats:

bitwise_and(tmp, tmp1, tmp1);

Maintenant, nous attendons pour le plus grand objet brillant:

findContours(tmp1, contours, CV_RETR_EXTERNAL, CV_CHAIN_APPROX_SIMPLE);
max_area = 0;
j = 0;
for(k = 0; k < contours.size(); k++)
{
    tmp_area = contourArea(contours[k]);
    if(tmp_area > max_area)
    {
        max_area = tmp_area;
        j = k;
    }
}
tmp1 = Mat::zeros(original.size(),CV_8U);
approxPolyDP(contours[j], contours[j], 30, true);
drawContours(tmp1, contours, j, Scalar(255,255,255), CV_FILLED);

Maintenant, nous avons presque terminé, mais il reste encore quelques imperfections à cause de la neige. Pour les couper, nous allons créer un masque à l'aide d'un cercle et un rectangle de rapprocher la forme d'un arbre de supprimer des morceaux:

m = moments(contours[j]);
boundrect = boundingRect(contours[j]);
center = Point2f(m.m10/m.m00, m.m01/m.m00);
radius = (center.y - (boundrect.tl().y))/4.0*3.0;
Rect heightrect(center.x-original.cols/5, boundrect.tl().y, original.cols/5*2, boundrect.size().height);

tmp = Mat::zeros(original.size(), CV_8U);
rectangle(tmp, heightrect, Scalar(255, 255, 255), -1);
circle(tmp, center, radius, Scalar(255, 255, 255), -1);

bitwise_and(tmp, tmp1, tmp1);

La dernière étape est de trouver le contour de notre arbre et de le dessiner sur l'image d'origine.

findContours(tmp1, contours, CV_RETR_EXTERNAL, CV_CHAIN_APPROX_SIMPLE);
max_area = 0;
j = 0;
for(k = 0; k < contours.size(); k++)
{
    tmp_area = contourArea(contours[k]);
    if(tmp_area > max_area)
    {
        max_area = tmp_area;
        j = k;
    }
}

approxPolyDP(contours[j], contours[j], 30, true);
convexHull(contours[j], contours[j]);

drawContours(original, contours, j, Scalar(0, 0, 255), 3);

Je suis désolé, mais pour le moment j'ai une mauvaise connexion de sorte qu'il n'est pas possible pour moi de télécharger des photos. Je vais essayer de le faire plus tard.

Joyeux Noël.

EDIT:

Voici quelques photos de la sortie finale:

Answer 4

J'ai écrit le code en Matlab R2007a. J'ai utilisé des k-means à peu près extrait de l'arbre de noël. J' va montrer mon résultat intermédiaire avec une seule image, et les résultats finaux avec les six.

Tout d'abord, je l'ai associé l'espace RVB sur l'espace de Laboratoire, ce qui pourrait améliorer le contraste de rouge dans son canal b:

colorTransform = makecform('srgb2lab');
I = applycform(I, colorTransform);
L = double(I(:,:,1));
a = double(I(:,:,2));
b = double(I(:,:,3));

En plus de la fonction dans l'espace de couleur, j'ai aussi utilisé la texture de la fonctionnalité qui est en rapport avec le quartier plutôt que chaque pixel lui-même. Ici, je linéaire combinée de l'intensité de la 3 original canaux (R,G,B). La raison pour laquelle j'ai formaté de cette manière est parce que les fêtes de noël les arbres dans l'image ont tous feux rouges sur eux, et parfois vert/bleu l'éclairage ainsi.

R=double(Irgb(:,:,1));
G=double(Irgb(:,:,2));
B=double(Irgb(:,:,3));
I0 = (3*R + max(G,B)-min(G,B))/2;

J'ai appliqué un 3X3 local binary pattern sur I0, utilisé le centre de pixels que le seuil, et obtenu le contraste en calculant la différence entre la moyenne de la valeur d'intensité de pixel au-dessus du seuil et la valeur moyenne au-dessous.

I0_copy = zeros(size(I0));
for i = 2 : size(I0,1) - 1
    for j = 2 : size(I0,2) - 1
        tmp = I0(i-1:i+1,j-1:j+1) >= I0(i,j);
        I0_copy(i,j) = mean(mean(tmp.*I0(i-1:i+1,j-1:j+1))) - ...
            mean(mean(~tmp.*I0(i-1:i+1,j-1:j+1))); % Contrast
    end
end

Depuis que j'ai 4 dispose au total, j'ai choisi de K=5 dans ma méthode de clustering. Le code de k-means sont présentés ci-dessous (c'est à partir de Dr Andrew Ng lavable en cours d'apprentissage. J'ai pris le cours avant, et j'ai écrit le code moi-même, dans sa programmation, la cession).

[centroids, idx] = runkMeans(X, initial_centroids, max_iters);
mask=reshape(idx,img_size(1),img_size(2));

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function [centroids, idx] = runkMeans(X, initial_centroids, ...
                                  max_iters, plot_progress)
   [m n] = size(X);
   K = size(initial_centroids, 1);
   centroids = initial_centroids;
   previous_centroids = centroids;
   idx = zeros(m, 1);

   for i=1:max_iters    
      % For each example in X, assign it to the closest centroid
      idx = findClosestCentroids(X, centroids);

      % Given the memberships, compute new centroids
      centroids = computeCentroids(X, idx, K);

   end
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function idx = findClosestCentroids(X, centroids)
   K = size(centroids, 1);
   idx = zeros(size(X,1), 1);
   for xi = 1:size(X,1)
      x = X(xi, :);
      % Find closest centroid for x.
      best = Inf;
      for mui = 1:K
        mu = centroids(mui, :);
        d = dot(x - mu, x - mu);
        if d < best
           best = d;
           idx(xi) = mui;
        end
      end
   end 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function centroids = computeCentroids(X, idx, K)
   [m n] = size(X);
   centroids = zeros(K, n);
   for mui = 1:K
      centroids(mui, :) = sum(X(idx == mui, :)) / sum(idx == mui);
   end

Depuis que le programme s'exécute très lentement dans mon ordinateur, j'ai juste couru 3 itérations. Normalement l'arrêt les critères (i) d'itération de temps, au moins 10, ou (ii) pas de changement sur les centroïdes. Pour mon test, l'augmentation de l'itération peut différencier le fond (ciel et des arbres, du ciel et de bâtiment,...) avec plus de précision, mais ne montrent pas de changements radicaux dans l'arbre de noël extraction. Notez aussi k-means est pas à l'abri de l'aléatoire centre de gravité de l'initialisation, le fait d'exécuter le programme plusieurs fois pour faire une comparaison est recommandé.

Après le k-means, labellisés de la région avec le maximum d'intensité de l' I0 a été choisi. Et limite de traçage a été utilisé pour extrait les limites. Pour moi, le dernier arbre de noël est le plus difficile à extraire depuis le contraste de cette image n'est pas assez élevée, car ils sont dans les cinq premiers. Un autre problème dans ma méthode, c'est que j'ai utilisé bwboundaries fonction dans Matlab pour tracer la frontière, mais parfois à l'intérieur des limites sont également inclus comme vous pouvez le constater dans la 3ème, 5ème, 6ème résultats. Le côté obscur dans les arbres de noël ne sont pas seulement échoué à être regroupés avec le côté illuminé, mais ils conduisent également à donc beaucoup de petits intérieure limites de traçage (imfill ne s'améliore pas beaucoup). Dans tous mes algorithme a encore beaucoup d'amélioration de l'espace.

Certains de la publications indique que mean-shift peut être plus robuste que k-means, et de nombreux graph-cut algorithmes sont aussi très compétitive sur les limites compliqué la segmentation. J'ai écrit un mean-shift algorithme de moi-même, il semble de mieux en extraire les régions sans assez de lumière. Mais mean-shift est un peu plus segmenté, et certains de la stratégie de la fusion est nécessaire. Il courut même beaucoup plus lent que k-means dans mon ordinateur, je crains d'avoir à l'abandonner. J'ai attendons avec impatience de voir d'autres pourraient présenter d'excellents résultats ici avec ces algorithmes modernes mentionnés ci-dessus.

Mais je crois toujours à la fonction de sélection est l'élément clé de la segmentation d'images. Avec une bonne sélection de fonctionnalités qui peuvent maximiser la marge entre l'objet et le fond, de nombreux des algorithmes de segmentation sera certainement le travail. Différents algorithmes peuvent améliorer le résultat de 1 à 10, mais la fonctionnalité de sélection peut l'améliorer de 0 à 1.

Joyeux Noël !

Answer 5

Ceci est mon dernier post à l'aide de l'image traditionnelle de traitement des approches...

Ici j'ai un peu de combiner mes deux autres propositions, d'atteindre des résultats encore meilleurs. Comme une question de fait, je ne vois pas comment ces résultats pourrait être mieux (surtout quand on regarde les images masquées que la méthode produit).

Au cœur de la démarche est la combinaison de trois hypothèses principales:

1. Les Images doivent avoir de fortes fluctuations dans l'arbre des régions
2. Les Images doivent avoir une intensité plus élevée dans l'arbre des régions
3. Fond régions de faible intensité et surtout bleu-ish

Avec ces hypothèses à l'esprit la méthode fonctionne de la manière suivante:

1. Convertir les images à HSV
2. Filtrer les V canal avec un filtre de Journal
3. Appliquer seuillage dur sur Journal d'image filtrée pour obtenir une 'activité' Un masque
4. Appliquer seuillage dur à V canal pour obtenir l'intensité masque B
5. Appliquer H canal de seuillage pour la capture de faible intensité bleu-ish régions en arrière-plan masque C
6. Combiner des masques à l'aide ET à obtenir le final du masque
7. Dilater le masque pour agrandir les régions et les connecter dispersés pixels
8. Éliminer les petites régions et le dernier masque qui finira par représenter seul l'arbre

Voici le code en MATLAB (encore une fois, le script charge toutes les images jpg dans le dossier actuel et, encore une fois, c'est loin d'être optimisé morceau de code):

% clear everything
clear;
pack;
close all;
close all hidden;
drawnow;
clc;

% initialization
ims=dir('./*.jpg');
imgs={};
images={}; 
blur_images={}; 
log_image={}; 
dilated_image={};
int_image={};
back_image={};
bin_image={};
measurements={};
box={};
num=length(ims);
thres_div = 3;

for i=1:num, 
    % load original image
    imgs{end+1}=imread(ims(i).name);

    % convert to HSV colorspace
    images{end+1}=rgb2hsv(imgs{i});

    % apply laplacian filtering and heuristic hard thresholding
    val_thres = (max(max(images{i}(:,:,3)))/thres_div);
    log_image{end+1} = imfilter( images{i}(:,:,3),fspecial('log')) > val_thres;

    % get the most bright regions of the image
    int_thres = 0.26*max(max( images{i}(:,:,3)));
    int_image{end+1} = images{i}(:,:,3) > int_thres;

    % get the most probable background regions of the image
    back_image{end+1} = images{i}(:,:,1)>(150/360) & images{i}(:,:,1)<(320/360) & images{i}(:,:,3)<0.5;

    % compute the final binary image by combining 
    % high 'activity' with high intensity
    bin_image{end+1} = logical( log_image{i}) & logical( int_image{i}) & ~logical( back_image{i});

    % apply morphological dilation to connect distonnected components
    strel_size = round(0.01*max(size(imgs{i})));        % structuring element for morphological dilation
    dilated_image{end+1} = imdilate( bin_image{i}, strel('disk',strel_size));

    % do some measurements to eliminate small objects
    measurements{i} = regionprops( logical( dilated_image{i}),'Area','BoundingBox');

    % iterative enlargement of the structuring element for better connectivity
    while length(measurements{i})>14 && strel_size<(min(size(imgs{i}(:,:,1)))/2),
        strel_size = round( 1.5 * strel_size);
        dilated_image{i} = imdilate( bin_image{i}, strel('disk',strel_size));
        measurements{i} = regionprops( logical( dilated_image{i}),'Area','BoundingBox');
    end

    for m=1:length(measurements{i})
        if measurements{i}(m).Area < 0.05*numel( dilated_image{i})
            dilated_image{i}( round(measurements{i}(m).BoundingBox(2):measurements{i}(m).BoundingBox(4)+measurements{i}(m).BoundingBox(2)),...
                round(measurements{i}(m).BoundingBox(1):measurements{i}(m).BoundingBox(3)+measurements{i}(m).BoundingBox(1))) = 0;
        end
    end
    % make sure the dilated image is the same size with the original
    dilated_image{i} = dilated_image{i}(1:size(imgs{i},1),1:size(imgs{i},2));
    % compute the bounding box
    [y,x] = find( dilated_image{i});
    if isempty( y)
        box{end+1}=[];
    else
        box{end+1} = [ min(x) min(y) max(x)-min(x)+1 max(y)-min(y)+1];
    end
end 

%%% additional code to display things
for i=1:num,
    figure;
    subplot(121);
    colormap gray;
    imshow( imgs{i});
    if ~isempty(box{i})
        hold on;
        rr = rectangle( 'position', box{i});
        set( rr, 'EdgeColor', 'r');
        hold off;
    end
    subplot(122);
    imshow( imgs{i}.*uint8(repmat(dilated_image{i},[1 1 3])));
end

Résultats

Résultats haute résolution encore disponible ici!
Encore plus d'expériences avec d'autres images peuvent être trouvés ici.