Rozpoznanie wykresu na podstawie obrazka

Zastanawiam się jak przy użyciu C# wydobyć dane z wykresu w postaci obrazu (przykład poniżej).

Na chwilę obecną wyobrażam sobie to tak:

• za pomocą OCR sczytuję wszystkie liczby z wykresu,
• liczę pixele między wartościami OX, dzięki czemu mogę im przypisać miesiące,
• liczę pixele między wartościami OY, dzięki czemumogę każdej dacie przypisać dokładniejszą wartość,
• szukam wszystkich pixeli koloru krzywej, przypisuję im wartości x-y, usuwam duplikaty,
• choć jeszcze nie wymyśliłem jak przypiszę wartości X i Y dla danych zebranych przy użyciu OCR.

Wydaje mi się że podejście może działać, choć weryfikacja pixeli może być bardzo słaba wydajnościowo.

Może ktoś byłby w stanie polecić jakieś lepsze podejście? Jestem otwarty na pomysły. Może jest jakaś biblioteka C# do czytania wykresów o której nie słyszałem?

szukam wszystkich pixeli koloru krzywej, przypisuję im wartości x-y, usuwam duplikaty,

Ale skąd duplikaty? Jeśli dla każdego x będziesz iterować z góry na dół po y, to natrafisz na linię i już, możesz przerwać iterację po y. No, ew. dojść do końca niebieskiej linii i policzyć, gdzie ma środek. W końcu wykres jest nieidealny, bo niebieska linia symbolizuje punkt, ale ma pewną grubość.

a pomocą OCR sczytuję wszystkie liczby z wykresu,

Czy będzie to potrzebne? W końcu masz szarą siatkę. Jeśli wykresy będą takie same (albo jeśli będzie to tylko jeden wykres), to można by pominąć czytanie liczb i próbować wykryć samą siatkę.

Może ktoś byłby w stanie polecić jakieś lepsze podejście?

Inne jakie mi przychodzi na myśl, to, żeby znaleźć początek niebieskiej linii i poruszać się do przodu tylko w obrębie niebieskiej linii (wykrywać, czy niebieska linia idzie w górę, czy w dół). Wtedy powinno być mniej pikseli do iteracji.

przy użyciu C#

Nie wiem jak w C#, piszę ogólnie, jakbym to zrobił w innym języku.

Ale skąd duplikaty? Jeśli dla każdego x będziesz iterować z góry na dół po y, to natrafisz na linię i już, możesz przerwać iterację po y. No, ew. dojść do końca niebieskiej linii i policzyć, gdzie ma środek. W końcu wykres jest nieidealny, bo niebieska linia symbolizuje punkt, ale ma pewną grubość.

Tak ja piszesz, linia ma swoją grubość, planowałem usuwać powtarzające się wartości dla OX lub uśredniać, jeszcze nie wiem.

Czy będzie to potrzebne? W końcu masz szarą siatkę. Jeśli wykresy będą takie same (albo jeśli będzie to tylko jeden wykres), to można by pominąć czytanie liczb i próbować wykryć samą siatkę.

To jest bardzo dobre pytanie, jest szansa że może przynajmniej kategorie wykresów będą miały te same wartości OY, do sprawdzenia. Choć trochę boję się hardcodować wartości na wypadek gdyby z czasem weszły jakieś zmiany których bym nie wyłapał na pierwszy rzut oka.

Inne jakie mi przychodzi na myśl, to, żeby znaleźć początek niebieskiej linii i poruszać się do przodu tylko w obrębie niebieskiej linii (wykrywać, czy niebieska linia idzie w górę, czy w dół). Wtedy powinno być mniej pikseli do iteracji.

Coś na zasadzie: szukam początku linii -> idę pixel w prawo, jak jest niebieski ok, jak nie to szukam góra/dół itd? Brzmi dobrze.

bakunet napisał(a):

Coś na zasadzie: szukam początku linii -> idę pixel w prawo, jak jest niebieski ok, jak nie to szukam góra/dół itd? Brzmi dobrze.

Zwróć też uwagę, że to nie muszą być dokładnie te same kolory, więc trzeba brać poprawkę/uwzględnić pewną tolerancję. Ew. zrobić jakiś preprocessing, żeby zminimalizować liczbę kolorów.

Tak ja piszesz, linia ma swoją grubość, planowałem usuwać powtarzające się wartości dla OX lub uśredniać, jeszcze nie wiem.

Mógłbyś też wykryć krawędzie jakimś kernelem https://en.wikipedia.org/wiki/Kernel_(image_processing)
chociaż nie wiem, czy to konieczne.

