image - مقارنة الصور-خوارزمية سريعة




algorithm comparison computer-vision (8)

أفضل طريقة أعرفها هي استخدام تجسيد إدراكي. يبدو أن هناك تنفيذًا جيدًا لمصدر مفتوح لمثل هذه التجزئة متاح على:

http://phash.org/

والفكرة الرئيسية هي أن كل صورة يتم تقليلها إلى رمز تجزئة صغير أو "بصمة الإصبع" من خلال تحديد الخصائص البارزة في ملف الصورة الأصلي وتمييز تمثيل مضغوط لتلك الميزات (بدلاً من تجزئة بيانات الصورة مباشرةً). وهذا يعني أن معدل الإيجابيات الخاطئة ينخفض ​​بشكل كبير عبر مقاربة مبسطة مثل تقليل الصور إلى صورة بحجم بصمة صغيرة ومقارنة البصمات.

يقدم phash عدة أنواع من التجزئة ويمكن استخدامه للصور أو الصوت أو الفيديو.

أتطلع إلى إنشاء جدول أساسي للصور ثم مقارنة أي صور جديدة في مقابل ذلك لتحديد ما إذا كانت الصورة الجديدة هي نسخة مطابقة تمامًا (أو قريبة) من القاعدة.

على سبيل المثال: إذا كنت ترغب في تقليل سعة التخزين لنفس الصورة 100 مرة ، فيمكنك تخزين نسخة واحدة منها وتوفير ارتباطات مرجعية لها. عندما يتم إدخال صورة جديدة تريد مقارنتها مع صورة حالية للتأكد من أنها ليست أفكارًا مكررة ...؟

كانت إحدى الأفكار الخاصة بي هي تصغير الصورة المصغرة الصغيرة ثم اختيار مواقع 100 بكسل عشوائيًا ومقارنتها.


إذا كان لديك عدد كبير من الصور ، فابحث عن مرشح بلوم ، الذي يستخدم تجزئات متعددة للحصول على نتيجة واقعية ولكنها فعالة. إذا كان عدد الصور غير ضخم ، فيجب أن تكون التجزئة المشفرة مثل md5 كافية.


أعتقد أن إسقاط حجم الصورة إلى حجم أيقونة تقريبًا ، مثل 48 × 48 ، ثم التحويل إلى تدرج الرمادي ، ثم أخذ الفرق بين وحدات البكسل ، أو دلتا ، يجب أن يعمل جيدًا. نظرًا لأننا نقارن التغيير في لون البيكسل ، بدلاً من لون البيكسل الفعلي ، فلن يهم إذا كانت الصورة أخف أو أغمق قليلاً. ستشكل التغييرات الكبيرة أهمية نظرًا لأنه سيتم فقدان وحدات البكسل التي تصبح خفيفة جدًا / داكنة. يمكنك تطبيق ذلك عبر صف واحد أو على العدد الذي تريده لزيادة الدقة. على الأكثر ستحصل على 47x47 = 2،209 تسميات لتكوين مفتاح قابل للمقارنة.


فيما يلي ثلاث طرق لحل هذه المشكلة (وهناك العديد من الطرق الأخرى).

  • الأول هو نهج قياسي في رؤية الكمبيوتر ، ومطابقة المفتاح. قد يتطلب ذلك بعض المعرفة الأساسية للتنفيذ ، ويمكن أن تكون بطيئة.

  • تستخدم الطريقة الثانية معالجة الصور الأولية فقط ، وهي أسرع من النهج الأول ، وهي سهلة التنفيذ. ومع ذلك ، فإن ما يكتسبه في الفهم ، فإنه يفتقر إلى الصلابة - فالمطابقة تفشل في الصور المقاسة أو المتناوبة أو التي تغير لونها.

  • أما الطريقة الثالثة فهي سريعة وقوية ، ولكن من المحتمل أن تكون الأكثر صعوبة في التنفيذ.

مطابقة Keypoint

