ALINA: Advanced Line Identification and Notation Algorithm

In plain words

Labelling where the painted lines are in airport video means marking thousands of frames by hand. That is slow, costly and easy to get wrong. ALINA automates most of this work for taxiway line markings.

A person draws a four-sided area around the lines once, on the first frame of a video. The software stretches that area into a straight-down view, where the lines run in a predictable direction. It then keeps the pixels whose colour falls in a set range for paint-like markings, finds the vertical strip with the most such pixels, and grows a region outward from there to collect the marking's pixels. Those pixels are mapped back onto the original frame and their coordinates are saved to a text file.

The key idea is that one manual setup labels a whole video, rather than one setup per change of scene. The authors report that the method labelled 60,249 frames from three videos. Against a hand-made reference set it matched about 98% of the reference pixels, and it ran faster than the older method they compare against.

TL;DR

ALINA is a classical computer-vision labelling pipeline: a fixed bird's-eye warp of a user-drawn ROI, HSV colour thresholding, a column histogram to find the marking, and a flood-fill traversal (CIRCLEDAT) to gather its pixels. The labels are per-frame pixel coordinates. The authors report 98.45% recall on 120 hand-labelled frames and 50 ms per frame. The paper is light on numbers that an implementer needs. The code fills some of them in, and it differs from the paper on several points, listed below.

Problem

Supervised vision needs labelled data, and manual labelling is costly, slow and error-prone at scale §1. The authors work on taxiway line markings in the AssistTaxi dataset §1. The earlier method, CDLEM, needs a new region of interest for every change of scene, which means a lot of video has to be watched in advance §2 §4.5. The task is to produce pixel coordinates of markings on each frame, not bounding boxes §1 §3.9.

Method

ALINA runs the same pipeline on every frame of a video. The region of interest (ROI) is drawn once on the first frame and reused for the rest of the video §3.2 §4.5. Each frame goes through the following stages fig. 3 fig. 4:

1. Frame representation. A frame is read as an array of pixel values per row, column and colour channel §3.1 eq. 1.
2. ROI and bird's-eye warp. The four ROI corners are mapped to a rectangle with a planar perspective transform, solved from four point pairs into a 3×3 matrix M §3.2 §3.3 eq. 2. A pixel's warped position is the projective map of M applied to its coordinates §3.3 eq. 3.
3. HSV normalisation. The warped frame is converted to HSV. Each of H, S and V is min-max stretched to 0–255 §3.4 eq. 4. The paper applies this to the ROI, while the code stretches the whole warped frame color.py.
4. Colour thresholding. A pixel becomes white if H, S and V all lie inside the box (0, 70, 170) to (255, 255, 255) §3.5 eq. 5. Because H is stretched to 0–255, this hue bound accepts every hue (see Pitfalls).
5. Column histogram. Each binary pixel is 1 if white §3.6 eq. 6. The vertical projection counts white pixels in each column, summed over rows §3.6 eq. 7. The column with the highest count is the candidate marking.
6. Acceptance test. A candidate is accepted only if its peak count reaches a threshold. The paper sets this to 150 after an empirical false-positive table §4.2 eq. 8 eq. 9 eq. 10 tab. 2. Frames without a marking get an empty text file §4.2.
7. Seed. The seed is the peak column together with the mean row of its white pixels §4.2.
8. CIRCLEDAT. A depth-first traversal starts from the seed. It expands only white pixels, visits each neighbour once, and collects the white pixels it reaches §3.8 alg. 1 fig. 4.
9. Unwarp and annotate. The collected pixels are mapped back through the inverse warp to the original view and marked in red on the frame. Their coordinates go to a text file §3.9 fig. 4.

# ALINA: label the marking pixels of one frame  [§3.2]-[§3.9] [alg. 1]
# Input:  frame (H, W, 3) colour image; roi (4, 2) corner pixels
# Output: (N, 2) array of (x, y) marking pixels; empty if no marking

def label_frame(frame, roi):
    # Warp the ROI to a bird's-eye view  [§3.3] [eq. 2] [eq. 3]
    matrix = perspective_matrix(roi, bird_rectangle)
    warped = warp(frame, matrix)

    # Convert to HSV and stretch each channel to 0..255  [§3.4] [eq. 4]
    # Stretch uses the whole warped frame  [code: alina/color.py#L10-L14]
    hsv = to_hsv(warped)
    hsv_norm = stretch_each_channel(hsv, low=0, high=255)

    # Keep pixels inside the HSV box  [§3.5] [eq. 5]
    mask = inside_box(hsv_norm, lower=(0, 70, 170), upper=(255, 255, 255))
    mask[:, :300] = 0  # code only  [code: alina/pipeline.py#L51-L52]

    # Count white pixels per column  [§3.6] [eq. 6] [eq. 7]
    column_counts = count_white_per_column(mask)
    peak_col = argmax(column_counts)
    peak_value = column_counts[peak_col]

    # Reject a weak peak; paper: peak_min = 150  [§4.2] [eq. 10]
    # Code: peak_min = 50 and more than 200 white pixels
    # [code: alina/config.py#L23-L24]
    if peak_value < peak_min or white_count(mask[:, peak_col]) <= 200:
        return empty_marking

    # Seed at the peak column and the mean row of its white pixels  [§4.2]
    # Code also forces the seed pixel to white
    # [code: alina/pipeline.py#L62-L63]
    seed_row = mean_row_of_white(mask[:, peak_col])
    mask[seed_row, peak_col] = 255
    pixels = circledat(mask, peak_col, seed_row, theta)

    # Map the pixels back to the original view  [§3.9] [alg. 1]
    # Code paints radius-1 discs before unwarping
    # [code: alina/pipeline.py#L68-L79]
    canvas = paint_discs(pixels, radius=1, shape=mask.shape)
    marking = warp(canvas, inverse(matrix))
    return nonzero_pixels(marking)


def circledat(binary, seed_x, seed_y, theta):
    # Depth-first flood fill over white pixels  [§3.8] [alg. 1]
    # Code uses a square neighbourhood, not a disc
    # [code: alina/traversal.py#L13-L14]
    offsets = [(dx, dy) for dx in range(-theta, theta + 1)
               for dy in range(-theta, theta + 1) if (dx, dy) != (0, 0)]
    visited = {(seed_x, seed_y)}
    stack = [(seed_x, seed_y)]
    found = []
    while stack:
        x, y = stack.pop()
        # Only white pixels are kept and expanded  [§3.8]
        # [code: alina/traversal.py#L21]
        if binary[y][x] != 255:
            continue
        found.append((x, y))
        for dx, dy in offsets:
            nx, ny = x + dx, y + dy
            # Skip visited pixels and pixels outside the image  [alg. 1]
            if (nx, ny) in visited or not inside(nx, ny, binary):
                continue
            visited.add((nx, ny))
            stack.append((nx, ny))
    return found

Key equations: the HSV box test eq. 5, the column projection eq. 7, and the acceptance rule with the threshold T eq. 10.

For the ROI, the paper says the four corners are "source points" and gives no order §3.2. The code takes four clicks in the order bottom-left, top-left, top-right, bottom-right cli.py. The quadrilateral it builds is not the four free points (see Paper vs code).

For evaluation, a reference set of 120 frames was chosen by hand at scene changes §4.3. Each frame gets a manually outlined marking region, and an edge map is computed inside it with Canny edge detection §4.3 fig. 5 eq. 11 eq. 12. ALINA's output is compared with that edge map using recall eq. 15 tab. 4.

Hyperparameters

Results

Author-reported. Setup: a subset of AssistTaxi, 60,249 frames from three videos with different camera angles; a 120-frame hand-made reference; CPU timing on the machine above §4.1 §4.3 §4.5.

The threshold table reports only false positives, and it does not state how many frames it covers §4.2.

Paper vs code

Official code: alina/ and eval/ in the repository linked from the abstract, at code_commit. The licence is MIT, copyright the first author LICENSE. I read the code and did not run it, so none of the paper's numbers are re-computed here. The repository ships the 120 reference frames' coordinates and ALINA's output on them, which would allow a re-run.