i tak pewnie zależy od tego, jak będą dane wyglądać. Wykres z pierwszego posta jest wyraźny, myślę, że łatwo byłoby zanalizować te linie, jeśli wykres będzie wyglądał tak wyraźnie. Gorzej jeśli miałbyś analizować jakieś niewyraźne wykresy zeskanowane z książek czy coś.

Na pewno nie ma tych danych nigdzie wystawionych?

Jeżeli ten wykres jest u ciebie renderowany (przeglądarka/appka), to nie możesz z requesta ich wyciągnąć?

Zwróć też uwagę, że to nie muszą być dokładnie te same kolory, więc trzeba brać poprawkę/uwzględnić pewną tolerancję. Ew. zrobić jakiś preprocessing, żeby zminimalizować liczbę kolorów.

Słuszna opcja. Mogę wykorzystać albo zasięg kolorów albo pozamieniać kolory, coś na zasadzie:

private static void ClearImage(string image, string updated)
        {
            Bitmap myBitmap = new Bitmap(image);
            const float limit = 0.3f;
            for (int i = 0; i < myBitmap.Width; i++)
            {
                for (int j = 0; j < myBitmap.Height; j++)
                {
                    Color c = myBitmap.GetPixel(i, j);
                    if (c.GetBrightness() > limit)
                    {
                        myBitmap.SetPixel(i, j, Color.White);
                    }
                }
            }
            myBitmap.Save(updated);
        }

WeiXiao napisał(a):

Na pewno nie ma tych danych nigdzie wystawionych?

Niestety, już testowałem pod tym kątem.

Zrobiłem to kiedyś (miałem 16 lat i pisałem to do pracy inżynierskiej studenta materiałoznawstwa:P), o ile pamiętam to tak to zrobiłem:

