sortier algorithmus?

[syracus]

Hallo,

ich habe weniger ein spezielles python problem, als ein allg. algorithmus problem. Nichts desto trotz erhoffe ich mir hier hilfe, da dieser Algo in einem python script anwendung finden soll.

Folgendes Problem: Angenommen ich hätte folgende Liste von Zeichenketten (in dieser Reihenfolge):

01111110
11111111
00011000
00111100

Diese soll nun sortiert werden, sodass sich folgendes Bild ergibt:

00011000
00111100
01111110
11111111

Leider ist ein int(i)^i nicht so leicht möglich, da die Zeichenketten beliebig lang werden können (max 1024 Zeichen) und ich somit bei der potenzierung leicht die grenzen MAX_INT überschreite. des weitern können die Zeichenkette natürlich 'Lücken' enthalten, z.B. Zeile 3 '01101010'. Somit ist die Sortierung wahrscheinlich nur mit einer Art 'Verteilungs-Algorithmus' möglich, wobei '01101010' > '01101110' und '11111111' > '0000000'. Beim Vergleich zweier String kann davon ausgegangen werden, daß beide gleich lang sind 'len(s1)==len(s2)'

Irgentjemand von euch Gurus ne Idee ?

Gruß
syracus

[rayo]

Hi

Du könntest einfach nach der Anzahl Einsen sortieren:

Code: Alles auswählen

def einser_cmd(this, other):
    return cmp(this.count('1'), other.count('1'))

liste.sort(einser_cmd)
print liste

Gruss

*edit*
mh wenn ich das ja genauer anschaue: '01101010' > '01101110', nach welchem Kriterium ist der erste grösser als der zweite?

[BlackJack]

Mal davon abgesehen, dass das wieder mal nach einer Hausaufgabe aussieht, wo liegt das Problem wenn MAX_INT überschritten wird? Eine Binärzahl mit 1024 Einsen ist letztendlich gar nicht sooo gross:

Code: Alles auswählen

In [78]: int('1' * 1024, 2)
Out[78]: 17976931348623159077293051907890247336179769789423065727343008115773267
58055009631327084773224075360211201138798713933576587897688144166224928474306394
74124377767893424865485276302219601246094119453082952085005768838150682342462881
473913110540827237163350510684586298239947245938479716304835356329624224137215L

Da kommt Python prima mit klar.

Ansonsten schliesse ich mich der Frage von rayo an.

[syracus]

Hi rayo

hmmm...einfach zählen der 1en funzt nicht. Folgendes Szenario:

1:'00001000'
2:'00000001'
3:'10000000'

Einfach zählen ergäbe '0' für alle Vergleiche (aber ich finde x.count('1) schon mal irre soweit, habe ich nicht gekannt...bisher immer

Code: Alles auswählen

def x(s):
  c=0
  for i in s:
    if i == '1': c+=1
  return c

)

Was ich aber brauche ist

1: > 2:
1: > 3:
2: > 3:
3: < 2:

wobei für die Anforderung sogar 2: == 3: gelten könnte.
Entscheidend ist die 'Entfernung'.
Angenommen 2: wäre '00000011'
dann müsste gelten (und das unbedingt) 2: > 3:

Um die abolute Wertigkeit eines String festzustellen schweb mir eher sowas vor:

def x(s):
v=0
for i, x in enumerate(s):
v+=int(x)*i
return v

Mopl....hmm...das sieht egtl gut aus....
*nachdenk*
nee...
'0001000' < '00000001'

sollte aber ergeben
1: '0001000'
2: '0000001'

Code: Alles auswählen

print "\n".join( [hint for hint in hints] )

please )

Hi

Du könntest einfach nach der Anzahl Einsen sortieren:

Code: Alles auswählen

def einser_cmd(this, other):
    return cmp(this.count('1'), other.count('1'))

liste.sort(einser_cmd)
print liste

Gruss

*edit*
mh wenn ich das ja genauer anschaue: '01101010' > '01101110', nach welchem Kriterium ist der erste grösser als der zweite?

Code: Alles auswählen