أفضل من اختيار 100 نقطة عشوائية هو اختيار 100 نقطة مهمة . تحتوي أجزاء معينة من الصورة على معلومات أكثر من غيرها (خاصة عند الحواف والأركان) ، وهذه هي الأجزاء التي تريد استخدامها لمطابقة الصور الذكية. جوجل " استخراج keypoint " و " keypoint المطابقة " وستجد عدد غير قليل من الأوراق الأكاديمية حول هذا الموضوع. في هذه الأيام ، يمكن القول أن نقاط المفاتيح SIFT هي الأكثر شعبية ، لأنها يمكن أن تتطابق مع الصور تحت مستويات مختلفة ، وتناوب ، وإضاءة. بعض تطبيقات SIFT يمكن العثور عليها here .

جانب سلبي واحد للمطابقة الرئيسية هو وقت تشغيل تطبيق ساذج: O (n ^ 2m) ، حيث n هو عدد نقاط المفاتيح في كل صورة ، و m هو عدد الصور في قاعدة البيانات. قد تجد بعض الخوارزميات الذكية أقرب تطابق أسرع ، مثل quadtrees أو تقسيم الفضاء الثنائي.

الحل البديل: طريقة الرسم البياني

هناك حل آخر أقل قوة ولكنه من المحتمل أن يكون أسرع هو إنشاء مدرج توضيحي للميزات لكل صورة ، واختيار الصورة ذات المدرج التكراري الأقرب إلى الرسم البياني الخاص بالصورة المدخلة. لقد طبّقت هذا البرنامج كطالب جامعي ، واستخدمنا رسم بياني لوني 3 (أحمر ، أخضر ، وأزرق) ، ورسمان توضيحيان للنسيج ، واتجاه وحجم. سوف أعطي التفاصيل أدناه ، ولكن يجب أن أشير إلى أن هذا فقط عملت بشكل جيد لمطابقة الصور جداً مشابهة لصور قاعدة البيانات. يمكن أن تفشل الصور المعاد قياسها أو تدويرها أو التي تم تغيير لونها مع هذه الطريقة ، ولكن التغييرات الصغيرة مثل الاقتصاص لن تؤدي إلى كسر الخوارزمية

إن حساب الرسم البياني للألوان هو أمر بسيط ، فما عليك سوى اختيار نطاق دلاء المدرج التكراري ، ولكل مجموعة عدد وحدات البكسل ذات اللون في هذا النطاق. على سبيل المثال ، ضع في الاعتبار المدرج التكراري "الأخضر" ، ونفترض أن نختار 4 شرائح لمدرجنا البياني: 0-63 و64-127 و 128-191 و 192-255. ثم ، بالنسبة إلى كل بكسل ، ننظر إلى القيمة الخضراء ، ونضيف رصيدًا إلى الدلو المناسب. عند الانتهاء من إجراء الحصر ، نقوم بتقسيم كل مجموعة من مجموعات البيانات على عدد البكسلات في الصورة بأكملها للحصول على رسم بياني عادي للقناة الخضراء.

بالنسبة إلى الرسم البياني لتوجه النسيج ، بدأنا عن طريق إجراء كشف الحافة على الصورة. تحتوي كل نقطة حافة على متجه عادي يشير في الاتجاه العمودي إلى الحافة. قمنا بتكبير زاوية vector العادية في واحدة من 6 دلاء بين 0 و PI (نظرًا لأن الحواف لها تماثل 180 درجة ، قمنا بتحويل الزوايا بين -PI و 0 إلى ما بين 0 و PI). بعد حساب عدد نقاط الحواف في كل اتجاه ، يوجد لدينا رسم بياني غير مقيس يمثل اتجاه النسيج ، والذي قمنا بتسويته بقسمة كل مجموعة على العدد الإجمالي لنقاط الحواف في الصورة.

لحساب الرسم البياني لمقياس النسيج ، لكل نقطة حواف ، قمنا بقياس المسافة إلى أقرب نقطة حافة مع نفس الاتجاه. على سبيل المثال ، إذا كانت نقطة الحافة A لها اتجاه 45 درجة ، فإن الخوارزمية تمشي في هذا الاتجاه حتى تجد نقطة حافة أخرى مع اتجاه 45 درجة (أو ضمن انحراف معقول). بعد حساب هذه المسافة لكل نقطة حافة ، نقوم بتفريغ هذه القيم في مدرج تكراري وتطبيعها عن طريق القسمة على العدد الإجمالي لنقاط الحواف.

