Warum ist es schwierig, alle Farben im eindimensionalen Raum darzustellen, und wie oft ist dies möglich?

    Yandex kann Farben anhand ihres Namens abfragen und diejenigen in ihrer Nähe finden. Vor einiger Zeit musste dieser Hinweis (in uns nennen wir solche Dinge "Zauberer") überarbeitet werden, damit er der Art der Suchergebnisse nach ihrer Neugestaltung entsprach. Und wir haben diese Gelegenheit ernst genommen, um daran zu arbeiten, denn es stellte sich heraus, dass das lineare Anordnen von Farben eine sehr nicht triviale Aufgabe ist. In diesem Beitrag möchte ich Ihnen sagen, was für ein interessantes algorithmisches Problem, das das Eintauchen in die Farbtheorie erforderte , wir mit fast ganz Yandex lösen mussten, um den neuen Zauberer so zu machen, wie das Team es geplant hatte.












    Der Blumenzauberer tauchte 2008 in den Suchergebnissen von Yandex auf. Als es erfunden wurde, wollten wir, dass es nicht nur ein Spielzeug ist, das einer Person die Farbe des Oberschenkels einer verängstigten Nymphe offenbart, sondern auch hilft, die Farbe anhand der Formel zu erkennen, die Notation anhand der Farbe zu lernen und den Code von einem Farbraum in einen anderen zu übersetzen. Die alte Version des Zauberers bestand aus einer Trommel, einem Farbpicker, einem Eingang und 234 benannten Farben.

    alte Farben


    Zunächst schien es möglich, die aktualisierte Auslieferung in ein paar Wochen wiederzubeleben. Der erste Teil dieser Aufgabe bestand darin, das Aussehen des Zauberers auf den neuen Stil der Suchergebnisseite zu bringen.

    Es wurde schnell klar, dass es nicht auf Standardelementen montiert werden konnte. Außerdem würde der Zauberer, der für die alte Seite der Suchergebnisse gezeichnet wurde, nicht in die neue Version passen, und die Herstellung einer dreidimensionalen Trommel ist unseren Designern zufolge nicht mehr in Mode. So wurde ein flaches Design geboren. Das Wichtigste, was ich in der neuen Version unterstützen wollte, war, benutzerdefinierte Farben anzuzeigen, die keinen Namen hatten. In der alten Version beantwortete der Zauberer alle Anfragen mit den am nächsten benannten Farben und konnte die Menschen in die Irre führen. Jetzt kann jede Farbe von den nächsten benannten Nachbarn umgeben oder in einer anderen Helligkeit gesehen werden.



    Der Hauptsuchdesigner kovchiy überreichte dem Team eine Datei mit Tausenden benannten Blumen aus dem persönlichen Archiv. Als Ergebnis hatten wir 1010 Farben, deren Namen und Koordinaten teilweise in Standard-Farblisten festgelegt sind (z. B. HTML-Farbnamen, X11-Farbnamen) und teilweise unabhängig voneinander erfunden wurden. Und als sie zu überlegen begannen, wie sie in den Zauberer eingesetzt werden sollten, begann das Schwierigste. Das Team, das daran gearbeitet hat, hat sogar beschlossen, einen Wettbewerb für die beste Blumensortierung im internen sozialen Netzwerk von Yandex auszurichten. Dort erfuhr ich von dem Problem und schlug meine Lösung vor, die schließlich in Produktion ging. Aber das Wichtigste zuerst.

    Die Aufgabe bestand also darin, die Farbpalette auf der Trommel (auf einer Linie oder einem Ring) so anzuordnen, dass:
    • die Übergänge zwischen benachbarten Farben waren glatt und möglicherweise kontrastärmer, so dass die benachbarten Farben ähnlich waren;
    • nahe Farben wurden gruppiert, um ähnliche Farben nebeneinander stehen zu lassen.


    Es sah aus wie das ursprüngliche Farbenset ohne vorgegebene Reihenfolge,

    aber diese beiden Kriterien sind bereits:
    • redundant - eine Gruppierung ähnlicher Farben erhöht den Kontrast und eine Verringerung des Kontrasts teilt die Gruppen auf;
    • unzureichend - sie ermöglichen viele verschiedene Entscheidungen, wenn sie nach diesen Kriterien gleich sind, zeichnen sich einige unter anderem durch weniger definierte Eigenschaften aus, wie eine besser sichtbare Aussagekraft des gesamten Standorts;
    • undefined - Sie geben an, wie die gewünschte Lösung aussehen soll, erlauben uns jedoch nicht zu unterscheiden, welche der guten Lösungen besser ist.

    Sowohl die Richter als auch die Teilnehmer verließen sich beim Vergleich der Entscheidungen mehr auf den Geschmack als auf die Einhaltung der Kriterien.

    Manuell, ohne die Hilfe von Algorithmen, wird es nicht nur möglich sein, eine schöne Ordnung mit noch weniger Farben zu finden, sondern auch jemanden zu verbessern, der gefunden wurde. Wenn es den Anschein hat, dass eine Farbe an einer anderen Stelle der Trommel die gleiche Stelle hat, zeigt die Neuanordnung einen scharfen Kontrast: Die Wahrnehmung der Farbe hängt vom Hintergrund ab, und die neuen Nachbarn der verdrängten Farbe, die dem Hintergrund von Blumen in der Nähe so ähnlich zu sein schienen, zeigen nach dem Bewegen plötzlich einen dramatisch anderen Farbton .

    Wenn Sie die Farbanordnung algorithmisch auswählen, ist es naheliegend, das Optimierungsproblem im Problem zu sehen, und der erste Schritt zur Lösung besteht in der Auswahl des Optimierungsziels - eine Funktion, die angibt, wie gut oder schlecht diese oder jene Farbanordnung ist.

    Um diese Funktion zu konstruieren, wird eine Hilfsfunktion mit der Bezeichnung ΔE verwendet, der die Zahl auf den Unterschied oder den Grad der Ähnlichkeit zwischen den beiden Farben festlegt. Das heißt, wenn und nur wenn der Unterschied eines Paars enger Farben gleich dem Unterschied eines anderen Paars ist, sollte es dem Beobachter erscheinen, dass die Farben in jedem der Paare gleich voneinander beabstandet sind. AE ist eines der grundlegenden Probleme der Farbwissenschaft, aber in einem bestimmten Rahmen ist es vollständig gelöst. Glücklicherweise wurde die Funktion des Unterschieds zwischen Farben in der Farbwissenschaft lange untersucht, und jetzt wird, wo erforderlich, eine Formel verwendet, die von der Internationalen Beleuchtungskommission zusammen mit dem CIE L * a * b * -Farbraum veröffentlicht wurde(LAB) im Jahr 1976 (wobei der Unterschied zwischen den Farben einfach der euklidische Abstand zwischen ihnen ist) mit der Bezeichnung CIE ΔE bezeichnet und in den Jahren 1994 und 2000 verfeinert. Konkurrenten, die nicht über CIE AE Bescheid wussten, definierten AE normalerweise selbst als den euklidischen Abstand in RGB und HSV.

    Mit ΔE können wir eine Funktion zur Bewertung der Qualität der Anordnung der Farben auf der Trommel als Summe der Quadrate der Differenzen zwischen benachbarten Farben auf der Trommel konstruieren. Die Entscheidung zwischen den Teilnehmern beginnt sich nur von der Wahl der Qualitätsfunktion der Lösung zu unterscheiden. Alle guten Lösungen verwendeten CIE ΔE; Sie unterscheiden sich untereinander in der Wahl der Qualitätsfunktion der Lösung und des Algorithmus für deren Optimierung.

    Warum hat CIE ΔE eine etwas andere Bedeutung? Der CIE LAB-Farbraum wurde so erstellt, dass die Farben gleichmäßig verteilt sind. Es trennt die Helligkeit von zwei anderen Farbkoordinaten, die es so auswählt, dass eine Farbänderung mehrerer Helligkeitseinheiten als Unterschied wahrgenommen wird, wenn sich andere Koordinaten um dieselben Einheiten ändern. Aber die mathematische Einfachheit von Funktionen, die die Transformation des physikalischen Raums ausdrücken ( CIE XYZ) im LAB war offensichtlich signifikant. Nachfolgende Experimente zeigten, dass der wahrgenommene Farbunterschied nicht ganz, wenn auch nur sehr eng, mit dem dem LAB innewohnenden übereinstimmt. Das heißt, das LAB ist nicht vollständig homogen. Die Änderungen, die an CIE ΔE 1976 vorgenommen wurden, können jedoch nicht in den neuen Farbraum aufgenommen werden - dh es ist unmöglich, einen Raum zu haben, in dem das korrigierte CIE ΔE der euklidische Abstand wäre, wie das alte CIE ΔE im CIE LAB. Daher wird CIE LAB 1967 immer noch verwendet.

    Cielab


    Nachdem wir den Farbraum ausgewählt haben, können wir die natürlichste und einfachste Funktion der Qualität der Lösung auswählen - dies ist die Summe der Quadrate zwischen benachbarten Farben der Anordnung. Die Optimierung dieser Funktion führt zu den glattesten Übergängen zwischen benachbarten Farben (wenn CIE & Dgr; E verwendet wird), und diese Lösung wird jetzt in dem aktualisierten Farbzauberer verwendet. Es wird jedoch nicht speziell berücksichtigt, dass es möglicherweise besser ist, eine Gruppe benachbarter Farben in einer Reihe anzuordnen, als einen Teil davon zu verwenden, sanft zu anderen Schattierungen zu wechseln und wieder zur ersten zurückzukehren. Außerdem kann es wünschenswert sein, „in einer Richtung“ von Farbe zu Farbe zu wechseln: Nach Dunkelrot wird ein etwas helleres Rot noch heller als ein dunklerer Farbton. Um diesen Wünschen gerecht zu werden, Die Teilnehmer addierten zur einfachen Qualitätsfunktion die Summe der quadrierten Differenzen zu den weiter entfernten Nachbarn oder zur Durchschnittsfarbe aller nächsten Nachbarn. Dies verbesserte das Gesamterscheinungsbild des Arrangements, verschlechterte jedoch leider häufig übermäßig die Nahansicht - den Satz von fünf Farben, die der Zauberer gleichzeitig zeigt.

    Nach der Auswahl einer Qualitätsfunktion müssen Sie entscheiden, wie diese optimiert werden soll. Wenn diese Funktion wie die Summe der Quadrate der Unterschiede zwischen den Farben nebeneinander aussieht, entspricht die Aufgabe der Optimierung fast der Aufgabe der Optimierung des TSP (travelling salesman's path) , wobei alle Orte einmal besucht werden und versucht wird, den Gesamtpfad zu minimieren. TSP ist ein NP-komplexes, aber gut untersuchtes Problem, für das es im öffentlichen Bereich mehrere hervorragende Löser für eine ungefähre Lösung gibt - hauptsächlich LKH und Concorde . Mit einem speziellen Löser können Sie eine Lösung finden, die näher am Optimum und schneller ist als dies mit universellen Optimierungsmethoden möglich ist.

    Tsp


    Solche universellen Methoden sind erforderlich, wenn eine komplexere Funktion der Platzierungsqualität gewählt wird, wobei der Unterschied nicht nur zwischen den nächsten Nachbarn berücksichtigt wird.


    Sortieroption das metrische TSP mit CIE94 von Zubchick

    Zwei Mitglieder verwendete Methode Glühen. Diese Methode der konsequenten Lösungsoptimierung. Zuerst nehmen wir eine willkürliche Lösung und versuchen sie dann schrittweise zu verbessern. Bei jedem Schritt wählen wir eine einfache Transformation der vorherigen Lösung. Tauschen Sie beispielsweise ein paar zufällige Farben oder benachbarte Farben aus, drehen Sie ein Stück Blumen um oder platzieren Sie es an einem anderen Ort. Nach einer solchen Permutation gemäß der Qualitätsfunktion der Lösungen wird die Qualität der vorherigen und der nächsten Lösung verglichen.






    Verschiedene Sortiermöglichkeiten nach der Glühmethode von AOrazaev

    Wenn dies keine Glühmethode , sondern eine Gradientenabstiegsmethode wäre, würde er immer von einer Lösung mit schlechterer Qualität zu einer Lösung mit besserer Qualität übergehen . Eine solche Methode führt jedoch zu lokalen Optima, wenn es unmöglich ist, die Lösung mit einer einfachen Transformation zu verbessern. Wenn sich jedoch alles grundlegend ändert, können Sie ein besseres Ergebnis erzielen. Daher verschlechtert das Temperverfahren manchmal die Lösung. Aufgrund dessen ist es möglich, lokale Optima bei der Suche nach einem globalen Optimum loszuwerden. Die Lösungen waren nicht schlecht, aber nicht gut genug in der Nähe.

    Zwei unserer anderen Kollegen verwendeten genetische Algorithmen und erzielten entweder kein gutes Ergebnis oder sie verwendeten eine erfolglose Qualitätsfunktion. Ohne die Version von XtremAlRavenHierbei wurde von der unabhängig erhaltenen TSP-Lösung ausgegangen, die jedoch nicht signifikant verbessert werden konnte.


    Ein Versuch, den modifizierten TSP mit dem genetischen Algorithmus in der CIE1994-Metrik von XtremAlRaven zu verbessern

    Bisher habe ich gesagt, dass das Ergebnis nur algorithmisch erhalten werden kann, aber abgesehen von der Auswahl eines bestimmten Algorithmus war ein manueller Eingriff möglich. Zunächst versuchten einige Teilnehmer, die Farben zunächst um mehrere ausgewählte Punkte (z. B. um Schwarz, Rot, Grün) zu gruppieren, alle Zonen einzeln zu optimieren und sie dann zusammenzukleben.

    Ich habe versucht, die Farben in manuell ausgewählten Gruppen anzuordnen (damit sich ähnliche gesättigte Farben nicht miteinander vermischen), Grenzfarben zu finden, damit sie sich nahtlos ineinander verwandeln, und jede Gruppe zwischen den Grenzfarben zu sortieren. Mit dieser Methode können Sie eine Lösung finden, die von weitem besser aussieht, da sie an verschiedenen Stellen weniger als die gleichen Farbflecken aufweist. Wenn im Zauberer jedoch nur 5 Farben angezeigt werden, sieht sie etwas schlechter aus.

    Tatsächlich schien die Aufgabe schwierig zu sein, denn bevor der Wettbewerb angekündigt wurde, blieben die Entwickler des Zauberers anderthalb Monate lang offen, wie die Farben gut angeordnet werden sollten. Am Ende haben sie selbst eine gute Lösung gefunden, die qualitativ mit denen vergleichbar ist, die später am Wettbewerb teilgenommen haben. Wenn Sie einige Elemente der Farbtheorie im Voraus nicht kennen, ist es außerdem schwierig zu verstehen, wie Sie dieses Problem gut lösen können. Meine Entscheidung war am dritten Tag des Wettbewerbs fertig, die meisten anderen - in der ersten Woche.


    Endgültige Sortierung

    Es gab bereits eine Schwierigkeit für das Team, das in den Zauberer verwickelt war - sie mussten sich für eine von fast vierzig entscheiden.

    Jetzt auch beliebt: