Fotos und Logos für Lasergraviergeräte aufbereiten

vorher

nachher

In diesem Beitrag soll mit Gimp ein Logo oder Foto so vorbereitet werden, dass ein Lasergravierer das Bild gut verarbeiten kann.

Zunächst muss das Foto entsättigt werden. Mitt den verschiedenen Methoden lässt sich hier spielen. (Farben-> Entsättigen–> Entsättigen)

Im zweiten Schritt wird die Ebene dupliziert und das Duplikat farblich invertiert (Farben–> invertieren)

Bei Anwendung des Ebenenmodus “Abwedeln” für die obere (invertierte) Ebene, verschwindet das sichtbare Bild zunächst.

Durch einen Weichzeichner (Filter –> Weichzeichnen –> Gaußscher Weichzeichner) lassen sich dann die Umrisse des Motivs hervorheben. Genau diese kann der Lasergravierer gut verarbeiten.

Zur Optimierung der Kontrastwerte kann unter (Farben–>Kurven) eine steilere Farbkurve des Bildes eingerichtet werden. Diese lässt das Motiv noch Kontrastreicher werden. Dann ab damit aufs Holz!

Das Knapsack-Problem

Zunächst soll das Knapsack-Problem als abstraktes Modell in Google-OR-Tools implementiert werden.

Beschreibung des Knapsack-Problems
Das Knapsack-Problem entspringt der Aufgabe einen Rucksack (engl. Knapsack) mit beschränkter Kapazität zu packen. Dabei können verschieden Gegenstände i=1,...,I entweder eingepackt werden, oder zurückgelassen werden. Für jeden Gegenstand i gibt es im Modell eine Binärvariable x_{i}, die den Wert eins annimmt, wenn der Gegenstand in einer Lösung dem Rucksack zugeordnet wurde.

Kapazitätsrestriktion

Der Rucksack verfügt über eine beschränkte Kapazität K. Jeder Gegenstand nimmt einen bestimmten Anteil der Kapazität in Anspruch. Für Gegenstand i ist dessen Kapazitätsbedarf g_{i} als Parameter vorgegeben.

Als Nebenbedingung ergibt sich daraus:

\displaystyle\sum_{i=1}^{I} x_{i} \cdot g_{i} \leq K

Sie stellt sicher, dass nur die Gegenstände in den Rucksack gepackt werden können, die die Kapazität gemeinsam nicht übersteigen.

Dazu ein kleines Beispiel: Es gibt drei Gegenstände Schlafsack: i=1, Waschbeutel: i=2 und Winterjacke: i=3. Die Kapazität sei das zulässige Gesamtgewicht, dass der Rucksack haben darf K=7kg. Weiterhin gegeben sind die Gewichte (Kapazitätsbedarf der Gegenstände). Der Schlafsack wiegt w_1=4kg (Naturdaune). Das Gewicht des Waschbeutels ist w_2=3kg und die Winterjacke wiegt w_3=3kg.

Die Kapazitätsrestriktion baut sich nun wie folgt für die drei Gegenstände auf:
x_1 \cdot w_1 + x_2 \cdot w_2 + x_3 \cdot w_3 \leq K
Setzt man die Werte ein erhält man:
x_1 \cdot 4kg + x_2 \cdot 3kg + x_3 \cdot 3kg \leq 7kg

Wenn man die Gewichte betrachtet, zeigt sich, dass nicht alle drei Gegenstände mitgenommen werden können, wenn Kapazitätsrestriktion eingehalten werden soll. Würde man nun jede der drei Binärvariablen x_1, x_2, x_3 auf den Wert eins setzen (alle Gegenstände einpacken), wäre die Kapazität von 7kg überschritten.

4kg + 3kg + 3kg = 10kg
10kg \leq 7kg – womit die Kapazitätsrestriktion offensichtlich nicht einghalten ist.

