Comment détecter un arbre de Noël? [fermé]

382

Quelles techniques de traitement d'image pourraient être utilisées pour implémenter une application qui détecte les arbres de Noël affichés dans les images suivantes?

Je recherche des solutions qui vont fonctionner sur toutes ces images. Par conséquent, les approches qui nécessitent une formation sur les classificateurs en cascade ou la mise en correspondance de modèles ne sont pas très intéressantes.

Je cherche quelque chose qui peut être écrit dans n'importe quel langage de programmation, tant qu'il n'utilise que des technologies Open Source . La solution doit être testée avec les images partagées sur cette question. Il y a 6 images d'entrée et la réponse doit afficher les résultats du traitement de chacune d'entre elles. Enfin, pour chaque image de sortie, il doit y avoir des lignes rouges dessinées pour entourer l'arbre détecté.

Comment procéderiez-vous pour détecter par programme les arbres de ces images?

karlphillip
la source
3
Sommes-nous autorisés à utiliser certaines des images pour la formation, ou devons-nous utiliser toutes les images fournies pour la validation? Quoi qu'il en soit, compétition cool: D
Hannes Ovrén
7
@karlphillip, voulez-vous que nous utilisions ces images pour les tests et d'autres images pour la formation? C'est juste que ce n'est pas clair ce qu'est l'ensemble d'entraînement.
GilLevi
16
@karlphillip: Mon conseil: abandonnez l'exigence "open source". Peu importe le langage / framework que vous utilisez. Les algorithmes de traitement d'image / vision par ordinateur sont indépendants du langage, donc si vous pouvez l'écrire dans MATLAB, vous pouvez certainement le faire OpenCV ou tout autre framework que vous préférez ... De plus, je ne sais toujours pas ce que vous envisagez de former / tester des images !
Amro
2
@karlphillip merci d'avoir mobilisé chacun d'entre nous pour contribuer à votre «quête»! Cela a été une excellente occasion de passer quelques heures de manière productive, mais surtout, pour voir combien d'approches différentes peuvent être trouvées pour un seul problème ... J'espère que vous le ferez à nouveau pour le 1er janvier (peut-être un traîneau de Le défi du Père Noël? ;-))
sepdek
2
OK, j'ai reformulé la question pour supprimer les éléments du concours. Je pense que cela devrait lui permettre de se débrouiller tout seul.
Brad Larson

Réponses:

184

J'ai une approche qui me semble intéressante et un peu différente des autres. La principale différence dans mon approche, par rapport à certaines autres, réside dans la façon dont l'étape de segmentation de l'image est effectuée - j'ai utilisé le DBSCAN algorithme de clustering de scikit-learn de Python; il est optimisé pour trouver des formes quelque peu amorphes qui n'ont pas nécessairement un seul centroïde clair.

Au niveau supérieur, mon approche est assez simple et peut être décomposée en environ 3 étapes. D'abord j'applique un seuil (ou en fait, le "ou" logique de deux seuils séparés et distincts). Comme pour beaucoup d'autres réponses, j'ai supposé que l'arbre de Noël serait l'un des objets les plus brillants de la scène, donc le premier seuil n'est qu'un simple test de luminosité monochrome; tous les pixels avec des valeurs supérieures à 220 sur une échelle de 0 à 255 (où le noir est 0 et le blanc 255) sont enregistrés dans une image binaire en noir et blanc. Le deuxième seuil tente de rechercher des lumières rouges et jaunes, qui sont particulièrement importantes dans les arbres en haut à gauche et en bas à droite des six images, et se détachent bien sur le fond bleu-vert qui prévaut dans la plupart des photos. Je convertis l'image rgb en espace hsv, et exigent que la teinte soit inférieure à 0,2 sur une échelle de 0,0 à 1,0 (correspondant à peu près à la frontière entre le jaune et le vert) ou supérieure à 0,95 (correspondant à la frontière entre le violet et le rouge) et en outre, j'ai besoin de couleurs vives et saturées: la saturation et la valeur doivent toutes deux être supérieures à 0,7. Les résultats des deux procédures de seuil sont logiquement "ou" -ed ensemble, et la matrice résultante d'images binaires en noir et blanc est présentée ci-dessous:

Arbres de Noël, après seuillage sur HSV ainsi que luminosité monochrome

Vous pouvez clairement voir que chaque image a un grand groupe de pixels correspondant approximativement à l'emplacement de chaque arbre, et quelques-unes des images ont également d'autres petits groupes correspondant soit à des lumières dans les fenêtres de certains bâtiments, soit à un scène de fond à l'horizon. L'étape suivante consiste à faire reconnaître à l'ordinateur qu'il s'agit de clusters distincts et à étiqueter correctement chaque pixel avec un numéro d'ID d'appartenance au cluster.

Pour cette tâche, j'ai choisi DBSCAN . Il existe une assez bonne comparaison visuelle de la façon dont DBSCAN se comporte généralement, par rapport aux autres algorithmes de clustering, disponibles ici . Comme je l'ai dit plus tôt, il se marie bien avec les formes amorphes. La sortie de DBSCAN, avec chaque cluster tracé dans une couleur différente, est affichée ici:

Sortie de clustering DBSCAN

Il y a quelques points à prendre en compte lorsque l'on regarde ce résultat. Premièrement, DBSCAN oblige l'utilisateur à définir un paramètre de «proximité» afin de réguler son comportement, qui contrôle efficacement la séparation d'une paire de points pour que l'algorithme déclare un nouveau cluster séparé plutôt que d'agglomérer un point de test sur un cluster déjà préexistant. J'ai défini cette valeur à 0,04 fois la taille le long de la diagonale de chaque image. Étant donné que la taille des images varie d'environ VGA à environ HD 1080, ce type de définition relative à l'échelle est essentiel.

Un autre point à noter est que l'algorithme DBSCAN tel qu'il est implémenté dans scikit-learn a des limites de mémoire qui sont assez difficiles pour certaines des images plus grandes de cet exemple. Par conséquent, pour quelques-unes des images plus grandes, j'ai dû "décimer" (c'est-à-dire ne conserver que tous les 3 ou 4 pixels et supprimer les autres) chaque cluster afin de rester dans cette limite. À la suite de ce processus d'élimination, les pixels épars individuels restants sont difficiles à voir sur certaines des images plus grandes. Par conséquent, à des fins d'affichage uniquement, les pixels codés par couleur dans les images ci-dessus ont été effectivement "légèrement dilatés" juste de sorte qu'ils ressortent mieux. C'est purement une opération cosmétique pour le bien du récit; bien qu'il y ait des commentaires mentionnant cette dilatation dans mon code,