[Panke]

Was genau ist jetzt das Kriterium, wonach sortiert wird?

[syracus]

@BlackJack, rayo, Panke:

Ich sehe schon. Hab mich nicht klar genug ausgedrückt.
Mal sehen, ob ich das auch besser hinbekomme.

Stellt euch folgende 2dim Matrix vor:
1: 00000
2: 00000
3: 00000
4: 00000
5: 00000

angenommen nun kommt was wie:
1: 10001
2: 01010
3: 00100
4: 01010
5: 10001

dann sollte die Sortierung folgendes ergeben:
1: 00100
2: 01010
3: 01010
4: 10001
5: 10001

Soweit so einfach.

Wenn aber 4:=01110
dann ergäbe sich:
1: 00100
2: 01010
3: 01110 <----
4: 10001
5: 10001

somit denke ich etwas wie:

Code: Alles auswählen

def calc(s):
  for i in range(len(s)/2):
    v+=int( potenzial(s[i],i )
  for i in range(len(s)/2):
    v+=int( potenzial(reverse(s)[i],i )
  return v
def cmp(s1,s2):
  return calc(s2) - calc(s1)

sollte es tun. aber das haut irgenwie nicht hin
Abgesehen davon, ist das nicht sehr python-style denke ich

Um die Frage

Was genau ist jetzt das Kriterium, wonach sortiert wird?

zu beantworten:

Entscheidend für den gesuchten Algo ist, daß je weiter die '1' von den Rändern entfernt ist, desto höherwertig ist sie. Die Summe aller '1'en ergibt den Sortier-Koevizienten. (Sorry, bin kein Mathematiker. Deshalb eventuell falsche Nomenklarur)

Was genau ist jetzt das Kriterium, wonach sortiert wird?

[syracus]

Nee, ist keine HA Hoffe doch aus dem Alter bin ich raus

Es geht um einen Algo um 'ähnliche' Bilder zu finden...möglichst performant.
Das Script vergleicht momentan alle images absteigend in einer Liste. Die Infos pro Bild sind in einer Art Fingerprint von binären Werten mit einer Länge von 256 Werten gespeichert (0 und 1). Der Vergleich zweier Bilder findet mit SciPy.pearsonr() statt. Die Liste wird dynamisch bei ähnlichen Bildern gekürzt. Die Rechendauer ist allerdings ab einer Anzahl von 3000++ Bildern unterträglich (+2h auf meiner Kiste).
Die Idee war nun, ähnliche Bilder, basierend auf Ihrer 'Bit-Wertigkeit' zu sortieren. Damit würde die Anzahl den zu prüfenden Bildern stark abnehmen, da image ~= image[i+1]..usw, und damit die Liste sehr schnell kürzer werden würde.
Dabei ist klar, daß der pearsonnr-Koeffizient von '000010000' zu '000101000' ist als zu '111111111'.

Aber vielleicht liege ich ja bereits mit der Überlegung völlig falsch

Mal davon abgesehen, dass das wieder mal nach einer Hausaufgabe aussieht, wo liegt das Problem wenn MAX_INT überschritten wird? Eine Binärzahl mit 1024 Einsen ist letztendlich gar nicht sooo gross:

Code: Alles auswählen

In [78]: int('1' * 1024, 2)
Out[78]: 17976931348623159077293051907890247336179769789423065727343008115773267
58055009631327084773224075360211201138798713933576587897688144166224928474306394
74124377767893424865485276302219601246094119453082952085005768838150682342462881
473913110540827237163350510684586298239947245938479716304835356329624224137215L

Da kommt Python prima mit klar.

Ansonsten schliesse ich mich der Frage von rayo an.

[birkenfeld]

Um mal bei der gestellten Aufgabe zu bleiben (ohne zu beurteilen, ob die Anwendung sinnvoll ist):

Code: Alles auswählen

x.sort(key=lambda x: (len(x.strip('0')), x.count('1')))

sollte das gewünschte ergeben, wobei `x` eine Liste mit den einzelnen Zeilen ist.

[syracus]

Hi Birkenfeld

danke für die Antwort. Um nun mal konkreter zu werden:

unter verwendung von:

Code: Alles auswählen

def reorder_images(images,reverse=False):
    images.sort(key=lambda x: (len(x[1].strip('0')), x[1].count('1')))
    return images

wobei images eine Liste von Tupels (<filename>,<fingerprint>) ist, ergibt sich:

DEBUG:root:Loading image db
DEBUG:root:BEFORE ORDERING
DEBUG:root:0002.jpg -> 0010101101111011111110110001011110100001000000110000000111010001
DEBUG:root:0004.jpg -> 0111111101111001010010110000000000000111000000110000000110000111
DEBUG:root:0006.jpg -> 1111110011101101111101101100100000001011000100010000001000110100
DEBUG:root:0008.jpg -> 1111001111111111111101111111111100100011001001110000011100000111
DEBUG:root:0011.jpg -> 1111111111111111111111101110111111101011111111110001111100111111
DEBUG:root:0013.jpg -> 1111111111111111111111111111111111000011011110111011111000001011
DEBUG:root:0015.jpg -> 1111000111111100000010100000111000000100000011000000111110001011
DEBUG:root:0003.jpg -> 1011111110100001101110111111111100000111100100110000011100000101
DEBUG:root:0005.jpg -> 1111111111111000111011111111001100000101001111110000011100000011
DEBUG:root:0001.jpg -> 1111111000011111001111110011111101111101111111111110001111100001
DEBUG:root:0007.jpg -> 1111111111111111111111101111110010011001100001011000110111000111
DEBUG:root:0009.jpg -> 1110000011111111111111111100011100001111000000100000000101111111
DEBUG:root:0010.jpg -> 1111101111111011111010111111111111111111111111111111111011001110
DEBUG:root:0012.jpg -> 1100000011111110111111111110011101101011001110110001111001101111
DEBUG:root:0014.jpg -> 0111111101111110111111101111011111111111111100111111011011110110
DEBUG:root:Sorting images
DEBUG:root:Done
DEBUG:root:AFTER SORTING
DEBUG:root:0006.jpg -> 1111110011101101111101101100100000001011000100010000001000110100
DEBUG:root:0002.jpg -> 0010101101111011111110110001011110100001000000110000000111010001
DEBUG:root:0014.jpg -> 0111111101111110111111101111011111111111111100111111011011110110
DEBUG:root:0004.jpg -> 0111111101111001010010110000000000000111000000110000000110000111
DEBUG:root:0010.jpg -> 1111101111111011111010111111111111111111111111111111111011001110
DEBUG:root:0015.jpg -> 1111000111111100000010100000111000000100000011000000111110001011
DEBUG:root:0003.jpg -> 1011111110100001101110111111111100000111100100110000011100000101
DEBUG:root:0009.jpg -> 1110000011111111111111111100011100001111000000100000000101111111
DEBUG:root:0005.jpg -> 1111111111111000111011111111001100000101001111110000011100000011
DEBUG:root:0008.jpg -> 1111001111111111111101111111111100100011001001110000011100000111
DEBUG:root:0012.jpg -> 1100000011111110111111111110011101101011001110110001111001101111
DEBUG:root:0007.jpg -> 1111111111111111111111101111110010011001100001011000110111000111
DEBUG:root:0001.jpg -> 1111111000011111001111110011111101111101111111111110001111100001
DEBUG:root:0013.jpg -> 1111111111111111111111111111111111000011011110111011111000001011
DEBUG:root:0011.jpg -> 1111111111111111111111101110111111101011111111110001111100111111

Nicht ganz was ich erwartet hätte. Besonders interessant ist der Vergleich von 0006.jpg und 0014.jpg.

db['0006.jpg'].count('1') = 30
db['0014.jpg'].count('1') = 53

Trotzdem würde ich aufgrund der '0'en an den Rändern 0014 vor 0006 erwarten

Um mal bei der gestellten Aufgabe zu bleiben (ohne zu beurteilen, ob die Anwendung sinnvoll ist):

Code: Alles auswählen

x.sort(key=lambda x: (len(x.strip('0')), x.count('1')))

sollte das gewünschte ergeben, wobei `x` eine Liste mit den einzelnen Zeilen ist.

[birkenfeld]

0014 und 0006 haben beide die gleiche Anzahl 0en an den Rändern.

Du hast nicht spezifiziert, wie du die Nullen zählen willst.

[BlackJack]

Es scheint auch um Symmetrie, zumindest bei den 0en zu gehen!? Hier eine Schlüsselfunktion die symmetrische 0en primär bewertet und danach die Anzahl der '1'en als zweites Kriterium benutzt:

Code: Alles auswählen

def key_func(item):
    fingerprint = item[1]
    for i in xrange(len(fingerprint) // 2):
        if fingerprint[i] != fingerprint[-i] != '0':
            break
    return (-i, fingerprint.count('1'))

Bei den Beispieldaten kommt folgendes heraus:

Code: Alles auswählen

[('0008.jpg',
  '1111001111111111111101111111111100100011001001110000011100000111'),
 ('0007.jpg',
  '1111111111111111111111101111110010011001100001011000110111000111'),
 ('0013.jpg',
  '1111111111111111111111111111111111000011011110111011111000001011'),
 ('0011.jpg',
  '1111111111111111111111101110111111101011111111110001111100111111'),
 ('0005.jpg',
  '1111111111111000111011111111001100000101001111110000011100000011'),
 ('0010.jpg',
  '1111101111111011111010111111111111111111111111111111111011001110'),
 ('0004.jpg',
  '0111111101111001010010110000000000000111000000110000000110000111'),
 ('0014.jpg',
  '0111111101111110111111101111011111111111111100111111011011110110'),
 ('0001.jpg',
  '1111111000011111001111110011111101111101111111111110001111100001'),
 ('0006.jpg',
  '1111110011101101111101101100100000001011000100010000001000110100'),
 ('0015.jpg',
  '1111000111111100000010100000111000000100000011000000111110001011'),
 ('0009.jpg',
  '1110000011111111111111111100011100001111000000100000000101111111'),
 ('0012.jpg',
  '1100000011111110111111111110011101101011001110110001111001101111'),
 ('0002.jpg',
  '0010101101111011111110110001011110100001000000110000000111010001'),
 ('0003.jpg',
  '1011111110100001101110111111111100000111100100110000011100000101')]

[CM]

Hoi syracus,

Aber vielleicht liege ich ja bereits mit der Überlegung völlig falsch

Das weiß ich nicht, aber ich habe ein paar Fragen / Anmerkungen, die uns vielleicht einer Lösung näher bringen:
- Wie kommst Du von einem 256x256 px jpg auf diese bit strings? Was ist das für ein "Fingerprint"? (Wenn ich das Problem richtig verstanden habe, wäre scipy.linalg.eig eigentlich der "beste" "Fingerprint", es würde Dir nämlich die Möglichkeit einräumen augrund der Eigenwerte zu klassifizieren.)
- Ist jpg eigentlich das richtige Format für so ein Problem? Die "Ähnlichkeit" zweier Bilder könnte stark von der Auflösung bzw. der der Komprimierung abhängig sein.
- Aber der Pearsonsche Korrelationskoeffizient ist vielleicht auch nicht so schlecht. (Wobei ich nicht verstanden habe, woher diese binäre Matrix stammt, aber das ist Dein Problem .) Auf der Basis kannst Du auch direkt sortieren ( Lebart et al., MULTIVARIATE DESCRIPTIVE STATISTICAL ANALYSIS, J. Wiley and Sons, New York 1984, Chapter V, p.109)
- Warum vorher sortieren? Der Algorithmus wird dadurch nur schneller, wenn Du die als "ähnlich" eingeordneten Bilder wegläßt. Ansonsten brauchst Du immer noch alle Permutationen, wenn Du eine akkurate Klassifizierung machen möchtest.
- Es gibt im Bereich der Elektronenmikroskopie bereits bestehende Software mit Python-Interface: http://blake.bcm.tmc.edu/eman/eman1/ Durchklicken nach: Docs ->Individual Program Documentation (man pages) -> classifykmeans.py Vielleicht etwas für Dein Problem?
- Bzgl. Rechenzeit: Meist werden solche Probleme nur auf Clustern gelöst. Aber wenn Rebinning für Dich ggf. eine Lösung ist, kann ich da mit einem Script aushelfen (von der Scipy Cookbookseite, aber damit scheint es z. Zt. Probleme zu geben).

Gruß,
Christian

edit:
PS http://svn.scipy.org/svn/scipy/trunk/Li ... ication.py

[syracus]

Hi CM,

also der FP wird egtl ganz einfach erstellt.

Code: Alles auswählen

def fp(file,threshold=128):
  return list(Image.open(file).resize((160,160),ANTIALIAS).
  filter(ImageFilter.BLUR).convert('L').
  point( lambda p: int(p/threshold) ).
  resize( (16,16) ).getdata() )

Nicht wirklich ein guter Algorithmus, liefert für meine Bilder-Datenbank aber ganz ansehnliche Resultate mit dem pearsonr().

Was Kompression und Auflösung angeht, so gebe ich dir recht. allerdings ist der Informationsgehalt der Bilder nach dem obigen convert ausreichend, da diese von meiner Digitcam immer mit dem gleichen Werten skaliert und komprimiert wurden.

Interesant finde ich die Frage

- Warum vorher sortieren? Der Algorithmus wird dadurch nur schneller, wenn Du die als "ähnlich" eingeordneten Bilder wegläßt. Ansonsten brauchst Du immer noch alle Permutationen, wenn Du eine akkurate Klassifizierung machen möchtest.

Momentan wird nach folgenden Schema gesucht:

Code: Alles auswählen

i=0
while i < len(images):
  j=i+1
  while j < len(images):
    cor = compare(images[i],images[j])
    if cor >= threshold:
      # similar found
      del images[j]
    else:
      j+=1
  del images[i]

Nicht besonders schön, aber funktioniert

Leider ist es so, daß die innere Schleife immer bis zum Ende der Liste durchlaufen werden muss.

Angenommen die compare() wäre sowas wie:

Code: Alles auswählen

def compare(i1,i2):
  l=len(i1.data)
  c="".join( map(chr, [ operator.xor( ord(i1.data[i]), ord(i2.data[i]) ) for i in range(l) ]) ).count('1')
  return float(c)/l

Die Idee war nun (aber ich denke immer mehr das es wohl eine Schnappsidee war ). Die Liste so um zu sortieren, daß operator.xor möglichst früh hohe Werte für cor ermittelt. Ich habe angenommen, das cor somit immer mehr abnehmen würde und bei unterschreiten eines bestimmten Schwellenwertes von cor hätte ich die innere Schleife abgebrochen.

Langsam sehe ich aber, daß dies wohl nicht sonderlich sinnvoll ist

Ich bin mir natürlich auch bewusst, daß es bereits einige fertiger Programme gibt, die diese Aufgabe gut erledigen. Allerdings haben diese einfach eine Problem mit der schieren Menge an Bildern die ich scannen müsste (~ 200000). Zum anderen hat mich das Problem interessiert einen Weg zu finden einen guten Kompromiss zwischen der Qualität des Vergleichs und der Laufzeit zu finden der auf meine Anforderungen zugeschnitten ist

[CM]

Hoi syracus,

also der FP wird egtl ganz einfach erstellt.

Code: Alles auswählen

def fp(file,threshold=128):
  return list(Image.open(file).resize((160,160),ANTIALIAS).
  filter(ImageFilter.BLUR).convert('L').
  point( lambda p: int(p/threshold) ).
  resize( (16,16) ).getdata() )

Das verstehe ich schon nicht: Du schreibst return bevor der Rest der Funktion abgeschlossen ist? Glaube ich habe einen Blackout.

Nicht wirklich ein guter Algorithmus, liefert für meine Bilder-Datenbank aber ganz ansehnliche Resultate mit dem pearsonr().

Sind Deine Eingangsdaten Grauwerte? Dann sind Eigenwerte vielleicht eine echte Alternative .

Was Kompression und Auflösung angeht, so gebe ich dir recht. allerdings ist der Informationsgehalt der Bilder nach dem obigen convert ausreichend, da diese von meiner Digitcam immer mit dem gleichen Werten skaliert und komprimiert wurden.

Ok, das mußt Du wissen.

Die Idee war nun (aber ich denke immer mehr das es wohl eine Schnappsidee war ). Die Liste so um zu sortieren, daß operator.xor möglichst früh hohe Werte für cor ermittelt. Ich habe angenommen, das cor somit immer mehr abnehmen würde und bei unterschreiten eines bestimmten Schwellenwertes von cor hätte ich die innere Schleife abgebrochen.

Langsam sehe ich aber, daß dies wohl nicht sonderlich sinnvoll ist

Das kannst eigentlich nur Du beurteilen, weil nur Du Deine Daten kennst. Aber es widerspricht so ziemlich allem was ich über Bildbearbeitung weiß.

Ich bin mir natürlich auch bewusst, daß es bereits einige fertiger Programme gibt, die diese Aufgabe gut erledigen. Allerdings haben diese einfach eine Problem mit der schieren Menge an Bildern die ich scannen müsste (~ 200000). Zum anderen hat mich das Problem interessiert einen Weg zu finden einen guten Kompromiss zwischen der Qualität des Vergleichs und der Laufzeit zu finden der auf meine Anforderungen zugeschnitten ist

Arrgh. 200000??? Das ist in der Tat viel, insbesondere bei 256**2 Pixeln. Allerdings ist das vorgestellte Programm sehr leistungsfähig und genau für solche Probleme gemacht. Da Du auf ein Alingment verzichten kannst (scheinbar) und nur eine Klassifizierung machen möchtest, solltest Du Dir dieses Programm wirklich mal anschauen. Es gibt noch eine andere Alternative für Die ich auch eigene Skripte zur Verfügung stellen kann, allerdings kein Python, sondern eine eigene Skriptsprache: http://www.wadsworth.org/spider_doc/spi ... pider.html (dafür gibt es zwar inzwischen auch ein Pythoninterface, aber das steckt immer noch in den Kinderschuhen)
Grundbedingung ist allerdings: Kein jpg und keine Farbe. Das gilt auch für eman (das erste vorgestellte "Fertigprogramm".

Dein Problem ist alles andere als trivial. Eine letzte Alternative, die ich kenne ist unter
http://ldp.library.jhu.edu/projects/gamera/ zu finden. Sie ist vielleicht nicht mit so vielen Einschränkungen versehen, allerdings weiß ich nicht, wie leistungsfähig die Software für diese Art Problem ist.

Gruß,
Christian - der sich zum ersten Mal dabei ertappt jemandem "venutze Fertigsoße" zu sagen.

[BlackJack]

Hoi syracus,

also der FP wird egtl ganz einfach erstellt.

Code: Alles auswählen

def fp(file,threshold=128):
  return list(Image.open(file).resize((160,160),ANTIALIAS).
  filter(ImageFilter.BLUR).convert('L').
  point( lambda p: int(p/threshold) ).
  resize( (16,16) ).getdata() )

Das verstehe ich schon nicht: Du schreibst return bevor der Rest der Funktion abgeschlossen ist? Glaube ich habe einen Blackout.

Da habe ich auch erst gestutzt, das ist aber schon richtig so. Nur ziemlich ungünstig formatiert. Es wird eine Liste zurückgegeben, die von dem gesamten folgenden Ausdruck erzeugt wird. Die letzte schliessende Klammer ist das Gegenstück zu der ersten Klammer nach dem `list`. Hier exakt das gleiche, nur anders formatiert:

Code: Alles auswählen

def fp(file, threshold=128):
  return list(Image.open(file)
              .resize((160, 160), ANTIALIAS)
              .filter(ImageFilter.BLUR)
              .convert('L')
              .point(lambda p: int(p / threshold))
              .resize((16, 16))
              .getdata())