旅行商问题（TSP）相关性验证、跨州旅行最小成本求解及OpenCV FloodFill算法优化问询

Let’s walk through your problem step by step—you’ve got a few interconnected pieces to sort out here.

First, let’s clarify the core of your problem: you need to calculate the minimum cost to visit all cities across all states, where entering a new state costs $1, and intra-state travel is free.

Wait a second—your initial TSP instinct might be overcomplicating things here. Since intra-state travel has no cost, you can visit every city in a state once you’re in it without additional expense. The minimum cost boils down to the number of states minus 1: you start in one state (no cost to enter), then pay $1 each time you move to a new state.

That said, if your problem had additional constraints (like limited routes between states, or travel costs between states beyond the $1 entry fee), TSP could make sense. But based on your description, the key first step is accurately counting the number of states (i.e., connected components of cities linked by roads).

To turn your image into a graph structure (nodes = cities, edges = roads), here are my top picks for tools and a step-by-step workflow:

Recommended Libraries #

• OpenCV: You’re already using it—great for raw image processing (detection of points/lines, thresholding, etc.).
• NetworkX: Perfect for building and analyzing graph structures once you’ve extracted cities and roads. It has built-in functions to calculate connected components, which is exactly what you need to count states.
• scikit-image: Offers more advanced image analysis tools (e.g., precise point detection, edge filtering) if you need finer control than OpenCV provides.
• Union-Find (Disjoint Set Union, DSU): A lightweight data structure you can implement yourself (or use via networkx.utils.union_find) to track connected components as you add edges between cities.

Step-by-Step Workflow #

1. Preprocess the Image:
   • Load the image in color (not grayscale initially) to separate colored city points from roads.
   • Use thresholding or color segmentation (e.g., cv2.inRange) to isolate cities (colored dots) and roads (lines).
2. Detect Cities:
   • Use cv2.HoughCircles to detect circular city points, or cv2.findContours to identify small, distinct regions that represent cities.
3. Detect Roads:
   • Use edge detection (cv2.Canny) followed by cv2.HoughLinesP to detect straight road segments.
4. Build the Graph:
   • Create nodes for each detected city.
   • For each road segment, determine which two cities it connects (you may need to calculate proximity between road endpoints and city centers) and add an undirected edge between those nodes.
5. Count Connected Components:
   • Use networkx.connected_components() on your graph to get each state (connected group of cities). The number of these components is your state count.

Your current code returns 3 instead of the expected 6 because it’s misinterpreting what constitutes a "state" in the image. Here’s why and how to fix it:

What’s Wrong with the Original Code? #

You’re applying FloodFill directly to a grayscale image, only targeting pixels with value 255. This likely means:

• Either you’re only detecting roads (if roads are white) and ignoring colored cities, or
• You’re detecting cities but not including roads in the连通区域, so cities linked by roads aren’t being grouped into the same state.

Improved Approach #

Instead of manually traversing pixels, use OpenCV’s built-in connectedComponents function—it’s more reliable and efficient. First, create a mask that includes both cities and roads, then count the connected regions:

import cv2
import numpy as np

# Load the color image
img_color = cv2.imread('graph1.png')
img_gray = cv2.cvtColor(img_color, cv2.COLOR_BGR2GRAY)

# 1. Isolate roads (adjust threshold based on your image's road color)
_, road_mask = cv2.threshold(img_gray, 240, 255, cv2.THRESH_BINARY)

# 2. Isolate cities (example for red cities; adjust color ranges for your image)
lower_red = np.array([0, 0, 100])
upper_red = np.array([50, 50, 255])
city_mask = cv2.inRange(img_color, lower_red, upper_red)

# 3. Combine roads and cities into a single mask of "state" regions
state_mask = cv2.bitwise_or(road_mask, city_mask)

# 4. Count connected components (states)
num_components, _ = cv2.connectedComponents(state_mask)
# Subtract 1 to exclude the background component
num_states = num_components - 1

print(f"Number of states: {num_states}")

Key Fixes: #

• We’re combining both roads and cities into one mask, so connected cities+road regions are counted as a single state.
• connectedComponents automatically handles all连通区域 without manual pixel looping, reducing error.
• We’re using color segmentation to isolate cities, which works better than grayscale for colored points.

If you still want to use FloodFill, make sure to:

• Use a flood mask (flood_mask) to track already filled regions (your original code didn’t do this, leading to overcounting).
• Target the combined city+road mask instead of just grayscale 255 pixels.

内容的提问来源于stack exchange，提问作者Sparsh Garg