Es lassen sich demnach in dieser Beispielinstanz nur zwei der drei Gegenstände des Beispiels mitnehmen. Die zulässigen Lösungen sind:
– Schlafsack und Waschbeutel (x_1=1, x_2=1, x_3=0)
– Schlafsack und Wintermantel (x_1=1, x_2=0, x_3=1)
– Waschbeutel und Wintermantel (x_1=0, x_2=1, x_3=1)
– nur den Schlafsack (x_1=1, x_2=0, x_3=0)
– nur den Waschbeutel (x_1=0, x_2=1, x_3=0)
– nur den Wintermantel (x_1=0, x_2=0, x_3=1)

Zielfunktion
Jeder Gegenstand i im Rucksack hat einen bestimmten Nutzen u_{i}. Die Zielfunktion addiert nun den Nutzen sämtlicher eingepackter Gegenstände. Damit wird versucht, die gegenbene Kapazität bestmöglich auszunutzen.
Die Zielfunktion ergibt sich demnach wie folgt:

maximiere \, F(x) = \displaystyle\sum_{i=1}^{I} x_{i} \cdot u_{i}

F ist der Gesamtnutzen, der sich aus einer Lösung ergibt. Dieser Gesamtnutzen soll maximiert werden.
Den höchsten Wert den die Zielfunktion jemals annehmen könnte, wäre die Summe der Nutzenwerte sämtlicher Gegenstände. Dies könnte aber nur eintreten, wenn jeder Gegenstand eingepackt werden könnte. Das wird jedoch ggf. von der Kapazitätsrestriktion verhindert (wie das Beispiel oben zeigt).

Hier nochmal das gesamte Modell:

max \, F(x) = \displaystyle\sum_{i=1}^{I} x_{i} \cdot u_{i}
unter den Nebenbedingungen:

\displaystyle\sum_{i=1}^{I} x_{i} \cdot g_{i} \leq K
x_i \in \{0;1\} \, \forall \, i=1,...,I

 

Implementation in Google-OR-Tools

Zu Beginn des Programms wird eine Instanz des Solvers importiert.
from ortools.linear_solver import pywraplp

Anschließend werden die Problemdaten definiert. Hier werden die Daten aus dem oben beschriebenen Beispiel verwendet.
Zunächst die Anzahl der Gegenstände I:
I=3
Die Gewichte der Gegenstände ist eine Liste.
g_i=[4,3,3]
Als Nutzwerte für die drei Gegenstände wird 10, 5 und 9 festgelegt.
u_i=[10,5,9]
Die Kapazität des Rucksacks ist 7kg.
K=7
Zur besseren Darstellung werden auch die Namen der Gegenstände als Liste hinterlegt.
Namen_der_Gegenstaende=["Schlafsack","Waschbeutel","Wintermantel"]

Zum Modell:

Jede der drei Binärvariablen wird auch im Python-Modell eine eigene Variable angelegt. Jeder Variable könnte nun ein eigener Name zugeordnet werden. Z.B. “ZuordnenVonGegenstand1”. Der Nachteil daran wäre, dass bei einer großen Anzahl an Variablen das Programmieren extrem aufwendig wäre.

Damit nicht jeder Variable ein eigener Name zugeordnet werden muss, werden die Variablen in einer Liste oder einem Dictionary gesammelt. Das dict ist zwar etwas aufwendiger, erleichtert aber bei großen Modellen enorm den Zugriff. Hier wird gleich das Dictionary verwendet. Jedes Dictionary ist in Python eine Menge aus Paaren von Schlüsselwerten und dazugehörigen Elemente. Das hier verwendete Dictionary heißt “Variablen”. Zunächst wird es initialisiert.

Variablen = {}

Wir verwenden als Schlüssel den Index des Gegenstands um eins reduziert (0,1,2). Eine Schleife läuft alle Elemente von 0 bis I-1 durch (0,1,2).

for i in range(I):
 Variablen[i] = solver.IntVar(0, 1, 'Gegenstand[%i]' % i)

