Lassen Sie uns eine probabilistische Ausbreitungsmethode (Python) erstellen.

Was ist die stochastische Ausbreitungsmethode?

Die Wahrscheinlichkeitsausbreitungsmethode, auch Glaubensausbreitungsmethode (Belief Propagation) genannt, ist ein Algorithmus zum effizienten Ermitteln der peripheren Verteilung des Zustands jedes Knotens in einem grafischen Modell wie dem Bayes'schen Netzwerk oder dem Markov-Wahrscheinlichkeitsfeld (MRF). .. Wenn beim Versuch, diese periphere Verteilung zu finden, die Anzahl der Knoten N und die Anzahl der Zustände K beträgt, beträgt der Berechnungsbetrag ursprünglich $ O (K ^ N) $, und wenn die Anzahl der Knoten zunimmt, ist die Berechnung nicht in einer endlichen Zeit möglich. Wenn jedoch diese stochastische Ausbreitungsmethode verwendet wird, wird sie zu $ O (NK ^ 2) $ und kann in einer endlichen Zeit berechnet werden. Wenn diese periphere Verteilung erhalten wird, ist es zweckmäßig, dass abhängig von der Struktur des Graphen der optimale Zustand jedes Knotens unter Verwendung der peripheren Verteilung erhalten werden kann, oder eine Lösung in der Nähe davon kann erhalten werden, selbst wenn es nicht die optimale Lösung ist. Dieses Mal habe ich versucht, diese stochastische Ausbreitungsmethode in Python zu erstellen, daher möchte ich den Code Schritt für Schritt erklären.

Programmerklärung

Nutzungsdaten

Dieses Mal möchte ich die Wahrscheinlichkeitsausbreitungsmethode auf das verrauschte Bild von Herrn Lena anwenden, um das Rauschen zu entfernen. Die von jedem Pixel angenommenen Werte sind zwei Werte, 0 und 1.

Programm

Fügen Sie dem Originalbild zunächst Rauschen hinzu. Der Code sieht folgendermaßen aus:

python

def addNoise(image):
    output = np.copy(image)
    flags  = np.random.binomial(n=1, p=0.05, size=image.shape)

    for i in range(image.shape[0]):
        for j in range(image.shape[1]):
            if flags[i,j]:
                output[i,j] = not(output[i,j])

    return output

Betrachten Sie als Nächstes jedes Pixel im Bild als Knoten und erstellen Sie eine MRF. Von besonderer Bedeutung in dieser MRF-Klasse ist die Funktion beliePropagation. Da das Markov-Wahrscheinlichkeitsfeld auf dem Bild ein Netzwerk mit einer Schleifenstruktur ist, muss die Nachrichtenübertragung mehrmals wiederholt werden. Dieses Mal werden die Iterationszeiten wiederholt. Initialisieren Sie die von jedem Knoten vom benachbarten Knoten empfangene Nachricht mit 1, bevor Sie die Übertragung wiederholen. Senden Sie nach dem Eintritt in die Sendeschleife weiterhin Nachrichten mit der sendMessage-Methode an benachbarte Knoten und integrieren Sie schließlich die Nachrichten von benachbarten Knoten, die Sie für jeden Knoten haben, und berechnen Sie die Peripherieverteilung. Die Randmethode macht das.

python

class MRF:
    def __init__(self):
        self.nodes = [] #Knoten auf MRF
        self.id = {} #Knoten-ID
    
    #Fügen Sie der MRF einen Knoten hinzu
    def addNode(self, id, node):
        self.nodes.append(node)
        self.id[id] = node
    
    #Gibt den Knoten gemäß der ID zurück
    def getNode(self, id):
        return self.id[id]
    
    #Gibt alle Knoten zurück
    def getNodes(self):
        return self.nodes
    
    #Starten Sie die probabilistische Ausbreitung
    def beliefPropagation(self, iter=20):
        
        #Initialisieren Sie Nachrichten von benachbarten Knoten für jeden Knoten
        for node in self.nodes:
            node.initializeMessage()
        
        #Wiederholen Sie eine bestimmte Anzahl von Malen
        for t in range(iter):
            print(t)
            
            #Senden Sie für jeden Knoten eine Nachricht an die Knoten neben diesem Knoten
            for node in self.nodes:
                for neighbor in node.getNeighbor():
                    neighbor.message[node] = node.sendMessage(neighbor)
        
        #Berechnen Sie die periphere Verteilung für jeden Knoten
        for node in self.nodes:
            node.marginal()

Definieren Sie als Nächstes die Knotenklasse.

python

class Node(object):
    def __init__(self, id):
        self.id = id
        self.neighbor = []
        self.message = {}
        self.prob = None
        
        #Parameter für die Energiefunktion
        self.alpha = 10.0
        self.beta = 5.0

    def addNeighbor(self, node):
        self.neighbor.append(node)

    def getNeighbor(self):
        return self.neighbor
    
    #Initialisieren Sie Nachrichten von benachbarten Knoten
    def initializeMessage(self):
        for neighbor in self.neighbor:
            self.message[neighbor] = np.array([1.0, 1.0])
    
    #Integrieren Sie alle Nachrichten
    #prob ist die periphere Verteilung
    def marginal(self):
        prob = 1.0

        for message in self.message.values():
            prob *= message

        prob /= np.sum(prob)
        self.prob = prob
    
    #Berechnen Sie die Wahrscheinlichkeit unter Berücksichtigung des Zustands benachbarter Knoten
    def sendMessage(self, target):
        neighbor_message = 1.0
        for neighbor in self.message.keys():
            if neighbor != target:
                neighbor_message *= self.message[neighbor]

        compatibility_0 = np.array([np.exp(-self.beta * np.abs(0.0 - 0.0)), np.exp(-self.beta * np.abs(0.0 - 1.0))])
        compatibility_1 = np.array([np.exp(-self.beta * np.abs(1.0 - 0.0)), np.exp(-self.beta * np.abs(1.0 - 1.0))])

        message = np.array([np.sum(neighbor_message * compatibility_0), np.sum(neighbor_message * compatibility_1)])
        message /= np.sum(message)

        return message
    
    #Wahrscheinlichkeit berechnet aus beobachteten Werten
    def calcLikelihood(self, value):
        likelihood = np.array([0.0, 0.0])

        if value == 0:
            likelihood[0] = np.exp(-self.alpha * 0.0)
            likelihood[1] = np.exp(-self.alpha * 1.0)
        else:
            likelihood[0] = np.exp(-self.alpha * 1.0)
            likelihood[1] = np.exp(-self.alpha * 0.0)

        self.message[self] = likelihood

Die wichtigsten sind die Methoden calcLikelihood, sendMessage und marginal. Angenommen, Sie möchten eine Nachricht von Knoten 1 an Knoten 2 senden, wie in Abbildung 1 dargestellt. Diese Nachricht soll Ihnen sagen, welchen Wert Knoten 2 annehmen soll, wenn Sie Knoten 2 von Knoten 1 aus betrachten.

Um es zu berechnen, muss zuerst die Zuverlässigkeit (Gültigkeit, wenn der Wert genommen wird) für jeden Wert von Knoten 1 berechnet werden. Berechnen Sie zunächst die Zuverlässigkeit, wenn Sie nur den beobachteten Wert von Knoten 1 betrachten. Die calcLikelihood-Methode berechnet dies. Wenn der beobachtete Wert 0 ist, erhöht sich die Zuverlässigkeit, die der Knoten 0 annimmt, und umgekehrt nimmt die Zuverlässigkeit, die der Knoten 1 annimmt, ab. Wenn der beobachtete Wert 1 ist, ist das Gegenteil der Fall.

Als nächstes multiplizieren Sie die aus den beobachteten Werten berechnete Zuverlässigkeit mit der Zuverlässigkeit jedes Werts von Knoten 1, wenn er von Knoten 4 aus betrachtet wird (Nachricht von Knoten 4 zu Knoten 1). Abbildung 2 zeigt diese. In dieser Berechnung, im Code, in der sendMessage-Methode

python

neighbor_message = 1.0
        for neighbor in self.message.keys():
            if neighbor != target:
                neighbor_message *= self.message[neighbor]

Dies ist der

Teil. </ p>

Verwenden Sie diese dann, um die Nachricht zu berechnen, die an Knoten 2 gesendet werden soll. Die Nachricht (Zuverlässigkeit) wird wie folgt berechnet. 

Dies wird in der sendMessage-Methode berechnet

python

compatibility_0 = np.array([np.exp(-self.beta * np.abs(0.0 - 0.0)), np.exp(-self.beta * np.abs(0.0 - 1.0))])
compatibility_1 = np.array([np.exp(-self.beta * np.abs(1.0 - 0.0)), np.exp(-self.beta * np.abs(1.0 - 1.0))])