لديك الآن 5 رسومات بيانية لكل صورة. لمقارنة صورتين ، فإنك تأخذ القيمة المطلقة للفرق بين كل دلو مدرج تكراري ، ثم تجمع هذه القيم. على سبيل المثال ، لمقارنة الصور A و B ، سنحسب

|A.green_histogram.bucket_1 - B.green_histogram.bucket_1| 

لكل دلو في المدرج الإحصائي الأخضر ، وتكرار للرسم البياني الأخرى ، ثم تلخيص جميع النتائج. كلما كانت النتيجة أصغر ، كلما كانت المباراة أفضل. كرر لجميع الصور في قاعدة البيانات ، والمباراة مع أصغر نتيجة الانتصارات. قد ترغب في الحصول على حد أدنى ، وتستخلص الخوارزمية أعلاه أنه لم يتم العثور على أي تطابق.

الخيار الثالث - Keypoints + أشجار القرار

وهناك نهج ثالث ربما يكون أسرع بكثير من الأخريين ، وهو استخدام غابات النصوص الدلالية (PDF). هذا ينطوي على استخراج نقاط مفاتيح بسيطة واستخدام أشجار قرار جمع لتصنيف الصورة. هذا أسرع من مطابقة المفتاح الفرعي SIFT البسيطة ، لأنه يتجنب عملية المطابقة المكلفة ، ونقاط المفاتيح أبسط بكثير من SIFT ، لذلك يكون استخراج المفاتيح أسرع بكثير. ومع ذلك ، فإنه يحافظ على ثبات أسلوب SIFT في التدوير ، الحجم ، والإضاءة ، وهي ميزة مهمة تفتقر إليها طريقة المدرج التكراري.

تحديث :

خطأي - لا يتعلق ورق غابات النصوص الدلالية بالتحديد بالتطابق مع الصور ، ولكن بالأحرى تسمية المنطقة. الورقة الأصلية التي تتطابق مع هذا هو: التعرف على Keypoint باستخدام الأشجار العشوائية . أيضا ، تستمر الأوراق أدناه في تطوير الأفكار وتمثل حالة الفن (c. 2010):


قد يعني اختيار 100 نقطة عشوائية أن الصور المتشابهة (أو أحيانًا متباينة) سيتم وضع علامة على نفس الصور ، والتي أفترض أنها ليست ما تريده. لن تعمل تجزيئات MD5 إذا كانت الصور بتنسيقات مختلفة (png أو jpeg ، إلخ) أو كانت لها أحجام مختلفة أو كانت تحتوي على بيانات وصفية مختلفة. إن تقليل كل الصور إلى حجم أصغر يعتبر رهانًا جيدًا ، فلا يجب أن تستغرق مقارنة البيكسل مقابل البكسل وقتًا طويلاً طالما أنك تستخدم مكتبة صور جيدة / لغة سريعة ، والحجم صغير بما يكفي.

يمكنك محاولة جعلها صغيرة ، ثم إذا كانت هي نفسها إجراء مقارنة أخرى على حجم أكبر - يمكن أن يكون مزيجا جيدا من السرعة والدقة ...


كما أشار cartman ، يمكنك استخدام أي نوع من قيمة تجزئة للعثور على التكرارات الدقيقة.

نقطة بداية واحدة للعثور على صور قريبة يمكن أن تكون here . هذه أداة تستخدمها شركات CG للتحقق مما إذا كانت الصور التي تم تجديدها لا تزال تعرض المشهد نفسه بشكل أساسي.


