sortier algorithmus?
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
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
-
- User
- Beiträge: 773
- Registriert: Mittwoch 5. November 2003, 18:06
- Wohnort: Schweiz
- Kontaktdaten:
Hi
Du könntest einfach nach der Anzahl Einsen sortieren:
Gruss
*edit*
mh wenn ich das ja genauer anschaue: '01101010' > '01101110', nach welchem Kriterium ist der erste grösser als der zweite?
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
*edit*
mh wenn ich das ja genauer anschaue: '01101010' > '01101110', nach welchem Kriterium ist der erste grösser als der zweite?
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:
Da kommt Python prima mit klar.
Ansonsten schliesse ich mich der Frage von rayo an.
Code: Alles auswählen
In [78]: int('1' * 1024, 2)
Out[78]: 17976931348623159077293051907890247336179769789423065727343008115773267
58055009631327084773224075360211201138798713933576587897688144166224928474306394
74124377767893424865485276302219601246094119453082952085005768838150682342462881
473913110540827237163350510684586298239947245938479716304835356329624224137215L
Ansonsten schliesse ich mich der Frage von rayo an.
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
)
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'
please )
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] )
rayo hat geschrieben:Hi
Du könntest einfach nach der Anzahl Einsen sortieren:GrussCode: Alles auswählen
def einser_cmd(this, other): return cmp(this.count('1'), other.count('1')) liste.sort(einser_cmd) print liste
*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
@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:
sollte es tun. aber das haut irgenwie nicht hin
Abgesehen davon, ist das nicht sehr python-style denke ich
Um die Frage
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)
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)
Abgesehen davon, ist das nicht sehr python-style denke ich
Um die Frage
zu beantworten:Panke hat geschrieben:Was genau ist jetzt das Kriterium, wonach sortiert wird?
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)
Panke hat geschrieben:Was genau ist jetzt das Kriterium, wonach sortiert wird?
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
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
BlackJack hat geschrieben: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:
Da kommt Python prima mit klar.Code: Alles auswählen
In [78]: int('1' * 1024, 2) Out[78]: 17976931348623159077293051907890247336179769789423065727343008115773267 58055009631327084773224075360211201138798713933576587897688144166224928474306394 74124377767893424865485276302219601246094119453082952085005768838150682342462881 473913110540827237163350510684586298239947245938479716304835356329624224137215L
Ansonsten schliesse ich mich der Frage von rayo an.
- birkenfeld
- Python-Forum Veteran
- Beiträge: 1603
- Registriert: Montag 20. März 2006, 15:29
- Wohnort: Die aufstrebende Universitätsstadt bei München
Um mal bei der gestellten Aufgabe zu bleiben (ohne zu beurteilen, ob die Anwendung sinnvoll ist):
sollte das gewünschte ergeben, wobei `x` eine Liste mit den einzelnen Zeilen ist.
Code: Alles auswählen
x.sort(key=lambda x: (len(x.strip('0')), x.count('1')))
Hi Birkenfeld
danke für die Antwort. Um nun mal konkreter zu werden:
unter verwendung von:
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
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
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
birkenfeld hat geschrieben:Um mal bei der gestellten Aufgabe zu bleiben (ohne zu beurteilen, ob die Anwendung sinnvoll ist):
sollte das gewünschte ergeben, wobei `x` eine Liste mit den einzelnen Zeilen ist.Code: Alles auswählen
x.sort(key=lambda x: (len(x.strip('0')), x.count('1')))
- birkenfeld
- Python-Forum Veteran
- Beiträge: 1603
- Registriert: Montag 20. März 2006, 15:29
- Wohnort: Die aufstrebende Universitätsstadt bei München
0014 und 0006 haben beide die gleiche Anzahl 0en an den Rändern.
Du hast nicht spezifiziert, wie du die Nullen zählen willst.
Du hast nicht spezifiziert, wie du die Nullen zählen willst.
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:
Bei den Beispieldaten kommt folgendes heraus:
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'))
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')]
Hoi syracus,
- 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
Das weiß ich nicht, aber ich habe ein paar Fragen / Anmerkungen, die uns vielleicht einer Lösung näher bringen:syracus hat geschrieben: Aber vielleicht liege ich ja bereits mit der Überlegung völlig falsch
- 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
Hi CM,
also der FP wird egtl ganz einfach erstellt.
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
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:
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
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() )
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
Momentan wird nach folgenden Schema gesucht:- 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.
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]
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
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
Hoi syracus,
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.
Das verstehe ich schon nicht: Du schreibst return bevor der Rest der Funktion abgeschlossen ist? Glaube ich habe einen Blackout.syracus hat geschrieben: 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() )
Sind Deine Eingangsdaten Grauwerte? Dann sind Eigenwerte vielleicht eine echte Alternative .syracus hat geschrieben: Nicht wirklich ein guter Algorithmus, liefert für meine Bilder-Datenbank aber ganz ansehnliche Resultate mit dem pearsonr().
Ok, das mußt Du wissen.syracus hat geschrieben: 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.
Das kannst eigentlich nur Du beurteilen, weil nur Du Deine Daten kennst. Aber es widerspricht so ziemlich allem was ich über Bildbearbeitung weiß.syracus hat geschrieben: 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
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)syracus hat geschrieben: 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
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.
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:CM hat geschrieben:Hoi syracus,
Das verstehe ich schon nicht: Du schreibst return bevor der Rest der Funktion abgeschlossen ist? Glaube ich habe einen Blackout.syracus hat geschrieben: 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() )
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())