Oppfølging: "Sortere" farger av egenart

stemmer
19

Original Spørsmål

Dersom du får N maksimalt fjerne farger (og noen assosiert avstand metrisk), kan du komme opp med en måte å sortere disse fargene i litt orden slik at den første M er også rimelig nær å være et maksimalt distinkt sett?

Med andre ord, gitt en haug med forskjellige farger, komme opp med en bestilling så jeg kan bruke så mange farger som jeg trenger å starte på begynnelsen og være rimelig trygg på at de er alle forskjellige og at nærliggende farger er også veldig tydelig (for eksempel blålig rød er ikke ved siden av rødlig blå).

Tilfeldiggjørings er OK, men absolutt ikke optimal.

Avklaring: Gitt noen store og visuelt distinkt sett av farger (si 256 eller 1024), ønsker jeg å sortere dem slik at når jeg bruker den første, sier 16 av dem at jeg får en relativt visuelt distinkt undergruppe av farger. Dette er tilsvarende, omtrent, for å si at jeg ønsker å sortere denne listen over 1024 slik at de nærmere individuelle farger er visuelt, jo lenger fra hverandre de er på listen.

Publisert på 04/08/2008 klokken 15:14
kilden bruker
På andre språk...                            


9 svar

stemmer
2

N maksimalt fjernt farger kan betraktes som et sett av godt fordelte punkter i en tre-dimensjonal (farge) plass. Hvis man kan generere dem fra en Halton sekvens , da en hvilken som helst prefiks (de første M farger) består også av godt fordelte punkter.

Svarte 25/08/2008 kl. 08:44
kilden bruker

stemmer
2

Det synes oppfatningen er viktig for deg, i så fall vil du kanskje vurdere å arbeide med en perseptuelle fargeområde som YUV, YCbCr eller Lab. Hver gang jeg har brukt dem, de har gitt meg mye bedre resultater enn sRGB alene.

Konvertering til og fra sRGB kan være smertefullt, men i ditt tilfelle kan det faktisk gjøre algoritmen enklere og som en bonus vil det stort sett jobber for farge blinds også!

Svarte 12/08/2008 kl. 12:33
kilden bruker

stemmer
2

Dette problemet kalles farge kvantisering, og har mange kjente algoritmer: http://en.wikipedia.org/wiki/Color_quantization Jeg kjenner folk som gjennomførte den octree tilnærming til god effekt.

Svarte 12/08/2008 kl. 12:11
kilden bruker

stemmer
2

Dette høres også for meg som en slags motstand grafen hvor du prøver å kartlegge minste motstands vei. Hvis du inverse kravene, banen til maksimal motstand, kan det kanskje brukes til å produsere et sett som fra starten produserer maksimal forskjell som du går, og mot slutten begynner å gå tilbake til verdier nærmere de andre.

For eksempel, her er en måte å kanskje gjøre hva du vil.

  1. Beregn avstanden (ref ditt andre innlegg ) fra hver farge til alle andre farger
  2. Sum avstander for hver farge, dette gir deg en indikasjon på hvor langt unna denne fargen er fra alle andre farger totalt
  3. Bestill listen etter avstand, går ned

Dette vil, det synes, produserer en liste som starter med den fargen som er lengst borte fra alle andre farger, og deretter gå ned, farger mot slutten av listen ville være nærmere andre farger generelt.

Edit: Leser ditt svar til mitt første innlegg, om den romlige inndelingen, ville ikke akkurat passer beskrivelsen over, siden farger nær andre farger ville falle til bunnen av listen, men la oss si du har en klynge av farger eller annet sted, på minst en av fargene fra at klyngen ville bli plassert nær begynnelsen av listen, og det ville være den som vanligvis var lengst borte fra alle andre farger totalt. Hvis det er fornuftig.

Svarte 04/08/2008 kl. 15:38
kilden bruker

stemmer
1

Du kan bare sortere kandidat farger basert på den maksimale-distansert av minsteavstand til noen av de indeks farger.

Bruke euklidsk farge avstand:

public double colordistance(Color color0, Color color1) {
    int c0 = color0.getRGB();
    int c1 = color1.getRGB();
    return distance(((c0>>16)&0xFF), ((c0>>8)&0xFF), (c0&0xFF), ((c1>>16)&0xFF), ((c1>>8)&0xFF), (c1&0xFF));
}

public double distance(int r1, int g1, int b1, int r2, int g2, int b2) {
    int dr = (r1 - r2);
    int dg = (g1 - g2);
    int db = (b1 - b2);
    return Math.sqrt(dr * dr + dg * dg + db * db);
}

Selv om du kan erstatte den med noe du ønsker. Den trenger bare en farge avstand rutine.