لدي فكرة ، والتي يمكن أن تعمل وعلى الأرجح أن تكون سريعة جدا. يمكنك أخذ عينة من الصورة لتقول دقة 80x60 أو مقارنتها ، وتحويلها إلى مقياس رمادي (بعد أخذ عينة فرعية سيكون أسرع). قم بمعالجة الصورتين اللتين تريد مقارنتهما. ثم قم بتشغيل المجموع الطبيعي للفروق المربعة بين صورتين (صورة الاستعلام وكل منها من db) ، أو حتى أفضل ارتباط متقاطع عادي ، والذي يعطي الاستجابة أقرب إلى 1 ، إذا كانت الصورتين متشابهتين. ثم إذا كانت الصور متشابهة يمكنك الانتقال إلى تقنيات أكثر تطوراً للتحقق من أنها نفس الصور. من الواضح أن هذه الخوارزمية خطية من حيث عدد الصور في قاعدة البيانات الخاصة بك ، على الرغم من أنها ستكون سريعة للغاية تصل إلى 10000 صورة في الثانية على الأجهزة الحديثة. إذا كنت بحاجة إلى الثبات للدوران ، فيمكن حساب التدرج السائد لهذه الصورة الصغيرة ، ومن ثم يمكن تدوير نظام الإحداثيات بأكمله إلى التوجه الكنسي ، على الرغم من ذلك ، سيكون أبطأ. لا ، ليس هناك ثبات للقياس هنا.

إذا كنت تريد شيئًا أكثر عمومية أو استخدام قواعد بيانات كبيرة (مليون صورة) ، فأنت بحاجة إلى النظر في نظرية استرجاع الصور (ظهرت الكثير من الأوراق في آخر 5 سنوات). هناك بعض المؤشرات في إجابات أخرى. ولكن قد يكون من المبالغة ، واقتراح النهج المدرج التكراري سوف يؤدي المهمة. على الرغم من أنني أعتقد أن الجمع بين العديد من الأساليب السريعة المختلفة سيكون أفضل.


@jogojapan you brought awesome explanation and visualisation. But as @makagonov mentioned it's missing some rules regarding setting suffix links. It's visible in nice way when going step by step on http://brenden.github.io/ukkonen-animation/ through word 'aabaaabb'. When you go from step 10 to step 11, there is no suffix link from node 5 to node 2 but active point suddenly moves there.

@makagonov since I live in Java world I also tried to follow your implementation to grasp ST building workflow but it was hard to me because of:

  • combining edges with nodes
  • using index pointers instead of references
  • breaks statements;
  • continue statements;