• zamieniłem wszystko na tablicę dwuwymiarową True/False (czyli czy pikselowi X, Y jest bliżej do czarnego (True) czy białego (False)
• pobrałem OCR liczby z wykresu (taki OCR własnej roboty, zapisałem 9 obrazków z każdym znakiem i porównywałem, który obrazek ma największą zgodność z cyframi na wykresie)
• leciałem od lewej strony każdy pixel od góry do dołu. Pobrałem linie osi, czyli np. oś Y zaczyna się 3 px od góry i wynosi 10, a kończy 350 px od góry i wynosi tam -10
• wyliczałem wartość parametru, czyli jak daleko jest piksel linii wykresu jest od górnej osi i wyliczałem, że jeśli jest np. 30% od góry, a cała oś Y ma pikseli długości itd. Jeśli linia ma 6 px długości to dodaj połowę czyli 3 px do odległości od górnej osi.

itou123 napisał(a):

• leciałem od lewej strony każdy pixel od góry do dołu. Pobrałem linie osi, czyli np. oś Y zaczyna się 3 px od góry i wynosi 10, a kończy 350 px od góry i wynosi tam -10

Skąd wiedziałeś że jaka jest wartość osi? Były to stałe wartości?

Ale pomysł z OCR własnej roboty podoba mi się, może rozwiązać problem skuteczności OCR API oraz szukania wartości na osiach.

bakunet napisał(a):

itou123 napisał(a):

• leciałem od lewej strony każdy pixel od góry do dołu. Pobrałem linie osi, czyli np. oś Y zaczyna się 3 px od góry i wynosi 10, a kończy 350 px od góry i wynosi tam -10

Skąd wiedziałeś że jaka jest wartość osi? Były to stałe wartości?

Ale pomysł z OCR własnej roboty podoba mi się, może rozwiązać problem skuteczności OCR API oraz szukania wartości na osiach.

Wartości były zmienne, ustalałem to jak na obrazku poniżej. Czyli OCR odczytuje jaka liczba jest w obszarze 70 px od prawej strony obrazka i między zerowym a 60 px od góry.
Następnie szukam poziomej linii między 20 a 60 px i ona pokazuje mi gdzie jest 10.

Odczytywałem około 5 różnych typów wykresów - rozpoznawałem je i na podstawie tego stosowałem inną procedurę (algorytm) do odczytania danych. Poniżej przykładowe wykresy.

itou123 napisał(a):

Wartości były zmienne, ustalałem to jak na obrazku poniżej. Czyli OCR odczytuje jaka liczba jest w obszarze 70 px od prawej strony obrazka i między zerowym a 60 px od góry.
Następnie szukam poziomej linii między 20 a 60 px i ona pokazuje mi gdzie jest 10.

Jest spora szansa na to, że wartości oY są podane zawsze w tym samym miejscu, choć będę musiał to zweryfikować na większej próbie. Ale jeśli tak, to spokojnie będę mógł zaadoptować Twoje rozwiązanie. Dzięki.

Jeśli chodzi o piksele, to zamiast GetPixel i SetPixel użyj LockBits i operacje na tablicy, będzie znacznie szybciej. Bitmapę należy postrzegać jako tablice pikseli rysowanych linia po linii.

Poniżej kawałki kodu z moich hobbystycznych projektów. To są tylko przykłady, które mają naprowadzić na właściwą drogę, czego szukać, a nie gotowce. Jest możliwe, że nie będzie się kompilować lub będzie czegoś brakować, ale powinno być zrozumiałe, co jest potrzebne, i jak działa.

Skopiowanie tablicy do bitmapy "jak leci":

byte[] Data = new Data[640*480*3];
Bitmap Bmp = new Bitmap(640, 480, PixelFormat.Format24bppRgb);
BitmapData Bmp_ = Bmp.LockBits(new Rectangle(0, 0, Bmp.Width, Bmp.Height), ImageLockMode.ReadWrite, PixelFormat.Format24bppRgb);
System.Runtime.InteropServices.Marshal.Copy(Data, 0, Bmp_.Scan0, 640 * 480 * 3);
ToBitmapBmp.UnlockBits(Bmp_);

Operacja na pikselach (musi być włączone pozwolenie na unsafe w opcjach kompilacji), przepisanie piksel po pikselu z tablicy bajtów dowolnej długości do bitmapy (zakodowanie bajtów w kolorach):

byte[] Raw = new byte[10000];
Bitmap ImgBitmap = new Bitmap(640, 480, PixelFormat.Format24bppRgb);
int ImgW = ImgBitmap.Width;
int ImgH = ImgBitmap.Height;
GraphicsUnit GUP = GraphicsUnit.Pixel;
BitmapData ImgBitmap_ = ImgBitmap.LockBits(Rectangle.Round(ImgBitmap.GetBounds(ref GUP)), ImageLockMode.ReadWrite, PixelFormat.Format24bppRgb);
unsafe
{
    int RawPointer = 0;
    byte* ImgPointer = (byte*)ImgBitmap_.Scan0;
    
    // Create image iterated by rows and columns without the last, not full-width row
    for (int Y = 0; Y < (ImgH - 1); Y++)
    {
        for (int X = 0; X < ImgW; X++)
        {
            ImgPointer[0] = Raw[RawPointer + 0];
            ImgPointer[1] = Raw[RawPointer + 1];
            ImgPointer[2] = Raw[RawPointer + 2];
            RawPointer += 3;
            ImgPointer += 3;
        }
        ImgPointer += ImgBitmap_.Stride - (3 * ImgW);
    }
    
    // Put the last bytes in the last row, which may be not as length as image width
    while (RawPointer < Raw_Length)
    {
        ImgPointer[0] = Raw[RawPointer];
        RawPointer++;
        ImgPointer++;
    }
}
ImgBitmap.UnlockBits(ImgBitmap_);

Akurat wstawiłem kawałki kodu, które malują bitmapę na podstawie tablicy, ale działanie odwrotne, czyli odczyt pikseli, jest bardzo podobne, tylko teraz nie mam "na wierzchu" czegoś, co mogę wkleić jako przykład.

LukeJL napisał(a):

bakunet napisał(a):

Coś na zasadzie: szukam początku linii -> idę pixel w prawo, jak jest niebieski ok, jak nie to szukam góra/dół itd? Brzmi dobrze.

Zwróć też uwagę, że to nie muszą być dokładnie te same kolory, więc trzeba brać poprawkę/uwzględnić pewną tolerancję. Ew. zrobić jakiś preprocessing, żeby zminimalizować liczbę kolorów.

Tak ja piszesz, linia ma swoją grubość, planowałem usuwać powtarzające się wartości dla OX lub uśredniać, jeszcze nie wiem.

Mógłbyś też wykryć krawędzie jakimś kernelem https://en.wikipedia.org/wiki/Kernel_(image_processing)
chociaż nie wiem, czy to konieczne.

i tak pewnie zależy od tego, jak będą dane wyglądać. Wykres z pierwszego posta jest wyraźny, myślę, że łatwo byłoby zanalizować te linie, jeśli wykres będzie wyglądał tak wyraźnie. Gorzej jeśli miałbyś analizować jakieś niewyraźne wykresy zeskanowane z książek czy coś.

Do tego dodam od siebie, że warto rozdzielić zadanie na dwie niezależne czynności. Pierwsza to przygotowanie bitmapy, a druga to właściwy odczyt wykresu.

W ramach pierwszej czynności warto umożliwić zapisanie lub wyświetlanie przygotowanej bitmapy. Finalnie powinna być bitmapa czarno-biała (tylko białe i czarne piksele), gdzie biały piksel jest poza wykresem, a czarny jest linią wykresu.

Na etapie kolorowej bitmapy, to można użyć wspomniany kernel i rozpoznawanie kolorów (poprzez obliczanie odległości składowych do jakiegoś konkretnego koloru). Linie siatki powinny zniknąć. Można też posłużyć się przestrzenią kolorów inną niż RGB, np. HSV lub YUV. Możliwości jest naprawdę sporo i niektóre automatyczne czynności na pikselach nie są trudne w implementacji.

Na etapie czarno-białej bitmapy jeszcze można popróbować to: https://pl.wikipedia.org/wiki/Cyfrowe_przetwarzanie_obraz%C3%B3w_binarnych , jeżeli zostaną jakieś pojedyncze czarne i białe kropki, które mogą fałszować odczyt wykresu.

Bitmapa przygotowana do odczytu powinna zawierać sam wykres, bez siatki, bez liczb, ani innych napisów.

Natomiast sam odczyt zrobiłbym tak:
Dla każdego X w poziomie:

1. Patrząc od dołu poszukać Y1 z pierwszym czarnym pikselem.
2. Patrząc od góry poszukać Y2 z pierwszym czarnym pikselem.
3. Współrzędna Y to średnia arytmetyczna Y1 i Y2.
4. Jeżeli nie znaleziono czarnego piksela, to odnotować ten fakt (np. jako Y= -1).
5. Na koniec, dla każdego X, dla którego ustalono Y=-1, oszacować Y metodą interpolacji na podstawie najbliższych znanych wartości Y.

Taki algorytm powinien być odporny na linie grubszą niż jeden piksel (średnia ze współrzędnej górnej i dolnej krawędzi), a także odporny na przerwaną linię (z powodu niedoskonałości pierwszego etapu), gdzie brakujące wartości zostaną oszacowane.

@andrzejlisek: Dopiero znalazłem czas żeby się pochylić nad Twoim rozwiązaniem. Po Twoim poście zrobiłem mały research i znalazem podobne podejście: https://stackoverflow.com/a/24702215

W tym samym pytaniu jest przedstawiona jeszcze wydajeniejsza opcja: https://stackoverflow.com/a/34801225 Gość zrobił nawet porównanie wydajności różnych podejść. Ale tak jak piszesz, GetPixel SetPixel jest kilkadziesiąt razy wolniejsze niż LockBits. DirectBitmap jest tylko minimalnie szybsza niż Twoja opcja.

Dzięki za sugestię, sprawdzę jeszcze jak przy nowych podejściach, jak już je do końca zrozumiem, będę mógł czytać cyfry i określać przedziały danych dla OX i OY, może to być dodatkowym wyzwaniem.

bakunet napisał(a):

@andrzejlisek: Dopiero znalazłem czas żeby się pochylić nad Twoim rozwiązaniem. Po Twoim poście zrobiłem mały research i znalazem podobne podejście: https://stackoverflow.com/a/24702215

W tym samym pytaniu jest przedstawiona jeszcze wydajeniejsza opcja: https://stackoverflow.com/a/34801225 Gość zrobił nawet porównanie wydajności różnych podejść. Ale tak jak piszesz, GetPixel SetPixel jest kilkadziesiąt razy wolniejsze niż LockBits. DirectBitmap jest tylko minimalnie szybsza niż Twoja opcja.

Dzięki za sugestię, sprawdzę jeszcze jak przy nowych podejściach, jak już je do końca zrozumiem, będę mógł czytać cyfry i określać przedziały danych dla OX i OY, może to być dodatkowym wyzwaniem.

Myślę, że w tym przypadku najlepiej "przepisać" bitmapę do zwykłej tablicy liczb jednowymiarowej lub dwuwymiarowej, mogą być trzy tablice po jednej dla każdej składowej koloru. Kształt tablicy i typ wartości pozycji w niej sobie dobrać tak, jak się lubi. Samo przepisanie z wykorzystaniem metod wymienionych w StackOverflow powinno trwać moment i nie mam sensu za wszelką cenę walczyć o przyspieszenie. Najważniejszą częścią algorytmu będą tylko operacje na tablicach, będzie to najbardziej wydajne, bo poza samym odczytem, zapisem wartości i niezbędnymi przeliczeniami, nic więcej nie będzie się działo, nawet nie będzie konwersji typu, ewentualna konwersja nastąpi podczas przepisania.