Histogram Equalization - Spielraum für Optimierungen?



  • Hallo

    Ich habe eine grosse Matrix aus float s. Zunächst equalisiere ich das Histogramm, danach schaue ich die equalisierten float s - die nun im Intervall [0,1) liegen - in einer LUT nach. Das Ergebnis schreibe ich dann in eine zweite, gleich grosse Matrix.

    Werte, für die IsAbnormal true zurückgibt, sollen in der gesamten Funktion nicht berücksichtigt werden.

    Wie ich bei der Histogram Equalization vorgehe:
    Da die Werte kontinuierlich sind, kann ich die Cdf nicht einfach als ein Array speichern, sondern muss stattdessen die einzelnen Werte in einem sortierten Vektor ablegen. Um nun mit diesem Vektor Cdf(x) zu berechnen, muss ich x im Vektor suchen. Seine Position ist der equalisierte Wert.

    Hier der (vereinfachte) Code:

    template< typename MatrixT >
    void OperatorHistographic( MatrixT const& Matrix, ImageT& Output )
    {
    	static std::vector< float > CdfPrime;
    	CdfPrime.resize( 0 );
    	CdfPrime.reserve( Matrix.Size() );
    
    	for( Vec2s C{ 0, 0 }; C.y < Matrix.Height(); ++C.y )
    	{
    		for( C.x = 0; C.x < Matrix.Width(); ++C.x )
    		{
    			const float Current = Matrix( C );
    			if( !IsAbnormal( Current ) )
    			{
    				CdfPrime.push_back( Current );
    			}
    		}
    	}
    
    	std::sort( CdfPrime.begin(), CdfPrime.end() );
    
    	const float Factor = 1.f / CdfPrime.size();
    	for( Vec2s C{ 0, 0 }; C.y < Matrix.Height(); ++C.y )
    	{
    		for( C.x = 0; C.x < Matrix.Width(); ++C.x )
    		{
    			const float Current = Matrix( C );
    			if( !IsAbnormal( Current ) )
    			{
    				const auto Dist = std::distance( CdfPrime.begin(), std::lower_bound( CdfPrime.begin(), CdfPrime.end(), Current ) );
    				const ColorT Color = Palette( Factor * Dist );
    				Output.SetPixel( C, Color );
    			}
    		}
    	}
    }
    

    Der Algorithmus funktioniert einwandfrei, braucht aber gut 270ms für eine 1000x1000 Matrix. Davon gehen ~200ms für Zeilen 23-35 drauf und ~60ms für std::sort .
    Meine Frage: Kann man dieses Pro­ze­de­re auf der algorithmischen Ebene optimieren?

    LG



  • Du kannst das beschleunigen, indem du die Koordinaten in den zu sortierenden Vektor mit einbindest und dir damit das Suchen sparst. Damit läuft das bei mir in 25 ms statt 56 ms für eine 1000x1000-Matrix.
    270 ms ist aber auch langsam, zumindest für einen normalen Rechner. Alle Optimierungen eingeschaltet?

    bool IsAbnormal(float v)
    {
      return v<0.1 || v>0.9;
    }
    
    Color Palette(float v)
    {
      byte l=v*255.0;
      return Color(l,l,l);
    }
    
    template< typename MatrixT >
    void OperatorHistographic( MatrixT const& Matrix, Image& Output )
    {
        static std::vector< std::pair<float,Vec2s> > CdfPrime;
        CdfPrime.resize( 0 );
        CdfPrime.reserve( Matrix.Width() * Matrix.Height() );
    
        for( Vec2s C{ 0, 0 }; C.y < Matrix.Height(); ++C.y )
        {
            for( C.x = 0; C.x < Matrix.Width(); ++C.x )
            {
                const float Current = Matrix[C];
                if( !IsAbnormal( Current ) )
                {
                    CdfPrime.emplace_back( Current, C );
                }
            }
        }
    
        SORT_BY_MEMBER(CdfPrime,first);
    
        const float Factor = 1.f / CdfPrime.size();
        float currentPaletteIndex=0;
        foreach_i(p,CdfPrime)
        {
          auto Color = Palette(currentPaletteIndex);
          Output.pixel(p.second)=Color;
          if (i>0 && CdfPrime[i-1].first!=p.first)currentPaletteIndex=i*Factor;
        }
    }
    


  • Darauf wäre ich nie gekommen. Der Vorschlag ist Gold wert, von 270ms auf 120ms runter!

    Optimierungen habe ich schon an, aber meine Palette -Funktion - oder Klasse, im echten Code - beansprucht auch noch einiges an Laufzeit bei jedem Lookup und Matrix ist keine normale Matrix, die zeilenweise nacheinander im Speicher liegt, sondern ein Proxy-Objekt, das bei jedem Zugriff auch noch bisschen rechnen muss und wahrscheinlich auch deutlich mehr Cache-Misses nach sich zieht.

    Vielen Dank für die Hilfe. 🙂


Log in to reply