In jedem Schleifenschritt wird eine ganzzahlige Variable generiert (rechte Seite der Gleichung). Der erste Parameter ist der kleinstmögliche Wert, den die Variable annehmen kann (hier 0). Danach folgt der größtmögliche Wert (1 für Einpacken des Gegenstandes). Der letzte Parameter der Funktion übergibt eine Variablenbezeichnung. Diese lautet hier Gegenstand[%i] für %i setzt Python den aktuellen Indexwert i ein. Jede Variable kann damit eindeutig auseinandergehalten werden. Es ist aber auch ein anderer Variablenname möglich.

Und schon geht’s zur Nebenbedingung. Sie enthält eine Summe über jeden Gegenstand. Diese wird zunächst als Variable “linkeSeite” gespeichert.

linkeSeite=solver.Sum([g_i[i] * Variablen[i] for i in range(I)])

Dabei wird die Funktion solver.Sum der OR-tools verwendet. Als Parameter erhält sie eine Liste an Variablen. Diese kann man entweder beliebig erstellen, oder wie hier in einer inline Funktion erstellen. Über die bekannten Indizes for i in range(I) wird der jeweilige Gewichtswert mit dem Variablenwert multipliziert (genau wie in der echten Nebenbedingung).

Die Kapazitätsrestriktion wird nun an den Solver übergeben. Das macht die Funktion Solver.Add.

solver.Add(linkeSeite<=K)

Der Parameter K beinhaltet unseren oben definierten Paramter für die Kapazität (K=7).

Zielfunktion
Ganz ähnlich zur Restriktion wird nun die Zielfunktion als eigenes Objekt ZF definiert.

ZF=solver.Sum([Variablen[i] * u_i[i] for i in range(I)])

Anstelle des Gewichtes werden hier die Nutzwerte (jeweils das ite Element aus der Liste u_i) mit dem zugehörigen Variablenwert von i multipliziert.

Zuletzt wird die Optimierungsrichtung festgelegt:

objective=solver.Maximize(ZF)

Und schon beauftragen wir den Solver mit der Lösung des Modells:

solver.Solve()

Hier noch einige Zeilen zur Auswertung der Lösung. Diese beinhalten Ausgabe des Zielfunktionswertes, der benötigten Rechenzeit, Iterationen und der Lösung selbst.

print('Zielfunktionswert:', solver.Objective().Value())
print('WallTime:', solver.WallTime())
print('iterations:', solver.Iterations())
print()

for i in range(I):
 print("Variablenwert Gegenstand %i: %i" % (i,Variablen[i].SolutionValue()))

optimale_Loesung=[]
for i in range(I):
 if Variablen[i].SolutionValue()==1:
  optimale_Loesung.append(Namen_der_Gegenstaende[i])

print("Inhalt des Rucksacks: ",optimale_Loesung )

Hier die fertige Python-Datei zum Download.

Google OR-Tools einfach erklärt (Teil I – Einführung und Installation)

Hier soll eine Einführung in die Open-Source Optimierungssoftware Google-OR-Tools gegeben werden. Dieses sehr gute Bundle an Optimierungssoftware umfasst unter anderem eine eigene Modellierungssprache als auch einen Standardsolver. Diese Beitragsreihe konzentriert sich auf diese beiden Elemente. Dazu sollen Erklärungen von Einrichtung über Modellierung bis hin zur Lösung präsentiert werden und mit einfachen Beispielen ergänzt werden.

Voraussetzungen und Installation
Um Googles OR-Tools verwenden zu können, benötigt man eine Entwicklungsumgebung. Neben dem hier verwendeten Anaconda (Python 3.7) funktioniert auch Microsoft .net und C++. Wichtig: es muss eine 64bit Version des Python-Frameworks verwendet werden, sonst lassen sich die OR-tools nicht wie hier beschrieben installieren.

Anaconda lässt sich von deren Webseite kostenlos beziehen. Nach erfolgreicher Installation können Google-Or-Tools direkt per Befehl hinzugefügt werden.

Anleitung für Windows:
Nach einem Klick auf das Startmenü (Windowslogo): “Anaconda Promt” eingeben und das Programm starten
Im neuen Fenster folgendes eingeben:
pip install ortools

Bei erfolgreicher Installation erscheint unter anderem:
Installing collected packages: protobuf, ortools
Successfully installed ortools-6.9.5824 protobuf-3.6.1

