How the knn_connection Algorithm Finds Neighboring Bounding Boxes in doc2graph

The knn_connection method in doc2graph/data/graph_builder.py constructs a spatial k‑nearest‑neighbour graph by building axis‑aligned projection maps, dynamically expanding an aspect‑ratio‑aware search window to gather candidates, intersecting vertical and horizontal projections, and ranking the closest k neighbors by Euclidean distance.

The knn_connection algorithm serves as the spatial backbone of the andreagemelli/doc2graph repository, transforming raw document bounding boxes into graph edges that represent physical proximity. Unlike naive pairwise distance computations, this implementation leverages projection‑based spatial indexing and adaptive window expansion to efficiently identify neighboring boxes. Understanding how knn_connection finds neighboring bounding boxes is essential for optimizing document understanding pipelines that rely on graph neural networks.

Four-Stage Neighbor Detection Pipeline

The algorithm processes bounding boxes through four distinct computational stages defined in doc2graph/data/graph_builder.py, each optimized to reduce the search space before performing expensive distance calculations.

Building Projection Maps for Spatial Indexing

In the initialization phase (lines 30‑42), knn_connection constructs two auxiliary data structures that map spatial coordinates to bounding box indices:

• vertical_projections: A list of length width where each index stores the IDs of boxes intersecting that x‑coordinate.
• horizontal_projections: A list of length height where each index stores the IDs of boxes intersecting that y‑coordinate.

These maps are populated in a single pass over all bounding boxes, enabling O(1) lookup of boxes intersecting any given axis line. This projection strategy eliminates the need to compare every box against every other box during the neighbor search phase.

Dynamic Window‑Based Candidate Collection

For each reference box, the algorithm expands a rectangular search window until it contains at least k candidate neighbors (lines 53‑84). The window expansion logic incorporates several adaptive mechanisms:

• window_multiplier: The window size grows multiplicatively each iteration until sufficient candidates are found or a maximum size threshold is reached.
• Aspect ratio awareness: The offset applied in x and y directions scales according to the box’s aspect ratio (wider vs. taller), maintaining a roughly square visual search area regardless of box orientation.
• Projection queries: Using the pre‑computed maps, the algorithm retrieves vertical_bboxs (boxes intersecting the window’s x‑range) and horizontal_bboxs (boxes intersecting the window’s y‑range).

This windowed approach ensures that the algorithm only considers spatially relevant candidates rather than the entire document population.

Intersecting Vertical and Horizontal Candidates

Once candidate sets are retrieved, the algorithm computes their intersection (lines 94‑100) to produce the raw neighbor set. Only boxes that appear in both the vertical and horizontal projections—meaning they actually overlap the search window in 2D space—are retained. The implementation removes duplicate entries and explicitly excludes the reference box itself from consideration, ensuring that a node never connects to itself.

Distance‑Based Final Selection

With the filtered candidate set, knn_connection computes the precise Euclidean distance between box centers using the polar function imported from doc2graph/data/utils.py (lines 102‑118). The ranking process follows these steps:

1. Calculate polar distance from the reference box center to each candidate center.
2. Sort candidates by ascending distance.
3. Select the first k entries as final neighbors.
4. Append bidirectional edges ([src, dst] and [dst, src]) to the edge lists, avoiding duplicate connections.

The method ultimately returns two parallel lists—u (source node indices) and v (target node indices)—that conform to DGL’s graph construction API.

Practical Implementation Example

The following example demonstrates how to invoke the knn_connection algorithm directly using the GraphBuilder class:

from doc2graph.data.graph_builder import GraphBuilder

# Initialise the builder (configuration reads `edge_type = "knn"` from YAML)

builder = GraphBuilder()

# Prepare bounding boxes as [xmin, ymin, xmax, ymax] in pixel coordinates

boxes = [
    [30, 120, 210, 180],
    [220, 115, 400, 190],
    [45, 250, 190, 310],
    # … additional boxes …

]

# Execute k‑NN connection with k=5 neighbors

src_nodes, dst_nodes = builder.knn_connection(size=(800, 600), bboxs=boxes, k=5)

print("Source indices:", src_nodes)
print("Destination indices:", dst_nodes)

The returned index pairs integrate directly with Deep Graph Library (DGL):

import dgl
import torch

# Construct the graph from edge lists

g = dgl.graph(
    (torch.tensor(src_nodes), torch.tensor(dst_nodes)),
    num_nodes=len(boxes),
    idtype=torch.int32
)
print(g)

Key Source Files and Functions

• doc2graph/data/graph_builder.py: Contains the knn_connection method (lines 30‑118) implementing projection maps, window expansion, and distance ranking.
• doc2graph/data/utils.py: Defines the polar function used for Euclidean distance calculation between bounding box centers.
• doc2graph/utils.py: Provides the get_config helper that reads edge_type configuration from YAML files.
• doc2graph/main.py: Entry point that orchestrates graph creation and selects between fully connected and knn edge generation strategies.

Summary

• Projection indexing: knn_connection builds vertical_projections and horizontal_projections arrays (lines 30‑42) to enable constant‑time spatial lookups.
• Adaptive search windows: The algorithm expands aspect‑ratio‑aware windows (lines 53‑84) until capturing at least k candidate neighbors.
• Intersection filtering: Only boxes appearing in both vertical and horizontal projections are considered valid candidates (lines 94‑100).
• Exact distance ranking: Final neighbor selection uses the polar distance metric (lines 102‑118) to return the closest k boxes as bidirectional DGL‑compatible edge lists.

Frequently Asked Questions

What is the purpose of the projection maps in knn_connection?

The projection maps serve as spatial indexes that allow the algorithm to retrieve candidate boxes intersecting specific x or y coordinates in O(1) time. By building vertical_projections and horizontal_projections arrays during initialization (lines 30‑42), knn_connection avoids brute‑force O(n²) comparisons and quickly narrows the search space to boxes within the current window region.

How does the search window adapt to different bounding box shapes?

The window expansion logic incorporates the box’s aspect ratio to determine x and y offset multipliers (lines 53‑84). Wider boxes receive greater horizontal expansion relative to vertical, while taller boxes receive the opposite, ensuring the search window maintains a visually square proportion regardless of the reference box’s dimensions.

Why does the algorithm intersect vertical and horizontal projections?

The intersection operation (lines 94‑100) acts as a coarse geometric filter. A box must intersect both the vertical and horizontal ranges of the search window to occupy the 2D spatial region, eliminating boxes that merely align on one axis but lie far outside the actual rectangular window. This step significantly reduces the number of expensive distance calculations required.

What distance metric does knn_connection use to rank neighbors?

The algorithm uses Euclidean distance between bounding box centers, computed via the polar function defined in doc2graph/data/utils.py. This distance metric (invoked at lines 102‑118) measures the straight‑line spatial separation in the document image plane, ensuring that selected neighbors represent the physically closest elements.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}