Une fois les clusters identifiés et étiquetés, la troisième et dernière étape est facile: 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 pixels membres, bien que l'on puisse ont tout aussi facilement utilisé à la place un type de métrique qui mesure l'étendue physique) et calculent la coque convexe pour ce cluster. La coque convexe devient alors la bordure de l'arbre. Les six coques convexes calculées via cette méthode sont représentées ci-dessous en rouge:

Arbres de Noël avec leurs bordures calculées

Le code source est écrit pour Python 2.7.6 et il dépend de numpy , scipy , matplotlib et scikit-learn . Je l'ai divisé en deux parties. La première partie est responsable du traitement réel 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 script de niveau utilisateur qui appelle le premier fichier et génère tous les tracés 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()
stachyra
la source
La solution de @ lennon310 est le clustering. (k-means)
user3054997
1
@stachyra J'ai également réfléchi à cette approche avant d'en proposer les plus simples. Je pense que cela a un grand potentiel d'être étendu et généralisé pour produire de bons résultats dans d'autres cas également. Vous pouvez expérimenter avec des réseaux de neurones pour le clustering. Quelque chose comme un SOM ou un gaz neuronal ferait un excellent travail. Néanmoins, bonne proposition et bravo de ma part!
septembre
4
@Faust & Ryan Carlson: merci les gars! Oui, je suis d'accord pour dire que le système de vote positif, bien qu'il fonctionne bien pour juger entre 2 ou 3 réponses courtes toutes soumises en quelques heures les unes des autres, présente de sérieux biais lorsqu'il s'agit de concours avec des réponses longues qui se déroulent sur de longues périodes. . D'une part, les premières soumissions commencent à accumuler des votes positifs avant que les derniers ne soient même disponibles pour examen public. Et si les réponses sont toutes longues, alors dès que l'on établit une avance modeste, il y a souvent un «effet de marche en avant» car les gens ne votent que le premier sans prendre la peine de lire le reste.
stachyra
2
@stachyra grande nouvelle ami! Félicitations les plus chaleureuses et que cela marque le début de votre nouvelle année!
sepdek
1
@ lennon310: Je n'ai pas encore essayé de filtre de détection maximum local sur ce problème, mais si vous voulez l'explorer vous-même, scipy inclut celui-ci . Mon code source Python pour ce projet était si court que j'ai pu en publier 100%; littéralement, tout ce que vous devez faire est de copier-coller mes deux extraits de code dans des fichiers .py distincts, puis de substituer un appel à scipy.ndimage.filters.maximum_filter()au même endroit où j'avais utilisé un seuil.
stachyra
145

MODIFIER LA NOTE: J'ai édité ce post pour (i) traiter chaque image d'arbre individuellement, comme demandé dans les exigences, (ii) pour prendre en compte la luminosité et la forme de l'objet afin d'améliorer la qualité du résultat.


Ci-dessous est présentée une approche qui prend en considération la luminosité et la forme de l'objet. En d'autres termes, il recherche des objets de forme triangulaire et de luminosité importante. Il a été implémenté en Java, en utilisant le cadre de traitement d'image Marvin .

La première étape est le seuillage des couleurs. L'objectif ici est de concentrer l'analyse sur des objets avec une luminosité importante.

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 brillants de l'image sont dilatés afin de former des formes. Le résultat de ce processus est la forme probable des objets avec une luminosité importante. En appliquant une segmentation de remplissage, les formes déconnectées sont détectées.

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 le montre l'image de sortie, plusieurs formes ont été détectées. 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ée. Un algorithme simple détecte les formes avec un motif similaire à un triangle. L'algorithme analyse la forme de l'objet ligne par ligne. Si le centre de la masse de chaque ligne de forme est presque le même (étant donné un seuil) et que la masse augmente à mesure que y augmente, l'objet a une forme de triangle. La masse de la ligne de forme est le nombre de pixels de cette ligne qui appartiennent à la forme. Imaginez que vous coupez l'objet horizontalement et analysez chaque segment horizontal. S'ils sont centralisés les uns aux autres et que la longueur augmente du premier au dernier segment dans un motif linéaire, vous avez 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 similaire à un triangle et avec une luminosité importante, dans ce cas un arbre de Noël, est mise en évidence dans l'image d'origine, comme illustré ci-dessous.

images de sortie finale:

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 qu'elle fonctionnera probablement avec des images contenant d'autres objets lumineux car elle analyse la forme de l'objet.

Joyeux Noël!


MODIFIER LA NOTE 2

Il y a une discussion sur la similitude des images de sortie de cette solution et de quelques autres. En fait, ils sont très similaires. Mais cette approche ne se contente pas de segmenter les objets. Il analyse également les formes des objets dans un certain sens. Il peut gérer plusieurs objets lumineux dans la même scène. En fait, l'arbre de Noël n'a pas besoin d'être le plus brillant. Je ne fais que l'aborder pour enrichir la discussion. Il y a un biais dans les échantillons qui, à la recherche de l'objet le plus brillant, vous trouverez les arbres. Mais, voulons-nous vraiment arrêter la discussion à ce stade? À ce stade, dans quelle mesure l'ordinateur reconnaît-il vraiment un objet qui ressemble à un arbre de Noël? Essayons de combler cet écart.

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

image d'entrée

entrez la description de l'image ici

production

entrez la description de l'image ici

