2d:null 2e:["$","title",null,{"children":"Hough Transform | Leo Orpilla III | Observable"}] 33:T4bb,cartesianPlotHough = () => { const [theta, rho] = theta_rho(m, b); return Plot.plot({ aspectRatio: 1, x: { domain: [-5, 5] }, y: { domain: [-5, 5] }, color: { scale: "ordinal" }, clip: true, marks: [ Plot.frame({ opacity: 0.5, stroke: d3.schemeTableau10[0], strokeWidth: 2 }), Plot.ruleX([0], { opacity: 0.5 }), Plot.ruleY([0], { opacity: 0.5 }), Plot.line( [ [0, 0], [ rho * Math.cos((theta * Math.PI) / 180), rho * Math.sin((theta * Math.PI) / 180) ] ], { stroke: "blue" } ), Plot.line( [ [-10, slopeIntercept(m, -10, b)], [10, slopeIntercept(m, 10, b)] ], { stroke: "gray", strokeDasharray: [5] } ), Plot.line( [ [-10, slopeIntercept(m, -10, b)], [10, slopeIntercept(m, 10, b)] ], { stroke: "gray", strokeDasharray: [5] } ), Plot.dot(points, { x: "x", y: "y", fill: (_, i) => `point${i}`, r: 5, tip: true }) ] }); }34:[] 31:{"id":"223740e926f5c95e","slug":"hough-transform","title":"Hough Transform","thumbnail":"929797613b6ef56f1270f156e739504f759a46d98dfb08c06da947b2e290da69","access_level":"public","create_time":"$D2023-11-22T08:22:54.151Z","update_time":"$D2023-11-24T11:59:43.735Z","view_time":null,"first_public_time":"$D2023-11-22T14:23:15.948Z","has_unpublished_edits":null,"fork":false,"stars":0,"starred":false,"owner":{"type":"team","id":"304df413ac6d9b3b","login":"ldgrp","name":"Leo Orpilla III","avatar_url":"https://avatars-next.observableusercontent.com/9743f8415274ff1b872aff405e8a77d6dd9c25f412b1ce8853f1dee939c67e9a","tier":"starter_2024"},"version":946,"publish_version":null,"role":null,"authored":false,"authors":[{"type":"individual","id":"4d2ca89f2665bbeb","login":"ldgrp","name":"Leo Orpilla III","avatar_url":"https://avatars-next.observableusercontent.com/9743f8415274ff1b872aff405e8a77d6dd9c25f412b1ce8853f1dee939c67e9a","tier":null}],"members":[{"type":"individual","id":"4d2ca89f2665bbeb","login":"ldgrp","name":"Leo Orpilla III","avatar_url":"https://avatars-next.observableusercontent.com/9743f8415274ff1b872aff405e8a77d6dd9c25f412b1ce8853f1dee939c67e9a","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":true,"trashed":false,"lapsed":null,"subscribed":null,"forks":0,"collection":null,"type":"notebook","body":{"title":"Hough Transform","cells":[{"id":0,"value":"# Hough Transform","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":93,"value":"Consider a line in slope-intercept form: ${tex`y = mx+b`}.\n\nThis is equivalent to ${tex`b = -mx+y`}.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":142,"value":"We can plot all possible combinations of ${tex`m`} and ${tex`b`} that satisfy this equation for each point. Each **${cartesianFormat('point')}** from the ${cartesianFormat('cartesian space')} corresponds to a **${parameterFormat('line')}** in the ${parameterFormat('parameter space')}\n\nNotice that the **${parameterFormat('lines')}** in the ${parameterFormat('parameter space')} intersect at a point **${parameterFormat(html`(${m},${b})`)}**. This is the slope and y-intercept of the \n\nWe can use this concept to identify ${cartesianFormat('lines')} from arbitrary ${cartesianFormat('points')} in ${cartesianFormat('cartesian space')}.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":99,"value":"viewof m = Inputs.range([-10, 10], { label: \"Slope (m)\", step: 0.1, value: 1 })","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":101,"value":"viewof b = Inputs.range([-10, 10], {\n label: \"y-intercept (b)\",\n step: 0.1,\n value: 2\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":204,"value":"viewof range = Inputs.range([1, 10], {\n label: \"Point count\",\n step: 1,\n value: 3\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":113,"value":"x = Array.from({ length: range + 1 }, (_, i) =>\n i % 2 === 0 ? -Math.floor(i / 2) : Math.floor(i / 2)\n)\n .slice(1)\n .map((x_i) => x_i / (Math.abs(m) > 1 ? Math.abs(m) ** 1.1 : 1))","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":115,"value":"points = [...x.map((x_i) => ({ x: x_i, y: slopeIntercept(x_i, m, b) }))]","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":176,"value":"\n

\n ${cartesianPlot()}\n ${mbPlot()}\n

\n","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":8,"value":"Consider a more complicated example where multiple **${cartesianFormat('lines')}** can be identified from a complex arrangement of **${cartesianFormat('points')}**. \n\nIn this scenario, imagine that the ${cartesianFormat('points')} represent various features, such as the edges of a road or a sheet of paper. Notice that the **${parameterFormat('lines')}** in the ${parameterFormat('parameter space')} intersect at multiple **${parameterFormat('points')}**. \n\nIf we consider the **top 4** most significant intersections, specifically the points where the highest number of lines intersect, we recover the **${cartesianFormat('4 lines')}** that pass through the points in the ${cartesianFormat('cartesian space')}.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":283,"value":"\n

\n ${cartesianPlotComplex()}\n ${mbPlotComplex()}\n

\n","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":539,"value":"## Parametric Equation","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":545,"value":"Vertical lines cannot be represented with slope-intercept form. But we can also define a line parametrically using **${houghFormat('polar coordinates')}**: ${tex`x \\cos \\theta + y \\sin \\theta = r`}","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":573,"value":"If we plot all possible combinations of ${tex`r`} and ${tex`\\theta`} that satisfy the equation, then we end up with a sinusoidal curve in the **${houghFormat('Hough space')}**. ","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":637,"value":"Inputs.bind(\n Inputs.range([-10, 10], { label: \"Slope (m)\", step: 0.1 }),\n viewof m\n)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":642,"value":"Inputs.bind(\n Inputs.range([-10, 10], {\n label: \"y-intercept (b)\",\n step: 0.1\n }),\n viewof b\n)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":643,"value":"Inputs.bind(\n Inputs.range([1, 10], {\n label: \"Point count\",\n step: 1\n }),\n viewof range\n)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":704,"value":"\n

\n ${cartesianPlotHough()}\n ${houghPlot()}\n

\n","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":722,"value":"Collinear **${cartesianFormat('points')}** in the ${cartesianFormat('cartesian space')} appear as **${houghFormat('curves')}** that intersect each other in ${houghFormat('Hough space')}.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":713,"value":"\n

\n ${cartesianPlotComplex()}\n ${houghPlotComplex()}\n

\n","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":946,"value":"","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":921,"value":"## Circles","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":922,"value":"","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":775,"value":"### References\n\n- https://en.wikipedia.org/wiki/Hough_transform\n- https://www.semanticscholar.org/paper/How-the-Hough-Transform-Was-Invented-Hart/f7e8cbca97de34fd3695e538e164a1b40d27b04e\n- https://www.cs.cmu.edu/~16385/s17/Slides/5.3_Hough_Transform.pdf","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":782,"value":"","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":542,"value":"---","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":57,"value":"lineData = [\n [\n [-10, 4],\n [10, 4]\n ],\n [\n [-9, -10],\n [1, 10]\n ],\n\n [\n [9, -10],\n [-1, 10]\n ],\n [\n [10, -6],\n [-10, -6]\n ]\n]","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":111,"value":"slopeIntercept = (m, x, b) => m * x + b","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":11,"value":"complexPoints = [\n { x: -1, y: 4 },\n { x: 1, y: 4 },\n { x: -2, y: 4 },\n { x: 2, y: 4 },\n { x: 0, y: 4 },\n { x: -3, y: 2 },\n { x: 3, y: 2 },\n { x: -4, y: 0 },\n { x: 4, y: 0 },\n { x: -3, y: 2 },\n { x: 3, y: 2 },\n { x: -5, y: -2 },\n { x: 5, y: -2 },\n { x: -6, y: -4 },\n { x: 6, y: -4 },\n { x: -6, y: -4 },\n { x: 7, y: -6 },\n { x: -7, y: -6 },\n { x: 5, y: -6 },\n { x: -5, y: -6 },\n { x: 3, y: -6 },\n { x: -3, y: -6 },\n { x: 1, y: -6 },\n { x: -1, y: -6 }\n]","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":932,"value":"introPlot = () => {\n return Plot.plot({\n aspectRatio: 1,\n x: { domain: [-10, 10] },\n y: { domain: [-10, 10] },\n clip: true,\n marks: [\n Plot.frame({\n opacity: 0.5,\n stroke: d3.schemeTableau10[0],\n strokeWidth: 2\n }),\n Plot.ruleX([0], { opacity: 0.5 }),\n Plot.ruleY([0], { opacity: 0.5 }),\n Plot.dot(complexPoints, {\n x: \"x\",\n y: \"y\",\n fill: \"gray\",\n r: 5,\n tip: true\n })\n ]\n });\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":746,"value":"$33","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":127,"value":"cartesianPlot = () =>\n Plot.plot({\n aspectRatio: 1,\n x: { domain: [-5, 5] },\n y: { domain: [-5, 5] },\n color: { scale: \"ordinal\" },\n clip: true,\n marks: [\n Plot.frame({\n opacity: 0.5,\n stroke: d3.schemeTableau10[0],\n strokeWidth: 2\n }),\n Plot.ruleX([0], { opacity: 0.5 }),\n Plot.ruleY([0], { opacity: 0.5 }),\n Plot.line(\n [\n [-10, slopeIntercept(m, -10, b)],\n [10, slopeIntercept(m, 10, b)]\n ],\n {\n stroke: \"gray\",\n strokeDasharray: [5]\n }\n ),\n Plot.dot(points, {\n x: \"x\",\n y: \"y\",\n fill: (_, i) => `point${i}`,\n r: 5,\n tip: true\n })\n ]\n })","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":152,"value":"mbPlot = () => {\n const lines = [];\n const mItem = [-10, 10];\n\n points.forEach((point) => {\n for (let m of mItem) {\n let b = -m * point.x + point.y;\n lines.push({ m, b, label: `Point (${point.x}, ${point.y})` });\n }\n });\n\n // Observable Plot\n return Plot.plot({\n aspectRatio: 1,\n x: { domain: [-10, 10] },\n y: { domain: [-10, 10] },\n clip: true,\n marks: [\n Plot.frame({\n opacity: 0.5,\n stroke: d3.schemeTableau10[1],\n strokeWidth: 2\n }),\n Plot.ruleX([0], { opacity: 0.5 }),\n Plot.ruleY([0], { opacity: 0.5 }),\n Plot.line(lines, { x: \"m\", y: \"b\", stroke: \"label\", tip: true }),\n Plot.tip([md`**m**: ${m}\\n**b**: ${b}`], { x: m, y: b }),\n Plot.dot([{ b: b, m: m }], { x: \"m\", y: \"b\" })\n ]\n });\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":14,"value":"cartesianPlotComplex = () =>\n Plot.plot({\n aspectRatio: 1,\n x: { domain: [-10, 10] },\n y: { domain: [-10, 10] },\n clip: true,\n marks: [\n Plot.frame({\n opacity: 0.5,\n stroke: d3.schemeTableau10[0],\n strokeWidth: 2\n }),\n Plot.ruleX([0], { opacity: 0.5 }),\n Plot.ruleY([0], { opacity: 0.5 }),\n ...lineData.map((line, i) =>\n Plot.line(line, { stroke: d3.schemeTableau10[i], strokeDasharray: [5] })\n ),\n Plot.dot(complexPoints, {\n x: \"x\",\n y: \"y\",\n fill: \"gray\",\n r: 5,\n tip: true\n })\n ]\n })","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":589,"value":"houghPlot = () => {\n const [theta, rho] = theta_rho(m, b);\n return Plot.plot({\n height: 630,\n x: { domain: [-5, 180], label: \"theta\" },\n y: { domain: [-12, 12], label: \"r\" },\n clip: true,\n marks: [\n Plot.frame({\n opacity: 0.5,\n stroke: d3.schemeTableau10[2],\n strokeWidth: 2\n }),\n Plot.ruleX([0], { opacity: 0.5 }),\n Plot.ruleY([0], { opacity: 0.5 }),\n ...points.map((point, i) =>\n Plot.line(\n build_samples(\n (theta) =>\n point.x * Math.cos((theta * Math.PI) / 180) +\n point.y * Math.sin((theta * Math.PI) / 180),\n 0,\n 180,\n { N: 50 }\n ),\n {\n stroke: d3.schemeTableau10[i]\n }\n )\n ),\n Plot.tip([md`**theta**: ${theta}\\n**r**: ${rho}`], { x: theta, y: rho }),\n Plot.dot([[theta, rho]], { fill: \"black\" })\n ]\n });\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":685,"value":"houghPlotComplex = () =>\n Plot.plot({\n height: 630,\n x: { domain: [-5, 180], label: \"theta\" },\n y: { domain: [-12, 12], label: \"r\" },\n clip: true,\n marks: [\n Plot.frame({\n opacity: 0.5,\n stroke: d3.schemeTableau10[2],\n strokeWidth: 2\n }),\n Plot.ruleX([0], { opacity: 0.5 }),\n Plot.ruleY([0], { opacity: 0.5 }),\n ...complexPoints.map((point, i) =>\n Plot.line(\n build_samples(\n (theta) =>\n point.x * Math.cos((theta * Math.PI) / 180) +\n point.y * Math.sin((theta * Math.PI) / 180),\n 0,\n 180,\n { N: 50 }\n ),\n {\n stroke: \"gray\"\n }\n )\n ),\n Plot.dot(\n complexSlope.map(({ m, b }) => theta_rho(m, b)),\n {\n fill: (_, i) => d3.schemeTableau10[i],\n r: 5,\n tip: { format: { fill: false } }\n }\n )\n ]\n })","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":709,"value":"complexSlope = [\n { m: 0, b: 4, anchor: \"bottom\" },\n { m: 2, b: 8, anchor: \"right\" },\n { m: -2, b: 8, anchor: \"left\" },\n { m: 0, b: -6, anchor: \"top\" }\n]","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":286,"value":"mbPlotComplex = () => {\n const lines = [];\n const mItem = [-10, 10];\n\n complexPoints.forEach((point) => {\n for (let m of mItem) {\n let b = -m * point.x + point.y;\n lines.push({ m, b, label: `Point (${point.x}, ${point.y})` });\n }\n });\n\n return Plot.plot({\n aspectRatio: 1,\n x: { domain: [-10, 10] },\n y: { domain: [-10, 10] },\n clip: true,\n marks: [\n Plot.frame({\n opacity: 0.5,\n stroke: d3.schemeTableau10[1],\n strokeWidth: 2\n }),\n Plot.ruleX([0], { opacity: 0.5 }),\n Plot.ruleY([0], { opacity: 0.5 }),\n Plot.line(lines, {\n x: \"m\",\n y: \"b\",\n stroke: \"gray\",\n strokeWidth: 1,\n tip: true\n }),\n Plot.dot(complexSlope, {\n x: \"m\",\n y: \"b\",\n r: 5,\n fill: (_, i) => d3.schemeTableau10[i],\n tip: { format: { anchor: \"anchor\" } }\n })\n ]\n });\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":388,"value":"cartesianFormat = (text) =>\n html`${text}`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":390,"value":"parameterFormat = (text) =>\n html`${text}`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":551,"value":"houghFormat = (text) =>\n html`${text}`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":586,"value":"import { build_samples } from \"@mcmcclur/adaptive-plotter\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":695,"value":"theta_rho = (m, b) => {\n let theta = (Math.atan(-1 / m) * 180) / Math.PI;\n if (theta < 0) theta += 180;\n const rho = b * Math.sin((theta * Math.PI) / 180);\n return [theta, rho];\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":791,"value":"Plot.plot({\n height: 630,\n width: width,\n x: { domain: [-10, 180], label: \"theta\" },\n y: { domain: [-40, 40], label: \"r\" },\n clip: true,\n marks: [\n Plot.frame({\n opacity: 1,\n stroke: d3.schemeTableau10[2],\n strokeWidth: 2,\n fill: \"black\"\n }),\n Plot.ruleX([0], { opacity: 0.5 }),\n Plot.ruleY([0], { opacity: 0.5 }),\n ...complexSlope\n .flatMap(({ m, b }) =>\n build_samples((x) => m * x + b, -10, 10, { N: 50 }).map((point) =>\n build_samples(\n (theta) =>\n point[0] * Math.cos((theta * Math.PI) / 180) +\n point[1] * Math.sin((theta * Math.PI) / 180),\n -10,\n 180,\n { N: 10 }\n )\n )\n )\n .map((points, i) => Plot.line(points, { stroke: \"white\", opacity: 0.2 }))\n ]\n})","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W34","stdlib":"1","titling":"auto"}} 32:"$31:body"