• Acceptance threshold. The paper sets T = 150 on the peak count §4.2 eq. 10. The code and CLI default to 50 config.py cli.py. The paper does not say which value produced the released labels.
• Column count rule. The paper says a true marking yields "well over 150" white pixels in a column §4.2. The code needs more than 200 in the peak column histogram.py config.py.
• Stretch scope. The paper stretches the ROI's HSV channels §3.4. The code stretches all of the warped frame, including pixels outside the ROI color.py pipeline.py.
• ROI shape. The paper uses four free source points §3.2. The code builds the quadrilateral from the bottom-left and top-left clicks and the x-values of the top-right and bottom-right clicks, so the top and bottom edges are horizontal roi.py pipeline.py.
• Neighbourhood shape. The text says "circular" §3.8. The paper's own algorithm and the code use a square of side 2θ+1 alg. 1 traversal.py.
• Seed pixel. The code forces the seed to white before traversal pipeline.py. The paper does not mention this.
• Left-side mask. The code zeroes 300 columns of the mask pipeline.py. The paper does not mention this.
• Output coordinates. The paper saves the marking pixels §3.9. The code paints each pixel as a radius-1 disc, unwarps the canvas with bilinear interpolation, and saves every non-zero pixel pipeline.py. The saved set can differ from the traversal output.
• Centroid. The paper says the candidate's centroid starts the traversal §4.2. The code uses the integer mean of all white rows in the peak column, not a connected-component centroid histogram.py.
• CBEM Canny thresholds. The paper uses median-based thresholds with σ = 0.33 §4.3 eq. 11 eq. 12. The code uses fixed 30 and 150 with a 5×5 blur cbem.py. The code also draws the traced outline in black over the edge map cbem.py.
• Metric. The paper defines recall as TP/(TP+FN) on x and y coordinates §4.5 eq. 15. The code takes sets of x values and sets of y values separately, computes recall on each, and averages the two evaluate.py metrics.py. It does not match pixels as (x, y) pairs. The code also reports precision and F1, which the paper does not.
• Ablation and baselines. The repository has no code for the threshold ablation tab. 2, CDLEM tab. 4 or the sliding-window search tab. 3. Those numbers cannot be checked from the repository.

Pitfalls

• Hue bound accepts everything. H is stretched to 0–255 before thresholding, and the box allows 0–255 eq. 5 config.py. So the hue test passes every pixel. In practice the colour test is S ≥ 70 and V ≥ 170 after stretching.
• The threshold moves with each frame. The min-max stretch is recomputed for each frame color.py. The fixed bounds 70 and 170 therefore select different colours in different frames, depending on the frame's darkest and brightest pixels. This is a numerically sensitive step. The paper states the bounds on the stretched scale only §3.5.
• Warped borders. Pixels that the warp maps from outside the frame are zero. They can set the minimum of the stretch pipeline.py. This is inferred from the code, not measured.
• Gap bridging. Traversal joins white pixels within θ pixels of each other alg. 1. With the code default of 15, separate markings or other white pixels within 15 pixels are merged into one set. The paper does not test this, and it says the HSV mask also picks up non-marking pixels §3.5.
• Cost is not O(k). The paper states CIRCLEDAT as O(k) §4.4 tab. 3. With θ = 15 each white pixel checks (2θ+1)² − 1 = 960 offsets. The visited set holds every pixel pushed. The constant matters for the speed claim.
• Warp rectangle is fixed. The destination rectangle in the code is fixed in pixels, reaching x = 1200 and y = 800 config.py. The output has the frame's size pipeline.py, so a frame smaller than that rectangle cuts off part of the bird's-eye view. The paper gives no destination values §3.3.
• Robustness is shown by example. The claim that labels hold across camera angles and weather rests on three example frames, one per video §4.1. No failure cases are reported.
• Threshold selection. The paper uses an argmin over F_fp − F_tp to define T_optimal eq. 9. It reports false positives only, so the true-positive term is not available tab. 2. The sample size behind the table is not stated.
• Reference set is not random. The 120 reference frames were picked by hand at scene changes §4.3. The paper cites the law of large numbers and the central limit theorem to argue the sample is representative eq. 13 eq. 14. Those theorems do not justify a hand-picked sample. Coverage of the 60,249 frames is not measured.
• Aggregation is not stated. The paper does not say whether the 98.45% is pooled over pixels or averaged over frames. The code averages per-frame values evaluate.py.
• Edge map is not the marking. The reference set is a Canny edge map of a hand-outlined region §4.3. Recall measures how many of those edge pixels ALINA hits, not how many marking pixels it finds.
• Timing figures disagree. The text gives 50.9 ms and 19.65 fps §4.1 §4.5. The table gives 50.09 ms tab. 4. 19.65 fps matches 50.9 ms, not 50.09 ms (1000 / 50.09 ≈ 19.96).
• Equation notation. Equation 3 swaps the roles of t and s relative to their definitions, and it uses M₃₃ while equation 2 writes that entry as 1 §3.3 eq. 2 eq. 3. Treat M₃₃ as 1, as in a standard four-point solve.
• Empty files. Frames without a marking produce an empty text file §4.2 pipeline.py. Consumers must handle zero-length files.

Lineage

• Builds on: CDLEM, the contour-based detection and line extraction method from the AssistTaxi dataset paper §1 §2. Its ROI-per-scene-change limit is what ALINA removes §4.5.
• Builds on: the sliding-window lane search of Muthalagu et al. §4.4 §2, used as the earlier pixel-search baseline.
• Compared against: CDLEM tab. 4 and the sliding-window search tab. 3.
• Superseded by: not stated in the card's sources.