public void colordistancesort(Color[] candidateColors, Color[] indexColors) {
    double current;

    double distance[] = new double[candidateColors.length];
    for (int j = 0; j < candidateColors.length; j++) {
        distance[j] = -1;
        for (int k = 0; k < indexColors.length; k++) {
            current = colordistance(indexColors[k], candidateColors[j]);
            if ((distance[j] == -1) || (current < distance[j])) {
                distance[j] = current;
            }
        }
    }

    //just sorts.
    for (int j = 0; j < candidateColors.length; j++) {
        for (int k = j + 1; k < candidateColors.length; k++) {
            if (distance[j] > distance[k]) {
                double d = distance[k];
                distance[k] = distance[j];
                distance[j] = d;

                Color m = candidateColors[k];
                candidateColors[k] = candidateColors[j];
                candidateColors[j] = m;
            }
        }
    }
}
Svarte 03/09/2012 kl. 20:50
kilden bruker

stemmer
1
  1. Start med to lister. CandidateColors, som i utgangspunktet inneholder dine forskjellige farger og SortedColors, som er i utgangspunktet tom.
  2. Plukk alle farger og fjerne det fra CandidateColors og sette det inn SortedColors. Dette er den første fargen, og vil være den mest vanlige, så det er et bra sted å velge en farge som jives godt med søknaden.
  3. For hver farge i CandidateColors beregne total distanse. Den totale avstanden er summen av avstanden fra CandidateColor til hver av fargene i SortedColors.
  4. Fjerne fargen med den største totale avstanden fra CandidateColors og legge den til på slutten av SortedColors.
  5. Hvis CandidateColors ikke er tom, går du tilbake til trinn 3.

Dette grådig algoritme bør gi deg gode resultater.

Svarte 21/11/2008 kl. 09:29
kilden bruker

stemmer
1

Hvis jeg forstå spørsmålet riktig, ønsker du å oppnå undergruppe av M farger med høyest gjennomsnittlig avstand mellom farger, gitt en viss avstand funksjon d .

Sagt på en annen måte, med tanke på første sett av N farger som en stor, urettet graf der alle farger er koblet til, vil du finne den lengste banen som besøker noen M noder.

Løse NP-komplette grafen problemer er langt mer enn meg jeg er redd, men du kan prøve å kjøre en enkel fysisk simulering:

  1. Generere M tilfeldige punkter i fargerommet
  2. Beregne avstanden mellom hvert punkt
  3. Beregn frastøting vektorer for hvert punkt som vil bevege den bort fra alle andre punkter (ved å bruke 1 / ( avstand ^ 2) som størrelsen på vektoren I)
  4. Sum frastøtning vektorene for hvert punkt
  5. Oppdatering av posisjonen til hvert punkt i henhold til de summerte frastøting vektorene
  6. Begrense hvilke som helst av bundne koordinater (for eksempel lyshet kommer negativ eller over en)
  7. Gjenta fra trinn 2 til punktene stabilisere
  8. For hvert punkt, velg den nærmeste fargen fra det opprinnelige settet med N

Det er langt fra effektiv, men for lite M kan det være effektiv nok, og det vil gi nær optimale resultater.

Hvis farge avstand funksjon er enkel, kan det være en mer deterministisk måte å generere den optimale delsett.

Svarte 16/10/2008 kl. 17:11
kilden bruker

stemmer
0

Du kan dele dem i RGB HEX format slik at du kan sammenligne R med R av en annen farge, samme med G og B.

Samme format som HTML

XX XX XX
RR GG BB

00 00 00 = black
ff ff ff = white
ff 00 00 = red
00 ff 00 = green
00 00 ff = blue

Så det eneste du trenger å bestemme er hvor nær du vil at fargene og hva som er en akseptabel forskjell for segmentene som skal vurderes annerledes.

Svarte 04/08/2008 kl. 15:31
kilden bruker

stemmer
0

Mener du at fra et sett av N farger, må du velge M farger, hvor M <N, slik at M er den beste representasjonen av de N fargene i M plass?

Som et bedre eksempel redusere en ekte farger (24 bit fargerommet) til en 8-bit kartlagt fargerommet (GIF?).

Det er kvantisering algoritmer for dette, som Adaptive Spatial Subdivision algoritmen som brukes av Imagemagic.

Disse algoritmer vanligvis ikke bare plukke eksisterende farger fra kilden plass, men skaper nye farger i målet plass som mest ligner kilde farger. Som et forenklet eksempel, hvis du har 3 farger i originalbildet der to er rød (med forskjellig intensitet eller blålige nyanser etc.) og den tredje er blå, og må redusere til to farger, kan målbildet har en rød farge som er en slags gjennomsnitt av de opprinnelige to røde + den blå fargen fra det opprinnelige bildet.

Hvis du trenger noe annet så jeg ikke forstår spørsmålet ditt :)

Svarte 04/08/2008 kl. 15:29
kilden bruker

Cookies help us deliver our services. By using our services, you agree to our use of cookies. Learn more