Construisons une méthode de propagation probabiliste (Python)
Quelle est la méthode de propagation stochastique?
La méthode de propagation des probabilités, également appelée méthode de propagation des croyances (Croyance Propagation), est un algorithme permettant de trouver efficacement la distribution périphérique de l'état de chaque nœud sur un modèle graphique tel que le réseau bayésien ou le champ de probabilité de Markov (MRF). .. À l'origine, en essayant de trouver cette distribution périphérique, si le nombre de nœuds est N et le nombre d'états est K, le montant du calcul sera $ O (K ^ N) $, et si le nombre de nœuds augmente, le calcul ne sera pas possible dans un temps fini. Cependant, si cette méthode de propagation stochastique est utilisée, elle devient $ O (NK ^ 2) $ et peut être calculée en un temps fini. Ce qui est commode lorsque cette distribution périphérique est obtenue, c'est que, selon la structure du graphe, l'état optimal de chaque nœud peut être obtenu à l'aide de la distribution périphérique, ou une solution proche de celle-ci peut être obtenue même si ce n'est pas la solution optimale. Cette fois, j'ai essayé de construire cette méthode de propagation stochastique en Python, je voudrais donc expliquer le code étape par étape.
Explication du programme
Des données d'utilisation
Cette fois, je voudrais appliquer la méthode de propagation de probabilité à l'image bruyante de M. Lena pour supprimer le bruit. Les valeurs prises par chaque pixel sont deux valeurs, 0 et 1.
programme
Tout d'abord, ajoutez du bruit à l'image d'origine. Le code ressemble à ceci:
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
Ensuite, considérez chaque pixel de l'image comme un nœud et construisez un MRF. On notera en particulier dans cette classe MRF la fonction croyancePropagation. Puisque le champ de probabilité de Markov sur l'image est un réseau avec une structure en boucle, il est nécessaire de répéter la transmission du message plusieurs fois. Cette fois, il se répète plusieurs fois. Initialisez le message reçu par chaque nœud du nœud adjacent avec 1 avant de répéter la transmission. Après être entré dans la boucle d'envoi, continuez à envoyer des messages aux nœuds voisins avec la méthode sendMessage, et enfin intégrez les messages des nœuds voisins que vous avez pour chaque nœud et calculez la distribution périphérique. La méthode marginale fait cela.
python
class MRF:
def __init__(self):
self.nodes = [] #Nœud sur MRF
self.id = {} #ID de nœud
#Ajouter un nœud au MRF
def addNode(self, id, node):
self.nodes.append(node)
self.id[id] = node
#Renvoie le nœud en fonction de l'ID
def getNode(self, id):
return self.id[id]
#Renvoie tous les nœuds
def getNodes(self):
return self.nodes
#Démarrer la propagation probabiliste
def beliefPropagation(self, iter=20):
#Initialiser les messages des nœuds voisins pour chaque nœud
for node in self.nodes:
node.initializeMessage()
#Répétez un certain nombre de fois
for t in range(iter):
print(t)
#Pour chaque nœud, envoyez un message aux nœuds adjacents à ce nœud
for node in self.nodes:
for neighbor in node.getNeighbor():
neighbor.message[node] = node.sendMessage(neighbor)
#Calculez la distribution périphérique pour chaque nœud
for node in self.nodes:
node.marginal()
Ensuite, définissez la classe de nœuds.
python
class Node(object):
def __init__(self, id):
self.id = id
self.neighbor = []
self.message = {}
self.prob = None
#Paramètres de la fonction énergétique
self.alpha = 10.0
self.beta = 5.0
def addNeighbor(self, node):
self.neighbor.append(node)
def getNeighbor(self):
return self.neighbor
#Initialiser les messages des nœuds voisins
def initializeMessage(self):
for neighbor in self.neighbor:
self.message[neighbor] = np.array([1.0, 1.0])
#Intégrez tous les messages
#prob est la distribution périphérique
def marginal(self):
prob = 1.0
for message in self.message.values():
prob *= message
prob /= np.sum(prob)
self.prob = prob
#Calculer la vraisemblance en considérant l'état des nœuds voisins
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
#Probabilité calculée à partir des valeurs observées
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
Les plus importantes sont les méthodes calcLikelihood, sendMessage et marginale. Supposons que vous souhaitiez envoyer un message du nœud 1 au nœud 2, comme illustré à la figure 1. Ce message est pour vous dire quelle valeur le nœud 2 doit prendre lorsque vous regardez le nœud 2 à partir du nœud 1.
Pour le calculer, il faut d'abord calculer la fiabilité (validité lorsque la valeur est prise) pour chaque valeur du nœud 1. Tout d'abord, calculez la fiabilité en ne regardant que la valeur observée du nœud 1. La méthode calcLikelihood calcule cela. Si la valeur observée est 0, la fiabilité que le nœud prendra 0 augmente, et inversement, la fiabilité que le nœud prendra 1 diminue. Si la valeur observée est 1, le contraire est vrai.
Ensuite, multipliez la fiabilité calculée à partir des valeurs observées par la fiabilité de chaque valeur du nœud 1 vue du nœud 4 (message du nœud 4 au nœud 1). La figure 2 les montre. Dans ce calcul, dans le code, dans la méthode sendMessage
python
neighbor_message = 1.0
for neighbor in self.message.keys():
if neighbor != target:
neighbor_message *= self.message[neighbor]
C'est la partie
. </ p>
Ensuite, utilisez-les pour calculer le message à envoyer au nœud 2. Le message (fiabilité) est calculé comme suit. 
Ceci est calculé dans la méthode sendMessage
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)
Ce sera
. </ P>
Envoyez un message aux nœuds adjacents sur tous les nœuds. Après avoir répété cela plusieurs fois, la méthode marginale est utilisée pour multiplier tous les messages reçus par le nœud du nœud adjacent pour obtenir la distribution périphérique, et la valeur que le nœud doit prendre peut être trouvée.
Ensuite, créez une fonction pour construire le champ de probabilité de Markov.
python
#Créez un nœud pour chaque pixel et créez une connexion avec un nœud de pixel adjacent
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
Le dernier est la fonction principale
python
import numpy as np
import cv2
import matplotlib.pyplot as plt
from skimage.filters import threshold_otsu
def main():
#Des données d'utilisation
image = cv2.imread("Lenna.png ", 0)
binary = image > threshold_otsu(image).astype(np.int)
noise = addNoise(binary)
#Construction MRF
network = generateBeliefNetwork(image)
#Créer une vraisemblance à partir des valeurs observées (valeurs de pixel)
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])
#Effectuer la méthode de propagation stochastique
network.beliefPropagation()
#Distribution périphérique[0 probabilité,Probabilité de 1]Commande
#Si la probabilité de 1 est grande, modifiez la valeur de pixel de la sortie sur 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
#Affichage des résultats
plt.gray()
plt.subplot(121)
plt.imshow(noise)
plt.subplot(122)
plt.imshow(output)
plt.show()
Résultat d'exécution
Vous pouvez voir que la majeure partie du bruit a été supprimée et que l'image d'origine a été restaurée. La formule elle-même est assez difficile, mais il est assez facile de la composer avec un programme. Cette fois, nous avons traité le cas discret où le nombre d'états est binaire, mais lorsqu'il s'agit d'états continus comme le tracking, il est nécessaire d'utiliser la version variable continue de la méthode de propagation de probabilité. Diverses choses ont été proposées, mais la prochaine fois, j'aimerais créer une propagation de la croyance par changement moyen qui soit relativement facile à construire.
Références / Sites
Le dénosage est effectué par la méthode de propagation stochastique en utilisant la célèbre bibliothèque networkX pour la théorie des graphes. Il est très facile à comprendre car il explique l'algorithme à l'aide de chiffres.
Introduction à la technologie de traitement d'image par Probabilistic Model-Tanaka Laboratory
Cela semble être un PowerPoint écrit par un professeur dans un certain laboratoire de l'Université Tohoku. Il explique d'une manière facile à comprendre à l'aide de figures et de formules mathématiques.