PRML Kapitel 8 Summe der Produkte Algorithmus Python-Implementierung
Kapitel 8 beschreibt das grafische Modell. Ein grafisches Modell ist eine Methode zum grafischen Ausdrücken von Beziehungen wie stochastischen Variablen und Modellparametern. Modelle wie die lineare Regression in PRML können im Allgemeinen mithilfe grafischer Modelle dargestellt werden. Ich habe einen Produktsummenalgorithmus implementiert, der auf ein Modell angewendet werden kann, das durch ein grafisches Modell dargestellt werden kann, und versucht, Bildrauschen zu entfernen. Diese Methode scheint eine allgemeine Form der Methode zu sein, die auf das in Kapitel 13 von PRML eingeführte Hidden-Markov-Modell angewendet wird.
Betrachten Sie hier ein Binärbild (weiß: 1, schwarz: -1), in dem die Pixel im Bild entweder einen Wert von -1,1 haben. Bei einem Bild mit invertierten Werten bei einigen Pixeln wie dem folgenden wird ein rauschfreies Bild wie folgt wiederhergestellt: Markov-Wahrscheinlichkeitsfeld Als Modell für die Entfernung von Bildrauschen verwenden wir das Markov-Wahrscheinlichkeitsfeld (Markov-Netzwerk, ungerichtetes grafisches Modell), eine Art grafisches Modell. Die folgende Abbildung zeigt schematisch das diesmal betrachtete Markov-Wahrscheinlichkeitsfeld.
Der ** $ y $ -Knoten ist eine stochastische Variable, die den Pixelwert des mit Rauschen beobachteten Bildes darstellt, und der $ x $ -Knoten ist die stochastische Variable, die den Pixelwert des rauschfreien Bildes darstellt, das wir wiederherstellen möchten **. In einem rauschfreien Bild wird angenommen, dass benachbarte Pixel eine starke Korrelation aufweisen, sodass selbst in diesem Modell benachbarte Knoten durch eine Linie in $ x $ verbunden sind. Da der Anteil des Rauschens relativ klein ist, besteht auch eine starke Korrelation zwischen dem Wert eines Pixels in einem rauschfreien Bild und dem entsprechenden Pixelwert in einem verrauschten Bild.
Wenn beispielsweise ein Pixel in einem verrauschten Bild einen Wert von 1 hat, sind die an dieses Pixel angrenzenden Pixel wahrscheinlich 1, und der entsprechende Pixelwert in einem verrauschten Bild kann auch 1 sein. hoch. Dies bedeutet, dass die durch ** Linien verbundenen Knoten tendenziell den gleichen Pixelwert ** haben.
Dies als Formel ausdrücken,
p({\bf x},{\bf y}) = {1\over Z}\exp\left\{-E({\bf x},{\bf y})\right\}
Wenn Sie jedoch $ i, j $ als Index zur Darstellung des Knotens verwenden,
E({\bf x},{\bf y}) = -\alpha\sum_ix_iy_i-\beta\sum_{Angrenzend an i und j}x_ix_j
Und $ Z $ ist eine Normalisierungskonstante.
Gegeben ein Bild mit Rauschen
Produktsummenalgorithmus
Dieser Algorithmus ist eine Methode zur Berechnung der Wahrscheinlichkeit des Werts, den ein stochastischer variabler Knoten in einem grafischen Modell annehmen kann. Die Wahrscheinlichkeit wird berechnet, indem so etwas wie eine nicht normalisierte Wahrscheinlichkeit, die als Nachricht bezeichnet wird, von den durch eine Linie verbundenen Knoten ausgetauscht wird.
Nachricht von $ y_i $ an $ x_i $
m_{y_i\to x_i} = \exp(\alpha x_i y_i)
$ Y_i $ ist hier jedoch keine stochastische Variable, sondern ein beobachteter Wert.
Nachricht von $ x_j $ an $ x_i $
m_{x_j\to x_i} = \sum_{x_j}\exp(\beta x_ix_j)f(x_j)
$ F (x_j) $ ist jedoch das Produkt von Nachrichten von anderen Knoten als dem Knoten $ i $ neben dem Knoten $ j $. Um $ f (x_j) $ zu berechnen, benötigen Sie eine Nachricht von einem anderen Knoten zu Knoten $ i $. Da es sich bei dem grafischen Modell, mit dem wir uns diesmal befassen, um ein Modell mit einer Schleife handelt, initialisieren Sie die Nachricht zuerst mit einem bestimmten Wert und dann Senden Sie die beiden oben genannten Nachrichten, um $ {\ bf x} $ zu schätzen.
Implementierung
sum_product.py
import itertools
import numpy as np
from scipy.misc import imread, imsave
ORIGINAL_IMAGE = "qiita_binary.png "
NOISY_IMAGE = "qiita_noise.png "
DENOISED_IMAGE = "qiita_denoised.png "
class Node(object):
def __init__(self):
self.neighbors = []
self.messages = {}
self.prob = None
self.alpha = 10.
self.beta = 5.
def add_neighbor(self, node):
"""
add neighboring node
Parameters
----------
node : Node
neighboring node
"""
self.neighbors.append(node)
def get_neighbors(self):
"""
get neighbor nodes
Returns
-------
neighbors : list
list containing neighbor nodes
"""
return self.neighbors
def init_messeges(self):
"""
initialize messages from neighbor nodes
"""
for neighbor in self.neighbors:
self.messages[neighbor] = np.ones(shape=(2,)) * 0.5
def marginalize(self):
"""
calculate probability
"""
prob = reduce(lambda x, y: x * y, self.messages.values())
self.prob = prob / prob.sum()
def send_message_to(self, node):
"""
calculate message to be sent to the node
Parameters
----------
node : Node
node to send computed message
Returns
-------
message : np.ndarray (2,)
message to be sent to the node
"""
message_from_neighbors = reduce(lambda x, y: x * y, self.messages.values()) / self.messages[node]
F = np.exp(self.beta * (2 * np.eye(2) - 1))
message = F.dot(message_from_neighbors)
node.messages[self] = message / message.sum()
def likelihood(self, value):
"""
calculate likelihood via observation, which is messege to this node
Parameters
----------
value : int
observed value -1 or 1
"""
assert (value == -1) or (value == 1), "{} is not 1 or -1".format(value)
message = np.exp(self.alpha * np.array([-value, value]))
self.messages[self] = message / message.sum()
class MarkovRandomField(object):
def __init__(self):
self.nodes = {}
def add_node(self, location):
"""
add a new node at the location
Parameters
----------
location : tuple
key to access the node
"""
self.nodes[location] = Node()
def get_node(self, location):
"""
get the node at the location
Parameters
----------
location : tuple
key to access the corresponding node
Returns
-------
node : Node
the node at the location
"""
return self.nodes[location]
def add_edge(self, key1, key2):
"""
add edge between nodes corresponding to key1 and key2
Parameters
----------
key1 : tuple
The key to access one of the nodes
key2 : tuple
The key to access the other node.
"""
self.nodes[key1].add_neighbor(self.nodes[key2])
self.nodes[key2].add_neighbor(self.nodes[key1])
def sum_product_algorithm(self, iter_max=10):
"""
Perform sum product algorithm
1. initialize messages
2. send messages from each node to neighboring nodes
3. calculate probabilities using the messages
Parameters
----------
iter_max : int
number of maximum iteration
"""
for node in self.nodes.values():
node.init_messeges()
for i in xrange(iter_max):
print i
for node in self.nodes.values():
for neighbor in node.get_neighbors():
node.send_message_to(neighbor)
for node in self.nodes.values():
node.marginalize()
def denoise(img, n_iter=20):
mrf = MarkovRandomField()
len_x, len_y = img.shape
X = range(len_x)
Y = range(len_y)
for location in itertools.product(X, Y):
mrf.add_node(location)
for x, y in itertools.product(X, Y):
for dx, dy in itertools.permutations(range(2), 2):
try:
mrf.add_edge((x, y), (x + dx, y + dy))
except Exception:
pass
for location in itertools.product(X, Y):
node = mrf.get_node(location)
node.likelihood(img[location])
mrf.sum_product_algorithm(n_iter)
denoised = np.zeros_like(img)
for location in itertools.product(X, Y):
node = mrf.get_node(location)
denoised[location] = 2 * np.argmax(node.prob) - 1
return denoised
def main():
img_original = 2 * (imread(ORIGINAL_IMAGE) / 255).astype(np.int) - 1
img_noise = 2 * (imread(NOISY_IMAGE) / 255).astype(np.int) - 1
img_denoised = denoise(img_noise, 10)
print "error rate before"
print np.sum((img_original != img_noise).astype(np.float)) / img_noise.size
print "error rate after"
print np.sum((img_denoised != img_original).astype(np.float)) / img_noise.size
imsave(DENOISED_IMAGE, (img_denoised + 1) / 2 * 255)
if __name__ == '__main__':
main()
Ergebnis
Bild durch Entfernen von Rauschen wiederhergestellt
Ergebnis der Terminalausgabe
error rate before
0.109477124183
error rate after
0.0316993464052
Die Fehlerrate im Vergleich zum Originalbild ist reduziert.
Am Ende
Wenn der Zweck darin besteht, Rauschen zu entfernen, scheint die Grafikschnittmethode die genaueste zu sein.
Recommended Posts