message = np.array([np.sum(neighbor_message * compatibility_0), np.sum(neighbor_message * compatibility_1)])
message /= np.sum(message)

Es wird

sein. </ P>

Senden Sie eine Nachricht an benachbarte Knoten auf allen Knoten. Nach mehrmaliger Wiederholung wird die Randmethode verwendet, um alle vom Knoten vom benachbarten Knoten empfangenen Nachrichten zu multiplizieren, um die periphere Verteilung zu erhalten, und der Wert, den der Knoten annehmen sollte, kann gefunden werden.

Erstellen Sie als Nächstes eine Funktion zum Erstellen des Markov-Wahrscheinlichkeitsfelds.

python

#Erstellen Sie für jedes Pixel einen Knoten und stellen Sie eine Verbindung mit einem benachbarten Pixelknoten her
def generateBeliefNetwork(image):
    network = MRF()
    height, width = image.shape

    for i in range(height):
        for j in range(width):
            nodeID = width * i + j
            node = Node(nodeID)
            network.addNode(nodeID, node)

    dy = [-1, 0, 0, 1]
    dx = [0, -1, 1, 0]

    for i in range(height):
        for j in range(width):
            node = network.getNode(width * i + j)

            for k in range(4):
                if i + dy[k] >= 0 and i + dy[k] < height and j + dx[k] >= 0 and j + dx[k] < width:
                    neighbor = network.getNode(width * (i + dy[k]) + j + dx[k])
                    node.addNeighbor(neighbor)

    return network

Die letzte ist die Hauptfunktion

python

import numpy as np
import cv2
import matplotlib.pyplot as plt
from skimage.filters import threshold_otsu

def main():
    #Nutzungsdaten
    image = cv2.imread("Lenna.png ", 0)
    binary = image > threshold_otsu(image).astype(np.int)
    noise = addNoise(binary)
    
    #MRF-Konstruktion
    network = generateBeliefNetwork(image)
    
    #Wahrscheinlichkeit aus beobachteten Werten erstellen (Pixelwerte)
    for i in range(image.shape[0]):
        for j in range(image.shape[1]):
            node = network.getNode(image.shape[1] * i + j)
            node.calcLikelihood(noise[i,j])
    
    #Führen Sie die stochastische Ausbreitungsmethode durch
    network.beliefPropagation()
    
    #Periphere Verteilung[0 Wahrscheinlichkeit,Wahrscheinlichkeit von 1]Auftrag
    #Wenn die Wahrscheinlichkeit 1 groß ist, ändern Sie den Pixelwert der Ausgabe auf 1.
    output = np.zeros(noise.shape)

    for i in range(output.shape[0]):
        for j in range(output.shape[1]):
            node = network.getNode(output.shape[1] * i + j)
            prob = node.prob
            if prob[1] > prob[0]:
                output[i,j] = 1
    
    #Ergebnisanzeige
    plt.gray()
    plt.subplot(121)
    plt.imshow(noise)
    plt.subplot(122)
    plt.imshow(output)
    plt.show()

Ausführungsergebnis

Sie können sehen, dass der größte Teil des Rauschens entfernt und das Originalbild wiederhergestellt wurde. Die Formel selbst ist ziemlich schwierig, aber es ist ziemlich einfach, sie mit einem Programm zu komponieren. Dieses Mal haben wir uns mit dem diskreten Fall befasst, in dem die Anzahl der Zustände binär ist. Wenn es sich jedoch um kontinuierliche Zustände wie Tracking handelt, muss die kontinuierliche variable Version der Wahrscheinlichkeitsausbreitungsmethode verwendet werden. Es wurden verschiedene Dinge vorgeschlagen, aber beim nächsten Mal möchte ich eine mittlere Verschiebung der Glaubensausbreitung erstellen, die relativ einfach zu erstellen ist.

Referenzen / Websites

Markov Probability Field / Probability Propagation-Methode mit Python networkx implementieren

Die Denosierung erfolgt nach der stochastischen Ausbreitungsmethode unter Verwendung der berühmten Bibliothek networkX für die Graphentheorie. Es ist sehr leicht zu verstehen, da es den Algorithmus anhand von Zahlen erklärt.

Einführung in die Bildverarbeitungstechnologie durch das Probabilistic Model-Tanaka Laboratory

Es scheint ein Power Point zu sein, der von einem Professor in einem bestimmten Labor an der Tohoku-Universität geschrieben wurde. Es wird auf leicht verständliche Weise anhand von Zahlen und mathematischen Formeln erklärt.