Damit ist die Installation abeschlossen und die Modellierung kann beginnen!

Teile eines Strings ersetzen

Hier im Beispiel sollen deutsche Dezimalzeichen ins englische “0.5” Format gebracht werden


dim variable as string
variable="0,5"
variable = Replace(variable, ",", ".")  // Ergebnis: variable="0.5"

Datei beschreiben (überschreiben)

vorhandene Dateien mit dem gewählten Namen werden überschrieben


Dim pfad As String
pfad = ActiveWorkbook.Path & "" & "datensatz.txt" '<- Pfad der geöffneten Exceldatei
Open pfad For Output As #1
zeile = "Text in der Datei"
Print #1, zeile
zeile = "// noch mehr text" & vbCrLF '<- Zeilenumbruch
Print #1, zeile
Close #1

Zeilen und Spalten einer Tabelle zählen

Anzahl Zeilen und Spalten einer Exceltabelle zählen


anzahlzeilen = Worksheets("Tabelle1").Cells(Rows.Count, 1).End(xlUp).Row
anzahlSpalten = Worksheets(1).Cells(1, Worksheets(1).Columns.Count).End(xlToLeft).Column
'[Worksheets(1)=Worksheets("Tabelle1")= Tabelle in der gezählt werden soll]


 

Zellbereich verketten

Diese Funktion kann in ein beliebiges Modul in VBA eingefügt werden. In der Zelle steht dann z.B. die Formel =verketten2(A1:A100;”,”)

 


Public Function verketten2(ByRef rngBereich As Range, strTrennzeichen As String) As Variant
Dim rng As Range
Dim strTextkette As String

For Each rng In rngBereich
If rng <> "" Then
strTextkette = strTextkette & rng & strTrennzeichen
End If
Next
If Len(strTextkette) > 0 Then
strTextkette = Left(strTextkette, Len(strTextkette) - Len(strTrennzeichen))
Verketten2 = strTextkette
End If

End Function

Rand mit Gimp ins transparente verlaufen lassen

Das kann auch zum Freistellen eines Bildes genutzt werden, wenn der Rand ausgefranzt ist (die Grenze des freizustellenden Bildes nicht eindeutig abgegrenzt werden kann)

1. Rechtsklick auf die Ebene > Auswahl aus Alphakanal.
(Wenn kein Alphakanal vorhanden ist, ist der Ebenenname Fett geschrieben, du kannst per Rechtklick auf die entsprechende Ebene einen Alphakanal hinzufügen, dazu Alphakanal hinzufügen anklicken)

2. Nun Auswahl > Auswahl verkleinern (vllt um 10 px kommt auf deine Bildgröße an)

3. Drücke nun >strg< + >i< (das Invertiert die Auswahl, was nötig ist um den “Rand” auslaufen zu lassen und nicht das “Innere”)

4. Nun Auswahl ausblenden. Dazu >Auswahl > Ausblenden.
(Einstellung, kommt auf die Bildgröße und wie stark das ausgeblendet soll an, aber vllt 100 Px!?!

5. Nur noch >Entf< Drücken.

(6. vllt noch die Auswahl ausblenden >Strg< + >Umschalt< + >A<)

Quelle: http://www.gimpforum.de/archive/index.php/t-16250.html

Excel Funktion: Zahlen aus Zelle extrahieren

Der folgende VBA-Code gibt alle numerischen Zeichen einer Zelle zurück.
Der Code kann in ein beliebiges Modul geschrieben und im Sheet als Zellfunktion aufgerufen werden.
Zellfunktion Beispiel: =getzahl(A1)


Function getzahl(zelle As Range) As String
Text = zelle.Value
Dim zahl As String
zahl = ""
For i = 1 To Len(Text)
 If IsNumeric(Mid(Text, i, 1)) = True Then
  zahl = zahl & Mid(Text, i, 1)
 End If
Next i
getzahl = zahl
End Function

Interessante Menschen

“Nur weil ein Mensch nichts sagt, heißt das nicht, dass er nichts zu sagen hätte.”