So I ended up with such implementation in Java which I hope reflects all steps in clearer way and will reduce learning time for other Java people:

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class ST {

  public class Node {
    private final int id;
    private final Map<Character, Edge> edges;
    private Node slink;

    public Node(final int id) {
        this.id = id;
        this.edges = new HashMap<>();
    }

    public void setSlink(final Node slink) {
        this.slink = slink;
    }

    public Map<Character, Edge> getEdges() {
        return this.edges;
    }

    public Node getSlink() {
        return this.slink;
    }

    public String toString(final String word) {
        return new StringBuilder()
                .append("{")
                .append("\"id\"")
                .append(":")
                .append(this.id)
                .append(",")
                .append("\"slink\"")
                .append(":")
                .append(this.slink != null ? this.slink.id : null)
                .append(",")
                .append("\"edges\"")
                .append(":")
                .append(edgesToString(word))
                .append("}")
                .toString();
    }

    private StringBuilder edgesToString(final String word) {
        final StringBuilder edgesStringBuilder = new StringBuilder();
        edgesStringBuilder.append("{");
        for(final Map.Entry<Character, Edge> entry : this.edges.entrySet()) {
            edgesStringBuilder.append("\"")
                    .append(entry.getKey())
                    .append("\"")
                    .append(":")
                    .append(entry.getValue().toString(word))
                    .append(",");
        }
        if(!this.edges.isEmpty()) {
            edgesStringBuilder.deleteCharAt(edgesStringBuilder.length() - 1);
        }
        edgesStringBuilder.append("}");
        return edgesStringBuilder;
    }

    public boolean contains(final String word, final String suffix) {
        return !suffix.isEmpty()
                && this.edges.containsKey(suffix.charAt(0))
                && this.edges.get(suffix.charAt(0)).contains(word, suffix);
    }
  }

  public class Edge {
    private final int from;
    private final int to;
    private final Node next;

    public Edge(final int from, final int to, final Node next) {
        this.from = from;
        this.to = to;
        this.next = next;
    }

    public int getFrom() {
        return this.from;
    }

    public int getTo() {
        return this.to;
    }

    public Node getNext() {
        return this.next;
    }

    public int getLength() {
        return this.to - this.from;
    }

    public String toString(final String word) {
        return new StringBuilder()
                .append("{")
                .append("\"content\"")
                .append(":")
                .append("\"")
                .append(word.substring(this.from, this.to))
                .append("\"")
                .append(",")
                .append("\"next\"")
                .append(":")
                .append(this.next != null ? this.next.toString(word) : null)
                .append("}")
                .toString();
    }

    public boolean contains(final String word, final String suffix) {
        if(this.next == null) {
            return word.substring(this.from, this.to).equals(suffix);
        }
        return suffix.startsWith(word.substring(this.from,
                this.to)) && this.next.contains(word, suffix.substring(this.to - this.from));
    }
  }

  public class ActivePoint {
    private final Node activeNode;
    private final Character activeEdgeFirstCharacter;
    private final int activeLength;

    public ActivePoint(final Node activeNode,
                       final Character activeEdgeFirstCharacter,
                       final int activeLength) {
        this.activeNode = activeNode;
        this.activeEdgeFirstCharacter = activeEdgeFirstCharacter;
        this.activeLength = activeLength;
    }

    private Edge getActiveEdge() {
        return this.activeNode.getEdges().get(this.activeEdgeFirstCharacter);
    }

    public boolean pointsToActiveNode() {
        return this.activeLength == 0;
    }

    public boolean activeNodeIs(final Node node) {
        return this.activeNode == node;
    }

    public boolean activeNodeHasEdgeStartingWith(final char character) {
        return this.activeNode.getEdges().containsKey(character);
    }

    public boolean activeNodeHasSlink() {
        return this.activeNode.getSlink() != null;
    }

    public boolean pointsToOnActiveEdge(final String word, final char character) {
        return word.charAt(this.getActiveEdge().getFrom() + this.activeLength) == character;
    }

    public boolean pointsToTheEndOfActiveEdge() {
        return this.getActiveEdge().getLength() == this.activeLength;
    }

    public boolean pointsAfterTheEndOfActiveEdge() {
        return this.getActiveEdge().getLength() < this.activeLength;
    }

    public ActivePoint moveToEdgeStartingWithAndByOne(final char character) {
        return new ActivePoint(this.activeNode, character, 1);
    }

    public ActivePoint moveToNextNodeOfActiveEdge() {
        return new ActivePoint(this.getActiveEdge().getNext(), null, 0);
    }

    public ActivePoint moveToSlink() {
        return new ActivePoint(this.activeNode.getSlink(),
                this.activeEdgeFirstCharacter,
                this.activeLength);
    }

    public ActivePoint moveTo(final Node node) {
        return new ActivePoint(node, this.activeEdgeFirstCharacter, this.activeLength);
    }

    public ActivePoint moveByOneCharacter() {
        return new ActivePoint(this.activeNode,
                this.activeEdgeFirstCharacter,
                this.activeLength + 1);
    }

    public ActivePoint moveToEdgeStartingWithAndByActiveLengthMinusOne(final Node node,
                                                                       final char character) {
        return new ActivePoint(node, character, this.activeLength - 1);
    }

    public ActivePoint moveToNextNodeOfActiveEdge(final String word, final int index) {
        return new ActivePoint(this.getActiveEdge().getNext(),
                word.charAt(index - this.activeLength + this.getActiveEdge().getLength()),
                this.activeLength - this.getActiveEdge().getLength());
    }

    public void addEdgeToActiveNode(final char character, final Edge edge) {
        this.activeNode.getEdges().put(character, edge);
    }

    public void splitActiveEdge(final String word,
                                final Node nodeToAdd,
                                final int index,
                                final char character) {
        final Edge activeEdgeToSplit = this.getActiveEdge();
        final Edge splittedEdge = new Edge(activeEdgeToSplit.getFrom(),
                activeEdgeToSplit.getFrom() + this.activeLength,
                nodeToAdd);
        nodeToAdd.getEdges().put(word.charAt(activeEdgeToSplit.getFrom() + this.activeLength),
                new Edge(activeEdgeToSplit.getFrom() + this.activeLength,
                        activeEdgeToSplit.getTo(),
                        activeEdgeToSplit.getNext()));
        nodeToAdd.getEdges().put(character, new Edge(index, word.length(), null));
        this.activeNode.getEdges().put(this.activeEdgeFirstCharacter, splittedEdge);
    }

    public Node setSlinkTo(final Node previouslyAddedNodeOrAddedEdgeNode,
                           final Node node) {
        if(previouslyAddedNodeOrAddedEdgeNode != null) {
            previouslyAddedNodeOrAddedEdgeNode.setSlink(node);
        }
        return node;
    }

    public Node setSlinkToActiveNode(final Node previouslyAddedNodeOrAddedEdgeNode) {
        return setSlinkTo(previouslyAddedNodeOrAddedEdgeNode, this.activeNode);
    }
  }

  private static int idGenerator;

  private final String word;
  private final Node root;
  private ActivePoint activePoint;
  private int remainder;

  public ST(final String word) {
    this.word = word;
    this.root = new Node(idGenerator++);
    this.activePoint = new ActivePoint(this.root, null, 0);
    this.remainder = 0;
    build();
  }

  private void build() {
    for(int i = 0; i < this.word.length(); i++) {
        add(i, this.word.charAt(i));
    }
  }

  private void add(final int index, final char character) {
    this.remainder++;
    boolean characterFoundInTheTree = false;
    Node previouslyAddedNodeOrAddedEdgeNode = null;
    while(!characterFoundInTheTree && this.remainder > 0) {
        if(this.activePoint.pointsToActiveNode()) {
            if(this.activePoint.activeNodeHasEdgeStartingWith(character)) {
                activeNodeHasEdgeStartingWithCharacter(character, previouslyAddedNodeOrAddedEdgeNode);
                characterFoundInTheTree = true;
            }
            else {
                if(this.activePoint.activeNodeIs(this.root)) {
                    rootNodeHasNotEdgeStartingWithCharacter(index, character);
                }
                else {
                    previouslyAddedNodeOrAddedEdgeNode = internalNodeHasNotEdgeStartingWithCharacter(index,
                            character, previouslyAddedNodeOrAddedEdgeNode);
                }
            }
        }
        else {
            if(this.activePoint.pointsToOnActiveEdge(this.word, character)) {
                activeEdgeHasCharacter();
                characterFoundInTheTree = true;
            }
            else {
                if(this.activePoint.activeNodeIs(this.root)) {
                    previouslyAddedNodeOrAddedEdgeNode = edgeFromRootNodeHasNotCharacter(index,
                            character,
                            previouslyAddedNodeOrAddedEdgeNode);
                }
                else {
                    previouslyAddedNodeOrAddedEdgeNode = edgeFromInternalNodeHasNotCharacter(index,
                            character,
                            previouslyAddedNodeOrAddedEdgeNode);
                }
            }
        }
    }
  }

  private void activeNodeHasEdgeStartingWithCharacter(final char character,
                                                    final Node previouslyAddedNodeOrAddedEdgeNode) {
    this.activePoint.setSlinkToActiveNode(previouslyAddedNodeOrAddedEdgeNode);
    this.activePoint = this.activePoint.moveToEdgeStartingWithAndByOne(character);
    if(this.activePoint.pointsToTheEndOfActiveEdge()) {
        this.activePoint = this.activePoint.moveToNextNodeOfActiveEdge();
    }
  }

  private void rootNodeHasNotEdgeStartingWithCharacter(final int index, final char character) {
    this.activePoint.addEdgeToActiveNode(character, new Edge(index, this.word.length(), null));
    this.activePoint = this.activePoint.moveTo(this.root);
    this.remainder--;
    assert this.remainder == 0;
  }

  private Node internalNodeHasNotEdgeStartingWithCharacter(final int index,
                                                         final char character,
                                                         Node previouslyAddedNodeOrAddedEdgeNode) {
    this.activePoint.addEdgeToActiveNode(character, new Edge(index, this.word.length(), null));
    previouslyAddedNodeOrAddedEdgeNode = this.activePoint.setSlinkToActiveNode(previouslyAddedNodeOrAddedEdgeNode);
    if(this.activePoint.activeNodeHasSlink()) {
        this.activePoint = this.activePoint.moveToSlink();
    }
    else {
        this.activePoint = this.activePoint.moveTo(this.root);
    }
    this.remainder--;
    return previouslyAddedNodeOrAddedEdgeNode;
  }

  private void activeEdgeHasCharacter() {
    this.activePoint = this.activePoint.moveByOneCharacter();
    if(this.activePoint.pointsToTheEndOfActiveEdge()) {
        this.activePoint = this.activePoint.moveToNextNodeOfActiveEdge();
    }
  }

  private Node edgeFromRootNodeHasNotCharacter(final int index,
                                             final char character,
                                             Node previouslyAddedNodeOrAddedEdgeNode) {
    final Node newNode = new Node(idGenerator++);
    this.activePoint.splitActiveEdge(this.word, newNode, index, character);
    previouslyAddedNodeOrAddedEdgeNode = this.activePoint.setSlinkTo(previouslyAddedNodeOrAddedEdgeNode, newNode);
    this.activePoint = this.activePoint.moveToEdgeStartingWithAndByActiveLengthMinusOne(this.root,
            this.word.charAt(index - this.remainder + 2));
    this.activePoint = walkDown(index);
    this.remainder--;
    return previouslyAddedNodeOrAddedEdgeNode;
  }

  private Node edgeFromInternalNodeHasNotCharacter(final int index,
                                                 final char character,
                                                 Node previouslyAddedNodeOrAddedEdgeNode) {
    final Node newNode = new Node(idGenerator++);
    this.activePoint.splitActiveEdge(this.word, newNode, index, character);
    previouslyAddedNodeOrAddedEdgeNode = this.activePoint.setSlinkTo(previouslyAddedNodeOrAddedEdgeNode, newNode);
    if(this.activePoint.activeNodeHasSlink()) {
        this.activePoint = this.activePoint.moveToSlink();
    }
    else {
        this.activePoint = this.activePoint.moveTo(this.root);
    }
    this.activePoint = walkDown(index);
    this.remainder--;
    return previouslyAddedNodeOrAddedEdgeNode;
  }

  private ActivePoint walkDown(final int index) {
    while(!this.activePoint.pointsToActiveNode()
            && (this.activePoint.pointsToTheEndOfActiveEdge() || this.activePoint.pointsAfterTheEndOfActiveEdge())) {
        if(this.activePoint.pointsAfterTheEndOfActiveEdge()) {
            this.activePoint = this.activePoint.moveToNextNodeOfActiveEdge(this.word, index);
        }
        else {
            this.activePoint = this.activePoint.moveToNextNodeOfActiveEdge();
        }
    }
    return this.activePoint;
  }

  public String toString(final String word) {
    return this.root.toString(word);
  }

  public boolean contains(final String suffix) {
    return this.root.contains(this.word, suffix);
  }

  public static void main(final String[] args) {
    final String[] words = {
            "abcabcabc$",
            "abc$",
            "abcabxabcd$",
            "abcabxabda$",
            "abcabxad$",
            "aabaaabb$",
            "aababcabcd$",
            "ababcabcd$",
            "abccba$",
            "mississipi$",
            "abacabadabacabae$",
            "abcabcd$",
            "00132220$"
    };
    Arrays.stream(words).forEach(word -> {
        System.out.println("Building suffix tree for word: " + word);
        final ST suffixTree = new ST(word);
        System.out.println("Suffix tree: " + suffixTree.toString(word));
        for(int i = 0; i < word.length() - 1; i++) {
            assert suffixTree.contains(word.substring(i)) : word.substring(i);
        }
    });
  }
}




image algorithm comparison computer-vision