Gabriel Ambrósio Archanjo
la source
2
C'est intéressant. J'espère que vous pourrez obtenir les mêmes résultats lorsque chaque image est traitée individuellement. J'ai édité la question 4 heures auparavant pour vous poster la réponse pour le dire spécifiquement. Ce serait génial si vous pouviez mettre à jour votre réponse avec ces résultats.
karlphillip
@Marvin dans votre détection de triangle, comment avez-vous géré la fluctuation de masse? Ce n'est pas un triangle strict, la masse n'est pas mono car y change
user3054997
2
@ user3054997: C'est un autre point. Comme je l'ai signalé, l'algorithme ne cherche pas les formes triangulaires strictes. Il analyse chaque objet et considère un arbre qui "ressemble" à un triangle avec un critère simple: la masse de l'objet est utilisée pour augmenter à mesure que y augmente et le centre de la masse de chaque segment d'objet horizontal est presque centralisé les uns par rapport aux autres .
Gabriel Ambrósio Archanjo
@Marvin Ma solution est vraiment simple, je l'ai aussi dit dans ma réponse. Au fait, cela a mieux fonctionné que votre première solution. Si je me souviens bien, dans votre première réponse, vous avez parlé de descripteurs de fonctionnalités pour détecter les petites textures légères, ce qui n'est pas ce que vous faites ici. J'ai simplement dit que votre approche et vos résultats actuels sont beaucoup plus similaires aux miens qu'à votre première solution. Bien sûr, je ne m'attends pas à ce que vous l'admettiez, je l'ai déclaré juste pour mémoire.
smeso
1
@sepdek Il y a ici quelques solutions qui sont vraiment bien meilleures que la mienne et elles reçoivent toujours la moitié de mes votes positifs. Il n'y a rien de mal à "s'inspirer" d'autres solutions. J'ai vu tes solutions aussi, je n'ai rien à dire contre toi, tu les as postées après moi et mon "idée" n'était pas si originale de dire que tu viens de me copier. Mais Marvin était le seul qui a posté avant moi et édité sa solution après avoir vu le mien en utilisant le même algorithme ... au moins il aurait pu dire "Ouais, j'ai aimé ta solution et je l'ai réutilisée" il n'y a rien de mal, c'est juste un jeu.
smeso
75

Voici ma solution simple et stupide. Il est basé sur l'hypothèse que l'arbre sera la chose la plus lumineuse et la plus grande de 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 consiste à détecter les pixels les plus brillants de l'image, mais nous devons faire une distinction entre l'arbre lui-même et la neige qui réfléchit sa lumière. Ici, nous essayons d'exclure la neige en appliquant un filtre très simple sur les codes de 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 chaque pixel "lumineux":

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 joignons les deux résultats:

bitwise_and(tmp, tmp1, tmp1);

Maintenant, nous recherchons le plus grand objet lumineux:

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 y a encore quelques imperfections dues à la neige. Pour les couper, nous allons construire un masque en utilisant un cercle et un rectangle pour approximer la forme d'un arbre pour supprimer les pièces indésirables:

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 consiste à trouver le contour de notre arbre et à le dessiner sur l'image originale.

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 donc il ne m'est pas possible de télécharger des photos. J'essaierai de le faire plus tard.

Joyeux Noël.

ÉDITER:

Voici quelques photos de la sortie finale:

smeso
la source
1
salut! Assurez-vous que votre réponse respecte toutes les exigences: il y a 6 images d'entrée et la réponse doit afficher les résultats du traitement de chacune d'entre elles; .
karlphillip
Salut! Vous pouvez passer les noms de fichiers comme arguments CLI à mon programme: ./christmas_tree ./*.png. Ils peuvent être autant que vous le souhaitez, les résultats seront affichés l'un après l'autre en appuyant sur n'importe quelle touche. Est-ce mal?
smeso
C'est OK, mais vous devez toujours télécharger les images et les partager dans votre question afin que les téléspectateurs du fil puissent réellement voir votre résultat. Laisser les gens voir ce que vous avez fait améliorera vos chances d'obtenir des votes;)
karlphillip
J'essaie de trouver une solution à cela, j'ai des problèmes de connectivité.
smeso
2
Génial! Vous pouvez maintenant les redimensionner à l'intérieur de la réponse avec le code suivant: Modifiez <img src="http://i.stack.imgur.com/nmzwj.png" width="210" height="150">simplement le lien vers l'image;)
karlphillip
60

J'ai écrit le code dans Matlab R2007a. J'ai utilisé k-means pour extraire grossièrement l'arbre de Noël. Je ne montrerai mon résultat intermédiaire qu'avec une seule image et les résultats finaux avec les six.

Tout d'abord, j'ai mappé l'espace RVB sur l'espace Lab, ce qui pourrait améliorer le contraste du rouge dans son canal b:

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

entrez la description de l'image ici

Outre la fonction dans l'espace colorimétrique, j'ai également utilisé une fonction de texture qui est pertinente avec le quartier plutôt qu'avec chaque pixel lui-même. Ici, j'ai combiné linéairement l'intensité des 3 canaux originaux (R, G, B). La raison pour laquelle j'ai formaté de cette façon est que les arbres de Noël sur l'image ont tous des lumières rouges et parfois un éclairage vert / parfois bleu.

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

entrez la description de l'image ici

J'ai appliqué un motif binaire local 3X3 I0, utilisé le pixel central comme seuil et obtenu le contraste en calculant la différence entre la valeur d'intensité moyenne du pixel au-dessus du seuil et la valeur moyenne en 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

entrez la description de l'image ici

Étant donné que j'ai 4 fonctionnalités au total, je choisirais K = 5 dans ma méthode de clustering. Le code pour k-means est indiqué ci-dessous (il provient du cours d'apprentissage automatique du Dr Andrew Ng. J'ai suivi le cours auparavant et j'ai écrit le code moi-même dans sa tâche de programmation).

[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

Étant donné que le programme s'exécute très lentement sur mon ordinateur, je viens d'exécuter 3 itérations. Normalement, le critère d'arrêt est (i) un temps d'itération d'au moins 10, ou (ii) aucun changement sur les centroïdes. À mon avis, l'augmentation de l'itération peut différencier l'arrière-plan (ciel et arbre, ciel et bâtiment, ...) plus précisément, mais n'a pas montré de changements drastiques dans l'extraction des arbres de Noël. Notez également que k-means n'est pas à l'abri de l'initialisation aléatoire du centroïde, il est donc recommandé d'exécuter le programme plusieurs fois pour faire une comparaison.

Après les k-moyennes, la région marquée avec l'intensité maximale de a I0été choisie. Et le traçage des limites a été utilisé pour extraire les limites. Pour moi, le dernier arbre de Noël est le plus difficile à extraire car le contraste de cette image n'est pas assez élevé comme dans les cinq premiers. Un autre problème dans ma méthode est que j'ai utilisé la bwboundariesfonction dans Matlab pour tracer la frontière, mais parfois les frontières intérieures sont également incluses comme vous pouvez le constater dans les résultats des 3e, 5e et 6e. Le côté sombre à l'intérieur des arbres de Noël n'est pas seulement échoué à être agrégé avec le côté illuminé, mais il conduit également à de nombreuses minuscules traces de limites intérieures ( imfillne s'améliore pas beaucoup). Dans l'ensemble, mon algorithme a encore beaucoup d'espace d'amélioration.

Certaines publications indiquent que le décalage moyen peut être plus robuste que les moyennes k, et de nombreux algorithmes basés sur la coupe graphique sont également très compétitifs sur la segmentation complexe des frontières. J'ai écrit moi-même un algorithme de décalage moyen, il semble mieux extraire les régions sans assez de lumière. Mais le décalage moyen est un peu sur-segmenté et une stratégie de fusion est nécessaire. Il fonctionnait encore plus lentement que k-means sur mon ordinateur, je crains de devoir y renoncer. J'ai hâte de voir que d'autres soumettraient ici d'excellents résultats avec les algorithmes modernes mentionnés ci-dessus.

Pourtant, je crois toujours que la sélection des fonctionnalités est l'élément clé de la segmentation d'image. Avec une sélection de fonctionnalités appropriée qui peut maximiser la marge entre l'objet et l'arrière-plan, de nombreux algorithmes de segmentation fonctionneront certainement. Différents algorithmes peuvent améliorer le résultat de 1 à 10, mais la sélection des fonctionnalités peut l'améliorer de 0 à 1.

Joyeux Noël !

lennon310
la source
2
Merci d'avoir répondu! Je voulais juste souligner que Matlab n'est pas open source , mais Scilab l' est. J'aimerais aussi voir cette réponse concurrencer les autres. ;)
karlphillip
6
Merci Karl. Octave est un autre logiciel open source qui partage presque la même grammaire de codage avec Matlab: mathworks.fr/matlabcentral/answers/14399-gnu-octave-vs-matlab .
lennon310
Intéressant, je ne le savais pas, merci! Votre code fonctionne-t-il sur Octave?
karlphillip
Je n'ai pas encore testé, mais je pense que ce n'est pas un problème :)
lennon310
@ lennon310 Je pense que si vous abandonnez les limites et obtenez la coque convexe, vous vous débarrasserez du problème des trous. N'oubliez pas que la coque convexe est la plus petite zone qui comprend tous les points d'un ensemble.
sepdek du
57

Ceci est mon dernier article en utilisant les approches traditionnelles de traitement d'image ...

Ici, je combine en quelque sorte mes deux autres propositions, obtenant des résultats encore meilleurs . En fait, je ne vois pas comment ces résultats pourraient être meilleurs (surtout quand vous regardez les images masquées que la méthode produit).

Au cœur de l'approche se trouve la combinaison de trois hypothèses clés :

  1. Les images devraient avoir de fortes fluctuations dans les régions arborées
  2. Les images devraient avoir une intensité plus élevée dans les régions arborescentes
  3. Les régions de fond doivent avoir une faible intensité et être principalement bleues

Avec ces hypothèses à l'esprit, la méthode fonctionne comme suit:

  1. Convertissez les images en HSV
  2. Filtrer le canal V avec un filtre LoG
  3. Appliquer un seuil strict sur l'image filtrée LoG pour obtenir le masque «d'activité» A
  4. Appliquer un seuil strict au canal V pour obtenir le masque d'intensité B
  5. Appliquer un seuil de canal H pour capturer les régions bleues de faible intensité dans le masque de fond C
  6. Combinez les masques à l'aide de AND pour obtenir le masque final
  7. Dilatez le masque pour agrandir les régions et connecter les pixels dispersés
  8. Éliminez les petites régions et obtenez le masque final qui ne représentera finalement que l'arbre

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

% 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

Des résultats haute résolution toujours disponibles ici!
Encore plus d'expériences avec des images supplémentaires peuvent être trouvées ici.

sepdek
la source
1
Super truc! Veuillez vous assurer que vos autres réponses suivent également ce format. Pour concourir pour la prime, vous devez utiliser une technologie open source , et malheureusement Matlab n'en fait pas partie. Cependant, SciLab et Octave le sont et fournissent une syntaxe et des fonctions similaires. ;)
karlphillip
Le code d'octave est le même ...
sepdek
@karlphillip D'une manière ou d'une autre, cette question a fini par avoir une balise Matlab. Si l'open source est vraiment un must, je recommanderais de le supprimer.
Dennis Jaheruddin
@sepdek Très bien, peut-être pourrait-on encore faire quelque chose pour inclure les «trous» dans l'image finale. (Ajouter tous les pixels qui sont complètement entourés de pixels approuvés?!)
Dennis Jaheruddin
1
@karlphillip thanx man! Je suis content que vous ayez trouvé mon approche intéressante. De plus, je voudrais vous féliciter d'avoir choisi la solution la plus élégante et non celle qui a recueilli le plus de votes !!!
sepdek
36

Mes étapes de solution:

  1. Get R channel (from RGB) - toutes les opérations que nous effectuons sur ce canal:

  2. Créer une région d'intérêt (ROI)

    • Canal de seuil R avec valeur minimale 149 (image en haut à droite)

    • Dilater la zone de résultat (image du milieu à gauche)

  3. Détectez les eges dans le ROI calculé. L'arbre a beaucoup de bords (image du milieu à droite)

    • Résultat dilaté

    • Érode avec un rayon plus grand (image en bas à gauche)

  4. Sélectionnez le plus grand objet (par zone) - c'est la région de résultat

  5. Coque convexe (l'arbre est un polygone convexe) (image en bas à droite)

  6. Boîte englobante (image en bas à droite - boîte grren)

Pas à pas: entrez la description de l'image ici

Le premier résultat - le plus simple mais pas dans les logiciels open source - "Adaptive Vision Studio + Adaptive Vision Library": Ce n'est pas open source mais vraiment rapide à prototyper:

Algorithme complet pour détecter l'arbre de Noël (11 blocs): Solution AVL

L'étape suivante. Nous voulons une solution open source. Changer les filtres AVL en filtres OpenCV: ici, j'ai fait peu de changements, par exemple, la détection des bords utilise le filtre cvCanny, pour respecter le roi, j'ai multiplié l'image de la région par l'image des bords, pour sélectionner le plus grand élément que j'ai utilisé findContours + contourArea mais l'idée est la même.

https://www.youtube.com/watch?v=sfjB3MigLH0&index=1&list=UUpSRrkMHNHiLDXgylwhWNQQ

Solution OpenCV

Je ne peux pas montrer d'images avec des étapes intermédiaires maintenant car je ne peux mettre que 2 liens.

Ok maintenant nous utilisons des filtres openSource mais ce n'est pas encore tout open source. Dernière étape - portez sur le code c ++. J'ai utilisé OpenCV dans la version 2.4.4

Le résultat du code c ++ final est: entrez la description de l'image ici

Le code c ++ est également assez court:

#include "opencv2/highgui/highgui.hpp"
#include "opencv2/opencv.hpp"
#include <algorithm>
using namespace cv;

int main()
{

    string images[6] = {"..\\1.png","..\\2.png","..\\3.png","..\\4.png","..\\5.png","..\\6.png"};

    for(int i = 0; i < 6; ++i)
    {
        Mat img, thresholded, tdilated, tmp, tmp1;
        vector<Mat> channels(3);

        img = imread(images[i]);
        split(img, channels);
        threshold( channels[2], thresholded, 149, 255, THRESH_BINARY);                      //prepare ROI - threshold
        dilate( thresholded, tdilated,  getStructuringElement( MORPH_RECT, Size(22,22) ) ); //prepare ROI - dilate
        Canny( channels[2], tmp, 75, 125, 3, true );    //Canny edge detection
        multiply( tmp, tdilated, tmp1 );    // set ROI

        dilate( tmp1, tmp, getStructuringElement( MORPH_RECT, Size(20,16) ) ); // dilate
        erode( tmp, tmp1, getStructuringElement( MORPH_RECT, Size(36,36) ) ); // erode

        vector<vector<Point> > contours, contours1(1);
        vector<Point> convex;
        vector<Vec4i> hierarchy;
        findContours( tmp1, contours, hierarchy, CV_RETR_TREE, CV_CHAIN_APPROX_SIMPLE, Point(0, 0) );

        //get element of maximum area
        //int bestID = std::max_element( contours.begin(), contours.end(), 
        //  []( const vector<Point>& A, const vector<Point>& B ) { return contourArea(A) < contourArea(B); } ) - contours.begin();

            int bestID = 0;
        int bestArea = contourArea( contours[0] );
        for( int i = 1; i < contours.size(); ++i )
        {
            int area = contourArea( contours[i] );
            if( area > bestArea )
            {
                bestArea  = area;
                bestID = i;
            }
        }

        convexHull( contours[bestID], contours1[0] ); 
        drawContours( img, contours1, 0, Scalar( 100, 100, 255 ), img.rows / 100, 8, hierarchy, 0, Point() );

        imshow("image", img );
        waitKey(0);
    }


    return 0;
}
AdamF
la source
Quel compilateur peut construire ce programme sans erreur?
karlphillip
J'ai utilisé Visual Studio 2012 pour le créer. Vous devez utiliser le compilateur c ++ avec le support c ++ 11.
AdamF
Je n'ai pas de système à ma disposition avec ça. Pourriez-vous réécrire l' std::max_element()appel? Je voudrais également récompenser votre réponse. Je pense que j'ai gcc 4.2.
karlphillip
Ok c'est la fonctionnalité c ++ 11;) J'ai changé le code source ci-dessus. S'il te plaît, essaye maintenant.
AdamF
D'accord merci. Je l'ai testé et c'est magnifique. Dès que cette question est rouverte (les autres utilisateurs doivent m'aider), je peux définir une autre prime pour vous récompenser. Toutes nos félicitations!
karlphillip
31

... une autre solution à l'ancienne - purement basée sur le traitement HSV :

  1. Convertir des images dans l'espace colorimétrique HSV
  2. Créer des masques selon l'heuristique dans le HSV (voir ci-dessous)
  3. Appliquer une dilatation morphologique au masque pour connecter les zones déconnectées
  4. Jeter les petites zones et les blocs horizontaux (rappelez-vous que les arbres sont des blocs verticaux)
  5. Calculer la boîte englobante

Un mot sur l'heuristique dans le traitement HSV:

  1. tout avec des teintes (H) entre 210 et 320 degrés est jeté comme bleu-magenta qui est censé être en arrière-plan ou dans des zones non pertinentes
  2. tout ce qui a des valeurs (V) inférieures à 40% est également rejeté comme étant trop sombre pour être pertinent

Bien sûr, on peut expérimenter de nombreuses autres possibilités pour affiner cette approche ...

Voici le code MATLAB pour faire l'affaire (avertissement: le code est loin d'être optimisé !!! J'ai utilisé des techniques non recommandées pour la programmation MATLAB juste pour pouvoir suivre quoi que ce soit dans le processus - cela peut être grandement optimisé):

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

% initialization
ims=dir('./*.jpg');
num=length(ims);

imgs={};
hsvs={}; 
masks={};
dilated_images={};
measurements={};
boxs={};

for i=1:num, 
    % load original image
    imgs{end+1} = imread(ims(i).name);
    flt_x_size = round(size(imgs{i},2)*0.005);
    flt_y_size = round(size(imgs{i},1)*0.005);
    flt = fspecial( 'average', max( flt_y_size, flt_x_size));
    imgs{i} = imfilter( imgs{i}, flt, 'same');
    % convert to HSV colorspace
    hsvs{end+1} = rgb2hsv(imgs{i});
    % apply a hard thresholding and binary operation to construct the mask
    masks{end+1} = medfilt2( ~(hsvs{i}(:,:,1)>(210/360) & hsvs{i}(:,:,1)<(320/360))&hsvs{i}(:,:,3)>0.4);
    % apply morphological dilation to connect distonnected components
    strel_size = round(0.03*max(size(imgs{i})));        % structuring element for morphological dilation
    dilated_images{end+1} = imdilate( masks{i}, strel('disk',strel_size));
    % do some measurements to eliminate small objects
    measurements{i} = regionprops( dilated_images{i},'Perimeter','Area','BoundingBox'); 
    for m=1:length(measurements{i})
        if (measurements{i}(m).Area < 0.02*numel( dilated_images{i})) || (measurements{i}(m).BoundingBox(3)>1.2*measurements{i}(m).BoundingBox(4))
            dilated_images{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
    dilated_images{i} = dilated_images{i}(1:size(imgs{i},1),1:size(imgs{i},2));
    % compute the bounding box
    [y,x] = find( dilated_images{i});
    if isempty( y)
        boxs{end+1}=[];
    else
        boxs{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(boxs{i})
        hold on;
        rr = rectangle( 'position', boxs{i});
        set( rr, 'EdgeColor', 'r');
        hold off;
    end
    subplot(122);
    imshow( imgs{i}.*uint8(repmat(dilated_images{i},[1 1 3])));
end

Résultats:

Dans les résultats, je montre l'image masquée et le cadre de sélection. entrez la description de l'image ici

sepdek
la source
Bonjour, merci pour la réponse. Veuillez prendre un moment pour lire la section Exigences pour vous assurer que votre réponse suit toutes les instructions. Vous avez oublié de partager les images résultantes. ;)
karlphillip
2
@karlphillip sepdek n'a pas assez de réputation pour partager des images, j'ai déplacé les images dans le corps de la réponse selon son lien et ses instructions. Je ne suis pas sûr cependant que ce soient les bons, n'hésitez pas à commenter cette partie.
alko
@alko Je sais, merci. Mais certaines des images que vous avez partagées n'étaient pas dans le jeu d'entrée . La réponse doit montrer le résultat du traitement des 6 images partagées sur la question.
karlphillip
@karlphillip ce sont ses images, pas les miennes. c'est exactement ce que je voulais dire par "commenter cette partie";)
alko
2
Désolé d'avoir causé des problèmes ... pas mon intention. J'ai inclus toutes les images dans le jeu de données initial et l'ai amélioré avec encore plus juste pour prouver que mon concept est robuste ...
sepdek
23

Une approche de traitement d'image à l'ancienne ...
L'idée est basée sur l' hypothèse que les images représentent des arbres éclairés sur des arrière-plans généralement plus sombres et plus lisses (ou au premier plan dans certains cas). La zone de l'arbre éclairé est plus "énergique" et a une intensité plus élevée .
Le processus est le suivant:

  1. Convertir en niveaux de gris
  2. Appliquer le filtrage LoG pour obtenir les zones les plus "actives"
  3. Appliquer un seuillage intentionnel pour obtenir les zones les plus lumineuses
  4. Combinez les 2 précédents pour obtenir un masque préliminaire
  5. Appliquer une dilatation morphologique pour agrandir les zones et connecter les composants voisins
  6. Élimine les petites zones candidates en fonction de leur taille

Vous obtenez un masque binaire et un cadre de sélection pour chaque image.

Voici les résultats de cette technique naïve: entrez la description de l'image ici

Le code sur MATLAB suit: Le code s'exécute sur un dossier avec des images JPG. Charge toutes les images et renvoie les résultats détectés.

% 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={};
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 grayscale
    images{end+1}=rgb2gray(imgs{i});

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

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

    % compute the final binary image by combining 
    % high 'activity' with high intensity
    bin_image{end+1} = log_image{i} .* int_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');
    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
sepdek
la source
N'oubliez pas de télécharger les images résultantes, comme l'a fait Faust.
karlphillip
Je suis un noob ici, donc je ne peux pas télécharger d'images. Veuillez voir les résultats sur les liens fournis dans ma description.
sepdek
D'accord, mais vous devez toujours utiliser les images partagées sur la question comme tout le monde le fait. Une fois que vous les avez traités, téléchargez-les quelque part et modifiez votre réponse pour ajouter les liens. Plus tard, je modifierai votre réponse et placerai les images à l'intérieur pour vous.
karlphillip
Le lien semble contenir les images correctes maintenant.
Dennis Jaheruddin
22

En utilisant une approche assez différente de ce que j'ai vu, j'ai créé un script qui détecte les arbres de Noël par leurs lumières. Le résultat est toujours un triangle symétrique, et si nécessaire des valeurs numériques comme l'angle ("gras") de l'arbre.

La plus grande menace pour cet algorithme est évidemment les lumières à côté (en grand nombre) ou devant l'arbre (le plus gros problème jusqu'à une optimisation plus poussée). Modifier (ajouté): Ce qu'il ne peut pas faire: savoir s'il y a un arbre de Noël ou non, trouver plusieurs arbres de Noël dans une image, détecter correctement un arbre de Noël au milieu de Las Vegas, détecter les arbres de Noël fortement pliés, à l'envers ou coupé ...;)

Les différentes étapes sont:

  • Calculez la luminosité ajoutée (R + G + B) pour chaque pixel
  • Additionnez cette valeur des 8 pixels voisins au-dessus de chaque pixel
  • Classez tous les pixels en fonction de cette valeur (le plus brillant en premier) - Je sais, pas vraiment subtil ...
  • Choisissez N de ceux-ci, en commençant par le haut, en sautant ceux qui sont trop proches
  • Calculez le de ces N supérieurs (nous donne le centre approximatif de l'arbre)
  • Commencez à partir de la position médiane vers le haut dans un faisceau de recherche élargi pour la lumière la plus élevée à partir des plus brillantes sélectionnées (les gens ont tendance à mettre au moins une lumière tout en haut)
  • De là, imaginez des lignes allant de 60 degrés vers la gauche et la droite vers le bas (les arbres de Noël ne devraient pas être si gros)
  • Diminuez ces 60 degrés jusqu'à ce que 20% des lumières les plus brillantes soient en dehors de ce triangle
  • Trouvez la lumière tout en bas du triangle, vous donnant la bordure horizontale inférieure de l'arbre
  • Terminé

Explication des marquages:

  • Grande croix rouge au centre de l'arbre: médiane du sommet N lumières les plus brillantes
  • Ligne pointillée de là vers le haut: "faisceau de recherche" pour le haut de l'arbre
  • Croix rouge plus petite: sommet de l'arbre
  • Vraiment petites croix rouges: toutes les N les plus brillantes lumières
  • Triangle rouge: D'uh!

Code source:

<?php

ini_set('memory_limit', '1024M');

header("Content-type: image/png");

$chosenImage = 6;

switch($chosenImage){
    case 1:
        $inputImage     = imagecreatefromjpeg("nmzwj.jpg");
        break;
    case 2:
        $inputImage     = imagecreatefromjpeg("2y4o5.jpg");
        break;
    case 3:
        $inputImage     = imagecreatefromjpeg("YowlH.jpg");
        break;
    case 4:
        $inputImage     = imagecreatefromjpeg("2K9Ef.jpg");
        break;
    case 5:
        $inputImage     = imagecreatefromjpeg("aVZhC.jpg");
        break;
    case 6:
        $inputImage     = imagecreatefromjpeg("FWhSP.jpg");
        break;
    case 7:
        $inputImage     = imagecreatefromjpeg("roemerberg.jpg");
        break;
    default:
        exit();
}

// Process the loaded image

$topNspots = processImage($inputImage);

imagejpeg($inputImage);
imagedestroy($inputImage);

// Here be functions

function processImage($image) {
    $orange = imagecolorallocate($image, 220, 210, 60);
    $black = imagecolorallocate($image, 0, 0, 0);
    $red = imagecolorallocate($image, 255, 0, 0);

    $maxX = imagesx($image)-1;
    $maxY = imagesy($image)-1;

    // Parameters
    $spread = 1; // Number of pixels to each direction that will be added up
    $topPositions = 80; // Number of (brightest) lights taken into account
    $minLightDistance = round(min(array($maxX, $maxY)) / 30); // Minimum number of pixels between the brigtests lights
    $searchYperX = 5; // spread of the "search beam" from the median point to the top

    $renderStage = 3; // 1 to 3; exits the process early


    // STAGE 1
    // Calculate the brightness of each pixel (R+G+B)

    $maxBrightness = 0;
    $stage1array = array();

    for($row = 0; $row <= $maxY; $row++) {

        $stage1array[$row] = array();

        for($col = 0; $col <= $maxX; $col++) {

            $rgb = imagecolorat($image, $col, $row);
            $brightness = getBrightnessFromRgb($rgb);
            $stage1array[$row][$col] = $brightness;

            if($renderStage == 1){
                $brightnessToGrey = round($brightness / 765 * 256);
                $greyRgb = imagecolorallocate($image, $brightnessToGrey, $brightnessToGrey, $brightnessToGrey);
                imagesetpixel($image, $col, $row, $greyRgb);
            }

            if($brightness > $maxBrightness) {
                $maxBrightness = $brightness;
                if($renderStage == 1){
                    imagesetpixel($image, $col, $row, $red);
                }
            }
        }
    }
    if($renderStage == 1) {
        return;
    }


    // STAGE 2
    // Add up brightness of neighbouring pixels

    $stage2array = array();
    $maxStage2 = 0;

    for($row = 0; $row <= $maxY; $row++) {
        $stage2array[$row] = array();

        for($col = 0; $col <= $maxX; $col++) {
            if(!isset($stage2array[$row][$col])) $stage2array[$row][$col] = 0;

            // Look around the current pixel, add brightness
            for($y = $row-$spread; $y <= $row+$spread; $y++) {
                for($x = $col-$spread; $x <= $col+$spread; $x++) {

                    // Don't read values from outside the image
                    if($x >= 0 && $x <= $maxX && $y >= 0 && $y <= $maxY){
                        $stage2array[$row][$col] += $stage1array[$y][$x]+10;
                    }
                }
            }

            $stage2value = $stage2array[$row][$col];
            if($stage2value > $maxStage2) {
                $maxStage2 = $stage2value;
            }
        }
    }

    if($renderStage >= 2){
        // Paint the accumulated light, dimmed by the maximum value from stage 2
        for($row = 0; $row <= $maxY; $row++) {
            for($col = 0; $col <= $maxX; $col++) {
                $brightness = round($stage2array[$row][$col] / $maxStage2 * 255);
                $greyRgb = imagecolorallocate($image, $brightness, $brightness, $brightness);
                imagesetpixel($image, $col, $row, $greyRgb);
            }
        }
    }

    if($renderStage == 2) {
        return;
    }


    // STAGE 3

    // Create a ranking of bright spots (like "Top 20")
    $topN = array();

    for($row = 0; $row <= $maxY; $row++) {
        for($col = 0; $col <= $maxX; $col++) {

            $stage2Brightness = $stage2array[$row][$col];
            $topN[$col.":".$row] = $stage2Brightness;
        }
    }
    arsort($topN);

    $topNused = array();
    $topPositionCountdown = $topPositions;

    if($renderStage == 3){
        foreach ($topN as $key => $val) {
            if($topPositionCountdown <= 0){
                break;
            }

            $position = explode(":", $key);

            foreach($topNused as $usedPosition => $usedValue) {
                $usedPosition = explode(":", $usedPosition);
                $distance = abs($usedPosition[0] - $position[0]) + abs($usedPosition[1] - $position[1]);
                if($distance < $minLightDistance) {
                    continue 2;
                }
            }

            $topNused[$key] = $val;

            paintCrosshair($image, $position[0], $position[1], $red, 2);

            $topPositionCountdown--;

        }
    }


    // STAGE 4
    // Median of all Top N lights
    $topNxValues = array();
    $topNyValues = array();

    foreach ($topNused as $key => $val) {
        $position = explode(":", $key);
        array_push($topNxValues, $position[0]);
        array_push($topNyValues, $position[1]);
    }

    $medianXvalue = round(calculate_median($topNxValues));
    $medianYvalue = round(calculate_median($topNyValues));
    paintCrosshair($image, $medianXvalue, $medianYvalue, $red, 15);


    // STAGE 5
    // Find treetop

    $filename = 'debug.log';
    $handle = fopen($filename, "w");
    fwrite($handle, "\n\n STAGE 5");

    $treetopX = $medianXvalue;
    $treetopY = $medianYvalue;

    $searchXmin = $medianXvalue;
    $searchXmax = $medianXvalue;

    $width = 0;
    for($y = $medianYvalue; $y >= 0; $y--) {
        fwrite($handle, "\nAt y = ".$y);

        if(($y % $searchYperX) == 0) { // Modulo
            $width++;
            $searchXmin = $medianXvalue - $width;
            $searchXmax = $medianXvalue + $width;
            imagesetpixel($image, $searchXmin, $y, $red);
            imagesetpixel($image, $searchXmax, $y, $red);
        }

        foreach ($topNused as $key => $val) {
            $position = explode(":", $key); // "x:y"

            if($position[1] != $y){
                continue;
            }

            if($position[0] >= $searchXmin && $position[0] <= $searchXmax){
                $treetopX = $position[0];
                $treetopY = $y;
            }
        }

    }

    paintCrosshair($image, $treetopX, $treetopY, $red, 5);


    // STAGE 6
    // Find tree sides
    fwrite($handle, "\n\n STAGE 6");

    $treesideAngle = 60; // The extremely "fat" end of a christmas tree
    $treeBottomY = $treetopY;

    $topPositionsExcluded = 0;
    $xymultiplier = 0;
    while(($topPositionsExcluded < ($topPositions / 5)) && $treesideAngle >= 1){
        fwrite($handle, "\n\nWe're at angle ".$treesideAngle);
        $xymultiplier = sin(deg2rad($treesideAngle));
        fwrite($handle, "\nMultiplier: ".$xymultiplier);

        $topPositionsExcluded = 0;
        foreach ($topNused as $key => $val) {
            $position = explode(":", $key);
            fwrite($handle, "\nAt position ".$key);

            if($position[1] > $treeBottomY) {
                $treeBottomY = $position[1];
            }

            // Lights above the tree are outside of it, but don't matter
            if($position[1] < $treetopY){
                $topPositionsExcluded++;
                fwrite($handle, "\nTOO HIGH");
                continue;
            }

            // Top light will generate division by zero
            if($treetopY-$position[1] == 0) {
                fwrite($handle, "\nDIVISION BY ZERO");
                continue;
            }

            // Lights left end right of it are also not inside
            fwrite($handle, "\nLight position factor: ".(abs($treetopX-$position[0]) / abs($treetopY-$position[1])));
            if((abs($treetopX-$position[0]) / abs($treetopY-$position[1])) > $xymultiplier){
                $topPositionsExcluded++;
                fwrite($handle, "\n --- Outside tree ---");
            }
        }

        $treesideAngle--;
    }
    fclose($handle);

    // Paint tree's outline
    $treeHeight = abs($treetopY-$treeBottomY);
    $treeBottomLeft = 0;
    $treeBottomRight = 0;
    $previousState = false; // line has not started; assumes the tree does not "leave"^^

    for($x = 0; $x <= $maxX; $x++){
        if(abs($treetopX-$x) != 0 && abs($treetopX-$x) / $treeHeight > $xymultiplier){
            if($previousState == true){
                $treeBottomRight = $x;
                $previousState = false;
            }
            continue;
        }
        imagesetpixel($image, $x, $treeBottomY, $red);
        if($previousState == false){
            $treeBottomLeft = $x;
            $previousState = true;
        }
    }
    imageline($image, $treeBottomLeft, $treeBottomY, $treetopX, $treetopY, $red);
    imageline($image, $treeBottomRight, $treeBottomY, $treetopX, $treetopY, $red);


    // Print out some parameters

    $string = "Min dist: ".$minLightDistance." | Tree angle: ".$treesideAngle." deg | Tree bottom: ".$treeBottomY;

    $px     = (imagesx($image) - 6.5 * strlen($string)) / 2;
    imagestring($image, 2, $px, 5, $string, $orange);

    return $topN;
}

/**
 * Returns values from 0 to 765
 */
function getBrightnessFromRgb($rgb) {
    $r = ($rgb >> 16) & 0xFF;
    $g = ($rgb >> 8) & 0xFF;
    $b = $rgb & 0xFF;

    return $r+$r+$b;
}

function paintCrosshair($image, $posX, $posY, $color, $size=5) {
    for($x = $posX-$size; $x <= $posX+$size; $x++) {
        if($x>=0 && $x < imagesx($image)){
            imagesetpixel($image, $x, $posY, $color);
        }
    }
    for($y = $posY-$size; $y <= $posY+$size; $y++) {
        if($y>=0 && $y < imagesy($image)){
            imagesetpixel($image, $posX, $y, $color);
        }
    }
}

// From http://www.mdj.us/web-development/php-programming/calculating-the-median-average-values-of-an-array-with-php/
function calculate_median($arr) {
    sort($arr);
    $count = count($arr); //total numbers in array
    $middleval = floor(($count-1)/2); // find the middle value, or the lowest middle value
    if($count % 2) { // odd number, middle is the median
        $median = $arr[$middleval];
    } else { // even number, calculate avg of 2 medians
        $low = $arr[$middleval];
        $high = $arr[$middleval+1];
        $median = (($low+$high)/2);
    }
    return $median;
}


?>

Images: En haut à gauche Centre inférieur En bas à gauche En haut à droite Centre supérieur En bas à droite

Bonus: un Weihnachtsbaum allemand, de Wikipedia Römerberg http://commons.wikimedia.org/wiki/File:Weihnachtsbaum_R%C3%B6merberg.jpg

Christian
la source
17

J'ai utilisé python avec opencv.

Mon algorithme va comme ceci:

  1. D'abord, il prend le canal rouge de l'image
  2. Appliquer un seuil (valeur min 200) au canal rouge
  3. Ensuite, appliquez le gradient morphologique, puis faites une «fermeture» (dilatation suivie d'une érosion)
  4. Il trouve ensuite les contours dans le plan et sélectionne le contour le plus long.

Le résultat:

Le code:

import numpy as np
import cv2
import copy


def findTree(image,num):
    im = cv2.imread(image)
    im = cv2.resize(im, (400,250))
    gray = cv2.cvtColor(im, cv2.COLOR_RGB2GRAY)
    imf = copy.deepcopy(im)

    b,g,r = cv2.split(im)
    minR = 200
    _,thresh = cv2.threshold(r,minR,255,0)
    kernel = np.ones((25,5))
    dst = cv2.morphologyEx(thresh, cv2.MORPH_GRADIENT, kernel)
    dst = cv2.morphologyEx(dst, cv2.MORPH_CLOSE, kernel)

    contours = cv2.findContours(dst,cv2.RETR_TREE,cv2.CHAIN_APPROX_SIMPLE)[0]
    cv2.drawContours(im, contours,-1, (0,255,0), 1)

    maxI = 0
    for i in range(len(contours)):
        if len(contours[maxI]) < len(contours[i]):
            maxI = i

    img = copy.deepcopy(r)
    cv2.polylines(img,[contours[maxI]],True,(255,255,255),3)
    imf[:,:,2] = img

    cv2.imshow(str(num), imf)

def main():
    findTree('tree.jpg',1)
    findTree('tree2.jpg',2)
    findTree('tree3.jpg',3)
    findTree('tree4.jpg',4)
    findTree('tree5.jpg',5)
    findTree('tree6.jpg',6)

    cv2.waitKey(0)
    cv2.destroyAllWindows()

if __name__ == "__main__":
    main()

Si je change le noyau de (25,5) en (10,5) j'obtiens de meilleurs résultats sur tous les arbres mais en bas à gauche, entrez la description de l'image ici

mon algorithme suppose que l'arbre est éclairé, et dans l'arbre inférieur gauche, le haut a moins de lumière que les autres.

ifryed
la source